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

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

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

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

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

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

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

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