劉曉鵬,陳西宏,劉少偉

（空軍工程大學(xué) 防空反導(dǎo)學(xué)院，陜西 西安 710051）

無線自組網(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 Ad Hoc網(wǎng)絡(luò)QoS路由問題的動(dòng)態(tài)規(guī)劃模型

1.1 Ad Hoc網(wǎng)絡(luò)及QoS模型

可以用一個(gè)加權(quán)無向圖G(V,E)[6]來表示Ad Hoc網(wǎng)絡(luò)。圖的頂點(diǎn)表示網(wǎng)絡(luò)的移動(dòng)節(jié)點(diǎn)，圖的邊表示兩節(jié)點(diǎn)間的無線鏈路。V={ni}為網(wǎng)絡(luò)節(jié)點(diǎn)的集合；E={Im,n(m,n);m,n∈V}為無線鏈路的集合。網(wǎng)絡(luò)中兩點(diǎn)ns、nd之間的路徑由一組邊{ls,1,l1,2,l2,3,…,ln,d}連接而成。這組邊的集合組成兩個(gè)節(jié)點(diǎn)間的一條路由r:rs,d={ls,1,l1,2,l2,3,…,ln,d}。 這條路由還可用節(jié)點(diǎn)的集合表示：rs,d={nj,j=s,u,v,…,d}。任意兩個(gè)節(jié)點(diǎn)u、v間可以有多條路由,所有路由 r所組成的集合為路由集Ru,v合。

記節(jié)點(diǎn) ni的帶寬為 Bi，時(shí)延為 Ti，則路由 rs,d={nj,j=s,u,v,…,d}上的帶寬 B(s,d)，時(shí)延 T(s,d)的定義如下：

(1)路由rs,d的帶寬 B(s,d)為路由中各節(jié)點(diǎn)的最小帶寬值，單位為bit/s。

(2)路由rs,d上的時(shí)延T(s,d)為路由中各節(jié)點(diǎn)累計(jì)時(shí)延，單位為 s。

還可以表示為：

其中，Tt為數(shù)據(jù)的傳輸時(shí)延，Tp為節(jié)點(diǎn)的處理時(shí)延,Tprop為信號(hào)在無線信道中的傳播時(shí)延。

本設(shè)計(jì)中，考慮使網(wǎng)絡(luò)滿足以下QoS性能的路由：帶寬B和時(shí)延T。即尋找源節(jié)點(diǎn)s與目標(biāo)節(jié)點(diǎn)d之間的路由集合Rs,d，使其滿足以下兩個(gè)條件之一：

① 找到一條路由rs,d∈Rs,d滿足：

② 找到 n條路由Rs,d′∈Rs,d滿足：

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所示。

將整個(gè)過程劃分為N個(gè)階段，階段變量用k表示。用sk表示第k階段的狀態(tài)變量，表示一個(gè)可選節(jié)點(diǎn)。用uk(sk)來表示第k階段當(dāng)狀態(tài)處于sk狀態(tài)的決策變量，表示節(jié)點(diǎn)的可選用路徑。

時(shí)延最小路由求解問題可以描述為：

對于一個(gè)N級(jí)決策過程，其狀態(tài)方程為：

求決策序列u*(k)使式(7)所示的時(shí)延指標(biāo)函數(shù)最?。?/p>

上述問題的遞歸關(guān)系可以表示成：

由上式可以求得最優(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所示。

圖3 目的節(jié)點(diǎn)處理RREQ流程

(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所示。

表1 仿真參數(shù)

主要考查不同節(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é)議。

[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．