劉顯靜，吳學(xué)智，沈釗

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

0 引言

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

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

1 問題分析

跳數(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ù)最小的路徑。這種算法原理是將報文在一條路徑上所經(jīng)過的跳數(shù)進(jìn)行簡單累加。

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

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

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

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

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

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

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

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

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

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

研究證明ETX能夠很好的反應(yīng)鏈路的質(zhì)量，使用ETX作為鏈路質(zhì)量標(biāo)準(zhǔn)是非常適合WMN的。為了解決路由的單一鏈路瓶頸問題，本文設(shè)定一個可動態(tài)配置的丟包率門限值Pd，如果當(dāng)某條鏈路的丟包率大于Pd，那么該鏈路將直接被放棄，Pd可以根據(jù)當(dāng)前網(wǎng)絡(luò)的鏈路質(zhì)量來配置。因此可以得到整條路由的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)絡(luò)的全局來講，可以使得流量更加均勻，有利于提高網(wǎng)絡(luò)吞吐量。由式（5）可以得到整條路由的干擾因子I，如式（6）所示。

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

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

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

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

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

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

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

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

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

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

圖1 丟包率

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

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

圖3 吞吐量

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

4 結(jié)束語

針對AODV協(xié)議的最小跳數(shù)判據(jù)的不足，本文以傳統(tǒng)的ETX判據(jù)為基礎(chǔ)，考慮到無線Mesh網(wǎng)絡(luò)與Ad hoc網(wǎng)絡(luò)的不同之處，綜合鏈路參數(shù)因子對網(wǎng)絡(luò)的影響，提高了網(wǎng)絡(luò)的性能，對無線Mesh網(wǎng)絡(luò)的進(jìn)一步應(yī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)絡(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.

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

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