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 O with a given road map ?=?(V,E) where E contains all road segments and V consists of all intersection points on O. The first question we study is about sensor deployment, i.e., how to deploy a minimum number of sensor nodes on O 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 (C) 2010 John Wiley & Sons, Ltd.
wireless sensor networks path query k-support k-coverage