基于蚁群算法的AODV路由协议研究

李杰

（三江学院计算机科学与工程学院，南京210012）

0 引言

AODV（Ad hoc On-Demand Distance Vector Rout⁃ing）协议通过洪泛的方法，使得设备能够让很多的路由达到目的地，而且不需要设备在没有相互通讯时，协议可以自行维护这些路由。当这些路由因故断开时，可以快速做出响应，为完善拓扑结果做出及时应对。而且这个协议的频宽使用量有限，对资源占有较小。但是因为这种及时响应的措施也会出现附带的问题，虽然这种路由协议响应快，但是为了找到可达路由，会使整个网络的时延和路由开销在这个阶段大大增加。在这些问题上一直有大量研究人员进行研究。

从古到今，人类一直通过模仿自然界动物的行为特征来，认识自然科学并使用各种原理来发展人类自身科技。在算法领域中有一种新的仿生优化算法进入人们的视野——蚁群算法[1]。1991年，Marco Dorigo等人提出一种仿生算法，比利时、意大利、德国这三个国家是蚁群算法的主要研究国家，国内有上海、北京等几个研究所和大学对蚁群算法展开过研究。在改良AODV路由协议上可以鉴戒蚁群算法。蚁群算法采取正反馈机制的分布式启发式算法，具有适用于移动场景、自发建立、自动布置等特性，也被成为增强式学习系统，与AODV路由协议相适应[1]。

1 全面深入AODV

（1）AODV协议综述

AODV协议的目标是能够在未知环境中也能建立的，并且自身能够随拓扑的变化而自适应的网络。该协议以路径长度为取舍路由的标准，每个节点仅需对自己通往的最短路径节点进行维护，这个路径上的节点不只是线性的而是一个范围内所有的节点。取最短路径节点的方法，使得该协议对于网络拓扑变化时有着灵活的自适应性。该协议的相关操作使得变化时的收敛性很好，拓扑发生改变时，发生变化的节点会给就近节点发送通知信息包。附近节点就会更新自身路由表，剔除无效路由[4]。

AODV协议使用seq号来维护和更新路由信息表。目的节点创建seq号，在它给附近节点发送路由信息包时，把这个seq号作为路由中一部分发送出去，发送给所有给目的节点发送请求的节点。这个seq号是嵌入在路由信息表中不需要另外操作。该协议对路由更新也使用这个seq号，更新路由信息表时，检查收到的路由信息包，比较路由表中的当前seq号是否是最大值。当成为最大值之后进行更新。

无论是在未知环境中的网络构建，还是因拓扑发生变化而需要更新路由信息表，其本质都是需要改动路由表中的路由表项。那么就需要去了解路由表项的具体内容以及作用。AODV路由表项如表1所示。

表1 AODV路由表项

（2）AODV操作

在使用AODV协议通信时，节点会生成路由请求、路由应答和路由错误三种报文信息。为了恰当地对三种信息进行发送、接收，在路由表项中设定状态信息。

①seq号管理

为了恰当地对各种报文进行发送和接收，在路由信息表中维护一个seq号。这个seq号就是上述的目标seq号，即节点路由信息表中维护的最新的目的节点IP和其他信息。定义了这个seq号，当一个节点收到一系列新的报文，首先判断该报文是否跟请求消息、接收消息和错误消息的seq号有关，反之就会抛弃该报文消息。然后再检查这些消息中的seq号是否是最新的，如果是就更新路由表项中的seq号，否则也舍弃掉该报文。增加目标节点自身的seq号也有特定的场景下的。一个节点在向其他节点发起请求之前需要对自身的seq号进行加法操作，这相当是对当前版本号的操作，给当前操作规定一个版本号，如果响应者发回路由，那么就会核对版本号，版本号对不上就不会进行更新操作。所以AODV协议中有要求，为每一个节点新建和更新目标seq号。并且目标节点在对其他节点发来的请求报文进行答复时，目标节点也必须先更新自身的seq号，而且更新的seq号要保证是最新的版本号[4]。

②路由表项和先驱列表

当节点从邻居接收到AODV控制消息并创建和更新特定目标节点和目标子网的路由表条目时，它将检查该节点是否在表中，该条目对应于此目的地。如果没有关联的条目，将创建一个新条目。可以从AODV控制消息中提取seq号，也可以在路由表条目中的“seq号有效”位置标记为“无效”。

在维护和更新路由表时，可以使用控制消息。其中的有用路由超时字段，是用来更新路由表中有用时间字段的参考字段，更新规则是：路由转发时，请求路由、响应路由的节点的有用时间需要参考控制消息中的有用路由超时时间，新的值下限是当前时间与有用路由超时时间之和。因为发起请求节点和回复请求节点是相互对应的，那么请求节点向目标节点发送请求报文中的目的地址，就是目的节点也就是回复节点中的源地址是相同的，那么这样对应的两条路由就是对应存在的，请求节点中的这条路由如果删除了，意味着该条路由已失效，那么目标节点路由表中对应路由也应该删除，所以这两条路由的有效时间是相同的。对其中一条路由进行更新时另外一条路由也需要更新。

对于每条有效路由，每个节点会维护一张先驱表，所谓先驱表就是存放那些发送请求报文到本节点的节点。这些先驱节点可能会使用本地路由转发数据。先驱表的作用就是防止节点断开导致的重建路由的开销问题。本节点检测到下一跳节点与自身节点失效，本节点就会通知这些先驱节点，下一跳路由已失效[5]。

③处理和转发路由请求

节点接收到周围节点发送的请求消息后，首先检查在路径发现周期内是否已存在源IP和请求ID与该请求信息匹配的消息，存在该消息就会丢弃，否则就会检查本地路由表中是否存在通往该节点的可达路径，不存在则新建通往发送节点的路由表项，如果存在则只是将本地seq号进行加一操作。

请求消息的处理不仅仅是对路由信息表中的seq号进行更新或是简单转发，还需要更新跳数、源seq号，创建反向路由，匹配源IP地址。而且在创建了反向路由后，仍然需要比较seq号之后再更新路由表项，更新seq号合法标识，更新反向路由表中的跳数和路由生命周期。详细而言，若是节点领受到四围节点发送的请求消息，当请求消息在该节点以前没有存在过，就先将领受到的请求消息中的跳数加一，标识请求消息抵达了该节点。更新完跳数之后，需要去创建一条反向路由。反向路由的目的节点就是接收的请求消息中源IP，这条路由中的seq号使用请求消息中的源seq号加一。那么使用这条反向路由发送的消息相当于是对发送请求消息所在节点的回复消息[5]。创建和更新反向路由时，需要更新路由表项、更新seq号合法标识等。

④路由错误处理

当路由发生错误或者节点之间的连接发生中断时，需要以下步骤进行处理：

第一步，首先需要把本地路由进行无效化处理，具体是将本地路由信息表中的有效超时字段进行更新，还有每一个节点维护的先驱表也进行更新，通过先驱表向周围节点通知下一跳路由已失效。第二步，通过路由表枚举出没有通过错误路由的路径。第三步，检查出错误路由影响哪些邻居节点抵达目的节点。第四步，本节点向周围的邻居节点发出错误消息，提示通过这个节点抵达目标节点的路径已断开。

以下三种情况，节点会对错误消息进行初始化处理：

第一种，当节点向目标节点发送请求，就是向目标节点发送数据包时，节点在生存周期内检查出原本存活的路由发生了连接断开问题，并且修复路由没有结果，那么就会将错误信息初始化。第二种，当节点接收到附近节点发送的数据包时，检查数据包中的路由信息表，发现目的IP不可达，即本节点的路由表没有通往该目的IP的路径。那么节点对错误信息初始化。第三种，当节点没有接收到正常数据包，而是接收附近节点发送的错误消息，并且发送错误消息的在邻居节点集中不止一个，那么节点会对错误消息初始化。

（3）AODV相关应用

在某些网络配置中，无线自组网网络能够在不利用AODV的外部路由区域间提供连接。对于在外部路由区域中的任何相关网络，如果与其他网络连接的点能够像子网路由器一样工作，那么无线自组网网络就能够在外部路由区域间保持连接。实际上，外部路由网络可以将AODV所定义的无线自组网网络像传送网络（transit network）来使用。

为了使无线自组网网络向传送网络来使用，外部网络的连接点相当于是起到了每个子网中的一个路由器的作用。这个路由器需要使外部网络的子网提供访问权限。需要为外部子网创建并更新目的地址序列数[4]。

2 蚁群算法原理

（1）蚁群算法简介

只要观察过蚂蚁在觅食的行为，总能看到蚁群不断的尝试不同的路径，虽然一开始的路径会天差地别，但是最后总是能够找到一条最优路径，有时候不一是最短但一定是最优的路径。假设有一群蚂蚁，它们在寻找食物的时候遇到一个障碍物，所以出现左右两条路径，但是因为之前没有蚂蚁走过，也就没有信息素来指引蚂蚁，蚂蚁走左右路径是等概率的。每当有蚂蚁走过就会留下会以一定速度散发的信息素。后面的蚂蚁是以信息素强烈程度判断走哪条路径，因此，信息素大多分布在短的那条路径上，蚂蚁会趋向于走信息素多的路[10]。

（2）蚁群算法计算过程

首先需要对这个问题进行建模，假设出需要的参数变量。蚂蚁经过的路径，也就是标识每个蚂蚁访问过的地点，这里设置一个boolean型的visited访问矩阵来表示蚂蚁访问过的地点，如果只为false就表示没有访问过，如果是true表示已访问。Int型的变量S_L表示最短的距离，B_T表示最优的距离，这些距离计算起来都比较方便，每次只需将两个地点的距离加入即可。蚂蚁会释放信息素那么信息素量化，就创建一个信息素矩阵M_P，横纵坐标表示地点。那么地点之间的信息素需要记录，单个蚂蚁走一次释放的信息素也应该被记录下来，这里假设蚂蚁之间没有区别的，这个矩阵用来计算信息素和比较法方便。该矩阵命名为Ant_P，横纵坐标也是地点。蚂蚁需要对路线进行选择，因为不是所有路线蚂蚁都可以通过，所以需要另一个矩阵存储蚂蚁可以通过的地点，命名为Permit矩阵。在蚂蚁运动过程还有一些参数需要进行控制这里就设为a，b，c，d四个参数，蚂蚁运动时间也需要记录设为T。算法步骤如下[11]：

①初始化矩阵和参数。

设置算法开始运行的时间T为0，最优路径设为Integer.MAXVLAUE，B_T设为空值。设置蚂蚁的信息素矩阵的所有初始值为0，visited矩阵初始化false，Permit矩阵可访问地点设置为1，不能访问的地点设置为0。设置蚂蚁的初始位置，可以随机也可固定一个起始位置。在visited矩阵中将起始节点设置为true，可以访问的Permit矩阵中设置该起始节点值为0。

②迭代选路过程。

以轮盘赌选择方式选择每只蚂蚁的下一条路径，选择一条路径，在visit中将该节点改为true，并且将Permit矩阵中对应节点状态设为0。遍历全部节点后，将节点插入建立的res路径结果集。然后按照状态转移概率计算蚂蚁k在地点i和j之间选择某个地点，作为其信息素矩阵M_P的信息素值。然后比较出最好路径，经由对比每个蚂蚁的路径时间，然后将较小值赋值给B_L。状态转移概率公式如下[11]：

状态转移概率公式中p表示，第k个蚂蚁选择地点i到j的当中一个地点的概率，τi,j(t)表示节点i，j在t时刻的信息素，这个信息素的大小是从信息素矩阵M_P中按照第i行，第j列的取值大小，φi,j(t)表示节点i到节点j的距离的倒数，距离是按照地点i和地点j的距离计算的，然后取该距离的倒数代入公式中。公式中的α，β参数为信息启发式因子和期望启发式因子，这两个参数是信息素和路径上的指数，所以状态转移概率受到信息素大小和路径长度的影响是可以通过调整这两个参数大小来控制的。但是就算调整了这两个参数，概率还是主要受信息素和路径的影响。所以该公式的现实意义就是蚂蚁会选择离自己距离近的，信息素浓度大的路径。

③更新信息素矩阵M_P

更新信息素是根据上一只蚂蚁更新后的信息素，当然第一只是直接进行更新的。更新信息素是可以对距离进行设置，即走完n个地点进行更新，这里的n可以为1，2，…，n。按如下公式更新信息素矩阵M_P。

3 基于蚁群算法的AODV路由协议

（1）算法设计

Ad hoc网络拓扑抽象为图Graph，通信节点由顶点表示，链路由图的边表示，其中N为图Graph中所有节点集合，并且维护一张LinkedTable表，意为链路的集合，假设任意2个节点i，j存在链路，则表明节点i，j之间存在连接。

本文研究的是将Ad hoc网络中路由协议和蚁群算法结合起来，首先将蚂蚁分为前驱蚂蚁和后继蚂蚁，前驱蚂蚁对应AODV协议中的请求报文消息。后继蚂蚁对应回应消息报文。对上述两种报文消息进行修改，通过添加报文发送的时间和上一跳的阻塞程度，来更新前驱蚂蚁报文和后继蚂蚁报文，然后通过报文计算路由时延和拥塞状态。为了达到最佳路径，网络中的每一个节点保存信息素，建立一个概率路由表代替原来的AODV表，如图1所示。

图1 概率路由表表项和AODV路由表表项对应关系

图1 左边是概率路由表表项，右边AODV路由表表项。

概率路由表中的Dst Hops对应AODV路由表中Hop Count表项，存放去往同一个目的节点的多条不同的跳数，用Route list替换AODV路由表中的Next Hop以保证蚁群算法的运行。

计算这个状态转移概率使用改进的算法公式：

该公式计算结果为路由选择的概率，表示在t时刻在网络中传输的数据包k从当前节点i选择邻接节点j作为下一个节点的概率。μi,j(t)是链路质量函数，表示当前节点j的堵塞程度，当且仅当该值为0时，表示节点j阻塞，为1时j通畅。这里维护的概率路由表相当于是信息素的浓度表。蚂蚁根据信息素的浓度强烈程度选择要走的路径，而本文的则是数据包根据概率表大小也就是信息素浓烈程度，选择最佳的路径。与蚂蚁在前进过程中释放信息素和修改跳数、阻塞程度相一致，网络中的数据包在从一个节点抵达另一个节点也会对节点的概率路由、下一跳、阻塞程度进行更新，也就是在运动过程中不断维护每个节点的AODV路由表。由不断地路由组建和路由维护最终形成路由。

（2）算法实现

①路径探索

Source节点即源节点要和Destination即目标节点进行通信时，源节点在本地路由信息表中检查通往目标节点的路由信息，这个过程和上述反向路由建立过程相似，都需要现在本地查找，然后再作其它处理。在本地路由中找到通往目标节点的路由，并且在路由生命周期中没有消亡。那么就尝试发送请求消息给目标节点。如果能够抵达目标节点就更新该条路由，如果不能够抵达那么就从路由表中删除这条无效路由。

②路由组建

算法实现需要组建路由，发现路由采用广泛使用的广播方式，虽然可能会导致一些不必要的浪费，或许可能还会发生阻塞，但是这种方式最简单能将所有可能情况覆盖，所以还是选择了广播方式。

节点需要去搜寻目标节点时，节点向周围节点发送的请求消息后，首先检查在路径发现周期内是否已存在源IP和请求ID与该请求信息匹配的消息，存在该消息就会丢弃，否则就会检查本地路由表中是否存在通往该节点的可达路径，如果存在则向源节点回复消息建立路由，更新路径上节点的概率路由表。

如果没有检查到存在任何的路由信息，就比较请求消息报文中的seq号和目的节点的seq号，请求消息中的源seq号和目的节点的seq号需要保持一致。因为反向路由就是对发送节点的回复。但是也有可能不相等，如果发送请求消息的seq号大于目标节点的seq号，则更新为发送请求消息的seq号，并且继续向下一跳节点广播，否则就丢弃该请求消息，因为该请求消息已经过期了。每次建立路由时，还需检查周围报文中是否存在更小的跳数，如果存在就已该跳数建立一条反向路由用来跟本节点通信。当节点收到数据包时，更新概率路由表，计算邻居节点的转发概率，选择概率大的路径转发，借此来避免广播带来的网络中发生严重阻塞情况。

③路由维护

建立路由后需要维护路由表的表项。开始时广播数据包，广播到的节点动态更新概率路由表，路由的维护以发送Hello信息包的形式检测连接是否正常。假设存在节点i和节点j，需要维护这两个节点之间的通信。节点i收到邻居节点j的Hello消息后，节点i会根据返回的Hello消息更新路由表中的路径、时延和到下一跳j的路径。当节点i在一定时间内，没有收到来自邻居节点发送的Hello消息时，就认为该链路中断了。当链路中断时，不能立即重启网络，保证网络不会因为频繁重启而消耗大量资源。需要对中断链路进行替换。首先将该链路在概率表中对应的表项删除，然后查找概率路由表是否有其他的目的节点路径。当没有其他链路可选时，才需要从源节点开始重新构建整个网络。在通信过程中，数据传输过程可能出现路由黑洞问题。但对于该协议，循环问题在路径探索时就已解决，在发送请求消息阶段，蚂蚁走过的每一个节点会将自己的ID加入到蚂蚁的信息中，蚂蚁只会探索没访问过的节点。所以算法本身有效避免了死循环问题[12]。

④蚁群算法流程图

（3）仿真结果

图2 改进后的蚁群算法流程图

①不同暂停时间下的端对端传输延时性能

图3 平均端对端传输时延与暂停时间曲线图

由图3可知，在不同的暂停时间下，改进后的AODV路由协议的传输时延比原来的AODV协议小，这是由于改进后的蚁群算法可以提供比较稳定的连接，可以通过最优路径寻找下一个结点。因此，通过蚁群算法改进后的AODV协议可以改善因网络丢包严重导致的时延，具有更好的性能。

②不同结点移动速度下的端对端传输延时性能

图4 平均端对端传输时延与节点移动速度曲线图

由图4可知，在相同的节点移动速度下，改进后的AODV协议的传输延时比原来的AODV协议小，说明改进后的AODV协议比原来的AODV协议性能更好，更能适应拓扑不断变化的网络。

4 结语

MANET的路由协议可分为主动式（表驱动）和被动式（按需），具体取决于它们对拓扑变化的反应方式[6]。因为实际应用中，即使移动终端上没有这种主动协议也可能会花费网络资源来构建路由，浪费了有限的无线带宽，所以许多研究人员提出使用反应式协议，也就是使用按需方法构建路由协议。具体而言，基于这种按需方法提出的一种反应性协议是临时按需距离矢量路由（AODV）。

无线移动节点可以动态地进入网络以及离开网络，常规网络中的路由器通常不会四处走动，并且很少离开或加入网络，这种情况导致总体上无法收敛到稳定的路由。因此，在部署MANET时要考虑许多问题。由于节点的移动性，自组织网络中的拓扑可能会不断变化。MANET的路由协议必须处理这些问题才能有效。

因此，本文尝试应用已证明其在有线网络路由协议中有效的蚁群优化技术来优化现有的AODV路由协议。在仿真实验中，将蚁群算法应用于AODV路由协议尝试克服已解决的问题，并提高其运行性能。