自组织网络.ppt

1、第十章 自组织网络,Resource,郑少仁等著，Ad Hoc网络技术，人民邮电出版社，2005年1月 IETF Mobile Ad-hoc Networks (MANET) Working Group /html.charters/manet-charter.html S. Corson, J. Macher, Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations, RFC 2501, January 1999

2、C. Perkins, E. Belding-Royer, et al., Ad hoc On-Demand Distance Vector (AODV) Routing, RFC 3561, July 2003 David B. Johnson, et al., The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR), draft-ietf-manet-dsr-10.txt, July 2004 I. Chakeres, C. Perkins, Dynamic MANET On-demand (DYMO) Ro

3、uting, draft-ietf-manet-dymo-06.txt, October 2006 T. Clausen, et al., Optimized Link State Routing Protocol (OLSR), RFC 3626, October 2003 R. Ogier, et al., Topology Dissemination Based on Reverse-Path Forwarding (TBRPF), RFC 3684, February 2004 S. Basagni et al, Mobile Ad Hoc Networking, IEEE Press

4、 (John Wiley & Sons), 2004,内容,概述 体系结构 Ad Hoc网络路由 服务质量和能量意识,内容,概述 体系结构 Ad Hoc网络路由 服务质量和能量意识,基于预先架设网络基础设施的无线网络,蜂窝网络 移动终端通过基站接入移动通信网络,无线局域网 移动终端通过无线接入点接入Internet,依赖于基站、无线接入点等现有基础设施网络,自组织网络的应用需求,临时会议/紧急情况 科学考察/探险/军事战场 接入网络服务商所需的时间和成本 现有服务和架构的性能或者能力 远离网络基础设施而希望保持与网络的连接,无网络基础设施可用,不想使用网络设施,网络基础设施范围外,自组织网络,

5、自组织网的起源,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研究组 其它研究机构

6、,Closed,Ad Hoc：For the specific purpose only,MANET：Mobile Ad-hoc Networks ANS：Ad Hoc Networks Scalability,Ad Hoc网络的定义,由一组带有无线通信收发装置的(移动)终端节点组成的一个多跳临时性自治系统 每个(移动)终端同时具有路由器和主机两种功能：作为主机，终端需要运行面向用户的应用程序；作为路由器，终端需要运行相应的路由协议 节点间路由通常由多跳(Hop)组成 不需要网络基础设施，可以在任何地方、任何地点快速构建,多跳无线网络、自组织网络、无固定设施的网络或者对等网络,Ad Hoc网络

7、的特点（1）,独立组网 不需要任何预先网络基础设施 动态拓扑 节点移动/开机/关机 节点无线发送功率变化、无线信道干扰或者地形等因素影响 自组织 无控制中心 节点故障不会影响到整个网络,节点之间通过无线连接形成的网络拓扑结构随时可能 发生变化，而且变化的方式和速度可能都是无法预测的,Ad Hoc网络的特点（2）,多跳路由 接收端和发送端可使用比两者直接通信小得多的功率进行通信，因此节省了能量消耗 通过中间节点参与分组转发，能够有效降低对无线传输设备的设计难度和成本，同时扩大了自组织网络的覆盖范围,Ad Hoc网络的特点（3）,特殊的无线信道特征 无线信道提供的网络带宽比有线信道低得多 竞争无线

8、共享信道产生碰撞 信号衰落、噪声干扰以及信道之间的干扰等 终端的局限性 能量、存储、计算等资源受限 安全性差 无线链路的开放性 移动性导致节点之间信任关系的变化 可扩展性不强 节点之间的相互干扰造成网络容量下降 各节点吞吐量随网络节点总数的增加而下降 存在单向无线信道 终端发射功率的不同及地形环境的影响,Ad Hoc网络与Sensor网络,Sensor网络 可以看作是一种特殊类型的Ad Hoc网络 各个无线节点静态地随机分布在某一区域。传感器负责收集区域内的传感信号，将它们发到网关节点 网关具有更大的处理能力，能进一步处理信息，并且具有更大的发送范围，可将信息送往某个大型网络（Internet

9、）并且到达最终的用户,与一般Ad Hoc网络相比： 节点数量多、分布稠密 节点的能量、计算、存储等资源进一步受限,Ad Hoc网络与无线局域网,单跳与多跳 研究重点不同 通信模式不同,主要研究集中在物 理层和数据链路层,移动终端的所有通信必 须经过无线接入点进行,无线局域网为单跳网 络，不存在路由问题,Ad Hoc网络的研究 内容主要以路由协议 为核心的网络层设计,Ad Hoc网络中移动 终端的通信是对等的,移动Ad Hoc网络(MANET)与移动IP,MANET,移动IP,Ad Hoc网络所面临的问题(1),特殊的信道共享方式 共享信道 隐藏节点问题/暴露节点问题 动态变化网络拓扑 传统路由

10、协议花较高代价获取的路由信息可能已经陈旧 有限的无线传输带宽 减少节点之间的交换的消息 减少控制消息带来的额外开销 有限的能量 能量管理机制，各层考虑能量控制，包括网络层路由 安全问题 无线信道的开放性更容易受到各种攻击 移动性使得节点的信任关系不断变化 由于节点资源受限，安全机制应该是分布式的,RTS/CTS，CSMA/CA,网络路由时需考虑,Ad Hoc网络所面临的问题(2),网络管理 拓扑管理 确定将一组节点组织成网络的机制 移动性管理 跟踪网络中移动节点的位置 服务质量管理 多跳拓扑动态变化的移动Ad Hoc网络使得服务质量保证更加困难 自动配置 ,实现Ad Hoc网络的关键技术,路由

11、协议 服务质量管理 功率控制 传输层性能 Ad Hoc网络互联 安全问题 网络管理,感知网络拓扑结构的变化 维护网络拓扑的连接 高度自适应性 能量、服务质量等约束,信道接入技术 节能机制,多个Ad Hoc网络互联 Ad Hoc内部节点访问Internet,内容,概述 体系结构 Ad Hoc网络路由 服务质量和能量意识,节点结构,主机：运行应用程序，完成数据处理等功能 路由器：运行路由协议，完成路由选择、转发分组等功能 无线收发装置：完成数据传输功能,网络结构,平面结构 所有节点地位平等 层次结构 网络被划分为簇（Cluster） 每个簇由簇首节点(Cluster Head)和簇成员节点(Clu

12、ster Member)构成 簇首节点可形成更高一级的网络,平面结构,层次结构,平面结构和层次结构比较,网络协议栈,基于TCP/IP体系结构 与Internet互联 传统路由协议需要修改，以适应网络拓扑结构动态变化 传输层实现适应于无线网络的端到端可靠服务 Ad Hoc网络多用于能量受限的环境，能量管理尤为重要，因此各层都定义相应的节能机制,可选功能,Ad Hoc网络中的跨层设计,严格分层的体系结构(OSI参考模型，TCP/IP模型) 协议的设计缺乏足够的适应性，不能满足Ad Hoc网络动态变化的需求，特别是在能量或者QoS等约束条件下 跨层体系结构 任意层之间能够进行信息交互协作 在动态环境

13、下，根据能量或者QoS等约束条件自适应调节 避免重复的功能，减少开销 减少反应时间，快速适应网络动态变化,内容,概述 体系结构 Ad Hoc网络路由 服务质量和能量意识,Ad Hoc路由概述,需要进行通信的两个节点可能不在相互的无线信号范围内 需要其它节点承担转发工作 节点移动后需要重新建立新的路由,多跳路由,移动,传统的路由协议不适用于Ad Hoc网络,动态变化的网络拓扑结构 节点加入、离开、移动等 路由算法还未收敛,网络拓扑结构就发生变化 有限的系统带宽、能量等资源 周期性地公告路由信息严重降低系统的性能 间歇性的网络分割 传统路由协议容易形成路由回路 单向的无线传输信道 传统路由协议一般

14、假设链路是对称的,适应网络动态变化 减少路由开销 引入按需路由 在路由时考虑能量等约束条件,路由协议,Ad Hoc路由协议,表驱动路由 先验式(Proactive),按需路由 反应式(Reactive),DYMO,OLSR: Optimized Link State Routing TBRPF: Topology Dissemination Based on Reverse-Path Forwarding,AODV: Ad Hoc On Demand Distance Vector DSR: Dynamic Source Routing DTMO: Dynamic MANET On-deman

15、d Routing,表驱动（Table Driven）路由,先验式(Proactive)路由 传统的分布式最短路径路由协议 链路状态或者距离向量 所有节点周期性更新“可达”信息 每个节点维护到网络中所有其它节点的路由 所有路由都已存在并且随时可用 DSDV、OLSR、TBRPF,路由延时小，但是路由开销大,按需(On-demand)路由,反应式(Reactive)路由 源节点根据需要通过路由发现过程来确定路由 控制消息采用泛洪（Flooding）方式 两种实现技术 源路由（分组携带完整的路由信息） 逐跳（Hop-by-Hop）路由 DSR、AODV、DYMO,路由延时大，但是路由开销小,混合路

16、由,Ad Hoc网络划分为区域 每个节点在区域内部采用表驱动路由 对于区域外节点采用按需路由 簇和区域的不同 簇内所有节点都与簇首直接通信，簇内节点间的通信一般是两跳 区域的大小没有限制，区域内的节点通信可以多跳 ZRP：Zone Routing Protocol,减少了域内的路由延时 减少了域外的路由开销 区域半径的选择 小: 节点移动快的密集网络 大: 节点移动慢的稀疏网络,Ad Hoc路由协议的性能指标,端到端数据吞吐量和延时 反映了数据的传输质量 路由获取时间 有数据要发送到发送出去的时间 乱序分组发送率 衡量无连接路由协议应用于需要有序发送的传输层协议例如TCP时的性能 路由协议的效

17、率 路由控制消息/发送数据,路由协议的性能在不同环境表现不同, 因此需要根据环境特点使用不同的路由协议,表驱动（先验式）路由协议,带目的地序列号的距离向量协议(DSDV),Destination-Sequenced Distance-Vector DV (Distance Vector)算法 DSDV协议,DV算法概述,基于分布式Bellman-Ford算法 寻找从源点到某个点的最短路径 每个节点都维护一张路由表 所有可达的目的地 到达目的地的下一跳 到达目的地的“距离”（开销） 节点向邻居节点发送路由更新消息 定期更新：即使节点路由表无变化 触发更新：节点路由表中某条路由发生变化 路由更新消

18、息包含列表格式 节点在收到“更好”路由的情况下更新路由表 具有更小的开销：对于同一个目的地，来自不同的下一跳 更新开销：对于同一目的地，来自相同的下一跳,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)：当一个节点把路由更新发送给相邻节点时，它并不把从各个相邻节点处学到的路由再回送给该节点,无法发现路由循环,限制

19、了网络的可扩展性,对两个节点的路由循环有效，更大的路由循环需要更强的措施,DSDV协议概述,基于DV算法 简单，易于实现 需要的存储空间小（只须和邻居节点交换路由信息） 确保无路由回路 路由表中的每个表项都带有目的地序列号（由目的节点生成） 对拓扑变化能作出快速反应 路由表有显著变化时立即启动路由公告(Router Advertisement) 但是等待不稳定路由的公告，以减缓路由波动(damping fluctuations) 先验式（表驱动）路由 节点维护到所有目的地的路由信息 路由信息必须周期性的更新（无休眠节点） 即使网络拓扑无变化也存在着通信开销 维护的路由可能从不使用,DSDV:

20、Destination-Sequenced Distance Vector,DSDV路由表,序列号（Sequence number ） 由目的端产生，用来防止出现路由回路，并确保路由信息是最新的 格式： Dest_NNN 加入时间（Install Time） 路由表项的创建时间，用来删除过期表项 Stable Data 指向一个包含有路由稳定状态信息的表 目的节点地址 最近沉淀时间（last settling time） 平均沉淀时间 (average settling time) 用于缓解网络中的路由波动,对于同一个目的地，节点可能接收到来自其它节点的多条路由信息，settling time

21、定义为第一条路由和最佳路由之间的时间间隔,DSDV路由公告,向每个邻居公告自己的路由信息 目的节点地址 Metric：到目的节点的开销，一般为到目的节点的跳数 目的地序列号 其它信息（例如硬件地址等） 设置序列号信息的规则 每次公告增加自己的目的地序列号（只使用偶数值） 如果一个节点不再可达（timeout）,则将该节点的序列号加1（奇数序列号），并且设置metric为,DSDV路由选择,将更新信息与自己的路由表比较 选择具有更大目的地序列号的路由，这将保证始终使用来自目的地的最新信息 当序列号相等时，选择具有更好metric的路由,DSDV协议操作：更新前路由表,A,B,C,DSDV协议操作

22、：路由公告, , ,B递增序列号 100 - 102 B向邻居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协议操作：新节点加入, ,

23、 ,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(更新信息具有更大的序列号

24、，因此将取代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协议操作：减缓路由波动,在一个单独的表中记录每条路由的最近的和平均的S

25、ettling Time Settling Time：第一条路由和最佳路由之间的时间间隔 路由表中的stable data指向该表 A在包含新序列号的第一条路由到达时更新路由表，但是等待一段时间再广播该条路由 等待时间=2*(avg. Setting Time),10 Hops,11 Hops,A,P,Q,D,可缓解大型网络的路由波动问题， 从而避免不必要的公告，节约了带宽,DSDV总结,优点 简单（基本上与DV算法一致） 通过目的地序列号避免了路由循环，解决了DV算法中的计数到无穷问题 无路由发现延时（先验式路由） 缺点 所有节点都必须公告路由，因此不支持休眠（不能直接用于传感器网络） 收敛

26、慢（DV路由的特性） 开销大：大部分的路由信息从不使用 可扩展性是一个主要问题（所有先验式路由都存在的问题）,优化链路状态路由协议(OLSR),Optimized Link State Routing Protocol 先验式的链路状态路由协议 基于多点中继（MPR）的概念的优化 只有MPR转发广播消息，减少了消息开销 只有MPR产生链路状态信息，减少了网络中广播消息的数量 MPR可能选择只报告它和该MPR选举节点之间的链路，因此在网络中只散发部分链路状态信息,RFC3626,基于拓扑广播的反向路径转发(TBRPF),Topology Broadcast based on Reverse-Pa

27、th Forwarding 本质上是一种链路状态协议 协议组成 邻居发现模块 路由模块 与传统链路状态协议的差别 拓扑更新消息更小 路由开销更少 更适合拓扑迅速变化的无线网络,RFC3684,按需（反应式）路由协议,动态源路由协议(DSR),Dynamic Source Routing 按需路由 节点需要发送数据时才进行路由发现过程 反应型路由，仅维护活跃的路由 源路由 发送节点在分组中携带到达目的节点的路由信息（转发分组的完整的节点序列） 不需要中间节点维护路由信息 节点缓存到目的节点的多条路由 避免了在每次路由中断时都需要进行路由发现，因此能够对拓扑变化作出更快的反应，,DSR协议组成,路

28、由发现（Route Discovery） 只有在源节点需要发送数据时才启动 帮助源节点获得到达目的节点的路由 路由维护（Route Maintenance） 在源节点在给目的节点发送数据时监测当前路由的可用情况 当网络拓扑变化导致路由故障时切换到另一条路由或者重新发起路由发现过程,路由发现和路由维护都是按需进行的 不需要周期性路由公告 不需要感知链路状态 不需要邻居检测,DSR路由发现：路由请求,源节点向邻居节点广播路由请求（RREQ：Route Request）消息 源节点地址 目的节点地址 路由记录：纪录从源节点到目的节点路由中的中间节点 请求ID 中间节点接收到RREQ后，将自己的地址附

29、在路由纪录中,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后，给源节点返回路由应答（RRE

30、P：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软件返回确认 端到端证实机制 无法确定故障发生的位置

31、,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路由纪录中所有节点的路由，例

32、如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),中间节点使用缓存的到目的节点的路由响应RREQ RREP中的路由纪录=RREQ中的路由纪录+缓存的到目的节点的路由,A,B,C,D,E,F,(B-C-D),(A-B-C-D),(

33、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发起

34、到A的路由发现过程,DSR优化：路由缓存(5),预防RREP风暴 每个节点延时D发送RREP D与节点到目的节点的跳数成正比，使得到目的节点有最短路径的RREP最先发送 节点将接口设置成混杂模式(promiscuous)，监听是否存在有比自己更短的到目的节点的路径，如果有，则不发送本节点的RREP,D=H*（h-1+r） 其中H是每条链路的传播延时 h是自己返回的路径长度，即到目的节点的跳数 r是0或者1,DSR总结,优点 仅在需要通信的节点间维护路由，减少了路由维护开销 路由缓存技术能够进一步减少路由发现的代价 通过采用路由缓存技术，能够发现多条到达目的节点的路由 支持非对称信道 缺点 采用源节点路由，每个数据分组头标中都要携带路由信息，增加了网络开销 由于采用广播，用于路由发现的控制消息可能波及到全网节