一种移动Ad Hoc网络路由协议的设计与实现＊

李红卫

（广州海格通信集团股份有限公司 广州 510663）

1 引言

Ad Hoc网络是由一组无线移动节点组成、不需要依靠现有固定通信网络基础设施的自组织、自创造、自愈和自管理网络。Ad Hoc网络的多跳性使得借鉴固定网络的路由协议成为可能，但在网络拓扑结构快速变化的情况下，固定网络路由协议无法及时收敛，产生大量的不可靠路由和路由环路，而且路由开销过大［1］。另外，无线带宽有限、单向链路的存在等原因也使得在Ad Hoc网络中不能直接使用固定网络路由协议，而需要根据自身特点设计新的路由协议。

2 Ad Hoc路由协议的分类

根据网络节点发现路由的驱动模式的不同对移动Ad Hoc网络的路由算法进行分类其大致可以分为两大类：一类称作表驱动路由协议，一类称作按需路由协议［2］。

表驱动路由协议的路由发现策略与传统的路由协议类似，各节点需要周期性地在网络中传播路由更新消息，以维护路由表的一致性和正确性，它的优点是系统寻径时延小，缺点是周期性的路由更新消息对网络带宽的占用较大，不适合于移动性较大的通信系统，如DSDV、WRP、HSR等［3］。

按需路由协议在有数据需要发送的时候再向网络中广播路由发现请求信息，等待目的节点回送路由应答信息，其优点是不需要周期性的路由信息广播，因而节约网络带宽，适合于快速移动的通信系统，缺点是寻径时间较长，如AODV、DSR等［4］。

3 Ad Hoc路由协议工作原理

3.1 协议概述

本路由协议适用于移动Ad Hoc网络，最大支持6跳，采用可优化链路状态协议，该协议是一种反映链路质量的混合路由协议，其主要指导思想是基于按需进行路由操作的原理，在保证路由的基础上尽可能地减少路由控制信息的广播，提高实际数据传输率。考虑到使用的物理设备的无线信道传输可靠性较低，在分组传递中采用了逐跳确认数据分组、超时重发和报文序号等机制，为了弥补在相对静止的条件下，按需路由协议存在的反映速度比主动路由协议慢的缺陷，增加了定时或事件触发方式向邻居节点进行路由公告的机制来进行路由的维护。

3.2 路径发现

1）路由请求的发送

图1 网络拓扑结构图

如图1所示，当 Ad Hoc网络内的源节点S需要向目的节点D发送数据时，如果同时满足以下两个条件，S发起一个路由请求：（1）S的路由表中没有到D的路由；（2）距离上次S发起到D的路由请求的时间大于协议所规定的最小相同路由请求间隔。

条件（1）是显而易见，条件（2）是为了防止源节点频繁地发起到同一目的节点的路由请求的限制条件，即源节点对于同一目的节点的路由请求必须至少间隔一段时间。此时S生成一个到D的路由请求分组，其中包括目的节点地址、用于区分不同路由请求分组的唯一标志（ID）、源路由列表等（在开始时源路由列表中只有S自己），然后将此路由请求分组在网络内部进行泛洪。

2）路由请求的处理

如图1所示，收到路由请求分组的节点B要对该分组进行判断处理，算法如下：

（1）每个节点都有一个接收到的路由请求分组的缓存队列，用于存放最近收到的路由请求分组的标志和目的地址［5］。收到路由请求分组后，B首先查看该路由请求是否已在本节点的路由请求分组队列中，如果在，则说明曾经收到过该分组，丢弃该分组；

（2）否则，查看本节点是否已在该路由请求分组的源路由列表中，若在则说明这是一个通过环路过来的分组，丢弃该分组；

（3）否则，查看本节点的路由缓存中是否有到D的路由，如果有，则B构造一个路由应答分组，其中携带从S到B的路由和从B到D的路由，此时应避免出现路由环路；

（4）否则，查看本节点是否是该路由请求分组所请求的目的节点，如果是，则说明在该分组中已经包含了从源节点到目的节点的完整路由，提取该分组中的夹带选项进行处理，并将该分组中的源路由复制到路由应答分组中，构造一个路由应答分组，并将该路由应答分组发送给S；

（5）否则，B在路由表中加入从S到本节点的路由信息（路由学习），将本节点的地址加入该路由请求分组的源路由列表中，继续广播该分组；

（6）为了限制路由请求分组在网络中的传播范围，在分组中设置了TTL，接收节点在处理该分组时将TTL减1，当TTL为0时，丢弃该分组。

3）路由请求的应答

由于路由请求采用广播方式传输，目的节点D可能收到经过多个不同路径发来的路由请求分组，如图1所示，这些分组最终都到达了D，因此这些路径都是有效路径，但未必是最佳路径，因此D需要对它们进行选择，即D只对那些更短的或者等长的路径构造路由应答分组，而舍弃更长的路径。

如果目的节点D的路由表中没有到源节点S的路由，D发起一个路由请求，其过程与上文描述的相同，但是D在所构造的路由请求分组中携带一个路由应答选项，可称之为夹带，其原因是：

（1）在双向信道的情况下，路由应答分组按照路由请求分组的相反方向返回S，但由于无线信道可能存在的单向信道，逆向路由可能不存在，如果按照路由发现的一般过程先发送从D到S的路由请求，等待S的路由应答建立这段路由，然后利用源路由分组发送从D到S的路由应答的话，将会导致从D到S的路由应答时间较长，并且会在网络中增加大量的路由请求和路由应答分组，增大网络开销；

（2）当D请求到S的路由时，S还没有到D的路由，则S和D之间将出现死循环的路由请求过程。因此，可以通过夹带机制在路由请求分组中夹带路由应答、路由确认以及不同优先级的数据分组，从而避免路由请求中的死循环，并且加快路由协议对网络拓扑变化的反应速度。

中间节点在收到夹带路由应答选项的路由请求分组时，不但从路由请求分组中学习从D到本节点的路由，而且从夹带的路由应答选项中学习其中包含的从S到D的路由，以维护本节点的路由表。

源节点S在收到D发送的路由应答分组后，从路由应答选项中提取所发现的源路由，复制到本节点的路由表中，然后开始发送从S到D的数据分组。

节点在发送或者转发路由请求分组时采用广播方式发送给所有邻居节点，如果很多邻居节点都具有到该请求节点的路由，那么所有这些邻居节点都将试图进行路由应答，这种情况下路由应答将浪费大量的带宽并增加共享无线信道的冲突机率，这种问题又称“路由应答风暴”［6］。

因此，可以利用无线信道的广播特性对路由应答分组随机延迟一段时间后再判断是否进行传输，以减少不同节点同时发送路由应答的机率。

4）在路由请求中使用扩展环搜索

在路由请求的传播过程中，Ad Hoc网络内的所有节点都可能收到并传播任何节点的路由请求，这种情况将大大造成网络的拥塞。为了减少这种网络开销，源节点应当采取一定措施限制对路由请求的传播的最大值，例如扩展环搜索，算法如下：（1）源节点在进行路由请求时，首先发送一个限制传播范围在一跳之内的路由请求，称为非传播型路由请求；（2）如果在协议规定的时间参数内没有收到对非传播型路由请求的路由应答，源节点再发送一个传播范围限制在6跳之内的路由请求。

因此，当S试图请求到D的路由时，它有可能发送两次路由请求：一次是非传播型路由请求，一次是限制传播范围在6跳之内的路由请求。由于非传播型路由请求要求所有与本节点在一跳范周之内的节点进行路由应答，那么如果D在本节点的一跳范围内，D可以立即进行路由应答；否则，如果本节点的邻居中有节点具有到D的路由，那么它们可以进行路由应答，相当于本节点有效地利用了邻居节点的路由表对自己的路由表进行扩展。在这种情况下，S不必在两次发送路由请求之间进行规避。由于非传播型路由请求限制在一跳范围内，其超时的时间设置应当取一个很小的值。

3.3 路径维护

由于网络节点具有较强的移动性，Ad Hoc网络在拓扑结构发生变化后，源节点S到目的节点D的路由可能因为该路由中的某一跳失败而不再有效，此时必须依靠路由维护机制使S及时检测到该变化。当路由维护机制检测到一条路由变坏时，S可以尝试使用它偶然学习到的其它到D的路由，或者启动路由发现寻找一条新的路由。

路由维护提供一种机制来维护S和D之间路由的连通性。Ad Hoc网络中的每个节点都维护一张路由表，用来维护本节点到其它节点的路由。当网络拓扑发生变化时，节点根据收到的信息更新自己的路由表，使它与网络拓扑保持一致。

路由维护有三种基本手段：（1）定期发送路由公告，在节点之间交换路由信息，以维护路由；（2）通过路由应答获取和维护路由；（3）通过路由学习获取和维护路由。

1）路由公告

当AdHoc网络处于相对静止的使用环境中，如果采用按需路由协议，在第一次发送数据分组时，往往由于没有去往目的节点的路由，需要启动路由发现过程；如果采用主动路由协议，通过相邻节点周期性地相互交换路由信息，可以在发送数据分组之前知道去往目的节点的路由，分组到达目的节点的时间比采用按需路由协议要短，但这种速度优势是以消耗信道带宽为代价的［7］。

为了弥补按需路由协议在相对静止网络环境下的不足，本协议适当地采用了主动路由协议中的邻边维护机制，即：网络中所有节点每隔一定时间向相邻节点发送路由公告分组，且令该分组的TTL＝l，路由公告分组中包含本节点的路由表等内容，邻居节点根据收到的路由公告分组更新本节点的路由表。

2）拓扑结构获取

在Ad Hoc网络中，网络拓扑结构信息的获取有两种方法：一是各个节点周期性或事件触发的路由公告，二是各个节点发送的数据分组。

路由公告用于报告本节点的路由信息、它根据所收到的邻居节点和一跳以外其它节点的信息，节点周期性地将自己的路由表通过路由公告的形式向相邻节点广播，主要目的：一是报告自己的存在；二是与相邻节点交换路由表。通过路由公告，各个节点可以得到网络的拓扑信息。

节点收到一个分组时，首先判断该分组的类型。如果该分组不是路由公告，则提取分组头部，处理其中的路由信息，同时根据该分组的数据类型对分组进行相应处理；如果当该分组是路由公告，则提取并处理其中的路由信息，处理完毕后如果发现网络拓扑发生了变化，则更新本节点的路由表，并发送路由公告［8］。路由公告中包含节点的路由表内容，路由表以二维矩阵的形式表示。RouteTable［m，n］表示节点m到节点n的单向信道的边权值。

（1）当节点通过收到的路由请求分组、路由应答分组、数据分组中的路由信息更新路由表的时候，将相关矩阵元素值初始化为MaxLifeValue；

（2）与路由错误分组中的路由信息对应的相关矩阵元素值初始化为－MaxLifeValue；

（3）节点每隔TimeRefreshInterval对路由矩阵中的链路权值减少LifeShortScale，链路边权值越大说明链路越可靠；

（4）收到相邻节点的路由公告后，节点将路由公告的路由表中的边权值和自己路由表中的边权值进行比较并进行更新，然后节点根据新的路由表采用最短路径算法得到更新后的路由表：（IfNew［i，j］＞Old［i，j］，则用新的权值更新路由表；（IfNew［i，j］＜Old［i，j］，则保留本节点的权值。

Ad Hoc网络中的节点可以自由入网或者退网，因此将会产生新的无线链路，链路质量的变化或者节点的入网与退网将触发路由公告。路由公告的触发机制为：（1）将失效链路的权值设为0；（2）将新的链路的权值设为 MaxLifeValue；（3）修改自己的路由表，并构造一个路由公告分组，广播最新的链路状态信息。

3）邻边维护

在本路由协议中，将网内任何两个节点之间的有向链路定义为一条“边”。由于无线信道的传输质量较差，在进行路由选择时不仅要考虑源节点和目的节点之间的距离（即跳数），而且还要结合不同路由的边权值，以便更好地反应链路的当前通信状态。在每个节点的路由表中都保存有到其它节点的边的权值，进行路由公告时每个节点将本地路由表与邻居节点进行交换，这样一来不仅能够维护自己的路由，而且可对边和权值进行更新。当边权值发生变化时，相应地触发路由公告，将此信息通知邻居节点，从而实现邻边维护功能。

邻边维护的规则如下：（1）如果一个分组从源路由重传到泛洪重传都是失败的，没有任何形式的分组确认，则认为源节点到目的节点的边的可信度降低，例如将可信度减半；（2）如果收到一个分组，则发送该分组的源节点和本节点的边的可信度设为最大值；（3）如果收到一个泛洪分组，该分组前面已经采用源路由发送过，则分组的源节点和本节点之间的双向边的可信度减半；（4）对于源路由分组，本机作为中间节点如果转发成功，则本节点和下一跳节点之间的双向边的可信度设为最大值。

3.4 选路算法

当S需要在本地路由表中寻找一条到D的最优路由时，可以采用多种算法，如果考虑链路的权值，则最优路由是从S到D的所有链路的权值或者代价总和最小的一条路由。在本路由协议中，结合边的权值作为路由选择的依据。源节点采用Dijkstra算法。

Dijkstra算法用于计算一个顶点到其他所有顶点间的最短路径，其能得出最短路径的最优解，是典型的单源最短路径算法。为了求得这些最短路径，Dijkstra按路径长度递增，逐次产生源点到其他顶点间的最短路径。首先求出长度最短的一条路径，然后参照它求出长度次短的一条最短路径，以此类推，直到从顶点到其他顶点的最短路径全部求出为止［9］。该算法的具体描述如下：

集合S：存放已经求出最短路径的终点，初始状态下，S中只有一个源节点v0。以后每求得一条最短路径（v0，…，vk），就将vk加入到集合S中。直到全部顶点都加入到集合S中，算法结束。

使用数组dist存储当前找到的从源节点v0到其他节点的最短路径长度，每个顶点对应该数组中的一个元素dist［i］，这个元素存放当前源点到该顶点的最短路径长度，如果路径不存在的话便是无穷大。dist的初始状态是：若从源节点v0到终点vi有边，则dist［i］为该边上的权值；若从源点到终点没有边，则dist［i］为＋∞。此时的路径指示当前结果，并不一定是最终的最短路径。随着集合S的变化，其他节点不断地加入到集合中，可能以这些新加入的顶点为“桥梁”产生比以前路径更短的路径，dist数组元素的值是动态变化的。

1）设第一条最短路径为（v0，vk），其中k满足：dist［k］＝min｛dist［i］｜vi∈V－v0｝（V为所有顶点集合）。

2）求下一条最短路径：假设下次最短路径的终点是vj，则可想而知，它或者是（v0，vj），或者是（v0，vk，vj）。其长度或者是从v0到vj边上的权值，或者是dist［k］与从vk到vj边上的权值之和［10］。

一般情况下，假设S为已经求得最短路径的顶点集合，则可以证明：下一条最短路径必然是从v0出发，中间只经过S中的顶点便可到达的那些顶点vx（vx∈V－S）的路径中的一条。因此在一般情况下，下一条次短的最短路径的长度必是：

3）在每一次求得一条最短路径之后，其终点vk加入集合S，然后对所有的vi∈V－S，修改其dist［i］：dist［i］＝min｛dist［i］，dist［k］＋edge［k］［i］｝，其中，edge［k］［i］为边（vk，vi）上的权值。

4 协议的编程实现层次模型

本路由协议在实现上分为五层：物理层、数据链路层、网络层、运输层、应用和服务层。网络应用程序不直接与网络硬件交互，应用于协议软件交互，在设计无线网络协议栈时，除了必须考虑固有的无线信道问题、移动性问题以外，还需要考虑能量效率问题［11］。协议的编程层次模型如图2所示。

图2 协议层次模型图

1）应用和服务层

应用和服务层负责信源编码、数字信号处理、移动环境下的自适应。应用和服务层提供的服务是变化的、面向具体应用的。

2）传输层

运输层实现端对端的数据传送功能。负责提供网络端点之间的高效、可靠的IP数据传输，而与使用的物理网络无关。

3）网络层

网络层完成区域内所有站点上的区域内路由选择和区域出口站点上的区域间路由选择，维护网络拓扑结构信息；负责给分组寻找传输路由、建立网络服务类型、传输层与数据链路层之间的分组传递。在移动Ad Hoc网络环境中，网络层还要负责分组的转发路由，以及移动性管理。

4）数据链路控制

数据链路控制层负责在不可靠无线链上建立可靠、安全的逻辑链；负责无线链的差错控制、安全、将网络层分组映射为帧、分组重传；实现共享信道的多重访问控制和依据信道质量进行的发送速率控制，以及站点间相邻关系和信道质量信息的维护。

5）物理层

物理层包含射频RF电路、调制、信道编码系统。完成二进制数据与跳频信号间的调制／解调功能，并且包含设备保密单元对跳频信号序列的加密和解密，保证只有配备相同设备保密单元的站点间可进行数据传送。

5 结语

根据产品实际需求，本文提出了一种反映链路质量的混合路由协议。该协议主要包括主动路由和按需部分，主动路由是基于链路－状态法思想，体现在相邻节点之间链路状态信息的交换；按需路由是在现有按需路由策略中的路由请求／回答的交互过程基础上增加了信道指标信息的传播。经产品长时间使用验证，该协议寻径时间较短，路由协议开销较小，能对链路状态的变化做出快速反应，使用效果良好。

［1］赵迪，陈向东.Ad Hoc网络两种按需路由协议性能仿真分析［J］.通信技术，2010，43（4）：2－3.

［2］陈林星，曾曦，曹毅.移动Ad Hoc网络－自组织分组无线网络技术［M］.北京：电子工业出版社，2006：20－21.

［3］Hong X Y，Xu K X，Gerla M.Scalable routing protocols for mobile ad hoc networks［J］.IEEE Network，2002，16（4）：11－22.

［4］刘凯，李维英，李建东.支持多媒体业务的自组织无线网络协议［J］.西安电子科技大学学报，2000，27（2）：190－194.

［5］周海刚，肖军模.Ad Hoc网络的安全问题和安全策略［J］.电信科学，2001，17（12）：39－42.

［6］矣昕宝，全海燕，董会升.一种用于Ad hoc网络的精简路由协议设计与实现［J］.科学技术与工程，2011，11（35）：40－41.

［7］米志超，鲍民权，郑少仁.一种基于多跳Ad Hoc网络的路由协议的设计与实现［J］.西安电子科技大学学报（自然科学版），2001，28（6）：707－710.

［8］郑少仁，王海涛，赵志峰，等.Ad Hoc网络技术［M］.北京：人民邮电出版社，2005：32－33.

［9］周满元，周力为.基于不同源节点数目的AODV路由协议的性能比较研究［J］.计算机工程与应用，2007，43（18）：94－96.

［10］Akyildiz l F.A Survey on Wireless Mesh Networks［J］.IEEE Communications Magazine，2005，43（9）：23－30.

［11］Wolfgang kiess，Martin Mauve.A Survey on realworld Implementations of Mobile Ad－Hoc Networks［J］.Ad Hoc Networks，2007，5（3）：324－339.