基于IEEE802.11s的多射頻多信道無線mesh網(wǎng)絡(luò)路由判據(jù)的探究

熊道龍，郭見兵，顧燕飛

（1.武漢郵電科學(xué)研究院，湖北武漢，430074；2.武漢虹信通信技術(shù)有限責(zé)任公司，湖北武漢，430074)

0 前言

隨著視頻，圖像，語言等多媒體業(yè)務(wù)急速增長(zhǎng)，傳統(tǒng)的基于單信道的mesh網(wǎng)絡(luò)已經(jīng)無法滿足我們的需求。作為目前研究最廣泛的IEEE802.11s協(xié)議，其空時(shí)鏈路判據(jù)（ALM）也是基于單信道條件下的。那么如何在此基礎(chǔ)上拓展為適合于多信道條件的路由判據(jù)，是很多學(xué)者研究的目標(biāo)。

本文首先將簡(jiǎn)要的介紹IEEE802.11s路由技術(shù)，然后介紹當(dāng)前多信道MAC技術(shù)的研究進(jìn)展，最后主要分析比較加權(quán)累計(jì)期望傳輸時(shí)間（weighted cumulative expected transmission time，WCETT），干擾及信道切換（metric of interference and channel switching，MIC），歸一化的瓶頸鏈路容量（normalized bottleneck link capacity，NBLC），這3種多信道條件下的路由判據(jù)，并通過NS-2網(wǎng)絡(luò)仿真，更為直觀的將各種判據(jù)對(duì)網(wǎng)絡(luò)性能的影響展現(xiàn)出來。最后，結(jié)合理論分析及仿真結(jié)果，讓我們能夠明確每種判據(jù)的適用場(chǎng)合，并得出結(jié)論。

1 IEEE802.11s路由技術(shù)

混合無線網(wǎng)狀網(wǎng)協(xié)議（HWMP）是源自ad hoc的AODV路由協(xié)議與基于生成樹的路由協(xié)議的綜合。它結(jié)合了先驗(yàn)式和反應(yīng)式兩種構(gòu)件，適用于ad hoc、基礎(chǔ)結(jié)構(gòu)及混合WLAN網(wǎng)狀網(wǎng)等。它的優(yōu)勢(shì)就在于能夠靈活地適應(yīng)很多場(chǎng)景的需要；在網(wǎng)絡(luò)有根節(jié)點(diǎn)時(shí)，減少了網(wǎng)內(nèi)數(shù)據(jù)包的洪泛，使用按需路由發(fā)現(xiàn)時(shí)，減少了源端緩沖消息的需要。

協(xié)議所定義的路由判據(jù)是ALM，它反應(yīng)了數(shù)據(jù)在空中傳播的時(shí)間成本，具體計(jì)算如公式1，所示：

其中，O表示信道訪問開銷，Bt表示測(cè)試幀長(zhǎng)度，r表示數(shù)據(jù)傳輸長(zhǎng)度，ef 表示長(zhǎng)度為Bt的幀以r為速率傳輸失敗的概率。

2 WMN中MAC技術(shù)與多信道技術(shù)

IEEE802.11s在單信道的基礎(chǔ)上對(duì)MAC協(xié)議進(jìn)行了增強(qiáng)與改進(jìn)，它依舊無法滿足多信道應(yīng)用環(huán)境。因此，各種多信道MAC技術(shù)被提出來。

目前，根據(jù)信道選擇技術(shù)對(duì)現(xiàn)有的多信道MAC協(xié)議進(jìn)行分類。主要包括基于握手的信道選擇；信道跳躍；跨層信道分配。對(duì)于基于握手的信道選擇，包括動(dòng)態(tài)信道分配（DCA）、多信道CSMA MAC和多信道MAC。與802.11相同，它們通過在發(fā)送者和接收者之間交換控制信息實(shí)現(xiàn)握手機(jī)制。還有一些MMAC使用信道跳躍來完成兩個(gè)節(jié)點(diǎn)間的數(shù)據(jù)交換，如雙輪詢的接收端發(fā)起的信道跳躍（RICH-DP）和時(shí)隙種子信道跳躍（SSCH）。

關(guān)于信道分配問題，這是WMN中研究的一個(gè)熱點(diǎn)之一。簡(jiǎn)單來說，最佳信道分配問題，就是一個(gè)以對(duì)應(yīng)的圖形著色問題為基礎(chǔ)的“NP-Hard問題”。在多射頻多信道的WMN網(wǎng)絡(luò)中，路由和信道分配是相互依存的。路由取決于虛擬鏈路的容量，鏈路容量又由信道分配所決定。目前的信道分配方案種類繁多，在一定程度上改善了網(wǎng)絡(luò)的性能，但是面臨的挑戰(zhàn)是對(duì)于每個(gè)mesh路由器分配多少個(gè)射頻接口，依舊沒有給出具體的方案；另一方面的問題就在與，流量不均衡時(shí)應(yīng)該如何分配信道。這些問題都需要進(jìn)行深入細(xì)致的研究。

3 多射頻多信道路由判據(jù)

3.1 WCETT

WCETT是一種沖突感知的路由判據(jù)，在傳統(tǒng)的期望傳輸時(shí)間（ETT）的基礎(chǔ)上，綜合考慮了數(shù)據(jù)流內(nèi)的干擾問題，從而減少了在一個(gè)數(shù)據(jù)流所經(jīng)的路徑上使用同一信道的節(jié)點(diǎn)數(shù)。其表達(dá)式如公式2所示：

其中β是一個(gè)可調(diào)的參數(shù)，在0-1范圍內(nèi)。,xj是j信道在路徑p上使用的次數(shù)，以此來捕獲數(shù)據(jù)流內(nèi)的干擾。式中，部分是同樣的信道在路徑上出現(xiàn)次數(shù)的最大值，那些在鏈路的信道分配上更具多樣性的路徑具有更低的數(shù)據(jù)流內(nèi)干擾，而它們相應(yīng)這一項(xiàng)的權(quán)值也比較小。因此，公式中這一部分體現(xiàn)了流內(nèi)干擾的強(qiáng)度。

WCETT有兩方面的局限性。首先，雖然它確實(shí)捕捉到了數(shù)據(jù)流內(nèi)的干擾，但沒有顯式的考慮數(shù)據(jù)流間干擾。其次，WCETT不保序。因而缺乏有效的算法來計(jì)算最小代價(jià)路徑。為了保證路由中無環(huán)路，WCETT只能用在按需路由、源路由如LQSR或距離向量路由。對(duì)于這些問題MIC判據(jù)做出了一定的改進(jìn)。

3.2 MIC

干擾及信道切換路由判據(jù)（MIC），它是對(duì)WCETT的一個(gè)改進(jìn)，解決了WCETT不能捕捉到數(shù)據(jù)流間干擾問題，路徑P的MIC定義如公式3所示：

其中，N是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的個(gè)數(shù)，min(ETT)是網(wǎng)絡(luò)中最小的ETT值，這個(gè)最小值可以通過無線網(wǎng)卡最低傳輸速率來估算。而MIC的兩個(gè)要素：IRU(Interference—aware Resource Usage干擾感知型資源使用)和CSC(Channel Switching Cost信道切換權(quán)重)定義如下：

公式（4）中NI是在鏈路I上進(jìn)行數(shù)據(jù)傳輸時(shí)的一系列鄰接節(jié)點(diǎn)，也是干擾發(fā)生源；CH(I)表示分配給節(jié)點(diǎn)i用來傳輸數(shù)據(jù)的信道；prey(i)表示在路徑P上i節(jié)點(diǎn)前一跳的節(jié)點(diǎn)。IRU為，鏈路I上數(shù)據(jù)傳輸所消耗的鄰節(jié)點(diǎn)的信道時(shí)間的總和。因其傾向于選擇消耗鄰節(jié)點(diǎn)信道時(shí)間少的路徑，該判據(jù)捕捉到了數(shù)據(jù)流間的干擾；MIC的CSC部分表示了數(shù)據(jù)流內(nèi)的干擾。

值得注意的是，在真實(shí)網(wǎng)絡(luò)中直接應(yīng)用MIC，所得到的路徑權(quán)重函數(shù)不保序。因此我們只能利用按需路由獲得MIC的值。最新的研究表明，利用“虛節(jié)點(diǎn)”技術(shù)，可以解決MIC判據(jù)不保序的問題，由于篇幅的限制，本文不再贅述。

3.3 NBLC

NBLC路由判據(jù)通過綜合考慮了流量負(fù)載，信道容量，以及鏈路可用的剩余帶寬，極大地提升了系統(tǒng)的吞吐量。NBLC判據(jù)定義如下：獲得這些參數(shù)后，對(duì)于一條跳數(shù)為L(zhǎng)的路徑p定義判據(jù)NBLC判據(jù)如下：

在該路由判據(jù)中，每個(gè)節(jié)點(diǎn)需要周期性測(cè)量每個(gè)鏈接的RLC(residual link capacity)值，該值反應(yīng)的是鏈路的剩余帶寬，同時(shí)將這個(gè)值并廣播到k跳范圍內(nèi)所有的節(jié)點(diǎn)。同時(shí)計(jì)算一條路徑P上某個(gè)鏈接i的CEBT(Cumulative Expected Busy Time)值，其值等于路徑P上對(duì)鏈接i形成干擾的其他鏈接的ETT值之和，顯然干擾的鏈接應(yīng)該和鏈接i在同樣的信道上。代表了包被丟棄的概率。

總體上看，NBLC判據(jù)體現(xiàn)了一個(gè)瓶頸鏈路上可利用的剩余帶寬。一個(gè)更大的NBLC值表明一個(gè)更短，負(fù)載更小，更多可用信道的路徑。因此，根據(jù)選路算法，我們應(yīng)當(dāng)選擇NBLC值更大的那一個(gè)。

4 NS-2仿真及結(jié)果分析

仿真模擬采用NS-2仿真軟件[8]，每個(gè)節(jié)點(diǎn)有2個(gè)射頻口，每個(gè)接口有3個(gè)可用數(shù)據(jù)信道，1個(gè)控制信道。源節(jié)點(diǎn)隨機(jī)分配，仿真采用CBR流，每個(gè)CBR流是512Byte，每秒發(fā)送20個(gè)包。節(jié)點(diǎn)的傳輸范圍是250m，載波偵聽范圍是500m，為了排除移動(dòng)性的干擾，所有的N個(gè)節(jié)點(diǎn)是固定位置的。仿真范圍是1000m*1000m區(qū)域中分布的10*10的方格中。分析的主要參數(shù)為系統(tǒng)的平均吞吐量及端到端的時(shí)延。

上文公式中可調(diào)參數(shù)β設(shè)置為0.5，路由協(xié)議分為RMAODV與RANN兩種機(jī)制。根據(jù)IEEE802.11s默認(rèn)的HWMP路由協(xié)議，在NS2仿真平臺(tái)下，對(duì)AODV及RANN路由包進(jìn)行適當(dāng)?shù)脑O(shè)定，使之得能夠滿足仿真所需的要求。仿真結(jié)果如下圖所示：

結(jié)果分析

通過圖1，及圖2的仿真結(jié)果表明，WCETT，MIC，NBLC判據(jù)比傳統(tǒng)的單信道條件下的ALM判據(jù)在平均吞吐量上有更加優(yōu)越的性能，其中，MIC和NBLC判據(jù)對(duì)吞吐量的提升效果最明顯。根據(jù)圖3，和圖4的仿真結(jié)果，我們可以知道NBLC這種路由判據(jù)更加適合多節(jié)點(diǎn)，大范圍的網(wǎng)絡(luò)，其時(shí)延性相對(duì)其他的路由判據(jù)來說是最好的。在節(jié)點(diǎn)數(shù)相對(duì)較少的時(shí)候，WCETT，MIC，NBLC三種判據(jù)的端到端時(shí)延在AODV路由機(jī)制下差別不明顯。在RANN機(jī)制下，由于引入根節(jié)點(diǎn)，這種拓?fù)浣Y(jié)構(gòu)使得緊鄰根節(jié)點(diǎn)的鏈路能夠獲得更多的數(shù)據(jù)流量。因此，根據(jù)流量負(fù)載所設(shè)計(jì)的路由判據(jù)MIC及NBLC在擁有高吞吐量的同時(shí)也保持了較低的端到端時(shí)延，這與路由判據(jù)的設(shè)計(jì)思想是一致的。

圖1.AODV路由機(jī)制下的平均吞吐量

圖2.RANN路由機(jī)制下的平均吞吐量

圖3.AODV路由機(jī)制下的端到端延遲

圖4.RANN路由機(jī)制下的端到端延遲

5 結(jié)束語

本文主要討論了基于IEEE802.11s的無線mesh網(wǎng)絡(luò)中的路由判據(jù)問題。通過研究幾種多射頻，多信道條件下的路由判據(jù)，我們可以發(fā)現(xiàn)：在單信道條件下，ALM判據(jù)在單信道條件下是非常適合的；WCETT判據(jù)適合于多節(jié)點(diǎn)但數(shù)據(jù)量低的網(wǎng)絡(luò)；MIC判據(jù)適合于多鄰居同時(shí)干擾的網(wǎng)絡(luò)；NBLC判據(jù)適合于多節(jié)點(diǎn)高數(shù)據(jù)量的網(wǎng)絡(luò)。由于IEEE802.11s mesh網(wǎng)絡(luò)設(shè)計(jì)目標(biāo)就是為了支持高混合流量負(fù)載，因此MIC與NBLC判據(jù)更加適合IEEE802.11s mesh網(wǎng)絡(luò)。

未來研究的一個(gè)重點(diǎn)就是將多信道與路由技術(shù)相結(jié)合，信道分配取決于每條鏈路的負(fù)載能力，對(duì)于多射頻，多信道的無線mesh網(wǎng)絡(luò)而言，路由技術(shù)與信道分配技術(shù)是互相依賴的，下一步的工作將是研究信道分配與路由技術(shù)的聯(lián)合算法。

[1]Yan Zhang, Jijun Luo, Honglin Hu著，郭達(dá) 張勇等譯.無線網(wǎng)狀網(wǎng)：架構(gòu)、協(xié)議與標(biāo)準(zhǔn)[M].北京：電子工業(yè)出版社，2008.6.

[2]IEEE Std 802.1lTM-2011.IEEE standard for information technology- telecommunications and information exchange between systems.Local and metropolitan area network specific requirements-Part lI：Wireless LAN medium access control(MAC)and physical layer(PHY) specifications Amendment 10: Mesh Networking [S].Sep 2011.

[3]Sana Ghannay，F(xiàn)ethi Filali.Multi-radio multichannel routing metrics in IEEE 802.11s based wireless mesh networks[J],Ann.Telecommun.DOI 10.1007/s12243-011-0253-z May,2011.

[4]張鵬.無線Mesh網(wǎng)絡(luò)環(huán)境中多網(wǎng)關(guān)路由和切換機(jī)制的研究[D]，中國(guó)科學(xué)技術(shù)大學(xué)，2009.4.

[5]Ekram Hossain，Kin K.Leung著，易燕，李強(qiáng)等譯.無線Mesh網(wǎng)絡(luò)架構(gòu)與協(xié)議[M].北京：機(jī)械工業(yè)出版社，2009.5.

[6]Yang Y,Wang J,Kravets,R(2005)Designing routing metrics for mesh networks[J].In:Proc.of the IEEE workshop on wireless mesh networks(WiMesh).

[7]Liu T,Liao W(2008)On routing in multichannel wireless mesh networks:challenges and solutions[J].IEEE Network 22(1):13–18.

[8]黃化吉 秦麗嬌等著.NS網(wǎng)絡(luò)模擬和協(xié)議仿真[M].北京:人民郵電出版社，2010.5