一種新的基于最大流的無線Mesh網(wǎng)絡(luò)信道分配算法*

葛志輝，李陶深，韋亞歡

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院 南寧530004）

1 引言

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

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

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

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

上述信道分配方案中大多數(shù)算法都是假定網(wǎng)絡(luò)流量模型已知，根據(jù)已知的流量信息進(jìn)行信道分配及網(wǎng)絡(luò)優(yōu)化。雖然這些方法對已知流量模型的網(wǎng)絡(luò)都能進(jìn)行某種優(yōu)化工作，但它們并不適合實(shí)時(shí)動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境。在實(shí)際網(wǎng)絡(luò)環(huán)境中，很多業(yè)務(wù)是突發(fā)且無法預(yù)知的，因此本文提出一種基于未知流量模型的信道分配算法。首先利用最大流方法計(jì)算網(wǎng)絡(luò)所能達(dá)到的最大吞吐量及在此條件下每條鏈路承載的不同流量負(fù)載，然后以此作為信道分配的依據(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é)點(diǎn)的集合，E表示所有無向鏈路的集合。假設(shè)每個(gè)節(jié)點(diǎn)i配置了R(i)個(gè)網(wǎng)卡，網(wǎng)絡(luò)中可以使用|H|個(gè)正交無線信道。對于WMN中的任意兩個(gè)節(jié)點(diǎn)i,j∈V，記d(i,j)為 i、j之間的距離，r表示發(fā)射距離。如果 d(i,j)≤r，表示節(jié)點(diǎn)在i、j各自的通信范圍內(nèi)，則i和 j之間存在一條無向邊，即 ei,j∈E。

2.2 干擾模型

對于物理拓?fù)?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ū)域中，使用信道同時(shí)進(jìn)行通信時(shí)會(huì)產(chǎn)生干擾。因此，在進(jìn)行信道分配時(shí)，盡量使同一沖突區(qū)域內(nèi)各相關(guān)鏈路使用不同的信道。當(dāng)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的信道分配結(jié)束后，即各鏈路所使用的信道已確定，那么它的干擾鏈路集合也可知。此時(shí)，對于任意鏈路e，其干擾度可表示為：

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

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

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

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

2.4 信道分配

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

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

3 性能評價(jià)

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)

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

13 嚴(yán)軍榮，張順頤，龍華等.基于拓?fù)浞指畹臒o線mesh網(wǎng)絡(luò)信道分配策略.電子與信息學(xué)報(bào)，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