Sensor networks have received a lot of research attention recently. A sensor can detect the environment around it. Assuming that a sensor’s detecting ability is omni-directional, we can model the coverage of a sensor as a disk centered at the sensor. The radius of such a disk is determined by the energy level of the sensor. The coverage area of the sensor network is the union of all such disks. It is desirable that the coverage area be as thorough and complete as possible, such that an intruder is detected no matter where he or she hides.

Given two locations S and T, two relevant types of trajectories on the sensor plane are proposed. A maximum breach path from S to T is a path from S to T in which the minimum distance from a point P in the path to the sensor network is maximized. This distance is called the worst-case coverage distance of the network. Similarly, a maximum support path from S to T is a path in which the maximum distance of a point P in the path to the sensor network is minimized. This distance is called the best-case coverage distance of the network.

The best-case and worst-case coverage distances are two measures of the quality of the coverage of a sensor network. How to obtain these two measures in a dynamic sensor network, where old sensors may die, or new sensors may be added, is discussed first. The authors successfully transform these problems into graph connectivity problems. They present two algorithms to maintain low constant approximations on the best-case and worst-case coverage distances. Both algorithms have low update and query costs.

The paper does not consider the actual implementation scenario, where sensors have to communicate by sending data to one another. Frequent transmitting will soon exhaust the energy. The authors’ algorithm requires every sensor to send distance data to one sensor. This will lead to a large number of packets, and great system overhead.