无线传感器网络技术概述(路由协议)-lzy

无线传感器网络路由协议目录Internet路由机制概述传感器网络的路由概述经典传感器网络路由协议能量路由以数据为中心的路由：定向扩散路由、SPIN路由地理路由：GPSR路由、GEAR路由多路径路由：（不）相交多路径路由；总结INTERNET通信模式传统网络的通信模式:单播：点到点通信（主要方式）；组播：点到一组内的所有节点都有相应的IP地址泛播：点到一组内的一个节点广播：点到网络内的所有节点Internet路由机制概述传感器网络的路由概述经典传感器网络路由协议能量路由以数据为中心的路由：定向扩散路由、SPIN路由地理路由：GPSR路由、GEAR路由多路径路由：（不）相交多路径路由；总结传感器网络的通信模式传感器网络的通信模式点多点（汇聚节点－传感器节点）单播/广播（局部范围）传感器节点的标识节点ID没有位置的含义；通信关注的是：某个位置上或某种属性相关信息节点ID：不求全网唯一，局部唯一；邻居之间可相互区别；好处?不需要；节省能量；路由协议的特点特点自组织的网络（随机部署）数据的冗余性（多节点监测同一事件）基于局部拓扑信息（硬件限制）通信模式（数据收集）不以IP为中心，数据为中心？（不知道目的节点的编号，甚至在哪个区域）关心的是：数据，事件/地点/时间；路由协议的考虑有限能量供应、处理能力和通信带宽；可靠性；实时性；路由协议的要求传感器网络（Why现有协议不适合？）多跳的大规模网络；自组织的网络；网内数据融合处理的网络；节点少移动的网络；资源受限的网络；要求能量高效（协议简单|节省能量/均衡消耗）可扩展性（网络范围|节点密度）鲁棒性（节点变化|拓扑变化）快速收敛性目录Internet路由机制概述传感器网络的路由概述经典传感器网络路由协议能量路由以数据为中心的路由：定向扩散路由、SPIN路由地理路由：GPSR路由、GEAR路由多路径路由：（不）相交多路径路由；总结路由协议分类基于具体应用能量感知路由；基于查询的路由协议；地理位置路由协议可靠的路由协议；能量感知路由:－能量路由（1）能量路由：基于节点的可用能量（PowerAvailable）或传输路径上链路的能量需求选择数据的发送路径路径1：汇聚点-A-B-源节点，总PA=4，总a=3；路径2：汇聚点-A-B-C-源节点，总PA=6，总a=6路径3：汇聚点-D-源节点，总PA=3，总a=4；路径4：汇聚点-E-F-源节点，总PA=5，总a=6；能量感知路由:－能量路由（2）最大PA路由：选取从数据源到汇聚点所有路径中节点PA之和最大的路径最小能量路由：选取从数据源到汇聚点所有路径中节点耗能之和最少的路径最小跳数路由：选取从数据源到汇聚点所有路径中跳数最小的路径最大最小PA节点路由：选取从数据源到汇聚点所有路径中包含最小节点PA最大的路径能量感知路由:－能量路由（3）路径1：汇聚点-A-B-源节点，总PA=4，总a=3；路径2：汇聚点-A-B-C-源节点，总PA=6，总a=6路径3：汇聚点-D-源节点，总PA=3，总a=4；路径4：汇聚点-E-F-源节点，总PA=5，总a=6；最大PA路由：路径2最大的，但包含路径1，因不高效而排除，选择路径4；最少消耗能量路由：路径1最大最小PA节点路由：路径3评价：全网信息理想路由能量感知路由:－能量路由（4）优点优先考虑WSN最关心：能量；最大PA路由：能量均衡消耗（路径）；最小能量路由：能量最小消耗；最大最小PA节点路由：能量均衡消耗（节点）；缺点需要维护全网的拓扑信息和能量信息；结论理想路由；能量感知路由:能量多路径路由（1）目标均衡消耗节点能量增加网络的生存期。方法在源和目的之间建立多条路径，根据能量因素给每条路径赋予被选择使用的概率在发送数据时，基于概率随机选择其中的一条路径结果没有一条路径一直在传送数据，防止一条路径上节点能量消耗过快能量感知路由:能量多路径路由（2）三个阶段：路径建立阶段：根据能量代价建立源节点到目的节点的多条路径，并建立路由表；数据通信阶段或数据传播阶段：使用前阶段的信息，转发从源到目的节点的数据。根据早期计算的能量消耗，基于概率地选择数据传播的路径；路由维护：通过不经常的从目的到源节点的洪泛查询，维持所有路径的活动性。路径建立阶段是最关键的一个阶段能量感知路由:能量多路径路由（3）路径建立目的节点向邻居节点广播路径建立消息，发起路径建立过程中间节点：距离源节点更近同时距离目的节点更远的节点路径建立消息从节点Ni发送到节点Nj时本地路由表:节点Nj评价：多路经含义/目的以数据为中心路由协议定向扩散路由（DirectDiffusion）SPIN(SensorProtocolforInformationviaNegotiation)定向扩散路由（DIRECTDIFFUSION1）Sink节点：通过兴趣消息发出查询任务；通过洪泛方式传播兴趣；节点：接收仅广播一次查询消息；网络：洪泛（Flooding）；查询：温度30度的区域定向扩散路由（2）查询消息的传播—建立数据的传输梯度汇聚节点发送查询消息兴趣消息：任务性质、数据采集/发送数率、时间戳等中间节点：记录（邻居节点和兴趣内容）数据发送的节点→梯度转发邻居节点梯度：表示了数据的传输方向定向扩散路由（3）匹配数据的传输节点→邻居节点（发送interest）多个相同数据在网络中传递；路径：沿梯度发送给sink节点定向扩散路由（4）路径增强→形成主路径How？兴趣：建立多条路径增强：建立主路径周期性Why？定向扩散路由评价优点数据中心路由，定义不同任务类型/目标区域消息；路径加强机制可显著提高数据传输的速率；周期性路由：能量的均衡消耗；缺点周期性的洪泛机制---能量和时间开销都比较大；节点需要维护一个兴趣消息列表，代价较大；结论以数据为中心，适合大规模量数据的查询采集SPIN（1）SPIN协议是对Flooding协议的改进。Flooding的缺点：内爆：节点向邻居节点转发数据包，不管其是否收到过相同的重叠：感知节点感知区域有重叠，导致数据冗余SPIN（2）通过和邻居节点的协商来减少Flooding带来的内爆和重叠的影响通过元数据来完成协商过程元数据：一种对源数据的映射，比源数据短避免传输冗余数据3步握手协议(ADV-REQ-DATA)SPIN-2在SPIN-1的基础上加入了能量阈值当一个节点的剩余能量低于能量阈值后，减少其在协议中参与的活动。SPIN（3）协商通过元数据进行元数据描述实数据元数据与时数据一一对应协议消息消息广播包：Advertise(ADV)数据请求包：Request(REQ)数据包：Datatransfer(DATA)3步握手协议节点A有新数据，通过ADV发布新数据信息，使用元数据B节点收到ADV后，发现自己没有该数据，通过REQ向A请求新数据A节点向B节点传送源数据B节点融合新数据，并通过ADV发布新数据消息如果节点ADV中描述的数据的副本就忽略该消息SPIN协议评价优点部分解决了内爆和重叠问题不需要进行路由维护对网络拓扑变化不敏感，可用于移动WSN缺点本质上SPIN还是向全网扩散新消息，开销比较大地理路由:GPSR路由（1）贪婪算法利用节点的地理位置信息转发节点选取：•选择邻居节点中离数据包目的节点更近的点作为转发节点局部优化问题存在x到D的路径x的邻居w,y离D的距离比x大解决方法：边界转发边界转发平面图：二维空间结构；平面图中任意两条边都不相交；GPSR算法中构造平面图的方法是删除网络拓扑图中交叉的边算法：RNG(RelativeNeighborhoodGraph)GG(GabrielGraph)RNG节点u，v之间存在边的条件是对于任意一个节点w，u到v的距离要小于或等于u到w或是v到w的距离的最大值，用下式表示：)],(),,(max[),(:,wvdwudvudvuwGG节点u，v之间存在边的条件是在以d(u，v)为直径的圆中没有其它节点，用下式表示：)],(),([),(:,222wvdwudvudvuw边界转发时的右手法则一个数据分组从节点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网络；缺点需要地理位置信息的支持；需要维护邻居节点位置信息；GPSRFAMILYGRA（GeographicalRoutingAlgorithm)：发生局部优化问题时通过泛洪查找到目的节点的路由f-GEDIR(f表示泛洪)和c-GEDIR：发生局部优化问题，采用尽最大努力发送的方式：f-GEDIR：向所有邻节点广播该分组c-GEDIR：选择部分邻节点转发该分组收到数据包的节点继续使用GPSR协议转发该数据分组2-hopGEDIR：节点保存一跳和两跳范围邻居节点的位置信息常用的贪婪策略MFR(MostForwardwithinRadius)：使到目的节点的跳数最少NFP(NearestwithForwardProgress)：使节点之间干扰最少CR(CompassRouting)：减小数据传输范围地理路由:GEAR路由（2）应用到特定区域的路由前提已知目标区域的位置信息节点知道自己位置信息和剩余能量节点间无线链路是对称的GEAR路由的基本思想两步路由将查询命令传输到查询区域查询区域内传输到所有节点选路依据节点到查询区域通信能量能耗节点本身的剩余能量GEAR路由过程查询命令传送到目标区域估计代价代替实际代价节点到达指定区域的代价贪婪算法－选择邻居数据传输数据捎带技术实际代价查询命令的路由GEAR路由查询在监测区域内传送洪泛方式迭代地理转发将目标区域分解为若干子区域向子区域的中心位置转发实际阀值GEAR路由：路由空洞路由空洞贪婪算法-局部信息解决办法：节点拥有相邻两条节点的地理位置信息GEAR路由评价优点利用了位置信息，避免了查询消息的Flooding；考虑了消耗的能量和节点剩余能量，均衡消息；路径选择可达到局部最优；迭代地理转发对洪泛机制的补充；缺点可能出现路由空洞（局部信息）-两跳信息；结论适合移动性不强的应用；多路径路由（1）建立基础节点数量多；使用目的提高数据传输的可靠性（同时传送多个路径）实现网络负载平衡（概率选择一条路径）使用方式在多条路径上传送相同的数据；在多条路径上选择一条路径，传送一份数据；多路径路由（2）思想主动建立一条主路径和多条备用路径（避免洪泛维护路径）；多条路径可以同时使用，也可使用一条；仅使用一条：Sink节点决定哪一条路径；（不相交多路径）每个节点决定下一跳节点；（相交多路径）多路径的种类相交多路径不相交多路径多路径路由-不相交多路径（3）不相交多路径主路径：DD方式次路径：增强消息〈-〉应答消息从汇聚节点开始多路径路由-缠绕多路径（4）目的克服主路径上