An adaptive clustering algorithm based on grades for wireless sensor networks

doi:10.11772/j.issn.1001-9081.2017.06.1532

Abstract

Abstract: To solve the short life time and low network throughput problems caused by the heterogeneity and mobility of Wireless Sensor Network (WSN) clustering algorithm, an Adaptive Clustering Algorithm based on Grades (ACA_G) was proposed. The proposed algorithm was run on rounds, which was composed of three stages:the adaptive clustering stage, the cluster construction stage and the data transmission stage. In the adaptive clustering stage, every partition may be subdivided or united adjacently according to the change of the number of nodes in each partition to keep an appropriate number of nodes in it. The adaptive clustering measure could be able to solve the unreasonable problems of the number of cluster-heads and the scale of clusters caused by the node mobility in WSN. In order to deal with the phenomena of some nodes died too fast and the life time of WSN was shortened caused by the heterogeneity in WSN, the node with the highest grade was selected as the cluster-head in the cluster construction stage. In the WSN application, the grade of each node was calculated according to the node residual energy, the speed of energy consumption, the distance between the node and the base station, the accumulated distance between the node and other nodes in the same cluster. The experiment was simulated by OMNeT++ and Matlab on a WSN with energy heterogeneity, in which node's mobile speed is 0~0.6 m/s randomly. The experimental results show that, compared with the Low Energy Adaptive Clustering Hierarchy -Mobile (LEACH-Mobile) algorithm and the Distributed Energy-Efficient Clustering (DEEC) algorithm, the life time of WSN clustered by the proposed algorithm is 30.9% longer than the other two algorithms, its network throughout is 1.15 times at least as much as the other two algorithms.

Key words: adaptive clustering, grade, Wireless Sensor Network (WSN), energy heterogeneity, mobility

摘要： 为解决现有无线传感器网络（WSN）分簇算法难以同时兼顾其异构性和移动性，从而引发网络寿命较短、网络数据吞吐量较低等问题，提出了基于节点等级的自适应分簇算法。该算法按轮运行，每轮分为自适应分簇、簇建立、数据传输三个阶段。为解决节点移动性引发的簇首数目和成簇规模不合理的问题，在自适应分簇阶段，根据子区域内节点数目变化对相应子区域进行细化或就近合并，以确保每个子区域内节点数目在合理范围内。在簇建立阶段，选举簇内等级最高的节点为簇首，解决异构性引发的部分节点能耗过快、网络寿命缩短的问题；节点等级除考虑节点剩余能量外，还结合WSN实际应用，由节点剩余能量、能量消耗速率、到基站的距离、到簇内其他节点的距离综合决定。基于OMNeT++和Matlab的仿真实验结果表明，在节点移动速度为0~0.6 m/s的能量异构WSN环境下，较移动低功耗自适应集簇分层（LEACH-Mobile）算法和分布式能量有效分簇（DEEC）算法，运用所提算法分簇的WSN寿命延长了30.9%以上，网络数据吞吐量是其他两种算法分簇的网络的1.15倍以上。

关键词: 自适应分簇, 等级, 无线传感器网络, 能量异构, 移动性

CLC Number:

TP393.0

XIAO Wei, TU Yaqing. An adaptive clustering algorithm based on grades for wireless sensor networks[J]. Journal of Computer Applications, 2017, 37(6): 1532-1538.

肖玮, 涂亚庆. 基于等级的无线传感网自适应分簇算法[J]. 计算机应用, 2017, 37(6): 1532-1538.

References

[1] DONG M, OTA K, LIU A. RMER:reliable and energy-efficient data collection for large-scale wireless sensor networks[J]. IEEE Internet of Things Journal, 2016, 3(4):511-519.
[2] 赵海军,崔梦天,李明东,等.基于改进的洪泛广播和粒子滤波的无线传感器网络节点定位[J].计算机应用,2016,36(10):2659-2663.(ZHAO H J, CUI M T, LI M D, et al. Node localization based on improved flooding broadcast and particle filtering in wireless sensor network[J]. Journal of Computer Applications, 2016, 36(10):2659-2663.)
[3] MANN P S, SINGH S. Improved metaheuristic based energy-efficient clustering protocol for wireless sensor networks[J]. Engineering Applications of Artificial Intelligence, 2017, 57:142-152.
[4] 苏金树,郭文忠,余朝龙,等.负载均衡感知的无线传感器网络容错分簇算法[J].计算机学报,2014,37(2):445-456.(SU J S, GUO W Z, YU C L, et al. Fault-tolerance clustering algorithm with load-balance aware in wireless sensor network[J]. Chinese Journal of Computers, 2014, 37(2):445-456.)
[5] HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//HICSS'00:Proceedings of the 33rd Hawaii International Conference on System Sciences. Washington, DC:IEEE Computer Society, 2000, 8:8020.
[6] LINDSEY S, RAGHAVENDRA C S. PEGASIS:power-efficient gathering in sensor information systems[C]//Proceeding of the 2002 IEEE Aerospace Conference. Piscataway, NJ:IEEE, 2002:1125-1130.
[7] GURRUTXAGA I, ALBISUA I, ARBELAITZ O, et al. SEP/COP:an efficient method to find the best partition in hierarchical clustering based on a new cluster validity index[J]. Pattern Recognition, 2010, 43(10):3364-3373.
[8] ASLAM M, MUNIR E U, RAFIQUE M M, et al. Adaptive energy-efficient clustering path planning routing protocols for heterogeneous wireless sensor networks[J]. Sustainable Computing:Informatics and Systems, 2016, 12:57-71.
[9] SINGH S, MALIK A, KUMAR R. Energy efficient heterogeneous DEEC protocol for enhancing lifetime in WSNs[J]. Engineering Science and Technology, an International Journal, 2017, 20(1):345-353.
[10] GUPTA V, PANDEY R. An improved energy aware distributed unequal clustering protocol for heterogeneous wireless sensor networks[J]. Engineering Science and Technology, an International Journal, 2016, 19(2):1050-1058.
[11] KIM D S, CHUNG Y J. Self-organization routing protocol supporting mobile nodes for wireless sensor network[C]//IMSCCS'06:Proceedings of the 2006 First International Multi-Symposiums on Computer and Computational Sciences. Piscataway, NJ:IEEE, 2006:622-626.
[12] AMINE D, NASSREDDINE B, BOUABDELLAH K. Energy efficient and safe weighted clustering algorithm for mobile wireless sensor networks[J]. Procedia Computer Science, 2014, 34:63-70.
[13] AMINE D, NASR-EDDINE B, ABDELHAMID L. A distributed and safe weighted clustering algorithm for mobile wireless sensor networks[J].Procedia Computer Science, 2015, 52(34):641-646.
[14] ZHANG D-G, ZHU Y-N, ZHAO C-P, et al. A new constructing approach for a weighted topology of wireless sensor networks based on local-world theory for the Internet of Things (IOT)[J]. Computer and Mathematics with Applications, 2012, 64(5):1044-1055.
[15] ZORZI M, GLUHAK A, LANGE S, et al. From today's INTRAnet of things to a future INTERnet of things:a wireless-and mobility-related view[J]. IEEE Wireless Communications, 2010, 17(6):44-51.
[16] 肖竹,王东,李仁发,等.物联网定位与位置感知研究[J].中国科学:信息科学,2013,43(10):1265-1287.(XIAO Z, WANG D, LI R F, et al. Localization and nodes location-aware in Internet of things[J]. SCIENTIA SINICA Informationis, 2013, 43(10):1265-1287.
[17] MANZOOR B, JAVAID N, REHMAN O, et al. Q-LEACH:a new routing protocol for WSNs[J]. Procedia Computer Science, 2013, 19:926-931.
[18] 沈永增,陈宣扬,贾莲莲.一种事件驱动型无线传感器网络的分层路由算法[J].计算机系统应用,2011,20(8):81-85.(SHEN Y Z, CHEN X Y, JIA L L. Hierarchical routing algorithm in event-driven wireless sensor networks[J]. Computer Systems & Applications, 2011, 20(8):81-85.)
[19] 唐加山,王燕.无线传感器网络中改进的EEUC路由协议[J].重庆邮电大学学报:自然科学版,2013,25(2):172-177.(TANG J S, WANG Y. Improved EEUC routing protocol for wireless sensor networks[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2013, 25(2):172-177.)
[20] KUMAR D, ASERI T C, PATEL R B. EEHC:energy efficient heterogeneous clustered scheme for wireless sensor networks[J]. Computer Communications, 2009, 32(4):662-667.
[21] SILVA R T, COLLETTI R R, PIMENTEL C, et al. BETA random waypoint mobility model for wireless network simulation[J]. Ad Hoc Networks, 2016, 48:93-100.