基于鏈路狀態(tài)因子的無(wú)線MESH網(wǎng)絡(luò)路由判據(jù)研究*

亓沂濱 王君珺 朱華進(jìn) 劉顯靜

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

基于鏈路狀態(tài)因子的無(wú)線MESH網(wǎng)絡(luò)路由判據(jù)研究*

亓沂濱1王君珺2朱華進(jìn)2劉顯靜2

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

針對(duì)AODV協(xié)議的跳數(shù)路徑判據(jù)的不足,以傳統(tǒng)的ETX判據(jù)為基礎(chǔ),將鏈路質(zhì)量、鏈路干擾和節(jié)點(diǎn)負(fù)載等鏈路狀態(tài)參數(shù)相結(jié)合,提出新的路徑判據(jù)計(jì)算方案,通過(guò)仿真實(shí)驗(yàn)證明,新的路由判據(jù)計(jì)算方案的路徑選擇算法有助于提高網(wǎng)絡(luò)吞吐量,降低丟包率和平均延時(shí),對(duì)于提高網(wǎng)絡(luò)性能是行之有效的。

無(wú)線網(wǎng)狀網(wǎng); 路由協(xié)議; 路由判據(jù); 鏈路狀態(tài)

Class Number TP393

1 引言

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

在無(wú)線網(wǎng)狀網(wǎng)中,通信網(wǎng)絡(luò)提供高質(zhì)量、高效率服務(wù)的關(guān)鍵技術(shù)之一是路由算法,而路由算法的性能高低取決于路由判據(jù)。傳統(tǒng)Ad hoc路由選擇是根據(jù)跳數(shù)(hop count)來(lái)選擇路由,這種選路方式?jīng)]有綜合考慮到信道質(zhì)量及多信道下的鏈路干擾等問(wèn)題,因此難以達(dá)到無(wú)線網(wǎng)狀網(wǎng)在網(wǎng)絡(luò)容量和傳輸性能上的要求。

2 問(wèn)題分析

跳數(shù)判據(jù)是Ad hoc網(wǎng)絡(luò)中使用最廣泛的一種路由判據(jù),DSDV、AODV等路由協(xié)議都采用最小跳數(shù)作為路由判據(jù)[4]。跳數(shù)判據(jù)的最小權(quán)重路徑是從源節(jié)點(diǎn)到目的節(jié)點(diǎn)跳數(shù)最小的路徑。這種算法原理是將報(bào)文在一條路徑上所經(jīng)過(guò)的跳數(shù)進(jìn)行簡(jiǎn)單累加。

在無(wú)線Mesh網(wǎng)絡(luò)中最小跳數(shù)判據(jù)不太適用,原因在于最小跳數(shù)路徑準(zhǔn)則沒(méi)有考慮到其下層物理信道特性的變化對(duì)MAC層接入性能的影響等因素,以及上層對(duì)QoS要求,造成所選路徑無(wú)法適應(yīng)底層性能的變化,也可能造成傳輸層的較大波動(dòng)。此外,就無(wú)線信道而言,在通信期間即使鏈路環(huán)境沒(méi)有產(chǎn)生變化,最優(yōu)路徑不一定是跳數(shù)最小的路徑。在誤碼率相同條件下,單跳傳輸?shù)木嚯x越長(zhǎng),信道數(shù)據(jù)傳輸速率就越低,也就是說(shuō)短距離的非最短路徑也可能比長(zhǎng)距離的最短路徑的吞吐量傳或輸速率高。

目前改進(jìn)的路由判據(jù)主要有ETX(期望傳輸次數(shù))、ETT(期望傳輸時(shí)間)、ENT(有效傳輸數(shù)量)等[5],這些路由判據(jù)往往是針對(duì)特定路由協(xié)議設(shè)計(jì)的,本文旨在研究一種普遍適合無(wú)線Mesh網(wǎng)絡(luò)的路由判據(jù)。

3 新的路由判據(jù)的計(jì)算方案

3.1 傳統(tǒng)ETX算法的研究

評(píng)判一個(gè)路由協(xié)議的性能好壞,最重要的兩個(gè)指標(biāo)是丟包率和端到端時(shí)延[6]。丟包率很大程度上取決于鏈路的質(zhì)量,同時(shí)節(jié)點(diǎn)的擁塞也可能導(dǎo)致某些數(shù)據(jù)包因阻塞而丟失。ETX算法中,網(wǎng)絡(luò)中的節(jié)點(diǎn)每隔1s以1Mbps的速率廣播探測(cè)數(shù)據(jù)包,所有的鄰居節(jié)點(diǎn)可以通過(guò)接收這些探測(cè)數(shù)據(jù)包來(lái)計(jì)算丟包率。因此,可以通過(guò)回復(fù)消息得到前向傳輸丟包率df和后向傳輸丟包率dr。依據(jù)概率公式,可得到鏈路的丟包率p如式(1)所示。

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

(1)

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

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

(2)

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

(3)

ETX算法的存在兩點(diǎn)不足: 1) ETX沒(méi)有直接考慮鏈路的速率和節(jié)點(diǎn)負(fù)載; 2) ETX算法沒(méi)有考慮使用相同信道傳輸?shù)母蓴_問(wèn)題[7]。為此引入綜合考慮鏈路質(zhì)量、鏈路干擾、節(jié)點(diǎn)負(fù)載均衡三個(gè)方面因素的路由度量標(biāo)準(zhǔn)。

3.2 綜合路由度量標(biāo)準(zhǔn)的計(jì)算方案

1) 鏈路質(zhì)量因子Q

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

(4)

2) 鏈路干擾因子I

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

(5)

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

(6)

3) 節(jié)點(diǎn)負(fù)載因子L

在一條傳輸路徑中,若某個(gè)中間節(jié)點(diǎn)數(shù)據(jù)處理能力達(dá)到極限就會(huì)出現(xiàn)傳輸擁塞,那么該節(jié)點(diǎn)會(huì)嚴(yán)重影響整條路由的數(shù)據(jù)傳輸速率。當(dāng)一個(gè)中間節(jié)點(diǎn)收到數(shù)據(jù)包需要轉(zhuǎn)發(fā)或處理時(shí),會(huì)在本地將數(shù)據(jù)包緩存,然后再發(fā)往下一節(jié)點(diǎn)。如果由于網(wǎng)絡(luò)擁塞沖突等原因,導(dǎo)致不能建立連接,或數(shù)據(jù)包不能順利發(fā)送至下一節(jié)點(diǎn),則該節(jié)點(diǎn)會(huì)將需要轉(zhuǎn)發(fā)的數(shù)據(jù)包暫時(shí)緩存本地。

一個(gè)節(jié)點(diǎn)的緩存占用比例可以在一定程度體現(xiàn)該節(jié)點(diǎn)的擁塞程度[9]。下面將提出一種使用期望傳輸次數(shù)來(lái)大致估算節(jié)點(diǎn)緩存的占用比例,繼而可以在選擇路由時(shí)盡可能保證節(jié)點(diǎn)的負(fù)載均衡。

取某條路由上的一個(gè)中間節(jié)點(diǎn)q,假設(shè)該節(jié)點(diǎn)的下一節(jié)點(diǎn)路徑即前向鏈路的期望傳輸次數(shù)為ETXq,上一節(jié)點(diǎn)路徑即后向鏈路的期望傳輸次數(shù)為ETXq-1。若ETXq>ETXq-1,說(shuō)明后向鏈路成功傳輸所需的重傳次數(shù)更少,自后向節(jié)點(diǎn)發(fā)來(lái)數(shù)據(jù)包的速率大于發(fā)往前向節(jié)點(diǎn)的數(shù)據(jù)包的速率,數(shù)據(jù)包占用節(jié)點(diǎn)緩存的比例會(huì)加大,節(jié)點(diǎn)的負(fù)載加重;若ETXq

(7)

(8)

(9)

(10)

(11)

然后采用三個(gè)影響因子加權(quán)的方式得出本文路由策略的路由判據(jù)Meric值表達(dá)式,如式(12)所示。其中α、β、γ為權(quán)值參數(shù),滿足α+β+γ=1,且α、β、γ均大于等于0。這樣就可以通過(guò)配置不同的路由判據(jù)權(quán)值來(lái)適應(yīng)特定的網(wǎng)絡(luò)環(huán)境。

(12)

源節(jié)點(diǎn)計(jì)算出路由判據(jù)Metric后,將優(yōu)先選擇Metric值最小的路徑進(jìn)行數(shù)據(jù)發(fā)送。

3.3 仿真實(shí)驗(yàn)和分析

本文使用OPNET Modeler 14.5網(wǎng)絡(luò)仿真工具,實(shí)驗(yàn)環(huán)境:在1000m×1000m范圍內(nèi),分布5個(gè)固定節(jié)點(diǎn)和20個(gè)移動(dòng)節(jié)點(diǎn)的隨機(jī)拓?fù)?。以Random Waypoint模型模仿移動(dòng)節(jié)點(diǎn)的固定速率隨機(jī)移動(dòng),Metric參數(shù)設(shè)定α=0.5,β=γ=0.25。實(shí)驗(yàn)使用AODV協(xié)議,源節(jié)點(diǎn)業(yè)務(wù)流為CBR,數(shù)據(jù)包發(fā)送速率1Mbps,選取丟包率、吞吐量、網(wǎng)絡(luò)延時(shí)作為統(tǒng)計(jì)量,仿真時(shí)間60min。

圖1～圖3分別對(duì)Metric判據(jù)和跳數(shù)判據(jù)的丟包率、平均延時(shí)和吞吐量進(jìn)行了對(duì)比。圖1可以看出前者的丟包率波動(dòng)略小于后者,因?yàn)樗x擇了更適合的判斷鏈路好壞的機(jī)制,這樣在網(wǎng)絡(luò)數(shù)據(jù)包的傳輸路徑分配就更合理,不會(huì)造成局部擁塞而導(dǎo)致大量丟包。

圖1 丟包率

在圖2中可以看出采用兩種判據(jù)的的網(wǎng)絡(luò)延時(shí)對(duì)比,在初始階段,Metric判據(jù)遲時(shí)稍微較大,因?yàn)樵诔跗?探測(cè)鏈路信息的時(shí)候網(wǎng)絡(luò)中數(shù)據(jù)包較多而且都采用的泛洪式的查找機(jī)制。在網(wǎng)絡(luò)穩(wěn)定后,采用Metric判據(jù)降低了延時(shí)。

圖2 網(wǎng)絡(luò)平均延時(shí)

圖3 吞吐率

圖3為吞吐率對(duì)比,在前15min兩個(gè)協(xié)議的吞吐率相當(dāng),此時(shí)網(wǎng)絡(luò)瓶頸并未出現(xiàn)。當(dāng)仿真時(shí)間超過(guò)15min后,負(fù)載超過(guò)某一閾值,數(shù)據(jù)傳輸速率逐漸達(dá)到極限,由于Metric判據(jù)考慮了網(wǎng)絡(luò)鏈路質(zhì)量、節(jié)點(diǎn)負(fù)載均衡等因素,采用改進(jìn)的路由判據(jù)的路徑體現(xiàn)出一定優(yōu)勢(shì),此時(shí)路由選擇時(shí)將屏蔽負(fù)載過(guò)大的路徑,保持了較高的性能。

4 結(jié)語(yǔ)

針對(duì)AODV協(xié)議的最小跳數(shù)判據(jù)的不足,本文以傳統(tǒng)的ETX判據(jù)為基礎(chǔ),考慮到無(wú)線Mesh網(wǎng)絡(luò)與Ad hoc網(wǎng)絡(luò)的不同之處,綜合鏈路參數(shù)因子對(duì)網(wǎng)絡(luò)的影響,提高了網(wǎng)絡(luò)的性能,對(duì)無(wú)線Mesh網(wǎng)絡(luò)的進(jìn)一步應(yīng)用研究具有參考價(jià)值。

[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] 秦瑩瑩.無(wú)線Mesh網(wǎng)絡(luò)路由協(xié)議研究[J].軟件導(dǎo)刊,2012(11):99-101.

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

[5] 肖曉麗,張衛(wèi)平,康忠毅,等.HWMP協(xié)議的路徑選擇參數(shù)的研究與改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(23):107-109.

[6] 易奇,左會(huì)軍,孫徐玲,等.基于樹(shù)形拓?fù)涞臒o(wú)線Mesh網(wǎng)絡(luò)路由協(xié)議研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2010,31(9):1893-1897.

[7] 汪濤,崔遜學(xué).無(wú)線Mesh網(wǎng)在炮兵野戰(zhàn)網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用研究[J].炮兵學(xué)院學(xué)報(bào),2010(3):110-112.

[8] 何云強(qiáng),丁在田,艾寶利.基于戰(zhàn)場(chǎng)通信環(huán)境多頻分級(jí)移動(dòng)Ad Hoc網(wǎng)絡(luò)結(jié)構(gòu)的研究[J].現(xiàn)代電子技術(shù),2006(4):67-69.

[9] 楊斌,吳學(xué)智,陽(yáng)昆.水面艦艇編隊(duì)的無(wú)線局域網(wǎng)研究及構(gòu)建[J].艦船電子工程,2008,28(8):27-29.

[10] 秦軍,陳迪,袁翰林.無(wú)線Mesh網(wǎng)絡(luò)中的路由分析與設(shè)計(jì)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2012,22(2):90-94.

[11] 陳敏.OPNET網(wǎng)絡(luò)仿真[M].北京:清華大學(xué)出版社,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日

亓沂濱,女,工程師,研究方向:計(jì)算機(jī)網(wǎng)絡(luò)、導(dǎo)航工程。王君珺,男,工程師,研究方向:通信裝備維修、計(jì)算機(jī)網(wǎng)絡(luò)。朱華進(jìn),男,工程師,研究方向:無(wú)線通信技術(shù)、導(dǎo)航工程。劉顯靜,男,助理工程師,研究方向:通信網(wǎng)的組網(wǎng)與管理。

TP393

10.3969/j.issn1672-9730.2014.02.019