On Discovering Sensing Coverage Holes in Large-Scale Sensor Networks







Deposit Papers 


Tong, Bin and Tavanapong, Wallapak (2006) On Discovering Sensing Coverage Holes in Large-Scale Sensor Networks. Technical Report TR 06-03, Computer Science, Iowa State University.

Full text available as:Postscript


Abstract Sensing coverage is one of the key performance indicators of a large-scale sensor network. Sensing coverage holes may appear anywhere in the network field at any time due to random deployment, depletion of sensor battery power, or natural events in the deployment environment such as strong wind blowing some sensors away. Discovering the exact boundaries of coverage holes is important because (i) it facilitates an efficient patching of a sensor network to achieve a 100\% sensing coverage given enough mobile sensors; and (ii) it helps to estimate the values of the sensing data inside the coverage holes provided that the sensing data have certain properties. In this paper, we present two efficient distributed algorithms that periodically discover the exact boundaries of coverage holes. Our algorithms can handle the case that the transmission range of a sensor is smaller than twice the sensing range of the sensor. This case is largely ignored by previous work. We also present rigorous mathematical proofs of the correctness of the proposed algorithms. Our simulation results show that our distributed algorithms are much more efficient than their centralized counterparts in terms of network overhead and total discovery time while still achieving the same correctness in discovering the boundaries of coverage holes.

Keywords:Coverage problems, sensor networks, distributed protocols
Subjects:Computer Systems Organization: COMPUTER-COMMUNICATION NETWORKS: Distributed Systems
ID code:00000413
Deposited by:Wallapak Tavanapong on 24 March 2006

Contact site administrator at: