基于遗传算法的多约束QoS单播路由算法  

Multi-Constraint Qo S Unicast Routing Algorithm Based on Genetic Algorithm

作　　者：彭璐[1,2] 何加铭[3,2] 

机构地区：[1]宁波大学信息科学与工程学院,浙江宁波315211 [2]浙江省移动网应用技术重点实验室,浙江宁波315211 [3]宁波大学通信技术研究所,浙江宁波315211

出　　处：《移动通信》2015年第6期76-81,共6页Mobile Communications

基　　金：浙江省移动网络应用技术重点实验室(2010E10005);浙江省新一代移动互联网用户端软件科技创新团队(2010R50009);新一代移动互联网移动采编平台研究(2012R10009-20);浙江省重中之重学科开放基金项目(xkxl1305)

摘　　要：针对Qo S路由问题,设计了一种基于改进遗传算法的多约束Qo S单播路由算法。本算法的编码方法是节点路径序号编码,缩小编码空间的同时避免了编码空间与解空间的转换,提高了算法执行效率;计算适值函数时根据延时、丢包率和延时抖动约束引入一种新的惩罚机制,加快了淘汰速度,更好地保证了"优胜劣淘"的思想;在变异操作中采用"最佳路径替换"的思想,消除了不存在链路或避免产生循环链路,提高了收敛性。通过与传统遗传算法对比,实验结果证明本算法可行且具有更好的有效性和收敛性。According to QoS routing problem, a multi-constraint QoS unicast routing algorithm based on an improved genetic algorithm was proposed in this paper. In the proposed algorithm, path number coding is used to improve algorithm efficiency, which reduces coding space and avoids the switch between decoding space and coding space. A new punishment mechanism is introduced to compute fitness function according to delay, packet loss ratio and delay jitter constraints, which speeds up the elimination rate and guarantees“survival of the fittest”. In addition,“best path substitution”is adopted in mutation process, which eliminates the blank path or cycle path to enhance convergence. Simulation results demonstrate that, compared with traditional generic algorithm, the proposed algorithm is feasible with better effectiveness and convergence.

关 键 词：单播 路由算法 服务质量 遗传算法 收敛性 惩罚机制 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]