A Mathematical Model and a Heuristic for the Maximum Disjoint Set Covers Problem to Improve the Lifetime of the Wireless Sensor Network

 

Namsu Ahn and Sungsoo Park

 

ABSTRACT

 

One of the critical issues in wireless sensor network is the lifetime of the network. Since each sensor is equipped with a limited amount of battery capacity, efficient management of the battery powers is important to prolong the lifetime of the network. One possible network management scheme is to partition the sensors into disjoint sets, so that sensors in each of the disjoint sets can completely cover the targets. Then these sets are activated successively. As a result, the larger the number of disjoint sets, the longer the lifetime of the network. In this paper, we propose a new mathematical formulation to find a maximum number of such disjoint sets. Compared with the previous formulation, our formulation is smaller, and extensive computational experiments performed show that our formulation may be used to find an optimal solution much faster than the previous formulation. Also, we suggest a new heuristic algorithm to find the disjoint sets and computational results show that our algorithm is capable of finding good quality solutions quite fast.

 

KEYWORDS: wireless sensor network, maximum disjoint set covers, mathematical model, integer programming

 

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 : sspark@kaist.ac.kr