无线自组网[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.2 基于动态规划的最小时延路由优化算法
    动态规划法[7]是利用贝尔曼最优性原理求解多级决策过程最优化的一种非线性规划方法。多级决策过程，是指把一个决策过程分成若干阶段，每一阶段都做出决策，以使整个过程取得最优效果。
    可以把Ad Hoc网络中寻找时延最小路由的问题转化为一个多阶段决策问题，利用动态规划的思想转化为一系列的单阶段问题，求解最优策略。将实际网络模型转化为动态规划的标准模型[8]之后，建立如下动态规划路由模型，如图1所示。

    由上式可以求得最优策略以及指标函数的最小值，即时延最小的路由和该路由的时延。
    同时,多级决策过程的最优策略还具有这样的性质：不论初始状态和初始决策如何，当把其中任何一级和状态再作为初始级和初始状态时，其余的决策对此必定也是一个最优策略，即对于一个满足某些约束条件的最优策略的子策略，对于它的初态和终态而言也一定是最优的。因此，当满足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所示。

   (4)当源节点收到RREP分组后，表明已经找到一条路径满足数据的QoS需求，通过该路由发送数据。当源节点收到路由错误分组时，表明没有满足QoS需求的路由，则启动一个新的路由发现过程。
    路由维护则与DSR相似，当中间节点检测到错误后，则按照路由反向返回一个路由错误分组，源节点在路由缓存中删除相应路由，同时选择备份路由作为可行路径。如果不存在其他的可行路径，则源节点重新启动一个新的路由发现过程。
3 仿真与分析
    运用OPNET对提出的DPMCQR路由协议的性能进行仿真，同时与DSR路由协议的性能进行对比。仿真参数设置如表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．