基于遗传算法和模糊C均值聚类的WSN分簇路由算法

doi:10.11772/j.issn.1001-9081.2019010134

计算机应用 ›› 2019, Vol. 39 ›› Issue (8): 2359-2365.DOI: 10.11772/j.issn.1001-9081.2019010134

基于遗传算法和模糊C均值聚类的WSN分簇路由算法

董发志¹, 丁洪伟¹, 杨志军^1,2, 熊成彪¹, 张颖婕¹

1. 云南大学信息学院, 昆明 650500;
2. 云南省教育科学研究院, 昆明 650223

收稿日期:2019-01-21 修回日期:2019-04-02 出版日期:2019-08-10 发布日期:2019-04-17
通讯作者: 丁洪伟
作者简介:董发志(1993-),男,云南楚雄人,硕士研究生,主要研究方向:无线传感器网络、轮询多址通信;丁洪伟(1964-),男,江西于都人,教授,博士,主要研究方向:轮询多址通信、随机多址通信、通信与信息系统;杨志军(1968-),男,云南保山人,高级工程师,博士,主要研究方向:计算机通信与网络、轮询系统;熊成彪(1995-),男,云南楚雄人,硕士研究生,主要研究方向:随机多址通信系统;张颖婕(1993-),女,云南昆明人,硕士研究生,主要研究方向:机器学习。
基金资助:
国家自然科学基金资助项目（61461053，61072079）。

WSN clustering routing algorithm based on genetic algorithm and fuzzy C-means clustering

DONG Fazhi¹, DING Hongwei¹, YANG Zhijun^1,2, XIONG Chengbiao¹, ZHANG Yingjie¹

1. School of Information Science and Engineering, Yunnan University, Kunming Yunnan 650500, China;
2. Yunnan Academy of Educational Sciences, Kunming Yunnan 650223, China

Received:2019-01-21 Revised:2019-04-02 Online:2019-08-10 Published:2019-04-17
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61461053, 61072079).

摘要/Abstract

摘要： 针对无线传感器网络（WSN）的节点能量有限、生命周期短、吞吐量低等问题，提出一种基于遗传算法（GA）和模糊C均值（FCM）聚类的WSN分簇路由算法GAFCMCR，采取"集中分簇，分布簇头选举"的方式。网络初始化时基站采用由GA优化的FCM聚类算法形成网络分簇。第一轮簇头由距簇中心最近的节点担任；从第二轮开始，簇头的选举由上一轮的簇头负责，选举过程综合考虑候选节点的剩余能量、与基站的距离、与簇内其他节点的平均距离三个因子，并根据网络状态实时调整三个因子的权重。在数据传输阶段，将轮询机制引入簇内通信。仿真结果表明，相同网络环境下，与LEACH算法和基于K-Means的均匀分簇路由（KUCR）算法相比，GAFCMCR将网络生命周期延长了105%和20%。GAFCMCR成簇效果良好，具有良好的能量均衡性和更高的吞吐量。

关键词: 无线传感器网络, 模糊C均值聚类, 遗传算法, 均匀分簇, 轮询机制

Abstract: Aiming at the problems of limited energy of nodes, short life cycle and low throughput of Wireless Sensor Network (WSN), a WSN Clustering Routing algorithm based on Genetic Algorithm (GA) and Fuzzy C-Means (FCM) clustering (GAFCMCR) was proposed, which adopted the method of centralized clustering and distributed cluster head election. Network clustering was performed by the base station using a FCM clustering algorithm optimized by GA during network initialization. The cluster head of the first round was the node closest to the center of the cluster. From the second round, the election of the cluster head was carried out by the cluster head of the previous round. The residual energy of candidate node, the distance from the node to the base station, and the mean distance from the node to other nodes in the cluster were considered in the election process, and the weights of these three factors were real-time adjusted according to network status. In the data transfer phase, the polling mechanism was introduced into intra-cluster communication. The simulation results show that, compared with the LEACH (Low Energy Adaptive Clustering Hierarchy) algorithm and the K-means-based Uniform Clustering Routing (KUCR) algorithm, the life cycle of the network in GAFCMCR is prolonged by 105% and 20% respectively. GAFCMCR has good clustering effect, good energy balance and higher throughput.

Key words: Wireless Sensor Network (WSN), Fuzzy C-Means (FCM) clustering, Genetic Algorithm (GA), uniform clustering, polling mechanism

中图分类号:

TP393.04

董发志, 丁洪伟, 杨志军, 熊成彪, 张颖婕. 基于遗传算法和模糊C均值聚类的WSN分簇路由算法[J]. 计算机应用, 2019, 39(8): 2359-2365.

DONG Fazhi, DING Hongwei, YANG Zhijun, XIONG Chengbiao, ZHANG Yingjie. WSN clustering routing algorithm based on genetic algorithm and fuzzy C-means clustering[J]. Journal of Computer Applications, 2019, 39(8): 2359-2365.

参考文献

[1] 徐晶晶,张欣慧,许必宵,等.无线传感器网络分簇算法综述[J].计算机科学,2017,44(2):31-37. (XU J J, ZHANG X H, XU B X, et al. Overview of clustering algorithms for wireless sensor networks[J]. Computer Science, 2017, 44(2):31-37.)
[2] SINGH S P, SHARMA S C. Cluster based routing algorithms for wireless sensor networks[J]. IJETI International Journal of Engineering & Technology Innovations, 2014, 1(4):1-8.
[3] LIU F, WANG Y, LIN M, et al. A distributed routing algorithm for data collection in low-duty-cycle wireless sensor networks[J]. IEEE Internet of Things Journal, 2017, 4(5):1420-1433.
[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 R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Piscataway, NJ:IEEE, 2000:223-233.
[6] 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.
[7] KUMAR N, BHUTANI P, MISHRA P. U-LEACH:a novel routing protocol for heterogeneous wireless sensor networks[C]//Proceedings of the 2012 International Conference on Communication, Information and Computing Technology. Washington, DC:IEEE Computer Society, 2012:1-4.
[8] BAKARANIYA P, MEHTA S. K-LEACH:an improved LEACH protocol for lifetime improvement in WSN[J]. International Journal of Engineering Trends and Technology, 2013, 4(5):1521-1526.
[9] 张雅琼.基于K-Means的无线传感网均匀分簇路由算法研究[J].控制工程,2015,22(6):1181-1185. (ZHANG Y Q. Research on uniform clustering routing algorithm based on K-Means in wireless sensor networks[J]. Control Engineering of China, 2015, 22(6):1181-1185.)
[10] 严静静,张腾飞.基于粗糙C-均值聚类的能量均衡LEACH算法[J].计算机工程,2016,42(12):21-25. (YAN J J, ZHANG T F. Energy-balanced LEACH algorithm based on rough C-Means clustering[J]. Computer Engineering, 2016, 42(12):21-25.)
[11] 陶志勇,王和章.基于新型聚类的无线传感器网络非均匀分层路由协议[J].计算机科学,2018,45(3):115-123. (TAO Z Y, WANG H Z. Non-uniform hierarchical routing protocol based on new clustering for wireless sensor network[J]. Computer Science, 2018, 45(3):115-123.)
[12] 戴志强,严承,武正江.一种新的无线传感器网络非均匀分簇双簇头算法——PUDCH算法[J].传感技术学报,2016,29(12):1912-1918. (DAI Z Q, YAN C, WU Z J. New uneven double cluster head clustering algorithm for WSN——PUDCH algorithm[J]. Chinese Journal of Sensors and Actuators, 2016, 29(12):1912-1918.)
[13] 李安超,陈桂芬.基于奇偶轮成簇和双簇首的非均匀分簇协议[J].计算机应用,2018, 38(7):171-176. (LI A C, CHEN G F. Uneven clustering protocol based on odd-even round clustering and double cluster head[J]. Journal of Computer Applications, 2018, 38(7):1995-2000.)
[14] 戚攀,包开阳,马皛源.基于模糊C均值聚类及群体智能的WSN分层路由算法[J].计算机应用,2018,38(7):1974-1980,1988. (QI P, BAO K Y, MA X Y. WSN hierarchical routing algorithm based on fuzzy C-means clustering and swarm intelligence[J]. Journal of Computer Applications, 2018, 38(7):1974-1980,1988.)
[15] 孙增友, 周池. 基于能量和距离的WSN自适应分簇算法[J].东北电力大学学报,2016,36(1):82-86. (SUN Z Y, ZHOU C. Adaptive clustering algorithm based on energy and distance[J]. Journal of Northeast Dianli University, 2016, 36(1):82-86.)
[16] RUSPINI E H. Numerical methods for fuzzy clustering[J]. Information Sciences, 1970, 2(3):319-350.
[17] KONG L, PAN J-S, SNÁŠEL V, et al. An energy-aware routing protocol for wireless sensor network based on genetic algorithm[J]. Telecommunication Systems, 2018, 67(3):451-463.
[18] BAROUDI U, BIN-YAHYA M, ALSHAMMARI M, et al. Ticket-based QoS routing optimization using genetic algorithm for WSN applications in smart grid[J]. Journal of Ambient Intelligence and Humanized Computing, 2019, 10(4):1325-1338.
[19] 黄白梅.基于GA优化的核模糊C均值聚类算法的研究[D].武汉:武汉科技大学,2013:23-29. (HUANG B M. Researches in kernel-based fuzzy C-means clustering algorithm based on GA optimization[D]. Wuhan:Wuhan University of Science and Technology, 2013:23-29.)
[20] ZHANG L, LU W, LIU X, et al. A global clustering approach using hybrid optimization for incomplete data based on interval reconstruction of missing value[J]. International Journal of Intelligent Systems, 2016, 31(4):297-313.
[21] AL-BAZ A, EL-SAYED A. A new algorithm for cluster head selection in LEACH protocol for wireless sensor networks[J]. International Journal of Communication Systems, 2018, 31(1):1-13.
[22] 吴标,余剑,易仁杰.基于节点剩余能量的分时分簇LEACH改进算法[J].火力与指挥控制,2016,41(10):84-88. (WU B, YU J, YI R J.A time-division clustering algorithm of LEACH based on residual energy of sensor nodes[J]. Fire Control and Command Control, 2016, 41(10):84-88.)
[23] 刘龙军,丁洪伟,柳虔林,等.基于FPGA WSN轮询接入控制协议的研究[J].通信学报,2016,37(10):181-187. (LIU L J, DING H W, LIU Q L, et al. Design of polling access control protocol in WSN based on FPGA[J]. Journal on Communications, 2016, 37(10):181-187.)

基于遗传算法和模糊C均值聚类的WSN分簇路由算法

WSN clustering routing algorithm based on genetic algorithm and fuzzy C-means clustering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[4]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[5]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[6]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[7]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[8]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[9]	袁芊芊, 邓洪敏, 王晓航. 基于超像素快速模糊C均值聚类与支持向量机的柑橘病虫害区域分割[J]. 计算机应用, 2021, 41(2): 563-570.
[10]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[11]	孙环, 陈宏滨. 基于萤火虫算法的无线传感器网络节点重部署策略[J]. 计算机应用, 2021, 41(2): 492-497.
[12]	张阳, 王小宁. 基于Word2Vec词嵌入和高维生物基因选择遗传算法的文本特征选择方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3151-3155.
[13]	黄晓祥, 胡咏梅, 吴丹, 任力杰. 基于变分自编码器的异常颈动脉早期识别和预测[J]. 计算机应用, 2021, 41(10): 3082-3088.
[14]	杨华龙, 王美玉, 辛禹辰. 横向整合战略下异质车辆库存路径优化模型[J]. 计算机应用, 2021, 41(10): 3040-3048.
[15]	王永航, 张天宇, 郑红星. 考虑恶劣天气的班轮多阶段重调度方法[J]. 计算机应用, 2021, 41(1): 286-294.