无线自组网-2资料

1、无线网络与移动计算技术无线自组织网络(wnglu)攻防原理与实践共六十七页基础知识概述(i sh)：Ad Hoc路由需要进行通信的两个节点可能不在相互的无线信号(xnho)范围内需要其它节点承担转发工作节点移动后需要重新建立新的路由多跳路由移动共六十七页传统的路由协议不适(bsh)用于Ad Hoc网络动态变化的网络拓扑结构节点加入(jir)、离开、移动等路由算法还未收敛,网络拓扑结构就发生变化有限的系统带宽、能量等资源周期性地公告路由信息严重降低系统的性能间歇性的网络分割传统路由协议容易形成路由回路单向的无线传输信道传统路由协议一般假设链路是对称的适应网络动态变化减少路由开销引入按需路由在路由

2、时考虑能量等约束条件共六十七页多条路由的发现(fxin)与维护常见自组网路由协议： 先应式（表驱动）、反应式（按需驱动）、混合式：先应式（表驱动）路由协议：节点无论当前是否有数据需要发送(f sn)，都事先计算出到所有节点的路由表，并且周期地进行维护和更新这些路由表以适应网络拓扑变化。优点：是路由发现无延迟缺点：是路由表维护花费的系统开销大。共六十七页多条路由的发现(fxin)与维护常见自组网路由协议： 先应式（表驱动）、反应式（按需驱动）、混合式：反应式（按需驱动）：只是在源节点有数据通信的需要时才计算路由优点：节电且不需要花费(hufi)代价来维护无用的路由缺点：路由发现延迟很大且不可预测

3、。混合式：局部使用先应式，广域使用按需路由算法。共六十七页路由协议(xiy)Ad Hoc路由协议(xiy)表驱动路由先验式(Proactive)按需路由反应式(Reactive)ZRPDSDVTBRPFCGSROLSRLMRABRDSRAODVTORASSRDYMOOLSR: Optimized Link State RoutingTBRPF: Topology Dissemination Based on Reverse-Path ForwardingAODV: Ad Hoc On Demand Distance VectorDSR: Dynamic Source Routing DTMO:

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

5、y-Hop）路由DSR、AODV、DYMO路由延时大，但是(dnsh)路由开销小共六十七页混合(hnh)路由Ad Hoc网络划分为区域每个节点(ji din)在区域内部采用表驱动路由对于区域外节点采用按需路由簇和区域的不同簇内所有节点都与簇首直接通信，簇内节点间的通信一般是两跳区域的大小没有限制，区域内的节点通信可以多跳ZRP：Zone Routing Protocol减少了域内的路由延时减少了域外的路由开销区域半径的选择小: 节点移动快的密集网络大: 节点移动慢的稀疏网络共六十七页Ad Hoc路由协议(xiy)的性能指标端到端数据吞吐量和延时反映了数据的传输质量路由获取时间有数据要发送到发送

6、出去的时间乱序分组发送率衡量无连接路由协议应用于需要有序发送的传输层协议例如TCP时的性能路由协议的效率路由控制(kngzh)消息/发送数据路由协议的性能在不同环境表现不同,因此需要根据环境特点使用不同的路由协议共六十七页Ad Hoc的协议(xiy)与协议(xiy)栈自组网中必须在一次通信时解决的问题(wnt)：如何将数据分组包含的比特转化为信号发送和接收？如何能够保证传输的信息比特可靠？多节点共享信道时，这些节点如何分配使用信道？路由表如何生成？网络拓扑变化的时候如何修改路由表？自组网研究过程中采用将协议栈分层的方法将问题分解到各个层分别加以研究。自组网采用ISO七层协议模型加以分析和研究。

7、最具特色的两层：MAC和网络层。7应用层6表示层5会话层4传输层3网络层2链路控制层MAC子层1物理层OSI 网络七层协议模型共六十七页 Ad Hoc的协议(xiy)与协议(xiy)栈自组网通信采用分组传输方式：首先将传输的数据打成若干个分组，然后依次(yc)传输例 A-B-C-D-E，B接收，查路由表，确定下一跳C，直至发给E数据分组结构=控制部分+数据部分。其中，控制部分=源地址+目的地址+其它控制信息数据部分=数据部分共六十七页2.3.3 多条路由的发现(fxin)与维护自组网路由协议的设计目标：要求计算(j sun)出的路由具有良好的性质，例如跳数少、链路稳定可靠、传输时延小等要求协议

8、能够快速地适应网络拓扑的变化要求路由计算与维护引入的控制的开销小移动共六十七页表驱动（先验(xin yn)式）路由协议共六十七页带目的地序列号的距离(jl)向量协议(DSDV)Destination-Sequenced Distance-VectorDV (Distance Vector)算法(sun f)DSDV协议共六十七页DV算法(sun f)概述基于分布式Bellman-Ford算法寻找从源点到某个点的最短路径每个节点都维护一张路由表所有可达的目的地到达目的地的下一跳到达目的地的“距离”（开销）节点向邻居节点发送路由更新消息定期更新：即使节点路由表无变化触发更新：节点路由表中某条路由发

9、生变化路由更新消息包含列表格式节点在收到“更好”路由的情况下更新路由表具有更小的开销：对于同一个目的地，来自不同的下一跳更新开销：对于同一(tngy)目的地，来自相同的下一跳DV: Distance Vector 共六十七页DV算法(sun f)过程初始化ABCDest.NextMetricAA0BB3C-32Dest.NextMetricBB0AA3CC2Dest.NextMetricCC0BB2A-路由更新(gngxn)ABCDest.NextMetricAA0BB3CB532Dest.NextMetricBB0AA3CC2Dest.NextMetrictCC0BB2AB5路由更新消息共六

10、十七页DV算法中的计数(j sh)到无穷问题ABC32Dest.NextMetricBB0AA3CC2Dest.NextMetricCC0BB2AB5Dest.NextMetricBB0AACC2Dest.NextMetricBB0AC7CC2Dest.NextMetricCC0BB2AB9无穷(wqing)计数！共六十七页DV算法不能直接(zhji)用于Ad Hoc网络计数到无穷问题部分解决方法选择(xunz)一个相对较小的数作为无穷大水平分割 (split horizon)：当一个节点把路由更新发送给相邻节点时，它并不把从各个相邻节点处学到的路由再回送给该节点无法发现路由循环限制了网络的可

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

12、Destination-Sequenced Distance Vector 共六十七页DSDV路由表序列号（Sequence number ）由目的(md)端产生，用来防止出现路由回路，并确保路由信息是最新的；格式： Dest_NNN加入时间（Install Time）路由表项的创建时间，用来删除过期表项Stable Data 指向一个包含有路由稳定状态信息的表目的节点地址/最近沉淀时间/平均沉淀时间 用于缓解网络中的路由波动Dest.MetricNextSeq. NrInstall TimeStable DataAA0A-550001000Ptr_ABB1B-102001200Ptr_BCB

13、3C-588001200Ptr-CDB4D-312001200Ptr_D对于同一个目的地节点可能(knng)接收到来自其它节点的多条路由信息，settling time为第一条路由和最佳路由之间的时间间隔共六十七页DSDV路由公告(gnggo)向每个邻居公告自己的路由信息目的节点地址Metric：到目的节点的开销，一般为到目的节点的跳数目的地序列号其它信息（例如硬件地址等）设置序列号信息的规则每次公告增加自己的目的地序列号（只使用偶数值(shz)）如果一个节点不再可达（timeout）,则将该节点的序列号加1（奇数序列号），并且设置metric为共六十七页DSDV路由选择(xunz)将更新信息

14、与自己的路由表比较选择具有更大目的地序列号的路由，这将保证始终使用(shyng)来自目的地的最新信息当序列号相等时，选择具有更好metric的路由共六十七页DSDV协议操作(cozu)：更新前路由表Dest.NextMetricSeqAA1A-550BB0B-100C C1C-588Dest.NextMetricSeqAA0A-550BB1B-100C B2C-588Dest.NextMetricSeq.AB2A-550BB1B-100C C0C-588ABC共六十七页DSDV协议操作(cozu)：路由公告B递增序列号 100 - 102B向邻居A、C广播路由信息(xnx)，其中包含有目的地序

15、列号Dest.NextMetricSeqAA0A-550BB1B-100C B2C-588Dest.NextMetricSeqAA1A-550BB0B-102C C1C-588Dest.NextMetricSeq.AB2A-550BB1B-100C C0C-588ABC共六十七页DSDV协议操作(cozu)：更新后路由表Dest.NextMetricSeqAA0A-550BB1B-102C B2C-588Dest.NextMetricSeqAA1A-550BB0B-102C C1C-588Dest.NextMetricSeq.AB2A-550BB1B-102C C0C-588ABC共六十七页对

16、拓扑变化(binhu)的反应立即公告原则有关新路由、链路断开和metric变化的信息立即传递给邻居节点(ji din)两种更新模式（完全更新/增量更新）完全更新：发送自己路由表中的所有路由信息增量更新：只发送路由表中那些发生变化的表项（能包含在一个单独的分组中发送）共六十七页DSDV协议操作：新节点(ji din)加入Dest.NextMetricSeq.AA0A-550BB1B-104C B2C-590Dest.NextMetricSeq.AA1A-550BB0B-104CC1C-590Dest.NextMetricSeq.AB2A-550BB1B-104CC0C-5901. D第一次广播(

17、gungb), 发送序列号D-000ABCD共六十七页DSDV协议(xiy)操作：新节点加入Dest.NextMetricSeq.AB2A-550BB1B-104CC0C-590DD1D-0002. 插入(ch r)到D的表项，序列号为D-000Dest.NextMetricSeq.AA0A-550BB1B-104C B2C-590Dest.NextMetricSeq.AA1A-550BB0B-104CC1C-590ABCD共六十七页DSDV协议(xiy)操作：新节点加入C, 0, C-592)Dest.NextMetricSeq.AB2A-550BB1B-104CC0C-592DD1D-00

18、03. C递增自己(zj)的序列号到C-592，然后立即广播自己的新路由表Dest.NextMetricSeq.AA0A-550BB1B-104C B2C-590Dest.NextMetricSeq.AA1A-550BB0B-104CC1C-590ABCD共六十七页DSDV协议操作(cozu)：新节点加入4. B获取(huq)新的路由信息并且更新路由表Dest.NextMetricSeq.AC3A-550BC2B-104CC1C-592DD0D-000D从C获取路由表信息并且生成自己的路由表ABCDDest.NextMetricSeq.AB2A-550BB1B-104CC0C-592DD1D-

19、000Dest.NextMetricSeq.AA0A-550BB1B-104C B2C-590Dest.NextMetricSeq.AA1A-550BB0B-104CC1C-592DC2D-000共六十七页DSDV协议操作(cozu)：链路断开Dest.NextMetricSeq.DC2D-100Dest.NextMetricSeq.DB3D-100Dest.NextMetricSeq.DD1D-100因为B广播(gungb)的到达D的路由信息中的序列号小于C维护的D的序列号，因此C认为B的广播的是过期路由信息，不予采纳1. C检测到链路断开-序列号递增1(当且仅当这种情况不是目的节点设置序列

20、号-奇数序列号)2. B广播到达D的路由信息ABCD避免了循环避免了计数到无穷DDD-101共六十七页DSDV协议操作(cozu)：立即公告4. B立即传送更新消息(xio xi)给A(更新信息具有更大的序列号，因此将取代A中原有表项)3. C立即传递更新信息给B (更新信息具有更大的序列号，因此将取代B中原有表项)ABCDDest.NextMetricSeq.DC2D-100Dest.NextMetricSeq.DB3D-100Dest.NextMetricSeq.DDD-101(D, , D-101)DBD-101DCD-101共六十七页DSDV协议操作(cozu)：路由波动2. A收到来

21、自(li z)P的路由更新消息10 Hops11 HopsAPQDDest.NextMetricSeq.DQ14D-100DP15D-1021. D公告序列号为D-102的路由更新路由表中到D的表项立即进行路由公告3. A收到来自Q的路由更新消息DQ14D-102更新路由表中到D的表项立即进行路由公告由于D或者任何一个节点的路由更新消息到达节点A时存在着时间差,就会导致不必要的路由公告路由表波动共六十七页DSDV协议(xiy)操作：减缓路由波动在一个单独的表中记录每条路由的最近的和平均的Settling TimeSettling Time：第一条路由和最佳路由之间的时间间隔路由表中的stabl

22、e data指向该表A在包含(bohn)新序列号的第一条路由到达时更新路由表，但是等待一段时间再广播该条路由等待时间=2*(avg. Setting Time)10 Hops11 HopsAPQD可缓解大型网络的路由波动问题，从而避免不必要的公告，节约了带宽共六十七页DSDV总结(zngji)优点简单（基本上与DV算法一致(yzh)）通过目的地序列号避免了路由循环，解决了DV算法中的计数到无穷问题无路由发现延时（先验式路由）缺点所有节点都必须公告路由，因此不支持休眠（不能直接用于传感器网络）收敛慢（DV路由的特性）开销大：大部分的路由信息从不使用可扩展性是一个主要问题（所有先验式路由都存在的问

23、题）共六十七页优化链路状态(zhungti)路由协议(OLSR)Optimized Link State Routing Protocol先验式的链路状态路由协议基于多点中继（MPR）的概念的优化只有MPR转发(zhun f)广播消息，减少了消息开销只有MPR产生链路状态信息，减少了网络中广播消息的数量MPR可能选择只报告它和该MPR选举节点之间的链路，因此在网络中只散发部分链路状态信息RFC3626共六十七页基于(jy)拓扑广播的反向路径转发TBRPFTopology Broadcast based on Reverse-Path Forwarding本质上是一种链路状态协议协议组成邻居发现

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

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

26、EF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)共六十七页DSR路由发现：中间(zhngjin)节点处理中间节点维护(wih)序列对列表重复RREQ检测如果接收到的RREQ消息中的存在于本节点的序列对列表中如果接收到的RREQ消息中的路由纪录中包含本节点的地址如果检测到重复，则中间节点丢弃该RREQ消息ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)丢弃F转发的RREQ共六十七页DSR路由发现(fxin)：路由应答目的节点收到RREQ后，给源节点返回路由应答(yngd)（RREP：Route R

27、eply）消息拷贝RREQ消息中的路由纪录源节点收到RREP后在本地路由缓存中缓存路由信息(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C-D)共六十七页DSR路由发现(fxin)：非对称信道对称信道目的节点(ji din)到源节点(ji din)的路由即为源节点(ji din)到目的节点(ji din)的反向路由非对称信道如果目的节点的路由缓存中有到达源节点的路由，则直接使用否则目的节点需要发起到源节点的路由请求过程，同时将RREP消息稍带在新的RREQ消息中共六十七页DSR路由维护(wih)逐跳证实机制链路层确认被动(bidng)确认（监听其它节点间的数据发送）其它高层要求DS

28、R软件返回确认端到端证实机制无法确定故障发生的位置共六十七页DSR逐跳证实(zhngsh)机制如果数据分组被重发了最大次数仍然没有收到下一跳的确认，则节点向源端发送路由错误（Route Error）消息，并且指明中断的链路源端将该路由从路由缓存中删除如果源端路由缓存中存在另一条到目的节点的路由则使用该路由重发分组否则(fuz)重新开始路由发现过程ABCDEF(A-B-C-E-)Route Error共六十七页DSR优化：路由缓存(1) 每个节点缓存它通过任何方式获得的新路由转发RREQ获得从本节点到RREQ路由记录中所有(suyu)节点的路由，例如E转发RREQ(A-B-C)获得到到A的路由(

29、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)ABCDEF(A-B-C-D)(A-B-C-D)ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)以上(yshng)均假设信道是对称的!共六十七页DSR优化：路由缓存(2)中间节点使用缓存的到目的节点的路由响应(xingyn

30、g)RREQRREP中的路由纪录=RREQ中的路由纪录+缓存的到目的节点的路由ABCDEF(B-C-D)(A-B-C-D)(A-)共六十七页DSR优化：路由缓存(3)错误路由缓存网络拓扑的变化使得(sh de)缓存的路由失效影响和感染其它节点，使用该路由缓存的路由将不可用当节点根据路由缓存回应RREP时，其它监听到此RREP的节点会更改自己缓存的路由，从而感染错误路由缓存设置缓存路由的有效期，过期(guq)即删除共六十七页DSR优化：路由缓存(4)RREP风暴节点广播到某个目的节点的RREQ，当其邻居节点的路由缓存中都有到该目的节点的路由时，每个邻居节点都试图以自己缓存的路由响应，由此造成(z

31、o chn)RREP风暴RREP风暴将浪费网络带宽，并且加剧消息冲突ABCDEF(B-A)G(C-B-A)(F-A)(E-C-B-A)G发起到A的路由发现(fxin)过程共六十七页DSR优化：路由缓存(5)预防RREP风暴每个节点延时D发送RREPD与节点到目的节点的跳数成正比，使得到目的节点有最短路径的RREP最先发送节点将接口设置成混杂模式(promiscuous)，监听是否(sh fu)存在有比自己更短的到目的节点的路径，如果有，则不发送本节点的RREPD=H*（h-1+r）其中(qzhng)H是每条链路的传播延时h是自己返回的路径长度，即到目的节点的跳数r是0或者1共六十七页DSR总结

32、(zngji)优点仅在需要通信的节点间维护路由，减少了路由维护开销路由缓存技术能够进一步减少路由发现的代价通过采用路由缓存技术，能够发现多条到达目的节点的路由支持非对称信道缺点采用源节点路由，每个数据分组头标中都要携带路由信息，增加了网络开销由于采用广播，用于路由发现的控制消息可能波及到全网节点，需要这些消息的传输距离（跳数）RREP风暴问题(wnt)错误路由缓存问题共六十七页AODV协议(xiy)Ad Hoc On Demand Distance Vector RoutingAODV结合了DSR和DSDV使用DSR中基于广播的路由发现机制每个节点都维护路由表，采用DSDV逐跳(Hop-by-

33、Hop)路由、序列号数据分组不再携带完整的路由信息仅维护活跃的路由AODV特点与DSDV协议相比,采用按需路由,不需要维护整个网络的拓扑(tu p)信息,只有在发送分组且没有到目的节点的路由时才发起路由发现过程与DSR协议相比,由于节点建立和维护路由表,分组中不需携带完整的路由信息仅适用于对称信道路由表仅维护一条到目的节点的路由RFC3561共六十七页混合(hnh)路由协议共六十七页区域(qy)路由协议(ZRP)Zone Routing Protocol区域(zone)的划分整个网络被划分为若干个以节点(ji din)为中心,一定跳数为半径的区域区域内节点数与设定的区域半径有关路由策略每个节点

34、在区域内部采用表驱动路由对于区域外节点采用按需路由共六十七页ZRP路由架构(ji u)区域内路由协议IARP ( IntrAzone Routing Protocol)采用表驱动路由协议，节点之间周期性地交换路由信息获得到域内各个节点的最新路由距离向量路由协议DSDV等链路状态路由协议OLSR等完成区域内部节点间的路由功能区域间路由协议IERP (IntErzone Routing Protocol)采用按需路由协议完成与区域外节点间的路由功能边界传播(chunb)协议BRP (Bordercast Resolution Protocol)BRP协议使得路由查询分组只在边界节点之间广播共六十七页ZRP路由架构(ji u)区域内路由协议(xiy) IARP: IntrAzone Routing Protocol区域间路由协议 IERP: IntErzone Routing Protocol边界传播协议 BRP: Bordercast Resolution Protocol共六十七页ZRP路由过程(guchng)Z(A)=A, B, C, D, E, FA发现节点I不在自己的区域(qy)内，向边界节点E、F、D广播路由请求消息边界节点E收到路由请求消息后，发现节点I在自己的区域内，直接回复路由应答消息