Delaunay based two-phase algorithm for connected cover in WSNs

摘要

Monitoring applications are one of the main usages of wireless sensor networks, where the sensor nodes are responsible to report any event of interest in the monitoring area. Due to their limited energy storage, the nodes are prone to fail, which may lead to network partitioning problem. To cope with this problem, the number of deployed sensor nodes in an area is more than the required quantity. The challenge is to turn on a minimal number of nodes to preserve network connectivity and area coverage. In this paper, we apply computational geometry techniques to introduce a new 2-phase algorithm, called Delaunay Based Connected Cover (DBCC), to find a connected cover in an omnidirectional wireless sensor network. In the first phase, the Delaunay triangulation of all sensors is computed and a minimal number of sensors is selected to ensure the coverage of the region. In the second phase, connectivity of the nodes is ensured. The devised method is simulated by NS2 and is compared with two well-known algorithms, CCP and OGDC. For the case, where the communication and the coverage radii are equal, our method requires 23% and 45% fewer nodes compared to the aforementioned methods, respectively. In the second simulation case, the communication radius is set to 1.5 times of the coverage radius. The results demonstrate that DBCC chooses 14% and 34% fewer nodes, respectively.