Journal of Computer Research and Development (计算机研究与发展) 2009/2009:12 PP.2044-2052

An Distributed and Directed Clustering Algorithm Based on Load Balance for Wireless Sensor Network

Clustering routing protocol for wireless sensor network (WSN) have been growing in recent years. In view of the load balance problem during network clustering for WSN, a distributed and directed clustering algorithm based on load balance is proposed (DDC). In DDC, the pre-evaluation factors which are used for pre-evaluating the energy level and load ability for each node in the next round are presented. During the clustering per round, the whole network is firstly divided into appropriate subareas by the energy pre-evaluation factor, and then the cluster head of each subarea is selected according to the load balance pre-evaluation factor. DDC effectively ensures that the network energy consumption can be decentralized uniformly to every subarea, and that the load for each node in subarea can be balanced. Those characteristics of DDC can organically combine the network energy with the load of node so as to prolong the lifetime of WSN to the greatest extent. The simulation experiments demonstrate that DDC significantly outperforms some similar algorithms such as LEAH and DCHS in terms of energy efficiency, and the load of each node in WSN is more balanced. In the energy-heterogeneous network environments, DDC still has very good adaptability and expandability.

Key words:wireless sensor network (WSN),clustering algorithm,load balance,energy efficiency,pre-evaluation factor

ReleaseDate:2014-07-21 15:00:24

[1] Akyildiz I F, Su W, Sankarasubramaniam Y, et al. Wireless sensor networks: A survey [J]. Computer Networks, 2002, 38(4): 393-422

[2] Cui Li, Ju Hailing, Miao Yong, et al. Overview of wireless sensor network [J]. Journal of Computer Research and Development, 2005, 42(1): 163-174 (in Chinese)(崔莉, 鞠海玲, 苗勇, 等. 无线传感器网络研究进展 [J]. 计算机研究与发展, 2005, 42(1): 163-174)

[3] Li Fangmin, Xu Wenjun, Liu Xinhua, et al. A real-time energy-aware cluster-based routing protocol for wireless sensor and actor networks [J]. Journal of Computer Research and Development, 2008, 45(1): 26-33 (in Chinese)(李方敏, 徐文君, 刘新华. 等. 无线传感器执行器网络中能量有效的实时分簇路由协议 [J]. 计算机研究与发展, 2008, 45(1): 26-33)

[4] Li Fangmin, Liu Xinhua, Kuang Hailan, et al. Research on a stable clustering algorithm based on the optimal connectivity power for wireless sensor network [J]. Journal on Communications, 2008, 30(3): 75-83 (in Chinese)(李方敏, 刘新华, 旷海兰, 等. 基于最优连通功率的无线传感器网络稳定成簇算法 [J]. 通信学报, 2008, 30(3): 75-83)

[5] Heinzelman W, Chandrakasan A, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Trans on Wireless Communications, 2002, 1(4): 660-670

[6] Manjeshwar A, Grawal D P. TEEN: A protocol for enhanced efficiency in wireless sensor network [C]//Proc of the 15th Parallel and Distributed Processing Symp. Los Alamitos, CA: IEEE Computer Society, 2001: 2009-2015

[7] Younis O, Fahmy S. HEED: A hybrid, energy-efficient, distributed clustering approach for ad-hoc sensor networks [J]. IEEE Trans on Mobile Computing, 2004, 3(4): 660-669

[8] Handy M J, Haase M, Timmermann D. Low energy adaptive clustering hierarchy with deterministic cluster-head selection[C]//Proc of the 4th IEEE Conf on Mobile and Wireless Communications Networks. Piscataway, NJ: IEEE, 2002: 368-372

[9] Lindsey S, Raghavenda C S. PEGASIS: Power efficient gathering in sensor information systems [C]//Proc of the IEEE Aerospace Conf. Piscataway, NJ: IEEE, 2002: 1125-1130

[10] Tillapart P, Thumthawatworn T, Pakdeepinit P, et al. Method for cluster heads selection in wireless sensor network [C] //Proc of the 2004 IEEE Aerospace Conf. Piscataway, NJ: IEEE, 2004: 3615-3623

[11] Smaragdakis G, Matta I, Bestavros A. SEP: A stable election protocol for clustered heterogeneous wireless sensor network [C/OL]//Proc of the 2nd Int Workshop on Sensor and Actor Network Protocols and Applications. [2004-08-22]. http:

[12] Qing Li, Zhu Qingxin, Wang Mingwen. A distributed energy-efficient clustering algorithm for heterogeneous wireless sensor network [J]. Journal of Software, 2006, 17(3): 481-489 (in Chinese)(卿利, 朱清新, 王明文. 异构传感器网络的分布式能量有效成簇算法 [J]. 软件学报, 2006, 17(3): 481-489)