基于干扰感知的多接口无线Mesh网络信道分配算法

王子凡+刘作学+代健美

摘 要： 针对无线Mesh网络因受部署在本地的其他网络干扰而导致的传输能力下降的问题，设计了一种基于干扰感知的多接口动态信道分配算法予以克服。同时采用链接重建的方法避免传输中的数据流因信道改变而被破坏的问题。通过实验仿真，证明在复杂电磁环境下，该算法能有效降低网络干扰，保证网络服务质量。

关键词： 无线Mesh网络； 干扰感知； 多接口； 链路重建

中图分类号： TN915?34 文献标识码： A 文章编号： 1004?373X（2014）14?0024?04

Interference?aware based channel assignment algorithm for multi?interface

wireless Mesh networks

WANG Zi?fan， LIU Zuo?xue， DAI Jian?mei

（Equipment Academy of PLA， Beijing 101416， China）

Abstract： An interference?aware based channel assignment algorithm is presented in this paper to solve the problem that the transmission capacity of wireless Mesh networks declines due to the interference from other networks deployed in the same area. A methord of link reconstruction is used to prevent data flow disruption caused by channel change. The simulation experiment results demonstrate that the algorithm can effectively reduce the network interference in a complex electromagnetic environment and assure the quality of network service.

Keywords： wireless Mesh network； interference?aware； multi?interface； link reconstruction

0 引 言

静态部署的无线多跳网络被称为无线网状网（Wireless Mesh Networks，WMN）。P.Gupta等人研究发现，由于无线介质具有的半双工传输特性，会导致单信道无线网络的传输能力严重的下降[1]。同时随着WiFi热点日益密集，仅通过进行功率控制已无法满足频率复用的要求。动态信道分配方案以其高效的信道利用率和良好的信道自适应性，能够较好地避免网内数据流间的干扰。本文提出一种基于干扰感知的集中式多接口动态信道分配算法，着重解决因网内或网间干扰造成的传输能力下降问题。

1 系统模型

在无线Mesh网络中，用户终端通过网络提供的AP接入点实现网络接入的功能。图1所示的无线Mesh网络较传统网络引入了部分多射频接口Mesh路由器（MR）。网络中单射频接口路由器（SR）装配有相同类型的射频接口，称为默认射频接口。MR至少有一个射频接口与SR的射频接口类型相同。为提高网络容量，MR应部署在位靠近网关节点的位置。信道分配服务器（CAS）部署在网关节点，作用是为多射频Mesh路由器的射频接口分配信道。图1中实线表示默认信道，点状线表示非默认信道。

图1 多射频接口无线Mesh网络结构

2 关键算法研究

2.1 干扰估计

干扰估计的目标是周期性衡量每个Mesh路由器周边的干扰程度。干扰评估的过程可以描述为：Mesh路由器上每个射频接口短时间内在各自的信道上获取数据包。路由器根据非预期MAC地址数据包的数量衡量干扰射频的数量和信道的使用情况。每个路由器根据评估的计算结果维护两组队列，第一组根据检测到干扰源的数量多少排序，第二组根据数据流占用信道带宽的大小来排序。Mesh路由器将两组排序进行融合并向CAS传递。

2.2 信道分配

本文提出的信道分配算法称为冲突距离扫描信道分配算法（Interference Distance Scan Channel Assignment，IDS?CA）。将信道与CAS的距离作为判定权值，进而构造多射频冲突图（Multi?ratio Conflict Graph， MCG）。CAS从Mesh路由器得到干扰估计的情况，为默认射频接口选择一条信道。默认信道的选择原则是选择与当地无线网干扰最小的信道。之后CAS使用IDS?CA算法为每个非默认的射频接口选择信道。

（1） 默认信道选择算法。CAS利用信道等级选择默认信道。默认信道等级为Rc，表达式为：

[Rc=i=1nRankicn]

式中：n表示WMN中路由器的数量；[Rankic]表示使用信道c的接口i的等级。Rc最低的信道就是默认信道。

（2） 非默认信道选择算法。CAS使用路由器收集的邻居信息来构建MCG。Mesh路由器向CAS发送的信息中包含邻居的身份，数据传输延迟，和信道干扰情况。分配信道过程中CAS与MCG中每个顶点对应的延迟密切相关。CAS同样与每个顶点的信道等级有关，该信道等级为Rd，其表达式为：

[Rd=j=1mRankid]

式中：m表示MCG节点j包含接口数量；[Rankid]表示使用信道d的接口j的等级。得出信道距离之后，CAS使用IDS?CA算法来对WMN的射频接口分配信道。算法总结如下（IDS?CA算法）：

（1） 初始化网络，创建表V={v|v∈MCG}

（2） while 未遍历完表V中所有节点 do

（3） h=min{HopCount（V）}

（4） Q={v|v∈V & notVisited（v） & HopCount（v）==h}

（5） 将表Q按照链路延时的增加排序

（6） while size（Q）>0 do

（7） vcurent=RemoveHead（Q）

（8） if Visited（vcurent） then

（9） continue

（10） end if

（11） 访问链路vcurent

（12） Vn={u|u∈MCG & u与vcurent在位置上相邻}

（13） 将等级较高的稳定信道c分配给vcurent，并且该信 道不与ui相冲突，{ui∈Vn & 0≤i

（14） if c不存在 then

（15） 将一随机信道长久分配给vcurent

（16） end if

（17） L= {v|v∈MCG & v中含有vcurent所包含的任意一 个射频接口}

（18） 从MCG中移走包含有L因子的顶点

（19） 将信道c临时分配给R={r|r∈v & r?vcurent， v∈L}

（20） 设路由器rf为链路vcurent的远端射频接口（相对 CAS而言）所在的路由器

（21） 构造表Tail，Tail={v|v∈MCG & 链路v的一端为 rf 的射频接口}

（22） 将Tail按照链路延迟的增加排序

（23） 将表Tail中的链路添加到表Q中

（24） end while

（25） 为未被分配稳定信道的射频接口分配相对稳定信道

（26） end while

其中：HopCount（V）的作用是计算表V中所有链路的跳数；RemoveHead（Q）的作用为获取表Q中级别最高的链路，并将该链路从表Q中移出；size（Q）的作用为计算表Q中链路的数量；Visited（vcurent）返回一个布尔值，判定vcurent是否被访问过。当信道分配完毕，CAS通知Mesh路由器重新配置射频端的信道。

3 相关技术研究

（1） 干扰估计。在WMN中，Mesh路由器通过捕获数据包执行干扰估计。在实现中采用无线网卡模块普遍支持的RFMom模式（无线频率检测模式）进行数据包捕获，该模式能同时捕获管理帧和普通数据帧。当射频接口被设置成RFMom模式，在感知阶段不能传输数据。由于每个路由器的干扰估计与它的邻居进行干扰估计相互独立，因此不能保证两个工作在同一信道的射频端能够通信成功。为了防止数据流被破坏，引入了链接重建技术。

（2） 链接重建。链接重建是将数据流从非默认信道调整到默认信道的过程。其工作过程可描述为：无论何时，当一个射频接口需将它的状态变为干扰感知状态时，在它改变其状态的3 s之前，每秒广播一个INTERFACE?INACTIVE消息。任何邻居收到INTERFACE?INACTIVE消息后，从它的路由表中删除即将要变成干扰感知射频接口的地址。一旦删除发生后，连接重新定向功能便被激活。

（3） 信道分配协议。非默认信道分配通过调用链路重建防止数据流损坏。执行分配时，CAS向路由器发送射频接口重置的消息。Mesh路由器收到重置消息后向CAS发送一个确认，并开始调用链路重建过程。使用ping功能向链路上的邻居节点进行活跃确认，邻居节点将其添加入路由表中。分配默认射频端信道，我们假设一个可靠的广播协议是可用的，这个协议可以用来通知所有的Mesh路由器关于新的信道分配情况。

4 仿真及结果分析

网络仿真使用Matlab作为软件平台，使用OLSR（Optimized Link State Routing）路由协议作为Mesh网的路由协议。Mesh路由器的射频接口设置为IEEE 802.11a，多径传播模式使用瑞利衰落。传输功率设定为18 dBm。干扰估计每5 min 1次。每个信道干扰估计的时间被设定为3 s，共12个信道。CAS每10 min调用1次IDS?CA算法。

首先通过在一个简单的拓扑模型中来验证算法的正确性。网络拓扑由4个网络节点和2个干扰节点构成。节点a装备了1个射频接口，节点b和d装备有2个射频接口，节点c装备有3个射频接口，节点d为网关（如图2所示）。节点a以8 Mb/s的恒定速率向节点d发送包含大小为1 024 B的数据包。

图2 验证网络

仿真开始时，所有的默认的射频接口被配置在同一信道上。节点a的数据流只能通过默认信道到达网关。第一次信道分配发生在第600 s。在第900 s前夕，一个低比特率数据流在两个干扰节点e，f之间传输，该数据流能影响到节点b和节点c，且和链路sbc使用相同的信道。图3为网关节点收到的数据包的实时数量。

在第600 s之前，节点d每秒收到200个数据包。第600 s时，CAS进行了信道分配。节点d每秒收到数据包的数量上升到1 000个数据包左右。在在700～736 s处，路由节点进行干扰估计。在此时间段，节点d接收的数据包数量从1 000包/s降到200包/s。由于进行了链接重建，数据包传递速度没有降到0。在第900 s前一刻，引入了干扰数据流（红线），网络稳定性下降。节点c和d在1 036～1 072 s期间探测到了干扰，并将干扰估计送到CAS。在1 200 s时，CAS重新为链接分配信道，网络趋于稳定。在大范围性能评估中，网络拓扑使用文献所设计的4种拓扑结构，每个拓扑中共有30个路由器分布在500×500 m的区域内。在此仿真设计了两种网络流量方案。第一种方案为理想情况，网络中没有内部或外部的干扰数据流。第二种方案允许WMN中同时存在多个数据流，数据流之间存在相互影响。

图3 网关节点数据包吞吐量

在方案1中，评估了在四种拓扑网络结构使用多射频接口代替单射频接口所获得的吞吐量增益。图4标绘了10个FTP传输器在单射频Mesh路由器网络、多射频动态信道分配、多信道静态信道分配的平均吞吐量。相比单射频接口路由器，多射频接口路由器在拓扑1中吞吐量提高了200%，在拓扑2和3提高了100%；在拓扑4中提高了33%。值得注意的是，在拓扑2～4中，静态信道分配比IDS?CA算法有更好的吞吐量，分别高出大约8%，5%，15%。这是因为在理想条件下相比静态信道分配，IDS?CA算法在进行干扰估计的操作时要耗费额外的资源。

图4 方案1三种信道分配方式在四种拓扑结构中的对比

在方案2中网络中同时存在多个数据流。由于IDS?CA算法采用干扰估计技术，相邻信道相互正交，如图5所示，其传输性能要优于静态信道分配算法。特别在拓扑2中吞吐量提高了72%，在拓扑1，3，4分别提高了48%，60%和13%。

图5 方案2动态信道分配与静态信道分配的吞吐量对比

5 结 语

IDS?CA作为一种集中式多接口动态信道分配算法，在存在本地网络干扰的条件下能有效避免无线Mesh网络性能下降。下一步将对算法进一步优化，减少评估过程中流量波动，提高网络的传输稳定性。

参考文献

[1] GUPTA P， KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46（2）： 388?404.

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

[3] BUDDHIKOT M M， MILLER S C， SUBRAMANIAN A P. Interference aware routing in multi?radio wireless mesh networks： US， 8，532，023 [P]. 2013?9?10.

[4] MWENJA J M. Framework for securing wireless local area network [D]. [S.l.]： [s.n.]， 2014.

[5] WANG A， ZHU B. Realize node localization based on OLSR protocol in Ad Hoc networks [J]. International Journal of Networked and Distributed Computing， 2013， 1（1）： 61?71.

[6] BAR F， PARK N. Municipal Wi?Fi networks： The goals， practices， and policy implications of the US case [J]. Communications & Strategies， 2006， 61（1）： 107?125.

图3 网关节点数据包吞吐量

在方案1中，评估了在四种拓扑网络结构使用多射频接口代替单射频接口所获得的吞吐量增益。图4标绘了10个FTP传输器在单射频Mesh路由器网络、多射频动态信道分配、多信道静态信道分配的平均吞吐量。相比单射频接口路由器，多射频接口路由器在拓扑1中吞吐量提高了200%，在拓扑2和3提高了100%；在拓扑4中提高了33%。值得注意的是，在拓扑2～4中，静态信道分配比IDS?CA算法有更好的吞吐量，分别高出大约8%，5%，15%。这是因为在理想条件下相比静态信道分配，IDS?CA算法在进行干扰估计的操作时要耗费额外的资源。

图4 方案1三种信道分配方式在四种拓扑结构中的对比

在方案2中网络中同时存在多个数据流。由于IDS?CA算法采用干扰估计技术，相邻信道相互正交，如图5所示，其传输性能要优于静态信道分配算法。特别在拓扑2中吞吐量提高了72%，在拓扑1，3，4分别提高了48%，60%和13%。

图5 方案2动态信道分配与静态信道分配的吞吐量对比

5 结 语

IDS?CA作为一种集中式多接口动态信道分配算法，在存在本地网络干扰的条件下能有效避免无线Mesh网络性能下降。下一步将对算法进一步优化，减少评估过程中流量波动，提高网络的传输稳定性。

参考文献

[1] GUPTA P， KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46（2）： 388?404.

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

[3] BUDDHIKOT M M， MILLER S C， SUBRAMANIAN A P. Interference aware routing in multi?radio wireless mesh networks： US， 8，532，023 [P]. 2013?9?10.

[4] MWENJA J M. Framework for securing wireless local area network [D]. [S.l.]： [s.n.]， 2014.

[5] WANG A， ZHU B. Realize node localization based on OLSR protocol in Ad Hoc networks [J]. International Journal of Networked and Distributed Computing， 2013， 1（1）： 61?71.

[6] BAR F， PARK N. Municipal Wi?Fi networks： The goals， practices， and policy implications of the US case [J]. Communications & Strategies， 2006， 61（1）： 107?125.

图3 网关节点数据包吞吐量

在方案1中，评估了在四种拓扑网络结构使用多射频接口代替单射频接口所获得的吞吐量增益。图4标绘了10个FTP传输器在单射频Mesh路由器网络、多射频动态信道分配、多信道静态信道分配的平均吞吐量。相比单射频接口路由器，多射频接口路由器在拓扑1中吞吐量提高了200%，在拓扑2和3提高了100%；在拓扑4中提高了33%。值得注意的是，在拓扑2～4中，静态信道分配比IDS?CA算法有更好的吞吐量，分别高出大约8%，5%，15%。这是因为在理想条件下相比静态信道分配，IDS?CA算法在进行干扰估计的操作时要耗费额外的资源。

图4 方案1三种信道分配方式在四种拓扑结构中的对比

在方案2中网络中同时存在多个数据流。由于IDS?CA算法采用干扰估计技术，相邻信道相互正交，如图5所示，其传输性能要优于静态信道分配算法。特别在拓扑2中吞吐量提高了72%，在拓扑1，3，4分别提高了48%，60%和13%。

图5 方案2动态信道分配与静态信道分配的吞吐量对比

5 结 语

IDS?CA作为一种集中式多接口动态信道分配算法，在存在本地网络干扰的条件下能有效避免无线Mesh网络性能下降。下一步将对算法进一步优化，减少评估过程中流量波动，提高网络的传输稳定性。

参考文献

[1] GUPTA P， KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46（2）： 388?404.

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

[3] BUDDHIKOT M M， MILLER S C， SUBRAMANIAN A P. Interference aware routing in multi?radio wireless mesh networks： US， 8，532，023 [P]. 2013?9?10.

[4] MWENJA J M. Framework for securing wireless local area network [D]. [S.l.]： [s.n.]， 2014.

[5] WANG A， ZHU B. Realize node localization based on OLSR protocol in Ad Hoc networks [J]. International Journal of Networked and Distributed Computing， 2013， 1（1）： 61?71.

[6] BAR F， PARK N. Municipal Wi?Fi networks： The goals， practices， and policy implications of the US case [J]. Communications & Strategies， 2006， 61（1）： 107?125.