端到端时延下网络多路径负载均衡算法仿真

2023-03-29苏富林冯桂莲

计算机仿真 2023年2期

苏富林，冯桂莲

(1. 甘肃民族师范学院计算机科学系，甘肃合作 747000；2. 青海民族大学物理与电子信息工程学院，青海西宁 810007)

1 引言

传感器节点通常由多个部分组成，其主要负责数据的传输与接收、节点供电和数据处理等工作[1]，传感器节点在网络中所占的空间较小，其电源供应能力、计算能力等都会受到约束，为了降低网络能耗、延长网络寿命，需要保证节点之间数据稳定、可靠地传输[2]，在此背景下，研究网络多路径负载均衡算法具有重要意义。

许红亮[3]等人通过蜘蛛猴算法根据路径信息计算链路空闲率，并将其作为路径在网络中的适应度值，根据计算结果评估路径，并对路径更新，将链路占用率最小作为指标选取最优转发路径，实现网络多路径负载均衡。该算法的端到端时延较长，且数据传输过程中的分组丢失率较高。吕翊[4]等人根据网络前端结构特点构建路径选取模型，计算路径差分延迟和数据传输延迟，在粒子群优化算法的基础上通过多级惩罚函数分配网络负载，实现负载均衡，该算法的节点平均能耗较高，存在网络能量消耗高的问题。李锐[5]等人根据节点特性，计算节点在网络中的移动状态概率和剩余能量，将链路质量最优作为目标，根据上述计算结果选取最优路径，实现负载均衡，该算法的存活节点数量较少，网络生命周期短。

为了解决上述算法中存在的问题，提出基于蚁群优化的网络多路径负载均衡算法。

2 网络多路径负载均衡算法

基于蚁群优化的网络多路径负载均衡算法主要在Floodlinght控制器中通过路由模块、大象流检测模块、网络监听模块和计算决策模块实现网络多路径负载均衡，如图1所示。

图1 网络多路径负载均衡机制

2.1 路由模块

数据中心网络中的流可以分为大象流和老鼠流，通过路由模块区分网络中的大象流和老鼠流，确定转发路径，并在哈希散列的基础上通过ECMP算法[6]调度老鼠流，在决策模块中完成网络大象流的调度。

2.2 大象流检测

标记网络中存在的大象流是调度的首要步骤，在大象流检测过程中，用F={f1，f2，…，fx}表示链路中存在的大象流，可通过下式判断网络中存在的数据流是否为大象流

(1)

式中，tth代表的是数据流平均大小的倍数。

根据节点在网络中构成的集合V={v1，v2，…，vn}以及链路构成的集合L组建图G(V，L)，用于表示网络的拓扑结构。

设ul代表的是链路利用率，其计算公式如下

(2)

根据上式计算结果，通过下式确定网络的最大链路利用率umax

umax=max{ul}

(3)

(4)

2.3 网络监听模块

网络监听模块的主要任务是监听各节点在网络中的实时信息。

(5)

2)链路负载均衡度[7，8]，用n表示节点在网络中的数量，设ZB(t)代表的是链路在当前网络中的负载均衡程度，可通过下式计算得到

(6)

式中，lcij代表的是链路(i，j)在网络中的带宽；m描述的是网络中链路的实际数量。

3)网络流接收率GA(t)

GA(t)=gs(t)/gc(t)

(7)

式中，gc(t)代表的是总共发送的数据流；gs(t)代表的是接收到的数据流。

4)网络带宽占用率BP

(8)

式中，lpij代表的是链路在初始时刻的最大带宽容量。

5)网络吞吐量YR，描述的是网络拓扑在网络流时间无限长的情况下能够发送成功的最大流数目[9]，其计算公式如下

(9)

2.4 计算决策模块

2.4.1 兴趣扩散

经调查发现，由于大象流中包含了大量的数据，因此，在传输过程中容易造成网络拥塞现象，在计算决策模块中通过蚁群优化算法[10，11]合理地调度大象流，避免网络出现拥塞现象，实现多路径的负载均衡。

目的节点vd在网络中周期性地传送兴趣消息，兴趣消息包可以采集节点在网络中的剩余能量信息，通过格式interest=(type，interval，rect，timestamp，expiresat，energy)表示，将energy域增加到网络多路径负载均衡算法中，其主要目的是表示节点在网络中的剩余能量。将邻居节点vi内存在的兴趣消息存储到节点vj对应的梯度表中，邻居节点vi的剩余能量均记录在兴趣消息中，在梯度表中添加启发因子ιji，启发因子ιji可通过下式计算得到

(10)

式中，dji代表的是节点j和节点i在网络中的路径距离；ri代表的是节点i在网络中的剩余能量。

根据节点剩余能量完成兴趣消息中energy域的更新，消息包完成更新后通过链路传输到网络的邻居节点中，停止传播兴趣消息的条件是兴趣信息经过多个节点最终传输到源节点中。

2.4.2 多路径建立

在源节点中，M只蚂蚁获取探测数据包，并将其传输到下一个节点中，用probe=(type，instance，location，intensity，confidence，timestamp，minband，minenergy)描述源节点中存在的探测数据包。为了记录传输路径对应的带宽瓶颈和能量瓶颈，在探测数据包中设置minband域和minenergy域，minband域和minenergy域在网络中的初始化处理可通过源节点完成，处理时需要利用邻居节点在网络中的带宽以及源节点自身存储的能量，在下述规则的基础上使蚂蚁自身携带的探测数据包传输到网络的任意中继节点vi中：

1)判断蚂蚁在前进过程中是否经过该节点，若经过该节点，终止前进；若没有经过该节点，判断下一个目的节点与当前节点之间的距离，选择距离较近的节点作为蚂蚁访问的节点[12，13]。

2)获取链路带宽bij和节点vi的能量ri，针对探测数据包中存在的minenergy域和minband域，通过min(ri，minenergy)、min(bij，minband)完成更新。

3)当邻居节点在网络中无法传输探测数据包时，返回上一步重新选择可以传输探测数据包的邻居节点。

4)当梯度表中存在的邻居节点在网络中都无法传输探测数据包时，节点vi需要重新设置一个梯度表，删除原始的梯度表，新设置的梯度表中不包含目前获取的探测数据包内存在的信息。

根据上述过程，在网络中获得用于数据传输的多条路径。

2.4.3 路径加强与负载均衡

根据前向蚂蚁建立的传输路径，后向蚂蚁可以返回到网络的源节点中，设τ(i，j)代表的是全局信息素，设置信息素挥发程度ε，通过下式对τ(i，j)展开更新处理，获得更新后的全局信息素τ(i，j)new，其主要目的是加强上述过程构建的路径

τ(i，j)new←(1-ε)τ(i，j)old+ε[Δτ(i，j)+ηmaxτ(i，j)]

(11)

式中，τ(i，j)old代表的是原始全局信息素；η为引入的参数；Δτ(i，j)描述的是信息素在更新过程中产生的增量。

通过层次分析法[14，15]计算M条路径在网络中的负载分配权重，以此实验网络多路径的负载均衡，具体过程如下：

1)根据接收的探测数据包，确定负载分配过程中的决策因子，即M条路径对应的宽瓶颈向量B=(b1，b2，…，bM)T、传输延迟向量D=(d1，d2，…，dM)T和能量瓶颈向量R=(r1，r2，…，rM)T。

2)分析上述决策因子对网络多条路径负载分配产生的影响，遵循从大到小的顺序对带宽瓶颈ϑ3、传输延迟ϑ2和能量瓶颈ϑ1排序，在此基础上，构建比较矩阵Φ

(12)

3)根据B=(b1，b2，…，bM)T、D=(d1，d2，…，dM)T、R=(r1，r2，…，rM)T中存在的分量比值，在负载分配过程中建立对应的比较距离，以R=(r1，r2，…，rM)T为例，记φij=ri/rj，获得向量R的比较矩阵Φr=(rij)M×M，根据上述过程获得节点能量在网络中对应的有效权重Er，同理获得B、D在网络多路径负载分配过程中的有效权重Eb、Ed，结合有效权重Er、Eb、Ed计算路径在网络多路径负载分配中的加强权重，根据计算结果为M条路径分配负载，实现网路多路径负载均衡，这种负载分配方式可以有效地避免节点在网络中过早死亡。