Efficient coverage and connectivity preservation with load balance for wireless sensor networks

One of the primary objectives of wireless sensor networks is to provide full coverage of a sensing field as long as possible. Many tasks - such as object tracking and battlefield intrusion detection - require full coverage at any time. With the limited energy of sensor nodes, organizing these nodes into a maximal number of subgroups (or called set cover) capable of monitoring all discrete points of interest and then alternately activating them is a prevalent way to provide better quality of surveillance. In addition to maximizing the number of subgroups, how to guarantee the connectivity of sensor nodes (i.e., there exist links between the base station (BS) and sensor nodes) is also critically important while achieving full coverage. In this paper, thus, we develop a novel maximum connected load-balancing cover tree (MCLCT) algorithm to achieve full coverage as well as BS-connectivity of each sensing node by dynamically forming load-balanced routing cover trees. Such a task is particularly formulated as a maximum cover tree problem, which has been proved to be nondeterministic polynomial-complete. The proposed MCLCT consists of two components: 1) a coverage-optimizing recursive heuristic for coverage management and 2) a probabilistic load-balancing strategy for routing path determination. Through MCLCT, the burden of nodes in sensing and transmitting can be shared, so energy consumption among nodes becomes more evenly. Extensive simulation results show that our solution outperforms the existing ones in terms of energy efficiency and connectivity maintenance.