基于链路状态因子的无线MESH网络路由判据研究*

亓沂滨 王君珺 朱华进 刘显静

(1.海军司令部信息化部 北京 100841)(2.海军91469部队 北京 100841)

基于链路状态因子的无线MESH网络路由判据研究*

亓沂滨1王君珺2朱华进2刘显静2

(1.海军司令部信息化部 北京 100841)(2.海军91469部队 北京 100841)

针对AODV协议的跳数路径判据的不足,以传统的ETX判据为基础,将链路质量、链路干扰和节点负载等链路状态参数相结合,提出新的路径判据计算方案,通过仿真实验证明,新的路由判据计算方案的路径选择算法有助于提高网络吞吐量,降低丢包率和平均延时,对于提高网络性能是行之有效的。

无线网状网; 路由协议; 路由判据; 链路状态

Class Number TP393

1 引言

无线网状网(Wireless Mesh Network)是一种具有自组织和自愈特点的多跳宽带无线组网技术[1],可以看成是一种特殊的WLAN与Ad hoc网络的结合体,是一种由无线路由器和终端设备的静态无线网络,是Internet的无线版本[2]。无线网状网拥有比传统无线Ad hoc网络和无线局域网WLAN更高的可靠性、更高的数据吞吐率、更低的干扰及更强的扩展性等特点[3],因此它也成为了当前网络研究的热点,无线Mesh网络的军事应用前景也被十分看好。

在无线网状网中,通信网络提供高质量、高效率服务的关键技术之一是路由算法,而路由算法的性能高低取决于路由判据。传统Ad hoc路由选择是根据跳数(hop count)来选择路由,这种选路方式没有综合考虑到信道质量及多信道下的链路干扰等问题,因此难以达到无线网状网在网络容量和传输性能上的要求。

2 问题分析

跳数判据是Ad hoc网络中使用最广泛的一种路由判据,DSDV、AODV等路由协议都采用最小跳数作为路由判据[4]。跳数判据的最小权重路径是从源节点到目的节点跳数最小的路径。这种算法原理是将报文在一条路径上所经过的跳数进行简单累加。

在无线Mesh网络中最小跳数判据不太适用,原因在于最小跳数路径准则没有考虑到其下层物理信道特性的变化对MAC层接入性能的影响等因素,以及上层对QoS要求,造成所选路径无法适应底层性能的变化,也可能造成传输层的较大波动。此外,就无线信道而言,在通信期间即使链路环境没有产生变化,最优路径不一定是跳数最小的路径。在误码率相同条件下,单跳传输的距离越长,信道数据传输速率就越低,也就是说短距离的非最短路径也可能比长距离的最短路径的吞吐量传或输速率高。

目前改进的路由判据主要有ETX(期望传输次数)、ETT(期望传输时间)、ENT(有效传输数量)等[5],这些路由判据往往是针对特定路由协议设计的,本文旨在研究一种普遍适合无线Mesh网络的路由判据。

3 新的路由判据的计算方案

3.1 传统ETX算法的研究

评判一个路由协议的性能好坏,最重要的两个指标是丢包率和端到端时延[6]。丢包率很大程度上取决于链路的质量,同时节点的拥塞也可能导致某些数据包因阻塞而丢失。ETX算法中,网络中的节点每隔1s以1Mbps的速率广播探测数据包,所有的邻居节点可以通过接收这些探测数据包来计算丢包率。因此,可以通过回复消息得到前向传输丢包率df和后向传输丢包率dr。依据概率公式,可得到链路的丢包率p如式(1)所示。

p=1-(1-df)(1-dr)

(1)

假如经过k次尝试后在一条链路上传输成功,则该条链路传输成功的概率S(k)为

S(k)=pk-1×(1-p)

(2)

结合式(1)和式(2),可得出链路传输次数的数学期望ETX如式(3)所示:

(3)

ETX算法的存在两点不足: 1) ETX没有直接考虑链路的速率和节点负载; 2) ETX算法没有考虑使用相同信道传输的干扰问题[7]。为此引入综合考虑链路质量、链路干扰、节点负载均衡三个方面因素的路由度量标准。

3.2 综合路由度量标准的计算方案

1) 链路质量因子Q

研究证明期望传输次数判据能够较好地反映链路的质量,使用改进后的ETX判据作为判断链路质量好坏的标准可以适用于无线网状网[8]。为了解决单一链路传输极限问题,本文设置一个丢包率阈值Pd,Pd可动态配置,当某一条链路的丢包率大于Pd,则该条链路将被视为容量饱和而被放弃,Pd可以根据当前网络的链路质量来配置。因此可以得到一条完整路由的链路质量因子Q如式(4)所示。

(4)

2) 链路干扰因子I

定义一条链路e的干扰值Ie,Ie的算法如式(5)所示,其中k为系统可用的总信道数,Vi表示在信道i上的平均速率,Ci为信道i的最大速率。

(5)

I可以看作某条链路与受其干扰的其他链路的信道竞争情况。由上式可知I值越小,即链路占用信道的比例越小,那么其他链路可用于传输信道就越多,传输数据量越大。虽然因子I降低了本条链路的平均传输速率,但是有利于链路e的干扰区域内可能存在的其他互不干扰的链路的传输。从无线网状网的整体来看,可使整个网络流量更加均匀,有效提高网络吞吐量。根据式(5)可以得到整条路由的干扰因子I,如式(6)所示:

(6)

3) 节点负载因子L

在一条传输路径中,若某个中间节点数据处理能力达到极限就会出现传输拥塞,那么该节点会严重影响整条路由的数据传输速率。当一个中间节点收到数据包需要转发或处理时,会在本地将数据包缓存,然后再发往下一节点。如果由于网络拥塞冲突等原因,导致不能建立连接,或数据包不能顺利发送至下一节点,则该节点会将需要转发的数据包暂时缓存本地。

一个节点的缓存占用比例可以在一定程度体现该节点的拥塞程度[9]。下面将提出一种使用期望传输次数来大致估算节点缓存的占用比例,继而可以在选择路由时尽可能保证节点的负载均衡。

取某条路由上的一个中间节点q,假设该节点的下一节点路径即前向链路的期望传输次数为ETXq,上一节点路径即后向链路的期望传输次数为ETXq-1。若ETXq>ETXq-1,说明后向链路成功传输所需的重传次数更少,自后向节点发来数据包的速率大于发往前向节点的数据包的速率,数据包占用节点缓存的比例会加大,节点的负载加重;若ETXq

(7)

(8)

(9)

(10)

(11)

然后采用三个影响因子加权的方式得出本文路由策略的路由判据Meric值表达式,如式(12)所示。其中α、β、γ为权值参数,满足α+β+γ=1,且α、β、γ均大于等于0。这样就可以通过配置不同的路由判据权值来适应特定的网络环境。

(12)

源节点计算出路由判据Metric后,将优先选择Metric值最小的路径进行数据发送。

3.3 仿真实验和分析

本文使用OPNET Modeler 14.5网络仿真工具,实验环境:在1000m×1000m范围内,分布5个固定节点和20个移动节点的随机拓扑。以Random Waypoint模型模仿移动节点的固定速率随机移动,Metric参数设定α=0.5,β=γ=0.25。实验使用AODV协议,源节点业务流为CBR,数据包发送速率1Mbps,选取丢包率、吞吐量、网络延时作为统计量,仿真时间60min。

图1～图3分别对Metric判据和跳数判据的丢包率、平均延时和吞吐量进行了对比。图1可以看出前者的丢包率波动略小于后者,因为它选择了更适合的判断链路好坏的机制,这样在网络数据包的传输路径分配就更合理,不会造成局部拥塞而导致大量丢包。

图1 丢包率

在图2中可以看出采用两种判据的的网络延时对比,在初始阶段,Metric判据迟时稍微较大,因为在初期,探测链路信息的时候网络中数据包较多而且都采用的泛洪式的查找机制。在网络稳定后,采用Metric判据降低了延时。

图2 网络平均延时

图3 吞吐率

图3为吞吐率对比,在前15min两个协议的吞吐率相当,此时网络瓶颈并未出现。当仿真时间超过15min后,负载超过某一阈值,数据传输速率逐渐达到极限,由于Metric判据考虑了网络链路质量、节点负载均衡等因素,采用改进的路由判据的路径体现出一定优势,此时路由选择时将屏蔽负载过大的路径,保持了较高的性能。

4 结语

针对AODV协议的最小跳数判据的不足,本文以传统的ETX判据为基础,考虑到无线Mesh网络与Ad hoc网络的不同之处,综合链路参数因子对网络的影响,提高了网络的性能,对无线Mesh网络的进一步应用研究具有参考价值。

[1] Hossain E, Kin K L. Wireless Mesh Networks Architectures and Protocols[M]. Heidelberg: Springer Science,2008:1-4.

[2] Zhang Y, Luo J J, Hu H L. Wireless Mesh Networking: Architecture, Protocols and Standards[M]. Auerbach,2007:10-13.

[3] 秦莹莹.无线Mesh网络路由协议研究[J].软件导刊,2012(11):99-101.

[4] Yang Y, Wang J, Kravets R. Designing routing metrics for mesh networks[C]//Proc. WiMesh,2005:134-140.

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

[6] 易奇,左会军,孙徐玲,等.基于树形拓扑的无线Mesh网络路由协议研究[J].计算机工程与设计,2010,31(9):1893-1897.

[7] 汪涛,崔逊学.无线Mesh网在炮兵野战网络系统中的应用研究[J].炮兵学院学报,2010(3):110-112.

[8] 何云强,丁在田,艾宝利.基于战场通信环境多频分级移动Ad Hoc网络结构的研究[J].现代电子技术,2006(4):67-69.

[9] 杨斌,吴学智,阳昆.水面舰艇编队的无线局域网研究及构建[J].舰船电子工程,2008,28(8):27-29.

[10] 秦军,陈迪,袁翰林.无线Mesh网络中的路由分析与设计[J].计算机技术与发展,2012,22(2):90-94.

[11] 陈敏.OPNET网络仿真[M].北京:清华大学出版社,2004:98-101.

Routing Metric Based on Link State Factor of Wireless Mesh Network

QI Yibin1WANG Junjun2ZHU Huajin2LIU Xianjing2

(1. Information Department of Naval Headquarters, Beijing 100841)(2. No. 91469 Troops of PLA, Beijing 100841)

Aiming at the insufliciency of hop count metric of AODV protocol, based on traditional algorithm of ETX and combined with the parameters such as link quality, link interference and node load, a new path metric is put forward. The experimental results demonstrate that the new path selection algorithm program is helpful to improve network throughput, reduce packet loss rate and average delay, and effectively improve the network performance.

wireless mesh network, routing protocol, routing metric, link state

2013年8月11日,

2013年9月21日

亓沂滨,女,工程师,研究方向:计算机网络、导航工程。王君珺,男,工程师,研究方向:通信装备维修、计算机网络。朱华进,男,工程师,研究方向:无线通信技术、导航工程。刘显静,男,助理工程师,研究方向:通信网的组网与管理。

TP393

10.3969/j.issn1672-9730.2014.02.019