基于预留的动态机会路由算法

关学铭，齐先飞，马遥知

(沈阳工业大学辽阳分校，辽宁 辽阳 111003)

0 引 言

随着无线网络的不断发展，移动终端的种类和数量与日俱增，用户对无线网络的体验要求也不断提高，迫切需要更好的无线网络架构来提供高吞吐量、低延迟及高稳定性的网络。无线Mesh网络因其高容量、高速率、易实现及代价小等优点被各大研究机构和部门关注，被视为解决无线网络QoS的重要解决方案[1]。无线Mesh网络实现容易使其适用于较偏远的区域，同样也作为解决“最后一公里”网络问题的方案。

无线Mesh网络的路由是目前研究的热点问题，目前主要的无线Mesh路由分为以下几类：反应式路由、先应式路由、混合式路由、机会路由和基于网络编码的路由。前3种是早期网络研究成果引入无线Mesh网络，后2种是针对无线Mesh网络特点提出的路由解决方案。

机会路由是由MIT的Biswas等[2]在2004年提出来的，机会路由是无线Mesh网络路由的重要研究方向，与传统路由相比，机会路由更加充分地发挥了无线网络广播的特性，不用预先设置路由线路，而是通过竞争的方式来动态地确定数据转发节点。数据传递之前需要确定转发的候选节点，并通过对传递节点的优先级进行排序，候选节点都会接收到发送方广播的数据包，通过竞争的方式最先成功转发数据的节点就是实际转发的节点，其他节点将放弃转发该数据包，数据转发的路径也是通过这种竞争的方式动态地确定出来[3-4]。

机会路由能提高无线Mesh网络的吞吐量和可靠性，目前已经成为研究的热点。目前主要的机会路由有ExOR、SOAR及ROMER等。ExOR[5]是最早被提出的一种机会路由算法，ExOR 路由充分利用了无线信道广播的特性，通过选择距离目的节点最近的几点作为下一跳节点，ExOR使用ETX度量中间节点到目标节点的距离，从而确定候选节点的集合。ExOR路由充分发挥了无线信道的开放性，提高了数据转发的效率。但是ExOR的算法复杂性也限制了算法的性能提升，而且重复性数据的不断增加会使算法性能随之下降。SOAR[6]路由是基于ExOR的改进算法，它也使用ETX作为路由度量。它在源节点和目的节点之间建立最短路径，并通过设置EXT门限值来避免数据重复和干扰，算法将数据的传输节点集中在最短路径附近，提高了网络转发的效率。ROMER[7]是一种按照分组方式实现机会转发的路由算法。机会路由的主要研究问题大多集中在候选节点的选择上，候选节点的算法以及候选节点数量的确定是主要的热点研究问题[8-9]。

1 问题描述

随着无线网络的不断发展，移动终端的种类和数量与日俱增。在有线网络中，数据链路所受的干扰较少，数据传输的质量较高，数据的丢失率较低，一般会使用数据转发的跳数、往返时延等作为路由的度量标准来说明网络链路及转发的性能[10]。而在无线网络中是使用信道作为传输路径，这就使得传输数据过程中很容易受到干扰，信号的质量也得不到保证，很容易造成数据的丢包，因此，无线网络说明链路质量的路由度量方法与有线网络不同，一般是使用时延、误码率等作为度量标准。传统机会路由[11]有其自身的优势，但也有缺点[12-13]，研究表明使用机会路由过程中，真正负责转发的网络节点往往总是同一批候选节点，其他的候选节点很少有成功转发的机会。一直处于这种“垄断”的转发状态，可能会导致网络资源利用率低、网络负载不均衡等问题的出现。无线Mesh网络机会路由测量算法复杂度高也会给网络带来负担。无线Mesh网络机会路由算法会选择某种度量标准(如ETX、ETT等)来确定候选节点集合，并对候选节点集合进行排序，然后对数据进行转发，候选集合通过竞争的方式来争取转发的机会[14]。候选节点的确定需要转发节点对候选节点集合进行排序等操作，这将为转发节点带来额外的开销，在无线Mesh终端设备密集的区域这些开销将严重影响网络性能，特别是对服务质量要求较高的业务，这样的问题可能导致网络延迟增大、网络资源利用率下降等问题。

为了解决以上问题，本文对机会路由候选节点算法进行研究，从问题分析可知，减少候选节点数量会使候选节点选择时的系统开销降低，但是这样会降低网络转发的成功概率，增加数据重传的次数。

设机会路由发送节点(S)的候选节点个数为n，发送节点到候选节点的成功概率是p1，候选节点(C1, C2, …, Cn)转发到目标节点(D)的成功概率是p2，如图1所示。

图1 机会路由候选转发

图1所示机会转发成功的概率p为:

p=(1-(1-p1)/n)p2

从上式可知，增加候选节点数量将会使网络转发的成功概率增加，这与之前减少候选节点的方案矛盾，因此，候选节点的选择对网络的数据转发效率有重要的影响。

本文通过对传统的机会路由算法进行研究与分析，并在传统的机会路由算法基础上提出一种动态机会路由算法。算法通过预留候选节点的方式来提高转发效率，而不是去构造最优机会转发节点，通过降低选取候选节点网络开销的方式提高数据转发效率，从而提高网络的服务质量。

2 基于预留的机会路由算法

为改善传统机会路由候选节点网络负载，本文提出基于预留的动态路由算法(BRDOA)，通过减轻候选节点选择和排序复杂度，实现提高网络转发效率和网络QoS的目的。网络节点需要学习节点的一些状态信息，如候选节点变化率、时间限定t以及平均变化率的动态调整。

2.1 网络模型及算法设计

本文网络模型使用无向图G=(V,L)来表示。其中V表示网络的节点集合，vi∈V(i=1，2，…，N)表示网络中的任意节点，N为网络节点数；L表示无线Mesh网络中的链路集合，l(i，j)∈L表示vi到vj的任意链路。

网络转发节点需要维护一个时间段t内的候选节点信息，并计算出候选节点在这个时间段内的变化率，即:

αi=Δfi/fi, i=1，2，…，N

其中，fi表示第i次转发数据时候选节点数，Δfi表示第i次转发时相对上一次转发的变化节点数，αi则表示第i次转发候选节点的变化率，通过αi计算出时间t内候选节点的平均变化率，即β为：

β=(∑αx)/(j-i), x=i，i+1，…，j

通过平均变化率选出候选预留集合，在预留集合中节点的排序使用最近历史排序数据即可。但是，由于随着t设置的不同，变化率也有所不同，变化率过大，会导致预留候选集合数据过多，这样不仅不能提高网络资源利用率，还会导致历史数据对传输的影响增大。本文引入被诸多领域应用的帕累托法则来应对以上问题[15]，即20%节点决定了网络整体的转发率，因此，设置β的最大上限βmax为:βmax=20%，如果β>20%，那么就让节点自动调整时间t，缩短时间t会使传输过程减少，节点变化率也会下降，从而达到控制β上限的目的。

算法描述如下：

1. initial t;

2. fi←Candidate i;

3. fi-1←Candidate i-1;

4. αi←(fi- fi-1)/ fi

5. β←(αi+αi+1+…+αj)/(j-i)

6. Pareto principle, βmax←0.2

7. if (β>βmax) reduce t and return 1.

8. Forward

BRDOA算法依据历史转发数据以及预留节点平均变化率来确定预留节点数量，在传统机会路由算法的基础上增加了候选节点预留机制，从而降低排序带来的系统开销。

2.2 路由度量选择

节点在选择候选节点时，由路由度量确定各候选节点的优先级，选择高效的路由度量方法有助于路由转发速度的提升。ExOR采用的是EXT度量方式[16]，本文同样采用EXT[17]度量方法，BRDOA主要是对候选节点进行预约分配，对于任何的机会路由算法来说都要进行这个过程，因此，BRDOA可以在现有许多机会路由算法和度量方式基础上进行引入来提高路由算法性能，本文在ExOR和EXT基础上进行改进以实现BRDOA算法，通过仿真实验验证算法效率。

3 实验仿真

BRDOA是基于传统机会路由算法提出的机会路由算法，它与ExOR和SOAR都是通过无线网络的广播特性实现路由转发的，而且BRDOA与ExOR和SOAR一样使用EXT度量方式，因此通过对比BRDOA与ExOR及SOAR的算法性能，来判断BRDOA算法是否能够提高网络转发效率。

算法使用仿真实验验证，使用的是NS2仿真软件进行仿真，为了能够验证算法的转发效率和网络QoS特性，选取投递率、端到端延迟和吞吐量作为检验指标，将BRDOA算法与SOAR、ExOR算法进行对比。实验结果表明BRDOA的成功投递率、端到端时延和吞度量皆优于SOAR和ExOR，BRDOA算法有效地提高了网络转发效率，对网络QoS性能有所改进。结果如图2～图4所示。

图2 成功投递率对比图

图4 吞吐量对比图

4 结束语

无线Mesh网络作为无线网络的重要解决方案将被越来越多的单位和部门重视，机会路由为无线Mesh网络数据转发奠定基础，也同样会被进一步地开发，BRDOA作为一种基于预留模式的机会路由，可以提高无线Mesh网络的数据转发效率，改善无线Mesh网络的QoS，采用EXT的度量方式，使路由性能更高，本文提出的算法BRDOA通过仿真实验验证，结合无线Mesh网络具体情况，采用适当的参数设置，未来将会成为无线Mesh网络的路由转发的重要解决方案。但是，BRDOA算法也有其不足之处，算法不适用于网络空闲的无线Mesh网络中，网络数据转发量较低情况下，候选节点集合过程对网络开销影响较小，不适用BRDOA算法。