An Estimation of Distribution Algorithm Based Load-Balanced Clustering of Wireless Sensor Networks

Authors:
  • DJDongbin Jiao
    Dongbin Jiao
  • LKLiangjun Ke
    Liangjun Ke
  • WYWeibo Yang
    Weibo Yang
  • JLJing Li
    Jing Li

Abstract
The load-balanced clustering is a most significant problem for WSNs with unequal load of the sensor nodes but it is known to be an NP-hard problem. This paper introduces a new model for the problem in which the objective function is to maximize the overall minimum lifetime of the cluster heads. To solve this model, we propose a novel estimation of distribution algorithm based dynamic clustering approach (EDA-MADCA). In EDA-MADCA, a new vector encoding is introduced for representing a complete clustering solution, and a probability matrix model is constructed to guide the individual search. In addition, EDA-MADCA merges the EDA based exploration and the local search based exploitation within the memetic algorithm (MA) framework. A minimum-lifetime-based local search (MLLS) strategy is presented to avoid invalid search and enhance the local exploitation of the EDA. Experiment results demonstrate that EDA-MADCA can prolong network lifetime, it outperforms the existing DECA algorithm in terms of various performance metrics.