一种基于蚁群优化的DSR 路由协议*

梁哲文，张少杰，龙 飞

（北京慧清科技有限公司，北京 101500）

0 引言

隐蔽通信网络是一种不依赖基础设施的移动自组织网络，具有通信带宽小、通信距离远且网络拓扑变化慢等特点[1]。为了实现通信的隐蔽性，隐蔽通信网络的路由协议需要及时发现并动态维护跳数较少、传输可靠的路由，在保证低延时、高可靠的前提下，尽可能降低数据报文的转发次数。目前，隐蔽通信网络多采用动态源路由（Dynamic Source Routing，DSR）协议。该协议为按需路由协议，在数据报文发送时由源节点按照最短路径准则计算完整路由，不需要中继节点进行路由计算，从而降低了路由报文的发送开销。但是，DSR 协议没有考虑跳数、链路质量以及中继节点缓存等对路由的影响，造成路由中断概率高、数据传输延时大等问题，无法满足隐蔽通信网络的需求[2-3]。

蚁群优化（Ant Colony Optimization，ACO）算法利用蚁群的智能功能高效地在复杂的网络拓扑中找到最优路径，为隐蔽通信网络路由协议的设计提供了新的思路[4-5]。文献[6]提出了移动自组网蚁群路由（Ant Routing for Mobile Ad hoc Network，ARMAN）。该协议的路由发现过程与AODV 协议类似，在计算路由时根据端到端延时、链路容量等QoS 相关指标计算信息素以及选择概率，可以实现网络QoS 指标的改善。但是，该协议为逐跳路由协议，每个中继节点都需要计算路由并选择下一跳，因此节点需要周期性地广播HELLO 分组来进行路由维护，不适合隐蔽通信网络降低传输次数的需求。文献[7]同样针对AODV 协议做出了改进，在计算信息素时考虑传输可靠性、节点的拥塞状态和剩余能量，在改善端到端性能的同时通过能量均衡提高网络寿命。文献[8]提出的蚁群路由算法（Ant based Routing Algorithm，ARA）路由旨在优化无线传感器网络中节点的能量消耗，在节点信息素低于某个阈值时进入休眠模式以节约能量，从而实现节点间能量消耗的均衡。改进的蚁群路由算法（Improved ARA，IARA）对ARA 中的冗余邻居节点进行筛选，采用角度因子和距离因子限制搜索方向，避免产生无关路径。但是，该算法的节点计算复杂度高，收敛速度慢[9]。文献[8-9]主要关注网络中节点的能量消耗，无法解决隐蔽通信网络对路由开销和传输可靠性等指标的要求。

针对上述问题，本文在传统移动自组织网络动态源路由协议基础上，设计了一种基于蚁群算法的DSR 路由协议（Ant Colony based DSR，ACDSR）。本文第一次将蚁群算法融入DSR 协议，扩展了路由报文和ACK 报文并将其建模为蚂蚁，将其携带的链路质量和节点队列缓存映射为信息素，根据路由跳数计算启发函数计算各路由的选择概率，动态使用选择概率最高的路由发送数据报文。本文使用Opnet 实现了AC-DSR 路由协议，通过与传统的DSR 路由和基于ACO 的ARMAN 路由协议的性能对比，验证了AC-DSR 在路由协议开销、端到端延时等方面的性能上有显著提升。

1 基于蚁群算法的DSR 路由协议

与传统DSR 协议类似[10]，AC-DSR 协议包含3个功能模块。一是路由发现模块。源节点通过路由报文的交互获得多条通往目的节点的路由，并掌握多条路由的中继节点队列缓存、链路质量等信息建立路由表。二是路由选择模块。源节点考虑路由表中各路由的跳数、中继节点队列缓存以及链路质量等因素，实时计算各路由的信息素，并根据信息素推导选择各路由发送数据报文的概率，最终使用选择概率最高的路由发送数据报文，同时根据接收到的数据报文ACK 动态更新路由的信息素。三是路由维护模块。发现路由失效的节点向源节点发送路由报文，其他中继节点根据该路由报文更新路由表，并重新计算各路由的信息素以及对应的路由选择概率。

为了便于介绍，将以图1 的典型网络拓扑结构为例，对设计的AC-DSR 协议流程进行说明[11]。图1 中的顶点表示通信节点，不妨假设S 为源节点，D 为目的节点，连接顶点的边表示节点之间的无线链路，顶点上方数字表示该节点队列缓存中待发送数据报文的数量，无线链路上的数字表示该无线链路的质量。

图1 隐蔽通信网络拓扑结构

1.1 路由发现

源节点S 在发送数据报文前，首先在其路由缓存表中查找是否存在到目的节点D 的可用路由。不存在可用路由时，节点S 将需要发送的数据报文加入队列缓存，然后开始路由发现过程来动态查找通往目的节点的路由。AC-DSR 路由发现过程如图2所示，主要包括以下几个阶段。

图2 AC-DSR 路由发现过程

1.1.1 节点S 广播发送RREQ 报文

当前在节点S 无线传输范围内的所有节点（包括节点A 和B）都能够接收到节点S 广播发送RREQ 报文。节点S 发送的RREQ 报文内容如表1所示。

路由域表示该条路由所经过的各中继节点的地址。链路质量和缓存数量域分别表示该路由所经各链路的质量和各中继节点的队列缓存数。生存时间域表示该RREQ 报文剩余的可传输跳数。该数值与协议支持的跳数有关。

1.1.2 节点A 和B 收到节点S 发送的RREQ 报文

以节点B 为例进行说明。节点B 收到RREQ报文后，先读取报文中的目的地址信息，发现自身并不是目的节点，然后读取报文中的路由记录，发现在路由记录表中没有记录自身的地址。节点B 读取RREQ ID 并搜索其维护的＜源地址,RREQ ID,路由记录＞表，发现不存在＜S,1,Null＞项。因此，节点B 将＜S,1,NULL＞保存在＜源地址,RREQ ID,路由记录＞表中，将自身地址添加到该RREQ 报文的路由记录域中对应的位置，计算节点S 到本节点的链路质量“2”并添加到链路质量域中对应的位置，查看本节点当前队列缓存中待发的数据报文个数“3”并写入缓存数量域中对应的位置，将RREQ报文的生存时间值减1 并广播转发该分组。因此，节点B 转发的RREQ 报文内容如表2 所示，节点A转发的RREQ 报文内容如表3 所示。

表1 节点S 发送的RREQ 报文内容

表2 节点B 转发的RREQ 报文内容

表3 节点A转发的RREQ 报文内容

1.1.3 节点C 收到节点A 转发的RREQ 报文，节点C、D、F 收到节点B 转发的RREQ 报文

节点C、F 收到RREQ 报文后的处理与1.1.2 章节中所述的处理过程类似，这里不再说明。节点D收到节点B 转发的RREQ 报文后，读取分组中的目的地址信息，发现自身地址与RREQ 报文中目的地址域相匹配，然后计算节点B 到本节点的链路质量，创建RREP 报文回复至源节点S，并删除收到的RREQ 分组。节点D 回复的RREP 分组内容如表4 所示。

由于无法保证网络中所有节点间的无线链路都是双向链路，因此节点D 也将以洪泛转发的方式回复RREP 分组至源节点S。中继节点对收到RREP分组后的处理与RREQ 分组的处理过程相类似。

1.1.4 节点S 收到节点D 回复的RREP 报文

源节点S 收到RREP 报文后，读取分组中的路由记录，根据分组中的路由信息更新路由表。源节点S 维护的路由表如表5 所示。

AC-DSR 路由发现过程如图2 所示。通过上述流程，源节点S 可以获得多条通往目的节点D 的路由，并且能获得各条路由当前时刻的跳数、链路质量、中继节点缓存队列中待发送报文数量等信息。下面介绍源节点根据上述路由表和路由选择策略计算最优路由的过程。

表4 节点D 回复的RREQ 报文内容

表5 源节点S 维护的路由表

1.2 路由选择

源节点收到目的节点回复的RREP 报文或者数据报文的ACK 后，将根据蚁群算法更新每一条路由的信息素和选择概率，然后按照最大选择概率准则选择发送数据报文的路由。路由选择过程包括选择概率计算和信息素更新两个子过程。

1.2.1 选择概率计算

与传统路由协议仅考虑跳数、期望延时等影响因素不同，本文设计的基于蚁群算法的路由选择策略综合考虑了跳数、链路质量和节点负载等因素，并参考了历史路由选择结果，可以获得更优性能。

路由跳数、链路质量和节点负载等信息可以由RREP 报文和数据报文的ACK 携带至源节点处并动态更新，上述信息决定了每条链路上的信息素。在本文设计的基于蚁群算法的路由选择策略中，路由r上某段链路(i,j)上的信息素用τij(t)表示，是链路(i,j)的链路质量Lij(t)与中继节点i缓存队列中等待发送报文数量Ci(t)的比值，即：

路由r上的信息素，即路由r上所有链路的信息素之和，可以表示为：

路由r上的启发函数值ηr(t)可以表示为：

式中，dr表示源节点到目的节点经过路由r的跳数。显然，该启发函数表示蚂蚁经过路由r从源节点到目的节点的期望程度。值反映了寻优过程中确定性因素的作用强度。值越大，表示源节点选择最少跳数路由的可能性越大。

源节点在选择路由时，同时受到路由上的信息素和启发函数的影响。用R表示所有路由的集合，源节点路由r(r∈R)的选择概率表示为：

式中：α为信息素因子，表示路径上的信息素对路由寻优影响的程度；β为启发因子，表示启发函数对路由寻优影响的程度。作为路由信息素的幂数，α值越大，表示路由寻优时路由报文交互和ACK 报文携带的信息素的影响越大，即路由寻优主要受之前报文交互时获得的链路质量、缓存数据报文数的经验因素影响。作为启发函数的幂数，β值越大，表示路由寻优时路由跳数的影响越大，即路由寻优主要受路由跳数这个确定性因素的影响。根据图1 的各路由状态信息计算得到的各路由的选择概率如表5 所示，其中α和β均为0.3。

在AC-DSR 协议中，源节点采用最大选择概率准则选择发送数据报文的路由，因此最优路由可以表示为：

在后续的数据报文发送中，源节点S 会使用选择概率最高的S-B-D 路由。根据图1 中的拓扑结构可以看出，该路径所经过的链路质量较好，同时各中继节点队列缓存数据量少，使用该链路传输可以获得更优的性能。

1.2.2 信息素更新

源节点收到目的节点回复的RREP 报文后，先根据其携带的链路质量、中继节点缓存数据报文个数等信息，计算各路由的初始信息素值和启发函数值，进而计算各路由的选择概率，而源节点将使用选择概率最大的路由发送数据报文。源节点发送数据报文，当收到目的节点回复的数据报文ACK 消息后，获取ACK 消息携带的链路质量、中间节点缓存个数等信息，对发送该数据报文路由的信息素值进行更新，并重新计算其路由选择概率，以便源节点再次选择发送数据报文的路由。

数据报文的ACK 内容如表6 所示。

表6 数据报文的ACK 内容

根据接收到的ACK中的链路质量和缓存数量，源节点计算所选择的路由各链路的信息素τij(t)，然后计算整个路由的信息素增量Δτr(t)为：

最终该路由的信息素可以更新为：

式中，ρ为信息素挥发因子，ρ∈[0,1]，1-ρ表示信息素残留因子。

1.3 路由维护

路由发现过程完成后，数据报文会沿着其携带的源路由所指定的路径，依次被中间节点转发至目的节点。但是，由于网络拓扑和链路质量不断动态变化等因素，可能会使源路由中某些相邻节点不在彼此的通信范围内，导致当前正在使用的源路由因为中间一些链路的中断而不能成功转发数据报文到目的节点，因此需要路由维护过程来修复路由。

在AC-DSR 协议中，中继节点收到数据报文后，根据数据报文中包含的路由信息向下一跳发送数据报文。如果节点在设定的重发次数内收到下一跳节点回复的确认消息，则可以确定两节点间的链路状态正常；否则，认为链路中断，开始路由维护过程。

如图3 所示，当节点B、D 之间的链路中断后，路由维护过程如下。节点B 确认链路中断后，开始路由维护过程，需要创建并向源节点S 发送路由错误报文RERR。根据RERR 报文指定的路径，沿途转发该报文的节点。如果它的路由列表中存有包含中断链路的路由信息，必须被全部删除。然后，节点检查其自身的路由缓存，若存在另一条有效路由到达数据报文的目的节点，则利用这条路由来替代原有的路由将数据报文转发至目的节点。

源节点S 收到RERR 报文后，会根据报文中携带的中断链路信息删除其路由缓存中相应的失效路由。若源节点与目的节点之间仍存在通信业务，且源节点更新后的路由列表中有其他到目的节点的路由，则直接使用这条路由发送数据报文，否则将重新发起路由发现过程。

图3 AC-DSR 路由维护过程

2 性能仿真与分析

本文提出的AC-DSR 协议的仿真实验在Opnet环境下进行，在2 km×2 km 的区域内随机分布5个通信节点搭建移动自组织网络，并与经典的DSR协议和基于蚁群优化的AODV 路由协议ARMAN 就端到端延时和路由开销性能进行对比分析。仿真场景如图4 所示，表7 为仿真实验参数设置情况。

图4 仿真使用的网络场景

表7 仿真实验环境与参数设置

图5 显示的是数据报文端到端延时性能随时间变化的曲线。可以看出，与传统DSR 协议相比，基于蚁群优化的ARMAN 和本文提出的AC-DSR 协议都可以获得更低的端到端延时性能。究其原因，以图4 时刻的网络拓扑为例进行说明。当使用传统的DSR 协议时，源节点总是使用路径最短的路由，因此源节点0 向节点4 发送数据报文时总会选择路由“0-2-3-4”，造成节点2 处负载较重。发送队列缓存较长，源节点0 发出的数据报文在节点2 的缓存队列中等待较长时间才可以发往下一跳节点3，最终导致较长的端到端延时。但是，基于蚁群优化的ARMAN 和AC-DSR 协议可以根据队列缓存和链路质量实时计算各路径的信息素并更新选择概率，当节点2 队列缓存较长时，选择队列缓存更优的节点1 作为中继节点，从而降低了端到端延时。

图5 端到端延时性能随时间变化曲线

图6 显示的是路由协议的额外开销随时间变化的曲线。可以看出，DSR 和AC-DSR 协议路由报文的开销远低于ARMAN 协议。这主要是由于ARMAN 属于逐跳路由协议，每一个节点都要周期性发送路由报文以维护与邻节点的路由，而DSR 和AC-DSR 都属于源路由协议，由源节点维护路由信息且仅在有数据报文发送时才发送路由报文以获得到目的节点的路由信息，减少了发送的路由报文的数量，因此拥有更少的路由额外开销。

图6 路由协议额外开销随时间变化曲线

3 结语

隐蔽通信网络需要在保证低延时、高可靠的前提下尽量减少报文的发送次数，这对路由协议提出了新的挑战。本文设计的AC-DSR 将蚁群优化思想融入DSR 协议设计，可根据路由跳数、链路质量、缓存等状态实时更新路由的选择概率，能够达到减少数据报文端到端延时和降低路由协议额外开销的目标，为隐蔽通信网络路由协议设计提供了新的思路。