第7章-路由协议

第7章无线传感器网络的路由协议7.1路由协议概述7.1.1无线传感器网络路由协议的考虑因素设计无线传感器网络的路由要考虑的因素很多，大致分为以下两种类型。(1)网络特征：无线传感器网络具有与众不同的特征，应用于路由协议设计时，主要应该考虑能量损耗、节点部署和网络拓扑变化。(2)数据传输特征：无线传感器网络的数据采集和传输要求与其他网络不同，因此路由协议设计时也需要加以区别，主要考虑数据传输方式、无线传输手段以及数据融合技术等。7.1.2路由的过程无线传感器网络的路由过程主要分为以下4个步骤：①某一个设备发出路由请求命令帧，启动路由发现过程；②对应的接收设备收到该命令后，回复应答命令帧；③对潜在的各条路径开销(跳转次数、延迟时间)，进行评估比较；④将评估确定之后的最佳路由记录添加到此路径上各个设备的路由表中。7.1.3无线传感器网络路由协议分类方法1．按源节点获取路径的方法主动路由协议、按需路由协议、混合路由协议2．按节点参与通信的方式直接通信路由协议、平面路由协议、层次路由协议3．按路由的发现过程以位置信息为中心的路由协议、以数据为中心的路由协议4．按路由选择是否考虑服务质量(QoS)约束保证QoS的路由协议是指在路由建立时，考虑时延、丢包率等QoS参数，从多条可行的路由中选择一条最适合QoS应用要求的路由；或者根据业务类型，保证满足不同业务需求的QoS路由协议。7.2平面路由协议7.2.1FloodingandGrossing协议1.洪泛路由协议洪泛路由协议(FloodingProtocol)是一种最早的路由协议，接收到消息的节点以广播的彤式转发报文给所有的邻居节点，(如图7-1,2所示)。ABDC（x）图7-1洪泛法的信息爆炸问题（x）（x）（x）ABC图7-2洪泛法的信息重叠问题（q,r）（r,s）qrs2.闲聊法闲聊法(Grossing)是洪泛法的改进版本。如图7-3所示图7-3闲聊法协议过程2(x)1(x)4(x)(x)3CSABDE7.2.2SPIN协议基于协商机制的传感器网络SPIN协议(SensorProtocolsforInformationviaNegotiation)是一种以数据为中心的白适应通信方式，使用3种类型的信息进行通信，即ADV、REQ和DATA信息。图7-4表示了SPIN协议的工作过程。图7-4SPIN协议工作过程SPIN协议的缺点是没有考虑节能和多种信道条件下的数据传输问题。因此，后续又出现了SPIN-PP(PointtoPoint，点到点的通信模式)、SPIN-EC(EnergyControl，点到点模式下的节能路由)、SPIN-RL(RouteLossy，点到点通信中的信道衰减模式)、SPIN-BC(BroadcastChannel，广播信道模式)等在SPIN基础上改进的路由协议。7.2.3SAR、DD和MCFA协议1．SAR协议顺序分配路由SAR协议(SequentialAssignmentRouting)是第一个具有QoS意识的路由协议。该协议通过构建以Sink的单跳邻居节点为根节点的多播树来实现传感器节点到Sink节点的多跳路径。2．DD协议定向扩散路由DD协议(DirectedDiffusion)是一种以数据为中心的信息传播协议，与已有的路由算法有着截然不同的实现机制。3．MCFA协议最小开销前行算法MCFA协议(MinimumCostForwardingAlgorithmforLargeSensorNetworks)充分利用了传感器网络中的数据传输不对称的特点，即大多的数据流都是从传感器节点向Sink节点的方向传输。7.3层次路由协议7.3.1LEACH低功耗自适应聚类分级LEACH协议(LOWEnergyAdaptiveClusteringHierarchy)是无线传感器网络中最早提出的分层路由算法。LEACH可以将网络整体生存时间延长15％，其基本思想是通过随机循环地选择簇头节点将整个网络的能量负载平均分配到每个传感器节点中，从而降低网络能源消耗，提高网络整体生存时间。7.3.2PEGASIS高能效采集传感器信息系统PEGASIS协议(PowerEfficientGatheringinSensorInformationSystems)是在LEACH协议上提出的一种改进路由算法。PEGASIS路由协议在网络中选择一个节点作为起始节点建立一条最优回路链，起始节点将数据融合后的数据信息发送给Sink节点。由于起始节点的负载较重，PEGASIS采用了全网节点轮流作为回路链起始节点的方式来进行均衡。该路由协议中使用了贪婪算法(GreedyAlgorithm)来形成链，如图7-5所示。在每一轮通信之前才形成链。为确保每个节点都有其相邻节点，从离基站最远的节点开始构建，链中邻居节点的距离会逐渐增大，因为已经在链中的节点不能被再次访，当其中一个节点失效时，链必须重构。图7-5PEGASIS数据传输链的形成C0C1C2C3C4C0C1C2C3C4BS(基站)7.3.3TEEN阈值敏感的高效传感器网络TEEN协议(ThresholdSensitiveEnergyEfficientSensorNetwork)，是一个基于簇群的路由协议，也是由LEACH发展而来，在这个协议中定义了硬门限和软门限两个概念。这个算法适用于实时性要求较高的应用场合，用户可以及时获取感兴趣的信息。由于感应数据所耗能量比传输数据所耗能量要少得多，虽然节点一直处于感应状态，但是由于减少了很多不必要的数据传输，因此相对来说还是节能的。该协议也有一些不足之处：①门限值达不到，节点就永远不会和簇头节点通信，用户就无法从网络得到任何数据，即使节点已经死亡，用户也不知情；②TDMA机制的运用保证了群中不会出现数据冲撞的情况，但是如果一个节点没有数据要发送的话，属于它的时隙就浪费掉了，而其他节点却还在等待自己的时隙，这样会向系统中引入过多的时延，不适于实时性要求太高的场合；③没有相应的机制去区分那些没有感应到足够大变化的节点和处于关闭状态的节点。群头节点的接收机要时刻处于激活状态，以便接收任何时候由成员节点传来的数据，在某种程度上增加了簇头节点的负担。7.3.4APTEEN、TTDD和EARSN协议1．APTEENAPTEEN(AdaptivePeriodicFEEN)协议是对TEEN的扩展，它是一种结合响应型和主动型传感器网络策略的混合型网络路由协议，可以根据用户需要和应用类型来设定协议的周期性和相关阀值，即可以周期性采集数据又可以对突发事件作出快速反应。APTEEN在TEEN的基础上定义了一个计数时间，当节点从上一次发送数据开始经历这个计数时间还没有发送数据，那么不管当前的数据是否满足软、硬门限的要求都会发送这个数据。APTEEN可以通过改变计数时间来控制能量消耗。2．TTDD双列数据分发TTDD(TWO-TierDataDissemination)，协议假设节点静态，且各节点的位置信息已知。网络中可以存在多个Sink节点，Sink节点可以在网络中任意移动。网络中的节点以虚拟栅格的形式划分为若干区域，当监测区域发生事件，附近的多个节点将选择一个节点触发数据上报消息。发送数据上报消息的簇头节点将上报报文发送给栅格外的其他4个栅格的邻接节点，由邻接节点转发给该栅格的另外3个邻接节点，最后将上报的数据报文发送到每一个栅格。这样无论Sink节点移动到网络中的任何地方，都能够从距离最近的节点上收到上报的数据报文。7.3.4APTEEN、TTDD和EARSN协议3．EARSN簇头固定的分簇结构路由协议EARSN(EnergyAwareRoutingforClusterBasedSensorNetwork)是基于三层体系结构的路由协议。该协议要求网络运行前由终端用户将传感器节点划分成簇，并通知每个簇头节点的ID标识和簇内所分配节点的位置信息。传感器节点可以以活动方式和备用的低能源方式两种方式运行，并可以感知、转发、感知并转发和休眠4种方式之一存在。与其他路由协议不同的是，该协议的簇头不受能量的限制。它作为网络的中心管理者，可以监控节点的能量变化，决定并维护传感器的4种状态。算法依据两个节点间的能量消耗、延迟最优化等性能指标计算路径代价函数。簇头节点利用代价函数作为链路成本，选择最小成本的路径作为节点与其通信的最优路径。经仿真分析，该协议在运行过程中具有很好的节能性、较高的吞吐量和较低的通信延迟。7.3.4APTEEN、TTDD和EARSN协议7.3.5平面路由协议和层次路由协议比较表7-1为各种协议之间的简单对比，主要从移动性、能量需求、路径长度、扩展性、路由状态复杂度、计算和通信所需开销、数据融合技术等多方面进行了分析比较。总体来看，由于网络结构的不同，平面路由和层次路由体现出了以下几处差异。①移动性②能量使用③路由选择④可拓展性⑤开销7.3.5平面路由协议和层次路由协议比较7.4能量感知路由7.4.1能量消耗源1．通信相关的能量消耗通信相关的能耗包括对传输器、中转器和接收器的使用。2．计算相关的能量消耗计算相关的能耗主要涉及协议的处理，主要包括对CPU、主要存储器、一个很小的外设、磁盘或其他一些组成部分的使用。同样的，数据压缩技术在减少数据包长度的同时也因为计算量的增大而增加了能量消耗。7.4.2能量路由在如图7-6所示的网络中，源节点是一般功能的传感器节点，完成数据采集工作。汇聚节点是数据发送的目标节点。大写字母表示节点，如节点A，节点右侧括号内的数字表示节点的可用能量。图中的双向线表示节点之间的通信链路，链路上的数字表示在该链路上发送数据消耗的能量。在图中，从源节点到汇聚节点的可能路径有4条。图7-6能量路由算法示意源节点汇聚节点A(PA=2)B(PA=2)C(PA=2)E(PA=1)D(PA=3)F(PA=4)a3=2a4=2a5=2a1=1a2=1a8=2a9=2a10=2a6=2a7=1路径1：源节点—B—A—汇聚节点，路径上所有节点PA之和为4，在该路径上发送分组需要的能量之和为3；路径2：源节点—C—B—A—汇聚节点，路径上所有节点PA之和为6，在该路径上发送分组需要的能量之和为6；路径3：源节点—D—汇聚节点，路径上所有节点PA之和为3，在该路上发送分组需要的能量之和为4；路径4：源节点—F—E—汇聚节点，路径上所有节点PA之和为5，在该路径上发送分组需要的能量之和为6。能量路由选择策略主要有以下几种：最大可用能量路由、最小能量消耗路由、最少跳数路由和最大最小PA节点路由。7.4.3能量多路径路由能量多路径路由的主要流程描述如下：(1)发起路径建立(2)判断是否转发路径建立消息(3)计算能量代价(4)节点加入路径条件(5)节点选择概率计算(6)代价平均值计算7.5基于查询的路由基于查询的路由协议，在需要不断查询传感器节点采集的数据的应用中，通信流量主要产生于查询节点和传感器节点之间的命令和数据传输，同时传感器节点的采样信息在传输路径上通常要进行数据融合，通过减少通信流量来节省能量。7.5.1定向扩散路由定向扩散(DirectedDiffusion，DD)是一种基于查询的路由机制，是专门为无线传感器网络设计的。定向扩散路由机制包括周期性的兴趣扩散、梯度建立、数据传播、路径加强等阶段。1．兴趣扩散阶段2．梯度建立阶段3．数据传播阶段4．路径加强阶段图7-7定向扩散路由机制(a)兴趣扩散源Sink(b)梯度建立源Sink(c)正增强路径源Sink源(d)负增强路径表示数据传输7.5.2谣传路由谣传路由(RumorRouting)，其路由的建立是由Sink节点和源节点共同发起并完成的。谣传路由的原理如图7-8所示。图7-8谣传路由机制事件区域发起路径：查询路径：节点：谣传路由协议的执行过程如下：①每个传感器节点维护一个邻居列表和一个事件列表。②当传感器节点在本地检测到一个事件时，就在事件列表中增加一个表项，设置相关的事件名称、跳数等，同时根据一定的概率产生一个代理消息。代理消息是一个包含生命期等事件信息的分组，用来携