A New Energy Efficient Clustering Algorithm Based on Routing Spanning Tree for Wireless Sensor Network

Yating GAO  Guixia KANG  Jianming CHENG  Ningbo ZHANG  

IEICE TRANSACTIONS on Communications   Vol.E100-B   No.12   pp.2110-2120
Publication Date: 2017/12/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.2016EBP3487
Type of Manuscript: PAPER
Category: Network
wireless sensor network,  clustering algorithm,  routing spanning tree,  network lifetime,  energy balance,  

Full Text: PDF(2.1MB)
>>Buy this Article

Wireless sensor networks usually deploy sensor nodes with limited energy resources in unattended environments so that people have difficulty in replacing or recharging the depleted devices. In order to balance the energy dissipation and prolong the network lifetime, this paper proposes a routing spanning tree-based clustering algorithm (RSTCA) which uses routing spanning tree to analyze clustering. In this study, the proposed scheme consists of three phases: setup phase, cluster head (CH) selection phase and steady phase. In the setup phase, several clusters are formed by adopting the K-means algorithm to balance network load on the basis of geographic location, which solves the randomness problem in traditional distributed clustering algorithm. Meanwhile, a conditional inter-cluster data traffic routing strategy is created to simplify the networks into subsystems. For the CH selection phase, a novel CH selection method, where CH is selected by a probability based on the residual energy of each node and its estimated next-time energy consumption as a function of distance, is formulated for optimizing the energy dissipation among the nodes in the same cluster. In the steady phase, an effective modification that counters the boundary node problem by adjusting the data traffic routing is designed. Additionally, by the simulation, the construction procedure of routing spanning tree (RST) and the effect of the three phases are presented. Finally, a comparison is made between the RSTCA and the current distributed clustering protocols such as LEACH and LEACH-DT. The results show that RSTCA outperforms other protocols in terms of network lifetime, energy dissipation and coverage ratio.