基于跨层设计的CLRM-HWMP路由协议研究

蒋纬昌,龙昭华,侯堂杰(重庆邮电大学计算机科学与技术学院,重庆 400065)



基于跨层设计的CLRM-HWMP路由协议研究

蒋纬昌,龙昭华*,侯堂杰
(重庆邮电大学计算机科学与技术学院,重庆 400065)

在研究HWMP路由协议的基础上引入跨层设计方法,综合考虑数据链路层的数据帧传输成功率DFTE(Data Frame Transmission Efficiency)、网络层的可用带宽和节点跳数作为跨层路由度量值CLRM(Cross-Layer Routing Metric),提出一种综合路由判据的跨层路由协议CLRM-HWMP路由协议。该协议有效解决单一的路由量度判据在提高无线Mesh网络性能方面的局限问题。通过NS-3仿真工具对无线Mesh网络中的HWMP路由协议和提出的CLRM-HWMP跨层路由协议进行分析对比,实验结果表明:提出的CLRM-HWMP路由协议有效降低了节点间端到端时延、提高了数据包投递成功率和网络吞吐量。

无线Mesh网络;路由判据;跨层路由度量;HWMP;CLRM-HWMP

无线Mesh网络不仅具有传统无线网络方便管理的特性,还具有自组织、容量大、成本低、冗余性好、扩展灵活的特性[1]。近年来音视频等多媒体数据业务的爆发式增长,使得原有的无线Mesh网络路由协议难以满足用户的需求。

在IEEE802.11s标准中无线Mesh网络默认采用HWMP[2]路由协议,该协议具有按需路由协议和先验式路由协议的功能。例如基于网络层的按需路由的AODV[3]路由协议是当节点需要时才开始广播消息建立网络,但是容易造成路由发现时间长和分组传输时延过大。DSDV[4]路由协议设置序列号,用序列号作为路由判据的依据,序列号大的作为优先路由,当序列号相同时以跳数少的路由作为优先路由,采用洪泛方法开销较大,带宽利用率低。OLSR[5]路由协议以网络层的参数“最小跳数”为依据,没有考虑链路的可靠程度和节点的负载程度等。

文献[6]中使用3种基于跨层设计思想的路由判据EFW(Expected Forward Counter)、MEFW(Minimum Expected Forwarding Conuter)和JEFW(Joint Expected Forwarding Counter)来处理路由节点的自私行为。EFW路由判据采用跨层设计思路,结合路由层的转发机制以及MAC层对无线链路的质量测量的结果来优化路径选择。

文献[7]中Ding等提出了一个基于跨层的机会频谱获取和动态路由算法ROSA(Routing and Dynamic Spectrun Allocation)。ROSA算法通过结合跨层设计、联合机会路由(Joint Opportunity Routing)、动态频谱分配、分布式调度、传输功率控制等方面的机制,努力将网络吞吐量最大化,同时又不对其他用户产生干扰,并且还能将数据传输的误码率控制在一定范围之内。

通过设计合适的策略能够实现无线Mesh网络中不同层次之间的跨层信息交互[8],可以避免单一层次的路由度量值带来的不足。文献[9]中提出的能量受限的路径选择和能量高效的跨层负载分配方法,就是通过利用随机动态规划技术以及MAC层和网络层的跨层交互减少了节点能量的消耗,实现了能量高效的路由协议。

本文以无线Mesh网络中默认的HWMP协议为基础,提出了基于数据链路层数据帧传输成功率、网络层的可用带宽和节点跳数作为跨层路由度量值的CLRM-HWMP路由协议。实验结果表明提出的基于跨层设计的CLRM-HWMP路由协议在平均端到端时延、平均数据包投递率和网络吞吐量方面有更好的效果。

1 跨层路由度量值CLRM的设计

由于拥塞或者数据帧的丢失,网络节点在发送数据帧之后没有收到回复的ACK或者在发送完RTS后没有收到回复CTS就会重传。MAC层每次完成传输RTS和数据的重传次数概率就反应了当前链路的质量。因此,可以将其作为选择最佳路径的重要参数。但是在选择路径时,如果只考虑这一种参数显然是不够的,选择出来的路径可能会有较远的距离即很大的跳数,这和那些信道质量较差的路径相比较性能可能更差。所以在设计无线Mesh网络的路由协议时,应当考虑多种因素,特别是要打破层的界限,综合不同层之间的参数来设计新的路由判据。基于此文中提出基于数据链路层的数据帧传输成功率、网络层的可用带宽[10]和跳数作为综合路由判据。

1.1 数据帧传输成功率DFTE

数据链路层的数据帧传输成功率将在节点向其邻居节点转发分组信息的时候更新,即对每个成功传输数据帧的重传次数计数就能通过计算得到最新的数据帧传输成功率DFTE,然后将其传递给网络层。MX-MAC同样使用了IEEE802.11标准中的管理信息库里的ACKFailureCount和RTSFailureCount,这两个参数分别表示数据帧和RTS帧的重传次数。另外,数据帧传输成功率在无线链路中的变化很快,起伏可能会很大,因此选择出的路径也可能变化很快而不是最佳路径。为避免这种情况的发生,采用类似指数加权移动平均数EWMA[11](Exponentially Weighted Moving Average)的方法,在路由表更新周期T时间内使用DFTE移动平均数,同时根据当前的网络状况为最新的DFTE和旧的平均DFTE指定不同的权重系数。

使用RTS/CTS机制时,MAC层传输的过程如图1所示。当节点1发送RTS帧请求连接从节点1到节点2的信道后,节点1会等待一个时间,这个时间是请求时间超时。如果在这个时间段之内没有收到回复的CTS帧,节点1就会重新发送RTS帧,直到收到节点2回复的CTS帧。这时候节点1就获得了一个没有冲突的信道。RTS的重传次数可以表示节点1到节点2之间信道链路的竞争程度,反映了该信道的链路质量。

图1 RTS/CTS重传机制示意图

为了计算出当前链路的数据帧传输成功率DFTE,每个节点都使用MIB变量来获得当前链路上完成一个数据帧的重传次数。假设从节点A到节点B完成传输第i个分组的重传次数为FailureAB(i),其值为式(1):

FailureAB(i)=ACKFailureCountAB(i)+RTSFailureCountAB(i)

(1)

FailureAB(i)实际上就是DATA和RTS的重传次数和,在理想状态下对于RTS和DATA应该仅有一次传输,因此从节点A到FailureAB(i)节点B的数据帧的成功传输率DFTEAB(i)可以按式(2)计算:

(2)

这个参数是DATA帧和RTS帧成功发送的概率。当重传次数越大,DFTE的值将越小;当没有发生帧丢失时,重传的次数为0,FailureAB(i)为1,即数据分组一次性被全部发送成功。另一种情况则是:若重传次数超过一定的阈值则停止发送,这个时候FailureAB(i)为0,这将减小传输成功率的移动平均值。

不使用RTS/CTS机制时,FailureAB(i)是ACK帧的重传次数ACKFailureCountAB(i),则DFTEAB(i)如式(3):

(3)

在路由表的的更新周期T时间段内,发送节点A对得到的DFTEAB(i)求EWMA值,该值反映了链路AB之间的拥塞情况及链路质量。这个平均值为式(4):

DFTEAB(i)=αi×DFTEAB(i)+(1-αi)×DFTEAB(i-1)

(4)

式中:DFTEAB(i)是发送节点在传输第i个分组时该条链路DFTE的移动平均值,αi的值取决于信道变化的速度。为了避免选出的路径变化过大,αi被设定为10%,即当前的DFTE值占权重的10%,之前的平均DFTE值占权重的90%。如果信道不稳定,可以将αi的值提到到30%或者更高。

1.2 可用带宽估算

在无线Mesh网络中,由于无线信道空间复用的特性,导致不经过相同节点的多条链路之间也会存在干扰,相互竞争带宽资源。无线信道的冲突竞争和易受干扰的特性带来了挑战,其中一个挑战是节点I在网络层的参数可用带宽Bavailable(I)。由于邻居节点同时存在进行数据传输的干扰,其实际消耗的带宽远大于其所需要的带宽。因此,在考虑路由判据因素时,也要充分考虑网络的可用带宽。节点I所在信道的总的业务Bagg(I)由式(5)所示的三部分的和组成。

Bagg(I)=Bself(I)+Bneighbor(I)+Bboundary(I)

(5)

式中:Bself(I)表示节点I与其邻居节点间的业务占用带宽,Bneighbor(I)表示节点I的邻居节点间业务占用带宽,Bboundary(I)表示节点I的非邻居节点与I的邻居节点间业务占用带宽。由上可知,节点I的的可用带宽Bavailable(I)则可表示如下式(6)。

(6)

由式(6)可以看出,如果想要求得节点I的可用带宽Bavilable(I),则必须先求得其与邻居节点间业务已经占用的带宽。大多数算法采用发送HELLO分组的方式进行带宽估计,这样的方式大大消耗了网络资源,鉴于此,本文并不采用这种方式,而是利用MAC协议的能力实现估算。无线网络中,节点所在信道空闲的时间由该节点和所有邻居节点的业务量共同决定,信道空闲预示着节点能够传输数据。因此,信道空闲也就说明带宽可用,空闲时间的长短间接反应节点传输数据能力的强弱。所以,可用式(7)计算节点可用带宽。

(7)

式中:Tinteral表示时间间隔,Tidle表示在Tinteral时间段内信道的空闲时间。根据式(7),Bavilable(I)的估算主要取决于Tidle的计算。

由于CSMA载波监听机制[12]能够判断当前信道是否空闲,因此,借助该机制可以进行网络空闲时间的估算。载波监听分为两种:一种方式是虚拟方式,另一种方式是物理方式。其中物理层提供了物理载波监听机制,MAC层提供了虚拟载波监听机制,两种监听方式中如果有任何一种方式判定信道忙,则认为该信道处于忙的状态,继续监听。假设在单位时间间隔内,检测到信道忙的时间为Tbusy,则Tidle可以用式(8)进行计算。

Tidle=Tinteral-Tbusy

(8)

将式(8)代入式(7)就可以看出,节点可用带宽的估算结果是否精确主要在于观察时间间隔的选取。当选取的时间间隔过大时,则不能很好的反应带宽变化的实时性,选取过小时,无法获得精确的信息。针对此问题本文将带宽的计算公式进行如式(9)的改进,改进的主要目的在于计算当前时刻的可用带宽时,必须考虑上一时刻的观察值,进而体现带宽的动态特性。

Bavilable=Bt×∂+Bt-interal×(1-∂),0≤∂≤1

(9)

实验证明,∂取0.8,Tinteral取0.3比较合适。结合式(7)～式(9)很容易得出节点当前可用带宽。

1.3 跳数度量计算

在路由协议的判据因素中,跳数作为一个重要的参数被很多路由协议采用,其具有简单性也能控制网络规模大小。如果从发送节点A到目的节点B是一个多跳路径,DFTEAB则由当前链路上的DFTEXY相乘得到,X、Y是指链路之间每一跳的两个相邻节点。为了避免选择到一条跳数太大的链路则必须将跳数这一参数考虑进去,跳数记为HopMetricAB如式(10)所示:

(10)

式中:HopMetricAB反映了从发送节点A到目的节点B的最小跳数,该参数用作最后度量值的重要一部分,NodeNum是网络中节点的最大数,HopCountAB是当前链路的跳数。从式(10)可以看出,链路的跳数越大,则参数HopMetricAB则会越小。

最终的跨层路由度量值CLRM如式(11)所示:

CLRMAB=DFTEAB×Bavilable×HopMetricAB

(11)

式(10)代入式(11)得式(12):

(12)

在HWMP协议中默认采用时空链路度量[13]Ca作为路由度量值,公式如(13)所示:

(13)

式中:Oca表示信道接入负载,OP表示MAC协议负载,Bt表示测试帧中的比特数,并且这3个参数都是常量,r是传输比特率,单位是Mbit/s,efr表示帧错误率。可以看出HWMP协议的路由判据主要由r和efr来确定。

对比式(12)和式(13)可以看出,新的路由度量值CLRMAB综合考虑数据帧传输成功率、可用带宽和跳数等不同层的因素,且包含HWMP协议中的路由判据因素,其路由度量值不再由单一的因素决定,这样可以避免单一路由度量值带来的不足。

2 仿真与性能分析

本文通过仿真实验对提出的CLRM-HWMP跨层路由协议进行分析对比。仿真实验平台采用Ubutu14.01下的NS-3网络仿真软件,在平均端到端的时延、网络吞吐量和数据包成功投递率3个方面与HWMP路由协议进行分析对比。

在仿真实验中,根据无线网络的特性,设置在2 000m×2 000m的范围内,产生50个节点的随机拓扑。节点配置Single-radio单接口,传输域为200m,侦听范围[14]400m。采用UDP数据流,数据包大小为512byte。

图2为数据包的端到端时延随着网络中数据流增加的变化情况。由图所示,两种路由协议的端到端延时均随着网络流量的增加而增加,因为当网络流量增大时,网络的负载增加,导致冲突的可能性也急剧增大,然而由于CLRM-HWMP路由协议中的路由判据充分考虑了链路质量这一因素,因此该协议可以选择链路质量更优的路径从而避开拥塞路径,降低了端到端时延。

图2 平均端到端时延

图3为网络中数据包投递率随着网络流量增大的变化情况。由图所示,随着网络流量的增加,数据包的成功投递率都随之降低,这是因为流量的增加导致网络中数据冲突增加,致使数据包的投递率也随之下降。但是改进的协议的数据包投递率明显高于原有的协议,这是因为优化的MX-MAC协议中增加了退避机制,有效降低了移动节点之间的冲突,使得CLRM-HWMP协议的成功投递率要高于HWMP。

图3 数据包投递成功率

图4为网络吞吐量随着负载增加的变化趋势。随着网络中数据流的增加,网络吞吐量也随之增大,当吞吐量达到峰值时,网络中的数据包冲突的增加将导致网络吞吐量的下降。从图4可以看出,改进的协议吞吐量较HWMP协议较高,这一方面是因为CLRM-HWMP降低了网络中的数据包的冲突,另一方面是因为优化的CLRM路由判据选择了更优的路径,使得网络系统更加高效。

图4 网络吞吐量

3 总结

该文分析了传统的单一度量值的无线Mesh网络路由HWMP协议和基于跨层的CLRM-HWMP路由协议,通过在平均端到端时延、平均数据包投递率和网络吞吐量这3个方面进行仿真分析对比。仿真实验结果表明该文提出的CLRM-HWMP路由协议较HWMP路由协议有良好的表现。这也充分说明了基于跨层的和多种因素设计的路由协议能够有效的提升网络的性能。

[1] 王继红,石文孝. 无线Mesh网络负载与干扰感知传输时间路由度量[J]. 吉林大学学报(工学版),2015(1):297-303.

[2] 龙昭华,侯彦强,张林. 基于HWMP协议的路径选择判据研究[J]. 计算机工程与设计,2013(3):791-794.

[3] 梁建武,马晓亮,徐龙龙. 移动Ad Hoc网络AODV路由协议的研究与优化[J]. 重庆大学学报,2015(4):152-158.

[4] 吴全玉,孙怡宁. 井下无线传感器网络AODV和DSDV协议的仿真对比[J]. 传感技术学报,2009,22(10):1515-1518.

[5] 李杨,刘航,郭达伟,等. 基于跨层快速邻居感知的OLSR协议[J]. 传感技术学报,2012,25(1):99-103.

[6] 王福生. 基于无线网状网的AODV路由协议研究与改进[D]. 长春:吉林大学,2013.

[7] Ding L,Melodia T,Batalama S,et al. ROSA:Distributed Joint Routing and Dynamic Spectrum Allocation in Cognitive Radio Ad Hoc Networks[C]//ACM International Conference on Modeling,Analysis and Simulation of Wireless and Mobile Systems. ACM,2009:13-20.

[8] 任鹏,张剑英,冯小龙. 能耗均衡的煤矿井下巷道WSN跨层路由协议[J]. 煤炭学报,2016(2):522-530.

[9] 肖萍. 一种能量高效的无线Ad Hoc网络跨层协议的研究[D]. 长春:吉林大学,2011.

[10] 余燕平,倪玲玲,郑元琰. 无线自组织网络中带宽约束的分布式按需组播路由协议(英文)[J]. Journal of Southeast University(English Edition),2015(1):5-11.

[11] 李柏楠,钱叶魁,罗兴国. 基于往返时延矩阵子空间的网络异常检测方法[J]. 南京理工大学学报,2015,39(2):215-224.

[12] 罗震钧,张颖江,钟珞,等. 无线传感器网络中基于贝叶斯可变频的CSMA/CA算法研究[J]. 传感技术学报,2014,27(9):1269-1274.

[13] 江晓力,陈兵. 一种具有负载均衡功能的多网关路由协议LBMP_HWMP[J]. 小型微型计算机系统,2014,12:2608-2611.

[14] Xu K,Gerla M,Bae S. How Effective is the IEEE802.11 RTS/CTS Handshake in Ad Hoc Networks[C]//Global Telecommunications Conference,2002(1):72-76.

蒋纬昌(1989-),男,河南南阳人,硕士研究生,CCF学生会员,主要研究方向为无线传感器网络、无线Mesh网络,jiangwc_ny@163.com;

龙昭华(1962-),男,贵州遵义人,硕士生导师,教授,CCF会员,主要研究方向为网络通信与嵌入式系统,longzha@cqupt.edu.cn。

The Research of CLRM-HWMP Routing Protocol Based on Cross-Layer Design

JIANG Weichang,LONG Zhaohua*,HOU Tangjie
(College of Computer Science and Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

Based on the research HWMP routing protocol on the introduction of cross-layer design approach,proposed an integrated cross-layer routing metric routing protocol CLRM-HWMP. Considering the success rate of the data frame transmission DFTE(Data Frame Transmission Efficiency)in data link layer,available bandwidth and the number of hops in network layer as a cross-layer routing metric(Cross-layer Routing Metric,CLRM),this method is effective to solve a single routing metric criterion confined to raise the issue in the wireless Mesh network performance.By NS-3 simulation software for wireless Mesh network routing protocols and HWMP CLRM-HWMP proposed cross-layer routing protocol analysis and comparison of experimental results show that:the proposed CLRM-HWMP routing protocol effectively reduces the end to end delay between nodes,improves the packet delivery success rate and network throughput.

wireless mesh network;routing metric;cross-layer routing metric;HWMP;CLRM-HWMP

2016-06-16 修改日期:2016-12-17

TP393

A

1004-1699(2017)04-0587-05

C:6150P

10.3969/j.issn.1004-1699.2017.04.018