基于改进的免疫克隆蛙跳算法的多约束QoS路由优化研究

doi:10.11959/j.issn.1000-436x.2020102

摘要/Abstract

摘要：

针对多约束路由选择问题，设计了数学模型并提出了一种改进的免疫克隆蛙跳算法。所提方法结合了免疫克隆算法与传统蛙跳算法，在分组丢失率、链路带宽、时延抖动、时延、能量损耗条件的限制下，计算源节点到终端节点的能量损耗，通过所提算法寻找一条能量损耗最小的路径。在仿真实验中，将所提算法与自适应遗传算法、自适应蚁群算法进行了对比。实验结果表明，所提算法在一定程度上解决了多约束QoS单播路由优化问题，与自适应遗传算法与自适应蚁群算法相比，所提算法避免了局部最优，有效地降低了数据在传输路径上的能量损耗。

关键词: 蛙跳算法, 服务质量优化, 路由优化, 遗传算法, 蚁群优化算法

Abstract:

Aiming at the multi-constraint routing problem,a mathematical model was designed,and an improved immune clonal shuffled frog leaping algorithm (IICSFLA) was proposed,which combined immune operator with traditional SFLA.Under the constraints of bandwidth,delay,packet loss rate,delay jitter and energy cost,total energy cost from the source node to the terminal node was computed.The proposed algorithm was used to find an optimal route with minimum energy cost.In the simulation,the performance of IICSFLA with adaptive genetic algorithm and adaptive ant colony optimization algorithm was compared.Experimental results show that IICSFLA solves the problem of multi-constraints QoS unicast routing optimization.The proposed algorithm avoids local optimum and effectively reduces energy loss of data on the transmission path in comparison with adaptive genetic algorithm and adaptive ant colony optimization algorithm.

Key words: shuffled frog leaping algorithm, QoS optimization, routing optimization, genetic algorithm

中图分类号:

TP212.6

卢毅,徐梦颖,周杰. 基于改进的免疫克隆蛙跳算法的多约束QoS路由优化研究[J]. 通信学报, 2020, 41(5): 141-149.

Yi LU,Mengying XU,Jie ZHOU. Multi-constraints QoS routing optimization based on improved immune clonal shuffled frog leaping algorithm[J]. Journal on Communications, 2020, 41(5): 141-149.

图/表 14

图1

图2

图3

表1

表2

表3

图4

图5

图6

图7

图8

图9

图10

图11

参考文献 21

[1]	段军雨, 侯俊丞 . 面向物联网的无线传感器网络综述研究[J]. 物联网技术, 2019,9(4): 61-62+66.
	DUAN J Y , HOU J C . A survey of wireless sensor networks for Internet of things[J]. Internet of Things Technologies, 2019,9(4): 61-62+66.
[2]	LAI S , RAVINDRAN B . Least-latency routing over time-dependent wireless sensor networks[J]. IEEE Transactions on Computers, 2013,62(5): 969-983.
[3]	ZHANG H , SHEN H . Energy-efficient beaconless geographic routing in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2010,21(6): 881-896.
[4]	SALMAN A , AHEMD A . A route stability-based multipath QoS routing protocol in cognitive radio ad hoc networks[J]. Wireless Networks, 2019,25(5): 2931-2951.
[5]	吴蒋, 王龙, 石焕玉 . 一种无线传感器网络服务质量(QoS)评价方法[J]. 海南热带海洋学院学报, 2018,25(5): 80-85.
	WU J , WANG L , SHI H Y . Method for evaluating quality of service (QoS) of wireless sensor network[J]. Journal of Hainan TropicalOcean University, 2018,25(5): 80-85.
[6]	苏圣超, 赵曙光 . 基于能耗均衡的无线传感器路由算法[J]. 计算机科学, 2018,45(10): 111-114.
	SU S C , ZHAO S G . Wireless sensor routing algorithm based on energy balance[J]. Computer Science, 2018,45(10): 111-114.
[7]	施志刚, 李桂娟, 李亮 ,等. 一种节能高效的无线传感器网络分簇路由算法[J]. 传感器与微系统, 2018,37(9): 139-141.
	SHI Z G , LI G J , LI L ,et al. An energy-saving and efficient clustering routing algorithm for wireless sensor networks[J]. Transducer and Microsystem Technologies, 2018,37(9): 139-141.
[8]	张金宏, 王兴伟, 黄敏 . 面向绿色互联网的低功耗多播路由算法[J]. 通信学报, 2014,35(z1): 134-140.
	ZHANG J H , WANG X W , HUANG M . Low-power multicast routing algorithm for green Internet[J]. Journal on Communications, 2014,35(z1): 134-140.
[9]	李汉兵, 喻建平, 程时端 ,等. 时延受限的单播 QoS 路由算法[J]. 西安电子科技大学学报, 2003(4): 551-555.
	LI H B , YU J P , CHENG S R ,et al. Unicast QoS routing algorithm with limited delay[J]. Journal of Xidian University, 2003(4): 551-555.
[10]	胡浩, 张航, 康晓军 ,等. 基于遗传蚁群算法的多约束 QoS 组播路由算法[J]. 计算机与数字工程, 2015,43(9): 1566-1568+1705.
	HU H , ZHANG H , KANG X J ,et al. Multi-constrained QoS multicast routing algorithm based on genetic ant colony algorithm[J]. Computer＆ Digital Engineering, 2015,43(9): 1566-1568+1705.
[11]	程爱华, 季中恒, 葛宝忠 . 基于PSO和变异模拟退火的QoS单播路由算法[J]. 计算机工程, 2009,35(6): 205-207.
	CHENG A H , JI Z H , GE B Z . QoS unicast routing algorithm based on PSO and mutation simulated annealing[J]. Computer Engineering, 2009,35(6): 205-207.
[12]	李新明 . 基于群智能优化算法的多约束QoS单播路由问题研究[D]. 武汉:华中科技大学, 2017.
	LI X M . Research on multi-constrained QoS unicast routing problem based on swarm intelligence optimization algorithm[D]. Wuhan:Huazhong University of Science and Technology, 2017.
[13]	彭璐, 何加铭 . 基于遗传算法的多约束QoS单播路由算法[J]. 移动通信, 2015,39(6): 76-81.
	PENG L , HE J M . Multi-constrained QoS unicast routing algorithm based on genetic algorithm[J]. Mobile Communications, 2015,39(6): 76-81.
[14]	高新成, 刘德聚, 王莉利 ,等. 基于蚁群算法的QoS路由模型的设计与优化[J]. 陕西理工大学学报(自然科学版), 2019,35(2): 67-72.
	GAO X C , LIU D J , WANG L L ,et al. Design and optimization of QoS routing model based on ant colony algorithm[J]. Journal of Shaanxi University of Technology(Natural Science Edition), 2019,35(2): 67-72.
[15]	YUAN J , TIAN Y , WANG S ,et al. QoS multicast routing based on firefly algorithm[C]// Proceedings of the 2013 Sixth International Symposium on Computational Intelligence and Design. Piscataway:IEEE Press, 2013: 160-163.
[16]	MAHSEUR M , MERAIHI Y , BOUKRA A ,et al. QoS multicast routing based on a hybrid quantum evolutionary algorithm with firefly algorithm[C]// 2017 5th International Conference on Electrical Engineering. Piscataway:IEEE Press, 2017: 1-6.
[17]	俞立春, 吕红芳 . 基于改进蛙跳算法的无线传感网络的充电路径优化[J]. 科技经济导刊, 2018,26(25):93.
	YU L C , LYU H F . Optimization of charging path of wireless sensor network based on improved leapfrog algorithm[J]. Technology and Economic Guide, 2018,26(25):93.
[18]	MA Y C , SHAO H G . Wireless sensor network routing optimization based on improved shuffled frog leaping algorithm[J]. Applied Mechanics ＆ Materials, 2014,681: 253-257.
[19]	ANANDAMURUGAN S , ABIRAMI T . Antipredator adaptation shuffled frog leap algorithm to improve network life time in wireless sensor network[J]. Wireless Personal Communications, 2017,94(4): 1-12.
[20]	周立朋, 卡米力·木衣丁, 何迪 ,等. 基于蛙跳算法的 WSN 路由优化算法[J]. 计算机应用与软件, 2012,29(2): 243-245.
	ZHOU L P , CAMILLE M , HE D ,et al. WSN routing optimization algorithm based on leapfrog algorithm[J]. Computer Applications and Software, 2012,29(2): 243-245.
[21]	吴清, 吴开军 . 基于改进蛙跳算法的WSNs路由协议[J]. 传感器与微系统, 2016,35(7): 126-128.
	WU Q , WU K J . WSNs routing protocol based on improved leapfrog algorithm[J]. Transducer and Microsystem Technologies, 2016,35(7): 126-128.

个体数量/个	子种群数量	局部迭代次数/次	全局迭代次数/次
12	2	30	100

个体数量/个	交叉率	变异率	全局迭代次数/次
12	0.9	0.05	100

个体数量/个	信息挥发因子ρ	信息启发式因子α	期望启发式因子β	全局迭代次数/次
12	0.95	2	2	100