基于链路负载分级的无线Mesh网信道分配算法*

张　颉，柴继文，孙冠杰，林水生，余飞龙

（1.国网四川省电力公司电力科学研究院，四川 成都 610072；2.电子科技大学 通信与信息工程学院，四川 成都 611731）

基于链路负载分级的无线Mesh网信道分配算法*

张颉1，柴继文1，孙冠杰2，林水生2，余飞龙2

（1.国网四川省电力公司电力科学研究院，四川 成都 610072；2.电子科技大学 通信与信息工程学院，四川 成都 611731）

由于无线Mesh网络信道分配算法的性能增益与网络的流量负载特点密切相关，在对多射频多信道无线Mesh网络的流量特点进行分析的基础上，提出一种静态信道分配的启发式算法LPFCA。该算法根据无线链路在网络拓扑中的位置信息来估计无线链路的预期负载情况，并对网络中无线链路的预期负载进行量化分级，利用整数线性规划方法对信道分配进行描述并应用目标函数对信道分配进行优化，使网络总的干扰权重最小化。仿真结果表明，相比于现有的算法，该算法在吞吐量上平均提升了 18.9%。

信道分配；启发式算法；链路负载；线性规划；无线 Mesh网络

0　引言

信道分配是多射频多信道无线Mesh网络的关键技术之一，优秀的信道分配方案能够增大网络吞吐量，提升网络性能。

文献[1-3]通过解决节点、接口与信道之间的协调关系避免了波纹效应，实现负载平衡，但是该方法对网络的拓扑有约束，影响路由的灵活性。文献[4]采用模拟退火算法缓解接口约束对信道分配性能的影响，提升了节点接口受约束条件下的信道分配的性能。文献[5，6]以减小干扰来最大化网络吞吐量为目标，通过建立网络冲突图，采用启发计算法寻找低干扰的信道分配。文献[7，8]采用粒子群智能优化算法来解决信道分配问题，以全局分配的方式来达到网络整体干扰的最小化，但是这种方法没有考虑流量样式对信道分配的影响。文献[9]提出了基于流量感知的信道分配方法，将流量感知因素加入到信道分配的设计中，但是这种信道分配方法依赖于路由协议的联合设计。本文从链路负载估计和信道分配两阶段介绍信道分配策略LDFCA(Link Priority Fixed Channel Assignment)算法。

1　算法描述

无线Mesh骨干网作为接入网络，其网络架构图如图1所示，所有无线 Mesh路由器位置固定，为 Mesh客户端作回传接入。无线Mesh骨干网具有网络流量向网关节点汇聚、网络流量分布不均匀的特点；同时，在局部节点越密集处节点流量负载越重。

图1　无线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网络中所有链路的有效情况。

采用协议干扰模型，计算G={V，E}的干扰矩阵 GC，对于∀gcij∈GC，有：

对于多射频多信道无线 Mesh网络，由式(4)得到的干扰矩阵GC只是一个潜在干扰矩阵，只有当互为潜在干扰链路的两条链路工作在相同信道上时才能真正成为网络中的有效干扰。所以根据式(2)、(3)和(4)可得I(eijeuv)来表示两条链路间存在有效干扰。

式(5)表示当且仅当两条链路互为潜在干扰对象，且都分配了相同信道，链路 eij和链路 euv间存在干扰。

式中，PL_CID表示链路带上负载权重后网络的整体干扰权重，即每两条相互干扰的链路的链路负载权重之和。

综上，信道分配模型即使PL_CID的值最小。

1.2节点优先级的划分及节点负载权重的计算

在无线Mesh骨干网络中，越靠近网关节点的链路预期流量越大，对带宽的需求也越大，而链路的带宽取决于链路周围的干扰大小，靠近网关节点的链路应分配干扰较小的信道以获得较大的带宽。本文根据节点距离网关节点的远近程度，采用分配节点优先级PL(Priority Level)的策略，使靠近网关节点的节点分配较高的优先级。

同时，网络局部节点越密集处，节点预期承受的流量也越大，节点周围链路干扰越大，优先考虑给节点密集处的链路分配干扰较小的信道，平衡整个网络的干扰。在这里考虑节点的密集程度对信道分配的影响，采用为每一个节点计算它的邻居数 NB（Neighbor）的方式来表征节点的密集程度。在得到节点的优先级PL和邻居数NB之后，通过计算得到每个节点的节点负载权重。

首先使用 Dijkstra算法来计算每一个节点到网关节点的最小跳数并以此为每一个节点分级，网关节点的级数最高为1级，依次往下分，直至网络中所有的节点都分配一个等级 PLi，其中 i为节点标号；同时计算每一个节点周围的一跳邻居节点数目NBi，以此来表示周围节点的密集程度。然后定义每一个节点的节点负载权重为。

以图2为例，以节点3为网关节点，计算每个节点的优先级、邻居数以及节点负载权重，如表1所示。

图2　8个节点无线Mesh拓扑示意图

表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为仿真时间。

当林蓝说没抢到做活动的菜籽油或者某培训机构99元试听4节的乐高课，他不再高高在上地发个红包，而是报以宽容的微笑，说：“哇，真遗憾！”

(2)平均端到端延时：

其中 Nrp为成功传输的包的数量，Tdi表示数据包到达目的点的时间，表示数据包发送的时间。

本小节首先仿真LPFCA和文献[8]中的算法在不同可用信道数下的吞吐量对比。然后分别选取3种不同可用信道数，仿真随着数据流数目的增加两种算法的性能。

2.2.1不同信道数下的吞吐量对比

图3中的 Channel-Number表示可用信道数目，Throughput表示网络吞吐量，以kb/s为单位。图3表示了LPFCA和文献[8]中的算法在不同可用信道数下的网络吞吐量对比。LPFCA相对于文献[8]在吞吐量上平均提升了18.9%。

2.2.2不同数据流下的性能仿真

图4中仿真了在不同数据流数量下吞吐量和时延的变化情况。

图3　不同可用信道数下的吞吐量对比

图4　两种不同信道数目下随着数据流变化的性能对比

总体而言，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.

A link load classification-based channel assignment algorithm for wireless Mesh networks

Zhang Jie1，Chai Jiwen1，Sun Guanjie2，Lin Shuisheng2，Yu Feilong2
(1.State Grid Sichuan Electronic Power Research Institute，Chengdu 610072，China；2.School of Communication and Information Engineering，University of Electronic Science and Technology of China，Chengdu 611731，China)

Considering the performance gain of channel assignment algorithm for wireless Mesh networks is closely related to the network traffic load characteristic，through analyzing the traffic load model in multi-radio multi-channel wireless Mesh networks,this paper proposed a static channel assignment heuristic algorithm called LPFCA.The proposed algorithm estimated the expected traffic load of wireless links by its location in the network,quantified the expected load of wireless link and divided all links into different levels.After that the channel assignment was formulated as integer linear programming and the overall network interference weight is minimized by using objective function for optimizing channel assignment.Simulation results show that LPFCA can averagely increase 18.9%throughput compared with the existing algorithm.

channel assignment；heuristic algorithm；link traffic load；linear programming；wireless Mesh networks

TP393

A

10.16157/j.issn.0258-7998.2016.05.023

国网四川省电力公司科技项目(52199715000H)

2015-12-04)

张颉(1982-)，男，博士，主要研究方向：电力通信。

柴继文(1963-)，男，硕士，主要研究方向：电力通信与信息安全。

孙冠杰(1991-)，男，硕士研究生，主要研究方向：无线Mesh网络。

中文引用格式：张颉，柴继文，孙冠杰，等.基于链路负载分级的无线 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.