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.1 信道分配模型

    將無線Mesh無線網(wǎng)絡(luò)拓?fù)浔硎緸橐粋€(gè)無向圖G={V,，E},，其中V為無線Mesh網(wǎng)絡(luò)的節(jié)點(diǎn)集合。整個(gè)無線Mesh網(wǎng)絡(luò)可用正交信道表示為C_K={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,，存在e_uv∈E，表示節(jié)點(diǎn)u和節(jié)點(diǎn)v在彼此的傳輸范圍內(nèi),，可在相同信道上通信,，節(jié)點(diǎn)u和節(jié)點(diǎn)v存在一條通信鏈路e_uv。節(jié)點(diǎn)u的鄰居表示為NB_u={i|i∈V,，e_ui∈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ò),，鏈路e_uv通信的條件如式(2)、式(3)所示：

    式(2)中,，x_uv表示鏈路e_uv上所分配的信道標(biāo)號(hào),。當(dāng)e_uv∈E，并且分配信道k給鏈路e_uv,，k∈C_K時(shí),，x_uv=k；否則,，x_uv=0,。

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

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

式中,，PL_CID表示鏈路帶上負(fù)載權(quán)重后網(wǎng)絡(luò)的整體干擾權(quán)重，即每兩條相互干擾的鏈路的鏈路負(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í)PL_i，其中i為節(jié)點(diǎn)標(biāo)號(hào),；同時(shí)計(jì)算每一個(gè)節(jié)點(diǎn)周圍的一跳鄰居節(jié)點(diǎn)數(shù)目NB_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 仿真場景說明

    本節(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ò)吞吐量：

其中 L_pkt為每個(gè)數(shù)據(jù)包的長度,，N_rp為成功傳輸?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線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í),。

參考文獻(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] 彭利民，劉浩.多信道無線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.