基于蚁群优化的混合多路径QoS路由协议

顾斌，陆杰，张策

（1.南京邮电大学通信与信息工程学院，江苏 南京 210003；2.中国电科新一代移动通信创新中心，江苏 南京 210019）

0 引言

移动自组网（MANET,Mobile Ad hoc Network）是由无线链路连接的移动节点组成的网络[1-4]。在这种网络中，节点的位置和连接状态都会频繁变化，因此需要具备适应快速变化环境的路由协议。目前，针对MANET 已经开发了许多路由协议，如AODV（Ad hoc On-Demand Distance Vector Routing，无线自组网按需平面距离向量路由协议）、DSR（Dynamic Source Routing，动态源路由协议）、OLSR（Optimized Link State Routing，优化链路状态路由协议）等，然而，这些协议都着眼于找到从源到目的地的可行路径，它们未能很好地适应多种网络流量和QoS（Quality of Service，服务质量）需求，而当今众多应用程序正需要高质量的网络服务。因此，对路由协议进行QoS 保障成为必要之举。

合理的QoS 路由协议能够为业务提供满足一系列服务要求的路径[5-8]，这些服务要求是通过带宽、延迟、抖动、丢包率等多个可量化的指标来度量的。

近年来，研究者们从负载均衡、带宽预留等角度提出许多QoS 路由协议，扩展了传统路由协议，根据路由发现和维护策略这些协议可以划分为两类：主动式路由协议和反应式路由协议[9]。主动式路由协议维护节点的完整路由信息，以便在需要转发数据时迅速找到合适路由，这类协议需要持续更新和交换路由信息以应对网络拓扑变化，其路由开销较大。而反应式协议则仅在节点需要传输信息时才寻找路由，避免了周期性的路由信息交换，从而减小了路由开销。文献[10] 应用多路径路由策略提高了分组投递率和吞吐量，但是开销很大，并且无法应对快速移动场景下的QoS 路由问题。文献[11] 在传统AODV 基础上引入跨层路由以解决QoS 路由问题，却没有考虑业务对时延的要求。

由于多约束QoS 问题在文献[12] 中已经被证实是一个NP-C（Nondeterministic Polynomial Time Complete，非确定性多项式时间完全）问题，并且针对NP-C 问题人们大多采用启发式算法解决，使得蚁群优化算法、遗传算法等智能算法得到广泛应用。而蚁群优化（ACO,Ant Colony Optimization）通过模拟蚂蚁寻找食物的行为，具有一些独特的特性，包括分布式计算、正反馈机制、贪婪启发式和灵活性等。首先，ACO 算法的分布式计算特点与传统的集中式算法不同，其将问题分解为多个蚂蚁个体，每只蚂蚁根据局部信息素和问题相关的启发式信息独立地选择路径和做出决策，再将其经验贡献到全局信息素中，使它们在分布式环境中协作解决问题，在处理网络模型问题时具有出色的拓展性和并行性。其次，正反馈意味着蚂蚁更有可能选择已知信息素浓度高的路线，有助于加速全局最优路径的搜索。最后，蚂蚁在路径选择时不仅考虑信息素浓度，还考虑基于需求设计的启发式信息，可以帮助蚂蚁更有针对性选择路径，提高路径质量。基于蚁群优化的这些特性，使得本文选择它处理路由多约束QoS 问题。文献[13] 基于AntNet 蚁群算法引入QoS约束机制，考虑负载均衡来选择节点。文献[14] 基于蚁群算法综合考虑带宽、跳数、端到端时延三种QoS 参数来计算路径优先的概率，以选择合适的路径来传输数据。文献[15] 引入奖励函数，信息素更新时奖励优秀蚂蚁，提高了算法的收敛能力。文献[16] 提出基于蚁群算法的混合路由，其在路由建立时考虑端到端延迟指标和节点位置信息。文献[17] 提出基于区域的混合路由协议HRP，综合DSDV 和DSR 协议的优势，具有从主动性切换到反应性的功能。

虽然以上QoS 路由协议具有一些优势，但是这些协议存在一些局限：

（1）缺乏考虑不同种类业务问题，不同应用可能对QoS 参数有不同的要求，没有充分考虑带宽、时延、丢包率、链路拥塞、费用要求。

（2）传统蚁群算法会存在收敛速度慢，易于陷入局部最优解问题。

（3）大多协议没有兼顾路由建立和维护两个关键阶段，使得协议在动态网络环境下十分脆弱。

针对以上局限性，本文提出了一种基于蚁群优化的混合多路径QoS 路由协议。首先，HMQ-ACO（Hybrid Multipath QoS Routing Protocol Based on Ant Colony Optimization）引入多约束QoS 指标，充分考虑多种业务需求，如会话和交互类业务。其次，协议中蚁群优化算法改进了传统蚁群算法，先是加入新的启发式信息来建立路径选择模型，并采用多路径并行搜索以避免陷入局部最优解，然后重新设计局部和全局信息素更新规则，引导蚂蚁选择较优的路径，来加快蚁群算法收敛速度。最后，HMQ-ACO 结合主动式和反应式路由协议的优点，设计反应式蚂蚁和主动式蚂蚁来建立和维护最佳路径。

1 系统模型与问题分析

1.1 系统模型

移动自组网QoS 路由是一种实现端到端满足QoS 参数需求的路由机制，考虑所有移动节点间的链路具有相同的信道环境，系统模型可用一个无向加权图G(V,E)来表示[18]，其中V表示节点集合，E表示所有节点之间链路的集合。对于任意链路e∈E，可以定义以下链路的QoS 参数[19]：时延函数D(e)、带宽函数B(e)，费用函数C(e)。同样地，对于每个节点n∈V，可以定义节点的QoS 参数：时延函数D(n)、丢包率函数L(n)、拥塞函数G(n)，费用函数C(n)。

对于一条从源节点s到目的节点d的路径p(s,d)，该路径的QoS 参数表示如(1)～(5)：

1.2 问题分析

MANET 中QoS 路由选择问题就是在网络中找到一条路径p(s,d) 使得K(p(s,d)) 最大，费用C(p(s,d)) 和拥塞度G(p(s,d)) 较小且满足以下约束：

其中Dq为最大允许延迟，Bq为最小带宽，Lq为最大允许丢包率。

K(p(s,d))是QoS 路由目标函数，基于延迟D(p(s,d))、带宽B(p(s,d))和丢包率L(p(s,d))。表示为式(9)：

式(9) 中函数fD、fB、fL分别是基于延迟、带宽和丢包的惩罚函数，分别定义为：

λD、λB、λL分别是fD、fB和fL的正向权重，用于表示在目标函数中时延、带宽和丢包率的相对重要性,且λD+λB+λL=1。fD、fB和fL分别是时延、带宽和丢包率参数的惩罚函数。路径满足要求的时延、带宽和丢包率时不惩罚，否则惩罚值为rD(0＜rD＜1)。类似地，rB和rL的值也在相同的范围内。

为了确保各种类型应用所需的服务质量。对于延迟敏感的流量（如会话业务），可以将λD分配更高的值，以减少λB和λL代价。对丢包率敏感的流量（如交互类业务），赋予λL更高的值。通过这种灵活的参数设置为各种流量类型提供了定制化的服务以满足多样化的用户需求[20]。

根据系统模型定义，本文的QoS 路由协议即为在满足式(6)～(8)QoS 约束条件下，寻找K(p(s,d))最大的路径，同时最大程度使费用和节点拥塞度小。这是一个多约束条件下的目标优化问题，传统的求解算法如穷举搜索、贪婪算法、遗传算法等，在面对此种问题往往表现出效率低下、易陷入局部最优、解权衡困难等问题。而蚁群优化算法以其信息素引导机制、全局搜索等特性，有助于平衡多个目标的权衡，避免陷入局部最优解，而且具备一定的灵活性，可以通过调整信息素更新以及其他参数适应不同约束条件和目标函数需求。所以本文采用蚁群优化算法对QoS路由问题进行求解。

2 基于蚁群优化的混合QoS路由协议

2.1 蚁群优化算法

（1）路径选择概率模型

蚁群算法出色的全局搜索能力源于它在选择下一跳时的灵活性。在蚂蚁移动过程中，信息素浓度和启发式函数会不断更新，从而影响蚂蚁选择路径的决策。为了充分发挥启发式因子的作用，蚂蚁k由节点i转移到j的路径选择概率表示为公式(13)：

式(13) 中τij(t) 表示当前链路(i,j) 上的信息素值；α是信息素的影响因子，β是节点拥塞度的启发式因子。γ和σ是控制时延和丢包率的启发式因子，Ni是节点i的邻居节点集，j是节点i的邻居节点且其不在禁忌表中。

ηij启发值考虑费用和节点拥塞度，尽量避免选择拥塞度高和费用高的节点作为下一跳。ηij与Cij、Gij定义为式(14)。拥塞度取决于位于节点i处等待在发送队列上数据包的个数qij，费用主要考虑跳数。

γ和σ是相对取值，对于会话类业务的数据流[21]，γ＞σ，如话音数据要求低延迟。对于交互类业务，如远程操作要求低丢包率，γ＜σ。

（2）信息素的局部更新规则

当蚂蚁经过链路(i,j)时，信息素浓度τij(t)会按照下式进行局部信息素更新，其目的是实现信息素局部调整，由于此规则会使链路上的信息素浓度有所减少，所以会减小已选择过的路径再次被选择的概率，避免陷入局部最优。

式(15) 中ρ∈(0,1) 为信息素挥发因子；τ0为初始信息素浓度。

（3）信息素的全局更新规则

当所有蚂蚁完成了一次迭代后，按式(9) 计算其目标函数值K，K值较大的M(M≤3) 条路径上的信息素按式(16) 进行全局信息素更新。

通过全局更新规则，蚂蚁将逐渐聚集在满足QoS 约束且K值较大的M条路径上，K值最大的为最优路径，其他作为备用路径。

式中，ρ为信息素挥发因子，0＜ρ＜1。Q为奖励信息素常量。

2.2 HMQ-ACO路由协议流程

HMQ-ACO 是混合式路由协议，综合了反应式路由建立和主动式路由维护的策略，以达到有效的路径选择和优化目的。反应性表现在节点在会话开始时才建立到目的地的路由，而主动性则表现在会话期间，协议尝试维护和改进已建立的路由信息。HMQ-ACO 通过创建多条路径来连接源节点和目的节点，从而提高网络的可靠性和鲁棒性。

(1) 反应式QoS 路由建立流程

当源节点(标记为s) 与目的节点(标记为d) 需要建立会话时，且当前的路由表中不存在满足会话QoS 要求的s到d的路径时，开始进行反应式路由建立。此过程包括两种控制包：反应式前向蚂蚁（RFA，Reactive Forward Ant）和反应式后向蚂蚁（RBA，Reactive Backward Ant）。反应式路由建立步骤如下：

步骤1.反应式前向蚂蚁RFA 从源节点广播出发，其结构如图1 所示。RFA 携带源节点地址、目的节点地址、蚂蚁代数编号、QoS 约束指标值、路径上的QoS 度量值以及禁忌表P，记录从源节点s 到目的节点d 经过的节点；

步骤2.当中间节点i收到RFA 时，先根据RFA 中的源节点地址和代数编号判断是否处理过此报文，如果是，直接丢弃；然后检查自身地址是否在禁忌表P 中出现，如果是，直接丢弃，以避免环路；否则进入步骤3；

步骤3.节点i收到RFA 时，检查是否为目标节点。若是，进入步骤4；否则执行以下操作：

①提取RFA 的时延值D，判断D 与本节点的处理时延之和是否满足时延约束。若不满足，则丢弃RFA；否则，继续执行②。

②判断节点i的剩余带宽是否满足RFA 的带宽约束。若不满足，表明自身带宽资源不满足QoS 要求，丢弃RFA；否则，继续执行③。

③检查节点的丢包率是否满足RFA 的丢包率约束。若不满足，丢弃RFA；否则，继续执行④。

④将RFA 携带的代数编号和源节点地址添加到本地识别列表，对于从源节点到当前节点的路径，进行本地路由表的添加或更新操作，以反映出反向路由的信息。路由表包括了源地址、目的地址、下一跳节点地址和跳数，同时还有与业务相关的QoS 约束，包括业务带宽约束、时延约束和丢包率约束，以及当前节点拥塞度。

⑤将RFA 的代数编号k提取，则当蚂蚁k在中继节点i发现到目的节点d有多条可用的路由时，根据式(13)的概率Pijk选择下一跳节点j。

⑥当前向蚂蚁k完成一次路径选择后，RFA 在转发到下一跳的过程中，链路(i,j) 的信息素按照式(15) 进行局部信息素更新。

步骤4.所有反应式前向蚂蚁从s到d的旅程结束，即当所有蚂蚁完成一次迭代，根据式(9) 计算每只蚂蚁的目标函数K。

通过评估每次迭代后不同蚂蚁所经过路径的目标函数值，选择K值较大的M只反应性前向蚂蚁，对它们进行信息，然后销毁这些蚂蚁。随后，构造反应式后向蚂蚁RBA，其结构如图2 所示，将来自RFA 的相关信息填充到RBA 相关字段，具体包括跳数值和信息素奖励值。此外，还将之前禁忌表P反过来添加到RBA 中。最终它将沿着RFA 的路径单播返回到源节点s。

图2 反应式后向蚂蚁结构图

步骤5.反应式后向蚂蚁不被广播，每经过一个中间节点i，会进行以下操作：

①蚂蚁k每到一个节点按式(17) 更新本地路由表的跳数信息：

式(17) 中hij表示节点i经节点j到达目的节点d的平均跳数历史记录；hijk表示蚂蚁k由当前节点i经j到达d的跳数；α∈[0,1] 表示对新信息的采纳程度。

②根据式(16) 的全局信息素更新规则更新本地信息素表。

步骤6.RBA 回到源节点s，该蚂蚁被丢弃，此时建立了源节点到目的节点的正向路由。

根据步骤1 至步骤3 画出反应式前向路由建立过程如图3 所示，根据步骤4 至步骤6 画出反应式后向路由建立过程如图4 所示。

图4 反应式后向路由建立过程

在建立了到目的节点路径之后，会通知业务进行数据发送，数据包根据路由表中的信息进行转发。如果节点存在多条到目标的路径，则尽可能选最优路径。

（2）主动式QoS 路由维护

主动式路由维护旨在通过更新信息素值来保证路径选择的准确性和时效性，从而有效维护网络的路由状态。

源节点周期性地派发主动式前向蚂蚁（PFA，Proactive Forward Ant），以维护已构建路径的完整性并寻求更优或替代性的路径。PFA 结构与RFA 相同，并且都是由源节点广播，中间节点单播转发,其派发速率会根据网络负载情况和流量变化动态调整，与主动数据发送速率相协调。

PFA 在传播过程中收集与已建立路径有关的最新信息，并通过转化为相应的主动式后向蚂蚁（PBA，Proactive Backword Ant），更新路径上节点的路由表中的信息素值。

（3）链路断裂检测和路由修复

移动自组网中的链路断裂是一个重要的问题[22]，因为移动节点之间的链路不稳定，容易导致通信中断。为了检测链路断裂，协议中采用Hello 消息蚂蚁（Hant，Hello Ant）检测机制和数据包传输失败检测机制两种。Hant 结构包含源节点地址、蚂蚁代数编号、检测标志位。

每个节点定期发送Hant 管理邻居节点，Hant 只在一跳内转发，不能广播。若某节点在一定时间内未收到来自邻居的Hant，则是为检测到邻居链路断裂，会采取以下措施：本地节点将该邻居节点从邻居列表删除，并会向其他邻居节点广播链路断裂的消息，所有接收到此消息的邻居也会更新路由表。

如果源节点检测到数据包传输失败，并且不存在其他可用路径，则将数据包放入缓冲区并启动路由修复过程。

路由修复过程是由路由修复前向蚂蚁（RFFA，Route Fixing Forward Ant）和路由修复后向蚂蚁（RFBA，Route Fixing Backward Ant）完成，主要是为了尽快寻找到到达目的点的路径，RFFA 和RFBA 结构相同，包括目的节点地址、源地址、代数编号、失败链路信息。RFFA 沿着反应式前向蚂蚁所采取的路径前进到指定目的地（在该节点广播，在后续节点单播），然后转化成为RFBA 返回源节点。如果RFBA 返回到源节点，则继续发送存在缓冲区的数据包。如果在一定时间内没有收到RFBA，则节点会认为路径修复失败。然后，它会广播丢失目标的链路故障通知并丢弃所有临时缓冲的数据包。

3 仿真设置与结果分析

3.1 仿真设置

本节对提出的HMQ-ACO 路由协议进行仿真验证，并选择AODV、文献[13]AntNet-QoS 协议以及文献[16]中的路由协议作对比分析，选择它们的理由是为了充分评估HMQ-ACO 在MANET 中的性能和优越性。首先，AODV 代表传统的反应式路由协议，其优势在于快速路由建立，与其对比，旨在评估HMQ-ACO 在网络动态性较高时路由建立和数据传输表现以及能否有效降低时延。其次，文献[13] 中AntNet-QoS 基于蚁群算法并考虑了带宽、时延等QoS 约束，与其对比，来衡量HMQ-ACO在QoS 支持方面的性能。最后，文献[16] 路由协议基于蚁群优化算法并采用混合路由方法，与之对比，考察HMQ-ACO 在复杂网络环境中的QoS 保障性能，以及是否能够建立并维护好路由，保证较高分组传递率。

仿真中节点按照RWP（RandomWaypoint，随机路径点）移动模型来移动，并会有停顿时间。采用两径衰落信号传播模型模拟无线电传播，物理层采用IEEE 802.11协议，链路带宽为2 Mbps。MAC 层使用802.11b 协议。考虑通信业务主要为话音数据流。仿真场景参数配置如表1 所示，协议参数配置如表2 所示。

表1 仿真场景参数配置

3.2 结果分析

本节考虑了数据包的端到端延迟和传递率这2 个性能指标。

首先，在第1 组实验中，改变节点速度从5 m/s 变化到30 m/s。仿真结果如图5 和图6。

图5 端到端时延与节点速度

图6 分组投递率与节点速度

图5 为不同协议随节点速度变化时的端到端时延。显然AODV 的时延性能较差，由于它只能寻找从源到目的地的最短路由，而且其所构建的路径不符合QoS概率也很高，当其在QoS 业务不能满足要求时，它会重复构建路径，从而造成了平均端到端时延随速率的较大幅度上升。而其他的3 类ACO 协议均采用QoS，尽管时随着速率提高端到端时延也会有所增加，但受到平均端到端时延的制约，其平均端到端时间延迟的增加幅度相对较小。

图6 为不同协议随节点速度变化时的分组投递率。对于所有协议，分组投递率都随着节点速度的增加而降低。值的注意的是3 种基于蚁群优化思想的协议在分组投递率方面表现明显均优于AODV，这种优势归因于AODV在建立路由时未考虑QoS 支持，因此在传输QoS 敏感的业务时，其传输失败率相对较高。在这些ACO 类协议中，HMQ-ACO 达到了最高分组投递率,这一成就可以归功于在路由建立过程中尽量避免了拥塞节点，因此在这一方面胜过了AntNet-QoS 和文献[16] 的协议。

接下来，第2 组实验中逐步增加节点数量，从100增加到800，同时按比例增加网络面积以保持节点密度稳定。图7 和图8 展示了相应结果。

图7 端到端时延与节点数量

图8 分组投递率与节点数量

图7 为不同协议随节点数量变化时的端到端时延。HMQ-ACO 表现很好，但是AODV 落后很多，而且随着网络规模的增加，差距越来越大。AntNet-QoS 和文献[16]协议时延表现相近。

图8 为不同协议随节点数量变化时的分组投递率。4种协议的分组投递率都会随着节点数量的增加而下降。但HMQ-ACO 能够比其他协议正确的传送更多的数据包。此外，性能的差距随着网络规模的增加而增加。对于最大的网络规模，HMQ-ACO 仍能提供80% 的投递率,这是由于HMQ-ACO 可以搜索多条路径，有很多替代方案，因此在链路故障后重建路由相对容易。而AntNet-QoS 和文献[16] 协议时延表现相近。

4 结束语

本文针对MANET 中传统蚁群优化QoS 的路由协议的局限性，改进了蚁群算法的路径选择模型和信息素更新策略，并采用特殊的混合路由协议设计思想，综合考虑多种QoS 约束指标以及链路拥塞度、费用，提出基于蚁群优化的混合多路径QoS 路由协议HMQ-ACO。仿真结果表明，HMQ-ACO 在端到端延迟、数据包传递率方面表现较好。在未来的研究工作中，会考虑更多业务种类，并优化路由协议的开销。