傅彦铭,周 兴,黄保华,张小萍,朱杰夫

(广西大学 计算机与电子信息学院,南宁 530004)

无线传感器网络(WSN)是物联网[1]连接物理世界的桥梁,物联网的发展对无线传感器网络提出更高的要求.在物联网环境中,为了获取更多和更准确的数据,无线传感器网络的规模在不断增大,同时要求时延、能耗和丢包率更低.因此,无线传感器网络技术的发展不仅更加引人关注,而且更具有挑战性.

多播[2]是一种高效的点到多点通信方式,一个发送者只需要发送一份数据然后通过公共链路分发给多个接受者.相较单播[3],多播能够以更少的代价传输数据,是无线传感器网络中常用的通信方式.在无线传感器网络中,节点的电源电量有限且电池本身不易更换,发射功耗跟消耗的电量是正相关的,发射功耗越低,消耗的电量越少,但功耗太低会导致信号衰减过快,引发丢包率、延迟和抖动激增.无线传感器多播路由应该同时满足这些服务质量(Quality of service,Qos)指标,只满足某一个指标的多播路由在实际应用中难以提供良好的服务,但满足多个Qos指标的多播路由是一个NP难问题[4],并且无线传感器网络具有节点移动性、网络结构动态变化的特征,使问题更加的复杂.

为了解决同时满足多个Qos指标的多播路由问题,Roy等人[5]提出基于多目标遗传算法的移动多播路由协议(QM2RP),利用Pareto机制得到满足多个Qos的多播路由方案的最优非支配解集,研究表明该算法求解多Qos的多播路由问题比传统的单目标加约束的算法效果更好,但基于多目标遗传的QM2RP在处理复杂网络的时候容易陷入局部最优.针对无线传感器网络路由算法容易陷入局部最优的问题,Li等人[6]提出一种新型的量子蚁群多目标路由算法(QACMOR).QACMOR使用量子位元和量子旋转门等量子计算机制与量子进化算法(QEAs)[7]结合,可以更好地避免在路由寻优过程中早熟收敛,并且在WSN多播路由这种大规模问题上具有更好的性能,但是该算法的种群多样性较差.除了使用群体智能算法,Thangaramya等人[8]提出基于能量感知聚类和神经模糊的路由算法,并用于优化物联网中无线传感器网络的多播路由,该算法通过使用一种基于神经模糊规则的聚类算法来进行路由决策,提升准确性的同时降低了效率.为了进一步的提升算法的性能以适应更加复杂的问题,越来越多学者提出使用启发式策略和元启式策略相结合的算法.Bhardwaj等人[9]提出使用多目标分数粒子狮群算法(MOFPL)来解决无线传感器网络的能量感知路由问题.在MOFPL中,结合了分式理论(FT)、粒子群算法以及狮群优化算法[10]来优化基于能量、时延、流量、距离和簇密度的多目标路由.Chaudhry等人[11]提出支持转发区(FZ)的多目标粒子群算法(FZMOPSO)解决物联网在灾难管理(DMSs)中的多播路由问题.提出一种有效粒子发生器FZVPG算子与FZMOPSO相结合,在FZ中搜索有效解,实现有效粒子的转化,从而得到具有更好多样性的DMSs多播路由解集.Shende等人[12]融合Crow搜索算法[13]和Whale优化算法[14]提出了CrowWhale-ETR优化算法求解无线传感器网络中的能量和信任感知的多目标多播路由问题.MOFPL、FZMOPSO和CrowWhale-ETR都是由多种策略相互结合而得到的算法,其搜索能力和跳出局部最优的能力都得到提升,但其时间复杂度也是原来两者的之和甚至更高.

当前的研究表明,WSN的Qos多播路由问题较为复杂,单纯地将群体智能算法用于解决WSN的Qos多播路由容易陷入局部最优,难以取得较好的效果.大部分研究者使用多策略、多种群体智能算法相结合改善求解WSN的Qos多播路由效果,但这些研究主要是单纯针对算法的优化策略进行改进,并未从优化多播树本身结构角度进行研究.竞争协同进化算法是模拟自然界生物种群之间相互影响、相互促进的进化关系而提出的一类算法,这种通过多种群交互,保持种群多样性,并且可以同时考虑多种优化方向的算法,能够以相同的时间复杂度将多种策略相结合,从而相对其他算法能够以更少的计算代价跳出局部最优,获得性能更好的解集[15].因此,本文将竞争协同进化算法种群的每个个体用目标WSN的一颗多播树初始化,并将种群划分为两个子种群,每个子种群用不同的策略更新种群个体多播树的结构,通过种群内部和种群之间的竞争和协作来搜索目标WSN的最优QoS多播树.针对无线传感器网络多跳、能量有限的特点以及多播树的结构特征,本文提出一个基于竞争协同进化的多目标多播路由算法(Competitive Coevolution Multicast Route Algorithm,CCMRA),该算法可以很好的适用于物联网这类大规模网络环境.本文的主要工作包括以下几个方面.

1)根据多播树的结构特征设计了两种多播树构建方法.第1种方法合并同一个目标WSN的两颗多播树,充分利用这个并集的公共边来构造新的多播树.第2种方法对同一个目标WSN的两颗多播树,提取同源和目标点的路径,选择带权路径Pareto更优的一条路径,这些路径集合构造新的多播树.

2)竞争性协同进化算法种群个体是目标WSN的一颗多播树,种群划分为两个子种群.子种群内部分别使用上述两种多播树策略更新.子种群之间通过选择、融合等机制交换信息,从而促进算法的收敛和保持整体种群的多样性.

3)实验从两方面验证算法的性能.首先测试算法在功耗、时延和丢包率3个指标的表现,评估算法在WSN上的Qos性能效果.其次,通过超体积、反向世代距离和世代距离等多目标评价指标测试算法在多目标求解上的性能.

无线传感器网络构成带权图G={V,E},其中V={v1,v2,…,vn} 表示无线传感器网络节点集,E={e1,e2,…,ek} 表示无线传感器网络的链路集合.每个节点的传输功耗在最大值Pmax和最小值Pmin之间选择,传输功耗越大可通信的距离越远,可通信的节点也就越多.Power(e)、Delay(e)和PL(e)分别表示在实际传输过程中链路e∈E的传输功耗、延迟和丢包率.

设s∈V是G={V,E}上多播路由的源节点,D={d1,d2,…,dm}={V-s} 是多播路由的目标节点集.每一条源节点s到目标节点d的路径p(s,d)的并集构成了一棵由源节点s到目标节点集D的多播树T(s,D).

(1)

通过T(s,D)来计算WSN多播路由中的传输功耗、延迟和丢包率这3个目标函数.多播树T(s,D)的传输功耗PT为多播树上每一条边的传输功耗Power(e)之和.

PT(T(s,D))=∑e∈T(s,D)Power(e)

(2)

在T(s,D)一条路径p(s,d)上的丢包率PLP等于1减去该路径剩下的保有率.p(s,d)剩下的保有率等于路径上每条边e的保有率1-PL(e)的乘积.

PLP(p(s,d))=1-∏e∈p(s,d)(1-PL(e))

(3)

多播树T(s,D)的总丢包率PLT等于其每一条路径p(s,d)的丢包率之和.

PLT(T(s,D))=∑p∈T(s,D)PLp(p(s,d))

(4)

多播树T(s,D)上一条路径p(s,d)的延迟Delayp等于p(s,d)上每一条链路e的延迟Delay(e)之和.

Delayp(p(s,d))=∑e∈p(s,d)Delay(e)

(5)

T(s,D)的总延迟DelayT等于其单一路径延迟Delayp中的最大值.

(6)

传输功耗、延迟和丢包率最小化的无线传感器网络多目标多播路由问题,就是要寻找该WSN的多播树,使得多播树在目标函数(1)、(2)和(6)上获得的三维解最优.最优多播树往往不止一颗,因此构成最优多播树解集,该最优多播树解集构成的三维解集应该处于或者尽量接近Pareto最优前沿[16].无线传感器网络多目标多播路由问题的数学模型可以表示如下:

minimize:f(T(s,D))={f1,f2,f3}

(7)

其中f1,f2,f3如下:

f1(T(s,D))=PT(T(s,D))

f2(T(s,D))=DelayT(T(s,D))

f3(T(s,D))=PLT(T(s,D))

满足以下约束:

Delayp<=QD

其中的最大延迟应该小于或等于延迟的阈值QD.

多播树之间存在公共路径,因此最优多播树并不等于多条从源节点到目标节点的最优单播路径的简单组合.多播路由问题是一个不可划分问题,在给定的网络结构中寻找最优多播树是一个NP难问题,而且一个网络的最优多播树往往不止一颗.在求解最优多播树的搜索过程中保持种群多样性,使得搜索能够跳出局部最优,从而加快搜索的速度、提高搜索的精度.保持种群多样性的关键是尽量维持种群中多播树结构的多样化.

根据对公共链路的利用情况,多播树大致有两种结构.图1(a)是一个目标网络的拓扑结构,图1(b)和图1(c)都是该网络中的最优多播树,但其多播树的结构完全不同.图1(b)中从节点1到目的节点7的链路(1→2→5→7)和节点1到目的节点8的链路(1→2→5→6→8)存在公共链路(1→2→5),图1(b)的总边数不是两条链路简单相加的7而是去掉重复的公共链路后的5;图1(c)中到从节点1到目的节点7(1→4→7)和到目的节点8(1→3→6→8)都是其最短路径,但其链路没有公共链路,总边数也为5.在目标网络的多播树中,存在类似图1(b)利用公共边的最优多播树结构,也存在类似图1(c)的由源其到目的节点的最短路径集合构成的最优多播树结构.种群初始化时存在上述两种多播树结构的多样性,随着种群迭代增加,如果种群的多播树结构过于单一,算法就容易陷入局部最优并且难以跳出.

图1 多播树结构图Fig.1 Multicast tree structure

考虑到这些问题,本文提出一个基于竞争性协同进化的多播路由算法(CCMRA).CCMRA的种群分为两个子种群,种群的每一个体是目标网络其中一颗多播树.其中一个子种群GP构造如图1(b)具有公共边的多播树,这种更新方式称为Global操作,原理在3.2节中介绍.另一个子种群LP构造如图1(c)结构的多播树,尽可能使该多播树源节点到目标节点的路径更短,这种更新方式称为Local操作,原理在3.3中介绍.两个子种群之间通过选择和融合机制来交流信息.通过这两个种群内部和种群之间相互学习、相互竞争,CCMRA的种群在进化过程中能够保持多样性和随机性,从而提升搜索能力,避免陷入局部最优,使算法更快地收敛.

CCMRA的原理见算法1.首先CCMRA两个子种群GP和LP的每一个体使用算法2生成的目标网络多播树初始化.其次分别使用以GP和LP为主种群的竞争交配选择方式选取交配父代Parent1和Parent2,然后分别用Global操作和Local操作更新Parent1和Parent2种群,这两个种群沿着两种多播树结构方向进化,构成新的子代种群Off1和Off2.合并Off1,Off2和GP 构成新的GP种群,新种群融合多个子种群来交换种群信息、保持种群的多样性.用类似的方法生成新的LP种群.最后GP和LP分别采用多目标优化机制筛选N/2个较优个体构成下一代的GP和LP种群.本文的多目标优化机制采用NSGAII的所提出的非支配排序方式和拥挤度计算的多目标环境选择方式来更新种群的Pareto解集[17].非支配排序方式在非支配解较少的时候,通过对被支配集进行进一步的优劣排序保证足够的精英解,可以增加在多目标优化过程的搜索能力,同时通过拥挤度计算可以增加多目标优化的多样性,使解集分布更加均匀.迭代结束时GP和LP种群中的个体即为算法获得的最优多播树.

算法1.竞争性协同进化多播路由算法(CCMRA)

输入:网络G,源节点S,目的节点集D,最大迭代次数Itmax,种群个体数N.

输出:最优多播树集合MT.

1.begin

2.GP←用算法2生成G的N/2颗多播树构成GP的个体.

3.LP←用算法2生成G的N/2颗多播树构成LP的个体.

4.Iter←0.

5.WhileIter

6. Parent1←使用以GP为主种群的竞争交配选择方式从GP和LP种群中选择N/2个个体.

7. Parent2←使用以LP为主种群的竞争交配选择方式从LP和GP种群中选择N/2个个体.

8. Off1←Parent1通过Global操作生成子代种群.

9. Off2←Parent2通过Local操作生成子代种群.

10. GP←合并Off1,Off2和GP.

11. LP←合并Off1,Off2和LP.

12. GP←通过多目标优化机制在GP筛选N/2个体.

13. LP←通过多目标优化机制在LP筛选N/2个体.

14. Iter←Iter+1.

15.endwhile

16.MT←合并GP和LP.

17.end

在算法迭代进化的早期,多播树中的链路多且长,LP操作针对单条链路的趋优性可以使LP种群快速地收敛,在GP种群加入LP种群的个体,可以加快GP种群收敛速度,从而提升整体的收敛速度.随着算法深入迭代进化,GP和LP种群多样性变得单一,导致容易陷入局部最优,这是群体智能和进化算法都难以避免的问题.由于GP和LP种群具有一定的互斥性,所以在GP种群中加入LP种群的个体,在LP种群中加入GP种群的个体,可以帮助GP和LP种群在进化过程中保持种群多样性.通过在两个子种群内部使用Global和Local两种操作,在两个子种群之间相互选择、相互交叉融合的协同进化策略,可以保持整个种群的多样性,使得种群能够跳出局部最优,提高算法的收敛速度和精度.

3.1 随机多播树生成方法

对于一个节点众多的WSN,使用深度遍历或广度遍历寻找其多播树较为困难.因此,本文采用一种更高效的多播树生成算法,其原理见算法2.首先选择一条从源节点到任意目的节点的路径加入多播树.对于其余的目的节点,不用重新寻找一整条到源节点的路径,只需要找到一条连通多播树的路径即可.因为多播树是一个源节点到目的节点的连通图,这样能保证构成一颗不含环路的多播树,并且还可以选中更多公共链路,使得生成的整个多播树质量更好.

算法2.多播树生成算法

输入:网络G,源节点S,目的节点集D.

输出:多播树MT.

1.cur←随机选择一个目的节点.

2.whilecur!=sdo

3. cur←随机选择相邻节点.

4.whilecur 在MT中then

5. cur←随机选择其它邻节点;#避免成环.

6.endwhile

7. MT←MT∪cur;#添加到MT中.

8.endwhile

9.while还有目的节点没有添加到MT中do

10. cur←从剩余的目标节点随机选择一个目的节点.

11.whilecur不在MT中do

12. cur←随机选择邻结点.

13. MT←MT∪cur.

14.endwhile

15.endwhile

3.2 竞争交配选择方式

用交配选择方式实现GP和LP种群之间信息共享,在进化过程中增加种群之间密切联系,保持种群多样性.本文使用了一种竞争交配选择方式[18],这种方式从两个输入种群A和B中选出种群C,其中种群A为主种群.首先将种群A和B合并成种群H,然后分别计算A和B的中非支配解数量在整个H的非支配解总数中的所占比例pa和pb.若C的种群数量为N,则每次取两个个体,一共循环N/2次,则最终取得C种群的N个个体.下面说明每次取两个个体的方式的原理.

为了保持主种群的种群优势,在主种群A中用二元锦标赛选择方式选择第一个个体.若pa>pb,说明A的收敛效果更好,否则,说明B的收敛效果更好,效果更好的种群具有更高的机率被选择.设置一个(0,1)之间的随机数rand,因pa+pb=1,故pa越大,pb越小.若rand=pa,在B中用二元锦标赛选择方式选择第2个个体.竞争交配选择方式可以动态调节下一代种群的多样性,充分利用各种群之间的优势,提高算法的收敛.

本文使用了二元锦标赛选择方式来选择配对的父代,与文献[17]中所使用的方法相同,二元锦标赛选择方式是通过随机选择两个个体,然后根据其Pareto支配关系选择这两者中较优的一个,如果无法区分优劣程度则随机选择其中一个,二元锦标赛选择方式是一种概率选择方式,较优的个体被选中的概率更大,但不会稳定选择较优个体,可以同时提供一定的趋优性和多样性.

3.3 Global操作

决定多播树整体代价的主要因素是链路的多少和长短,公共链路多,就可以重复利用链路来减少链路数量.GP种群的进化充分考虑公共链路对最优多播树搜索的影响,以此来获取更加收敛的多播树.GP的进化不仅使用算法2的多播树生成方式,且提出一种新的Global操作来生成子代种群.

在Global操作中,将种群的两个个体合并成一个连通图,使得两个个体的公共链路尽量被选中,构成一颗新多播树的一部分,然后选择其它链路组成这颗完整的多播树.Global操作的原理见算法3.Global操作首先将种群两个个体合并成一个连通图,使用算法2生成该连通图的多播树.这颗多播树继承了这两个父代个体的相同链路,然后随机选择剩下的链路,剩下的链路相互交换而获得新的多样性.合并后的连通图更容易形成公共链路,并且两个个体合并的连通图的可供选择范围更加精准,所以Global操作可以较大概率获得具有公共链路的多播树,Global操作得到的子代个体,其链路都继承于双亲,不会出现非法或不存在的路径.为了抵消因此降低的多样性,变异机制必不可少,Global操作用算法2引入一个新的多播树个体,将新的个体和GP中的个体合并,再使用算法2生成新的多播树个体,将多样性引入种群.

算法3.Global操作算法

输入:网络G,源节点S,目的节点集D,父代种群Parent,父代种群个体的数目N.

输出:子代Offspring.

1.Parent1,Parent2←将Parent 种群对半划分成两种群.

3.fori = 1 to N/2do

4. Pool←将Parent1[i]和Parent2[i]合并成一个连通图.

5. Off1,Off2←分别用算法2在Pool上生成两颗多播树.

6.ifrand

7. newPop←用算法2随机生成G的多播树.

8. Pool←将Parent1[i]和newPop合并成一个连通图.

9. Off1←用算法2生成Pool的多播树.

10.endif

11. Offspring[i] ←Off1.

12. Offspring[i+N/2]←Off2.

13.endfor

3.4 Local操作

公共链路并非越多越好,链路的长短也很重要,因此Local操作构造源节点到各目的节点带权路径尽量短的多播树.使用Local操作更新LP种群,能够搜索GP种群很难搜索到的区域.Local操作随机取出种群的两个个体,将个体拆分成源节点到每个目的节点的路径,从两个个体分别获得的两条同源到目的节点的路径,然后利用多目标优化机制对这两条路径进行优劣筛选,选择其中更优的一条路径用于构造新的多播树.这样得到的多播树其每条源到目的节点路径是两个个体中最优的一条.Local操作构造的多播树,倾向于单播路径的优化,虽不能保证整体上最优,但每一条源节点到单个目的节点的路径较优,可以使多播树的各分支快速收敛.

实验均是在一台配有Intel(R)Core(TM)i7-10750H CPU @2.60GHz和16GB RAM的电脑上进行,操作系统配置Windows 10.算法在Matlab R2019a上编写和运行.使用Waxman随机网络生成器[19]生成8个不同的网络拓扑结构,模拟真实情况下的无线传感器网络,网络的各项参数列于表1.为了模拟真实环境,各节点之间的传输功耗(Transmission Power)取决于节点之间的欧几里得距离,延迟(Delay)设置为10ms～100ms之间的随机数,每条链路的丢包率(Packet Loss)在0～1之间随机产生,最大延迟QD设置为2000ms.

表1 网络参数Table 1 Network parameters

CCMRA与3个经典的多目标算法CrowWhale-ET、FZMOPSO和MOMR-DE[20]在上述8个WSN网络上进行对比实验,验证CCMRA的可行性和优越性.CrowWhale-ETR和FZMOPSO在第1节已经介绍过,MOMR-DE是一种多目标差分多播路由算法.

对比算法的运行参数全部参照原文献,算法的种群大小和迭代次数分别设置为100和1000次,CCMRA的GP和LP子种群大小各为50,总迭代次数为1000次.

4.1 WSN的Qos指标对比分析

实验结果表明,随着网络规模增大,网络变得更加复杂,相应地也会影响算法的性能.在图2、图3和图4中,从Net 1到Net 8网络规模增加和目的节点的增加,多播路由问题变得更加复杂,算法的寻优能力的变弱和最优多播树的本身的扩张都会使得传输功耗、延迟和丢包率随之增加,但也会存在波动,如图2中Net 4和Net 6、图3中的Net 2和图4中的Net4,这是由于网络都是随机生成的,目标节点也是随机选者,会存在个别网络虽然其网络复杂度增加,但其网络的Qos性能指标不一定会增加的情况,在这部分实验中,主要验证算法在不同复杂度的网络结构中与对比算法的性能对比,所以该波动不影响算法的性能分析.

图2 平均传输功耗Fig.2 Mean transmission power

图3 平均延迟Fig.3 Mean delay

图4 平均丢包率Fig.4 Mean packet loss

在图2,图3 和图4中,CCMRA在各个网络环境下的传输功耗、延迟和丢包率都更低,在Net 1 到Net 5上各算法的性能比较接近,在Net 5 到Net 8上CCMRA相较其他对比算法有较明显的优势.CCMRA的种群划分为GP和LP两个子种群,两个子种群组成的竞争协同进化策略能够保持种群的多样性和随机性,使得种群在进化过程中能跳出局部最优,加快种群的收敛.这种竞争性的协同策略显著提升了算法的性能,从而可以在相同的种群大小和迭代次数下,获得更加高质量的解.

此外,在图3中,CCMRA比其它算法获得了更低的延迟,除了协同进化策略的作用,也得益于LP种群,多播树的延迟与其单播链路的最大延迟有关,以最优单播链路为主要考虑目标的LP种群有助于CCMRA算法获得更小的延迟.

图5 、图6和图7分别表示了各算法在Net4、Net6和Net8上获取的Pareto 前沿,结果显示,CCMRA 算法的解集优于其他算法,更加接近理想的Pareto真实前沿.相比图6和图7,在图5中MOMRDE、CrowWhale-ETR、FZMOPSO和CCMRA获得Pareto解都比较少、分散且接近.这是因为Net4节点数比Net6和Net8少,网络复杂度低,因此整个网络的可行解少且容易搜索得到所致的,但在Net4中依旧发现CCMRA和FZMOPSO获取的Pareto解更加逼近理想Pareto前沿.图6中,CCMRA获取的Pareto解集明显优于FZMOPSO的Pareto解集,更加的贴近真实前沿,同时分布也更加的均匀.图7中,显然CrowWhale-ETR和MOMRDE已经无法获取令人满意的解集,CCMRA和FZMOPSO仍能获取较优的Pareto解集,CCMRA和FZMOPSO的Pareto解集收敛性相当,但CCMRA的Pareto前沿面覆盖更广,综合性能表现CCMRA优于FZMOPSO.这是因为,随着网络规模和复杂程度的增大,多播路由问题变得更加难以求解.而CCMRA由于其强关联的两个种群提供的搜索能力,可以在复杂的网络环境下,不容易陷入局部最优,以更少的代价加强收敛.

图5 网络4的Pareto前沿Fig.5 Pareto front of network 4

图6 网络6的Pareto前沿Fig.6 Pareto front of network 6

图7 网络8的Pareto前沿Fig.7 Pareto front of network 8

4.2 多目标指标对比分析

通过超体积(Hyper Volume,HV)、反向世代距离(Inverted Generational Distance,IGD)和世代距离(Generational Distance,GD)等多目标指标[21]评估CCMRA在求解多目标问题的收敛和解集多样性保持上的性能.HV,IGD和GD指标的实验结果分别见表2、表3和表4.全部数据都是单独运行30次得到的均值.

表3 不同算法的GD 指标Table 3 GD metric for different algorithms

HV指标表示所获得的Pareto解集在目标空间上覆盖范围的大小,Pareto覆盖面越宽、分布越均匀或越接近真实Pareto前沿,HV指标都会变大.从表2中看出, CCMRA的HV指标平均值都比其它算法大,说明CCMRA在收敛性和多样性保持上都具有一定的优越性.主要得益于GP和LP子种群更新策略在协同进化过程中起的重要作用.

表2 不同算法的HV指标Table 2 HV metric for different algorithms

GD评价指标可以评价算法的收敛性,GD指标越小,算法的收敛性越好,IGD评价指标可以综合评价算法的收敛性和多样性,IGD指标越小,算法的收敛性和多样性越好.在表3中,CCMRA 的GD指标在各个网络上都优于对比算法.在表4中,CCMRA在Net3,Net4的IGD指标略差于其他算法,对于其它网络CCMRA全都以较大差距优于对比算法.整体而言,实验表明,CCMRA算法得到的非支配解更接近真实的Pareto前沿,可以获得分布更加均匀的非支配解.

表4 不同算法的IGD 指标Table 4 IGD metric for different algorithms

上述实验结果表明,CCMRA所采用的种群更新机制和协同进化策略保持了种群进化过程中的多样性和随机性,使得算法在全局搜索和局部搜索之间能够达到良好的平衡,因此算法获得更好的收敛性能,此外通过不同网络之间的性能对比,可以得知较复杂的网络环境下,CCMRA的性能相较其他对比算法可以仍然可以获得更好的性能,因此CCMRA算法可以适用于网络规模较大的场景.

同时考虑传输功率、延迟和丢包率的无线传感器网络多目标多播路由问题属于复杂的NP问题.为了有效地解决该问题,本文提出一种基于竞争协同进化的多播路由算法(CCMRA).CCMRA使用协同进化算法框架,算法种群的每一个体是目标WSN的一颗多播树,把种群分成GP和LP两个子种群.GP子种群内部通过Global操作更新子种群.Local子种群内部通过Local操作更新子种群.LP和GP子种群之间通过交叉选择和融合机制在整个种群之间共享和交换信息.上述的协同进化策略能够保持种群多样性和随机性,使算法在迭代进化过程中跳出局部最优,从而提高算法的收敛精度和速度.CCMRA与NSGA-II、MOPSO和MOMR-DE在8个WSN上分别进行Qos多播路由实验和多目标求解性能实验.结果显示CCMRA在传输功耗、延迟和丢包率3个Qos指标上优于对比算法.CCMRA的多目标求解性能实验证实,该算法在多目标指标HV、GD、IGD上都有比较明显的优势.此外,CCMRA在处理复杂WSN的良好性能表明该算法能很好地应用于大规模的WSN多播路由问题.

猜你喜欢多播路由链路胖树拓扑中高效实用的定制多播路由算法计算机研究与发展(2022年12期)2022-12-15用于超大Infiniband网络的负载均衡多播路由计算机工程与应用(2022年5期)2022-04-09InfiniBand中面向有限多播表条目数的多播路由算法计算机研究与发展(2022年4期)2022-04-06天空地一体化网络多中继链路自适应调度技术移动通信(2021年5期)2021-10-25基于星间链路的导航卫星时间自主恢复策略空间科学学报(2020年3期)2020-07-24铁路数据网路由汇聚引发的路由迭代问题研究铁道通信信号(2020年9期)2020-02-06一种基于虚拟分扇的簇间多跳路由算法太原科技大学学报(2019年3期)2019-08-05探究路由与环路的问题网络安全和信息化(2018年3期)2018-11-07网络编码与家族体系下的可靠多播方案泰山学院学报(2018年3期)2018-06-01基于预期延迟值的扩散转发路由算法电信科学(2016年11期)2016-11-23