基于蚁群算法的能量均衡多路径路由算法的研究*

童孟军，关华丞

(杭州电子科技大学计算机学院，杭州310018)

无线传感网 WSN(Wireless Sensor Networks)[1－3]是新一代的传感器网络，由于其集成了传感器和无线网络技术，因而具有非常广泛的应用前景，对人类的生活和生产也将产生深远的影响。无线传感网通常具有能量有限的节点，节点数目庞大且无法及时补充，所以节约并均衡节点的能量消耗，最大限度的延长网络生存时间，是无线传感网的主要设计目标之一[4]。对于类似AOMDV[5]这类的多路径路由协议，一直选择相同的路径进行数据的转发，将导致路径中部分节点的能量过早耗尽，而节点的失效又造成网络分割，严重影响网络的生存时间。如何能根据网络当前的实际情况，进行数据包的转发，从而做到整个网络更好的负载均衡。基于蚁群算法[6－9]ACO(Ant Colony Optimization)的路由协议，通过蚂蚁包的发送，每个节点可以获悉网络当前实际情况，根据信息素概率公式选择下一跳，非常适合设计这种能量负载均衡的多路径路由协议。基于蚁群算法的无线传感网路由协议是目前国内外研究的热点之一。本文以蚁群算法为切入点，在分析各类蚁群多路径路由协议的基础上，提出一种基于蚁群算法的能量均衡多路径路由协议ABMR(Ant-Based Multipath Routing)，并通过仿真及实验对此协议的性能进行了分析。

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

蚁群算法来源于蚂蚁觅食的优化方式。蚁群系统ACS(Ant Colony System)是分布式的生物系统，蚂蚁们之间协作帮助能完成单个个体所难以完成的艰巨任务，体现了生物的群体智能性。蚂蚁从居住的地方去出发寻找食物的时候，会在经过的路径上释放一种叫信息素的化学物质。蚂蚁们相互之间能感知到这种叫信息素的化学物质，后面的蚂蚁会沿着信息素浓度高的路径前进。信息素这种化学物质会随着时间的变化而挥发，结果是距离短的路径上的信息素浓度也变得越来越多，另外的路径信息素就会越来越少。最终，蚂蚁们通过相互合作会找到最优路径。无线传感网中的路由也一样，需要发送数据的节点通过释放类似蚂蚁的路由搜索包到目的节点，类似蚂蚁的路由搜索包从目的节点返回，最终形成一条源节点到目的节点的路由。

文献[10]提出了适用于有线网络的AntNet协议，第一次在网络路由表的建立过程中使用了蚁群算法，也是迄今为止最成功的基于蚁群算法的路由协议之一。在AntNet协议中，使用了前向蚂蚁和后向蚂蚁的概念，前向蚂蚁根据路由表中的启发式信息值来概率选择下一跳，并且把经过的节点放到前向蚂蚁头部中。前向蚂蚁到达目的节点后，完成使命，对应转换成一个后向蚂蚁，后向蚂蚁按照前向蚂蚁经过的路径返回，在经过的每个链路上释放信息素。

文献[11]中提出的ARA算法是最早的将蚁群算法应用于无线移动自组织网络的按需多路径算法。路由的建立是依靠前向蚂蚁和后向蚂蚁来实现。ARA开销比较小，只需用发送蚂蚁包的ID(序列号)，目的地址和源地址，另外路径维护的时候，也不用发送蚂蚁包，只需用在发送数据包的时候进行信息素更新就可以了，信息素在目的节点的链路上和到源节点的链路上都进行信息素的更新，另外进行定时的信息素挥发。

文献[12]提出了ARAMA协议。ARAMA定义梯度(grade)的概念，这个值由后向蚂蚁返回的途中进行计算并保存在节点中。梯度的计算公式依赖前向蚂蚁收集的能量等链路信息。当中间节点收到一个后向蚂蚁的时候，要根据蚂蚁包中的路径梯度值进行信息素更新，后向蚂蚁包经过的链路信息素增加，另外链路信息素挥发。挥发的目的是为了节点更快的忘记老的路径。数据发送的时候，是沿着最佳路径发送，这样就不用在路径上进行切换。当最佳路径被破坏时，马上可以用另外的路径来进行数据的发送。

与ARA和ARAMA不同，文献[13]中提到的IEEABR是一个主动式的路由协议，网络初始化时，每个节点随机的向Sink节点发送一个前向蚂蚁。后向蚂蚁返回时，中间节点根据后向蚂蚁中携带的信息素参数以及距离Sink节点的跳数对后向蚂蚁经过的链路进行信息素更新，后向蚂蚁到达源节点后就死亡。数据包根据概率选择公式，选择较好的路径进行转发。值得注意的是，IEEABR采用累加的方式进行信息素更新，这样的策略容易陷入局部最优，使个别路径上的节点过早的死亡，从而对整体的网络寿命和通信能力产生不利影响。

在文献[14]中Di Caro等人提出了AntHocNet协议，AntHocNet协议是一种基于蚁群算法的多路径混合式路由协议。该协议的路由发现按需进行，而路径维护则主动完成。这个路由协议有四个主要的过程:按需路径建立、随机数据发送、主动路径维护和探索和处理失效的链路。

AntHocNet的优点是路由发现时找到了多路径，这样可以减少路由发现的频率，主要缺点查找到的多路径是相交多路径，因此一个节点的断开可能引起多条路径的失效，路由维护过程需要有大量的蚂蚁，另外，每个节点保存着一张它所有可达目的节点的路由表，对于规模大的网络AntHocNet并不太适合。

文献[15]提出了DAR(Distributed Ant Routing)协议，DAR是一种按需的蚁群路由协议，和主动式路由相比较，可以减少开销，减少节点的能量消耗。在DAR协议中，前向蚂蚁只关心交叉节点的情况，选择下一跳时，只使用信息素值。后向蚂蚁从目的节点返回时候，在返回的链路上只释放常量值的信息素。节点根据信息素概率选择下一跳发送数据。DAR协议的蚂蚁保存所有经过节点的ID，适用于不大的网络，同时网络收敛较慢，有时候也容易导致局部最优。

文献[16]提出了HOPNET协议，它是一种混合式路由协议，协议把网络分成多个区域，在区域内部采用主动的路由方式，在区域之间，采用蚁群的按需路由协议。由于区域不是很大，所以区域内部的主动式路由协议，开销也不会很大。通过这种方式，HOPNET在网络规模比较大的时候，能表现出比较好的优势。

在文献[17]中，S．Misra等人在 AntHocNet基础上提出了EAAR协议。该协议在信息素更新公式上考虑了到目的节点的最小跳数和能量。文献[18]研究表明，信息素更新公式如果只用跳数作为参数，是很不合理的。优先选用了到目的节点跳数少的路径，路径上跳数是少了，有可能节点之间距离长，信号强度小，连接松散，容易导致网络分割。另外节点之间距离增加，也会导致数据发送消耗的能量大幅度提高[19]。EAAR协议在进行多路径判断的时候，需要把符合条件的蚂蚁都保存在蚂蚁访问列表中，其中包括蚂蚁包访问过的所有节点ID，如果符合条件的蚂蚁包多的话，节点的内存开销和多路径的计算消耗也会比较大。

文献[20]提出了一种基于信息素扩散模型蚁群算法的路由协议DBACRA。该协议分为实际和虚拟两种信息素，一起来引导蚂蚁包和数据包进行目的性路径搜索。实际信息素是后向蚂蚁从目的节点返回的时候，释放在链路上的信息素。前向蚂蚁可以通过虚拟信息素和实际信息素的引导到达目的节点。但由于虚拟信息素是通过扩散的方法来进行传播的，在网络移动和网络比较大的时候，虚拟信息素也很容易陷入环路。

前面所说的一些多路径路由协议，很多都没有考虑到能量因素，如果按照传统的蚁群算法，找到最优路径，最后所有的流量几乎都会集中到一条路径上，而无线传感网的节点能量受限，这样就会导致这条路径上的节点很快死亡，因此这类协议不能很好的直接应用于无线传感网中。有些协议，虽然考虑到了各个路径上的剩余能量，但没有考虑到各个路径所消耗的能量的速度。有些协议，没有考虑到数据在传感网的网络拥塞情况。综合考虑以上这些因素，结合蚁群算法，本文提出了基于蚁群算法的能量均衡多路径路由协议ABMR，ABMR在信息素更新方式、信息素更新公式和蚁群多路径形成方面进行了改进和创新。

2 蚁群算法的能量均衡多路径路由协议

本文基于无线传感网节点的能量有限的特点，提出一种基于蚁群算法的多路径协议，记为ABMR协议。在该协议中，采用了一种新的多路径生成的机制，在信息素更新公式上综合考虑了路径的能量消耗速度、路径上剩余的最小能量、距离目的节点Sink的跳数和路径的拥塞程度，这样信息素更新公式更加合理。当源节点需要发送数据但没有到目的节点的路由信息时，通过广播发送前向蚂蚁到目的Sink节点，目的节点生成对应的后向蚂蚁，后向蚂蚁按照前向蚂蚁的路径返回到源节点，后向蚂蚁返回的时候在链路上释放信息素。传统的信息素的更新方式，在一个路径上释放的信息素会越来越多，造成这个路径上的数据越来越多，不能自动到达网络负载均衡。ABMR协议对信息素更新方式进行了改进，节点每次收到一个后向蚂蚁，都重新对链路上信息素值进行计算，而不是传统的信息素的累加更新方式，这样的话，数据包在网络上的分布会更均匀。每个节点根据后向蚂蚁释放的信息素采用概率路由选择的方法发送数据，概率路由选择策略使得数据均衡发布，最后导致自动的网络负载均衡，提高了整个网络的寿命。

2．1 路由发现

ABMR是一个混合多路径路由协议，路由建立的时候是反应式路由协议，也就是按需路由协议，路由建立后，是主动路由协议，定期发送前向蚂蚁。当源节点S需要向目的节点d发送数据时，需要查看路由信息，如果这个时候没有到达目的节点的路由，就需要开始广播发送前向蚂蚁，需要发送的数据进行缓存。如果有到达目的节点的路由，就可以直接进行数据发送。源节点广播前向蚂蚁，标记为(这里一个蚂蚁代表了一个控制报文)，。由于初始阶段是广播蚂蚁，s节点的每个邻居将收到的一个副本，记为．k(“．k”这个符号代表的是编号——单个广播包的第k个副本表示为)，经过下一跳之后，下一个邻居节点将收到(K，l是整数)，由于这些广播蚂蚁包是同一个源节点在同一个时刻产生的，我们称它们为同类蚂蚁，同类蚂蚁有相同的源节点地址和序列号。每个前向蚂蚁包的任务是找到一条连接s和d的路径。在源节点和目的节点之间的每个中间节点，单播或者广播前向蚂蚁，这取决于当前的节点是否有到目的节点d的路由信息，没有路由信息就广播发送前向蚂蚁，有路由信息的话，就按照信息素概率选择公式单播发送前向蚂蚁，式(1)是前向蚂蚁信息素概率选择公式:

当一个节点收到第一个前向蚂蚁，马上会把蚂蚁转发出去，同时第一个蚂蚁的一些信息被保存在蚂蚁访问列表中(蚂蚁访问列表的结构在3．4节中有详细介绍)。后面收到的前向蚂蚁，如果收到的是和前面不同类的蚂蚁，节点可以把这类前向蚂蚁转发出去。对于源节点的邻居节点，只接收从源节点直接发出的前向蚂蚁，也就是拒绝接收蚂蚁头部包含另外节点ID的那些前向蚂蚁。节点如果收到的是相同类型的前向蚂蚁，时延、跳数和能量可能比前面的蚂蚁包都要差，如果都被丢弃，中间节点到目的节点就只能形成单路径，不能发挥蚁群算法的优势。因此，为了减少网络中蚂蚁传播的开销，节点收到一个同类蚂蚁，先要进行环路的判断，即前向蚂蚁头部携带的节点有没有包含节点本身，如果形成环路，就直接丢弃这个蚂蚁，否则按照下面同类蚂蚁的多路径判断规则，形成源节点到目的节点的多路径，具体步骤如下:

第1步:先要判断新收到的同类蚂蚁和蚂蚁访问列表中已有的同类蚂蚁的第一跳是否一样，这个第一跳也就是离开源节点后的第一节点。如果第一个节点不一样，将新收到蚂蚁的时延dnew和跳数hnew与蚂蚁访问列表中同类蚂蚁的时延dsim和跳数hsim 相比较，只要 dnew＜λddsim且 hnew＜λhhsim，就接收新来的前向蚂蚁。本文规定λh为1．5，λd为2.5，可以根据不同的网络环境来进行调整。

第2步:如果新收到的前向蚂蚁的第一跳和蚂蚁访问列表中保存的其中任一个同类蚂蚁的第一跳一样，就要判断新收到的前向蚂蚁的入链路是否和蚂蚁访问列表中的同类蚂蚁一样。如果入链路不一样，也就是上一跳不一样，只要dnew＜λddsim且hnew＜λhhsim，就接收新来的前向蚂蚁。本文规定 λh为1.5，λd为2．5，可以根据不同的网络环境来进行调整。

第3步:如果新收到的前向蚂蚁的入链路与第一跳和节点中保存的同类蚂蚁一样，只有hnew＜hsim，才接收新来的蚂蚁。

通过这个方法，可以使得蚂蚁探索路径时获得多条路径，在数据发送的时候，如果一个链路出现故障，可以通过另外的链路发送出去。同时，多路径有助于网络的能量和负载均衡。

采用前面的蚂蚁包发送方法，到达目的节点d的前向蚂蚁有一定的数量，每个前向蚂蚁按次序保存了路径上所经过的所有节点ID。但无线传感网本身环境比较复杂，考虑到网络拥塞和时延问题，为了减少一些不必要的浪费，有些到达目的节点“太迟”的前向蚂蚁，目的节点作丢弃处理，不往回发送后向蚂蚁。在目的节点收到第一个到达的前向蚂蚁之后，会针对这类前向蚂蚁，设置一个等待时间，超过这个等待时间到达的这类前向蚂蚁，就被丢弃，不作任何处理。等待时间的计算公式见式(2)。后面介绍前向分组结构的时候会看到，前向蚂蚁分组里携带了从源节点s出发的那个时间，这样端到端的时延Ts－d就会很容易得到。Cd是个参数，可以根据网络环境进行适当调整。

在Td这段时间内，就像图1里显示的一样，目的节点收到了一个前向蚂蚁(Forward Ant)，就将前向蚂蚁转换成对应的一个后向蚂蚁(Backward Ant)，后向蚂蚁将沿着前向蚂蚁走过的路径返回到源节点s。如果由于下一跳节点发生了异常情况，例如由于节点的位置发生了改变，那么这个后向蚂蚁将被丢弃。当后向蚂蚁从一个编号为j的节点移动到编号为i的节点时，需要对节点i进行信息素更新，节点i更新或建立目的节点为d的路由信息，这个路由信息的下一跳就是j。式(3)为信息素更新公式:

图1 前向蚂蚁和后向蚂蚁经过的路径

在式(3)中，H是当前节点i到达目的节点d的跳数，这个值可以从后向蚂蚁的visitednode字段里得到。Ts－i是源节点到当前节点的时延，Eavg是从源节点s到目的节点已经消耗的平均能量，从后向蚂蚁包中得到。Min值是后向蚂蚁所经过的所有节点中，剩余能量最小的节点的能量值。在式(3)的信息素更新公式中，Eavg反应了整个链路的能量消耗情况，Eavg值大，说明这个链路上能量消耗多，也就是能力消耗速度快，可能这个链路上的节点承受了比较多的数据发送任务，所以在以后的路由选择过程中，这些路由上的节点应尽可能少承担数据转发任务。Min反应了一条链路的瓶颈情况，具有瓶颈的链路也应当尽可能少的承担数据发送任务。这样有助于延长节点和网络的寿命。有时候一个节点的提前死亡，会导致整个网络的分割，特别是在有些移动场景，当一个提前死亡的节点刚好移动到整个网络两个部分的连接处，这时候一个死亡的节点，就会导致网络的分割或一段时间的分割。H是当前节点i到达目的节点d的跳数，数据包尽可能沿着跳数少的路径到达目的节点，H值小，后向蚂蚁在链路上释放的信息素的值也大，数据包选择这个链路的概率也大。Ts－i是后向蚂蚁包到达当前节点的时间减去后向蚂蚁包携带的从源节点发出的时间，也就是前向蚂蚁包从源节点到目的节点的时间的时延加上后向蚂蚁包到当前节点的时延。一般来说，所需要传输延时小的路径要优于传输延时大的路径。传输延时大的路径，有可能网络在这个部分的传输任务比较重，负载比较大，有可能会进入拥塞状态，所以尽可能的往这些地方少发数据和蚂蚁包，根据式(3)在这些链路上释放的信息素也会相对的少些。k1，k2，k3和k4是以上4个参数的系数，在各个不同的网络环境，通过调节各个系数，来适应网络的环境。

2．2 数据发送

通过蚂蚁的发送，在各个节点建立了路由信息，一旦有后向蚂蚁返回，源节点中保存在缓冲区里的数据就可以通过蚂蚁建立起来的路由发送出去。数据发送是以概率发送的方法进行，所有的节点收到需要转发的数据包后，按照式(4)进行选择发送:

在式(4)中，β2是一个参数因子，可以调节链路信息素对数据转发的影响，β2值越大，信息素值越大的链路，被选中转发的数据的概率就越大，也就是“好的链路“使用频率会更高，可以根据具体的使用环境进行调整。本文中β2是一个大于等于1的值。发送数据多的链路，可能会比较拥挤，发送时间变长，能量消耗也会比较多，链路上节点的剩余能量减少，通过信息素的自动更新，数据会自动往剩余能量多和数据少的路径上发送，最后做到整个网络的负载均衡。

路由表中信息素的挥发是周期性进行的。τ为时间周期，信息素挥发公式如式(5)所示:

在式(5)中，ρ的范围是0到0．05之间。

2．3 路由维护和链路故障

节点在数据发送的时候，需要进行路由维护，一般发送N个数据报后发送一个前向蚂蚁或者定时发送前向蚂蚁。ABMR采用定时发送前向蚂蚁的方式，当节点开始发送数据后，定时产生一个前向蚂蚁。定时发送前向蚂蚁的时间间隔，可以根据节点的移动速度和网络情况来进行设定，本文暂时设为5 s。但是否发送这个前向蚂蚁，需要根据路由表中各个链路上的剩余的信息素大小和蚂蚁访问列表的长度来决定，如果各个链路上最大的剩余信息素已经小于某个门限值，且蚂蚁访问列表的长度小于一个上限值，就可以发送前向蚂蚁，这样也可以保证网络中的前向蚂蚁是异步发送。同样的，源节点收到一个后向蚂蚁，也可以根据上述的方法来决定是否发送前向蚂蚁。如果剩余信息素足够大或者蚂蚁访问列表大于上限值，可以重新定时发送。信息素的门限值可以设定为原始值的30%，当然这个值可以调整。蚂蚁访问列表的上限值，可以根据整个网络的节点规模数和节点内存大小来确定，本文后面的仿真实验设置为总节点数的20%。

为了避免相同路径上的节点重复发送前向蚂蚁，当一个节点收到一个前向蚂蚁时，需要把发送前向蚂蚁的定时器清零，重新进行计时。经过这样的处理，源节点到目的节点之间的正在进行数据发送的中间节点，如果有前向蚂蚁经过，把收到的前向蚂蚁发出去，把节点自己产生的前向蚂蚁延迟后再发送，就可以减少自己蚂蚁包的发送数量，减轻网络的开销。

路由维护时候，前向蚂蚁的发送有单播和广播两种方式，发送单个前向蚂蚁的时候，按照信息素概率选择公式，只是对原有的路径进行信息素的更新。广播发送蚂蚁的方式有10%的概率，发送广播包有两个方面的原因:一方面，发送单播包，只会对已有的路径进行信息素的更新，但不能搜寻新的路径(特别是在节点移动或有节点能量消耗掉的情况下)，这可能会导致原来的路由失效。另一方面发送广播包，既可以搜寻新的路径，又可以避免陷入局部最优。广播包发送到邻居的时候，邻居节点可能也没有路由信息，这时候邻居节点会继续发送广播包。但考虑到这样会很快在整个网络中进行洪泛，开销会很大，所以对这样的广播包进行了限制，本文把这些广播蚂蚁的TTL值设置为2(这个值可以根据环境变化)，就是说两跳后还没发现路由，就把蚂蚁包删除。采用跳数限制的机制，是因为考虑到新路径一般是在当前路径附近

无线传感网环境复杂，节点在数据发送过程中，有可能会失去和邻居的联系，造成链路故障。和很多协议类似，ABMR协议也采用了hello机制，邻居之间定时发送hello报文。通过hello报文相互发送，可以发现这个邻居还是否可达，就可以判断和这个邻居的链路是否出现了故障。当然节点本身有故障的话，也需要主动通知邻居，使得和它相邻的节点能及时发现链路故障。

当节点发现和一个邻居的链路出现故障，节点要把这个邻居的相关信息从邻居表和路由表中删除。在删除链路故障的邻居之前，节点首先要做个判断，将要被删除的邻居节点是否是自己到达目的节点的唯一下一跳，如果是唯一的下一跳，就需要给其他的邻居发送链路故障通告。或者这个邻居节点不是到目的节点的唯一下一跳，但通过查看信息素，这条路由是最佳路由，也需要给其他的邻居发送故障通告。在前向蚂蚁的发送过程中，本地节点需要保存自己的“上一跳”，也就是把前向蚂蚁发给自己的节点地址，这个时候发送链路故障通告，只需要发送给自己的“上一跳”就可以，不需要广播，这样可以减少开销。收到链路故障通告的节点，按照上面的方法，同样进行处理。

当节点由于数据包发送失败而知道链路故障，并且没有另外的路径用于发送数据包，节点开始本地修复路由，这个机制和AODV有点类似。但有区别的是，为了减少网络消耗，这儿的修复蚂蚁不是广播，而是根据邻居数量，连续发送几个路由修复蚂蚁，当然这些路由修复蚂蚁包有最大跳数限制(本文的跳数限制为3)。在发出第一个修复蚂蚁后，节点同时开始计时，如果在计时期结束没有收到后向修复蚂蚁，节点断定没有到目的节点的路径，节点会丢弃缓存需要发送的数据，同时按照上面讲的方法，向它的“上一跳”发送链路故障通告。

2．4 ABMR报文格式

在ABMR协议的报文结构中，前向蚂蚁需要保存该它已经访问过的所有节点ID，也就是把所有访问过的节点放在visitednode字段。在利用概率公式在邻居表中选择下一跳时，该字段做为禁忌表。也就是说只有存在于邻居表中，且不存在于visitednode中的节点，才有可能成为下一跳。虽然visitednode字段增加了前向蚂蚁包的长度，但是避免了产生环路和边缘节点丢包的情况，同时后向蚂蚁也是通过visitednode字段中的节点顺序返回源节点。

图2是前向蚂蚁报文格式。其中，Type是数据包类型，这里该字段值为前向蚂蚁的类型;Src_address是产生前向蚂蚁的源节点的地址;Seqno是源节点生成前向蚂蚁时候的序列号，每个新生成的前向蚂蚁的序列号都不一样，收到前向蚂蚁的节点就可以用＜Src_address，seqno＞这个标志来判断是否收到了同类的蚂蚁包。Esum是蚂蚁访问过的节点已经消耗的能量总和，每个节点收到一个前向蚂蚁后，需要把本节点已经消耗的能量加上去。Esum用于计算信息素。Src_timeh这个字段记录了从源节点出发的时间。TTL是蚂蚁生存时间段，表明蚂蚁在网络中的寿命。目的主要有两个，一方面可以限制蚂蚁的搜索范围，另一方面是防止蚂蚁无限制的在网络中兜圈子，因而白白浪费网络资源。每经过一个中间节点，就把TTL值减1。当TTL值为零时，就丢弃这个蚂蚁。visitednode字段保存该前向蚂访问过的所有节点ID。

图2 前向蚂蚁报文格式

前向蚂蚁到达目的节点后就自己消亡，符合条件的前向蚂蚁，就生成相应的后向蚂蚁。后向蚂蚁的报文格式如图3所示。其中，Type字段为后向蚂蚁包类型;Eavg是从源节点s到目的节点已经消耗的平均能量，由目的节点计算并赋值。Eavg通过前向蚂蚁中的Esum除以VisitedNode中的节点个数得到，Eavg用于信息素更新公式中。Emin是后向蚂蚁所经过路径上能量最小节点的能量值，Src_time是这个后向蚂蚁对应的前向蚂蚁从源节点发出的时间。visitednode是从前向蚂蚁传递过来的前向蚂蚁所走过的路径，后向蚂蚁沿着这个路径原路返回源节点，返回的过程中更新每条链路上的信息素。后向蚂蚁均按式(3)对链路上的信息素值进行更新。后向蚂蚁和前向蚂蚁有个区别，那就是后向蚂蚁没有了TTL字段，主要的原因是后向蚂蚁已经携带了路径信息visitednode，如果按照路径信息，后向蚂蚁的下一跳不可达，后向蚂蚁就自己作丢弃处理，所以也就不用TTL字段。到了源节点，后向蚂蚁完成任务，被丢弃。

图3 后向蚂蚁报文格式

到达中间节点的前向蚂蚁，如果符合条件可以转发出去寻路，都需要在蚂蚁访问列表中保存。蚂蚁访问列表是一个链式结构，图4其表项的结构。＜Src_address，seqno＞这个组合标志是用来判断是否是同类的蚂蚁包。F_hop是源节点到当前节点的第一跳，L_hop是当前节点的上一跳，也就是源节点到当前节点的最后一跳，这两个标志主要是用于同类蚂蚁的多路径判断规则。蚂蚁访问列表中的蚂蚁没有保存整个visitednode，这样可以节省传感器节点有限的资源。Hops是源节点到当前节点的跳数，Src_time和前向蚂蚁中的意思一样，记录了从源节点出发的时间。Hops和Src_time一起用于同类蚂蚁的多路径判断规则。TTL是蚂蚁生存时间，当节点收到后向蚂蚁的时候，把对应的前向蚂蚁从蚂蚁访问列表中删除，但如果对应的后向蚂蚁在返回的路径上丢失，就需要通过TTL字段定期删除蚂蚁访问列表中对应的蚂蚁，通过TTL字段可以定期把蚂蚁访问列表中无效的蚂蚁删除，避免无效的蚂蚁包长时间占用节点宝贵的资源。

图4 蚂蚁访问列表表项的结构

图5是邻居表结构图，保存着邻居节点的信息和到目的节点的路由信息素。Nei_addr是邻居节点的地址，Nei_energy是邻居节点当前的能量值。Hops是从目的节点到邻居节点的距离，以跳数为单位，当刚开始建立邻居表，没有收到后向蚂蚁的时候，Hops初始值为一个常量BIGGEST_HOPS，协议规定这个值为9999，表示这个邻居还不能作为下一跳进行数据转发，当节点收到一个后向蚂蚁的时候，更新Hops字段里的值。当节点收到后向蚂蚁的时候，就要根据式(3)计算信息素的值，在链路上释放信息素，这个信息素的值就赋给了图5里的Pheromone。Pheromone的初始值是零，前向蚂蚁到一个节点，如果发现所有的链路都没有信息素，就需要广播前向蚂蚁。每过一定的时间，Pheromone里的值就要进行挥发。最后，Last_update_time是节点最近更新这个邻居表项的时间。

图5 邻居表结构图

图6是HELLO包的结构图。其中Type表示数据包类型。Src_addr是发送HELLO包的邻居节点的地址，Node_energy是邻居节点当前的能量值。节点通过相互之间定期发送hello包，维护着节点之间的邻居表信息，HELLO的发送时间间隔可以根据节点不同场景来进行设置，对于节点移动快的场景，HELLO的发送间隔可以小一点。本文设定HELLO的发送间隔时间为2 s，如果超过6 s没有收到邻居的HELLO包，就需要把这个邻居节点从邻居表中删除。

图6 HELLO包结构图

2．5 算法描述

ABMR协议的具体算法步骤如下:

第1步:在协议运行初始阶段，先进行hello包的广播，建立起节点与其邻居之间的相互关系，初始时每个具有邻居关系的链路上的信息素设置为空;

第2步:需要发送数据的源节点，首先查看节点的路由信息表中有没有到目的节点的路由信息，如果没有路由信息，则广播前向蚂蚁，同时把发送的前向蚂蚁保存到蚂蚁访问列表中。有路由信息，就可以直接按路由信息选择下一跳进行发送;

第3步:如果中间节点是源节点的邻居节点，只接收从源节点直接发出的前向蚂蚁。中间节点收到一个前向蚂蚁，如果TTL值的是1，就直接丢弃前向蚂蚁。如果节点收到的是一个不同类蚂蚁，先把蚂蚁保存在蚂蚁访问列表，然后看看有没有到目的节点的路由信息，如果有到目的节点的路由信息，按照式(1)概率选择下一跳转发出去，如果没有路由信息，就广播转发前向蚂蚁。如果节点收到的是同类蚂蚁，先要判断是否形成环路，形成环路的蚂蚁要被丢弃，对于没有形成环路的前向蚂蚁，就要按照3．1路由发现里的多路径判断规则进行处理，符合条件的前向蚂蚁保存到蚂蚁访问列表，按照前面的方法转发出去，不符合条件的前向蚂蚁，直接被丢弃。

第4步:目的节点如果收到第一个前向蚂蚁，前向蚂蚁就被删除，生成对应的一个后向蚂蚁，后向蚂蚁沿着前向蚂蚁所走过的路径返回到源节点，同时目的节点开始定时计时。对于后面到达的前向蚂蚁，如果在计时范围内到达，前向蚂蚁转换成对应的一个后向蚂蚁沿原路返回，超过计时范围到达的前向蚂蚁直接删除，不作另外处理。

第5步:中间节点每收到一个后向蚂蚁，删除对应蚂蚁访问列表中保存的蚂蚁，如果节点不是目的节点的邻居节点，中间节点要按照式(3)计算信息素，在链路上释放信息素。这样，收到后向蚂蚁的节点就有了到目的节点的路由信信息。如果节点是目的节点的邻居节点，节点可以直接发送数据给目的节点，不用在链路上释放信息素。

第6步:当源节点收到第一个后向蚂蚁，马上在链路上释放信息素，建立到目的节点的路由信息表，删除蚂蚁访问列表中保存的蚂蚁，同时把缓存中的数据发送出去。数据报的发送通过式(4)来进行概率选择。如果节点是目的节点的邻居节点，不用进行公式概率选择，可以通过邻居表直接把数据发送目的节点。

3 仿真与分析

为了测试本文提出的多路径蚁群算法应用到无线传感网中的效果，本实验对ABMR、AOMDV和AntHocNet协议的性能进行比较分析。本文对ABMR协议采用的仿真平台是ubuntu10．04+NS2．34网络仿真平台。笔者实现了用于集成进NS2的ABMR代码，包括ABMR报文格式数据结构和ABMR代理类的实现，并将其添加进 NS2仿真软件。按照AntHocNet协议的功能，基本实现了这个协议，也添加到NS－2里面，用于和ABMR协议的性能分析比较。

3．1 仿真场景与参数设置

移动场景文件使用 CMU工具 setdest创建，SINK节点放在网络中心位置，选用参数表如表1所示。数据流场景选用 CBR，由 CMU工具中的cbrgen．tcl创建，CBR流属于固定速率比特流，方便在不同网络拓扑或节点运动情况下比较性能。各项参数设置表如表2所示。

表1 移动场景参数表

表2 数据流参数表

为了便于研究协议能耗改进性能，能量的传输模型本文选用 First-order Ratio Model[19]，传感器节点参数表如表3所示。ABMR协议里的蚁群路由参数如表4所示。

表3 传感器无线节点的参数

表4 蚁群路由算法参数

3．2 性能分析

仿真实验主要从投递率、时延、路由开销和能量有效性这几个方面对几个路由协议的性能进行比较分析。

图7 分组投递率与节点最大移动速度关系

三种协议分组投递率与节点最大移动速度的关系如图7所示。除了AOMDV协议以外，另外两种协议的数据发送是采用多路径概率发送机制，所以这两个协议的投递率都比AOMDV要高。AntHocNet虽然采用多路径的随机概率发送机制，但数据包会更多的往信息素多的链路上发送，数据包发送多的链路，信息素也会越来越多，最后一条“好”的路径上，数据量会很多，这样会造成局部链路的繁忙，导致丢包的概率上升，所以在移动速度慢的场景，AntHocNet在分组投递率方面比ABMR要差点。AMBR由于采用更好的多路径机制，信息素会根据路径当前能量和负载情况实时进行调整，数据会更均衡的注入网络中的各个路径，最后导致自动的网络负载均衡，各个路径平均分摊网络的流量，在数据流量比较大和节点移动速度快的时候，ABMR在这方面的性能表现的更优越。另外ABMR采用了更合理的链路故障恢复机制，当发现路由出现问题的时候，可以快速恢复路由，从而提高了数据的投递率。所以在各种速度的移动场景下，ABMR协议的分组投递率比另外两个协议表现出更好的性能。

图8显示了几种协议端到端平均时延与节点最大移动速度的关系，非常明显，在延时方面，AntHocNet和ABMR要比AOMDV低不少。AntHocNet是尽量往时延最小的链路发送数据包，如果发包速度不快的话，AntHocNet这时候的时延有优势。当随着节点移动速度的加快，AMBR协议比另外两个协议的延时更少。一方面AMBR采用的多路径机制，到目的节点形成的路径比另外两个协议更多，每个链路上的信息素会根据路径当前能量和负载情况实时进行调整，各个路径平均分摊网络的流量，在某个链路上拥塞的机会就比较少，而且节点在路由上有效的下一跳多的话，当节点快速移动的时候，选择的机会更多。所以，在数据流量比较大和节点移动速度快的时候，ABMR相比另外协议，延迟有更多的优势。另一方面，ABMR采用的链路故障恢复机制，当发现路由出现问题的时候，可以快速恢复路由，减少了数据包的盲目发送，相应的也减少了时延。当节点移动速度加快的时候，下一跳不可达的可能性会增大，数据包的丢失和路由的重新构建会增多，这种情况下，几种种协议的时延都有增加的趋势。

图8 端到端平均时延与节点最大移动速度的关系

蚁群算法在投递率和时延方面显示了良好的性能，但取得这样好的性能，需要有一定的成本和付出。从前面对ABMR协议的详细介绍和分析里我们可以发现，为了适应网络中节点的不断移动和变化，ABMR在路由维护的时候需要定时发送一些前向蚂蚁包，通过后向蚂蚁对路由信息素进行实时的更新。从前面的实验分析结果也可以看到，ABMR提高了数据的投递率以及降低了时延，但定时蚂蚁包的发送也增加了路由的开销。本实验中路由开销是指，目的节点平均每收到一个数据包，所需要的控制包的个数。AntHocNet在路由维护的时候，也需要定时发送蚂蚁包，和AntHocNet相比较，ABMR协议路由维护时候前向蚂蚁的发送方式、多路径机制、基于能量和负载的信息素更新机制和改进的链路维护机制，使得ABMR的路由开销比AntHocNet要少。图9说明了ABMR和AntHocNet的路由开销要比AOMDV大，但ABMR的路由开销又比AntHocNet要少一些。

图9 路由开销与节点最大移动速度的关系

图10 平均能量消耗与最大移动速度关系

平均能量消耗表示目的节点收到一个数据包网络所消耗的平均能量，收到一个数据包消耗的能量越小，说明网络的能量有效性越高。AMBR采用的多路径机制和链路故障恢复机制使得它在和AntHocNet协议的比较中胜出，另外ABMR的路由维护机制也使得ABMR可以发送更少的前向蚂蚁，从而降低了平均能量消耗。随着节点移动速度的增加，数据包的丢包率会提高，路由请求的次数也会变多，导致几个协议的平均能量消耗也增多。当节点移动速度超过30 m/s的时候，几个协议的平均能量消耗的速度快速递增。

4 结束语

本文在分析各种蚁群路由协议的基础上，提出了ABMR协议。ABMR协议在蚂蚁数据包结构、信息素更新公式、信息素更新方式和多路径建立机制等方面都作了进一步改进。

协议在信息素更新公式中综合考虑了路径的能量消耗速度、路径上剩余的最小能量、和距离目的节点Sink的跳数和路径的拥塞程度，这样信息素更新公式更加合理。在信息素更新方式上，每次收到一个后向蚂蚁，都彻底对链路上信息素值进行更新，而不是传统的信息素的累加更新方式，这样的话，数据包在网络上的分布会更均匀。传统的信息素的更新方式，在一个路径上释放的信息素会越来越多，造成这个路径上的数据越来越多，不能到达网络负载均衡。在多路径建立机制方面，中间节点对同一源节点发来的前向蚂蚁作了处理，可以在源节点与目的节点之间建立起多条路径。在数据发送阶段，概率路由选择策略通过每条路径不同的信息素值，把数据流量均衡的注入无线传感网，使得数据均衡发布，最后导致自动的网络负载均衡。减少数据的发送时延，提高数据的投递率和网络寿命。本文最后在NS－2仿真环境下对ABMR、AOMDV、AntHocNet协议进行仿真实验，对结果进行评价和分析。仿真结果表明，ABMR协议在能量有效性和数据分组投递率方面有了一定的提高，同时减小了分组端到端时延。

[1]李建中，高宏．无线传感器网络的研究进展[J]．计算机研究与发展，2008，45(1):1－15．

[2]Akyildiz I F，Su W L，et al．A Survey on Sensor Networks[J]．IEEE Communications Magazine，2002，40(10):2－116．

[3]Rahman K C．A Survey on Sensor Network[J]．Journal of Computer and Information，2010，1(1):76－87．

[4]Shafiullah G M，Amoakoh G A，Wolfs P J．A Survey of Energy-Efficient and Qos-Aware Routing Protocols for Wireless Sensor Metworks[G]//Novel Algorithms and Techniques in Telecommunications，Automation and Industrial Electronics．Springer Netherlands，2008:352－357．

[5]Marina M K，Das S R．Ad Hoc On-Demand Multipath Distance Vector Routing[J]．Wireless Coommunications and Mobile Computing，2006;6:969－988．

[6]Colorni A，Dorigo M，Maniezzo V．Distributed Optimization by Ant Colonies[C]//Proceedings of the 1st European Conference on Artificial Life．1991:134－142．

[7]Dorigo M．Optimization，Learning and Natural Algorithms[D]．Department of Electronics，Politecnico di Milano．1992．

[8]Dorigo M，Stutzle T．蚁群优化[M]．北京:清华大学出版社，2007:3－7．

[9]Dorigo M，Bonabeau E，Theraulaz G．Inspiration for Optimization from Social Insect Behavior[J]．Nature，2000，406(6):39－42．

[10]Di Caro G，Dorigo M．AntNet:Distributed Stigmergetic Control for Communication Networks[J]．Journal of Artificial Intelligence Research，1998，9(1):317－365．

[11]Mesut Gunes，Udo Sorges，Imed Bouazizi．ARA:The Ant-Colony Based Routing Algorithm for MANETs[C]//Proceedings of the 2002 International Conference on Parallel Processing Workshops．Aachen．2002，79－85．

[12]Hussein O，Saadawi T．Ant Routing Algorithm for Mobile Ad-Hoc Networks ARAMA[C]//Proceedingsofthe IEEE Performance Computing and Communications Conference(IPCCC)，2003:15－17．

[13]童孟军，俞立，郑立静．基于蚁群算法的无线传感器网络能量有效路由算法研究[J]．传感技术学报，2011，24(11):1632－1638．

[14]Di Caro，Ducatelle F，Gambardella L M．AntHocNet:An Adaptive Nature-Inspired Algorithm for Routing in Mobile Ad Hoc Networks[J]．European Transactions on Telecommunnications，2006，16(5):443－455．

[15]Laura R，Matteo B，Cgianluca R．On Ant Routing Algorithms in Ad Hoc Networks with Critical Connectivity[J]．Ad Hoc Network Journal，2008，6(6):827－859．

[16]Wang J，Osagie E，Thulasiraman P．HOPNET:A Hybrid Ant Colony Optimization Routing Algorithm for Mobile Ad Hoc Network[J]．Ad Hoc Networks，2009，7(4):690－705．

[17]Misra，Sanjay K Dhurandher，Mohammad S，et al．An Ant Swarm-Inspired Energy-Aware Routing Protocol for Wireless Ad-Hoc Networks[J]．The Journal of Systems and Software，2010，83(11):2188－2199．

[18]Ducatelle F，Di Caro G A，Gambardella L M．An Analysis of the Different Components of the AntHocNet Routing Algorithm[C]//ANTS’06 Proceedings of the 5th International Conference on Ant Colony Optimization and Swarm Intelligence，2006:37－48．

[19]Heinzelman W B，Chandrakasan A P，Balakrishnan H．An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]．IEEE Transactions on Wireless Communications，2002，1(4):660－670．

[20]鲍荣，潘浩，董齐芬．基于信息素扩散模型蚁群算法的无线传感网路由研究[J]．传感技术学报，2011，24(11):1644－1648．