基于混合架構(gòu)無線Mesh網(wǎng)的多路徑路由協(xié)議

沈 華

(1.湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢 430068;2.武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢 430072)

無線 Mesh網(wǎng)絡(luò)(wireless mesh networks，WMNs)的路由是一項(xiàng)關(guān)鍵技術(shù)［1-2］。一方面，WMNs繼承了Ad hoc網(wǎng)絡(luò)的特點(diǎn)，Ad hoc網(wǎng)絡(luò)的一些路由協(xié)議可以應(yīng)用到WMNs中，如基于距離矢量的按需路由協(xié)議(on-demand distance vector routing，AODV)［3］、動(dòng)態(tài)源路由協(xié)議(DSR)［4-5］等;另一方面，WMNs在移動(dòng)性、能量約束、業(yè)務(wù)模式等方面又有著不同于Ad hoc網(wǎng)絡(luò)的特性。因此，如何使Ad hoc環(huán)境下的路由協(xié)議更好地適用于WMNs成為一個(gè)研究熱點(diǎn)。同時(shí)，相對(duì)于單路徑路由協(xié)議，多路徑路由協(xié)議在容錯(cuò)、路由可靠性和QoS路由等方面有較大優(yōu)勢(shì)。為了進(jìn)一步提高移動(dòng)自組網(wǎng)絡(luò)的路由質(zhì)量，多路徑路由也逐漸被廣泛關(guān)注［6-10］。

基于此，提出了一種改進(jìn)DSR的路由協(xié)議，即MOMDSR(mesh-oriented multipath DSR)協(xié)議。MOMDSR針對(duì)混合架構(gòu)WMNs的特點(diǎn)并借鑒分級(jí)路由的思想，提出了一種有效減少數(shù)據(jù)報(bào)文頭部源路由信息的方法，同時(shí)在路由發(fā)現(xiàn)過程中引入了多路徑路由的思想，使得協(xié)議在路由開銷、報(bào)文傳輸率等性能上有所改善。

1 協(xié)議概述

1.1 協(xié)議的適用環(huán)境

MOMDSR的適用環(huán)境是客戶端域互不相交的混合架構(gòu)WMNs，即不同客戶端域中的節(jié)點(diǎn)之間不能直接通信，它們的通信必須通過Mesh骨干網(wǎng)完成。以樓宇間的WMNs為例，一棟樓中的各種 Mesh客戶端(如便攜式 PC、PDA、IP電話等)自組聯(lián)網(wǎng)構(gòu)成一個(gè)客戶端域，它們可以通過多跳的方式互相通信。而樓宇間(即不同客戶端域中)的Mesh客戶端通過WMNs骨干網(wǎng)來實(shí)現(xiàn)通信，該骨干網(wǎng)由樓宇中的Mesh路由器構(gòu)成。同時(shí)通過這個(gè)骨干網(wǎng)，樓宇中的節(jié)點(diǎn)還可以訪問Internet或其他的無線網(wǎng)絡(luò)。

1.2 引入的概念

在MOMDSR中引入了“臨界Mesh路由器”和“合法路由”兩個(gè)概念。

“臨界Mesh路由器”是指與某個(gè)或某幾個(gè)Mesh客戶端直接連接的Mesh路由器。如圖1中，節(jié)點(diǎn)B、D是客戶端域Ⅰ的臨界Mesh路由器;節(jié)點(diǎn)C、D是客戶端域Ⅱ的臨界Mesh路由器;節(jié)點(diǎn)G是客戶端域Ⅲ的臨界Mesh路由器。

圖1 路由請(qǐng)求的5種情況

1.3 MOMDSR數(shù)據(jù)報(bào)文頭部的路由信息

數(shù)據(jù)報(bào)文在客戶端域內(nèi)傳輸時(shí)，頭部攜帶的是域內(nèi)的源路由信息;當(dāng)它在骨干網(wǎng)中傳輸時(shí)，采用逐跳路由。例如，假設(shè)客戶端域Ⅰ中的節(jié)點(diǎn)A向客戶端域Ⅱ中的節(jié)點(diǎn)E發(fā)送數(shù)據(jù)報(bào)文，并假設(shè)B、C分別是Ⅰ和Ⅱ的臨界Mesh路由器，那么數(shù)據(jù)報(bào)文頭部初始包含A到B的路由信息;到達(dá)B后，刪除頭部的路由信息并按B路由表中的下一跳信息進(jìn)行轉(zhuǎn)發(fā);當(dāng)?shù)竭_(dá)C后，頭部將包含從C到E的路由信息。如果Ⅰ和Ⅱ的臨界路由器相同(假設(shè)都是B)，那么當(dāng)數(shù)據(jù)報(bào)文到達(dá)B后，用從B到E的路由信息覆蓋頭部原有的路由信息。

1.4 MOMDSR中的多路徑策略

客戶端域內(nèi)或骨干網(wǎng)中的多路徑節(jié)點(diǎn)是不相關(guān)的，客戶端域間或客戶端域與骨干網(wǎng)間的多路徑是鏈路不相關(guān)的。路徑相關(guān)性的判斷由目的節(jié)點(diǎn)和源節(jié)點(diǎn)共同完成。多路徑路由的使用模式是替換多路徑(或備份多路徑)模式。

2 協(xié)議結(jié)構(gòu)

2.1 協(xié)議中各報(bào)文的具體格式

(1)MOMDSR 路由請(qǐng)求(route request，RRQ)報(bào)文是在DSR路由請(qǐng)求報(bào)文的基礎(chǔ)上增加“源節(jié)點(diǎn)所在客戶端域標(biāo)識(shí)”字段得到的。如果發(fā)起路由請(qǐng)求過程的是Mesh路由器，則不需要填寫該字段。此外，還增加了節(jié)點(diǎn)類型字段，用來記錄所經(jīng)過節(jié)點(diǎn)的類型。

(2)MOMDSR 路由響應(yīng)(route reply，RRP)報(bào)文是在DSR路由響應(yīng)報(bào)文的基礎(chǔ)上增加“目的節(jié)點(diǎn)所在客戶端域標(biāo)識(shí)”字段得到的。如果目的節(jié)點(diǎn)是Mesh路由器，則不需要填寫該字段。此外，還增加了節(jié)點(diǎn)類型字段。

(3)MOMDSR路由確認(rèn)(route acknowledgement，RAK)報(bào)文(如圖2所示)幫助Mesh路由器形成逐跳路由表。

圖2 路由確認(rèn)報(bào)文

2.2 節(jié)點(diǎn)所需維護(hù)的數(shù)據(jù)結(jié)構(gòu)

(1)節(jié)點(diǎn)信息表。節(jié)點(diǎn)信息表數(shù)據(jù)結(jié)構(gòu)圖如圖3所示。

圖3 節(jié)點(diǎn)信息表數(shù)據(jù)結(jié)構(gòu)圖

對(duì)于Mesh客戶端而言，需要填寫“所在客戶端域標(biāo)識(shí)”字段。對(duì)于Mesh路由器，“客戶端域標(biāo)識(shí)i”記錄以該節(jié)點(diǎn)為臨界路由器的客戶端域標(biāo)識(shí)。

(2)Mesh客戶端的路由表。Mesh客戶端的路由表數(shù)據(jù)結(jié)構(gòu)圖如圖4所示。

在進(jìn)行駕駛行為評(píng)價(jià)的過程中，各個(gè)狀態(tài)之間沒有明確界限，具有模糊性. 選擇函數(shù)性質(zhì)穩(wěn)定、控制平緩、分辨度高的梯形隸屬度函數(shù). 根據(jù)采集到的駕駛行為影響因素分布情況，分析其平均值、中位數(shù)、四分位數(shù)等關(guān)鍵數(shù)據(jù)，結(jié)合專家修正意見，建立急加速次數(shù)、急減速次數(shù)、長時(shí)怠速次數(shù)、長時(shí)加速次數(shù)的隸屬度函數(shù)，如圖2所示.

圖4 Mesh客戶端的路由表數(shù)據(jù)結(jié)構(gòu)圖

根據(jù)合法路由的定義可知，＜節(jié)點(diǎn)1，節(jié)點(diǎn)2，…，節(jié)點(diǎn)M＞記錄的要么是該節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由，要么是該節(jié)點(diǎn)到某個(gè)臨界路由器的路由。

(3)Mesh路由器的路由表。如果下一跳是Mesh路由器，則記錄下一跳的地址;否則記錄從下一跳開始的后繼路由。

3 協(xié)議工作過程

3.1 MOMDSR的路由發(fā)現(xiàn)過程

當(dāng)源節(jié)點(diǎn)的路由表中不存在到達(dá)目的節(jié)點(diǎn)的路由時(shí)，源節(jié)點(diǎn)通過廣播RRQ來啟動(dòng)路由發(fā)現(xiàn)過程。根據(jù)所討論的環(huán)境，可知有以下5種情況:源節(jié)點(diǎn)和目的節(jié)點(diǎn)屬于同一客戶端域，如圖1中的F和E;源節(jié)點(diǎn)是Mesh客戶端，目的節(jié)點(diǎn)是Mesh路由器，如圖1中的A和G;源節(jié)點(diǎn)是Mesh路由器，目的節(jié)點(diǎn)是Mesh客戶端，如圖1中的G和E;源節(jié)點(diǎn)和目的節(jié)點(diǎn)均是Mesh路由器，如圖1中的B和G;源節(jié)點(diǎn)和目的節(jié)點(diǎn)屬于不同客戶端域，如圖1中的A和E。

當(dāng)一個(gè)節(jié)點(diǎn)接收到RRQ時(shí)，采用以下步驟進(jìn)行處理:

(1)如果該節(jié)點(diǎn)是目的節(jié)點(diǎn)，那么首先判斷該RRQ中的路由跳數(shù)是否大于之前收到的路由跳數(shù)，如果大于，則丟棄該RRQ;否則繼續(xù)判斷RRQ中的路由與之前收到路由的相關(guān)性，如果相關(guān)，則丟棄該 RRQ;否則，向源節(jié)點(diǎn)返回一個(gè)RRP。如果該節(jié)點(diǎn)的路由表中沒有到達(dá)源節(jié)點(diǎn)的路由，那么將啟動(dòng)路由發(fā)現(xiàn)過程。如果該節(jié)點(diǎn)不是目的節(jié)點(diǎn)，則進(jìn)入步驟(2)。

(2)檢查RRQ的路由記錄是否已包含該節(jié)點(diǎn)，若包含，則丟棄該RRQ;否則，進(jìn)入步驟(3)。

(3)判斷RRQ的路由記錄在加入該節(jié)點(diǎn)后是否合法，如果不合法，則丟棄該RRQ;否則，進(jìn)入步驟(4)。

(4)判斷該RRQ是否是重復(fù)RRQ，如果不是，則進(jìn)入步驟(5);否則，接著判斷該RRQ中的路由跳數(shù)是否小于第一次收到的RRQ中的路由跳數(shù)。如果小于，則繼續(xù)轉(zhuǎn)發(fā)該RRQ;否則，丟棄該RRQ。

(5)在路由請(qǐng)求表中記錄該RRQ的相關(guān)信息;再將自己的地址和類型附加到RRQ后，轉(zhuǎn)發(fā)該報(bào)文。

3.2 MOMDSR的路由確認(rèn)過程

第一個(gè)到達(dá)源節(jié)點(diǎn)的RRP將觸發(fā)MOMDSR路由確認(rèn)過程的開始。有以下3種情況:①源節(jié)點(diǎn)在接收到一個(gè)從目的節(jié)點(diǎn)發(fā)來的RRP之前沒有收到過從中間節(jié)點(diǎn)發(fā)來的RRP。在這種情況下，源節(jié)點(diǎn)將判斷RRP返回的源路由中是否包含Mesh路由器，如果包含，則根據(jù)RRP的內(nèi)容形成RAK，并發(fā)送該RAK;否則，將直接存儲(chǔ)該路由。②源節(jié)點(diǎn)在接收到一個(gè)從目的節(jié)點(diǎn)發(fā)來的RRP之前收到過中間節(jié)點(diǎn)發(fā)送的RRP。在這種情況下，源節(jié)點(diǎn)首先判斷RRP返回的路由與中間節(jié)點(diǎn)返回的路由是否相關(guān)，如果相關(guān)，則丟掉該路由;否則，進(jìn)入情況①的處理過程。③源節(jié)點(diǎn)在收到某個(gè)中間節(jié)點(diǎn)發(fā)送來的RRP之前，已經(jīng)收到過目的節(jié)點(diǎn)返回的RRP或其他中間節(jié)點(diǎn)返回的RRP。在這種情況下，源節(jié)點(diǎn)首先判斷該中間節(jié)點(diǎn)返回的路由與已收到路由的相關(guān)性，如果相關(guān)，則丟掉該路由;否則，進(jìn)入情況①的處理過程。需要說明的是，RAK根據(jù)源路由進(jìn)行發(fā)送。

下面說明中間節(jié)點(diǎn)處理RAK的過程。

如果是客戶端節(jié)點(diǎn)接收到RAK，那么它將直接向下一跳節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā);如果是Mesh路由器接收到RAK，且下一跳仍是Mesh路由器，那么它將RAK中的目的節(jié)點(diǎn)地址、剩余跳數(shù)和下一跳節(jié)點(diǎn)地址等信息填寫到自己路由表的相應(yīng)字段中;如果下一跳是客戶端節(jié)點(diǎn)，那么它將RAK中的目的節(jié)點(diǎn)地址、剩余跳數(shù)、從下一跳節(jié)點(diǎn)開始到目的節(jié)點(diǎn)的路由等信息填寫到路由表的相應(yīng)字段中;然后，向下一跳轉(zhuǎn)發(fā)該RAK。例如，當(dāng)包含如下路由信息C(1)-D(1)-E(1)-F(1)-G(0)-M(0)-N(0)(Ⅱ)的RAK在到達(dá)節(jié)點(diǎn)N之后，路由上各Mesh路由器的路由表為:C(N，6，D);D(N，5，E);E(N，4，F(xiàn));F(N，3，G-M-N)。并且在源節(jié)點(diǎn)A的路由表中關(guān)于該路由的記載為(N，8，B-C)。

3.3 MOMDSR的路由維護(hù)過程

在路由建立后，就進(jìn)入路由維護(hù)階段。MOMDSR采用的是一種混合式的路由維護(hù)，即在客戶端域內(nèi)采用按需式路由維護(hù)，在骨干網(wǎng)中采用主動(dòng)式路由維護(hù)。這樣可使Mesh路由器的路由表得到及時(shí)更新并降低路由維護(hù)的整體開銷。

4 仿真實(shí)驗(yàn)和性能分析

4.1 仿真模型

對(duì)DSR、MOMDSR協(xié)議進(jìn)行了仿真實(shí)驗(yàn)，所采用的仿真平臺(tái)是Windows+cygwin+nsallinone-2.28。

仿真模擬了一個(gè)有50個(gè)移動(dòng)節(jié)點(diǎn)的WMNs，并且這些節(jié)點(diǎn)隨機(jī)分布在一個(gè)1500 m×300 m的矩形區(qū)域內(nèi)，整個(gè)仿真時(shí)間為450 s。在仿真中，移動(dòng)節(jié)點(diǎn)按照Random Waypoint移動(dòng)模型移動(dòng)，并且采用CBR(constant bit rate)流量源來產(chǎn)生通信量，以4個(gè)/s的速率發(fā)送報(bào)文，在該仿真中含有20個(gè)CBR源。

這里仿真的協(xié)議性能是暫停時(shí)間的函數(shù)，并且針對(duì)兩種節(jié)點(diǎn)移動(dòng)速度的最大值(1 m/s和20 m/s)。在仿真中，定義了7個(gè)不同暫停時(shí)間的移動(dòng)模型，分別為 0 s，20 s，40 s，70 s，150 s，300 s和450 s。暫停時(shí)間為0，表示連續(xù)不斷地移動(dòng);暫停時(shí)間為450 s，表示節(jié)點(diǎn)靜止。

4.2 協(xié)議性能比較參數(shù)

(1)報(bào)文傳輸率=成功接收到的數(shù)據(jù)報(bào)文數(shù)/發(fā)送的數(shù)據(jù)報(bào)文數(shù)。

(2)路由開銷=路由報(bào)文數(shù)。

4.3 仿真結(jié)果及分析

在圖5(a)中，可以看到在移動(dòng)速度最大值為1 m/s時(shí)，有7個(gè)暫停時(shí)間處MOMDSR的報(bào)文傳輸率要略高于DSR協(xié)議。從圖5(c)中可以看出在較高移動(dòng)速度下，MOMDSR在報(bào)文傳輸率性能上的優(yōu)化要更加明顯。

圖5 MOMDSR和DSR的報(bào)文傳輸率和路由開銷的比較(分別在1 m/s和20 m/s兩種移動(dòng)速度下)

比較圖5(b)和圖5(d)發(fā)現(xiàn)，在較低或較高移動(dòng)速度下，都是在移動(dòng)較頻繁時(shí)，MOMDSR的路由開銷要小于DSR，但在節(jié)點(diǎn)相對(duì)穩(wěn)定時(shí)，MOMDSR的路由開銷要略高于 DSR?？傮w上看，MOMDSR的路由開銷性能略優(yōu)于DSR。

5 結(jié)論

提出了一種基于混合構(gòu)架無線Mesh網(wǎng)絡(luò)的多路徑路由協(xié)議MOMDSR。在MOMDSR中，引入了路由確認(rèn)階段，修改或設(shè)計(jì)了相關(guān)數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了Mesh骨干網(wǎng)中的逐跳路由，使得數(shù)據(jù)報(bào)文在骨干網(wǎng)中傳輸時(shí)，不用攜帶路由信息，而在客戶端域內(nèi)傳輸時(shí)，只需攜帶部分源路由信息，縮短了DSR中數(shù)據(jù)報(bào)文頭部的路由信息。在MOMDSR的路由發(fā)現(xiàn)過程中引入了臨界Mesh路由器、合法路由等概念，實(shí)現(xiàn)了多條路由的發(fā)現(xiàn)。仿真結(jié)果表明，MOMDSR在路由開銷、報(bào)文傳輸率等方面略優(yōu)于DSR。

［1］AKYILDIZ I F，WANG X D，WANG W L.Wireless mesh networks:a survey［J］.Computer Networks，2005，47(4):445-487.

［2］RAYNER K.Mesh wireless networking［J］.IEEE Communications Engineer，2003，1(5):44-47.

［3］PERKINS C E，BHAGWAT P.Highly dynamic destination-sequenced distance-vector routing(DSDV)for mobile computers［J］.Comp Comm Rev，1994(10):234-244.

［4］JOHNSON D，MALTZ D.Dynamic source routing algorithm for mobile wireless networks［C］//IEEE NFOCOM1997.［S.l.］:［s.n.］，1997:1405-1413.

［5］JOHNSON D B，MALTZ D A.The dynamic source routing protocol for mobile Ad Hoc networks［ED/OL］.［2011-07-05］.http://www3.ietf.org/proceedings/02nov/I-D/draft-ietf-manet-dsr-07.txt.

［6］NASIPURI A，DAS S R.On-demand multipath routing for mobile Ad Hoc networks［C］//Proc IEEE ICCCN.［S.l.］:［s.n.］，1999:64-70.

［7］LEE S J，GERIA M.Split multipath routing with maximally disjoint paths in Ad Hoc networks［J］.IEEE，2001，10(6):3201-3205.

［8］PHAM P P，PERREAU S.Increasing the network performance using multi-path routing mechanism with load balance［J］.Ad Hoc Networks，2004，2(4):433-459.

［9］LEI W.Multipath source routing in wireless Ad Hoc networks［C］//2000 Canadian Conference on Electrical and Computer Engineering.［S.l.］: ［s.n.］，2000:479-483.

［10］MUELLER S，GHOSAL D.Multipath routing in mobile Ad Hoc networks:ssues and challenges［R］.［S.l.］:Invited Paper in Lecture Notes in Computer Science，2004.