无线传感器网络课件第章无线传感器网络的路由协议PPT课件.ppt

第4章 无线传感器网络的路由协议 1 2020 3 18 路由协议 路由协议是WSN的关键技术之一 它负责将数据分组从源节点通过网络转发到目的节点主要包括两个方面的功能 寻找源节点和目的节点的优化路径将数据分组沿着优化路径正确转发 与有线网络和蜂窝式无线网络不同 WSN中没有基础设施和全网统一的控制中心在这种无中心的环境下 路由可以看成分布式地获取网络拓扑信息 以一定准则计算路径并对路径进行维护的过程 2020 3 18 2 WSN的特点及对路由设计的影响 WSN的网络特点是路由设计的主要依据 对网络特点的分析是进行协议设计的前提 无线传感网络中 网络业务的最大特点是具有明显的方向性 为了实现信息采集的目的 WSN的网络业务大都发生在数据汇聚节点 sink 和普通的传感器节点之间 包括sink节点到传感器节点的下行业务 如查询指令下达 和传感器节点到sink的上行业务 如采集信息的回传 传感器节点之间的横向业务所占比例较小 主要是网络的控制信息和网内信息处理所需要的信息 无线传感器网络的一个基本理念是以大量低成本节点组网 通过节点之间的协作获得比单一的高精度 高可靠性和高成本的传感器更好的信息采集效果 单个传感器低能量和不可靠是无线传感器网络固有的 将对协议设计产生较大影响 2020 3 18 3 从对路由协议设计影响的角度 归纳WSN的特点 1 形式多样的信息报告模式WSN中信息报告模式分三类 a 事件触发 节点采集信息后判断 若超过一定的阈值 则认为发生了某种事件 需要立即上报 如用于预警的WSNb 周期的 节点定期把采集到的信息报告给sink 如野生动植物和环境监测WSNc 基于查询 node不主动向sink上报采集到的信息 而是等待用户查询 根据用户需要反馈信息 d 混合模式 前三种的综合 如智能交通的WSN 不同的信息报告模式影响路由的触发机制a 事件触发模式 从节能的角度 按需建立路由更恰当b 周期报告模式 采用先应式的方法建立路由更加合适c 基于查询模式 查询信息的本身就可以辅助建立路由 2020 3 18 4 2 多对一和一对多为主的业务模式WSN的主要业务是传感器节点把采集到的信息传给sink和sink向WSN下达查询命令 这是典型的多对一和一对多的模式 为了支持这种通信模式 WSN中很多路由协议建立具有树状结构的路由 2020 3 18 5 3 数据为中心的设计理念把WSN看成是一个大型的数据库 用户关心的是从这里得到什么信息 而不关心数据库中的哪个元素 node 提供了该信息 该理念对网络层的一个重要影响是节点的地址分配一般情况下没必要为每个node分配全局唯一地址 node描述信息产生时间 地点和内容即可 统一编址 对大规模WSN开销过大特定情况 节点ID和位置具有一定绑定关系 可用ID代替位置 如工业检测WSN从实现多跳通信的角度 需要在局部标识不同的节点 该理念还影响分组转发的过程WSN中 原始数据可能存在一定的冗余 在满足信息采集的要求前提下 可以在数据转发过程中对其进行修改 甚至把多个分组合并成一个分组 从而降低能耗 2020 3 18 6 4 动态变化的网络拓扑大部分的WSN中节点并不移动 造成网络拓扑变化的主要原因是节点的失效和存在不可靠性 非对称链路 为了节能和延长网络寿命 需要对网络进行休眠调度 会在一定程度上增加网络拓扑的动态性 在有些WSN中为了弥补节点失效造成的性能损失 进行再布设 re deployment 也会使网络拓扑发生变化 有些WSN中的节点是可移动的 如医疗监测WSN 候鸟迁徙WSN 网络拓扑变化比较快 2020 3 18 7 5 能量受限 结构简单的节点Node大都由电池供电 电池体积小 能量有限且难以更换许多场合需要WSN连续工作数年甚至更长 Node结构简单 存储 处理 通信能力低 单个节点可靠性差 要求协议尽可能简单 具有容错性 6 密集布设的大规模网络WSN通常密集布设大量节点 节点数量达到成千甚至上万 同时节点的密度也很高 有的情况下可以达到20个 m 这些使得协议的可扩展性变得十分重要 2020 3 18 8 1 能量有效性提高能量有效性是WSN从硬件设计到软件开发都必须考虑的问题 从路由协议设计的角度有两种思路提高能量有效性 a 节能 寻找节能路由 减少路由建立和维护的控制开销 提高路由可靠性b 能耗均衡 从空间上调度能量资源 使网络中节点能量均衡消耗 路由协议的关键问题分析 2 可扩展性可扩展性是指网络的性能不随着网络中节点的数量增加而有明显的下降两类重要策略 a 分层路由 网络分成若干层 低一层的群首构成高一层的网络 节点地位不同 首为局部控制中心 负责群内路由 信道接入 休眠调度等 大多数节点作为群成员其操作相对简单 控制开销较低b 地理路由 地理位置信息实际上体现节点间相对拓扑关系 利用这一信息路由能很大程度上降低用于收集拓扑信息付出的开销 提高协议的可扩展性地理路由使用的前提是节点能获得自己和目的节点的地理位置信息对于节点有移动性 任意两个节点之间都可能进行通信的网络 为获得目的节点位置信息需不断更新位置信息 开销较大 地理路由的优势就不明显 2020 3 18 9 3 数据传输可靠性数据传输的可靠性直接关系到WSN是否能给用户提供准确 全面和可靠的信息 而WSN中节点无线通信能力弱 应用环境复杂 实际的链路质量比较低 如何保证数据传输的可靠性是WSN路由设计中的一个关键问题影响WSN数据传输可靠性原因 a 无线信道上的碰撞导致分组无法正确接收b 节点故障使路由不可用 导致分组丢失c 链路不可靠 导致分组传输出错或丢失 路由协议的解决策略 a 建立多路径路由 建立信源节点到目标节点的多条路径 选择最优路径作为主路径 其他路径为备份 使用多条路径发送原始分组的多个副本 即使其中一些传输丢失也不会影响端到端的可靠性b 选择可靠链路 2020 3 18 10 几十种WSN路由协议 未统一分类标准一种分类方法 5类 路由协议的分类 1 基于聚簇的路由协议LEACH PEGASIS TEEN等 2 基于地理位置的路由协议基于地理位置的距离贪心路由协议 基于地理位置的角度贪心路由协议 GEM MAP LCR等 3 以数据为中心的路由协议Flooding SPIN DD Rumor routing TTDD 支持查询的近似路由算法等 4 能量感知路由协议Energyawarerouting GEAR 等 5 容错路由协议建立多条路径 重复传输数据包 基于编码的机会路由协议 MORE 等 2020 3 18 11 以数据为中心 泛洪路由 Flooding 扩散法 Flooding 是一种传统的网络路由协议 不需要知道网络拓扑结构和使用任何路由算法 协议内容 一节点S希望发送一块数据给节点D 节点S首先通过网络将数据副本传送给它的每一个邻居节点 每一个邻居节点又将其传输给各自的每一个邻居节点 除了刚刚给它们发送数据副本的节点S外 如此继续下去 直到将数据传输到目标节点D为止或者为该数据所设定的生命期限 在传感器网络里面通常定义为最大跳数 变为零为止或者所有节点拥有此数据副本为止 2020 3 18 12 洪泛路由 Flooding 的优点 实现简单 不需要为保持网络拓扑信息和实现复杂的路由发现算法而消耗计算资源 适用于健壮性要求高的场合 洪泛路由 Flooding 的不足 存在信息爆炸 Implosion 问题 即出现一个节点可能得到一个数据多个副本的现象 出现部分重叠 Overlap 现象 如果处于同一观测环境的两个相邻同类传感器节点同时对一个事件作出反应 二者采集的数据性质相同 数值相近 那么 这两个节点的邻居节点将收到双份数据副本 盲目使用资源 即扩散法不考虑各节点能量可用状况因而无法作出相应的自适应路由选择 洪泛路由 Flooding 的应用情况 网络资源过于浪费 实际很少直接采用 具有极好的健壮性 可用于军事应用 作为衡量标准评价其它路由算法 2020 3 18 13 SPIN协议 sensorprotocolforinformationvianegotiation SPIN是最早的以数据为中心的自适应路由协议 通过协商机制来解决洪泛算法中的 内爆 和 重叠 问题 节省了能量的消耗 a 为了避免出现扩散法的信息爆炸问题和部分重叠现象 传感器节点在传送数据之前彼此进行协商 协商制度可确保传输有用数据b 节点间通过发送元数据 即描述传感器节点采集的数据属性的数据 meta data 而不是采集的整个数据进行协商 由于元数据大小小于采集的数据 所以 传输元数据消耗的能量相对较少 为避免盲目使用资源 所有传感器节点必须监控各自的能量变化情况 2020 3 18 14 c 在传输或接收数据之前 每个节点都必须检查各自可用的能量状况 如果处于低能量水平 必须中断一些操作 比如充当路由器的角色 停止对其他节点的一些数据转发操作 d SPIN有3种数据包类型 即ADV REQ和DATA 节点用ADV宣布有数据发送 用REQ请求希望接收数据 用DATA封装数据ADV 用于新数据广播 当一个节点有数据可共享时 它可用ADV数据包 包含元数据 对外广播REQ 用于请求发送数据 当一个节点希望接收DATA数据包时 发送REQ数据包DATA 包含附上元数据头 meta dataheader 的传感器采集的数据的数据包 2020 3 18 15 SPIN PP采用点到点的通信模式 并假定两节点间的通信不受其他节点的干扰 分组不会丢失 功率没有任何限制 1 在发送一个DATA数据包之前 一个传感器节点首先对向邻居节点广播ADV数据包 2 如果一个邻居节点在收到ADV后有意愿接收该DATA数据包 那么它向该节点发送一个REQ数据包 接着节点向该邻居节点发送DATA数据包 3 类似地进行下去 DATA数据包可被传输到远方汇节点或基站 2020 3 18 16 SPIN协议的优点 1 小ADV消息减轻了内爆问题 2 通过数据命名解决了交叠问题 3 节点根据自身资源和应用信息决定是否进行ADV通告 避免了资源利用盲目问题 有效地节约了能量 SPIN协议的不足 在传输新数据的过程中 直接向邻居节点广播ADV数据包 而没有考虑其所有邻居节点由于自身能量的原因 不愿承担起转发新数据的功能 则新数据无法传输 将会出现 数据盲点 进而影响整个网络信息的收集 2020 3 18 17 DD DirectedDiffusion 定向扩散路由协议 DirectedDiffusion是一种以数据为中心的路由协议 与已有的路由协议有着截然不同的实现机制 其突出特点是引入了梯度来描述网络中间节点对该方向继续搜索获得匹配数据的可能性 2020 3 18 18 DD协议内容 节点用一组来命名它所生成的数据 1 建立路由时 sink节点flooding包含属性列表 上报间隔 持续时间 地理区域等信息的查询请求Interest 该过程本质上是设置一个监测任务 通过分配不同属性值来表示不同任务的描述符 2 每个传感器节点在收到嗜好 Interest 后保存在各自的Cache中 每个嗜好项 interestentry 包含一个时间标签域 timestampfield 和若干个梯度域 gradientfield 按成本最小化和能量自适应原则引导数据扩散的方向 3 当一个嗜好传遍整个网络后 从源节点 即嗜好所在区域的传感器节点 到sink节点或基站之间的梯度就建立起来了 4 一旦源节点采集到嗜好所需的数据 那么源节点沿着该嗜好的梯度路径传输数据到sink节点或基站 其中 源节点采集的数据首先在本地采用数据融合技术进行整合 然后在网上传输 右图描述DD路由协议的工作原理 2020 3 18 19 在DirectedDiffusion中 可以对路径进行修复 在建立多条数据源到Sink节点的路径之后 Sink节点可以选择增强其中的一条路径用于数据的传输 而同时保持另外一条低速数据传输的路径 当高速路径 也就是经过增强的路径出现故障时 Sink节点可以增强低速路径 保证源节点到Sink节点的数据传输 虽然保持低速路径的过程需要消耗一些能量 但是在故障时 可以节省很多能量开销 对于故障比较频繁的网络 保持一条低速路径是很有好处的 DD与SPIN的最大区别 DD采用基于需求的数据查询机制 在DD中 由Sink节点发出数据查询请求 而在SPIN中 节点广播自己的数据 以允许其他节点来查询 DD路由协议的优点 1 采用多路径 健壮性好 2 节点只需要和邻居节点通信 因而不需要全局的地址机制 使用查询驱动机制按需建立路由 避免了保存全网信息 3 每个节点都可以进行数据融合操作 能减少数据通信量 节省能量消耗 4 sink点根据实际情况采取增强或减弱方式能有效利用能量 5 节点不需要维护网络的拓扑结构 数据的发送是基于需求的 因此它是一个非常节能的路由协议 DD路由协议的优点 1 基于查询驱动模型的 不适用于环境监测的WSN 2 Gradient的建立开销很大 不适合多sink点网络 3 数据聚合过程采用时间同步技术 会带来较大开销和时延 4 不同的应用中需要定义不同的命名方案 也就是对 从而限制了它的应用 2020 3 18 20 Rumor路由协议 谣传路由 RumorRouting是在DirectedDiffusion的基础上演化而来的 通常情况下 DirectedDiffusion协议需要向整个网络广播兴趣 而在某些应用中 只有少量的数据需要从源节点传递到Sink节点 在这种情况下 没有必要向整个网络广播兴趣 当WSN中的事件 对应着数据的传递 数量很少 而查询 对应着兴趣的广播 数量很多的时候 可以采用广播事件的方法 以节省能量的消耗 RumorRouting是一个介于事件广播 向整个网络广播事件 和兴趣广播 向整个网络广播兴趣 之间的一种路由协议 RumorRouting核心思想 1 借鉴了欧氏平面图上任意两条曲线交叉几率很大的思想2 当节点监测到事件后将其保存 并创建称为Agent的生命周期较长的包括事件和源节点信息的数据包 将其按一条或多条随机路径在网络中转发3 收到Agent的节点根据事件和源节点信息建立反向路径 并将Agent再次随机发送到相邻节点 并可在再次发送前在Agent中增加其已知的事件信息4 sink点的查询请求也沿着一条随机路径转发 当两路径交叉时则路由建立5 如不交叉 sink点可flooding查询请求 2020 3 18 21 Rumor协议中Agent传播和Agent路径与查询路径的交叉 在多sink点 查询请求数目很大 网络事件很少的情况下 Rumor协议较为有效 但如果事件非常多 维护事件表和收发Agent带来的开销会很大 2020 3 18 22 基于聚簇的路由协议 LEACH Low EnergyAdaptiveClusteringHierarchy 路由协议 LEACH是一种基于聚类 Clustering 路由协议 在WSN路由协议占有重要地位 其他基于聚类的路由协议如TEEN APTEEN PEGASIS等大都由LEACH发展而来 LEACH路由协议的核心思想 1 LEACH协议分为两个阶段操作 即类准备阶段 set upphase 和就绪阶段 readyphase 为了使能耗最小化 就绪阶段持续的时间比类准备阶段长 类准备阶段和就绪阶段所持续的时间总和称为一轮 round 2 在类准备阶段 LEACH协议随机选择一个传感器节点作为类头节点 clusterheadnode 随机性确保类头与基站之间数据传输的高能耗成本均匀地分摊到所有传感器节点 3 具体的选择办法是 一个传感器节点随机选择0和1之间的一个值 如果选定的值小于某一个阈值T n 那么这个节点成为类头节点 T n 值按右边公式计算 N 网络中传感器节点的总数 p 一轮中网络的类头节点数 r 己完成的轮数 Gr 在剩余的N k r个回合中未成为类头节点的传感器节点组成的集合 2020 3 18 23 4 在类头节点选定后 该类头节点对网络中所有节点进行广播 广播数据包含有该节点成为类头节点的信息 一旦传感器节点收到广播数据包 根据接收到的各个类头节点广播信号强度 该节点选择信号强度最大的类头节点加入 向其发送成为其成员的数据包 类形成后 类头节点采用TDMA策略分配通道使用权给类内节点 5 一旦处于就绪阶段 类头节点开始接收类内各节点采集的数据 然后采用数据融合和数据压缩等技术进行汇聚 将整合后的数据传输给Sink节点 在就绪阶段持续了一段时间后 网络又进入了另一次的类准备阶段 LEACH路由协议模型 2020 3 18 24 LEACH协议的优点 随机选择簇头 平均分担路由业务 减小了能耗LEACH协议的不足 不适合大范围的应用 集群分组方式带来了额外开销以及覆盖问题 仅适用于每个节点在单位时间内需要发送的数据量基本相同的情况 而不适合突发数据通信 PEGASIS power efficientgatheringinsensorinformationsystem 协议PEGASIS由LEACH发展而来 它是LEACH协议的一种改进版本 仍然采用动态选举簇头的思想 但为避免频繁选举簇头的通信开销 采用无通信量的簇头选举方法 且网络中所有节点只形成一个簇 称为链 该协议要求每个节点都知道网络中其他节点的位置 通过贪心算法选择最近的邻节点形成链 动态选举簇头的方法 设网络中N个节点都用1 N的自然数编号 第j轮选取的簇头是第i个节点 i jmodN i为0时 取N 簇头与sink点一跳通信 利用令牌控制链两端数据沿链传送到簇头本身 在传送过程中可聚合数据 当链两端数据都传送完成时 开始新一轮选举与传输 2020 3 18 25 PEGASIS的基本原理 PEGAGIS假定组成网络的传感器节点是同构和静止的 节点发送能量递减的测试信号 通过检测应答来确定离自己最近的相邻节点 通过这种方式 网络中的所有节点能够了解彼此的位置关系 进而每个节点依据自己的位置选择所属的聚类 聚类的簇头参照位置关系优化计算出到sink节点的最佳链路 右图为PEGAGIS中的聚类由于节点了解彼此的位置信息 因而可以形成到簇头节点的最佳链路 图中 节点N1到N5都采集到相关的数据需要发送给簇头节点 节点N1可以将数据发送给N2 N2收到后将其与本身采集的数据进行数据融合操作 然后发送给N5 同样的N3将数据发送给N4 N4融合后将数据发送给N5 N5收到N2和N4的数据后 和自己的数据进行融合 然后发送给簇头 簇头然后将数据发送给Sink节点 2020 3 18 26 PEGASIS的优点 不需要周期性地动态选择簇头节点 采用最佳链路进行数据传输 并且采用数据融合技术减少了数据的发送和接收 因此 整个网络的功耗比LEACH要小很多 研究结果表明 PEGASIS支持的传感器网络的生命周期是LEACH的近两倍 PEGASIS的不足 1 节点维护位置信息 相当于传统网络中的拓扑信息 需要额外的资源 2 固定不变的簇头使得簇头成为关键点 其失效会导致路由失败 3 且要求节点都具有与sink点通信的能力 4 如果链过长 数据传输时延将会增大 不适合实时应用 5 成链算法要求节点知道其他节点位置 开销非常大 2020 3 18 27 TEEN thresholdsensitiveenergyefficientsensornetworkprotocol 协议 TEEN协议是一个层次路由协议 利用过滤方式来减少数据传输量 TEEN协议的基本