| Abstract: | 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  = (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 k = 1 and O(k) generally. If sensors can be deployed in arbitrary locations, we propose an efficient method with the approximation ratio 24 + ϵ when k = 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. Copyright © 2010 John Wiley & Sons, Ltd. |
