Years and Authors of Summarized Original Work
2013; Wu, Du, Wu, Li, Lv, Lee
Problem Definition
Nowadays, the sensor exists everywhere. The wireless sensor network has been studied extensively. In view of this type of networks, there are two most important properties, coverage and connectivity. In fact, the sensor is often used for collecting information, and hence, its sensing area has to cover the target (points or area). Usually, for a wireless sensor, its sensing area is a disk with the center at the sensor. The radius of this disk is called the sensing radius. After information is collected, the sensor has to send to central station for analysis. This requires all active sensors to form a connected communication network. Actually, every sensor has also a communication function, and it can send information to other sensors located in its communication area, which is also a disk with center at the sensor. The radius of the communication disk is called the communication radius.
The...
Recommended Reading
Alam SMN, Haas ZJ (2006) Coverage and connectivity in three-dimensional networks. In: MobiCom’06, Los Angeles
Bai X, Kumar S, Xuan D, Yun Z, Lai TH (2006) DEploying wireless sensors to achieve both coverage and connectivity. In: MobiHoc’06, Florence, pp 131–142
Byrka J, Grandoni F, Rothvoss T, Sanita L (2010) An improved LP-based approximation for Steiner tree. In: STOC’10, Cambridge, 5–8 June, pp 583–592
Ding L, Wu W, Willson JK, Wu L, Lu Z, Lee W (2012) Constant-approximation for target coverage problem in wireless sensor networks. In: Proceedings of the 31st annual joint conference of IEEE communication and computer society (INFOCOM), Miami
Funke S, Kesselman A, Kuhn F, Lotker Z, Segal M (2007) Improved approximation algorithms for connected sensor cover. Wirel Netw 13:153–164
Ghosh A, Das SK (2005) A distributed greedy algorithm for connected sensor cover in dense sensor networks. LNCS 3560:340–353
Ghosh A, Das SK (2006) Coverage and connectivity issues in wireless sensor networks. In: Shorey R, Ananda AL, Chan MC, Ooi WT (eds) Mobile, wireless, and sensor networks: technology, applications, and future directions. Wiley, Hoboken, pp 221–256
Gupta H, Das SR, Gu Q (2003) Connected sensor cover: self-organization of sensor networks for efficient query execution. In: MobiHoc’03, Annapolis, pp 189–200
Mustafa N, Ray S (2009) PTAS for geometric hitting set problems via local search. In: Proceedings of the SoCG 2009, Aarhus, pp 17–22. ACM, New York
Wu L, Du H, Wu W, Li D, Lv J, Lee W (2013) Approximations for minimum connected sensor cover. In: INFOCOM, Turin
**ng G, Wang X, Zhang Y, Liu C, Pless R, Gill C (2005) Integrated coverage and connectivity configuration for energy conservation in sensor networks. ACM Trans Sens Netw 1(1):36–72
Zhang H, Hou JC (2005) Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc Sens Wirel Netw 1:89–124
Zhou Z, Das S, Gupta H (2004) Connected k-coverage problem in sensor networks. In: Proceedings of the 13th international conference on computer communications and networks, Chicago, pp 373–378
Zhou Z, Das SR, Gupta H (2009) Variable radii connected sensor cover in sensor networks. ACM Trans Sens Netw 5(1):1–36
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer Science+Business Media New York
About this entry
Cite this entry
Wu, L., Wu, W. (2014). Minimum Connected Sensor Cover. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA. https://doi.org/10.1007/978-3-642-27848-8_616-1
Download citation
DOI: https://doi.org/10.1007/978-3-642-27848-8_616-1
Received:
Accepted:
Published:
Publisher Name: Springer, Boston, MA
Online ISBN: 978-3-642-27848-8
eBook Packages: Springer Reference Computer SciencesReference Module Computer Science and Engineering