2005 · 45 citations · 40 references
ComputingComputer EngineeringComputer ScienceDistributed SystemsFault ToleranceFault-tolerant SystemsCoverage ControlDistributed Sensor NetworksNetwork ConnectivityNetwork ReliabilitySensor NetworksWireless Sensor NetworksEnergy-efficient Wireless Sensor NetworksFault Tolerance MechanismsFault-tolerant Sensor NetworksNetwork LifetimeNetwork Lifetime OptimizationSensingSensor ModelVoronoi Cells
Abstract — Sensor networks are often deployed in a redundant fashion. In order to prolong the network lifetime, it is desired to choose only a subset of sensors to keep active and put the rest to sleep. In order to provide fault tolerance, this small subset of active sensors should also provide some degree of redundancy. In this paper, we consider the problem of choosing a minimum subset of sensors such that they maintain a required degree of coverage and also form a connected network with a required degree of fault tolerance. In addition, we consider a more general, variable radii sensor model, wherein every sensor can adjust both its sensing and transmission ranges to minimize overall energy consumption in the network. We call this thevariableradiik1-Connected, k2-Cover problem. To address this problem, we propose a distributed and localized Voronoibased algorithm. The approach extends the relative neighborhood graph (RNG) structure to preserve k-connectivity in a graph, and design a distributed technique to inactivate desirable nodes while preserving k-connectivity of the remaining active nodes. We show through extensive simulations that our proposed techniques result in overall energy savings in random sensor networks over a wide range of experimental parameters. I.
40
Computer graphics: principles and practice
Choice Reviews Online · 2013 · 4.7K citations
Coverage problems in wireless ad-hoc sensor networks
Saro Meguerdichian, Farinaz Koushanfar, Miodrag Potkonjak et al. · 2002 · 1.7K citations
Benjie Chen, Kyle Jamieson, Hari Balakrishnan et al. · 2001 · 1.4K citations
Integrated coverage and connectivity configuration in wireless sensor networks
Xiaorui Wang, Guoliang Xing, Yuanfang Zhang et al. · 2003 · 1.3K citations · Full text
Approximation Algorithms for Connected Dominating Sets
Suvajyoti Guha, Samir Khuller · Algorithmica · 1998 · 1.1K citations