Providing and findingk‐road‐coverage efficiently in wireless sensor networks
Xufei Mao, Xiaohua Xu, Shaojie Tang, Xiangyang Li · Wireless Communications and Mobile Computing · 2010
ABSTRACT In this paper, we studyk‐road‐coverage problems in wireless sensor networks (WSNs). Assume there is a 2‐dimensional area Ω with a given road map = (V,E) whereEcontains all road segments andVconsists 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 isk‐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 wherek = 1 and O(k) generally. If sensors can be deployed in arbitrary locations, we propose an efficient method with the approximation ratio 24 + ϵ whenk = 1 and O(k) generally. The second question we study is about ‘path query’,i.e., how to find thek‐covered path ork‐support path connecting any given source/destination pair of points on the road map . Basically, given any source/destination pair of pointsSandD, we present two algorithms which can efficiently find ak‐covered path connectingSandDand ak‐supported path connectingSandD, respectively. Copyright © 2010 John Wiley & Sons, Ltd.