葛志輝，李陶深，韋亞歡

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

1 引言

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

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

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

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

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

2 系統(tǒng)模型與系統(tǒng)假設(shè)

2.1 網(wǎng)絡(luò)模型

用無向圖G(V，E)表示多信道無線Mesh網(wǎng)絡(luò)，其中V表示所有節(jié)點的集合，E表示所有無向鏈路的集合。假設(shè)每個節(jié)點i配置了R(i)個網(wǎng)卡，網(wǎng)絡(luò)中可以使用|H|個正交無線信道。對于WMN中的任意兩個節(jié)點i,j∈V，記d(i,j)為 i、j之間的距離，r表示發(fā)射距離。如果 d(i,j)≤r，表示節(jié)點在i、j各自的通信范圍內(nèi)，則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的所有干擾鏈路集合可以表示為：

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

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

2.3 業(yè)務(wù)模型

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

假定鏈路的流量負載用符號f表示。業(yè)務(wù)從源端到目的端時，經(jīng)由鏈路eij并在該鏈路上的負載為：

2.4 信道分配

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

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

3 性能評價

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

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

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

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

4 結(jié)束語

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

參考文獻

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網(wǎng)絡(luò)中信道分配算法研究.小型微型計算機系統(tǒng),2009,5(5):812～816

13 嚴軍榮，張順頤，龍華等.基于拓撲分割的無線mesh網(wǎng)絡(luò)信道分配策略.電子與信息學報，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