基于節點優先級的無線Mesh網絡資源分配

張 劼，鐘 朗，李廣軍，楊學敏，楊云樂(. 國網四川省電力公司電力科學研究院 成都 6007；. 電子科技大學通信與信息工程學院 成都 673)

?

基于節點優先級的無線Mesh網絡資源分配

張 劼1，鐘 朗2，李廣軍2，楊學敏2，楊云樂2
(1. 國網四川省電力公司電力科學研究院 成都 610072；2. 電子科技大學通信與信息工程學院 成都 611731)

【摘要】隨著網絡負載的增加，多射頻多信道(MRMC)無線Mesh網絡的性能也隨之下降。為減小網絡中的擁塞和干擾，提升網絡性能，綜合考慮鏈路干擾和鏈路負載，提出了一種基于節點優先級策略的信道資源分配(NPFCA)方案，并引入離散粒子群優化(DPSO)算法對NPFCA進行快速迭代收斂。仿真在不同的正交信道數以及不同網絡負載下進行，結果表明，該NPFCA方案在不同網絡條件下，其吞吐量較傳統的CCA和C-HYA算法分別具有32.9%～73.3%和5.5%～17.0%的提升。

關 鍵 詞優先級; 粒子群優化; 資源分配; 無線Mesh網絡

Node-Priority Based Resource Allocation in Wireless Mesh Networks

ZHANG Jie1, ZHONG Lang2, LI Guang-jun2, YANG Xue-min2, and YANG Yun-le2
(1. Sichuan Electric Power Research Institute, State Grid Chengdu 610072; 2. School of Communications and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731)

Abstract The performance of multi-radio multi-channel (MRMC) wireless Mesh networks decreases with the increase of the network load. To mitigate congestion and interference and improve the performance, this paper focuses on the channel resource assignment optimization of MRMC wireless Mesh networks. Instead of the conventional minimum interference allocation methods, both link interference and node load are considered to classify nodes into multiple levels. Based on this classification, a mathematical optimization objective is proposed, which named as node priority fixed channel assignment (NPFCA). In order to solve this problem efficiently, the discrete particle swarm optimization (DPSO) algorithm is introduced. Numerical simulation results on different number of orthogonal channels and different network loads demonstrate that the presented NPFCA scheme has about 32.9%～73.3% and 5.5%～17.0% throughput improvement, respectively, compared with traditional CCA and C-HYA schemes.

Key words priority; PSO; resource allocation; wireless Mesh networks

在無線Mesh網絡中，隨著通信距離增大，跳數增多，數據傳輸速率會明顯降低，同時產生網絡擁塞和信道干擾等問題，極大地影響網絡吞吐量[1]。如何緩解無線Mesh節點負載，疏通整個網絡，從而提高整體傳輸性能已成為至關重要的問題。

由于傳統單射頻單信道技術(single-radio single-channel，SRSC)信道切換頻繁，不僅增加延遲，還需復雜的節點同步與信道切換機制[2-3]。因此，無線Mesh網絡引入了多射頻多信道(multi-radio multi-channel，MRMC)技術[4]，使用多個正交信道與不同相鄰節點通信，以減輕鏈路干擾。然而，實際無線Mesh網絡節點接口數往往遠小于系統可用信道數，故如何分配信道和無線射頻接口，是MRMC無線Mesh網絡所要面臨的挑戰。

常見的信道分配算法根據接口切換頻率分為靜態分配、動態分配和混合式3種。其中靜態分配又分為公共信道分配(common channel assignment，CCA)和變化信道分配(varying channel assignment，VCA)。CCA中每個網絡節點都分配相同的信道[5]，資源利用率不高。VCA中不同節點射頻接口所分配的信道可能不同[6]，故不同的分配方案會得到不同的網絡拓撲，其典型代表為分布式信道分配(D-HYA)算法[7]?；旌鲜叫诺婪峙溆汕皟烧呋旌辖M成，其中一部分節點無線射頻接口采用靜態分配，其余則采用動態分配，代表算法有基于鏈路層協議(link layer protocol，LLP)[8]和基于干擾感知的廣度優先搜索信道分配(breadth first search-channel assignment，BFS-CA)[9]算法。

以上文獻多以最小化鏈路干擾為主，較少考慮鏈路負載分布的不同。實際網絡中不同鏈路負載不一，對資源的需求亦有所區別。本文提出NPFCA的分配方案從無線Mesh網絡整體出發，綜合考慮鏈路間干擾和每條鏈路負載，對節點按負載不同進行優先級劃分，以進一步提升網絡容量，并使用離散粒子群優化(DPSO)算法快速求解。

1 系統模型

無線Mesh網絡的系統模型主要包括網絡模型和鏈路干擾模型。

1.1 網絡模型

無線Mesh網絡通常包括網關節點(mesh point collocated with a mesh portal，MPP)、Mesh節點(mesh point，MP)、接入節點(mesh access point，MAP)和用戶終端。本文模型中所有節點均使用全向天線。此外，每個節點都可在不同射頻和信道間進行切換，且每個射頻接口都工作在半雙工模式下。

式(2)中xuv表示鏈路euv上所分配信道的標號，當且分配了信道時，有否則式(3)中fuv表示鏈路euv的有效情況，當被分配了信道，即可得否則可用表示無線Mesh網絡中所有鏈路的有效情況。由式(2)可得，節點u所分配信道數為：

式中，card{}為返回集合中元素個數；條件xui≠表示返回集合中不相同且不為零元素的個數，是節點u所有射頻接口上分配的信道集合。

1.2 干擾模型

無線Mesh網絡根據干擾源的定義不同，可分為物理干擾模型和協議干擾模型[10]。由于物理干擾模型較為復雜，故本文采用文獻[11]中的協議干擾模型，將節點有效范圍分為節點傳輸范圍Rtx、節點載波偵聽范圍Rcs和節點干擾范圍Ri?？紤]到當Rcs和不等時，節點可能因偵聽和干擾范圍不相匹配而無法準確把握網絡狀態，為便于分析，令而Rcs一般為Rtx的2～2.78倍，本文取模型如圖1所示，當節點u通過信道k向節點v發送數據時，成功接收的充要條件是：1) v、u之間的距離滿足對于其他使用信道k的節點w，均滿足

圖1　協議干擾模型示意圖

圖2　基于鏈路的協議干擾模型

由于節點間的通信是相互的，若要保證網絡中任意兩條鏈路ei和ej互不干擾，如圖2所示，條件2)應重寫為：

2 節點優先級劃分及鏈路負載計算

無線Mesh網絡中端到端數據流分為MP與MPP間的數據流和MP之間的數據流。對于前者，越靠近MPP負載越重，要提高性能必須盡可能減少鏈路干擾；而對于后者，往往相鄰MP越多，該MP潛在負載越重。在實際網絡中數據流以前者居多[12]，因此本文假設絕大部分數據流為第一類，并對節點設置優先級，MPP設為最高級，其余節點按網關的最小跳數分級，越少優先級越高。

以圖3中的無線Mesh網絡為例，設節點3為MPP，分級結果如圖3b所示。根據節點優先級及其相鄰節點數，得到相應鏈路eij的負載權重為：

即wij為鏈路eij兩端節點各自相鄰節點數與節點優先級比值之和，wij越大則優先級越高，反之亦然。

圖3　隨機8節點無線Mesh網絡拓撲分級示意圖

3 NPFCA信道資源分配優化模型

根據文獻[7]，信道分配須遵守以下準則：1) 網絡總可用信道數有限；2) 每個節點占用信道數不超過其射頻接口數；3) 任意兩節點可直連的必要條件是它們在彼此的Rtx內，且至少有一個共用信道。

根據式(3)，實際干擾可為：

在計算網絡整體干擾度時，本文運用第2節提出的節點優先級策略，將網絡節點按潛在負載分級，同時，在對同一節點的多條鏈路進行分配時，按照其負載權重wij分級，其值越大，優先分配權越高，以保證其干擾范圍內的鏈路盡量不使用與之相同的信道。引入鏈路負載后的網絡整體干擾度為：

基于式(6)的靜態信道資源分配優化模型為：

式(7)為一個整數線性規劃模型，其輸入為網絡拓撲、總可用信道數、節點接口數和MPP標號。盡管該問題可用LINGO[13]等商業軟件求解，但無線Mesh網絡信道分配優化問題已經被證實為一個NP問題[14]，求解時間隨網絡規模增加呈指數級遞增?？紤]到實用性，需要一種低復雜度的算法求解。

4 基于PSO的NPFCA分配優化方案

顯然式(7)中的優化問題需要迭代求解，而傳統迭代優化算法通常是從搜索空間中的一點按一定規則轉移到另外一點，效率不高。針對此問題，本文引入粒子群優化(PSO)算法求解。該方法屬于群智能優化算法，通過概率轉移規則，從不同的初始點對搜索空間進行并行搜索，能快速發現最優解，因此更具實用性。

4.1 基于DPSO算法的信道分配方案

由于PSO算法[15]針對連續優化問題，因此必須將其離散化為DPSO才能應用于式(7)。在DPSO算法[16]中，若一個粒子群規模為M，第i( i∈ M )個粒子在第d次迭代中的位置為，速度為所經歷的最優解為整個種群所經歷的最優解為gB，則粒子i將會根據式(8)和式(9)更新自己的速度和位置，有：

式中，ω為慣性權重，賦予粒子一定的運動慣性；c1和c2為常數，稱為學習因子，用于保證粒子向個體最優解和全局最優解靠近，且為均勻分布于[0,1]之間的隨機數。

將DPSO算法引入提出的NPFCA信道分配方案，則粒子的位置、速度及相關操作定義如下：

1) 粒子的位置：由式(2)中鏈路euv上所分配的信道標號xuv組成粒子的位置矢量X=其中X對應一種信道分配方案，有。

2) 粒子的速度：對應于信道分配中鏈路上信道標號的變化，定義為

3) 位置與位置的減法操作：即DPSO算法中兩種信道分配方案的差別，記為其元素vi通過逐一比較X2和X1中的元素x2,i和x1,i得到：

7) pBi和gB的計算：根據式(6)得到的網絡整體干擾度PL_CID，判斷出當前pBi和gB并記錄。

4.2 慣性權重與學習因子的設置

下面通過仿真尋找參數ω、c1和c2的最優配對。網絡拓撲如圖4所示，相鄰節點間距170 m，僅縱向和橫向相鄰節點能直接通信。每個節點有3個無線射頻接口，采用IEEE802.11a協議，可用正交信道數為12，粒子群規模為50，最大迭代次數100，通過10次計算取平均值。

圖4　網格型拓撲結構圖

先令ω=1，考察不同c1、c2取值下的迭代結果和收斂速度。具體結果如表1～表3所示。

表1　不同c1和c2配對下的網絡干擾度

表2　不同c1和c2配對下的收斂速度(越小越好)

表3　不同ω取值下網絡干擾度和收斂速度

5 性能仿真和結果分析

本節主要對提出的基于DPSO的NPFCA信道分配算法進行仿真，并與文獻[5]中的CCA和文獻[12]中的C-HYA兩種典型算法進行比較。仿真分別考察不同可用正交信道數和不同網絡負載下NPFCA算法及兩種參考算法的平均吞吐量。

5.1 仿真參數設置

表4　仿真系統的參數設置

網絡平均吞吐量為[17]：

式中，C為網絡吞吐量；s為數據包大??；Nr為接收數據包數；Tp為接收據包總時長；N為數據流數。所有仿真均使用表4所示的公共參數設置。信道模型采用的對數距離模型其中，rx為發送功率；tx為接收功率；n為路徑損耗距離因子；d為節點間距；d0為系統參考距離；L0則表示參考距離的路徑損耗。

所有仿真均使用HWMP先驗式路由，且以相同模型和場景中20個隨機種子仿真結果的平均值作為結果，基本符合網絡數據的統計特性。

5.2 不同正交信道數性能對比

在實際網絡中，可用正交信道數并非一成不變，故仿真旨在考察不同正交信道數對吞吐量的影響。設節點12為根節點，得到分級結果如表5所示。

表5　32節點網格拓撲節點分級

隨機選取5個MP同MPP建立速率為500 kb/s的固定碼率(constant bit rate，CBR)數據業務，每個節點在仿真時長內隨機選取時間發起數據傳輸，并持續50 s，如果從開始發起到仿真結束不足50 s，則以仿真結束為終止標記。仿真結果如圖5所示。

圖5　不同正交信道數網絡總吞吐量的比較

從圖5可以看出：隨著正交信道數目的增加，本文的NPFCA方案以及C-HYA方案的網絡吞吐量呈遞增趨勢，而CCA方案中由于所有節點均分配相同的3個正交信道，其網絡總吞吐量并未發生改變；當信道數增加至9后NPFCA和C-HYA上升趨勢變緩。在正交信道數為6時，本文的NPFCA方案吞吐量較CCA提升約32.9%，較C-HYA提升約11.2%，當可用正交信道數為12時，NPFCA方案吞吐量較CCA提升約46.8%，較C-HYA提升約5.5%。

5.3 不同網絡負載性能對比

實驗一：不同傳輸速率下的吞吐量比較。隨機選取5個MP同MPP建立CBR業務，設置CBR流速率為200 kb/s～2 Mb/s，其余條件同上，全網可用正交信道數為6，結果如圖6所示。

圖6　不同CBR傳輸速率下網絡總吞吐量比較

由圖6可知，隨著傳輸速率的增加，3種方案的吞吐量均隨之增加，但逐步趨緩；本文的NPFCA方案在三者中性能最好，增長曲線最平滑，且隨著傳輸速率的增加性能優勢逐步擴大；當速率達到2 Mb/s時，NPFCA吞吐量較CCA高60.6%，較C-HYA高17.0%。

圖7　不同CBR數據流數下網絡總吞吐量比較

實驗2：不同CBR數據流數吞吐量比較。隨機選取1～20個MP同MPP建立CBR業務，速率為500 kb/s，其余條件同上，結果如圖7所示。

觀察圖7不難看出：隨著數據流數增加，3種算法吞量開始均呈遞增趨勢，但是到后期反而有所下降，主要是因為當數據流增加到一定程度，網絡中同時存在的數據流數達到甚至超過最大鏈路帶寬負載，使得數據沖突嚴重；本文的NPFCA方案在數據流數為18時吞吐量達到最大值，隨后才開始下降，較C-HYA方案來得更晚；此時NPFCA的性能較CCA 和C-HYA分別有73.3%和10.6%的提升。

6 結 束 語

本文針對MRMC無線Mesh網絡中擁塞和傳輸干擾問題，綜合考慮了網絡中鏈路干擾和鏈路負載分布，提出了一種基于節點優先級策略的靜態信道分配優化方案NPFCA，以最小化網絡整體干擾度，從而進一步提升網絡吞吐量。該方案從實際應用角度出發，引入離散粒子群優化算法DPSO進行迭代收斂，以快速得到最優信道分配。仿真考慮了不同正交信道數和不同網絡負載，結果表明，在不同的網絡條件下，本文提出的NPFCA方案在吞吐量方面較傳統的CCA和C-HYA方案分別有約32.9%～73.3% 和5.5%～17.0%的提升。

本文的研究工作得到了國網四川省電力公司科技項目(52199715000H)的支持，在此表示感謝！

參 考 文 獻

[1] JAIN K, PADHYE J, PADMANABHAN V N, et al. Impact of interference on multi-hop wireless network performance[J]. Wireless Networks, 2005, 11(4): 471-487.

[2] KU C Y, LIN Y D, TSAO S L, et al. Utilizing multiple channels with fewer radios in wireless Mesh networks[J]. IEEE Transactions on Vehicular Technology, 2011, 60(1): 263-275

[3] SHARMA A, BELDING E M. FreeMAC: Framework for multi-channel mac development on 802.11 hardware[C]// Proceedings of the ACM Workshop on Programmable Routers for Extensible Services of Tomorrow. [S.l.]: ACM, 2008: 69-74.

[4] PENG Yu-huai, YU Yao, GUO Lei, et al. An efficient joint channel assignment and QoS routing protocol for IEEE 802.11 multi-radio multi-channel wireless Mesh networks[J]. Journal of Network and Computer Applications, 2013, 36(2): 843-857.

[5] ADYA A, BAHL P, PADHYE J, et al. A multi-radio unification protocol for IEEE 802.11 wireless networks[C]// International Conference on Broadband Networks. [S.l.]: IEEE, 2004: 344-354.

[6] MARINA M K, DAS S R, SUBRAMANIAN A P. A topology control approach for utilizing multiple channels in multi-radio wireless Mesh networks[J]. Computer Networks, 2010, 54(2): 241-256.

[7] RANIWALA A, CHIUEH T. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless Mesh network[C]//Annual Joint Conference of the IEEE Computer and Communications Societies. [S.l.]: IEEE, 2005(3): 2223-2234.

[8] KYASANUR P, VAIDYA N H. Routing and link-layer protocols for multi-channel multi-interface ad hoc wireless networks[J]. Mobile Computing and Communications Review, 2006, 10(1): 31-43.

[9] RAMACHANDRAN K N, BELDING E M, ALMEROTH K C, et al. Interference-aware channel assignment in multi-radio wireless Mesh networks[C]//IEEE International Conference on Computer Communications. [S.l.]: IEEE, 2006(6): 1-12.

[10] GUPTA P, KUMAR P R. The capacity of wireless networks[J]. IEEE Transactions on Information Theory, 2000, 46(2): 388-404.

[11] XU Kai-xin, GERLA M, BAE S. How effective is the IEEE 802.11 RTS/CTS handshake in ad hoc networks[C]// Global Telecommunications Conference. [S.l.]: IEEE, 2002, 1: 72-76.

[12] RANIWALA A, GOPALAN K, CHIUEH T. Centralized channel assignment and routing algorithms for multichannel wireless Mesh networks[J]. Mobile Computing and Communications Review, 2004, 8(2): 50-65.

[13] LINGO. LINGO 11.0[EB/OL]. [2014-08-20]. http:// www. lingo.com 2005-9-1.

[14] MURTHY C S, MANOJ B S. Ad hoc Wireless Networks: Architectures and Protocols[M]. [S.l.]: Prentice Hall PTR, 2004.

[15] KENEEDY J, EBERHART R C, SHI Y. Swarm Intelligence[M]. [S.l.]: Morgan Kaufman Publishers, 2001. [16] KENNEDY J, EBERHART R C. A discrete binary version of the particle swarm algorithm[C]//IEEE International Conference on Computational Cybernetics and Simulation. [S.l.]: IEEE, 1997(5): 4104-4108.

[17] RANIWALA A, CHIUEH T. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless Mesh network[C]//Annual Joint Conference of the IEEE Computer and Communications Societies. [S.l.]: IEEE, 2005(3): 2223-2234.

編 輯 漆 蓉

作者簡介：張劼(1982 ? )，男，博士，主要從事無線通信技術方面的研究.

基金項目：國家自然科學基金(612032301)；中國博士后科學基金(2013M530629)

收稿日期：2014 ? 10 ? 08；修回日期： 2015 ? 03 ? 02

中圖分類號TN915.02

文獻標志碼A

doi:10.3969/j.issn.1001-0548.2016.01.008