移动计算技术-Ad_Hoc网络路由-2014.ppt

DSR路由发现：路由请求 源节点向邻居节点广播路由请求（RREQ：Route Request）消息 源节点地址 目的节点地址 路由记录：记录从源节点到目的节点路由中的中间节点 请求ID 中间节点接收到RREQ后，将自己的地址附在路由记录中 A B C D E F (A-) (A-F) (A-) (A-B-) (A-B-C-) (A-B-C-) (A-B-C-E-) DSR路由发现：中间节点处理 中间节点维护源节点地址、请求ID序列对列表 重复RREQ检测 如果接收到的RREQ消息中的源节点地址、请求ID存在于本节点的序列对列表中 如果接收到的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后，给源节点返回路由应答（RREP：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软件返回确认 端到端证实机制 无法确定故障发生的位置 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路由记录中所有节点的路由，例如B转发RREP(A-B-C-D)获得到D的路由(C-D) 转发数据分组 获得从本节点到数据分组节点列表中所有节点的路由，例如E转发数据分组(A-B-C)获得到A的路由(C-B-A) 监听相邻节点发送的分组 RREQ、RREP、数据分组等 (A-B-C-D) A B C D E F (A-B-C-D) (A-B-C-D) 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) (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发起到A的路由发现过程 DSR优化：路由缓存(5) 预防RREP风暴 每个节点延时D发送RREP D与节点到目的节点的跳数成正比，使得到目的节点有最短路径的RREP最先发送 节点将接口设置成混杂模式(promiscuous)，监听是否存在有比自己更短的到目的节点的路径，如果有，则不发送本节点的RREP D=H*（h-1+r） 其中H是每条链路的传播延时 h是自己返回的路径长度，即到目的节点的跳数 r是0或者1 DSR总结 优点 仅在需要通信的节点间维护路由，减少了路由维护开销 路由缓存技术能够进一步减少路由发现的代价 通过采用路由缓存技术，能够发现多条到达目的节点的路由 支持非对称信道 缺点 采用源节点路由，每个数据分组头标中都要携