无线传感器网络的路由协议

1、 无线传感器网络的路由协议路由协议概述无线传感器网络的路由协议路由协议主要任务是确保数据由确保数据由源节点准确高效地传输到目的节点源节点准确高效地传输到目的节点，即寻找数据的寻找数据的最优路径最优路径以及沿最优路径发送数据沿最优路径发送数据。能耗：能耗：WSN中，路由协议的制定受能耗的限制。邻居发现过程：邻居节点间交换信息会消耗能量，交换数据越大，能耗越大。处理过程：数据传输过程的计算和通信会消耗能量，通信的能耗大于计算。可扩展性可扩展性：路由协议需能满足网络拓扑形态的变化，即使发生变化，节点也能有效把握网络传输路径情况。编址：编址：用户对来自多个节点的整合后信息感兴趣，而非单个节点，因此唯一

2、编址方式不适合WSN健壮性健壮性：防止由于部分节点故障失效造成的信息丢失，以及信道不稳定造成的信息受损和丢失。路由协议概述拓扑拓扑：路由协议需能适应WSN的拓扑变化。预订拓扑：节点相对固定，可实现高效路由协议。随机拓扑：网络自组织，可利用拓扑发现作为路由计算的前提，路由协议也需适应节点或观测目标的移动。设计目的设计目的：网络的目的(上层应用)的不同导致路由协议原则的不同。路由协议概述WSN路由协议的分类能量感知路由WSN网络是能量受限的网络，节省能量是路由设计需考虑的重要因素。能量路由是WSN最基本的路由协议之一能量路由是根据节点可用能量(Power Available，PA)或传输路径上的能

3、量需求(E)，选择数据的转发路径。节点可用能量就是节点当前的剩余能量。基本能量路由能量感知路由基本能量路由路径1：源BA目标， PA=4，E=3；路径2：源CBA目标， PA=6，E=6；路径3：源D目标， PA=3，E=4；路径4：源FE目标， PA=5，E=6。最大PA路由：路径2最小能耗路由：路径1最少条数路由：路径3最大平均路由：路径4能量感知路由能量多径路由能量多径路由基本思想能量多径路由基本思想在源节点和目标节点之间建立多条数据传输路径根据每条路径上节点的剩余能量和传输消耗的能量来给每条路径赋予一定的选择概率依概率在多条路径中选择传输路径，均衡消耗节点能量，延长网络生存期传统能量路

4、由频繁通过某一路径传输数据，易导致该路径上节点能量消耗过快，节点提早失效。能量感知路由能量多径路由路径建立路径建立n建立从源节点到目的节点的多条路径n计算出各条路径的选择概率主要过程数据传输数据传输n对于接收到的每组数据，节点根据概率从所有下一跳节点中选择一个节点路由维护路由维护n周期性从目的节点到源节点进行洪泛查询以维护路径的有效性和活跃性能量感知路由能量多径路由路径建立具体过程目的节点目的节点向邻居广播路径建立消息邻居邻居收到消息，如处于目的节点和源处于目的节点和源节点节点之间则转发，否则丢弃如节点决定转发(加入路由集合)，则更新转发消息更新转发消息中的代价值中的代价值如选择某一邻居代价代

5、价太高太高，则放弃选择路由集合中的节点计算下一跳各选择的概率，概率与代概率与代价成反比价成反比节点根据选择概率选择概率和能量消耗和能量消耗计算自己到目的节点的传输代价泛洪是一种传统的路由技术。泛洪算法的主要思想是由某节点发起数据广播，然后任意一个收到广播的节点都无条件将该数据包广播出去，每一节点都重复这样的过程直到数据遍历全网或者达到规定的最大跳数。数据包像洪水一样漫过所有地方，因此称为洪泛协议。算法不用维护网络拓扑结构和路由计算，实现简单。但是最主要的是内爆和重叠以及资源盲点等。洪泛 (Flooding)协议以数据为中心的路由协议洪泛 (Flooding)协议以数据为中心的路由协议内爆现象内

6、爆现象：洪泛机制允许大量冗余消息，节点会收到来自多个邻居节点转发的相同消息。重叠现象重叠现象：监测同一区域的节点容易产生相同的信息，造成传播过程中的信息冗余，消耗大量能量。谣言协议是对洪泛协议的改进。当节点收到数据包时，只将数据包随机转发给与其相邻的节点的某一个节点或几个，而不是所有节点。选定的邻居也采用同样的办法转发下去。优点：降低数据转发重叠的可能性，减少内爆现象的发生。缺点：点到点的时延较大随机转发某一个节点的方向并不一定在距离目的节点更近的方向上，易造成数据超时或者跳数己达最大，导致递送失败。开始的短时间内发送速率很大，随着数据的发送，速度明显降低。谣言 (Gossiping)协议以数

7、据为中心的路由协议SPIN协议以数据为中心的路由协议信息协商传感器信息协商传感器(SPIN)协议协议是 最基本的一类WSN路由协议，是对Flooding协议的改进。考虑到WSN的数据冗余，临近节点所感知的数据具有相似性，通过协商和能量自适应来减少数据传输量，解决洪泛协议存在的不足。SPIN协议采用了两种机制： 在数据发送前通过协商确定是否发送在数据发送前通过协商确定是否发送 节点监测自己的能量并进行能量感知决策节点监测自己的能量并进行能量感知决策SPIN协议假定两点间的通信不受到其他节点的干扰，分组不会丢失，功耗无限制进。SPIN协议包括三种类型的消息：广告消息广告消息(Advertise,A

8、DV)、请求发请求发送消息送消息(Request,REQ)、数据消息数据消息(Data transfer,DATA)SPIN协议以数据为中心的路由协议三次握手三次握手机制(点对点模式，即SPIN-PP)节点A向邻居B发送ADV，ADV消息对DATA消息进行了描述。如果B对DATA消息感兴趣，则发送REQ消息给A节点。A收到REQ后，将DATA消息发送给B节点。SPIN协议以数据为中心的路由协议三次握手三次握手机制(点对多点模式)节点B向多个邻居节点发送ADV。有部分收到ADV的节点对DATA感兴趣，回复REQ。B节点向回复REQ的节点发送DATA。SPIN协议以数据为中心的路由协议SPIN-E

9、C机制(在SPIN基础上加入能量感知功能)当一个节点的可用能量低于阈值，该节点不参与DATA消息的转发。低能量节点只接收消息。通过减少参与转发活动，能耗可降低10%。SPIN协议以数据为中心的路由协议SPIN-BC机制当一个节点发送REQ时，其他节点可以听到此与DATA有关的REQ，则放弃此次发送REQ等待DATA消息。源节点收到REQ，会将DATA广播出去，感兴趣的节点可以收到这个DATA。SPIN-RL机制如一节点对DATA感兴趣，但由于信道错误等原因，未收到DATA消息。该节点可以向其他可能收到DATA消息的邻居节点发起传输请求，获得DATA消息。n优点优点解决了内爆问题和部分解决了重叠

10、问题不需要进行路由维护对网络拓扑变化不敏感，可用于移动WSNn缺点缺点本质上SPIN还是向全网扩散新消息，开销比较大 当多个节点向同一个节点同时发送REQ时，需要退避算法 SPIN协议以数据为中心的路由协议定向扩散协议以数据为中心的路由协议定向扩散定向扩散( (Directed Diffusion) )协议协议：汇聚节点汇聚节点接到上层应用的查询任务后，将兴趣消息通过洪泛方式周期性地广播广播出去，即告诉其他节点我要收集什么兴趣。在传输过程中建立从数据源节点到汇聚节点的传输梯度。在区域内“兴趣”匹配节点沿着梯度方向通过路径传送数据到汇聚节点。n四个阶段：兴趣扩散兴趣扩散（采用泛洪）；梯度建立梯度

11、建立（反向建立）；强化路径强化路径（汇聚节点会收到多条路径，选最优路径，进行加强，以后的数据按照加强路径传送）数据传输数据传输n汇聚节点汇聚节点向全网查询兴趣兴趣，邻居节点邻居节点更新自己的兴趣缓存兴趣缓存，并且转发n兴趣缓存中的条目(兴趣表项)时间戳：指示接收到相关兴趣消息的最近时间梯度：当前节点从哪个邻居收到兴趣消息以及相应的数据传输率 持续时间：该兴趣消息的有效期定向扩散协议以数据为中心的路由协议路径增强路径增强:在多条对应的梯度路径中，汇聚节点可以对某一条路径经行梯度增强。沿这条路径再次发送兴趣消息当前节点选定下一跳，兴趣消息只会发送给选定的下一跳节点逐跳传导下去，即形成一条专门的路径

12、定向扩散协议以数据为中心的路由协议反向路径增强反向路径增强:如之前的某条路径遭到破环，汇聚节点需“增强”另一条路径就可以改变数据的路由向之前的路径发送反向增强消息，抑制节点使用之前路径传输数据GBR路由(Gradient-Based Routing)协议：梯度域扩展（传感器节点到Sink节点的跳数信息、无线链路评估信息）EAR(Energy Aware Routing)路由协议：建立路由过程中加入能量评估机制；路由路径的能量开销大于某一阈值不采用；CADR路由(Constrained Anisotropic Diffusion routing)协议：兴趣消息往指定方向发送定向扩散协议以数据为中

13、心的路由协议定向扩散协议以数据为中心的路由协议n优点优点数据中心路由，定义不同任务类型/目标区域消息；路径加强机制可显著提高数据传输的速率；周期性路由：能量的均衡消耗；n缺点缺点周期性的洪泛机制-能量和时间开销都比较大；Sink周期性广播，不适用于大规模网络 节点需要维护一个兴趣消息列表，代价较大；分层路由协议分层路由基本思想分层路由基本思想网络划分为多个簇，每个簇由簇头和簇成员组成簇头组成更高一级的网络，簇头管理簇内节点，收集融合簇内信息簇头节点间还可以再次分簇分层结构扩展性较好，适合大规模网络使用扁平结构路由协议容易使汇聚节点及周围形成性能瓶颈，加重这些节点能量消耗，缩短网络生命周期。LE

14、ACH协议分层路由协议LEACH协议是最早最基本的一种分层路由算法，主要考虑簇内节点能耗使用Leach协议后，形成两级星形结构簇头作为一定区域所有节点的代理，负责和Sink的通信簇头节点可以对所辖区域节点数据进行融合，减少网络中传输的数据；簇内节点与簇头距离近，使用小功率与簇头节点通信，功耗小簇头消耗大量能量，所以定期选举簇头，簇头选举算法的设计，要求保证公平性LEACH协议分层路由协议网络按照周期工作，每个周期分为两个阶段：簇头建立阶段： 节点运行算法，确定本次自己是否成为簇头（选簇）； 簇头节点广播自己成为簇头的事实； 其他非簇头节点按照信号强弱选择应该加入的簇头，并通知该簇头节点； 簇头

15、节点按照TDMA的调度，给依附于他的节点分配时隙；稳定工作阶段： 节点在分配给他的时隙上发送数据；LEACH协议分层路由协议稳定工作阶段： 只有簇头节点一直保持活跃状态 簇成员节点按需要保持活跃或者在不发送数据时进入睡眠状态稳定工作状态结束后，所有节点进入下一周期，重新建立簇并通信n优点优点每个节点都有机会担任簇头，能耗平均消耗；优化了传输数据所需能量；优化了网络中的数据量（簇头数据融合）；延长了网络寿命；n缺点缺点节点硬件需要支持射频功率自适应调整；无法保证簇头节点能遍及整个网络；分簇与簇头选举 要公平LEACH协议分层路由协议PEGASIS协议分层路由协议PEGASIS协议是对于LEACH

16、的一种改进，节点间不再组成簇，而是组成链PEGASIS协议基本原理： 1.假定传感器节点是同构和相对静止的 2.节点通过发送能量递减的测试信号，确定相邻节点的位置 3.进而了解网络的全局信息 4.节点选择其最近的邻居作为链上的下一跳 5.节点只需维护自己上一跳和下一跳的邻居信息PEGASIS协议分层路由协议链上的通信按照节点顺序进行，下一跳节点汇聚来自上一跳的数据，直到链头汇聚了链上所有节点的数据链头节点通过传递令牌来控制节点间的通信次序PEGASIS协议分层路由协议n优点优点不需要周期性选举簇头节点；采用最佳链路进行数据传输；采用数据融合技术，减少了整体数据的发送和接收；降低能耗，相对LEA

17、CH协议降低50%75%；延长网络寿命。n缺点缺点节点维护位置信息需要额外资源；链头通信量大，其失效会导致路由失败；成链算法要求节点知道其他节点位置，开销较大；如果链过长，传输时延会增大。TEEN协议分层路由协议TEEN协议按照分层结构组织节点，利用过滤方式减少数据传输量，即用来提供基于事件的数据传递。TEEN协议基本原理： 1.采用与LEACH协议相同的聚簇方式，但簇头根据与汇聚节点的距离形成层次结构 2.聚簇完成后，汇聚节点通过簇头向全网广播两个阈值(即硬阈值和软阈值)以过滤数据的传输 3.在节点第一次监测到数据超过硬阈值时，节点向簇头上报数据，并将当前监测数据保存为监测值(SV) 4.此

18、后只有当监测到的数据大于硬阈值而与SV之差不小于软阈值时，节点才向簇头上报数据，并更新SVTEEN协议分层路由协议硬阈值规定了什么情况下需要传输数据，即事件。软阈值设置了事件发生时数据的传输频率。通过引入两个阈值限制，TEEN协议大幅减少了数据传输的次数。TEEN协议分层路由协议n优点优点通过硬阈值和软阈值减少了数据传输量；多层次型簇头结构不要求节点具有大功率通信能力；能耗低，适用于事件响应型应用。n缺点缺点如某节点的监测数据始终未达到硬阈值，则无法获得该节点任何数据，也无法掌握该节点状况，是否失效； 不适用于需周期性采样的应用。GEAR协议基于地理位置的路由协议GEAR协议中，已知目标区域的

19、位置信息，节点知道自身位置信息和可用的能量信息。GEAR协议基本原理： 1.查询消息到达目标区域的路径：节点选择传输代价最小的邻居作为下一跳并转发数据 2.查询命令到达事件区域后，采用递归转发或受限洪泛方式进行传输 3.节点会更新传输代价GEAR协议基于地理位置的路由协议节点利用贪心算法贪心算法选择邻居节点到达指定区域的代价估计代价： C(Ni ,R)=Distance( Ni , R) + (1)Left_Enery(Ni )实际代价：C(Ni ,R)=Enery_Cost(Ni ,R)+(1)Left_Enery(Ni ) Ni为有转发需求的节点的邻居节点，R为目标区域的中心位置。当N不知道Ni的实际代价时使用估计代价。GEAR协议基于地理位置的路由协议在递归转发方式中，目标区域分成4个子区域，将查询命令转发至子区域中心子区域再次划分并进行转发，知道子区域只剩下一个节点，则该节点收到查询命令后不再转发GEAR协议基于地理位置的路由协议n路由空