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所示。

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

${E_{{\rm{Tx}}}}(l,d) = \left\{ {\begin{array}{*{20}{l}} {l{E_{{\rm{elec}}}} + l{\varepsilon _{{\rm{fs}}}}{d^2},} & {d \le {d_0}}\\ {l{E_{{\rm{elec}}}} + l{\varepsilon _{{\rm{amp}}}}{d^4},} & {d > {d_0}} \end{array}} \right.$

(1)

${E_{{\rm{Rx}}}}(l,d) = {E_{{\rm{elec}}}}l$

(2)

其中:E_elec为发送或接收电路的能耗，E_elec=5 nJ/b；ε_fs为自由空间信道功率放大器能耗，ε_fs=10 pJ/(b·m²)；ε_amp为多径衰落信道功率放大器能耗，ε_amp=0.001 3 pJ/(b·m⁴)；${d_0} = \sqrt {{\varepsilon _{{\rm{fs}}}}/{\varepsilon _{{\rm{amp}}}}} $。

1.3 节点移动模型

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

2 算法原理

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

2.1 自适应分簇

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

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

令第r轮第m个子区域内节点数目为N_m^r，该区域节点数目的上限阈值和下限阈值分别为N_max^r和N_min^r，如式(3)、(4) 所示：

$N_{\max }^r = \left\lfloor {{\omega _2}{N_r}/{M_{r - 1}}} \right\rfloor $

(3)

$N_{\min }^r = \left\lfloor {{\omega _1}{N_r}/{M_{r - 1}}} \right\rfloor $

(4)

其中：m∈[1, M_r-1]，M_r-1表示网络监测区域第r-1轮划分的子区域总数，M_r-1、r、m为大于0的整数；N_r表示第r轮网络中存活节点的总数; ω₁和ω₂表示权重系数，ω₁∈[0, 1]，ω₂∈[1, 2]；符号$\left\lfloor \quad \right\rfloor $表示取整数运算。

若N_m^r满足式(5) 条件，表明该子区域内节点密度过大，按一定原则，如从左到右-从上到下原则，将该子区域进一步细化，直到细化后每个所述子区域内的节点数目$N{{_{m}^{r}}^{\prime }}$满足式(6) 条件为止。子区域细化前后示意图如图 4所示。图 4(a)给出了细化前的节点分布图，在灰色的两个子区域中，节点数目过多，密度过大，如使该区域内的节点自成一簇，势必造成簇规模过大，簇首能量消耗过快；图 4(b)给出了细化后的节点分布图，原节点数目过多的2个子区域被分为4个区域，将该子区域内所有节点成簇，簇规模较细化前更合理。

$N_m^r > N_{\max }^r$

(5)

$N_{\min }^{r}\le N{{_{m}^{r}}^{\prime }}\le N_{\max }^{r}$

(6)

$N_{\min }^r > N_m^r$

(7)

若N_m^r满足式(7) 条件，表明该子区域内节点密度过小，将其与就近子区域合并，直到合并后的子区域中节点数目$N{{_{m}^{r}}^{\prime }}$满足式(6) 为止。区域合并前后示意图分别如图 5所示。图 5(a)给出了合并前的节点分布图，灰色子区域中仅4个点，如使该区域内的节点自成一簇，势必造成簇规模过小，网络中簇首数目过多，资源浪费；图 5(b)给出了合并后的节点分布图，原节点密度少的子区域被合并到就近子区域，合并后的区域中节点数目将较合并前更合理。

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

2.2 簇建立

簇建立阶段的一个主要任务是选举簇首。由于网络中节点的异构性，不同类型节点的监测对象可能不同，能量消耗速率也可能不同。在实际应用中存在初始能量大但同时能量消耗速率也大的节点，如仅通过剩余能量的多少来选举簇首显然是不合理的。此外，根据1.2节所述的无线通信能耗模型，节点通信能耗与通信距离成正比，因此减小通信距离也是降低节点能耗的一条有效途径。综上所述，本文算法在簇首选举中综合考虑了本轮次节点的剩余能量，能量消耗速率，通信距离(具体包含到基站的距离、到簇内其他节点的距离)，按式(8) 计算节点i在第r轮中的等级G_i^r。选举本簇内等级最高的节点为第r轮本簇簇首。

$G_i^r = E_i^r(1 - {a_i}{t_r}) - {\omega _3}(L_i^r + D_i^r)$

(8)

其中：E_i^r表示第r轮中节点i的第r轮的剩余能量，E_i^r>0；a_i表示第r轮中节点i的能量消耗速率，a_i>0；t_r表示第r轮的时长，t_r>0；D_i^r表示第r轮中节点i到簇内其他节点的累计距离平方和；L_i^r表示第r轮中节点i到基站的距离平方；ω₃表示权重系数，ω₃∈(0, 1)。

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

2.3 数据传输

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

3 仿真验证与分析

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

3.1 网络寿命情况

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

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

当节点随机移动速度为0.6 m/s时，运用ACA_G算法、

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

3.2 网络数据吞吐量

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

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

3.3 结果分析

由上述仿真结果可知，当节点移动速度在0~0.6 m/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.6 m/s的能量异构WSN环境下，与LEACH-Mobile算法和DEEC算法相比，本文算法优势明显。下一步应进行算法参数优化，如参数ω₁、ω₂、ω₃的取值等，进一步提高算法性能。