一种改进的遗传聚类拓扑分簇算法
|
摘要
针对标准遗传算法在拓扑分簇中由于收敛速度慢而引发网络时延能耗不均的问题,提出了一种快速收敛的最优簇聚类算法。文中在网络能耗最小的基础上引入了遗传搜索最优簇原理,设计了网络能耗最优模型。通过P矩阵改进簇心编码,缩小最优簇心的搜索空间;构造自适应遗传算子操作,定向指导搜索方向,提高局部寻优的搜索效率;利用一步迭代策略改善全局搜索,提高迭代过程中的分簇精度。实验结果表明,该算法能够高效实现网络拓扑均匀划分,节点聚类准确率比标准遗传算法提高约15%;与REDDC算法和粗糙C-Leach算法相比,最高可延长网络生存寿命84%。
In order to solve the problem that the low convergence rate of the standard genetic algorithm in topological clustering results in uneven energy consumption and network delay,the paper proposes a fast convergence optimal clustering method.Based on the minimum network energy consumption,the genetic search principle of the optimal cluster is introduced,and the optimal energy consumption model is designed.The P matrix coding method improves the cluster center coding,reducing the search space of the optimal cluster center.Through constructing the adaptive genetic operator,the search direction is guided,improving the search efficiency of local optimization.The clustering accuracy is improved in the iteration process by using the one-step iteration strategy to better global search.The experimental results show that the proposed algorithm can efficiently achieve uniform topology partition in the network and that the accuracy of node clustering is about 15% higher than that of the standard genetic algorithm.Compared with such algorithms as REDDC and rough C-Leach,the method can extend the network lifetime by a maximum of 84%.
In order to solve the problem that the low convergence rate of the standard genetic algorithm in topological clustering results in uneven energy consumption and network delay,the paper proposes a fast convergence optimal clustering method.Based on the minimum network energy consumption,the genetic search principle of the optimal cluster is introduced,and the optimal energy consumption model is designed.The P matrix coding method improves the cluster center coding,reducing the search space of the optimal cluster center.Through constructing the adaptive genetic operator,the search direction is guided,improving the search efficiency of local optimization.The clustering accuracy is improved in the iteration process by using the one-step iteration strategy to better global search.The experimental results show that the proposed algorithm can efficiently achieve uniform topology partition in the network and that the accuracy of node clustering is about 15% higher than that of the standard genetic algorithm.Compared with such algorithms as REDDC and rough C-Leach,the method can extend the network lifetime by a maximum of 84%.
引文
[1]赵继军,谷志群,薛亮,等.WSN中层次型拓扑控制与网络资源配置联合设计方法[J].自动化学报,2015,41(3):646.ZHAO Jijun,GU Zhiqun,XUE Liang,et al.A Joint Design Method of Hierarchical Topology Control and Network Resource Allocation for Wireless Sensor Networks[J].Acta Automatic Sinice,2015,41(3):646.(in Chinese)
[2]苏金树,郭文忠,余朝龙,等.负载均衡感知的无线传感器网络容错分簇算法[J].计算机学报,2014,37(2):445.SU Jinshu,GUO Wenzhong,YU Chaolong,et al.Fault-tolerance Clustering Algorithm with Load-balance Aware in Wireless Sensor Network[J].Chinese Journal of Computers,2014,37(2):445.(in Chinese)
[3]HONG Y W,SCAGLIONE A.Energy-efficient Broadcasting with Cooperative Transmissions in Wireless Sensor Networks[J].IEEE Transactions on Wireless Communications,2016,5(10):2844.
[4]张海燕,刘虹.基于K-means聚类的WSN能耗均衡路由算法[J].传感技术学报,2011,24(11):1639.ZHANG Haiyan,LIU Hong.Balanced Energy Consumption Routing Algorithm Based on K-means for WSN[J].Chinese Journal of Sensors and Actuators,2011,24(11):1639.(in Chinese)
[5]覃匡宇,黄传河,王才华,等.SDN网络中受时延和容量限制的多控制器均衡部署[J].通信学报,2016,37(11):90.QIN Kuangyu,HUANG Chuanghe,WANG Caihua,et al.Balanced Multiple Controllers Placement with Latency and Capacity Bound in Software-Defined Network[J].Journal on Communications,2016,37(11):90.(in Chinese)
[6]何世钧,代岩岩,周汝雁,等.一种基于遗传聚类的无线传感器网络分簇算法[J].传感器与微系统,2012,31(11):128.HE Shijun,DAI Yanyan,ZHOU Ruyan,et al.A Clustering Algorithm of WSNs Based on Genetic Cluster[J].Transducer and Microsystem Technologies,2012,31(11):128.(in Chinese)
[7]曲志坚,张先伟,曹雁锋,等.基于自适应机制的遗传算法研究[J].计算机应用研究,2015,32(11):3222.QU Zhijian,ZHANG Xianwei,CAO Yanfeng,et al.Research on Genetic Algorithm Based on Adaptive Mechanism[J].Application Research of Computers,2015,32(11):3222.(in Chinese)
[8]MEHR M A.Design and Implementation of a New Energy Efficient Clustering Algorithm Using Genetic Algorithm for Wireless Sensor Networks[J].World Academy of Science Engineering&Technology,2011(76):430.
[9]TING C K,WANG T C,LIAW R T,et al.Genetic Algorithm with a Structure-Based Representation for Genetic-Fuzzy Data Mining[J].Soft Computing,2016:1.
[10]薛猛,姜淑娟,王荣存.基于智能优化算法的测试数据生成综述[J].计算机工程与应用,2018,54(17):16.XUE Meng,JIANG Shujuan,WANG Rongcun.Survey of Test Data Generation Based on Intelligent Optimization Algorithm.[J].Computer Engineering and Application,2018,54(17):16.(in Chinese)
[11]刘浩然,韩涛,李雅倩,等.具有路径能耗优化特性的WSN无标度容错拓扑控制算法[J].通信学报,2014,35(6):64.LIU Haoran,HAN Tao,LI Yaqian,et al.Scale-free Fault-tolerant Topology Control Algorithm in Wireless Sensor Network with Optimization of Path Energy Consumption[J].Journal on Communications,2014,35(6):64.(in Chinese)
[12]刘端阳,暴占兵,程珍.一种可分负载WSN的能耗均衡负载调度算法[J].传感技术学报,2014(2):225.LIU Duanyang,BAO Zhanbing,CHENG Zhen.A Load Schedule Algorithm for Energy Balance in Divisible Load WSN[J].Chinese Journal of Sensors and Actuators,2014(2):225.(in Chinese)
[13]李安超,陈桂芬.能量异构无线传感器网络分簇路由改进算法[J].传感技术学报,2017,30(11):1712.LI Anchao,CHEN Guifen.An Improved Clustering Routing Algorithm for Energy Heterogeneous Wireless Sensor Networks[J].Chinese Journal of Sensors and Actuators,2017,30(11):1712.(in Chinese)
[14]严静静,张腾飞.基于粗糙C-均值聚类的能量均衡LEACH算法[J].计算机工程,2016,42(12):21.YAN Jingjing,ZHANG Tengfei.Energy-balanced LEACH Algorithm Based on Rough C-means Clustering[J].Computer Engineering,2016,42(12):21.(in Chinese)
[2]苏金树,郭文忠,余朝龙,等.负载均衡感知的无线传感器网络容错分簇算法[J].计算机学报,2014,37(2):445.SU Jinshu,GUO Wenzhong,YU Chaolong,et al.Fault-tolerance Clustering Algorithm with Load-balance Aware in Wireless Sensor Network[J].Chinese Journal of Computers,2014,37(2):445.(in Chinese)
[3]HONG Y W,SCAGLIONE A.Energy-efficient Broadcasting with Cooperative Transmissions in Wireless Sensor Networks[J].IEEE Transactions on Wireless Communications,2016,5(10):2844.
[4]张海燕,刘虹.基于K-means聚类的WSN能耗均衡路由算法[J].传感技术学报,2011,24(11):1639.ZHANG Haiyan,LIU Hong.Balanced Energy Consumption Routing Algorithm Based on K-means for WSN[J].Chinese Journal of Sensors and Actuators,2011,24(11):1639.(in Chinese)
[5]覃匡宇,黄传河,王才华,等.SDN网络中受时延和容量限制的多控制器均衡部署[J].通信学报,2016,37(11):90.QIN Kuangyu,HUANG Chuanghe,WANG Caihua,et al.Balanced Multiple Controllers Placement with Latency and Capacity Bound in Software-Defined Network[J].Journal on Communications,2016,37(11):90.(in Chinese)
[6]何世钧,代岩岩,周汝雁,等.一种基于遗传聚类的无线传感器网络分簇算法[J].传感器与微系统,2012,31(11):128.HE Shijun,DAI Yanyan,ZHOU Ruyan,et al.A Clustering Algorithm of WSNs Based on Genetic Cluster[J].Transducer and Microsystem Technologies,2012,31(11):128.(in Chinese)
[7]曲志坚,张先伟,曹雁锋,等.基于自适应机制的遗传算法研究[J].计算机应用研究,2015,32(11):3222.QU Zhijian,ZHANG Xianwei,CAO Yanfeng,et al.Research on Genetic Algorithm Based on Adaptive Mechanism[J].Application Research of Computers,2015,32(11):3222.(in Chinese)
[8]MEHR M A.Design and Implementation of a New Energy Efficient Clustering Algorithm Using Genetic Algorithm for Wireless Sensor Networks[J].World Academy of Science Engineering&Technology,2011(76):430.
[9]TING C K,WANG T C,LIAW R T,et al.Genetic Algorithm with a Structure-Based Representation for Genetic-Fuzzy Data Mining[J].Soft Computing,2016:1.
[10]薛猛,姜淑娟,王荣存.基于智能优化算法的测试数据生成综述[J].计算机工程与应用,2018,54(17):16.XUE Meng,JIANG Shujuan,WANG Rongcun.Survey of Test Data Generation Based on Intelligent Optimization Algorithm.[J].Computer Engineering and Application,2018,54(17):16.(in Chinese)
[11]刘浩然,韩涛,李雅倩,等.具有路径能耗优化特性的WSN无标度容错拓扑控制算法[J].通信学报,2014,35(6):64.LIU Haoran,HAN Tao,LI Yaqian,et al.Scale-free Fault-tolerant Topology Control Algorithm in Wireless Sensor Network with Optimization of Path Energy Consumption[J].Journal on Communications,2014,35(6):64.(in Chinese)
[12]刘端阳,暴占兵,程珍.一种可分负载WSN的能耗均衡负载调度算法[J].传感技术学报,2014(2):225.LIU Duanyang,BAO Zhanbing,CHENG Zhen.A Load Schedule Algorithm for Energy Balance in Divisible Load WSN[J].Chinese Journal of Sensors and Actuators,2014(2):225.(in Chinese)
[13]李安超,陈桂芬.能量异构无线传感器网络分簇路由改进算法[J].传感技术学报,2017,30(11):1712.LI Anchao,CHEN Guifen.An Improved Clustering Routing Algorithm for Energy Heterogeneous Wireless Sensor Networks[J].Chinese Journal of Sensors and Actuators,2017,30(11):1712.(in Chinese)
[14]严静静,张腾飞.基于粗糙C-均值聚类的能量均衡LEACH算法[J].计算机工程,2016,42(12):21.YAN Jingjing,ZHANG Tengfei.Energy-balanced LEACH Algorithm Based on Rough C-means Clustering[J].Computer Engineering,2016,42(12):21.(in Chinese)