《ADHOC路由协议图解.pdf》由会员分享，可在线阅读，更多相关《ADHOC路由协议图解.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1http:/Copyright 2006 YAN Wei.All rights reserved.1第二十一讲第二十一讲移动移动ad hocad hoc网络网络http:/Copyright 2006 YAN Wei.All rights reserved.2移动移动ad hocad hoc网络基础知识网络基础知识?基本要求?熟练掌握MANET基本概念?掌握MANET路由体系?掌握DSDV协议思想?掌握DSR协议思想?阅读?5.2.9?参考资料?主要内容?MANET概述?MANET路由概述?主动路由&DSDV?按需路由&DSR?层次路由概述http:/Copyright 2006 YAN W
2、ei.All rights reserved.3移动无线网络移动无线网络?蜂窝移动通信网络?移动终端和固定基站互相通信?移动终端不具备路由功能?基站负责路由和交换功能?基站充当接入有线网络的网关Internet Internet http:/Copyright 2006 YAN Wei.All rights reserved.4移动无线网络移动无线网络?WLAN?移动节点配备无线网网卡?移动节点通过接入点与固定网络连接?WLAN工作在链路层，对网络层透明?对网络层来说WLAN是一个单跳网络依赖于类似基站或接入点的现有网络基础设施。?Internet Internet http:/Copyrig
3、ht 2006 YAN Wei.All rights reserved.5移动互联网的需求移动互联网的需求?特殊环境（空旷）?临时会议/紧急情况?科学考察/探险/军事战场?接入网络服务商所需的时间和成本?现有服务和架构的性能或者能力?用户可远离网络基础设施而保持与网络的连接无网络设施可用无网络设施可用不想使用不想使用网络设施网络设施延伸网络设施的范围延伸网络设施的范围http:/Copyright 2006 YAN Wei.All rights reserved.6移动互联网的起源移动互联网的起源?源自军事领域?20世纪70年代分组无线网（PRNET）?1983年的抗毁自适应网络（SURAN）
4、?1994年的全球移动信息系统（GloMo）?IEEE802.11首次提出“ad hoc”?IETF1997年成立MANET工作组?IRTF在2003成立了ANS 研究组DARPA资助MANETMANET：mobile ad hoc networkmobile ad hoc networkANS ANS：Ad Hoc Networks ScalabilityAd Hoc Networks Scalability2http:/Copyright 2006 YAN Wei.All rights reserved.7移动移动ad hocad hoc网络网络?移动Ad hoc网络/多跳无线网络?由一组
5、带有无线通信收发装置的移动终端节点组成?网络中每个终端可以自由移动、地位相等?是一个多跳、临时、无中心网络?不需要现有信息基础网络设施的支持?可以在任何时候、任何地点快速构建Ad hoc Ad hoc?“for the specific purpose onlyfor the specific purpose only”http:/Copyright 2006 YAN Wei.All rights reserved.8移动移动ad hocad hoc网络的特点网络的特点?具备移动通信网络和计算机网络的特点?网络拓扑动态变化?无中心网络的自组性?多跳组网方式?有限的无线传输带宽?移动终端的自主性
6、?安全性差?网络的可扩展性不强?存在单向的无线信道?生存时间短?多跳无线网?自组织网络?无固定设施?对等网络http:/Copyright 2006 YAN Wei.All rights reserved.9移动移动ad hocad hoc网络与其他网络比较网络与其他网络比较?与常规移动通信网络比较?不需要网络通信基础设施支持?不依赖基站进行通信?分组交换机制?数据通信业务为主?拓扑结构动态变化?与传统固定网络比较?固定网络中主机位置基本不变?固定网络结构一般比较复杂?ad hoc网络规模相对较小?ad hoc网络的拓扑结构比较简单?ad hoc网络拓扑结构快速变化http:/Copyrigh
7、t 2006 YAN Wei.All rights reserved.10ad hocad hoc网络与其他网络（续）网络与其他网络（续）?与分组无线网、无线局域网、红外网络比较?单跳与多跳?研究重点不同?通信模式不同导致Ad hoc网络的研究内容主要以路由协议为核心的网络层设计WLAN、红外网络都是单跳网络，不存在路由问题移动终端的所有通信都要经过接入点进行ad hoc移动终端的通信是对等的主要研究内容是在网络的物理层和DLhttp:/Copyright 2006 YAN Wei.All rights reserved.11ad hocad hoc网络应用现状与前景网络应用现状与前景Nova
8、的无线移动路由器http:/Copyright 2006 YAN Wei.All rights reserved.12实现实现ad hocad hoc网络的关键技术网络的关键技术?路由协议?服务质量?功率控制?安全问题?Ad hoc网络的互联?Ad hoc网络的资源管理?传输层服务的性能?感知网络拓扑结构的变化?维护网络拓扑的连接?高度自适应的路由?广播和多播?信道接入技术?能耗节约机制?多个ad hoc网络互联?内部节点访问Internet功能3http:/Copyright 2006 YAN Wei.All rights reserved.13Ad hocAd hoc网络的多跳通信网络的多
9、跳通信?通信两点可能不在相互的无线传输范围内?需要其他节点承担路由器的转发工作?节点移动要发现新路由ABChttp:/Copyright 2006 YAN Wei.All rights reserved.14Ad hocAd hoc路由面临的困难路由面临的困难?路由信息不易获得?定期交换路由信息或者按需搜索路由的开销大?网络资源有限，并且必须被所有节点共享?节点资源（电池、CPU 等）也是有限?也许不可能收集齐所有的路由信息?路由信息不完整?由于移动和分区很难将信息分发到一个没有固定成员网络的所有节点?路由信息可能过期?不可能连续地或者立即地交换信息?节点随时移动?无线传播变化很大http:/
10、Copyright 2006 YAN Wei.All rights reserved.15常规路由协议是否可用？常规路由协议是否可用？?常规路由协议不是为移动性和低带宽网络设计的?DV算法存在“无穷计算”问题和慢收敛?采用泛洪技术的（链路状态）协议造成额外的通信和控制开销?常规路由协议周期性地路由更新消耗大量的网络带宽和节点能源?当网络节点失效和网络分区时形成路由回路?无线终端功率的差异以及无线信道的干扰导致单向信道的存在http:/Copyright 2006 YAN Wei.All rights reserved.16Ad hocAd hoc网络对路由协议的要求网络对路由协议的要求?收敛迅
11、速?提供无环路由?避免无穷计算?控制管理开销小?对终端无过高要求?支持单向信道?尽量简单实用?路由机制必须适应网络三个不断变化的基本特征?移动节点的总体密度?节点到节点的拓扑?网络的使用模式http:/Copyright 2006 YAN Wei.All rights reserved.17Ad hocAd hoc路由协议分类路由协议分类?平面路由?无需建立具有特殊cluster头功能节点的层次结构；?不划分区域以及所谓的区内/外不同路由?所有的节点在路由机制中地位平等?寻址方式是平面的?层次路由?节点功能不同?寻址方式是分层进行的?地理信息辅助路由?利用地理信息进行路由选择http:/Cop
12、yright 2006 YAN Wei.All rights reserved.18非地理定位辅助路由非地理定位辅助路由表驱动表驱动(Proactive)(Proactive)DSDVCGSR按需驱动按需驱动(Reactive)(Reactive)LMRABRTORA SSROLSROLSRTBRPFTBRPFWRPFSRFSLSSTARA平面路由平面路由分层路由分层路由ZRPHSRCEDARLANMAR地理定位辅助路由地理定位辅助路由LARDREAMGPSRGeoCastAd hocAd hoc单播路由协议单播路由协议DSRDSRAODVAODV4http:/Copyright 2006 Y
13、AN Wei.All rights reserved.19主动路由主动路由?表驱动（Table driven）路由?先应式路由机制?传统的分布式最短路径路由协议链路状态或者距离向量所有节点连续更新“可达”信息?每个节点维护到网络中所有节点的路由?所有路由都已经存在并且随时可用?路由请求的延迟低?路由开销大?OLSR、TBRPFhttp:/Copyright 2006 YAN Wei.All rights reserved.20DV DV 协议能否适应协议能否适应MANETMANET?DV的固有缺点?无法发现路由回路?“无穷计算”问题?DSDV(Destination-sequenced dis
14、tance vector)?没有全局拓扑视图?主动先应式路由?每个节点维护到所有已知目的地的路由信息?路由信息必须定期更新?即使网络拓扑没有变化也有通信开销?维护的路由可能从来不用DV不能直接用在MANEThttp:/Copyright 2006 YAN Wei.All rights reserved.21DSDVDSDV协议特点协议特点?保持了DV算法的简单性?确保无路由回路?新的路由表带有目标序列号?对于拓扑变化能快速反应?当路由表发生重大变化时立即启动route advertisement?但是延迟不稳定路由的通告(减缓路由波动)http:/Copyright 2006 YAN Wei.
15、All rights reserved.22DSDVDSDV路由表路由表?Sequence number?由目标节点确定，用来保证不出现路由回环?Install time?该表项的创建时间(用来删除表中过时路由信息)?Stable data?用来缓解路由波动DestDest.ABCDNextNextABBBMetricMetric0134Seq.noSeq.noA-550B-102C-588D-312Install timeInstall time001000001200001200001200Stable dataStable dataPtr_APtr_BPtr_CPtr_Dhttp:/Co
16、pyright 2006 YAN Wei.All rights reserved.23路由通告（路由通告（route advertisementroute advertisement）?向每个邻居通告自己的路由信息?目标地址?metric=到目标的跳计数?目的地的序号?设置序号的规则?每次通告递增自己的目标序号（只用偶数值）?如果一个节点不再可达(timeout)，则将该节点的序号递增1(奇数值)并置metric=http:/Copyright 2006 YAN Wei.All rights reserved.24路由选择路由选择(Route(Route Selection)Selection
17、)?将收到的路由更新信息与自己的路由表比较?选择目标序号大的路由(这样能确保使用的总是来自目的地的最新路由信息)?如果目标序号相同，则选择具有较好metric值的路由。5http:/Copyright 2006 YAN Wei.All rights reserved.25DSDVDSDV实例实例A AB BC C12DestDest.NextNextMetricMetric Seq.Seq.AA0A-550BB1B-100CB3C-588DestDest.NextNextMetricMetric Seq.Seq.AA1A-550BB0B-100CC2C-588DestDest.NextNext
18、MetricMetric Seq.Seq.AB3A-550BB2B-100CC0C-588111http:/Copyright 2006 YAN Wei.All rights reserved.26DSDVDSDV实例（续）实例（续）A AB BC C11222向邻居发送路由表100-102向邻居发送路由表100-102DestDest.NextNextMetricMetric Seq.Seq.AA0A-550BB1B-102CB2C-588DestDest.NextNextMetricMetric Seq.Seq.AA1A-550BB0B-102CC1C-588DestDest.NextNe
19、xtMetricMetric Seq.Seq.AB2A-550BB1B-102CC0C-588(A,1,A-550)(B,0,B-102)(C,1,C-588)(A,1,A-550)(B,0,B-102)(C,1,C-588)http:/Copyright 2006 YAN Wei.All rights reserved.27对拓扑变化的响应对拓扑变化的响应?立即通告?有关新路由、链路中断、metric变化的信息立即传播给邻居?完全/增量更新?Full Update?发送自己路由表的全部路由信息?Incremental Update?仅发送路由表中有变化的表项(使得可用一个分组完成更新)htt
20、p:/Copyright 2006 YAN Wei.All rights reserved.28增加一个新节点增加一个新节点A AB BC C11223D D1(D,0,D-000)(A,2,A-550)(B,1,B-104)(C,0,C-592)(D,1,D-000)DestDest.NextNextMetricMetric Seq.Seq.AA0A-550BB1B-104CB2C-590DestDest.NextNextMetricMetric Seq.Seq.AA1A-550BB0B-104CC1C-590DestDest.NextNextMetricMetric Seq.Seq.AB2
21、A-550BB1B-104CC0C-592DD1D-0003.C递增自己的序号 C-592，然后广播自己的新路由表。2.C将D插入自己的路由表1.D第一次广播自己用序号000http:/Copyright 2006 YAN Wei.All rights reserved.29增加一个新节点增加一个新节点A AB BC C11244D D1(A,2,A-550)(B,1,B-104)(C,0,C-592)(D,1,D-000)DestDest.NextNextMetricMetric Seq.Seq.AA0A-550BB1B-104CB2C-590DestDest.NextNextMetricM
22、etric Seq.Seq.AA1A-550BB0B-104CC1C-592DestDest.NextNextMetricMetric Seq.Seq.AB2A-550BB1B-104CC0C-592DD1D-0004.B更新自己的路由表DC2D-000http:/Copyright 2006 YAN Wei.All rights reserved.30如何解决路由回环和无穷计算？如何解决路由回环和无穷计算？A AB BC C11445D D1DestDest.NextNextMetricMetric Seq.Seq.DestDest.NextNextMetricMetric Seq.Seq.
23、DestDest.NextNextMetricMetric Seq.Seq.DDD-1011.C检测到链路中断-将序号递增1DC2D-100XDB3D-1002.B继续广播自己的路由表(D,2,D-100)(D,2,D-100)因为B广播的有关D的序号小于C维护的D序号，因此C认为B的路由信息过时，不予采纳。无环避免“无穷计算”6http:/Copyright 2006 YAN Wei.All rights reserved.31立即通告立即通告A AB BC C11555DestDest.NextNextMetricMetric Seq.Seq.DestDest.NextNextMetric
24、Metric Seq.Seq.DestDest.NextNextMetricMetric Seq.Seq.DDD-1013.C立即传播路由变化DCD-101DBD-1014.B用序号大的信息更新自己的路由表项，并立即通告给邻居(D,D-101)(D,D-101)http:/Copyright 2006 YAN Wei.All rights reserved.32DSDVDSDV总结总结?优点?非常简单（几乎与DV算法一致）?通过目的地赋予的序号值来防止出现路由回环?不存在路由发现带来的延迟?缺点?不能有节点睡眠?开销可能白费?多数路由信息从不使用http:/Copyright 2006 YAN
25、 Wei.All rights reserved.33按需（按需（onon-demanddemand）路由协议）路由协议?反应式（reactive）路由?在源端需要时候通过路由发现过程来确定路由?控制信息采用泛洪（flooding）方式?路由请求延迟高?路由开销低?两种实现技术?源路由（报文头携带完整的路由信息）?hop-hop路由?DSR、AODVhttp:/Copyright 2006 YAN Wei.All rights reserved.34按需操作的优点按需操作的优点?路由发现和维护都是按需进行的?不需要周期性地通告路由?不需要感测链路状态?不需要邻居检测?不依赖于任何底层协议htt
26、p:/Copyright 2006 YAN Wei.All rights reserved.35动态源路由协议（动态源路由协议（DSRDSR）?Dynamic Source Routing protocol?基于源路由概念的按需自适应路由协议?允许节点动态发现到任何目的地source route?中间节点不必存储转发分组所需的路由信息?采用Cache存放路由信息?允许网络完全自我组织和自我配置?因其简单而有效成为首选协议?网络开销较小?存在陈旧路由DraftDraft-ietfietf-manetmanet-dsrdsr-10.txt10.txthttp:/Copyright 2006 YAN
27、 Wei.All rights reserved.36DSRDSR协议描述协议描述?DSR协议由两个相互协同的机制组成?Route discovery?由需要发送数据给目标节点D的源节点S使用；?该过程只在S需要发送数据并且不知道到D的路由时才启动；?Route maintenance?S在给D发送数据时要能检测出由于网络拓扑动态变化导致源路由中断的情况；?当前的源路由不能用时S切换到另一条已知的路由或者重新发起route discovery 寻找新路由；7http:/Copyright 2006 YAN Wei.All rights reserved.37DSRDSR的多路径思想的多路径思想
28、?多路径获得的途径?作为route discovery的响应；?Overheard到其他路由控制包和数据包中的路由信息；?为任何目的地缓存多条路由；?多路径的作用?如果正在使用的一条路径中断，节点可立即切换到另一条缓存的路由；?多条路由的缓存可避免每次路由中断后执行route discovery；http:/Copyright 2006 YAN Wei.All rights reserved.38DSRDSR的单向链路支持能力的单向链路支持能力?DSR支持单向链路和非对称路由?天线不同?传播模式不同?干扰源不同?DSR支持不同类型无线网络的互联?有的节点使用短程无线电?有的节点使用长途无线电?
29、DSR将所有的节点都看成是一个ad hoc网络中的节点?DSR路由可集成到标准Internet路由中?DSR路由可集成到Mobile IP路由中提高网络的整体性能和网络连通性http:/Copyright 2006 YAN Wei.All rights reserved.39基本基本route discoveryroute discovery?源节点A将路由请求（Route Request）消息作为局部广播分组发送?Route discovery 的发起者A?Route discovery 的目标E?Request id?List(初始为空)：用来记录路由发现包经过的节点?所有位于A无线传输范
30、围内的节点都将收到该路由请求包A AB BC CD DE EA,Id=2A,BId=2A,B,CId=2A,B,C,DId=2ROUTE REQUESThttp:/Copyright 2006 YAN Wei.All rights reserved.40基本基本route discoveryroute discovery（续）（续）?如果目标节点E收到该请求包，给请求源A回答一个ROUTE REPLY消息?List：拷贝自ROUTE REQUEST?路由发现源收到ROUTE REPLY消息后在本地Route Cache中缓存路由信息A AB BC CD DE ED,C,B,AId=2D,C,B
31、,AId=2D,C,B,AId=2D,C,B,AId=2ROUTE REPLYRouteCacheA,B,C,D,Ehttp:/Copyright 2006 YAN Wei.All rights reserved.41基本基本route discoveryroute discovery（续）（续）?重复请求包的检测?如果中间节点收到了来自同一个源（A）请求id相同的请求包；?如果中间节点收到的请求包中路由记录已经包含本节点；?则中间节点丢弃该请求包；?中间节点对于未处理过的请求包?将自己的地址填入请求包的list位置；?将该请求包作为本地广播分组发送给邻居；http:/Copyright 20
32、06 YAN Wei.All rights reserved.42基本基本route discoveryroute discovery（续）（续）?无穷迭代的路由发现过程?如果目标端在route cache中没有找到去往路由发起端的路由信息，并且网络存在单向链路;?则需要发起新一轮route discovery 过程;?DSR规定目标端（E）可使用ROUTE REQUEST消息中记录的路由作为返回的ROUTE REPLY的源路由；?DSR规定目标端在发起逆向返回到源端的新一轮route discovery时，在ROUTE REQUEST 中“捎带”ROUTE REPLY消息；首选逆向路由可避免
33、有可能的第二次路由发现过程带来的开销8http:/Copyright 2006 YAN Wei.All rights reserved.43基本基本route maintenanceroute maintenance?路由的维护?每个节点确保使用源路由发送/转发的数据分组被路由中的下一跳接收；?如果没有收到下一跳的确认则不断重发（至最大重试次数）；?如何确保数据报被逐跳转发？?链路级的确认（IEEE802.11）;?被动确认（B侦听C向D转发）;?要求DSR软件返回确认;A AB BC CD DE EA,B,C,D各个节点分别确保将分组转发到下一跳http:/Copyright 2006 YA
34、N Wei.All rights reserved.44基本基本route maintenanceroute maintenance（续）（续）?如果数据分组被重发了最大次数仍然没有收到下一跳的确认，则节点（C）要向分组的源端发送ROUTE ERROR消息，并指明中断的链路；?分组的源端（A）将该路由从路由缓存中删除；?如果源端路由缓存中存在另一条到目标的路由则重发此分组；?否则，重新开始route discovery 过程；A AB BC CD DE EXROUTEERRORRouteCacheA,B,C,D,Ehttp:/Copyright 2006 YAN Wei.All rights
35、reserved.45DSRDSR协议优点协议优点?节点不需要周期性地发送路由广播分组?无须维持到全网所有节点的路由信息?节省了电池能量和网络带宽，尤其是当没有节点要发送数据时，网络中没有通信开销。?仅需要维护路径上节点之间的路由?能完全地消除路由环路?能同时提供多条路由?可用于单向信道?中间节点的应答使源节点快速获得路由http:/Copyright 2006 YAN Wei.All rights reserved.46DSRDSR协议缺点协议缺点?会引起过时路由问题?每个分组都需要携带完整的路由信息?造成开销增大?降低了网络带宽的利用率?不适合网络直径大的自组网?网络可扩展性不强http:
36、/Copyright 2006 YAN Wei.All rights reserved.47分级路由协议分级路由协议?分级路由协议?一些节点组成一个cluster或者zone?这些cluster或者zone可组成较大的supercluster或者superzone?Cluster和zone的不同?cluster内所有节点都与cluster head直接通信，cluster内节点间的通信一般是两跳。?zone的大小没有限制，zone内节点的通信可多跳。http:/Copyright 2006 YAN Wei.All rights reserved.48分级路由协议概念分级路由协议概念?无线分级路
37、由的基本思想?把节点划分为不同的cluster/zone，并对内外节点指定不同功能;?设计目的?减少参与路由计算的节点数，降低交换路由信息的通信开销，缩短路由表的长度和维护开销。?通过分区策略产生较为稳定的子网，减少拓扑结构变化对路由协议带来的影响9http:/Copyright 2006 YAN Wei.All rights reserved.49二级路由协议概念描述二级路由协议概念描述第一层网络cluster headCluster第一层网络第一层网络第一层网络第二层网络http:/Copyright 2006 YAN Wei.All rights reserved.50分级路由协议的优缺
38、点分级路由协议的优缺点?优点?网络拓扑结构的细节通过节点的层层聚合被隐藏起来，由此大大降低大型网络的存储要求。?路由信息分层传播，需要在全局传播的路由信息较少。?有限的链路状态维护?按需建立路由?缺点?分级路由协议的移动管理比较复杂?某些节点（cluster head/gateway）比其他节点承担更多的通信和计算负载。具有较好的伸缩性可靠性受影响http:/Copyright 2006 YAN Wei.All rights reserved.51评价评价ad hocad hoc网络路由协议的指标网络路由协议的指标?端-端的数据吞吐量和延迟?反映了数据报的传输质量?路由请求的时间?有数据需要发送到发送出去的时间?路由协议的效率?路由控制信息与数据信息的比率路由协议的性能在不同的网络环境中表现不同！http:/Copyright 2006 YAN Wei.All rights reserved.52