無線Mesh網(wǎng)絡(luò)多路徑路由協(xié)議的研究

賈小慧，劉乃安，李曉輝，時　鵬

(西安電子科技大學(xué) 通信工程學(xué)院，陜西 西安 710071)

?

無線Mesh網(wǎng)絡(luò)多路徑路由協(xié)議的研究

賈小慧，劉乃安，李曉輝，時鵬

(西安電子科技大學(xué) 通信工程學(xué)院，陜西 西安 710071)

L2MPM路由協(xié)議工作在第2層，屬于多經(jīng)路由中的備份路由，但并未考慮主路經(jīng)與備份路徑之間存在鏈路相交的問題，降低了網(wǎng)絡(luò)的容錯能力。因此，在L2MPM協(xié)議的基礎(chǔ)上，提出了LD-L2MPM路由協(xié)議。該協(xié)議通過采用鏈路不相交策略，在Hello包中添加第一跳和最后一跳字段來確保所選的兩條路徑是鏈路不相交。仿真結(jié)果表明，與原有協(xié)議相比，數(shù)據(jù)包投遞率提高約6%，平均端到端時延降低約5%。

無線Mesh網(wǎng)絡(luò)；多路徑；鏈路不相交

無線Mesh網(wǎng)絡(luò)是一種具有自組織、自修復(fù)的網(wǎng)絡(luò)。最大特點是由Ad-hoc的單一型網(wǎng)絡(luò)節(jié)點演變成了由MAP(Mesh Access Point)、MP(Mesh Point)和MPP(Mesh Portal Point)組成的混合型網(wǎng)絡(luò)節(jié)點，其中MAP可給移動用戶提供接入Mesh網(wǎng)絡(luò)的功能[1]。

作為一種新型的無線網(wǎng)絡(luò)，無線Mesh網(wǎng)絡(luò)從早期走向成熟，有一系列的關(guān)鍵性技術(shù)問題亟需解決。就目前來看，對數(shù)據(jù)鏈路層的主要研究工作體現(xiàn)在信道干擾、吞吐量和負載均衡等方面；在網(wǎng)絡(luò)層，關(guān)鍵點是路由協(xié)議的開發(fā)，其最終目標(biāo)是選擇業(yè)務(wù)流傳輸路由；在MAC(Medium Access Control )層，無線 Mesh 網(wǎng)絡(luò)中的 MAC 是分布式的，需要互相協(xié)調(diào)，實現(xiàn)多跳通信[2]。

無線 Mesh 網(wǎng)絡(luò)是一種多跳中繼網(wǎng)絡(luò)，數(shù)據(jù)傳輸時面臨如何選擇一條快速、穩(wěn)定、高效的最佳路徑的問題。無線Mesh網(wǎng)絡(luò)路由的設(shè)計一般考慮路由判據(jù)、容錯的多路徑路由、擴展性、減少路由開銷等方面。本文針對多路徑路由協(xié)議中存在的鏈路相交的問題提出了解決方案，可獲得更好的時延，提高網(wǎng)絡(luò)吞吐量，改善負載均衡。

1　無線Mesh網(wǎng)多路徑協(xié)議

1.1多路徑基本概述

無線Mesh網(wǎng)本身就支持節(jié)點之間的多路徑，在需要傳輸數(shù)據(jù)的兩個節(jié)點之間可選擇多條路徑。多路徑協(xié)議的主要目標(biāo)是能夠獲取多條高質(zhì)量的傳輸路徑來增強無線網(wǎng)絡(luò)性能，當(dāng)所使用的路徑上某鏈路由于信道質(zhì)量較差或移動性而失效時，便可選擇備份路徑中其他路徑繼續(xù)傳輸。因此，由于無需重新建立路由，端到端時延、吞吐量和容錯性都能得到一定的改善。

多路徑按照相關(guān)性準則可分為3種類型的路徑：節(jié)點不相關(guān)(Node Disjoint Paths)、路徑不相關(guān)(Link Disjoint Paths)和路徑相關(guān)(Link Joint Paths)[3]。

1.2多路徑協(xié)議分類

多路徑協(xié)議也可劃分成兩類：一是先應(yīng)式路由協(xié)議，包括MOLSR[4](Multipath Optimized Link State Routing Protocol)、MESH[5](Multipath MESH)；第二類是反應(yīng)式路由協(xié)議，包括AOMDV[6](Ad hoc on Demand Multipath Distance Vector)、AODV-BR[7](AODV Backup Routing)、MSR[8](Multipath Source Routing)。

2　L2MPM協(xié)議

2.1L2MPM工作原理

上述協(xié)議都在 OSI(Open System Interconnect)參考模型的第三層， L2MPM(Layer 2 Mesh Protocol for Mobile)是一種先應(yīng)式二層 Mesh 路由協(xié)議。網(wǎng)絡(luò)中所有節(jié)點周期性廣播Hello包消息來通告網(wǎng)絡(luò)中其他節(jié)點自身的存在，鄰居節(jié)點收到此 Hello 消息后根據(jù)相應(yīng)的轉(zhuǎn)發(fā)規(guī)則進行重播。該路由協(xié)議的工作原理：源節(jié)點通過在網(wǎng)絡(luò)中周期性地洪泛 Hello 數(shù)據(jù)包，建立自身的路由表并對路由表進行更新。當(dāng)網(wǎng)絡(luò)中的節(jié)點需要到目標(biāo)節(jié)點的路由時，L2MPM 路由協(xié)議會確定一個到目標(biāo)節(jié)點的最佳本地鄰居節(jié)點作為下一跳路由[9]。

L2MPM 協(xié)議的特點只存儲到達目標(biāo)節(jié)點的最優(yōu)和潛在下一跳，這樣一方面可減少存儲開銷，另一方面，當(dāng)最優(yōu)下一跳節(jié)點突然離開時，可直接選擇潛在下一跳來路由。L2MPM路由協(xié)議屬于多徑路由中的備份路徑，但是未考慮路由表中存儲的兩條路徑之間存在鏈路相交的可能，結(jié)果會導(dǎo)致所用路徑出現(xiàn)鏈路錯誤同時，備份路徑也會存在斷路的風(fēng)險。因此，在原有協(xié)議的基礎(chǔ)上進行多路徑的改進，保證主路徑與備份路徑是鏈路不相交路徑，提高工作效率，減小端到端時延。

2.2L2MPM路由協(xié)議優(yōu)化方案—LD-L2MPM

為使一個節(jié)點到另一個節(jié)點建立的主路徑和潛在路徑是鏈路不相交路徑，此次優(yōu)化方案參考了AOMDV協(xié)議的工作原理。這兩種路由協(xié)議皆是通過逐跳的形式來發(fā)現(xiàn)路由，源節(jié)點通過選擇和添加鄰居節(jié)點來發(fā)現(xiàn)到達目標(biāo)節(jié)點的路徑，并使用所選擇鄰居節(jié)點來作為業(yè)務(wù)流轉(zhuǎn)發(fā)的下一跳節(jié)點，無需維護整個網(wǎng)絡(luò)的拓撲及路由信息。因此，LD-L2MPM(Link Disjoint-Layer 2 Mesh Protocol for Mobile)協(xié)議在Hello包格式和路由表上做了些改進，在Hello包格式中添加第一跳，在路由表中加入最后一跳字段。在發(fā)送Hello包的整個過程中，中間節(jié)點均要檢查第一跳和最后一跳是否相同，只有第一跳和最后一跳不同才加入路由表，保證每一條路徑是鏈路不相交路徑。

圖1說明鏈路不相交的思路，圖1(a)在路徑發(fā)現(xiàn)過程中到B節(jié)點時，有兩條路徑(S-A-B)和(S-C-B)，滿足具有不同的第一跳和最后一跳的條件，但是到C節(jié)點時，兩條路徑有共同鏈路，因此就不屬于鏈路不相交路徑，圖1(b)中兩條路徑滿足上述條件，為鏈路不相交路徑。

圖1　鏈路不相交策略

2.3LD-L2MPM的路由建立和更新

路由信息表的建立和維護涉及到接收和轉(zhuǎn)發(fā)Hello包的過程，本地節(jié)點為聲明自身的存活性而周期性地廣播包含自身物理地址的Hello包。當(dāng)前節(jié)點收到某節(jié)點發(fā)來的Hello包后，第一步是要判斷是否由本身所發(fā)的數(shù)據(jù)包，若是則直接釋放，若不是則判斷是否是鄰居節(jié)點發(fā)來的Hello包，如果是，且前一跳的地址等于源節(jié)點地址，則將第一跳的地址置為該節(jié)點MAC地址。若是鄰居節(jié)點發(fā)來源節(jié)點自身的Hello包，則進行相關(guān)路由信息的建立或更新。如果不是，要在路由表中查找到始發(fā)Hello包源節(jié)點的路由是否存在，如果路由表中存在到源節(jié)點的路徑，再將該路徑與原有路徑比較，看是否為鏈路不相交路徑，如果是鏈路不相交，就將該路徑添加到該節(jié)點路由表項中；若路由表項中不存在到發(fā)送Hello包源節(jié)點的有效路徑，則直接將新路徑添加到當(dāng)前節(jié)點到源節(jié)點的路徑表項中。然后，對Hello包進行相關(guān)字段的更新，轉(zhuǎn)發(fā)給下一鄰居節(jié)點。

3　仿真測試及分析

利用NS2[10]仿真軟件對LD-L2MPM多路徑路由協(xié)議進行仿真測試，并與L2MPM協(xié)議在平均端到端時延、分組投遞率等方面進行性能比較。

3.1傳輸模型選擇

本次仿真與以往不同的是，此次在無線傳輸模型上選取了Shadowing模型，以往則是選取Two-Ray-Ground模型。NS2中實現(xiàn)了3個無線模型，分別是：Free -Space(自由空間)模型、Two-Ray-Ground(雙徑地面)模型及Shadowing(陰影)模型。這3個模型的主要功能是來監(jiān)測每個數(shù)據(jù)包的接收信號，每一個無線節(jié)點的接收閾值均存在于物理層中，若是一個數(shù)據(jù)包的接收信號功率低于此處接收閾值，MAC層會判為錯誤并丟棄此數(shù)據(jù)包。Free-Space模型、Two-Ray-Ground模型采用的接收功率公式主要以距離參數(shù)來決定，其通信范圍是一個理想的環(huán)。Shadowing模型[11]包括兩部分：一是路徑損耗模型；二是反映了距離一定時接收功率的變化。Shadowing模型不再是理想的環(huán)模型，而是基于統(tǒng)計的模型，所以節(jié)點在接近通信范圍邊界處只是有可能進行通信，而不是絕對。

3.2仿真參數(shù)設(shè)置

場景參數(shù)設(shè)置如表1所示。

表1　參數(shù)設(shè)置

3.3仿真結(jié)果分析

仿真數(shù)據(jù)比較如圖2和圖3所示。

圖2　平均端到端時延

圖2為在不同的數(shù)據(jù)包發(fā)送速率中，L2MPM和LD-L2MPM協(xié)議在平均端到端時延的曲線對比圖。從圖中可看出，隨著發(fā)包速率的增大，時延也在不斷增加，這是因隨著發(fā)包速率的增加，網(wǎng)絡(luò)節(jié)點出現(xiàn)過載，致使網(wǎng)絡(luò)中業(yè)務(wù)流擁塞的幾率升高，平均時延也隨之增加。而LD-L2MPM協(xié)議的平均端到端時延總小于L2MPM協(xié)議，說明LD-L2MPM在加入鏈路不相交的路由選擇機制起到了較好的作用，降低了網(wǎng)絡(luò)時延，提高工作效率。

圖3表明，LD-L2MPM協(xié)議在分組投遞率性能上要優(yōu)于L2MPM協(xié)議，主要是因為L2MPM協(xié)議并未考慮到鏈路相交的問題，使得不同的數(shù)據(jù)流可能使用相同的鏈路在傳輸，導(dǎo)致鏈路負載加重，分組投遞數(shù)量降低。隨著節(jié)點發(fā)包率的增加，節(jié)點負載加重，會導(dǎo)致緩存隊列擁塞而丟棄數(shù)據(jù)組，兩個協(xié)議的分組投遞率都會隨之下降。

圖3　分組投遞率

4　結(jié)束語

本文所提出的LD-L2MPM協(xié)議確保所選出的主路經(jīng)與備份路徑是鏈路不相交路徑，在不增加路由開銷的基礎(chǔ)上，提高網(wǎng)絡(luò)工作效率，降低端到端時延。利用NS2仿真軟件，對L2MPM協(xié)議、LD-L2MPM協(xié)議進行了仿真測試比較。以上仿真數(shù)據(jù)曲線表明，LD-L2MPM協(xié)議在平均端到端時延、分組投遞率方面的性能要優(yōu)于L2MPM協(xié)議。

[1]宋立梅,劉乃安,曾興雯.無線,Mesh網(wǎng)絡(luò)路由協(xié)議研究[J].電子科技,2008,21(7):30-33.

[2]柴遠波,鄭晶晶.無線Mesh網(wǎng)絡(luò)應(yīng)用技術(shù)[M].北京:電子工業(yè)出版社,2015.

[3]史曉晨.無線MESH網(wǎng)絡(luò)多路徑路由協(xié)議的研究與設(shè)計[D].北京:北京郵電大學(xué),2011.

[4]Xuekang S,Wanyi G, X Xiao,et al.Node discovery algorithm based multipath OLSR routing protocol[C].Taiyuan：WASE International Conference on Information Engineering, 2009.

[5]楊艷.WMN多路徑路由協(xié)議研究[D].南京:南京航空航天大學(xué),2011.

[6]李波,潘進,李國鵬,等.基于NS2的AOMDV路由協(xié)議的改進與性能仿真[J].計算機應(yīng)用與軟件,2010,27(2):56-58.

[7]Lee S J, Gerla M.AODV-BR: backup routing in ad hoc networks[C].Chicago:Wireless Communications and Networking Conference, 2000.

[8]喬平安,邵凱,劉運爽.基于無線Ad hoc的多路徑多信道路由度量準則[J].電子科技,2015,28(8):60-62.

[9]時鵬.WMN中節(jié)點部署算法和網(wǎng)關(guān)自適應(yīng)的設(shè)計與實現(xiàn)[D].西安:西安電子科技大學(xué),2014.

[10] 吉祖勤,蔡長安.NS2仿真技術(shù)在網(wǎng)絡(luò)實驗教學(xué)中的應(yīng)用[J].實驗室技術(shù)與管理,2012,28(12):96-99.

[11] 于斌,孫斌,溫暖,等.NS2與網(wǎng)絡(luò)模擬[M].北京:人民郵電出版社,2007.

Research on the Multi-Path Routing Protocol in the Wireless Mesh Network

JIA Xiaohui, LIU Naian, LI Xiaohui, SHI Peng

(School of Telecommunications Engineering, Xidian University, Xi’an 710071, China)

The L2MPM (Layer 2 Mesh Protocol for Mobile) routing protocol works on the second layer which belongs to the backup route in the multi-path routing, but it does not consider the link intersecting between main and backup path to reduce the tolerance of the network. An LD-L2MPM (LINK_DISJOINT_L2MPM) routing protocol based on L2MPM is proposed in the paper, which adopts the strategy of non-intersecting link that adds the first hop and the last hop to the packet of Hello to ensure that the two paths selected by the protocol are link-disjoint．The simulation results show that the rate of packet delivery increases by about 6%, and the average end-to-end delay reduces by about 5% compared with those of the original routing protocol.

wireless mesh network; multi-path; link-disjoint

10.16180/j.cnki.issn1007-7820.2016.08.036

2015-11-11

陜西省科學(xué)技術(shù)研究發(fā)展計劃基金資助項目(2014K05-13)

賈小慧(1991-)，女，碩士研究生。研究方向：擴頻技術(shù)與通信與對抗。劉乃安(1966-)，男，教授。研究方向：無線擴頻通信與射頻電路。李曉輝(1972-)，女，博士，教授。研究方向：寬帶無線通信。

TN915.04；TP393

A

1007-7820(2016)08-124-03