移动自组织网络中基于链路预测的多路径路由协议研究

黄钱飞万 俊邱海燕

(1.江西现代职业技术学院，江西 南昌 330000；2.重庆邮电大学，重庆 404100)

1.引言

移动自组织网络(MANET)[1]是由多个具有收发功能的移动终端组成的一个多跳的网络。它不像传统的无线网络需要固定的基础通信设施，也没有控制节点，抗毁灭性非常强，适合于许多网络布线困难的环境。随着该类网络的发展，像多媒体实时业务以及大流量的视频业务也开始在该类网络上应用，然而移动自组织网络自身带宽以及延时方面的局限性也成为了该类业务发展的瓶颈，本文将从多路径并发路由协议着手解决这些业务瓶颈。

2.AOMDV协议

AOMDV[2]是按需多路径距离矢量路由协议，是在AODV单路径路由协议的基础上扩展的多路径路由协议，因此保留了AODV的许多特性，两者最主要的区别在于AOMDV在路由发现过程中建立了多条可用的路径。因此AOMDV在移动自组织网络中有较强的适应性和较好的可扩展性。

3.AOMDV路由改进及实现

3.1 改进思路

目前AOMDV路由协议仍有不足之处：第一，AOMDV路由协议中使用最短路径作为路径选择的依据，但是在移动自组织网络中节点运动频繁，网络拓扑变化快，链路断链的可能性大大增加，显然最短路径的稳定度不足，路径断链的肯定性也增加了；第二，AOMDV使用一条路径作为主路径，其他路径作为备用路径，然而当主路径失效的时候，才使用备用的路径，但是在移动自组织网络的拓扑变化快，可能当主路径失效后切换到备用路径时，备用路径已经失效，从而增加了端到端的时延；第三，AOMDV只使用一条主路径进行数据传输，不能满足大数据量业务的需求。本文针对以上不足之处，提出了AOMDV-SPC路由协议进行了以下两点改进：

(1)在路径选择时，选择路径稳定性高的路径进行数据传输，可以降低数据转发期间路径中断的概率，减小网络重建和修复开销、提高网络的性能。

(2)提出了多条路径并行传输的数据传输机制，充分利用网络资源，并使用基于路径持续时间的流量分配机制。

3.2 改进协议描述

3.2.1 算法模型

根据Two Ray Ground Reflection无线传播模型来计算链路危险阈值，设定链路危险阈值功率Pthreshold，如图1所示，在图中节点b以vmax的相对速度移动，虚线圆表示路径危险的无线覆盖范围d，当节点a在虚线圆与实线圆之间时表示链路处于危险状态，而链路危险阈值功率Pthreshold为图中虚线圆的接收到的节点a的功率。

图1 链路危险阈值模型

常用的WaveLAN的无线网卡的最低接收的功率和无线传输半径的取值分别为3.65×10-10W和250m。设定节点最大速度为vmax，路由警告分组或错误分组在移动自组织网络中传输的最久时间为tmax，则危险阈值Pthreshold是当两节点间在相距(250－vmax×tmax)M时的接收到的功率，可以得到公式：

在网络中的某个节点接收到的分组的能量小于某一危险阈值，节点就需要启动链路持续时间预测机制来预测该节点与前驱节点链路的持续时间。所以危险阈值直接关系到是否启动预测机制。在链路持续时间预测机制中，节点路由表中保存三组前驱值，即在最近三个时刻t1、t2、t3时刻接收到的三个前驱节点数据的能量值P1、P2、P3，当收到新的分组时需要更新以上数据。假定网络中两个可以直接通信的节点A、B，设A为B的前驱节点，PAB(current)表示节点B当前接收到前驱节点A的分组信号的能量值，PAB(ave)表示为节点B的最近三次接收到节点A的分组信号的能量值的平均值，用△PAB表示节点B接收到的分组的能量变化率：

如果△PAB大于0时，说明节点B接收到节点A的能量在增强，不用考虑进入危险状态，如果△PAB小于0时，说明节点的节点B接收到节点A的能量在减弱，通过以下公式计算链路持续时间tLC的值：

设路径持续时间为PSF，定义为路径中所有链路的持续时间的最小值。

3.2.2 协议实现

AOMDV-SPC的路由发现过程是在AOMDV路由协议的基础上扩展的，在RREQ RREP分组以及路由表结构在加入路径持续时间因子PSF，RREQ具体更改如表1：

表1 RREQ分组结构

当源节点需要发送数据给目的节点时：源节点查看自己的路由表中是否包含到达目的节点的路由，如果有就根据路径稳定因子选择一组路径进行传输，没有的话就启动路由发现过程，在全网洪泛改进后的RREQ分组，当某个节点i接收到RREQ分组时，就根据分组来创建或更新到源节点的反向路由，特别是会根据RREQ分组更新反向路由中的路径持续时间因子PSF，节点i判断是否有到目的节点的有效路由，如果存在就回复源节点RREP分组，若不存在就判断节点是否收到过相同的RREQ分组，若收到则不转发，若未收到则继续广播路径持续时间因子PSF更新后的RREQ分组。当目的节点或还有到目的节点路径的中间节点收到RREQ分组时，目的节点回复RREQ时，路径稳定因子初始化为1，如果是中间节点回复RREQ分组，则分组的路径持续时间因子PSF为中间节点到目的节点路径的路径持续时间因子PSF。当节点收到RREQ，确定节点i是否有到目的节点的前向路由表项，如果有则根据路由更新规则创建和更新前向路径并更新前向路径的路径持续时间因子PSF，如果没有就创建路由表项并添加和更新前向路径并更新路径持续时间因子PSF。

4.数据发送及流量分配

在多路径并行传送数据时应该考虑如何将数据分组以合理的方式分配到不同的路径中去，充分利用网络资源，选择合理的数据颗粒度能够提高网络数据分组分发效率。本文采用基于每分组分配粒度方式[4]。

与AOMDV协议中采用的备用路由的数据发送方式不同，AOMDV-SPC协议采用的是在不同路径上同时发送数据，在AOMDV-SPC路由协议中主要分两种情况进行数据的发送：

(1)当发送的是多种不同类型业务时，AOMDV-SPC协议采用不同的传输路径发送不同的业务流量。

(2)当发送的某一种业务流量很大、某一条链路不能够满足其业务需求时，AOMDV-SPC协议使用不用路径同时发送该业务的流量。

情况一中，当数据分组从源节点的应用层传到路由层时，协议根据分组中的IP头的ToS（type of service）字段对分组进行分类，我们可以把流量类型分为两类，一类是尽力而为的数据业务，另一类是对流量需求较大的实时业务。根据相关的多路径路由的文献[5，6]，多路径的数目不是越多越好，因为随着路径的增加，路由开销增加较大。本文中选取的是最大路径数目是3条。因此，当源节点有分组需要发送时，如果是实时业务分组，则从路由列表中选择路径稳定因子较高的路径进行发送，而尽力而为的数据业务则用路径稳定因子较小的路径进行发送。

每条路径上需要分配多少数据流量，主要根据数据流量的实际大小和业务类型。像数据量小的业务如果采用多路径传输就显得不合适了，可以选择一条路径稳定度高的路径进行传输，这样降低整个网络的路由开销，提高路径的使用效率。由于小的数据流只使用一条路径传输而其他的链路就可以更多的传输其它的数据流，从而提高网络利用率。针对数据流量较大的业务，将一个很大的数据流量分成小块，然后再分配到多条路径上进行传输，可以明显的降低端到端的延时，增加网络的吞吐量。我们需要确定每条路径需要分配多少的流量。

本文采用路径稳定度权值分配流量，同时需要避免稳定度大的路径分配流量过大，稳定度小的路径分配流量过小，下面给出了每条路径流量分配的公式，fk为路径k上的流量，F为总流量：

5.仿真结果及分析

本文模拟环境采用自由空间移动模型，网络节点随机分布在1000*1000的矩形范围内。所有节点的无线传输半径为250m，网络中的路由请求和相应的目的节点随机产生，各节点发送缓存长度为50个分组，每个分组是512字节的长度，实验使用CBR流作为数据源，使用IEEE802.11的DCF作为媒体接入控制协议，通过暂停时间来设定网络的移动性，节点的移动速度为2-20m/s。

图2 不同数据分组发送速率下的吞吐量

图3 不同数据发送速率下的端到端延时

图2、图3、图4中分别给出了改进后协议AOMDV-SPC在不同数据发送速率下的吞吐量、端到端延时以及分组到达率，从图中可以看出改进后协议AOMDV-SPC在CBR不断增加过程中，吞吐量一直高于AOMDV、AODV，端到端延时一直低于AOMDV、AODV，分组到达率一直高于AOMDV、AODV，这是由于AOMDV-SPC协议中源节点到目的节点采用的是3条路径并行传输方式，在带宽方面充分保证了数据传输，充分利用了网络传输资源，降低了某些路径的拥塞程度，提高了吞吐量，降低了端到端延时，而AODV和AOMDV协议都是使用一条路径进行数据传输，限制了数据传输速度，而且AOMDV-SPC在路由选择上使用的路径的路径持续时间因子较高的路径，降低了链路断裂的几率，因此就提高吞吐量及分组到达率，降低了延时。

图4 不同数据发送速率下的分组到达率

6.结语

仿真结果显示，AOMDV-SPC在一定程度上增加了路由控制包数量，提高了网络的吞吐量、时延以及分组到达率的性能，使得AOMDV-SPC能够在一定程度上满足移动Ad hoc网络的多媒体实时业务以及大流量传输要求。参考文献：

[1]郑少仁，王海涛，赵志峰等.Ad hoc网络技术[M].北京：人民邮电出版社，2005：1-13.

[2]毛靖添.Ad Hoc网络按需多径路由协议的研究[D].哈尔滨工程大学.2007.

[3]Illya Stepanov，Kurt Rothermel.On the impact of amore realistic physical layer on MANET simulations results.Ad Hoc Networks.2006.6 (1)：61-78.

[4]杨俊丽，刘明等.基于相关因子的节点不相交的ad hoc多路径路由算法[J].小型微型计算机系统，2006，27(9)：1669-1672.

[5]Li Li，Ram jee，R，Buddhikot M.，M iller，S..Network Coding-Based Broadcast in Mobile Ad-hoc Networks.IEEE.INFOCOM 2007.26th IEEE International Conference on Computer Communications.2007：1739-1747.

[6][Nasipuri A，Castaneda R，Das S.R.Performance of M ultipath Routing for On-Demand Protocols in Mobile Ad hoc Networks[J]，Mobile Networksand Applications.2001，V6：339-349.