無線自組織網(wǎng)絡(luò)中一種擁塞意識(shí)的多徑路由算法

袁永瓊

(中國電子科技集團(tuán)公司第20研究所通信事業(yè)部，陜西西安 710068)

無線組織網(wǎng)絡(luò)是一種無需固定基礎(chǔ)設(shè)施支撐的無線多跳網(wǎng)絡(luò)，具有網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化、帶寬資源受限、鏈路不可靠等特性。針對(duì)以上特性，許多路由協(xié)議被提出，以克服這些限制提高網(wǎng)絡(luò)的傳輸效率。

首先，在降低路由開銷方面，按需路由協(xié)議僅建立和維護(hù)需要的路徑，可有效降低路由的開銷和路由表的緩存空間。近年來學(xué)者們已提出許多按需路由協(xié)議［1－2］。在現(xiàn)有的無線自組織網(wǎng)絡(luò)按需路由協(xié)議中，其多采用簡單洪泛機(jī)制實(shí)現(xiàn)路由發(fā)現(xiàn)。由于無線信道的廣播特性，簡單的洪泛雖保證了發(fā)現(xiàn)路由的最大可能性，但往往轉(zhuǎn)發(fā)了較多冗余的路由控制分組。為此，學(xué)者們提出了一些改進(jìn)算法。Gossip路由［3－4］和洪泛受限的路由協(xié)議［5］有效降低了路由開銷。文獻(xiàn)［3］提出的Gossip路由無論節(jié)點(diǎn)當(dāng)前的鏈路狀態(tài)和負(fù)載如何，所有節(jié)點(diǎn)均采用同一固定轉(zhuǎn)發(fā)概率。為使Gossip機(jī)制更好地適用動(dòng)態(tài)無線網(wǎng)絡(luò)，根據(jù)節(jié)點(diǎn)網(wǎng)絡(luò)狀態(tài)來動(dòng)態(tài)確定轉(zhuǎn)發(fā)概率，可有效保證路由請求消息對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋的同時(shí)避免不必要的冗余轉(zhuǎn)發(fā)。

其次，大多數(shù)單徑路由協(xié)議通常依據(jù)某種路由度量選擇一條路徑傳輸數(shù)據(jù)。當(dāng)源和目的節(jié)點(diǎn)之間的路徑中任何鏈路中斷，則必須重新喚起路由發(fā)現(xiàn)過程，這樣將導(dǎo)致路由開銷增加和數(shù)據(jù)分組傳輸時(shí)延增加。多徑傳輸由于同時(shí)在多條路徑上傳輸，而當(dāng)其中一條路徑中斷時(shí)，其可以快速切換到其他路徑上，從而緩解上述問題。多徑路由能夠提高數(shù)據(jù)分組傳輸?shù)目煽啃?、平衡流量?fù)載和節(jié)點(diǎn)的功率消耗，減低端到端時(shí)延和路由發(fā)現(xiàn)頻率，解決頻繁的拓?fù)渥兓鴮?dǎo)致的不可靠通信服務(wù)［6－7］。近年來學(xué)者們已提出多種適用于無線多跳網(wǎng)絡(luò)的按需多徑路由協(xié)議［6－9］，有效平衡了網(wǎng)絡(luò)流量負(fù)載和降低路由開銷。上述多徑路由協(xié)議多采用最短路徑為路由度量。然而在無線自組織網(wǎng)絡(luò)，由于鏈路質(zhì)量、網(wǎng)絡(luò)中流量負(fù)載不均衡和無線沖突，最小跳數(shù)路由難以找到高吞吐量路徑?；贓TX的路由［10］已被驗(yàn)證在存在信道衰落的網(wǎng)絡(luò)環(huán)境下是一種有效提高網(wǎng)絡(luò)吞吐量的路由度量策略。但如果一條路徑鏈路質(zhì)量良好，但是路徑中的節(jié)點(diǎn)有較長的隊(duì)列，則其并不是最好的選擇。

考慮到以上問題，文中提出了一種適用于無線自組織網(wǎng)絡(luò)的多徑路由算法——擁塞意識(shí)的多徑路由算法(Congestion－aware Multipath Routing，CMR)。在路由發(fā)現(xiàn)階段，根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的隊(duì)列長度和路徑跳數(shù)來動(dòng)態(tài)確定轉(zhuǎn)發(fā)概率，轉(zhuǎn)發(fā)盡可能少的路由請求來覆蓋幾乎所有的節(jié)點(diǎn)，以有效降低路由開銷。在多路徑選擇和流量分配階段，以路徑質(zhì)量和節(jié)點(diǎn)的隊(duì)列長度作為路由度量標(biāo)準(zhǔn)選擇多條路徑，以該路由度量值為依據(jù)進(jìn)行流量分配，在使用高質(zhì)量路徑和避免擁塞熱點(diǎn)之間做一個(gè)折衷。

1 擁塞意識(shí)的多徑路由算法

CMR的核心思想主要包括兩個(gè)部分:(1)路由發(fā)現(xiàn)。根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的隊(duì)列長度和路徑跳數(shù)來動(dòng)態(tài)確定路由請求分組的動(dòng)態(tài)轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)概率。(2)路由選擇和流量分配。以路徑質(zhì)量和節(jié)點(diǎn)的隊(duì)列長度以路由度量標(biāo)準(zhǔn)進(jìn)行路徑的選擇和流量分配。

1.1 基于Gossip機(jī)制的路由發(fā)現(xiàn)

在CMR路由算法的路由發(fā)現(xiàn)過程中，收到路由請求分組(Route REQuest，RREQ)的節(jié)點(diǎn)根據(jù)其負(fù)載的隊(duì)列長度和路徑的跳數(shù)來動(dòng)態(tài)轉(zhuǎn)發(fā)概率后再?zèng)Q定是否轉(zhuǎn)發(fā)該分組。為避免路由請求消息過早消亡，通過接收到鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)量感知消息的傳播情況作為一個(gè)補(bǔ)充保障手段，即如果中間節(jié)點(diǎn)第一次收到RREQ而且沒有轉(zhuǎn)發(fā)該請求，以一個(gè)延遲轉(zhuǎn)發(fā)概率轉(zhuǎn)發(fā)該請求?；?Gossip的DSR路由發(fā)現(xiàn)機(jī)制具體如下:(1)源節(jié)點(diǎn)沒有到達(dá)目的節(jié)點(diǎn)的路徑時(shí)，向鄰居節(jié)點(diǎn)廣播路由請求RREQ。(2)中間節(jié)點(diǎn)收到該路由請求RREQ的處理流程如下:1)如果是第一次收到該路由請求RREQ且緩存中存在到達(dá)目的節(jié)點(diǎn)的路徑，給源節(jié)點(diǎn)回復(fù)一個(gè)路由應(yīng)答RREP。2)如果是第一次收到該路由請求RREQ且緩存中沒有到達(dá)目的節(jié)點(diǎn)的路徑時(shí)，記錄其前一跳節(jié)點(diǎn)為NIdSD，按式(1)計(jì)算轉(zhuǎn)發(fā)概率pforward。以概率pforward轉(zhuǎn)發(fā)該路由請求RREQ。在沒有轉(zhuǎn)發(fā)的情況下，一定時(shí)間Ttimeout延遲后，以延遲轉(zhuǎn)發(fā)概率pdelay繼續(xù)轉(zhuǎn)發(fā)該路由請求RREQ，防止其過早消亡。其中

式中，α，h為常數(shù)(0＜α ＜1，h≥1);mum_hops為路由請求表中路徑的跳數(shù);queue_size為節(jié)點(diǎn)的隊(duì)列長度;pqs(queue_size)為根據(jù)queue_size確定的概率。

式中，n為時(shí)間Ttimeout內(nèi)收到前兩跳節(jié)點(diǎn)NIdSD廣播的同一路由請求消息的數(shù)量。這里Timeout取i×Node_Traversal_time，i∈N，一般 i取 35，Node_Traversal_time是數(shù)據(jù)包平均一跳轉(zhuǎn)移時(shí)間的保守估計(jì)，包括排隊(duì)時(shí)間、處理時(shí)間、傳輸和傳播時(shí)間。3)如果該節(jié)點(diǎn)已經(jīng)收到過相同的RREQ，直接丟棄該包。(3)如果是目的節(jié)點(diǎn)收到RREQ，給源節(jié)點(diǎn)回復(fù)路由應(yīng)答。

對(duì)于式(1)，pforward由路徑跳數(shù)和節(jié)點(diǎn)負(fù)載隊(duì)列長度聯(lián)合確定。為使路由請求不過早地消亡，在消息剛開始傳播時(shí)(h跳以內(nèi))以較高的概率充分?jǐn)U散，h跳之外的節(jié)點(diǎn)降低轉(zhuǎn)發(fā)概率。考慮無線自組織網(wǎng)絡(luò)的規(guī)模，式(1)中h一般取2。節(jié)點(diǎn)的隊(duì)列長度小于隊(duì)列的期望長度時(shí)，表明節(jié)點(diǎn)的負(fù)載較輕，那么節(jié)點(diǎn)以較高的概率轉(zhuǎn)發(fā)，反之表明節(jié)點(diǎn)的負(fù)載較重，那么節(jié)點(diǎn)以較低的概率轉(zhuǎn)發(fā)。根據(jù)當(dāng)前該節(jié)點(diǎn)的隊(duì)列長度，基于文獻(xiàn)［3］，概率pqs(queue_size)的計(jì)算如式(3)所示

1.2 擁塞意識(shí)的路由度量

在無線自組織網(wǎng)絡(luò)中，常用的路徑選擇機(jī)制是以跳數(shù)度量的最短路徑。該路由度量沒有考慮網(wǎng)絡(luò)中鏈路質(zhì)量和流量負(fù)載，往往難以保證選中高吞吐量的路徑。考慮路徑質(zhì)量的路徑選擇機(jī)制可以有效降低因丟包造成的重傳延時(shí)，但路徑中如果某個(gè)節(jié)點(diǎn)負(fù)載較重，從負(fù)載均衡的角度來說，應(yīng)適當(dāng)減少對(duì)該路徑的使用以分散流量?？紤]到以上因素，論文提出考慮鏈路質(zhì)量和節(jié)點(diǎn)的隊(duì)列長度作為路徑度量準(zhǔn)則，以 CRM表示。鏈路l(i，j)的CRM定義如下

其中，NQ為節(jié)點(diǎn)的期望隊(duì)列長度。假設(shè)在入口處數(shù)據(jù)流的達(dá)到服從特征率為λ的負(fù)指數(shù)分布，每個(gè)數(shù)據(jù)分組的服務(wù)時(shí)間服從相同的概率分布且相互獨(dú)立，采用M/G/1隊(duì)列服務(wù)模型模擬。設(shè)Xi表示第i個(gè)到達(dá)分組的服務(wù)時(shí)間。隨機(jī)變量(X1，X2，…)具有相同的概率分布且相互獨(dú)立，到達(dá)時(shí)間間隔也相互獨(dú)立。運(yùn)用Pollaczek－Khinchin(P －K)和 Little公式［12］可得，隊(duì)列的期望長度NQ為

其中，Qi(l)為節(jié)點(diǎn)i的平均隊(duì)列長度;pl為分組丟包率。路徑P的路由度量為

相比最小跳數(shù)的路由度量，CRMP綜合考慮網(wǎng)絡(luò)拓?fù)浜土髁控?fù)載，以一種統(tǒng)一的表達(dá)方式在使用高質(zhì)量路徑和避免擁塞之間做折衷。

1.3 路徑選擇與流量分配

經(jīng)過路由發(fā)現(xiàn)過程，源節(jié)點(diǎn)獲得多條到達(dá)目的節(jié)點(diǎn)的備選路徑。路徑選擇和流量分配機(jī)制如下:源節(jié)點(diǎn)計(jì)算各條路徑的CRMP，并按照CRMP值大小升序排列路徑后選取前K條不相交路徑，該不相交路徑集表示為{Pi}Ki=1。其中，K為用戶指定參數(shù);K確定流量分配粒度。通常K是一個(gè)較小的整數(shù)，例如，K取2或3。按照式(7)確定每條路徑的選擇概率pp。

2 性能仿真

通過在網(wǎng)絡(luò)仿真軟件OPNET中實(shí)現(xiàn)了CMR和多徑源路由算法(Multipath Source Routing，MSR)［2］，并進(jìn)行了性能仿真和對(duì)比分析模擬的網(wǎng)絡(luò)為2 200 m×900 m平面內(nèi)150個(gè)移動(dòng)節(jié)點(diǎn)隨機(jī)均勻分布。MAC層協(xié)議為 IEEE 802.11 DCF，信道速率為 2 Mbit·s－1，每個(gè)節(jié)點(diǎn)的通信半徑為250 m。網(wǎng)絡(luò)業(yè)務(wù)負(fù)載為隨機(jī)選擇10對(duì)連接，并且每對(duì)鏈接在仿真開始30 s內(nèi)隨機(jī)發(fā)起業(yè)務(wù)流。對(duì)于移動(dòng)性的模擬，使用隨機(jī)路點(diǎn)模型RWP［13］，速度設(shè)置為［1 m/s，10 m/s］。業(yè)務(wù)流采用CBR形式，服從到達(dá)率為的負(fù)指數(shù)分布，數(shù)據(jù)有效載荷為2 Mbit，源節(jié)點(diǎn)產(chǎn)生分組速率從4 packet/s逐漸增加至16 packet/s。

仿真中主要評(píng)估3個(gè)性能:(1)成功投遞率Packet Delivery Fraction——成功交付給目的節(jié)點(diǎn)的數(shù)據(jù)分組總數(shù)與源節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組總數(shù)的比值。(2)平均端到端時(shí)延Average end－to－end Delay——數(shù)據(jù)分組傳輸?shù)钠骄说蕉藭r(shí)延，包括所有可能引起的時(shí)延，如路徑發(fā)現(xiàn)時(shí)間、排隊(duì)時(shí)間、傳輸和傳播時(shí)延、重傳時(shí)間等。(3)標(biāo)準(zhǔn)化路由開銷 Normalized Routing Overhead——定義為每交付給目的節(jié)點(diǎn)一個(gè)數(shù)據(jù)分組所需要發(fā)送的路由分組的數(shù)量。路由控制分組每被傳輸一跳，則計(jì)算一次路由分組發(fā)送。

通過仿真，在上述給定的仿真場景中，α取0.8時(shí)可以得到較高的分組交付率及較小的延遲，圖1是α=0.8時(shí)的仿真結(jié)果。如圖1所示，相比MSR，CMR有效提高了網(wǎng)絡(luò)性能。圖1(a)給出了不同流量負(fù)載下的分組送達(dá)率。隨著流量負(fù)載的增加，CMR的分組投遞率緩慢下降而MSR顯著下降。這是因?yàn)樵诼窂竭x擇和流量分配方面，CMR考慮節(jié)點(diǎn)的隊(duì)列長度和鏈路質(zhì)量，有效避免網(wǎng)絡(luò)擁塞熱點(diǎn)，平衡了網(wǎng)絡(luò)負(fù)載，減少重傳和分組丟失。圖1(b)給出了不同流量負(fù)載下的平均端到端時(shí)延。隨著流量負(fù)載的增加，CMR的端到端時(shí)延增加顯著小于MSR。圖1(c)給出了不同流量負(fù)載下的標(biāo)準(zhǔn)化路由載荷。圖1(c)所示，CMR的路由控制開銷小于MSR。原因是，在路由發(fā)現(xiàn)過程中，CMR根據(jù)節(jié)點(diǎn)的網(wǎng)絡(luò)狀態(tài)動(dòng)態(tài)地以一定的概率轉(zhuǎn)發(fā)路由請求分組以避免不必要冗余轉(zhuǎn)發(fā)，而MSR使用簡單的洪泛轉(zhuǎn)發(fā)機(jī)制，仿真結(jié)果表明根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的隊(duì)列長度和路徑的跳數(shù)確定的路由請求消息動(dòng)態(tài)轉(zhuǎn)發(fā)概率來決定分組是否轉(zhuǎn)發(fā)，有效降低了路由開銷。

圖1 不同流量負(fù)載下性能

3 結(jié)束語

提出一種擁塞意識(shí)的多徑路由算法。首先，根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的隊(duì)列長度和路徑跳數(shù)來動(dòng)態(tài)確定路由請求消息的轉(zhuǎn)發(fā)概率，保證路由請求消息對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋的同時(shí)避免不必要的冗余轉(zhuǎn)發(fā)，以有效降低路由開銷。其次，在多路徑選擇和流量分配階段，以鏈路質(zhì)量和節(jié)點(diǎn)的隊(duì)列長度作為路由度量標(biāo)準(zhǔn)來選擇多條路徑，并以此為依據(jù)進(jìn)行流量分配，在使用高質(zhì)量路徑和避免擁塞熱點(diǎn)之間做一個(gè)折衷。仿真結(jié)果顯示所提出的算法有效提高了網(wǎng)絡(luò)的整體性能。

［1］MARINA M K，DAS S R.On － demand multipath distance vector routing in ad hoc networks［C］.Nineth International Conference on Network Protocols，2001:14 －23.

［2］WANG L，SHU Y，DONGM，et al.Adaptive multipath source routing in ad hoc networks［C］.Proc.of IEEE ICC，2001:867－871.

［3］HAAS Z J，HALPERN J Y.Gossip － based ad hoc routing［J］.IEEE/ACM Transactions on Networking，2006，14(3):479－491.

［4］BAKO B，SCHOCH E，KARGL F，et al.Advanced adaptive gossiping using 2－h(huán)op neighborhood information［C］.IEEE Globecom，2008:1 －6.

［5］JIANG Guoxing，YI Ming.Low overhead on － demand routing protocol for mobile ad hoc networks［J］.Journal on Communications，2009，30(7):27 －35.

［6］ABBASA M，JAIN B N.Analysis of disjoint multipath routing for mobile ad hoc networks［C］.Proc.of IEEE ICPWC 2005，2005:42 －46.

［7］VELERA A，SEAH W，RAOS.Improving protocol robustness in ad hoc networks through cooperative packet caching and shortest multipath routing［J］.IEEE Transactions on Mobile Computing，2005，4(5):443 －457.

［8］MARINA M K，DAS S R.On － demand multipath distance vector routing in ad hoc networks［C］.Nineth International Conference on Network Protocols，2001:14 －23.

［9］WANG L，SHU Y，DONGM，et al.Adaptive multipath source routing in ad hoc networks［C］.Proc.of IEEE ICC'2001，2001:867－871.

［10］COUTO D，AGUAYO D，BICKET J，et al.A high － throughput path metric for multi－ hop wireless routing［J］.Wireless Networks，2005，11(4):419 －434.

［11］LASSABE F，CHARLET D，CANALDA P，et al.Friis and iterative trilateration based WiFi devices tracking ［C］.Montbéliard，Sochaux，F(xiàn)rance:The 14th Euromicro International Conference on Parallel，Distributed and Network －Based Processing(PDP 2006)，2006:362 －365.

［12］DIMITRI B，ROBERT G.Data networks［M］.Newyork:Prentice Hall，1992.

［13］YOON J，LIU M，NOBLE B.Random waypoint considered harmful［C］.Proc.of IEEE Infocom，2003:1312－1321.