基于鏈路負載分級的無線Mesh網(wǎng)信道分配算法*

張　頡，柴繼文，孫冠杰，林水生，余飛龍

（1.國網(wǎng)四川省電力公司電力科學研究院，四川 成都 610072；2.電子科技大學 通信與信息工程學院，四川 成都 611731）

基于鏈路負載分級的無線Mesh網(wǎng)信道分配算法*

張頡1，柴繼文1，孫冠杰2，林水生2，余飛龍2

（1.國網(wǎng)四川省電力公司電力科學研究院，四川 成都 610072；2.電子科技大學 通信與信息工程學院，四川 成都 611731）

由于無線Mesh網(wǎng)絡(luò)信道分配算法的性能增益與網(wǎng)絡(luò)的流量負載特點密切相關(guān)，在對多射頻多信道無線Mesh網(wǎng)絡(luò)的流量特點進行分析的基礎(chǔ)上，提出一種靜態(tài)信道分配的啟發(fā)式算法LPFCA。該算法根據(jù)無線鏈路在網(wǎng)絡(luò)拓撲中的位置信息來估計無線鏈路的預(yù)期負載情況，并對網(wǎng)絡(luò)中無線鏈路的預(yù)期負載進行量化分級，利用整數(shù)線性規(guī)劃方法對信道分配進行描述并應(yīng)用目標函數(shù)對信道分配進行優(yōu)化，使網(wǎng)絡(luò)總的干擾權(quán)重最小化。仿真結(jié)果表明，相比于現(xiàn)有的算法，該算法在吞吐量上平均提升了 18.9%。

信道分配；啟發(fā)式算法；鏈路負載；線性規(guī)劃；無線 Mesh網(wǎng)絡(luò)

0　引言

信道分配是多射頻多信道無線Mesh網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，優(yōu)秀的信道分配方案能夠增大網(wǎng)絡(luò)吞吐量，提升網(wǎng)絡(luò)性能。

文獻[1-3]通過解決節(jié)點、接口與信道之間的協(xié)調(diào)關(guān)系避免了波紋效應(yīng)，實現(xiàn)負載平衡，但是該方法對網(wǎng)絡(luò)的拓撲有約束，影響路由的靈活性。文獻[4]采用模擬退火算法緩解接口約束對信道分配性能的影響，提升了節(jié)點接口受約束條件下的信道分配的性能。文獻[5，6]以減小干擾來最大化網(wǎng)絡(luò)吞吐量為目標，通過建立網(wǎng)絡(luò)沖突圖，采用啟發(fā)計算法尋找低干擾的信道分配。文獻[7，8]采用粒子群智能優(yōu)化算法來解決信道分配問題，以全局分配的方式來達到網(wǎng)絡(luò)整體干擾的最小化，但是這種方法沒有考慮流量樣式對信道分配的影響。文獻[9]提出了基于流量感知的信道分配方法，將流量感知因素加入到信道分配的設(shè)計中，但是這種信道分配方法依賴于路由協(xié)議的聯(lián)合設(shè)計。本文從鏈路負載估計和信道分配兩階段介紹信道分配策略LDFCA(Link Priority Fixed Channel Assignment)算法。

1　算法描述

無線Mesh骨干網(wǎng)作為接入網(wǎng)絡(luò)，其網(wǎng)絡(luò)架構(gòu)圖如圖1所示，所有無線 Mesh路由器位置固定，為 Mesh客戶端作回傳接入。無線Mesh骨干網(wǎng)具有網(wǎng)絡(luò)流量向網(wǎng)關(guān)節(jié)點匯聚、網(wǎng)絡(luò)流量分布不均勻的特點；同時，在局部節(jié)點越密集處節(jié)點流量負載越重。

圖1　無線Mesh骨干網(wǎng)架構(gòu)示意圖

1.1信道分配模型

將無線 Mesh無線網(wǎng)絡(luò)拓撲表示為一個無向圖G= {V，E}，其中V為無線Mesh網(wǎng)絡(luò)的節(jié)點集合。整個無線Mesh網(wǎng)絡(luò)可用正交信道表示為 CK={1，2，3，…K}，將所有正交信道分別標號為：1，2，3，…K。對于每個無線Mesh網(wǎng)絡(luò)節(jié)點 u∈V，節(jié)點 u的無線射頻接口數(shù)用 R(u)表示，C(u)表示節(jié)點使用的正交信道集。

E表示該無線Mesh網(wǎng)絡(luò)的鏈路集合，對于u，v∈V，存在euv∈E，表示節(jié)點u和節(jié)點v在彼此的傳輸范圍內(nèi)，可在相同信道上通信，節(jié)點u和節(jié)點v存在一條通信鏈路euv。節(jié)點u的鄰居表示為NBu={i|i∈V，?eui∈E}。

對于每個無線Mesh網(wǎng)絡(luò)節(jié)點，一個無線射頻接口在某一時刻最多只能分配一個信道。同時，為了保證每個射頻接口的有效利用，節(jié)點接口數(shù)不能超過可用的正交信道數(shù)。所以有如下關(guān)系：

對于多射頻多信道無線Mesh網(wǎng)絡(luò)，鏈路euv通信的條件如式(2)、式(3)所示：

式(2)中，xuv表示鏈路 euv上所分配的信道標號。當 euv∈E，并且分配信道 k給鏈路 euv，k∈CK時，xuv=k；否則，xuv=0。

式(3)中，當鏈路 euv被分配了某個信道，表示鏈路 euv有效，得到 fuv=1；否則，鏈路 euv未分配信道或者節(jié)點 u和節(jié)點v間不存在鏈路，得到fuv=0。設(shè) F={fuv|u，v∈V且xuv∈X}表示無線 Mesh網(wǎng)絡(luò)中所有鏈路的有效情況。

采用協(xié)議干擾模型，計算G={V，E}的干擾矩陣 GC，對于?gcij∈GC，有：

對于多射頻多信道無線 Mesh網(wǎng)絡(luò)，由式(4)得到的干擾矩陣GC只是一個潛在干擾矩陣，只有當互為潛在干擾鏈路的兩條鏈路工作在相同信道上時才能真正成為網(wǎng)絡(luò)中的有效干擾。所以根據(jù)式(2)、(3)和(4)可得I(eijeuv)來表示兩條鏈路間存在有效干擾。

式(5)表示當且僅當兩條鏈路互為潛在干擾對象，且都分配了相同信道，鏈路 eij和鏈路 euv間存在干擾。

式中，PL_CID表示鏈路帶上負載權(quán)重后網(wǎng)絡(luò)的整體干擾權(quán)重，即每兩條相互干擾的鏈路的鏈路負載權(quán)重之和。

綜上，信道分配模型即使PL_CID的值最小。

1.2節(jié)點優(yōu)先級的劃分及節(jié)點負載權(quán)重的計算

在無線Mesh骨干網(wǎng)絡(luò)中，越靠近網(wǎng)關(guān)節(jié)點的鏈路預(yù)期流量越大，對帶寬的需求也越大，而鏈路的帶寬取決于鏈路周圍的干擾大小，靠近網(wǎng)關(guān)節(jié)點的鏈路應(yīng)分配干擾較小的信道以獲得較大的帶寬。本文根據(jù)節(jié)點距離網(wǎng)關(guān)節(jié)點的遠近程度，采用分配節(jié)點優(yōu)先級PL(Priority Level)的策略，使靠近網(wǎng)關(guān)節(jié)點的節(jié)點分配較高的優(yōu)先級。

同時，網(wǎng)絡(luò)局部節(jié)點越密集處，節(jié)點預(yù)期承受的流量也越大，節(jié)點周圍鏈路干擾越大，優(yōu)先考慮給節(jié)點密集處的鏈路分配干擾較小的信道，平衡整個網(wǎng)絡(luò)的干擾。在這里考慮節(jié)點的密集程度對信道分配的影響，采用為每一個節(jié)點計算它的鄰居數(shù) NB（Neighbor）的方式來表征節(jié)點的密集程度。在得到節(jié)點的優(yōu)先級PL和鄰居數(shù)NB之后，通過計算得到每個節(jié)點的節(jié)點負載權(quán)重。

首先使用 Dijkstra算法來計算每一個節(jié)點到網(wǎng)關(guān)節(jié)點的最小跳數(shù)并以此為每一個節(jié)點分級，網(wǎng)關(guān)節(jié)點的級數(shù)最高為1級，依次往下分，直至網(wǎng)絡(luò)中所有的節(jié)點都分配一個等級 PLi，其中 i為節(jié)點標號；同時計算每一個節(jié)點周圍的一跳鄰居節(jié)點數(shù)目NBi，以此來表示周圍節(jié)點的密集程度。然后定義每一個節(jié)點的節(jié)點負載權(quán)重為。

以圖2為例，以節(jié)點3為網(wǎng)關(guān)節(jié)點，計算每個節(jié)點的優(yōu)先級、鄰居數(shù)以及節(jié)點負載權(quán)重，如表1所示。

圖2　8個節(jié)點無線Mesh拓撲示意圖

表1　各節(jié)點優(yōu)先級、鄰居數(shù)及節(jié)點負載權(quán)重

1.3算法實現(xiàn)流程

，然后將鏈路負載權(quán)重從大到小排序，從鏈路負載權(quán)重最大的鏈路開始，按順序為每條鏈路分配信道。

在為每一條鏈路分配信道時，需要計算該鏈路在每一個可用信道上的干擾權(quán)重值，以選取干擾最小的信道分配給當前鏈路。鏈路在信道c上的干擾權(quán)重值為該鏈路干擾范圍內(nèi)所有使用信道c的鏈路負載權(quán)重之和。

2　仿真實驗與分析

2.1仿真場景說明

本節(jié)在NS3仿真平臺上仿真驗證 LPFCA算法與文獻[8]中算法的性能，仿真結(jié)果主要通過網(wǎng)絡(luò)吞吐量和平均端到端延時兩個指標來衡量。

仿真中每個節(jié)點的傳輸距離和干擾距離分別設(shè)置為250 m和550 m，在 1 200 m×1 200 m的區(qū)域內(nèi)隨機生成包含32個節(jié)點的網(wǎng)絡(luò)拓撲，每個節(jié)點均配置2個無線網(wǎng)卡，無線鏈路的傳輸速率為54 Mb/s。路由協(xié)議采用802.11s標準中的HWMP，傳輸業(yè)務(wù)類型為UDP的CBR流，數(shù)據(jù)流的源節(jié)點隨機選取，目的節(jié)點為網(wǎng)關(guān)節(jié)點，開啟RTS/CTS機制，每個數(shù)據(jù)包大小為 1 024 B，仿真時間為100 s。

2.2仿真結(jié)果分析

仿真的性能指標計算如下：

(1)網(wǎng)絡(luò)吞吐量：

其中 Lpkt為每個數(shù)據(jù)包的長度，Nrp為成功傳輸?shù)陌臄?shù)量，T為仿真時間。

當林藍說沒搶到做活動的菜籽油或者某培訓機構(gòu)99元試聽4節(jié)的樂高課，他不再高高在上地發(fā)個紅包，而是報以寬容的微笑，說：“哇，真遺憾！”

(2)平均端到端延時：

其中 Nrp為成功傳輸?shù)陌臄?shù)量，Tdi表示數(shù)據(jù)包到達目的點的時間，表示數(shù)據(jù)包發(fā)送的時間。

本小節(jié)首先仿真LPFCA和文獻[8]中的算法在不同可用信道數(shù)下的吞吐量對比。然后分別選取3種不同可用信道數(shù)，仿真隨著數(shù)據(jù)流數(shù)目的增加兩種算法的性能。

2.2.1不同信道數(shù)下的吞吐量對比

圖3中的 Channel-Number表示可用信道數(shù)目，Throughput表示網(wǎng)絡(luò)吞吐量，以kb/s為單位。圖3表示了LPFCA和文獻[8]中的算法在不同可用信道數(shù)下的網(wǎng)絡(luò)吞吐量對比。LPFCA相對于文獻[8]在吞吐量上平均提升了18.9%。

2.2.2不同數(shù)據(jù)流下的性能仿真

圖4中仿真了在不同數(shù)據(jù)流數(shù)量下吞吐量和時延的變化情況。

圖3　不同可用信道數(shù)下的吞吐量對比

圖4　兩種不同信道數(shù)目下隨著數(shù)據(jù)流變化的性能對比

總體而言，LPFCA算法在吞吐量和延時上都體現(xiàn)出較優(yōu)的性能，這是因為無線Mesh網(wǎng)絡(luò)中流量分布不均勻，各鏈路上承載的流量負載也不同，而 LPFCA以無線鏈路的位置信息來預(yù)估無線鏈路的預(yù)期負載的方式結(jié)合了無線Mesh網(wǎng)絡(luò)的流量特點，使得預(yù)期負載越大的鏈路能夠分配干擾越小的信道以獲取更高的帶寬來滿足流量負載需求，因而能夠體現(xiàn)出更好的性能。

3　結(jié)論

本文首先建立信道分配模型，用線性規(guī)劃方式描述信道分配的目標函數(shù)和約束條件；然后根據(jù)鏈路的位置信息和網(wǎng)絡(luò)的流量特點來估計鏈路的預(yù)期負載情況，同時為每一條鏈路計算一個鏈路負載權(quán)重；最后以每條鏈路的負載權(quán)重為基礎(chǔ)，以啟發(fā)式算法的形式為其分配信道。與文獻[8]中的算法相比，LPFCA更符合無線Mesh網(wǎng)絡(luò)的流量特點，更能滿足其流量負載需求。通過仿真結(jié)果證明，該算法能夠有效地提升無線Mesh網(wǎng)絡(luò)的吞吐量，減小延時。

[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]彭利民，劉浩.多信道無線Mesh網(wǎng)絡(luò)信道分配算法[J].計算機應(yīng)用，2009，29(7)：1849-1851.

[7]張旭，殷昌盛，熊輝，等.無線 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.

A link load classification-based channel assignment algorithm for wireless Mesh networks

Zhang Jie1，Chai Jiwen1，Sun Guanjie2，Lin Shuisheng2，Yu Feilong2
(1.State Grid Sichuan Electronic Power Research Institute，Chengdu 610072，China；2.School of Communication and Information Engineering，University of Electronic Science and Technology of China，Chengdu 611731，China)

Considering the performance gain of channel assignment algorithm for wireless Mesh networks is closely related to the network traffic load characteristic，through analyzing the traffic load model in multi-radio multi-channel wireless Mesh networks,this paper proposed a static channel assignment heuristic algorithm called LPFCA.The proposed algorithm estimated the expected traffic load of wireless links by its location in the network,quantified the expected load of wireless link and divided all links into different levels.After that the channel assignment was formulated as integer linear programming and the overall network interference weight is minimized by using objective function for optimizing channel assignment.Simulation results show that LPFCA can averagely increase 18.9%throughput compared with the existing algorithm.

channel assignment；heuristic algorithm；link traffic load；linear programming；wireless Mesh networks

TP393

A

10.16157/j.issn.0258-7998.2016.05.023

國網(wǎng)四川省電力公司科技項目(52199715000H)

2015-12-04)

張頡(1982-)，男，博士，主要研究方向：電力通信。

柴繼文(1963-)，男，碩士，主要研究方向：電力通信與信息安全。

孫冠杰(1991-)，男，碩士研究生，主要研究方向：無線Mesh網(wǎng)絡(luò)。

中文引用格式：張頡，柴繼文，孫冠杰，等.基于鏈路負載分級的無線 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.