基于鏈路狀態因子的無線MESH網絡路由判據研究*

亓沂濱 王君珺 朱華進 劉顯靜

(1.海軍司令部信息化部 北京 100841)(2.海軍91469部隊 北京 100841)

基于鏈路狀態因子的無線MESH網絡路由判據研究*

亓沂濱1王君珺2朱華進2劉顯靜2

(1.海軍司令部信息化部 北京 100841)(2.海軍91469部隊 北京 100841)

針對AODV協議的跳數路徑判據的不足,以傳統的ETX判據為基礎,將鏈路質量、鏈路干擾和節點負載等鏈路狀態參數相結合,提出新的路徑判據計算方案,通過仿真實驗證明,新的路由判據計算方案的路徑選擇算法有助于提高網絡吞吐量,降低丟包率和平均延時,對于提高網絡性能是行之有效的。

無線網狀網; 路由協議; 路由判據; 鏈路狀態

Class Number TP393

1 引言

無線網狀網(Wireless Mesh Network)是一種具有自組織和自愈特點的多跳寬帶無線組網技術[1],可以看成是一種特殊的WLAN與Ad hoc網絡的結合體,是一種由無線路由器和終端設備的靜態無線網絡,是Internet的無線版本[2]。無線網狀網擁有比傳統無線Ad hoc網絡和無線局域網WLAN更高的可靠性、更高的數據吞吐率、更低的干擾及更強的擴展性等特點[3],因此它也成為了當前網絡研究的熱點,無線Mesh網絡的軍事應用前景也被十分看好。

在無線網狀網中,通信網絡提供高質量、高效率服務的關鍵技術之一是路由算法,而路由算法的性能高低取決于路由判據。傳統Ad hoc路由選擇是根據跳數(hop count)來選擇路由,這種選路方式沒有綜合考慮到信道質量及多信道下的鏈路干擾等問題,因此難以達到無線網狀網在網絡容量和傳輸性能上的要求。

2 問題分析

跳數判據是Ad hoc網絡中使用最廣泛的一種路由判據,DSDV、AODV等路由協議都采用最小跳數作為路由判據[4]。跳數判據的最小權重路徑是從源節點到目的節點跳數最小的路徑。這種算法原理是將報文在一條路徑上所經過的跳數進行簡單累加。

在無線Mesh網絡中最小跳數判據不太適用,原因在于最小跳數路徑準則沒有考慮到其下層物理信道特性的變化對MAC層接入性能的影響等因素,以及上層對QoS要求,造成所選路徑無法適應底層性能的變化,也可能造成傳輸層的較大波動。此外,就無線信道而言,在通信期間即使鏈路環境沒有產生變化,最優路徑不一定是跳數最小的路徑。在誤碼率相同條件下,單跳傳輸的距離越長,信道數據傳輸速率就越低,也就是說短距離的非最短路徑也可能比長距離的最短路徑的吞吐量傳或輸速率高。

目前改進的路由判據主要有ETX(期望傳輸次數)、ETT(期望傳輸時間)、ENT(有效傳輸數量)等[5],這些路由判據往往是針對特定路由協議設計的,本文旨在研究一種普遍適合無線Mesh網絡的路由判據。

3 新的路由判據的計算方案

3.1 傳統ETX算法的研究

評判一個路由協議的性能好壞,最重要的兩個指標是丟包率和端到端時延[6]。丟包率很大程度上取決于鏈路的質量,同時節點的擁塞也可能導致某些數據包因阻塞而丟失。ETX算法中,網絡中的節點每隔1s以1Mbps的速率廣播探測數據包,所有的鄰居節點可以通過接收這些探測數據包來計算丟包率。因此,可以通過回復消息得到前向傳輸丟包率df和后向傳輸丟包率dr。依據概率公式,可得到鏈路的丟包率p如式(1)所示。

p=1-(1-df)(1-dr)

(1)

假如經過k次嘗試后在一條鏈路上傳輸成功,則該條鏈路傳輸成功的概率S(k)為

S(k)=pk-1×(1-p)

(2)

結合式(1)和式(2),可得出鏈路傳輸次數的數學期望ETX如式(3)所示:

(3)

ETX算法的存在兩點不足: 1) ETX沒有直接考慮鏈路的速率和節點負載; 2) ETX算法沒有考慮使用相同信道傳輸的干擾問題[7]。為此引入綜合考慮鏈路質量、鏈路干擾、節點負載均衡三個方面因素的路由度量標準。

3.2 綜合路由度量標準的計算方案

1) 鏈路質量因子Q

研究證明期望傳輸次數判據能夠較好地反映鏈路的質量,使用改進后的ETX判據作為判斷鏈路質量好壞的標準可以適用于無線網狀網[8]。為了解決單一鏈路傳輸極限問題,本文設置一個丟包率閾值Pd,Pd可動態配置,當某一條鏈路的丟包率大于Pd,則該條鏈路將被視為容量飽和而被放棄,Pd可以根據當前網絡的鏈路質量來配置。因此可以得到一條完整路由的鏈路質量因子Q如式(4)所示。

(4)

2) 鏈路干擾因子I

定義一條鏈路e的干擾值Ie,Ie的算法如式(5)所示,其中k為系統可用的總信道數,Vi表示在信道i上的平均速率,Ci為信道i的最大速率。

(5)

I可以看作某條鏈路與受其干擾的其他鏈路的信道競爭情況。由上式可知I值越小,即鏈路占用信道的比例越小,那么其他鏈路可用于傳輸信道就越多,傳輸數據量越大。雖然因子I降低了本條鏈路的平均傳輸速率,但是有利于鏈路e的干擾區域內可能存在的其他互不干擾的鏈路的傳輸。從無線網狀網的整體來看,可使整個網絡流量更加均勻,有效提高網絡吞吐量。根據式(5)可以得到整條路由的干擾因子I,如式(6)所示:

(6)

3) 節點負載因子L

在一條傳輸路徑中,若某個中間節點數據處理能力達到極限就會出現傳輸擁塞,那么該節點會嚴重影響整條路由的數據傳輸速率。當一個中間節點收到數據包需要轉發或處理時,會在本地將數據包緩存,然后再發往下一節點。如果由于網絡擁塞沖突等原因,導致不能建立連接,或數據包不能順利發送至下一節點,則該節點會將需要轉發的數據包暫時緩存本地。

一個節點的緩存占用比例可以在一定程度體現該節點的擁塞程度[9]。下面將提出一種使用期望傳輸次數來大致估算節點緩存的占用比例,繼而可以在選擇路由時盡可能保證節點的負載均衡。

取某條路由上的一個中間節點q,假設該節點的下一節點路徑即前向鏈路的期望傳輸次數為ETXq,上一節點路徑即后向鏈路的期望傳輸次數為ETXq-1。若ETXq>ETXq-1,說明后向鏈路成功傳輸所需的重傳次數更少,自后向節點發來數據包的速率大于發往前向節點的數據包的速率,數據包占用節點緩存的比例會加大,節點的負載加重;若ETXq

(7)

(8)

(9)

(10)

(11)

然后采用三個影響因子加權的方式得出本文路由策略的路由判據Meric值表達式,如式(12)所示。其中α、β、γ為權值參數,滿足α+β+γ=1,且α、β、γ均大于等于0。這樣就可以通過配置不同的路由判據權值來適應特定的網絡環境。

(12)

源節點計算出路由判據Metric后,將優先選擇Metric值最小的路徑進行數據發送。

3.3 仿真實驗和分析

本文使用OPNET Modeler 14.5網絡仿真工具,實驗環境:在1000m×1000m范圍內,分布5個固定節點和20個移動節點的隨機拓撲。以Random Waypoint模型模仿移動節點的固定速率隨機移動,Metric參數設定α=0.5,β=γ=0.25。實驗使用AODV協議,源節點業務流為CBR,數據包發送速率1Mbps,選取丟包率、吞吐量、網絡延時作為統計量,仿真時間60min。

圖1～圖3分別對Metric判據和跳數判據的丟包率、平均延時和吞吐量進行了對比。圖1可以看出前者的丟包率波動略小于后者,因為它選擇了更適合的判斷鏈路好壞的機制,這樣在網絡數據包的傳輸路徑分配就更合理,不會造成局部擁塞而導致大量丟包。

圖1 丟包率

在圖2中可以看出采用兩種判據的的網絡延時對比,在初始階段,Metric判據遲時稍微較大,因為在初期,探測鏈路信息的時候網絡中數據包較多而且都采用的泛洪式的查找機制。在網絡穩定后,采用Metric判據降低了延時。

圖2 網絡平均延時

圖3 吞吐率

圖3為吞吐率對比,在前15min兩個協議的吞吐率相當,此時網絡瓶頸并未出現。當仿真時間超過15min后,負載超過某一閾值,數據傳輸速率逐漸達到極限,由于Metric判據考慮了網絡鏈路質量、節點負載均衡等因素,采用改進的路由判據的路徑體現出一定優勢,此時路由選擇時將屏蔽負載過大的路徑,保持了較高的性能。

4 結語

針對AODV協議的最小跳數判據的不足,本文以傳統的ETX判據為基礎,考慮到無線Mesh網絡與Ad hoc網絡的不同之處,綜合鏈路參數因子對網絡的影響,提高了網絡的性能,對無線Mesh網絡的進一步應用研究具有參考價值。

[1] Hossain E, Kin K L. Wireless Mesh Networks Architectures and Protocols[M]. Heidelberg: Springer Science,2008:1-4.

[2] Zhang Y, Luo J J, Hu H L. Wireless Mesh Networking: Architecture, Protocols and Standards[M]. Auerbach,2007:10-13.

[3] 秦瑩瑩.無線Mesh網絡路由協議研究[J].軟件導刊,2012(11):99-101.

[4] Yang Y, Wang J, Kravets R. Designing routing metrics for mesh networks[C]//Proc. WiMesh,2005:134-140.

[5] 肖曉麗,張衛平,康忠毅,等.HWMP協議的路徑選擇參數的研究與改進[J].計算機工程與應用,2008,44(23):107-109.

[6] 易奇,左會軍,孫徐玲,等.基于樹形拓撲的無線Mesh網絡路由協議研究[J].計算機工程與設計,2010,31(9):1893-1897.

[7] 汪濤,崔遜學.無線Mesh網在炮兵野戰網絡系統中的應用研究[J].炮兵學院學報,2010(3):110-112.

[8] 何云強,丁在田,艾寶利.基于戰場通信環境多頻分級移動Ad Hoc網絡結構的研究[J].現代電子技術,2006(4):67-69.

[9] 楊斌,吳學智,陽昆.水面艦艇編隊的無線局域網研究及構建[J].艦船電子工程,2008,28(8):27-29.

[10] 秦軍,陳迪,袁翰林.無線Mesh網絡中的路由分析與設計[J].計算機技術與發展,2012,22(2):90-94.

[11] 陳敏.OPNET網絡仿真[M].北京:清華大學出版社,2004:98-101.

Routing Metric Based on Link State Factor of Wireless Mesh Network

QI Yibin1WANG Junjun2ZHU Huajin2LIU Xianjing2

(1. Information Department of Naval Headquarters, Beijing 100841)(2. No. 91469 Troops of PLA, Beijing 100841)

Aiming at the insufliciency of hop count metric of AODV protocol, based on traditional algorithm of ETX and combined with the parameters such as link quality, link interference and node load, a new path metric is put forward. The experimental results demonstrate that the new path selection algorithm program is helpful to improve network throughput, reduce packet loss rate and average delay, and effectively improve the network performance.

wireless mesh network, routing protocol, routing metric, link state

2013年8月11日,

2013年9月21日

亓沂濱,女,工程師,研究方向:計算機網絡、導航工程。王君珺,男,工程師,研究方向:通信裝備維修、計算機網絡。朱華進,男,工程師,研究方向:無線通信技術、導航工程。劉顯靜,男,助理工程師,研究方向:通信網的組網與管理。

TP393

10.3969/j.issn1672-9730.2014.02.019