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网络可用正交信道表示为C_K={1，2，3，…K}，将所有正交信道分别标号为：1，2，3，…K。对于每个无线Mesh网络节点u∈V，节点u的无线射频接口数用R(u)表示，C(u)表示节点使用的正交信道集。

    E表示该无线Mesh网络的链路集合，对于u，v∈V，存在e_uv∈E，表示节点u和节点v在彼此的传输范围内，可在相同信道上通信，节点u和节点v存在一条通信链路e_uv。节点u的邻居表示为NB_u={i|i∈V，e_ui∈E}。

    对于每个无线Mesh网络节点，一个无线射频接口在某一时刻最多只能分配一个信道。同时，为了保证每个射频接口的有效利用，节点接口数不能超过可用的正交信道数。所以有如下关系：

    对于多射频多信道无线Mesh网络，链路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未分配信道或者节点u和节点v间不存在链路，得到f_uv=0。设F={f_uv|u，v∈V且x_uv∈X}表示无线Mesh网络中所有链路的有效情况。

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

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

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

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

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

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

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

    以图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)网络吞吐量：

其中 L_pkt为每个数据包的长度，N_rp为成功传输的包的数量，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.