Distributed Coverage-Preserving Routing Algorithm for Wireless Sensor Networks

In most of the applications of wireless sensor networks(WSN), covering the area of interest and delivering the sensed information to the sink are two fundamental functions. Extensive research associated with these two issues, such as energy efficient coverage and delay-constraint routing, can be found in the literature. However, few works combine these two issues together. Considering the fact that wireless sensors can take the responsibility of both sensing and routing, it is expected that a solution jointly considering these two issues will provide more benefit. In this paper, we consider the problem: how to find a routing path in a WSN with the maximum sensing coverage provided by the nodes on the path subject to the delay constraint. We first proved that this problem is NP-hard and then proposed a distributed algorithm based on Monte-Carlo integration method and label setting(LS) algorithm. Analysis and simulation results show that under the same time delay constraint, the proposed algorithm can find a routing path with significantly larger sensing coverage (more than 87% in our simulation) than that was obtained considering only hop constraint.