基于粒子群优化的无线Mesh网络信道分配算法

张云春，王玉婧，姚绍文，李 娜，胡建陶



基于粒子群优化的无线Mesh网络信道分配算法

张云春，王玉婧，姚绍文，李 娜，胡建陶

(云南大学软件学院 昆明 650095)

多信道多天线(MCMR)广泛被用于提升无线Mesh网络的性能，但现有信道分配算法存在两方面问题：算法的时间太长和空间复杂度过高，无法获得全局最优解；算法可扩展性差，无法适用于大规模的网络。为解决上述问题，该文借鉴粒子群优化算法在收敛快、开销小等方面的优势，以建模无线Mesh网络中的信道分配问题。通过网络信息的交换和干扰模型的定义，以最小化适应度函数为优化目标，以天线、可用信道数量、信号干扰等为约束条件，设计并实现了基于粒子群优化的信道分配算法(PSOCA)。仿真实验表明了算法的可行性，且与同类算法相比，该算法在网络吞吐量和丢包率两个方面具有明显的改善。

信道分配; 适应度函数; 多信道多天线; 粒子群优化; 无线Mesh网络

MCMR技术通过提高无线信号的时空复用度，已经被证明是一种有效提高无线网络性能的手段，近年来在工业界和学术界都取得了显著发展。在众多类型的无线网络中，无线Mesh网络因其便利的安装和维护、高可扩展性等优势取得了广泛的应用。将MCMR技术用于无线Mesh网络，可显著地缓解容量问题，增加网络聚合带宽[1-2]。然而MCMR技术并非完美无瑕的解决方案[3]，将其用于无线Mesh网络时仍面临诸多挑战。配置了MCMR的无线Mesh网络提升性能的关键在于通过信道分配，最大化可并发传输的链路的总数量。而MCMR下求解最优的信道分配算法已经被证明为NP-complete问题[4-5]，因此，如何实现合理信道分配显得尤其重要。

在现有的信道分配方法中，集中式信道分配能够通过全局的信息进行合理的分配，但获取网络的全局信息使得开销增大且性能降低，无法满足实际应用的需求。分布式信道分配算法虽然能有效降低开销，但要求节点之间的同步，很难实现全局最优分配。为降低信道分配算法的复杂度，提高算法的可扩展性，许多学者提出不同的改进算法，如基于贪心策略[6]、子集和[7]、Max-Cut算法[8]和博弈论[9]的分配方案。此类算法不一定能得到全局最优解，但适应动态变化的无线网络特点，且能有效降低算法复杂度。因此，对信道分配问题有待深入研究和改进，提出更加优化的算法。

同时，随着群体智能技术不断创新，其模型和算法在降低复杂度、可扩展性、快速收敛等方面展现了良好的性能。其中，粒子群优化算法(particle swarm optimization, PSO)具有计算简单、优化性能好等特点，在许多领域获得广泛应用。因此，该文对粒子群优化运用于求解无线Mesh网络中的信道分配问题进行研究，证明其合理性和有效性。

1 研究背景

根据节点上信道切换的频率可将信道分配算法分为静态、动态和混合式3种类型。

常见的静态信道分配算法有CLICA[10]、CTA[4]、MesTiC[1]等。静态分配算法一旦分配信道后，在很长一段时间内不再发生改变。这种分配方式虽缺少灵活性，但能保证网络的连通性，考虑到WMN骨干网的拓扑相对稳定，静态分配算法在静态拓扑网络中效果显著。但实际应用中，网络拓扑结构、节点状态、数据流等频繁变化，致使静态分配算法无法直接运用。

动态信道分配算法以D-HYA[11]为代表，根据网络实时状态的变化而自动进行信道切换，实现网络性能的最佳配置。虽然动态分配反映了网络的实时信息，但频繁切换导致的延迟使得切换期间无法正常传输，降低了网络性能。

混合式信道分配算法以HMCP[12]和LLLA[13]为代表。该类算法兼具前两者的优点，用静态分配的信道接口交换控制信息，剩下的接口可动态切换信道，用于进行数据传输。

综合来看，信道分配面临复杂度高和可扩展性差两个主要困难。因此，需要结合网络和应用的特点来设计适用的信道分配算法。

2 信道分配建模与算法

2.1 干扰模型

5) 潜在的链路干扰图(possible link interference graph, PLI)，表示两条链路之间的潜在干扰关系，当且仅当这两条链路在实际通信时分配了相同的信道，潜在干扰才会转化成真实干扰。其定义如下：

6) 链路的信道分配矩阵(link-channel assignment matrix, LCAM)，表示链路及其上信道的分配关系，定义如下：

7) 节点信道分配矩阵(node-channel assignment matrix, NCAM)，表示节点上已经分配的信道信息。通过节点链路矩阵和链路信道分配矩阵中的数据来计算NCAM。NCAM的建立是为了在信道分配后，判断真实的信道干扰情况，定义为：

8) 真实链路干扰图(real-link interference graph, RLI)，表示链路之间的干扰关系，通过PLM与LCASSIGN计算而得，作为优化模型中计算适应度的主要依据，定义为：

2.2 链路发送速率模型

2.3 适应度模型

基于PSO的信道分配算法中，采用适应度模型作为算法优化目标评价函数。适应度函数以网络中链路的干扰程度和发送速率为基础加权计算而得：

以最小化适应度函数为目标，优化模型受两个主要约束条件制约，即信道资源和天线资源。

首先，任何一个链路上分配的信道数不允许多于1个，根据PLI的定义，该约束条件可定义为：

其次，网络中任何一个节点上分配的信道总量不能超过此节点上配置的天线总量。该约束可定义为：

2.4 粒子群优化模型

基于PSO的优化算法的关键在于粒子的速度和位置，在粒子群优化算法中粒子的速度和位置满足：

在信道分配模型中，定义通信链路为单个独立的粒子，通信链路上分配的信道为粒子的位置，信道切换的概率定义为粒子的移动速度，即在节点上对应的链路选择某个信道的概率函数。基于如上的定义，建立的信道分配模型可以表示为：

综合上述定义，本文设计的基于PSO的信道分配算法，以最小化适应度函数为目标，同时满足天线和信道分配等约束条件，即：

目标函数：min(fitness)

2.5 算法执行过程

通过模型的建立和适应度函数的定义，基于PSO的无线Mesh网络信道分配算法主要包括两个步骤：算法初始化、迭代优化最终解。

算法1：PSOCA//基于粒子群优化的信道分配算法

//采集网络各节点信息，获得各参数初始化值

{

初始化粒子种群initiate()；

{

ELSE {

verify and adjust result()；

//约束条件检查及分配调整

Localbest()；//局部最优解计算}

}

globalbest()；//计算全局最优解

}

3 仿真实验与性能分析

3.1 仿真环境

仿真实验在NS2模拟器中进行，增加了多输入多输出天线(multiple input multiple output, MIMO)的配置，并修改节点配置函数。假定节点均匀分布，每个节点的通信半径、干扰半径、可用的信道总数和无线射频接口数量均相同。模拟以无线Mesh网络的骨干网为主，即假定网络中的节点具有较小的移动性。实验中随机选择发送数据的源节点及接收数据的目的节点。经过多次实验，计算平均值作为最终的结果。

3.2 性能测试与分析

为比较基于PSO的信道分配算法(PSOCA)的性能，测试中选取单信道单接口(SISO)和基于Ramon的信道分配算法进行比较，分别从网络吞吐量、端到端时延和丢包率3个方面进行测试和分析。

1) 网络吞吐量性能分析

网络吞吐量(network throughput)指单位时间内节点可以接收的数据包总量。随着节点发送速率的变化，三者的吞吐量测试结果如图1所示。

图1 网络吞吐量对比

如图1所示，基于多信道的两种方案(PSOCA及Ramon)比单信道方案获得更好的吞吐量。另外，PSOCA获得最好的网络吞吐量，因为该算法有效地降低了网络干扰，从而提升网络吞吐量。

2) 端到端时延分析

端到端传输时延表示每个数据包从离开发送节点至接收节点之间所经过的平均时间延迟。仿真时，在单网关节点网络中，随机设置1个和3个源节点，平均端到端时延的结果分别如图2和图3所示。

由图2和图3可知，在数据量不大的情况下，单天线单信道情况下的平均端到端时延较低。因为此时网络中数据量较小，路由相对固定。相反，多信道多天线的通信方式下的平均端到端时延相对较高，因为信道的切换和重新分配使得数据包的传输受到一定程度的影响。

图2 平均端到端时延(单网关-1个源节点)

图3 平均端到端时延(单网关-3个源节点)

3) 丢包率分析

丢包率指丢失的数据包在所有发送数据包中所占的百分比。在单网关节点网络中，分别设置1～3个发送源节点，得到的丢包率性能分别如图4、图5和图6所示。

如图4所示，在单天线单信道的场景中丢包率维持在较高的比例，而采用多信道多天线能够降低网络中的丢包率。另外，基于PSO的信道分配算法中丢包率维持在较为平稳的水平，而仅仅采用Ramon的多天线多信道的方式呈现出较好的性能。这是因为，Ramon的配置脚本中假设网络中天线数量大于可用信道的数量，没有信道切换的开销。

如图5及图6所示，随着网络中源节点的增加，节点发送数据包的增多，基于PSO的信道分配算法呈现出最好的性能，随着数据量的增大，丢包率趋于稳定状态。初始时的波动是因为信道的动态切换所导致的，但一旦稳定后，由于PSO对网络干扰进行了最佳优化，因此获得了良好的性能。

图4 丢包率对比(单网关-单源节点)

图5 丢包率对比(单网关-2个源节点)

图6 丢包率对比(单网关-3个源节点)

综合来看，基于PSO的信道分配算法在网络吞吐量和丢包率两个方面均比单信道单天线固定信道算法及同类算法呈现出更好的性能，但因信道的动态切换，导致平均端到端延迟有所增加。

4 结束语

应用范围的扩大和需求的持续增长都对无线Mesh网络提出更高的性能需求。MCMR虽能有效改善网络性能，但信道分配算法的复杂度、最优解计算和可扩展性都有待借鉴新方法加以优化。利用粒子群优化算法具有计算复杂度低、优化性能良好的优点，设计了基于PSO的信道分配算法。仿真实验结果表明，基于PSO的信道分配算法在网络吞吐量和丢包率方面均比同类算法展现出了更好的性能。但该算法受限于信道切换所造成的临时性网络传输中断，在平均端到端延迟方面还有待进一步改善，可行的改善途径应注重静态分配信道和动态分配信道两者的结合和优化，这也是下一步的主要工作。

信道分配问题因其本身的复杂度较高，在有限的时间范围内不能得到合理的全局最优解，只能适用于实时性和精确度要求不高的场景。因此要对信道分配算法进行优化，而优化的算法不局限于群体智能优化算法。未来可以引入更好的优化算法来降低现有算法的复杂度，使其能在有限时间内得到较好的方案。目前的优化算法只考虑了网络中的干扰和链路的发送速率，为了取得更好的全局效应，还可以考虑结合更多的性能指标。

[1] SKALLI H, GHOSH S, DAS S K, et al. Channel assignment strategies for multiradio wireless mesh networks: Issues and solutions[J]. Communication Magazine, 2007, 45(11): 86-95.

[2] LIU K M, TAO M A, LIU Y A, et al. Fairness-oriented routing algorithm joint with power control and channel assignment for multi-radio multi-channel wireless mesh networks[J]. Journal of China Universities of Posts & Telecommunications, 2014, 21(5): 55-60.

[3] WANG J, SHI W, CUI K, et al. Partially overlapped channel assignment for multi-channel multi-radio wireless mesh networks[J]. Eurasip Journal on Wireless Communications & Networking, 2015(1): 1-12.

[4] SUBRAMANIAN A P, GUPTA H, DAS S R, et al. Minimum interference channel assignment in multiradio wireless mesh networks[J]. IEEE Transactions on Mobile Computing, 2008, 7(12): 1459-1473.

[5] AUDHYA G K, SINHA K, GHOSH S, et al. A survey on the channel assignment problem in wireless mesh networks[J]. Wireless Communications & Mobile Computing, 2011, 11(5): 583-609.

[6] WANG W, KASIRI B, CAI J, et al. Channel assignment schemes for cooperative spectrum sensing in multi-channel cognitive radio networks[J]. Wireless Communications & Mobile Computing, 2015, 15(10): 1471-1484.

[7] UYANIK G S, ABDEL-RAHMAN M J, KRUNZ M. Optimal channel assignment with aggregation in multi- channel systems: a resilient approach to adjacent-channel interference[J]. Ad Hoc Networks, 2014, 20(2): 64-76.

[8] YANG M, LIU B, WANG W, et al. Maximum capacity overlapping channel assignment based on max-cut in 802.11 wireless mesh networks[J]. Journal of Universal Computer Science, 2014, 20(13): 1855-1874.

[9] DUARTE P B F, FADLULLAH Z M, VASILAKOS A V, et al. On the partially overlapped channel assignment on wireless mesh network backbone: a game theoretic approach[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(1): 119-127.

[10] 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 the International Journal of Computer & Telecommunications Networking, 2010, 54(2): 241-256.

[11] RANIWALA A, TZI-CKER C. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh networks[C]//the 24th Annual Joint Conference of the IEEE Computer and Communications Societies. [S.l.]: IEEE, 2005.

[12] KYASANUR P, VAIDYA N H. Routing and link-layer protocols for multi-channel multi-interface Ad Hoc wireless networks[J]. SIGMOBILE Mob Comput Commun Rev, 2006, 10(1): 31-43.

[13] SHOJAFAR M, POORANIAN Z, SHOJAFAR M, et al. LLLA: New efficient channel assignment method in wireless mesh networks[J]. Advances in Intelligent Systems & Computing, 2014, 237: 143-152.

[14] CHAUDHRY A U, HAFEZ R H M, CHINNECK J W. On the impact of interference models on channel assignment in multi-radio multi-channel wireless mesh networks[J]. Ad Hoc Networks, 2015, 27: 68-80.

编 辑 叶 芳

A PSO-Based Channel Assignment Algorithm in Wireless Mesh Networks

ZHANG Yun-chun, WANG Yu-jing, YAO Shao-wen, LI Na, and HU Jian-tao

(School of Software, Yunnan University Kunming 650095)

Multi-channel multi-radio (MCMR) has been widely used in wireless mesh networks for improving the network performance. Two primary problems are faced in existing channel assignment algorithms. One is that it is impossible to achieve global optimization because both the time and space complexity are high. The other problem is that those algorithms can not be scaled flexibly and, thus, cannot be applied to large networks. To solve the above problems, this paper models the channel assignment problem with particle swarm optimization model by utilizing its advantages of fast convergence and low cost. Based on the network message exchange and interference model, a particle swarm optimization based channel assignment algorithm (PSOCA) is proposed. This algorithm aims at minimizing the fitness function with constraints of radios, channels, interference and so on. Through intensive simulations, the algorithm proposed is proved feasible, both the network throughput and packet drop ratio are remarkably improved in comparison with other similar algorithms.

channel assignment; fitness function; multi-channel multi-radio; particle swarm optimization; wireless mesh networks

TP393

A

10.3969/j.issn.1001-0548.2017.05.015

2016-01-21；

2017-03-06

国家自然科学基金(61363021)；云南省应用基础研究计划青年项目(2012FD004)

张云春(1981-)，男，博士，主要从事无线网络、并行与分布式计算等方面的研究.