An Optimization Algorithm for the Maximum Lifetime Coverage Problem in Wireless Sensor Network

Namsu Ahn and Sungsoo Park




One of the critical issues in the wireless sensor network is the lifetime of the network. Since each sensor is equipped with a limited amount of battery capacity, one of the important design issues is using the energy efficiently. One possible network management scheme is to cluster the sensors into several sets, so that the sensors in each of the sets can completely perform the monitoring task. Then the sensors in one set become active to perform the monitoring task and the rest of the sensors switch to a sleep state to save energy. Therefore, to maximize the lifetime of the network, it is critical to rotate the roles of the active set among the sensors. In this paper, we introduce the maximum lifetime coverage problem that asks for a schedule of the sensors which maximizes the network lifetime and we suggest an optimal algorithm which uses the column generation procedure. For comparison, we implemented both the heuristic proposed earlier and our optimal algorithm for the problem and executed computational experiments. Computational results show that, our algorithm outperforms the heuristic in terms of the obtained network lifetimes, and it found the solutions in a reasonable amount of time.


KEYWORDS: wireless sensor network, maximum lifetime coverage problem, optimal algorithm, integer programming, column generation


Contact Address :

Sungsoo Park, Professor, 
Department of Industrial Engineering 
Korea Advanced Institute of Science and Technology (KAIST) 
373-1 Gusung-Dong, Yusong-Gu, Taejon 305-701, Korea 
PHONE : +82-42-350-3121 
FAX : +82-42-350-3110 
E-mail :