无线网状网路由协议的路由判据研究与改进

刘显静，吴学智，沈钊

（1. 海军通信工程技术研究中心，武汉 430033; 2. 华中科技大学电信系, 武汉 430033）

0 引言

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

在无线Mesh网络中，高性能路由算法是保证通信网络提供高效率、高质量服务的关键技术之一，而路由判据是决定路由算法性能高低的基础。传统Ad hoc路由选择是依据跳数（hop count）来选择路由的，这种方法没有考虑信道质量问题以及多信道环境下链路的干扰等问题，所以最终难以满足无线Mesh网络在网络容量和传输性能上的要求。

1 问题分析

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

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

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

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

2.1 传统ETX算法的研究

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

如果一条链路经过k次尝试后成功传输，那么该链路的传输成功的概率S(k)为：

结合式（1）和式（2），可得出链路传输次数的数学期望即ETX。具体计算如式（3）所示。

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

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

1）链路质量因子Q

研究证明ETX能够很好的反应链路的质量，使用ETX作为链路质量标准是非常适合WMN的。为了解决路由的单一链路瓶颈问题，本文设定一个可动态配置的丢包率门限值Pd，如果当某条链路的丢包率大于Pd，那么该链路将直接被放弃，Pd可以根据当前网络的链路质量来配置。因此可以得到整条路由的Q如式（4）所示。

2）链路干扰因子I

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

I可以理解为链路与受他干扰的其他链路的信道竞争情况。显然I越小，即链路对信道的占用越少，那么其他链路可以传输的数据就越多。虽然因子I牺牲了本链路的平均传输速率，但是有利于链路e的干扰区域内可能存在的其他互不干扰的链路的传输。从无线Mesh网络的全局来讲，可以使得流量更加均匀，有利于提高网络吞吐量。由式（5）可以得到整条路由的干扰因子I，如式（6）所示。

3）节点负载因子L

在一条完整的传输路由中，若某个中间节点出现传输拥塞，那么这个节点会对整条路由的传输产生很大的负面影响。一个中间节点在收到需要转发的数据包后，会将数据包本地缓存，然后再向下一节点进行发送。若因为冲突等种种原因，连接不能建立，或数据包迟迟不能顺利到达下一节点，该节点只能将需要转发的数据包暂时保存在缓存中。

一个节点阻塞程度可以通过该节点的缓存占用来衡量。下面将提出一种使用ETX来大致估算节点缓存的变化趋势，从而可以在进行路由选择时尽量保证节点的负载均衡。

假设一条路由上有一个中间节点q，设该节点的前向链路的期望传输次数为ETXq，后向链路的期望传输次数为ETXq-1。若ETXq>ETXq-1，说明后向链路成功传输所需的重传次数更少。此时，来自上一跳节点的数据包的速率高于发往下一跳节点的数据包的速率，节点缓存的数据会越来越多，节点负载加重；若ETXq

将以上所述的三个路由判据因子统一度量化后分别得到Q'，I'，L'。具体方法为：当路由发现过程结束后，源节点一共获得了M条可选路由。以ETXd为例，这M条路由的ETXd分别为ETXd1，ETXd2，ETXd3……ETXdM，则其中一条路由K统一度量化后的链路质量因子为ETXdK'，计算如式（9）所示。用同样方法可以统一度量化路由K的干扰因子IK'和负载因子LK'，如式（10）所示。

然后即可得到本路由机制的路由判据Metric，如式（11）所示。其中α，β，γ为权重参数，满足α+β+γ=1，且α，β，γ均大于等于0。这样就可以通过配置不同的路由判据权重来适应不同的网络环境。

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

3 仿真实验和分析

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

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

图1 丢包率

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

图2 网络平均延时

图3 吞吐量

图3所示为吞吐率对比，在前15 min两个协议的吞吐率相当，此时网络瓶颈并未出现。当仿真时间超过15 min后，负载超过一定门限，网络传输开始出现瓶颈，由于Metric判据考虑了网络链路质量、节点负载均衡等因素，逐渐体现出优势，此时路由选择时将避开负载过重的路由，保持了较高的性能。

4 结束语

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

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

[2] Zhang Y, Luo JJ, Hu HL. 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.

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

[6] 彭锋华, 周学军. 海军通信需求分析理论研究[J].船电技术, 2012, 32(1): 57-59.