0 引言

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

    文獻[1-3]通過解決節(jié)點、接口與信道之間的協(xié)調(diào)關(guān)系避免了波紋效應，實現(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.1 信道分配模型

    將無線Mesh無線網(wǎng)絡(luò)拓撲表示為一個無向圖G={V，E}，其中V為無線Mesh網(wǎng)絡(luò)的節(jié)點集合。整個無線Mesh網(wǎng)絡(luò)可用正交信道表示為C_K={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，存在e_uv∈E，表示節(jié)點u和節(jié)點v在彼此的傳輸范圍內(nèi)，可在相同信道上通信，節(jié)點u和節(jié)點v存在一條通信鏈路e_uv。節(jié)點u的鄰居表示為NB_u={i|i∈V，e_ui∈E}。

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

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

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

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

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

式中，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é)點的鏈路預期流量越大，對帶寬的需求也越大，而鏈路的帶寬取決于鏈路周圍的干擾大小，靠近網(wǎng)關(guān)節(jié)點的鏈路應分配干擾較小的信道以獲得較大的帶寬。本文根據(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é)點預期承受的流量也越大，節(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é)點都分配一個等級PL_i，其中i為節(jié)點標號；同時計算每一個節(jié)點周圍的一跳鄰居節(jié)點數(shù)目NB_i，以此來表示周圍節(jié)點的密集程度。然后定義每一個節(jié)點的節(jié)點負載權(quán)重為

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

1.3 算法實現(xià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è)務類型為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ò)吞吐量：

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

    (2)平均端到端延時：

    本小節(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ù)量下吞吐量和時延的變化情況。

    從圖4可以看出，在3個可用分配信道下，LPFCA吞吐量平均提升了22.6%，延時減小了16.7%；在6個可用分配信道下，LPFCA吞吐量平均提升了15.6%，延時減小了17.8%。 

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

3 結(jié)論

    本文首先建立信道分配模型，用線性規(guī)劃方式描述信道分配的目標函數(shù)和約束條件；然后根據(jù)鏈路的位置信息和網(wǎng)絡(luò)的流量特點來估計鏈路的預期負載情況，同時為每一條鏈路計算一個鏈路負載權(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].計算機應用，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.