張志超，鄢楚平，苑海濤，張鈞媛，計 龍，張立茹

(華北計算技術(shù)研究所，北京 100083)

0 引言

無線 Mesh網(wǎng)絡(luò)(Wireless Mesh Network，WMN)是一種多跳、具有自組織和自愈特點的寬帶無線網(wǎng)絡(luò)，是一種高容量、高速率的分布式網(wǎng)絡(luò)。目前主要認(rèn)為，WMN是一種由無線鏈路連接路由器和終端設(shè)備的固定/弱移動無線網(wǎng)絡(luò)，是Internet的無線版本。WMN可以看成是WLAN(單跳)和移動Ad Hoc網(wǎng)絡(luò)(多跳)的融合，且發(fā)揮了兩者的優(yōu)勢，是一種新型的可以解決“最后一英里”瓶頸問題的分布式網(wǎng)絡(luò)。

對于多收發(fā)信機多信道MAC協(xié)議，不少學(xué)者進(jìn)行了研究。Wu等人提出了一種動態(tài)分配信道的協(xié)議(Dynamic Channel Assignment，DCA)［12］，它使用一個信道傳輸信令，其他信道傳輸數(shù)據(jù)，每個節(jié)點使用2個收發(fā)信機，因為一個收發(fā)信機一直在監(jiān)聽信道，可以避免多信道隱藏終端問題。該協(xié)議不需同步，信令開銷小。但是，控制信令獨占一個信道浪費極大;Sana Ghannay等人提出了一種聚合路由和信道分配的機制(Joint Routing and Channel Assignment Protocol，JRCAP)［13］，將全網(wǎng)按照聚類算法分簇(Cluster)，對于每一簇選定一個固定信道，而每對通信鏈路的選擇在路由算法中協(xié)商好，之后跳變到協(xié)商好的信道傳輸數(shù)據(jù)，若協(xié)商失敗，則用固定信道傳輸。其特色是使大網(wǎng)變小網(wǎng)，但是處于網(wǎng)簇之間的節(jié)點負(fù)載較大，容易造成瓶頸，使全網(wǎng)的吞吐量上不去;Chia-Yu ku等人觀測到網(wǎng)卡的增多并不能帶來吞吐量的線性增加，提出了采用少量收發(fā)信機替代每個信道一個收發(fā)信機的機制來降低成本［14］。

除了如Ad Hoc網(wǎng)絡(luò)中存在的暴露終端和隱藏終端問題之外，無線Mesh網(wǎng)絡(luò)的MAC還存在新的問題，表現(xiàn)在3個方面:

(1)在無線環(huán)境中，每一跳如果都需要競爭，就會產(chǎn)生大量不確定的延時，多跳后累積的延時可能會非常大;

(2)對于采用單收發(fā)信機多信道的MAC，不停的信道切換會導(dǎo)致開銷變大;

(3)當(dāng)節(jié)點移動導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時，下一跳的路由選擇機制是個很大的問題，在多跳環(huán)境中，這個問題更加突出［15］。

本文采用基于多收發(fā)信機的設(shè)計方法來解決作為骨干Mesh網(wǎng)絡(luò)的帶寬逐跳衰減問題，進(jìn)而提高全網(wǎng)的吞吐量，降低網(wǎng)絡(luò)時延。

1 802.11s無線Mesh協(xié)議架構(gòu)

1.1 無線Mesh網(wǎng)絡(luò)體系結(jié)構(gòu)

802.11 s中定義的無線Mesh網(wǎng)絡(luò)架構(gòu)如圖1所示?；痉?wù)集BSS無需直接連到有線網(wǎng)絡(luò)，可以通過多跳連接最終接入到有線網(wǎng)，即網(wǎng)絡(luò)中只要有節(jié)點可以接入Internet網(wǎng)絡(luò)即可。在802.11s中定義了3類新節(jié)點:Mesh節(jié)點(MP)是支持無線Mesh服務(wù)的802.11實體，其作用是作為中繼節(jié)點;Mesh接入點(MAP)是作為接入點的 MP;Mesh門橋節(jié)點(MPP)是MAC協(xié)議數(shù)據(jù)單元(MSDU)接入或離開無線Mesh網(wǎng)絡(luò)的橋接。

圖1 無線Mesh網(wǎng)絡(luò)架構(gòu)

(1)骨干網(wǎng)絡(luò)。

無線Mesh網(wǎng)絡(luò)從邏輯上可以理解為一個二層網(wǎng)絡(luò)，其中由無線MP組成的網(wǎng)絡(luò)架構(gòu)是網(wǎng)絡(luò)的核心，因此也被稱為骨干網(wǎng)絡(luò)。骨干網(wǎng)絡(luò)是無線Mesh網(wǎng)絡(luò)的一種網(wǎng)絡(luò)架構(gòu)，這與WLAN類似，不過是將有線的骨干節(jié)點替換為無線MP。

(2)客戶端網(wǎng)絡(luò)。

與骨干網(wǎng)絡(luò)相對的便是有客戶端組成的客戶端網(wǎng)絡(luò)，它是無線Mesh網(wǎng)絡(luò)的二層網(wǎng)絡(luò)。在WMN中，由于客戶端也具備信息收發(fā)功能，所以它們之間也可以進(jìn)行有效的通信，所以客戶端也可以組成一個網(wǎng)絡(luò)。在這種網(wǎng)絡(luò)中沒有明確的網(wǎng)絡(luò)架構(gòu)，其本質(zhì)就是一個純Ad Hoc網(wǎng)絡(luò)。

(3)混合無線Mesh網(wǎng)。

混合無線Mesh網(wǎng)就是有骨干網(wǎng)絡(luò)與客戶端網(wǎng)絡(luò)混合而成的WMN網(wǎng)絡(luò)，這是我們最常見的一種無線Mesh網(wǎng)絡(luò)架構(gòu)。MP節(jié)點組成了整個網(wǎng)絡(luò)的骨干架構(gòu)，一般是靜態(tài)而且變化較小。移動節(jié)點通過MAP接入網(wǎng)絡(luò)，具備可移動性，節(jié)點間也可以進(jìn)行有效的通信。

1.2 802.11s多跳性能仿真分析

為了對802.11s無線 Mesh協(xié)議［1］的多跳性能進(jìn)行摸底，對仿真工具NS3［2］自帶的Mesh協(xié)議進(jìn)行了多跳測試，圖2為隨著跳數(shù)的增加，全網(wǎng)的吞吐量整體呈指數(shù)下降的趨勢，即逐跳減半，嚴(yán)重限制了傳統(tǒng)Mesh網(wǎng)絡(luò)的可擴展性和實用性。

圖2 多跳后的吞吐量

1.3 干擾模式圖

假設(shè)每個無線Mesh節(jié)點采用同種網(wǎng)卡、全向天線，發(fā)射功率、天線增益、調(diào)制速率都相同，則每個節(jié)點射頻覆蓋范圍都相同，可以近似為一個圓。單收發(fā)信機的鏈狀拓?fù)浣Y(jié)構(gòu)下的干擾模式如圖3所示，處于網(wǎng)絡(luò)中間的節(jié)點(如B、C、D)射頻覆蓋范圍有大量的重疊，造成多個節(jié)點競爭使用信道，在節(jié)點數(shù)量密集的無線網(wǎng)絡(luò)環(huán)境中，會使端到端的吞吐量逐跳地快速衰減。

圖3 單收發(fā)信機鏈狀拓?fù)浣Y(jié)構(gòu)下的干擾模式示意圖

2 基于雙收發(fā)信機的Mesh組網(wǎng)算法

2.1 雙收發(fā)信機鏈狀拓?fù)浣Y(jié)構(gòu)下的無干擾信道分配模式

802.11網(wǎng)絡(luò)2.4GHz、ISM 頻段內(nèi)理論上可以找到3個正交的無線信道(頻率上不相重疊的信道，如信道 1、6、11，簡稱為 1、2、3 邏輯信道)，考慮每個節(jié)點配備2個收發(fā)信機，可以選擇使用3個正交信道中的2個，在鏈狀拓?fù)浣Y(jié)構(gòu)情況下，可以構(gòu)造出如圖4所示的無干擾信道分配模式。節(jié)點A分配1、2信道，節(jié)點B分配2、3信道，則節(jié)點A、B通信，可以使用2信道，并且2信道在局部網(wǎng)絡(luò)中沒有其他節(jié)點的干擾，近似于一個理想的單跳通信模式，則A、B鏈路帶寬達(dá)到最大;同理B、C使用3信道通信也可以使鏈路帶寬達(dá)到最大。將這些無干擾的鏈路串聯(lián)起來，使得端到端帶寬保持單跳的帶寬而不減少。

圖4 雙收發(fā)信機鏈狀拓?fù)浣Y(jié)構(gòu)下的無干擾信道分配

2.2 入網(wǎng)信道分配

對于一個新加入網(wǎng)絡(luò)的節(jié)點需要選擇合適的信道接入網(wǎng)絡(luò)，若只考慮某一信道上使用的鄰居數(shù)，則可以根據(jù)信道掃描結(jié)果對信道排序，選擇使用數(shù)最少的信道和次少的信道分配給每個收發(fā)信機。另外接收信號強度指示(RSSI)指標(biāo)也是一個重要影響因素，較強的RSSI值則說明2個節(jié)點之間通信距離較近。綜合考慮，對信道的忙閑程度CBI(Channel Busy Index)值進(jìn)行排序，如式(1)所示，然后從3個信道中選取2個較閑的信道分配給本節(jié)點的2個收發(fā)信機。

2.3 數(shù)據(jù)包轉(zhuǎn)發(fā)

無線 Mesh網(wǎng)絡(luò)中現(xiàn)有的 Airtime link metric［1］反映的是在某條特定鏈路上傳輸數(shù)據(jù)幀所消耗的信道資源，這種方式是近似的測量方法，其主要目的是為了降低具體實現(xiàn)和交互的難度。

式(2)中，O和Bt是常量，代表信道接入開銷和測試幀的長度(8192bit)，r是數(shù)據(jù)調(diào)制速率，ef是傳輸幀的誤碼率。Ca即為Airtime link metric的開銷，這種度量只考慮了傳輸速率與信道質(zhì)量，并不適用于多收發(fā)信機多信道的Mesh網(wǎng)絡(luò)。

在雙收發(fā)信機的Mesh網(wǎng)絡(luò)中，由于引入了網(wǎng)橋，通過網(wǎng)橋轉(zhuǎn)發(fā)數(shù)據(jù)包走不同的信道通信能夠降低競爭信道的沖突，故得修改原有的Airtime link metric，加上網(wǎng)橋的因素。

式(3)中Ca1、Ca2分別為接收數(shù)據(jù)包的收發(fā)信機和節(jié)點的第二個收發(fā)信機的路由Airtime link cost。在試驗中，α取值0.8，這樣保證同等條件下的下一跳開銷，選取經(jīng)過網(wǎng)橋的路由，轉(zhuǎn)發(fā)接口由式(4)求出。轉(zhuǎn)發(fā)算法描述如Algorithm 1所示。

2.4 信道切換算法

在網(wǎng)絡(luò)使用過程中，節(jié)點的位置可能改變，入網(wǎng)分配的信道是按照以前周圍環(huán)境通信節(jié)點的狀況來分配的信道。那么，在節(jié)點移動后，周圍的無線環(huán)境發(fā)生了變化，這時候也應(yīng)考慮進(jìn)行信道切換使得節(jié)點間沖突最小，以降低信道的競爭。

信道切換算法不僅需要按照式(1)考慮信道的繁忙程度，還要考慮鄰居節(jié)點每個收發(fā)信機的鄰居數(shù)。為了簡化信息收集工作，在每個節(jié)點的Beacon信標(biāo)幀中都攜帶本地節(jié)點的每個收發(fā)信機所在的信道號、鄰居數(shù)以及CBI值，節(jié)點收到其它節(jié)點的Bea-con信標(biāo)幀后會將其緩存到本地的鄰居信息列表里，根據(jù)每個信道的鄰居數(shù)和信號強度如式(1)所示對信道忙閑程度進(jìn)行排序，將信道分配在比較空閑的2個信道里，由于只使用了3個信道，故最多有一個收發(fā)信機的信道需要切換，算法如Algorithm 2所示。

為了避免分布式切換算法出現(xiàn)碰撞，將各個節(jié)點執(zhí)行切換算法的時間取一個隨機值(10s～15s)，這樣可以有效避免碰撞。

3 Linux下雙收發(fā)信機Mesh組網(wǎng)算法的實現(xiàn)

為了驗證算法的有效性，在Linux系統(tǒng)下對網(wǎng)絡(luò)內(nèi)核進(jìn)行了修改驗證。實驗所用的Linux版本是3.0.55，主要修改包括2部分，一部分是MAC層代碼修改，一部分是Bridge層代碼修改，在Linux內(nèi)核中分別為MAC80211和Bridge兩個個內(nèi)核模塊。Mesh節(jié)點的網(wǎng)絡(luò)架構(gòu)如圖5所示。

圖5 Mesh節(jié)點網(wǎng)絡(luò)架構(gòu)

代碼詳細(xì)修改包括:

(1)Beacon信標(biāo)幀添加無線收發(fā)信機所在信道的鄰居數(shù)和CBI值，修改 Beacon信標(biāo)幀的間隔為100ms;

(2)在MAC80211模塊中添加對Beacon信標(biāo)幀的發(fā)送與處理，并將此信息傳遞給Bridge;

(3)在Bridge里添加信息統(tǒng)計、CBI更新以及本地信道鄰居信息的維護(hù)，維護(hù)與MAC層本地信道鄰居信息的一致性，并處理由MAC收到的鄰居信息并觸發(fā)信道切換機制;

(4)信道切換按照算法2實現(xiàn)，首先檢驗是否需要切換，若需切換則執(zhí)行信道切換;

(5)數(shù)據(jù)包轉(zhuǎn)發(fā)按照算法1實現(xiàn)，將經(jīng)過橋的路由設(shè)置優(yōu)先于經(jīng)過同一信道轉(zhuǎn)發(fā)的路由降低節(jié)點之間的干擾、競爭信道。

4 實驗結(jié)果與分析

代碼修改完畢后，在Linux環(huán)境下進(jìn)行了對比測試。實驗環(huán)境部署了4個節(jié)點，分別稱作A、B、C、D，每個Mesh節(jié)點的實驗準(zhǔn)備情況如表1所示。

表1 實驗準(zhǔn)備

先進(jìn)行單頻多跳組網(wǎng)測試，掃描2.4GHz頻段，周圍環(huán)境中1信道使用量最大并且周圍WiFi-AP設(shè)備太多、6信道次之、11信道再次之，故使用11信道做測試。通過指定A、B、C、D四個Mesh節(jié)點的Mesh路由來形成3跳的鏈狀拓?fù)洌瑢嶒灲Y(jié)果如表2所示。

表2 單頻鏈狀組網(wǎng)TCP吞吐量測試(3次)

由表2的數(shù)據(jù)可以看出，每加一跳吞吐量必然衰減，最多達(dá)一半。

再進(jìn)行雙頻多跳組網(wǎng)測試，為了降低信道間的干擾，采用信道號為11、149、165的3個信道作為邏輯信道(1、2、3)。A 節(jié)點分配1、2邏輯信道，B節(jié)點分配2、3邏輯信道，C節(jié)點分配1、3邏輯信道，D節(jié)點分配1、2邏輯信道，構(gòu)成鏈狀拓?fù)洹榱朔乐规溌烦森h(huán)、首位相接，關(guān)閉掉A節(jié)點1信道所在的收發(fā)信機，關(guān)閉掉D節(jié)點2信道所在的收發(fā)信機，實驗結(jié)果如表3所示。

表3 雙收發(fā)信機多信道鏈狀組網(wǎng)TCP吞吐量測試(3次)

單收發(fā)信機多跳TCP吞吐量與多收發(fā)信機多跳TCP吞吐量對比如圖6所示，單跳的對比有差距是因為使用的網(wǎng)卡為普通WiFi網(wǎng)卡，周圍有很多居民使用WiFi設(shè)備，造成的干擾所致。由圖6可知，經(jīng)過修改后的雙收發(fā)信機Mesh組網(wǎng)算法，多跳后帶寬基本保持不變，而單收發(fā)信機Mesh組網(wǎng)，網(wǎng)絡(luò)帶寬逐跳衰減，網(wǎng)絡(luò)可擴展性差。

圖6 單雙收發(fā)信機TCP吞吐量對比

5 結(jié)束語

針對單收發(fā)信機Mesh組網(wǎng)吞吐量逐跳衰減、網(wǎng)絡(luò)可擴展性差的特點，本文提出了采用雙收發(fā)信機三信道Mesh組網(wǎng)的方案，并在Linux環(huán)境下實現(xiàn)了算法。實驗結(jié)果表明，修改后的雙收發(fā)信機Mesh組網(wǎng)算法，其網(wǎng)絡(luò)吞吐量經(jīng)過多跳后基本保持不變，使得網(wǎng)絡(luò)的可擴展性大大增強，并且可有效抑制單收發(fā)信機組網(wǎng)算法的多跳吞吐量急劇下降的缺點。雙收發(fā)信機Mesh組網(wǎng)模式可以延伸到骨干組網(wǎng)，適用于無線傳輸多路視頻等業(yè)務(wù)，但對于大規(guī)模的外場測試、抗干擾等問題還需進(jìn)一步研究。

［1］IEEE 802.11，Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Specifications(2012 revision)［S］.

［2］Nsnam.The NS-3 Network Simulator［EB/OL］.http://www.nsnam.org/，2013-05-16.

［3］Hu Ming-Xin，Kuo Geng-Sheng.Delay and throughput analysis of IEEE 802.11s networks［C］//IEEE International Conference on Communications Workshops.2008:73-78.

［4］Kernel.Linux Wireless Org［EB/OL］.http://linuxwireless.org/，2013-05-16.

［5］Open80211.Open80211s Consortium［EB/OL］.http://open80211s.com/，2013-05-16.

［6］Andreev K，Boyko P.IEEE 802.11s Mesh Networking NS-3 Model［EB/OL］.http://www.nsnam.org/workshops/wns3-2010/dot11s.pdf，2011-06-15.

［7］Deng J，Haas Z.Dual busy tone multiple access(DBTMA):A new medium access control for packet radio networks［C］//Proc.of IEEE ICUPC.1998:975-985.

［8］Tang Z，Garcia-Luna-Aceves J J.Hop-reservation multiple access(HRMA)for Ad-hoc networks［C］//Proc.of IEEE INFOCOM.1999:194-201.

［9］Tzamaloukas A，Garcia-Luna-Aceves J J.A receiver-initiated collision-avoidance protocol for multi-channel networks［C］//The 20th Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2001).2001:189-198.

［10］So J，Vaidya N H.Multi-channel MAC for Ad Hoc networks:Handling multi-channel hidden terminal using a single transceiver［C］//Proceedings of the 5th ACM international symposium on Mobile Ad hoc Networking and Computing.2004:222-233.

［11］Bahl P，Chandra R，Dunagan J.SSCH:Slotted seeded channel hopping for capacity improvement in IEEE 802.11 Ad-hoc wireless networks［C］//Proceedings of the 10th Annual International Conference on Mobile Computing and Networking.2004:216-230.

［12］Wu S L，Lin C Y，Tseng Y C，et al.A New multi-channel MAC protocol with on-demand channel assignment for multi-hop mobile Ad Hoc networks［C］//Proceedings.International Symposium on Parallel Architectures，Algorithms and Networks.2000:232-237.

［13］Sana Ghannay，Sonia Mettali Gammar.Joint routing and channel assignment protocol for multi-radio multi-channel IEEE 802.11s mesh networks［C］//Wireless and Mobile Networking Conference(WMNC)，20114th Joint IFIP.2011:1-8.

［14］Ku Chia-Yu，Lin Ying-Dar，Tsao Shiao-Li，et al.Utilizing multiple channels with fewer radios in wireless mesh networks［J］.IEEE Transactions on Vehicular Technology，2011，60(1):263-275.

［15］崔勇，張鵬.無線移動互聯(lián)網(wǎng)原理、技術(shù)與應(yīng)用［M］.北京:機械工業(yè)出版社，2011:181-224.