Title: Optimal sensor placement with signal propagation effects and inhomogeneous coverage preferences
Authors: Sergey N. Vecherin, D. Keith Wilson, Chris L. Pettit
Addresses: US Army Cold Region Research & Engineering Laboratory, Hanover, NH 03755, USA. ' US Army Cold Region Research & Engineering Laboratory, Hanover, NH 03755, USA. ' US Naval Academy, Aerospace Engineering Department, Annapolis, MD 21402, USA
Abstract: The optimal sensor placement problem consists of determining the number, types, and locations of sensors satisfying inhomogeneous coverage requirements while minimising a specified cost function. The cost function can reflect various factors such as the actual cost of the sensors, their total number, and energy consumption. A strict and general formulation of the problem is described here for sensors characterised by probability of detection at some specified probability of false alarm. The formulation includes non-uniform coverage preferences and realistic, non-line-of-sight detection accounting on signal propagation effects. The optimisation is expressed as a solution to a binary linear programming problem. While exact solution of this problem is typically prohibitive, a fast greedy algorithm is presented that yields a near-optimal solution. It can also be successfully applied to improve coverage of an existing sensor network. This approach compares very favourably to an alternative heuristic strategy based on placing sensors one-by-one in the previously worst-covered location.
Keywords: binary linear programming; optimal sensor configuration; sensor placement; wireless sensor networks; WSNs; sensor location optimisation; distributed sensor networks; wireless networks; inhomogeneous coverage; false alarms.
International Journal of Sensor Networks, 2011 Vol.9 No.2, pp.107 - 120
Accepted: 10 Oct 2010
Published online: 01 Mar 2011 *