archives

On Discovering Sensing Coverage Holes in Large-Scale Sensor Networks


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

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

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: ssg@cs.iastate.edu