基于分組管理的無(wú)線(xiàn)mesh網(wǎng)多信道分配算法

摘 要:為了合理利用多信道來(lái)提高無(wú)線(xiàn)網(wǎng)絡(luò)吞吐量，針對(duì)基于802.11標(biāo)準(zhǔn)無(wú)線(xiàn)mesh網(wǎng)的業(yè)務(wù)特點(diǎn)，提出了基于分組管理的分布式多信道分配算法。該算法將節(jié)點(diǎn)接口分為回程接口與轉(zhuǎn)發(fā)接口，并使回程接口分配到在干擾區(qū)域內(nèi)干擾值盡可能小的信道。仿真實(shí)驗(yàn)結(jié)果表明，該算法可以減少區(qū)域干擾，并可充分利用信道的多樣性和得到較高的網(wǎng)絡(luò)吞吐量。

關(guān)鍵詞:無(wú)線(xiàn)mesh網(wǎng); 多信道; 分組; 干擾值; opnet

中圖分類(lèi)號(hào):TP393

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)02-0661-03

doi:10.3969/j.issn.1001-3695.2010.02.071

Multi-channel allocation algorithm of wireless mesh networksbased on group management

JIANG Hang-zhou， SUN Ji-feng

(School of Electronic Information Engineering， South China University of Technology， Guangzhou 510640， China)

Abstract:To improve network throughput by using multi-channel properly， proposed distributed multi-channel allocation method based on group management， according to the traffic characteristics of the wireless mesh networks based on 802.11 standards. This method divided the interfaces in node into backhaul interfaces and data transfer interfaces， and could allocate channels to the backhaul interfaces with the least channel interference cost in the interference region. Simulation results show that the proposed method can reduce regional interference， take full advantage of the diversity of channel and get better network throughput.

Key words:WMN; multi-channel; group-based; interference cost; opnet

無(wú)線(xiàn)mesh網(wǎng)絡(luò)是由一些無(wú)線(xiàn)mesh路由器(MR)和mesh終端設(shè)備組成的多跳無(wú)線(xiàn)網(wǎng)絡(luò)，主要用于擴(kuò)張Internet的覆蓋范圍，在網(wǎng)絡(luò)邊緣為無(wú)線(xiàn)用戶(hù)提供最后一公里的接入服務(wù)。按照節(jié)點(diǎn)的功能不同可劃分為基礎(chǔ)設(shè)施mesh網(wǎng)、終端設(shè)備mesh網(wǎng)和混合式mesh網(wǎng)。在基礎(chǔ)設(shè)施mesh網(wǎng)中，所有MR之間形成自組織、自愈的骨干網(wǎng)，每個(gè)MR為終端設(shè)備提供骨干網(wǎng)的接入功能。802.11系列標(biāo)準(zhǔn)[1]可以提供多個(gè)信道的使用，802.11b/g可提供3個(gè)互相正交的可使用的信道，802.11a甚至可以提供多至12個(gè)互不重疊的信道。另外，物理技術(shù)的發(fā)展讓一個(gè)節(jié)點(diǎn)擁有多個(gè)網(wǎng)卡(本文中網(wǎng)卡與接口屬同一意思)成為可能。在多網(wǎng)卡多信道的節(jié)點(diǎn)中，如何做到將合適的信道分配給合適的網(wǎng)卡[2]，從而使得整個(gè)網(wǎng)絡(luò)的吞吐量能達(dá)到最大化，這是研究這個(gè)問(wèn)題的關(guān)鍵所在。

文獻(xiàn)[3]將信道的分配與路由協(xié)議相結(jié)合，提出了hyacinth集中式信道分配算法，整個(gè)信道分配過(guò)程是一個(gè)復(fù)雜的迭代優(yōu)化的過(guò)程。文獻(xiàn)[4]首先將在無(wú)線(xiàn)mesh網(wǎng)體系結(jié)構(gòu)中的信道分配所需的約束抽象成公式，然后利用這些約束作為條件，求目標(biāo)函數(shù)為網(wǎng)絡(luò)吞吐量的最大值。文獻(xiàn)[3~5]均屬于集中式信道分配方式，不能及時(shí)反映局部網(wǎng)絡(luò)性能的變化。文獻(xiàn)[6]考慮網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)陌踩裕瑢踩蛩刈鳛樾诺婪峙淇紤]的重要問(wèn)題。本文引入信道干擾區(qū)域內(nèi)干擾值的概念，將信道根據(jù)干擾值大小進(jìn)行分組管理，提出了基于分組管理的分布式多信道分配算法。

1 Mesh網(wǎng)信道分配模型

1.1 約束條件

在多信道多網(wǎng)卡無(wú)線(xiàn)mesh網(wǎng)中，信道的分配問(wèn)題必須滿(mǎn)足以下幾個(gè)約束條件[7]。假設(shè)網(wǎng)絡(luò)中有N個(gè)靜態(tài)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有I個(gè)網(wǎng)卡，每個(gè)網(wǎng)卡可以分配C個(gè)信道，有L條單向鏈路。假設(shè):

xcl=1 if lth link uses the cth channel

0 otherwise(1)

for c=1，…，C，l=1，…，L。研究的信道分配問(wèn)題是基于節(jié)點(diǎn)接口數(shù)少于信道數(shù)的情況，所以必須滿(mǎn)足約束條件Ⅱ:

I

每條鏈路在某個(gè)時(shí)刻只可以分配一個(gè)信道，所以對(duì)于鏈路l必須滿(mǎn)足約束條件Ⅱ:

x1l+…+xCl=1AX=1(3)

其中:A=(1…1)1×C;X=(x1l…xCl)TC×1;同時(shí)，在某個(gè)時(shí)刻同一鏈路上互相通信的兩個(gè)接口必須分配在同一信道上，滿(mǎn)足約束條件Ⅲ:

xcu-xcv=0BX=0(4)

其中:B=(1，-1);X=(xcu，xcv)T。另外，為保證信道分配的有效性，分配給鏈路l的信道帶寬必須大于或等于鏈路的負(fù)載，滿(mǎn)足約束條件Ⅳ:

BWcl≥Cl(5)

其中:BWcl表示分配給鏈路l的信道c的帶寬;Cl表示鏈路l的容量。

1.2 信道分配準(zhǔn)則

在無(wú)線(xiàn)通信中，無(wú)線(xiàn)鏈路是一種廣播媒介，每一個(gè)傳輸都可能影響網(wǎng)絡(luò)系統(tǒng)中的多個(gè)接收終端，因此，信道之間干擾是導(dǎo)致無(wú)線(xiàn)網(wǎng)絡(luò)性能下降的主要原因之一[8]。假設(shè)節(jié)點(diǎn)的傳輸距離為d，干擾范圍為2d，若節(jié)點(diǎn)n(n=1，…，N)的某個(gè)接口i使用的信道為cni，Si為信道cni干擾范圍內(nèi)的節(jié)點(diǎn)集。

f(cni，cmj)=1 cni=cmj

0 cni≠cmj(6)

其中:cmj表示其他節(jié)點(diǎn)接口使用的信道;f(cni，cmj)表示信道干擾值，若存在干擾為1，反之為0。那么信道cni在干擾區(qū)域范圍內(nèi)的干擾值為

F(cni)=∑m∈Si ∑Ij=1f(cni，cmj)(7)

其中:cni，cmj∈{1，…，C}。

無(wú)線(xiàn)鏈路的容量是不固定的，它是其他一些網(wǎng)絡(luò)參數(shù)的函數(shù)[9]，如鏈路l的容量可以用式(8)來(lái)表示。

Cl(P，cni，Y)=(1/T)log(1+SINRl(P，cni，Y))(8)

其中:P為傳輸功率;Y為節(jié)點(diǎn)位置;cni為鏈路l使用的信道;SINRl為信號(hào)干擾噪聲比。要想使得鏈路l的容量最大則要求SINRl最大，而SINRl可以用式(9)簡(jiǎn)單表示[9]:

SINRl=gllpl/(F(cni)∑k≠l∈Lpkglk+nl)(9)

其中:p1、pk分別為鏈路l、k的傳輸功率;gll為鏈路l的增益;glk為鏈路l和k之間的增益;nl為噪聲。可以看出要使SINRl最大則要求F(cni)∑k≠l∈Lpkglk+nl最小，若假設(shè)傳輸功率、鏈路增益與噪聲都保持一定，那么就要求F(cni)最小，即

Fmin=min{F(cni)}，cni={1，…，C}(10)

從式(10)可以看出，在多信道分配的問(wèn)題中，要想得到較大的鏈路容量，從而達(dá)到較高的網(wǎng)絡(luò)吞吐量，必須在信道干擾區(qū)域內(nèi)分配干擾值最小的信道給對(duì)應(yīng)的鏈路。本文依據(jù)信道干擾值的大小對(duì)信道進(jìn)行分組，分為信道狀態(tài)較好組(better state group， BSG)與信道狀態(tài)較差組(poor state group， PSG)。

2 信道分配算法

在基礎(chǔ)設(shè)施無(wú)線(xiàn)mesh網(wǎng)中，主要業(yè)務(wù)有兩種[10]，即去往網(wǎng)關(guān)節(jié)點(diǎn)的業(yè)務(wù)和mesh內(nèi)部業(yè)務(wù)。根據(jù)業(yè)務(wù)特點(diǎn)，將節(jié)點(diǎn)的接口分配成兩種類(lèi)型:a)回程接口(backhaul interface， BI)，主要負(fù)責(zé)去往網(wǎng)關(guān)業(yè)務(wù)的傳輸;b)內(nèi)部業(yè)務(wù)數(shù)據(jù)轉(zhuǎn)發(fā)接口，簡(jiǎn)稱(chēng)轉(zhuǎn)發(fā)接口(transfer interface， TI)，主要負(fù)責(zé)數(shù)據(jù)傳輸和網(wǎng)內(nèi)終端節(jié)點(diǎn)之間業(yè)務(wù)的轉(zhuǎn)發(fā)。本文只考慮一個(gè)節(jié)點(diǎn)擁有兩個(gè)接口的情況，即在節(jié)點(diǎn)中BI與TI分別為一個(gè)。

由于大部分業(yè)務(wù)都是去往網(wǎng)關(guān)的，離網(wǎng)關(guān)節(jié)點(diǎn)近的鏈路所承擔(dān)的負(fù)載更大，反之較少。基于這一特點(diǎn)，在給BI接口分配信道時(shí)都是從BSG組中選取，并保持固定一定時(shí)間，以保證通往網(wǎng)關(guān)的業(yè)務(wù)能獲得更高的鏈路容量;而TI接口可以自由切換，以保證充分利用信道的多樣性。

信道分配算法步驟如下:

初始化:網(wǎng)絡(luò)拓?fù)湫纬桑鱉R節(jié)點(diǎn)隨機(jī)選取信道，計(jì)算到網(wǎng)關(guān)的最小跳數(shù)。

a)對(duì)于節(jié)點(diǎn)中的BI接口執(zhí)行算法Ⅰ:

begin procedure

Fmin=F(cni)

for cni=1→C

F(cni)=∑m∈Si∑2j=1f(cni，cmj)

if k∈{1→C} s.t.F(k)

Fmin=F(k)

end if

end procedure

節(jié)點(diǎn)計(jì)算干擾區(qū)域內(nèi)各信道干擾值F(cni)，并根據(jù)信道干擾值對(duì)信道排序分組，選取中排序最高的信道作為其固定信道。

b)節(jié)點(diǎn)中的TI接口執(zhí)行算法Ⅱ:

begin procedure

if Ccurrent used==CBI used

select the first channel from PSG

else

keep original channel

end procedure

c)為保持網(wǎng)絡(luò)的連通性，節(jié)點(diǎn)中TI接口定時(shí)約定在PSG中的最后一個(gè)信道上。

在算法Ⅱ中Ccurrent used表示TI接口當(dāng)前使用的信道，CBI used表示BI接口所分配的信道。

由于給BI接口分配的都是本干擾區(qū)域內(nèi)干擾值最小的信道，那么在不斷尋找干擾值最小信道的過(guò)程中，是否會(huì)引起信道的頻繁切換[11]，整個(gè)過(guò)程是否能收斂到一個(gè)穩(wěn)定的狀態(tài)，本文做了如下證明。

假設(shè)節(jié)點(diǎn)n的BI接口i從t1時(shí)刻的信道cni(t1)切換到t2時(shí)刻干擾值更少的信道cni(t2)，其他節(jié)點(diǎn)的接口的信道沒(méi)有發(fā)生變化，F(xiàn)t1、Ft2分別表示t1、t2時(shí)刻干擾區(qū)域內(nèi)的干擾總值，Si為干擾區(qū)域內(nèi)節(jié)點(diǎn)集。由于i接口是切換到信道干擾值更小的信道，則F(cni(t1))>F(cni(t2))。另外，由于假設(shè)其他節(jié)點(diǎn)在接口i切換信道的同時(shí)沒(méi)有發(fā)生信道切換，干擾區(qū)域范圍以外的干擾值不發(fā)生任何變化。對(duì)于Si集內(nèi)其他節(jié)點(diǎn)m的接口j，當(dāng)接口i信道切換后的干擾值為

Fmj(t2)=Fmj(t1)+f(cmj，cni(t2))-f(cmj，cni(t1))(11)

其中:Fmj(t1)、Fmj(t2)分別表示t1、t2時(shí)刻節(jié)點(diǎn)m中接口j的干擾值。所以有

Ft1=∑m∈Si∑2j=1Fmj(t1)+F(cni(t1))=

Ft2=F(cni(t2))+∑m∈Si∑2j=1Fmj(t2)=

(12)

F(cni(t2))+∑m∈Si∑2j=1(Fmj(t1)+f(cmj，cni(t2))-f(cmj，cni(t1)))=

F(cni(t2))+∑m∈Si∑2j=1Fmj(t1)+∑m∈Si∑2j=1f(cmj，cni(t2))-∑m∈Si∑2j=1f(cmj，cni(t1))=

F(cni(t2))+∑m∈Si∑2j=1Fmj(t1)+F(cni(t2))-F(cni(t1))= (13)

∑m∈Si∑2j=1Fmj(t1)+F(cni(t1))+2[F(cni(t2))-F(cni(t1))]=

Ft1+2[F(cni(t2))-F(cni(t1))]

由于F(cni(t1))>F(cni(t2))，F(xiàn)t2

在信道分配算法完成后，各節(jié)點(diǎn)保存BSG列表、PSG列表和鄰居信息表(neighbor interface information table， NIT)。節(jié)點(diǎn)中TI接口和BI接口都定期廣播hello包，告訴鄰居接口自己現(xiàn)使用的信道(BI接口固定信道)、IP地址、MAC地址。如圖1所示，對(duì)于TI接口與BI接口，它們廣播的hello包類(lèi)型有所不同，前者廣播的是此時(shí)正使用的信道，而后者廣播的是固定信道;另外在NIT表中，若鄰居是BI接口，則保存其固定信道，若是TI接口則保存此時(shí)用的信道。如圖2所示，若存在一條從節(jié)點(diǎn)A發(fā)往網(wǎng)關(guān)節(jié)點(diǎn)的業(yè)務(wù)流，經(jīng)過(guò)路徑ABC，各節(jié)點(diǎn)的BI接口的固定信道已分配，那么通信過(guò)程為:A節(jié)點(diǎn)TI接口根據(jù)鄰居信息表從信道4切換到2;B節(jié)點(diǎn)的TI接口從信道1切換到3，完成通信過(guò)程。

BSGI/2CH(1)…CH(I/2)

PSGI/2CH(I/2+1)…CH(I)

(a)BSG列表

(b)PSG列表

typeflaglifetime(固定)信道IP地址MAC地址

typelifetimeIP地址MAC地址(固定)信道

(c)Hello包格式

(d)鄰居信息列表

圖1 信道分配中使用的信息列表

3 仿真實(shí)驗(yàn)

本文采用opnet modeler網(wǎng)絡(luò)仿真軟件[12]對(duì)本文提出的信道分配算法進(jìn)行仿真。仿真基本參數(shù)設(shè)置分別是物理層技術(shù)為IEEE 802.11a OFDM;MAC層協(xié)議為IEEE 802.11 DCF;傳輸距離為250 m;干擾范圍為450 m;數(shù)據(jù)傳輸率為54 Mbps。

3.1 鏈型拓?fù)鋱?chǎng)景

首先將本文提出的方案應(yīng)用于單鏈型的拓?fù)浣Y(jié)構(gòu)，鏈的跳數(shù)從1跳到7跳變化;業(yè)務(wù)流為從第一個(gè)節(jié)點(diǎn)到末端節(jié)點(diǎn)的CBR數(shù)據(jù)流;信道數(shù)從兩個(gè)變化為四個(gè)，仿真時(shí)間為100 s，仿真結(jié)果如圖3所示。從結(jié)果可以看出，在單接口單信道的情況下，吞吐量在兩跳后就顯著下降了。主要原因可能有兩方面:a)使用同一信道，干擾情況較嚴(yán)重;b)中間節(jié)點(diǎn)只有一個(gè)接口，不能同時(shí)發(fā)送和接收，造成了吞吐量的下降。在使用四信道的情況，執(zhí)行本文提出的算法后， BI接口可以盡可能地分配不同的信道，由于干擾較小，同時(shí)節(jié)點(diǎn)可以同時(shí)發(fā)送和接收數(shù)據(jù)，甚至到第四跳吞吐量都沒(méi)有發(fā)生明顯下降。

3.2 隨機(jī)拓?fù)鋱?chǎng)景

這部分主要仿真隨著FTP業(yè)務(wù)流數(shù)目的變化，隨機(jī)拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)中吞吐量的變化。20個(gè)節(jié)點(diǎn)隨機(jī)分布在800 m×800 m的場(chǎng)景中，F(xiàn)TP服務(wù)器設(shè)置在中心位置，其他節(jié)點(diǎn)隨機(jī)分布，仿真時(shí)間設(shè)置為240 s，流業(yè)務(wù)為較重的FIP業(yè)務(wù)，數(shù)目從2變化到15。仿真分四種情況，依次為:單網(wǎng)卡單信道、兩網(wǎng)卡兩信道、兩網(wǎng)卡四信道、兩網(wǎng)卡六信道。第一種不執(zhí)行任何信道分配算法，后三種執(zhí)行本文的信道分配算法。仿真結(jié)果如圖4、5所示。圖4是表示歸一化網(wǎng)絡(luò)總計(jì)吞吐量，從圖上可以看出，總的趨勢(shì)上看，本文提出的信道分配算法可以得到更高的網(wǎng)絡(luò)吞吐量，在使用六信道的情況下，最高的吞吐量甚至可以達(dá)到單網(wǎng)卡單信道情況下的7.57倍。可以看到，當(dāng)FTP流數(shù)目較小時(shí)，多信道的優(yōu)勢(shì)并不是很明顯，隨著FTP流數(shù)的增加，單信道干擾嚴(yán)重的問(wèn)題開(kāi)始凸顯，而多信道的合理使用可以較好地克服這一缺點(diǎn)。

圖5反映了MAC層媒介訪(fǎng)問(wèn)延時(shí)情況。在這里，本文作了歸一化處理。可以看到，隨著FTP流數(shù)的增加，多信道情況下的延時(shí)均低于單信道，兩網(wǎng)卡六信道情況下的最少的延時(shí)是單信道單網(wǎng)卡的0.113倍。可能原因是隨著業(yè)務(wù)流的增加單信道需要頻繁的信道掃描和信道競(jìng)爭(zhēng)增加了延時(shí)，而多信道更多的是信道之間的切換。在業(yè)務(wù)流數(shù)較小時(shí)，甚至出現(xiàn)比單信道延時(shí)更大的情況，可能的原因是一方面由于可利用的信道數(shù)相對(duì)較少，在干擾區(qū)域內(nèi)，節(jié)點(diǎn)之間的信道競(jìng)爭(zhēng)依然激烈;另一方面，接口因?qū)ふ易钚「蓴_值信道需要信道切換的次數(shù)的增多也導(dǎo)致了延時(shí)的增加。可以看到，當(dāng)信道數(shù)增加為6時(shí)，這一情況得到了很好的解決。

4 結(jié)束語(yǔ)

本文首先總結(jié)了無(wú)線(xiàn)mesh網(wǎng)本身所具有的結(jié)構(gòu)和業(yè)務(wù)特點(diǎn)。通過(guò)分析發(fā)現(xiàn)要想無(wú)線(xiàn)鏈路的容量達(dá)到最大化，從而增加網(wǎng)絡(luò)總和吞吐量，必須要使接口選取在干擾范圍內(nèi)干擾值最小的信道作為工作信道。本文使用雙接口的節(jié)點(diǎn)體系結(jié)構(gòu)，將接口分為數(shù)據(jù)回程接口和網(wǎng)內(nèi)數(shù)據(jù)轉(zhuǎn)發(fā)接口，并根據(jù)信道干擾值大小，提出了基于信道分組管理的分布式信道分配算法，通過(guò)仿真發(fā)現(xiàn)可以在總體上得到更高的網(wǎng)絡(luò)吞吐量和更低的媒介訪(fǎng)問(wèn)延時(shí)。同時(shí)，為了分組方便，本文只選用了兩個(gè)接口和偶數(shù)個(gè)信道進(jìn)行仿真研究，對(duì)于使用任意個(gè)接口，任意個(gè)信道，網(wǎng)絡(luò)性能如何變化將是下一步的研究工作。

參考文獻(xiàn):

[1]802.11drafts[EB/OL].(2007-07-20)[2009-06-01].http//www.ieee802.org/11/.

[2]SKALLI H， GHOSH S， DAS S K， et al. Channel assignment strategies for multi-radio wireless mesh networks: issues and solutions[J]. IEEE Communications Magazine， 2007，45(11):86-95.

[3]RANIWALA A ， GOPALAN K， CHIUEH T C. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks [J]. Mobile Computing and Communications Review， 2004，8(2):50-65.

[4]RAD H M， WONG V W S. Logical topology design and interface assignment for multi-channel wireless mesh networks[C]//Proc of IEEE Global Telecommuaications Conference. Piscataway， NJ: IEEE，2006:1-6.

[5]RAMACHANDRAN K N， BELDING E M， ALMEROTH K C， et al. Interference-aware channel assignment in multi-radio wireless mesh networks[C]//Proc of the 25th IEEE International Conference on Computer Communications.Piscataway， NJ:IEEE，2006:1-12.

[6]HAD A， NAVEED A， KANHERE. Securing channel assignment in multi-radio multi-channel wireless mesh networks[C]//Proc of IEEE.[S.l.]:IEEE，2007:3111-3116.

[7]RANIWALA A， CHIUEH T. Architectrue and algorithms for an IEEE 802.11-based multi-channel wireless mesh networks[C]//Proc of IEEE INFOCOM.2005:2223-2234.

[8]JAIN K， PADHYE J， PADMANABHAN V N， et al. Impact of interference on multi-hop wireless network performance[C]//Proc of the 9th Annual International Conference on MCAN. New York: ACM Press，2003:66-80.

[9]靳榮利.多網(wǎng)卡無(wú)線(xiàn)mesh網(wǎng)絡(luò)中多信道MAC協(xié)議研究[D].北京:北京郵電大學(xué)，2007.

[10]LIM A O， WANG Xu-dong， KADD Y， et al. A hybrid centralized routing protocol for 802.11s WMNs[J]. MobleNetwAppl，2008，13(1-2):117-131.

[11]KO B J， MISRA V， PADHYE J， et al. Distributed channel assignment in multi-radio 802.11 mesh networks[C]//Proc of IEEE Wireless Communications and Networking Conference.[S.l.]: IEEE Press，2007: 3978-3983.

[12]Opnet Technologies Inc[EB/OL].http://www.opnet.com.