ad hoc路由协议.doc

移动ad hoc网络的路由协议移动自组网的路由协议为什么不同？1. 主机的移动性由于移动性造成链路的失败和修复与平常网络不同。2. 当节点移动速度快的时候，链路失效率可能很高3. 可能使用新的标准移动时路由不变，能量消耗单播路由协议1. 洪泛数据传输FDD (7-18)发送者向所有邻居广播数据包P，每个节点收到P时向其邻居传播，用序列号防止是一个数据包被传播多次，当包到达目的地址的时候说明目标地址可达，目标节点不再传播数据包，所以目标节点之后的节点收不到。这种方法可能造成很多包转发。优势：简单；当信息传输率很低的时候可能更有效；可靠性高，数据能通过多个路径到达。缺点：开销太大，数据传递给很多不需要接收的节点；可靠性低，使用广播容易引发冲突造成丢包。管理包洪泛很多协议使用控制包洪泛，控制包用于发现路由，被发现的路由随后用户数据传输，控制包的开销被数据包传输分摊。2. 动态源路由 DSR (19-41)当S想与D通信，但是不知道路由信息，则S启动路由发现。S洪泛路由请求RREQ，每个节点在转发RREQ时追加自己的标识。D在收到第一个RREQ之后，从来的路径发送路由回应RREP，RREP中有从S到D的路由。S收到RREP存下路由信息，当S向D发送数据的时候在包头中包含完整的路由信息。中间节点使用源路由决定向那个节点转发数据。当S发现到D的路径出现问题时，如果路由缓存中有相关信息则使用缓存的信息，否则发送路由发现。中间节点知道到目标的路由信息时可以发送路由回应。路由回应RREP只有已知链路是双向的，才可以翻转来时的路径发送路由回应。如果链路是单向的，则路由回应也需要启动路由发现来寻找S。IEEE802.11 的mac层是双向的。路由错误：RERR中间节点发现路由不同时，返回路由错误。节点收到路由错误的时候清除路由缓存里的相关信息。优化：路由缓存源节点通过到目的节点的路由信息，也获得了到中间节点的信息。当中间节点收到路由发现时，获得到源节点的路由信息。中间节点收到路由回复的时候，获得到目标节点的路由信息。中间结点转发数据包的时候，获得到目标节点的路由信息。节点监听到数据包也可以学习路由。使用路由缓存可以加速路由发现，减少路由请求的传播。路由缓存的注意事项陈旧的信息对性能不利；由于节点的移动性，信息可能失效；DSR的优势：路由只维护需要通信节点的信息路由缓存减少路由发现的开销由于节点可能从缓存读取信息发送回应，一个路由发现可能产生多个到达目的节点的路由。DSR的缺点：使包头长度增加洪泛使得所有节点都可能收到路由请求临节点需要注意防止冲突(随机退避)当节点使用缓存返回信息的时候增加了网络的竞争，可能造成广播风暴(当节点听到有更短的路由回应时，不发送回应，这样可以缓解风暴)使用陈旧的路由信息发送时污染其他缓存（当有路由净化机制的时候缓解）3. 控制洪泛 （42页）1. 怎么减少路由请求洪泛的范围LARQuery localization2. 怎么减少冗余的广播广播风暴的问题4. 位置辅助路由协议（LAR） （43-51）利用位置信息限制路由查询报文洪泛的范围,所以路由开销相对较小。（1）两个概念：l 期望域：是一个表示目的节点的当前位置的区域范围，由目的节点原来的位置与其移动速度共同决定。eg：源节点知道目的节点D在t0时刻的位置X，及其移动速度v，t1时刻D的期望域就是以X为圆心，以r=（t1-t0）*v 为半径的圆形区域。l 寻找域：由转发节点和目的节点的期望域共同确定的最小矩形区域（2）特点：l 只有在寻找域中的节点才转发路由请求报文。l 路由请求报文中携带寻找域信息。l 每个节点必须知道其路由位置，据此判断它是否在寻找域中。l 如果使用小的寻找域,路由查询可能失败,若使用大的寻找域，极端的情况是,寻找域被扩大到整个网络空间,这时LAR也就等同于一般的洪泛路由协议l 其余的路由发现信息与DSR相似。（3）优点：l 减少路由查询报文的洪泛的范围l 减少路由查询报文的开销（4）缺点：l 节点需要知道它们的物理位置信息l 没有考虑无线电传播过程中可能存在的阻碍5. 地理距离路由协议（GEDIR） （52-55）假设目的节点的位置是已知的，每个节点知道其邻居节点的位置，每个节点转发一个包到距离目的节点最近的邻居节点。如果连续两次走过相同的边，算法结束。路由与确保交付是在GEDIR基础上做的改进，确保源节点与目的节点之间存在一条路径，传输过程中尽量绕过障碍物。6. 请求定位路由协议（Query Localization） （57-60）可减少路由请求洪泛的范围，不使用物理信息来限制路由请求泛滥。路由请求值沿着与之前路线接近的路线传播。位置路径启发式：寻找一个新的路径，最多包括k个没有出现在之前的路径中。路由请求被转发仅仅在累积的路由中路由请求包含最多k个原来路径中没有的新节点。限制路由请求的转发优点：降低利用物理位置信息发现路由的开销。 可以通过寻找老路径附近的新路径，在存在障碍物时执行的更好。缺点：可能产生的路线长度超过LAR（最短的路径可能包含多于k个的新节点）7. 广播风暴问题 （61-66）冗余：一个给定的节点可能从很多节点收到同样的多份路由请求信息，当一份已经足够了。广播风暴的解决方法：l 概率方案：当第一次接收到一个路由请求时，节点将以概率p再次广播该请求。另外，被不同的节点再次广播的时候应该交错使用冲突避免机制（当信道空闲时等待一个随机的延迟）将会解决两个节点同时转发接收到的相同的包的问题。l 计数器基础方案：如果一个节点E听到超过k个邻居广播一个给定的路由请求，在它自己转发之前，那么该节点将不会转发该请求。直觉：k个邻居很有可能已经转发该请求给所有E的邻居。l 基于距离的方案：如果一个节点E从某一个节点Z听到RREQ广播，并且在物理距离d内，那么E将不会在广播该请求。直觉：Z和E太近，所以被Z或E覆盖的转播区域没什么特别的不同。总结：广播风暴问题洪泛应用在很多协议中，例如DSR与洪泛有关的问题：冲突；冗余。冲突解决可以通过在转播洪泛之前等待一个随机的间隔。冗余可以通过有选择的广播包从节点的一个子集8. Ad hoc请求式距离矢量路由 AODV (67-125)DSR在头部包含路径信息，导致头部太大性能下降。AODV尝试在节点中维持路由表来改进DSR，这样数据包不用包含路径信息。AODV保持DSR的特点，只维护需要通信的节点的路由。AODVAODV的路由请求传递和DSR相似。当一个节点重新广播路由请求，它会翻转路径指向源节点。目标节点收到请求是回复路由回应，路由回应从刚才翻转的路径发给源节点。路由信息不包含在包头中，而是在路由表项中给出。AODV的路由回应中间结点可能发送路由回应，包含它知道的比源节点新的路由信息。目标序列号用来标识那个路由信息更新。AODV中由中间节点发送的路由回应比DSR少。超时在超时后，路由表象维护的翻转的路径被清除。路由表项中的转发路径也在超时后清除。在超时之前用过的临节点被认为是活跃的当路由表中的一项无效了，要通知所有的临节点链路失败用于传递失效信息，链路失效报告也消耗目标序列号。路由错误当中间节点不能转发包的时候，形成路由错误信息。中间节点在自己的缓存中增加不能到达的节点的目标序列号，这个序列号N也包含在错误报告中。源节点收到路由错误报告时，发起新的路由发现，路由发现使用序列号N标识。目标序列号当D收到路由请求中的序列号为N，D会把自己的序列号设置给请求，除非D的序列号比N大。临节点定期交换hello信息，缺少hello信息意味着链路失败。收到一些mac层的回单也意味着链路失败。AODV中为什么使用序列号？防止使用陈旧的路由信息。防止形成环优化：扩展环搜索路由请求TTL比较小，这样限制它传播。假如没有回应，则增大TTL在尝试。总结路由信息不用包含在头中。节点保存活跃的路由信息。在每个节点对于一个目标节点，只保存最多一跳的信息。即使拓扑没有改变，没有使用的路由也被清除链路翻转算法对每一个目标节点维护一个有向图不用于目标节点的任何一个没有出边的节点，将他的入边翻转(一个边可以多次翻转，每次翻转没有出边的节点)。重复，直到除了目标节点，所有的节点都有出边。这样最终只有一个节点成为终点。当发生链路失效时，尝试本地保持链路翻转。当第一个包送达的时候，有向图建立完成。最初的有向图是有控制包洪泛建立的。部分翻转节点只翻转和没有发生过翻转的邻居相连的入边，如果所有节点都翻转过了，则节点翻转自己所有的入边。链路翻转的优点尝试在链路破坏时限制更新路由表每个节点可能有通向目标节点的多条链路链路翻转的缺点需要发现链路失效的机制(hello机制可以，但是hello机制增加冲突)当网络被划分的时候(分成不相连的几部分)，翻转会一直进行下去，不能停止，直到网络又合并了。短暂有序路由算法TORA该算法修改部分翻转算法，可以察觉网络的划分。当发现划分的时候，通知所有节点，链路翻转停止。当一个节点收到最初时候它发出翻转命令的节点发出的翻转命令时，发现划分。TORA算法只维持到目标节点的有向图。9. 链路状态路由协议（LSR） （127-128）每个节点周期性的洪水其链路状态信息。每个节点广播接收到的其它节点的链路状态信息每个节点跟踪从其它节点接收到的链路状态信息每个节点利用以上信息去决定到每个目的节点的下一跳10. 最佳链路状态信息（OLSR）是在LSR上的基础优化 （129-134）洪水的链路状态信息的开销通过需要更少的节点去传播信息来减少。一个来自节点X的广播仅仅被它的多点中继站传播。OLSR通过多点中继转播站洪泛信息OLSR使用的所有路由仅使用多点中继站作为中间节点OLSR中的关键概念是多点转播（MPRs），MPRs是在广播洪泛的过程中挑选的转发广播的节点。传统的链路状态协议每个节点都转发它收到信息的第一份拷贝，同它相比，OLSR很大程度上减少了转发的信息。在OLSR协议中，链路状态信息都是由被挑选为MPRs的节点产生的，这样减少了在网络中洪泛的控制信息OLSR的优点减少了由于链路状态信息洪泛带来的路由开销。l 多点中继站(MPR )的利用, 每个节点在自己的一跳邻居节点中选择一部分节点作为自己的MPR,由MPR 而不是所有的一跳邻居节点转发链路状态消息, 通过MPR 实现路由控制消息的选择性洪泛。l 链路状态信息的压缩, 链路状态信息只是描述与MPR 之间的链路, 而不是与所有的一跳邻居节点的链路。11. 目标序列距离路由矢量算法（DSDV）主动协议 （134-136）（1） 每个节点维护一个路由表存储：l 到目的节点的下一条l 到每个目的节点的成本度量值（如最小跳数）l 由目的节点自己创建的目的节点相关的序列号l 序列号是用来避免出现路由环路（2） 每个节点周期性的向其邻居节点通告其路由表12. 区域路由协议（ZRP） 混合协议 （138-143）区域路由协议结合：l 主动协议：预先主动更新网路状态和维护路线无论任何数据流量存在与否。l 被动协议：只有在有一些数据需要被发送到目的节点的时候才决定路线。ZRP：内部区域路由：主动维护来自任何一个给定节点的短距离链路状态信息、区域间路由：使用一个理由发现协议去决定到很远的节点的路线。路由发现与DSR类似路由请求通过外围节点传播。13. 里程碑路由协议（Landmark Routing）(144-148)一个节点被选为一个很有可能节点会一块移动的组的里程碑节点。定义一个范围，每个节点在里程碑节点的范围内。每个节点只对其范围内的节点传播链路状态信息；对所有的里程碑节点传递距离矢量信息。14. 能量感知路由 (149-154)协议讨论寻找或者维护路由信息，一些协议通过能源控制确保路由存在。协议讨论在一个给定的网络拓扑中寻找路由。一些研究通过发送能源控制来控制网络的拓扑。能量感知路由:定义以能量消耗为依据的优化标准。比如每个包的最小消耗能量，由于能量消耗的网络分区最小时间等。给每条链路一个权值，可能根据在链路上发送一个包的最小能量决定。优先寻找总能量消耗最小的路径。可以修改DSR使它具有能量感知：路由请求整合经过的链路的权值。对于第一个到达的或者是权值最小的路由请求，目标节点发送路由回应。15. 抢占路由协议（Preemptive Routing） （155-157）在被动协议中加入一些主动性，如DSR、AODV 启动路由发现在现有路由中断之前，可以减少发现延迟。16. 地址自动配置 (157-192)自动配置对于adhoc网络很重要。Adhoc网络中重复地址的探测，当收到路由回应的时候重复的地址被发觉。强重地址发现：在t秒之内发现由于不知道网络的规模，不能保证强重地址发现。弱重地址发现：所有同一个节点发送给另一个节点的包，即使有重复的地址，也要到同一节点(即使是个错误的节点，也要收到所有的包)。实现：用路由维护整合重复地址链路状态路由中的弱重地址发现：每个节点有唯一的标识，在包中地址附加自己标识在重地址被发现之前，路由表可能存在错误。总结：强DAD一般实现不了；弱DAD可行，联合路由维护信息实现；弱DAD的开销应该低。Adhoc网络的能力固定能力P187移动能力：P188DSR 和AODV的对比DSR 和AODV 两种协议的路由寻找都是查询和应答往返过程进行的。按照一定的格式将路由信息存储在路由的所有中间节点上。但是两者在动态性上面有差别。第一DSR协议使用源路由访问的路由协议明显多于AODV协议。DSR协议中国，源节点使用一次路由请求与路由应答过程，除了可以得到目的节点的路由之外，还可以得到到达路由上每个中间节点的路由。第二，DSR协议对于在单独一个路由请求于路由应答过程中到达目的节点的所有路由请求RREQ分组做应答。因此源节点知道到达目的节点的很多路由。在AODV协议中，目的节点只对第一个到达的路由请求分组RREQ做出应当，而忽略和丢掉随后到达的RREQ第三，DSR协议的当前版本里面没有任何机制来删除路由存储器中期满过时而失效的路由。也没有任何机制来确定在面俺对多跳路由选择时有限选择哪条。AODV是比DSR协议保