基于改进蚁群算法的应急通信网络路由协议

宋方振，徐彦彦，唐 鑫，潘少明

武汉大学 测绘遥感国家重点实验室，武汉 430079

1 引言

自然灾害和公共突发事件会造成传统通信手段失效，如何启动应急通信机制，快速高效地构建应急通信网络，提升网络的传输效能，成为亟待解决的问题[1]。应急通信具有发生的时间和地点不确定性、通信需求不可预测性、业务紧急性、网络构建快速性、节点移动性等特点[1]，移动无线自组网（MANET）[2]具有网络自组织和协同合作的特征，非常适合在事发现场组建应急通信网络来协调各类人员开展救援行动和应对突发事件。应急MANET[3]具有更高的Qos传输要求，并且要求网络能够较好地适应通信拥塞及快速变化的网络拓扑结构，如何设计合理的路由算法，实现路由选择及资源的优化配置是应急MANET的核心。

传统MANET路由协议使用静态路由决策机制，无法对网络拥塞进行感知并做出相应调整，不适用于应急通信[4]。近年来仿生学在MANET路由中的应用展现了突出的优势[5]，其中蚁群算法以其能够有效适应MANET网络拓扑的动态变化，最终建立收敛的最优路径等特点而得到广泛应用[6]。文献[7]提出了一种ARA路由协议，目的是使用蚁群元启发方法降低网络的路由开销。文献[8]提出的Ant-AODV 路由协议结合按需路由协议AODV和蚁群算法，有效降低了网络的端到端时延和路由发现等待间隔。文献[9]提出的Ant Hocnet是一种多径路由算法，包括被动发现和主动维护路由组件，其中被动发现过程存在于相互通信的节点间，而主动维护过程存在于相邻节点间用于更新和维持路由表项。文献[10]中Hopnet 是基于蚁群算法的混合路由协议，同时搭载区域路由框架用于分区间的蚂蚁包跳转传递。文献[11]提出PERA（Probabilistic Emergent Routing Algorithm）路由协议，在该协议中数据包使用确定的路由路径，即蚁群探索得到的最佳质量保证路径，而前向蚂蚁包则使用广播机制以发现到目的节点的多条备选路径。文献[12]提出MABR（Mobile Ant Based Routing）路由协议，采用主动式路由方案释放前后向蚂蚁周期性地更新网络状态信息，该算法同时利用节点地理分区信息进行信息素的产生。

上述路由协议的共同特点是均使用前向蚂蚁采集网络信息，当前向蚂蚁到达目标节点后再释放反向蚂蚁对经过路径节点进行信息素更新，在高度动态变化的MANET 网络中，上述机制不再适用[13]。针对应急通信网络较高的节点移动性和突发的网络拥塞状况，本文提出一种结合强化学习的改进蚁群路由协议MLSA（Modelbased Learning Strategy combine with ACO），依概率释放局部探测蚂蚁包，收集网络状态信息进行系统建模，从而动态评估链路状态，进行最优路径的选取。考虑整个路由过程中，每个节点对下一跳的选取决策，可以等效为局部的马尔可夫过程[14-16]，通过调整决策过程与网络环境间的相互作用，达到路由节点对网络动态变化与拥塞程度的智能感知；同时保留蚁群算法并行、多径可达的特点，使得在网络拓扑或流量分布发生变化时，路由决策能够动态调整到新的最优路径并对网络拥塞进行流量均衡。仿真实验证明了本文提出方法的有效性。

2 传统蚁群路由算法

传统蚁群优化算法使用一组蚂蚁协同作用，寻找问题的最优解，即整个探索路径的最小消费[17]。蚁群搜索过程开始于一个特定的起始状态，使用概率选择模型决定下一个移动的邻居状态，最终收敛于一个或多个结束状态，如公式（1）所示：

其中，τij为信息素，即为路径ci和cj间存在影响该路径选择概率大小的评价值；ηij为系统先验信息，该先验信息对应于强化学习中的探索过程，蚁群在搜索过程中将受到ηij的影响；α和β分别为剩余信息素值τij与期望函数ηij的权重因子；allowedk为所有下一跳邻居节点构成的集合，表示第k只前向蚂蚁fant从节点vi选择节点vj作为下一跳的概率。

每只蚂蚁在路径寻优时会记录所经过的路径，以及路径节点的相关信息，因此在到达目标节点时能够利用这些路径信息对求解过程进行评估，并且反向更新所经过路径上的信息素值，如公式（2）所示：

其中，ρ∈( 0,1) 表示信息素τij随时间的推移而衰减的程度，Δτij为蚂蚁所选路径的单次信息素累积量。

通过蚁群算法的正反馈作用，同时结合相邻节点i、j间网络Qos 链路状态信息的加权和作为启发值函数ηij，如公式（3）所示：

其中，N为所选Qos 评估指标总数，Qij(m)为相邻网络节点i、j间第m个Qos 链路状态信息评估值，αm为第m个Qos 评估值的权重因子。网络中带宽较大、丢包率较小、时延低的多条路径被筛选出来，作为后续数据传输中使用的首选传输路径。

在路径探索过程中，每只蚂蚁独立地对环境产生影响，体现在高质量路径上信息素值τij的不断积累，环境反过来对每只蚂蚁的决策过程产生指导，后续蚁群将更加集中在信息素浓度较高的路径上。这种正反馈的产生使得蚁群算法极易收敛在局部最优解上，并且难以进行控制。传统蚁群算法作为典型模型无关的强化学习算法，尽管降低了计算复杂度，但其实验敏感，即对应于不同的起始状态趋向于不同收敛解的特性，使得探索搜索过程难以收敛到全局最优解。此外，由于应急网络具有节点机动性及网络状态高度动态变化的特性，网络拓扑更新间隔较短，往往前向蚂蚁刚刚到达目的节点，路由包中记录的路径信息已经由于网络拓扑的变化而失效，信息素的积累过程被搁置，中间节点不断开启路径修复过程，致使路由信息不稳定和难以长期维护。因此，传统蚁群算法难以适用于应急通信网络。

3 结合强化学习的改进蚁群路由算法

针对上述问题，本文提出一种结合强化学习的改进蚁群路由算法（MLSA），通过系统探测和评估同步的连续建模，解决传统蚁群算法易陷入局部最优及路由决策过程缓慢的问题。MLSA 使用强化学习模型进行系统建模，感知系统路由状态变化并记录动作产生的回报；利用上述模型对系统局部进行连续探测，并采用时间轴加窗的方式加速信息素的衰减；在数据传输过程依据Qos优先函数限制进行最优数据的传输，同时更新各节点网络状态。

3.1 网络模型及问题定义

根据应急通信的具体需求，使用丢包率、时延、传输开销的加权和作为系统评估的强化函数，根据不同的Qos 需求，动态调整三者的权重。整个寻优过程为在具体Qos 指标限定下，寻找使得核函数取得最大值的从源节点S到目的节点D的最优路径，当有新的数据传输任务到来时，系统依参数启动路径搜索和数据传输过程。

假设应急响应系统网络的部署环境是二维平面拓扑，其网络拓扑可抽象成带权有向图G(V,E)，其中：V为移动节点集合，节点个数n=|V|；E为单跳通信链路集合，对任意单跳通信链路eij=e(vi,vj)∈E,vi,vj∈V,i≠j,i,j=1,2,…,n，当且仅当vi与vj在单跳通信范围内可通信。G中每条链路eij包含时延、带宽、丢包率、时延抖动等通信代价参数。根据应急响应通信系统的应用特点，如数据传输实时性与质量保障，考虑时延、带宽与丢包率这3 个参数，其中：时延包括中继节点上的排队与处理时延和链路传输时延，丢包率包括节点缓冲区溢出丢包与信道间干扰丢包，带宽即为链路允许的最大数据传输速率。对应于每一单跳通信链路eij∈E，其权值用一个三元组(b(vi,vj),d(vi,vj),l(vi,vj))表示，分别表示链路带宽、链路时延与链路丢包率。

定义1（可行路径）给定网络G，如果从源节点source 到目的节点destination 通过多跳存在一条路径p={v1,v2,…,vn} ，能够将数据从source 节点传输到destination 节点，则称p为一条可行路径。

定义2（路径Qos 参数）给定一条可行路径p={v1,v2,…,vn}，设其路径包括节点的个数为n，则路径p的Qos 参数为路径带宽、路径时延、路径丢包率。根据参数凹性特征，其定义如下：

其中，B(p)、D(p)、L(p)分别表示路径带宽、路径时延与路径丢包率。

定义3（路径优先函数）给定一条路径p，其优先级函数综合考虑定义2 中路径的3 个Qos 参数，优先函数f(p)定义如下：

其中，Bmin与Dmax分别是应急响应系统数据传输所能容忍的最小带宽与最大路径时延，α、β、γ分别是3 种Qos 参数的权重因子，三者的范围为[0,1],α+β+γ=1。通过公式（7）的处理，路径优先函数的取值范围为[0,1]。

本文所提出的算法MLSA 将利用路由发现过程得到的多条可行路径，在相应路径优先函数f(p)的条件限制下进行数据的逐跳传递，结合强化学习过程进行网络拥塞的实时感知，完成系统流量的均衡及路径的动态更新。

3.2 使用强化学习模型进行系统建模

强化学习模型通过感知系统现有状态，评估计算采取下一行为对系统带来的增益，从而选择执行对系统状态带来较大增益的行为；节点执行状态更改决策后，收到执行该行为获取的系统增益值[18]。如图1 所示，网络中各个节点在路由发现过程t时刻采取不同的动作策略ai(t)，共同对整个网络进行影响，节点完成从状态si(t)到状态si(t+1) 的转换，获得环境回馈的相应回报值ri(t+1) ，各节点重新评估自身价值函数Vi(s)并将其广播到邻居节点；此外，其他未被采用策略集上积累的信息素含量随时间的流逝而蒸发。

图1 强化学习决策过程

由于提前引入了数据包传输的最大TTL值，即数据传输过程中系统的状态转移次数总是限制在整体系统状态集S内，单一节点的系统状态评估值可应用无限视野价值评估模型：

进行计算，同时设置未来有限步内的系统状态转换所带来的增益rt具有相同的权重γ。系统优化问题转化为，调整从源节点S到目的节点D经过的所有数据传输节点的决策过程，以取得最大的价值函数V(s)值，下面介绍求解过程。

定义系统状态集为S，当前状态下可以执行的动作集为A，则系统增益R和状态转移分布函数T均可表示为S和A的某种运算结果，这里用R(s,a)表示从状态s执行动作a带来的系统增益，T(s,a,s′)表示s经过动作a后转移到s′的概率。通过求解贝尔曼方程可以得到系统的最优解V*(s)：

其中，γ为状态转移增益权重，V*(s′ )对应于状态集S中每个状态s′的当前价值评估值。相应的，采取使得价值评估函数V*(s)取得最大值的动作a作为下一步的状态转移操作。

取T(s,a,s′ )为每条通信链路数据投递成功与失败的比例，为了计算T(s,a,s′ )，在每个节点记录尝试发送的单播包数NA、单播传输失败包数NF、接收到的单播包数NR、接收到的广播包数NB和混杂接收单播包数NP等统计量；考虑网络的动态变化性，指定有效统计时间窗口，即选取从当前时间往前的一段时间内的统计量作为有效统计量。对于单个节点来说，自身发送数据包的统计值较成功接收数据包的统计值具有更高的可信度，因此在计算投递率时，接收数据包统计量前添加置信参数σ；此外，将ρ作为节点未发送数据包时的投递率估计值，最终投递率计算公式表示为：

公式（10）对应系统下一状态切换到投递成功s′=S时的转移概率T(s,a,S)。在路由过程中，对于一次成功的数据传输，其消耗的系统能量最小，将该过程获得的强化函数值标记为rS，其系统消费归一化为-1；同样地，对于一次失败的单跳数据传输，将该过程获得的强化函数值记为rF=-7，其系统消费对应于底层802.11 MAC 协议的最大重传次数7[19]。由于指定了rS和rF为确定值(-1和-7)，相应的

为T(s,a,s′ )的简单组合函数。确定了评估模型T(s,a,s′ )、R(s,a)，最优值函数V(s)的计算可以通过求解贝尔曼方程：

考虑每个动作集a仅导致当前状态s朝两种可能的状态转变，假设下一跳节点为P，则系统的状态转变为：发生传输成功事件S，使得系统由当前状态s=N转化到s′=P；或发生传输失败事件F，使得系统当前状态s=N保持停留从而s′=N。因此系统Q值的计算如下式所示：

其中，pS是数据包成功传输到节点P的概率，相应的pF是传输失败的概率。根据公式（14）：

转化为求解

从而

一旦最优值函数由评估模型计算得到，最佳的决策过程便是采取使每个状态能够获得最大Q值的动作，称该优化决策过程为系统的开发策略。鉴于开发策略是由系统评估模型计算得到，而应急网络具有较高动态性，评估模型会随着时间变化；同时评估模型又依赖于系统的探测过程，因此为了执行较优的开发策略，需要对系统进行连续的探测。

3.3 系统模型的连续探测

为了利用已学习到的系统知识进行决策过程，并且同时能够连续地对系统进行探测过程，以更新系统模型，本文提出使用如下策略：

（1）使用玻尔兹曼决策过程，对系统已知的动作集进行概率转移，根据执行动作回馈信息更新网络模型，有利于控制系统探测过程的频次，使路由选择朝着最优的方向前进，决策过程如下式所示：

其中，u(a)反应了决策a对系统带来的实际效用，参数T反应了系统选择次优决策过程的可能性，即参数T越大，系统选择次优决策的可能性越大，该参数将极大影响系统建模所需的探测过程频次。

（2）设计周期性的探测过程用来发现邻居节点，在路由过程中选择价值函数较高的节点作为下一跳。当一个节点尝试发送单播或广播数据包时，会在数据包头添加关于源节点S和目的节点D的最优值估计，当邻居节点接收到该数据包后，会利用这些估计值更新自身对S和D的最优值记录。此外，考虑到系统网络拓扑的动态变化性，同时需要对旧的记录值进行蒸发操作，以不断减小无用信息对路由决策的影响，具体更新过程如式（18）所示：

图2 数据包格式

其中，Vadv(s)是该节点最后接收到的关于节点s的最优值通告，ΔT(s)是从最后一次接收到该通告值过去的时间，λ用来控制记录值的消散速率。

（3）为了限制探索过程只在对系统感兴趣的相关部分进行，且保证发送数据包较探测过程的优先级，使用贪婪算法规避对当前决策无用的部分进行探测。由于系统全局信息难以获取，本文提出的方法只计算处于数据包投递路线上相关节点的价值函数而不是针对整个网络的所有节点进行计算。MLSA 将采用按需路由的方式，即当有数据请求到来时才进行路由发现过程，因此可以将相关的系统评估信息附加在数据包上用于邻居节点信息素的更新，使得学习过程仅在数据传输链路附近进行，从而缩减了系统开销；此外，将评估信息附加在数据包上进行传递，较发送独立的路由包而言降低了网络传输负载。

4 MLSA算法实现

根据协议设计策略，构造数据包格式如图2。其中，括号中数字表示对应域所占字节数，单位：字节（Byte）。

其中，Qos 参数需求指示下一跳最低传输限制，对应于优先函数f(p)限制值；源节点价值函数估计值记录了数据包原始传输节点价值函数VS(s)值，目的节点价值函数估计值记录了目的节点价值函数VD(s)值；错误标记位指示数据包传递过程中下一跳是否发生传输失败；而数据包序列号可以用来判断是否收到重复报文，并执行相应的丢弃操作。

MLSA路由算法流程概述如下：

（1）系统启动阶段，网络各节点进行邻居发现并收集各链路Qos 状态信息。

（2）当数据传输任务到来时，检测路由表项中是否存在到目标节点的路由条目，存在则根据公式（7）选择相应的路径进行数据传输；否则启动路由发现过程。

（3）当节点收到路由包时，检测是否是重复路由包，并丢弃重复路由包；若数据包目的节点为当前节点，发送后向蚂蚁包通告源节点S数据传递成功，更新当前价值函数V(s)的值，并广播到邻居节点；若数据包记录目的IP地址非本节点，则选择邻居节点中对应价值函数值最大的动作a，进行到下一跳的数据传递。

（4）路由建立阶段，当节点收到路由发现广播包时，按照公式（16）的玻尔兹曼探测模型，结合邻居节点的价值函数，进行连续探测过程；同时更新系统状态评估模型，建立到目标节点的最优路径，该过程将统计链路丢包率、时延、带宽等状态信息。

（5）数据传输过程中，若当前节点找不到满足路径优先函数f(p)限制条件下，指定动作所a对应的下一跳节点，则以该节点为源节点S进行路由发现过程，转至步骤（4）。

（6）在数据包传递过程中，前向蚂蚁包到达的每一跳路由节点，将根据采取的动作a所带来的回报值ri(t+ 1)更新自身价值函数V(s)，并将新的价值函数广播到邻居节点；从而该节点在相关路径上积累了较高的信息素含量，以该节点作为下一跳的决策a，在邻居节点的动作集中具有较高的选择优先级。同时，链路性能较差或移动性较强的节点，仅在其通信局部范围内拥有较高的价值函数而被选取为备选路径；而在其他网络节点的信息素更新策略中，仅按照公式（17）进行信息素累积量的衰减。

5 MLSA算法评估

使用NS2进行MLSA路由算法的网络仿真，配置仿真场景对应于实际应急网络环境，即网络拥有少量服务器节点（这里配置为3），作为Mesh子网络边界的网关节点，同时设置大量网络无线节点，具有1～60 m/s 不等的移动速度，运动方向设置为在二维平面内随机做出选择；各移动节点配置为在任意时刻，以随机通信时长间隔的方式，进行到邻近服务器节点的数据传输，传输数据为指定大小（512 Byte）的udp数据包。其他网络参数配置为，仿真场景大小1 000 m×400 m，使用802.11作为MAC层协议，无线传播模型为two-ray-ground。最后做出说明，对于移动节点到服务器（接入点）的选择，将由路由算法根据到邻居节点的强化学习评价值进行自主决策，优先连接到强化学习评价值最高的服务器节点。实验拓扑如图3所示。

图3 实验拓扑环境

该场景下网络节点数设置为30～50，当移动节点数小于15 时，由于平均范围内节点数目过少而无法建立持续有效的传输链路，导致网络数据传输不能正常进行；节点数大于60时，由于节点数量增加带来的局部网络拥塞较为严重，无法继续通过增加网络负载有效控制网络整体拥塞程度。最终对照实验取网络节点数目为45。

此外，全局蚁群算法寻优参数设置如下，对应公式（1）中剩余信息素值τij权重因子α取0.5，期望函数ηij权重因子β取1，该部分参数的获取为在α 取值范围为0.1～0.9，β取值范围为1～5，经过大量对照实验得到的能使蚁群算法快速收敛的最优参数解；局部强化学习模型中评价参数设置如下，对应公式（11）中一次成功传递的强化函数反馈值rS取-1，一次失败传递的强化函数惩罚值rF取-7，该部分参数的设置充分考虑底层802.11 MAC协议的最大重传次数为7，并将一次数据包传递产生的代价归一化为1。实验证明，取以上组合参数有利于蚁群快速寻优和强化收敛过程的完成。

为了测试MLSA对网络拥塞的适应能力，逐渐加大网络通信负载的数据传输率，与按需路由的代表协议DSR[20]及AODV[21]进行同一场景下的数据传输性能对比，实验结果如图4～6 所示。其中图4 显示了随着拥塞程度的增加，DSR和AODV的投递率迅速降低，而MLSA协议由于使用了对系统的动态探测过程，不断更改最优路径决策，使网络流量尽可能多地分配到更多次优的链路上（全局次优，当前最优），从而在很大程度上缓和了网络的拥塞程度，数据包投递率下降缓慢。

图4 网络拥塞对投递率的影响

图5 网络拥塞对传输时延的影响

图6 网络拥塞对吞吐量的影响

图5 显示了在网络拥塞的情况下，AODV 和MLSA均表现出较低的平均数据传输端到端时延，总体上看，MLSA平均时延变化较为稳定，呈现与拥塞程度增长的正比例关系，且相对于其他两个路由协议在同一量级的网络拥塞下具有更小的平均传输延时。

图6 显示了在拥塞情况下三个路由协议网络吞吐量的表现，AODV 和DSR 曲线的网络吞吐量先是随着网络负载通信流量的增加而快速增长，最后网络吞吐量趋于一个上限阈值，实际上，在路由表记录的最优路径上，大量数据包未能被成功缓存而丢弃，体现在图4 中数据投递率的下降；而MLSA由于使用对系统的动态探索估计，当发现最优路径上存在拥塞情况时，能及时调整寻优策略，改选路径发现阶段记录的次优路由条目进行流量均衡，然而，由于无线自组织网络中每个节点的邻居数目有限，当网络拥塞持续增加时，数据传输节点无法再将多余的流量平均到更多的路径上，从而导致网络吞吐量的下降和丢包率的上升。

6 结论

本文针对应急通信中网络拓扑的快速动态变化及突发的网络拥塞现象，详细分析了传统蚁群路由算法在该应用场景下不再适用的原因，提出了一种适用于应急通信网络的路由算法MLSA，利用蚁群算法框架结合强化学习过程进行系统建模，将网络链路性能统计分析过程限制在较高优先级的区域，通过探测局部邻居节点的状态信息，对不同路由决策过程进行打分，并根据网络反馈做出策略调整，从而改善网络整体性能，有利于缓解网络拥塞，增加了数据传输的实时性、稳定性。实验证明，在较高节点移动性环境下，针对应急通信中产生的网络拥塞现象，MLSA较经典按需路由协议AODV和DSR，具有明显的性能优势。