自组织路由协议（精选7篇）
自组织路由协议 篇1
0引言
车载自组织网络作为一种特殊的移动自组织网, 不仅面临一般无线自组织网络已有的挑战[1],同时其自身网络的特性也面临诸如车辆移动性高、拓扑变化快、车辆地理位置以及移动方向受限等问题。 这些问题造成了事先建立端到端路由路径的传统单播路由协议并不能很好适应复杂的城市环境。而在该无线环境下,利用了无线信道天然广播特性的机会转发策略能够有效提升单跳路由的转发性能,从而显著提升端到端的路由性能。
已有的机会转发研究[2,3]通过数据包迭代的方式来计算最优转发节点,这在拓扑高速变化的街道会带来很大的开销。本文提出一种只需单跳邻居动态信息的机会路由协议,该协议考虑了多个影响路由性能的要素,从而设计合理的转发优先级。为了进一步优化性能,本文针对车辆的移动性对发送车辆候选集进行了优化。
1候选集选择
考虑城市环境下车辆高速移动性,定义两车在时间内的链路可用概率如下:
其中和分别表示车辆Vs和Vr在T 时间后的欧拉距离以及相对速度,T的取值依赖于路由协议邻居信息的刷新时间。假设街道内相同行驶方向的车辆其速度服从高斯分布[4],则两车相对速度∆vsr也服从高斯分布, f （∆vsr）为其概率密度函数。Rsrd余可持续传输距离,其值将根据以下情况来确定。
情况一:两车具备相同的行驶方向。
情况二:两车具备不同的行驶方向。
在机会转发策略中,候选集的大小对路由性能有着至关重要的影响。当数据包被转发时,它会被以广播的形式发送至候选集中的车辆。只有在发送车辆候选集中的车辆才能有机会被最终选择为转发车辆。虽然更大的候选集可以提高单跳的数据包投递率,但是该候选集也会包含更多更小地理前进的车辆,从而潜在造成路由性能下降的可能。因此车辆的运动状态和所处位置需要满足以下两条规则:
规则一:只有当链路可用概率大于一定的阈值时,车辆才会被纳入发送车辆的候选集。
规则二:候选集中的车辆必须比发送车辆具备更大的地理前进。
如图1所示,假设链路可用概率P lr的阈值为0.1, 发送车辆Vs的邻居车辆Ve由于规则一被排除,车辆Va和Vb由于规则二被排除。
2机会转发设计
当发送车辆进行数据转发时,首先检测当前无线信道是否空闲,如空闲则以广播的形式发送数据包进而取代原有的单播转发形式,否则执行相应的退避算法。收到数据包且满足一定转发条件的邻居车辆将分别设置等待计时器(wait-time timer),其配置的初始化将结合接收车辆自身以及发送车辆的情况来完成。等待计时器最先到期的车辆将以广播的形式继续转发该数据包,其余的接收车辆感知到其转发的数据包时将取消自己的等待计时器,并且丢弃该已收到的数据包。本节将对影响路由性能的三个要素对等待计时器进行设计。
2.1街道内地理前进
接收车辆Vr对于发送车辆Vs的地理前进距离为Dr,其定义如下:
其中ds ,s tr ee t和dr, st re e t表示发送车辆Vs和接收车辆Vs沿发送方向到达当前街道的街道口距离。沿发送方向街道口更近的接收车辆拥有更大的地理前进距离,但是需要注意的是本节所有统计地理前进距离采用的目的地并不是诸如GPSR[5]等地理路由协议中使用的数据包目的车辆。这样做可以避免路由协议在街道内遇到的局部最大值(local maximum)问题[5]。
2.2平均缓冲区队列长度
街道内车辆缓冲区队列的状态对路由性能起着至关重要的影响。如果数据包被发送至一个已经具有更多数据包缓存的车辆,这势必会带来额外的排队时延。同时数据包引导的不合理也会导致数据包在某些特定的车辆造成堆积,导致缓冲区溢出丢包。 所以平均缓冲区队列长度将作为衡量一个车辆数据负载程度的重要指标。车辆Vr平均缓冲区队列长度计算如下:
其中Q l e nr代表车辆在采样时刻平滑后的缓冲区队列平均长度。 Q l e nold代表了车辆上一时刻所维护的历史缓冲区队列平均长度,Q l e ncurrent代表了车辆在采样时间时的瞬时缓冲区队列长度。α的值域为[0,1], α的值越大表示路由策略更关注缓冲区队列的历史信息。
2.3平均竞争窗口大小
当前竞争窗口的大小在一定程度上能够反映当前车辆所处的无线信道环境以及自身的数据流量特征[5]。 关于车辆Vr平均竞争窗口CW大小的计算如下:
其中C Wr代表车辆Vr在采样时刻平滑后的平均竞争窗口大小。 C Wold代表了车辆上一时刻所维护的历史平均竞争窗口大小, C Wc u r r e nt代表车辆在采样时间时的瞬时竞争窗口大小。β的值域为[0,1],β的值越大表示路由策略更关注竞争创窗口的历史信息。
2.4多路由度量等待计时器设计
本节将考虑上述三个路由度量来初始化车辆的等待计时器,具有更高优先转发权的邻居车辆具有更小的等待时间,其初始值设置的函数如下:
其中Dr(max)、Q l e nr(max)和C Wr(max)分别为最大地理前进(通信半径)、最大缓冲队列长度和最大竞争窗口大小。 αi( i = 1 , 2 , 3)为三个路由度量的权重 ,Tmax为最大等待时间。因此公式7返回一个不大于Tmax的等待时间,各邻居车辆根据其计算的结果设置自身的等待计时器,从而分布式的决定各个邻居车辆的转发优先级。
2.5基于多路由度量的机会路由算法
数据包在街道内根据多路由度量执行机会转发策略,在街道口根据Dijkstra算法选取一条拥有转发车辆且处于最短路径中的街道作为下一条转发街道。 基于多路 由度量的 机会路由 协议O R P M(Opportunistic Routing Protocol based on Multi-metrics)如下:
3性能评测
为了评测ORPM协议的性能,本文在仿真软件NS-2中实现了另外两个路由协议GPSR[5]和LSGO[2]。 城市拓扑大小设置为2000m*2000m,车辆的初始化分布和行驶轨迹都被限制于街道内,车辆的行驶速度为30km/h至60km/h,通信半径为250m。随机选取10对CBR产生数据流量,仿真时间300s,图中所有数据都是10次实验的平均值。
图2是端到端时延的对比结果,ORPM在街道内考虑多路由度量作为车辆转发优先级的依据,该策略能够有效减少排队时延以及转发跳数,因此能够获得更小的端到端时延。
图3是数据包投递率的对比结果,ORPM使用机会转发策略,该策略利用了无线信道广播的特性, 从而提升了单跳的数据包投递率,获得更高的端到端数据据包包投投递递率率。 。
图3数据包投递率 (参见右栏)
图4路由开销 (参见右栏)
图4是路由开销的对比结果,其定义为全网控制数据包的总大小与目的车辆收到数据包总大小的比值。ORPM利用单跳邻居信息进行路由决策,能够有效控制网络中用于信息交换的控制数据包的总大小,因此具有最小的路由开销。
4结束语
本文提出了基于多路由度量的机会路由协议ORPM,该协议使用多路由度量确定候选集中车辆的转发优先级,指引数据包在街道内高效的传输。 实验表明ORPM在更低的路由开销情况下显著降低了端到端时延并提升了数据包投递率。
摘要：车载自组织网络面临车辆移动速度快、拓扑变化频繁等问题,而机会转发策略利用无线信道天然的广播特性相比于传统的确定性转发策略能更加有效应对复杂的城市环境。本文提出一种只需利用单跳邻居信息的多路由度量机会路由协议,该协议能够合理安排邻居车辆的转发优先级,同时根据车辆移动特性对候选集进行了进一步优化。仿真结果表明,本文所提出的路由协议能够显著提升单播路由性能。
关键词：车载自组织网络,机会路由,路由度量,候选集
参考文献
[1]Zhang X M,Zhang Y,Yan F.Interference-based Topology Control Algorithm for Delay-constrained[J].IEEE Transactions on Mobile Ad hoc Networks.2014,14(4):742-754.
[2]Cai X,He Y,Zhao C.LSGO:Link State aware Geographic Opportunistic routing protocol for VANETs[J].EURASIP Journal on Wireless Communications and Networking,2014(1):1-10.
[3]Dubois H,Grossglauser M.Least-cost opportunistic routing[R].Technical Report,2007.
[4]Eiza M H,Ni Q.An evolving graph-based reliable routing scheme for VANETs[J].IEEE Transactions on Vehicular Technology,2013,62(4):1493-1504.
[5]Karp B,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C].Proc.of ACM/IEEE Mobi Com'00,2000:243-254.
[6]Gao X M,Zhang X M,Shi D,et al.Contention and Queue-aware routing protocol for mobile ad hoc networks[C].Proc.of IEEE Wi Com’07,2007:1628-1631.
自组织路由协议 篇2
关键词：自组织,路由协议,仿真技术
0 引言
随着计算机科学和互联网技术的不断发展，无线自组织网络技术已经取得长足的进步[1]。无线自组织网络的特点是，两个相关节点之间的信息通讯，需要多跳路由来完成，同时网络的节点通过相应的分层网络协议以及查询算法，实现网络协调上的自组织[2]。关于自组织网络的建立，在硬件结构上，不需增加任何的网络报送装置的，依靠每一节点配置相关的路由协议，任意的移动终端需要兼顾主机和路由的功能，主机是基于面向用户的应用程序;路由的功能是通过相应的路由协议策略和路由节点表进行相应的数据包管理和维护[3]。目前无线自组织网络在军事和民用领域都获得了广泛的应用，例如学校、港口码头及勘测实验的区域网等[4]，节点数量基本都在10～20个之间，网络数据的传输速度在1.2 Kbps～2 Mbps。由于自组织网因素之间的相关性，例如移动速度、密度和规模等，对于网络的设计具有较大的影响。现有的大多数自组织网络协议设计，都是基于特殊的应用场合进行局域概念性开发，本文提出一种自适应的自由网络控制协议，依据相临节点之间相对位置参数，设计自组织网络路由协议的改进算例。
1 自组织网络结构
自组织网络平台是一种无中心的分层控制网络。在整个控制网络，不设置固定的网络基础设施，可以对无法使用互联网的场合，进行网络信息数据通信技术扩展，实现网络应用环境上的范围扩大化。自组织网络平台中的相关节点，具有随机性移动的特点，同时可以与网络中的其他节点，进行相应的任意数据点的链接，并且实时地改变动态自身节点和其他节点链接位置，相应的节点链接改变对于分层网络结构的协议策略有较大的影响。移动的自组织网络可以实现相对较强的自组织功能，也就是说一些相对较为简单的规则，在网络中的不同层次上进行相应的应用，相对规模较大的网络协议自适应能力，相应的网络平面结构解析图，如图1所示。网络构成的相应节点在路由协议选取、控制和流量分配上具有等价的地位，网络具有较大的功能，数据传输上具有多路径选择，由于网络的覆盖范围上相对较小，一般只应用于小型的局域网络中。自组织网络的分层次结构，利用完全相对的分布和中心式分层的相关优势，把整体网络划分成组合簇的结构，即把相应的数据功能进行相应的打包处理，利用簇节点进行数据的收发、管理和协调。双频分级网络结构是自组织的网络分级结构，任意级的功能特点相对较为简单，实现了维护的效率上的提高，降低了自组织网络的控制消息功能，具有相对较好的可靠性、扩展性，由于相应的簇头节点，可以依据相应的功能进行提取，这将使得网络具有较强的抗破坏性。
2 自组织网络移动模型
自组织的无线通信网络中，对于网络信息的路由协议策略的影响主要基于两个方面的问题，一是网路节点的任意移动;二是由于外界的干扰所引起的信号不稳定性。自组织网络节点的移动，将会造成相应的路径通断，使得路径进行相应的重新建立，这种情况将会使用相应的路由协议，维持相应的数据信息的通信。为了研究相应的自由网络路由协议，就要首先建立相应的节点移动模型，进行相应的节点模型仿真分析研究，以此模型为基础进行相应的网络协议功能的评价。
2.1 自组织网络移动模型
自组织网络移动的模型，对于个体来说，单个节点的移动相对独立于其他周围节点，而在实际的网络中，节点的移动具有相应的分组概念，即单一节点的移动是受到相应其他节点行为的影响，网络中节点的移动自动进行群体的组织，依据节点要实现的相应数据功能，本文选取移动的参考节点运动模型，其相应的结构运动如图2所示。
自组织网络中，所有节点依据相应的功能分自动分配成相应的组群体，每一个组中含有相应的逻辑中心节点，各组的逻辑中心点，存在相互独立的关系，并有其相应的中心移动轨迹，组中的相关节点与逻辑节点具有相同的运动方向和轨迹，并且组中的节点具有相对于逻辑中心位置的运动模型。该自组织网络移动模型就有下叙述特点，一是节点划分为功能组后，组中将会生成一个逻辑的中心点，中心点的移动将会代表整个组的移动过程，包含运动方程的位移、速度和加速度信息指标，可以理解为组群的运动可以以组中逻辑中心点移动位移表示;二是组中的任意节点将会分配一个相应的参考节点(RP)，节点和参考点之间具有相互独立的运动模式及空间范围，同时参考点随着组中群体节点移动而发生相应的动态变化，其运动规律如图2所示;三是相应的节点依据参考实际的相关空间位置进行自由状态的移动，参考点可以为节点进行相应的参数配置工作，假设参考点的相应位置发生位移量变化时，参考点A将进行组群之间的联动位移，矢量是GM(组群之间的位移矢量决定、逻辑中心组合判断)，发生A→B的位移，建立新的参考点位置随机网络位移节点RM，生产新的参考点位置B;四是相应的自组织网络中的随机位移变量将会独立于以前的参考点位置，RM的数量值以网络中的中心点为圆心，建立周期为0～2π的空间自由点随机分布，如图3所示。
2.2 网络中节点的预测模型
依据相应节点运动模型中是否含有运动方向角度θ，区分为两类情况进行考虑。
(1)节点n在时间t的运动速度为v，相应方向角度为θ，空间位置的坐标为(x,y)，则依据运动轨迹方程，可知预测节点n，将在tp时刻的位置(xp,yp):
(2)节点无运动轨迹的相关信息，则必须依据近邻两个点的数据对预测点进行估计，t1时刻，节点n1的相关空间平面位置(x1,y1);t2时刻，节点n2的相关空间平面位置(x2,y2);则有预测节点n，将在tp时刻的位置(xp,yp)。
3 自组织网络节点预测算法
自由网络中节点的相互独立性运动，可能会引起网络的拓扑变化，以及网络中相应的路径操作，这将会很大程度上损失相应的网络节点资源，导致数据信息的计算量增加和通讯控制成本的复杂化，引起了通讯信息的网络堵塞，主要体现在网络数据的延时，降低了网络服务的速度和质量。对于自组织网络节点的预测算法研究，基于节点的移动感知技术，实现自组织网络路由协议功能的改善。
3.1 节点的移动特征
依据自组织网络节点信息数据收发所具有的无线传输性性能，网络中任意节点的信号传输功率不同。理论条件下，网络中节点的收发功率相对比值与始末信息节点路径的平方成反比。自组织网络中设定所有节点具有相同的信号发送功率，则信息接收功率与距离的平方成反比。在网络节点两类移动模型的基础上，对于所测量的相应接受频率信号功能，依据式(5)，进行相应的节点与邻近点相对位置的计算，单独依据相对位置点确定节点的移动参数特性是不准确的，一方面节点1的变化速度相对较快，就不能体现节点2的移动特征，另一方面节点2变化不够快，主要的移动特征将会体现在节点2上。因此可以依据式(7)进行相应的网络节点移动特性的判断，并发送相应的判断性数据，进行相应邻近节点的移动特性更新。设网络中节点y有相关的n个邻近节点，分别用:i=1,2，…，n，用Xi点表示，MXi为节点Y接受到的节点Xi功率，相应的约束条件为
设定网络中的相关移动函数为MYrel(Xi)，相应值的确定为，网络中节点Y相对与邻近节点的运动特性，依据当前时刻与过去时刻的Wi值进行相应的确定，计算出网络节点Y的相对移动变量。
网络中任意单一节点具有n个相邻近的节点，也就有n个MYrel(Xi)，通过对于网络节点n个移动函数MYrel(Xi)的统计学计算，获得节点Y的网络移动特性:
其中，My值大，说明网络节点Y与周围邻近节点的相对移动位置较大;My值小，说明网络节点Y与周围邻近节点的相对移动位置较小。
3.2 自组织网络协议的改进
自组织网络路由协议的控制消息分为三类，即RREQ(RouteRequest)、RREP(RouteReply)、RERR(Route Error)。通过相应的判断标志信息“HELLO”，依据式(7)计算获得节点的网络移动位置信息，保存在节点的路由信息列表中。网络中节点定期计算中相应的位置移动参数MY，发送周期为“HELLO”的时间间隔M＿INTEVAL，并将所计算的位置相对移动参数MY，依据路由信息判断的格式发送到相应的近邻节点。时间间隔M＿INTEVAL，相邻节点没有收到邻近节点的数据包，WYi=0,MYrel(Xi)=1，说明节点Y相对于Xi具有较高位移移动性能。自组织网络协议中的路由路径选取原则是，相邻节点进行信息数据的转发过程中，选取位置相对移动参数MY较小的节点，作为下一个信息传输的跳跃点，节点获得一组路由信息后，将网络的路由信息表进行更新，并发出新的RREQ(RouteRequest)请求数据包。
4 实验仿真研究
应用NS2仿真软件[5]，进行了改进自组织网络协议的仿真实验研究，通过相应的实验结果可知，自组织网络节点移动预测算法，能够较好地描述节点移动的变化情况，并且随着网络节点数量的增加，预测的节点数度更加接近于实际情况。
基于自组织网络的位置移动特性，将相应的节点预测结果，应用到自组织网络的路由协议中，依据相应的网络端点相对延时性能，以横坐标为网络的正常运行时间，纵坐标为网络端点延时，改进后的自组织网络协议，对于端点间的网络时间延时，有较好的较低效果，同时在自组织网络中节点选取路由时的标准是，选取移动性能相对交换的节点，为跳跃节点。基于50个网络节点，进行改进前后的自组织网络协议对比，如图4所示。
5 结语
关于无线自组织网络的高效路由协议研究，一直是人们所关注的重要热点问题。依据无线自组织网络的结构特点和相应的节点移动模型基础上，实现了节点与邻近节点之间的移动位置特性确定的原则。在移动位置特性参数的前提下，明确改进无线自组织网络路由协议的相关思路，应用网络节点移动仿真工具NS2平台，对于无线自组织网络50个节点的前提下，进行相应路由改进前后的协议端点之间的延时时间计算。结果表明，改进后的无线自组织网络协议，降低网络端点之间的延时，能够有效对网络性能进行提高。
参考文献
[1]郑相全,等.无线自组网技术实用教程[M].北京:清华大学出版社,2010.
[2]蔡一兵.无线自组网MAC及路由技术研究[D].北京:中国科学院,2006.
[3]于宏毅.无线移动自组织网[M].北京:人民邮电出版社,2008:11-25.
[4]丁宁,赵春晓,高路.校园无线移动模型的研究[J].计算机应用与软件,2009,26(4):37-39
[5]The Network Simulator-ns-2[OL].http://www.isi.edu/nsnam/ns/.
[6]余旭涛,毕光国,王霄峻,等.Ad Hoc网络按需路由协议的改进[J].计算机学报,2004,27(6):838-843.
[7]李建东.大规模无线移动Ad Hoc网络[J].深圳大学学报:理工版,2004,21(4):283-286.
[8]张继荣,赵颜.自组织网络按需路由协议的性能研究[J].西安邮电学院学报,2011,16(1):21-25.
[9]陈林星.移动Ad Hoc网络[M].北京:电子工业出版社,2009:1-11.
[10]Khelifa S,Maaza Z M.An Energy Multi-path AODV routing protocol in ad hoc mobile networks[C]//ISVC,2010 5th International Symposium on,2010:1-4.
[11]钱钊.基于位置信息的移动自组织网络路由算法研究[D].哈尔滨:哈尔滨工业大学,2013.
自组织路由协议 篇3
关键词：缓存优化,DSR,路由缩短,NS2
随着无线移动网络的发展，基于固定通信设备的移动通信网络得到了普遍的应用，如无线局域网和移动蜂窝网等。而对于没有事先布置好网络装置并且多变的场合，就需要一种没有固定通信设备也能快速组网的网络体系。Ad Hoc网络就是一种不依赖于固定通信设施的移动自组织网络，具有动态的拓扑结构、能够迅速地展开使用。Ad Hoc网络中的节点既可当作终端，也可作为路由器使用，主要完成网络中路由的建立、选择和维护。对于不能直接到达的两个节点，需要经过中间节点通过多跳的方式转发数据，因此又叫多跳网。目前已有10～20种移动Ad Hoc网络路由协议，每种路由协议都有各自的特点和适应的场合。一般可以将Ad Hoc网络路由协议分为表驱动路由和按需驱动路由协议两类。DSR协议是一种典型按需驱动路由协议，相比之下，DSR协议是Ad Hoc网络路由协议中与传统路由差别最大且整体性能最优的路由协议，对DSR协议的研究具有重要的意义。
1 DSR协议概述
动态源路由协议DSR(Dynamic Source Routing Protocol)是专门为Ad Hoc网络设计的、具有多跳无线、简单且高效的路由协议。DSR是基于源路由方式的，即在每一个传输分组的头部插入完整的源路由信息，以保证分组按照指定的路径传送。这种方法有效地避免了环路的出现，且在节点移动或者网络发生变化的情况下也能将分组正确地传送，提高了移动通信节点对于网络拓扑动态变化的适应能力。DSR协议包括两大机制：路由发现和路由维护。
(1)路由发现：DSR是一种按需路由协议，只在节点发送数据时才启动路由发现过程。节点接收到数据后，先查找自己的路由缓存表，如果路由表中不存在可到达目的节点的路由信息，就使用洪泛技术向邻居节点广播路由请求报文(RREQ),邻居节点在接收到请求报文后，缓存表存在到达目的节点的路由或者本身是目的节点，就发送一个路由应答包(RREP)，并把路由信息反馈给源节点供其使用。若没有到达目的节点的路由或本身不是目的节点,则继续向自己的邻居节点发送RREQ包。
(2)路由维护：DSR的路由维护过程是在发送数据的过程中才进行的。在分组转发过程中如果发现某一跳链路不可达，中间节点向源节点发送路由出错报文(RERR)，源路由在收到出错报文后，当再有发往该目的节点数据包时重新发起路由发现过程，且所有收到RERR报文的源节点和中间节点都将删除包含该跳链路的缓存路径。
DSR路由协议作为按需路由协议，具有开销小、简洁高效等特点。DSR协议也有一些缺点，主要表现在以下几方面：(1)采用源路由方式，储存报文传输过程中整个路径节点的路由信息，浪费了宽带资源。(2)其路由缓存机制，将导致在广播路由请求报文时，有许多中间节点同时应答，这可能会引起“应答风暴”，还可能导致过时的路由在网路中大量扩散。(3)为满足节点快速传送信息需求，没有考虑无线节点的能量问题。这会导致整个网络的能量或某些重要节点的能量很快被消耗，最终造成网络较快地分裂，影响了数据的传输效率，缩短了网络的生存时间。
2 DSR协议的改进设计
针对DSR路由协议存在的不足，本文对DSR路由协议进行了改进。针对DSR缓冲器先引入以下三个参数：
(1)形成时间路由参数：定义加入路由最晚的节点的时间为形成时间路由参数，记为TB。t表示DSR缓冲器中路由的某一节点加入到路由中的时间，则TB=max(t)。
(2)生存时间路由参数：定义路由中相邻的节点之间构成的链路从形成到失效的时间为生存时间路由参数，记为TL。
(3)剩余生存时间路由参数：定义生存时间路由参数与路由已存活的时间参数之差为剩余生存时间路由参数，记为TR。TC表示当前时间，则TR=TL-(TC-TB)。
针对DSR缓冲策略存在的不足，对DSR的缓冲策略进行以下改进：选择最佳路径时，首先选择路由长度最短的路由，在最短路由不止一条的情况下，则选择最短路径中剩余生存时间最长max(TR)的一条路由。当缓存器满时,就舍弃剩余生存时间路由参数最小min(TR)的路由。
优化DSR路由的自动缩短机制：主要进行以下两方面改进。
(1)寻找跳数最小、所产生的新路由的路由质量最好的路由。TL决定路由的质量，取TL最大值的路由。
(2)通过新形成链路的移动节点速度、移动方向、位置估算出新形成链路的TR，来判断是否要让节点使用新的链路路由。如果产生的新链路的剩余时间参数TR小于原来链路的TR，则路由缩短机制产生的路由是没有意义的，这条新链路被判断为失效。采用本方案设计的路由自动缩短机制不仅能产生跳数尽可能小的路由，同时还确保了新形成路由的TR不会很小。
3 改进DSR协议的ns2仿真
3.1 仿真条件的设置
仿真实验所用网络参数的设置如下：在一个总共由180个节点组成的宽带无线自组网上进行。接入设备由36个节点均匀分布在6×6的网格空间，所有节点的传输距离和干扰距离都相同，节点间的空间距离为200 m。MAC层协议采用CSMA接入，网络环境为IEEE 802.11，传输速率为1.6 Mb/s，功率衰减参数为2，网络协议为IP协议。传输半径为250 m，干扰半径为550 m，两者比例为2.2。网络采用的路由协议为DSR协议以及改进的DSR协议，具体参数如表1所示。
3.2 改进的DSR协议性能仿真分析
本文将改进的DSR协议与NS2现有的DSR协议的性能进行对比，所有的仿真都是在NS2仿真平台上进行的。在该仿真过程中，网络使用一条恒定速率(CBR)的数据流，由节点0在0～1 s之间随机选择一个时间往节点24发送数据流。仿真时间为100 s，画出网络吞吐量和时间的关系图，进行对比，如图1所示。
由图1可知，在数据传输期间，改进的DSR的吞吐量略微高于原DSR。这是因为在改进的DSR协议中，对DSR协议的缓冲策略以及路由缩短机制进行了优化。当有多条最短路由时，选择剩余时间最大的一条;在选择跳数较小的路由时，必须保证所选的路由的剩余时间不小于它所代替的路由，从而保证了路由选择的质量。而原DSR协议中，把所有跳数最小的路由都加入路由缓存表，用跳数小的路由代替跳数大的路由。因此改进的DSR协议实现路由切换的代价比DSR协议小。
测试网络时延的仿真环境配置与网络吞吐量比较时的配置完全一致，网络时延的情况结果如图2所示。
由图2可知，在数据传输期间，采用改进DSR协议的网络时延略低于采用DSR协议的网络时延。由此说明，在网络路由路径发生变化时，采用改进DSR协议的网络能够保证修改后路由的质量，从而保持较低的时延，避免网络性能在切换路由时恶化的情形。
测试网络丢包率的仿真环境配置与网络吞吐量比较时的配置完全一致，网络丢包率对比图如图3所示。
上面的仿真实验表明,与DSR协议相比,改进的DSR协议能够使网络获得更高的吞吐量以及更低的丢包率,且其时延相应减少。其原因是在其他设置一样的情况下,改进的DSR协议可以迅速地选择跳数少、质量高的路由,这样可减少切换所需要的时间，提高网络的吞吐量并减少丢包率，进而提高宽带无线自组网的性能。
本文阐述了基于路由缓冲优化的路由协议，并在路由缩短机制的基础上，对现有的按需路由协议提出了一种通用改进方法，同时讨论比较了DSR协议与改进的DSR协议，并具体地实现了改进的DSR协议在NS2的仿真实验。实验仿真结果证明了对于DSR协议的改进协议确实具有优于传统DSR协议的特性,让明了改进算法的可行性。
参考文献
[1]MATSUO H,MORI K.Accelerated ants routing in dynamicnetworks[C].International Conference On Software Engineer-ing,Artificial Intelligence,Networking and Parallel/Distri-buted Computing,2001,8:333-339.
[2]CHOUDHARY R R,BHANDHOPADHYAY S,PAUL K.A distributed mechanism for topology discovery in Ad Hocwireless networks using mobile agents[M].Procedings ofMobicom,2000:145-146.
[3]HAAS Z J,PEARLMAN M R,SAMAR P.The zone rout-ing protocol(ZRP)for Ad Hoc Networks[M].IETF Internet-Draft,2002.
[4]PERKINS C E.Ad Hoc networking[M].Addison-Wesley,Boston,2001:139-172.
[5]BROCH J,JOHNSON D B,MALTZ D A.The dynamicsource routing protocol for mobile Ad Hoc networks[M].IETF Internet-Draft,1998.
[6]吴东亚,侯朝桢,侯紫峰,等.移动自组网路由协议DSR性能评价[J].计算机应用与软件,2004,21(12):66-68.
自组织路由协议 篇4
无线自组织网络是由多个带有无线收发装置的可移动的节点组成的一个多跳的临时性网络, 可以快速地搭建一个通信网络。由于节点的位置变化及拓扑动态变换, 使得传统的路由协议不再适用, 因此根据无线自组织网络自身特点进行修改, 或者提出一些新的路由协议。本文通过对比现有的一些无线路由协议, 找出一种适合于无线自组织网络的路由协议。
1 路由协议
良好的路由协议是无线自组织网络要研究的首要问题, 也是研究的热点与难点, 到现在已提出多种不同的路由协议。这些路由协议可从不同角度进行分类。目前, 无线自组织网络路由协议主要是按照路由发现方式进行分类, 分为表驱动路由协议、按需驱动路由协议和混合路由协议。本文介绍几种典型的路由协议。
1) DSDV
DSDV (Destination-Sequenced Distance-Vector Routing) 是一种表驱动式路由协议, 是基于Bellman-Ford算法改进的路由算法。DSDV协议给网络中的每个路由设定序列号以避免路由环路, 每个节点维护一份路由表, 路由表中包括目的节点、跳数和一个由目的节点注明的序列号, 序列号能帮助节点区分有效和过期的路由信息, 当主机接到一条路由信息时将此信息与以前接受的信息比较, 带有最新序列号的路由被保留, 从而防止闭环产生。但路由表需要频繁地更新, 每个节点周期性地与临节点交换信息, 在网络空闲时仍然会耗费节点能量和网络带宽。一旦网络的拓扑结构发生变化, 就会生成新的路由表;DSDV算法的收敛速度慢, 需要周期性地向外发布路由信息, 所以效率比较低[6]。
2) AODV
AODV (Ad hoc On-Demand Distance Vector Routing) 是结合了DSDV协议和DSR协议改进后提出的一种按需路由协议。按需路由一般包括:路由发现、路由维护和路由拆除。按需路由协议是根据业务需求建立和维护路由, 只有当源节点需要和目的节点建立联系时才会发起路由发现过程;当源节点发起的路由请求到达目的节点时, 目的节点向源节点发送一个路由应答信息, 建立起有效的路由路径。在路由建立以后, 进行路由维护, 直到这条路由不再被需要或断开;通信结束后, 再进行路由拆除过程, 将路由删除[7]。
AODV采用逐跳转发的分组方式, 当网络中的节点需要给其它节点传送信息时, 如果没有到达目的节点的路由, 就采用多播的方式发出路由请求 (RREQ) 报文。RREQ报文中有源节点和目标节点的地址, 邻近节点收到RREQ后, 首先判断目标节点是否为自己。如果是, 则向发起节点发送路由回应 (RREP) ;如果不是, 则在路由表中查找是否有到达目的节点的路由, 如果有, 则向源节点发送RREP, 否则继续转发RREQ进行查找, 直到找到目的节点。按需路由协议在无需求时不维护路由, 节点不保存路由信息, 也不参与路由表的交换, 这和DSDV需要保存完整的路由表不同, 因此可以降低网络的开销。
3) DSR
DSR (Dynamic Source Routing) 是一种基于源路由的按需路由算法, 它使用源路由算法而不是逐跳路由的方法。所谓源路由, 是指每个数据分组都携带有源节点到达目的节点之前所有分组经过的节点的列表, 即分组中有到达目的节点的完整路由。DSR路由协议中路由是按需建立的, 容易得到快速恢复, 这样可以减少网络的带宽开销和能量消耗, 也避免了网络中大范围的路由更新。
DSR主要包括两个过程:路由发现和路由维护。当源节点需要向目的节点发送数据时, 先检查缓存中是否存在有非过期的到达目的节点的路由, 如果存在, 则可以直接使用, 否则启动路由发现过程。源节点泛洪广播发送路由请求, 当源节点接收到目的节点路由回复后, 路由发现过程结束。建立路由后, 需要对路由进行维护。源节点通过路由维护可以检测到因为网络拓扑改变不能使用的路由。当路由维护检测到使用中的路由出现了问题时, 就会发送RERR (路由错误报文) 给源节点, 而源节点在收到该RERR后, 就会从自己的路由缓存中删除所有包含该路由的信息, 并且重新发起路由发现过程[3]。
4) ZRP
ZRP (Zone Routing Protocol) 是一个分区路由协议。它结合了表驱动路由协议和按需路由协议, 综合利用了这两种协议的各自优点。在区域内采用主动路由方式, 区域间采用按需方式。ZRP将整个网络分成若干个互相重叠的区域, 在区域内部, 采用IARP (Intrazone Routing Protocol) 协议, 区域间路由采用IERP (Interzone Routing Protocol) 协议。只有区域间周期交换信息, ZRP协议才变为按需路由协议;在区域内, ZRP协议又变为纯粹的表驱动路由协议。这样既减小路由建立所带来的时延, 又减少网络广播带来的开销。
2 路由协议性能评价标准
路由协议的评级标准主要包括丢包率、端到端平均时延、网络吞吐量几个方面的指标。
1) 分组成功投递率
分组成功投递率为目的节点收到正确分组数据与源节点发出分组数据数之比, 端到端的传递效率反映了路由协议的可靠性。数值越高, 表示传递效率越高, 算法可靠性就越高。通过计算发送包总数和接受包总数的比值得到。
2) 端到端平均时延
端到端平均时延是指单位数据包从源节点到目的节点的整个过程所用的时间。端到端平均时延可用来衡量协议构建路由的速度, 时延越小, 说明响应越快, 网络质量越好。
3) 网络开销
网络开销为单位数据包个数所引起的额外路由分组个数, 该指标衡量了路由查找过程中所带来的网络通信开销, 反映了路由协议的效率。
3 实验仿真
本文通过NS2仿真平台对几种典型协议DSDV、AODV和DSR进行仿真对比, 分析协议的性能[8]。在环境相同的情况下, 对三种路由算法在端到端平均时延、分组递送成功率等参数方面的性能进行仿真分析。
1) 在数据流不变的情况下, 改变节点移动速度, 对三种路由协议进行仿真, 得到分组投递成功率、端到端平均时延差异如图1、图2所示。
由仿真结果图可知, 在数据流相同的情况下, 节点速度变化时, 按需路由协议AODV、DSR的效率较高, 波动较小, 而主动路由协议DSDV递送率较低, 而且波动较大。端到端的延时波动都比较大, DSDV相对延时较小, 而DSR较大。
2) 在不改变节点场景下, 改变移动节点间最大连接数, 分组投递成功率、端到端平均时延的性能比较如图3、图4所示[9]。
由仿真结果图可知, 在场景不变的情况下, 改变节点间的最大连接数时, AODV和DSR路由协议的分组投递成功率比较好, 而DSDV最差。但是, AODV和DSR的延时较大, 而DSDV的延时小。
4 结论
本文主要介绍了几种典型的路由协议并使用NS2的仿真, 然后根据仿真结果对各协议的性能情况进行了分析比较。从仿真结果看, 无论是改变网络节点的移动速度还是改变节点的连接数, AODV和DSR能更好地完成信息的传递, 但相对的延迟较高, 而DSDV算法延迟较低, 但信息传送不佳。通过对比主动路由协议DSDV和典型路由协议AODV和DSR的分组投递率和端到端延时的数据可知, 这些路由协议都不能够完全适用于自组织网络, 对于不同需求选择不同的路由协议。
摘要：近年来随着网络的发展, 无线自组织网络的研究也引起了广泛的关注。在无线自组织网络中, 路由协议是无线自组织网络的研究热点。本文首先介绍几种典型的路由协议, 再使用仿真软件NS2对AODV、DSDV、DSR三种无线路由协议进行仿真。最后对仿真结果进行分析。
关键词：无线自组织网络,路由协议,NS2
参考文献
[1]王金龙, 吴启辉.认知无线网络[M].北京:机械工业出版社, 2010.
[2]丁楠, 张立军.移动Ad Hoc网络路由协议的分析和比较[J].计算机与数字工程, 2007, 35 (7) :116-119, 158.
[3]范青刚, 叶雪梅, 蔡艳宁, 等.移动自组网典型路由协议研究[J].电子科技, 2013, 26 (11) :181-183, 186.
[4]王道远, 田辉, 张平.移动自组织网络的研究与应用[J].电信科学, 2008 (6) :66-70.
[5]李振宇.移动自组织网络中路由协议的分析与研究[D].北京:北京邮电大学, 2006.
[6]PERKINS C E, BAGWAT P.Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers[D].In Proceeding of ACM SIGCOMM, 1994, New York:ACM Press, 1994:234-244.
[7]Perkias C E, Royer E M, Das.Ad Hoc On-Demand Distance Vector (AODV) Routing[G].Intemet Draft, draftietf-manet-aodv-13.txt, work in progress, February 2003.
[8]王辉, NS2网络模拟器的原理和应用[M].兰州:西北工业大学出版社, 2008.
自组织路由协议 篇5
关键词：高速公路,跨层协作,自适应
车载自组织网络 (Vehicular Ad hoc Network, VANET) 是移动自组织网络 (Mobile Ad hoc Networks, MANET) 的一个新兴研究分支, 基本思想是在一定通信范围内的车辆可以相互交换各自的速率、位置等信息, 并自动建立一个移动的网络。在VANET中, 利用大规模计算和无线网络通信, 可以实现车辆与车辆之间 (Vehicle to Vehicle, V2V) , 车辆与路边基础设施之间 (Vehicle to Infrastructure, V2I) 的多跳无线通信, 并为车辆提供了各种安全应用 (如碰撞预警、协助交通管理等) 以及非安全应用 (如路况指示, 娱乐等) 。
一、研究背景
在车联网中, 路由协议的优劣和自适应程度, 直接影响了网络中的整体性能。由于VANET对于路由协议的研究并没有给出一个标准或是研究方向, 路由的设计还是一个很开放的课题。它们在发现路由、建立路由以及通信的初期阶段往往有不错的性能表现, 但随着节点的移动, 网络拓扑的快速变化导致路由链路的断裂, 性能往往会急剧下降。随着车载全球定位系统 (Global Position System, GPS) 的广泛运用, 借助GPS获取的地理位置信息而设计的位置路由 (Geographic Routing, GR) 逐渐发展起来。由于重大交通事故发生的场合主要是在高速路上, 所以如何保证高速公路上安全消息的可靠传递显得至关重要。一个好的路由协议的使用, 保证数据传输的成功率和时延要求, 并控制整个网络的负载开销, 才能保证应用能够稳定可靠的实现。但是传统的车联网分层结构对路由协议的设计, 仅仅依靠单一层次, 很难在各种变化的网络环境下达到安全消息极其严格的传递要求, 有必要采用跨层设计, 上层协议必须与下层进行有效的状态信息交互以配合分配好网络资源, 满足实时性和可靠性的要求。本文在此基础上本文提出了一种跨层的结构设计, 用以满足车联网信息传输中实时性和可靠性的要求。
二、CCR算法设计
根据车联网中不同的通信需求所需的Qos不同, 车联网中的消息可以划分为2个等级 (1和2) :等级越高, 表示对Qos的需求越高, 消息的优先程度也就越高。消息的优先级划分如表1所示。
首先, 在车联网中, 不同的消息种类对通信提出了不同的需求, 对于高优先级消息 (优先级为2的消息) , 如车辆碰撞预警、防追尾等, 这类消息往往与交通安全甚至人生安全息息相关, 因此, 实时性对于这类消息至关重要, 需要进行快速、可靠的分发。但对于低优先级的消息 (优先级为1的消息) , 如位置导航、地图下载、车载娱乐互动等消息, 这类消息对实时性的要求并没有像高优先级消息那样苛刻, 因此, 只需尽力传输即可。基于跨层协作的路由协议 (CCR) , 通过传输层与网络层的协作, 根据不同的优先级, 选择不同的路由策略, 从而保证了消息能够得到适当的处理。
CCR转发机制
(1) 需要发送消息的源车辆节点的应用层产生一个message, 并在每个packet中的头部的Destination_Priority字段标记数据包的优先级。按照CCR的优先级分类, 可以标记为1或2, 等级越高, 消息的优先级越高。
(2) 邻居车辆节点接收到message后, 将该message传输到网络传输层, 传输层的分类器通过查询头部的Destination_Priority字段, 判断该消息所处的优先级, 根据不同的优先级采取不同的转发策略
(3) 若Destination_Priority为2, 则该packet放入高优先级队列, 若队列没有满, 则进行洪泛广播, 若队列满, 则溢出, 由于高优先级消息对实时性有很苛刻的要求, 所以, 队列满后, 最后到达的数据包被直接丢弃;若Destination_Priority为1, 则放入低优先级队列进行排队, 如果该队列满, 则进行暂存, 最后到达的数据包将会被放入一个缓存池里, 待低优先级队列的有空隙时, 缓存池里的消息按照先进先出的原则依次进入低优先级队列, 排队等待发送。
(4) 当高优先级队列和低优先级队列中都有packet时, 则高优先级队列中的packet将会被优先发送出去, 以确保高优先级的安全消息被及时处理, 保证行车安全。
(5) 若高优先级队列中无packet, 则低优先级队列中按照先进先出的原则发送队列中的数据包, 由于在高速公路场景下, 优先级为2的数据包发送的概率相比与优先级为1的数据包相对较低, 如此, 采用CCR既可以保证高优先级的消息可以及时转发, 又兼顾了低优先级的消息稳定持续的进行路由。
在本文设计的CCR (cross-layer cooperation routing) 协议中, 一个基本假设是车联网中的车辆都配有车载射频发射机和接收机, 能够通过装载在车辆上的GPS获得自身的位置、速率等相关信息。并且规定了每个车辆节点都需要维护一个邻居节点历史移动信息数据库, 同时也必须通过周期性地向邻居节点广播beacon消息来刷新自己的速度信息和位置坐标信息。当节点收到邻居节点广播的beacon消息后, 根据时间戳在历史移动信息数据库中更新邻居节点的移动信息。
节点通过周期性广播的beacon消息交换当前所处状态信息, beacon消息所包含的信息如下:<类型, 节点ID, 生存时间, 位置信息, 速度信息, 状态>, 类型指明该消息数据包类型为beacon信息, 每一个车辆节点都有其唯一的节点ID, 生存时间是数据包存在的时间值, 位置信息包含车辆节点的位置 (x, y, z) , 是指其GPS坐标值, 速度信息是节点的速度大小v及运动方向Ѳ, 状态表明该节点是否处于繁忙状态, 若有数据包需要转发, 则繁忙, 否则空闲。
历史移动数据库主要包含以下内容<ID, (X, Y) , Velocity, last update time, CT>, 其中ID是邻居节点号, (X, Y) 是邻居节点坐标位置坐标, Velocity是邻居节点的速度信息, last update Time是该邻居节点信息的最新更新时间, CT (connection time) 是经过计算后得出的节点与该邻居节点的预测链路的最大连接时间。
在CCR中, 假设车辆的通信范围为R, 则在固定通信范围R内的一对节点被认定为处于可连通状态。但由于这两个车辆节点具有不同的行驶速率以及不同的行驶方向, 随着两个车辆节点的移动, 两个节点的位置也处于相对变化中, 在未来的某一时刻, 两个节点间的距离将超过车辆节点覆盖的通信范围R, 由此, 这一对节点变为不连通状态。这一段从可连通状态到不可连通状态的时间预测, 即双方连通性的预测。
如图1所示, 车辆节点a和车辆节点b相距距离为r。两点有各自不同的位置信息和速度信息。节点a位于 (xa, ya, ta) 处, 移动速度为;节点b位于 (, tb) , 移动速度为。这里ta和tb分别表示节点a和节点b位置更新时刻。R为两节点的通信距离。当r小于R时, 两节点处于连通状态。t为当前时刻。在短时间内, 节点的移动速度变化较小, 为计算方便, 我们假定车辆节点匀速行驶, 即保持匀速行驶。则两节点间距离r是关于时间t的函数r (t) 。由于ta和tb并不相同, 两节点的位置信息更新时刻不同步, 所以需要经过同步修正后使用。经同步修正后, 两节点均在ta时刻进行后续计算。经修正后的两节点位置坐标差如式 (1) (2) 所示
这样即可可到两点间距离函数r (t) 表达式
容易得出, 当r (T) <=R时候, 两节点处于连通状态。连通时间CT表示最大连通时间, 由式 (3.5) 计算得到表达式
(1) 低优先级消息分发机制
如图2所示, 在双向四车道的场景下, 节点S有5个邻居节点, 分别为N1, N2, N3, N4, N5。在传输层对消息进行分类后, 若判定为低优先级消息 (优先级为1的消息) , 则进行如图所示的转发过程, 启动贪婪算法选择的结果会试图选择靠近通信边缘的节点作下一跳。这样带来一个问题, 处于通信边缘的节点是不稳定状态。如图中节点N5所示情况一样, 它即将在短时间内移出之前中继节点的通信范围。而该中级节点无法及时知道这种情况, 仍然会选择这个“存在”的节点N5传输, 这样, 在传输过程中, 就会出现持续丢包情况。
低优先级转发算法要求每个节点维护了一个邻居节点历史移动数据库, 连通时间由式 (6) 计算得出, 如图中中继节点给出示例。考虑到传统MANET路由信标周期在1S左右, 即在1S内邻居节点发送的位置变化, 是难以获知的。所以设置CT值可信阈值下线为1S。CT值不足1S的邻居节点将视为不可靠节点, 意味着会在短时间内有很高的可能性移出通信范围。
(2) 高优先级消息分发机制
在高速公路场景下, 车辆能够以较高的期望速率行驶, 车流密度相对较小, 传输层对数据包的优先级进行分类后, 为了能够获得较低的时延, 以及较高的可靠性, 将高优先级消息 (优先级为2) 的数据包直接采取洪泛的方式进行广播。由于在高速公路场景下, 车辆密度相对较低, 采用洪泛广播的方式反而降低了发生广播风暴的可能性, 提高了数据包传输的及时性与可靠性。
三、性能仿真及分析
3.1 VISSIM以及NS3仿真工具
VISSIM是一种微观的、基于时间间隔和驾驶行为的仿真建模工具, 不仅可以完善地模拟各种真实的交通场景, 还可以生成可视化的交通运行状况, 并且以文件的形式输出各种交通评价参数, 是评价交通工程设计和城市规划方案的有效工具。
NS3是一个离散事件模拟器, 是一款开源软件, 由C++编写, C++语言作为前台, 可以对网络性能进行仿真, 并且能正确地处理节点上的多重接口, 使用IP地址, 与因特网协议和设计更一致, 和更加详细的802.11模块等。
3.2仿真结果
在仿真实验中, 仿真结果展示了车辆在高速公路环境下路由的性能表现, 由于我国交通法规的限制, 高速公路上车速的限制在60km/h到120km/h之间, 本文也据此进行了速率的设定, 为了对提出的路由协议CCR进行性能分析, 本文利用VISSIM生成交通流模型, 并通过NS3仿真软件对路由协议的性能进行了分析。
图3和图4分别显示了三个路由协议在高速公路场景下的性能表现, 通过仿真结果可以看出, CCR路由协议相比于AODV与GPSR有较高的传输成功率以及较低的端到端延时。这是由于在高速公路场景下, CCR采用了基于跨层协作的路由协议, 使得高优先级与低优先级消息都能得到合理的处理, 对于低优先级消息, 对CT进行了估计, 剔除了不可信点, 减少了链路断裂的概率, 对于高优先级消息, 由于高速公路场景的特殊性, 采取洪泛的广播, 提高了数据包成功传输率, 所以, CCR的数据包成功传输率远高于其它两种路由协议, 平均的端到端延迟也小于GPSR、AODV协议, 而且随着数据发包率的增加这种优势愈发明显。通过仿真结果表明, CCR较传统基于拓扑和基于地理信息的路由有更好的传输成功率, 而且表现出更好的稳定性。
四、结语
综上所述, CCR算法重点在于通过传输层与路由层的跨层协作机制, 针对不同的优先级采取了不同的路由策略。仿真结果表明, 在高速公路场景下, 针对车联网不同业务的Qos需求, CCR最大程度地利用了有限的网络资源, 减少了数据传输延时, 有效地满足了车联网各种业务的需求。
参考文献
移动自组网典型路由协议研究 篇6
1 MANET与传统无线网络在路由上的区别
目前生活中常见的移动通信网络主要有蜂窝数据网络和无线局域网, 在系统的组织、管理和维护方面都与MANET有较大的区别[2]。
1.1 MANET与蜂窝数据网络的区别
典型的蜂窝数据网有全球移动通信 (Globa System for Mobile communication, GSM) 网络和码分多址 (Code Division Multiple Access, CDMA) 网络, 网络中的移动节点主要通过基站进行连接, 基站之间通过有线网络进行互联, 因此移动节点之间通信路由的建立或选择主要由基站等固定基础设施完成。而在MANET中, 不存在固定基础设施, 节点通信路由的选择和建立完全由移动节点完成。在蜂窝数据网中, 由于有网络固定基础设施的存在, 网络结构相对较为稳定。而在MANET中, 节点的随意移动会使得网络拓扑结构动态变化, 影响通信路由的选择。
1.2 MANET与无线局域网的区别
无线局域网中的节点通过无线接入点连接到网络, 是单跳的网络, 路由器和主机通常是两个独立的设备。而MANET是多跳的网络, 每个节点均同时具备路由和主机两种功能。通过比较发现, MANET与传统的无线网络在路由方面有较大差异, 因此路由协议是MANET研究的重点内容。
2 MANET路由协议分类
MANET的路由协议可基于不同角度进行分类[1,3], 如按路径类型可分为单路径型路由协议和多路径型路由协议, 按广播方式可分为单播路由协议和多播路由协议, 按地理定位方式可分为地理定位辅助路由协议和非地理定位辅助路由协议, 而最常见的分类方式有以下两种: (1) 按网络拓扑结构分类。从这个角度可分为平面结构和分层结构两种。对于前者, 所有移动节点地位平等, 如动态源路由协议 (Dynamic Source Routing, DSR) 。对于后者, 网络中的所有节点按簇划分, 每个簇由一个簇头和若干个簇成员组成, 多个簇头又是更高一级簇的成员。 (2) 按驱动方式分类。可分为表驱动和按需驱动两种, 例如图1所示。前者采用周期性的路由分组广播来交换路由信息, 如目的序号距离矢量路由协议 (DSDV) ;后者则是根据发送数据分组需要进行路由发现, 建立路径, 实现信息传送。如需求驱动距离矢量路由协议 (Ad Hoc Ondemand Distance Vector, AODV) 和临时排序路由选择算法 (Temporary Ordered Routing Algorithm, TORA) 协议。
3 典型的MANET路由协议
文中选取DSDV作为表驱动路由协议的代表重点介绍;选取AODV、DSR作为按需路由协议的代表并作重点介绍。
3.1 DSDV协议
DSDV是一种基于距离矢量算法的路由协议[4], 通过附加序列号的方法来区分路由的新旧程度, 进而防止可能产生的路由环路。 (1) 路由表结构。每个节点包含一个路由表, 路由表项包括:目的信宿、下一跳、度量值和序列号。 (2) 信息通告。各个节点周期性地向邻居节点通告其当前的路由表。 (3) 链路断开。如果在较长一段时间内无法收到邻居节点的广播消息, 可推断出链路断开, 同时, MAC层实体也可检测到。一旦链路断开, 则通过以下方法通知网络中其余节点:1) 断开的链路度量值为∞。2) 节点检测路由表, 下一跳经过该链路的路由表项的度量值标记为∞, 并分配一个新的序列号, 且为奇数, 以区别于信宿发出的更新报文。3) 触发“递增更新”报文的立即发送。经过以上过程, 在较短时间内, 该链路的变化将通告到网络的各个节点。 (4) 路由选择准则。DSDV中路由选择的准则为:序列号新或度量值小。
DSDV协议操作实例:在图2及表1表2中, MHi (i=1, 2, …, 8) 表示节点标识, SXXX_MHi (i=1, 2, …, 8) 发出更新报文的序列号为XXX。以MH2为例, 当MH1移动, 成为MH7的邻居时, MH1与MH3的链路断开。表1和表2分别为MH1移动前和移动后MH2的路由。
3.2 AODV协议
AODV路由协议[5]是按需驱动的距离矢量路由协议, 使用目的序列号和经典的距离矢量算法, 具有对动态链路的快速自适应, 处理和存储开销小, 网络利用率小等优点。AODV路由协议最明显的特征是每条路由均使用一个目的节点序列号, 能够确保路由是开环的。该序列号由目的节点产生, 与发送给路由请求节点的信息相组合。协议由两部分组成:路由请求和路由维护。
AODV的路由请求 (RREQ) 包含下列项[6]:
<跳数;路由请求码;目的地址;目的序列号;源地址;源序列号>
收到请求报文的节点, 查看路由表中是否有到目的节点更新的路由, 即目的序列号大于等于请求报文中的序列号。若没有, 该节点将记录请求报文的信息并广播;若有或节点是目的节点, 则将发送路由应答报文 (RREP) 给源节点。RREP包含如下项:
<跳数;目的地址;目的序列号;源地址;寿命>
转发RREP的节点根据RREP更新路由表, 并将RREP转发给先前记录的上游节点, 直至源节点S, 此时由源节点到目的节点的路由已建立。
AODV通过周期性的广播Hello报文来监视链路状态[7], 若节点在使用过程中发现某条链路断开, 则将从自身的路由表中删除包含该链路的路由, 并发送“路由出错”报文 (RERR) 给因链路断开而不可达的节点, 沿途转发RERR的节点并同时删除自身路由表中的对应路由。如图3所示, 节点6为目的节点, 由于节点4从4处移动到4'处, 导致节点3到目标节点的链路中断。图3 (a) 所示为RERR通知过程, 图3 (b) 所示为重新建立的路由。
3.3 DSR协议
DSR是动态源路由协议[7,8], 其最重要的特点是利用了源路由, 即发送方知道到达目的地的完整路径, 可实现节点间跨越多跳传输空间进行通信。DSR路由协议包括路由寻找和路由维护两个主要机制, 共同作用于移动Ad Hoc网络, 完成源路由的寻找和维护。
(1) 路由寻找。当节点S有分组要发送至节点D, 而S并未找到任何可用的路由, 那么节点S就通过路由寻找协议来动态的寻找一条可达节点D的新路由。如图4所示, 源节点S试图寻找一条路由到达目的节点D。
节点S的路由寻找进程执行如下:1) 节点S按照本地广播分组方式发送路由请求 (RREQ) , 被当前正处在节点S的无线电波覆盖范围的所有节点所接受, 如节点A。RREQ识别路由寻找的源节点和目的节点, 也包含了由源节点确定的唯一请求识别码 (Request ID) 。RREQ还包含一个记录列表, 用于记录该RREQ被成功转发的中间节点。2) 当另一个节点接收到该RREQ时, 若该节点是目标节点, 则给源节点回送一个路由应答 (RREP) , 同时回送在路由寻找过程中的路由记录, 源节点接受到该RREP后, 存储该路信息。否则, 若接受到该RREQ的节点已经收到另一个来自相同源节点、具有相同请求识别码和目标节点的RREQ, 或该节点已经发现自己的地址已在该RREQ的路由记录中, 那么该节点认为该路由请求已被接受, 即丢掉该路由请求;否则该节点将自己的地址添加到该RREQ的记录中, 然后按照本地广播分组方式将该路由请求发送出去。3) 目的节点D收到RREQ后, 要给源节点S回送路由应答 (RREP) , 先检查自己是否有到达源节点S的路由, 如果有, 则目的节点D通过这条路由将RREP交付给源节点S;否则, 目的节点D执行自己的路由寻找, 找出到达源节点S的路由。
(2) 路由维护。当使用某条源路由发送分组时, 该路由中的节点均要通过应答 (Acknowledgement) 机制来保证该分组能够顺利到达下一跳节点。若一个应答请求发送后仍未得到回应, 则需要重发, 当重发次数达到最大值时, 发送节点则认为到下一节点的链路已经断开, 同时从路由表中删除该断开链路, 并给该源路由上的节点回传一个路由错误 (Router Error) 。
如图5所示, 若节点B经过若干次应答请求后, 仍未接收到节点C的回应, 则B认为到C的链已断开, 同时从路由表中删除该断开链路, 并给S及所有同样的节点回传一个路由错误。若S的路由表中存在另一条到达D的路由, 则S使用该条路由, 否则S应执行一个新的路由寻找来获取一条可到达D的新路由。
4 MANET路由协议发展方向
目前, MANET路由协议的研究多集中在设计路由协议, 用来支持网络节点之间的高效通信。MANET路由协议的性能和多样性仍有较大的提高空间, 其中包括以下几个方面: (1) 路由安全性。MANET与传统网络结构上的差异导致传统网络中的安全机制不再适用于MANET。对于MANET来说, 路由安全具有重要的地位, 也是较难解决的问题。路由协议是网络攻击的主要目标, 然而目前已经提出的路由协议在安全方面鲜有涉及, 因此提高路由协议的安全是今后的研究方向。 (2) 路由协议的节能问题[9]。由于MANET没有固定基础设施的支持, 单个节点必须依靠可携带的电源提供能量。网络的发展导致单个节点的能量消耗越来越大, 这就使得减少节点的耗能显得尤为重要。目前的许多协议都没有节能策略, 因此这方面的问题仍有待进一步的研究。
参考文献
[1]张程.移动自组网的关键技术研究[D].重庆:重庆大学, 2010.
[2]陈林星.移动Ad Hoc网络-自组织分组无线网络技术[M].北京:电子工业出版社, 2006.
[3]李振宇.移动自组网中路由协议的分析与研究[D].北京:北京邮电大学, 2006.
[4]AMITH K.Step by step procedural comparison of DSR, AODV and DSDV Routing protocol[C].Torolento:ICCET, 2012.
[5]吴翠萍, 蔡明.AODV路由协议的改进[J].计算机工程与应用, 2012, 48 (24) :91-94.
[6]SARITA R, SINGH B, BHADAURIA W, et al.Bandwidth reservation routing technique based on agent in mobile ad hoc networks using rate control with AODV[C].Amsterdam:ICNCS, 2012.
[7]KHATAWKAR S D, PANDYAJI K K.Performance comparison of DSDV, AODV, DSR routing protocols for MANETs[C].Paris:ICCNC, 2012.
[8]SANGEETA B, SUNEETA M.Study of DSR routing protocol in mobile adhoc network[C].Nanjing:ICINT, 2011.
自组织路由协议 篇7
由于航空自组网具有动态拓扑、有限带宽、多跳路由、自组织、存在单向信道等特点,对在其上运行的路由协议便提出了许多具体而严格的要求。因此,路由协议的设计和选取一直是航空自组网中的重点和难点。
1 航空自组网中的路由协议
在航空自组网中,由于节点的高速移动导致拓扑结构动态、随机且快速地变化,这样常规路由协议在拓扑结构变化时,就会花很大代价重新使路由收敛,占用大量的网络资源,致使信息的传输无法实现。目前,典型的航空自组网路由协议以目的节点序列距离矢量(Destination Sequence Distance Vecto,DSDV)和按需距离矢量(Ad Hoc on Demand Distance Vector,AODV)路由协议为代表,特别是伴随着卫星定位系统的发展,基于地理信息的栅格路由协议(Grid Routing Protocol,GRID)也越来越受亲睐。
相关文献已经研究了多种适应于航空通信环境中的路由协议,但对这些协议的性能分析和比较还不够全面。文献[3,4]指出AODV等按需路由协议应用于航空自组网会出现路由发现的时延较大,文献[5]仿真表明DS-DV等先验路由协议会产生大量的网络开销,而且收敛速度慢。文献[6]提出的GRID路由协议可以避免路由探测分组的盲目洪泛广播,进行有效的路由发现和路由维护。但这些文献研究重点都放在了比较各路由算法本身在网络中所占用的开销,而没有深入研究不同路由协议对业务的影响。
本文重点研究了DSDV、AODV和GRID对网络性能的影响,采用路由开销、端到端平均延时、分组丢失率和平均跳数这4个指标作为衡量网络性能的标准。
2 路由协议描述
2.1 DSDV路由协议
DSDV路由协议[7]是一种主动路由协议,维护的路由表采用触发式的更新机制,并且会根据触发机制周期性地在网络中进行广播和更新。其基本思想是在传统Distance-Vector算法的基础上采用序列号机制,给每个路由设定序列号来区分新旧路由,网络中的每一个节点维护一个路由表,路由表中记录着到达网络中所有节点的路由信息,比如路由路经、目的节点序列号和到达目的节点的跳速。其中,目的节点序列号用于区别有效和过期的路由信息,从而避免了失效路由和环路的产生。
DSDV路由表的更新策略是周期性的,所以每个节点的路由表会周期性地进行更新,这种更新对于网络拓扑结构的变化是有利的,而且路由表更新频率会伴随着网络拓扑结构的变化而进行调整,从而保证路由的时效性。
2.2 AODV路由协议
AODV路由协议[8]是一个纯粹的按需路由系统,不在路径内的节点不保存路由信息,也不参与路由表的交换。AODV路由协议可以实现在移动终端间动态、自发地路由,使移动终端很快获得通向所需目的地的路由,同时又不用维护当前没有使用的路由信息,并且还能很快对断链的拓扑变化作出反应。
AODV的操作是无环路的,在避免了通常Bellmanford路由算法的无穷计数问题的同时,还提供了很快的收敛速度。AODV的路由表中每项都使用了目的节点序列号,该序列号是目的节点创建并在发给源节点的路由信息中使用的,使用目的节点序列号可以避免路由环路的发生。
2.3 GRID路由协议
GRID路由协议[9,10]是基于地理信息的完全感知型路由协议,其基本原理是网络中的每一个节点都配有一个可以对自身地理位置和移动状态进行精确定位和测量的装置,如GPS,在数据传输之前,源节点通过定位装置确定目的节点的地理位置并将该位置信息写入数据包的头部,然后数据包会根据目的节点的位置信息选择合适的路径进行数据转发直至该目的节点。
GRID路由协议把整个网络划分为若干个等边虚拟栅格,在每一个栅格中通过一定的策略选取一个节点担当网关,负责通过所在栅格内所有数据包的转发工作。
3 路由连通性能评估准则
3.1 路由开销
路由开销是指节点发送的用来进行路由查询或路由维护等目的的控制报文数。在逐跳的路由查询过程中,对于每一跳所转发的路由报文都需要计算在这个开销之内,路由开销反映了一个路由协议是否具有可扩展性。在主动路由协议(如DSDV)中,主要的路由开销是由节点位置广播造成的更新开销(Location-Update-Overhead,LUO),而在按需路由协议(如AODV)和地理路由协议(如GRID)中,主要的路由开销则是由路由发现引起的搜索开销(Rout-Search-Overhead,RSO),LUO伴随着节点位置更新广播频率的增大而不断增加,同时,这种节点位置更新广播频率的增大也降低了用于路由发现的搜索范围,即随着节点位置更新广播频率的增大,RSO是一个递减的过程,所以,LUO和RSO在某一个频点A时,会取得相同的值,如图1所示。
而在实际场景中,节点位置更新的广播频率是伴随着网络拓扑结构的变化而变化的,所以,网络拓扑结构的变化会影响路由开销,例如,网络中移动节点的运动情况、网络中节点的分布情况都会对路由开销造成影响。具体的,路由开销可表示为
式中:RSO表示搜索开销;LUO表示更新开销。即当RSO与LUO之和最小时,路由开销得到极值RCmin。
3.2 端到端平均延时
网络的端到端延时(End-to-End Delay)定义为数据分组从源节点的发起直到被目的节点正确接收所经历的时长。端到端延时反映了网络中业务处理的响应时间,当信道资源缺乏或网络拥塞严重时,传输延时将会增大,因此该性能参数是系统实时性以及拥塞状况的一个重要衡量指标。具体如
式中:D(i)表示第i个分组的传输时延;RT(i)表示第i个分组的接收时间;ST(i)表示第i个分组的发送时间。通常,对式(2)取均值,可以得到端到端平均延时,即
式中:N代表分析脚本中N个分组。进一步通过对不同分组的端到端时延进行统计计算,可以得到时延抖动(Delay-Jitter),时延抖动可以定义为前后两个分组的时延之差,即
而在实际网络中,常对最小时延Dmin和最大时延Dmax进行均值处理,然后用均值时延和这两者进行比较,即
当式(5)所得到的值在允许的阈值之内,那么可以认定网路的时延抖动J较小,网络的稳定性好。
3.3 分组丢失率
分组丢失率(Packet-Loss-Rate)是指网络在转发数据分组的过程中,被丢弃的数据分组个数占源节点发出的数据分组个数的比例。发生分组丢失的原因很多,例如网络拥塞、接收分组的缓冲区不足、TTL值超过门限值以及无线信号的同频干扰等。分组丢失率反映了网络连通性能的效率,当网络发生分组丢失的现象时,数据的传输会受到影响,例如在视频传输过程中出现分组丢失,则会出现马赛克现象。分组丢失率也从一个侧面反映了路由协议的适应性和鲁棒性,具体可表示为
式中:NSP表示节点发送的总的分组数目,NRP表示节点接收到的分组数目。通常分组丢失率也可以用分组投递率PGR来间接表示,即
即分组投递率越大或者分组丢失率越小,网络的连通性能效率越高。
3.4 平均跳数
平均跳数(Mean-Hop)是指从源节点到目的节点,完成一条路由经历所有中继节点的跳数的均值。具体的,平均跳数可以通过两个方面解释:如果侧重网络中数据包分组的发送情况,平均跳数可以定义为分组转发的总次数(Fowd-Packet)与分组总个数(Number of Send Packet)的比值,即
式中:分组总个数NSP包括成功转发的分组个数(Number of Send Packet Success,NSPS)与被丢弃的分组个数(Number of Send Packet Loss,NSPL),为了简化程序,一般忽略被丢弃的分组个数。
同样的,如果侧重网络中拓扑结构的情况,可以直接通过对源节点和目的节点之间路由经历的中继节点的个数进行统计,得到相关跳数的统计均值,即
式中:M表示源节点和目的节点之间存在的链路的个数;N(i)表示第i条链路所经历的中继节点的个数。
平均跳数受到路由协议策略以及节点有效辐射半径的影响,平均跳数的增多会导致网络路由开销的非线性增加,从而间接地造成网络拥塞和分组丢失。
4 仿真及性能分析
仿真软件采用NS2,节点个数设定为50,单跳距离为500 m,移动速度为0～100 m/s,暂停时间设置为10 s,仿真时间为2 000 s。仿真区域大小设为变量,决定节点密度。节点移动模型采用适用于航空环境的RWP模型。路由协议采用AODV路由协议、DSDV路由协议和GRID路由协议,以此来验证按需路由协议、主动路由协议和基于地理信息路由协议在航空自组网环境中的性能。
4.1 路由开销
由图2可以得到,随着网络中节点密度的增大,DS-DV路由协议的路由开销总体呈现出一个先逐渐增大,然后平缓增大的趋势,这是由于节点密度逐渐增大,节点之间的相对位置变化度就会逐渐增大,即路由对节点的运动情况比较敏感,需要对路由表进行频繁更新,所以路由协议会根据路由策略增大节点位置广播的频率,从而进一步使路由开销增大。
在AODV路由协议中,路由开销伴随着节点密度的增大,呈现出一个先增大后减小的过程,而且总体路由开销比DSDV路由协议的开销要高,这首先说明了路由发现过程引起的路由开销要比节点位置广播的更新开销要大,其次说明了在AODV路由协议中,路由发现引起的路由开销并不会因为节点密度的逐渐增大而无限增大,而是在达到一定的程度后开始逐渐降低,这是由于大量的路由发现过程会导致丢包现象的产生。
在GRID路由协议中,路由开销整体呈现出一个较平稳的过程,没有出现路由开销急剧增加和突然减小的情况,这是由于GRID路由协议中,每个栅格网关节点的分布具有一定的概率平稳性,而且由于有限泛洪式的路由发现策略,路由开销不会因节点密度的变化而发生过大的变化。
4.2 端到端平均延时
如图3所示,从整体情况看到AODV路由协议的端到端平均延时最小,DSDV路由协议次之,GRID路由协议最大。这是由于在DSDV路由协议中,数据包的收发过程会选择最短路径和最少跳数的路由,而AODV路由协议和DSDV路由协议具有类似的路由策略,但同时也具备了DSR路由协议的良好路由发现策略,所以端到端平均延时对比有所提升。而GRID路由协议的端到端平均延时有一个逐渐增大随后平缓的过程,这反映出GRID路由协议的端到端平均延时相比较大,但是在高节点密度情况下趋于平稳,即在此情况下,时延抖动较小,网络的稳定性好。
4.3 分组丢失率
如图4所示,分组投递率都伴随着节点密度的增加,呈现出一个递增趋势,并且在节点密度到达一定值时趋于稳定,这说明了节点密度越大,节点间建链的概率越大,但是在节点密度逐渐变化的过程中,DSDV路由协议、AODV路由协议的分组投递率变化程度较大,说明这两种路由协议的分组投递率对于节点密度的变化比较敏感,路由协议的连通适应性和鲁棒性不佳;而GRID路由协议虽然也有变化,但是整体变化度不大,而且基本维持在一个比较好的数值范围内,所以得到GRID路由协议在分组投递率方面有优势。
4.4 平均跳数
伴随着节点密度的逐渐增加,DSDV路由协议、AODV路由协议和GRID路由协议的平均跳数都呈现出一个比较稳定的情况,如图5所示,DSDV路由协议的平均跳数最小,这主要是由于路由策略中路由寻求最短路径的本质特性而导致。AODV路由协议的平均跳数比DSDV路由协议的平均跳数稍大,这是由于AODV路由协议是在DSDV路由协议的基础上进行了路由策略的改进和提升。而GRID路由协议的平均跳数明显比以上两种路由协议的平均跳数要大,而且在某一个节点密度的情况下出现了一个比较明显的拐点,一方面说明了GRID路由协议必须要通过网关节点进行数据中继转发,会造成过多的跳数,另一方面也说明了节点密度发生的变化可以等效为栅格的尺寸划分变化,而且,在某一个特定的节点密度下,平均跳数会出现一个极值。
5 小结
本文通过NS2对AODV路由协议、DSDV路由协议和GRID路由协议进行仿真,并定义了4个准则,从这4个准则角度分析评价了这3种协议在航空自组网中的性能。得出的结论是,在航空自组网环境中,不同的路由协议性能和侧重点不同,所以在进行航空自组网的研究中,选择具有特定优势的路由协议以符合特定的应用需求至关重要。
参考文献
[1]徐雪飞,甘忠辉,刘芸江.基于地理信息的航空自组网路由协议综述[J].电讯技术,2011,51(5):133-138.
[2]SAKHAEE E,JAMALIPOUR A,KATO N.Aeronautical Ad Hoc net works[C]//Proc.IEEE WCNC.Las Vegas,USA:IEEE Press,2006:246-251.
[3]JOHNSON D B,MALTZ D A.Dynamic source routing in Ad Hocwireless networks[M].[S.l.]:Kluwer Publishing Company,1996.
[4]ROYER C E,DAS S R.Ad hoc on demand distance vector routing[C]//Proc.2nd IEEE Workshop on mobile Computing Systems andApplications.USA:IEEE Press,1999:90-100.
[5]PERKINS C E,BHAGWAT P.Highly dynamic destination se quenced distance vector routing(DSDV)for mobile computers[C]//Proc.ACM SIGCOMM Conference.USA:IEEE Press,1994:234-244.
[6]LIAO Wenhwa,SHEN Jangping.GRID:a fully location-aware rout ing protocol for mobile Ad Hoc networks[J].Telecommunication Sys tems,2001(18):61-84.
[7]TIAN D,SHAFIEE K,LEUNG V C M,et al.Position-based direc tional vehicular routing[C]//Proc.GLOBECOM.[S.l.]:IEEE Press,2009:1-6.
[8]BAKHOUYA M,COTTIN N.Performance evaluation of the location-based protocol DREAM for large mobile Ad hoc networks[C]//Proc.New Technologies,Mobility and Security.[S.l.]:IEEE Press,2008:1-6.
[9]CHAO Chihmin,SHEU Jangping,HU Chengta.Energy-conservinggrid routing protocol in mobile Ad Hoc networks[C]//Proc.Interna tional Conference on Parallel Processing.[S.l.]:IEEE Press,2003:265-272.