Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'05)
A Simulated Annealing Algorithm for Energy-Efficient Sensor Network Design
Riva del Garda, Trentino, Italy
April 04-April 06
ISBN: 0-7695-2267-X
In this paper, we develop an algorithm to deploy an energy efficient sensor network such that it provides surveillance and target-positioning services. We consider to place K independent sets of sensors on a sensor field. These sets monitor the field in turn and work together when intrusion events occur. The life-time of the sensor network is therefore prolonged up to K times. The problem is therefore a variant of the set K-cover problem, which is NP-complete. We formulate such sensor deployment problem as a 0/1 integer programming problem. A Simulated Annealing based heuristic then is proposed for solving the optimization problem. The experimental results show that the proposed algorithm indicates a significant improvement in the sensor lifetime compared to the intuitive approach. Furthermore, the proposed algorithm is highly effective and efficient in terms of the overall deployment cost.
Citation:
Frank Y. S. Lin, P. L. Chiu, "A Simulated Annealing Algorithm for Energy-Efficient Sensor Network Design," wiopt, pp.183-189, Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt'05), 2005