基于IEEE802.11s的多射频多信道无线mesh网络路由判据的探究

熊道龙，郭见兵，顾燕飞

（1.武汉邮电科学研究院，湖北武汉，430074；2.武汉虹信通信技术有限责任公司，湖北武汉，430074)

0 前言

随着视频，图像，语言等多媒体业务急速增长，传统的基于单信道的mesh网络已经无法满足我们的需求。作为目前研究最广泛的IEEE802.11s协议，其空时链路判据（ALM）也是基于单信道条件下的。那么如何在此基础上拓展为适合于多信道条件的路由判据，是很多学者研究的目标。

本文首先将简要的介绍IEEE802.11s路由技术，然后介绍当前多信道MAC技术的研究进展，最后主要分析比较加权累计期望传输时间（weighted cumulative expected transmission time，WCETT），干扰及信道切换（metric of interference and channel switching，MIC），归一化的瓶颈链路容量（normalized bottleneck link capacity，NBLC），这3种多信道条件下的路由判据，并通过NS-2网络仿真，更为直观的将各种判据对网络性能的影响展现出来。最后，结合理论分析及仿真结果，让我们能够明确每种判据的适用场合，并得出结论。

1 IEEE802.11s路由技术

混合无线网状网协议（HWMP）是源自ad hoc的AODV路由协议与基于生成树的路由协议的综合。它结合了先验式和反应式两种构件，适用于ad hoc、基础结构及混合WLAN网状网等。它的优势就在于能够灵活地适应很多场景的需要；在网络有根节点时，减少了网内数据包的洪泛，使用按需路由发现时，减少了源端缓冲消息的需要。

协议所定义的路由判据是ALM，它反应了数据在空中传播的时间成本，具体计算如公式1，所示：

其中，O表示信道访问开销，Bt表示测试帧长度，r表示数据传输长度，ef 表示长度为Bt的帧以r为速率传输失败的概率。

2 WMN中MAC技术与多信道技术

IEEE802.11s在单信道的基础上对MAC协议进行了增强与改进，它依旧无法满足多信道应用环境。因此，各种多信道MAC技术被提出来。

目前，根据信道选择技术对现有的多信道MAC协议进行分类。主要包括基于握手的信道选择；信道跳跃；跨层信道分配。对于基于握手的信道选择，包括动态信道分配（DCA）、多信道CSMA MAC和多信道MAC。与802.11相同，它们通过在发送者和接收者之间交换控制信息实现握手机制。还有一些MMAC使用信道跳跃来完成两个节点间的数据交换，如双轮询的接收端发起的信道跳跃（RICH-DP）和时隙种子信道跳跃（SSCH）。

关于信道分配问题，这是WMN中研究的一个热点之一。简单来说，最佳信道分配问题，就是一个以对应的图形着色问题为基础的“NP-Hard问题”。在多射频多信道的WMN网络中，路由和信道分配是相互依存的。路由取决于虚拟链路的容量，链路容量又由信道分配所决定。目前的信道分配方案种类繁多，在一定程度上改善了网络的性能，但是面临的挑战是对于每个mesh路由器分配多少个射频接口，依旧没有给出具体的方案；另一方面的问题就在与，流量不均衡时应该如何分配信道。这些问题都需要进行深入细致的研究。

3 多射频多信道路由判据

3.1 WCETT

WCETT是一种冲突感知的路由判据，在传统的期望传输时间（ETT）的基础上，综合考虑了数据流内的干扰问题，从而减少了在一个数据流所经的路径上使用同一信道的节点数。其表达式如公式2所示：

其中β是一个可调的参数，在0-1范围内。,xj是j信道在路径p上使用的次数，以此来捕获数据流内的干扰。式中，部分是同样的信道在路径上出现次数的最大值，那些在链路的信道分配上更具多样性的路径具有更低的数据流内干扰，而它们相应这一项的权值也比较小。因此，公式中这一部分体现了流内干扰的强度。

WCETT有两方面的局限性。首先，虽然它确实捕捉到了数据流内的干扰，但没有显式的考虑数据流间干扰。其次，WCETT不保序。因而缺乏有效的算法来计算最小代价路径。为了保证路由中无环路，WCETT只能用在按需路由、源路由如LQSR或距离向量路由。对于这些问题MIC判据做出了一定的改进。

3.2 MIC

干扰及信道切换路由判据（MIC），它是对WCETT的一个改进，解决了WCETT不能捕捉到数据流间干扰问题，路径P的MIC定义如公式3所示：

其中，N是网络中所有节点的个数，min(ETT)是网络中最小的ETT值，这个最小值可以通过无线网卡最低传输速率来估算。而MIC的两个要素：IRU(Interference—aware Resource Usage干扰感知型资源使用)和CSC(Channel Switching Cost信道切换权重)定义如下：

公式（4）中NI是在链路I上进行数据传输时的一系列邻接节点，也是干扰发生源；CH(I)表示分配给节点i用来传输数据的信道；prey(i)表示在路径P上i节点前一跳的节点。IRU为，链路I上数据传输所消耗的邻节点的信道时间的总和。因其倾向于选择消耗邻节点信道时间少的路径，该判据捕捉到了数据流间的干扰；MIC的CSC部分表示了数据流内的干扰。

值得注意的是，在真实网络中直接应用MIC，所得到的路径权重函数不保序。因此我们只能利用按需路由获得MIC的值。最新的研究表明，利用“虚节点”技术，可以解决MIC判据不保序的问题，由于篇幅的限制，本文不再赘述。

3.3 NBLC

NBLC路由判据通过综合考虑了流量负载，信道容量，以及链路可用的剩余带宽，极大地提升了系统的吞吐量。NBLC判据定义如下：获得这些参数后，对于一条跳数为L的路径p定义判据NBLC判据如下：

在该路由判据中，每个节点需要周期性测量每个链接的RLC(residual link capacity)值，该值反应的是链路的剩余带宽，同时将这个值并广播到k跳范围内所有的节点。同时计算一条路径P上某个链接i的CEBT(Cumulative Expected Busy Time)值，其值等于路径P上对链接i形成干扰的其他链接的ETT值之和，显然干扰的链接应该和链接i在同样的信道上。代表了包被丢弃的概率。

总体上看，NBLC判据体现了一个瓶颈链路上可利用的剩余带宽。一个更大的NBLC值表明一个更短，负载更小，更多可用信道的路径。因此，根据选路算法，我们应当选择NBLC值更大的那一个。

4 NS-2仿真及结果分析

仿真模拟采用NS-2仿真软件[8]，每个节点有2个射频口，每个接口有3个可用数据信道，1个控制信道。源节点随机分配，仿真采用CBR流，每个CBR流是512Byte，每秒发送20个包。节点的传输范围是250m，载波侦听范围是500m，为了排除移动性的干扰，所有的N个节点是固定位置的。仿真范围是1000m*1000m区域中分布的10*10的方格中。分析的主要参数为系统的平均吞吐量及端到端的时延。

上文公式中可调参数β设置为0.5，路由协议分为RMAODV与RANN两种机制。根据IEEE802.11s默认的HWMP路由协议，在NS2仿真平台下，对AODV及RANN路由包进行适当的设定，使之得能够满足仿真所需的要求。仿真结果如下图所示：

结果分析

通过图1，及图2的仿真结果表明，WCETT，MIC，NBLC判据比传统的单信道条件下的ALM判据在平均吞吐量上有更加优越的性能，其中，MIC和NBLC判据对吞吐量的提升效果最明显。根据图3，和图4的仿真结果，我们可以知道NBLC这种路由判据更加适合多节点，大范围的网络，其时延性相对其他的路由判据来说是最好的。在节点数相对较少的时候，WCETT，MIC，NBLC三种判据的端到端时延在AODV路由机制下差别不明显。在RANN机制下，由于引入根节点，这种拓扑结构使得紧邻根节点的链路能够获得更多的数据流量。因此，根据流量负载所设计的路由判据MIC及NBLC在拥有高吞吐量的同时也保持了较低的端到端时延，这与路由判据的设计思想是一致的。

图1.AODV路由机制下的平均吞吐量

图2.RANN路由机制下的平均吞吐量

图3.AODV路由机制下的端到端延迟

图4.RANN路由机制下的端到端延迟

5 结束语

本文主要讨论了基于IEEE802.11s的无线mesh网络中的路由判据问题。通过研究几种多射频，多信道条件下的路由判据，我们可以发现：在单信道条件下，ALM判据在单信道条件下是非常适合的；WCETT判据适合于多节点但数据量低的网络；MIC判据适合于多邻居同时干扰的网络；NBLC判据适合于多节点高数据量的网络。由于IEEE802.11s mesh网络设计目标就是为了支持高混合流量负载，因此MIC与NBLC判据更加适合IEEE802.11s mesh网络。

未来研究的一个重点就是将多信道与路由技术相结合，信道分配取决于每条链路的负载能力，对于多射频，多信道的无线mesh网络而言，路由技术与信道分配技术是互相依赖的，下一步的工作将是研究信道分配与路由技术的联合算法。

[1]Yan Zhang, Jijun Luo, Honglin Hu著，郭达 张勇等译.无线网状网：架构、协议与标准[M].北京：电子工业出版社，2008.6.

[2]IEEE Std 802.1lTM-2011.IEEE standard for information technology- telecommunications and information exchange between systems.Local and metropolitan area network specific requirements-Part lI：Wireless LAN medium access control(MAC)and physical layer(PHY) specifications Amendment 10: Mesh Networking [S].Sep 2011.

[3]Sana Ghannay，Fethi Filali.Multi-radio multichannel routing metrics in IEEE 802.11s based wireless mesh networks[J],Ann.Telecommun.DOI 10.1007/s12243-011-0253-z May,2011.

[4]张鹏.无线Mesh网络环境中多网关路由和切换机制的研究[D]，中国科学技术大学，2009.4.

[5]Ekram Hossain，Kin K.Leung著，易燕，李强等译.无线Mesh网络架构与协议[M].北京：机械工业出版社，2009.5.

[6]Yang Y,Wang J,Kravets,R(2005)Designing routing metrics for mesh networks[J].In:Proc.of the IEEE workshop on wireless mesh networks(WiMesh).

[7]Liu T,Liao W(2008)On routing in multichannel wireless mesh networks:challenges and solutions[J].IEEE Network 22(1):13–18.

[8]黄化吉 秦丽娇等著.NS网络模拟和协议仿真[M].北京:人民邮电出版社，2010.5