一种基于蚂蚁算法的分布式自组网动态路由方法

摘要

本发明公开了一种基于蚂蚁算法的分布式自组网动态路由方法，它是由路由发现和路由维护两部分构成。本发明的路由发现过程由前向蚂蚁分组和后向蚂蚁分组这两种路由发现蚂蚁分组共同完成，前向蚂蚁分组负责建立返回源节点的路径，后向蚂蚁分组负责建立到目的节点的路径；各中间节点在路由维护阶段的数据传输过程中，实现拥塞问题、断链问题和捷径问题的分布式处理。采用本发明的方法可以减少算法中需要大量蚂蚁造成的附加开销，解决自组网中存在的捷径问题和拥塞问题，使网络负载趋于平衡，减少分组传输的端到端时延。

说明书

技术领域

本发明属于使用自组网技术的领域，如无线自组网络、传感器网络、无线局域网、无线接入等，特别是涉及到无线自组织互连网的路由技术。

背景技术

自组网是一种移动通信和计算机网络相结合的网络，网络中的终端节点在网络中可任意移动，网络拓扑结构变化频繁。便携式移动节点通常依靠电池提供能量，发射功率有限，有时需要多跳转发实现通信，每个用户节点都兼有路由器和终端两种功能。节点需要运行各种面向用户的应用程序和相应的路由协议，并根据路由策略和路由表完成数据分组的转发和路由维护工作，故要求节点采用合适的路由协议。自组网路由算法的设计需要考虑网络的移动性、能量受限、带宽有限和较高的误比特率等特征，在处理网络的快速变化带来的影响的同时对网络的多个服务质量(QoS)参数进行优化。

现有的表驱动和源发起按需路由协议在解决路由问题时都将产生大量难以控制的开销，需要消耗大量的无线带宽和节点能量，影响了网络的可扩展性和网络的性能。另外，大多数现有的路由算法只对某一个QoS参数进行优化，通常主要是针对跳数最优。基于蚂蚁的自组网路由算法由于其优良的分布式特性，能自动配置、自动适应自组网的动态变化，为网络提供大量的路由和可靠连接，可同时对多个QoS参数进行优化。

现有基于蚂蚁的自组网路由方法有：

(1)ARA采用概率选路的方式改善负载平衡问题和减少路由开销，没有考虑如何实现拥塞控制以及对不同业务流的适应，算法没有解决收敛速度问题。参见文献Gunes M，Sorges U，Bouazizi I.ARA-the ant-colony based routing algorithm forMANETs.International Conference on Parallel Processing Workshops.18-21 Aug.2002pp.79-85所述。

(2)MABR协议利用蚂蚁算法寻找目的节点，该算法由于需要确定所有节点的位置并将位置信息传输给网络中的所有节点而过于复杂，难以真正实现。参见文献Heissenbuttel M，Braun T.Ants-based Routing in Large Scale Mobile ad-hocNetworks.Kommunikation in verteilten System(KiVS03)，March 2003pp.281-190所述。

(3)ARAMA对路由的跳数和节点电池使用的公平性进行了优化，目的节点根据前向蚂蚁收集到的路径信息进行路由选择，该算法中采用前向蚂蚁只转发给一个邻居节点的方式对路由发现开销进行控制将造成网络中负载分布不均衡，导致拥塞和瓶颈，而算法也没有相应的解决拥塞问题和捷径问题的机制。参见文献Hussein O，Saadawi T.Ant routing algorithm for mobile ad-hoc networks(ARAMA).Performance，Computing，and Communications Conference，2003.ConferenceProceedings of the 2003 IEEE International，9-11 April 2003 pp.281-290所述。

现有的基于蚂蚁的自组网路由方法存在算法收敛时间较长的问题，对于堵塞问题和捷径问题没有有效的解决方法，而且算法在路由建立时需要大量人工蚂蚁将带来大量的附加通信开销。相关问题参见文献SCHOONER WOERD R，HOLLAND O，et al.Ant-Based LoadBalancing in Telecommunications Networks.Adaptive Behavior，1996，5(2)pp.169-207所述。

发明内容

本发明的目的在于提供一种基于蚂蚁算法的分布式自组网动态路由方法，采用本发明的方法可以改善自组网中基于蚂蚁算法的路由方法的收敛速度问题，减少算法中需要大量蚂蚁造成的附加开销，解决自组网中基于蚂蚁算法的路由方法中存在的捷径问题和拥塞问题，使网络负载趋于平衡，减少分组传输的端到端时延。

为使描述方便，本发明方法做如下定义：

定义1路由发现过程中使用的蚂蚁分组格式定义如下：

ant.ID ant.type ant.hop ant.node ant.destination

其中，ant.ID为蚂蚁分组标识，用以区别于数据分组，ant.type为路由发现蚂蚁分组的类型，用于区别是前向蚂蚁分组还是后向蚂蚁分组，ant.hop为路由发现蚂蚁分组所历经节点的跳数；ant.node为路由发现蚂蚁分组所经历路径中的节点列表；ant.destination为路由发现蚂蚁分组的目的节点。

定义2路由发现过程是指当源节点s有数据分组要发送而又没有到目的节点d的路由时，源节点发起路由发现过程。

需要说明的是，在本发明方案的具体实施步骤中所述的路由发现和路由维护过程中各节点对信息素表中各个表项的信息素概率值的刷新方法，是用下面公式实现的：

$>>>P>>i>,>j>>>>(>d>)>>=>>>>\psi >>i>,>j>>>>(>d>)>>>\underset{}{}$

其中：

P_i，j(d)表示节点i到目的节点d的信息素表中，以j为下一跳节点的信息素概率值，S_i为节点i的所有一跳邻居节点构成的集合，且 $>\underset{}{}$

ψ_i，j(d)表示节点i以j为下一跳节点到目的节点d的信息素浓度，在路由发现和路由维护过程中ψ_i，j(d)先于P_i，j(d)进行刷新，其刷新方式按如下公式表示的方式进行：

ψ_i，j(d)←(1-ρ)ψ_i，j(d)+Δψ_i，j(d)，

其中ρ∈(0，1)为信息素挥发强度参数，Δψ_i，j(d)是节点i收到来自节点n的刷新触发分组时(刷新触发分组包括路由发现的前向和后向蚂蚁分组、路由维护的拥塞控制和捷径增强蚂蚁分组)为ψ_i，j(d)带来的增量值，按以下公式进行刷新：

Δψ_i，j(d)＝0(j≠n)

$>>\Delta >>\psi >>i>,>n>>>>(>d>)>>=>>>(>1>+>>\psi >>i>,>n>>>)>>>->>1>k>>>>\times >>>(>v>+>q>+>h>)>>>->m>>>\times >>(>1>->r>)>>+>>(>r>->2>p>)>>cr>+>1>n>>(>>c>l>>+>l>)>>,>>s>$

其中对于路由发现的前向和后向蚂蚁分组r＝0，对于拥塞控制和捷径增强蚂蚁分组有r＝1，对于拥塞控制蚂蚁分组有p＝1，捷径增强蚂蚁有p＝0，k，m∈N，ν为节点运动速度，q为节点排队产生的时延，h为后向蚂蚁分组从源节点到当前节点所经过的节点跳数，c_l和c均为大于0的常数，l∈[0，1]，反映节点i与节点n之间的链路l_i，n链路质量，ln(c_l+l)为链路质量对ψ_i，n(d)增量的影响。

本发明提供一种基于蚂蚁算法的分布式自组网动态路由方法，包括：路由发现和路由维护两过程，

所述的路由发现的步骤如下：

步骤1  源节点s广播一个寻找目的节点d的前向蚂蚁分组，类型域ant.type＝前向蚂蚁、跳数域ant.hop＝0、节点集合域ant.node＝{s}、目的节点标识域ant.destination＝d。

步骤2  中间节点i在拥塞情况下将收到的来自节点i-1的前向蚂蚁分组丢弃，在可以接纳新路由建立的情况下根据前向蚂蚁分组携带的节点列表ant.node判断是否出现环路，将出现环路的蚂蚁分组丢弃，对于没有出现环路的前向蚂蚁分组将根据该中间节点的信息素表中是否已经有目的节点为s、下一跳节点为i-1的表项决定是否为该前向蚂蚁分组创建记录：如果该中间节点的信息素表中没有目的节点为s、下一跳节点为i-1的信息素表项，则在该中间节点的信息素表中增加一个信息素表项，该表项包括：目的节点s的标识、下一跳节点i-1的标识、节点i通过节点i-1到源节点s的信息素概率值。并对目的节点为s、下一跳节点为节点i的邻居节点的所有信息素表项的信息素概率值进行刷新；如果该中间节点的信息素表中有目的节点为s、下一跳节点为i-1的信息素表项，则直接刷新信息素表中目的节点为s、下一跳节点为节点i的邻居节点的所有信息素表项的信息素概率值；之后，节点在更新前向蚂蚁分组的跳数域ant.hop←ant.hop+1和节点列表域ant.node←ant.node∪{i}后对该前向蚂蚁分组进行转发。中间节点i对信息素表中各个表项的信息素概率值按照信息素概率值刷新方法进行(此时目的节点d此处为s)；

步骤3  前向蚂蚁分组到达目的节点后，目的节点根据收到的前向蚂蚁分组所包含的整个路由发现信息创建后向蚂蚁分组：类型域ant.type＝后向蚂蚁、跳数域ant.hop＝0，顺序提取前向蚂蚁分组的节点列表域ant.node中的所有节点，得到前向蚂蚁分组所经过的路径s→，……，→d并将其逆序后插入后向蚂蚁分组的节点列表域ant.node中。后向蚂蚁分组根据节点列表域按照源路由的方式选择下一跳节点向源节点进行转发，前向蚂蚁分组死亡；

步骤4  中间节点i收到来自节点i+1的后向蚂蚁分组后对信息素表中各个表项的信息素概率值按照信息素概率值刷新方法进行刷新，之后中间节点i再对后向蚂蚁分组中跳数域的值进行修改ant.hop←ant.hop+1，并以此为指针选择后向蚂蚁分组的节点列表域ant.node中的相应节点作为下一跳对该后向蚂蚁分组进行转发；

步骤5  源节点收到第一个后向蚂蚁分组后即建立了到目的节点的路径，该路径中各节点通过在信息素表中选择具有到目的节点最大信息素概率值的表项对应的邻居节点作为到达目的节点的下一跳节点(如果存在多个最大浓度可选择，就在其中随机地选取)的方式逐跳选路，最终到达目的节点，路由发现工作完成。

步骤6  源节点根据其节点信息素表中最大信息素概率值对应的路径进行数据分组传送，各中间节点依次按照其最大信息素概率值逐跳选路，最终将数据分组送到目的节点。

所述的路由维护过程包括：拥塞问题、断链问题和捷径问题处理三部分，

所述的路由维护中对拥塞问题的处理步骤如下：

步骤1当中间节点负载超过设定的拥塞门限时，该中间节点主动向其上游节点发送拥塞控制蚂蚁分组，该拥塞控制蚂蚁分组的生存时间根据拥塞程度设置，拥塞越严重，其生存时间越长。如果该拥塞节点中存在重叠路由，可选择向重叠路由对应的多个上游节点中的任意上游节点发送拥塞控制蚂蚁分组。

步骤2收到来自节点i+1的拥塞控制蚂蚁分组的上游节点i降低相应路由的信息素浓度，对信息素表中各个表项的信息素概率值按照信息素概率值刷新方法进行刷新，并在后续的分组转发中选择其他信息素概率值较大的到同一目的节点的路径进行分组转发。如果拥塞控制蚂蚁分组的生存时间减1以后仍然大于0，则修改其生存时间值以后继续向上游节点转发该控制蚂蚁分组。当生存时间等于0但节点没有其他冗余路由时，该上游节点仍然需要继续向上游节点转发该控制蚂蚁分组。当生存时间等于0且节点有其他冗余路由时，该上游节点丢弃该拥塞控制蚂蚁分组。

步骤3  源节点收到拥塞控制蚂蚁分组且没有其他冗余路由可选用时，则采用本发明所述的路由发现方法重新进行新的路由发现过程以获得新的路由，完成后续数据的传输。

所述的路由维护阶段对断链问题的处理步骤如下：

步骤1  当中间节点i发现到下游节点i+1断链或收到断链消息时，首先删除出现断链的路径对应的信息素浓度表项，再查找本节点是否还记录有到目的节点的另一信息素表项对应的冗余路由。如果有其他冗余路由，则将选择信息素浓度最大的路径作为后续分组转发的路径，并对本节点的信息素表中各个表项的信息素概率值按照信息素概率值刷新方法进行刷新，此时ψ_i，j(d)←(1-ρ)ψ_i，j(d)，其中ρ∈(0，1)为信息素挥发强度参数，j≠i+1(信息素表中ψ_i，i+1(d)项已经被删除)。如果本节点没有其他冗余路由，则继续向本节点的上游节点发送断链信息。

步骤2  源节点收到断链消息，或在数据传输完成前发现了断链且没有其他冗余路由可选用时，则采用所述的路由发现方法重新进行新的路由发现过程以获得新的路由，完成后续数据的传输。

所述的路由维护中对捷径问题的处理步骤如下：

步骤1各个有数据需要发送的节点以设定的概率让新加入的邻居节点和信息素表中信息素概率值较低的邻居节点对数据分组进行转发。

步骤2中间节点i收到来自上一跳节点i-1转发来的源节点s发送到目的节点d的数据分组时，该中间节点对本节点至源节点s的反向链路l_i，i-1进行记录并对该记录设定一个的生存时间，并将数据分组转发到本节点信息素表中到目的节点d的信息素概率值最大的表项对应的下一跳节点。

步骤3如果中间节点i在收到来自相同源节点s但上一跳节点i-1不同的数据分组时发现该数据分组从源节点到本节点所经历的跳数或时延更小，表明此时发现捷径，则该中间节点i将数据分组转发到本节点信息素表中到目的节点d信息素概率值最大的表项对应的下一跳节点，同时沿步骤2建立的反向链路l_i，i-1发送捷径增强蚂蚁分组。

步骤4收到来自节点i+1的捷径增强蚂蚁分组的节点i对信息素表中各个表项的信息素概率值按照信息素概率值刷新方法进行刷新；

步骤5在捷径增强蚂蚁分组的作用下若节点i发现信息素表中Δψ_i，i+1(d)和P_i，i+1(d)项出现较大幅度增长，则可通过直接选择(而不是通过概率选择)Δψ_i，i+1(d)和P_i，i+1(d)大幅度增长的表项对应的下一跳路径转发后续分组，实现后续分组按捷径转发。

综上所述，本发明路由发现过程由前向蚂蚁分组和后向蚂蚁分组这两种路由发现蚂蚁分组共同完成，前向蚂蚁分组负责建立返回源节点的路径，后向蚂蚁分组负责建立到目的节点的路径；各中间节点在路由维护阶段的数据传输过程中，通过对自身的拥塞和链路状态进行监视，实现拥塞问题、断链问题和捷径问题的分布式处理。

本发明方案中路由发现的创新之处在于：现有的基于蚂蚁的自组网路由方法中路由发现时需要源节点发送大量前向蚂蚁分组实现路由的收敛，如ARA、MABR和ARAMA等。本发明中源节点只需发送一个前向蚂蚁分组即可完成路由选择。现有的基于蚂蚁的自组网路由方法中对于同一序列号的蚂蚁分组采用简单的丢弃处理，难以在开销增加不大的情况下提供足够的冗余路由。本发明则在不出现环路的情况下可以提供更多的冗余路由，降低路由重选的开销和时延，并且由于本发明将经过拥塞节点的前向蚂蚁分组进行丢弃，可以使产生的路由在避开拥塞节点的同时减少拥塞节点对前向蚂蚁分组转发带来的附加控制开销。现有的基于蚂蚁的自组网路由方法由目的节点选择路由，再通过后向蚂蚁分组单向更新信息素表，效率较低。本发明中由中间节点在保证不出现环路的情况下通过前向和后向蚂蚁分组实现双向信息素浓度的更新，而且对信息素表的更新主要依靠节点的本地信息做分布式处理，具有更低的传输开销和更高的更新效率。

本发明方案中路由维护的创新之处在于路由维护阶段引入节点负载对信息素浓度贡献的低奖高惩制度，通过相应的QoS参数对信息素浓度的控制实现在拥塞出现前对可能的拥塞进行适当的分流控制，实现网络业务流的均衡，通过捷径增强蚂蚁分组和拥塞抑制蚂蚁分组对信息素浓度的不同影响权值加快解决拥塞控制和捷径问题的收敛速度。

本发明的实质是利用多个不同QoS参数对信息素浓度和信息素概率值的不同影响权值，实现中间节点对路由的分布式优化选择、对路由的快速分布式优化重选和业务流均衡。

本发明与其他自组网路由方法相比，具有以下优点：

1.通过概率选路能提供到目的节点的大量冗余路由，是一种可靠性和顽存性非常好的路由算法。大多数路由分组都集中在最优路径附近，当最优路径失效时，算法可以立即使用次优的路径完成后续数据分组的传输。

2.结合了表驱动和按需方法的优点，克服了两者的不足，对路由进行按需发现，减少了路由发现开销，对附加开销的控制有利于增加算法的可扩展性。

3.能对路径跳数、信道质量、节点负载等多个QoS参数进行优化。

4.通过反向抑制的拥塞控制蚂蚁分组和捷径增强蚂蚁分组进行主动控制，可以有效解决拥塞问题和捷径问题，算法的收敛速度快。

5.数据传输期间通过数据本身携带的信息实现对捷径问题的发现，无需额外引入路由维护分组进行网络负载信息的统计。

与传统的多跳无线自组网路由方式相比，本发明的路由技术更简单有效，能提供到目的节点的大量冗余路由而具有更好的可靠性和顽存性，结合了表驱动和按需方法的优点，克服了两者的不足，对路由进行按需发现，减少了路由发现开销，对附加开销的控制有利于增加算法的可扩展性，能对路径跳数、信道质量、节点负载等多个QoS参数进行优化，可以有效解决拥塞问题和捷径问题，算法的收敛速度快，具有较高的通信能力，网络算法的实现难度低，具有较高的实用价值等优点。

附图说明

图1本发明的路由发现过程的流程示意图

图2是本发明的路由维护过程中对捷径问题的处理流程示意图

具体实施方式：

下面给出一个具体的无线自组网中本专利的实施方法。

无线自组网中每一个节点的路由表均采用信息素表，信息素中各项均为信息素概率值。每个节点的信息素表中均有一个表项与每一个可能的目的节点相对应。一个有30个节点的无线自组网中，每个节点的信息素表都有29个表项，每个表项的元素个数与该节点的邻居节点个数相等。如果一个节点有4个邻居节点，则此节点将的29个信息素表项中每项都有4个元素。按照本发明的方法对信息素表项中的各元素值进行刷新及路由发现和维护，本发明方法中所述步骤，可以通过编程来实现。网络中数据的传输根据信息素表中各元素值选择相应的路由从源节点到达目的节点。

计算机仿真结果表明，采用本发明的路由方法能提供从源节点到目的节点的大量冗余路由，路由发现开销少，能对路径跳数、信道质量、节点负载等多个QoS参数进行优化，能有效地解决拥塞问题和捷径问题，算法具有良好的可扩展性和收敛速度快等优点。