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

Chia Pang Chen, Subhas Chandra Mukhopadhyay, Cheng Long Chuang, Maw Yang Liu, Joe Air Jiang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

77 Citations (Scopus)


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.

Original languageEnglish
Article number2336257
Pages (from-to)48-62
Number of pages15
JournalIEEE Sensors Journal
Issue number1
Publication statusPublished - 1 Jan 2015
Externally publishedYes


Dive into the research topics of 'Efficient coverage and connectivity preservation with load balance for wireless sensor networks'. Together they form a unique fingerprint.

Cite this