基于节点优先级的无线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]。混合式信道分配由前两者混合组成，其中一部分节点无线射频接口采用静态分配，其余则采用动态分配，代表算法有基于链路层协议(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