一種新的基于最大流的無線Mesh網絡信道分配算法*

葛志輝，李陶深，韋亞歡

（廣西大學計算機與電子信息學院 南寧530004）

1 引言

隨著無線技術的發展，無線網絡可以讓人們擺脫有線的束縛，隨時隨地進行通信并享受豐富的信息服務，給廣大用戶提供了極大的便利。無線Mesh網絡（wireless mesh network，WMN）融合了移動自組織網 (mobile ad-hoc network，MANET)和無線局域網 (wireless local area network，WLAN)的優勢[1]，具有多跳、易擴展、自組織和自恢復等特點，部署成本低，在商業應用中優勢明顯，如今越來越受到人們的關注。無線網絡帶寬受限、多跳傳輸以及無線鏈路之間的干擾等因素制約了WMN的發展。

目前，在IEEE 802.11系列技術標準中，都提供不同數量的正交信道。多信道技術的引入可以大幅度提升無線網絡的空間復用率，但多信道的信道分配、降低信道間的干擾以及實現網絡的負載均衡等問題，都給研究人員提出了新的挑戰。

[2]中，將信道分配和路由協議相結合，設計了一種基于負載感知的集中式信道分配算法，但需要事先知道端到端的路由路徑以及路徑上的流量模型等信息。參考文獻[3]綜合考慮信道分配與路由協議的相互依賴關系，提出了一種聯合信道分配、路由選擇的靜態平衡信道分配算法(BSCA)，在受到公平性約束的條件下，最大限度地提高分配給各流量節點的帶寬。Das等人給出了WMN中靜態信道分配的最優化模型[4]，將信道分配問題轉化成目標最大化時傳輸的業務流數目的線性規劃問題，約束條件為網絡全連通、信道數目受限以及潛在干擾邊數目受限，然而卻沒給出實用的多項式時間算法。參考文獻[5]提出一種“TiMesh”MC-WMN網絡結構，將接口分配、信道分配和路由作為一種聯合線性優化問題，較好地解決各流量間的公平性問題。由于它們所采用的算法都是靜態分配算法，一旦進行信道分配后將不再改變，因此不能根據業務量的變化動態地調整分配給鏈路的信道，在實際應用中吞吐量較小，極大地限制了使用多信道的資源和多樣性。

參考文獻[6]提出基于Hyacinth結構的動態信道分配算法。信道分配通過鄰居-接口綁定和接口-信道綁定兩個階段實現，前者能夠有效地避免節點信道切換帶來的漣漪效應，后者只需搜索具有較高優先級的干擾鄰居的信道負載，即可實現信道分配。JARS[7]是一種聯合信道分配、路由、調度的信道分配方案，把底層信道分配和調度信息的效率（即邏輯距離）結合到路由度量計算中，使得路由擁有最大的連接空間和頻道復用選擇，并可根據不同的通信模型（如廣播、單播）調整不同的信道分配和調度策略。該方法可以有效地利用多信道多無線接口網絡中信道的多樣性和空間復用特征，但它沒有考慮如何把信道分配和調度策略適應到動態變化的流量模型中。

上述信道分配方案中大多數算法都是假定網絡流量模型已知，根據已知的流量信息進行信道分配及網絡優化。雖然這些方法對已知流量模型的網絡都能進行某種優化工作，但它們并不適合實時動態的網絡環境。在實際網絡環境中，很多業務是突發且無法預知的，因此本文提出一種基于未知流量模型的信道分配算法。首先利用最大流方法計算網絡所能達到的最大吞吐量及在此條件下每條鏈路承載的不同流量負載，然后以此作為信道分配的依據。在信道分配過程中，同一沖突域中的無線鏈路應盡量使用不同的正交信道，以減少同信道干擾問題，提高網絡傳輸速率和容量。

2 系統模型與系統假設

2.1 網絡模型

用無向圖G(V，E)表示多信道無線Mesh網絡，其中V表示所有節點的集合，E表示所有無向鏈路的集合。假設每個節點i配置了R(i)個網卡，網絡中可以使用|H|個正交無線信道。對于WMN中的任意兩個節點i,j∈V，記d(i,j)為 i、j之間的距離，r表示發射距離。如果 d(i,j)≤r，表示節點在i、j各自的通信范圍內，則i和 j之間存在一條無向邊，即 ei,j∈E。

2.2 干擾模型

對于物理拓撲 G(V，E)，如果存在兩條邊 i圮j，m圮n∈E，且 min{d(i,m),d(i,n),d(j,m),d(j,n)}≤r’,其中 r’表示干擾距離，稱這兩條邊為 “潛在”的干擾邊。對于任意的e∈E，用PIL(e)表示鏈路 e的所有潛在干擾鏈路集合。用χ(e)表示分配給鏈路e的信道，鏈路e的所有干擾鏈路集合可以表示為：

由于在同一沖突區域中，使用信道同時進行通信時會產生干擾。因此，在進行信道分配時，盡量使同一沖突區域內各相關鏈路使用不同的信道。當網絡中所有節點的信道分配結束后，即各鏈路所使用的信道已確定，那么它的干擾鏈路集合也可知。此時，對于任意鏈路e，其干擾度可表示為：

其中，I(χ(e′)= χ(e))表示當“潛在”的干擾鏈路 e’上分配的信道與鏈路e相同時，該函數值等于1，否則為0。那么，整個網絡的干擾度可表示為：

2.3 業務模型

本文采用參考文獻[8]提出的鏈路流量模型，考慮一個業務，從源端s通過中間路由器轉發到達目的端t，在目的端接收到的業務速率為γst。假設該業務在轉發過程中通過某條鏈路eij，定義一個變量ρijst，則有以下約束：

假定鏈路的流量負載用符號f表示。業務從源端到目的端時，經由鏈路eij并在該鏈路上的負載為：

2.4 信道分配

網絡流問題在交通運輸、容量網絡、信息傳遞等方面有廣泛的應用，許多線性規劃的實際問題可轉化為網絡流的模型求解。在WMN中尋求網絡最大吞吐量的問題，實質上就是一個典型的最大流問題。因此，提出一種集中式基于最大流的無線Mesh網絡信道分配算法（centralized max-flow based channelassignmentalgorithm，CMCA）。CMCA以最小化網絡干擾為目標，即：

信道的分配首先根據每條鏈路的容量，利用最大流方法求解網絡中能達到的最大吞吐量及其每條鏈路的流量負載情況，然后根據每條鏈路的流量負載情況采用貪心策略依次進行信道分配。

3 性能評價

采用NS2[9]對實驗結果進行仿真，網絡中布置25個節點，以網格狀均勻分布在場景大小為1 000×1 000 m2范圍內，傳輸距離和干擾距離分別為250 m和500 m。每個節點配置兩個無線接口，每個業務源的流量取值為0～500 kbit/s，仿真時間為20 s。以吞吐量、端到端時延作為性能評價指標，與LACA算法[2]及公共信道分配算法（CCA）[10]進行對比分析。

圖1、2顯示了CMCA算法、LACA算法及CCA算法的吞吐量和時延隨業務流數目增加的變化情況。

當網絡負載較輕時，各個算法所獲得的網絡吞吐量相差不大；隨著網絡負載的增加，采用CMCA算法的吞吐量逐漸優于其他兩個算法，當業務流數目增加到20條時，采用CMCA算法獲得的網絡吞吐量可達到LACA算法的1.2倍左右。這是因為CMCA算法在信道分配時以最小干擾為目標，各信道間干擾的降低有效地提高了數據傳輸率，從而獲得較好的網絡性能；而LACA算法在進行信道分配時，側重于各信道間的負載均衡，因此在網絡負載不高時，其比CMCA算法的性能稍差。

隨著網絡負載的加重，LACA算法在業務流數目為25時獲得較好的網絡性能，但同時由于其基于已知流量模型，在信道分配時需事先預知每條鏈路上的流量負載，再根據假定的預知值進行信道分配，該算法不能滿足實時動態網絡業務突發性的要求，因此當網絡負載持續加重時，其獲得的網絡性能反而較差。而CMCA算法基于未知流量模型，利用最大流算法求解網絡中能達到的最大吞吐量及其每條鏈路的流量負載情況，并依次進行信道分配，能較好地適應網絡中業務流量的動態變化，因此當網絡負載加重時也能獲得相對較好的網絡性能。CCA算法是一種公共信道分配算法，算法中每個節點的射頻信道分配都相同，限制了使用信道的多樣性，無法充分利用多信道的資源，因而在整個實驗過程中獲得的網絡吞吐量較低。

4 結束語

本文提出了一種基于最大流的信道分配算法，算法先通過最大流進行計算，得出網絡中可達到的最大吞吐量及相關鏈路可達到的最大負載量，以此作為信道分配的依據。同時，算法充分考慮到網絡獲得最大吞吐量時每條鏈路所承載的最大流量負載，優先為流量負載較大的鏈路分配信道，使網絡能夠較好地適應各種業務的需求。仿真結果表明，本文算法即使在網絡負載較重的情況下，仍能保持較好的網絡性能。

參考文獻

1 Akyildiz I F,Wang Xudong,Wang Weilin.Wireless mesh networks:a survey.Computer Network Journal(Elsevier),2005,47(4):445～487

2 Raniwala A,Gopalan K,Chiueh T.Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks.Mobile Computing and Communications Review,2004,8(2):50～65

3 Alicherry M,Bhatia R,Li L.Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks.In:Proceedings of the ACM MobiCom,2005

4 Das A K,Alazemi H M K,Vijayakumar R,et al.Optimization models for fixed channel assignment in wireless mesh networks with multiple radios.In:Proceedings of IEEE SECON,Santa Clara,CA,2005

5 Mohsenian Rad A H,Wong V W S.Joint logical topology design,interface assignment,channel allocation,and routing for multi-channel wireless mesh networks.IEEE Transactions on Wireless Communications,2007,6(12):4 432～4 440

6 Raniwala A,Chiueh T C.Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network.In:Proceedings of IEEE INFOCOM,2005

7 Xin Wang,Garcia-Luna-Aceves J J.Distributed joint channel assignment,routing and scheduling for wireless mesh networks.Computer Communications,2008(7):1 436～1 446

8 Aoun B,Boutaba R,Kenward G.Analysis ofcapacity improvements in multi-radio wireless mesh networks. In:Proceedings of Vehicular Technology Conference,IEEE 63rd,2006

9 ns-2.http://www.isi.edu/nsnam/ns/

10 Adya A,Bahl P,Padhye J,et al.A multi-radio unification protocol for IEEE 802.11 wireless networks.In:Proceedings of BROADNETS’04,San Jose,California,USA,2004

11 Hejiao Huang,Xiaolu Cao, Xiaohua Jia, et al. Channel assignmentusing block design in wirelessmesh networks.Computer Communication,2009(9):1 148～1 153

12 畢坤,顧乃杰,任開新等.混合式無線mesh網絡中信道分配算法研究.小型微型計算機系統,2009,5(5):812～816

13 嚴軍榮，張順頤，龍華等.基于拓撲分割的無線mesh網絡信道分配策略.電子與信息學報，2009,31(7)：1 588～1 593

14 Marina M,Das S R,Subramanian A P.A topology control approach for utilizing multiple channels in multi-radio wireless mesh networks.Computer Networks,2010,54(2):241～256