文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.05.023
中文引用格式： 張頡，柴繼文，孫冠杰，等. 基于鏈路負載分級的無線Mesh網信道分配算法[J].電子技術應用，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 引言
信道分配是多射頻多信道無線Mesh網絡的關鍵技術之一，優秀的信道分配方案能夠增大網絡吞吐量，提升網絡性能。
文獻[1-3]通過解決節點、接口與信道之間的協調關系避免了波紋效應，實現負載平衡，但是該方法對網絡的拓撲有約束，影響路由的靈活性。文獻[4]采用模擬退火算法緩解接口約束對信道分配性能的影響，提升了節點接口受約束條件下的信道分配的性能。文獻[5，6]以減小干擾來最大化網絡吞吐量為目標，通過建立網絡沖突圖，采用啟發計算法尋找低干擾的信道分配。文獻[7，8]采用粒子群智能優化算法來解決信道分配問題，以全局分配的方式來達到網絡整體干擾的最小化，但是這種方法沒有考慮流量樣式對信道分配的影響。文獻[9]提出了基于流量感知的信道分配方法，將流量感知因素加入到信道分配的設計中，但是這種信道分配方法依賴于路由協議的聯合設計。本文從鏈路負載估計和信道分配兩階段介紹信道分配策略LDFCA(Link Priority Fixed Channel Assignment)算法。
1 算法描述
無線Mesh骨干網作為接入網絡，其網絡架構圖如圖1所示，所有無線Mesh路由器位置固定，為Mesh客戶端作回傳接入。無線Mesh骨干網具有網絡流量向網關節點匯聚、網絡流量分布不均勻的特點；同時，在局部節點越密集處節點流量負載越重。
1.1 信道分配模型
將無線Mesh無線網絡拓撲表示為一個無向圖G={V，E}，其中V為無線Mesh網絡的節點集合。整個無線Mesh網絡可用正交信道表示為CK={1，2，3，…K}，將所有正交信道分別標號為：1，2，3，…K。對于每個無線Mesh網絡節點u∈V，節點u的無線射頻接口數用R(u)表示，C(u)表示節點使用的正交信道集。
E表示該無線Mesh網絡的鏈路集合，對于u，v∈V，存在euv∈E，表示節點u和節點v在彼此的傳輸范圍內，可在相同信道上通信，節點u和節點v存在一條通信鏈路euv。節點u的鄰居表示為NBu={i|i∈V，
eui∈E}。
對于每個無線Mesh網絡節點，一個無線射頻接口在某一時刻最多只能分配一個信道。同時，為了保證每個射頻接口的有效利用，節點接口數不能超過可用的正交信道數。所以有如下關系：
對于多射頻多信道無線Mesh網絡，鏈路euv通信的條件如式(2)、式(3)所示：
式(2)中，xuv表示鏈路euv上所分配的信道標號。當euv∈E，并且分配信道k給鏈路euv，k∈CK時，xuv=k；否則，xuv=0。
式(3)中，當鏈路euv被分配了某個信道，表示鏈路euv有效，得到fuv=1；否則，鏈路euv未分配信道或者節點u和節點v間不存在鏈路，得到fuv=0。設F={fuv|u，v∈V且xuv∈X}表示無線Mesh網絡中所有鏈路的有效情況。
對于多射頻多信道無線Mesh網絡，由式(4)得到的干擾矩陣GC只是一個潛在干擾矩陣，只有當互為潛在干擾鏈路的兩條鏈路工作在相同信道上時才能真正成為網絡中的有效干擾。所以根據式(2)、(3)和(4)可得I(eij euv)來表示兩條鏈路間存在有效干擾。
式中，PL_CID表示鏈路帶上負載權重后網絡的整體干擾權重，即每兩條相互干擾的鏈路的鏈路負載權重之和。
綜上，信道分配模型即使PL_CID的值最小。
1.2 節點優先級的劃分及節點負載權重的計算
在無線Mesh骨干網絡中，越靠近網關節點的鏈路預期流量越大，對帶寬的需求也越大，而鏈路的帶寬取決于鏈路周圍的干擾大小，靠近網關節點的鏈路應分配干擾較小的信道以獲得較大的帶寬。本文根據節點距離網關節點的遠近程度，采用分配節點優先級PL(Priority Level)的策略，使靠近網關節點的節點分配較高的優先級。
同時，網絡局部節點越密集處，節點預期承受的流量也越大，節點周圍鏈路干擾越大，優先考慮給節點密集處的鏈路分配干擾較小的信道，平衡整個網絡的干擾。在這里考慮節點的密集程度對信道分配的影響，采用為每一個節點計算它的鄰居數NB（Neighbor）的方式來表征節點的密集程度。在得到節點的優先級PL和鄰居數NB之后，通過計算得到每個節點的節點負載權重。
首先使用Dijkstra算法來計算每一個節點到網關節點的最小跳數并以此為每一個節點分級，網關節點的級數最高為1級，依次往下分，直至網絡中所有的節點都分配一個等級PLi，其中i為節點標號；同時計算每一個節點周圍的一跳鄰居節點數目NBi，以此來表示周圍節點的密集程度。然后定義每一個節點的節點負載權重為
以圖2為例，以節點3為網關節點，計算每個節點的優先級、鄰居數以及節點負載權重，如表1所示。
1.3 算法實現流程
在為每一條鏈路分配信道時，需要計算該鏈路在每一個可用信道上的干擾權重值，以選取干擾最小的信道分配給當前鏈路。鏈路在信道c上的干擾權重值為該鏈路干擾范圍內所有使用信道c的鏈路負載權重之和。
2 仿真實驗與分析
2.1 仿真場景說明
本節在NS3仿真平臺上仿真驗證LPFCA算法與文獻[8]中算法的性能，仿真結果主要通過網絡吞吐量和平均端到端延時兩個指標來衡量。
仿真中每個節點的傳輸距離和干擾距離分別設置為250 m和550 m，在1 200 m×1 200 m的區域內隨機生成包含32個節點的網絡拓撲，每個節點均配置2個無線網卡，無線鏈路的傳輸速率為54 Mb/s。路由協議采用802.11s標準中的HWMP，傳輸業務類型為UDP的CBR流，數據流的源節點隨機選取，目的節點為網關節點，開啟RTS/CTS機制，每個數據包大小為1 024 B，仿真時間為100 s。
2.2 仿真結果分析
仿真的性能指標計算如下：
(1)網絡吞吐量：
其中 Lpkt為每個數據包的長度，Nrp為成功傳輸的包的數量，T為仿真時間。
(2)平均端到端延時：
本小節首先仿真LPFCA和文獻[8]中的算法在不同可用信道數下的吞吐量對比。然后分別選取3種不同可用信道數，仿真隨著數據流數目的增加兩種算法的性能。
2.2.1 不同信道數下的吞吐量對比
圖3中的Channel-Number表示可用信道數目，Throughput表示網絡吞吐量，以kb/s為單位。圖3表示了LPFCA和文獻[8]中的算法在不同可用信道數下的網絡吞吐量對比。LPFCA相對于文獻[8]在吞吐量上平均提升了18.9%。
2.2.2 不同數據流下的性能仿真
圖4中仿真了在不同數據流數量下吞吐量和時延的變化情況。
從圖4可以看出，在3個可用分配信道下，LPFCA吞吐量平均提升了22.6%，延時減小了16.7%；在6個可用分配信道下，LPFCA吞吐量平均提升了15.6%，延時減小了17.8%。
總體而言，LPFCA算法在吞吐量和延時上都體現出較優的性能，這是因為無線Mesh網絡中流量分布不均勻，各鏈路上承載的流量負載也不同，而LPFCA以無線鏈路的位置信息來預估無線鏈路的預期負載的方式結合了無線Mesh網絡的流量特點，使得預期負載越大的鏈路能夠分配干擾越小的信道以獲取更高的帶寬來滿足流量負載需求，因而能夠體現出更好的性能。
3 結論
本文首先建立信道分配模型，用線性規劃方式描述信道分配的目標函數和約束條件；然后根據鏈路的位置信息和網絡的流量特點來估計鏈路的預期負載情況，同時為每一條鏈路計算一個鏈路負載權重；最后以每條鏈路的負載權重為基礎，以啟發式算法的形式為其分配信道。與文獻[8]中的算法相比，LPFCA更符合無線Mesh網絡的流量特點，更能滿足其流量負載需求。通過仿真結果證明，該算法能夠有效地提升無線Mesh網絡的吞吐量，減小延時。
參考文獻
[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網絡信道分配算法[J].計算機應用，2009，29(7)：1849-1851.
[7] 張旭，殷昌盛，熊輝，等.無線Mesh網絡中基于離散粒子群優化的信道分配算法[J].現代電子技術，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.