A New Mathematical Formulation and a Heuristic for the Maximum Disjoint Set Covers Problem to Improve the Lifetime of the Wireless Sensor Network
Namsu Ahn and Sungsoo Park
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 BIP formulation and a new heuristic algorithm to find such disjoint sets. Compared with the previous researches, our formulation may be used to find an optimal solution much faster than the previous formulation and our heuristic is capable of finding good quality solutions quite fast.
Keywords: Wireless sensor network, network lifetime, maximum disjoint set covers, mathematical formulation, heuristic