卫星网络中基于多QoS约束的蚁群优化路由算法
|
摘要
针对蚁群算法在求解多目标优化问题时存在收敛速度慢、容易陷入局部最优解等问题,提出一种面向卫星网络的多约束QoS路由算法。通过改进蚁群算法的启发函数,将链路QoS信息作为蚂蚁选择下一跳节点的重要依据,并结合排序思想与最大最小蚂蚁算法优化信息素更新规则,获取符合当前业务的最优QoS路径。实验结果表明,该算法在满足卫星网络业务多QoS需求的同时,具有良好的收敛速度和寻优能力。
Aiming at the problems of ant colony algorithm in solving multi-objective optimization problems,such as slow convergence speed and easy to fall into local optimal solution,a multi-constrained QoS routing algorithm for satellite networks is proposed.By improving the heuristic function of the ant colony algorithm, the link QoS information is used as an important basis for the ant to select the next hop node, and the ordering idea and the maximum and minimum ant algorithm are combined to optimize the pheromone update rule to obtain the optimal QoS path in line with the current service.Experimental results show that the algorithm has good convergence speed and optimization ability while satisfying multi-QoS requirements of satellite network services.
Aiming at the problems of ant colony algorithm in solving multi-objective optimization problems,such as slow convergence speed and easy to fall into local optimal solution,a multi-constrained QoS routing algorithm for satellite networks is proposed.By improving the heuristic function of the ant colony algorithm, the link QoS information is used as an important basis for the ant to select the next hop node, and the ordering idea and the maximum and minimum ant algorithm are combined to optimize the pheromone update rule to obtain the optimal QoS path in line with the current service.Experimental results show that the algorithm has good convergence speed and optimization ability while satisfying multi-QoS requirements of satellite network services.
引文
[1] 卢勇,赵有健,孙富春,等.卫星网络路由技术[J].软件学报,2014,25(5):1085-1100.
[2] WU Zhaofeng,HU Guyu,JIN Fenglin,et al.Agent-based dynamic routing in the packet-switched LEO satellite networks[C]//Proceedings of 2015 International Conference on Wireless Communications and Signal Processing.Washington D.C.,USA:IEEE Press,2015:1-6.
[3] GUO Andong,ZHAO Chenglin,XU Fangmin.LEO satellite routing algorithm in software defined space terrestrial integrated network[C]//Proceedings of the 17th International Symposium on Communications and Information Technologies.Washington D.C.,USA:IEEE Press,2017:1-6.
[4] 董明,王兴伟,黄敏.一种面向空间信息网的SCPS-NP QoS单播路由机制[J].小型微型计算机系统,2017,38(7):1425-1429.
[5] SONG Yan,YAO Xiaomei.Design of routing protocol and node structure in wireless sensor network based on improved ant colony optimization algorithm[C]//Proceedings of 2017 International Conference on Computer Network,Electronic and Automation.Washington D.C.,USA:IEEE Press,2017:236-240.
[6] MOUHCINE E,KHALIFA M,MOHAMED Y.Route optimization for school bus scheduling problem based on a distributed ant colony system algorithm[C]//Proceedings of 2017 Intelligent Systems and Computer Vision.Washington D.C.,USA:IEEE Press,2017:1-8.
[7] WEN Guoli,ZHANG Qi,WANG Houtian,et al.An ant colony algorithm based on cross-layer design for routing and wavelength assignment in optical satellite networks[J].China Communications,2017,14(8):63-75.
[8] WANG Houtian,ZHANG Qi,XIN Xiangjun,et al.Cross-layer design and ant-colony optimization based routing algorithm for low earth orbit satellite networks[J].China Communications,2013,10(10):37-46.
[9] DAI Yangyang,LOU Yuansheng,LU Xin.A task scheduling algorithm based on genetic algorithm and ant colony optimization algorithm with multi-QoS constraints in cloud computing[C]//Proceedings of the 7th International Conference on Intelligent Human-Machine Systems and Cybernetics.Washington D.C.,USA:IEEE Press,2015:428-431.
[10] 陈莹.基于蚁群算法的QoS网络路由的研究与设计[D].武汉:武汉理工大学,2010.
[11] ZHANG Yi,ZHOU Quan,LI Jun,et al.The generation and update algorithm of routing table in satellite network[C]//Proceedings of 2015 IEEE International Conference on Communication Problem-Solving.Washington D.C.,USA:IEEE Press,2015:619-622.
[12] YAN Dong,GUO Jian,WANG Luyuan,et al.SADR:network status adaptive QoS dynamic routing for satellite networks[C]//Proceedings of the 13th International Conference on Signal Processing.Washington D.C.,USA:IEEE Press,2016:1186-1190.
[13] DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics,1996,26(1):29-41.
[14] 岳超源.决策理论与方法[M].北京:科学出版社,2003.
[15] STUTZLE T,HOOS H.MAX-MIN ant system and local search for the traveling salesman problem[C]//Proceedings of IEEE International Conference on Evolutionary Computation.Washington D.C.,USA:IEEE Press,1997:309-314.
[16] 詹士昌,徐婕,吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报,2003,19(5):381-386.
[2] WU Zhaofeng,HU Guyu,JIN Fenglin,et al.Agent-based dynamic routing in the packet-switched LEO satellite networks[C]//Proceedings of 2015 International Conference on Wireless Communications and Signal Processing.Washington D.C.,USA:IEEE Press,2015:1-6.
[3] GUO Andong,ZHAO Chenglin,XU Fangmin.LEO satellite routing algorithm in software defined space terrestrial integrated network[C]//Proceedings of the 17th International Symposium on Communications and Information Technologies.Washington D.C.,USA:IEEE Press,2017:1-6.
[4] 董明,王兴伟,黄敏.一种面向空间信息网的SCPS-NP QoS单播路由机制[J].小型微型计算机系统,2017,38(7):1425-1429.
[5] SONG Yan,YAO Xiaomei.Design of routing protocol and node structure in wireless sensor network based on improved ant colony optimization algorithm[C]//Proceedings of 2017 International Conference on Computer Network,Electronic and Automation.Washington D.C.,USA:IEEE Press,2017:236-240.
[6] MOUHCINE E,KHALIFA M,MOHAMED Y.Route optimization for school bus scheduling problem based on a distributed ant colony system algorithm[C]//Proceedings of 2017 Intelligent Systems and Computer Vision.Washington D.C.,USA:IEEE Press,2017:1-8.
[7] WEN Guoli,ZHANG Qi,WANG Houtian,et al.An ant colony algorithm based on cross-layer design for routing and wavelength assignment in optical satellite networks[J].China Communications,2017,14(8):63-75.
[8] WANG Houtian,ZHANG Qi,XIN Xiangjun,et al.Cross-layer design and ant-colony optimization based routing algorithm for low earth orbit satellite networks[J].China Communications,2013,10(10):37-46.
[9] DAI Yangyang,LOU Yuansheng,LU Xin.A task scheduling algorithm based on genetic algorithm and ant colony optimization algorithm with multi-QoS constraints in cloud computing[C]//Proceedings of the 7th International Conference on Intelligent Human-Machine Systems and Cybernetics.Washington D.C.,USA:IEEE Press,2015:428-431.
[10] 陈莹.基于蚁群算法的QoS网络路由的研究与设计[D].武汉:武汉理工大学,2010.
[11] ZHANG Yi,ZHOU Quan,LI Jun,et al.The generation and update algorithm of routing table in satellite network[C]//Proceedings of 2015 IEEE International Conference on Communication Problem-Solving.Washington D.C.,USA:IEEE Press,2015:619-622.
[12] YAN Dong,GUO Jian,WANG Luyuan,et al.SADR:network status adaptive QoS dynamic routing for satellite networks[C]//Proceedings of the 13th International Conference on Signal Processing.Washington D.C.,USA:IEEE Press,2016:1186-1190.
[13] DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics,1996,26(1):29-41.
[14] 岳超源.决策理论与方法[M].北京:科学出版社,2003.
[15] STUTZLE T,HOOS H.MAX-MIN ant system and local search for the traveling salesman problem[C]//Proceedings of IEEE International Conference on Evolutionary Computation.Washington D.C.,USA:IEEE Press,1997:309-314.
[16] 詹士昌,徐婕,吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报,2003,19(5):381-386.