无线Mesh网络机会路由技术研究

李锋，沈崧

（中国航天科工集团第二研究院七〇六所 北京　100085）

无线Mesh网络机会路由技术研究

李锋，沈崧

（中国航天科工集团第二研究院七〇六所 北京100085）

文章介绍了无线Mesh网络的特点和机会路由的原理，分析了ExOR的优缺点，针对其没有考虑路由路径中转发节点自身的因素，过度使用最优路径而导致网络局部拥塞的问题，提出了路由节点能力评估模型，结合原有路径度量方法，构成新的路由度量。并引入参数限制候选转发节点的个数，避免数据进入质量较差的路径。仿真实验表明，新的机会路由方案，能够较好地实现网络负载均衡，数据吞吐量和网络利用率都有所提升。

无线Mesh网络；机会路由；路由度量；负载均衡

无线Mesh网络 （Wireless Mesh Network，WMN）［1］，又称“无线网状网”、“无线网格网”，是一种具有自组织、多跳、多点分布的新型无线宽带接入网络。无线网状网极其广泛，可以应用于偏远地区的宽带接入、网络语音通讯，政府机构、学校、企事业单位的无线宽带接入，远程医疗、安全监控、交通监测、数字城市、军队战场通讯系统等各个方面。路由技术作为WMN的关键技术之一，是目前国内外研究的热点问题。本文研究的机会路由［2］是由麻省理工大学的研究者提出的，机会路由是一种多路径路由［3］，与传统路由相比它没有固定的传输路径，通过多个中继节点相互合作进行通信，充分利用无线广播的特性，大大提高了端到端的数据吞吐量和网络资源的利用率。然而无线链路质量随距离增加而下降，且易受临近无线链路的干扰。因此在设计路由度量的时候，我们因该考虑到链路质量的因素。另外过度使用最优路径可能导致网络局部拥塞，严重影响网络资源的均衡性。文中以此为出发点，参考现有的ExOR协议［4］，设计了一种新的路由度量。

1　无线Mesh网络及其特点优势

无线Mesh网络中的节点通常包括移动用户、无线Mesh路由器和网关［5］。移动用户通过无线技术接入无线Mesh路由器，不同于传统无线网络的单点AP（Access Point）接入，WMN中的移动用户也可以为其他客户端转发数据。多个无线Mesh路由器可以构成WMN骨干网［6］，无线Mesh路由器相互协同工作，数据经过它们之间的合作多跳转发，在网内来回传递或穿过网关实现与Internet的通信。从而为移动用户提供了类似“最后一英里”的骨干网接入环境，也称为“Mesh云”。Mesh网具有可靠性和冗余性，当其中的一些节点停止工作，其它节点可以选择别的路径继续通信，从而保证整个网络的运行。Mesh网也可以兼容多种通信技术，如802.11，802.15，802.16，蜂窝无线网技术等。

WMN具有下列优势：快速部署和易于安装、非视距传输（NLOS）、健壮性、结构灵活、高带宽。

2　机会路由

由麻省理工大学研究者提出的机会路由策略，是一种用于无线多跳网络的路由协议，其从源节点到目的节点发送的数据包并不是按一条固定的最佳路径传输，而是充分利用无线网络的广播传输特性，每次数据包都转发给一组节点，这些节点根据它们到目的节点的度量（Metric）来确定它们优先级，优先级高的节点，优先转发数据包给另外一组节点，如此重复直到目的节点。

图1列举了机会路由的两个典型例子，来说明机会路由的优点，假设各链路独立，各链路正确传输报文的概率已在图中标明。在图1（a）中，传统的单路径路由会选择S→B→D的传输路径，一个数据包从S到D的成功传递概率为50% *100%=50%，成功送达一个数据包平均需要传输1/0.5+1=3次，而机会路由则同时利用A、B、C作为中继，一个数据包从S到D的传递成功率为：［1-（1-0.5）3］*100%=87.5%，其中（1-0.5）3为A、B、C都没有收到S发送的数据的概率。因此成功传递所需次数为1/［1-（1-0.5）3］+1=2.143。机会路由比传统的但路径路由的成功传递率更高，所需的平均传递次数更少，因而能大大提高数据的吞吐量。图1（b），传统路由中按照路由表逐次传递数据，而忽略目的节点有一定的概率直接接收到数据，使得资源利用率较低。而机会路由则可以避免这方面的不足，提高数据传输效率。

图1　机会路由典型示例Fig.1　Typical example of opportunistic routing

ExOR（Extremely Opportunistic Routing）协议是一种基于端到端最短路径策略的机会路由协议，它的路由度量为ETX端到端的期望传输次数（expected transmission count），其主要工作原理：源节点向目的节点转发数据时，首先根据每个候选节点的ETX的排序来选择转发节点。候选集中的转发节点也根据自身的ETX大小来给自己编排优先级别号。当候选集中的节点收到上游节点的广播数据分组时，优先级最高的那个节点则自动进行数据分组的转发，同时发送通知信息给其他候选节点，其他候选节点侦听到通知信息则放弃发送同一分组信息，转而发送其他信息分组和优先级搞的节点未能发送的分组，依次发送，直到目的节点接收到大部分的分组数据为止。

影响机会路由的关键因素有两点：其一，如何选择转发节点，在无线Mesh网络中，也就是设计合适的路由度量的问题；其二，如何协调候选转发节点，使其不会发生冲突，顺利的转发报文。本文参考基于端到端策略的ExOR协议，考虑链路质量度对数据路由的影响，以及网络资源均衡的问题，提出了一种改进的路由度量。

3　基于ExOR协议的路由度量的改进

3.1总体设计思路

基于端到端的最短路径策略的ExOR协议是一种有效的简单机会路由协议，它充分利用的广播传输的特性，通过节点间的协作，能够提高数据的传输效率，保证传输的稳定性，但是却无法做到全局最优，过度使用最优路径反而带来网络的局部拥塞，严重影响网络资源的均衡性。

ExOR协议的路由度量为端到端的期望传输次数ETX，源节点向目的节点转发数据时，根据每个候选节点的ETX的排序来选择转发节点。但是这种算法却没有考虑路由节点自身是否满足条件就强制转发，常使得数据偏离到链路质量较差路径上，另外候选节点过多而混入质量较差的节点，也可能使得数据进入链路质量较差的传输路径，从而导致重传的可能性变大，数据延时加大，甚至数据丢失。

为了减轻最优路径的负担，防止网络拥塞，本文建立了一种链路节能力评估模型，将节点能力和ETX相结合作为一种新的路由度量，这样降低负载过重的节点的能力，减轻其负担，以此达到网络资源均衡的目的。针对候选节点过多而造成的问题，引入EAX来限制候选节点集的大小。这里的EAX（期望任意路径传输数）指数据发端到终端所有可能的路径的ETX的加权平均。这种改进的机会路由协议是一种基于ExOR协议的改进，本文称其为EExOR协议（Extention of Extremely Opportunistic Routing）。

3.2EExOR协议路由度量模型

新的路由度量，同时考虑链路质量和节点能力的因素，其中链路质量仍由源节点通过候选节点到达目的节点的期望传输次数（ETX）表示。在本文的节点能力评估模型中，引入环境属性，既包含节点资源，又包含消息属性。融入此消彼长的因素，随着节点负载过重，降低其对外能力，限制转发数据流量，实现自我保护，以达到网络资源均衡的目的。

3.2.1前提假设

参考Mesh网络现有的各种协议，文中做出以下假设：

1）节点是无私的，会尽自己的能力转发数据。

2）当节点资源紧缺时，通过降低自身对外的能力，实现自我保护，减少局部拥塞。

3）数据包的发送过程中节点与节点之间的投递率保持稳定不变，与此同时，同一节点与不同邻居节点之间的链路始终保持统计独立。

4）文中讨论的Mesh网络都是有源或可充电的，不涉及能耗问题。

3.2.2网络模型

本文中的网络模型以无向图图来G=（V，L，D）表示来表示。V为网络中节点集合，节点数为N=［V］，Vi∈V（i=1，2，…，N）表示网络中的任意节点，N个节点随机分布于一个给定的区域内。L是节点间链路集合的表示，D则是节点间的投递率集合的表示，其中l（i，j）∈L为任意两个节点间的链路，并且其对应的投递率为d（i，j）∈D，它表示一个数据包经节点Vi的一次传输成功到达节点Vj的概率。节点间的投递率可以通过洪泛的方式来获取。

3.2.3环境属性设计

候选节点的选取是机会路由中两个关键点之一，它决定着整个网络的性能优劣，是与整体设计思路密切相关的重要因素。也影响到基于端到端路径的策略是否能够选取全局最优解的问题。因此根据实际环境，获取最有效的路由度量标准更为关键。EExOR协议中的环境属性包含两个因素：消息属性和节点资源。

消息的属性包括消息的大小l和剩余时间TTL。消息的大小即为消息本身占缓存区的大小。而TTL预示着消息消亡前的剩余时间。这意味着消息在网络中存在时间越长，那么它的传输就越紧迫。

节点资源主要参考因素为缓存空间。缓存空间是路由节点本身存储信息能力的资源体现，决定着信息转发等待时间的长短。定义缓存空间为剩余存储容量空闲百分比，其公式定义如下

其中Bsi和Buf分别为剩余存储空间和总的存储容量。Bi则是缓存区的空闲百分比。很明显节点空闲缓存区越大，其承载数据传输的能力就越大。

3.2.4节点能力评估

文中设计的EExOR协议中，由于节点是无私的，会尽自己的能力转发数据，评估节点对外数据转发能力时，需考虑自身现有资源，做出合适的能力评估，另外网络中数据包受其生存时间的限制，有时急需转发，因而评估节点能力也应该到消息的属性。定义节点能力参数如下：

这里l表示需要传递消息的大小，Bi表示节点i的缓存区空闲百分比，Tres和Tttl分别表示消息的剩余TTL和消息的原始的TTL。α和β分别是Bi和TTL的权值，并且α+β=1。因此0≤Ci≤1。

从上式可以看出，节点能力越高，其转发数据的愿望就越高，相反的，愿望就越低。节点的空闲缓存区越小，其转发数据的愿望就越小，更多的考虑自身数据处理要求；消息在节点缓存区滞留时间越长，对下一节点转发愿望的影响就越大，消息得到转发的可能性就越高。这样消息得到转发，节点的空闲缓存就变大了，就能满足更多的数据转发的请求。综上，节点总是尽自己的能力转发数据，同时又能平衡消息的迫切性。

3.2.5路由度量选路

节点在选择候选节点时，由路由度量确定各候选节点的优先级，本文设计的路由度量由ETX和节点能力参数Ci通过线性耦合共同确定，路由节点优先级定义如下：

式（3）中ETX为源节点通过候选节点i到达目的节点的期望传输次数，ETX的计算参见3.1节中ExOR协议。数据到达目的节点的路径越短，候选节点的ETX越小，Pi越小，候选节点i优先级越高。上式中Ci为候选节点的能力值，Ci越大，Pi越小，候选节点i优先级越高。在选择候选节点时，由EAX限制候选节点集的大小，选择优先级高的节点作为候选节点。这里EAX（期望任意路径传输数）指数据发端到终端所有可能的路径的ETX的加权平均。

综上，EExOR协议在路由选路和候选节点的选择过程中，既考虑了链路质量的因素，又考虑到节点自身能力。而在节点能力评估模型中也很好的平衡了节点资源和消息属性对节点能力的影响。在EExOR协议中生存时间越短的消息，能够得到更快的转发，如此能够减少数据丢失，提高传输效率。当节点负载过重时，通过调整自身能力值，较少数据流量，实现网络的负载平衡，减少拥塞，提高网络的吞吐量。

4　仿真验证与性能分析

文中采用NS2仿真软件在Linux操作系统下进行仿真。选取无线网络最常用的3个指标：网络端到端的成功投递率、端到端平均延迟和吞吐量。

消息的产生率能够反映这个网络的负载拥塞状态，产生率越大，整个网络的传输压力越大，每个节点的缓存空间就越拥挤。如图2所示，ExOR和EExOR协议随着产生率的增加，成功投递率都有所减少。在相同的消息产生率下，EExOR协议的成功投递率明显比ExOR协议的高。

图2　成功投递率Fig.2　Successfully delivery rate

如图3所示，整体来看，EExOR协议比ExOR协议的网络平均延时短，其原因在于EExOR协议中，节点根据自身负载和消息属性调整自身能力，使得网络负载均衡性更高，且生存时间短的消息会得到优先转发。拥塞少了，消息时延也就越小。

从图4中可以看出，EExOR和ExOR分别随着产生率的增加而趋于平缓。从图中的整体趋势来看，EExOR的吞吐量要高于ExOR，说明EExOR协议的网络局部拥塞更少了，网络资源的均衡性得到了提高。

仿真实验表明，相比于ExOR协议，EExOR在成功投递率、传输时延和吞吐量这3个性能指标上都有所提升。

5　结　论

Mesh网络具有重要的理论价值和广泛的应用前景，它是当今无线网络领域的研究热点。本文通过研究Mesh网络的机会路由协议，提出了基于ExOR协议的改进方案。设计了一种节点能力评估模型，结合原有的路由度量ETX，能够更好地选择机会路由中数据转发的候选节点，同时引入EAX限制候选节点个数。新的EExOR协议能够较好地实现网络负载均衡，提高了数据的吞吐量和网络的利用率。

图3　平均时延Fig.3　The average time delay

图4　端到端吞吐量Fig.4　The throughput from end to end

［1］Steve Methley.无线Mesh网络基础［M］.王平，李颖哲，黄飞，译.西安：西安交通大学出版社，2012.

［2］王梦莹.无线Mesh网络的改进研究［D］.南京：南京邮电大学，2013.

［3］Brunoa R，Nurchis M.Survey on diversity-based routing in wireless mesh networks：challenges and solution［J］.Computer Communications，2010，33（3）：268-282

［4］ExOR:Opportunistic Multi-Hop Routing for Wireless Networks，Sanjit Biswas，Robert Morris，Presented at SIGCOMM′05，2005，Copyright ACM，Philadelphia，Penn.2005，ACM No. 1-59593-009-4/05/0008.

［5］IEEE 802.11s.IEEE amendment:mesh networking.IEEE P802.11s/D1.06，2007，Piscataway.

［6］郑彦光，徐平平，常瑞.无线Mesh网络技术及其应用［J］.电力系统通信，2007，28（177）:1-2.

The study of opportunistic routing for wireless mesh networks

LI Feng，SHEN Song
（Second Academy of China Aerospace Science and Industry Corporation，Beijing 100854，China）

This paperintroduces the character of wireless Mesh networks and the principle of opportunistic routing，analyzed the advantages and disadvantages of ExOR.The ExOR protocol ignores the ability of routing nodes during data transmision and excessive uses of the optimal path which leads to local network congestion problem.To solve these problems the routing node capability assessment model is put forward，and forms a new routing metric combining the original path measurement method. And we introduce a parameter to limit the candidate number of routing nodes，to avoid the data into the path of poor quality. The simulation experiments shows that the new routing scheme can well realize the network load balance，improve data throughput network utilization.

wireless Mesh networks；opportunistic routing；routing metric；load balance

TP393

A

1674－6236（2016）05-0058-04

2015-04-18稿件编号：201504194

李 锋（1990—），男，湖南永顺人，硕士研究生。研究方向：计算机系统结构。