Authors: Ka-Shun Hung, King-Shan Lui
Addresses: Department of Electrical and Electronic Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong. ' Department of Electrical and Electronic Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong
Abstract: One of the major applications of sensor networks is tracking and surveillance. Very often, a single sensor is sufficient to monitor a single target. However, when the object is very large, several sensors have to work together to monitor the object continuously. In this paper, we study how to identify a set of sensors that can cover the perimeter of a large target with the minimum cost. We develop a novel distributed algorithm that requires fewer messages than existing mechanisms. Our algorithm can be extended to solve the problem when the sensor range is adjustable. We provide a formal proof of correctness and convergence time analysis of our algorithm. We further demonstrate the performance through extensive simulations.
Keywords: perimeter coverage; wireless sensor networks; WSNs; minimum cost; circular-arc graphs; distributed algorithms; wireless networks; tracking; surveillance; monitoring; adjustable sensor range; simulation.
International Journal of Sensor Networks, 2011 Vol.9 No.2, pp.76 - 88
Received: 01 Dec 2009
Accepted: 23 Aug 2010
Published online: 01 Mar 2011 *