無線網格網關鍵技術分析

張記瑞　黃圣春　魏急波

摘 要： 作為一種新興的無線組網技術，無線網格網在災后救援、臨時大型活動及時通信和家庭辦公多媒體數據交互等多個領域都有著廣闊的應用前景。介紹了無線網格網的網絡結構和標準化協議，并針對MAC協議設計的兩個關鍵技術：時隙分配和跨層設計進行了闡述和總結，為解決現有無線網格網協議中時隙利用率低和多跳傳輸效率不高提供了依據。

關鍵詞： 無線網格網； 時隙分配； 跨層； MAC協議

中圖分類號： TN911?34 文獻標識碼： A 文章編號： 1004?373X（2015）19?0057?03

Abstract： As an emerging wireless networking technique， wireless mesh network has a vast application prospect in the fields of rescue after disaster， instant messaging for temporary large?scale activities and telecommuting multimedia data interaction. The network structures and standardized protocols of the wireless mesh network are introduced. The two key technologies of time slot allocation and cross?layer design for MAC protocol design are presented and summarized， which provides the basis for improving the time slot utilization ratio and multi?hop transmission efficiency in the existing wireless mesh network protocols.

Keywords： wireless mesh network； time slot allocation； cross?layer； MAC protocol

0 引 言

隨著通信技術的不斷發展，人們對通信網絡的依賴也日趨強烈。據中國網絡信息中心發布的《中國互聯網絡發展狀況統計報告》顯示，截止2014年底，我國手機網民規模已經達到5.56億人，占網民總數的85.8%。然而，傳統無線網絡的問題依然存在，在偏遠地區的網絡架設成本高、基站損壞導致信息傳輸中斷，人們迫切希望找到一種抗毀性強、可靠性高、支持多跳、具有自組織特性的網絡，于是一種新的網絡技術——無線網格網（Wireless Mesh Networks，WMN）進入了人們的視野。

由于無線網格網具有容錯能力強、易于架設以及高帶寬等特性，各標準組織都已經或準備將其納入到自己的規范中[1]。無線網格網網絡構架靈活，網絡拓撲結構可變，節點的入網、離網便捷，使得網絡具有較好的延展性[2]。對于臨時舉辦大型活動、災后應急救援、家庭辦公場所的網絡通信和數據傳輸，無線網格網發揮著很大的作用。

1 網絡結構

無線網格網的網絡結構主要可以分為以下三類：

（1） 骨干無線網格網

圖1為骨干無線網格網，該網絡是由無線Mesh路由器（Wireless Mesh Router，WMR）作為網關連接到互聯網或者專有網絡。無線Mesh客戶端再通過連接網關，通過無線Mesh路由器進行數據交互，從而實現無線Mesh客戶端的數據傳輸。這與蜂窩網最大的不同在于，蜂窩網基站之間是有線網進行連接，而無線網格網路由器之間為無線數據傳輸。

（2） 客戶端無線網格網

圖2為客戶端無線網格網，該網絡的特點是利用客戶端設備自身網絡建立一個點對點的通信傳輸鏈路。兩個距離較遠的節點之間通信可通過客戶端作為中繼節點傳輸。客戶端無線網格網隨著客戶的移動，網絡拓撲也會隨之改變。這種網絡具有自愈性高，抗毀性強等特點。

（3） 混合無線網格網

圖3為混合無線網格網，該網絡實現了骨干Mesh網和客戶端Mesh網的融合，在支持通過Mesh路由器連接到互聯網的同時，客戶端之間也可實現直接通信。

2 標準化協議

2.1 IEEE 802.11

作為移動通信網絡中應用最廣泛的協議，IEEE 802.11在無線網格網中也被廣泛使用。無線網格網可以看作是一種特殊的Ad hoc網絡[3]，同時融合了WLAN網絡，所以根據文獻[4]，IEEE 802.11也能夠對無線網格網有著較好的支持。正如文獻[5]中所提到的，分布式協調（Distributed Coordination Function，DCF）機制是在IEEE 802.11定義中進行無線數據傳輸最基本也是最常用的方式，該機制將載波偵聽技術（Carrier Sense Multiple Access with Collision Avoidance，CSMA/CA）和確認技術（Acknowledgement，ACK）相融合。由于當節點發送產生沖突時，采用二進制指數隨機退避策略，節點發送將難以保證公平性。文獻[6]給出了一個緩解由于競爭導致節點非公平性的方法。由于存在著隱藏終端和暴露終端的問題，隨著節點數量的增加，沖突將更加劇烈，網絡吞吐量下降明顯，數據傳輸的成功率也將隨之降低。

2.2 IEEE 802.15

通過定義無線個人局域網通信技術（Wireless Personal Area Network Communication Technologies，WPAN）的PHY層和MAC層內容，使得IEEE 802.15能夠有效支持工業界中低功耗的無線網格網。文獻[7]給出IEEE 802.15的兩種組網模式：一種是任意節點都可以與其他相鄰節點進行通信的全網格網結構；另一種是只有部分節點可以與其他節點進行多跳通信，其余節點只能和一跳鄰節點相互通信的部分網格網結構。該協議主要是針對避免沖突、低能耗等重點問題展開研究。endprint

2.3 IEEE 802.16

IEEE 802.16協議[8]下的無線網格網是基于時分雙工（Time Devision Duplexing，TDD）的工作模式。該協議主要用于解決無線城域網（Wireless Metropolitan Area Networks，WMAN）的接入問題，其中包括PHY層和MAC層的詳細問題。通過基站（Base Station，BS）對時隙進行預約和分配，可以有效避免沖突。每個節點都可以作為中繼進行時隙多跳傳輸。該協議下的無線網格網分為集中式調度和分布式調度兩種，基于調度機制可實現由基站劃分預約時隙的集中式調度以及三次握手協商的分布式調度。

3 關鍵技術

3.1 時隙分配

由于基于CSMA/CA的載波偵聽技術，在節點數量增多或業務量增大時，產生較大的沖突會引起節點退避，這樣吞吐量會急劇下降。而時分多址（Time Division Multiple Access，TDMA）技術通過對時隙的預約和分配，可以有效避免沖突，實現時隙的優化分配，是提高傳輸效率的保證。

3.1.1 集中式時隙分配算法

集中式時隙分配主要是由無線網格網中的中心節點對全網所有節點進行時隙劃分。這樣的好處是，中心節點通過獲取全網節點的拓撲信息，從而將時隙利用最大化。文獻[9]給出了一種有序頂點著色算法（SVC），該算法主要利用圖論中的染色問題，對傳統的啟發式時隙分配算法[10]進行了改進，通過獲取最小幀長和時隙復用最大化兩步，實現時隙優化分配。具體方法如下：

（1） 對全網節點按序標號，并列出每個節點的兩跳內相鄰節點。接下來按照相鄰節點數由多到少排列，依次占用時隙，保證同一時隙內沒有在兩跳內的節點。把所有節點都分配時隙后，此時所得到的幀長即為最小化幀長；

（2） 實現時隙復用最大化，將鄰節點數由少到多排列，并依次占用時隙，做到盡可能使時隙復用最大化。

然而，SVC并不能尋找到一個時隙復用最大化的解，只能通過該算法找到次優解。除了SVC外，基于神經網絡的時隙分配算法[11]也可以找到最小幀長。然而，尚沒有有效的算法可以直接尋找到時隙復用最大化解。

3.1.2 分布式時隙分配算法

相比于集中式算法，分布式算法的優點是可以不用獲取全網的拓撲信息，只需要知道本節點兩跳范圍內的鄰節點信息即可。最先提出的分布式時隙分配算法是分布式貪婪算法[12]，該算法需要獲取本節點兩跳以內鄰節點的信息，通常采取假設，即已獲得了本節點兩跳以內鄰節點信息。在分布式貪婪算法中，幀長是固定的，時隙數與節點數相等，保證每個節點都能夠占用到不同的時隙。當有空閑時隙時，節點可以通過競爭占用。該算法實現較為簡單，時隙分配效率也較高，然而如何獲取節點的兩跳鄰節點信息，還需進一步研究。

3.2 跨層設計

在無線網格網中，PHY層無線信道容量和誤比特率的變換特性，使得盡管有多種方法來提高物理信道的性能，但是分層設計依然無法保證低丟包率和可靠的傳輸性能。為了達到較好的傳輸性能，需要將MAC層、傳輸層、路由層等與PHY層實現有效融合。在MAC協議的跨層設計中，有兩種主要的方法可采用[13]。一種是采用基于定向天線的MAC協議；另一種是采用有能量約束的MAC協議。

當采用定向天線時，可以有效消除暴露終端的問題，如圖4所示。然而帶來的問題是潛在的隱藏終端數會增多，如圖5所示，同時，也面臨一些系統復雜度的問題。當采用有能量約束的MAC協議時，在節點密度大而采用較小發送功率時，也可以較好地避免隱藏終端，當然，隨著發射功率的降低，能夠避免隱藏終端干擾的可能性也會降低，所以隱藏終端問題依然會比較突出。除此之外，文獻[14]也給出了一種通過跨層設計解決分層設計中多跳傳輸帶來的低吞吐量的問題。

4 結 語

到目前為止，無線網格網的多跳傳輸時隙還沒有達到人們理想的預期，主要是由于IEEE 802.11協議廣泛成熟的應用，IEEE 802.11協議所采用的CSMA/CA機制決定了當節點數多或數據量大時，會導致吞吐量急劇下降，這使得該協議在拓寬到兩跳及其以上的應用上還存在著一些瓶頸。文獻[15]是MIT計算機科學和人工智能實驗室搭建的基于IEEE 802.11無線網格網平臺Roofnet，通過該平臺的實測結果表明，當網絡由一跳擴展到兩跳時，網絡吞吐量下降超過了[23。]本文通過對MAC協議中基于TDMA MAC協議的時隙劃分和跨層技術的研究與分析，旨在為下一步研究中找到一種避免沖突、提高網絡傳輸效率的傳輸協議，以此來解決目前還存在的時隙利用率不高，多跳傳輸效率低等問題。

參考文獻

[1] 姜欣，杜建鳳.Mesh核心關鍵技術現狀分析[J].現代電信科技，2009（6）：50?54.

[2] BELJADID A， HAFID A S. Design of wireless mesh networks： expansion and reliability studies [C]// Proceedings of 2008 IEEE Global Communications Conference. New Orleans： IEEE， 2008： 163?172.

[3] AKYILDIZ I F， WANG Xudong. A survey on wireless mesh networks [J]. IEEE Radio Communications， 2005， 38（4）： 393?422.

[4] LAN/MAN Standards Committee. ANSI/IEEE Std 802.11?1999 wireless LAN medium access control （MAC） and physical layer （PHY） specifications [S]. New York： IEEE?SA， 2009.endprint

[5] CARRANO R C， MAGALHAES L C S， SAADE D C M， et al. IEEE 802.11s Multihop MAC： a tutorial. [J]. IEEE Communications Surveys & Tutorials， 2011，13（1）： 52?67.

[6] WANG W， LEONG B， OOI W T. Mitigating unfairness due to physical layer capture in practical 802.11 mesh networks [J]. IEEE Transactions on Mobile Computing， 2015， 14（1）： 99?112.

[7] STANISLOWSKI D， VILAJOSANA X， WANG Q， et al. Adaptive synchronization in IEEE802.15.4e networks [J]. IEEE Transactions on Industrial Informatics， 2013， 10（1）： 795?802.

[8] IEEE Computer Society and the IEEE Microwave Theory and Techniques Society. IEEE Std 802.16?2004 air interface for fixed broadband wireless access systems [S]. New York： IEEE Computer Society and the IEEE Microwave Theory and Techniques Society， 2004.

[9] LEE H， YEO J， KIM S， et al. Time slot assignment to minimize delay in ad?hoc networks [J]. IST Mobile Communications， 2001， 11（3）： 128?134.

[10] VUONG T H P， HUYNH D T. Adapting broadcasting sets to topology changes in packet radio networks [C]// Proceedings of 1999 the 8th International Conference on Computer Communications and Networks. Boston： IEEE， 1999： 263?268.

[11] CHAKRABOTRY. Genetic algorithm to solve optimum TDMA transmission schedule in broadcast packet radio networks [J]. IEEE Transactions on Communications， 2004， 52（5）： 765?777.

[12] EPHREMIDES A， TRUONG T V. Scheduling broadcasts in multihop radio networks [J]. IEEE Transactions on Communications， 1990， 38（4）： 456?460.

[13] AKYILDIZ I F， WANG X D. A survey on wireless mesh networks [J]. IEEE Radio Communications， 2005， 11（9）： 23?30.

[14] LAUFER R， SALONIDIS T， LUNDGREN H， et al. A cross?layer backpressure architecture for wireless multihop networks [J]. IEEE/ACM Transactions on Networking， 2014， 22（2）： 363?376.

[15] BICKET J， BISWAS S， AGUAYO D， et al. Architecture and evaluation of the MIT roofnet mesh network （DRAFT） [C]// Proceedings of 2005 ACM Mobicom. [S.l.]： ACM， 2005： 31?42.

[16] 趙金東，王沁，萬亞東，等.面向最小延遲的無線mesh網絡時隙分配問題研究[J].小型微型計算機系統，2012，33（5）：1041?1046.

[17] Mesh Networks Inc. Mesh networks information headquarters [EB/OL]. [2012?08?12]. http：//www.meshnetworks.com/.

[18] Nortel Mesh Networks. Nortel networks corporation [EB/OL]. [2009?03?16]. http：//www.nortelnetworks.com/

[19] 北電網絡.無線網狀網（Wireless Mesh Network）：全新的廣域寬帶無線接入解決方案[C]//2005中國無線技術大會論文集.北京：信息產業部無線電管理局，2005：78?83.

[20] 姜永，鄭明春，李國強.IEEE 802.16中的無線Mesh網絡研究[J].計算機技術與發展，2008（5）：234?237.

[21] 曾智慧.基于IEEE 802.16標準的無線Mesh網絡研究[D].上海：同濟大學，2006.endprint