无线传感器网络的路由算法

1、AODV议定书1.概观由诺基亚研究中心开发的自组织网络路由协议RFc标准是DSR和DSDV的综合。它借鉴了DSR路由发现和维护的基本程序，以及DSDV逐跳路由、目的节点序列号和路由维护阶段的定期更新机制。它以DSDV为基础，结合了DSR的按需路由思想，并对其进行了改进。它应用于无线自组织网络中的路由协议，可以实现单播和组播路由。该协议是自组织网络中按需生成路由模式的典型协议。用于特定网络中的移动节点。它可以在动态变化的点对点网络中确定到达目的地的路由，具有访问速度快、计算量小、占用内存少、网络负载轻的特点。它使用目的地序列号来确保在任何时候都不会出现环路，从而避免了传统距离矢量协议中的许多问题

2、。AODV最初提出建立一个纯按需路由系统。网络中的节点根本不依赖于活动路径，既不维护任何路由信息，也不参与任何常规的路由表交换。节点不需要发现和维护到其他节点的路由，除非两个节点需要通信或者节点提供特定服务作为中间转发节点来维护其他两个节点的连通性。当需要新路由时，我们以最小化广播和传输延迟为目标，设计了一个协议来提高DSDV在创建和维护自组织网络方面的性能特征。2.特征优点：(1)基本的路由算法是距离矢量算法，但它有所改进，其思想简单易懂。(2)按需路由协议，节点只存储所需的路由，减少了内存需求和不必要的复制。(3) UDP封装，属于应用层协议。(4)支持中间节点的回复可以使源节点快速获得路

3、由，有效减少广播次数，但存在过时的路由问题。(5)通过使用目的序列号来避免路由环路，解决了传统的基于距离矢量的路由协议的无限计数问题。(6)具有网络可扩展性。(7)对活动路径上断开的链接做出快速响应。缺点：在无线个人局域网中，拓扑结构相对简单，网络规模相对较小，节点位置不固定。设计时首先要考虑的因素是简单、节能等。3.路线发现(a)广播RREQ路由请求帧(b)中间节点向源节点更新它们的路由表(c)如果接收到RREQ的节点不是目的地节点并且没有到目的地节点的更新的有效路由，则转发RREQ(d)中间节点维护指向路由发起节点(源节点)的反向路由(e)目的节点或具有到目的节点的有效路由的中间节点生成R

4、REP路由响应帧(f)通过先前建立的反向节点向源节点单播RREP(g)当源节点接收到RREP响应帧时，源节点可以向目的节点发送数据包。4.路由维护你好消息当TTL=1时，问候信息帧实际上是RREP帧。生存时间是一个数据包字段，它指示帧的传播跳数。Hello消息帧用于监控活动路径上相邻节点的链路状态。例如，当活动路径上的节点在允许的_ hello _ loss * hello _ interval的毫秒内没有接收到Hello消息帧或路径上的相邻节点发送的任何其他帧时，该节点认为其与相邻节点的链路已断开。只有当一个节点在活动路径上时，它才能发送Hello消息帧。5.判断新旧路由信息AODV依靠网络

5、中的每个节点来维护自己的序列号。在广播路由请求帧RREQ之前，源节点应该更新它自己的序列号，也就是说，将序列号加1。在生成RREP响应帧之前，目的节点还应该在自己的序列号中添加1。当每个节点在自己的序列号上加1时，它被认为是一个无符号数。通过将来自目的节点的路由控制帧中的序列号SN1与该节点维护的目的节点的序列号SN2进行比较，可以确定该链路的新旧程度，然后可以进行相应的处理。如果SN2-SN10(减去有符号数)表示路由表中维护的信息已过期，则路由信息应更新为路由控制帧中的最新路由信息。6.拥塞控制当源节点在发送RREQ后的指定时间内没有从目的节点接收到RREP时，它可以选择再次发送RREQ路

6、由请求帧。如果在尝试RREQ_RETRIES后仍未收到RREP，请在路由表中标记目标节点不可达，并通知应用层。每次重传RREQ请求帧时，等待RREP响应帧的时间应根据原始时间乘以2，以避免拥塞。DSR议定书1.概观动态源路由是一种按需路由协议，它允许节点动态发现到目的节点的多跳路由。源路由是指每个数据包的报头携带一个节点列表，所有数据包在到达目的节点之前都必须经过该列表，也就是说，数据包包含一条到目的节点的完整路由。在自组织网络中，移动节点需要其他节点的帮助才能将数据包传输到目的节点，目的节点能够快速适应节点移动时路径的变化，并且能耗较低2.特征优点：(1)采用源路由机制，避免路由环路。(2)

7、采用路由缓存技术，避免了每次路由中断时都需要进行路由发现，减少了路由请求信息对信道的占用(3)中间节点不需要存储转发数据包所需的路由信息，网络开销较小缺点：(1)随着跳数的增加，包头长度线性增加，开销较大(2)路由请求包RREQ通过洪泛扩散到整个网络，导致网络负载过重(3)来自相邻节点的RREQ分组可能在某个节点上冲突。解决方案是在发送RREQ数据包时引入随机延迟(4)当源节点发送路由请求包RREQ时，可能会收到多个节点缓存的路由信息到达目的节点，导致竞争。解决方案：如果一个节点听说其他节点发送的RREQ数据包中的路由信息包含较少的跳数，该节点将停止发送。(5)源节点发送路由请求包RREQ时，

8、可能会接收到多个节点缓存的路由信息到达目的节点，但有些路由信息可能已经过时。解决方案：当引入定时器并且链路断开时，整个网络应该被淹没。3.路线发现(洪水路线)当一个节点要发送数据包时，源节点首先检查缓存中是否有到目的地的路由信息，如果有未过期的路由，它可以直接采用，否则，它将广播并发送一个路由请求包。(1)初始广播路由请求(2)中间节点接收后，进行如下处理：如果之前已经收到请求，则放弃该请求；如果该节点的地址在请求中，则放弃该请求；如果到达目的节点，它将返回路由回复。否则，将您自己的地址添加到数据包的路由记录中，并将其转发给相邻节点(3)如果是目的节点，返回路由应答包，当源节点收到路由应答时，

9、路由发现过程结束。如果RREQ分组存在于最近接收的“历史RREQ列表”中，或者路由记录包括该节点，则该节点将删除“路由请求”分组，以防止循环处理和路由循环。4.路由维护路由建立后，源节点将传输数据，在此过程中需要维护已建立的路由。源节点可以通过路由维护机制检测网络拓扑的变化，从而知道到目的节点的路由是否可用。当路由维护检测到正在使用的路由有问题时，它将向源节点发送RERR(路由错误消息)。收到RERR后，源节点将从其路由缓存中删除包含故障链路的所有路由，并重新启动路由发现过程。DSR与ADOV之比较1基本算法类型：AODV采用逐跳路由算法，每个节点只记得下一跳；DSR使用源路由算法，每个节点都

10、记住整个路由。2 .路径支持：AODV单一路径；DSR多路支持。如果一条路径损坏，可以使用路由缓存中的其他路径。3定期广播：AODV也定期发送Hello数据包，以维护路由；DSR不要求定期广播。4逻辑结构：两者都是平面路由，协议中的所有节点都具有同等的地位。5单向链路支持：AODV依赖于对称链路；DSR可以处理不对称链接的网络。6 .路由获取机会：DSR首先检查缓存中是否有到目的节点的未到期路由，如果有，则直接使用可用路由，否则，启动路由发现过程；每当AODV需要到新节点的路径时，它就会启动路由发现过程。注水(注水方法)1.概观泛洪意味着从任何节点通过路由器发送的数据包将被发送到连接到路由器的

11、所有其他节点(发送数据包的节点除外)。首先，源节点通过网络向其每个邻居节点发送数据的副本，然后每个邻居节点相互发送数据，发送数据的节点除外。这一直持续到数据传输目标节点或数据集寿命(TTL)为0。2.特征优点：它易于实现，容错性强，不需要消耗计算资源来维护网络拓扑信息和实现复杂的路由发现算法，适用于鲁棒性要求高的场合。缺点：(1)存在信息爆炸问题，即一个节点可能获得一个数据的多个副本。(2)会有部分重叠。如果同一观测环境中同类传感器的两个同事对一个事件做出反应，并且他们收集的数据具有相同的属性和相似的值，那么这两个节点周围的相邻节点将接收到数据的两个副本。(3)盲目使用资源，即扩散方法没有考虑

12、每个节点的能量可用性，因此无法做出相应的自适应路由。3.算法模型接收消息的任何节点ni的动作可以用下面的伪代码来描述。每条消息都包含TTL(消息寿命)、DATA等。(1)信宿和其他节点广播它们自己的位置信息和序列号；(2)源节点广播消息；(3)如果接收消息的节点是信宿，则消息已经被发送到目的地；否则转到(4)；(4)如果消息的TTL-1等于0或者节点已经接收到消息，则转到(5)，否则转到(6)；(5)节点丢弃消息；(6)该节点将消息转发给其所有相邻节点。闲聊协议1.概观流言协议是对洪泛协议的改进，在洪泛协议中，节点将生成或接收的数据随机转发给一个或多个相邻节点，从而避免了以广播形式传输信息的能

13、耗，避免了内爆，但增加了延迟，避免了重叠问题。每次选择下一跳节点时，都没有采用相关的路径优化算法，因此选择的路由往往不理想，这将导致端到端时延增加或数据包到达目的节点前的生命周期结束。2.算法节点n通过向随机选择的b邻居发送消息m来完成该消息传播：当(节点p从节点q接收到消息m)时如果(p收到的m不超过Ftimes)p将m统一发送给B，随机发送给该p的邻居知道还没有见过米b表示在一次传播中可以转发消息的邻居节点的最大数量；参数f决定了一个节点向其邻居转发相同消息的次数。例如，如果f为1，节点只将第一个接收到的消息M转发给它的B邻居，稍后到达的消息M将被忽略。通过调整B和F，我们可以在效率和成本

14、之间找到平衡，以满足不同的需求。当f为1时，b是网络中节点的最大数量，这就是泛洪协议。自旋协议1.概观传感器信息协商协议(spin)是一种以数据为中心的自适应通信路由协议。它利用节点间的协商机制和资源自适应机制，解决了传统协议中资源内爆、重叠和盲目使用的问题。SPIN协议有三种数据包类型，即ADV、请求和数据。ADV用于广播元数据(元数据指数据的属性)，REQ用于请求发送数据，数据是传感器收集的数据包。洪水得到了改善。考虑到WSN数据的冗余性，相邻节点感知到的数据是相似的，通过节点间的协商减少了数据传输，只广播其他节点没有的数据。2.路由过程传感器节点与自旋协议交互的基本过程；(1)节点a收集

15、数据m.带有m个元数据(元数据是指数据的属性)的Adv包被向外广播。(2)邻居节点B接收到A的adv数据包，并根据其携带的元数据判断是否需要数据M。如果不需要，销毁adv数据包。如果需要，生成相应的请求数据包并向外部广播。(3)节点甲接收来自节点乙的请求数据包请求，并生成相应的异相广播数据包。(4)节点B接收到节点A的数据包，并存储该数据包(5)节点B继续广播具有M个元数据的adv数据包，以便在网络中传输数据M。3.特征优点：(1)简单，一个节点只需要知道它的邻居节点，不需要其他拓扑信息(2)节点只广播数据，其他节点不必减少冗余数据，从而有效降低能耗。(3)利用三步握手机制解决内爆(4)利用数据融合部分解决重叠问题(5)不需要路线维护(6)对网络拓扑数不敏感缺点：(1)本质上，它仍在向整个网络传播新消息，开销相对较大(2)当多个节点同时向同一个节点发送请求消息时，需要一种退避算法定向扩散协议1.概观定向扩散路由协议是一种重要的基于数据和查询驱动的路由机制。汇聚节点通过兴趣消息发送查询任务，并将兴趣消息泛洪到整个区域或部分区域的所有传感器节点。兴趣信息用于表示查询任务，表达网络用户对检测区域感兴趣的信息，如检测区域的温度、湿度