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

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

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

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

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

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

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

0　引言

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

文獻(xiàn)[1-3]通過解決節(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]以減小干擾來最大化網(wǎng)絡(luò)吞吐量為目標(biāo)，通過建立網(wǎng)絡(luò)沖突圖，采用啟發(fā)計(jì)算法尋找低干擾的信道分配。文獻(xiàn)[7，8]采用粒子群智能優(yōu)化算法來解決信道分配問題，以全局分配的方式來達(dá)到網(wǎng)絡(luò)整體干擾的最小化，但是這種方法沒有考慮流量樣式對(duì)信道分配的影響。文獻(xiàn)[9]提出了基于流量感知的信道分配方法，將流量感知因素加入到信道分配的設(shè)計(jì)中，但是這種信道分配方法依賴于路由協(xié)議的聯(lián)合設(shè)計(jì)。本文從鏈路負(fù)載估計(jì)和信道分配兩階段介紹信道分配策略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é)點(diǎn)匯聚、網(wǎng)絡(luò)流量分布不均勻的特點(diǎn)；同時(shí)，在局部節(jié)點(diǎn)越密集處節(jié)點(diǎn)流量負(fù)載越重。

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

1.1信道分配模型

將無線 Mesh無線網(wǎng)絡(luò)拓?fù)浔硎緸橐粋€(gè)無向圖G= {V，E}，其中V為無線Mesh網(wǎng)絡(luò)的節(jié)點(diǎn)集合。整個(gè)無線Mesh網(wǎng)絡(luò)可用正交信道表示為 CK={1，2，3，…K}，將所有正交信道分別標(biāo)號(hào)為：1，2，3，…K。對(duì)于每個(gè)無線Mesh網(wǎng)絡(luò)節(jié)點(diǎn) u∈V，節(jié)點(diǎn) u的無線射頻接口數(shù)用 R(u)表示，C(u)表示節(jié)點(diǎn)使用的正交信道集。

E表示該無線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è)無線Mesh網(wǎng)絡(luò)節(jié)點(diǎn)，一個(gè)無線射頻接口在某一時(shí)刻最多只能分配一個(gè)信道。同時(shí)，為了保證每個(gè)射頻接口的有效利用，節(jié)點(diǎn)接口數(shù)不能超過可用的正交信道數(shù)。所以有如下關(guān)系：

對(duì)于多射頻多信道無線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}表示無線 Mesh網(wǎng)絡(luò)中所有鏈路的有效情況。

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

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

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

式中，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ì)算

在無線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）的方式來表征節(jié)點(diǎn)的密集程度。在得到節(jié)點(diǎn)的優(yōu)先級(jí)PL和鄰居數(shù)NB之后，通過計(jì)算得到每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)負(fù)載權(quán)重。

首先使用 Dijkstra算法來計(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，以此來表示周圍節(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所示。

圖2　8個(gè)節(jié)點(diǎn)無線Mesh拓?fù)涫疽鈭D

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

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

，然后將鏈路負(fù)載權(quán)重從大到小排序，從鏈路負(fù)載權(quán)重最大的鏈路開始，按順序?yàn)槊織l鏈路分配信道。

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

2　仿真實(shí)驗(yàn)與分析

2.1仿真場(chǎng)景說明

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

仿真中每個(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ǎng)卡，無線鏈路的傳輸速率為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í)間。

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

(2)平均端到端延時(shí)：

其中 Nrp為成功傳輸?shù)陌臄?shù)量，Tdi表示數(shù)據(jù)包到達(dá)目的點(diǎn)的時(shí)間，表示數(shù)據(jù)包發(fā)送的時(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í)延的變化情況。

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

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

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

3　結(jié)論

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

[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].計(jì)算機(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

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

2015-12-04)

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

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

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

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