文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2016.05.023
中文引用格式： 張頡，柴繼文，孫冠杰，等. 基于鏈路負(fù)載分級(jí)的無(wú)線Mesh網(wǎng)信道分配算法[J].電子技術(shù)應(yīng)用，2016，42(5)：82-84，89.
英文引用格式： Zhang Jie，Chai Jiwen，Sun Guanjie，et al. A link load classification-based channel assignment algorithm for wireless Mesh networks[J].Application of Electronic Technique，2016，42(5)：82-84，89.
0 引言
信道分配是多射頻多信道無(wú)線Mesh網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，優(yōu)秀的信道分配方案能夠增大網(wǎng)絡(luò)吞吐量，提升網(wǎng)絡(luò)性能。
文獻(xiàn)[1-3]通過(guò)解決節(jié)點(diǎn)、接口與信道之間的協(xié)調(diào)關(guān)系避免了波紋效應(yīng)，實(shí)現(xiàn)負(fù)載平衡，但是該方法對(duì)網(wǎng)絡(luò)的拓?fù)溆屑s束，影響路由的靈活性。文獻(xiàn)[4]采用模擬退火算法緩解接口約束對(duì)信道分配性能的影響，提升了節(jié)點(diǎn)接口受約束條件下的信道分配的性能。文獻(xiàn)[5，6]以減小干擾來(lái)最大化網(wǎng)絡(luò)吞吐量為目標(biāo)，通過(guò)建立網(wǎng)絡(luò)沖突圖，采用啟發(fā)計(jì)算法尋找低干擾的信道分配。文獻(xiàn)[7，8]采用粒子群智能優(yōu)化算法來(lái)解決信道分配問(wèn)題，以全局分配的方式來(lái)達(dá)到網(wǎng)絡(luò)整體干擾的最小化，但是這種方法沒(méi)有考慮流量樣式對(duì)信道分配的影響。文獻(xiàn)[9]提出了基于流量感知的信道分配方法，將流量感知因素加入到信道分配的設(shè)計(jì)中，但是這種信道分配方法依賴于路由協(xié)議的聯(lián)合設(shè)計(jì)。本文從鏈路負(fù)載估計(jì)和信道分配兩階段介紹信道分配策略LDFCA(Link Priority Fixed Channel Assignment)算法。
1 算法描述
無(wú)線Mesh骨干網(wǎng)作為接入網(wǎng)絡(luò)，其網(wǎng)絡(luò)架構(gòu)圖如圖1所示，所有無(wú)線Mesh路由器位置固定，為Mesh客戶端作回傳接入。無(wú)線Mesh骨干網(wǎng)具有網(wǎng)絡(luò)流量向網(wǎng)關(guān)節(jié)點(diǎn)匯聚、網(wǎng)絡(luò)流量分布不均勻的特點(diǎn)；同時(shí)，在局部節(jié)點(diǎn)越密集處節(jié)點(diǎn)流量負(fù)載越重。
1.1 信道分配模型
將無(wú)線Mesh無(wú)線網(wǎng)絡(luò)拓?fù)浔硎緸橐粋€(gè)無(wú)向圖G={V，E}，其中V為無(wú)線Mesh網(wǎng)絡(luò)的節(jié)點(diǎn)集合。整個(gè)無(wú)線Mesh網(wǎng)絡(luò)可用正交信道表示為CK={1，2，3，…K}，將所有正交信道分別標(biāo)號(hào)為：1，2，3，…K。對(duì)于每個(gè)無(wú)線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)u∈V，節(jié)點(diǎn)u的無(wú)線射頻接口數(shù)用R(u)表示，C(u)表示節(jié)點(diǎn)使用的正交信道集。
E表示該無(wú)線Mesh網(wǎng)絡(luò)的鏈路集合，對(duì)于u，v∈V，存在euv∈E，表示節(jié)點(diǎn)u和節(jié)點(diǎn)v在彼此的傳輸范圍內(nèi)，可在相同信道上通信，節(jié)點(diǎn)u和節(jié)點(diǎn)v存在一條通信鏈路euv。節(jié)點(diǎn)u的鄰居表示為NBu={i|i∈V，
eui∈E}。
對(duì)于每個(gè)無(wú)線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)，一個(gè)無(wú)線射頻接口在某一時(shí)刻最多只能分配一個(gè)信道。同時(shí)，為了保證每個(gè)射頻接口的有效利用，節(jié)點(diǎn)接口數(shù)不能超過(guò)可用的正交信道數(shù)。所以有如下關(guān)系：
對(duì)于多射頻多信道無(wú)線Mesh網(wǎng)絡(luò)，鏈路euv通信的條件如式(2)、式(3)所示：
式(2)中，xuv表示鏈路euv上所分配的信道標(biāo)號(hào)。當(dāng)euv∈E，并且分配信道k給鏈路euv，k∈CK時(shí)，xuv=k；否則，xuv=0。
式(3)中，當(dāng)鏈路euv被分配了某個(gè)信道，表示鏈路euv有效，得到fuv=1；否則，鏈路euv未分配信道或者節(jié)點(diǎn)u和節(jié)點(diǎn)v間不存在鏈路，得到fuv=0。設(shè)F={fuv|u，v∈V且xuv∈X}表示無(wú)線Mesh網(wǎng)絡(luò)中所有鏈路的有效情況。
對(duì)于多射頻多信道無(wú)線Mesh網(wǎng)絡(luò)，由式(4)得到的干擾矩陣GC只是一個(gè)潛在干擾矩陣，只有當(dāng)互為潛在干擾鏈路的兩條鏈路工作在相同信道上時(shí)才能真正成為網(wǎng)絡(luò)中的有效干擾。所以根據(jù)式(2)、(3)和(4)可得I(eij euv)來(lái)表示兩條鏈路間存在有效干擾。
式中，PL_CID表示鏈路帶上負(fù)載權(quán)重后網(wǎng)絡(luò)的整體干擾權(quán)重，即每?jī)蓷l相互干擾的鏈路的鏈路負(fù)載權(quán)重之和。
綜上，信道分配模型即使PL_CID的值最小。
1.2 節(jié)點(diǎn)優(yōu)先級(jí)的劃分及節(jié)點(diǎn)負(fù)載權(quán)重的計(jì)算
在無(wú)線Mesh骨干網(wǎng)絡(luò)中，越靠近網(wǎng)關(guān)節(jié)點(diǎn)的鏈路預(yù)期流量越大，對(duì)帶寬的需求也越大，而鏈路的帶寬取決于鏈路周圍的干擾大小，靠近網(wǎng)關(guān)節(jié)點(diǎn)的鏈路應(yīng)分配干擾較小的信道以獲得較大的帶寬。本文根據(jù)節(jié)點(diǎn)距離網(wǎng)關(guān)節(jié)點(diǎn)的遠(yuǎn)近程度，采用分配節(jié)點(diǎn)優(yōu)先級(jí)PL(Priority Level)的策略，使靠近網(wǎng)關(guān)節(jié)點(diǎn)的節(jié)點(diǎn)分配較高的優(yōu)先級(jí)。
同時(shí)，網(wǎng)絡(luò)局部節(jié)點(diǎn)越密集處，節(jié)點(diǎn)預(yù)期承受的流量也越大，節(jié)點(diǎn)周圍鏈路干擾越大，優(yōu)先考慮給節(jié)點(diǎn)密集處的鏈路分配干擾較小的信道，平衡整個(gè)網(wǎng)絡(luò)的干擾。在這里考慮節(jié)點(diǎn)的密集程度對(duì)信道分配的影響，采用為每一個(gè)節(jié)點(diǎn)計(jì)算它的鄰居數(shù)NB（Neighbor）的方式來(lái)表征節(jié)點(diǎn)的密集程度。在得到節(jié)點(diǎn)的優(yōu)先級(jí)PL和鄰居數(shù)NB之后，通過(guò)計(jì)算得到每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)負(fù)載權(quán)重。
首先使用Dijkstra算法來(lái)計(jì)算每一個(gè)節(jié)點(diǎn)到網(wǎng)關(guān)節(jié)點(diǎn)的最小跳數(shù)并以此為每一個(gè)節(jié)點(diǎn)分級(jí)，網(wǎng)關(guān)節(jié)點(diǎn)的級(jí)數(shù)最高為1級(jí)，依次往下分，直至網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都分配一個(gè)等級(jí)PLi，其中i為節(jié)點(diǎn)標(biāo)號(hào)；同時(shí)計(jì)算每一個(gè)節(jié)點(diǎn)周圍的一跳鄰居節(jié)點(diǎn)數(shù)目NBi，以此來(lái)表示周圍節(jié)點(diǎn)的密集程度。然后定義每一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)負(fù)載權(quán)重為
以圖2為例，以節(jié)點(diǎn)3為網(wǎng)關(guān)節(jié)點(diǎn)，計(jì)算每個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)、鄰居數(shù)以及節(jié)點(diǎn)負(fù)載權(quán)重，如表1所示。
1.3 算法實(shí)現(xiàn)流程
在為每一條鏈路分配信道時(shí)，需要計(jì)算該鏈路在每一個(gè)可用信道上的干擾權(quán)重值，以選取干擾最小的信道分配給當(dāng)前鏈路。鏈路在信道c上的干擾權(quán)重值為該鏈路干擾范圍內(nèi)所有使用信道c的鏈路負(fù)載權(quán)重之和。
2 仿真實(shí)驗(yàn)與分析
2.1 仿真場(chǎng)景說(shuō)明
本節(jié)在NS3仿真平臺(tái)上仿真驗(yàn)證LPFCA算法與文獻(xiàn)[8]中算法的性能，仿真結(jié)果主要通過(guò)網(wǎng)絡(luò)吞吐量和平均端到端延時(shí)兩個(gè)指標(biāo)來(lái)衡量。
仿真中每個(gè)節(jié)點(diǎn)的傳輸距離和干擾距離分別設(shè)置為250 m和550 m，在1 200 m×1 200 m的區(qū)域內(nèi)隨機(jī)生成包含32個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)洌總€(gè)節(jié)點(diǎn)均配置2個(gè)無(wú)線網(wǎng)卡，無(wú)線鏈路的傳輸速率為54 Mb/s。路由協(xié)議采用802.11s標(biāo)準(zhǔn)中的HWMP，傳輸業(yè)務(wù)類型為UDP的CBR流，數(shù)據(jù)流的源節(jié)點(diǎn)隨機(jī)選取，目的節(jié)點(diǎn)為網(wǎng)關(guān)節(jié)點(diǎn)，開啟RTS/CTS機(jī)制，每個(gè)數(shù)據(jù)包大小為1 024 B，仿真時(shí)間為100 s。
2.2 仿真結(jié)果分析
仿真的性能指標(biāo)計(jì)算如下：
(1)網(wǎng)絡(luò)吞吐量：
其中 Lpkt為每個(gè)數(shù)據(jù)包的長(zhǎng)度，Nrp為成功傳輸?shù)陌臄?shù)量，T為仿真時(shí)間。
(2)平均端到端延時(shí)：
本小節(jié)首先仿真LPFCA和文獻(xiàn)[8]中的算法在不同可用信道數(shù)下的吞吐量對(duì)比。然后分別選取3種不同可用信道數(shù)，仿真隨著數(shù)據(jù)流數(shù)目的增加兩種算法的性能。
2.2.1 不同信道數(shù)下的吞吐量對(duì)比
圖3中的Channel-Number表示可用信道數(shù)目，Throughput表示網(wǎng)絡(luò)吞吐量，以kb/s為單位。圖3表示了LPFCA和文獻(xiàn)[8]中的算法在不同可用信道數(shù)下的網(wǎng)絡(luò)吞吐量對(duì)比。LPFCA相對(duì)于文獻(xiàn)[8]在吞吐量上平均提升了18.9%。
2.2.2 不同數(shù)據(jù)流下的性能仿真
圖4中仿真了在不同數(shù)據(jù)流數(shù)量下吞吐量和時(shí)延的變化情況。
從圖4可以看出，在3個(gè)可用分配信道下，LPFCA吞吐量平均提升了22.6%，延時(shí)減小了16.7%；在6個(gè)可用分配信道下，LPFCA吞吐量平均提升了15.6%，延時(shí)減小了17.8%。
總體而言，LPFCA算法在吞吐量和延時(shí)上都體現(xiàn)出較優(yōu)的性能，這是因?yàn)闊o(wú)線Mesh網(wǎng)絡(luò)中流量分布不均勻，各鏈路上承載的流量負(fù)載也不同，而LPFCA以無(wú)線鏈路的位置信息來(lái)預(yù)估無(wú)線鏈路的預(yù)期負(fù)載的方式結(jié)合了無(wú)線Mesh網(wǎng)絡(luò)的流量特點(diǎn)，使得預(yù)期負(fù)載越大的鏈路能夠分配干擾越小的信道以獲取更高的帶寬來(lái)滿足流量負(fù)載需求，因而能夠體現(xiàn)出更好的性能。
3 結(jié)論
本文首先建立信道分配模型，用線性規(guī)劃方式描述信道分配的目標(biāo)函數(shù)和約束條件；然后根據(jù)鏈路的位置信息和網(wǎng)絡(luò)的流量特點(diǎn)來(lái)估計(jì)鏈路的預(yù)期負(fù)載情況，同時(shí)為每一條鏈路計(jì)算一個(gè)鏈路負(fù)載權(quán)重；最后以每條鏈路的負(fù)載權(quán)重為基礎(chǔ)，以啟發(fā)式算法的形式為其分配信道。與文獻(xiàn)[8]中的算法相比，LPFCA更符合無(wú)線Mesh網(wǎng)絡(luò)的流量特點(diǎn)，更能滿足其流量負(fù)載需求。通過(guò)仿真結(jié)果證明，該算法能夠有效地提升無(wú)線Mesh網(wǎng)絡(luò)的吞吐量，減小延時(shí)。
參考文獻(xiàn)
[1] RANIWALA A，CHIUEH T.Evaluation of a wireless enter-prise backbone network architecture[C].High Performance Interconnects，2004.Proceedings.12th Annual IEEE Symposium on.IEEE，2004：98-104.
[2] RANIWALA A，CHIUEH T.Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network[C].INFOCOM 2005.24th Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings IEEE.IEEE，2005，3：2223-2234.
[3] KVASANUR P，VAIDVA N F.Routing and interface assignment in multi-channel multi-interface wireless networks[C].Wireless Communications and Networking Conference，2005 IEEE. IEEE，2005，4：2051-2056.
[4] CHEN Y Y，CHEN C，JAN R H.Impact of interface constraint on channel assignment in wireless mesh networks[C].Wireless Communications and Networking Conference (WCNC)，2013 IEEE.IEEE，2013：1309-1314.
[5] MARINA M K，DAS S R，SBURAMANIAN A P.A topology control approach for utilizing multiple channels in multiradio wireless mesh networks[J].Computer networks，2010，54(2)：241-256.
[6] 彭利民，劉浩.多信道無(wú)線Mesh網(wǎng)絡(luò)信道分配算法[J].計(jì)算機(jī)應(yīng)用，2009，29(7)：1849-1851.
[7] 張旭，殷昌盛，熊輝，等.無(wú)線Mesh網(wǎng)絡(luò)中基于離散粒子群優(yōu)化的信道分配算法[J].現(xiàn)代電子技術(shù)，2013，8(36)：31-36.
[8] MOUNTASSIR T，NASSEREDDINE B，HAQIQ A，et al.An efficient optimization model for Fixed Channel Assignment in Wireless Mesh Networks[C].Next Generation Networks and Services(NGNS)，2012.IEEE，2012：177-180.
[9] AVALLONE S，STASI G，KASSLER A.A traffic-aware channel and rate reassignment algorithm for wireless mesh networks[J].IEEE Transactions on Moblie Computing，2013，12(7)：1335-1348.