Connected sensor cover

The connected sensor cover was first studied by Cardei et al. The minimum connected sensor cover problem (Problem 1.3.2) was first proposed by Gupta, Das, and Gu. They presented a greedy algorithm with performance ratio O(rln n) where n is the number of sensors and r is the link radius of the sensor network, i.e., for any two sensors s and s′ with a sensing point in common, there exists a path between s and s′ with hop distance at most r in communication network. Zhang and Hou studied the minimum connected sensor cover problem in homogeneous wireless sensor networks with property that R_c ≥ 2R_s. They showed that in this case, the coverage of a connected target area implies the connectivity. This result was generalized by Zhou, Das, and Gupta to the m-connectivity that if every point in a connected target area is covered by at least m sensors, then those sensors induce an m-connected sensor network. Xing et al. presented a coverage configuration protocol which can give different degree of coverage requested by applications. Bai et al. studied a sensor deployment problem regarding the coverage and connectivity. Alam and Haas studied this problem in three-dimensional sensor networks.