基于HWMP协议的无线网络路由判据研究*

余 智 汪慧君 肖雪露

(武汉船舶通信研究所 武汉 430250)



基于HWMP协议的无线网络路由判据研究*

余 智 汪慧君 肖雪露

(武汉船舶通信研究所 武汉 430250)

HWMP路由协议采用标准空时开销判据进行路径选择时,仅考虑了链路中节点所消耗的信道资源总量,不能综合考虑链路的质量、负载及其受干扰的情况。针对该问题,论文提出了一种新的路径选择算法,该方法将MAC层中更多的信道质量参数提取到路由判据中来,能综合考虑复杂多变的无线信道多种因数,有助于提高无线网络吞吐量,降低端到端时延。经过仿真实验表明,新路由判别方法能够优化802.11s的路径选择,提高网络的整体性能。

MAC层; 路由判据; 端到端时延; 吞吐量

Class Number TM933

1 引言

无线Mesh网络(Wireless Mesh Networks)是一种新兴的无线组网技术,支持无线多跳路由,又称“无线网格网”。无线Mesh网络结构作为解决“最后一公里”网络接入瓶颈问题的方案,具有较高的可靠性、较大的伸缩性、较强的自愈性和较低的投资成本,因此,无线网格网已成为当前网络研究的技术热点[1]。

在网络研究领域,路由协议一直是研究的重点。IEEE802.11标准工作组针对无线网格网制定了802.11s标准,该标准中使用混合无线网格协议(Hybrid Wireless Mesh Protocol,HWMP)作为其默认的路径选择协议。HWMP协议是一种混合式路径选择协议[2],同时结合了反应式和先验式路由协议的特点。该协议工作在MAC层,和传统的三层网络协议不同,HWMP协议中通过MAC地址进行路径寻址、数据转发[3]。

为得到更加优化的路径选择,提高无线Mesh网络的性能,国内外关于HWMP路由协议的研究主要集中在以下几个方面:一是对路径选择判据的研究,二是对HWMP的实际性能进行测试,三是根据HWMP协议的问题,提出新的路由算法或是在HWMP基础上进行算法改进。本文主要针对路径选择判据进行相应的研究,提出一种新的路径选择判别算法,并对该算法进行仿真实验。试验证明该方法优化了路径选择,降低了端到端时延,提高了无线网络吞吐量。

2 传统空时路径选择判别方法

为了确保可扩展框架中不同路径选择协议间基本的互操作,IEEE802.11s标准定义了基于空时(airtime)消耗的默认的链路metric来度量无线选择路径[4]。当帧经过某链路时,采用下式计算空时链路metric值Ca,来度量该链路传输该帧所消耗的信道资源总量。路径metric是路径中所有链路metric的总和[5～6]。

(1)

上式中,Oca为信道接入负载,Op为MAC协议负载,Bt为测试帧中的比特数,这三个参数均是常量,不同IEEE802.11传输技术下其取值如表1所示。传输比特率r(Mbit/s)指Mesh节点基于当前无线环境传输一个大小为Bt数据帧的速度,帧错误率efr是指标准Bt大小帧在当前传输比特率r下,由于传输错误造成的帧丢失概率。

表1 空时消耗判据参数典型取值

可以看出,基于射频感知的空时路径选择判据虽然考虑了MAC层中的一些参数作为路由判据的参量,据此进行路径选择,能得到稍优化的路由;但由于Oca,Op等参数都为固定值,不能体现不断变化的无线信道环境,因此,需要研究新的路径判别方法,使得网络在复杂多变的无线环境中能得到更加优化的路径。

3 新路径选择判别算法

由移动节点构成的自组织无线Mesh网络,不同链路的质量是不同的,且是不断变化的。空时路径判别是802.11s中HWMP协议默认的路径选择判据,它虽然选取了MAC层中的参数作为路径选择的度量标准,但所选取的MAC层参数远远不够,没有考虑链路的质量、拥塞及负载等情况,也没有考虑其他节点的干扰;而这些都影响着整个网络的性能,如果路径选择没有将这些关键因素都考虑进来的话,就无法适应复杂多变的无线信道环境,无法得到最优的路径,无法最大优化网络的性能。

HWMP中路径选择参数注重考虑了不同网络间路径选择操作的兼容性,却没有很好考虑到各链路类型的差异对路径选择的影响。因此,需要针对其在无线多跳网格网中所存在的不足,研究新的路径选择判据,综合考虑多方面因素,争取从MAC层中提取更多的参数引入到判据中来,提供信道质量判别,帮助选择一条链路质量稳定、时延较小、因链路质量及拥塞问题造成重传需求最小的路径,避免网络拥塞。

新路由判据在现有空时判据基础上,至少应包含: 1) 对拥塞及链路质量的衡量判别, 2) 对节点干扰信息的感知。

3.1 链路质量和路径拥塞判别方法

链路质量和路径拥塞情况可以通过引入期望传输效率来表示。

节点在发送RTS或数据时,如果在规定的时间内没有收到相应的CTS或者ACK,就会启用重传机制;数据包丢失或者链路拥塞造成RTS重传[7]。所以利用RTSFailureCount和ACKFailureCount可以表示成功发送一个数据包所需要重传帧的次数,RTSFailureCount表示RTS的重传次数,ACKFailureCount表示数据重传的次数。

设节点A到节点B成功发送第k个数据包的重传次数为

ETXAB(k)=RTSFailureCountAB(k)

+ACKFailureCountAB(k)

(2)

理想状态是RTS和数据只经过一次传送就可以达到目的地。所以可认为节点A到达节点B成功发送第k个数据包的期望传输效率为

(3)

从源节点s到目的节点d的整个路径上的期望传输效率[8]为

(4)

当链路没有断裂且没有拥塞时,数据重传的次数少即ETX小。在路由选择时,在使用ETX参量作为判据,优先选择ETX较小的路径,可判别出当前链路质量和路径拥塞情况。此外,当其他判据相同的时候,跳数较少意味着代价更低、端到端时延更小,同时跳数也会明显影响吞吐量。而跳数越多的路径,其ETX值越高,通过引入期望传输效率ETX作为判据,还可达到选择路径较短、时延较低的路径的目的。

3.2 节点间的干扰衡量方法

802.11MAC中帧与帧之间的时间间隔称为帧间间隔(Inter Frame Space,IFS)。MAC层定义了四种不同的IFS,分别为短帧间间隔(SIFS)、集中协调功能帧间间隔(PIFS)、分布式协调功能帧间间隔(DIFS)以及扩展帧间间隔(EIFS)。使用RTS和CTS机制交互时,信道接入的帧间间隔如图1所示,帧间间隔表示了无线信道接入的优先级。

图1 使用RTS/CTS交互的信道接入方式

由上图即可看出,网络分配矢量NAV值可体现出节点周围数据流量的变化情况,反映出其他节点对本节点的干扰影响。因此,通过合适的计算方式对NAV值进行处理可以得到该节点所受干扰的程度。

在MAC帧头中的duration/ID字段中记录了数据分组需要占用信道的时间值,以此为依据可更新节点的NAV值。网络负载越重,NAV值就越大。每个节点周期性地从MAC层中获取NAV信息,通过下式计算出一段时间内的累积平均NAVC值。

(5)

已有的研究证明[9]:在NAVC与节点可用带宽BW及平均延时Delay之间有固定关系,且与用户数及通信模式无关。下式中x为NAVC值,L为平均数据包长度。

(6)

BW(L,x)=(0.0024L+0.9)-(0.0036L+1.4)x

(7)

当NAVC小于0.20时,延时较小且不受用户数影响;当NAVC大于0.65时,说明该节点已经过载,数据传输时延将大大增加,此时的时延约为NAVC达到阈值时的两倍。

NAVC衡量了邻节点之间的干扰,节点时延随NAVC变化而变化。引入路径中所有节点的平均时延和Delay_SUM为路径判断参数,路由发现的过程中,对于节点的干扰,Delay_SUM有三种处理方式: 1) 当节点的NAVC大于0.65时,该节点被标记为过载节点,在路由发现的过程中Delay值乘以2累加入Delay_SUM; 2) 当NAVC值在0.2与0.65之间时,仅增加Delay_SUM; 3)NAVC小于0.2时,该Delay值不计。

3.3 新路径选择判据构成

新路径选择判据包含三个部分: 1) 现有的空时判据; 2) 对拥塞及链路质量的衡量判据; 3) 对节点的干扰感知信息,如下所示:

α+β+γ=1

(8)

式中Cn为原有空时判据,期望传输效率ETXn倾向于选出链路质量更好的路径,平均时延和Delay_SUM信息从MAC层网络分配矢量NAV演算而来,反映了路径上节点周边环境对时延的影响。α,β及γ代表了各个因素在新判据中所占的权重,其和为1。经过反复的仿真实验,系数取值暂定α=0.3,β=0.3,γ=0.4,可得到较好的路径选择效果。

该路径选择算法不仅反映了节点传输数据所占的信道资源量,而且还反映了链路的质量及拥塞情况,同时还考虑了其他节点的干扰情况。

4 实验仿真及性能分析

使用NS2网络仿真软件对上述路径选择算法进行仿真实验,实验模拟环境设置如下[10]:在传输范围1200km×1200km的方形区域内分布了50个节点,节点在该区域内可随机移动,移动速度为50m/s,每个节点的传输半径为250km;采用udp进行数据的传输,数据包大小设为512byte。MAC层队列缓冲区是100,使用DropTail策略,无线信道采用TwoRayGround模型。通过模拟仿真,得到采用不同路径选择判据下,网络吞吐量和分组时延的仿真结果,并用Matlab绘制出对比图。图2和图3分别表示采用传统空时判据和新路径选择判据下,端到端时延和网络吞吐量的对比情况。

图2 两种路径选择判据下网络端到端时延比对图

从图2可看出,当网络中并发的业务流数量达到40的时候,数据包每一跳的平均时延开始急剧加大,但采用新路径选择算法,网络时延较采用原空时判据时时延低。图3则显示采用新路径选择算法时,网络吞吐量较采用空时判据时吞吐量高。当并发业务流数量达到60的时候,吞吐量达到最大,之后吞吐量不再增大反而减少,是因为新路径选择判据将更多的因素考虑进来,综合各方面考虑优选路径,使得更多的数据流量倾向于链路质量较好、干扰和时延较小的链路上进行传输,单节点的吞吐量虽在降低,但提高了整个系统的吞吐量。

图3 两种路径选择判据下网络平均吞吐量对比图

5 结语

本文针对HWMP路由协议中默认空时路径选择判据的不足,综合考虑多方面因素,从MAC层提取多个参数加入到新路径选择判据中,使新路由判据能更好地考虑其他节点的干扰及链路的质量,更加适应复杂多变的无线环境。并通过实验证明,新路径选择判别算法更加有助于提高网络吞吐量、降低时延,对优化mesh无线自组网的路径选择,提高网络的整体性有更加积极的作用。

[1] 方旭明,马忠建.无线Mesh网络跨层设计研究[J].数据通信,2005,4:15-18.

[2] Liu T, Liao W. On Routing in Multichannel Wireless Mesh Networks: Challenges and solutions[J]. IEEE Network,2008,22(1):13-18.

[3] De Couto D, Aguayo D, Bicket J, et al. Morris. High-throughput path metric for multi-hop wireless routing[C]//Wireless Networks,2005,11(4):419-434.

[4] Borges V C M, Curado M, Monteiro E. The impact of interference-aware routing metrics on video streaming in Wireless Mesh Networks[J]. Ad Hoc Networks,2011,9(4):652-661.

[5] 肖晓丽,张卫平,康忠毅,等.HWMP协议的路径选择参数的研究与改进.[J].计算机工程与应用,2008,44(23):107-109.

[6] 冯文江,沈嘉皓,李琳.基于负载平衡的分层无线mesh网络路由协议[J].计算机应用研究,2011,28(2):651-653.

[7] Guo C, Gip Z, Zhang Q, et al. Seamless and proactive end-to-end mobility solution for roaming across heterogeneout wireless networks[J]. IEEE Journal on Selected Areas of Communications,2005,22(5):834-848.

[8] Jain K, Padhye J, Padmanabhan V, et al. Impact of interference on multi- hop wireless network performance[C]//ACM Annual International Conference on Mobile Computing and Networking(MOBICOM),2003:66-80.

[9] 裴晓萍.HWMP路由协议的研究与仿真[D].西安:西安电子科技大学硕士研究生论文,2008:30-55.

[10] 游波,牟荣增,阎跃鹏.Linux内核中IEEE802.11s的设计与实现[J].计算机工程,2011,12(37):84-88.

Router Metric Based on HWMP Wireless Network

YU Zhi WANG Huijun XIAO Xuelu

(Wuhan Maritime Communications Research Institute, Wuhan 430250)

The router metric of hybrid wireless mesh protocol only considers the channel resource consumption, but pay no attention to other parameters of MAC layer for interference, link quality and congestion. So a new solution of router metric is proposed, which comprehensively considers various factors. The new metric will help increase the network throughput and reduce the end-to-end delay. Finaly, simulation results show that the new metric can optimize the path selection based on 802.11s and improve the overall performance of the network.

MAC layer, router metric, end-to-end delay, network throughput

2015年2月13日,

2015年3月24日

余智,女,硕士,高级工程师,研究方向:舰船通信网络系统。汪慧君,女,硕士,工程师,研究方向:舰船通信网络系统。肖雪露,女,硕士,工程师,研究方向:舰船通信网络系统。

TM933

10.3969/j.issn1672-9730.2015.08.021