物联网讲座05-WSN路由协议

物联网技术概论内容提纲1WSN路由协议概要2WSN路由协议分类3WSN协议的主要最新成果物联网技术概论1WSN路由协议概要物联网技术概论1WSN路由协议概要作用：路由协议负责将数据从源节点(S)通过网络转发到目的节点(D)。功能：寻找源节点和目的节点的优化路径：公平高效、低延迟、避免拥塞、均衡网络流量；将数据协议沿着路由协议正确转发；设计目标满足应用需求低网络开销资源利用的整体有效性网络高吞吐率节约能量物联网技术概论WSN网络特点特点自组织的网络（随机部署）数据的冗余性（多节点监测同一事件）基于局部拓扑信息（硬件限制）网络功能（数据收集）数据为中心物联网技术概论WSN路由协议设计要求无线传感网络具有很强的应用相关性，所以路由协议没有一个通用的万能的协议，应根据具体应用来选择路由协议。要求 能量高效（协议简单&节省能量&均衡消耗）可扩展性（网络范围&节点密度）鲁棒性（节点变化&拓扑变化）快速收敛性灵活性物联网技术概论WSN路由协议关键技术考虑网络和节点能量优化（硬件限制）具有高可扩展性（网络规模&自组织）

适应强网络拓扑变化（节点移动&无线信道）传感器网络路由中使用数据融合技术（数据为中心）传感器网络中流量分布不对称（数据收集网络&多源单Sink)物联网技术概论WSN路由协议的挑战自组织布撒（Adhocdeployment）能量消耗（Energyconsumption）路由精度（Routingaccuracy）计算能力（Computationcapabilities）通信能力（Communicationtolerance）容错能力（Faulttolerance）可扩展性（Scalability）控制负载（Controloverhead）物联网技术概论路由的性质a)单播b)广播c)多播d)任播e)k-任播物联网技术概论2WSN路由协议分类物联网技术概论WSN路由协议分类从具体应用出发，进行分类，大致可分类四类：能量感知路由协议基于查询的路由协议地理位置路由协议Qos路由协议物联网技术概论能量感知路由协议物联网技术概论能量感知路由特点：从数据传输中的能量消耗出发，讨论最优能量消耗路径以及最长网络生存周期。路由方式：根据节点的可用能量（PA，poweravailable）或传输路径上的能量需求，进行数据的转发。节点的可用能量就是剩余能量。物联网技术概论能量路由算法示意图汇聚节点源节点a1=1a2=1a3=2a4=2a6=2a10=2a7=1a8=2a9=1a5=2A(PA=2)B(PA=2)C(PA=2)D(PA=3)E(PA=1)F(PA=4)路径1：源-B-A-SINK，所有节点的PA之和为4，在该路径上转发分组需要能量之和为3;路径2：源-C-B-A-SINK,所有节点的PA之和为6，在该路径上转发分组需要能量之和为6;路径3：源-D-SINK,所有节点的PA之和为3，在该路径上转发分组需要能量之和为4;路径4：源-F-E-SINK,所有节点的PA之和为5，在该路径上转发分组需要能量之和为6；物联网技术概论路由策略分析路由策略：最大PA路由：路径2的PA之和最大，但包含了路径1，不是最优解，应选择路径4。最小能量消耗路由：路径1能量消耗最小。最少跳数路由：选择从源到汇聚节点的最小跳数路径，选择路径3最大最小PA节点路由：路径上每个节点的可用能量不同，从中选取每条路径中最小能量的节点表示这条路径的可用能量，最大最小路径就是选择可用能量最大的路径。物联网技术概论能量路由算法分析较好的解决了能量均衡问题，延长了网络生存周期。算法的收敛性较好网络负载未必均衡节点需要知道全局网络信息，但WSN资源约束，节点只能获得局部网络信息。物联网技术概论能量多路径路由（1）传统网络的路由机制往往选择从源到目的节点之间跳数最小的路径，但是再WSN中，频繁的使用同一条路径传输数据，就会造成该路径上的节点因能量消耗过快而过早失效，从而使网络分割成互不相连的孤立部分，减少了网络生存期。能量多路径路由在源节点和目的节点之间建立多条路径，根据路径上节点的通信消耗及节点剩余能量情况，给每条路径赋予一定概率，使数据传输均衡消耗网络能量。物联网技术概论能量多路径路由（2）能量多路径路由包括路径建立、数据传播和路由维护三个过程。每个节点需要知道到达目的节点的所有下一跳节点，并计算选择每个下一跳节点的概率。概率的选择根据节点到目的节点的通信代价来计算的，用Cost(Ni)表示节点i到目的节点的通信代价。节点到目的节点的路径很多，这个代价值是加权平均值物联网技术概论能量多路径路由（3）过程描述如下：1）目的节点向邻居节点广播路径建立消息，启动路径建立过程。路径建立消息中包含一个代价域，表示发出该消息的节点到目的节点路径上的能量信息，初始值为0.2）当节点收到邻居节点的路径建立消息时，相对发送该消息的邻居节点，只有当自己距源节点更近，而且距目的节点更远的情况下，才需要转发该消息，否则丢弃该消息。3）如果节点决定转发该消息，需要重新计算代价值替代原来的代价值。当路径建立消息从节点Ni到节点Nj时，该路径的通信代价为节点Ni的代价值加上两个节点间的通信代价，即：物联网技术概论能量多路径路由（4）4)节点要放弃代价太大的路径，节点Nj将节点Ni加入本地路由表FTj的条件是：5）节点为路由表中每个下一跳节点计算选择概率，节点的选择概率与能量消耗成反比。节点Nj选择公式如下：6）节点根据路由表中每项的能量代价和下一跳节点选择概率计算本身到目的节点代价Cost(Nj)。Cost(Nj)定义为经由路由表中节点到达目的节点代价的平均值，即：物联网技术概论能量多路径路由性能分析将通信代价分散到多跳路径上，实现整个网络的能量平稳降级，最大限度的延长网络生存周期。维护代价太高，需要周期性的从目的节点到源节点实施洪泛查询来维持所有路径的活动性。扩展性不好，不适宜节点动态加入和离去。物联网技术概论基于查询的路由定向扩散路由（directeddiffusion,DD)谣传路由（rumorrouting)物联网技术概论定向扩散路由汇聚节点通过兴趣消息发出查询任务，采用洪泛方式传播兴趣消息到整个区域或部分区域内的所有传感器节点。兴趣消息采用表示查询的任务，表达网络用户对监测区域内感兴趣的信息，例如监测区域的温度、湿度等。在兴趣消息的传播过程中，协议逐跳地在每个传感器节点上建立反向的从数据源到汇聚节点的数据传输梯度(gradient)。传感器节点将采集到的数据沿着梯度方向传送到汇聚节点。物联网技术概论定向扩散路由Sink节点向全网查询兴趣M建立源节点和Sink间路径兴趣在全网中扩散对每一个活动任务，Sink周期进行查询邻居更新自己的兴趣消息，并且转发兴趣消息中的条目时间戳：指示接收到相关兴趣消息的最近时间若干梯度域：每个梯度和其邻居节点相关联每个梯度中含有一个指定的数据传输率持续时间：该兴趣消息的有效期物联网技术概论定向扩散路由查询消息的传播—建立数据的传输梯度汇聚节点发送查询消息兴趣消息：任务性质、数据采集/发送速率、时间戳等中间节点：记录转发梯度：表示了数据的传输方向定向扩散路由路径增强---汇聚节点在收到许多低速率数据后，向数据到达最快的邻居节点发送增强消息，增强消息表示汇聚节点要求高速率的发送数据，相应邻居节点按照同样的方式，一次传递增强信息给其邻居节点，直到到达数据源，据此构建数据发送的主路径。DD适用持续性查询的应用而不适用于一次性查询的应用，代价较大。物联网技术概论物联网技术概论定向扩散路由协议-路径修复加强路径上的节点可以触发和启动路径的加强过程新路径C和源节点之间路径断裂物联网技术概论定向扩散路由协议分析优点数据中心路由，定义不同任务类型/目标区域消息；路径加强机制可显著提高数据传输的速率；周期性路由：能量的均衡消耗；缺点周期性的洪泛机制---能量和时间开销都比较大；节点需要维护一个兴趣消息列表，代价较大；物联网技术概论DD协议族GBR路由(Gradient-BasedRouting)协议：梯度域扩展（传感器节点到Sink节点的跳数信息、无线链路评估信息）EAR(EnergyAwareRouting)路由协议建立路由过程中加入能量评估机制；路由路径的能量开销大于某一阈值不采用；CADR路由(ConstrainedAnisotropicDiffusionrouting)协议兴趣消息往指定方向发送物联网技术概论谣传路由传感器节点采用代理消息，代理消息沿随机路径向外扩散传播，汇聚节点发送的查询消息也随机在网络中传播。物联网技术概论谣传路由工作原理1）每个传感器节点维护一个邻居列表和一个事件列表；事件列表包括事件名称、跳数等，同时根据一定的概率产生一个代理消息。2）收到代理消息的节点，将代理消息和事件列表的表项做比较，根据跳数值决定更新代理消息或事件列表的表项。如本地事件列表无此表项，则将生存期减1，再随机转发。3）任何节点可以产生查询消息4）查询消息路径和代理消息路径的交叉节点沿查询消息反向路径建立连接。物联网技术概论谣传路由分析通过消息生存期解决环路问题。避免了洪泛方式，减小了网络开销随机性强，不能做到优化路由。物联网技术概论地理位置路由物联网技术概论地理位置路由在一些传感器网络的应用中，不光要知道网络中产生的事件，还需要知道事件产生的位置。如在森林防火中，不光需要知道发生了火灾，还需要知道在哪发生了火灾。地理位置路由假设节点知道自己的地理位置信息，以及目的节点和目的区域的地理位置信息。以地理位置信息作为路由依据。地理位置的精确度和代价相关，在不同的应用中会选择不同精确的位置信息来实现数据的路由转发。物联网技术概论GEAR路由协议应用建立到特定区域的路由查询工作方式前提已知目标区域的位置信息节点知道自己位置信息和剩余能量节点直到邻居节点的位置信息和剩余能量节点间无线链路是对称的物联网技术概论GEAR路由协议分两个阶段：查询消息到达目的区域的路径查询消息在目标区域的传播选路依据节点到查询区域通信能量能耗节点本身的剩余能量最小代价节点为转发节点物联网技术概论GEAR路由协议查询命令传送到目标区域贪婪算法－选择邻居节点到达指定区域的代价估计代价：

F(Ni,R)=α•Distance(Ni,R)+(1−α)•Left_Enery(Ni)实际代价：F(Ni,R)=α•Enery_Cost(Ni,R)+(1−α)•Left_Enery(Ni)归一化处理

Ni为有转发需求的节点的邻居节点，R为目标区域的中心位置。当N不知道Ni的实际代价时使用估计代价。

物联网技术概论GEAR路由协议查询在监测区域内传送：洪泛方式，迭代地理转发将目标区域分解为若干子区域、向子区域的中心位置转发）物联网技术概论GEAR路由协议-路由空洞问题路由空洞：邻居节点传输代价都比本地节点大处理办法：选择邻居节点中代价最小的作为转发节点；修改本地节点的转发代价；

F(N,R)=F(Nmin,R)+C(N,Nmin)，C(N,Nmin)表示将数据包从N传送到Nmin的代价物联网技术概论GEAR路由协议-路由空洞KLTFGHIJABCDES物联网技术概论GEAR路由评价优点利用了位置信息，避免了查询消息的Flooding；考虑了消耗的能量和节点剩余能量，均衡消息；路径选择可达到局部最优；迭代地理转发对洪泛机制的补充；缺点可能出现路由空洞（局部信息）-两跳信息；不适合在移动WSN使用物联网技术概论GPSR路由协议GPSR（greedyperimeterstatelessrouting）这是一个典型的基于位置的路由协议.使用GPSR协议,网络节点都知道自身地理位置并被统一编址,各节点利用贪婪算法尽量沿直线转发数据.GPSR路由协议当节点S需要向节点D转发数据分组的时候，它首先在自己的所有邻居节点中选择一个距节点D最近的节点作为数据分组的下一跳，然后将数据传送给它。该过程一直重复，直到数据分组到达目的节点D或某个最佳节点。利用节点的地理位置信息转发节点选取：选择邻居节点中离目的节点更近的点作为转发节点物联网技术概论物联网技术概论局部优化问题存在x到D的路径x的邻居w,y离D的距离比x大解决方法：边界转发物联网技术概论边界转发平面图：二维空间结构；平面图中任意两条边都只相交于顶点；GPSR算法中构造平面图的方法是删除网络拓扑图中交叉的边算法：RNG(RelativeNeighborhoodGraph)GG(GabrielGraph)物联网技术概论平面图讲解下面的(a)、(b)、(c)、(d)为四个平面图.数一数,每个平面图各有多少个顶点?多少条边?它们分别围成了多少个区域（内部）?请将结果填入下表(按填好的样子做).(2)观察表格，推断一个平面图的顶点数、边数、区域数之间有什么关系？

3)现已知某个平面图有999个顶点，且围成了999个内部区域，试根据以上关系确定这个图有多少条边.平面图的判断平面图判断公式：（欧拉公式）面+定点-边=2物联网技术概论物联网技术概论RNG节点u，v之间存在边的条件是对于任意一个节点w，u到v的距离要小于或等于u到w或是v到w的距离的最大值，用下式表示：

物联网技术概论GG节点u，v之间存在边的条件是在以d(u，v)为直径的圆中没有其它节点，用下式表示：物联网技术概论物联网技术概论边界转发时的右手法则一个数据分组从节点y到达节点x；下一条边的选择：下一边是以x为定点，沿(x，y)顺时针方向上的第一条边，图中为(x，z)后续各边同样依次法则确定物联网技术概论Face平面图的边将整个图分成许多小的互补重叠的有界多边形和一些无界区域，这些有界多边形和无界区域统称为face。其中，有界区域称为内部face，无界区域称为外部face。途中xD通过3个有界face和一个无界face。物联网技术概论边界转发数据包在x点进入边界转发模式，通过face边界向目的节点D转发，这些face都被xD穿越；转发边的选择采用右手法则，初始边为xD；数据包在同一个face中转发时采用右手法则，当碰到与xD相交的边时，进行face切换，进入下一个face；物联网技术概论GPSR协议评价优点采用局部最优的贪婪算法，不需要维护网络拓扑，路由开销小；可适用于静态和移动的WSN网络；缺点需要地理位置信息的支持；需要维护邻居节点位置信息；物联网技术概论基于Qos的路由物联网技术概论基于Qos的路由无线传感网络的某些应用对通信的服务质量有较高要求，如高可靠性和实时性等；而由于网络链路的稳定性难以保证，通信信道质量比较低，拓扑变化比较频繁，要在无线传感网络中实现一定服务质量的保证，需要设计基于Qos的路由协议。基于不相交路径的多路径路由机制SPEED协议物联网技术概论基于不相交路径的多路径路由机制在WSN中，引入多路径路由是为了提高数据传输的可靠性和实现网络负载平衡。在多径路由中，首要的问题是解决如何建立源到目的地址的多跳路径。主要思想：首先建立主路径，再建立多跳备用路径。数据从主路径传输，同时利用备用路径低速传输数据维护路由有效性。物联网技术概论基于不相交路径的多路径路由机制物联网技术概论缠绕多路径局部缠绕多路径：主路径上的每一个节点（除两头节点外）都发送备用路径增强消息给自己的次优节点A，A寻找自己的最优节点B，如果B不再主路径上将继续向自己的最优路径转发，直到与主路径相交。Speed协议物联网技术概论物联网技术概论SPEED协议SPEED是一个实时路由协议，在一定程度上实现了端到端的传输速率保证、网络拥塞控制以及负载平衡机制。首先要求节点交换节点的传输延迟，以得到负载情况；然后利用局部地理信息和传输速率作出路由决定，同时通过邻居反馈机制保证网络传输速率在一个全局定义的传输速率阀值之上。物