第06次课-移动计算技术--Ad-hoc路由技术

移动计算技术——MANETs专题：路由技术授课教师：赵蕴龙Email：[e-mail]移动自组网络路由技术路由概述(OSI参考模型)网络层定义网络操作系统通信用的协议为信息确定地址将逻辑地址和名字翻译成物理地址路由器的功能在网络层实现将多个子网连接在一起数据分组以最佳路径通过通信子网到达目的结点自组网协议面临的问题和挑战网络的自组性动态变化的网络拓扑结构有限的无线传输带宽单向信道的存在分布式的控制网络有限的网络安全生存时间较短移动自组网络路由技术自组网路由协议功能监控网络拓扑结构的变化交换路由信息确定目的节点的位置产生、维护以及取消路由选择路由并转发数据移动自组网络路由技术自组网对路由协议的要求收敛迅速提供无环路由避免无穷计算对终端性能无过高要求支持单向信道尽量简单实用移动自组网络路由技术自组网路由协议的设计自组网的网络拓扑结构较为固定●采用常规的路由协议基本可以解决自组网路由协议自组网的拓扑结构变化极为剧烈●除了采用泛洪(Flooding)协议外没有任何协议可以适应变化速度移动自组网络路由技术泛洪协议无移动自组网络路由技术自组网路由协议三种设计思路●通过修改现有的常规路由协议以适应在自组网环境工作●基于按需路由发现的路由原则，结点是在发现没有去往目的结点的路由的时候按需发起路由请求●基于Qos路由，选择一条最有可能满足用户Qos的路由移动自组网络路由技术自组网路由协议的分类非定理定位辅助路由定理定位辅助路由平面路由分层路由按需路由主动路由移动自组网络路由技术主动路由(周期性路由维护)只要到目的结点的路由存在，所需的时延最小花费开销较大尽可能使路由更新随拓扑结构的变化路由协议可能始终处于不收敛的状态DSDV、WRP、STARA、FSR等移动自组网络路由技术●按需路由无周期性路由信息广播，节省网络资源发送数据分组时，如果没有到目的节点的路由，需要进行路由发现数据分组因路由发现过程而被时延AODV、DSR、TORA等移动自组网络路由技术平面结构无特殊节点网络中业务流平均分散路由协议鲁棒性好不需要进行节点移动性管理可扩展性差，限制了网络的规模移动自组网络路由技术●分群路由网络由多个群组成，扩展性好适合大规模的自组网环境群首节点的可靠性和稳定性对全网性能影响较大节点在不同群之间的漫游所进行的移动管理要产生一定的开销移动自组网络路由技术协议性能比较分布式运行方式提供无环路路由按需进行协议操作安全性提供设备“睡眠”操作特性对单向信道的支持移动自组网络路由技术协议性能比较（定量分析）端到端的平均延时分组的平均递交率路由协议开销路由请求时间移动自组网络路由技术路由协议研究的发展趋势Qos(QualityofService)路由路由安全性路由协议的可扩展性路由协议的节能自组网互联支持单向信道定位辅助移动自组网络路由技术主动路由协议又称为表驱动路由协议、先应式路由协议路由发现策略类似于传统的路由协议每一个节点周期性地向其他节点发送最新的路由信息每一个节点都要保存一个或多个路由表来存储路由信息拓扑发生变化时，节点在全网内广播路由更新信息移动自组网络路由技术主动路由协议的特点不管有无通信需求，都要进行路由信息交换每个节点都要维护一张到其它节点的相对稳定的最新路由表通过全网广播路由更新信息来反映网络拓扑结构的变化，交换并更新路由信息不同路由协议只是所需要的路由表的种类、数量及更新路由信息的方法不同移动自组网络路由技术FSR协议鱼眼状态路由(FSR,FisheyeStateRouting)协议California大学LosAngeles分校的无线自适应移动实验室（WAM，WirlessAdaptiveMobilityLaboratory）开发简单、有效的链路状态(LS,LinkState)类型的主动路由协议移动自组网络路由技术规范（无线局域网络）2400~2483.5MHz频段上至少要使用75个调频信道最大发射功率为1W每个信道的占用时间不允许超过400ms移动自组网络路由技术FSR协议的思想FSR仅在邻居节点间交换完整的链路状态信息，而不再全网广播链路状态通过从邻居节点接收信息来进行更新链路信息的交换是周期性的而不靠事件触发,避免了在不可靠的无线环境中因链路中断引起的链路状态更新移动自组网络路由技术FSR协议的思想根据距离跳数的多少来划分范围，不同范围内周期性广播链路信息的频率不同，近高远低更新消息的传输范围，显著减少了网络中控制分组的数量减少了路由开销，具有潜在的可扩展性移动自组网络路由技术FSR协议的特性:协议简单使用最新的最短路径对节点的移动具有良好的稳健性仅和邻居节点部分交换路由更新信息路由更新产生的附加开销少路由信息周期性发送，不要求对分组采用可靠传递移动自组网络路由技术带宽扩展路由分组的发送和接收采用主动方式路由分组和一般数据分组分别进行处理每个节点维护的表项内容邻居列表拓扑表路由表移动自组网络路由技术邻居列表当节点收到一个链路状态信息后，对发送链路状态信息的节点在本节点邻居列表中的信息进行更新如果节点在一个邻居超时周期间隔内没有收到邻居节点的链路信息，节点将该邻居节点在邻居节点列表中的条目删除邻居列表维护的信息为邻居ID从该邻居节点接收消息的最近时刻移动自组网络路由技术拓扑表每个目的节点在该表中都占有一个条目条目包含三部分目的节点信息目的节点的链路状态信息可选择的有效项移动自组网络路由技术移动自组网络路由技术移动自组网络路由技术移动自组网络路由技术路由表路由表包含目的地址、下一跳地址及距离3个字段提供为网络中的其他目的节点转发分组的下一跳信息表项内容在拓扑表发生变化时更新移动自组网络路由技术数据分组的转发在路由表计算的基础上，数据可以实现逐跳转发源节点或者任意中间节点从数据分组中检索到目的节点从路由表中检索，将分组转发到下一跳节点重复直到分组最终到达目的节点移动自组网络路由技术按需路由协议反应式路由协议、源启动按需路由协议仅在需要路由时才由源节点创建拓扑结构和路由表的内容是按需建立的可能仅仅是整个拓扑结构信息的一部分节省系统开销移动自组网络路由技术按需路由的3个过程路由发现路由维护路由拆除源节点在全网内发起路由发现过程通信过程进行路由维护，通常由低层提供的链路失效检测机制进行触发通信结束后，路由拆除过程将路由取消移动自组网络路由技术典型的按需路由协议动态源路由协议DSR（DynamicSourceRoutingProtocol）按需驱动距离矢量路由协议AODV（AdHocOn-DemandDistanceVectorRouting）临时路由需求协议TORA（TemporallyOrderedRoutingAlgorithm）基于关联性的路由协议ABR（AssociativitybasedRouting）等AODV协议使用的最为广泛移动自组网络路由技术AODV协议的特点基于距离向量的路由协议每个路由都有目的序列号序列号由目的主机产生用于防止路由循环每当目的主机和相邻主机之间的拓扑发生变化它就会将目的序列号加1并将该号附加在路由回答中AODV同时还支持多址通信移动自组网络路由技术AODV协议使用的控制信息路由请求包RREQ(RouterRequests)路由确认包RREP(RouterReplies)路由错误包RERR(RouterErrors)通过这三种控制信息来发现路由、维护路由移动自组网络路由技术AODV协议的路由表主要内容目的IP地址目的序列号下一跳ip地址去往目的的跳数上一次跳数（lasthopcount）先辈列表生存时间移动自组网络路由技术AODV协议的路由表在维护路由表的过程中，节点会监视一个活动路由下一跳节点的情况当下一跳节点不可用时，一条活动路由发生了断链该节点发送RERR消息通知先辈节点移动自组网络路由技术AODV协议的路由表先辈列表移动自组网络路由技术AODV协议路由发现按需路由不在活跃路径上的节点不会维持任何相关路由信息不在活跃路径上的节点不参与任何周期路由交换节点不发现和维护不与之通信节点的路由移动自组网络路由技术AODV协议路由发现当源节点想与另外一个节点通信时，如果路由表中没有相应的路由信息，发起路由发现过程每一个节点维护两个独立的计数器节点序列号计数器广播标识计数器源节点通过向自己的邻居广播RREQ分组来发起一次路由发现过程移动自组网络路由技术RREQ的格式跳数广播标识RREQID目的节点IP目的节点序列号源节点IP源节点序列号移动自组网络路由技术RREQ的格式源地址，广播标识唯一确定了一个RREQ分组当源节点发送一个新的RREQ分组时，广播标识计数器加1收到RREQ的邻居节点或者向源节点发送路由响应RREP，或者增加该RREQ分组跳数后，重新向自己的邻居广播该RREQ移动自组网络路由技术一个节点可能从不同邻居节点收到同一个广播的多个副本如果节点收到了相同广播标识和源节点地址的RREQ，则丢弃如果节点没有收到这样的RREQ分组，它保存一些信息用于建立反向路径，然后再把这个RREQ广播出去移动自组网络路由技术反向路由的建立一个节点可以回应一个RREQ，当且仅当它是目的节点本身或是它有一个通往目的节点的比较新的路径源节点序列号用来维持到源节点的反向路由的最新特性当节点获得新的邻居节点信息时序列号被加1一个收到RREQ的节点首先更新他的路由表以记录源节点的序列号和nexthop信息移动自组网络路由技术反向路由的建立当RREQ分组从一个源节点转发到不同的目的节点时，沿途经过的节点都要自动建立到源节点的反向路由节点通过记录收到的第一个RREQ分组的邻居地址来建立反向路由这些反向路由会维持一段时间，该时间足够RREQ分组在网内转发以及产生RREP分组返回源节点移动自组网络路由技术RREP分组当RREQ分组到达目的节点，目的节点就会产生RREP分组并利用反向路由返回源节点RREP格式跳数目的节点IP目的节点序列号源节点IP生命期移动自组网络路由技术正向路由的建立当分组到达一个节点，该节点可能是目的节点或该节点有到达目的节点的路由节点首先检查收到的RREQ是否是从双向链路上来的如果中间节点有到达目的的路由项，比较路由项里的目的序列号和RREQ分组的目的序列号如果中间节点的路由新则返回RREP分组移动自组网络路由技术正向路由的建立在RREP返回源节点的过程中，沿着反向路径的每一个节点都建立到目的节点的正向路由记录RREP是从哪一个邻居节点来的地址更新有关源和目的路由的定时器信息记录RREP中目的节点的最新序列号移动自组网络路由技术移动自组网络路由技术正向路由的建立收到RREP的节点对某一个源节点的第一个RREP分组进行转发同一源节点的RREP，只有当后到分组中包含了更高的序列号，才进行转发相同序列号，选择经过的跳数较少保证了最新最快的路由移动自组网络路由技术AODV路由的维护源节点移动，向目的节点重新发起路由查找中间节点或目的节点移动，转发一个特殊的RREP－RERR分组到那些受影响的源节点节点周期性发送Hello分组可以用来确保链路的对称性，并检测不可用的链路节点发现下一跳不可达，发送RERR给前辈节点重新发送RREQ分组开始新的路由发现过程移动自组网络路由技术路由维护移动自组网络路由技术AODV局部连接性管理监控网络拓扑结构变化交换路由信息定位目标节点的位置产生和维护路由移动自组网络路由技术AODV局部连接性管理节点可以通过收到邻居节点的广播消息来知道邻居的存在更新自己的局部连接性信息表，使它包含该邻居节点采用Hello分组，节点在预置Hello分组时间间隔内，没有向所有下游邻居节点发送任何分组，则要广播Hello分组表明它的存在移动自组网络路由技术AODV协议的优点基于传统的距