Computer Science ›› 2017, Vol. 44 ›› Issue (2): 31-37.doi: 10.11896/j.issn.1002-137X.2017.02.003

Previous Articles     Next Articles

Survey of Clustering Algorithms for Wireless Sensor Networks

XU Jing-jing, ZHANG Xin-hui, XU Bi-xiao and SUN Zhi-xin   

  • Online:2018-11-13 Published:2018-11-13

Abstract: Clustering algorithms are very important in the area of wireless sensor network.On the viewpoint of energy balance and network lifetime,according to whether or not an only central control node is responsible for the whole network,clustering algorithms can be divided into three categories.Some typical clustering algorithms and the latest achievements of recent years were briefly reviewed,and their characteristics and application scope were analyzed.At last,according to the existed study on WSN,some problems worthy of note were mentioned in this paper.Besides,the developing trend and prospects of WSN were predicted.

Key words: Wireless sensor network,Clustering algorithms,Energy balance,Network lifetime

[1] YU J Y,CHONG P H J.A survey of clustering schemes for mobile ad hoc networks[J].Communications Surveys & Tutorials,IEEE,2005,7(1):32-48.
[2] HEINZELMAN W R,CHANDRAKASAN A,BALAKRISH-NAN H.Energy-efficient communication protocol for wireless microsensor networks[C]∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences,2000.IEEE,2000
[3] NAYEBI A,SARBAZ-AZAD H.Performance modeling of the LEACH protocol for mobile wireless sensor networks[J].Journal of Parallel and Distributed Computing,2011,71(6):812-821.
[4] MANJESHWAR A.TEEN:a protocol for enhanced efficiency in wireless sensor networks[C]∥Proc Ipdps Workshops.2001:2009-2015.
[5] SMARAGDAKIS G,MATTA I,BESTAVROS A.SEP:A stable election protocol for clustered heterogeneous wireless sensor networks[C]∥Second International Workshop on Sensor and Actor Network Protocols and Applications (SANPA 2004).2004:1-11.
[6] QING L,ZHU Q,WANG M.Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J].Computer Communications,2006,29(12):2230-2237.
[7] LINDSEY S,RAGHAVENDRA C S.PEGASIS:Power-efficient gathering in sensor information systems[C]∥Aerospace Confe-rence Proceedings,2002.IEEE,2002 :1125-1130
[8] JUNG S M,HAN Y J,CHUNG T M.The concentric clusteringscheme for efficient energy consumption in the PEGASIS[C]∥The 9th International Conference on Advanced Communication Technology.IEEE,2007:260-265.
[9] FANG Q,ZHAO F,GUIBAS L.Lightweight sensing and communication protocols for target enumeration and aggregation[C]∥Proceedings of the 4th ACM International Symposium on Mobile Ad hoc Networking & Computing.ACM,2003:165-176.
[10] YOUNIS O,FAHMY S.HEED:a hybrid,energy-efficient,distributed clustering approach for ad hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):366-379.
[11] GUPTA I,RIORDAN D,SAMPALLI S.Cluster-head election using fuzzy logic for wireless sensor networks[C]∥Proceedings of the 3rd Annual Communication Networks and Services Research Conference,2005.IEEE,2005:255-260.
[12] ALLA B.Gateway and Cluster Head Election using Fuzzy Logic in heterogeneous wireless sensor networks[C]∥2012 International Conference on Multimedia Computing and Systems.2012:761-766.
[13] CHAN H,PERRING A.ACE:An emergent algorithm for highly uniform cluster formation[M]∥Wireless Sensor Networks.Springer Berlin Heidelberg,2004:154-171.
[14] AL-KARAKI J N,UL-MUSTAFA R,K AMEL A E.Data aggregation in wireless sensor networks-exact and approximate algorithms[C]∥Workshop on High Performance Switching and Routing,2004(HPSR).IEEE,2004:241-245.
[15] KOUTSONIKOLAS D,DAS S M,HU Y C,et al.Hierarchical geographic multicast routing for wireless sensor networks[J].Wireless Networks,2010,16(2):449-466.
[16] LUO H,YE F,CHENG J,et al.TTDD:Two-tier data dissemination in large-scale wireless sensor networks[J].Wireless Networks,2005,11(1-2):161-175.
[17] LIN K,ZHAO H,YIN Z Y,et al.A clustering algorithm based on energy predicition in wireless sensor networks[J].Acta Electronica Sinica,2008,4(4):824-828.(in Chinese) 林恺,赵海,尹震宇,等.一种基于能量预测的无线传感器网络分簇算法[J].电子学报,2008,4(4):824-828.
[18] HU J,SHEN L F,SONG T C,et al.A new clustering algorithm in wireless sensor networks[J].Journal on Communications,2008,29(7):20-26.(in Chinese) 胡静,沈连丰,宋铁成,等.新的无线传感器网络分簇算法[J].通信学报,2008,29(7):20-26.
[19] YANG J,ZHANG D Y,ZHANG Y Y,et al.A cluster based data aggregation and transmission protocol for wireless sensor networks[J].Journal of Software,2010,5(5):1127-1137.(in Chinese) 杨军,张德运,张云翼,等.基于分簇的无线传感器网络数据汇聚传送协议[J].软件学报,2010,5(5):1127-1137.
[20] JIANG C J,SHI W R,TANG X L,et al.Non uniform clustering routing protocol with energy balanced for wireless sensor networks[J].Journal of Software,2012,34(5):1222-1232.(in Chinese) 蒋畅江,石为人,唐贤伦,等.能量均衡的无线传感器网络非均匀分簇路由协议[J].软件学报,2012,34(5):1222-1232.
[21] ZHANG D,WANG X,SONG X,et al.A new clustering routing method based on PECE for WSN[J].EURASIP Journal on Wireless Communications and Networking,2015,2015(1):1-13.
[22] WANG R,LIU G,ZHENG C.A clustering algorithm based on virtual area partition for heterogeneous wireless sensor networks[C]∥International Conference on Mechatronics and Automation,2007(ICMA 2007).IEEE,2007:372-376.
[23] DUARTE JR E P,WEBER A,FONSECA K V O.Distributed diagnosis of dynamic events in partitionable arbitrary topology networks[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(8):1415-1426.
[24] MA D,MA J,XU P,et al.An adaptive node partition clustering protocol using particle swarm optimization[C]∥2013 10th IEEE International Conference on Control and Automation (ICCA).IEEE,2013:250-253.
[25] DEL VALLE Y,VENAYAGAMOORTHY G K,MOHAGH-EGHI S,et al.Particle swarm optimization:basic concepts,variants and applications in power systems[J].IEEE Transactions on Evolutionary Computation,2008,12(2):171-195.
[26] WANG E,YANG Y J,LI L.A DTN clustering routing method based on dynamic semi Markov path searching model[J].Chinese Journal of Computer,2015,38(3):483-499.(in Chinese) 王恩,杨永健,李莅.基于动态半马尔可夫路径搜索模型的DTN分簇路由方法[J].计算机学报,2015,38(3):483-499.
[27] JAVAID N,RASHEED M B,IMRAN M,et al.An Energy Efficient Distributed Clustering Algorithm for Heterogeneous WSNs[J].EURASIP Journal on Wireless Communications and Networking,2015,5(1):1-11
[28] WEI X,LU J,ZHUANG Y,et al.Adaptive clustering routing optimization for wireless sensor networks[C]∥2013 9th International Conference on Natural Computation (ICNC).2013:1011-1015.
[29] TYAGI S,TANWAR S,KUMAR N,et al.Cognitive radio-based clustering for opportunistic shared spectrum access to enhance lifetime of wireless sensor network[J].Pervasive and Mobile Computing,2015,22(c):90-112.
[30] XIE W X,ZHANG Q Y,SUN Z M,et al.A Clustering Routing Protocol for WSN Based on Type-2 Fuzzy Logic and Ant Colony Optimization[J].Wireless Personal Communications,2015,84(2):1165-1196.
[31] LIU J,LI J,NIU X,et al.GreenOCR:An Energy-Efficient Optimal Clustering Routing Protocol[J].Computer Journal,2015,58(6):1344.
[32] SHIN H,MOH S,CHUNG I,et al.Equal-size clustering for irregularly deployed wireless sensor networks[J].Wireless Personal Communications,2014,82(2):995-1012.
[33] ARUMUGAM G S,PONNUCHAMY T.EE-LEACH:development of energy-efficient LEACH Protocol for data gathering in WSN[J].EURASIP Journal on Wireless Communications and Networking,2015,2015(1):1-9.
[34] PEI E,HAN H,SUN Z,et al.LEAUCH:low-energy adaptiveuneven clustering hierarchy for cognitive radio sensor network[J].EURASIP Journal on Wireless Communications and Networking,2015,2015(1):1-8.
[35] XIAO G,SUN N,LV L,et al.An HEED-Based Study of Cell-Clustered Algorithm in Wireless Sensor Network for Energy Efficiency[J].Wireless Personal Communications,2015,81(1):373-386.
[36] MEHMOOD A,KHAN S,SHAMS B,et al.Energy-efficientmulti-level and distance-aware clustering mechanism for WSNs[J].International Journal of Communication Systems,2015,28(5):972-989.
[37] BARANIDHARAN B,SANTHI B.GAECH:Genetic Algorithm Based Energy Efficient Clustering Hierarchy in Wireless Sensor Networks[J].Journal of Sensors,2015,2015(4):715740.
[38] BASKARAN M,SADAGOPAN C.Synchronous Firefly Algorithm for Cluster Head Selection in WSN[J].The Scientific World Journal,2014,2015(1):780879.
[39] ELHABYAN R S Y,YAGOUB M C E.Two-tier particle swarm optimization protocol for clustering and routing in wireless sensor network[J].Journal of Network and Computer Applications,2015,52:116-128.
[40] HEINZELMAN W B.Application-specific protocol architectures for wireless networks[D].Massachusetts Institute of Technology,2000.
[41] MURUGANATHAN S D,MA D C F,BHASIN R,et al.A centralized energy-efficient routing protocol for wireless sensor networks[J].Communications Magazine,IEEE,2005,43(3):S8-13.
[42] GOU H,YOO Y,ZENG H.A partition-based LEACH algo-rithm for wireless sensor networks[C]∥Ninth IEEE International Conference on Computer and Information Technology,2009(CIT’09).IEEE,2009:40-45.
[43] YIN Y,SHI J,LI Y,et al.Cluster head selection using analytical hierarchy process for wireless sensor networks[C]∥2006 IEEE 17th International Symposium on Personal,Indoor and Mobile Radio Communications.IEEE,2006:1-5.
[44] GUPTA I,RIORDAN D,SAMPALLI S.Cluster-head election using fuzzy logic for wireless sensor networks[C]∥Proceedings of the 3rd Annual Communication Networks and Services Research Conference,2005.IEEE,2005:255-260.
[45] TILLAPART P,THUMTHAWATWORN T,P AKDEEPINIT P,et al.Method for cluster heads selection in wireless sensor networks[C]∥2004 IEEE Aerospace Conference.2004:3615-3623.
[46] ALI S A,SEVGI C.Energy load balancing for fixed clustering in wireless sensor networks[C]∥2012 5th International Confe-rence on New Technologies,Mobility and Security (NTMS).IEEE,2012:1-5.
[47] YUNJIE J,MING L,SONG Z,et al.A clustering routing algorithm based on energy and distance in WSN[C]∥2012 International Conference on Computer Distributed Control and Intelligent Environmental Monitoring (CDCIEM).IEEE,2012:9-12.
[48] PARK G Y,KIM H,JEONG H W,et al.A novel cluster head selection method based on K-means algorithm for energy efficient wireless sensor network[C]∥2013 27th International Conference on Advanced Information Networking and Applications Workshops (WAINA).IEEE,2013:910-915.
[49] LIU Z X,ZHENG Q C,XUE L,et al.A clustering algorithm together with energy and node degree for sensor networks[J].Journal of Software,2009,20(supp):250-256.(in Chinese) 刘志新,郑庆超,薛亮,等.一种综合能量和节点度的传感器网络分簇算法[J].软件学报,2009,20(supp):250-256.
[50] AOUDIA H,TOUATI Y,ALI-CHERIF A.Energy-efficientrouting protocol based on dynamic clustering mechanism for WSN applications[C]∥Proceedings of the 11th ACM International Symposium on Mobility Management and Wireless Access.ACM,2013:89-92.
[51] AOUDIA H,TOUATI Y,ALI-CHERIF A,et al.Hierarchical routing approach-based energy optimization in wireless sensor networks[C]∥Proceedings of the 10th ACM International Symposium on Mobility Management and Wireless Access.ACM,2012:131-134.
[52] VARALAKSHMI P,NANDAKUMAR R,UMADEVI M.AnEfficient Cluster Head Selection and Aggregation for Wireless Sensor Networks[C]∥2014 International Conference on Communications and Signal Processing (ICCSP).IEEE,2014:1318-1321.
[53] LIANG Y,ZHANG A L,LI Y Z.An Energy-Effective Routing ProtocolEfficiently Constructs Cluster Topology for WSN[C]∥2013 Third International Conference on Instrumentation,Measurement,Computer,Communication and Control (IMCCC).IEEE,2013:1097-1100.
[54] KUMAR R,HOSSAIN A,HUIDROM R.Energy optimization of wireless sensor network with node density in multi hop hexagonal clustering for large structure[C]∥2015 International Conference on Innovations in Information,Embedded and Communication Systems (ICIIECS).IEEE,2015.

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .