無線網(wǎng)狀網(wǎng)路由協(xié)議的路由判據(jù)研究與改進

劉顯靜，吳學智，沈釗

（1. 海軍通信工程技術研究中心，武漢 430033; 2. 華中科技大學電信系, 武漢 430033）

0 引言

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

在無線Mesh網(wǎng)絡中，高性能路由算法是保證通信網(wǎng)絡提供高效率、高質量服務的關鍵技術之一，而路由判據(jù)是決定路由算法性能高低的基礎。傳統(tǒng)Ad hoc路由選擇是依據(jù)跳數(shù)（hop count）來選擇路由的，這種方法沒有考慮信道質量問題以及多信道環(huán)境下鏈路的干擾等問題，所以最終難以滿足無線Mesh網(wǎng)絡在網(wǎng)絡容量和傳輸性能上的要求。

1 問題分析

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

在無線Mesh網(wǎng)絡最小跳數(shù)判據(jù)不太適用，原因在于最小跳數(shù)路徑準則沒有考慮到其下層物理信道特性的變化對MAC層接入性能的影響等因素，以及上層對QoS要求，造成所選路徑無法適應底層性能的變化，也可能造成傳輸層的較大波動。此外，就無線信道而言，即使信道環(huán)境在通信期間沒有產(chǎn)生變化，最短路徑也未必是最優(yōu)路徑。在同樣的誤碼率條件下，傳輸距離越長，所支持的數(shù)據(jù)傳輸速率就越低，也就意味著長距離的最短路徑比短距離的非最短路徑的傳輸速率或吞吐量低。

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

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

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

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

如果一條鏈路經(jīng)過k次嘗試后成功傳輸，那么該鏈路的傳輸成功的概率S(k)為：

結合式（1）和式（2），可得出鏈路傳輸次數(shù)的數(shù)學期望即ETX。具體計算如式（3）所示。

ETX算法的存在兩點不足：第一，ETX沒有直接考慮鏈路的速率和節(jié)點負載；第二，ETX算法沒有考慮使用相同信道傳輸?shù)母蓴_問題。為此引入綜合考慮鏈路質量、鏈路干擾、節(jié)點負載均衡三個方面因素的路由度量標準。

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

1）鏈路質量因子Q

研究證明ETX能夠很好的反應鏈路的質量，使用ETX作為鏈路質量標準是非常適合WMN的。為了解決路由的單一鏈路瓶頸問題，本文設定一個可動態(tài)配置的丟包率門限值Pd，如果當某條鏈路的丟包率大于Pd，那么該鏈路將直接被放棄，Pd可以根據(jù)當前網(wǎng)絡的鏈路質量來配置。因此可以得到整條路由的Q如式（4）所示。

2）鏈路干擾因子I

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

I可以理解為鏈路與受他干擾的其他鏈路的信道競爭情況。顯然I越小，即鏈路對信道的占用越少，那么其他鏈路可以傳輸?shù)臄?shù)據(jù)就越多。雖然因子I犧牲了本鏈路的平均傳輸速率，但是有利于鏈路e的干擾區(qū)域內(nèi)可能存在的其他互不干擾的鏈路的傳輸。從無線Mesh網(wǎng)絡的全局來講，可以使得流量更加均勻，有利于提高網(wǎng)絡吞吐量。由式（5）可以得到整條路由的干擾因子I，如式（6）所示。

3）節(jié)點負載因子L

在一條完整的傳輸路由中，若某個中間節(jié)點出現(xiàn)傳輸擁塞，那么這個節(jié)點會對整條路由的傳輸產(chǎn)生很大的負面影響。一個中間節(jié)點在收到需要轉發(fā)的數(shù)據(jù)包后，會將數(shù)據(jù)包本地緩存，然后再向下一節(jié)點進行發(fā)送。若因為沖突等種種原因，連接不能建立，或數(shù)據(jù)包遲遲不能順利到達下一節(jié)點，該節(jié)點只能將需要轉發(fā)的數(shù)據(jù)包暫時保存在緩存中。

一個節(jié)點阻塞程度可以通過該節(jié)點的緩存占用來衡量。下面將提出一種使用ETX來大致估算節(jié)點緩存的變化趨勢，從而可以在進行路由選擇時盡量保證節(jié)點的負載均衡。

假設一條路由上有一個中間節(jié)點q，設該節(jié)點的前向鏈路的期望傳輸次數(shù)為ETXq，后向鏈路的期望傳輸次數(shù)為ETXq-1。若ETXq>ETXq-1，說明后向鏈路成功傳輸所需的重傳次數(shù)更少。此時，來自上一跳節(jié)點的數(shù)據(jù)包的速率高于發(fā)往下一跳節(jié)點的數(shù)據(jù)包的速率，節(jié)點緩存的數(shù)據(jù)會越來越多，節(jié)點負載加重；若ETXq

將以上所述的三個路由判據(jù)因子統(tǒng)一度量化后分別得到Q'，I'，L'。具體方法為：當路由發(fā)現(xiàn)過程結束后，源節(jié)點一共獲得了M條可選路由。以ETXd為例，這M條路由的ETXd分別為ETXd1，ETXd2，ETXd3……ETXdM，則其中一條路由K統(tǒng)一度量化后的鏈路質量因子為ETXdK'，計算如式（9）所示。用同樣方法可以統(tǒng)一度量化路由K的干擾因子IK'和負載因子LK'，如式（10）所示。

然后即可得到本路由機制的路由判據(jù)Metric，如式（11）所示。其中α，β，γ為權重參數(shù)，滿足α+β+γ=1，且α，β，γ均大于等于0。這樣就可以通過配置不同的路由判據(jù)權重來適應不同的網(wǎng)絡環(huán)境。

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

3 仿真實驗和分析

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

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

圖1 丟包率

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

圖2 網(wǎng)絡平均延時

圖3 吞吐量

圖3所示為吞吐率對比，在前15 min兩個協(xié)議的吞吐率相當，此時網(wǎng)絡瓶頸并未出現(xiàn)。當仿真時間超過15 min后，負載超過一定門限，網(wǎng)絡傳輸開始出現(xiàn)瓶頸，由于Metric判據(jù)考慮了網(wǎng)絡鏈路質量、節(jié)點負載均衡等因素，逐漸體現(xiàn)出優(yōu)勢，此時路由選擇時將避開負載過重的路由，保持了較高的性能。

4 結束語

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

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

[2] Zhang Y, Luo JJ, Hu HL. Wireless Mesh Networking：Architecture, Protocols and Standards[M]. Auerbach,2007: 10-13.

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

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

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

[6] 彭鋒華, 周學軍. 海軍通信需求分析理論研究[J].船電技術, 2012, 32(1): 57-59.