无线传感器网络技术概述路由协议lzy.pptx

《无线传感器网络技术概述路由协议lzy.pptx》由会员分享，可在线阅读，更多相关《无线传感器网络技术概述路由协议lzy.pptx（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录Internet路由机制概述传感器网络的路由概述经典传感器网络路由协议能量路由以数据为中心的路由：定向扩散路由、SPIN路由地理路由：GPSR路由、GEAR路由多路径路由：（不）相交多路径路由；总结第1页/共77页Internet 通信模式传统网络的通信模式:单播：点到点通信（主要方式）；组播：点到一组内的所有节点 都有相应的IP地址泛播：点到一组内的一个节点广播：点到网络内的所有节点第2页/共77页Internet路由机制概述传感器网络的路由概述经典传感器网络路由协议能量路由以数据为中心的路由：定向扩散路由、SPIN路由地理路由：GPSR路由、GEAR路由多路径路由：（不）相交多路径路由

2、；总结第3页/共77页传感器网络的通信模式传感器网络的通信模式点 多点（汇聚节点传感器节点）单播/广播（局部范围）传感器节点的标识节点ID没有位置的含义；通信关注的是：某个位置上或某种属性相关信息节点ID：不求全网唯一，局部唯一；邻居之间可相互区别；好处?不需要；节省能量；第4页/共77页路由协议的特点特点自组织的网络（随机部署）数据的冗余性（多节点监测同一事件）基于局部拓扑信息（硬件限制）通信模式（数据收集）不以IP为中心，数据为中心？（不知道目的节点的编号，甚至在哪个区域）关心的是：数据，事件/地点/时间；第5页/共77页路由协议的考虑有限能量供应、处理能力和通信带宽；可靠性；实时性；第6

3、页/共77页路由协议的要求传感器网络（Why现有协议不适合？）多跳的大规模网络；自组织的网络；网内数据融合处理的网络；节点少移动的网络；资源受限的网络；要求能量高效（协议简单|节省能量/均衡消耗）可扩展性（网络范围|节点密度）鲁棒性（节点变化|拓扑变化）快速收敛性第7页/共77页目录Internet路由机制概述传感器网络的路由概述经典传感器网络路由协议能量路由以数据为中心的路由：定向扩散路由、SPIN路由地理路由：GPSR路由、GEAR路由多路径路由：（不）相交多路径路由；总结第8页/共77页路由协议分类基于具体应用能量感知路由；基于查询的路由协议；地理位置路由协议可靠的路由协议；第9页/共7

4、7页能量感知路由:能量路由（1）能量路由：基于节点的可用能量（Power Available）或传输路径上链路的能量需求选择数据的发送路径 路径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；第10页/共77页能量感知路由:能量路由（2）最大PA路由：选取从数据源到汇聚点所有路径中节点PA之和最大的路径最小能量路由：选取从数据源到汇聚点所有路径中节点耗能之和最少的路径最小跳数路由：选取从数据源到汇聚点所有路径中跳数最小的路径最大最小P

5、A节点路由：选取从数据源到汇聚点所有路径中包含最小节点PA最大的路径第11页/共77页能量感知路由:能量路由（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 评价：全网信息理想路由第12页/共77页能量感知路由:能量路由（4）优点优先考虑WSN最关心：能量；最大PA路由：能量均衡消耗（路径）；最小能量路

6、由：能量最小消耗；最大最小PA节点路由：能量均衡消耗（节点）；缺点需要维护全网的拓扑信息和能量信息；结论理想路由；第13页/共77页能量感知路由:能量多路径路由（1）目标均衡消耗节点能量增加网络的 生存期。方法在源和目的之间建立多条路 径，根据能量因素给每条路径 赋予被选择使用的概率在发送数据时，基于概率随机 选择其中的一条路径结果没有一条路径一直在传送数 据，防止一条路径上节点能量 消耗过快第14页/共77页能量感知路由:能量多路径路由（2）三个阶段：路径建立阶段：根据能量代价建立源节点到目的节点的多条路径，并建立路由表；数据通信阶段或数据传播阶段：使用前阶段的信息，转发从源到目的节点的数据

7、。根据早期计算的能量消耗，基于概率地选择数据传播的路径；路由维护：通过不经常的从目的到源节点的洪泛查询，维持所有路径的活动性。路径建立阶段是最关键的一个阶段第15页/共77页能量感知路由:能量多路径路由（3）路径建立目的节点向邻居节点广播路径建立消息，发起路径建立过程中间节点：距离源节点更近同时距离目的节点更远的节点路径建立消息从节点Ni发送到节点Nj时本地路由表:节点Nj评价：多路经含义/目的第16页/共77页以数据为中心路由协议定向扩散路由（Direct Diffusion）SPIN(Sensor Protocol for Information via Negotiation)第17页/

8、共77页定向扩散路由（Direct Diffusion 1）Sink节点：通过兴趣消息发出查询任务；通过洪泛方式传播兴趣；节点：接收仅广播一次查询消息；网络：洪泛（Flooding）；查询：温度30度的区域第18页/共77页定向扩散路由（2）查询消息的传播建立数据的传输梯度汇聚节点发送查询消息兴趣消息：任务性质、数据采集/发送数率、时间戳等中间节点：记录（邻居节点和兴趣内容）数据发送的节点梯度转发 邻居节点梯度：表示了数据的传输方向第19页/共77页定向扩散路由（3）匹配数据的传输节点 邻居节点（发送interest）多个相同数据在网络中传递；路径：沿梯度发送给sink节点第20页/共77页定

9、向扩散路由（4）路径增强形成主路径How？兴趣：建立多条路径增强：建立主路径周期性Why？第21页/共77页定向扩散路由评价优点数据中心路由，定义不同任务类型/目标区域消息；路径加强机制可显著提高数据传输的速率；周期性路由：能量的均衡消耗；缺点周期性的洪泛机制-能量和时间开销都比较大；节点需要维护一个兴趣消息列表，代价较大；结论以数据为中心，适合大规模量数据的查询采集第22页/共77页SPIN（1）SPIN协议是对Flooding协议的改进。Flooding的缺点：内爆：节点向邻居节点转发数据包，不管其是否收到过相同的重叠：感知节点感知区域有重叠，导致数据冗余第23页/共77页SPIN（2）通

10、过和邻居节点的协商来减少Flooding带来的内爆和重叠的影响通过元数据来完成协商过程元数据：一种对源数据的映射，比源数据短避免传输冗余数据3步握手协议(ADV-REQ-DATA)SPIN-2在SPIN-1的基础上加入了能量阈值当一个节点的剩余能量低于能量阈值后，减少其在协议中参与的活动。第24页/共77页SPIN（3）协商通过元数据进行元数据描述实数据元数据与时数据一一对应协议消息消息广播包：Advertise(ADV)数据请求包：Request(REQ)数据包：Data transfer(DATA)第25页/共77页3步握手协议节点A有新数据，通过ADV发布新数据信息，使用元数据B节点收到

11、ADV后，发现自己没有该数据，通过REQ向A请求新数据A节点向B节点传送源数据B节点融合新数据，并通过ADV发布新数据消息如果节点ADV中描述的数据的副本就忽略该消息第26页/共77页SPIN协议评价n优点部分解决了内爆和重叠问题不需要进行路由维护对网络拓扑变化不敏感，可用于移动WSNn缺点本质上SPIN还是向全网扩散新消息，开销比较大第27页/共77页地理路由:GPSR路由（1）贪婪算法利用节点的地理位置信息转发节点选取：选择邻居节点中离数据包目的节点更近的点作为转发节点第28页/共77页局部优化问题存在x到D的路径x的邻居w,y离D的距离比x大解决方法：边界转发第29页/共77页边界转发平

12、面图：二维空间结构；平面图中任意两条边都不相交；GPSR算法中构造平面图的方法是删除网络拓扑图中交叉的边 算法：RNG(Relative Neighborhood Graph)GG(Gabriel Graph)第30页/共77页RNG节点u，v之间存在边的条件是对于任意一个节点w，u到v的距离要小于或等于u到w或是v到w的距离的最大值，用下式表示：第31页/共77页GG节点u，v之间存在边的条件是在以d(u，v)为直径的圆中没有其它节点，用下式表示：第32页/共77页边界转发时的右手法则一个数据分组从节点y到达节点x；下一条边的选择：下一边是以x为定点，沿(x，y)逆时针方向上的第一条边，图中

13、为(x，z)后续各边同样依次法则确定 第33页/共77页Facen平面图的边将整个图分成许多小的互补重叠的有界多边形和一些无界区域，这些有界多边形和无界区域统称为face。其中，有界区域称为内部face，无界区域称为外部face。途中xD通过3个有界face和一个无界face。第34页/共77页边界转发数据包在x点进入边界转发模式，通过face边界向目的节点D转发，这些face都被xD穿越；转发边的选择采用右手法则，初始边为xD；数据包在同一个face中转发时采用右手法则，当碰到与xD相交的边时，进行face切换，进入下一个face；第35页/共77页GPSR协议评价n优点采用局部最优的贪婪算

14、法，不需要维护网络拓扑，路由开销小；可适用于静态和移动的WSN网络；n缺点需要地理位置信息的支持；需要维护邻居节点位置信息；第36页/共77页GPSR FamilynGRA（Geographical Routing Algorithm)：发生局部优化问题时通过泛洪查找到目的节点的路由nf-GEDIR(f表示泛洪)和c-GEDIR：发生局部优化问题，采用尽最大努力发送的方式：nf-GEDIR：向所有邻节点广播该分组 nc-GEDIR：选择部分邻节点转发该分组 收到数据包的节点继续使用GPSR协议转发该数据分组n2-hop GEDIR：节点保存一跳和两跳范围邻居节点的位置信息 第37页/共77页常

15、用的贪婪策略nMFR(Most Forward within Radius)：使到目的节点的跳数最少nNFP(Nearest with Forward Progress)：使节点之间干扰最少nCR(Compass Routing)：减小数据传输范围第38页/共77页地理路由:GEAR路由（2）应用到特定区域的路由前提已知目标区域的位置信息节点知道自己位置信息和剩余能量节点间无线链路是对称的第39页/共77页GEAR路由的基本思想两步路由将查询命令传输到查询区域查询区域内传输到所有节点选路依据节点到查询区域通信能量能耗节点本身的剩余能量第40页/共77页GEAR路由过程查询命令传送到目标区域估计

16、代价代替实际代价节点到达指定区域的代价贪婪算法选择邻居数据传输数据捎带技术实际代价查询命令的路由第41页/共77页GEAR路由查询在监测区域内传送洪泛方式迭代地理转发将目标区域分解为若干子区域向子区域的中心位置转发实际阀值第42页/共77页GEAR路由：路由空洞路由空洞贪婪算法-局部信息解决办法：节点拥有相邻两条节点的地理位置信息第43页/共77页GEAR路由评价优点利用了位置信息，避免了查询消息的Flooding；考虑了消耗的能量和节点剩余能量，均衡消息；路径选择可达到局部最优；迭代地理转发对洪泛机制的补充；缺点可能出现路由空洞（局部信息）-两跳信息；结论适合移动性不强的应用；第44页/共7

17、7页多路径路由（1）建立基础节点数量多；使用目的提高数据传输的可靠性（同时传送多个路径）实现网络负载平衡（概率选择一条路径）使用方式在多条路径上传送相同的数据；在多条路径上选择一条路径，传送一份数据；第45页/共77页多路径路由（2）思想主动建立一条主路径和多条备用路径（避免洪泛维护路径）；多条路径可以同时使用，也可使用一条；仅使用一条：Sink节点决定哪一条路径；（不相交多路径）每个节点决定下一跳节点；（相交多路径）多路径的种类相交多路径不相交多路径第46页/共77页多路径路由-不相交多路径（3）不相交多路径主路径：DD方式次路径：增强消息-应答消息从汇聚节点开始第47页/共77页多路径路由

18、-缠绕多路径（4）目的克服主路径上单个节点失败问题；缠绕路径对于主路径上的任意一个节点，在网络不包括该节点时，从源节点到目的节点的最优路径；缠绕多路径主路径上每个节点都有对应的缠绕路径，这些缠绕路径构成一组备用路径，称为缠绕多路径；第48页/共77页多路径路由-缠绕多路径（5）缠绕多路径形成过程主路径上每个节点，假设它的下一跳节点失效，形成最优路径，直到节点在主路经上为止；如果不到主路径？第49页/共77页多路径路由-评价（6）优点主动建立备用路径；失效时及时更新，或随机选择一条可用路径；在可靠性、能量均衡性和实时性等方面提供支持避免了洪泛路径维护增加存储开销计算开销第50页/共77页集群结构

19、路由协议LEACH:Low-Energy Adaptive ClusteringHierarchy第51页/共77页LEACH算法每个节点直接和Sink节点通信：节点能量消耗过大节点密度较大时冲突过大，效率低LEACH算法：簇头节点作为一定区域所有节点的代理，负责和Sink的通信；非簇头节点可以使用小功率和簇头节点通信；簇头节点可以对所辖区域节点数据进行融合，减少网络中传输的数据；簇头选举算法的设计，要求保证公平性第52页/共77页簇头选择算法每个传感器节点选择0，1之间的一个随机数，如果选定的值小于某一个阈值，那么这个节点成为簇头节点，计算如下：N表示网络中传感器节点的个数，k为一个网络中的

20、簇头节点数，r为已完成的回合数，G为网络生存期总的回合数。第53页/共77页LEACH算法网络按照周期工作，每个周期分为两个阶段：簇头建立阶段：节点运行算法，确定本次自己是否成为簇头；簇头节点广播自己成为簇头的事实；其他非簇头节点按照信号强弱选择应该加入的簇头，并通知该簇头节点；簇头节点按照TDMA的调度，给依附于他的节点分配时间片；数据传输阶段：节点在分配给他的时间片上发送数据；第54页/共77页LEACH算法评价优点优化了传输数据所需能量；优化了网络中的数据量；缺点节点硬件需要支持射频功率自适应调整；无法保证簇头节点能遍及整个网络；第55页/共77页LEACH FamilyLEACH-c：

21、簇头由Sink节点指定；通过模拟退火算法选择簇头；PEGASIS：将网络中所有节点连成一条线；每次只有一个簇头节点负责和Sink的通信，簇头在链上移动；第56页/共77页集群结构路由协议TTDD:A Two-tier Data Dissemination Model for Large-scale Wireless Sensor Networks第57页/共77页TTDD传感器节点不移动，Sink节点移动；多Sink；以源节点为中心建立格状网；运用代理，实现对移动Sink的透明传输；Sink通过泛洪查找感兴趣的事件，泛红区域限定在一个网格区间；第58页/共77页格状网的建立源节点B的坐标(x,

22、y)；网格的边长为B建立的格状网的交叉点坐标为B为中心建立网络的转发点选择与交叉点最近的点，如图中黑点成为转发节点的点启动下一级转发节点的选取过程第59页/共77页格状网建立时的上下游关系上游节点转发节点在格状网建立阶段由源节点或者其它转发节点指定，这个指定本转发节点的源节点或者转发节点称为本转发节点的上游节点 下游节点和上游节点的定义相反第60页/共77页查询过程所有的转发节点都包含有源节点的数据公告消息Sink通过泛洪方式发起查询请求，查询范围是一个网格区间匹配节点通过格状网建立时的上下游关系将查询传送到源节点源节点响应查询，沿查询消息的反向传输路径传送数据第61页/共77页对移动Sink

23、的支持直接转发节点第一个响应Sink查询的格状网中的转发节点初级代理(PA)Sink节点指定的一个节点，负责接收直接转发节点发送过来的数据直接代理(IA)Sink节点移动时动态指定IA，PA将数据传送给IA，由IA将数据提交给Sink。PA和IA可以是同一个节点。当Sink移出距离太远，找不到IA时，Sink重新发起查询过程。第62页/共77页TTDD路由协议评价优点提出了一种新的应用场景 支持多Sink以及Sink移动的网络环境缺点需要地理位置信息的支持网格大小不容易确定第63页/共77页一种平衡网路能量和负载的协议n需要解决的问题多源单汇数据流远远大于控制流离汇聚节点近能量消耗快需要解决流

24、量和能量的均衡问题第64页/共77页一种平衡网路能量和负载的协议n提出的方法汇聚节点移动B为Sink节点,Rm为其移动圆形轨迹半径，R为网络半径，最好RmRl最优移动策略Sink节点在网络外边界移动，左图为圆形网络模型，灰色区域是Sink节点移动区域。第65页/共77页一种平衡网路能量和负载的协议n路由方法最好是取一个和Sink移动区节点数据Sink移动区外节点数据数据沿着以O为中心的环转发，直到该数据包到达OB(B为节点Sink所在的位置)线附近的一个节点，到达该节点后再沿着OB，采用最短路径算法到达Sink节点。直接采用最短路径路由算法到达Sink节点。第66页/共77页一种平衡网路能量和

25、负载的协议n优点 提出了一种新思路，通过Sink移动的方式从一定程度上削弱了网络中能耗和负载不平衡的现象n缺点 大多数应用背景下要求Sink节点固定；普通节点定位Sink节点的问题不能很好的解决；第67页/共77页一种跨层设计路由协议n网络协议软件设计方法分层设计比较成熟的方法，比如TCP/IP。分层的设计方法使协议设计规范化，但是效率不高。跨层设计不成熟，设计复杂，但是效率高，系统优化性能强。传输控制层物理层网络层数据链路层应用层第68页/共77页一种跨层设计路由协议n方法传感器采样事件(S，Sample)节点接收数据事件(R，Receive)节点发送数据事件(T，Transmit)每个节点

26、在事件发生时醒来工作，其他时间休眠第69页/共77页一种跨层设计路由协议n时间片分配约束时间片的分配保证相邻节点的R与T事件互相配合。时间片调度要避免冲突6号节点接收事件与其邻居节点4和9的发送事件时刻匹配4号节点在发送数据时，其邻居节点2和5都不能接收(会发生隐终端的问题)和发送数据(会引起数据冲突)R与T的匹配自动建立路径第70页/共77页一种跨层设计路由协议n优点 无需路由维护，网络开销小；节点休眠，节省了能量；n缺点 需要比较精确的节点同步；对拓扑变化敏感，不能快速调整节点的时间片调度；第71页/共77页路由协议分类原则分类原则界限明确共有的特性不作为分类依据，如数据为中心的特点不同类

27、别间没有重叠避免过细从多个视角去观察路由协议，采用多种分类方法尽量避免每个类别中只有一、两个协议向后兼容不采用容易被折中的特性作为分类依据，比如延迟、公平性等第72页/共77页路由协议分类方法根据协议的宏观特性，可有多种分类方法：依据网络结构平坦型(flat)和层次型(hierarchical)依据执行位置集中式(centralized)和分布式(distributed)依据路径数目单路径(single-path)和多路径(multi-path)根据协议的操作，可有多种分类方法：基于局部信息的和基于地理位置的proactive，reactive，hybrid第73页/共77页传感器网络路由协议的挑战Ad hoc deployment;Energy consumption without losing accuracy;Computation capabilities;Communication tolerance;Fault tolerance;Scalability;Control overhead;第74页/共77页WSN路由协议最新研究成果n一些解决办法路由协议专用性设计 跨层设计新技术开发（UWB等）第75页/共77页谢谢！第76页/共77页感谢您的观看。第77页/共77页