一种基于鲸鱼优化的多路径路由发现算法

王勇智,范 钦,戴 华,李武劲

(湖南理工学院 信息科学与工程学院,湖南 岳阳 414006)

0 引言

1 基于鲸鱼优化的多路径路由发现算法

1.1 网络模型

用无向加权连通图G=(V,E)表示网络,其中V为网络中节点的集合,E为网络中节点之间的网络链路的集合,v∈V表示图中的节点,e=(i,j)∈E表示节点vi与vj之间的有效链路.定义Psd为源节点vs∈V到目标节点vd∈{V-{vs}}之间的有效路径的集合,pi∈Psd是该路径集合中的第i条有效路径.假定候选有效路径数目为N,则有Psd={p1,p2,p3,…,pN}.

1.2 鲸鱼优化算法

鲸鱼优化算法(WOA)是Mirjalili和Lewis在2016年提出的一种元启发优化算法,该算法基于座头鲸的狩猎行为,将优化求解的问题划分为泡泡网攻击(Bubble-net attacking)以及搜索猎物(Searching for prey)两个过程[1].每只鲸鱼的位置代表一个可行解,在D维解空间中其位置为Xsd=(x1,x2,x3,…,xD),其中xj∈Xsd表示源节点到目标节点的一条有效路径.结合传统WOA算法,移动自组网络的多路径路由发现优化模型由泡泡网攻击与搜索猎物两个子模型组成.

(1) 泡泡网攻击

收缩包围机制:在鲸鱼优化算法中,所有鲸鱼根据猎物的位置更新自己的位置:

其中t表示当前路由发现的迭代,→表示当前迭代的位置向量,而表示截至当前迭代的局部最优解.和是系数向量,且

其中随着迭代过程的推进由2递减到0,和为[0,1]上的随机向量.通过降低式(3)中的值,可实现收缩包围的行为.假设为[-1,1]上的随机向量,则可定义当前鲸鱼的新位置为其原始位置与猎物位置之间的任意位置.

目前，关于测绘监理的国家统一法规、技术规范还未出台，各省还是在执行各自的测绘监理管理办法，工作的重心通常还是聚焦在测绘成果质量检查环节，尚不能对质量管理、进度控制、工程组织协调等进行科学统筹协调，由于没有相应机制上的制约与保护，监理发挥的作用受到了很大限制，工作形式各不相同，业主和监理方的权利难以保障，甚至存在业主引进监理装门面走形式的现象，重大测绘项目的成果质量仍然难以保证。只有将监理纳入测绘行业统一管理的范畴，制定并实行国家测绘工程监理有关法规和技术规范，实行统一监管，才能保证测绘工程监理健康发展。

螺旋更新位置:鲸鱼靠近猎物的过程满足螺旋方程

由于泡泡网攻击的过程中收缩包围机制与螺旋更新位置同时发生,假设鲸鱼执行其中任意一个行为的概率均为50%,即鲸鱼的位置更新公式为:

其中p是[0,1]中的随机数.

(2) 搜索猎物

由于在实际情况中座头鲸的随机搜索过程依赖于彼此的位置,故鲸鱼算法使用||＞1强迫搜索代理远离参考鲸鱼.与攻击过程相反,在搜索过程中并不根据最佳搜索代理更新位置,而是根据随机选择的搜索代理的位置进行更新.该机制与|→|＞1都强调探索的过程并允许鲸鱼算法进行全局搜索,其位置更新公式为

其中是当前种群选择的一个随机位置向量(随机鲸鱼).

1.3 适应度函数

为了衡量优化搜索过程中与最优解的距离,针对移动自组网络在视频传输过程中存在的链路拥塞及能量损耗问题,本文采用路径拥塞度及路径总能量作为适应度函数.

(1) 路径拥塞度

为预测并衡量生成路径的工作负载,引入路径拥塞度的概念,表示生成路径工作负载的程度.路径拥塞度由节点负荷率计算所得:

其中fcj为生成路径pj的拥塞度,ai表示节点vi的负荷率.节点负荷率由通过经过该节点的链路数l决定:

其中L为网络中有效链路总和.

(2) 路径鲁棒性

由于移动自组网络节点通常使用电池供电,故有限的能量也成为了影响移动自组网络可靠性的一个因素.为尽可能保障移动自组网络在有限能量下的生存时间,引入路径鲁棒性作为约束.路径的生存周期与当前路径中剩余能量最少的节点有关,当该节点能量耗尽时,路径将不再有效.假设路径pj中剩余能量最少的节点为vi,则可定义路径鲁棒性为:

其中Einit表示该节点的初始能量.该公式表明路径鲁棒性与路径中剩余能量最少的节点的剩余能量比例以及节点负荷率有关,该节点剩余能量占初始能量比例越多,负荷率越小,则鲁棒性越强.

(3) 适应度函数

综上可知,路径拥塞度越小,路径鲁棒性越强时,该路径越有可能被选为候选路径.除此之外,候选路径应尽可能短,所以还引入跳数作为约束条件,于是适应度函数为

其中ω1,ω2和ω3是非负加权常量,ε为路径跳数.

2 仿真实验与分析

2.1 仿真环境参数

使用Matlab对本文路由发现算法进行仿真与比较.测试所用的网络拓扑由Atarraya工具[2]生成.网络拓扑节点数为25,通讯距离为100 m,节点类型为Mica2,节点能量为不大于2000 mAh的随机数.生成的网络拓扑如图1所示.

图1 测试用网络拓扑

图1中节点旁标注的数字表示该节点剩余能量.当两个节点间的距离小于通讯距离(100 m)时,两个节点间存在链路.

2.2 仿真结果与性能分析

为评估路由发现算法的性能,引入路由算法AODV[3]与AOMDV[4]进行比较.三个算法的测试参数均保持一致,其中种群数量为50,维度为25,迭代次数为50,1ω,2ω和3ω分别取值为0.4,0.4和0.2.假设源节点为1,目的节点为25,测试结果见表1.

表1 各算法查找结果

从表1数据可知,AODV算法的寻找速度明显快于AOMDV和本文算法(WOA-MPD).可能的原因是AODV算法仅考虑跳数最短的路径,且不考虑多路径的情况,故寻找时间最少.虽然AODV算法成功找出了网络拓扑中跳数最短的路径,但是它在寻找路径的过程中没有考虑网络服务质量的问题,所得路径的Fitness值较高,并不满足实际应用情况.

AOMDV和WOA-MPD均考虑了多路径情况,实际鲁棒性更强.但是AOMDV算法同样只考虑了网络的拓扑结构,而没有考虑网络运行中的服务质量,得出的部分路径Fitness值较大,在网络的实际运行过程中容易出现节点电量过早耗尽的情况,影响网络的正常服务.同时AOMDV算法的寻找时间最长,在大规模网络的情况下耗时过大.

由于在适应度函数中考虑了节点拥塞度与剩余电量等因素,本文提出的WOA-MPD算法找出的三条路径的Fitness值均较小,保障了网络的鲁棒性.并且三条路径的跳数均与最低跳数(5跳)仅相差一跳,在保障了鲁棒性的同时也保障了路径的长度尽可能短,提高了路由效率.

3 结论

本文针对移动自组网络在视频传输过程中存在的链路拥塞及能量损耗问题,将路径拥塞度及路径鲁棒性定义为适应度函数,并通过鲸鱼优化算法有效求解满足多约束条件的多路由路径,提高了移动自组网络的性能与鲁棒性,并保证其服务质量.