Title: Improved n 1-cover discovery using perimeter coverage information

Authors: James C. Beyer, David H.C. Du, Ewa Kusmierek

Addresses: Department of Computer Science and Engineering, Digital Technology Center, University of Minnesota, Minneapolis, MN 55455, USA. ' Department of Computer Science and Engineering, Digital Technology Center, University of Minnesota, Minneapolis, MN 55455, USA. ' Pozna'n Supercomputing and Networking Center, ul. Z. Noskowskiego 12/14, Pozna'n 61-704, Poland

Abstract: Over-deploying sensors into a coverage region allows for coverage guarantees in the face of random deployments. Extending the lifetime of these deployments by only turning on a handful of sensors that cover the entire region is a viable means of conserving energy. In order to maximally extend the life of a sensor network, several problems must be solved. These are: the 1-cover, the k-cover and n 1-covers. The 1-cover and k-cover problems have been solved previously; however, the n 1-cover problem has proven more difficult to address. We present a perimeter-centric approach to the NP-complete n 1-covers problem, which chooses neighbours based on an optimal disk placement theory, but takes practical constraints into consideration. Simulation results have shown that our system outperforms both the critical field selection algorithm and an n 1-cover selection algorithm derived from Zhang and Hou|s OGDC algorithm.

Keywords: perimeter coverage; n 1-covers; self-organisation; power-saving; scheduling; sensor deployment; sensor networks; simulation.

DOI: 10.1504/IJSNET.2008.018480

International Journal of Sensor Networks, 2008 Vol.3 No.3, pp.175 - 190

Published online: 25 May 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article