無線Ｍｅｓｈ網絡關鍵技術

摘要：無線Mesh網絡(WMN)是一種特殊的Ad hoc網絡，具有分層的網絡結構，其傳輸骨干網具有多跳、拓撲穩定、無供電約束、業務流量相對匯聚等特性。提高WMN頻譜空間復用度是增加網絡容量有效的方法，而其設計的關鍵是有效控制無線鏈路間的干擾范圍。基于多信道的組網技術是WMN關鍵技術之一，其核心是信道的分配，通過合理的信道分配以獲得最大信道利用率。WMN中路由度量的選取需要考慮多跳無線鏈路間的相互干擾，而通過采用負載均衡路由技術可以均衡網絡資源的使用，從而提高網絡容量和節點的吞吐率。

關鍵詞：空間復用度；多信道；路由度量；負載均衡

Abstract: The Wireless Mesh Network (WMN) is a special kind of Ad hoc network with a hierarchical network structure. Its backbone transmission network has such characteristics as multi-hop， topology stability， no electricity supply constraints， convergence of flows. Improving the spatial reuse of spectrum is an effective approach to increase network capacity. The linchpin of this approach is to effectively control the interference range between wireless links. The multi-channel networking technology is one of the key technologies of WMN， and its core is the channel allocation through which the channel utilization can be maximized. The mutual interference between multi-hop wireless links should be considered when choosing the routing metrics in WMN. Through the load-balancing routing method， the network capacity and throughput of nodes can be improved.

Key words: spatial reuse; multi-channel; routing metric; load balancing

無線Mesh網絡(WMN)是一種多跳、自組織的寬帶無線網絡，一般由Mesh路由器和Mesh客戶節點組成。其典型結構是一種分級網絡結構：Mesh路由器互聯構成多跳無線骨干網，負責數據的中繼；骨干網一般通過網關節點與其他網絡互聯，而Mesh客戶節點通過Mesh路由器接入到WMN。通過WMN最終實現Mesh客戶節點間、客戶節點與Internet等其他網絡間的互聯互通。

與蜂窩移動通信系統不同，WMN是一種多跳的，具有自形成、自愈和自組織能力的無線網絡。雖然WMN具有上述無線Ad hoc網絡的特性，但是WMN與無線Ad hoc網絡之間仍然存在許多重大差別。首先，Ad hoc網絡中節點是移動的，所以其網絡拓撲結構具有動態變化特性；而在WMN中，負責中繼的Mesh路由器一般是靜止的，所以骨干網的拓撲結構保持相對穩定。由于節點的移動性使得設備供電受限，在Ad hoc網絡的組網協議設計中必須考慮功耗因素，而WMN的中繼節點保持靜止，便于實現外部供電，所以功耗的限制相對減弱。另外，Ad Hoc網絡的設計目標是為了實現移動節點間的對等網絡通信，而WMN 著眼于為各種業務需求的客戶節點提供無線寬帶接入功能。

對于任何一種無線網絡來講，提高網絡傳輸容量都是組網協議首要的設計目標。與一般的多跳無線自組織網絡相同，WMN中無線鏈路間也存在較強的相互影響，這使得“提高WMN網絡傳輸容量”的設計目標更具挑戰性。目前WMN組網協議設計的基本思路是：充分挖掘WMN自身特點，采用跨層聯合設計，提高網絡容量，同時提供一定的QoS保障。本文圍繞“提高WMN網絡容量”這一核心問題，從提高頻譜空間復用度、多信道技術以及路由優化等方面分析并總結當前WMN組網協議中的相關關鍵技術。

1 提高WMN的空間復用度

WMN是一種多跳無線網絡，由于無線信道的廣播特性，網絡中任意一條鏈路都和地理位置與其相鄰的無線鏈路間存在相互干擾，制約了網絡的傳輸容量。另一方面，由于無線信道的衰減特性，多跳網絡具有潛在的空間復用特性。設法提高網絡的空間復用度，就能增加并行傳輸的鏈路數目，從而提升網絡容量。

具有高空間復用度的組網協議的WMN基本設計思想是：有效控制無線鏈路間的干擾范圍。本文重點介紹采用高級物理層技術如定向天線、多輸入多輸出(MIMO)等的WMN和結合物理層功率控制的媒體接入控制(MAC)協議。

1.1 基于定向天線技術的WMN

與傳統的全向天線不同，定向天線(智能天線)可以將能量集中于某一方向傳輸，使天線在該方向上具有最強的增益，而其他方向上增益較小。而正是由于定向天線的傳播具有這種波束方向性，可以提高WMN的空間復用度。但是，在提高空間復用度的同時，定向天線也給共享信道的訪問引入了新的問題：定向隱藏終端問題、“耳聾”問題以及接收節點定位問題。

定向隱藏終端問題是指：物理上相鄰的節點，由于傳輸方向的不匹配彼此互不可見，形成隱藏終端。例如在圖1中，相鄰節點A、B分別向節點C發送，由于A、B在發送之前都無法通過載波偵聽發現對方正在發送，即節點A、B是一對隱藏節點，所以傳輸會在節點C處發生碰撞。顯然這種隱藏終端問題在全向天線網絡中是不會發生的。“耳聾”問題是指：發送節點不能與某個節點建立無線通信，原因是該節點正在另一個方向上偵聽或者接收。接收節點定位問題是指：在通信前，發送節點必須首先確定接收節點的位置，才能確定發射波束的方向，所以節點必須對鄰居節點位置進行跟蹤和定位。

為了有效解決定向天線引入的新問題，基于定向天線的MAC研究大多采用跨層設計機制，通過MAC子層與物理層的協同工作，可以提高WMN容量。

D-MAC協議是基于IEEE802.11 分布式協調功能(DCF)的定向天線MAC協議。該協議通過定向發送請求發送(RTS)、數據(DATA)、確認(ACK)幀，達到減少暴露終端數目以及提高空間復用度，而允許發送(CTS)幀仍然采用全向傳輸，從而減少潛在的隱藏終端；協議采用全球定位系統(GPS)定位鄰居節點。

基于帶外音的定向MAC協議[1]提出采用全向帶外音解決“耳聾”問題。協議采用定向傳輸RTS、CTS、DATA和ACK，當數據傳輸完畢后，收、發節點都調整回全向發送帶外音，提示鄰居節點可以與其通信。

文獻[2]在IEEE802.11 DCF基礎上提出定向虛擬載波偵聽(DVCS)機制，協議通過對控制幀接收功率的測量，估算出信號的入射角度(AOA)，進而控制波束方向，實現定向傳輸。并且在DVCS機制中，節點為每一個方向都設置相應的網絡分配向量(NAV)。

1.2 WMN中的功率控制

在無線Ad hoc網絡中，由于移動性節點一般采用電池供電，所以需要通過功率控制來降低節點的能耗；而與Ad hoc網絡不同，WMN中節點一般不存在供電限制，所以在WMN中，功率控制的目的是：節點控制共享信道的覆蓋范圍，從而減小鄰近無線鏈路干擾，增加網絡的空間復用度，提高WMN的網絡容量。

在WMN中，節點可以根據網絡環境動態控制發送功率，也可以動態調整載波偵聽的門限參數以控制功率，或者是二者協同控制。功率控制仍需要解決一些技術問題，例如：如何在保持網絡連通性的前提下，提高網絡空間復用度；發射功率與載波偵聽門限在控制空間復用度方面存在何種關系；如何確定節點的發射功率以實現網絡性能最優化。其中，確定每個節點的發射功率是一個難題。減小節點的發射功率可以提高信道的空間復用度，但是可能造成節點間數據傳輸率減小，數據流端到端時延增加。如果增大發送功率，節點間通信距離隨之增加，數據流端到端時延可能降低，但這樣又會使信道的空間復用度減小，降低網絡容量；同時如何在WMN中實現分布式的功率控制也具有相當難度。

早期的功率控制研究大多集中在基于圖模型的拓撲控制方面。在圖模型中，如果兩個節點間的距離在其傳輸范圍之內，那么這兩個節點就是鄰居節點，這兩個節點間就存在一條邊。而傳輸范圍取決于發射功率，路徑損耗，以及接收靈敏度等因素。在這種模型下，功率控制的目標是在保持連通性的前提下，盡量減小節點的度數。這一目標是建立在一個基本觀點之上：低節點度數，意味著較小鏈路干擾。而最近研究[3-4]認為：圖模型并不能完全刻畫無線鏈路間的相互干擾，轉而采用基于信干噪比值(SINR)的物理模型研究功率控制。載波偵聽的門限值決定了通信節點能夠在多大覆蓋范圍內不會因其他傳輸而干擾。文獻[5]提出了一種能夠動態調整載波偵聽的門限值提高空間復用度的功率控制算法。

2 WMN中的多信道技術

基于多信道的WMN組網技術是提高WMN容量的最有效的方法，受到研究者的高度重視。

2.1 多信道網絡模型

多信道MAC模型可以分為以下3種類型，如圖2所示：

單接口(網卡)多信道。只有一個收發器可用，每個網絡節點在同一時間只有一個信道是活動的。不同的節點在同一時間可以工作在不同的信道上，從而提高系統容量。

單接口多收發器多信道。一個接口上采用多個收發器共用一組信道。多個物理層實體通過一個MAC層來協調多信道的功能。

多接口多信道。一個網絡節點有多個具有獨立MAC和物理層的接口。這些接口的通信是相互完全獨立的。因此，需要虛擬一個子層協議，實現在多個MAC實體之上協調所有信道的通信。

在實際的研究和應用中，單接口多收發器多信道模型使用的比較少。早期研究的多是單接口(網卡)多信道模型，目前多數研究的是多接口多信道模型，尤其是接口數小于可用信道數的情況。

2.2 多信道分配

信道分配是多信道技術中的一個關鍵問題。多接口WMN環境下的信道分配，主要目的是在保證網絡連通度的基礎上，獲得最大信道利用率。信道分配主要包括固定信道分配方式、動態信道分配方式和混合信道分配方式。

(1) 固定信道分配方式

固定分配機制將信道永久地、或者是長時間(相對接口切換時間)地分配給某一個接口，在信道分配后不再考慮拓撲和負載的變化。這種方式適合網絡穩定、拓撲和負載變化小的環境中。這種機制又可以細分為公共信道分配(CCA)模式和差別信道分配(VCA)模式。

CCA模式是最簡單的一種機制。在CCA模式中，給每個節點分配相同的一組信道。如圖3(a)所示，每個節點有兩個接口，使用相同的兩個信道。由于這種方式過于簡單，并不能高效地利用網絡資源。

在VCA模式中，協議結合網絡中各種對信道分配的影響因素，給不同節點的接口合理地分配不同的一組信道[6]，如圖3(b)所示。這種分配方式可能導致網絡分區或者是拓撲變化。文獻[6]為WMN提出了一種集中式信道分配算法，算法根據負載由大到小的順序進行信道分配，確保每次分配的信道是當前具有最小使用量的信道，并保證網絡連通性，同時保證每條鏈路的帶寬限制。連通低干擾信道分配(CLICA)[7]是一種流量透明的信道分配方式，這種方式為每個Mesh節點計算優先級，根據連通圖和沖突圖進行信道分配。文獻[8]中基于圖染色和圖的最大切割提出了兩種算法，以保證在信道分配中獲得最小的沖突率。文獻[9]中將信道分配和拓撲控制看作是兩個獨立但相關的問題，在此基礎上提出了一種非集中式的信道分配策略。

(2) 動態信道分配方式

動態信道分配方式適應于網絡負載變化大的情況。該方式仍然允許任何接口被分配到任意的信道上，但是和固定分配方式不同的是，在初始化分配后，動態信道分配方式仍然允許接口從一個信道切換到另一個信道。因此，在動態信道分配中，需要有一個協調機制，以保證需要互相通信的節點能夠處于一個共同的信道。

一種典型的協調機制是，所有的節點周期性的訪問一個預先制定的信道，在這個信道上協商下一個周期的信道使用。分時隙種子化頻道跳變(SSCH)[10]提出了另一種機制，在該機制下，每個節點依照一個偽隨機序列同步的切換信道，以保證所有的鄰居能夠周期性的擁有相同的信道。采用控制信道方式也是常見的一種協調機制。這種方式下，一個接口被固定分配到一個公共信道上，用于信道控制；其他的接口可以在剩余的信道上切換，用于數據交換。文獻[11]中提出根據負載變化動態分配信道，以提高網絡總吞吐量，并獲得較好的負載平衡。算法中以每個網關節點為根，建立多棵生成樹拓撲。

動態信道分配方式的好處在于能夠把接口切換到任何信道，從而提供了在少量的接口上使用多個信道的潛在能力。動態切換方法的主要問題在于如何決策何時切換信道，以及將接口切換到哪一個信道。

(3) 混合分配方式

混合信道分配方式[12]結合了固定分配和動態分配的特點。在這種方式下，一部分接口使用固定分配方式，其他接口使用動態分配方式。固定接口可以分配一個專門的控制信道，或者是一個數據/控制混合信道，而其余的接口可以動態地在信道間進行切換。

3 WMN中的路由優化

在多跳網絡中，由于相鄰無線鏈路間存在相互干擾，使得中繼節點的轉發過程將會抑制其鄰居節點的發送，所以，在WMN中，不同路徑的數據流間，同一路徑上相鄰鏈路間都存在某種程度的干擾，制約著WMN的網絡容量。

另一方面，WMN的骨干網具有拓撲相對穩定，無功耗約束，多跳中繼，業務流量匯聚于網關等特點，所以可以通過對路由的合理優化，減小無線鏈路干擾，提高網絡容量。

3.1 WMN中路由度量的選取

路由度量是路由選擇的基礎，傳統無線Ad hoc網絡中所普遍采用的跳數不能反映出多跳網絡中的干擾特性，對QoS支持力度很弱。所以WMN應該采用支持QoS的路由度量機制，根據無線鏈路狀態以及高層需求等信息，綜合評估鏈路度量值，并形成最優路由，有效增加網絡可用帶寬和容量。

無線信道通信質量依賴于背景噪聲、障礙物、信道衰減以及其他通信產生的干擾等。一般鏈路層協議在有數據幀發生丟失時，通常會進行重傳操作。根據此特點，De Couto等人提出了基于期望傳輸次數(ETX)的路由度量方法[13]，ETX定義為WMN網絡節點的MAC層在一條無線鏈路上成功交付一個數據幀所需傳輸次數的期望值。基于ETX的路由算法認為，降低幀重傳次數也就是增大了網絡的吞吐量。所以，這類路由算法選擇最優路徑上所有鏈路的ETX的總和應為最小。

Koksal等人通過研究指出[14]，由于無線網絡信道狀態的時變性，ETX不能夠準確的度量無線信道質量。為了解決這個問題，Koksal等人在ETX的基礎上提出了修正EXT(mETX)方法作為路由度量參數[15]，在度量值中引入表示信道的相對較快變化特性的參數。

在最優路徑的選取過程中，還應采用跨層協作機制，綜合考慮高層與鏈路層對誤比特率的要求，例如傳輸控制協議(TCP)要求在某條鏈路上誤幀重傳次數不能超過給定門限值，若超過門限，將引起傳輸層重傳，觸發TCP慢啟動機制，造成網絡性能的降低。有效傳輸次數(ENT)[15]度量方法的引入較好地解決了這個問題。研究表明，在真實的WMN網絡中使用ENT路由方式，相對于ETX方式，平均丟幀率可以降低50%。

3.2 WMN中負載均衡路由

負載均衡的主要動機是通過均衡網絡資源的使用，從而提高網絡容量和節點的吞吐率。在WMN網絡中，負載不均衡主要體現在網關節點、網絡中心部分以及瓶頸節點處。

WMN網絡中，大量流量將在網關節點匯聚，網關節點的處理能力將制約整個WMN網絡的容量。對于多網關節點的WMN網絡，要考慮如何在網關節點間分配流量，避免負載不均。特別的，當各個網關節點具有不同類型、不同帶寬的外部接入鏈路時，還需要綜合考慮到這些不同外部接入鏈路的傳輸能力對負載均衡分配方案的影響。

在網關節點間進行負載均衡通常采用的策略有：基于移動邊界的負載均衡(MBLB)、基于節點分割的負載均衡(PHLB)、基于概率分條的負載均衡(PSLB)。在MBLB和PHLB方法中，每個Mesh節點各自僅利用一個網關節點作為出網通道；而PSLB方法中，每個Mesh節點可以分別同時利用多個網關節點作為出網通道，這樣在理論上可以達到完全負載均衡。

WMN網絡中心區域的節點與其他節點相比，容易產生過載現象，原因是大部分采用“最短路徑”的路由算法會使的中部節點正好位于大多數“最短路徑”上。該問題的解決方案是通過路由的方式，將負載動態分布在較輕負載的節點上，避免對中心區域節點的過載。解決方案大都采用基于環狀路由的負載均衡方法[16]，其基本思想是：將整個WMN網絡區域劃分為多個同心環，每個節點都位于一個環中。從環i中的源節點到環j中的目的節點的流量盡可能的不傳遞到環i和環j外的節點上去。

現有的基于環的負載均衡算法有：外環優先路由法(PORS)、內環優先路由法(PIRS)、目的環優先路由法(PDRS)、源環優先路由法(PSRS)。其中PORS和PIRS分別將主要流量集中在外環或內環中，而PSRS和PDRS是前兩種方法的綜合，將流量分配在內外環中，進一步均勻了負載。從圖4中可以看出，相對于傳統的最短路徑算法，以上4種方法可以分散流量，有效減輕中心區域節點的負載。

除了以上分析的負載均衡方法外，還有一些問題亟待研究，例如：負載均衡優劣的度量、流量分配的穩定性、流量的分割和負載均衡對路由的影響以及由于流量分割產生的亂序現象對TCP性能的影響、節點如何跨層感知負載情況并形成基于跨層協作的負載均衡算法等。

4 結束語

WMN是一種特殊的Ad hoc網絡，具有分層的網絡結構，其傳輸骨干網具有多跳、拓撲穩定、無供電約束等特性。同時作為寬帶無線接入網絡，WMN通過網關節點與其他類型的網絡實現互聯，業務流量相對匯聚。如何針對WMN的特點，提高網絡的通信性能仍然是目前研究的熱點問題，而增加WMN的網絡容量是其中關鍵而又基礎的問題。除此之外，尚有一些關鍵技術問題有待進一步解決，如WMN的QoS保障、分布式網絡管理、控制機制、WMN安全機制等問題。盡管如此，我們相信WMN必將成為下一代無線網絡中的主流技術之一。

5 參考文獻

[1] Choudhury r r， Vaidya n h. Deafness: A MAC problem in ad hoc networks when using directional antennas[C]//Proceedings of IEEE 12th International Conference on Network Protocols (ICNP’04)， Oct 5-8， 2004. Berlin， Germany. Piscataway， NJ， USA: IEEE， 283-292.

[2] Takai m， Martin j， Ren a， et al. Directional virtual carrier sensing for directional antennas in mobile ad hoc networks[C]// Proceedings of 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’02)， Jun 9-11， 2002， Lausanne， Switzerland. New York， NY， USA: ACM， 2002: 83-193.

[3] Burkhart m， Rickenbach p， Wattenhofer r， et al. Does topology control reduce interference? [C]// Proceedings of 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’04)， May 24-26， 2004， Tokyo， Japan. New York， NY， USA: ACM， 2004: 9-19.

[4] Fuemmeler j a， Vaidya n h， Veeravalli v v. Selecting transmit powers and carrier sense thresholds for CSMA protocols[R]. Urbana-Champaign， IL， USA: Department of Electrical and Computer Engineering， University of Illinois at Urbana-Champaign， 2004.

[5] Zhu j， Guo x， Yang l， et al. Adapting physical carrier sensing to maximize spatial reuse in 802.11 mesh networks[J]. Wireless Communications and Mobile Computing， 2004， 4(8): 933-946.

[6] Raniwala a， Gopalan k， Chiueh t. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks [J]. ACM Mobile Computing and Communications Review， 2004， 8(2): 50-65.

[7] Marina m， Das s r. A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks[C]// Proceedings of the 2nd IEEE International Conference on Broadband Networks: Applications and Services Symposium (BroadNets'05)， Oct 3-7， 2005， Boston， MA， USA. Piscataway， NJ， USA: IEEE， 2005: 381-390.

[8] Subramanian a， Gupta h， Das s r. Minimum-interference channel assignment in multi-radio wireless mesh networks[C]//Proceedings of4th Annual IEEE Communications Society Conference on Sensor， Mesh and Ad Hoc Communications and Networks( SECON '07)， Jun 18-21， 2007， San Diego， CA， USA. Piscataway， NJ， USA:IEEE， 2007: 481-490.

[9] Rad a h m， Wong v w s. WSN16-4: Logical topology design and interface assignment for multi-channel wireless mesh networks[C]// Proceedings of IEEE Global Telecommunications Conference (Globecom' 06)， Nov 27-Dec 1， 2006， San Francisco， CA， USA. Piscataway， NJ， USA: IEEE， 2006:1-6.

[10] 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 10th Annual International Conference on Mobile Computing and Networking (MOBICOM'04)， Sep 26-Oct 1， 2004， Philadelphia， PA， USA. New York， NY， USA: ACM， 2004: 216-230.

[11] Raniwala a， Chiueh t. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network[C]// Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05): Vol 3， Mar 13-17， 2005， Miami， FL， USA. Piscataway， NJ， SA:IEEE， 2005: 2223-2234.

[12] Ramachandran k， Almeroth k， Belding-Royer e， et al. Interference-aware channel assignment in multi-radio wireless mesh networks[C]// Proceedings of 25th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’06): Vol 3， Apr 23-29， 2006， Barcelona， Spain. Piscataway， NJ， USA: IEEE， 2006: 1-12.

[13] De Couto d， Aguayo d， Bicket j， et al. A high throughput path metric for multi-hop wireless routing[C]//Proceedings of 9th Annual International Conference on Mobile Computing and Networking， Sep 14-19， 2003， San Diego， CA， USA. New York， NY， USA: ACM， 2003: 136-146.

[14] Koksal c e， Jamieson k， Telatar e， et al. Impacts of channel variability on link-level throughput in wireless networks[C]//Proceedings of ACM SIGMETRICS/Performance， June 26-30， 2006， Saint-Malo， France. 2006.

[15] Koksal c e， Balakrishnan h. Quality aware routing metrics for time-varying wireless mesh networks[J]. IEEE Journal on Selected Areas in Communications， 2006， 24(11): 1984-1994.

[16] Bhaya g， Manoj b s， Siva c， et al. Ring-based routing schemes for load distribution and throughput improvement in multi hop cellular， Ad hoc， and mesh networks[C]//Proceedings of 2003 International Conference on High Performance Computing (HiPC’03)， Dec 17-20， 2003， Hyderabad， India. Berlin， Germany: Springer-Verlag， 2003: 152-161.

收稿日期：2008-01-14

吳凡，電子科技大學通信與信息工程學院在讀博士研究生。先后參加多項國家“863”項目，主要研究領域為無線自組織網絡、無線路由技術。

毛玉明，電子科技大學通信與信息工程學院教授、博士生導師。先后主持多項國家“863”項目，擁有多項專利。目前主要研究方向為寬帶無線通信網絡、寬帶通信網技術和高速信息處理技術。

張科，電子科技大學通信與信息工程學院在讀博士研究生。先后參加多項國家“863”項目，主要研究領域為無線自組織網絡QoS、網絡測量技術。