无线传感器网络簇类路由协议的研究

无线传感器网络簇类路由协议的研究李梦娥，张登银(1．南京邮电大学计算机学院，江苏省南京市210003；2．南京邮电大学信号处理与传输研究院，江苏省南京市210003)0引言WSN(无线传感器网络)由部署在监测区域内的大量廉价的微型传感器节点组成，通过无线通信方式形成一个多跳、自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。WSN的随机布设、自组织、环境适应等特点使其在军事国防、工农业、城市管理、生物医疗、环境监测、抢险救灾、防恐反恐、危险区域远程控制等领域具有广阔的应用前景和很高的应用价值。而源于WSN自身的特点，路由协议成为其研究的重点之一。目前，已有很多路由协议，其目的是要节省系统的能量，延长系统的生命周期，提高系统的性能。主要有平面路由协议和层次路由协议。层次路由协议的基本思想是选取一些节点负责某个区域的路由，相对于其他节点具有更大的责任，而节点之间不是完全平等的关系。簇类协议具有良好的节能效果和可扩展性。具有代表性的、成熟的路由协议主要有：LEACH(Low-EnergyAdaptiveClusteringHierarchy)、TEEN(ThresholdsensitiveEnergyEfficientsensorNetworkprotocol)、PE-GASIS(Power-EfficientGatheringinSensorInformationSystems)，以及在此基础上改进的协议。1LEACH类协议1.1LEACH协议LEACH的基本思想是将整个网络划分为不同的簇，簇类节点的数据发送和接收由簇头负责，簇头节点以循环的方式随机选择。LEACH定义了轮的概念，LEACH的运行过程就是轮不断循环的过程。每个轮分成两个阶段：簇的建立阶段和传输数据的稳定阶段。在簇的建立阶段，相邻节点动态地形成簇，随机产生簇头；在数据通信阶段，簇内节点把数据发给簇头，簇头进行数据融合后把结果发送给基站。其中，簇的建立过程又可以分成4个阶段：簇首节点的选择、簇首节点的广播、簇的建立和调度机制的生成。关于簇头选择的算法，LEACH采用分布式。选择簇头的具体做法是：在每一个回合即轮的第1阶段，传感器节点随机的选择0～1之间的一个数值，如果这个数值小于某一个阈值T(n)，那么这个节点就被选为簇头节点。节点n的阈值T(n)的计算公式如下：式中：N为网络中传感器节点的总数；k为一轮网络中的簇头节点数；r为已完成的轮数；G为在剩余的r轮中未成为簇头节点的传感器节点的集合。LEACH这种簇首随机选择机制的优点在于，通过把网络的负载均匀地分布在整个网络上，很大程度上节约了通信过程中的能量损耗。每一轮中，由不同的节点充当簇头，从而网络中的节点都有机会来担当远距离通信的任务。而且，簇头节点在把簇内节点发送来的数据传送给BS(基站)之前，先进行数据融合与压缩，进而减少数据的传输量，节省了能量。LEACH实现起来相对简单，操作也比较灵活。LEACH的不足在于，每轮进行选择簇头并划分簇，并且簇头需要一直处于醒着的状态以接收数据，这样系统开销较大，离散式区域算法虽然对节点位置等要求不高，但无法确定最优的簇数目。LEACH采用TDMA的MAC层机制，而事实上，在分配给节点的每个时隙，节点并不是都有数据要发送给簇头，这样的通信机制不能有效利用带宽，浪费了能量。LEACH还要求节点之间以及节点与sink之间都可以直接通信，因此局限了网络的可扩展性，不适用于大型的网络。1.2LEACH-EE协议高效聚类路由算法LEACH-EE是在LEACH基础上改进的，不同于LEACH的单跳路径选择模式，而LEACH-EE是簇头间多跳路径选择模式。LEACH-EE的基本思想大部分继承了LEACH的模式，协议的运行过程就是簇不断循环重构的过程，每一轮也分为簇的建立阶段和传输数据的稳定阶段，簇的建立阶段也分为4个阶段：簇首节点的选择、簇首节点的广播、簇的建立和调度机制的生成。与LEACH不同的是在簇首节点广播的阶段和传输数据的稳定阶段。在簇首节点的广播阶段，每个簇头节点需要计算出自己与其他簇头之间的距离，以及自己与sink之间的距离；在传输数据的稳定阶段，由sink发起，遍历所有的簇头节点，寻找与sink路径最短的簇头，找到后，再寻找与这个簇头路径最短的下一个簇头，以此类推，直到所有的簇头节点遍历完了，建立一条通往sink的最短路径，数据就可以由这条路径融合并经多跳发送给sink。LEACH-EE的这种多跳路由模式把能量消耗均匀地分担到每个节点，网络的寿命延长，而且就算Bs与检测距离变大，也不会使得离BS远的节点迅速死亡。而LEACH中离sink较远的节点因为远距离单跳传输数据，能量消耗比较多，相对容易过早地死亡。这一点，LEACH-EE要优于LEACH。LEACH-EE也有不足，在簇首节点的广播阶段和数据传输阶段的簇头之间距离的计算和最短路径的计算都需要消耗节点的能量和时间，增加了每个节点的开销，也没有考虑到簇头节点维护的开销，这一点不利于网络的负载平衡。1.3DEEAC协议DEEAC是与LEACH类似的分布式能量有效的成簇算法。与LEACH不同的在于DEEAC的簇头选择方式上，其数据传输过程相同。DEEAC的做法是：网络中的每个节点根据某个阈值自主判断自己是否成为临时簇首，这个阈值由网络所决定的最优簇首概率Popt确定，然后，临时簇首负责收集簇内节点的信息，根据簇内通信总能耗最小化原则，选择一个使得每一轮簇内通信能量消耗最小的节点作为真正的簇首。临时簇首判断簇类通信总能耗最小，是根据簇内节点和BS的距离，而簇内节点与BS的距离的计算，通过在网络配置阶段，BS向全网广播的消息hello。临时簇首选择中，节点si随机选择0～1之间的一个值，该值若小于节点的阈值T(si)，那么这个节点就成为临时簇首节点。T(si)计算公式如下：式中：r为当前的轮数；G为在最近rmod(1／Popt)轮中没有成为簇首的节点的集合。DEEAC算法不是通过优化LEACH算法达到网络内能耗尽可能均匀分布的目标，而是通过优化LEACH随机生成的簇结构来减少每一轮的能量消耗，进而不仅使网络能耗均匀分布，而且延长网络的整体寿命。1.4LEACH-NEW协议LEACH-NEW的做法是：基站在距离r内广播查询消息(NFO)，统计距离r范围内的传感器节点数，并在这些节点中选择簇首，其中r是每个传感器节点的发射距离。每个簇头允许簇内最大的跳数由某个计算值k确定。簇的建立过程是：当距离基站r范围内的簇头确定后，簇头广播自己的D和k，那些接收到广播信息的节点将k减去1，并选择加入到k0的最近的簇头节点中，并不加入到k为0的节点，如此继续广播。而最终那些既没有收到广播信息又不是簇头的节点，过一段时间后，自选为簇头，称为被迫簇头。若在协议运行过程中，某些中间节点死亡，那么在下一轮的路由选择中，已经死亡的节点就不再加入任何簇内。LEACH-NEW簇的建立过程是在簇内节点到簇头之间形成了多跳路由。而后的过程与LEACH相似。LEACH-NEW只在距离BS为r的范围内选择簇首，因此，信息可以经簇头直接发送至BS，避免了节点离BS的距离近于节点离簇头的距离，从而节省了能量。实验仿真证明LEACH-NEW比LEACH更延长了网络寿命。但是，LEACH-NEW只在距离BS为r的范围内选择簇首，这一点并不适用于大型传感器网络。1.5LEACH-C协议LEACH-C是一种集中式的簇首选择机制，不同于LEACH分布式随机选择簇头的方式，它要求只有能量高于网络平均剩余能量的节点才有可能被选为簇首。LEACH-C通过每个节点与BS直接通信以汇报自己的位置和能量信息的方式，来评估网络剩余能量的平均值和优化簇首的选择。BS根据各节点发送来的信息选择簇头，这样使得每个区域内的节点数大致相同，实现负载均衡，因而LEACH-C的性能要优于LEACH。显然，这个过程需要消耗较多的通信能量，但却延长了网络第1个节点死亡的时间。2TEEN协议LEACH是响应型传感器网络，而TEEN是主动型传感器网络。所谓主动型传感器网络，它持续监测周围的物质现象，并以恒定速率发送监测数据。所谓响应型传感器网络，只在被观测变量发生突变时才传送数据。后者更适合应用在对时问敏感的场合中。TEEN的基本思想是设置硬、软阈值以减少数据的传输量。硬、软阈值在每次簇头轮换时广播出去，节点监测到的数据第1次超过设置的硬阈值时，就把这次数据设为新的硬阈值，并在下一个时隙发送给簇头。然后在下面的过程中，只有当监测到的数据超过硬阈值并且监测数据的变化幅度大于软阈值时，节点才会传送最新的监测数据，并将它设为新的硬阈值。TEEN根据硬、软两个阈值来确定是否传送数据，传送的数据量要比主动网络少得多，所以节点因传送数据消耗的能量也减少。仿真结果也表明，TEEN在平均能量消耗和存活的总节点数这两个性能方面要优于LEACH。TEEN存在的问题是：一方面，如果节点监测的数据一直不能超过设定的硬阈值，节点就不会传送数据，用户将无法得到任何数据，也不知道这个节点是否失效了；另一方面，节点监测到合适的数据会实时传送数据，采用TDMA的机制会造成数据延迟。3PEGASIS协议PEGASIS并不是非常严格的簇类协议，却延用了簇的思想。PEGASIS的基本思想是：节点通过定位装置或者通过发送能量递减的测试信号来发现距自己最近的邻居节点，然后从距基站最远的节点开始，采用贪婪算法来构造一条链，这条基于地理位置的链就是PEGASIS中的簇。链上的相邻节点是地理位置上距离最短的两个邻居节点，前提是假设这些节点都是静止的。PEGASIS中的数据传输使用令牌(Token)机制：簇头产生一个令牌，发送到链的一端，通知末梢节点开始传输数据，簇头与末梢之间的每个节点接收到数据之后，先与自己采集的数据进行融合处理，再向下一个节点转发，直至数据传输到簇头，簇头受到一侧的数据后再将令牌发送到链的另一端，开始同样的过程。簇接收到两侧传送来的数据后再发送给BS。PEGASIS中的数据在距离最短的相邻节点之间传输，因而节点只以最小功率发送数据分组，在每个中间节点还进行了数据融合，这样减少了业务流量，整个网络的功耗也就减少了。而事实上，研究结果也表明，使用PEGASIS的传感器网络的生命周期是使用LEACH的网络的近2倍。PEGASIS采用令牌方式传送数据，先在簇的一侧融合数据，再在另一侧融合数据，这样却增加了延迟。4比较与研究以上介绍的各种WSN中分簇的路由算法，有的优化簇头的产生，有的优化簇内的拓扑结构，有的优化簇的数据传输。表1中，对具有代表性的簇类协议LEACH、TEEN、PEGASIS，从几个性能标准方面进行比较。LEACH、LEACH-EE、DEEAC、LEACH-NEW、PEGASIS都是分布式成簇算法。所谓分布式算法，是指通过节点之间的信息交互和反馈成簇，而在实际应用中，WSN的传感器节点是随机分布、不完全均匀的，而这种基于局部信息成簇的方式容易导致网络负载整体不均匀，造成局部网络负载过重。但是，这种分布式算法有较好的扩展性、较快的收敛速度和能量的高效性。相对于分布式成簇算法，LEACH-C是集中式成簇方式。集中式算法基于全局信息由基站选择簇头，因而生成的簇比较均衡，避免了分布式算法的不均衡的缺陷，而且集中式算法的健壮性也比较好。但是，LEACH-C中的节点必须周期性地向BS汇报它们的能量和位置信息，能量开销比较大，扩展性也不好，一般只适合中小型网络。LEACH、TEEN、DEEAC是单跳路由模式，数据在TDMA分配的时隙内发送数据，其他时候节点关闭它的通信模块以节省能量。LEACH-EE、LEACH-NEW、PEGASIS是多跳路由模式，数据必需依靠中间节点进行转发，因此，靠近簇头或者靠近BS的节点就承担了更多的转发任务，导致能量消耗较快，最终影响了网络的生存周期。5结束语综上可以看出WSN中的簇类路由协议各有优势，大多从节省能量的角度进行设计，应用于各种各样的环境中。但是实际的应用环境