搜索
多径路由算法（协议）简介——2017.6.20内容1、背景2、多径路由算法概述3、多径路由算法原理4、展望1、背景无线多跳网络（转发节点）传感器网络(传感器节点)AdHoc自组织网络（）无线Mesh网络ZigBee这种网络没有固定的路由器，网络中的节点可随意移动并能以任意方式相互通信。每一个节点都能实现路由器的功能而在网络中搜寻、维护到另一节点的路由Adhoc网络节点能够适应网络的动态变化，快速检测其它节点的存在和探测其他节点的能力集，网络节点通过分布式算法来协调彼此的行为，无需人工干预和任何其它预置的网络设施，可以在任何时刻任何地方快速展开并自动组网。由于网络的分布式特征、节点的冗余性和不存在单点故障点，任何结点的故障不会影响整个网络的运行，具有很强的抗毁性和健壮性。在无线多跳网络中，源结点到目的结点之间的典型路径是由多跳组成的，该路径上的中间结点充当转发结点。因此，无线多跳网络中一个结点具有两种功能，首先结点可以充当端结点产生或接受数据分组，其次结点可以充当路由器对来自其它结点的数据分组进行转发。在现有的无线网络中，无线AdHoc网络，无线传感器网络以及无线Mesh网络均属于无线多跳网。多跳网络是由节点构造的，包括诸如电脑和移动电话这些设备，这些设备全都用无线连接到彼此，然后互相可以通过网络转发数据。数据从一个节点跳到另一个节点，直到抵达目的地。除非所有的节点都发生故障，否则数据总是可用的，如此使得这种网络拓扑结构可靠且可扩展。.无线网状网(WMN)技术是面向基于IP接入的新型无线移动通信技术适合于区域环境覆盖和宽带高速无线接入。无线Mesh网络基于呈网状分布的众多无线接入点间的相互合作和协同，具有宽带高速和高频谱效率的优势，具有动态自组织、自配置、自维护等突出特点ZigBee是基于IEEE802.15.4标准的低功耗局域网协议。根据国际标准规定，ZigBee技术是一种短距离、低功耗的无线通信技术。1、背景特征：1）无中心和自组织性2）动态变化的网络拓扑3）多跳路由4）受限的无线传输带宽5）节点能源有限6）安全性较差7）移动终端的局限性1、背景分类先应式路由：DSDV（目的序号距离矢量算法）、WRP（无线路由协议）反映式路由：AODV（按需距离矢量路由算法）、DSR（动态源路由算法）混合式路由：ZRP（区域路由算法）2、多径路由算法概述単径路由算法：优点：简单缺点：负载不均，性能较低（没有考虑到路径的公平性，过多的依赖最短路径或者最优路径；无法很好的获取网络的拓扑信息，导致无法有效的利用网络的整体信息，进而增加了路由开销；数据发送一般只利用一条路径，无法实现并行或并发的发送数据）2、多径路由算法概述多径路由策略是指通过一定的约束规则，在网络中找出到达目的节点的多条路径，要求更多的节点来承担数据包的转发任务，然后在这多条路径间合理的分配负载。优点：可以较好的利用网络拓扑信息；可以为不同的服务质量要求提供不同的路径；可以为同一类型的服务提供多条路径，利用多条路径来并行\并发发送数据，实现更高的服务质量；提供网络的利用效率；实现负载均衡，延长网络生命周期缺点：算法复杂度高多径下链路关系：链路不相关、节点不相关、相关多路径。特征：路径间的独立性越高，所有路径同时失效的可能性越低；不同路径共享链路或者节点会导致路径集内部争用信道。节点不相关的要求会导致路径数量的减小，路径之间的相关性定量指标为“相关度（多条路径间的共同的链路数）”和“交合度（因为其它路径正在传输而导致的阻塞的平均节点数）”。2、多径路由算法概述多径路由原理（AOMDV）1）路由发现2）路由维护3）路由选择路由帧格式主要包括:RREQ–路由请求帧RREP–路由应答帧RERR–路由错误帧HELLO–活跃路由链路监测帧RREQ路请求由帧在两个节点之间的路由有效、通信正常的情况下，路由协议不起任何作用只有当源节点S需要向目的节点D发送数据包，但又没有D节点的路由入口时才会发起路由请求，即发送路由广播帧RREQ当RREQ在网络中传播时，中间节点会更新各自到源节点的路由，我们称此路由为反向路由RREQ请求帧的传播B?B?B?B?B?B?B?BARREP应答帧当RREQ最终到达目的节点时，目的节点通过向该反向路由（即该RREQ传播路线）发送RREP应答帧，从而在该条路径的各个节点建立通向目的节点的前向路由只有在以下情况下节点才会产生RREP:该节点本身就是目的节点该节点为中间节点，但是它有通向目的节点的活跃路径当RREP传播到源节点时，中间节点根据该RREP更新它们各自指向目的节点的路由信息RREP路由应答帧的传播BAAAAAAA1）路由发现（AODV）当源节点需发送数据包到目的，且源没有到达目的的路径时，才发起路由发现过程。1）路由发现（AOMDV）路由维护Hello消息Hello消息帧用于监测活跃路径上相邻节点的链接状况。例如：当活跃路径上某节点多长时间内没有收到该路径上的邻居节点发送来的Hello消息帧或其他任何帧时，该节点就认为与它与邻居节点的链路已断只有当某节点位于某活跃路径之上时，它才能发送Hello消息帧活跃路径节点以HELLO_INTERVAL为周期发送Hello消息在DELETE_PERIOD的时间内没有收到来自邻居节点的Hello消息，则认为该链路已失效发起一次指向该邻居节点的局部修复路由修复超时以后，路由错误信息RERR向源节点和目的节点发送RERR传播过程中，各中间节点删除该失效路径上相应的路由信息RERR路由错误帧以下情况发生时，则广播RERR路由错误帧：i.一个节点检测到与一个邻居节点的链路断裂（即该邻居节点不可达）ii.节点收到一个数据包，而该节点路由表中没有指向数据包制定的目的地址的有效路由，并且该路由并非处于修复状态iii.节点收到来自邻居节点的RERR路由错误信息帧，该帧可能指示多个目的节点不可达2)路由维护2)路由维护若某一路径上节点故障或链路故障，可能会引起路径不可用。这种情况下，节点会定期广播HELLO包给邻居节点以监测链路状况，一旦发现故障立即生成RERR包（RouteError），发起路由维护过程。然后，中间节点将RERR包传送给经过此故障链路的所有源节点，源节点在接收到RERR包之后，视自身需要决定是否重新发起到目的节点的路由发现过程。多径路由与单径路由维护过程区别在于：单径路由协议在唯一的路径不可用之后发起维护过程，而多径路由协议在多条路径都不可用之后，或者经裁定某些路径不可以用之后才发起路由维护过程。这将大大减少路由发现的次数，有利于降低路由发现的成本，而且路由发现过程中全网范围内的RREQ包泛洪会引起网络拥塞，泛洪次数的减少也有利于网络性能的提高。重新建立路由源节点在收到RERR路由错误信息后，如果还需要与目的节点通信，它可以再次发起路由请求。再次建立起的路由可能跟原来路由大不相同中间节点在收到发送到目的节点的数据包时，如果发现目的节点的路由入口已失效（如路由计时超时），则该节点可以选择缓存该数据包，然后发起到该目的节点的路由请求RREQ。等重新建立到达目的节点的路由后，在转发此数据包到目的节点。路径数量和质量对路径的质量进行估计，选择质量较优的路径，可以使用跳数、时延、负载、路径独立性等作为估计路径质量的判据。3）路由选择流量分配策略：1）贪婪策略：当一个数据包到达且等待转发时，节点计算并比较每一条路径的评价值，从中选择最优的一条路径转发改数据包。该策略一定程度上可以满足负载均衡，但是无法解决分组乱序的问题，同时造可能造成某条路径的过度使用，使得负载均衡这一点也很难得到保障。2）轮转策略：当一个数据包到达且等待转发时，节点计算并比较每条路径的转发计数器，从中选择转发数据包较少的路径转发改数据包。该方法可以达到最优的负载均衡，但是无法解决分组乱序的问题。3）随机概率策略：当一个数据包到达且等待转发时，节点通过概率计算来选择一条路径转发该数据包。该策略一定程度上可以满足负载均衡，也无法避免分组乱序的问题，同时也增加了概率计算开销谢谢