無線自組網[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．