多信道無(wú)線Mesh網(wǎng)絡(luò)信道分配算法

1、多信道無(wú)線Mesh網(wǎng)絡(luò)信道分配算法第29卷第7期2021年7月計(jì)算機(jī)應(yīng)用JournalofComputerApplieationsJuly2021文章編號(hào):10019081(2021)071849一o3多信道無(wú)線Mesh網(wǎng)絡(luò)信道分配算法彭利民,劉浩(1.華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣州510641;2.廣州體育學(xué)院計(jì)算機(jī)應(yīng)用教研室,廣州510500)(penglm86126.tom)摘要:針對(duì)無(wú)線Mesh網(wǎng)絡(luò)的網(wǎng)絡(luò)容量?jī)?yōu)化問題,通過(guò)對(duì)無(wú)線鏈路的干擾進(jìn)行量化,利用整數(shù)線性規(guī)劃公式對(duì)信道分配進(jìn)行描述;在信道分配時(shí),應(yīng)用目標(biāo)函數(shù)對(duì)信道分配進(jìn)行優(yōu)化,減少網(wǎng)絡(luò)總的干擾權(quán)重,并在此根底上提出一個(gè)信道

2、分配的啟發(fā)式算法.仿真結(jié)果說(shuō)明,該算法能提高網(wǎng)絡(luò)的吞吐量.關(guān)鍵詞:無(wú)線網(wǎng)狀網(wǎng);信道分配;干擾;整數(shù)線性規(guī)劃;均勻流量中圖分類號(hào):TP393.03文獻(xiàn)標(biāo)志碼:AChannelassignmentalgorithminmulti-channelwirelessmeshnetworks(1.SchoolofComputerScienceandEngineering,SouthChinaUniversityofTechnology,GuangzhouGuangdong510641,China;2.ComputerApplicationTeachingDepartment,GuangzhouSportU

3、niversity,GuangzhouGttangdong510500,China)Abstract:Concerningtheoptimizationproblemofnetworkcapacityinthewirelessmeshnetworks,thispaperquantifiedinterferenceofwirelesslink,andformulatedthechannelassignmentasintegerlinearprogram,thenproposedachannelassignmentheuristicalgorithmbyusingobjectivefunction

4、foroptimizingchannelassignmentinordertominimizetheoverallthroughputcanbeimprovedsignificantlybytheproposedalgorithm.Keywords:WirelessMeshNetwork(WMN);channelassignment;interference;integerlinearprogram;uniformtraffic0引言隨著移動(dòng)通信技術(shù)的開展,傳統(tǒng)的無(wú)線接入方式面臨接人帶寬缺乏,效勞質(zhì)量得不到保證,難以適應(yīng)靈活多變的業(yè)務(wù)狀況等問題.無(wú)線網(wǎng)狀網(wǎng)(WirelessMeshNetwor

5、k,WMN)是一種由網(wǎng)狀分布的無(wú)線節(jié)點(diǎn)構(gòu)成,通過(guò)節(jié)點(diǎn)自動(dòng)發(fā)現(xiàn),網(wǎng)絡(luò)拓?fù)渥詣?dòng)維護(hù)和多跳路由轉(zhuǎn)發(fā),實(shí)現(xiàn)節(jié)點(diǎn)間互連的網(wǎng)絡(luò)技術(shù).WMN不但具有分布式自組織的網(wǎng)絡(luò)特征,而且還可以利用多種通信手段(如IEEE802.11,WiMax,ZigBee等)為用戶提供高速率的接入方式,從而解決無(wú)線寬帶接入面臨的嚴(yán)重問題.許多文獻(xiàn)對(duì)WMN的網(wǎng)絡(luò)性能進(jìn)行了深入的研究,文獻(xiàn)3通過(guò)分析信道分配的關(guān)鍵問題,給出了信道分配與路由的相互關(guān)系,提出了一個(gè)最大化網(wǎng)絡(luò)吞吐量啟發(fā)式算法,文獻(xiàn)4在網(wǎng)絡(luò)業(yè)務(wù)流量均勻分布的情況下,基于無(wú)線信道的沖突圖模型,利用頂點(diǎn)著色的Tabu搜索算法和最大K度切割算法,研究了WMN的信道分配問題,文獻(xiàn)5聯(lián)

6、合邏輯拓?fù)湓O(shè)計(jì),接口分配,信道分配和路由四個(gè)問題,使用TiMesh結(jié)構(gòu)研究了WMN的網(wǎng)絡(luò)容量問題.文獻(xiàn)6通過(guò)建立WMN的沖突圖模型,按照WMN中節(jié)點(diǎn)的干擾權(quán)重大小,為每個(gè)節(jié)點(diǎn)設(shè)信道是共享信道,節(jié)點(diǎn)之間的通信存在競(jìng)爭(zhēng),同一信道在其鄰近區(qū)域存在干擾,因此,在進(jìn)行信道分配時(shí),必須考慮無(wú)線鏈路之間的相互影響.本文在已有研究的根底上,通過(guò)分析多信道WMN的特點(diǎn),假定業(yè)務(wù)流量均勻分布的狀態(tài)下,借助無(wú)線網(wǎng)絡(luò)協(xié)議層干擾模型,對(duì)無(wú)線鏈路的干擾進(jìn)行量化,提出一個(gè)減少鏈路干擾的信道分配啟發(fā)式算法,到達(dá)了提高網(wǎng)絡(luò)吞吐量的目的.1WMN符號(hào)描述及定義WMN由網(wǎng)狀分布的無(wú)線節(jié)點(diǎn)構(gòu)成,K(u)表示節(jié)點(diǎn)"可用的網(wǎng)卡

7、數(shù),C(")表示節(jié)點(diǎn)/,可用的信道,WMN可用的信道數(shù)為fC,假定網(wǎng)絡(luò)中所有節(jié)點(diǎn)的發(fā)射功率均相等,其發(fā)射距離.y,以及相應(yīng)的干擾距離y,也均相等.定義1WMN的物理拓?fù)銰(,E).其中,表示W(wǎng)MN所有節(jié)點(diǎn)集合,E表示W(wǎng)MN中所有的無(wú)向邊集合,對(duì)于節(jié)點(diǎn)m,n,其中m,neN,如果r/,在m點(diǎn)的通信范圍內(nèi),即D(n,m),那么頂點(diǎn)m和n之間存在無(wú)向邊,即:如果存在一條邊eeE,那么當(dāng)且僅當(dāng)eeE.定義2WMN的虛擬拓?fù)銰=(V,E).其中,表示W(wǎng)MN所有節(jié)點(diǎn)集合,表示W(wǎng)MN中所有的通信鏈路集合,當(dāng)網(wǎng)絡(luò)信道分配完成后,如果WMN中的節(jié)點(diǎn),V使用信道C建立了通信,其中,eE,那么那么存在通信

8、鏈路e:.定義3鏈路e"潛在的"干擾度PI(e).根據(jù)WMN的協(xié)議層干擾模型,如果G(V,E)上存在兩條邊mnE和|pgE,且mind(m,P),d(m,q),d(n,p),d(n,q)R,那么就稱這兩條邊為"潛在的"干擾邊,根據(jù)此定義,我們使用N(e)表示所有和鏈路e存在"潛在的"干擾的鏈路集合,那么鏈路e的"潛在的"干擾度為收稿日期:2021一O113;修回日期:202103一t1.基金工程:廣東省自然科學(xué)基金資助工程(05011896).作者簡(jiǎn)介:彭利民(1976一),男,湖南邵陽(yáng)人,講師,博士研究生,主要研

9、究方向:無(wú)線網(wǎng)絡(luò),并行計(jì)算;劉浩(1977一),男,湖南邵陽(yáng)人,博士研究生,主要研究方向:P2P,并行計(jì)算.1850計(jì)算機(jī)應(yīng)用第29卷IN(e)I.定義4鏈路e的干擾權(quán)重,(e).當(dāng)WMN信道分配完成后,無(wú)線鏈路之間的干擾也相應(yīng)確定,因此,我們使用(e)表示所有和鏈路e存在干擾的鏈路集合,其中,(e)包含鏈路e本身,那么鏈路e的干擾權(quán)重為I妒(e).定義5節(jié)點(diǎn)/3,的信道c干擾度c.當(dāng)為節(jié)點(diǎn)分配了信道c后,節(jié)點(diǎn)"的信道c干擾度也相應(yīng)確定,即cr,;maxI磊()(e:."I,其中,.:表示以節(jié)點(diǎn)"為端點(diǎn)的鏈路,也就是說(shuō)cr.為所有e:鏈路中干擾權(quán)重的最大值;當(dāng)e:

10、.表示以節(jié)點(diǎn)/Z或?yàn)槎它c(diǎn)鏈路時(shí),那么cru.表示節(jié)點(diǎn)或的信道c干擾度.2WMN線性規(guī)劃描述在wMN中,信道分配后的網(wǎng)絡(luò)干擾權(quán)重越小,那么WMN和公式描述.變量(u)表示網(wǎng)絡(luò)節(jié)點(diǎn)u的網(wǎng)卡數(shù),其中,u;變量c表示信道變量,C表示當(dāng)前WIIN可用的信道數(shù),其中,Cc;對(duì)于節(jié)點(diǎn)"和信道C,我們定義了二元變量:,其中,:0,11,當(dāng):為1時(shí),那么表示節(jié)點(diǎn)"分配了信道C,否那么,表示沒有分配信道c;對(duì)于每條鏈路e和信道c,我們使用二元變量Y,其中,0,1,eE,當(dāng)Y:為1時(shí),那么表示鏈路e分配了信道c,否那么,表示沒有分配信道c;對(duì)于網(wǎng)絡(luò)中的兩條鏈路e和e:,其中,Ve.,e:E,定義

11、一個(gè)變量z,0,1,當(dāng)z,為1時(shí),那么表示路e.和e分配了信道c,否那么,表示沒有分配信道c.min(1)其中,:IIW(e)cE最小.:(u),式(1)使當(dāng)前WMN總的干擾權(quán)重(2)式(2)表示節(jié)點(diǎn)u使用的信道數(shù)必須不大于該節(jié)點(diǎn)可用的網(wǎng)卡數(shù).y:1(3)cEC式(3)表示任意一條鏈路e上最多只能分配一個(gè)信道.:+:;e="H,V",V,Ve6(4)其中,e="一,V,V,VeG,式(4)表示一條鏈路分配信道c的必要條件是鏈路的兩個(gè)端節(jié)點(diǎn)同時(shí)分配了信道c.J(e)n;VeGA(5)1其中,=寺mI,(e)l,力是每條鏈路e在信道分配的干擾權(quán)重閾值,式(5)使WMN

12、信道分配完成后,網(wǎng)絡(luò)G上的每條邏輯鏈路e的干擾權(quán)重不超過(guò)設(shè)置的閾值n,從而使上每條鏈路上的網(wǎng)絡(luò)帶寬容量趨于均衡分布.3無(wú)線信道分配算法對(duì)于WMN的信道分配問題,目前常用的研究方法是通過(guò)路由計(jì)算,預(yù)測(cè)通過(guò)WMN上每條鏈路的流量,然后基于流量分布進(jìn)行信道分配,并通過(guò)路由計(jì)算與信道分配的迭代算法,最終使信道分配后的鏈路帶寬接近鏈路的流量需求,從而鏈路的干擾權(quán)重J,由于本文基于WMN各節(jié)點(diǎn)間業(yè)務(wù)流量均衡分布,那么意味著通過(guò)各鏈路的流量需求根本均等.因此,在進(jìn)行信道分配時(shí),我們通過(guò)設(shè)置干擾閾值n,使每條鏈路的干擾不大于.r2,同時(shí)使網(wǎng)絡(luò)總的干擾權(quán)重最小,即保證每條鏈路上分配的帶寬盡可能相等,也使網(wǎng)絡(luò)總的

13、帶寬容量最大.算法輸入:WMN的物理拓?fù)銰(V,E);每個(gè)節(jié)點(diǎn)u可用的網(wǎng)卡數(shù)Jj(")和信道數(shù)C(").算法輸出:每個(gè)節(jié)點(diǎn)的信道分配狀態(tài).步驟1在G(V,E)上計(jì)算每條鏈路e的干擾權(quán)重,(e)l,并利用公式=對(duì)G(,E)中所有的鏈路e按叩值降序排列,并依次進(jìn)行信道分配.步驟2鏈路e,按照以下步驟進(jìn)行信道分配.1)如果K(i)和節(jié)點(diǎn)K(j),且C(i)nc(j),那么為鏈路e分配信道c,其中,ccIc=C(i)nc(j).如果網(wǎng)絡(luò)的干擾權(quán)重一不大于且le.,(c)不大于,那么為鏈路e分配信道c,同時(shí)使=,否那么取消鏈路e的信道分配;2)如果K(i),且C(i)nc(j),但是

14、K(j)=,那么在節(jié)點(diǎn)已經(jīng)分配的信道中選擇一個(gè)c最小的擾權(quán)重不大于且,(c)不大于n,那么為鏈路e分配信道c,同時(shí)使=,否那么取消鏈路e的信道分配;3)如果K(i),且K(j),但是C(i)nc(j):,那么在已分配的信道中選擇一個(gè).,最小的信道c重不大于且.(c)不大于,那么為鏈路e分配信道c,同時(shí)使=,否那么取消鏈路e的信道分配;4)如果K(j),且C(i)rlc(j),但是K(i):,那么在節(jié)點(diǎn)i已經(jīng)分配的信道中選擇一個(gè)cr,最小干擾權(quán)重不大于且(c)不大于力,那么為鏈路e分配信道c,同時(shí)使=一,否那么取消鏈路e的信道分配.步驟3按照步驟2進(jìn)行信道分配時(shí),每次都進(jìn)行了干了使信道分配后建立

15、的網(wǎng)絡(luò)拓?fù)銰(,EA)是連通的,那么需要依次為孤立節(jié)點(diǎn)所有的鄰接鏈路,按照步驟2(無(wú)干擾權(quán)重約束的條件下)依次進(jìn)行信道"預(yù)分配",然后在其中選擇干擾權(quán)重最小的鄰接鏈路e分配信道,同時(shí)更新網(wǎng)絡(luò)干擾權(quán)重一.第7期彭利民等:多信道無(wú)線Mesh網(wǎng)絡(luò)信道分配算法l85l步驟4如果對(duì)于WMN所有的鏈路按照上述步驟進(jìn)行信道分配后,WMN節(jié)點(diǎn)還有可用的網(wǎng)卡,那么為這些節(jié)點(diǎn)的鄰接鏈路e按照步驟2依次進(jìn)行信道分配.步驟5返回WMN節(jié)點(diǎn)的信道分配.MinCI算法主要根據(jù)WMN上鏈路流量分布的特點(diǎn),通過(guò)設(shè)置鏈路干擾閾值n,使WMN鏈路上的干擾盡可能均勻分布,因而使信道分配后的鏈路帶寬也盡可能相等.

16、另外,在進(jìn)行信道分配時(shí),MinCI算法通過(guò)使用目標(biāo)函數(shù)值對(duì)每次信道分配進(jìn)行評(píng)價(jià),使每次信道分配后的網(wǎng)絡(luò)干擾權(quán)重盡可能道分配后,由于GA(V,EA)中可能出現(xiàn)孤立節(jié)點(diǎn),因此MinCI算法對(duì)于擾約束進(jìn)行松弛,使用步驟3進(jìn)行信道分配,從而保證了G(V,EA)的連通性.4仿真實(shí)驗(yàn)與分析采用NS2網(wǎng)絡(luò)仿真工具建立類似文獻(xiàn)6的仿真場(chǎng)景,相應(yīng)的干擾距離分別設(shè)為250Ill和550in,在1000×1000m的場(chǎng)景中隨機(jī)生成10組包含30個(gè)和50個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu),每個(gè)節(jié)點(diǎn)均配置3個(gè)NIC,采用IEEE802.11a標(biāo)準(zhǔn),無(wú)線鏈路的傳輸速率設(shè)為54Mbps.為了有效地實(shí)施多跳路由,采用網(wǎng)絡(luò)協(xié)議,利用R

17、TS/CTS機(jī)制將數(shù)據(jù)分組發(fā)送到相鄰節(jié)點(diǎn),實(shí)驗(yàn)采用連續(xù)比特速率(CBR)的流量模式,每個(gè)數(shù)據(jù)包的大小為1024字節(jié),在每組網(wǎng)絡(luò)結(jié)構(gòu)下,各業(yè)務(wù)連接請(qǐng)求均勻地分布在各節(jié)點(diǎn)對(duì)之間.為了比擬本文提出的MinCI算法網(wǎng)絡(luò)性能,結(jié)合最小跳步數(shù)路由算法,對(duì)MinCI和文獻(xiàn)6中CLICA算法進(jìn)行實(shí)驗(yàn).為了比擬兩個(gè)算法在不同網(wǎng)絡(luò)狀態(tài)下的網(wǎng)絡(luò)吞吐量,實(shí)驗(yàn)分別在3至l2個(gè)信道狀態(tài)下,對(duì)兩種節(jié)點(diǎn)分布模式進(jìn)行模擬比較,實(shí)驗(yàn)結(jié)果如圖1,2所示.u1肘信遭數(shù)圖1網(wǎng)絡(luò)吞吐量與信道數(shù)(30個(gè)節(jié)點(diǎn))如圖1,2所示,隨著WMN中可用信道數(shù)增多,MinCI算法和CLICA算法的網(wǎng)絡(luò)吞吐量都增大,說(shuō)明WMN中節(jié)點(diǎn)可用的信道數(shù)越多,WM

18、N中無(wú)線鏈路之間的干擾越小,從而網(wǎng)絡(luò)吞吐量也越大.另外,從如圖1,2也可以看出,隨著節(jié)點(diǎn)個(gè)數(shù)增多,MinCI算法和CLICA算法都呈現(xiàn)網(wǎng)絡(luò)吞吐量下降的問題,主要原因是在節(jié)點(diǎn)增多時(shí),WMN中鏈路之間的干擾加務(wù)連接請(qǐng)求均勻分布在各節(jié)點(diǎn)之間,各鏈路上的流量需求趨于均勻分布,符合MinCI算法分配的鏈路帶寬特點(diǎn),然而,CLICA算法在進(jìn)行信道分配時(shí),沒有考慮網(wǎng)絡(luò)流量的分布特點(diǎn),使得WMN中的某些鏈路帶寬受限,業(yè)務(wù)請(qǐng)求的平均跳步數(shù)增大,鏈路之間干擾增多,因而MinCI算法的網(wǎng)絡(luò)吞吐量比CLICA算法明顯增大.可用信道數(shù)圖2網(wǎng)絡(luò)吞吐量與信道數(shù)(50個(gè)節(jié)點(diǎn))5結(jié)語(yǔ)本文在協(xié)議層干擾模型的根底上,通過(guò)對(duì)鏈路的干擾進(jìn)行定量分析,應(yīng)用線性規(guī)劃的公式對(duì)信道分配進(jìn)行描述,使信道分配能適應(yīng)WMN的流量分布特點(diǎn),減少WMN的干擾權(quán)重.仿真結(jié)果說(shuō)明,MinCI較CLICA算法能顯著提高網(wǎng)絡(luò)性能.由于WMN無(wú)中心控制節(jié)點(diǎn),當(dāng)網(wǎng)絡(luò)規(guī)模變大時(shí),集中式的信道分配算法不再適應(yīng),同時(shí),無(wú)線網(wǎng)絡(luò)有別于有線網(wǎng)絡(luò),WMN各層協(xié)議之間相互依賴,因此,下一步的工作是根據(jù)WMN的特點(diǎn),對(duì)WMN的分布式算法與跨層優(yōu)化問題進(jìn)行研究.參考文獻(xiàn):(1】楊盤隆,陳貴海.無(wú)線網(wǎng)狀網(wǎng)容量分析與優(yōu)化理論研究J】.軟件,2021,19(3):687701.meshnetworks:A