基于穷举搜索的无线Mesh网络分配信道可行性研究

张继成+羊秋玲

摘 要： 信道分配问题在多天线无线Mesh网络中已被各种文献证明是NP难问题。分析了一般的信道分配问题的复杂性与某些基本和常见的属性。结果表明，不同信道分配数量的复杂度和无线链路的数量呈指数关系。此外，估计了通过穷举搜索确定最优信道分配的理论运行时间，并通过实验验证。实验表明，给予一定的计算能力（如一个现成的笔记本电脑），在小规模和中等规模的商业无线Mesh网络中，对于最优解决信道分配问题是可行的。

关键词： 无线Mesh网络； 信道分配； 穷举搜索； 干扰最小化； 复杂度； 无线链路

中图分类号： TN929.5?34 文献标识码： A 文章编号： 1004?373X（2018）05?0014?06

Abstract： The channel assignment problem in multi?radio wireless Mesh networks （WMNs） is the NP?hard problem proved by various literatures. The complexity of the general channel assignment problem is analyzed， as well as a certain basic and common properties. The results show that the complexity of different possible channel assignment quantity has exponent relation to the wireless link quantity. Furthermore， the theoretical runtime of optimal channel assignment determined by exhaustive search was estimated， and verified with experiments. The experimental results show that， giving a certain computing power （notebook PC）， it is feasible to solve the optimal channel assignment problem in small?and medium?scale commercial WMNs.

Keywords： wireless Mesh network； channel assignment； exhaustive search； interference minimality； complexity； wireless link

0 引 言

作为一个非常有前途的无线宽带技术，无线Mesh网络被认为是WLAN热点区域最好的解决方案之一[1]。事实上，由于网络接口卡相对比较廉价，为了提高网络的吞吐量，越来越多的商业Mesh路由器在多个信道上配备多个天线。然而，可以利用的无线信道数量相对有限，因此，在商业多天线无线Mesh网络的设计和部署中，如何分配可利用的有限信道变得非常重要。

近年来，研究人员对无线Mesh网络信道分配问题产生了极大的研究兴趣，在文献中也提出了许多解决的方法，包括动态或者静态方法。文献[2]在无线Mesh网络中提出基于信道状态的动态信道分配算法。文献[3]提出基于演化博弈的抗振荡动态信道分配策略，动态方法需要在非常快的时间内进行信道切换，因此需要节点之间的同步合作。此外，大部分的动态方法还需要专门的MAC协议或者修改的802.11MAC层，因此，它们不适合在现存的硬件上使用。在靜态分配方法中，除非有重大的网络流量负载或者网络拓扑结构变化，算法永久的分配信道，同时也不考虑信道切换延迟和流量测量开销。除了动态、静态方法，文献[4?5]提出基于干扰感知的多接口无线Mesh网络信道分配算法，文献[6]提出一种流量感知和干扰优化的信道分配机制。

除了以上提供的解决方案，最近提出了许多联合优化解决方案[7?9]。相关工作提出信道分配和其他因素联合优化问题，比如和路由、拓扑控制、调度、拥塞控制、媒体访问控制（MAC）等的联合。

在本文中，研究在多天线无线Mesh网络中给链路静态分配不重叠的信道问题，在实际的商业网络中考虑通用性和可行性。研究基于穷举搜索最优化信道分配的复杂度，进一步找出在给定规模的商业无线Mesh网络中，以这种最简单的方法优化解决这类问题是否可行。

在相关工作中，一些特定的信道分配问题已经被证明是NP难问题。文献[10]对提出的信道分配问题通过减少多个子集和问题证明其是NP难问题。基于文献[10]的证据，文献[11]通过打破单一碰撞域使之成为更小的冲突域，表明定向信道分配也是NP难问题。

值得注意的是，一方面，所有特定的信道分配问题都被证明是NP难问题，因此，不能证明广义信道分配问题具有不同的目标或约束。另一方面，信道分配问题的NP难问题意味着在大规模WMNs中很难确定最优信道分配。出于这个原因，大部分研究聚焦在发展高效的近似算法上，而不是最优的，其可以提供质量好的信道分配，运行速度快。然而，在许多现有的小型和中型的商业WMNs中，在合适的时间确定最优的信道分配是可能的。关键问题是确定多大的网络规模是可行的。到目前为止，对于这个问题，相关研究人员已经提出了大量的信道分配方案，本文试图通过理论分析和仿真实验找出这个问题的答案，具体如下：

在多天线无线Mesh网络中，本文研究纯粹的信道分配问题的复杂性，而不是联合优化问题。根据理论分析结果，估计基于穷举搜索确定最优信道分配的理论运行时间。为优化解决相应的信道分配问题，设计三个穷举搜索算法并在实验中加以运行。通过比较理论运行时间和在实际场景中的实验结果，验证了理论估计时间。结论表明，给予一定的计算能力（如一个现成的笔记本电脑），在实际小规模和中等规模商业多天线无线Mesh网络中，决定最优信道分配问题是可行的。endprint

1 问题描述

在商业多天线无线Mesh网络中，通常路由器被配备多个无线网络接口，而且每个接口被分配不同的信道。从本质上讲，信道分配问题是给每个无线网络接口分配可用的无线信道，以最大化网络吞吐量。无线网络接口和无线链路都可以被认为是基本的信道分配单元，在本文分析中，考虑双向无线链路作为基本的信道分配单元。

无线Mesh网络中有两种类型的流量：客户及其相关mesh路由器之间的网络访问流量；mesh路由器之间的回程流量。本文只讨论回程通信的信道分配问题，因此只考虑回程链接。本文中，根据双向无线链路的数量，商业多天线无线Mesh网络的网络规模被归类为以下三种类型（其中用表示无线链路）：

小规模的多天线无线Mesh网络：

中等规模的多天线无线Mesh网络：

大规模的多天线无线Mesh网络：。

假设在回程无线Mesh网络中包含个无线路由器、个双向无线链路和个非重叠的信道。一般的信道分配问题（G?CAP）是为了优化某个目标给个不同的链路分配个不同的信道。实际上，在网络设计和部署的早期阶段，无线信道的链路质量是不确定或者未知的。因此，实际的信道分配问题（P?CAP）并没有考虑不同信道的链路质量。如果一个P?CAP的优化目标是通过最小化链路之间的总干扰来最大化网络的吞吐量，那么P?CAP被称为最小化干扰P?CAP（简称i?mP?CAP）。事实上，大多数优化目标相关的工作相当于等价转化为一个最小化总干扰问题。

此外，假设在给定的信道分配（CA），在中计算目标函数的值需要多项式时间。因此信道分配问题的复杂性由许多不同的信道分配所决定，用来表示。

2 复杂度分析

2.1 一般的信道分配问题（G?CAP）

给定个不同的链路和个不同的信道，对于第（2，…，）个链路，它被分配个信道中的一个。一旦每条链路被分配一个信道，则构建了一个不同的信道分配方案CA，这个信道是彼此不同的，对于每个链路都有次机会，因此：

2.2 实际的信道分配问题（P?CAP）

如前所述，在P?CAP中，不考虑不同信道链路之间的区别，定义相同的信道如下：

定义1：不同频率的不同信道是相同的，当且仅当这些信道的链路质量被认为是相同的。

因此，在P?CAP中，所有可利用的信道是等价的；在G?CAP中，不同的信道分配例子在P?CAP某种情况下能变得相同。表1给出了两种等价的信道分配方案的例子，给定4个不同的链路有3个信道CH1，CH2，CH3。CA1和CA2在P?CAP中是相同的，而在G?CAP中却是不同的。

给定个不同的链路和个等价的信道，不同的信道分配方案数量可以由组合得出。将个不同的链路看做一组个元素，将个等价的信道看做是个无法区分的盒子，则P?CAP变成一个区分问题，即如何把个元素放到个盒子里，要求不允许有空盒子。因此，不同的信道分配方案数量就等于区分的数量。

在P?CAP中，不同的信道分配数量可以表示如下：

2.3 干扰最小化信道分配P?CAP（i?mP?CAP）

在i?mP?CAP中，能够获得比（Nca）P?CAP更少的不同信道分配数量。详细的分析和推导如下：

引理1：给定个不同的链路和个等价的信道，对于任何一个信道分配CA使用个不同的信道比使用个信道能够获得更好的性能。

证明：设是个不同的链路，是个等价但不同的信道。对于任何一个信道分配CA，使用个不同的信道记为个链路的组成可以记为它可以被分割為个不相交的子集如下：

第链路子集相对应于一个不同的信道。换句话说，链路在同样的子集被分配同样的信道对于任意的根据式（3）中对的定义和引理1中提供的条件，得出：

根据式（7）得，比小，因此，通过鸽巢原理，至少有一个子集拥有至少两条链路。为了不失一般性，定义是这个子集，被描述如下：

其中是链路子集的大小。

随机选择一个链路记为从中形成另外一个链路子集（注意改变的记为）。分配一个没有使用的信道给中的使用个不同的信道构造一个新的信道分配CA记为在中，链路集合被分割为个不相交的子集如下：

在这里和不同的信道相对应，在形成的个链路子集中没有使用。

因此，在和中惟一的区别是信道分配给在中，在中，由于引入没有被使用的信道中减少了中的和中的所有链路之间的干扰，而这些链路在中共享信道作为中的元素。与此同时，其他链路子集的链路在中除了仍然保持不变的性能，因此能实现比更好的性能。

关于引理1及其证明，以下两点值得注意：对于不同的信道，如果考虑不同的链路质量，对于能实现比更好的性能是不确定的；当一个新的信道被引入，尽管它可以减少干扰，这个新信道的链路质量比原来的更糟糕，在子集和整个网络中，不能实现更好的总体性能。因此，对于引理1必须具备所有的信道是等价的这个前提。换句话说，虽然它适合i?mP?CAP信道分配，但它对G?CAP是不确定的。

如果优化目标不是等价的，或者不能等价转化为最小化总的干扰，对于引理1是不确定的。换句话说，虽然它适合i?mP?CAP信道分配，但它对P?CAP也是不确定的。

基于引理1，则有以下定理：

定理1：给定个不同的链路和个等价的信道，最优的信道分配CA必须使用个不同的信道。

证明：在式（2）中给出不同的信道分配方案数量对于第（k=1，2，…，）个信道分配CA，个不同的信道被分配给个链路。如果认为最优的信道分配CA，记为CAC，它使用个不同的信道，而比小，通过引理1，CA使用个不同的信道能实现更好的性能，因此CAC不是最优的。假设最优的信道分配CA已经使用个不同的信道，通过引理1和式（3）中对的定义，在i?mP?CAP中，不同的信道分配的数量为：endprint

2.4 复杂度比较

不同信道分配的数量复杂度总结如表2所示。其中和由式（4）决定。假设有3个正交信道可供分配，表3中给出了一个算例复杂性。

如表2和表3所示，信道分配方案的复杂度随着无线链路数量的增加而增大，此外，当无线链路的数量变得更大时，信道分配的复杂性在P?CAP和i?mP?CAP中的值比G?CAP小得多。

3 理论运行时间

在本节中，首先给出基于穷举搜索的最优信道分配CA估算公式的理论运行时间。然后在实际场景中提出一个例子，给出特定的评估结果。

3.1 理论估计

在估计最优信道分配CA的运行时间之前制定一个信道分配问题的优化目标是很有必要的。根据对G?CAP和P?CAP的定义，它们在优化目标上都没有限制，因此采用i?mP?CAP，它认为优化目标是最小化链路之间的总干扰。

对应一个给定的信道分配CA，对于个链路中的每一个，计算和其他链路之间的干扰来确定相关信道分配CA的总干扰。对于每一个链路是等价的，为干扰链路的上限数量。另一方面，设为计算两条链路之间干扰度的时间，考虑到计算能力，是一个常数，可以由测试得出。因此，在本文中常数反映了给定的计算能力。对于一个信道分配CA，计算目标函数的时间成本由给出，它是一个的二次多项式函数，记为，所以认为一个信道分配CA的运行时间是。

此外，本文发现最优信道分配CA是所有的信道分配中基于穷举搜索的，因此，通过第2节对的定义（见表2），对于先前提到的信道分配问题，确定最优的信道分配CA的理论运行时间为：

3.2 评估结果

例如，考虑一个实际的场景，在该场景中，在一个现成的惠普笔记本电脑上计算最优的信道分配CA，笔记本的相关系统配置信息如下：处理器：英特尔酷睿双核T2300E（1.66 GHz，667 MHz FSB 2 MB L2高速缓存）；内存：2×512 Mb DDR2 SDRAM。

是计算两个链路之间干扰的实时时间成本。运行100 000次之后得到的平均值为1.7。与此同时，假设3个正交信道可供分配，的值为3，这种假设是合理的。根据IEEE 802.11标准，在802.11b/g带宽中有3个正交信道，因此，式（11）可以写成：

基于式（12），给出理论运行时间和无线链路数量的关系如图1所示。

从图1中可以看到，一方面，通过穷举搜索计算最优信道分配CA的运行时间随着链路的增加呈指数型增长。另一方面，对于增加同样数量的链路数，在G?CAP信道分配中运行的时间比在P?CAP和i?mP?CAP中更多一些，而在i?mP?CAP中信道分配运行的时间在同样数量的链路下比P?CAP要更少一些。

4 实验和可行性讨论

4.1 实验验证

除了在第3节提到的主要因素尽管核心算法是相同的（比如穷举搜索），在实际中确定最优信道分配CA的真正运行时间也会受到软件设计细节的影响。与此同时，理论估计不可能考虑到所有软件设计的细节。因此，在实际场景中依靠实验来验证在第3节提到的理论结果是非常有必要的。

对于多天线多信道无线Mesh网络，基于信道分配工具CAT，设计了三种穷举搜索算法来解决三种相应的信道分配问题：G?CAP，P?CAP，i?mP?CAP。最优信道分配CA的最优性能在先前的工作中被CAT验证，在本节中，关注对以上三种算法使用CAT工具在三种信道分配问题上确定最优信道分配CA的真正运行时间，和实验时间相比，验证了理论估计结果。

在这个实验的实际场景中，和3.2节中的例子一样，具体来说，在同样的惠普笔记本上运行软件CAT，此外，可以利用的正交信道数量也设置为3。对于优化解决先前提到的信道分配问题，运行CAT以后，则记录了真实的實验运行时间，实验运行时间和双向无线链路数量的大小关系如图2所示。

通过图1和图2中理论运行时间和实验结果的比较，得出以下结论：在以上三种信道分配问题上，理论结果和实验结果在运行时间的走势上是相同的，都为单独考虑每个问题，理论运行时间和实验结果彼此接近；随着网络规模的增长，运行时间的增量趋势在理论和实验结果上是一致的。因此，通过在实际场景中的实验，在信道分配问题上验证了理论估计运行时间来确定最优信道分配CA 。

4.2 可行性讨论

根据上述分析和验证，显示当无线链路增加时，最优解决G?CAP的运行时间比P?CAP和i?mP?CAP增加得更快一些。对于提到的所有信道分配问题，由于采用了穷举搜索算法，即使网络的规模不是很大，在实际中运行时间仍然会很久。因此，在大规模无线Mesh网络中，近似算法对信道分配问题是不可或缺的。

然而，本文也表明给定一定的计算能力（如现成的笔记本电脑），在商业小规模和中等规模的无线Mesh网络中，通过穷举搜索确定最优信道分配CA是可行的。以4.1节中所描述的实验为例，当无线链路的数量小于20时，在P?CAP和i?mP?CAP中的运行时间成本在实践中是可以接受的。这里的无线链路被认为是最基本的信道分配单元，由于信道依赖共享Mesh路由器公共接口的链路，而在实际的无线Mesh网络中，真正的信道分配单元通常包括若干个无线链路。真正的信道分配单元要比无线链路的数量要少，给定在第3节描述的一个笔记本配置的计算能力，在商业中等规模的无线Mesh网络中，只要信道分配单元的数量少于20，通过穷举搜索确定最优信道分配CA是可行的。

对于商业小规模和中等规模的无线Mesh网络，没有必要设计近似算法提供给非优化的信道分配CA。给定一定的计算能力和网络信息，根据文中提出的理论估计方法，能够提供一个有用的判断。

5 结 语

本文研究了商业多天线无线Mesh网络中三种类型的信道分配问题的复杂性。根据分析结果，通过穷举搜索，估计确定最优信道分配的理论运行时间，然后在实际场景中通过实验验证。结果表明，给定一定的计算能力，在实际的小型和中型多天线无线Mesh网络中，优化解决信道分配问题是可行的，而近似算法在大规模Mesh网络中是不可或缺的。最后，在商业无线Mesh网络中提出公开的基本信道分配问题，并为算法设计和网络规划提供指导意义。endprint

参考文献

[1] AKYILDIZ I F， WANG X， WANG W. Wireless mesh networks： a survey [J]. Computer networks & ISDN systems， 2005， 47（3）： 445?487.

[2] 夏汉铸，刘辉元.无线Mesh网络中基于信道状态的动态信道分配算法研究[J].重庆邮电大学学报（自然科学版），2014，26（3）：362?366.

XIA Hanzhu， LIU Huiyuan. Channel?state?based dynamic channel assignment algorithm in multichannel wireless Mesh networks [J]. Journal of Chongqing University of Posts and Telecommunications （natural science edition）， 2014， 26（3）： 362?366.

[3] 乐光学，李明明，丁辉，等.无线 Mesh网络中基于演化博弈的抗振荡信道分配策略[J].电子学报，2016，44（1）：176?185.

YUE Guangxue， LI Mingming， DING Hui， et al. The anti?channel oscillation channel assignment scheme based on evolutionary game in wireless Mesh network [J]. Acta electronica sinica， 2016， 44（1）： 176?185.

[4] 王子凡，刘作学，代健美.基于干扰感知的多接口无线Mesh网络信道分配算法[J].现代电子技术，2014，37（14）：24?27.

WANG Zifan， LIU Zuoxue， DAI Jianmei. Interference?aware based channel assignment algorithm for multi?interface wireless Mesh networks [J]. Modern electronics technique， 2014， 37（14）： 24?27.

[5] 张伟昆，黄炜，张大伟.基于连接低干扰的无线Mesh网络信道分配算法研究[J].电子科技大学学报，2014，43（6）：817?822.

ZHANG Weikun，HUANG Wei， ZHANG Dawei. A study of wireless Mesh networks based on connected low interference channel assignment algorithm [J]. Journal of University of Electronic Science and Technology of China， 2014， 43（6）： 817?822.

[6] 张绳武，曾锋，陈志刚.无线Mesh网中一种流量感知和干扰优化的信道分配机制[J].计算机应用研究，2016，33（3）：810?812.

ZHANG Shengwu， ZENG Feng， CHEN Zhigang. Traffic?aware and interference optimized channel assignment mechanism in wireless Mesh network [J]. Application research of computers， 2016， 33（3）： 810?812.

[7] WU Di， YANG S H， BAO Lichun， et al. Joint multi?radio multi?channel assignment， scheduling， and routing in wireless mesh networks [J]. Wireless networks， 2014， 20（1）： 11?24.

[8] ULUCINAR A R， KORPEOGLU I. Distributed joint flow?radio and channel assignment using partially overlapping channels in multi?radio wireless mesh networks [J]. Wireless networks， 2016， 22（1）： 83?104.

[9] CHENG Hongju， XIONG Naixue， CHEN G， et al. Links organization for channel assignment in multi?radio wireless mesh networks [J]. Multimedia tools & applications， 2013， 65（2）： 239?258.

[10] RANIWALA A， GOPALAN K， CHIUEH T. Centralized channel assignment and routing algorithms for multi?channel wireless mesh networks [J]. ACM mobile computing and communications review， 2004， 8（2）： 50?65.

[11] DAS S M， PUCHA H， KOUTSONIKOLAS D， et al. DMesh： incorporating practical directional antennas in multi?channel wireless mesh networks [J]. IEEE journal on selected areas in communications， 2006， 24（11）： 2028?2039.endprint