無(wú)線自組網(wǎng)[1]是一種自組織,、自愈合的網(wǎng)絡(luò),，能夠不依賴現(xiàn)有的網(wǎng)絡(luò)設(shè)施，通過(guò)系統(tǒng)中的無(wú)線移動(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)上的分布式控制和無(wú)中心特點(diǎn)使得網(wǎng)絡(luò)整體具有較好的魯棒性和抗毀性,，非常適合復(fù)雜多變戰(zhàn)場(chǎng)環(huán)境，對(duì)于數(shù)字化戰(zhàn)場(chǎng)通信的建設(shè)具有重要的作用,。

    隨著信息技術(shù)的發(fā)展,，Ad Hoc網(wǎng)絡(luò)需要支持越來(lái)越多不同類型的應(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問(wèn)題，需要采用啟發(fā)式算法來(lái)求解,。但啟發(fā)式算法的局限性[4]在于尋路時(shí)間長(zhǎng),，不利于傳輸對(duì)時(shí)延約束要求嚴(yán)格的業(yè)務(wù)。因此針對(duì)時(shí)延約束要求高的業(yè)務(wù)傳輸,，需要尋找更加快捷的算法和路由協(xié)議,。
    網(wǎng)絡(luò)中某些要求判據(jù)或測(cè)度的最大化或最小化的問(wèn)題可以用分治法[5]來(lái)解決,，但其線性時(shí)間復(fù)雜度卻對(duì)網(wǎng)絡(luò)整體性能的影響很大。而采用動(dòng)態(tài)規(guī)劃的方法來(lái)解決這個(gè)問(wèn)題,，盡管動(dòng)態(tài)規(guī)劃比分治法復(fù)雜,，但其線性時(shí)間復(fù)雜度卻更容易接受，特別是在對(duì)于時(shí)延要求嚴(yán)格的網(wǎng)絡(luò)之中,，能夠節(jié)約節(jié)點(diǎn)的計(jì)算時(shí)間和資源,。動(dòng)態(tài)規(guī)劃法相對(duì)于分治法還可以避免大量子問(wèn)題的重復(fù)計(jì)算。因而,，可用于優(yōu)化Ad Hoc中最優(yōu)路由算法的設(shè)計(jì),。
    針對(duì)上述兩個(gè)問(wèn)題，本文在分析Ad Hoc網(wǎng)路及其QoS模型的基礎(chǔ)上,，對(duì)現(xiàn)有的DSR路由協(xié)議進(jìn)行改進(jìn),，考慮帶寬和時(shí)延的約束，提出了一種基于動(dòng)態(tài)規(guī)劃的多約束QoS路由協(xié)議,，從相關(guān)的分組結(jié)構(gòu)和流程兩個(gè)方面進(jìn)行了描述,，并對(duì)其進(jìn)行了仿真。

1.2 基于動(dòng)態(tài)規(guī)劃的最小時(shí)延路由優(yōu)化算法
    動(dòng)態(tài)規(guī)劃法[7]是利用貝爾曼最優(yōu)性原理求解多級(jí)決策過(guò)程最優(yōu)化的一種非線性規(guī)劃方法,。多級(jí)決策過(guò)程,，是指把一個(gè)決策過(guò)程分成若干階段，每一階段都做出決策,，以使整個(gè)過(guò)程取得最優(yōu)效果,。
    可以把Ad Hoc網(wǎng)絡(luò)中尋找時(shí)延最小路由的問(wèn)題轉(zhuǎn)化為一個(gè)多階段決策問(wèn)題，利用動(dòng)態(tài)規(guī)劃的思想轉(zhuǎn)化為一系列的單階段問(wè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í)決策過(guò)程的最優(yōu)策略還具有這樣的性質(zhì)：不論初始狀態(tài)和初始決策如何,，當(dāng)把其中任何一級(jí)和狀態(tài)再作為初始級(jí)和初始狀態(tài)時(shí)，其余的決策對(duì)此必定也是一個(gè)最優(yōu)策略,，即對(duì)于一個(gè)滿足某些約束條件的最優(yōu)策略的子策略,，對(duì)于它的初態(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ù)來(lái)保證QoS,尋求一個(gè)相對(duì)簡(jiǎn)化的QoS策略。簡(jiǎn)化的QoS策略為：首先以帶寬為約束,，在路由請(qǐng)求的過(guò)程中尋找滿足帶寬的多條可用路徑,，繼而在目的節(jié)點(diǎn)收到路由請(qǐng)求之后基于動(dòng)態(tài)規(guī)劃選擇可用路徑中時(shí)延最小的路徑，從該路徑返回至源節(jié)點(diǎn),，通過(guò)這條最優(yōu)的路徑傳輸數(shù)據(jù),。
2.1 相關(guān)分組結(jié)構(gòu)
    在DSR路由協(xié)議的基礎(chǔ)上修改得到DPMCQR其中主要的修改是： (1)本地資源表能夠保存本地的帶寬資源信息； (2)在路由緩存表中添加了帶寬和時(shí)延參數(shù),。路由建立和路由維護(hù)過(guò)程中的相關(guān)分組結(jié)構(gòu)修改如圖2所示,。

    圖中，路由請(qǐng)求分組結(jié)構(gòu)中按照請(qǐng)求分組傳遞路徑逐步添加中間轉(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è)過(guò)程,。建立路由可以分為4步：
    (1)當(dāng)源節(jié)點(diǎn)S有數(shù)據(jù)要發(fā)送時(shí),，首先檢查自己的路由緩存表是否有滿足帶寬和時(shí)延要求的到達(dá)目的節(jié)點(diǎn)的可行路徑。如果有,，則沿著該路徑發(fā)送數(shù)據(jù)分組,。否則，廣播路由請(qǐng)求分組RREQ,，并在RREQ中添加數(shù)據(jù)的帶寬和時(shí)延需求,。
    (2)中間節(jié)點(diǎn)收到RREQ后，讀取分組ID,，如果之前收到過(guò)相同ID的分組,，丟棄之;如果沒(méi)有收到過(guò)，則將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)化問(wèn)題,，得到時(shí)延最優(yōu)和次優(yōu)路由(作為備份路由),將該路由時(shí)延與RPEQ中數(shù)據(jù)的時(shí)延進(jìn)行對(duì)比,。若不滿足時(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需求，通過(guò)該路由發(fā)送數(shù)據(jù),。當(dāng)源節(jié)點(diǎn)收到路由錯(cuò)誤分組時(shí),，表明沒(méi)有滿足QoS需求的路由，則啟動(dòng)一個(gè)新的路由發(fā)現(xiàn)過(guò)程,。
    路由維護(hù)則與DSR相似,，當(dāng)中間節(jié)點(diǎn)檢測(cè)到錯(cuò)誤后，則按照路由反向返回一個(gè)路由錯(cuò)誤分組,，源節(jié)點(diǎn)在路由緩存中刪除相應(yīng)路由,，同時(shí)選擇備份路由作為可行路徑。如果不存在其他的可行路徑,，則源節(jié)點(diǎn)重新啟動(dòng)一個(gè)新的路由發(fā)現(xiàn)過(guò)程,。
3 仿真與分析
    運(yùn)用OPNET對(duì)提出的DPMCQR路由協(xié)議的性能進(jìn)行仿真，同時(shí)與DSR路由協(xié)議的性能進(jìn)行對(duì)比,。仿真參數(shù)設(shè)置如表1所示,。

　主要考查不同節(jié)點(diǎn)數(shù)目下兩者在平均端到端時(shí)延、路由開(kāi)銷和分組投遞率三個(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é)議的路由開(kāi)銷隨節(jié)點(diǎn)數(shù)目的變化情況,。圖中可以看出，DPMCQR的路由開(kāi)銷要小于DSR的,。這是因?yàn)榍罢卟坏峁㏎oS保證，而且目的節(jié)點(diǎn)針對(duì)每條路由請(qǐng)求只返回1條或2條路由回復(fù),，都能夠降低路由開(kāi)銷,。
    圖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路由問(wèn)題,，將DSR路由協(xié)議進(jìn)行了改進(jìn)，提出了一種基于動(dòng)態(tài)規(guī)劃的多約束QoS路由協(xié)議,。針對(duì)帶寬和時(shí)延兩種約束,，簡(jiǎn)化了路由策略，分步驟尋求滿足QoS保證的路由,，并利用動(dòng)態(tài)規(guī)劃方法尋求最優(yōu)時(shí)延路由,。最后對(duì)改進(jìn)的路由協(xié)議進(jìn)行仿真，與DSR路由協(xié)議進(jìn)行對(duì)比,。結(jié)果表明相對(duì)于DSR,，DPMCQR在平均端到端時(shí)延、路由開(kāi)銷和分組投遞率三方面對(duì)網(wǎng)絡(luò)的性能,，特別是在大規(guī)模自組網(wǎng)的性能,，都有很大提升。但本文在節(jié)點(diǎn)移動(dòng)速度較低的情況下沒(méi)有考慮鏈路的穩(wěn)定性,，因此下一步的工作方向?qū)?huì)結(jié)合節(jié)點(diǎn)高速移動(dòng)時(shí)的鏈路穩(wěn)定性來(lái)設(shè)計(jì)QoS路由協(xié)議,。
參考文獻(xiàn)
[1] 鄭相全.無(wú)線自組網(wǎng)技術(shù)實(shí)用教程[M].北京：清華大學(xué)出版社，2004.
[2] 李云,，趙為糧,，隆克平，等.無(wú)線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]. 國(guó)防科技大學(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ī)劃的間斷連接無(wú)線互聯(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．