基于IEEE802.11s的多射頻多信道無線mesh網絡路由判據的探究

熊道龍，郭見兵，顧燕飛

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

0 前言

隨著視頻，圖像，語言等多媒體業務急速增長，傳統的基于單信道的mesh網絡已經無法滿足我們的需求。作為目前研究最廣泛的IEEE802.11s協議，其空時鏈路判據（ALM）也是基于單信道條件下的。那么如何在此基礎上拓展為適合于多信道條件的路由判據，是很多學者研究的目標。

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

1 IEEE802.11s路由技術

混合無線網狀網協議（HWMP）是源自ad hoc的AODV路由協議與基于生成樹的路由協議的綜合。它結合了先驗式和反應式兩種構件，適用于ad hoc、基礎結構及混合WLAN網狀網等。它的優勢就在于能夠靈活地適應很多場景的需要；在網絡有根節點時，減少了網內數據包的洪泛，使用按需路由發現時，減少了源端緩沖消息的需要。

協議所定義的路由判據是ALM，它反應了數據在空中傳播的時間成本，具體計算如公式1，所示：

其中，O表示信道訪問開銷，Bt表示測試幀長度，r表示數據傳輸長度，ef 表示長度為Bt的幀以r為速率傳輸失敗的概率。

2 WMN中MAC技術與多信道技術

IEEE802.11s在單信道的基礎上對MAC協議進行了增強與改進，它依舊無法滿足多信道應用環境。因此，各種多信道MAC技術被提出來。

目前，根據信道選擇技術對現有的多信道MAC協議進行分類。主要包括基于握手的信道選擇；信道跳躍；跨層信道分配。對于基于握手的信道選擇，包括動態信道分配（DCA）、多信道CSMA MAC和多信道MAC。與802.11相同，它們通過在發送者和接收者之間交換控制信息實現握手機制。還有一些MMAC使用信道跳躍來完成兩個節點間的數據交換，如雙輪詢的接收端發起的信道跳躍（RICH-DP）和時隙種子信道跳躍（SSCH）。

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

3 多射頻多信道路由判據

3.1 WCETT

WCETT是一種沖突感知的路由判據，在傳統的期望傳輸時間（ETT）的基礎上，綜合考慮了數據流內的干擾問題，從而減少了在一個數據流所經的路徑上使用同一信道的節點數。其表達式如公式2所示：

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

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

3.2 MIC

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

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

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

值得注意的是，在真實網絡中直接應用MIC，所得到的路徑權重函數不保序。因此我們只能利用按需路由獲得MIC的值。最新的研究表明，利用“虛節點”技術，可以解決MIC判據不保序的問題，由于篇幅的限制，本文不再贅述。

3.3 NBLC

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

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

總體上看，NBLC判據體現了一個瓶頸鏈路上可利用的剩余帶寬。一個更大的NBLC值表明一個更短，負載更小，更多可用信道的路徑。因此，根據選路算法，我們應當選擇NBLC值更大的那一個。

4 NS-2仿真及結果分析

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

上文公式中可調參數β設置為0.5，路由協議分為RMAODV與RANN兩種機制。根據IEEE802.11s默認的HWMP路由協議，在NS2仿真平臺下，對AODV及RANN路由包進行適當的設定，使之得能夠滿足仿真所需的要求。仿真結果如下圖所示：

結果分析

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

圖1.AODV路由機制下的平均吞吐量

圖2.RANN路由機制下的平均吞吐量

圖3.AODV路由機制下的端到端延遲

圖4.RANN路由機制下的端到端延遲

5 結束語

本文主要討論了基于IEEE802.11s的無線mesh網絡中的路由判據問題。通過研究幾種多射頻，多信道條件下的路由判據，我們可以發現：在單信道條件下，ALM判據在單信道條件下是非常適合的；WCETT判據適合于多節點但數據量低的網絡；MIC判據適合于多鄰居同時干擾的網絡；NBLC判據適合于多節點高數據量的網絡。由于IEEE802.11s mesh網絡設計目標就是為了支持高混合流量負載，因此MIC與NBLC判據更加適合IEEE802.11s mesh網絡。

未來研究的一個重點就是將多信道與路由技術相結合，信道分配取決于每條鏈路的負載能力，對于多射頻，多信道的無線mesh網絡而言，路由技術與信道分配技術是互相依賴的，下一步的工作將是研究信道分配與路由技術的聯合算法。

[1]Yan Zhang, Jijun Luo, Honglin Hu著，郭達 張勇等譯.無線網狀網：架構、協議與標準[M].北京：電子工業出版社，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，Fethi 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網絡環境中多網關路由和切換機制的研究[D]，中國科學技術大學，2009.4.

[5]Ekram Hossain，Kin K.Leung著，易燕，李強等譯.無線Mesh網絡架構與協議[M].北京：機械工業出版社，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網絡模擬和協議仿真[M].北京:人民郵電出版社，2010.5