coverage using sensor networks

Long time no post.

Dan Wang, Qlan Zhang, and Jiangchuan Liu give some NP completeness statements for various coverage problems in their paper Self-Protection for Wireless Sensor Networks, which was presented at ICDCS 2006.

Barrier Coverage With Wireless Sensors, a Mobicom 2005 paper by Santosh Kumar, Ten H. Lai, and Anish Arora treats barrier coverage. Paths crossing a region defined by two parallel curves are to be detected by at least k sensors, a possible application could be monitoring the border between two countries. This barrier coverage is weaker than blanket coverage, where all points of a region and not just paths crossing the region have to be covered.
Even though this sounds like a geometric problem suitable for the unit disk model it might not be suitable if k is not 1.
The problem is modeled as a graph: one node for each sensor, edges between sensors if their sensing regions (within the region) overlap, and two additional nodes L (and R) connecting from left (and right) to the geometrically leftmost (rightmost) nodes of the region meaning that following in the direction of the border curve no other node is further left (right) on that very curve. If L and R are k-connected, every crossing path is detected by at least k sensors (therefore this does not work for closed curves).
It is also stated that it cannot be determined locally whether a region satisfies this condition.