Approximation Algorithms for Road Coverage Using Wireless Sensor Networks for Moving Objects Monitoring.

Coverage problem in wireless sensor networks measures how well a region orparts of it is sensed by the deployed sensors. Definition of coverage metricdepends on its applications for which sensors are deployed. In this paper, weintroduce a new quality control metric/measure called road coverage. It will beused for measuring efficiency of a sensor network, which is deployed fortracking moving/mobile objects in a road network. A road segment is a sub-partof a road network. A road segment is said to be road covered if an objecttravels through the entire road segment then it must be detected somewhere onthe road segment by a sensor. First, we propose different definitions of roadcoverage metrics. Thereafter, algorithms are proposed to measure those proposedroad coverage metrics. It is shown that the problem of deploying minimum numberof sensors to road cover a set of road segments is NP-hard. Constant factorapproximation algorithms are proposed for road covering axis-parallel roadsegments. Experimental performance analysis of our algorithms are evaluatedthrough simulations.