无线Mesh网络集中式信道分配算法设计

刘 贺,张陆勇,陈明刚,李 茁

(北京邮电大学信息与通信工程学院,北京100876)

0 引言

无线Mesh网络多接口多信道分配方案中,公共信道分配(CCA)是常见的分配方案[1,2]。该方案中,每个节点的射频端都分配相同信道,不能有效提高多信道的利用率。文献[3]根据Hyacinth架构提出了一种集中式的WMN信道分配算法,但该方案限定了路由模式为静态路由,应用场景有限。在此基础上提出了CAR-NL算法,通过采用节点优先级和链路分组的方法,保证了网络中流量集中区域的带宽需求,而且通过网关节点对网络信道质量的评估,提高了全网的整体容量,降低了链路间干扰。

1 系统模型

1.1 多接口WMN架构

Hyacinth无线Mesh网络架构如图1所示。图中,网关节点作为树型拓扑的根节点,承载网络中大部分流量的输入和输出,并负责对网络负载状况做出评估和分配方案,假设网关节点有足够能力来进行相关处理。Mesh路由节点负责汇聚和转发由终端节点上传的业务流量,起到负载均衡和多跳传输的作用。终端节点多用于业务流上传的发起者或者业务流反馈回来的接收者。

图1 Hyacinth无线Mesh网络架构

1.2 节点优先级评估

网关节点承载网络中大部分流量,作为树形拓扑的根节点,其优先级设为最高。其余节点优先级表示为:

式中,R(i)为节点i的优先级;ATi为节点i的总流量;Mi为节点i距离网关中心节点的最小跳数;NICi为节点i的网络接口数量;N为节点i的相邻节点数。

这样,流量承载负荷越大、距离网关节点跳数越小的节点优先级越高。这样的节点等级划分可以适应集中式无线Mesh网络架构的流量承载要求。

1.3 节点链路分组

文献[1,3]中指出了信道分配问题和图着色问题很类似,但是标准图着色算法无法解决一些实际场景中的限制问题。比如通过边着色公式无法解决节点的射频端数量有限的限制问题,因为每个节点对应的色彩数量应该不大于该节点的射频端数量。

通过按照优先级递减的顺序遍历节点,在当前节点所属的所有单跳链路中,选取该节点和优先级更低的节点组成的链路进行分组,分组数量(包括当前节点和优先级更高的节点组成的组)与该节点的射频端数量一致,以此来解决节点分配信道数量超过自身接口数量的矛盾,并且通过链路分组实现每个节点所属链路的信道分配只经过一次优化过程就可以达到最优,防止出现多次调整已分配方案以及由此引发的涟漪效应。分组按照链路中节点优先级和链路预期流量负荷为标准,将优先级高、预期流量负荷较大的链路单独分组,即给予更高的链路带宽。

1.4 链路负载和链路干扰

每个接入路由节点把自身的流入流出负载信息发送给网关节点,网关节点由此计算出端到端业务流对链路的占用比例。

传统的基于IEEE 802.11无线网络数据传输会受到路径内干扰和路径间干扰[4]。路径内干扰是指在发送节点载波侦听范围内同一时刻只能有一个节点进行接收,其余节点要保持空闲状态;路径间干扰是指不同链路中相邻节点发送或者接收信息时对对方造成的干扰。这些都会造成链路数据传输速率的降低和网络系统吞吐量的降低。减少这些干扰的有效手段就是调整不同链路在同一节点或者相邻近节点处的带宽分配,即通过评估链路负载,给不同业务流路径分配不同传输质量的信道,来保证不同带宽需求的业务流路径,达到高效利用有限带宽的目的。

2 信道分配设计和算法

2.1 负载评估

假设在传输范围内每一对Mesh路由节点都有直接的链路连接。网络的连接性由每个节点上分配的公共信道来保证,所有的控制信息均通过固定的公共信道来进行传输。首先计算出链路l的容量:

式中,Cl为链路l的容量;Q为可用信道数量;CQ为每条信道的信道容量;Ll为链路l干扰范围内虚拟链路的数量。

然后计算出链路l的预期负载为:

式中,对于节点对(s,d),φl为链路l预期负载;Pl(s,d)为节点对(s,d)间所有可行路径(Path)中通过链路l的数量;P(s,d)为节点对(s,d)间所有可行路径数量;B(s,d)为节点对(s,d)在业务流中预期的负载(所需带宽)。式(3)表明,链路的初始预期负载就是所有可行路径上的负载之和。

根据式(1)计算出每个节点的优先级,并根据节点优先级和预期负载通过遍历节点对所属链路进行分组。当可用分组数(即节点射频模块数量)大于节点链路数时,可以进行非重叠信道的均匀分配;反之则需要将负载较低的多条链路合并到相同分组中。

考虑到相邻链路间可能的信道干扰,在相邻链路分配相同信道时按照式(4)进行链路容量评估[3],

式中,bwl为链路l的评估容量;φl为链路l的预期负载;Intf(l)为链路l干扰范围内链路集合;C为理论信道容量。

如果相同信道上链路容量之和大于信道理论带宽时,则更换负载较低链路分配的信道来进行调整。

2.2 信道分配

节点优先级和节点链路分组完成后,首先对节点和链路进行降序排序,然后遍历节点依次为节点所属的链路进行信道分配。假设节点拥有射频模块数量为q,节点a和节点b通过链路l连接,会有以下2种情况:

①节点a和节点b的已分配信道数量小于q,则从未分配信道列表里面选取负载最小的信道添加到节点a和节点b的已分配信道列表中;

②有一个节点(假设节点a)已经分配了q条信道,b还有剩余链路组未分配信道,则从a中选取链路l所属组已分配的信道,分配给链路l。并且将信道添加到节点b的已分配信道列表中。

CAR-NL算法信道分配流程如图2所示。

图2 CAR-NL算法流程

3 仿真

使用NS2作为仿真平台进行CAR-NL算法信道分配方案的验证。使用带有 RTS/CTS的 IEEE 802.11MAC协议,路由则采用AODV协议,主要通过CAR-NL算法和CCA算法在多信道多射频模块前提下进行无线Mesh网络的系统吞吐量和丢包率的比较。网络拓扑采用9节点矩阵网络结构。为了简化和产生模拟实验,将矩阵初始节点设为网关节点。每个信道的初始带宽设为1 M,业务流设为CBR类型,速率设定为300 kbit/s和600 kbit/s两种,每个节点最多的接口数设为3。节点水平和垂直间距为200 m,每个节点的接收范围小于节点两跳距离,同时又大于单跳距离。

对吞吐量和丢包率的仿真结果如图3和图4所示。在系统中有8个随机业务流时,单信道网络和CCA网络中的系统吞吐量明显低于CAR-NL网络吞吐量。表明当网络中业务流逐渐增大时,单信道网络系统容量由于多个业务流的干扰没有明显增长,而CAR-NL网络系统吞吐量则实现了较大的增长。与此同时,随着网络负载的增大,不同业务流间的干扰也在逐渐增大,但从整体上看,CAR-NL网络的丢包情况要明显好于前二者,同时,有2个业务流丢包极少,即通过信道的高效利用实现了降低干扰的目标。

图3 系统吞吐量仿真

图4 系统丢包率仿真

4 结束语

在集中式无线Mesh网络基础上,分析了网络负载要求和链路间干扰,提出了信道分配改进算法,并通过仿真表明,该算法在保持较低丢包率的同时能有效提高网络整体吞吐量。集中式无线Mesh网络多信道分配算法的发展方向大多集中在反映网络拓扑和链路质量变化的动态自适应调整方面,对于无线Mesh网络性能的提高具有重要的意义。

[1]HOSSAIN E.无线Mesh网络架构与协议[M].易 燕,李 强,译.北京:机械工业出版社,2009:235-380.

[2]DRAVES R,PADHYE J,ZILL B.Routing in Multi-radio,Multi-hop Wireless Mesh Networks[C].MobiCom'04,2004:114-128.

[3]RANIWALA A,GOPALAN K,CHIUEH T.Centralized Channel Assignment and Routing Algorithms for Multi-channel Wireless Mesh Networks[J].ACM Mobile Computing and Communications Review(MC2R),2004:50-65.

[4]REN J,QIU Z.Centralized Quasi-static Channel Assignment in Multi-Radio Wireless Mesh Networks[C].Communication Systems.ICCS 2008.11th IEEE SingaporeInternational Conference,2008:1149-1154.