Topology Control Based On Proximity Graphs In Wireless Sensor Networks

Wireless sensor networks consist of a large member of cheaper small sensors that organize themselves into a multi-hop wireless network without the central control and the infrastructure construction. Sensors have the limited abilities such as the data processing, the memory capacity and the bandwidth of wireless communication. Especially sensors are powered through the battery with the limited energy. Consequently, how to exploit the limited resources to raise the energy efficiency of sensors and prolong the the network lifetime becomes the primary goal of the network design for wirless sensor networks.The topology control is a fundamental problem in wireless sensor networks. Firstly, the topology control is a kind of energy conservation technology, which can improve the energy efficiency of sensors and prolong the network lifetime. Secondly, the topology control deduces the radio interference and the channel competition, which can improve the network communication efficiency. Thirdly, the topology control forms a favorable underlying logical topology for wireless sensor networks, which can improve the efficiency of routing and MAC. Finally, the topology control can also offer help for the data-fusion and the location. In a word, the topology control will influence the performances of wireless sensor networks.This thesis will research the power control, the coverage control and the clustering of wireless sensor networks based on the proximity graphs, aiming at improving the energy efficiency of sensors and prolonging the network lifetime under the condition of meeting service reqirements. The main researchs and the contributions of the thesis are as follows:(1) The Voronoi region ContructionWhen we research the power control and coverage control, the Voronoi tessellation or Delaunay triangulation is firstly used as the underlying logical topology of wireless sensor networks. Thus, the runtime of constructing the Voronoi tessellation or Delaunay triangulation will influence the time performance of the topology control. The Voronoi tessellation and the Delaunay triangulation are two classical proximity graphs for wireless networks, and are dual graphs each other in computational geometry, which can be constructed by the same algorithm. Firstly, we summarize some properties of the Voronoi tessellation and Delaunay triangulation, which can provide the theoretical foundation for the following researches. Sceondly, in order to reduce the runtime of constructing the Voronoi region, we propose an algorithm of incremental construction Voronoi region (ICVR), and an algorithm of decremental construction Voronoi region (DCVR) based on the bound Voronoi tessellation. Meanwhile, we give the implements of ICVR and DCVR in C++, which can offer help for the following simulations.(2) The coverage control based on the Voronoi tessellationIn the real network environment, the coverage hole is a very common phenomenon which can not be ignored. Currently, how to deal with these coverage holes is an unsolved problem in the coverage control of wireless sensor networks based on the Voronoi tessellation. On the hypothesis conditions that wireless sensor networks can only cover partial target area and the communication radius is no less than twice of the sensing radius, we firstly propose a centralized coverage control algorithm based on the Voronoi Tessellation (VTC), then present a distributed coverage control algorithm based on the local Voronoi Tessellation (LVC), whose computational complexities are unconcerned with the density of sensors and scheduling methods use the Voronoi tessellation as the underlying logical topology. The simulation results show that the average number and the coverage-degree of active sensors produced by VTC and LVC are close to that of the other centralized algorithm and smaller than that of the other distributed algorithm, but VTC and LVC have more advantages in terms of the average residual energy of the active sensor, the scheduling astringency and the runtime. Meanwhile, the simulation results also show that there are plenty of redundant sensors when the wireless sensor networks can not cover the whole target area. Therefore, the coverage control considering the coverage hole has the actual value.(3) The power control based on the local Delaunay graphThe unit Delaunay triangulation (UDel), which has the properties such as connectivity, planar, bouded degree and spanner and so on, is an ideal underlying logical topology of the wireless networks, but it can not be locally contructed. We propose a planar sysmetric local Delaunay graph (PSLDel), which is a supergraph of UDel. When PSLDel is used as the underlying logical topology of the wireless sensor networks, each sensor can adjust its transmission power to minimum according to the farthest logical neighbor, which forms a network topology with desirable features, such as connectivity, sparseness, planar and spanner. Theoretic analyses and simulation results show that the performance of PSLDel is close to that of UDel, which is globally constructed, in terms of the physical neighbor and the minimal transmission power, but the distance stretch factor of PSLDel is slightly better than that of UDel. Meanwhile, compared with the other approximate structures of UDel which can be also locally constructed, PSLDel have more advantages on the communication cost and the runtime. The followed properties can improve the energy efficiency and prolong the lifetime of the wireless sensor networks.(4) The power control based on the partial Delaunay graphThe partial Delaunay graphs are subgaphs of UDel. Now, all kinds of existing partial Delaunay graphs have proved not to be or cannot prove to be a spanner, which can not meet the requirement of the network delay. We propose a spanner partial unit Delaunay graph (PUDel) which is also a subgaph of UDel. During locally constructing PUDel, there are no message exchage between nodes, in addition to the maintaining the postion information of neighbors. While the other approximate structures of UDel with spanner have not this advantage. Theoretic analyses and simulation results show that the distance stretch factor of PUDel is close to UDel, but the performances of PUDel are better than UDel in terms of the minimal transmission power and the physical neighbor.In order to further reduce the minimal transmission power and the physical neighbor, we also propose an optimal PUDel (OPUDel), which is a subgaph of PUDel and UDel. OPUDel has still the properties such as connectivity, planar, bouded degree and spanner and so on. Theoretic analyses and simulation results show that the distance stretch factor of OPUDel is greater than that of PUDel and UDel, but the difference between them is very small. Howerver, the performances of OPUDel are better than that of UDel and PUDel in terms of the minimal transmission power and the physical neighbor. Although the communication cost of OPUDel is greater than that of PUDel, it is lower than that of other approximate structures of UDel with spanner.(5) The hierarchial topology control based on the connected dominating setMost of researches on the hierarchical topology have focused on the election mechanism of cluster-heads, but few studies have considered the energy efficiency of the communication mechanism between cluster-heads. We research the topology control of the wireless sensor networks based on the hierarchial proximity graph, and propose a distributed clustering algorithm based on the connected dominating set (HCCDS), whose cluster-heads election mechanisms have considered the residual energy, the initial energy and the degree of the sensors. On the hypothesis conditions that the communication radii are the same between the inter-cluster and the intra-cluster, the cluster-heads can be formed a connected virtual bone network, which can improve the energy effciency of the inter-cluster communication and prolong the network lifetime. Simulation results demonstrate that HCCDS can actually reduce the costs of the intra-cluster communication.