Providing and finding k-road-coverage efficiently in wireless sensor networks

In this paper, we study k-road-coverage problems in wireless sensor networks (WSNs). Assume there is a 2-dimensional area ω with a given road map R=(V,E) where E contains all road segments and V consists of all intersection points on ω. The first question we study is about 'sensor deployment', i.e., how to deploy a minimum number of sensor nodes on ω such that each path (each road segment) on is k-covered when all sensor nodes have the same sensing range. When sensors can only be deployed in a set of discrete locations, we propose an efficient method with the approximation ratio 6 + ∈ for the special case where kR= 1 and O(k) generally. If sensors can be deployed in arbitrary locations, we propose an efficient method with the approximation ratio 24 + ∈ when kR= 1 and O(k) generally. The second question we study is about 'path query', i.e., how to find the k-covered path or k-support path connecting any given source/destination pair of points on the road map. Basically, given any source/destination pair of points S and D, we present two algorithms which can efficiently find a k-covered path connecting S and D and a k-supported path connecting S and D, respectively.