摘 要: 无线Mesh网络是一种特殊的Ad Hoc网络。它易于部署、安装，能有效地构建无线骨干网，通常被用作宽带Internet接入和扩展无线LAN的覆盖范围。针对无线Mesh网络的特点，提出了一种不同于一般MANET路由协议的路由算法。该算法基于网络拓扑生成树，使用多个无重叠信道；在解决信道分配问题的同时，兼顾信道多样性和信道重用，更好地利用无线频谱资源，支持链路并行传输。
关键词: 无线Mesh网络; 多信道; 生成树
无线Mesh网络是一种新型的多跳网络技术。它与MANET大致相同，由一系列可以提供转发、互相通信的无线节点组成，每个节点既是主机又是路由器。无线Mesh网络具有网状拓扑，其网络架构一般由3层组成：最高层是一个或几个Gateway节点，WMNs通过它们与Internet进行有线连接；中间层由许多Mesh路由器组成，它们是网状拓扑的顶点，在WMNs中进行接力转发；底层由一些终端用户组成，包括移动客户端和静止客户端。通常Mesh路由器是静止的，底层终端用户无线登录Mesh路由器，通过Mesh网络构建局域网并访问Internet。
IEEE PHY规格说明，允许在2.4 GHz的频带上使用3个无重叠信道，在5 GHz频带上使用12个无重叠信道。为了提高WMN的容量，在WMNs中使用多个无重叠信道，为每个Mesh路由器配置一个或多个无线接口，制定信道分配机制，挑选合适的路由方案，并把两者结合起来，得出可行的路由算法。
1 相关工作
随着WMNs的广泛应用，人们不再满足于使用一般的MANET路由协议。MANET路由协议主要关注节点的能量耗费和移动特征。而由几乎静止的Mesh路由器所构成的无线骨干网络，无能量限制，旨在提供更高的网络吞吐量和更低的端到端延迟，以期支持VoIP、实时视频监视，宽带网络互联通信等大流量服务[1]。目前已有的专为无线Mesh网络设计的路由协议有：
(1)参考文献[2]提出的多个版本的Mesh路由协议。认为大部分流量来自并流向Internet，WMNs中的节点仅需知道怎样到达Gateway；少量的终端用户间流量可通过其父节点路由。本质上，形成了以Gateway节点为根的树。
(2)参考文献[1]提出了一种基于状态的多接口多信道多路径的自适应路由协议。协议为节点配置多个无线接口，固定选取接受信道，动态切换发送信道，以期多链路同步传输流量。
(3)多信道技术作为提高网络容量最有效的手段，信道分配（CA）是其重点和难点。多接口多信道无线Mesh网络中的信道分配可以分为集中式分配和分布式分配两大类[4]。集中式分配预先知道Mesh网络的完整信息，在一个节点上阐明并解决信道分配问题，计算结果再分发给其他节点。分布式分配中节点独立运行CA算法，计算出本身所用信道。根据流量模式又可分为两种，Gateway导向的CA方法认为网络中的主要流量流经Gateway节点，CA使用启发式方法使近Gateway链路分配较高的带宽。对等导向的CA方法则认为网络中流量没有固定模式，来自任一对节点之间，所以要尽可能地适应不同类型的网络流量[3]。
本文在参考文献[2]的基础上，研究在路由过程中使用多信道，为此提出了一种考虑接口数目的生成树方法。为了减少信道切换的耗费，采用了静态信道分配，节点在传送数据时，不用考虑信道选择问题，可直接从读取路由信息，快速转发数据。
除了干扰模型之外，与干扰相关的限制因素还有：网络可用信道数目，节点的接口数目，而节点部署决定了节点之间的距离，明显影响节点间的干扰关系。
2.3 信道多样性
信道多样性可为相邻的链路分配不同信道，使它们可以并行传输，不发生干扰。好的信道区分可以避免两种干扰：流内干扰和流间干扰，如图1所示。
图1（a）中，分配信道后，流A→C与流D→E不存在干扰，而流A→C中，链路AB和BC之间存在干扰。而图1（b）中不存在流内干扰，但流A→C和流D→E存在干扰，两个数据流不能同时传输。为了消除这两种干扰，需使相邻的链路AB、BC、DE、EF分配互不相同的信道。
2.4 连通性
信道分配会影响网络的连通性。使用相同信道的节点越多，网络会更健壮，但也会导致更多的干扰。信道分配首先要保证网络的连通，在此基础上尽可能减少冲突。
在综合考虑干扰模型、可用信道数目、每个节点接口数目、节点的部署等因素情况下，对WMN进行静态信道分配以得到一个连通网络是一个NP问题。
3 本文方法
而对于未分配信道的节点和新加入网络中的节点以及因接口限制不在V′中的节点，此时，可考虑其邻居节点，如邻居节点有剩余接口，调用上述分配方法；如所有邻居节点均无剩余接口，则为其分配信道相关节点集最小的信道，并把游离节点加入树结构V′。
4 可行性与优点
无线Mesh网络中的Mesh路由器节点很少移动，其构成的骨干网络除了使用无线通信方式外，还具有有线网络稳定的优点，在WMN中使用先应式路由协议就可免去考虑频繁更新路由表的问题；同样认为无线Mesh网络中大部分流量来自并流向Internet，节点仅需知道如何到达Gateway；少量的终端用户间流量可通过其父节点路由。对于一个连通的网络拓扑图G′(V，E)来说，必然存在一棵生成树T。在对链路分配信道时，生成树T只有n-1边，与G′(V，E)相比，整个网络中的链路冲突将大大减少，如图2所示。
在只有5个可用信道时，图2（a）中的AC与FD、AF与CD、BC与EF之间存在流间干扰，而图2（b）中则不存在干扰。但这只是一种理想状况，因为节点还要受到接口数目的限制。如果节点C只有2个接口，最多能为其分配2个无重叠信道，而不是图2（a）中所示的4个无重叠信道。
本文针对无线Mesh网络的特点，提出了一种树形路由算法，该路由算法利用对原网络拓扑进行剪枝处理，得到了一棵保证网络连通的生成树，节点利用生成树结构构建路由表，通过父节点与其他节点进行通信。在信道分配阶段，全面考虑整个网络，只对生成树的边进行信道分配，减少了非生成树边对网络的干扰；对链路分配信道时，考虑了该链路的整个干扰区域，而不是只考虑流经该链路的线性路径，尽可能地排除流内干扰和流间干扰。对信道相关节点集进行排序，有利于信道重用。
参考文献
[1] DEEPTI S N, NAGESH S N. DHARMA P A.Adaptive statebased multi-radio multi-channel multi-path routing in Wireless Mesh Networks[J]. Pervasive and Mobile Computing, 2009，5(1):93-109.
[2] JANGEUN J, MIHAIL L S. MRP: wireless mesh networks routing protocol[J]. Computer Communications, 2008，31(7): 1413-1435.
[3] MAO Xu Fei，LI Xiang Yang，MAKKI S K. Static channel assignment for multi-radio multi-channel multi-hop wireless networks.[2006-06-16].http://www.asee-ncsection.org/papers/122.pdf.
[4] SI Wei Sheng, SELVAKENNEDY S,ZOMAYA A Y. An overview of channel assignment methods for multi-radio multi-channel wireless mesh networks[J]. Journal of Parallel Distributed Computing, 2010，70(5)：505-524.