第8讲 WSN路由协议

2020/2/121第8讲WSN路由协议2020/2/1222020/2/1238.1无线传感器网络路由协议的分类无线传感器网络路由协议按照协议的应用特征分类按照网络结构分类平面路由协议层次路由协议基于位置路由协议基于位置路由协议基于查询路由协议基于协商路由协议基于可靠路由协议基于多径路由协议基于QoS路由协议图2.1无线传感器网络路由协议分类2020/2/124层次路由协议的基本思想是：将网络节点进行分簇，其拓扑结构是层次型的，每簇由一个簇头节点及若干簇成员节点组成。簇头节点担任各簇的数据收集、处理和转发任务。层次路由通过分簇提高了网络可扩展性，降低了节点能耗，延长了网络生命周期。2020/2/1258.2性能指标及设计原则1.需要综合考虑下列性能指标：能量有效性及网络生命周期可扩展性为了适应网络拓扑的动态变化、实现大量节点的协同工作容错性由于外界环境的影响、敌方的恶意破坏以及节点自身能量耗尽等因素，常常导致部分传感器节点失效。2020/2/126快速收敛收敛是指所有担当路由器的节点在判断最佳路径时信息更新达到一致的过程。收敛慢的路由算法可能会导致路径循环或网络中断。安全性2020/2/1272.设计必须遵循如下原则（1）通常布置在恶劣或危险的环境中，节点电池容量有限且不易更换。因此，为了延长节点的使用寿命及网络生存时间，必须减少或均衡电源的消耗。（2）是以数据为中心的，其最终目的是收集数据。因此，不需要考虑太多通信带宽方面的问题。（3）重视数据汇集和数据融合。网络中邻近节点采集的数据往往是雷同的，会产生大量的数据冗余，且传输数据时所消耗的电源开销过大。因此，需要在网络内部进行数据汇集和数据融合操作，以消除冗余，减少通信量，降低电源开销。2020/2/1288.3常见无线传感器网络路由协议（1）Flooding最简单的，最早的不需要维护网络拓扑结构，网络中的节点仅简单地将它所收到的数据包广播出去，如此反复，直到数据到达目的节点为止，或者数据包达到最大跳数为止，或者所有节点都拥有此数据副本为止。2020/2/129缺点：节点将多次收到相同的消息，容易导致消息的内爆(Implosion)、重叠(Overlap)。将同一个数据包多次转发给同一个节点的现象就是内爆。2020/2/1210(2)GossipingGossiping是对Flooding的一种改进。主要解决Flooding协议的内爆问题。节点在发送数据时，不是向所有邻居节点都进行广播，而是随机选择一个邻居节点发送数据副本，这样就避免了消息内爆问题。缺点：无法解决消息重叠问题以及资源的盲目利用问题，此外还增加了端到端的数据时延。2020/2/1211（3）SPIN协议SPIN是以数据为中心的自适应路由协议，通过协商机制和资源自适应机制来解决Flooding协议中的内爆和重叠问题。SPIN协议主要有四种形式：SPIN-PP、SPIN-EC、SPIN-BC和SPIN-RL。2020/2/1212SPIN协议的主要思想：利用ADV、REQ和DATA三种类型的消息进行数据协商。ADV用于新数据广播，其大小远小于DATA；REQ表示请求发送数据；DATA表示数据。2020/2/1213节点有新的数据需要转发时，首先向自己的邻居节点广播ADV消息；根据ADV消息中对新数据属性的描述，感兴趣的邻居节点会向该节点发送REQ消息表示请求发送数据；该节点根据收到的REQ消息的情况，向相应的邻居节点发送DATA消息。2020/2/1214优点：SPIN协议可以有效地解决Flooding协议中消息的内爆和重叠问题，避免资源的盲目利用，节省了能量消耗。缺点：SPIN协议中有可能会出现数据盲点。而且当网络规模较大时，仍然会出现ADV消息的内爆问题。2020/2/1215（4）DirectedDiffusion协议DirectedDiffusion是以数据为中心、查询驱动的路由协议。分为三个阶段：兴趣（interest）扩散阶段、梯度(gradient)建立阶段、路径加强阶段。2020/2/1216兴趣消息表示查询任务。sink节点周期性地向邻居节点以泛洪的方式广播兴趣消息（interest）。当节点收到兴趣消息后建立相应的梯度并将兴趣消息继续广播给它的邻居节点，建立临时的梯度场。传感器节点将采集的数据沿着梯度方向发送到sink节点。然后sink节点从若干条返回路径中选择一条代价最小的作为加强路径，后续的数据将沿着加强路径发送到sink节点。2020/2/12172020/2/12182020/2/12192020/2/1220（5）LEACH协议LEACH（lowenergyadaptiveclusteringhierarchy）协议是基于低能量自适应分簇的路由协议。2020/2/1221LEACH协议每“轮”分为两个阶段：周期性的簇的建立阶段与稳定的数据通信阶段。簇的建立阶段又包括簇头的选举以及簇的形成这两部分。稳定的数据传输阶段结束后，即进入下一“轮”的簇的建立阶段，整个网络开始下一“轮”的工作周期。LEACH协议将传感器节点划分成不同的簇，每簇选举一个节点为簇头，其余节点为簇内节点。簇内节点将数据发送给本簇的簇头节点，簇头节点收集簇内信息进行数据处理后再发送给sink节点。2020/2/1222Why?协议分类：层次型，可扩展性好，更节省能量，网络生存时间更长。典型性：层次型路由协议中的典型代表，是无线传感器网络中提出的第一个基于分簇的路由协议。其他几种层次式路由协议都是在LEACH协议的基础上发展起来的，比如TEEN、PEGASIS等。低功耗：一种低功耗自适应动态分簇路由算法，与一般的平面多跳路由协议和静态分簇算法相比，能够将网络生命周期延长15%。2020/2/1223网络模型（1）基站（sink节点）位置固定且远离无线传感器网络其他节点，同时假设基站有足够的能量供应。（2）所有传感器节点同构、初始能量相同且是有限的。（3）通信信道是对称的，即节点A发送消息给节点B消耗的能量与节点B发送同样大小的消息给节点A消耗的能量相同。且无线电信号在各个方向的能耗是相同的。（4）传感器节点之间可以相互通信，能够控制自身的发射功率，且有足够的能量与基站直接通信。（5）节点有足够的计算能力来支持所需的不同的MAC协议并实现不同的信号处理功能。（6）传感器节点总有数据要向基站发送，且其采集的数据与邻近节点采集的数据具有较高的相关性、有较高的数据冗余，可以进行数据融合。（7）网络中的节点是基本静止的。2020/2/1224能量损耗模型采用的能量损耗模型是一阶无线电模式。其中，Eelec为无线收发器的电路部分消耗的能量，εamp为信号放大器的放大倍数，d为信号传输的距离；n是由无线电信道决定的常量。当信号传输距离d较短且小于某个临界值时，可采用自由空间传播模型，取n=2；当信号传输距离d较长且大于某个临界值时，可采用多路衰减模型,取n=4。2020/2/1225节点发送k比特的数据到距离为d的另一节点所消耗的能量为：节点接收k比特的数据所消耗的能量为：2020/2/1226具体描述1、簇头的选举给每个传感器节点设定一个阀值T（n）,同时传感器节点产生一个介于0、1之间的随机数。若产生的这个随机数小于阀值T（n），则该节点当选为簇头并向网络中发布公告消息，宣布自己是新当选的簇头节点。其中T（n）按下式进行计算：2020/2/1227P是簇首节点占所有传感器节点中的百分比，p的最佳取值因网络的不同而不同；r是当前轮数；G是最近前rmod(1/p)轮中还未当选为簇头的节点集合。若节点在最近前rmod(1/p)轮中已经当选过簇头，则把该节点的T（n）置0，则该节点就不会再次被选举为簇头；在最近前rmod(1/p)轮中还没有当选过簇头的节点，则以T（n）的概率被选举为簇头。每个节点都会在1/p轮操作内充当一次簇头节点。2020/2/12282、簇的形成2020/2/12293、稳定的数据传输阶段簇头节点的接收器始终处于开启状态；簇内成员节点在属于自己的时隙到来时才开启收发器，其他时隙则关闭收发器以节省能量。簇内成员节点在各自的时隙向簇头节点发送数据，簇头接收完一帧的数据后，对接收到数据进行数据融合并将新数据发送到sink节点。2020/2/1230（1）选举簇头时没有考虑节点剩余能量，没能给剩余能量多的节点更多的机会来担当簇头。造成无论节点剩余能量多少，当选为簇头的概率都没有差别。（2）频繁进行簇头选举，耗费了大量的能量。且每轮选举簇头时，所有非簇头节点都要参加，不仅增加了复杂性，也浪费了部分能量。（3）簇头节点直接与sink节点通信，导致距离sink节点较远的簇头能量消耗较快，各簇头之间能耗严重不均衡。（4）没有把安全性作为设计目标4.存在的问题2020/2/12315.安全威胁LEACH协议容易受到三种类型的路由攻击：选择性转发攻击Sybil攻击HELLO泛洪攻击2020/2/12326.LEACH-CLEACH-C采用集中式算法。簇的建立阶段，各传感节点将自身剩余能量及位置信息发送给sink节点。sink节点根据各传感节点剩余能量占当前轮网络总能量的比例来选举簇头节点LEACH-C可以改善簇头的分布。但是每次选举簇头节点时，sink节点都需要知道全网的总剩余能量并集中运算，不利于网络的扩展性。2020/2/12337.LEACH-FLEACH-F为了减少成簇的能量消耗，使得分簇一旦完成后各簇的组织结构即保持不变，仅仅在簇内实现簇头节点的轮转。缺点：LEACH-F算法无法响应网络拓扑结构的变化。2020/2/12342020/2/1235