無線自組網(wǎng)[1]是一種自組織、自愈合的網(wǎng)絡，能夠不依賴現(xiàn)有的網(wǎng)絡設施，通過系統(tǒng)中的無線移動通信節(jié)點的分布式協(xié)議算法互聯(lián)或組織成一個整體的網(wǎng)絡系統(tǒng)。網(wǎng)絡中移動節(jié)點可以根據(jù)需要動態(tài)地組織成任意臨時性的網(wǎng)絡拓撲，各節(jié)點不但具有終端的功能，而且還具有路由的功能。這種結(jié)構(gòu)上的分布式控制和無中心特點使得網(wǎng)絡整體具有較好的魯棒性和抗毀性，非常適合復雜多變戰(zhàn)場環(huán)境，對于數(shù)字化戰(zhàn)場通信的建設具有重要的作用。

    隨著信息技術(shù)的發(fā)展，Ad Hoc網(wǎng)絡需要支持越來越多不同類型的應用，包括實現(xiàn)多媒體數(shù)據(jù)的傳輸、實時信息的獲取等。因此，與Internet一樣，Ad Hoc網(wǎng)絡同樣也需要QoS控制的支持，而基于QoS的路由技術(shù)是保證在Ad Hoc中支持這些應用的關鍵。Ad Hoc網(wǎng)絡的QoS路由[2]是為了能夠合理有效利用網(wǎng)絡資源，選擇滿足一定QoS約束(如帶寬、時延等)的信息傳輸路徑。參考文獻[3]指出,當QoS約束條件包含兩個或兩個以上的可加性參數(shù)，或者包括可加性參數(shù)和/或可乘性參數(shù)組合時，路由選擇則變成為一個NPC問題，需要采用啟發(fā)式算法來求解。但啟發(fā)式算法的局限性[4]在于尋路時間長，不利于傳輸對時延約束要求嚴格的業(yè)務。因此針對時延約束要求高的業(yè)務傳輸，需要尋找更加快捷的算法和路由協(xié)議。
    網(wǎng)絡中某些要求判據(jù)或測度的最大化或最小化的問題可以用分治法[5]來解決，但其線性時間復雜度卻對網(wǎng)絡整體性能的影響很大。而采用動態(tài)規(guī)劃的方法來解決這個問題，盡管動態(tài)規(guī)劃比分治法復雜，但其線性時間復雜度卻更容易接受，特別是在對于時延要求嚴格的網(wǎng)絡之中，能夠節(jié)約節(jié)點的計算時間和資源。動態(tài)規(guī)劃法相對于分治法還可以避免大量子問題的重復計算。因而，可用于優(yōu)化Ad Hoc中最優(yōu)路由算法的設計。
    針對上述兩個問題，本文在分析Ad Hoc網(wǎng)路及其QoS模型的基礎上，對現(xiàn)有的DSR路由協(xié)議進行改進，考慮帶寬和時延的約束，提出了一種基于動態(tài)規(guī)劃的多約束QoS路由協(xié)議，從相關的分組結(jié)構(gòu)和流程兩個方面進行了描述，并對其進行了仿真。

1.2 基于動態(tài)規(guī)劃的最小時延路由優(yōu)化算法
    動態(tài)規(guī)劃法[7]是利用貝爾曼最優(yōu)性原理求解多級決策過程最優(yōu)化的一種非線性規(guī)劃方法。多級決策過程，是指把一個決策過程分成若干階段，每一階段都做出決策，以使整個過程取得最優(yōu)效果。
    可以把Ad Hoc網(wǎng)絡中尋找時延最小路由的問題轉(zhuǎn)化為一個多階段決策問題，利用動態(tài)規(guī)劃的思想轉(zhuǎn)化為一系列的單階段問題，求解最優(yōu)策略。將實際網(wǎng)絡模型轉(zhuǎn)化為動態(tài)規(guī)劃的標準模型[8]之后，建立如下動態(tài)規(guī)劃路由模型，如圖1所示。

    由上式可以求得最優(yōu)策略以及指標函數(shù)的最小值，即時延最小的路由和該路由的時延。
    同時,多級決策過程的最優(yōu)策略還具有這樣的性質(zhì)：不論初始狀態(tài)和初始決策如何，當把其中任何一級和狀態(tài)再作為初始級和初始狀態(tài)時，其余的決策對此必定也是一個最優(yōu)策略，即對于一個滿足某些約束條件的最優(yōu)策略的子策略，對于它的初態(tài)和終態(tài)而言也一定是最優(yōu)的。因此，當滿足QoS約束的最優(yōu)路由選定之后，其子路由也必定是最優(yōu)的，這樣就能夠避免大量重復路由的計算。同時，動態(tài)規(guī)劃的算法時間復雜度和計算量較少，大大節(jié)約了節(jié)點的資源。
2 路由協(xié)議描述
    在動態(tài)源路由DSR的基礎上構(gòu)建基于動態(tài)規(guī)劃的多約束QoS路由協(xié)議DPMCQR(Dynamic Programming based Multi-Constraints QoS Routing)，選擇帶寬以及時延這兩個參數(shù)來保證QoS,尋求一個相對簡化的QoS策略。簡化的QoS策略為：首先以帶寬為約束，在路由請求的過程中尋找滿足帶寬的多條可用路徑，繼而在目的節(jié)點收到路由請求之后基于動態(tài)規(guī)劃選擇可用路徑中時延最小的路徑，從該路徑返回至源節(jié)點，通過這條最優(yōu)的路徑傳輸數(shù)據(jù)。
2.1 相關分組結(jié)構(gòu)
    在DSR路由協(xié)議的基礎上修改得到DPMCQR其中主要的修改是： (1)本地資源表能夠保存本地的帶寬資源信息； (2)在路由緩存表中添加了帶寬和時延參數(shù)。路由建立和路由維護過程中的相關分組結(jié)構(gòu)修改如圖2所示。

    圖中，路由請求分組結(jié)構(gòu)中按照請求分組傳遞路徑逐步添加中間轉(zhuǎn)發(fā)節(jié)點的ID以及于上一級節(jié)點之間的時延。路由回復分組中則將目的節(jié)點利用動態(tài)規(guī)劃法計算的最小時延添加到分組中，并沿著選定的最優(yōu)路徑返回到源節(jié)點。
2.2 流程描述
    路由流程分為路由建立和路由維護兩個過程。建立路由可以分為4步：
    (1)當源節(jié)點S有數(shù)據(jù)要發(fā)送時，首先檢查自己的路由緩存表是否有滿足帶寬和時延要求的到達目的節(jié)點的可行路徑。如果有，則沿著該路徑發(fā)送數(shù)據(jù)分組。否則，廣播路由請求分組RREQ，并在RREQ中添加數(shù)據(jù)的帶寬和時延需求。
    (2)中間節(jié)點收到RREQ后，讀取分組ID，如果之前收到過相同ID的分組，丟棄之;如果沒有收到過，則將RREQ分組中的數(shù)據(jù)帶寬要求與本地資源信息表中的可用帶寬[9-10]相比較。不滿足帶寬要求，丟棄；否則，根據(jù)時間戳計算與上一節(jié)點的時延，與節(jié)點的ID同時添加到RREQ中，并轉(zhuǎn)發(fā)。
　(3)當目的節(jié)點D收到第一個RREQ后，啟動一個計時器，在時間范圍內(nèi)，將收到的RREQ全部保存到路由緩存中。計時結(jié)束后，從路由緩存中取出路由信息，按1.2節(jié)的方法解決時延最優(yōu)化問題，得到時延最優(yōu)和次優(yōu)路由(作為備份路由),將該路由時延與RPEQ中數(shù)據(jù)的時延進行對比。若不滿足時延要求，則返回路由錯誤分組；否則按照最優(yōu)和次優(yōu)順序回復RREP，同時相應路徑上的中間節(jié)點將該路徑添加到路由緩存表中。處理流程如圖3所示。

   (4)當源節(jié)點收到RREP分組后，表明已經(jīng)找到一條路徑滿足數(shù)據(jù)的QoS需求，通過該路由發(fā)送數(shù)據(jù)。當源節(jié)點收到路由錯誤分組時，表明沒有滿足QoS需求的路由，則啟動一個新的路由發(fā)現(xiàn)過程。
    路由維護則與DSR相似，當中間節(jié)點檢測到錯誤后，則按照路由反向返回一個路由錯誤分組，源節(jié)點在路由緩存中刪除相應路由，同時選擇備份路由作為可行路徑。如果不存在其他的可行路徑，則源節(jié)點重新啟動一個新的路由發(fā)現(xiàn)過程。
3 仿真與分析
    運用OPNET對提出的DPMCQR路由協(xié)議的性能進行仿真，同時與DSR路由協(xié)議的性能進行對比。仿真參數(shù)設置如表1所示。

　主要考查不同節(jié)點數(shù)目下兩者在平均端到端時延、路由開銷和分組投遞率三個方面的性能。 仿真結(jié)果如圖4~圖6所示。

    圖4表明了兩種協(xié)議的平均端到端時延隨節(jié)點數(shù)目的變化情況。從圖中可以看出，兩種協(xié)議的平均時延首先隨著節(jié)點數(shù)目的增加而增加，當?shù)竭_一定規(guī)模時下降。這是因為節(jié)點數(shù)目較少時，可用路徑較少，節(jié)點轉(zhuǎn)發(fā)時引入較多時延。但隨著節(jié)點數(shù)目的增多，可用的路徑也隨之增多，降低了平均端到端時延。同時，還可以看到當節(jié)點達到一定規(guī)模時，DPMCQR協(xié)議表現(xiàn)出更好的時延性能，這是由于DPMCQR選取的是時延最優(yōu)的路由，而DSR選取的不一定是時延最優(yōu)的。
    圖5反映了兩種協(xié)議的路由開銷隨節(jié)點數(shù)目的變化情況。圖中可以看出，DPMCQR的路由開銷要小于DSR的。這是因為前者不但提供QoS保證，而且目的節(jié)點針對每條路由請求只返回1條或2條路由回復，都能夠降低路由開銷。
    圖6中可以看出，二者的分組投遞率都會隨著節(jié)點數(shù)目的增多而增加，是由于節(jié)點數(shù)目的增多使得源節(jié)點到目的節(jié)點可選路由增多，增加分組投遞的成功率。而DPMCQR的分組投遞率要高于DSR的，這是由于協(xié)議選擇滿足帶寬和時延約束的路由，能夠保證數(shù)據(jù)的有效傳輸，提高分組投遞率。
    本文為解決Ad Hoc網(wǎng)絡中多約束QoS路由問題，將DSR路由協(xié)議進行了改進，提出了一種基于動態(tài)規(guī)劃的多約束QoS路由協(xié)議。針對帶寬和時延兩種約束，簡化了路由策略，分步驟尋求滿足QoS保證的路由，并利用動態(tài)規(guī)劃方法尋求最優(yōu)時延路由。最后對改進的路由協(xié)議進行仿真，與DSR路由協(xié)議進行對比。結(jié)果表明相對于DSR，DPMCQR在平均端到端時延、路由開銷和分組投遞率三方面對網(wǎng)絡的性能，特別是在大規(guī)模自組網(wǎng)的性能，都有很大提升。但本文在節(jié)點移動速度較低的情況下沒有考慮鏈路的穩(wěn)定性，因此下一步的工作方向?qū)Y(jié)合節(jié)點高速移動時的鏈路穩(wěn)定性來設計QoS路由協(xié)議。
參考文獻
[1] 鄭相全.無線自組網(wǎng)技術(shù)實用教程[M].北京：清華大學出版社，2004.
[2] 李云，趙為糧，隆克平，等.無線Ad Hoc網(wǎng)絡支持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] 杜青松，朱江，張爾揚.戰(zhàn)術(shù)MANET中基于多態(tài)轉(zhuǎn)移策略的蟻群優(yōu)化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] 沈暉，石冰心，鄒玲，等.一個自組網(wǎng)中基于局部狀態(tài)位置已知的分布式QoS路由算法[J]. 通信學報,2004,25(10):58-66.
[7] 胡壽松,王執(zhí)銓,胡維禮.最優(yōu)控制理論與系統(tǒng)[M].北京：科學出版社，2005.
[8] 李云，尤肖虎，趙曉娜，等.一種基于動態(tài)規(guī)劃的間斷連接無線互聯(lián)網(wǎng)絡選路算法[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．