基于SEP协议和无线传感网节点剩余能量的多跳传输节能算法的实现

姚萌萌　邵秀丽　任智娟　郭海波

摘 要：针对基于SEP协议实现的传感器网络存在簇头节点过早死亡的现象和远距离通信网络传输能耗大的弊端。文中设计了一种基于节点剩余能量的多跳传输节能算法。该算法把剩余能量高的节点作为簇头的候选节点，采用多跳树簇拓扑通信机制，建立簇头与汇聚节点间的通信链路。使用Matlab对算法进行仿真实验分析，结果表明，该算法减小了用于网络传输的能量开销，有效延长了网络的生命周期。

关键词：SEP协议；节能算法；节点剩余能量；多跳树簇拓扑结构；多跳传输

中图分类号：TP393 文献标识码：A 文章编号：2095-1302（2016）08-00-04

0 引 言

一个成熟传感器网络有许多传感器节点，这些传感器节点进行数据的采集、压缩、识别、融合等多种处理以满足用户的多样化需求。但传感器节点体积小、能量有限，大都采用电池供电，需要与汇聚节点通信来上传采集的数据，且通信耗能比较大。因此，如何降低传感器网络中的通信耗能以延长网络的生命周期是本文的重点。

SEP协议是一种二重异构网络分簇路由协议[1，2]，它是在LEACH协议的基础上提出的适应异构网络的协议[3，4]。异构网络中节点有两种，一种是普通节点，另一种是高能量节点。但由于SEP协议在每轮成簇过程中，随机选择的簇头会使能量低的节点当选为簇头，使节点过早死亡，因此选择簇头时，应选择能量高的节点作为簇头。簇头选择好后，SEP协议建立了簇头与汇聚节点间的直接通信链路，致使远距离的簇头节点与汇聚节点的通信能量消耗非常大。如何均衡距离汇聚节点远近簇头节点的能量消耗，也决定了传感器网络生命周期的长短。

因此，本文基于SEP协议设计了一种基于节点剩余能量的多跳传输节能算法。该算法在每轮选择簇头时考虑网络中所有节点的剩余能量，选择能量高的节点当选为簇头，以及采用多跳树簇拓扑结构路由通信机制实现簇头与汇聚节点的通信，减少了距离汇聚节点较远的簇头节点的能量开销，从而均衡了传感器网络中簇头节点的能耗，延长了网络的生命周期。

实验表明，基于改进后的SEP协议设计实现的算法比普通SEP协议算法有更长的生存周期。

1 基于SEP协议动态随机选择簇头和簇头直接通信的解决方案

在无线传感器网络中，由传感器节点感知区域数据，并将数据传输到汇聚节点（Sink），汇聚节点把接收的数据进行处理，从中得到有价值的信息。而传感器节点与汇聚节点如何通信，本文采用分簇路由通信协议。这种分簇协议在节约能量上更有优势[5]。分簇的思想是：网络被划分为若干个簇（Cluster），每个簇按照一定的选举机制选举一个节点作为簇头（Cluster Head）。每个簇内除了簇头，其他节点均为成员节点（Cluster Member）。成员节点负责感知区域数据，并将数据传输到相近的簇头，簇头将数据以自组织的方式传送到汇聚节点（Sink）。分簇协议以轮为单位，每轮分为簇头的建立和稳定通信阶段。

SEP协议是一种异构无线传感器网络的稳定分簇选举协议。它在节点能量分布不均的情况下，解决了簇头节点耗能高的问题，但存在以下不足：

（1）在每轮动态成簇的过程中，会随机产生簇头，若能量低的节点当选为簇头，会使某些节点过早死亡，加速第一个死亡节点出现的时间，进而缩短网络的稳定期；

（2）簇头向汇聚节点传输数据时，采用直接通信方式（如图1所示的虚线线路），耗能单一，但随着距离的增大，簇头节点能耗急剧增加，导致传感器网络中节点能耗不均，影响传感器网络的稳定性，进而缩短传感器网络的生命周期。

针对上述不足，本文提出了如下解决方案：

（1）针对簇头节点过早死亡的现象，在建立簇头时，把节点剩余能量列为选择簇头的标准，剩余能量高的节点优先被选为簇头，以避免能量低的节点当选簇头，使其能量过早耗尽。

（2）针对直接通信的弊端，提出多跳的树簇拓扑结构通信机制（如图1所示的实线线路），使传感器网络中的簇头和汇聚节点通信时，尽可能采用多跳方式以节省能量，均衡簇头节点的能量消耗。

2 基于SEP协议的无线传感器网络节点剩余能量多跳传输节能算法及其实现过程

本文算法在实现前，需要一个合适的能量模型对算法在传感器网络中的能量消耗进行模拟，以验证算法在延长网络生命周期中的作用。

2.1 算法的能量模型

在对算法进行实现时，采用第一顺序能量模型来模拟传感器网络中各个节点的能量消耗[6，7]。该模型把节点能量的消耗分为数据发送耗能、数据融合耗能、数据接收耗能三个部分，以对网络传输中的能耗进行模拟。

本文采用的耗能模型假设：节点A向距离为d的另一节点B传输L比特的信息，则A节点发送耗能的计算公式为：

每个簇头节点融合1 b数据所消耗的能量为EDA。

2.2 基于SEP协议的无线传感器网络节点剩余能量多跳传输节能算法

由于基于SEP协议实现的传感器网络存在节点过早死亡的现象和远距离通信能耗大的弊端，本文设计的基于节点剩余能量多跳传输的节能算法基于SEP协议做了以下两处改进：

（1）把节点剩余能量列为簇头选择的标准；

（2）簇头和汇聚节点通信时采用多跳树簇拓扑通信机制。

2.2.1 剩余能量列为选举簇头标准

选择簇头时要考虑节点的剩余能量[8]，这就需对SEP协议中随机选择簇头的方法做改进，以增加能量高的节点被选为簇头的概率，避免能量低的节点当选簇头而出现节点过早死亡的现象[9]。

SEP协议的自适应成簇技术是在簇头建立阶段，传感器节点生成0～1之间的随机数rand。如果随机数小于阈值T（n），则该节点被选为簇头。在该技术中随机数rand的生成以及阈值T（n）的计算均与节点剩余能量无关，这样不利于高能量节点被选为簇头。可通过减小随机数rand的值来增大剩余能量高的节点当选为簇头的概率。

因此，本文考虑将节点剩余能量按照某种函数组织起来，以此对rand加权。该函数要使节点剩余能量更大，rand的权值更小，进而经过权值处理的rand值越小，最终增大剩余能量高的节点当选为簇头的概率。

由于（1）式为指数函数，在该函数中节点剩余能量越大，指数越小，进而对应的指数函数的值越小。用该权值对rand做处理，会减小rand的值。因此，用该权值对随机数rand做处理，会增大剩余能量高的节点当选为簇头的概率。

2.2.2 采用多跳树簇拓扑结构路由通信机制建立网络

对于簇头与汇聚节点的通信方式本文算法采用多跳树簇拓扑结构路由通信机制[10]，以该方式建立的通信网络降低了基于SEP协议中簇头与汇聚节点直接通信对于远距离簇头节点的能量消耗，均衡了传感器网络中的能耗。

簇头和汇聚节点的通信方式采用直接通信方式和多跳通信方式所形成的网络结构，簇头与汇聚节点通信图如图2所示。该图在一个100×100区域内的传感器网络中，网络被划分为若干个簇，簇头和汇聚节点通信。

多跳树簇拓扑通信机制是由一系列簇头节点通过单跳或多跳的形式形成的一种树状拓扑通信方式。簇头会选择距离汇聚节点较近的簇头作为上级节点进行多跳通信。但不是网络中所有的簇头都会进行多跳通信，需要把单个簇头与上级节点的通信耗能同汇聚节点的直接通信耗能进行比较，若传输到上级节点的耗能低则进行多跳通信，反之进行直接通信。所谓的上级节点是距离该簇头最近且已加入通信链路的簇节点。在确定好单个簇头的通信方式后，网络中就形成了一条由簇头到汇聚节点的多跳树状拓扑通信链路。

2.2.2.1 判断簇头节点是否需要进行多跳通信

假设簇头与汇聚节点的距离为d1，与上级节点的距离为d2，且都大于d0。那么根据传感器网络能耗模型，簇头与汇聚节点（Sink）直接通信对整个网络消耗的能量为（不需计较汇聚节点接收耗能，只需计算发送耗能+融合耗能）：

2.2.2.2 采用多跳树簇拓扑结构的具体算法

采用多跳树簇拓扑结构的具体算法步骤如下所示：

（1）将汇聚节点标记为已加入通信链路，并标记为父节点；

（2）选择距离汇聚节点最近的簇头节点，加入通信链路，同时标记为父节点；

（3）对于每个非父簇头节点执行如下操作：

①找出距离该簇头最近的已加入通信链路的节点；

②比较该簇头节点直接与汇聚节点通信所需要消耗的能量和与上级节点通信全网所消耗的能量，即Ec与Eb+Ep做比较，如果Ec>Eb+Ep，则采用多跳通信，在通信时按该节点耗能为Eb、父节点耗能为Ep计算；

③标记该节点为已加入通信链路，同时标记为父节点；

④重复直到所有簇头节点都加入通信链路。

2.3 算法的流程描述

本文基于剩余能量多跳传输节能算法的程序运行流程图如图3所示。

该算法分多次进行迭代，迭代与算法的时间轮对应，每次迭代分两部分模拟本文算法在传感器网络中的耗能过程。

2.3.1 簇头的产生与各个节点的耗能

簇头的产生与各个节点的耗能如图3中的Part1所示。首先设置初始化参数，根据参数和相应公式计算出阈值T（n），并为每个节点生成随机数rand，然后按照上述规则用剩余能量对rand加权（剩余能量高的权值小）。若加权后的rand小于T（n），则该节点当选为簇头。其次，成员节点选择距离最近的簇头加入。最后按能耗模型模拟网络中成员节点向簇头节点传输数据的耗能，其中成员节点耗能只考虑发送数据耗能，簇头节点考虑融合耗能和接收耗能。

2.3.2 簇头向汇聚节点通信部分

簇头向汇聚节点通信的部分如图3中的Part2所示。首先找到距离汇聚节点最近的簇头节点，加入通信链路，然后逐一对每个未加入通信链路的簇头进行处理，找到该簇头的上级节点（上级节点是距离该点最近的且已加入通信链路的簇节点），然后根据能耗模型计算该簇头和上级节点的通信耗能（Eb+Ep）和直接与汇聚节点的通信耗能（Ec）。若Eb+Ep>Ec，选择与上级节点通信；若Eb+Ep

3 算法实验

本次实验基于Windows系统、Matlab语言进行算法仿真分析。模拟从簇节点的生成，到簇头通过多跳形式和汇聚节点通信的过程，根据第一顺序能耗模型，对各节点按轮进行能量消减，对采用SEP协议算法和本文算法的结果进行对比分析。在执行过程中，每轮簇的划分、簇头的产生均动态可视化。可清晰的看到簇、簇头的交替动态变化。

3.1 算法的执行过程分析

该实验设置的仿真参数为：在100 m×100 m的正方形区域内，随机部署100个节点，汇聚节点位于（50， 50）处，在整个网络运行期间，节点和汇聚节点的位置固定；能量消耗参数：Eelec=50×0.000 000 001 J，εfs=10×0.000 000 000 001 J/b/m2，εmp=0.001 5×0.000 000 000 001 J/b/m4；EDA=6×0.000 000 001 J/b/signal；数据包的平均长度为4 000 b；在该异构网络中高能量节点高于普通节点的能量倍数a=0.5。

对于能量异构无线传感器网络，节点的能量初始化分布为两种类型，普通节点Eo=0.5 J，高能量节点Eo×（1+a）；节点信息以结构化方式存储，如表1所列。

根据节点坐标来计算节点之间的距离。运用该结构化方式对节点信息进行存储，以此作为模拟本文算法的基础。然后采用第一顺序能耗模型对网络在数据传输过程中的成员节点向簇头节点通信、簇头节点向汇聚节点通信的能量消耗进行模拟。

算法第一轮执行过后，部分节点产生的中间结果如图4所示。

第二轮结束后，节点19到24均未被选为簇头，和第一轮结果对比可知未被选为簇头的节点能量E消耗缓慢。且节点在选择簇头时各节点因为坐标不一，所要加入的簇（min_dis_cluster）也不一样。

中间结果表明本文算法很好地实现了分簇路由通信协议的思想，并且用第一顺序能耗模型能很好地模拟网络中的能量消耗。

3.2 算法的运行结果分析

某一轮的簇划分与簇头的选择过程如图6所示。

将本文算法与基于SEP协议路由算法进行对比，可明显看出本文算法的有效性。将剩余能量加入选择簇头的标准，让剩余能量高的节点被选为簇头的几率增大，避免了因为能量不足造成节点过早死亡的现象；通过加入多跳树簇拓扑结构通信机制，使得簇头到汇聚节点间的通信更具有灵活性，减少了网络传输中的能量开销，对比结果表明本文算法达到了延长网络生存周期的目的。

4 结 语

本文通过对稳定异构网络协议SEP进行分析，发现在大规模传感器网络中存在节点过早死亡的现象，以及远距离数据传输能耗大的不足，设计了一种基于节点剩余能量的多跳节能算法。该算法在选取簇头时，增大了剩余能量高的节点当选为簇头的概率，并采用多跳树簇拓扑通信结构的方式，在簇头和汇聚节点建立了一条多跳树状数据传输链路，有效降低了用于网络传输的能量消耗，延长了网络的生命周期。

参考文献

[1] Georgios Smaragdakis，Ibrahim Mata，Azer Bestavros. SEP： A Stable Election Protocol for clustered heterogeneous wireless sensor networks[Z].Computer Science Department Boston University.

[2]杨莉莉.SEP2.0通信协议研究[J].中国新通信，2014（12）：80.

[3]杨永健，贾冰，王杰.无线传感器网络中LEACH协议的改进[J].北京邮电大学学报，2013（1）：105-109.

[4]李岩，张曦煌，李彦中.基于LEACH协议的簇头多跳（LEACH-M）算法[J].计算机工程与设计，2007，28（17）：4158-4160.

[5]沈波，张世永，钟亦平.无线传感器网络分簇路由协议[J].软件学报，2006，17（7）：1588-1600.

[6]Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Trans. on Wireless Commun.，2002，1（4）：660-667.

[7]张志东，孙雨耕，刘洋，等.无线传感器网络能量模型[J]. 天津大学学报，2007，40（9）：1029-1034.

[8]丁男，谭国真，由笛，等.一种基于WSN时变性与节点剩余能量均衡的机会路由算法[J].电子与信息学报，2013，35（3）：715-720.

[9]郭文强，周强，侯勇严，等.一种基于无线传感器网络分簇路由的改进算法[J].陕西科技大学学报，2013，31（2）：132-135，141.

[10]李小亚，黄道平，吴洪艳.无线传感器网络单跳与多跳路由的选择性[J].计算机工程，2009，35（3）：13-14，53.