无线Mesh网络中的信道分配研究

廖龙龙

摘要：无线Mesh网络是广播网络的一种特殊方式，它结合了WLAN网络和ad hoc网络的优点，网络通过跳跃通信和相对降低基础设施在电线和硬件方面的成本来提供与因特网最后一英里的连接。信道分配方案是提高无线Mesh網络容量的主要途径。随着用户数量的增加，网状网络对信道资源的公平利用一直是一个挑战。合理利用多信道和节点的多接口，不仅增加了网络的总吞吐量和可扩展性，而且为信道分配方法带来了新的曙光。针对现有信道分配方案进行了详细讨论。

关键词：无线Mesh网络；多接口；多信道；信道分配；网络容量

中图分类号：TN915.01 文献标识码：A 文章编号：1009-3044（2017）27-0024-04

Abstract： The wireless Mesh network is a special way of broadcasting networks that combines the advantages of WLAN networks and ad hoc networks that provide connectivity to the last mile of the Internet by jumping communications and relatively reducing the cost of infrastructure in terms of wire and hardware. Channel allocation scheme is the main way to improve the capacity of wireless Mesh network. With the increase in the number of users， the mesh network on the fair use of channel resources has been a challenge. Reasonable use of multi-channel and multi-interface nodes， not only increased the total network throughput and scalability， but also for the channel allocation method has brought a new shine. The existing channel allocation scheme is discussed in detail.

Key words： wireless mesh networks；multi-radio；multi-Channel；channel allocation；network capacity

1 概述

无线Mesh网络（WMN）是一种重要的技术，涵盖了几乎各行各业，具有诸如灾难恢复服务，交叉点安全摄像机，连接多个热点，校园网络，战场等孤立的地区[1-2]。WMN是提供最后一英里连接的经典有线骨干网技术的架构转变[3]，它具有易于部署、可靠性、可扩展性、可用性、良好吞吐量和低成本的特性。

无线Mesh网络具有多跳、自组织和自我修复等特性，其中节点互连形成网格。虽然只有少数节点通过最后一公里网关连接到互联网，但是这种业务形式和其他类似的业务可以扩展到整个网络。可以把其认为是融合网络的一种类型，其结合了有线和无线网络部署的技术，是临时和基础设施模式网络。

图1为典型的无线Mesh网络架构，主要由Mesh客户端、Mesh路由器和网关组成。客户端是静态/移动节点，如计算机和笔记本电脑，也可以充当路由器，将其他客户端的数据传送到网关或从网关传输。路由器作为客户端和网关之间的中介，网关具有和外部互联网相连的功能。与经典路由器相比，网状路由器只需要较低的传输功率，因为它们只要将数据包转发到临近的路由器即可。

在传统的单频单信道无线Mesh网络中，因为无线信道的传输特性，在节点的干扰范围内同信道的链路之间会相互干扰，不能同时进行数据的传输，因此会降低网络的容量。然而在多射频环境下的WMN，信道分配的目的是确保良好的网络连接，同时有效地提高信道利用率。虽然不同的物理层标准如802.11a/b/g/n提供了多个正交可用信道，但是网络中存在着节点的接口约束，流量不均衡等各种不确定因素，所以在考虑网络场景的同时，如何为网络中的链路分配信道从而最大化网络容量一直是研究信道分配算法的目标。无线Mesh网络信道分配问题类似于图着色问题，已被证明是一个NP-hard问题[4]。因此，信道分配机制应采用启发式算法来完成信道分配。根据节点的射频接口上信道的切换频率可以将信道分配方案主要划分为3种类型[5]：静态信道分配（Fixed Channel Assignment）、动态信道分配（Dynamic Channel Assignment）和混合信道分配（Hybird Channel Assignment）。

2 静态信道分配

在静态信道分配里，每个Mesh路由器中的每个接口被长时间固定的分配一个信道。 静态信道分配的目标是最大化整体网络性能。大多数工作仅在信道分配中考虑正交信道。不同正交信道上的无线链路可以始终在没有干扰的情况下同时工作。

文献[6]中提出了CCA信道分配方案，该方案将Mesh路由器分列成簇，在CCA中信道分配取决于簇中节点的数量，信道的重新分配取决于簇集间的距离。网络中至少应该存在两个簇。C表示网络中所有簇的集合：[C={C1，C2，C3，…，Cn}]。

网络中邻居节点最多的节点被选为簇头节点，它根据本簇集中的拓扑信息来执行CCA信道分配方案。CCA信道分配主要为三步：

（1） 初始信道的划分endprint

（2） 邻居簇集的选择

（3） 信道的重分配

为了让两个邻域簇集合获得不相交的信道集，网络中的所有可用信道均匀分布在簇集中，刚开始，簇头节点为该簇中的所有节点分配单个公共信道，而且边界节点也采用该信道来和邻域簇进行通信。然后簇头节点再将剩余的信道分配给为分配信道的节点。

CCA信道分配的主要局限在于信道没有充分的被利用，而且该方案没有考虑每条链路的负载，这将导致链路之间的干扰。

文献[7]中提出一种针对网络中拥塞和传输干扰算法，该算法是基于节点优先级策略的静态信道分配（NPFCA）方案，在该方案中将网络中的所有节点按照距离网关节点的跳数进行分级。根据节点优先级和其邻居节点数，通过计算链路两端节点各自邻居节点数与节点优先级之比的和得到对应链路的负载权重，然后根据链路的负载权重来给链路分配相应的信道。由于信道分配问题是一个NP问题，所以该方案采用了离散粒子群优化算法来求解。该方案能够在一定程度上减少网络中的干扰，从而有效提高网络中的容量。

文献[8]中提出了一种差异信道分配算法（VCA），此算法给不同节点的无线射频接口分配不同的信道，减少了网络中的同信道干扰，因为所有接口的信道是固定的，所以其降低了网络的连通性。

文献[9]给出了一种集中式信道分配算法（C-HYA），该算法认为所有网络中的流量来于互联网，假设已知网络流量负载，以此计算出每条链路的流量负载，按照假设的节点优先级从高到低访问节点，按贪婪的方法给节点分配信道，也就是说具有优先级高的节点分配性能好的信道。算法以Hyacinth架构为基础，认为所有网络中的流量都是流向互联网或来自互联网，节点的流量负载已知，C-HYA算法通过公式（1）计算网络中每条链路的流量负载之和，估计每条虚拟链路的预期流量负载。

其中s表示源节点，d表示目的节点，[Ρ（s，d）]表示节点对[（s，d）]之间可以进行通信的链路数，[Ρι（s，d）]表示节点对[（s，d）]之间能够进行通信的路径中经过链路l的路径数量，[Β（s，d）]表示节点对（s，d）之间的评估负载，[Γι]表示链路L上的预期流量负载。通过比较链路预估流量负载为对应的链路选取信道，为预估链路流量负载重的选取带宽比较大的信道，预期流量负载轻的链路选取带宽比较小的信道。C-HYA算法输入参数是初始预估链路流量的负载，然后通过使用多次迭代的方式来进行信道分配方案的计算，直到分配给网络中的所有链路带宽都满足预估的流量负载需求。该信道分配算法虽然降低了网络中的链路干扰，提升了网络的容量，但其易发生波纹效应现象，即当网络中的某条已分配信道的链路发生改变时，会对其他已分配了信道的链路产生影响，导致剩余的链路为了保证网络的连通也需要跟着改变其所分配的信道来避免网络分割现象。

在文献[10]中，作者提出了一种线性规划的方法，将优化网络中的链路干扰作为最终目标，以此来减少整个网络中的干扰权重。

从此可以看出，静态信道分配方案主要是通过理论分析和系统建模的方法，给拓扑结构稳定和固定业务模式的WMN提供解决方案。静态信道分配方案在WMN部署与业务分配等方面有着重要的参考意义。

3 动态信道分配

动态信道分配方案与静态信道方案的最大区别是，节点的无线射频接口可以动态的从一条信道上切换到另外一条信道上，而不是固定的使用一条信道。动态信道分配面临两个挑战。（1）目前的文献显示，一个信道切换到另一个信道的切换延迟是不能忽略的。对于相同频带内的频道切换（2.4GHz上的802.11b/g或5GHz上的802.11a），延迟显示为[11]中的几毫秒到几毫秒。对于不同频段的信道切换，延迟预计会大得多[12]。现在主流的基于IEEE802.11的商业硬件很难满足这种要求[13]。而且，大多数动态信道分配方案需要对MAC层进行特定的修改，这对于IEEE802.11硬件是种巨大的挑战。（2）接口之间需要协调机制。当两个接口想要相互通信时，它们必须切换到同一个通道。因此，需要一些同步或控制协议来使得接口能够协商公共信道并同时切换到信道。

为了充分利用多信道的优点，在文献[14]定义了一种新的MAC协议MMAC（Multi-channel MAC），但是该方法存在着切换时间长、时间同步比较复杂，而且其引入了更多的暴露终端。

D-HYA算法[15]是按照网络中流量负载的变化，已实现网络的负载均衡、降低网络中的干扰链路，从而提升网络的整体容量的一种分布式动态信道方案。在算法中以网关节点作为根节点构建网络的树形结构，给每个节点都划分优先级，越接近网关的节点优先级越高。

DCA算法是一种经典的动态信道分配算法[16]，算法通过给每个网络中的节点分配一个控制信道和多个数据信道，其中所有的信道都具有相同的带宽。控制信道主要解决信道冲突问题，数据信道用来进行数据的传输。每个网络中的节点都配有半双工收发器两个，一个控制收发器和一个数据收发器。网络中节点间的信息交互和数据信道接入的权限通过控制收发器控制信道来完成，数据的传输主要是通过数据收发器动态切换数据信道完成。

在DCA算法中，网络中的所有节点都需要维护CUL表和FCL表的信息。CUL是用来记录信道使用信息的表，在表中每条CUL[i]信息记录了i的邻居节点信息与它自己的信息，里面有三个域，CUL[i].host表示节点i邻居节点的编号，CUL[i].ch表示域CUL[i].host中節点使用的信道编号，CUL[i].rel_time表示域CUL[i].ch中信道释放的时间。通过实时动态的更新节点的CUL表信息，而空闲信道表FCL的信息可以通过CUL表信息计算出来。

DCA算法的主要步骤为：若网络中的节点A想要与另一节点B进行通信，首先节点A需要向节点B发送请求服务消息，该消息中包含了节点A的FCL表信息。其次节点B在收到节点A请求的信息后，通过比较自己的FCL表信息和请求信息中的FCL表信息，找到空闲的数据信道，最后给节点A返回响应消息，节点A在收到响应信息后，通过数据信道与节点B进行数据的传输，同时给其邻居节点广播该信道被占用的消息，禁止邻居节点在使用该信道。所有数据交互的过程都是经过控制信道完成的。DCA作为相对简单的一种动态信道分配方案，其提高了数据的传输速率与网络的吞吐量，由于其需要使用专门的一个控制信道用以对数据信道的分析和选取，因此其降低了信道的利用率。endprint

文献[17]中给出了一种将时间进行分片的SSCH（Slotted Seeded Channel Hopping）新协议，其可以让无线射频接口在空闲信道之间进行切换，并可以让节点之间达成偏序同步，用以提升传输的速率。但是SSCH只对单无线射频接口支持，而且它对全网时钟同步有一定的要求。

文献[18]中给出了一种基于网络流量与干扰感知的动态信道分配方案，根据节点的流量、节点与网关的距离和节点的接口数量来计算节点的优先级，然后使用时间贪婪启发式算法给节点进行信道分配。

在文献[19]中，作者通过考虑拓扑控制和信道分配这两个方面，用拓扑控制解决信道独立性问题，用信道分配解决信道干扰问题。

大多数的动态信道分配方案都要求无线射频接口在极短时间内实现信道之间的切换，因为只有无线射频接口的信道切换时延越小，新协议才能够充分发挥性能。目前的无线射频接口硬件设备的信道切换时延在实际应用中还是比较大的，无法完美满足此类要求。

4 混合信道分配

混合信道分配方案是静态和动态信道分配方案的组成，方案中将节点的一部分接口使用静态信道分配方案，其他的射频接口则使用动态信道分配方案，能够依据实时需求动态的切换信道。混合信道分配方案既具有确保网络连通性的静态信道分配方案优势，又能够像动态信道分配方案一样，根据网络实时负载和链路干扰情况，进行合理的信道分配，最小化局部干扰链路，提高网络的整体容量。

混合多信道协议（Hybrid Multi-Channel Protocol，HMCP）[20-21]是一种主要针对多射频接口的链路层多信道协议对于每个节点，一些接口分配固定信道，而其余接口可以频繁切换通道。每个节点通过在所有信道上向其邻居广播消息来向其邻居通知其固定信道。假如一个节点需要想邻居发送数据包，首先它通过一个可切换的射频接口切换到与其邻居固定接口上的一个信道，之后通过这个可切换接口进行数据包的发送。图2为一个例子，其中每个节点都有一个固定接口和一个可切换接口。固定接口分配固定信道。A可以通过将可切换接口切换到信道2来将数据传输到B，B可以通过将可切换接口切换到信道3来将数据传输到C。尽管这种方法会导致信道切换开销，并且具有简单的控制，延迟数据传输，因为每跳的数据传输需要信道切换。

文献[22]中Ding等提出了ADCA协议。它考虑了混合无线架构，并使用hyacinth架构来支持MC和多接口的仿真。主要针对网络中的吞吐量和延迟问题。在混合架构中，节点的一些接口可以进行信道切换，其他接口使用静态信道分配。使用静态信道分配方案的接口有助于最大化从终端用户到网关节点的吞吐量。而使用动态信道方案的接口则增加了网络的连接，并可以帮助网络适应不同的业务需求。ADCA将时间分成固定长度间隔：[T=Tc+Td]，其中[Tc]和[Td]分别表示控制间隔和数据间隔。在控制间隔中，所有节点使用相同的默认信道。数据发送和接收在数据间隔期间完成。在数据传输过程中，动态接口选取邻居节点并进行信道的协商。它维护链路层中的邻居队列长度，并根据队列长度和队列等待时间选择邻居。该协议使用队列阈值（[QT]）来确定信道协商过程是否应该继续。队列长度大于阈值会导致流量负载饱和。ADCA协议中的业务负载有阈值。当业务流量超过阈值时，网络面临相当大的延迟。

广度优先搜索信道分配算法[23]是一个集中式的基于干扰避免的信道分配算法，其目的是最小化干扰的影响来提升WMNs骨干网的容量。通过对冲突图的概念进行扩展，BFS-CA算法提出了一种多射频冲突图（Multi-radio Conflict Graph，MGC）的概念。在MCG中，顶点代表的是节点每个接口之间的链路，而不再是Mesh节点之间的链路。在算法中给节点的一个接口分配默认的静态信道，节点的剩余接口分配非默认信道。BFS-CA算法按照从多射频冲突图中获取的干扰射频接口数量信息来计算带宽与干扰，然而仅仅根据无線射频接口的干扰数量并不能准确反映出接口的干扰情况，应该同时考虑到干扰射频接口的流量大小。在两个信道间无线干扰射频接口数量一样的情况下，若其中一条信道经常被使用，而另外一条信道使用频率较低，则显然第一条信道的干扰情况更严重。所以每个节点都会给信道划分两个独立的等级，第一级是依据干扰射频接口的数量给信道分级，第二级是通过信道的利用率给信道分级，最后通过将两种等级综合考虑求得最终的信道等级信息。首先网络按照信道等级信息将默认信道分配给节点，然后按照多射频冲突图的信息给节点分配非默认信道。

BFS-CA算法全面考虑了信道带宽和干扰的问题，通过分配默认静态信道防止了默认的信道切换导致的数据流中断问题，由于需要节点周期性获得干扰射频数量与信道使用状况信息，从而导致了射频接口的利用率降低。

文献[24]中给出了一种结合静态和动态信道分配特点的混合多信道多接口无线Mesh网络架构。在这种架构中网络中的每个节点的其中一个接口都能够频繁的进行信道的切换，而其他接口则在固定的信道上工作。包括网关的大多数节点具有3个接口，并且几个边界节点（c，g，i，f）具有2个接口。相邻节点的静态接口如果在相同的固定信道上工作，则构建静态链路（无信道切换）。静态接口的信道分配旨在最大化从终端用户到网关的网络吞吐量，这通常构成网络中流量的主要部分。如图4所示，通过静态接口上的信道分配构建了树形拓扑，从而最大限度地提高了最终用户的吞吐量。动态接口以按需方式工作。在节点的传输范围内的两个动态接口能够在需要传输数据时切换到相同的信道进行通信。图3说明了所有可能的动态链接。所提出的架构不仅通过静态链路确保高质量的路径，而且还改善了网络的连接性和适应性，以改变动态链路的交换。此外，它还降低了信道的切换开销。

与动态信道分配方法相比，混合信道分配方式降低了信道交换开销，并且与静态信道分配方法相比，保持了对变化的流量的良好适应性。当节点上可以使用的无线射频接口较少时，混合信道分配方式会导致信道资源的浪费。因为其要将为数不多的可用无线接口中，分出一部分以维持网络拓扑结构。endprint

5 结论和未来研究方向

静态信道分配方案通常具有较低的信道切换开销，动态信道分配方案更适应于变化的流量，而混合信道分配方案则结合了这两种信道分配方案的优点。由于信道分配问题是一个NP-hard问题，所以绝大部分信道分配方案都是采用启发式的方法。

静态信道分配方案不需要接口进行信道的切换，因此开销较低。然而，它们依赖于稳定的网络流量模式。虽然动态信道分配方案具有较高的信道切换开销，但当网络流量频繁变化时，它们更为合适。在静态信道分配中，通常考虑MAC层和路由层之间的跨层问题，而在动态信道分配中，关键问题是如何协调信道同步问题和信道切换问题。大部分的静态信道分配方案都使用集中式的方法，而大部分动态信道分配方案都使用分布式的方法。

由于静态和动态信道分配方案的优点和缺点，最好考虑混合信道分配方案，其中每个Mesh路由器都具有静态和动态接口。该架构可以降低信道切换开销，同时使信道分配适应不断变化的环境。 有几个难点在这个领域值得深入的研究，例如如何协调静态和动态接口的信道分配，以及如何确定每个流量的负载，从而达到信道的最佳性能。

信道分配中面临的一个挑战问题是无线信道没有充分的利用，大多数以前的研究只考虑了不重叠的信道。由于部分重叠信道的干扰模型比正交信道更为复杂，因此在信道分配算法的设计中增加了更多的复杂性。由于使用多接口多信道能够极大提升网络的容量，所以可以设想，将来越来越多实时应用，将在无线Mesh网络中流行。如何确保延迟敏感和高比特率流量的服务质量，找出适当的路由和信道分配是一个具有挑战性的问题。

参考文献：

[1] M. Portmann and A. A. Pirzada.Wireless mesh networks for public safety and crisis management applications[J]. IEEE Internet Computing， 2008，12（1）：18-25.

[2] S. Avallone， I.F. Akyildiz.A Channel Assignment Algorithm for Multi-Radio Wireless Mesh Networks[C]. Proc of 16th Int. Conf. on Computer Communications and Networks，2007： 1034-1039.

[3] K. N. Ramachandran， E. M. Belding， K. C. Almeroth， M. M. Buddhikot.Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks[C]. Proc. of 25th IEEE Int. Conf. on Computer Communications， 2006： 1-12.

[4] Raniwala A， Gopalan K， Chiueh T. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2004， 8（2）：50-65.

[5] Wireless Mesh networking： architectures， protocols and standards[M]. CRC Press， 2006.

[6] S.A. Makram，and M.Gunes.Channel assignment for multi-radio wireless mesh networks using clustering[C].Proceedings of the 2008 International Conference on Telecommunications，IEEE，June 2008：1-6.

[7] 張劼，钟朗等.基于节点优先级的无线Mesh网络资源分配[J].电子科技大学学报，2016，01：54-49.

[8] 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.

[9] Raniwala A， Gopalan K， Chiuen T. Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2004， 8（2）：50-65.

[10] 彭利民，刘浩.多信道无线Mesh网络信道分配算法[J].计算机应用，2009，29（7）：1849-1851.

[11] R. Chandra， P. Bahl， P. Bahl， Multinet： connecting to multiple ieee 802.11 networks using a single wireless card， in： INFOCOM， 2004.endprint

[12] P. Kyasanur， N. Vaidya， Routing and interface assignment in multi-channel multi-interface wireless networks， in： WCNC， 2005. （下轉第43页）

（上接第27页）

[13] A. Raniwala， T. Chiueh， Architecture and algorithms for an ieee 802.11-based multi-channel wireless mesh network， in： INFOCOM， 2005.

[14] J. So，N.H. Vaiday. Multi-Channel MAC for Ad Hoc Networks： Handling Multi-Channel Hidden Terminals Using A Single Transceiver. Proc. of ACM MobiHoc，2004：222-233.

[15] 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.

[16] Wu S L， Lin C Y， Tseng Y C， etal. A new multi-channel MAC protocol with on-demand channel assignment for multi-hop mobile ad hoc networks[C]. International Symposium on Parallel Architectures，Algorithms and Networks， 2000：232-237.

[17] P. Bahl， R. Chandra， J. Dunagan. SSCH： Slotted seeded channel hopping for capacity improvement in IEEE 802.11 adhoc wireless networks[C]. Proc. Of ACM MobiCom， 2004：216-230.

[18] Subramanian A， Gupta H， Das S R. Minimum interference channel assignment in multi-radio wireless mesh networks[J]. IEEE Transactions on Mobile Computing， 2008， 7（12）：1459-1473.

[19] Rad A H， Wong V W. Logical topology design and interface assignment for multi-channel wireless mesh networks[C]. IEEE Global Telecommunications Conference， 2006：1-6.

[20] Kyasanur P， Vaidya N H. Routing andinterface assignment in multi-channel multi-interface wireless networks[C].Wireless Communications and Networking Conference， 2005 IEEE.IEEE， 2005， 4： 2051-2056.

[21] P Kyasanur P， Vaidya N H. Routing and link-layer protocols for multi-channel multi-interface ad hoc wireless networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review， 2006， 10（1）：31- 43.

[22] Y. Ding， K. Pongaliur， L. Xiao， and S. Member.Channel allocation and routing in hybrid multichannel multiradio wireless mesh networks[J].IEEE Trans. Mobile Compute， 2013， 12： 206-218.

[23] Ramachandran K N， Belding E M， Almeroth K C， et al. Interference-aware channel assignment in multi-radio wireless mesh networks[C].IEEE INFOCOM. 2006， 6： 1-12.

[24] Y. Ding， K. Pongaliur， L. Xiao， Hybrid multi-channel multi-radio wireless mesh networks， in： IWQoS， 2009.endprint