多径路由算法简介

多径路由算法简介

——2017.6.20内容1、背景2、多径路由算法概述3、多径路由算法原理4、总结1、背景无线网络：无线多跳网络传感器网络AdHoc自组织网络无线Mesh网络ZigBee1、背景特征：1）无中心和自组织性2）动态变化的网络拓扑3）多跳路由4）受限的无线传输带宽5）节点能源有限6）安全性较差7）移动终端的局限性1、背景分类先应式路由：DSDV（目的序号距离矢量算法）、WRP（无线路由协议）反映式路由：AODV（按需距离矢量路由算法）、DSR（动态源路由算法）混合式路由：ZRP（区域路由算法）2、多径路由算法概述単径路由算法：优点：简单缺点：负载不均，性能较低（没有考虑到路径的公平性，过多的依赖最短路径或者最优路径；无法很好的获取网络的拓扑信息，导致无法有效的利用网络的整体信息，进而增加了路由开销；数据发送一般只利用一条路径，无法实现并行或并发的发送数据）2、多径路由算法概述多径路由策略是指通过一定的约束规则，在网络中找出到达目的节点的多条路径，要求更多的节点来承担数据包的转发任务，然后在这多条路径间合理的分配负载。优点：可以较好的利用网络拓扑信息；可以为不同的服务质量要求提供不同的路径；可以为同一类型的服务提供多条路径，利用多条路径来并行\并发发送数据，实现更高的服务质量；提供网络的利用效率；实现负载均衡，延长网络生命周期挑战：延时、丢包、开销、吞吐量。。。多径下链路关系：链路不相关、节点不相关、相关多路径。路径间的独立性越高，所有路径同时失效的可能性越低；不同路径共享链路或者节点会导致路径集内部争用信道。节点不相关的要求会导致路径数量的减小，路径之间的相关性定量指标为“相关度（多条路径间的共同的链路数）”和“交合度（因为其它路径正在传输而导致的阻塞的平均节点数）”。2、多径路由算法概述3、多径路由原理1）路由发现2）路由维护3）路由选择3、AODV——>AOMDV路由帧格式主要包括:RREQ–

路由请求帧RREP–

路由应答帧RERR–

路由错误帧HELLO–

活跃路由链路监测帧RREQ路请求由帧在两个节点之间的路由有效、通信正常的情况下，路由协议不起任何作用只有当源节点S需要向目的节点D发送数据包，但又没有D节点的路由入口时才会发起路由请求，即发送路由广播帧RREQRREQ请求帧的传播B?B?B?B?B?B?B?BARREP应答帧当RREQ最终到达目的节点时，目的节点通过向该反向路由（即该RREQ传播路线）发送RREP应答帧，从而在该条路径的各个节点建立通向目的节点的前向路由只有在以下情况下节点才会产生RREP:该节点本身就是目的节点该节点为中间节点，但是它有通向目的节点的活跃路径当RREP传播到源节点时，中间节点根据该RREP更新它们各自指向目的节点的路由信息RREP路由应答帧的传播BAAAAAAA1）路由发现（AODV）当源节点需发送数据包到目的，且源没有到达目的的路径时，才发起路由发现过程。1）路由发现（AOMDV）2）路由维护Hello消息Hello消息帧用于监测活跃路径上相邻节点的链接状况。例如：当活跃路径上某节点多长时间内没有收到该路径上的邻居节点发送来的Hello消息帧或其他任何帧时，该节点就认为与它与邻居节点的链路已断只有当某节点位于某活跃路径之上时，它才能发送Hello消息帧中间节点发起一次指向该邻居节点的局部修复RERR传播过程中，各中间节点删除该失效路径上相应的路由信息RERR路由错误帧以下情况发生时，则广播RERR路由错误帧：一个节点检测到与一个邻居节点的链路断裂（即该邻居节点不可达）节点收到一个数据包，而该节点路由表中没有指向数据包制定的目的地址的有效路由，并且该路由并非处于修复状态节点收到来自邻居节点的RERR路由错误信息帧，该帧可能指示多个目的节点不可达2)路由维护若某一路径上节点故障或链路故障，可能会引起路径不可用。这种情况下，节点会定期广播HELLO包给邻居节点以监测链路状况程。RERR信息的发送方式单播将RERR信息单播发送给一个接收者重复单播将RERR信息分别的单播发送给多个接收者广播将RERR信息同时发送给多个接收者使用IP地址255.255.255.255进行广播2)路由维护多径路由与单径路由维护过程区别在于：

单径路由协议在唯一的路径不可用之后发起维护过程，而多径路由协议在多条路径都不可用之后，或者经裁定某些路径不可以用之后才发起路由维护过程。这将大大减少路由发现的次数，有利于降低路由发现的成本，而且路由发现过程中全网范围内的RREQ包泛洪会引起网络拥塞，泛洪次数的减少也有利于网络性能的提高。3）、路由选择路径数量和质量对路径的质量进行估计，选择质量较优的路径，可以使用跳数、时延、负载、路径独立性等作为估计路径质量的判据。3）路由选择流量分配策略：1）贪婪策略：当一个数据包到达且等待转发时，节点计算并比较每一条路径的评价值，从中选择最优的一条路径转发改数据包。2）轮转策略：当一个数据包到达且等待转发时，节点计算并比较每条路径的转发计数器，从中选择转发数据包较少的路径转发改数据包。3）随机概率策略：当一