DocumentCode :
2699698
Title :
Connected K-coverage problem in sensor networks
Author :
Zhou, Zongheng ; Das, Samir ; Gupta, Himanshu
Author_Institution :
Dept. of Comput. Sci., SUNY, Stony Brook, NY
fYear :
2004
fDate :
11-13 Oct. 2004
Firstpage :
373
Lastpage :
378
Abstract :
In overdeployed sensor networks, one approach to conserve energy is to keep only a small subset of sensors active at any instant. In this article, we consider the problem of selecting a minimum size connected K-cover, which is defined as a set of sensors M such that each point in the sensor network is "covered" by at least K different sensors in M, and the communication graph induced by M is connected. For the above optimization problem, we design a centralized approximation algorithm that delivers a near-optimal (within a factor of O(lg n)) solution, and present a distributed version of the algorithm. We also present a communication-efficient localized distributed algorithm which is empirically shown to perform well
Keywords :
computational complexity; distributed algorithms; optimisation; wireless sensor networks; centralized approximation algorithm; communication graph; communication-efficient localized distributed algorithm; least K different sensor; minimum size connected K-cover; sensor network; Algorithm design and analysis; Approximation algorithms; Computer science; Design optimization; Distributed algorithms; Intelligent networks; Monitoring; Sensor phenomena and characterization; Signal processing algorithms; Wireless sensor networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Communications and Networks, 2004. ICCCN 2004. Proceedings. 13th International Conference on
Conference_Location :
Chicago, IL
ISSN :
1095-2055
Print_ISBN :
0-7803-8814-3
Type :
conf
DOI :
10.1109/ICCCN.2004.1401672
Filename :
1401672
Link To Document :
بازگشت