A memetic algorithm for extending wireless sensor network lifetime

Extending the lifetime during which a wireless sensor network (WSN) can cover all targets is a key issue in WSN applications such as surveillance. One effective method is to partition the collection of sensors into several covers, each of which must include all targets, and then to activate these covers one by one. Therefore, more covers enable longer lifetime. The problem of finding the maximum number of covers has been modeled as the SET K-COVER problem, which has been proven to be NP-complete. This study proposes a memetic algorithm to solve this problem. The memetic algorithm utilizes the Darwinian evolutionary scheme and Lamarckian local enhancement to search for optima given the considerations of global exploration and local exploitation. Additionally, the proposed algorithm does not require an upper bound or any assumption about the maximum number of covers. The simulation results on numerous problem instances confirm that the algorithm significantly outperforms several heuristic and evolutionary algorithms in terms of solution quality, which demonstrate the effectiveness of the proposed algorithm in extending WSN lifetime. (C) 2010 Elsevier Inc. All rights reserved.