Ad Hoc中基于动态规划的多约束QoS路由协议

刘晓鹏,陈西宏,刘少伟

（空军工程大学 防空反导学院，陕西 西安 710051）

无线自组网[1]是一种自组织、自愈合的网络，能够不依赖现有的网络设施，通过系统中的无线移动通信节点的分布式协议算法互联或组织成一个整体的网络系统。网络中移动节点可以根据需要动态地组织成任意临时性的网络拓扑，各节点不但具有终端的功能，而且还具有路由的功能。这种结构上的分布式控制和无中心特点使得网络整体具有较好的鲁棒性和抗毁性，非常适合复杂多变战场环境，对于数字化战场通信的建设具有重要的作用。

随着信息技术的发展，Ad Hoc网络需要支持越来越多不同类型的应用，包括实现多媒体数据的传输、实时信息的获取等。因此，与Internet一样，Ad Hoc网络同样也需要QoS控制的支持，而基于QoS的路由技术是保证在Ad Hoc中支持这些应用的关键。Ad Hoc网络的QoS路由[2]是为了能够合理有效利用网络资源，选择满足一定QoS约束(如带宽、时延等)的信息传输路径。参考文献[3]指出,当QoS约束条件包含两个或两个以上的可加性参数，或者包括可加性参数和/或可乘性参数组合时，路由选择则变成为一个NPC问题，需要采用启发式算法来求解。但启发式算法的局限性[4]在于寻路时间长，不利于传输对时延约束要求严格的业务。因此针对时延约束要求高的业务传输，需要寻找更加快捷的算法和路由协议。

网络中某些要求判据或测度的最大化或最小化的问题可以用分治法[5]来解决，但其线性时间复杂度却对网络整体性能的影响很大。而采用动态规划的方法来解决这个问题，尽管动态规划比分治法复杂，但其线性时间复杂度却更容易接受，特别是在对于时延要求严格的网络之中，能够节约节点的计算时间和资源。动态规划法相对于分治法还可以避免大量子问题的重复计算。因而，可用于优化Ad Hoc中最优路由算法的设计。

针对上述两个问题，本文在分析Ad Hoc网路及其QoS模型的基础上，对现有的DSR路由协议进行改进，考虑带宽和时延的约束，提出了一种基于动态规划的多约束QoS路由协议，从相关的分组结构和流程两个方面进行了描述，并对其进行了仿真。

1 Ad Hoc网络QoS路由问题的动态规划模型

1.1 Ad Hoc网络及QoS模型

可以用一个加权无向图G(V,E)[6]来表示Ad Hoc网络。图的顶点表示网络的移动节点，图的边表示两节点间的无线链路。V={ni}为网络节点的集合；E={Im,n(m,n);m,n∈V}为无线链路的集合。网络中两点ns、nd之间的路径由一组边{ls,1,l1,2,l2,3,…,ln,d}连接而成。这组边的集合组成两个节点间的一条路由r:rs,d={ls,1,l1,2,l2,3,…,ln,d}。 这条路由还可用节点的集合表示：rs,d={nj,j=s,u,v,…,d}。任意两个节点u、v间可以有多条路由,所有路由 r所组成的集合为路由集Ru,v合。

记节点 ni的带宽为 Bi，时延为 Ti，则路由 rs,d={nj,j=s,u,v,…,d}上的带宽 B(s,d)，时延 T(s,d)的定义如下：

(1)路由rs,d的带宽 B(s,d)为路由中各节点的最小带宽值，单位为bit/s。

(2)路由rs,d上的时延T(s,d)为路由中各节点累计时延，单位为 s。

还可以表示为：

其中，Tt为数据的传输时延，Tp为节点的处理时延,Tprop为信号在无线信道中的传播时延。

本设计中，考虑使网络满足以下QoS性能的路由：带宽B和时延T。即寻找源节点s与目标节点d之间的路由集合Rs,d，使其满足以下两个条件之一：

① 找到一条路由rs,d∈Rs,d满足：

② 找到 n条路由Rs,d′∈Rs,d满足：

1.2 基于动态规划的最小时延路由优化算法

动态规划法[7]是利用贝尔曼最优性原理求解多级决策过程最优化的一种非线性规划方法。多级决策过程，是指把一个决策过程分成若干阶段，每一阶段都做出决策，以使整个过程取得最优效果。

可以把Ad Hoc网络中寻找时延最小路由的问题转化为一个多阶段决策问题，利用动态规划的思想转化为一系列的单阶段问题，求解最优策略。将实际网络模型转化为动态规划的标准模型[8]之后，建立如下动态规划路由模型，如图1所示。

将整个过程划分为N个阶段，阶段变量用k表示。用sk表示第k阶段的状态变量，表示一个可选节点。用uk(sk)来表示第k阶段当状态处于sk状态的决策变量，表示节点的可选用路径。

时延最小路由求解问题可以描述为：

对于一个N级决策过程，其状态方程为：

求决策序列u*(k)使式(7)所示的时延指标函数最小：

上述问题的递归关系可以表示成：

由上式可以求得最优策略以及指标函数的最小值，即时延最小的路由和该路由的时延。

同时,多级决策过程的最优策略还具有这样的性质：不论初始状态和初始决策如何，当把其中任何一级和状态再作为初始级和初始状态时，其余的决策对此必定也是一个最优策略，即对于一个满足某些约束条件的最优策略的子策略，对于它的初态和终态而言也一定是最优的。因此，当满足QoS约束的最优路由选定之后，其子路由也必定是最优的，这样就能够避免大量重复路由的计算。同时，动态规划的算法时间复杂度和计算量较少，大大节约了节点的资源。

2 路由协议描述

在动态源路由DSR的基础上构建基于动态规划的多约束QoS路由协议DPMCQR(Dynamic Programming based Multi-Constraints QoS Routing)，选择带宽以及时延这两个参数来保证QoS,寻求一个相对简化的QoS策略。简化的QoS策略为：首先以带宽为约束，在路由请求的过程中寻找满足带宽的多条可用路径，继而在目的节点收到路由请求之后基于动态规划选择可用路径中时延最小的路径，从该路径返回至源节点，通过这条最优的路径传输数据。

2.1 相关分组结构

在DSR路由协议的基础上修改得到DPMCQR其中主要的修改是：(1)本地资源表能够保存本地的带宽资源信息；(2)在路由缓存表中添加了带宽和时延参数。路由建立和路由维护过程中的相关分组结构修改如图2所示。

图中，路由请求分组结构中按照请求分组传递路径逐步添加中间转发节点的ID以及于上一级节点之间的时延。路由回复分组中则将目的节点利用动态规划法计算的最小时延添加到分组中，并沿着选定的最优路径返回到源节点。

2.2 流程描述

路由流程分为路由建立和路由维护两个过程。建立路由可以分为4步：

(1)当源节点S有数据要发送时，首先检查自己的路由缓存表是否有满足带宽和时延要求的到达目的节点的可行路径。如果有，则沿着该路径发送数据分组。否则，广播路由请求分组RREQ，并在RREQ中添加数据的带宽和时延需求。

(2)中间节点收到 RREQ后，读取分组 ID，如果之前收到过相同ID的分组，丢弃之;如果没有收到过，则将RREQ分组中的数据带宽要求与本地资源信息表中的可用带宽[9-10]相比较。不满足带宽要求，丢弃；否则，根据时间戳计算与上一节点的时延，与节点的ID同时添加到RREQ中，并转发。

(3)当目的节点D收到第一个RREQ后，启动一个计时器，在时间范围内，将收到的RREQ全部保存到路由缓存中。计时结束后，从路由缓存中取出路由信息，按1.2节的方法解决时延最优化问题，得到时延最优和次优路由 (作为备份路由),将该路由时延与RPEQ中数据的时延进行对比。若不满足时延要求，则返回路由错误分组；否则按照最优和次优顺序回复RREP，同时相应路径上的中间节点将该路径添加到路由缓存表中。处理流程如图3所示。

图3 目的节点处理RREQ流程

(4)当源节点收到RREP分组后，表明已经找到一条路径满足数据的QoS需求，通过该路由发送数据。当源节点收到路由错误分组时，表明没有满足QoS需求的路由，则启动一个新的路由发现过程。

路由维护则与DSR相似，当中间节点检测到错误后，则按照路由反向返回一个路由错误分组，源节点在路由缓存中删除相应路由，同时选择备份路由作为可行路径。如果不存在其他的可行路径，则源节点重新启动一个新的路由发现过程。

3 仿真与分析

运用OPNET对提出的DPMCQR路由协议的性能进行仿真，同时与DSR路由协议的性能进行对比。仿真参数设置如表1所示。

表1 仿真参数

主要考查不同节点数目下两者在平均端到端时延、路由开销和分组投递率三个方面的性能。 仿真结果如图4～图6所示。

图4表明了两种协议的平均端到端时延随节点数目的变化情况。从图中可以看出，两种协议的平均时延首先随着节点数目的增加而增加，当到达一定规模时下降。这是因为节点数目较少时，可用路径较少，节点转发时引入较多时延。但随着节点数目的增多，可用的路径也随之增多，降低了平均端到端时延。同时，还可以看到当节点达到一定规模时，DPMCQR协议表现出更好的时延性能，这是由于DPMCQR选取的是时延最优的路由，而DSR选取的不一定是时延最优的。

图5反映了两种协议的路由开销随节点数目的变化情况。图中可以看出，DPMCQR的路由开销要小于DSR的。这是因为前者不但提供QoS保证，而且目的节点针对每条路由请求只返回1条或2条路由回复，都能够降低路由开销。

图6中可以看出，二者的分组投递率都会随着节点数目的增多而增加，是由于节点数目的增多使得源节点到目的节点可选路由增多，增加分组投递的成功率。而DPMCQR的分组投递率要高于DSR的，这是由于协议选择满足带宽和时延约束的路由，能够保证数据的有效传输，提高分组投递率。

本文为解决Ad Hoc网络中多约束QoS路由问题，将DSR路由协议进行了改进，提出了一种基于动态规划的多约束QoS路由协议。针对带宽和时延两种约束，简化了路由策略，分步骤寻求满足QoS保证的路由，并利用动态规划方法寻求最优时延路由。最后对改进的路由协议进行仿真，与DSR路由协议进行对比。结果表明相对于DSR，DPMCQR在平均端到端时延、路由开销和分组投递率三方面对网络的性能，特别是在大规模自组网的性能，都有很大提升。但本文在节点移动速度较低的情况下没有考虑链路的稳定性，因此下一步的工作方向将会结合节点高速移动时的链路稳定性来设计QoS路由协议。

[1]郑相全.无线自组网技术实用教程[M].北京：清华大学出版社，2004.

[2]李云，赵为粮，隆克平，等.无线 Ad Hoc网络支持QoS的研究进展与展望[J].软件学报,2004,15(12):1885-1893.

[3]WANG Z,CROWCROF J.Quality of service routing for supporting multimedia applications[J]．IEEE Journal on Selected Areas in Communications,1996,14(7)：1228-1234．

[4]杜青松，朱江，张尔扬.战术 MANET中基于多态转移策略的蚁群优化QoS路由算法[J].国防科技大学学报,2012,34(2):107-114.

[5]CORMEN T H,LEISERSON C E,RIVEST R L,et al.Introduction to Algorithms,2nd Ed[M].the MIT Press,2002.

[6]沈晖，石冰心，邹玲，等.一个自组网中基于局部状态位置已知的分布式QoS路由算法[J].通信学报,2004,25(10):58-66.

[7]胡寿松,王执铨,胡维礼.最优控制理论与系统[M].北京：科学出版社，2005.

[8]李云，尤肖虎，赵晓娜，等.一种基于动态规划的间断连接无线互联网络选路算法[J].电子学报,2010,38(10):2342-2349.

[9]ZHU C,Corson MS．QoS routing for mobile ad hoc networks[C]．In：Proc．of the 21st Intil Annual Joint Con.of the IEEE Computer and Communications Societies．2002，01(2):958-967．

[10]LIN C R，LIU J S．Qos routing in ad hoc wireless networks[J]．IEEE Joumal selected Areas in communications，1999，17(8)：1426-1438．