基于布谷鸟优化K均值的WSN分簇路由算法

doi:10.11959/j.issn.2096-3750.2022.00257

物联网学报 ›› 2022, Vol. 6 ›› Issue (1): 73-81.doi: 10.11959/j.issn.2096-3750.2022.00257

基于布谷鸟优化K均值的WSN分簇路由算法

朱开磊, 孙爱晶

西安邮电大学通信与信息工程学院，陕西西安 710121

修回日期:2021-12-29 出版日期:2022-03-30 发布日期:2022-03-01
作者简介:朱开磊（1995− ），男，西安邮电大学硕士生，主要研究方向为物联网技术及应用、路由协议
孙爱晶（1971− ），女，西安邮电大学教授，主要研究方向为物联网技术及应用
基金资助:
陕西省科技成果推广项目(2018CG-007);陕西省创新人才推进计划-物联网科技创新团队项目(2019TD-028)

WSN clustering routing algorithm based on Cuckoo Search algorithm optimized K-means

Kailei ZHU, Aijing SUN

School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China

Revised:2021-12-29 Online:2022-03-30 Published:2022-03-01
Supported by:
The Shaanxi Province Science and Technology Achievement Promotion Project(2018CG-007);The Shaanxi Province Innovative Talent Promotion Plan-The Internet of Things Technology Innovation Team Project(2019TD-028)

摘要/Abstract

摘要：

为了延长无线传感器网络生命周期，提出了一种基于布谷鸟优化 K 均值（K-means）的无线传感器网络分簇路由算法。分簇阶段，使用布谷鸟算法选出初始聚类中心，使K-means算法的分簇结果更均匀，以均衡节点能耗；簇首选举综合考虑节点的剩余能量、与聚类中心的距离因素，并依据节点剩余能量动态调整权重，使选举的簇首更合理；数据通信阶段，为了进一步均衡簇首负载，综合考虑中继节点剩余能量及其负载、簇首路由能耗因素，结合布谷鸟算法为簇首规划路由。仿真结果表明，提出的算法在能耗均衡性方面比LEACH-K、LEACH-improve和DTK-means算法更优，以首节点死亡作为网络生命周期，网络寿命分别提高了173%、21%、6%，所提算法有效延长了网络生命周期。

关键词: 无线传感器网络, 布谷鸟算法, K均值聚类, 分簇均匀, 能耗均衡

Abstract:

In order to extend the lifetime of wireless sensor network (WSN), a clustering routing algorithm for WSN based on Cuckoo Search (CS) algorithm optimized K-means was presented.In the clustering stage, the initial cluster centers were selected by CS algorithm, which make the clustering results of the K-means algorithm more uniform to balance node energy consumption.The remaining energy of the node, the distance from the center of the cluster were comprehensively considered in the cluster election, and the weight according to the remaining energy of the node was dynamically adjusted.In the data communication stage, in order to further balance the load of the cluster head, the remaining energy of the relay node and its load, and the cluster head routing energy consumption were comprehensively considered, CS algorithm was combined to plan routing for the cluster head.The simulation results show that the proposed algorithm is better than LEACH-K, LEACH-improve and DTK-means in terms of energy consumption balance.With the death of the first node as the life cycle of the network, the network lifespan was increased by 173%, 21%, and 6% respectively.The proposed algorithm effectively extending the network life cycle.

Key words: wireless sensor network, cuckoo search algorithm, K-means clustering, even clustering, balanced energy consumption

中图分类号:

TP393

朱开磊, 孙爱晶. 基于布谷鸟优化K均值的WSN分簇路由算法[J]. 物联网学报, 2022, 6(1): 73-81.

Kailei ZHU, Aijing SUN. WSN clustering routing algorithm based on Cuckoo Search algorithm optimized K-means[J]. Chinese Journal on Internet of Things, 2022, 6(1): 73-81.

图/表 8

图1

表1

最优簇首路由路径"

簇首坐标	簇首中继节点坐标	基站坐标
$(x_{ch}, y_{ch}) \to$	$(re_x_{1}, re_y_{1}) \to \dots \to (re_x_{hop- 1}, re_y_{hop-1})$	$\to (x_{bs}, y_{bs})$

表1

表2

图2

图3

图4

图5

图6

参考文献 19

[1]	SONG Y , GUI C , LU X C ,et al. A genetic algorithm for energy-efficient based multipath routing in wireless sensor networks[J]. Wireless Personal Communications, 2015,85(4): 2055-2066.
[2]	徐晶晶, 张欣慧, 许必宵 ,等. 无线传感器网络分簇算法综述[J]. 计算机科学, 2017,44(2): 31-37.
	XU J J , ZHANG X H , XU B X ,et al. Survey of clustering algorithms for wireless sensor networks[J]. Computer Science, 2017,44(2): 31-37.
[3]	李文峰, 沈连丰, 胡静 . 传感器网络簇间通信自适应节能路由优化算法[J]. 通信学报, 2012,33(3): 10-19.
	LI W F , SHEN L F , HU J . Adaptive energy-saving routing algorithm for inter-clustering communications in WSN[J]. Journal on Communications, 2012,33(3): 10-19.
[4]	GULERIA K , VERMA A K . Comprehensive review for energy efficient hierarchical routing protocols on wireless sensor networks[J]. Wireless Networks, 2019,25(3): 1159-1183.
[5]	HEINZELMAN W B , CHANDRAKASAN A P , BALAKRISHNAN H . An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002,1(4): 660-670.
[6]	RAZAQUE A , MUDIGULAM S , GAVINI K ,et al. H-LEACH:hybrid-low energy adaptive clustering hierarchy for wireless sensor networks[C]// Proceedings of 2016 IEEE Long Island Systems,Applications and Technology Conference (LISAT). Piscataway:IEEE Press, 2016: 1-4.
[7]	李成法, 陈贵海, 叶懋 ,等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报, 2007,30(1): 27-36.
	LI C F , CHEN G H , YE M ,et al. An uneven cluster-based routing protocol for wireless sensor networks[J]. Chinese Journal of Computers, 2007,30(1): 27-36.
[8]	GANTASSI R , GOUISSEM B B , OTHMEN J B . Routing protocol LEACH-K using K-means algorithm in wireless sensor network[M]// Advances in Intelligent Systems and Computing. Cham: Springer International Publishing, 2020: 299-309.
[9]	黄利晓, 王晖, 袁利永 ,等. 基于能量均衡高效WSN的LEACH协议改进算法[J]. 通信学报, 2017,38(S2): 164-169.
	HUANG L X , WANG H , YUAN L Y ,et al. Improved LEACH protocol algorithm for WSN based on energy balance and high efficiency[J]. Journal on Communications, 2017,38(S2): 164-169.
[10]	张顶, 张琳 . 基于K-means的WSN动态信任度双簇头选取算法[J]. 南京邮电大学学报(自然科学版), 2020,40(2): 108-114.
	ZHANG D , ZHANG L . Dual cluster head selection algorithm based on K-means and dynamic trust degree in WSN[J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2020,40(2): 108-114.
[11]	ERISOGLU M , CALIS N , SAKALLIOGLU S . A new algorithm for initial cluster centers in K-means algorithm[J]. Pattern Recognition Letters, 2011,32(14): 1701-1705.
[12]	JANG S , KIM H Y , KIM N U ,et al. Energy-efficient clustering scheme with concentric hierarchy[C]// Proceedings of 2011 IEEE International RF ＆ Microwave Conference. Piscataway:IEEE Press, 2011: 79-82.
[13]	RAY A , DE D . Energy efficient clustering protocol based on K-means (EECPK-means)-midpoint algorithm for enhanced network lifetime in wireless sensor network[J]. IET Wireless Sensor Systems, 2016,6(6): 181-191.
[14]	YANG X S , DEB S . Cuckoo search:recent advances and applications[J]. Neural Computing and Applications, 2014,24(1): 169-174.
[15]	YANG X S , DEB S . Engineering optimisation by cuckoo search[J]. International Journal of Mathematical Modelling and Numerical Optimisation, 2010,1(4): 330.
[16]	董发志, 丁洪伟, 杨志军 ,等. 基于遗传算法和模糊 C 均值聚类的WSN分簇路由算法[J]. 计算机应用, 2019,39(8): 2359-2365.
	DONG F Z , DING H W , YANG Z J ,et al. WSN clustering routing algorithm based on genetic algorithm and fuzzy C-means clustering[J]. Journal of Computer Applications, 2019,39(8): 2359-2365.
[17]	SHETA A F , SOLAIMAN B . Evolving clustering algorithms for wireless sensor networks with various radiation patterns to reduce energy consumption[C]// Proceedings of 2015 Science and Information Conference (SAI). Piscataway:IEEE Press, 2015: 1037-1045.
[18]	李道全, 张玉霞, 魏艳婷 . 基于聚类分析的能耗均衡无线传感器网络分簇算法[J]. 计算机工程, 2019,45(10): 116-121.
	LI D Q , ZHANG Y X , WEI Y T . Energy consumption balanced clustering algorithm for wireless sensor network based on clustering analysis[J]. Computer Engineering, 2019,45(10): 116-121.
[19]	KIMURA N , LATIFI S . A survey on data compression in wireless sensor networks[C]// Proceedings of International Conference on Information Technology:Coding and Computing (ITCC'05) - Volume II. Piscataway:IEEE Press, 2005: 8-13.

参数	取值
监测区域	100 m ×100 m
节点个数	100
基站坐标	(50,50)
数据长度	4 000 bit
最佳传输距离d	32 m
E_init	5J
Eelec	50 nJ/bit
Eda	5 nJ/(bit?packet^{- 1})
εfs	10 pJ/(bit?m^{- 2})
ε_mp	0.001 3 pJ/(bit?m^{- 4})
χ、η、δ、λ	0.4, 0.4,0.2,0.8

基于布谷鸟优化K均值的WSN分簇路由算法

WSN clustering routing algorithm based on Cuckoo Search algorithm optimized K-means

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 19

相关文章 6

Metrics

推荐阅读 0

[1]	赵小强, 吴帅, 高传义, 李宁, 李波东, 杨小勇. 基于测距修正及改进灰狼优化器的DV-Hop定位算法研究[J]. 物联网学报, 2021, 5(4): 62-70.
[2]	赵小强, 任少亚, 翟永智, 权恒, 杨婷. 基于模拟退火算法和改进灰狼优化器的异构无线传感器网络路由协议[J]. 物联网学报, 2021, 5(2): 97-106.
[3]	杨金凤,王骥. 精准农业无线传感器网络协议研究[J]. 物联网学报, 2020, 4(4): 62-69.
[4]	胡洁,詹杰,任保全. WSN中基于流网络的K连通算法[J]. 物联网学报, 2019, 3(3): 11-17.
[5]	何鹏举,刘刚易,刘寺意. 基于WSN和盲源分离的多目标识别方法研究[J]. 物联网学报, 2019, 3(1): 45-50.
[6]	罗小娟,朱煜,黄如. 无线传感器网络病毒传播动力学模型研究[J]. 物联网学报, 2017, 1(2): 63-67.