第章路由协议PPT课件.ppt

无线传感器网络技术 讲义 第二章 路由协议 2007年8月20日 内容提要 WSN路由协议概述WSN路由协议分类2 1以数据为中心路由协议2 2集群结构路由协议2 3地理信息路由协议2 4QOS路由协议WSN路由协议最新研究成果主要参考文献 内容提要 WSN路由协议概述WSN路由协议分类2 1以数据为中心路由协议2 2集群结构路由协议2 3地理信息路由协议2 4QOS路由协议WSN路由协议最新研究成果主要参考文献 WSN路由协议功能 定义WSN路由协议是一套将数据从源节点传输到目的节点的机制 设计目标满足应用需求低网络开销资源利用的整体有效性网络高吞吐率 WSN路由协议特点 特点自组织的网络 随机部署 数据的冗余性 多节点监测同一事件 基于局部拓扑信息 硬件限制 网络功能 数据收集 数据为中心 WSN路由协议要求 要求能量高效 协议简单 节省能量 均衡消耗 可扩展性 网络范围 节点密度 鲁棒性 节点变化 拓扑变化 快速收敛性 WSN路由协议关键技术 考虑网络和节点能量优化 硬件限制 具有高可扩展性 网络规模 自组织 适应强网络拓扑变化 节点移动 无线信道 传感器网络路由中使用数据融合技术 数据为中心 传感器网络中流量分布不对称 数据收集网络 多源单Sink 传感器网络路由协议的挑战 自组织布撒 Adhocdeployment 能量消耗 Energyconsumption 路由精度 Routingaccuracy 计算能力 Computationcapabilities 通信能力 Communicationtolerance 容错能力 Faulttolerance 可扩展性 Scalability 控制负载 Controloverhead 内容提要 WSN路由协议概述WSN路由协议分类2 1以数据为中心路由协议2 2集群结构路由协议2 3地理信息路由协议2 4QOS路由协议WSN路由协议最新研究成果主要参考文献 WSN路由协议分类 数据为中心路由协议SPIN Flooding DirectedDiffusion Gradient 集群结构的路由协议LEACH TTDD地理信息路由协议GPSR GEARQOS路由协议QOS路由协议 详见第十章 内容提要 WSN路由协议概述WSN路由协议分类2 1以数据为中心路由协议2 2集群结构路由协议2 3地理信息路由协议2 4QOS路由协议WSN路由协议最新研究成果主要参考文献 以数据为中心路由协议 SPIN SensorProtocolforInformationviaNegotiation SPIN SPIN协议是对Flooding协议的改进 Flooding的缺点 SPIN 通过和邻居节点的协商来减少Flooding带来的内爆和重叠的影响通过元数据来完成协商过程元数据 一种对源数据的映射 比源数据短避免传输冗余数据3步握手协议 ADV REQ DATA SPIN 2在SPIN 1的基础上加入了能量阈值当一个节点的剩余能量低于能量阈值后 减少其在协议中参与的活动 SPIN 协商通过元数据进行元数据描述实数据元数据与时数据一一对应协议消息消息广播包 Advertise ADV 数据请求包 Request REQ 数据包 Datatransfer DATA 3步握手协议 A A A A A A 节点A有新数据 通过ADV发布新数据信息 使用元数据B节点收到ADV后 发现自己没有该数据 通过REQ向A请求新数据A节点向B节点传送源数据B节点融合新数据 并通过ADV发布新数据消息如果节点ADV中描述的数据的副本就忽略该消息 SPIN协议评价 优点部分解决了内爆和重叠问题不需要进行路由维护对网络拓扑变化不敏感 可用于移动WSN缺点本质上SPIN还是向全网扩散新消息 开销比较大 SPIN协议族 ProtocolFamily SPIN PPFornetworksusingpoint to pointtransmissionmediaIdealconditionsassumedwithnopacketlossSPIN ECSPIN PPwithlowenergythresholdSPIN BC3 stagehandshakeprotocolforbroadcastmediaSPIN RLSPIN BCforLossynetworks 数据中心网络和地址中心网络 DC Data centric AC Address centric DC网络可进行数据融合 减少网络中的数据量 以数据为中心路由协议 DirectedDiffusion DirectedDiffusion Sink节点查询兴趣消息兴趣消息采用泛洪的方法传播到网络有和兴趣匹配数据的节点发送数据兴趣扩散阶段建立节点到Sink的路径兴趣的定义 由属性值对组成 type four leggedanimal detectanimallocationinterval 20ms sendbackeventsevery20msduration 10seconds forthenext10secondsrect 100 i00 200 400 fromsensorswithinrectangle 兴趣和梯度 Sink节点向全网查询兴趣M建立源节点和Sink间路径兴趣在全网中扩散对每一个活动任务 Sink周期进行查询邻居更新自己的兴趣cach 并且转发兴趣cach中的条目时间戳 指示接收到相关兴趣消息的最近时间若干梯度域 每个梯度和其邻居节点相关联每个梯度中含有一个指定的数据传输率持续时间 该兴趣消息的有效期 DirectedDiffusion 查询消息的传播 建立数据的传输梯度汇聚节点发送查询消息兴趣消息 任务性质 数据采集 发送数率 时间戳等中间节点 记录转发梯度 表示了数据的传输方向 路径修复问题 加强路径上的节点可以触发和启动路径的加强过程 DD协议评价 优点数据中心路由 定义不同任务类型 目标区域消息 路径加强机制可显著提高数据传输的速率 周期性路由 能量的均衡消耗 缺点周期性的洪泛机制 能量和时间开销都比较大 节点需要维护一个兴趣消息列表 代价较大 DirectedDiffusionFamily GBR路由 Gradient BasedRouting 协议 梯度域扩展 传感器节点到Sink节点的跳数信息 无线链路评估信息 EAR EnergyAwareRouting 路由协议建立路由过程中加入能量评估机制 路由路径的能量开销大于某一阈值不采用 CADR路由 ConstrainedAnisotropicDiffusionrouting 协议兴趣消息往指定方向发送 DirectedDiffusionFamily 谣传路由 基于代理 agent 消息的单播随机转发方法 内容提要 WSN路由协议概述WSN路由协议分类2 1以数据为中心路由协议2 2集群结构路由协议2 3地理信息路由协议2 4QOS路由协议WSN路由协议最新研究成果主要参考文献 集群结构路由协议 LEACH Low EnergyAdaptiveClusteringHierarchy LEACH算法 每个节点直接和Sink节点通信 节点能量消耗过大节点密度较大时冲突过大 效率低LEACH算法 簇头节点作为一定区域所有节点的代理 负责和Sink的通信 非簇头节点可以使用小功率和簇头节点通信 簇头节点可以对所辖区域节点数据进行融合 减少网络中传输的数据 簇头选举算法的设计 要求保证公平性 簇头选择算法 每个传感器节点选择 0 1 之间的一个随机数 如果选定的值小于某一个阈值 那么这个节点成为簇头节点 计算如下 N表示网络中传感器节点的个数 k为一个网络中的簇头节点数 r为已完成的回合数 G为网络生存期总的回合数 LEACH算法 网络按照周期工作 每个周期分为两个阶段 簇头建立阶段 节点运行算法 确定本次自己是否成为簇头 簇头节点广播自己成为簇头的事实 其他非簇头节点按照信号强弱选择应该加入的簇头 并通知该簇头节点 簇头节点按照TDMA的调度 给依附于他的节点分配时间片 数据传输阶段 节点在分配给他的时间片上发送数据 LEACH算法评价 优点优化了传输数据所需能量 优化了网络中的数据量 缺点节点硬件需要支持射频功率自适应调整 无法保证簇头节点能遍及整个网络 LEACHFamily LEACH c 簇头由Sink节点指定 通过模拟退火算法选择簇头 PEGASIS 将网络中所有节点连成一条线 每次只有一个簇头节点负责和Sink的通信 簇头在链上移动 集群结构路由协议 TTDD ATwo tierDataDisseminationModelforLarge scaleWirelessSensorNetworks TTDD 传感器节点不移动 Sink节点移动 多Sink 以源节点为中心建立格状网 运用代理 实现对移动Sink的透明传输 Sink通过泛洪查找感兴趣的事件 泛红区域限定在一个网格区间 格状网的建立 源节点B的坐标 x y 网格的边长为B建立的格状网的交叉点坐标为B为中心建立网络的转发点选择与交叉点最近的点 如图中黑点成为转发节点的点启动下一级转发节点的选取过程 格状网建立时的上下游关系 上游节点转发节点在格状网建立阶段由源节点或者其它转发节点指定 这个指定本转发节点的源节点或者转发节点称为本转发节点的上游节点下游节点和上游节点的定义相反 查询过程 所有的转发节点都包含有源节点的数据公告消息Sink通过泛洪方式发起查询请求 查询范围是一个网格区间匹配节点通过格状网建立时的上下游关系将查询传送到源节点源节点响应查询 沿查询消息的反向传输路径传送数据 对移动Sink的支持 直接转发节点第一个响应Sink查询的格状网中的转发节点初级代理 PA Sink节点指定的一个节点 负责接收直接转发节点发送过来的数据直接代理 IA Sink节点移动时动态指定IA PA将数据传送给IA 由IA将数据提交给Sink PA和IA可以是同一个节点 当Sink移出距离太远 找不到IA时 Sink重新发起查询过程 TTDD路由协议评价 优点提出了一种新的应用场景支持多Sink以及Sink移动的网络环境缺点需要地理位置信息的支持网格大小不容易确定 内容提要 WSN路由协议概述WSN路由协议分类2 1以数据为中心路由协议2 2集群结构路由协议2 3地理信息路由协议2 4QOS路由协议WSN路由协议最新研究成果主要参考文献 地理位置信息 地理位置信息路由协议要求每个节点知道自己在网络中的位置下列方法可确定节点位置GPS GlobalPositioningSystem 超声波三角定位系统标定用途作为其它路由算法的辅助直接用于路由的计算 地理位置信息路由协议 GPSR GreedyPerimeterStatelessRouting GPSR 贪婪算法利用节点的地理位置信息转发节点选取 选择邻居节点中离数据包目的节点更近的点作为转发节点 局部优化问题 存在x到D的路径x的邻居w y离D的距离比x大 解决方法 边界转发 边界转发 平面图 二维空间结构 平面图中任意两条边都不相交 GPSR算法中构造平面图的方法是删除网络拓扑图中交叉的边算法 RNG RelativeNeighborhoodGraph GG GabrielGraph 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网络 缺点需要地理位置信息的支持 需要维护邻居节点位置信息 GPSRFamily GRA GeographicalRoutingAlgorithm 发生局部优化问题时通过泛洪查找到目的节点的路由f GEDIR f表示泛洪 和c GEDIR 发生局部优化问题 采用尽最大努力发送的方式 f GEDIR 向所有邻节点广播该分组c GEDIR 选择部分邻节点转发该分组收到数据包的节点继续使用GPSR协议转发该数据分组2 hopGEDIR 节点保存一跳和两跳范围邻居节点的位置信息 常用的贪婪策略 MFR MostForwardwithinRadius 使到目的节点的跳数最少NFP NearestwithForwardProgress 使节点之间干扰最少CR CompassRouting 减小数据传输范围 地理位置信息路由协议 GEAR GeographicandEnergyAwareRouting 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路由过程 查询在监测区域内传送 洪泛方式 迭代地理转发将目标区域分解为若干子区域 向子区域的中心位置转发 路由空洞问题 路由空洞邻居节点传输代价都比本地节点大 选择邻居节点中代价最下的作为转发节点 修改本地节点的转发代价 F N R F Nmin R C N Nmin C N Nmin 表示将数据包从N传送到Nmin的代价 GEAR路由评价 优点利用了位置信息 避免了查询消息的Flooding 考虑了消耗的能量和节点剩余能量 均衡消息 路径选择可达到局部最优 迭代地理转发对洪泛机制的补充 缺点可能出现路由空洞 局部信息 两跳信息 不适合在移动WSN使用 内容提要 WSN路由协议概述WSN路由协议分类2 1以数据为中心路由协议2 2集群结构路由协议2 3地理信息路由协议2 4QOS路由协议WSN路由协议最新研究成果主要参考文献 WSN路由协议最新研究成果 现阶段WSN路由设计主要关注下面几个方面提高能量效率 实现网络负载的平衡 延长网络生存时间 满足各种应用场景的参数指标 也就是QOS 实现一定程度的数据安全性 后两条留待后面的章节介绍 WSN路由协议最新研究成果 一些解决办法路由协议专用性设计跨层设计新技术开发 UWB等 一种平衡网路能量和负载的路由协议 JointMobilityandRoutingforLifetimeElongationinWirelessSensorNetworks 一种平衡网路能量和负载的协议 需要解决的问题 多源单汇 数据流远远大于控制流 离汇聚节点近能量消耗快 需要解决流量和能量的均衡问题 一种平衡网路能量和负载的协议 提出的方法 最优移动策略Sink节点在网络外边界移动 左图为圆形网络模型 灰色区域是Sink节点移动区域 汇聚节点移动 B为Sink节点 Rm为其移动圆形轨迹半径 R为网络半径 最好Rm R 一种平衡网路能量和负载的协议 路由方法 最好是取一个和 Sink移动区节点数据 Sink移动区外节点数据 数据沿着以O为中心的环转发 直到该数据包到达OB B为节点Sink所在的位置 线附近的一个节点 到达该节点后再沿着OB 采用最短路径算法到达Sink节点 直接采用最短路径路由算法到达Sink节点 一种平衡网路能量和负载的协议 优点提出了一种新思路 通过Sink移动的方式从一定程度上削弱了网络中能耗和负载不平衡的现象缺点大多数应用背景下要求Sink节点固定 普通节点定位Sink节点的问题不能很好的解决 一种跨层设计路由协议 Cross LayerSchedulingforPowerEfficiencyinWirelessSensorNetworks 一种跨层设计路由协议 网络协议软件设计方法分层设计比较成熟的方法 比如TCP IP 分层的设计方法使协议设计规范化 但是效率不高 跨层设计不成熟 设计复杂 但是效率高 系统优化性能强 一种跨层设计路由协议 方法 每个节点在事件发生时醒来工作 其他时间休眠 一种跨层设计路由协议 时间片分配约束时间片的分配保证相邻节点的R与T事件互相配合 时间片调度要避免冲突 6号节点接收事件与其邻居节点4和9的发送事件时刻匹配 4号节点在发送数据时 其邻居节点2和5都不能接收 会发生隐终端的问题 和发送数据 会引起数据冲突 R与T的匹配自动建立路径 一种跨层设计路由协议 优点无需路由维护 网络开销小 节点休眠 节省了能量 缺点需要比较精确的节点同步 对拓扑变化敏感 不能快速调整节点的时间片调度 WSN路由协议未来的研究方向 传感器网络路由协议未来的研究方向 新型网络结构的提出 节点密集部署及空间多样性的考虑 网内存储及网内处理 时间和位置的同步 自组织与重配置 主动传感器网络 内容提要 WSN路由协议概述WSN路由协议分类2 1以数据为中心路由协议2 2集群结构路由协议2 3地理信息路由协议2 4QOS路由协议WSN路由协议最新研究成果主要参考文献 主要参考文献 1 唐勇 周明天 张欣 无线传感器网络路由协议研究进展 JournalofSoftware 2006 17 3 pp 410 421 2 郭午平 无线传感器网络的研究现状及发展 中国通信学会信息通信网络技术委员会2005年年会 3 JAMALN AL KARAKI THEHASHEMITEUNIVERSITYAHMEDE KAMAL IOWASTATEUNIVERSITY ROUTINGTECHNIQUESINWIRELESSSENSORNETWORKS ASURVEY IEEEWirelessCommunications 2004 11 6 pp 6 28 4 高传善 杨珉 毛迪林 无线传感器网络路由协议研究 世界科技研究与发展 2005 27 8 PP 1 8 5 W Heinzelman J Kulik andH Balakrishnan AdaptiveProtocolsforInformationDisseminationinWirelessSensorNetworks In Proc 5thACM IEEEMobicom Seattle WA Aug 1999 pp 174 85 6 S HedetniemiandA Liestman ASurveyofGossipingandbrocadcastinginCommunicationNetworks IEEENetwork 1988 18 4 pp 319 49 7 BhaskarKrishnamachari DeborahEstrin andStephenWicker ModellingData CentricRoutinginWirelessSensorNetworks DepartmentofElectricalEngineering SystemsUniversityofSouthernCaliforniaLosAngeles TechRep ComputerEngineeringTechnicalReportCENG02 14 8 C Intanagonwiwat R Govindan andD Estrin DirectedDiffusion aScalableandRobustCommunicationParadigmforSensorNetworks In Proc ACMMobi Com2000 Boston MA 2000 pp 56 67 9 C SchurgersandM B Srivastava EnergyEfficientRoutinginWirelessSensorNetworks MILCOMProc CommunforNetwork CentricOps CreatingtheInfo Force McLeanVA 2001 1 1 pp 357 361 主要参考文献 10 M Chu H Haussecker andF Zhao ScalableInformationDrivenSensorQueryingandRoutingforAdHocHeterogeneousSensorNetworks Int l J HighPerf Comp Apps 2002 16 3 pp 219 314 11 R C ShahandJ Rabaey EnergyAwareRoutingforLowEnergyAdHocSensorNetworks In IEEEWCNC Orlando FL 2002 pp 17 21 12 D BraginskyandD Estrin RumorRoutingAlgorithmforSensorNetworks In Proc 1stWksp SensorNetworksandApps Atlanta GA 2002 pp 22 31 13 WendiRabinerHeinzelman AnanthaChandrakasan andHariBalakrishnan Energy EfficientCommunicationProtocolforWirelessMicrosensorNetworks In Proceedingsofthe33rdHawaiiInternationalConferenceonSystemSciences Hawaii USA 2000 14 WendiRabinerHeinzelman AnanthaChandrakasan andHariBalakrishnan AnApplication specificprotocolarchitectureforwirelessmicosensornetworks IEEETransactiononWirelessCommunication 2002 1 4 pp 660 670 15 LindseyS RaghavendraCS PEGASIS Power efficientgatheringinsensorinformationsystems In Proc oftheIEEEAerospaceConf Montana IEEEAerospaceandElectronicSystemsSociety 2002 pp 1125 1130 16 A ManjeshwarandD P Agarwal TEEN aRoutingProtocolforEnhancedEfficiencyinWirelessSensorNetworks In 1stInt l Wksp onParallelandDistrib Comp IssuesinWirelessNetworksandMobileComp 2001 pp 2009 2015 17 A ManjeshwarandD P Agarwal APTEEN AHybridProtocolforEfficientRoutingandComprehensiveInformationRetrievalinWirelessSensorNetwork In ProcInt lParallelandDistribProcSymp Florida USA 2002 pp 195 202 18 HLUO FANYE JCHENG SLU LZHANG TTDD ATwo tierDataDisseminationModelforLargescaleWirelessSensorNetworks WirelessNetworks 2005 11 2 pp 161 175 主要参考文献 19 Young BaeKoandNitinH Vaidya Location AidedRouting LAR inmobileadhocnetworks ACM BaltzerWirelessNetworks WINET Journal 2000 6 4 pp 307 321 20 YaXu JohnHeidemann DeborahEstrin Geography informedEnergyConservationforAdHocRouting In ACMSI