An energy-aware multilevel clustering algorithm for wireless sensor networks

Clustering sensors nodes as the basic of routing is an efficient mechanism for prolonging the lifetime of wireless sensor networks. In this paper, the high-efficient multilevel clustering is abstracted as a root tree which has the performances of the minimal relay set and the maximal weight according to graph theory. A mathematical model for the clustering virtual backbone is built. Based on the model, an algorithm called energy-aware multilevel clustering (EAMC) is proposed. The EAMC can reduce the number of relays used for data transmission by minimizing the amount of the nodes in the root tree (that is cluster-head). Furthermore, the algorithm combining with periodical rotation of cluster-heads, enable the energy load be evenly distributed among all the sensors in the network. The maintenance and update for EAMC algorithm is also presented in this paper. Simulation results demonstrate that the proposed approaches significantly increase the lifetime of the sensor network.