移动Ad Hoc网络中基于QoS的多路径路由协议研究

李 健，董亚雷，王 刚

(1.重庆市民防办公室，重庆400015;2.重庆邮电大学，重庆400065)

移动自组织网络(简称移动Ad Hoc网［1］)作为一个临时性多跳自治系统，是由一组带有无线收发装置的可移动节点所组成，并且不依赖于预设的基础设施，具有可临时组网、快速展开、无控制中心、抗毁性强等特点，在军事和民用方面都具有广阔的应用前景，是目前网络研究中的热点问题。近年来，随着无线通信技术的迅速发展，语音、视频等多媒体业务也逐渐应用于移动Ad Hoc网，因而如何在移动Ad Hoc网中提供高质量的QoS保障［2-3］是当前亟待解决的问题。同时值得注意的是，在Ad Hoc网中，数据的传输主要通过单路径路由的方式进行，对于大流量数据业务来说，该方式无论在容错能力上还是在带宽利用率［4］上都远远无法满足需求。因此本文将针对移动Ad Hoc网中多路径QoS路由进行研究，通过推导证明提出路径长度限制的路径稳定的约束关系，引入QoS的判定因子对该确定性的最优权值约束算法进行实例化，并在该路由算法的基础上提出基于QoS保障的多路径［5］路由协议(MP-QAODV)。

1 网络模型及数学描述

本文采用通过一个有向图G(V，E)表示一个网络，V为节点集合，E为边集合，e=u→v表示节点v到节点u的链路，其中每条链路e都关联k个相互独立的权值w1(e)，w2(e)，…，wk(e)，wj(e)∈R+，∀1≤j≤k。向量W(e)=［w1(e)，w2(e)，…，wk(e)］表示链路e的权值矩阵。向量W(p)=［w1(p)，w2(p)，…，wk(p)］表示路径p的权值矩阵，其中每条路径p的权值wj(p)可以通过简单累加路径中的每一条边的权值来获得，即

定义1:假设图G(V，E)有k个不同的权值，其中k≥2，src表示源节点，dest表示目的节点，多约束条件限制问题(Multi-Constrained Problem，MCP)就是找出一条从src到dest的路径p，其中w1(p)≤c1，w2(p)≤c2，…，wk(p)≤ck，c1，c2，…，ck表示k个约束条件。当k=2时，转换成两个约束条件问题。

定义2:假设图G(V，E)有k个不同的权值，存在两条从相同源节点到相同目的节点的路径p和q，如果W(p)＜W(q)，那么有路径p主导路径q，也可以说q被p主导。如果路径p在从相同的源节点到相同的目的节点的路径上不被任何路径主导，那么就有路径p为非主导路径。由此可知，当k≥2时，图中存在不止一条非主导路径。当k=1时，该非主导路径也就是最优路径。

性质1:如果从源节点到目的节点存在一条满足所有QoS约束的路径，那么必然至少存在一条从源节点到目的节点并且满足这些约束的非主导路径。一个性能较佳的QoS路由算法仅仅只需要考虑从源节点到目的节点的非主导路径。

2 基于QoS约束的路由算法描述

2.1 路径长度限制的路径稳定的路由算法

通常来讲，路径的稳定度直接影响网络性能，尤其在无线网络环境下，对路径的稳定度要求更高。但是路径的稳定度和对应节点跳数要有一个权衡，往往由大量节点跳数组成的稳定路径的网络性能都不尽如人意。本算法意在对路径长度和路径稳定度进行权衡，从而寻找出一条满足两个限制条件的最佳路径。下面定义两个权值:

假设权值w1∈N*表示路径中的节点跳数，对于任意e∈E，存在w1(e)=1;对于任意路径p=(scr=u0)→u1→…→(un=dest)，存在权值ui+1)=n。

假设权值w2∈R+表示路径稳定度。为了定量分析路径稳定度，设定一个范围值，1表示稳定度最高，0表示稳定度最低，同时规定路径中一条边的存在仅在两个端节点的通信范围R之内，这样路径中边的稳定度判定条件为

式中:dx，y表示端节点x，y之间的距离值。通过数学变换，式(1)可以转化成

一条路径由多条边构成，因而路径稳定度可表示成

式中:路径P=(s，d)，而s，d分别表示源节点和目的节点;集合Ss，d表示构成路径的边的集合。

假设集合Πs，d表示从源节点s到目的节点d的所有路径，那么稳定度最高的路径Popt可以表示为

由于自然对数(ln)严格遵循单调递增，可得

由式(3)和(5)进一步转化可得

将式(6)化简，每条边稳定度的权值可以表示为

根据以上的数学推导过程可以得出路径长度和路径稳定度的关系，即路径长度越短，其稳定度越高。

2.2 确定性的最优权值约束算法描述

通过上述算法，可以获取路径长度因子和路径稳定因子两个限制权值w1，w2。下面将通过本算法解决在两个权值限定的基础上获取最佳路径的问题，即为具有相同源节点和目的节点的路径寻找一条最优权值约束的路径。集合PATH(u)用来存储任意节点与节点u相关联并且满足权值w1的限制条件的非主导路径，而寻找一条最优权值约束的路径就是在集合PATH(dest)中挑选满足另一权值w2限制条件的非主导路径。

算法具体实现的伪代码如下所示:

1:for i=1 to|V(G)|do

2:PATH(i)←Φ

3:end for

4:PATH(src)←{src}

5:for i=1 to|V(G)|do//Note:W=(w1，w2)

6:for all(u，v)∈E(G)do//u and v are neighbors

7: for all p∈PATH(u)do

8: if(w1((u，v))+w1(p))≤C then

9: for all q∈PATH(v)do

10: if(W((u，v))+W(p)≤W(q))then

11: delete q from path(v)

12: end if

13: r←p+(u，v)

14: if w1(r)≥w1(q)and w2(r)＞w2(q)then

15: delete r

16: Ignore p

17: break

18: else

19: add r to PATH(V)

20: end if

21: end for

22: end if

23:end for

24:end for

25:end for

26:

27:if PATH(dest)is empty then

28:return NUL

29:end if

30:

31:Shortest_Path←First element of PATH(dest)

32:for all p∈PATH(dest)do

33:if W(p)≤W(Shortest_Path)then

34:Shortest_Path←p

35:end if

36:end for

37:return Shortest_Path

上述代码中:第1～4行是路径的初始化过程，该过程除了源节点src以外，其他任何节点的PATH集合都设置为空。第5～25行是构建满足约束条件的路径集合PATH，该集合中不仅包括从源节点src到目标节点的所有非主导路径，而且还包括用于计算非主导路径的其他路径。由此可知，从源节点src到任意节点n的多数非主导路径存储在集合PATH(n)中，而算法的第2个权值限制条件w2，主要为了在集合PATH(n)中寻找最佳路径(w2权值最小的路径也就是最短路径)。当节点n为dest节点时，寻找出来的最佳路径就是从源节点到目的节点的最佳路径，第27～37行为在集合PATH(n)中取最佳路径的过程。

3 基于QoS的多路径路由协议描述

前面提出了一种路径长度和路径稳定度限制的路由算法，通过数学推导得出路径长度和路径稳定度的关系，并将QoS判定因子实例化到算法中。将算法应用于AODV［6］协议后，仅加入一个路径长度衡量标志就可确保从源节点到目的节点满足QoS要求的路径。但是单路径的路由协议在网络利用率和容错性上仍不能满足现有大流量数据传输业务的QoS需求，因此采用多路径的方式来克服单路径路由存在的缺陷。本节将对现有的AODV协议进行修改，从而提出一种基于QoS的节点不相交备份多路径路由协议MP-QAODV。

3.1 路径长度限制的路径稳定的路由算法

MP-QAODV协议对路由请求包RREQ和路由应答包都作了修改。RREQ包中添加了Distance Sign字段，该字段存储了节点通过配备GPS设备获取所处位置的坐标信息。源节点s到目的节点d的距离可以根据公式dis=得到，根据前面算法中路径长度和路径稳定度的关系，直接通过路径长度判断路径稳定度。

同时，RREQ又添加了1 bit的标志位“F”，该标志位主要用来区分路由发现阶段主路径的数据包(RREQ，RREP)和备选路径的数据包(RREQ_2，RREP_2)，如图1所示。

3.2 MP-QAODV路由协议描述

3.2.1 路由发现过程

MP-QAODV源节点开始广播ID值为1的路由请求包RREQ到目的节点。当中间节点接收到RREQ包后，将把ID值以及有关源节点的路由信息保存在本地路由表中。目的节点将沿着反向路由将RREP包发送给源节点。

图1 MP-QAODV RREQ包格式和RREP包格式

中间节点收到RREP包后将对保存在路由表中的RREQ ID进行递增。协议通过递增RREQ ID值的过程确保备份路径不占用主路径中的任意一个节点。

当源节点接收到RREP包后，就完成了主路径建立的过程，这时源节点开始一边发送数据包一边广播RREQ_2包(RREQ ID值递增后为2)来寻找备用路径。其中RREQ_2是备份路径的路由请求包，它的标志位F设置为1。

当RREQ_2包传递到中间节点时，中间节点就在本地路由表中查询RREQ包的ID值与RREQ_2包进行比较。若相同，则丢弃该数据包;否则将转发该数据包。由于主路径在建立过程中都对各个节点路由表中的RREQ ID值进行了递增，所以如果RREQ_2 ID值与中间节点路由表中RREQ ID值相同，说明中间节点是主路径中的一个节点，这样协议在选择备用路径时将放弃该节点(MPQAODV属于节点不相交的备用多路径路由协议)。

当RREQ_2包到达目的节点后，目的节点将沿着反向路由方向发送RREP_2(标志位F设置为1)包到源节点。源节点收到RREP_2包后，备份路径的建立过程完成。在整个备份路由发现过程中，路径中的节点将不会递增路由表中的RREQ ID值，但主路径节点路由表中的RREQ ID值必须递增。即在协议完成路由发现过程之后，主路径节点路由表中的RREQ ID值为3，而备份路径中的为2，总是要比备份路径的值大1。图2所示为MPQAODV协议的流程图。

3.2.2 路由维护过程

MP-QAODV协议的路由维护过程存在两种情况:

1)当主路径发生断裂［7］时，源节点会收到返回错误信息包RERR。同时备份路径将取代主路径来进行数据包的传输，而主路径将初始化并重新建立路由。主路径重新发起路由发现之前，需要将RREQ ID值在备份路径的基础上递增1个单位，由此来区分重新建立主路径和备份路径。

图2 MP-QAODV路由发现流程图

2)当备份路径发生断裂时，源节点仍然需要接收返回错误信息包RERR，为了判断该错误信息包是来自主路径还是备份路径问题，协议在源节点的本地路由表中增添了一个表项Route_flag。如图3所示，Route_flag值为0和1，分别代表主路径和备份路径。所以源节点收到RERR包后，通过核对路由表中的“Route_flag”表项来判断是主路径还是备份路径。

图3 源节点的本地路由表

备份路径重新建立过程只需要初始化源节点，同开始建立备份路由过程一样重新进行路由发现，这样备份路由中的RREQ ID值相比主路径的值仍然小于1，从而与主路径相区别。如图4所示，MP-QAODV协议路由维护过程流程图。

图4 MP-QAODV路由维护流程图

4 仿真评估

本文采用NS2仿真场景来衡量MP-QAODV，AOMDV和AODV协议的性能［8］。同时本文采用IEEE802.11 DCF(Distrbuted Coordination Function)MAC协议的CSMA/CA技术来传输分组数据;传输信道带宽设置为2 Mbit/s;无线信道范围为R=250 m。节点的移动模型采用双径地面反射模型(Two-ray Ground Reflection，TGR)，在R=250 m的网络覆盖范围内，发送天线和接收天线的高度为1.5 m，收发天线的增益为1，最低接收功率3.65×10-10W;节点的移动速度为［0 m/s，30 m/s］，仿真时间为900 s。具体参数如表1所示。

表1 仿真环境参数设置

本仿真场景主要对比节点移动状态下3种路由协议的性能，分别对比端到端时延、分组投递率、归一化路由开销和路由发现频率4个参数，测试场景具体参数如表2所示。

表2 仿真参数

如图5所示，随着节点移动速度的增加，AODV，AOMDV和MP-QAODV三种路由协议的端到端平均时延也相应增加，这是由于节点的移动增大了路径失效的概率，从而数据分组不能有效传输到目的端，导致端到端的时延增加。对于多路径路由协议AOMDV和MP-QAODV来说，由于采用了备份路由机制，比单路径路由协议的路由发现次数要少，进而端到端的平均时延也要小于AODV。同时MP-QAODV引入了路径稳定性的路由算法，增强了网络路径的稳定性，路径的失效概率要小于AOMDV协议，因而其端到端的平均时延最小。

图5 节点移动速度变化时端到端平均时延比较图

由图6可知，当节点接近静止时，3种协议的分组投递率非常相近，但随着移动速度的增加，它们的分组投递率都有所下降，其中AOMDV下降程度明显高于其他两种协议。这是因为AOMDV协议采用备份路由方式，即在所有路径都失效后才发起新的路由请求，并且分组数据在主路径传输时没有对备份路径进行有效的维护，从而很容易造成备份路径在启动前失效后主路径在路径间来回切换，最后导致丢失更多的数据分组。对于同样是多路径的MPQAODV协议来说，因为它是基于AODV协议改进的，其备份路径的建立与主路径发送数据分组在同一过程并且该协议仅维护一条备份路径，不存在主路径和失效路径的频繁切换，因而分组投递率要高于AOMDV和AODV协议。

图6 节点移动速度变化时分组投递率比较图

如图7所示，随着节点移动速度的增加，AODV，AOMDV和MP-QAODV三种路由协议的归一化路由开销也相应增加。AOMDV协议相对于其他两种协议的路由开销要大些，这是因为AOMDV在路由发现过程中建立了多条备份路径，在节点移动速度增加的时候，其备份路径失效的可能性增加，从而维护路由分组消息将大大增加，同时根据图6可知，AOMDV在较快的节点移动速度时分组投递率相对较低，从而导致AOMDV的归一化路由开销明显高于其他两种协议。对于多路径路由协议MPQAODV，它仅仅维护一条备份路由协议，并且在AODV的基础上加入了路径稳定性算法，在移动速度增加情况下路径失效的可能性大大减少，同时相对于AODV协议，它的控制分组数明显要小一些，再加上相对较高的分组投递率，因而MP-QAODV的归一化路由开销要小一些。

图7 节点移动速度变化时归一化路由开销比较图

由图8可知，AODV，AOMDV和MP-QAODV三种协议的路由发现频率随着节点移动速度的增加而增加。对于多路径路由协议AOMDV和MP-QAODV，一次路由发现会找到多条路径，所以路由发现频率相对于单路径路由协议AODV要明显低很多。同时，与AOMDV在路由发现阶段选择多条备份路径相比，MP-QAODV仅选择一条备份路径，因而MP-QAODV的路由发现频率略高于AOMDV。

图8 节点移动速度变化时路由发现频率比较图

仿真结果表明，随着节点移动速度的变化，AODV，AOMDV和MP-QAODV三种路由协议端到端的平均时延、分组投递率、归一化路由开销以及路由发现频率都有相应的变化。同时由以上分析可知，MP-QAODV协议在端到端的平均时延、分组投递率以及归一化路由开销所表现出来的网络性能要优于其他两种协议。尽管在路由发现频率上略高于AOMDV协议，但是并不影响其整体的网络性能。

5 结束语

本文针对当前移动Ad Hoc网络不能有效满足大流量业务情况，提出了一种基于QoS保障的多路径路由协议(MP-QAODV)，该协议采用路径长度限制的路径稳定的路由算法，其平均端到端时延、分组投递率以及归一化路由开销3项性能指标都优于AODV和AOMDV协议，仅在路由发现频率上略高于AOMDV协议。因此，下一步的主要工作是研究如何降低该协议的路由发现频率，从而达到更好的网络性能。

［1］JOHNSON D B，MALTZ D A.Dynamic source routing in Ad Hoc wireless networks［M］//IMIELINSKI T，KORTH H F.Mobile Computing:The Kluwer International Series in Engineering and Computer Science.［S.l.］:Springer US，1996:153-181.

［2］MUELLER S，TSANG R P，OHOSAL D.Multipath muting in mobile Ad Hoc networks:issues and challenges［EB/OL］.［2012-05-05］.http://alumni.cs.ucr.edu/～ibasaran/research/Multipath% 20Routing%20in% 20Mobile% 20Ad% 20Hoc% 20Networks% 20Issues% 20and%20Challenges.pdf.

［3］SHENG M，LI J D，SHI Y.Routing protocol with QoS guarantees for adhoc network［J］.Electronics Letters，2003，9(1):143-145.

［4］JULIAN D，CHIANG M.QoS and fairness constrained convex optimization of resource allocation for wireless cellular and Ad Hoc networks［C］//Proc.21st Almual Joint Conf.IEEE Computer and Communications Societies.［S.l.］:IEEE Press，2002:477-486.

［5］WU K，HARMS J.Multipath routing for mobile ad hoc networks［J］.Journal Of Communications And Networks，2002，4(1):48-58.

［6］RFC3561，Ad Hoc on-demand distance vector(AODV)routing［S］.2003.

［7］魏明磊，王浩，李云，等.基于DSR路由协议的无线Ad hoc网络实验［J］.重庆邮电大学学报:自然科学版，2005，17(6):714-717.

［8］MARINA M K，DAS S R.Ad Hoc on-demand multipath distance vector routing［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2002，6(3):92-93.