无线mesh网络中基于拓扑分层的多信道分配算法研究

肖伟　王丽文

摘要：无线Mesh网络是具有多跳、自组织、自愈合和高健壮性等特点的宽带网络。因为结点信号之间存在干扰及频谱资源的有限性，如何通过频谱分配来提升网络效率成为Mesh网络研究的重要方向。该文给出一种多信道分配算法，目的在于改善无线mesh网络可用信道频率的综合效率，基础在于网络结构按拓扑进行结构分层。该算法首先进行分层设计，然后在拓扑分层的基础上根据信道的优先级分配信道，达到频率资源的有效分配的目标。仿真实验说明该算法能有效地提高无线网络整体性能。

关键词：无线mesh网络；信道分配；拓扑分层

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）29-6839-03

Abstract： Wireless Mesh Network is the broadband wireless Networks with multi-hop， self-organization， self-healing， high robustness and other characteristics. Due to the limited spectrum resources and the signal transmission between nodes interfere with each other， how to distibute spectrum scope and increase the transmission performance becomes an important orientation in the Mesh network. for increasing the combined efficiency in wireless mesh network based on the available channels frequency utilization， this paper presents a novel algorithm based on topology hierarchy. Firstly， this algorithm realize the hierarchical topology， and then layered on the basis of the topology depend on the priority of the channels to assign channels. Simulation consequence indicates that the whole performance in Mesh networks would be improved using the algorithm.

Key words： wireless mesh networks； channel assignment； topology hierarchical

无线Mesh网络[1，2]是一种在无线局域网的基础上发展起来的，具有自组织、自愈合和高健壮性等优点的新型宽带无线网络结构。无线 Mesh 网络技术采用多点到多点通信的网络拓扑结构，支持多种类型的网络接入，被认为是未来无线通信发展的关键技术。

在无线Mesh网络中，频率通道选择、功率控制和无线路由等将直接影响系统设备的传输能力和无线链路质量等Qos性能。为了适应无线Mesh网络对传输性能的要求，近年来提出多射频多信道（Multi-Radio Multi-Channel，MRMC）[3，4]技术应用到无线 Mesh 网络中，形成了多射频多信道 Mesh 网络（（Multi-Radio Multi-Channel WMN，MRMC-WMN）[5]。

MRMC-WMN 网络具有提升网络容量，增强数据传输可靠性，减轻网络的信道干扰等诸多优点。在此基础上，高效的信道分配算法能有效地提高网络的吞吐率，增加信道的重用性，优化网络的通信性能。该文在多射频和多信道的条件下，基于拓扑分层及信道的优先级分配通信信道，实现频率资源的高效率分配利用。

1 无线信道分配约束

由于无线环境存在的频道干扰以及相对有限的资源，无线网络如何分配频谱资源通常是无线Mesh网络研究的重要方向。为了提高提升网络的传输性能，通常处理方法是把网络各种资源按单个的资源类型来分配，最后再综合考虑整体性能，这样就造成往往难以实现网络资源分配的最优化。该文中，我们主要研究Mesh无线网络中信道分配策略，综合考虑信道优先级、干扰等因素，实现网络资源的最优分配。

无线网络中信道的最优化分配问题是NP-完全问题[6]，它通常满足下面约束条件：第一，由于结点的射频数量有限且固定，网络的可用信道数量将固定，每个结点可以利用的信道数目也将受到限制，所以相互通信的两个结点需要使用相同频率；第二，网络中相互通信的结点间具有信道依赖性，如果改变通信的频率，将造成相邻结点通信也相应发生频率变化；第三，信道分配需要考虑网络的通信链路负载量，信道分配研究通常假设链路有相同的通信负载，但是在实际网络中，链路的负载通常是不相同的，例如在网关结点的负载明显要大些，而分配算法通常以分配更高带宽的方式来解决；第四，信道分配通常还需考虑采用的路由分配算法的影响。

2 无线信道分配研究现状

在多跳无线网络中，无线信道的分配研究已取得了不少成果，主要的研究方向包括如下几个方面：

1） 集中和分布式分配算法研究。文献[7]给出了自我稳定的信道分配算法，它通过贪婪法选择频道，减少局部目标函数对分配算法的影响。另外，文献[8]提出了一种相对集中式分配算法，在不考虑流量等参数情况下，只利用局部结点的互动信息实现信道分配，但是算法执行后，对网络性能有影响。

2） 针对信道干扰研究。文献[9]给出了DGA算法，它是基于干扰的分配算法，算法先利用Tabu-based算法找到一个可行的信道分配函数，然后再分配信道。其中MinC算法给出的信道分配算法能适应数据流量分布的特点，但是网络的吞吐量将受到影响，最终影响网络的综合性能。endprint

3） 基于拓扑结构的算法研究。该算法是目前主要的研究方向，主要目标在保证网络连通性的同时，合理分配信道。文献[10]在保证网络的连通性和最小的干扰性前提下，给出基于拓扑结构的信道分配算法，但是忽略了结点的优先级及网络的流量对性能的影响。文献[11，12]提出了网络结构与信道分配相互结合的分配方法，算法从逻辑拓扑结构的设计来考虑多信道分配问题。

3 基于拓扑分层的多信道分配算法

本算法给出的基于拓扑分层的多信道分配算法，整体考虑了无线Mesh网络的干扰模型及网络连通性。该算法分为二个主要步骤，第一步实现对通信网络中结点层号的确定，即拓扑分层。首先确定Mesh网络的第一层，将与Mesh结点相邻的结点都作为第一层，然后在第一层的基础上按深度优先的方法扩展，依次为每个结点分配层号；第二步在拓扑分层的基础上，给所有的信道初始化优先级，然后根据结节的层号及动态变化的信道优先级，确定信道动态分配优先级实现信道的分配。

3.1 算法使用模型

1） 网络模型：无线mesh网络中各结点构成的连接图是无向图G（V， E），Vi表示结点， edge（i，j）表示结点i和j连通的边。每个结点i有Ri个无线射频接口，如果结点i和结点j的各自的射频接口有一个相同的信道则可以通信。Gi表示网络的第i层结构，包含结点及相应连通边。chan[k]表示在网络中有k个可用信道，K={1，2……k}，根据干扰模型的要求，可以设定k大于4。

2） 干扰模型：由于无线信道中的频率存在信道干扰，干扰模型定义为连接信号通信会干扰网络中已经存在连接信号的模型。不同文献提供了许多不同的干扰模型，例如物理和协议干扰模型等。该文参考TRCA干扰模型，即连续三跳内同一信道的干扰非常大，它和网络中的拓扑结构有关。

3.2 算法过程

1） 结点分层阶段

首先，算法确定链路干扰模型。纵向干扰和横向干扰是无线链路最常见的干扰方式，因为纵向干扰对网络性能的影响比横向干扰大，所以网络中应尽量采用不同的措施减少纵向干扰对网络的影响。因此，算法在对结点进行分层过程中，第一步确定与网关相邻的结点为第一层，然后按深度优先扩展方式依次对余下的各结点逐级进行分层处理。

在分层的实现中，定义逻辑型变量flag_embed作为结点是否分层标志，flag_embed∈{0，1}。由于分层越靠后的结点离网关结点就越远，当某一层结点数量过多时，表明这些结点构成的路径不是最优的，需设计一个变量来控制某层结点的数量。

2） 信道分配阶段

本算法在第一阶段给出的分层拓扑结构基础上，对信道进行分配。主要使用的是网络的干扰模型与流量模型，要求信道分配不出现纵向干扰，尽量避免横向干扰，采用的模型是TRCA干扰模型；网络的流量负载从网关结点开始呈树状向四周逐步减少，为了实现网络信道的负载平衡，算法利用给定的信道优先级来控制信道的使用次数。信道最终的分配是依据信道优先级动态进行，其中信道优先级的确定是算法的重点因素，实现步骤如下：

STEP 1：给信道初始化，赋优先值为1。

STEP 2：为G1的各个结点Vj分配信道，从拥有最低优先级的信道开始，如每个信道的优化值相同时，随机选择信道进行分配，每当分配完一个信道，此结点对应的信道优先级增加1。

STEP 3：为下一层G2的结点分配信道，同样选择从结点具有的最低优先级开始，保证该结点的直接相连的结点不使用同一信道，如相同，刚往下移一个，分配完信道优先级增加0.5。在实现优先级增加以后，算法为同一层中其它结点分配信道，此时结点在分配完一个信道后，优先级将依次递减0.1。当同层的第二个结点分配完信道后，信道优先级减0.2，如此递减，直到完成这一层所有结点的信道优先级分配为止，同时实现结点信道的分配。

STEP 4：返回执行步骤2和3，实现每层中所有结点的信道分配。

4 仿真的实现及运行结果分析

本算法使用的仿真工具是NS2，结果分析工具采用gnuplot及gawk。硬件平台：CPU：Intel 酷睿i5 4690， 1.60MHz，内存：4GM，Window 7。图1，图2分别考虑了在4个可用信道和10个可用信道下公共信道分配（CCA）方案[10]和本算法吞吐量的比较情况。MAC层采用RTS/CTS机制，数据包的大小为1KB，传输速率为2Mbps。每个结点都有4个射频端口。仿真结果如下图：

5 结论

与其它的算法相比较，该文提出的算法从拓扑结构分层，干扰模型，流量特点及信道优先级等多方面综合考虑，提高了整个网络的吞吐量。仿真可以看出，当信道的数量的增加时，更能体现本算法的特点。另外，无线网络路由算法也是影响信道分配效率的重要因素，本算法没有充分考虑其作用，这是本算法继续提升和改进的地方。

参考文献：

[1] Ian F. Akyildiz， XudongWang， andWeilin Wang. Wireless mesh networks： a survey.

[2] Akyildiz I F， Wang Xudong， Wang Weilin. Wireless mesh networks： a survey[J]. Computer Networks and ISDN Systems， 2005，47（4）：445-487.

[3] So J， Vaidya N. Multi-channel MAC for ad hoc networks： handling multi-channel hidden terminals using a single transceiver[C]. ACM International Symposium on Mobile Ad Hoc Networking and Computing， 2004：222—233.endprint

[4] Adya A， Bahl P， Padhye J， et al. A multi-radio unication protocol for IEEE 802.11 wireless networks[C]. International Conferences on Broadband Networks， 2004：344-354.

[5] Hong X，Gu B，Hoque M，et al.Exploring multiple radios and multiple channels in wireless mesh networks[J]. IEEE Wireless Communications，2010，17（3）：76-85.

[6] 张勇，郭达.无线网状网原理与技术[M].北京：电子工业出版社，2007.

[7] Bong-Jun Ko，Vishal Misra，Jitendra Padhye，Dan Rubenstein Distributed Channel Assignment in Multi-Radio 802.11 Mesh Networks Comput. Netw. ISDN Syst.，2005，47（4）.

[8] Krishna N. Ramachandran， Elizabeth M. Belding-Royer， Kevin C. Interference-aware channel assignment in multi-radio wireless mesh networks. In IEEE Infocom'06.

[9] Gupta P，Kumar P R. The Capacity of Wireless Networks.IEEE Transactions on Information Theory，2000，46（2）. （下转第6845页）

（上接第6841页）

[10] Anand Prabhu Subramanian，Himanshu gupta， Samir R.Das Minimum Interference Channel Assignment inMulti-Radio Wireless Mesh Networks

[7] AVALLONE S， AKYILDIZ IF. A channel assignmentalgorithm for multi-radiowirelessmesh networks[J].Computer Communications，2008，31（7）：1343-1353.

[8] Raniwala A， Chiueh T C.Architecture and algorithm for an IEEE-based multi-channel wireless mesh network.Proc of IEEE Info-com.March 2005

[9] Mohsenian-Rad A H and Wong V W S. Joint logical topology design， interface assignment， channel allocation， and routing for multi-channel wireless mesh networks. IEEE Transactions on Wireless Communications，2007，6（12）：4432-4440.

[10] Jain K， Padhye J， Padmanabhan V N， et al. Impact of Interference on Multi-hop Wireless Network Performance. InMOBICOM， 2003.

[11] http：//www.cse.msu.edu/wangbo1/ns2/nshowto8.html

[12] Kodialam M， Nandagopal T. Characterizing the CapacityRegion in Multi-Radio.Multi-Channel Wireless Mesh Networks.In MOBICOM， 2005.endprint

[4] Adya A， Bahl P， Padhye J， et al. A multi-radio unication protocol for IEEE 802.11 wireless networks[C]. International Conferences on Broadband Networks， 2004：344-354.

[5] Hong X，Gu B，Hoque M，et al.Exploring multiple radios and multiple channels in wireless mesh networks[J]. IEEE Wireless Communications，2010，17（3）：76-85.

[6] 张勇，郭达.无线网状网原理与技术[M].北京：电子工业出版社，2007.

[7] Bong-Jun Ko，Vishal Misra，Jitendra Padhye，Dan Rubenstein Distributed Channel Assignment in Multi-Radio 802.11 Mesh Networks Comput. Netw. ISDN Syst.，2005，47（4）.

[8] Krishna N. Ramachandran， Elizabeth M. Belding-Royer， Kevin C. Interference-aware channel assignment in multi-radio wireless mesh networks. In IEEE Infocom'06.

[9] Gupta P，Kumar P R. The Capacity of Wireless Networks.IEEE Transactions on Information Theory，2000，46（2）. （下转第6845页）

（上接第6841页）

[10] Anand Prabhu Subramanian，Himanshu gupta， Samir R.Das Minimum Interference Channel Assignment inMulti-Radio Wireless Mesh Networks

[7] AVALLONE S， AKYILDIZ IF. A channel assignmentalgorithm for multi-radiowirelessmesh networks[J].Computer Communications，2008，31（7）：1343-1353.

[8] Raniwala A， Chiueh T C.Architecture and algorithm for an IEEE-based multi-channel wireless mesh network.Proc of IEEE Info-com.March 2005

[9] Mohsenian-Rad A H and Wong V W S. Joint logical topology design， interface assignment， channel allocation， and routing for multi-channel wireless mesh networks. IEEE Transactions on Wireless Communications，2007，6（12）：4432-4440.

[10] Jain K， Padhye J， Padmanabhan V N， et al. Impact of Interference on Multi-hop Wireless Network Performance. InMOBICOM， 2003.

[11] http：//www.cse.msu.edu/wangbo1/ns2/nshowto8.html

[12] Kodialam M， Nandagopal T. Characterizing the CapacityRegion in Multi-Radio.Multi-Channel Wireless Mesh Networks.In MOBICOM， 2005.endprint

[4] Adya A， Bahl P， Padhye J， et al. A multi-radio unication protocol for IEEE 802.11 wireless networks[C]. International Conferences on Broadband Networks， 2004：344-354.

[5] Hong X，Gu B，Hoque M，et al.Exploring multiple radios and multiple channels in wireless mesh networks[J]. IEEE Wireless Communications，2010，17（3）：76-85.

[6] 张勇，郭达.无线网状网原理与技术[M].北京：电子工业出版社，2007.

[7] Bong-Jun Ko，Vishal Misra，Jitendra Padhye，Dan Rubenstein Distributed Channel Assignment in Multi-Radio 802.11 Mesh Networks Comput. Netw. ISDN Syst.，2005，47（4）.

[8] Krishna N. Ramachandran， Elizabeth M. Belding-Royer， Kevin C. Interference-aware channel assignment in multi-radio wireless mesh networks. In IEEE Infocom'06.

[9] Gupta P，Kumar P R. The Capacity of Wireless Networks.IEEE Transactions on Information Theory，2000，46（2）. （下转第6845页）

（上接第6841页）

[10] Anand Prabhu Subramanian，Himanshu gupta， Samir R.Das Minimum Interference Channel Assignment inMulti-Radio Wireless Mesh Networks

[7] AVALLONE S， AKYILDIZ IF. A channel assignmentalgorithm for multi-radiowirelessmesh networks[J].Computer Communications，2008，31（7）：1343-1353.

[8] Raniwala A， Chiueh T C.Architecture and algorithm for an IEEE-based multi-channel wireless mesh network.Proc of IEEE Info-com.March 2005

[9] Mohsenian-Rad A H and Wong V W S. Joint logical topology design， interface assignment， channel allocation， and routing for multi-channel wireless mesh networks. IEEE Transactions on Wireless Communications，2007，6（12）：4432-4440.

[10] Jain K， Padhye J， Padmanabhan V N， et al. Impact of Interference on Multi-hop Wireless Network Performance. InMOBICOM， 2003.

[11] http：//www.cse.msu.edu/wangbo1/ns2/nshowto8.html

[12] Kodialam M， Nandagopal T. Characterizing the CapacityRegion in Multi-Radio.Multi-Channel Wireless Mesh Networks.In MOBICOM， 2005.endprint