AdHoc网络路由.ppt

自组织网络路由协议,课程主要内容,概述体系结构Ad Hoc网络路由,内容提要,概述体系结构Ad Hoc网络路由,基于预先架设网络基础设施的无线网络,蜂窝网络移动终端通过基站接入移动通信网络,无线局域网移动终端通过无线接入点接入Internet,依赖于基站、无线接入点等现有基础设施网络,自组织网络的应用需求,临时会议/紧急情况科学考察/探险/军事战场接入网络服务商所需的时间和成本现有服务和架构的性能或者能力远离网络基础设施而希望保持与网络的连接,无网络基础设施可用,不想使用网络设施,网络基础设施范围外,自组织网络,自组织网的起源,1972年分组无线网（PRNET）战场环境下的数据通信1983年抗毁自适应网络（SURAN）支持大规模网络适应战场快速变化环境需要的自适应网络协议1994年全球移动通信系统（GloMo）满足军事应用需要的、可快速展开、高抗毁星的移动信息系统,DARPA资助Defense Advanced Research Project Agency,自组织网络研究,1991年IEEE 802.11首次提出“Ad Hoc网络”自组织、对等式、多跳无线移动通信网络1997年IETF成立MANET工作组基于IP的无线多跳网络路由2003年IRTF成立ANS研究组其它研究机构,Closed,Ad Hoc：For the specific purpose only,MANET：Mobile Ad-hoc NetworksANS：Ad Hoc Networks Scalability,Ad Hoc网络的定义,由一组带有无线通信收发装置的(移动)终端节点组成的一个多跳临时性自治系统每个(移动)终端同时具有路由器和主机两种功能：作为主机，终端需要运行面向用户的应用程序；作为路由器，终端需要运行相应的路由协议节点间路由通常由多跳(Hop)组成不需要网络基础设施，可以在任何地方、任何地点快速构建,多跳无线网络、自组织网络、无固定设施的网络或者对等网络,Ad Hoc网络的特点（1）,独立组网不需要任何预先网络基础设施动态拓扑节点移动/开机/关机节点无线发送功率变化、无线信道干扰或者地形等因素影响自组织无控制中心节点故障不会影响到整个网络,节点之间通过无线连接形成的网络拓扑结构随时可能发生变化，而且变化的方式和速度可能都是无法预测的,Ad Hoc网络的特点（2）,多跳路由接收端和发送端可使用比两者直接通信小得多的功率进行通信，因此节省了能量消耗通过中间节点参与分组转发，能够有效降低对无线传输设备的设计难度和成本，同时扩大了自组织网络的覆盖范围,Ad Hoc网络的特点（3）,特殊的无线信道特征无线信道提供的网络带宽比有线信道低得多竞争无线共享信道产生碰撞信号衰落、噪声干扰以及信道之间的干扰等终端的局限性能量、存储、计算等资源受限安全性差无线链路的开放性移动性导致节点之间信任关系的变化可扩展性不强节点之间的相互干扰造成网络容量下降各节点吞吐量随网络节点总数的增加而下降存在单向无线信道终端发射功率的不同及地形环境的影响,Ad Hoc网络与Sensor网络,Sensor网络可以看作是一种特殊类型的Ad Hoc网络各个无线节点静态地随机分布在某一区域。传感器负责收集区域内的传感信号，将它们发到网关节点网关具有更大的处理能力，能进一步处理信息，并且具有更大的发送范围，可将信息送往某个大型网络（Internet）并且到达最终的用户,与一般Ad Hoc网络相比：节点数量多、分布稠密节点的能量、计算、存储等资源进一步受限,Ad Hoc网络与无线局域网,单跳与多跳研究重点不同通信模式不同,主要研究集中在物理层和数据链路层,移动终端的所有通信必须经过无线接入点进行,无线局域网为单跳网络，不存在路由问题,Ad Hoc网络的研究内容主要以路由协议为核心的网络层设计,Ad Hoc网络中移动终端的通信是对等的,移动Ad Hoc网络(MANET)与移动IP,MANET,移动IP,Ad Hoc网络所面临的问题(1),特殊的信道共享方式共享信道隐藏节点问题/暴露节点问题动态变化网络拓扑传统路由协议花较高代价获取的路由信息可能已经陈旧有限的无线传输带宽减少节点之间的交换的消息减少控制消息带来的额外开销有限的能量能量管理机制，各层考虑能量控制，包括网络层路由安全问题无线信道的开放性更容易受到各种攻击移动性使得节点的信任关系不断变化由于节点资源受限，安全机制应该是分布式的,RTS/CTS，CSMA/CA,网络路由时需考虑,Ad Hoc网络所面临的问题(2),网络管理拓扑管理确定将一组节点组织成网络的机制移动性管理跟踪网络中移动节点的位置服务质量管理多跳拓扑动态变化的移动Ad Hoc网络使得服务质量保证更加困难自动配置,实现Ad Hoc网络的关键技术,路由协议服务质量管理功率控制传输层性能Ad Hoc网络互联安全问题网络管理,感知网络拓扑结构的变化维护网络拓扑的连接高度自适应性能量、服务质量等约束,信道接入技术节能机制,多个Ad Hoc网络互联Ad Hoc内部节点访问Internet,内容,概述体系结构Ad Hoc网络路由,节点结构,主机：运行应用程序，完成数据处理等功能路由器：运行路由协议，完成路由选择、转发分组等功能无线收发装置：完成数据传输功能,网络结构,平面结构所有节点地位平等层次结构网络被划分为簇（Cluster）每个簇由簇首节点(Cluster Head)和簇成员节点(Cluster Member)构成簇首节点可形成更高一级的网络,平面结构,层次结构,平面结构和层次结构比较,网络协议栈,基于TCP/IP体系结构与Internet互联传统路由协议需要修改，以适应网络拓扑结构动态变化传输层实现适应于无线网络的端到端可靠服务Ad Hoc网络多用于能量受限的环境，能量管理尤为重要，因此各层都定义相应的节能机制,可选功能,Ad Hoc网络中的跨层设计,严格分层的体系结构(OSI参考模型，TCP/IP模型)协议的设计缺乏足够的适应性，不能满足Ad Hoc网络动态变化的需求，特别是在能量或者QoS等约束条件下跨层体系结构任意层之间能够进行信息交互协作在动态环境下，根据能量或者QoS等约束条件自适应调节避免重复的功能，减少开销减少反应时间，快速适应网络动态变化,内容,概述体系结构Ad Hoc网络路由,Ad Hoc路由概述,需要进行通信的两个节点可能不在相互的无线信号范围内需要其它节点承担转发工作节点移动后需要重新建立新的路由,多跳路由,移动,MANET路由面临的问题,路由信息不易获得定期交换路由信息或者按需搜索路由的开销大网络资源有限，并且必须被所有节点共享节点资源（电池、CPU）等有限也许不能接收到所有的路由信息路由信息不完整移动和分区很难将信息分发到一个没有固定成员网络的所有节点路由信息可能过期不可能连续的或者立即交换信息节点随时移动无线传播变化大,MANET对路由协议的需求,收敛迅速提供无环路由避免无穷计算控制管理开销小对终端无过高要求支持单向信道尽量简单实用路由机制必须适应网络三个不断变化的基本特征移动节点的总体密度节点到节点的拓扑网络的使用模式,传统的路由协议不适用于Ad Hoc网络,动态变化的网络拓扑结构节点加入、离开、移动等路由算法还未收敛,网络拓扑结构就发生变化有限的系统带宽、能量等资源周期性地公告路由信息严重降低系统的性能间歇性的网络分割传统路由协议容易形成路由回路单向的无线传输信道传统路由协议一般假设链路是对称的,适应网络动态变化减少路由开销引入按需路由在路由时考虑能量等约束条件,路由协议,Ad Hoc路由协议,表驱动路由先应式(Proactive),按需路由反应式(Reactive),DYMO,OLSR:Optimized Link State RoutingTBRPF:Topology Dissemination Based on Reverse-Path Forwarding,AODV:Ad Hoc On Demand Distance VectorDSR:Dynamic Source Routing DTMO:Dynamic MANET On-demand Routing,表驱动（Table Driven）路由,先应式(Proactive)路由传统的分布式最短路径路由协议链路状态或者距离向量所有节点周期性更新“可达”信息每个节点维护到网络中所有其它节点的路由所有路由都已存在并且随时可用DSDV、OLSR、TBRPF,路由延时小，但是路由开销大,按需(On-demand)路由,反应式(Reactive)路由源节点根据需要通过路由发现过程来确定路由控制消息采用泛洪（Flooding）方式两种实现技术源路由（分组携带完整的路由信息）逐跳（Hop-by-Hop）路由DSR、AODV、DYMO,路由延时大，但是路由开销小,混合路由,Ad Hoc网络划分为区域每个节点在区域内部采用表驱动路由对于区域外节点采用按需路由簇和区域的不同簇内所有节点都与簇首直接通信，簇内节点间的通信一般是两跳区域的大小没有限制，区域内的节点通信可以多跳ZRP：Zone Routing Protocol,减少了域内的路由延时减少了域外的路由开销区域半径的选择小:节点移动快的密集网络大:节点移动慢的稀疏网络,Ad Hoc路由协议的性能指标,端到端数据吞吐量和延时反映了数据的传输质量路由获取时间有数据要发送到发送出去的时间乱序分组发送率衡量无连接路由协议应用于需要有序发送的传输层协议例如TCP时的性能路由协议的效率路由控制消息/发送数据,路由协议的性能在不同环境表现不同,因此需要根据环境特点使用不同的路由协议,表驱动（先应式）路由协议,带目的地序列号的距离向量协议(DSDV),Destination-Sequenced Distance-VectorDV(Distance Vector)算法DSDV协议,DV算法概述,基于分布式Bellman-Ford算法寻找从源点到某个点的最短路径每个节点都维护一张路由表所有可达的目的地到达目的地的下一跳到达目的地的“距离”（开销）节点向邻居节点发送路由更新消息定期更新：即使节点路由表无变化触发更新：节点路由表中某条路由发生变化路由更新消息包含列表格式节点在收到“更好”路由的情况下更新路由表具有更小的开销：对于同一个目的地，来自不同的下一跳更新开销：对于同一目的地，来自相同的下一跳,DV:Distance Vector,DV算法过程,初始化,A,B,C,3,2,路由更新,A,B,C,3,2,路由更新消息,DV算法中的计数到无穷问题,A,B,C,3,2,无穷计数！,DV算法不能直接用于Ad Hoc网络,计数到无穷问题部分解决方法选择一个相对较少的数作为无穷大水平分割(split horizon)：当一个节点把路由更新发送给相邻节点时，它并不把从各个相邻节点处学到的路由再回送给该节点,无法发现路由循环,限制了网络的可扩展性,对两个节点的路由循环有效，更大的路由循环需要更强的措施,DSDV协议概述,基于DV算法简单，易于实现需要的存储空间小（只须和邻居节点交换路由信息）确保无路由回路路由表中的每个表项都带有目的地序列号（由目的节点生成）对拓扑变化能作出快速反应路由表有显著变化时立即启动路由公告(Router Advertisement)但是等待不稳定路由的公告，以减缓路由波动(damping fluctuations)先应式（表驱动）路由节点维护到所有目的地的路由信息路由信息必须周期性的更新（无休眠节点）即使网络拓扑无变化也存在着通信开销维护的路由可能从不使用,DSDV:Destination-Sequenced Distance Vector,DSDV路由表,序列号（Sequence number）由目的端产生，用来防止出现路由回路，并确保路由信息是最新的格式：Dest_NNN加入时间（Install Time）路由表项的创建时间，用来删除过期表项Stable Data 指向一个包含有路由稳定状态信息的表目的节点地址最近沉淀时间（last settling time）平均沉淀时间(average settling time)用于缓解网络中的路由波动,对于同一个目的地，节点可能接收到来自其它节点的多条路由信息，settling time定义为第一条路由和最佳路由之间的时间间隔,DSDV路由公告,向每个邻居公告自己的路由信息目的节点地址Metric：到目的节点的开销，一般为到目的节点的跳数目的地序列号其它信息（例如硬件地址等）设置序列号信息的规则每次公告增加自己的目的地序列号（只使用偶数值）如果一个节点不再可达（timeout）,则将该节点的序列号加1（奇数序列号），并且设置metric为,DSDV路由选择,将更新信息与自己的路由表比较选择具有更大目的地序列号的路由，这将保证始终使用来自目的地的最新信息当序列号相等时，选择具有更好metric的路由,DSDV协议操作：更新前路由表,A,B,C,DSDV协议操作：路由公告,B递增序列号 100-102B向邻居A、C广播路由信息，其中包含有目的地序列号,A,B,C,DSDV协议操作：更新后路由表,A,B,C,对拓扑变化的反应,立即公告有关新路由、链路断开和metric变化的信息立即传递给邻居节点完全/增量更新完全更新：发送自己路由表中的所有路由信息增量更新：只发送路由表中那些发生变化的表项（能包含在一个单独的分组中发送）,DSDV协议操作：新节点加入,1.D第一次广播,发送序列号D-000,A,B,C,D,DSDV协议操作：新节点加入,2.插入到D的表项，序列号为D-000,A,B,C,D,DSDV协议操作：新节点加入,3.C递增自己的序列号到C-592，然后立即广播自己的新路由表,A,B,C,D,DSDV协议操作：新节点加入,4.B获取新的路由信息并且更新路由表,D从C获取路由表信息并且生成自己的路由表,A,B,C,D,DSDV协议操作：链路断开,因为B广播的到达D的路由信息中的序列号小于C维护的D的序列号，因此C认为B的广播的是过期路由信息，不予采纳,1.C检测到链路断开-序列号递增1(当且仅当这种情况不是目的节点设置序列号-奇数序列号),2.B广播到达D的路由信息,A,B,C,D,避免了循环,避免了计数到无穷,DSDV协议操作：立即公告,4.B立即传送更新消息给A(更新信息具有更大的序列号，因此将取代A中原有表项),3.C立即传递更新信息给B(更新信息具有更大的序列号，因此将取代B中原有表项),A,B,C,D,(D,D-101),DSDV协议操作：路由波动,2.A收到来自P的路由更新消息,10 Hops,11 Hops,A,P,Q,D,1.D公告序列号为D-102的路由,更新路由表中到D的表项立即进行路由公告,3.A收到来自Q的路由更新消息,更新路由表中到D的表项立即进行路由公告,由于D或者任何一个节点的路由更新消息到达节点A时存在着时间差,就会导致不必要的路由公告路由表波动,DSDV协议操作：减缓路由波动,在一个单独的表中记录每条路由的最近的和平均的Settling TimeSettling Time：第一条路由和最佳路由之间的时间间隔路由表中的stable data指向该表A在包含新序列号的第一条路由到达时更新路由表，但是等待一段时间再广播该条路由等待时间=2*(avg.Setting Time),10 Hops,11 Hops,A,P,Q,D,可缓解大型网络的路由波动问题，从而避免不必要的公告，节约了带宽,DSDV总结,优点简单（基本上与DV算法一致）通过目的地序列号避免了路由循环，解决了DV算法中的计数到无穷问题无路由发现延时（先应式路由）缺点所有节点都必须公告路由，因此不支持休眠（不能直接用于传感器网络）收敛慢（DV路由的特性）开销大：大部分的路由信息从不使用可扩展性是一个主要问题（所有先应式路由都存在的问题）,优化链路状态路由协议(OLSR),Optimized Link State Routing Protocol先应式的链路状态路由协议基于多点中继（MPR）的概念的优化只有MPR转发广播消息，减少了消息开销只有MPR产生链路状态信息，减少了网络中广播消息的数量MPR可能选择只报告它和该MPR选举节点之间的链路，因此在网络中只散发部分链路状态信息,RFC3626,基于拓扑广播的反向路径转发(TBRPF),Topology Broadcast based on Reverse-Path Forwarding本质上是一种链路状态协议协议组成邻居发现模块路由模块与传统链路状态协议的差别拓扑更新消息更小路由开销更少更适合拓扑迅速变化的无线网络,RFC3684,按需（反应式）路由协议,动态源路由协议(DSR),Dynamic Source Routing按需路由节点需要发送数据时才进行路由发现过程反应型路由，仅维护活跃的路由源路由发送节点在分组中携带到达目的节点的路由信息（转发分组的完整的节点序列）不需要中间节点维护路由信息节点缓存到目的节点的多条路由避免了在每次路由中断时都需要进行路由发现，因此能够对拓扑变化作出更快的反应，,DSR协议组成,路由发现（Route Discovery）只有在源节点需要发送数据时才启动帮助源节点获得到达目的节点的路由路由维护（Route Maintenance）在源节点在给目的节点发送数据时监测当前路由的可用情况当网络拓扑变化导致路由故障时切换到另一条路由或者重新发起路由发现过程,路由发现和路由维护都是按需进行的不需要周期性路由公告不需要感知链路状态不需要邻居检测,DSR路由发现：路由请求,源节点向邻居节点广播路由请求（RREQ：Route Request）消息源节点地址目的节点地址路由记录：记录从源节点到目的节点路由中的中间节点请求ID中间节点接收到RREQ后，将自己的地址附在路由记录中,A,B,C,D,E,F,(A-),(A-F),(A-),(A-B-),(A-B-C-),(A-B-C-),(A-B-C-E-),DSR路由发现：中间节点处理,中间节点维护序列对列表重复RREQ检测如果接收到的RREQ消息中的存在于本节点的序列对列表中如果接收到的RREQ消息中的路由记录中包含本节点的地址如果检测到重复，则中间节点丢弃该RREQ消息,A,B,C,D,E,F,(A-),(A-F),(A-),(A-B-),(A-B-C-),(A-B-C-),(A-B-C-E-),丢弃F转发的RREQ,DSR路由发现：路由应答,目的节点收到RREQ后，给源节点返回路由应答（RREP：Route Reply）消息拷贝RREQ消息中的路由记录源节点收到RREP后在本地路由缓存中缓存路由信息,(A-B-C-D),A,B,C,D,E,F,(A-B-C-D),(A-B-C-D),DSR路由发现：非对称信道,对称信道目的节点到源节点的路由即为源节点到目的节点的反向路由非对称信道如果目的节点的路由缓存中有到达源节点的路由，则直接使用否则目的节点需要发起到源节点的路由请求过程，同时将RREP消息附加在新的RREQ消息中,DSR路由维护,逐跳证实机制链路层确认被动确认（监听其它节点间的数据发送）其它高层要求DSR软件返回确认端到端证实机制无法确定故障发生的位置,DSR逐跳证实机制,如果数据分组被重发了最大次数仍然没有收到下一跳的确认，则节点向源端发送路由错误（Route Error）消息，并且指明中断的链路源端将该路由从路由缓存中删除如果源端路由缓存中存在另一条到目的节点的路由则使用该路由重发分组否则重新开始路由发现过程,A,B,C,D,E,F,(A-B-C-E-),Route Error,DSR优化：路由缓存(1),每个节点缓存它通过任何方式获得的新路由转发RREQ获得从本节点到RREQ路由记录中所有节点的路由，例如E转发RREQ(A-B-C)获得到到A的路由(C-B-A)转发RREP获得本节点到RREP路由记录中所有节点的路由，例如B转发RREP(A-B-C-D)获得到D的路由(C-D)转发数据分组获得从本节点到数据分组节点列表中所有节点的路由，例如E转发数据分组(A-B-C)获得到A的路由(C-B-A)监听相邻节点发送的分组RREQ、RREP、数据分组等,A,B,C,D,E,F,(A-),(A-F),(A-),(A-B-),(A-B-C-),(A-B-C-),(A-B-C-E-),以上均假设信道是对称的!,DSR优化：路由缓存(2),中间节点使用缓存的到目的节点的路由响应RREQRREP中的路由记录=RREQ中的路由记录+缓存的到目的节点的路由,A,B,C,D,E,F,(B-C-D),(A-B-C-D),(A-),DSR优化：路由缓存(3),错误路由缓存网络拓扑的变化使得缓存的路由失效影响和感染其它节点，使用该路由缓存的路由将不可用当节点根据路由缓存回应RREP时，其它监听到此RREP的节点会更改自己缓存的路由，从而感染错误路由缓存,设置缓存路由的有效期，过期即删除,DSR优化：路由缓存(4),RREP风暴节点广播到某个目的节点的RREQ，当其邻居节点的路由缓存中都有到该目的节点的路由时，每个邻居节点都试图以自己缓存的路由响应，由此造成RREP风暴RREP风暴将浪费网络带宽，并且加剧消息冲突,A,B,C,D,E,F,(B-A),G,(C-B-A),(F-A),(E-C-B-A),G发起到A的路由发现过程,DSR优化：路由缓存(5),预防RREP风暴每个节点延时D发送RREPD与节点到目的节点的跳数成正比，使得到目的节点有最短路径的RREP最先发送节点将接口设置成混杂模式(promiscuous)，监听是否存在有比自己更短的到目的节点的路径，如果有，则不发送本节点的RREP,D=H*（h-1+r）其中H是每条链路的传播延时h是自己返回的路径长度，即到目的节点的跳数r是0或者1,DSR总结,优点仅在需要通信的节点间维护路由，减少了路由维护开销路由缓存技术能够进一步减少路由发现的代价通过采用路由缓存技术，能够发现多条到达目的节点的路由支持非对称信道缺点采用源节点路由，每个数据分组头标中都要携带路由信息，增加了网络开销由于采用广播，用于路由发现的控制消息可能波及到全网节点，需要这些消息的传输距离（跳数）RREP风暴问题错误路由缓存问题,AODV协议,Ad Hoc On Demand Distance Vector RoutingAODV结合了DSR和DSDV使用DSR中基于广播的路由发现机制每个节点都维护路由表，采用DSDV逐跳(Hop-by-Hop)路由、序列号数据分组不再携带完整的路由信息仅维护活跃的路由AODV特点与DSDV协议相比,采用按需路由,不需要维护整个网络的拓扑信息,只有在发送分组且没有到目的节点的路由时才发起路由发现过程与DSR协议相比,由于节点建立和维护路由表,分组中不需携带完整的路由信息仅适用于对称信道路由表仅维护一条到目的节点的路由,RFC3561,混合路由协议,区域路由协议(ZRP),Zone Routing Protocol区域(zone)的划分整个网络被划分为若干个以节点为中心,一定跳数为半径的区域区域内节点数与设定的区域半径有关路由策略每个节点在区域内部采用表驱动路由对于区域外节点采用按需路由,ZRP路由架构,区域内路由协议(IARP:IntrAzone Routing Protocol)采用表驱动路由协议，节点之间周期性地交换路由信息获得到域内各个节点的最新路由距离向量路由协议DSDV等链路状态路由协议OLSR等完成区域内部节点间的路由功能区域间路由协议(IERP:IntErzone Routing Protocol)采用按需路由协议完成与区域外节点间的路由功能边界传播协议(BRP:Bordercast Resolution Protocol)BRP协议使得路由查询分组只在边界节点之间广播,ZRP路由过程,Z(A)=A,B,C,D,E,FA发现节点I不在自己的区域内，向边界节点E、F、D广播路由请求消息边界节点E收到路由请求消息后，发现节点I在自己的区域内，直接回复路由应答消息,H,I,路由请求消息,路由应答,ZRP总结,综合利用了按需路由和表驱动路由的优点在区域内减少了路由发现时间在区域间减少了系统开销区域半径的设置将直接影响到路由的效率,内容,概述体系结构Ad Hoc网络路由服务质量和能量意识,Ad Hoc路由中的服务质量,与传统网络相比，更困难网络拓扑动态变化资源受约束扩展路由协议支持QoS基于表驱动的QoS路由协议按需QoS路由协议,Ad Hoc路由中的能量意识,Ad Hoc网络环境下节点的能量受限基于能量约束的路由协议最小化每消息能量消耗考虑每跳之间消耗的能量固定(T为常数)，该约束实际上与最小跳数一致最大化网络生存时间保证所有节点协同工作的时间尽量的长,