基于等级的无线传感网自适应分簇算法

肖 玮，涂亚庆

(后勤工程学院 后勤信息与军事物流工程系,重庆 401311)

基于等级的无线传感网自适应分簇算法

肖 玮*，涂亚庆

(后勤工程学院 后勤信息与军事物流工程系,重庆 401311)

(*通信作者电子邮箱wzwry@163.com)

为解决现有无线传感器网络(WSN)分簇算法难以同时兼顾其异构性和移动性，从而引发网络寿命较短、网络数据吞吐量较低等问题，提出了基于节点等级的自适应分簇算法。该算法按轮运行，每轮分为自适应分簇、簇建立、数据传输三个阶段。为解决节点移动性引发的簇首数目和成簇规模不合理的问题，在自适应分簇阶段，根据子区域内节点数目变化对相应子区域进行细化或就近合并，以确保每个子区域内节点数目在合理范围内。在簇建立阶段，选举簇内等级最高的节点为簇首，解决异构性引发的部分节点能耗过快、网络寿命缩短的问题；节点等级除考虑节点剩余能量外，还结合WSN实际应用，由节点剩余能量、能量消耗速率、到基站的距离、到簇内其他节点的距离综合决定。基于OMNeT++和Matlab 的仿真实验结果表明，在节点移动速度为0～0.6 m/s的能量异构WSN环境下，较移动低功耗自适应集簇分层(LEACH-Mobile)算法和分布式能量有效分簇(DEEC)算法，运用所提算法分簇的WSN寿命延长了30.9%以上，网络数据吞吐量是其他两种算法分簇的网络的1.15倍以上。

自适应分簇；等级；无线传感器网络；能量异构；移动性

0 引言

无线传感器网络(Wireless Sensor Network, WSN)是由大量的静止或移动的传感器以自组织和多跳的方式构成的无线网络，以协作地感知、采集、处理和传输网络覆盖地理区域内被感知对象的信息，并最终把这些信息发送给网络所有者，广泛应用于军事、航空、防爆、救灾、环境、医疗、保健、家居、工业、商业等诸多领域[1-2]。由于WSN中节点体积小、携带能量有限，因此如何利用节点有限的能量延长网络寿命，增大网络数据吞吐量一直是WSN亟需解决的问题之一。相关研究表明，分簇技术能均衡节点能量消耗，延长节点存活时间，是降低节点能耗和延长网络寿命的一种有效途径。经过数十年快速稳健发展，WSN分簇技术取得了较为丰硕的成果[3-6]。比较经典的是层次路由协议，典型代表是文献[5]提出的低功耗自适应集簇分层(Low Energy Adaptive Clustering Hierarchy, LEACH)协议。该协议通过随机选举簇首，平均分担能量负载，延长了网络生命周期。但存在簇首分布随机、节点能量利用率不高的问题。文献[6]在其基础上进行改进，提出了传感器信息系统的高效采集(Power-Efficient Gathering in Sensor Information System, PEGASIS)协议，该协议通过在网络中只形成一个簇，称为“链”，有效避免了LEACH协议频繁选举簇首带来的通信开销，减少了数据传输次数和通信量；但如果链过长，延迟更严重。

在WSN中，传感器节点能量异构的现象普遍存在。因为在布置网络时传感器节点可能会配置不同的初始能量；此外，在具体工作过程中，每个节点的能量消耗不同也会导致网络中出现能量异构现象。目前，针对能量异构WSN的分簇算法主要有如下几种：针对二级能量异构网络设计的可靠选举协议(Stable Election Protocol, SEP)[7]，该协议将节点分为高能量和低能量两种，并为两种不同节点设置不同的当选簇头的门限。针对三级异构网络，文献[8]对集中能量高效分簇(Centralized Energy Efficient Clustering, CEEC)算法进行改进，提出了两种新算法，主要综合考虑初始能量、剩余能量、区域标识和到基站的距离选择簇首。文献[9]提出了适用于多级能量异构网络设计的分布式能量有效成簇算法(Distributed Energy-Efficient Clustering algorithm, DEEC)，其核心思想是让剩余能量高的节点有更大的概率当选簇首节点，通过动态调整网络结构充分利用网络能量。文献[10]提出一种能量敏感的非均匀分簇(Energy Aware Distributed Unequal Clustering, EADUC)协议，该协议主要以邻居节点个数、基站位置和剩余能量为主要指标来选择簇首，用以解决异构网络中的能量空洞问题。

此外，WSN应大量应用于节点移动领域[11-13]。由于节点移动造成网络拓扑变化，针对静止WSN的大部分路由算法并不能很好地适用于移动WSN，因此针对移动WSN，大量专门的路由算法应运而生。例如，文献[11]提出的移动LEACH(LEACH-Mobile, LEACH-Mobile)算法沿用LEACH按轮进行，当节点因移动远离原簇首而更靠近新的簇首时，建立一种机制帮助其判断是否换簇首。簇建立之后，簇首维护一个成员节点列表，簇首向各个成员节点发送请求数据消息，簇首与成员节点根据该消息机制来维护簇的动态结构。但实验表明 LEACH-Mobile算法在簇首轮换选举前，存在大量丢失数据包的情况。文献[12-13]提出分布式安全加权的系列分簇算法，通过综合五大标准来确定簇首，并检测和剔除恶性节点。

近年来随着对物联网(Internet of Things, IOT)研究的兴起，对作为物联网感知层的WSN的研究显得尤为基础和重要[14]。由于物联网的移动性和能量异构性十分显著，使得WSN的应用拓展到诸多移动性和能量异构性显著的领域，如军队集团作战、部队后勤保障、反恐抗灾行动等[15-16]。但现有分簇技术难以同时应对具有能量异构和移动性的无线传感器网络。这些算法或仅考虑无线传感器移动性，如LEACH-Mobile算法；或仅考虑网络异构性，如DEEC算法和仅适用于二级异构网络的SEP算法，和三级异构网络的CEEC算法；鲜见同时兼顾移动性和异构性的分簇算法。此外，LEACH及其改进算法Q-LEACH[17]、门限敏感能量高效(Threshold sensitive Energy Efficient sensor Network, TEEN)算法[18]中的簇首均是随机产生，因此常出现簇首数目不合理、簇首分布和成簇规模不均的情况，这些情况将直接导致节点能耗不均、网络寿命缩短。能量高效非均匀分簇(Energy-Efficient Uneven Clustering, EEUC)算法[19]、能量高效异构分簇(Energy Efficient Heterogeneous Clustered, EEHC)算法[20]、DEEC算法则以节点剩余能量作为选举簇首的主要指标，使剰余能量高的节点有更大的概率成为簇首，但在能量异构性显著的WSN应用中，存在剩余能量大同时能量消耗也快的节点，从网络整体性能来看，这类节点并不是簇首节点的最佳选择；同时，节点能耗与通信距离成正比，但现有分簇算法鲜见将其作为簇首选择参考因素。

为此，本文兼顾WSN的移动性和能量异构性，提出了基于节点等级的自适应分簇算法(Adaptive Clustering Algorithm based on Grades, ACA_G)。该算法利用自适应分簇解决节点移动引发的簇首数目和成簇规模不合理的问题。通过选举簇内等级最高的节点为簇首，解决异构性引发的部分节点能耗过快、网络寿命缩短问题。节点等级除考虑节点剩余能量外，还结合WSN的实际应用，综合考虑节点剩余能量、能量消耗速率、到基站的距离、到簇内其他节点的距离等因素。

1 网络模型和能耗模型

1.1 网络模型

按照节点的功能不同，将节点分为三类：基站、簇首、普通节点。簇首和普通节点可以相互转换，相关属性设定如下：

1)基站固定于WSN监测区域中心位置，能量无限；其余节点初始位置随机分布，能量有限且不能补充。

2)WSN的异构性体现为能量异构，异构节点的初始能量和能量消耗速率不同，同构节点的初始能量和能量消耗速率相同；节点可感知自身的剩余能量和计算能量消耗速率。

3)节点移动方向和移动角度在每轮中恒定。

4)节点能够参照信标节点或锚节点，感知自身位置。

1.2 能耗模型

本文算法中使用的无线通信能耗模型参照Heinzelman等[5]提供的一阶无线通信能耗模型，该模型如图1所示。

图1 无线通信能耗模型

由于节点的收发能耗远大于节点感知和处理信息的能耗及节点闲置、休眠时的能耗，因此在该模型中，主要考虑节点的收发能耗。其中，节点的发送能耗包含发送电路能耗、放大电路能耗；节点的接收能耗仅包含接收电路能耗。该模型根据数据传输距离的远近，采用两种不同的信道模型。当传输距离d小于阈值距离d0时，采用自由空间信道模型；反之，采用多径衰落信道模型。式(1)、(2)分别给出了向距离d处的节点发送/接收lb数据的能耗ETx(l,d)和ERx(l,d)。

(1)

ERx(l,d)=Eelecl

(2)

1.3 节点移动模型

本文算法的节点移动模型选用随机移动模型[21]。随机移动模型中，节点随机选择在[0，vmax]内均匀分布的某个值作匀速运动，到达目的地后，停留Tpause时间后，节点又随机选择新的目的地移动。如果Tpause=0，则表示节点连续运动。由此可见，节点最大运动速率vmax和停留时间Tpause是随机移动模型的两个关键参数。如果vmax小而Tpause大，则网络拓扑相对稳定；反之，则网络拓扑具有较高的动态性。此外，ACA_G算法基于以下假设进行验证：簇首在当选时间内处于基本静止状态，其余的节点移动主要集中在数据传输阶段。

2 算法原理

ACA_G算法按轮依次运行，每一轮包括自适应分簇、簇建立、数据传输三个阶段。ACA_G算法算法流程如图2所示。

图2 ACA_G算法流程

2.1 自适应分簇

初始化时，根据网络监测区域大小，按一定原则，如从左到右-从上到下原则将网络监测区域等分成M0(M0≥1)个子区域，每个子区域中所有节点自成一簇，初始节点分布如图3所示，监测区域中心位置为能量无限大、位置固定的基站。图3中，通过节点颜色表征当前节点的能量高低，颜色越深的节点表示能量越高。网络运行过程中，由于节点移动或因能量消耗殆尽死亡，每个子区域内的节点数目是动态变化的。本文算法通过监测每个子区域内节点数目变化，实现自适应分簇，以防止因簇首分布不均、簇规模不合理造成的部分节点能量衰减过快，网络整体寿命缩短。

图3 节点初始分布

自适应分簇的实施方法如下：

(3)

(4)

其中：m∈[1,Mr-1]，Mr-1表示网络监测区域第r-1轮划分的子区域总数，Mr-1、r、m为大于0的整数；Nr表示第r轮网络中存活节点的总数;ω1和ω2表示权重系数，ω1∈[0,1]，ω2∈[1,2]；符号⎣」表示取整数运算。

(5)

(6)

(7)

由图4～5可知，通过自适应分簇，可实现网络中簇首数目和成簇规模合理化。

图4 子区域细化示意图

图5 就近子区域合并示意图

2.2 簇建立

(8)

选举本簇内等级最高的节点为第r轮簇首，具体实施步骤如下：网络中每个节点广播自身等级和ID号、自身所在的簇号，并设置定时器T1。T1的时间长度应使广播信息能够往返于监测网络中的任一节点为宜。节点仅对同簇内比自身等级低的节点进行反馈，反馈信息包括自身等级和ID号。在定时器T1时间内，如节点i在定时器T1结束时收到同簇内比自身等级高的节点的反馈信息，则转为簇内成员节点，等待接收簇首当选的消息；如节点i在定时器T1结束时未收到任何反馈信息，则表明自己为本轮次本簇等级最高的节点，随即向簇内其余节点广播当选簇首的消息和自身ID号，并设置定时器T2。T2的时间长度应使广播信息能够往返于网络中的任一节点为宜。簇内成员节点收到簇首的当选消息后，向簇首发送请求加入信息，加入信息包括自身ID号和等级；簇首根据成员节点的加入信息确定本簇的成员个数，根据成员节点等级高低制定不同时隙长度的时分多址(TimeDivisionMultipleAccess,TDMA)表广播给成员节点；等级越高的成员节点分配到的TDMA时隙越长。当簇内所有成员节点接收到入簇确认信息和TDMA表，簇建立完成。

2.3 数据传输

成员节点与簇首，簇首与基站间均采用单跳通信。簇内成员节点在自己的TDMA时隙发送监测信息给簇首。为避免不同簇中成员节点的TDMA时隙冲突，成员节点在发送信息后将对信道进行检测，如果发现通信冲突，等级高的节点将停止发送数据，让出信道，让等级低的节点优先与自身簇首通信，确保等级低的节点尽量一次性与自己的簇首通信成功。由于在TDMA时隙分配时高等级节点分得的时隙较长，在发生冲突后退出信道竞争的高等级节点随机等待Tx时间后(Tx为远小于该节点分得的TDMA时隙长度的一个随机数)，继续同簇首通信，同时按上述策略减少不同簇中成员节点的通信冲突。如果发生冲突的节点等级相同，它们均随机等待Tx后再向自己的簇首发送信息。簇首收集、汇总、融合成员节点信息后上传给基站，直到本轮时间Tr结束(Tr应远大于T1和T2)，进行下一轮自适应分簇、簇首选举和簇建立、信息传输，直到节点全部死亡，网络寿命终止。

3 仿真验证与分析

为验证ACA_G算法，使用OMNeT++仿真软件对其进行仿真验证，并使用Matlab进行数据分析。为验证ACA_G算法对网络移动特性的性能，将其与LEACH-Mobile算法进行对比实验；为验证ACA_G算法对网络异构特性的性能，将其与DEEC算法进行对比实验。其中：基站位于方形网络监测区域中心，能量无限大；其余节点初始位置随机分布在网络监测区域内。在网络监测区域四周边界处等间距部署12个信标节点用于节点定位。节点通信能耗模型、移动模型参见1.2、1.3节。网络的异构性主要体现为能量异构，如图3～5所示，图中节点颜色越深表示能量越高。其余实验参数设置如表1所示。根据以上仿真条件，每个实验在相同的条件下进行500次实验，然后取其整数平均值。为简化仿真，不考虑节点因移动带来的能耗。并假设每个成员节点均向簇首发送4kb的数据，无论簇内成员节点数目为多少，簇首将其成员节点的数据压缩为4kb数据转发给基站，簇内数据融合能耗设定为5nJ/b。ω1=0.54，ω2=1.26，ω3=1。

3.1 网络寿命情况

由于WSN布置一般存在冗余节点，只要能保证一定比例的节点存活，就能覆盖监测区域并上传监测信息到基站，因此本文中网络寿命定义为从网络运行开始到半数节点死亡的时间。当节点能耗等于或小于0时表明节点死亡。由于图6(a)～(d)给出了节点移动速度v分别为0m/s、0.2m/s、0.4m/s、0.6m/s时的节点死亡发生的轮次。其余实验参数设置如表1所示。

当节点随机移动速度为0m/s时，运用ACA_G算法、LEACH-Mobile算法和DEEC算法进行分簇，网络中半数节点死亡分别发生在2 733轮、1 767轮、1 909轮，如图6(a)所示。运用ACA_G算法分簇后的网络，半数节点死亡时间比运用LEACH-Mobile算法和DEEC算法分簇的WSN分别延长了54.7%和43.2%。

当节点随机移动速度为0.2m/s时，运用ACA_G算法、LEACH-Mobile算法和DEEC算法进行分簇，网络中半数节点死亡分别发生在2 098轮、1 603轮、1 491轮，如图6(b)所示。ACA_G算法分簇后的网络，半数节点死亡时间比LEACH-Mobile算法和DEEC算法分簇的WSN分别延长了30.9%和40.7%。

当节点随机移动速度为0.4m/s时，运用ACA_G算法、LEACH-Mobile算法和DEEC算法进行分簇，网络中半数节点死亡分别发生在1 733轮、1 080 轮、529轮，如图6(c)所示。运用ACA_G算法分簇后的网络，半数节点死亡时间比运用LEACH-Mobile算法和DEEC算法分簇的WSN分别延长了60.5%和227.6%。

当节点随机移动速度为0.6m/s时，运用ACA_G算法、LEACH-Mobile算法和DEEC算法进行分簇，网络中半数节点死亡分别发生在1 106轮、363轮、80轮，如图6(d)所示。运用ACA_G算法分簇后的网络，半数节点死亡时间比运用LEACH-Mobile算法和DEEC算法分簇的WSN分别延长了204.7%和1 382.5%。

图6 异构移动WSN环境下的网络寿命示意图

3.2 网络数据吞吐量

图7给出了上述仿真条件下网络数据吞吐量随轮数的变化情况。

图7 异构移动WSN环境下的网络数据吞吐量示意图

当节点以随机移动速度在0～0.6m/s范围内以0.2m/s递增时，截至网络寿命终止，运用上述三种算法进行分簇的WSN，其网络数据吞吐量都有所降低，但运用ACA_G算法分簇的网络，其数据吞吐量仍高于其余两种算法，如表2所示。当v=0m/s时，运用ACA_G算法分簇的网络，其网络数据吞吐量分别是运用LEACH-Mobile算法、DEEC算法分簇的网络的2.24倍、2.11倍；当v=0.2m/s时，运用ACA_G算法分簇的网络，其网络数据吞吐量分别是运用LEACH-Mobile算法、DEEC算法分簇的网络的1.15倍、1.24倍；当v=0.4m/s时，运用ACA_G算法分簇的网络，其网络数据吞吐量分别是运用LEACH-Mobile算法、DEEC算法分簇的网络的1.79倍、3.67倍；当v=0.6m/s时，运用ACA_G算法分簇的网络，其网络数据吞吐量分别是运用LEACH-Mobile、DEEC算法分簇的网络的2.60倍、8.24倍。

表2 截至网络寿命终止的网络数据吞吐量

3.3 结果分析

由上述仿真结果可知，当节点移动速度在0～0.6m/s范围内越来越快时，网络拓扑变化也越快；分别运用三种算法分簇后，节点的死亡速度均在加快，与LEACH-Mobile算法和DEEC算法相比，本文算法的半数节点死亡时间明显滞后，网络寿命更长，网络数据吞吐量更多。这是因为在LEACH-Mobile算法中，簇首是随机选举产生的，因此在能量异构的网络中，很可能是一些低能量节点来当选簇首，这样势必造成这些低能量节点能量消耗过快，从而加速它们的死亡。DEEC算法则是选举剩余能量高的节点当选簇首，但在异构网络中，由于监测对象不同，存在剩余能量大同时能量消耗也快的节点，从网络整体性能来看，这类节点并不是簇首的最佳选择。同时节点通信能耗与通信距离成正比，像DEEC算法这样仅仅以剩余能量为标准来选举簇首在实际应用中是不合理的，同时，DEEC算法并无应对节点移动的机制，因此，在节点静止时，其性能略优于LEACH-Mobile算法，但节点移动速度加快时，其性能却逊于LEACH-Mobile算法。ACA_G算法通过自适应分簇克服节点移动性带来的网络拓扑结构变化影响，均衡网络簇首数目和簇规模，综合考虑节点剩余能量、能量消耗速率、到基站的距离、到簇内其他节点的距离计算节点等级；且ACA_G算法通过选举簇内等级最高的节点为簇首，均衡节点能量消耗、延长网络寿命、提高网络数据吞吐量。因此，较LEACH-Mobile算法和DEEC算法，本文提出的ACA_G算法具有明显优势。

4 结语

本文提出的基于节点等级的自适应分簇算法ACA_G，通过自适应分簇、选举簇内等级高的节点为簇首等措施，分别解决WSN异构性和移动性对网络寿命、网络数据吞吐量带来的影响。实验结果表明，在节点移动速度0～0.6m/s的能量异构WSN环境下，与LEACH-Mobile算法和DEEC算法相比，本文算法优势明显。下一步应进行算法参数优化，如参数ω1、ω2、ω3的取值等，进一步提高算法性能。

)

[1]DONGM,OTAK,LIUA.RMER:reliableandenergy-efficientdatacollectionforlarge-scalewirelesssensornetworks[J].IEEEInternetofThingsJournal, 2016, 3(4): 511-519.

[2] 赵海军,崔梦天,李明东,等.基于改进的洪泛广播和粒子滤波的无线传感器网络节点定位[J].计算机应用,2016,36(10):2659-2663.(ZHAOHJ,CUIMT,LIMD,etal.Nodelocalizationbasedonimprovedfloodingbroadcastandparticlefilteringinwirelesssensornetwork[J].JournalofComputerApplications, 2016, 36(10): 2659-2663.)

[3]MANNPS,SINGHS.Improvedmetaheuristicbasedenergy-efficientclusteringprotocolforwirelesssensornetworks[J].EngineeringApplicationsofArtificialIntelligence, 2017, 57: 142-152.

[4] 苏金树，郭文忠，余朝龙，等.负载均衡感知的无线传感器网络容错分簇算法[J].计算机学报,2014,37(2):445-456.(SUJS,GUOWZ,YUCL,etal.Fault-toleranceclusteringalgorithmwithload-balanceawareinwirelesssensornetwork[J].ChineseJournalofComputers, 2014, 37(2): 445-456.)

[5]HEINZELMANW,CHANDRAKASANA,BALAKRISHNANH.Energy-efficientcommunicationprotocolforwirelessmicrosensornetworks[C]//HICSS’00:Proceedingsofthe33rdHawaiiInternationalConferenceonSystemSciences.Washington,DC:IEEEComputerSociety, 2000, 8: 8020.

[6]LINDSEYS,RAGHAVENDRACS.PEGASIS:power-efficientgatheringinsensorinformationsystems[C]//Proceedingofthe2002IEEEAerospaceConference.Piscataway,NJ:IEEE, 2002: 1125-1130.

[7]GURRUTXAGAI,ALBISUAI,ARBELAITZO,etal.SEP/COP:anefficientmethodtofindthebestpartitioninhierarchicalclusteringbasedonanewclustervalidityindex[J].PatternRecognition, 2010, 43(10): 3364-3373.

[8]ASLAMM,MUNIREU,RAFIQUEMM,etal.Adaptiveenergy-efficientclusteringpathplanningroutingprotocolsforheterogeneouswirelesssensornetworks[J].SustainableComputing:InformaticsandSystems, 2016, 12: 57-71.

[9]SINGHS,MALIKA,KUMARR.EnergyefficientheterogeneousDEECprotocolforenhancinglifetimeinWSNs[J].EngineeringScienceandTechnology,anInternationalJournal, 2017, 20(1): 345-353.

[10]GUPTAV,PANDEYR.Animprovedenergyawaredistributedunequalclusteringprotocolforheterogeneouswirelesssensornetworks[J].EngineeringScienceandTechnology,anInternationalJournal, 2016, 19(2): 1050-1058.

[11]KIMDS,CHUNGYJ.Self-organizationroutingprotocolsupportingmobilenodesforwirelesssensornetwork[C]//IMSCCS’06:Proceedingsofthe2006FirstInternationalMulti-SymposiumsonComputerandComputationalSciences.Piscataway,NJ:IEEE, 2006: 622-626.

[12]AMINED,NASSREDDINEB,BOUABDELLAHK.Energyefficientandsafeweightedclusteringalgorithmformobilewirelesssensornetworks[J].ProcediaComputerScience, 2014, 34: 63-70.

[13]AMINED,NASR-EDDINEB,ABDELHAMIDL.Adistributedandsafeweightedclusteringalgorithmformobilewirelesssensornetworks[J].ProcediaComputerScience, 2015, 52(34): 641-646.

[14]ZHANGD-G,ZHUY-N,ZHAOC-P,etal.Anewconstructingapproachforaweightedtopologyofwirelesssensornetworksbasedonlocal-worldtheoryfortheInternetofThings(IOT) [J].ComputerandMathematicswithApplications, 2012, 64(5):1044-1055.

[15]ZORZIM,GLUHAKA,LANGES,etal.Fromtoday’sINTRAnetofthingstoafutureINTERnetofthings:awireless-andmobility-relatedview[J].IEEEWirelessCommunications, 2010, 17(6): 44-51.

[16] 肖竹，王东，李仁发，等.物联网定位与位置感知研究[J].中国科学：信息科学,2013,43(10):1265-1287.(XIAOZ,WANGD,LIRF,etal.Localizationandnodeslocation-awareinInternetofthings[J].SCIENTIASINICAInformationis, 2013, 43(10): 1265-1287.

[17]MANZOORB,JAVAIDN,REHMANO,etal.Q-LEACH:anewroutingprotocolforWSNs[J].ProcediaComputerScience, 2013, 19: 926-931.

[18] 沈永增，陈宣扬，贾莲莲.一种事件驱动型无线传感器网络的分层路由算法[J].计算机系统应用,2011,20(8):81-85.(SHENYZ,CHENXY,JIALL.Hierarchicalroutingalgorithminevent-drivenwirelesssensornetworks[J].ComputerSystems&Applications, 2011, 20(8): 81-85.)

[19] 唐加山，王燕.无线传感器网络中改进的EEUC路由协议[J].重庆邮电大学学报：自然科学版,2013,25(2):172-177.(TANGJS,WANGY.ImprovedEEUCroutingprotocolforwirelesssensornetworks[J].JournalofChongqingUniversityofPostsandTelecommunications(NaturalScienceEdition), 2013, 25(2): 172-177.)

[20]KUMARD,ASERITC,PATELRB.EEHC:energyefficientheterogeneousclusteredschemeforwirelesssensornetworks[J].ComputerCommunications, 2009, 32(4): 662-667.

[21]SILVART,COLLETTIRR,PIMENTELC,etal.BETArandomwaypointmobilitymodelforwirelessnetworksimulation[J].AdHocNetworks, 2016, 48: 93-100.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(61302175),theYouthScienceFoundationofLogisticalEngineeringUniversity(X2050114).

XIAO Wei, born in 1982, Ph. D., lecturer. Her research interests include wireless sensor network, Internet of things, digital signal processing.

TU Yaqing, born in 1963, Ph. D., professor. His research interests include intelligent control, signal processing.

An adaptive clustering algorithm based on grades for wireless sensor networks

XIAO Wei*, TU Yaqing

(DepartmentofLogisticalInformation&LogisticsEngineering,LogisticalEngineeringUniversity,Chongqing401311,China)

To solve the short life time and low network throughput problems caused by the heterogeneity and mobility of Wireless Sensor Network (WSN) clustering algorithm, an Adaptive Clustering Algorithm based on Grades (ACA_G) was proposed. The proposed algorithm was run on rounds, which was composed of three stages: the adaptive clustering stage, the cluster construction stage and the data transmission stage. In the adaptive clustering stage, every partition may be subdivided or united adjacently according to the change of the number of nodes in each partition to keep an appropriate number of nodes in it. The adaptive clustering measure could be able to solve the unreasonable problems of the number of cluster-heads and the scale of clusters caused by the node mobility in WSN. In order to deal with the phenomena of some nodes died too fast and the life time of WSN was shortened caused by the heterogeneity in WSN, the node with the highest grade was selected as the cluster-head in the cluster construction stage. In the WSN application, the grade of each node was calculated according to the node residual energy, the speed of energy consumption, the distance between the node and the base station, the accumulated distance between the node and other nodes in the same cluster. The experiment was simulated by OMNeT++ and Matlab on a WSN with energy heterogeneity, in which node’s mobile speed is 0～0.6 m/s randomly. The experimental results show that, compared with the Low Energy Adaptive Clustering Hierarchy -Mobile (LEACH-Mobile) algorithm and the Distributed Energy-Efficient Clustering (DEEC) algorithm, the life time of WSN clustered by the proposed algorithm is 30.9% longer than the other two algorithms, its network throughout is 1.15 times at least as much as the other two algorithms.

adaptive clustering; grade; Wireless Sensor Network (WSN); energy heterogeneity; mobility

2016- 10- 11;

2017- 01- 08。

国家自然科学基金资助项目(61302175)；后勤工程学院青年科学基金资助项目(X2050114)。

肖玮(1982—)，女，重庆人，讲师，博士，主要研究方向：无线传感器网络、物联网、数字信号处理; 涂亚庆(1963—)，男，重庆人，教授，博士，主要研究方向：智能控制、信号处理。

1001- 9081(2017)06- 1532- 07

10.11772/j.issn.1001- 9081.2017.06.1532

TP393.0

A