Wireless Sensor Networks Coverage Problem

During the recent twenty years, wireless sensor networks (WSNs) have received swift evolution, which benefits from the features of low cost, low-power dissipation, and self-organization. In such a network, the number of sensors deployed is far more than the quantity to full cover the whole target area to avoid the interruption of application tasks resulted from energy exhaust or physical damage. It is crucial to design an algorithm which reduces the number of working sensors while guaranteeing the quality of coverage service. Coverage capability has become one of the important service indicate provided by wireless sensor networks. Studying the coverage problem has both theoretical significance and practical values.Based on the analysis and summary of the existing literatures, this thesis addresses optimal coverage problem under graph model. And two cover set construction algorithms are proposed, one is a coverage contribution area-based algorithm for area coverage problem and the other one is an algorithm for target coverage problem in heterogeneous networks under convex sensing and communication model, the correctness of which is proved. Finally, the corresponding simulations and data comparisons’verify the effectiveness of both algorithms.There are five chapters in this thesis. In the first one, an introduction of wireless sensor network, applications in great demand, the background of the topic researched here and its significance is presented. In the second chapter, both two popular and common used sensing models and the analysis and conclusion of literatures on coverage problem are detailed. Coverage contribution area-based centralized and distributed algorithms are proposed in chapter three. In this chapter, coverage contribution area is guaranteed to be exist for width constrained area, Basing on which one lower bound on the working sensor nodes density for the fully coverage of targeted area is deducted. For the centralized algorithms (both SCRT-PCAk and DCRT-PCAk), the whole targeted area is divided into overlapping reuleaux triangles. According to the information of both the reuleaux triangles and sensors deployed, the sink selects sensors located in the coverage contribution area of the reuleaux triangle to the fully coverage of it. After all the reuleaux triangles being handled, the whole area is guaranteed to be fully covered. The second version of centralized algorithm updates the effective area covered by one sensor. And sensors with larger size of the effective area have priority to be selected into cover set. The resulted cover set is optimal. In the distributed algorithm, the whole sensing disk will be divided into overlapping reuleaux triangles. Sensors in coverage contribution area of each triangle will be selected into coverage set to the fully coverage of each triangle. And connectivity is considered at the same time, once the construction of cover set finished, redandent nodes check whether each pair of neighboring working sensors can communicate with each other directly. If the answer is no, more nodes will join into cover set to build a connected network.In chapter forth, target coverage problem is addressed. Both irregular convex sensing and irregular convex communication model are taken into consideration for the construction of targets coverage sets. The irregularity makes it difficulty to design coverage algorithm. Thus, the largest enclosed disk is introduced to simplify both sensing and communication model. The radius of the largest enclosed disk of convex sensing area is treated as the sensing radius and so does the communication radius. Thus, the design complexity of coverage algorithm is reduced. When selecting another node into cover set, these nodes with more remaining energy, sensing more targets, and sensing more uncovered targets have priorities. Theoretical analysis shows that the cover set generated by the proposed algorithm can fully cover all targets, and the resulted network is connected. At the same time, the simulation verifies the theoretical analysis. The last chapter concludes this thesis.