Perimeter coverage made practical in wireless sensor networks

Many sensor network applications require the tracking and the surveillance of target objects. However, it is generally assumed that the whole target object can be monitored by a sensor in case the target falls within its sensing range. Unfortunately, this assumption may not be realistic in case the target object is a large one, and each sensor can only monitored a certain portion of the perimeter of the target object. The coverage problem which aims at monitoring the whole perimeter of the target object is known as perimeter coverage problem. Previously, we have developed distributed algorithms to find the minimum set of sensors and the set of sensors with the minimum cost to monitor the target. Unfortunately, no known polynomial time optimal solution exists in a practical scenario. Hence, our previously proposed algorithms failed to find the optimal solutions anymore. In this paper, we show that by modifying our previously proposed algorithms, approximation solutions to these problems are found.