| In last decade, with the in-depth research of related technologies and the advancement in hardware, wireless sensor networks are deployed widely in practice and draw mass attention from a broad range of applications. As fundamental problems in wireless sensor networks, node deployment and coverage control are researched widely. The network deployment scheme significantly impacts the cost of construction of network, the quality of coverage, topology and routing protocols. Especially, it is assumed as a foundation for solving coverage problems. In order to achieve energy efficiency and prolong lifetime, coverage control exploits node redundancy, node scheduling and density controlling with meeting sensing quality requirement. For the purpose of improving energy efficiency, this thesis studies several problems that involve minimum deployment and three coverage issues. The main contributions are:(1) Data are forwarded to sink hop by hop in wireless sensor networks. Due to the characteristics of the gathering data manner, energy consumption is not uniform throughout the task area. As a result, uniform deployment is not efficient in terms of residual energy at the death of network. Therefore, this thesis addresses the minimum node deployment problem with the objectives to sufficing the full coverage and lifetime requirement. To solve the problem, we model the energy consumption for wireless sensor networks first of all. Based on the model, a planed placement and a random deployment are devised: (a) node number descending placement. Inspired by the optimization of triangular lattice, various numbers of sensors are placed at different locations in triangular lattice. The number of sensor placed is dependent on the distance to sink. In other words, more nodes are placed if the location is closer to sink, otherwise fewer, (b) density descending deployment. A critical active density is estimated with coverage requirement in random uniform deployment, and then minimum deploying density is derived for a given lifetime based on the aforementioned critical active density. Roughly speaking, nodes are deployed more intensively for the fraction of task area that is closer to sink, otherwise sparser. Finally, analysis and simulations show that both two descending deployment schemes need fewer nodes than those of uniform deployment manners, waste less energy and obtain higher efficiency.(2) In heterogeneous sensor networks, the heterogeneity is exploited to prolong networking lifetime and improve scalability. For these applications, this thesis proposes and formulates the minimum relay connected set cover (MRCSC) problem which satisfies: (a) full coverage, and (b) relay connectivity, which means any sensing node is connected to at least one heterogeneous node reliably. Because of the NP-hard complexity of MRCSC, we design an approximate two-stage algorithm: (a) finding approximate minimum set cover. Motivated by optimality of triangular lattice in terms of the number of sensor needed, sensing nodes are chosen whose positions are closest to corresponding locations in triangular lattice. However, random deployment makes it difficult to find a sensor at each optimal location always. Thus we derive a principle to constrain the spread of irregularity of sensing node lattice and detail the construction of minimum set cover (MSC), (b) verifying and reinforcing relay connectivity. Two theorems are proven to check whether MSC is relay connected and convert relay connectivity reinforcement to finding a relay connected tree. The reinforcement is implemented via relay connectivity verification and iterative enhancing requests. Simulations evaluate the performance of our algorithm. The coverage provided by MSC is close to that of OGDC, but without angle information of neighbors. The relay connectivity of MRCSC is strongly improved by few additional nodes by relay connectivity reinforcement.(3) To monitor and sense the target flow comprised by numerous continuous arriving targets, we propose a new model of coverage, called proactive coverage that dynamically adapts coverage quality according to the properties of target flow. The basic idea is: all nodes work in low duty cycle monitoring state to save energy if no target flow crossing task area. Nodes are awakened to provide high quality coverage by the intrusion and traveling of target flow. When target flow moves out, the state of nodes returns to monitoring. Therefore, four problems arise and are solved: (a) how to determine the lowest duty cycle? In surveillance, lower duty cycle can save more energy, but for the purpose of without loss of intruding target, the lowest duty is bounded by a specific value, (b) how far the nodes should be awakened? After detecting a target flow, a number of nodes in a range are awakened to sense the flow. The activated sensors should cover most of the trajectory of the target flow, (c) how long the active nodes work? In order to provide undisrupted sensing, activated nodes are expected work a duration where the next target will arrive with high probability. The duration is determined by the interval between the arriving of two contiguous targets, (d) how to determine whether the flow leaves? Nodes should go back to monitoring state to decrease energy consumption at or after the target flow going away. One thing is noticed that misjudgments of target flow leaving are expected as little as possible. Extensive simulations are designed to evaluate proactive coverage. The coverage quality of proactive coverage reaches that of static coverage nearly, especially for large scale target flow. Proactive coverage is more energy efficient and more suitable for sensing target flow.(4) For some sensing devices, their sensing regions are fanlike sectors, instead of nice regular disks. Hence this thesis studies the issue of directional multiple set covers of target sensing, which is NP-hard. The goal is to find maximum number of directional set cover. Considering that the sensing direction of sensors is adjustable, the proposed method works in two phases: (a) working direction optimization. Two schemes are employed to optimize the working directions of sensors. One is enhanced greedy algorithm (EGA) for optimizing. EGA selects working direction for each sensor in consideration of maximum number of its covering uncovered targets. The advantage exhibited by EGA is low computing complexity at cost of unfair assignment of coverage resources. Furthermore, the other, called equitable direction optimization (EDO) is elaborated. EDO exploits utility function to assess the benefit of each direction for total coverage. Utility takes target coverage into account, that is, lower coverage brings greater utility. As a result, the target with lowest coverage is covered prior to others in EDO, (b) node schedule. All nodes are divided into several set covers and total lifetime is into rounds by neighbors sensing scheduling (NSS). NSS schedules each set works for a round, and all sets are activated alternately to prolong lifetime. Making use of local set cover, NSS determines which set will turn to work at the end of each round in terms of remaining energy of each sensor. The selected set starts working at the beginning of the next round. At last, we demonstrate the outperformed performance of our algorithm via simulations. Both EDO and EGA can increase targets'coverage, but the coverage of EDO on average is greater than that of EGA by 30%. Although the performance of NSS is trivially less than centralized Greedy-MSC, the distribution of NSS makes it more practical.In summary, this thesis focuses on node deployment and coverage control problems from the perspective of energy efficiency and presents their solutions. Our research has academic and practical value for advancing the theory and practicability in wireless sensor networks.
|
PDF Full Text Request