孙 暖,周继鹏

（暨南大学 信息科学技术学院计算机系，广东 广州510632）

无线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 问题描述

2.1 网络模型

无线Mesh网络通常用作骨干网络，这里所说的网络指的是由Mesh路由器及其之间的无线链路所形成的网络。为了在Mesh网络中使用多信道，假定网络中的节点静止，每个节点配置一个或多个无线接口卡，网络中有多个无重叠信道可供使用。

网 络 G(V，E)，V={v1，v2，v3，… ，vn}；∀v1，v2∈V，若(v1，v2)∈E，则 v1的接口和 v2的接口分配有相同的信道，并且它们在该信道的电波传输范围之内；I(vi)表示节点vi的无线接口数目，网络所有可用信道集是 F={f1，f2，f3，…，fk}，RT(i)表示信道 fi上电波的传输半径，RI(i)表示信道fi上电波的干扰半径。

2.2 干扰模型

干扰是降低无线网络性能的首要因素，信道分配就是利用多接口多信道最小化WMN中的干扰。目前，有协议和物理两种干扰模型用来描述干扰问题。物理干扰模型较协议模型颇为复杂。本文采用一种协议干扰模型，它规定节点vi在信道fm上向节点vj成功传输数据流，要求：(1)节点 vi、vj上均有接口分配信道 fm；(2)||vjvi||≤RT(m)，节点 vj到节点 vi的距离在信道 fm的电波传输范围之内；(3)任意其他节点 vk若要使用信道 fm，则||vk-vi||>RI(m)且||vk-vj||>RI(m)。

除了干扰模型之外，与干扰相关的限制因素还有：网络可用信道数目，节点的接口数目，而节点部署决定了节点之间的距离，明显影响节点间的干扰关系。

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 本文方法

3.1 生成树方法

考虑到要在生成树中合理分配信道，在构建生成树时，要同时考虑节点的邻居节点集和该节点的接口数目，使节点的最大度受限于邻居节点个数和接口数目。

从Gateway节点开始进行选取子节点操作，使V′={vg}，递归遍历生成树结构V′，并调用选取子节点方法。

节点v选取子节点：

节点v从未选入V′的邻居节点中选择，选择子节点的数目不大于v已剩接口数目；为了使得到的生成树深度尽可能小（即节点到Gateway节点的跳数较少），每次都要选择可能有最多子节点的邻居节点。可能有最多子节点意味着 min(|Hvi-V′|，Ivi)最大。

3.2 信道分配

为生成树的边分配信道，需注意：（1）因近根链路负载较重，所以尽可能保证近根链路的信道差异性，使这些链路减少冲突，并行传输数据。有助于提高整个网络吞吐量。（2）信道重用原则：在没有信号冲突的情况下，尽量使用较少信道，以留给后来节点更多可选择信道。（3）鉴于可用信道有限的现实，网络中各链路不可能均无干扰。以链路干扰为代价，优先保证网络连通性。

网络所有可用信道集为 F={f1，f2，f3， …，fk}。 信道分配方法如下：

广度遍历生成树结构V′，由根开始为每对父子节点间链路调用信道分配算法。为链路vf→vc分配信道算法如下：

起始条件：为每个信道创建集合 ch1、ch2，…，chk，其中chk指使用信道fk的节点集合。并且初始为空集。

将邻居节点集 Hf∪Hc按顺序与 ch2，…，chk做交运算，若为空，为 vf→vc，将 vf、vc加入相应的信道相关节点集，ch2，…，chk按照集的势呈降序排序 （实现信道重用）。若均不为空，暂不分配。

而对于未分配信道的节点和新加入网络中的节点以及因接口限制不在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.