（精选）专题3 无线传感器网络路由技术.ppt

WMIIPL,1,专题三：无线传感器网络路由技术,三、典型的路由协议,二、WSN节点能耗分析,一、WSN路由概述,四、无线传感器网络高可靠性路由,2020/5/22,电子科技大学自动化工程学院,2,一、WSN路由概述,WSN路由是把信息从源穿过网络传递到目的行为，包括选定最优路径和传输数据包两个部分,源节点,目的节点,1、低能耗路由的重要性,节点一般采用微型化设计并使用电池供电，很难提供充足的能量供给，如果大量节点因为能量耗尽而失效，那么网络的可用性将受到严重威胁在无线传感器网络各项技术中，最为核心的技术挑战是如何降低能耗、延长网络使用寿命,WMIIPL,3,低能耗成了几乎所有无线传感器网络技术的标准，从最底层的天线设计、到MAC协议、到时间同步和定位技术、到拓扑控制和路由技术，再到上层的数据存储与查询等，都涉及到合理高效的利用节点能量路由协议是无线传感器网络重要支撑技术之一，它负责源节点和目的节点之间的数据传输，是无线传感器网络数据交互的纽带，在传感器网络设计中占有重要地位。为了最大限度的节省能量，高能效的路由设计是减少能耗的根本保障，也是延长网络生命周期的重要手段。,WMIIPL,4,1、低能耗路由的重要性,2020/5/22,电子科技大学自动化工程学院,5,2、无线自组织路由协议需解决的问题,无线信道的不断变化、节点的移动、加入、退出等会引起网络拓扑结构的动态变化，这种环境不同于传统固定网络的路由协议，主要需解决以下问题：（1）高鲁棒性路由适应环境因素的动态变化，故障自恢复能力（2）高可靠性路由（3）节点能量最优化问题（节能）,（1）路由鲁棒性,将路由协议在其自身或外界因素摄动的情况下维持原有性能的能力称为鲁棒性为数据传输而设计的路由协议很多是在数据通信可靠的假设下设计的，而实际环境往往不能保证可靠通信无线传感器网络的特殊运行环境、特殊能量供给方式和组网模式使得网络很容易出现故障，一些可控(通信功率大小、天线方向等)及不可控(障碍、孤儿节点、移动等)因素的摄动都将可能导致数据传输性能的下降甚至系统崩溃。,WMIIPL,6,（1）路由鲁棒性,频繁变化的网络拓扑结构使网络中的传感器、感知对象和观察者这三要素都可能具有很大的不确定性，并且经常有新节点的加入或已有节点失效，这就要求无线传感器网络有能力处理这些不定因素带来的网络变化，并能迅速适应新的网络环境，防止网络性能下降给系统带来不利影响,WMIIPL,7,（1）路由鲁棒性,无线传感器网络必须能够承受间歇性的资源及通信失效，个别节点的失效不影响全局工作，即要求系统能够在不降低性能或者即使在较低性能下仍继续工作这就要求路由协议具有较高的鲁棒性，能够消除典型错误，保证网络信息的传输，达到网络高可用性和高可靠性的要求,WMIIPL,8,（2）高可靠性路由,在现有高可靠性路由设计中，普遍采用的是多路径(multi-path)路由方式，数据的多个拷贝沿着多条可能的路径同时传输多路径的多跳通信方式虽然在一定程度上提高了数据传输可靠性，但整个系统能量消耗比较大，能效较低，使得网络的生命周期减小。因此，数据通信的可靠性和能量的高效性两者往往是相互制约，在无线传感器网络路由设计中应努力寻求两者的最佳结合点，使网络以最低的能耗成本达到最满意的系统性能。,WMIIPL,9,高能效、高可靠性路由协议在无线传感器网络的发展中占有重要地位，也是近年来的一个研究热点,有限的节点能量决定了无线传感器网络进行数据传输、接收和处理的能力是有限的，这个能力用网络生命周期进行衡量。为了最大限度的延长网络生命周期，在无线传感器网络设计的各个层面上都必须贯穿高能效的设计理念不仅在节点的能耗设计上采用了低能耗策略，更在路由协议的设计上采取了一系列高能效的措施,WMIIPL,10,（3）节点能量最优化问题,3路由算法设计指标,路由算法设计指标,WMIIPL,11,最优化：选择最佳路径的能力简洁性：算法开销小，能量高效鲁棒性：自恢复能力快速收敛：算法速度灵活性：适应各种环境的能力,二、WSN节点能耗分析,节点主要由传感器模块、处理器模块和无线通信模块构成，随着微机电系统(MicroElectro-MechanicalSystems，MEMS)、集成制造技术的飞速发展，传感器和处理器模块的功耗变得很低，而主要的能耗点在无线通信模块,WMIIPL,12,无线通信模块划分了四个工作状态：发送、接收、空闲和休眠发送状态时能耗最大，而接收和空闲状态下能耗相当。,WMIIPL,13,降低能耗的措施,除了设计低功耗的无线通信模块和天线外，减少无线通信模块的能量损耗主要措施还有：采用多跳通信方式减少通信流量增加休眠时间功率控制,WMIIPL,14,采用多跳通信方式,通信模块的能耗很大程度取决于无线发射功率，在自由空间模型下，能耗与通信距离的关系为，E=dn。可见，随着通信距离的增加，能耗将成指数级急剧增加。因此，应该尽量减少单跳通信距离，增加传感器节点的部署密度，减小无线电覆盖范围，降低无线发射功率，最终达到节省能耗延长网络寿命的目的。多跳通信方式是无线传感器网络，特别是在大规模无线传感器网络普遍采用的方式。,WMIIPL,15,减少通信流量,除了无线发射功率外，数据传输、接收的时间跨度也是无线通信模块能耗的重要方面，因此，应尽量减少数据包不必要的转发和接收，不需要通讯时使节点尽快进入睡眠状态，特别是在路由算法中应尽量减少路由建立过程中的控制包数量。此外，减少冲突、增加错误校验和校正机制、减少控制包的开销、数据融合(Dataaggregation)等，也能有效地减少传输的报文数量和长度,WMIIPL,16,增加休眠时间,通信模块处于休眠状态时能耗最低，对于Mica2Mote，发送、接收、空闲和休眠状态下的能耗分别为81mw，30mw，30mw，0.003mw而即使处于没有数据传输的空闲状态下，节点也在不断的监听信道，在无线传感器网络中空闲状态的能耗也是惊人的。因此，当不需要通信时，应尽量使节点处于休眠状态，以节省无线通信模块的能耗,WMIIPL,17,功率控制,功率控制主要是通过调整发送节点的信号发射功率，在保证一定通信质量的前提下尽量降低信号发射功率。在物理层采用发射功率等级可变的无线网卡，根据收发信机之间的距离，结合节点运动预测，采用自适应天线改变发射功率的大小，以及根据信道特性合理分配功率等来提高能量的利用率,WMIIPL,18,三、典型的路由协议,1、平面路由从网络拓扑结构的角度看，路由可分为平面路由协议和层次路由协议两类。在平面路由协议中，各个网络节点地位平等，不存在等级和层次差异，路由简单，易扩展，无需进行任何架构维护，不易产生瓶颈效应，具有较好的健壮性,WMIIPL,19,典型的平面路由算法如SPIN，DD，SAR，RomorRouting等平面路由的最大缺点在于：网络中无管理节点，缺乏对通信资源的优化管理，自组织协同工作算法复杂，网络规模受限，路由跳数往往较多，因而对网络动态变化的反应速度较慢等,WMIIPL,20,2、层次路由协议层次路由协议的典型方式是分簇通过分簇路由协议将网络划分为多个簇(Cluster)。所谓簇，就是具有某种关联的网络节点集合，簇将网络节点划分为不同功能的个体，它们依据特定的方式在簇中扮演不同的角色,WMIIPL,21,簇一般包括一个簇头(ClusterHead，CH)和多个簇成员(ClusterMember，CM),WMIIPL,22,簇成员采集的数据不是直接发送给基站(BS)，而是将其传送给自己的簇头，簇头把成员节点的传感数据进行聚集和融合，再传送给基站。同时，簇头还可以负责簇间数据的转发和基站控制消息的分发，负荷较重，能耗较大簇成员和簇头之间通信可以采取直接通信的方式，也可以通过多跳路由方式,WMIIPL,23,将簇进行更细粒度的划分就形成多层嵌套的簇结构，即簇头节点还可以再选举产生更高一级簇头多层簇结构适用于规模更大的网络，但通常两层结构己可以满足大多数应用需求,WMIIPL,24,2020/5/22,电子科技大学自动化工程学院,25,基于簇的路由主要研究内容,簇,簇如何形成1簇规模优化24平均能耗58TDMA9路由优化10负载均衡,细分为：,簇间重叠问题簇头不在簇中央簇头在网络内分布不均匀通信障碍问题11数据传输过程中的能量浪费簇内节点定位问题,3、典型的簇路由,簇路由的发展自2000年麻省理工学院电子工程和计算机科学系的Heinzelman等提出LEACH算法开始但是，由于其簇头所占百分比的确定与网络规模和节点的密度相关，比较难以量化，同时，各节点随机决定是否成为簇头，导致簇头位置和簇成员个数很不均匀，而且采用了簇头直接与基站通信的路由模式，能耗较大，这些缺点使得LEACH算法的应用非常受限。,WMIIPL,26,针对LEACH的不足，Heinzelman等人又与2002年提出了改进的LEACH算法LEACH-C引入剩余能量来竞选簇头，因而，网络中的节点都需要告知BS自身位置及剩余能量信息，由BS进行优化运算，然后将结果广播给网络中的各个节点。但是，作为一种集中式的路由算法，网络需要交互的控制信息增多，浪费能耗加大，时间延迟增加，节省的有用能耗往往不能抵消浪费能耗，算法还需进一步改善。,WMIIPL,27,分簇路由的改进簇头的选择、簇的划分及簇的数据传输是基于簇结构的路由要解决的三大核心问题，在簇路由的不断发展过程中，针对这三个方面的优化问题涌现出了很多改进算法。1)对簇头选举方法的改进为了延长网络周期，簇头需要更新，目前的簇头选择算法一般需考虑以下因素：节点的剩余能量；簇内通信代价，包括簇头到簇成员间的距离、跳数等信息；邻居节点数；簇头的位置分布，包括连通度和覆盖度等,WMIIPL,28,一种分布式的节能簇算法HEEDHEED算法综合节点的剩余能量和其他参数(如候选节点与邻居节点的邻近性)来周期性地选择簇头。HEED算法比传统的簇算法具有更小的消息开销，并且HEED可以保证簇头节点在整个网络中分布良好EADEEG算法在簇头的竞选中也考虑了节点剩余能量及节点周围邻居的平均剩余能量两种信息，很好地解决了能量异构问题。然而，在簇形成阶段节点仍然需要交互多个控制信息包，即消耗了大量无用能耗，因而增大了系统的能量开销,WMIIPL,29,文献“EnergyAdaptiveClusterHeadSelectionforWirelessSensorNetworks.”引入上一轮节点剩余能量和簇平均能量以及消耗的能量三个参数重新改进了LEACH中阈值，降低了低能量节点当选簇头的概率，进一步提高了簇头选择的合理性依据节点能量信息进行簇头选举的算法比较典型的还有DEEC、REECP等,WMIIPL,30,除了剩余能量外，节点间的距离信息也是竞选簇头的一个重要参考指标，距离信息一般包括节点到基站距离以及节点到簇内其余节点的距离平方和等参数。距离信息的引入可以使所形成的簇在簇内的通信代价进一步缩小，这类算法如HYENAS、EAREC等,WMIIPL,31,一些算法在竞选簇头过程中参考了节点的邻居数等信息，比如WCA、MECH等，其中WCA在簇头选举过程中，除了节点邻居信息外，还依据了节点的通信能力、电池寿命以及节点的移动情况等。,WMIIPL,32,为了提高簇结构的网络应付突发情况的能力，同时分摊簇头的部分任务，很多算法引入了“双簇头”的簇路由机制。即通过在簇中增加一个副簇头(或称代理)来分担簇头的任务，“双簇双簇头路由”模式，在提高算法鲁棒性的同时减少了数据排队时间。,WMIIPL,33,2）簇划分的改进在LEACH算法中，每轮循环都需要重新分簇，能量浪费较大。HYENAS算法基于簇的相似度来判断是否需要重新分簇，如果相似度大于某个阈值，基站采用集中式算法重新选择簇头，进行分簇；如果相似度不大，簇结构无须改变，基站只需重新为该簇选择簇头。HYENAS避免了簇的多次重组，节省了每轮成簇的开销，但需对节点的移动特别处理,WMIIPL,34,BCDCP算法基于网络平均能量来划分簇，基站将节点剩余能量大于网络平均能量的节点作为簇头候选子集，并在其中选择距离最远的两个节点作为簇头，将网络划分为成员数量相当的两个大的子簇，并在此基础上依据同样的方式将网络继续细分为4个、8个直到达到基站所期望的簇数量。在每个划分实施阶段，通过使簇头相互间距最大化来实现簇头分布的均匀性，通过使每个簇成员节点数量相似来均衡负载,WMIIPL,35,虽然BCDCP较LEACH等成簇速度更快，能形成更加合理的簇，簇间能量负载均衡，产生良好的网络拓扑，但是BCDCP中节点需要自身定位，且和基站之间有大量控制信息交互，不仅增加了节点复杂度，也增加了网络能耗。,WMIIPL,36,EDDCR是一种基于事件驱动的动态簇划分算法，该算法中，簇的生存时间和覆盖范围依据事件情况而动态调整，即事件情况越严重，簇的生存时间越长，覆盖范围越大，解决了传统分簇路由算法中分簇与事件无关的问题。,WMIIPL,37,此外，由于采用各个簇头多跳中继的模式进行数据传输，使得靠近汇聚节点的簇头由于转发大量数据而负载过重，可能过早耗尽能量而失效，这将导致网络分割现象的出现。为了减轻由于节点与基站位置不同所造成的能量消耗不平衡问题，学者们通过簇的不均匀划分等方式解决，比较典型的算法如CODE、EEUC、EECS、CEB-UC等。,WMIIPL,38,3)簇的数据传输簇结构一般采用分层多跳的数据传输模式，数据由下层簇头向上层簇头传输，最上层簇头节点构成数据传输的主干网负责将数据最终发送给基站。对于两层簇结构,WMIIPL,39,数据通信分簇内和簇间两个阶段：在簇内，由于簇内成员和簇头距离一般较近，数据通常直接传输给簇头节点，如果两者距离较远、有障碍而不能直接通信或者直接通信代价过高等，则也采用中继等方式向簇头传输数据。在簇间，各个簇头依据一定的要求或约束并通过特定的路由算法形成数据传输的路径，由于此阶段的数据传输只在各个簇头中进行，没有了层级划分，因此，很多平面路由协议可以被采用，比如SPIN，DD，SAR等,WMIIPL,40,此外，树形路由也被很多算法采用，比如EADEEG就在簇划分的基础上，由各个上层簇头节点形成一个汇聚树，簇头节点收集并处理后的数据包就是通过该汇聚树传输给基站。同时，数据可以采用周期性的上报方式，也可只在发生突发事件时才通过一定的路由策略上报，因而数据传输又有主动性和响应性之分。TEEN算法是一种采用响应型工作模式的簇路由协议，而APTEEN算法作为TEEN的补充，将主动型和响应型的工作模式混合应用于其中。,WMIIPL,41,4、簇路由的优点,1)“多节点，小范围”的传输模式减小了系统能耗。通过簇结构将数据通信局部化在每个簇内，减少长距离通信，同时减少参与路由计算的节点数目，减小了路由表的大小，降低了交换路由信息所需的通信开销以及维护路由表所需的内存开销；2)簇头通过数据融合等措施降低了网络中的数据流量，减少有用能耗的开销。,WMIIPL,42,3)簇路由能有效实现负载均衡。动态分簇技术的应用使得网络中节点轮流充任簇头，在全网合理分配能量，实现了负载均衡，有利于延长网络生命周期。4)通过特定的簇形成算法产生较为稳定的子网络，从而减少了拓扑结构变化对路由算法带来的影响。簇头节点对其簇内的节点进行管理，能方便地向汇聚节点传达节点的各种信息，例如能量、安全性、故障等。另外汇聚节点通过簇头节点可以有效地向网络中其它节点发送命令，这是平面路由所不能有效实现的。,WMIIPL,43,5、簇路由存在的问题及发展方向,高能效的路由协议是延长无线传感器网络生命周期的重要手段，对于大规模无线传感器网络，簇结构的层次路由协议显示出了其特有的优势。虽然簇路由具有较平面路由更好的性能，但是也存在一些需要进一步改进的地方，主要表现在以下几个方面：,WMIIPL,44,1）充分利用节点的地理位置信息，改善簇头选择的合理性簇头是簇的核心，负责簇内数据的收集及融合，并管理簇事务。簇头的竞争方法以及簇的划分方法对整个网络具有重大影响，关系到整个网络生命周期长短。到目前为止，以节点剩余能量多少选择簇头是大多数算法普遍采用的方式，比如HEED、BCDCP等。,WMIIPL,45,它们通过轮流选择剩余能量多的节点充任簇头，在一定程度上均衡了网络负载，对延长网络生命周期具有重大意义。但是，对于无线传感器网络这种复杂的网络环境，仅靠剩余能量选择簇头显得并不充分，其他因素比如节点的地理位置信息同样举足轻重。,WMIIPL,46,当剩余能量最多的节点集中在某一个区域，簇成员到簇头的距离较远，则形成的簇并不是最优的，反而可能导致更多的能耗，因此簇头节点的选择还应考虑节点在簇内的位置。HYENAS、EAREC、EECS等算法在选择簇头时包含了节点地理位置信息，特别是HYENAS算法，它以成员节点到簇头节点的距离平方和以及簇头节点到基站的距离平方作为参数参与簇头的竞争，具有一定合理性。,WMIIPL,47,总之，基于地理位置路由不需经过复杂的计算，操作简单，可减少传输时延，具有较高时效性，还可以降低系统专门维护路由协议所需花费的能耗，同时避免了洪泛传播方式，减少路由开销，在路由算法的设计中应充分利用。,WMIIPL,48,2）地理位置信息的获取方式有待于进一步改善节点的地理位置信息是无线传感器网络路由设计中的一个重要辅助信息，节点不得不通过为配备GPS等定位设备来感知自身绝对位置，这不仅增加了成本，也增加了大量额外的能量开销。因此，突破节点位置获取方式，建立无需GPS等定位设备支持即可获取节点位置信息的路由是学者们追求的一个目标。,WMIIPL,49,3）充分利用集中式和分布式算法的优点，研究集分布式和集中式于一体的高能效路由。集中式路由在网络整体权衡的基础上设计更为合理的路由策略，但是需要收集大量网络信息，耗能较大，而且也增加了网络延迟，特别是对于大规模无线传感器网络更是如此。,WMIIPL,50,而分布式路由算法依据网络局部信息，自适应的构建路由，交换的控制信息相对较少，因而能耗较低。路由算法的集中式和分布式各有优缺点，因此，将两者相结合，充分利用其各自优点，构建更为合理的路由是无线传感器网络发展的一个重要方向。,WMIIPL,51,4）减少浪费能耗浪费能耗是指为了传输有效数据而不得不消耗的附加能量，在网络层主要指路由建立过程中交换控制信息包等所消耗的能量因而，减少控制包的数量是一种行之有效的方式。,WMIIPL,52,5）提高能耗的均衡性能耗是无线传感器网络的核心问题，如果某个区域能耗过快，则容易造成网络缺失或分割，不仅影响网络性能，也会导致网络生命周期减小。簇划分的不合理、簇头竞选条件等都对网络能耗的均衡性产生影响，如何在全网范围内实现能耗的均衡是需要进一步改善的问题。,WMIIPL,53,6）减小时间延迟时延是网络的一个重要性能指标，特别是在需要对事件作出快速响应的大规模无线传感器网络中，要减小数据传输的时延必须从网络结构和算法上同时进行优化。,WMIIPL,54,四、无线传感器网络高可靠性路由,在高能效的基础上，提高可靠性则是路由设计的另一个重要目标，也是无线传感器网络数据传输的基本要求。在无线传感器网络中，很多算法是在基于高可靠性的假设下设计的但是，由于无线传感器网络工作环境及工作模式的特殊性，使得通信链路的稳定性难以保证，通道质量比较低，再加上网络拓扑变化比较频繁。,WMIIPL,55,因此，要实现服务质量保证，高可靠性的假设条件往往并不现实，需要采取不同的措施提高路由的可靠性。,WMIIPL,56,典型高可靠性路由,在网络层，一般通过采用高可靠性的路由策略来提高数据传输的成功率，典型高可靠性路由策略如下：1、泛洪路由泛洪路由是最早也是最简单的路由模式，它通过向通信覆盖范围内的所有节点广播的方式传输数据包，收到数据包的节点同样通过广播的方式向其它节点转发数据，直到数据包到达目标节点。,WMIIPL,57,不需要维护网络的拓扑结构和路由计算，泛洪路由方式的优点是具有较高的鲁棒性，数据传输可靠，特别是在某些具有高移动特性、网络拓扑变化频繁的网络系统中泛洪路由具有明显优势。但是，泛洪路由中同一数据包的多个拷贝都通过网络传输，浪费了带宽和大量有用能耗，仅在小型网络中可用。,WMIIPL,58,2、多路径路由数据通信的失败往往源于高的节点失效率、高的通信错误率，如果采用单一路径，那么路由上的任何一个节点失效或任何链路的通信错误都可能导致路由中断，数据很难到达目的基站。多路径路由采用在源和目标节点之间建立数据传输的多条路径，数据包可以沿着多条路径向目标传输，提高算法适用环境等因素变迁的能力，从而提高数据传输的可靠性。,WMIIPL,59,HREEMR，ReInForM，SPEED、SAR等都是典型的多路径路由。文献“MMSPEED:MultipathMulti-SPEEDProtocolforQoSGuaranteeofReliabilityandTimelinessinWirelessSensorNetworks.”对SPEED进行扩展，提出了一个保证无线传感器网络服务质量(QoS)的新的数据包传送机制，被称为多路径多速度路由协议(MMSPEED)，通过实时性域和可靠性域来保证无线传感器网络的QoS。,WMIIPL,60,Dong等人提出的DAMER算法是一种在不可靠无线链路环境下以最小能耗维护的、具有一定鲁棒性的路由策略，同样是通过多个冗余路径提高路由的可靠性。文献“LightweightRobustRoutinginMobileWirelessSensorNetworks”采用跨层设计的方式提高数据通信的可靠性，为每个路由节点建立备用节点，通过MAC层和网络层的协作实现数据在动态变化的网络环境下的可靠传输。,WMIIPL,61,3、路径修复技术虽然通过多路径路由机制改善了系统的鲁棒性，数据传输的可靠性提高了，但要维护这么多路径必然造成能量的过多损耗，网络使用寿命大打折扣。同时，如果数据的多个拷贝同时在网络中传输，则很容易造成网络拥塞，引起更严重的通信问题。,WMIIPL,62,实现这种低能耗高效率数据传输的另一种方法就是通过单一路径传输，并采用错误探测技术，当探测到路由错误或中断时进行路由修复。SWR就是通过这种方式在提高数据传输可靠性的同时减少了系统能耗。,WMIIPL,63,WangJun等人在文献”ResearchonReliableLinkLayerCommunicationinWirelessSensorNetworks”中给出了一种单路径传输加路径修复的路由机制。每个节点都有唯一的转发节点，当节点把数据发送给转发节点后，即等待确认信息的到来，