Title :
A simulated annealing algorithm for energy-efficient sensor network design
Author :
Lin, Frank Y S ; Chiu, P.L.
Author_Institution :
Dept. of Inf. Manage., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
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 lifetime 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.
Keywords :
integer programming; simulated annealing; wireless sensor networks; energy-efficient sensor network design; integer programming; optimization problem; simulated annealing algorithm; target-positioning service; Algorithm design and analysis; Communications technology; Cost function; Energy efficiency; Information management; Linear programming; Monitoring; Simulated annealing; Surveillance; Wireless sensor networks;
Conference_Titel :
Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, 2005. WIOPT 2005. Third International Symposium on
Print_ISBN :
0-7695-2267-X
DOI :
10.1109/WIOPT.2005.7