一种可扩展的WSN节能分簇算法

王莹莹,郑永爱,王咏梅

(苏州高博软件技术职业学院,江苏 苏州 215163)

0 引言

在无线传感器网络(WSN,wireless sensor network)中，具有感知、计算及通信能力的传感器节点被部署在监控区域内，实现对特定物理量的采集，传感器节点自组织成网，最终将采集的数据传输到基站[1]。

在WSN中，大部分传感器节点采用电池供电，节点能量十分有限，若节点能量耗尽，将影响整个网络的运行。对于节点而言，其能量主要消耗在数据采集与数据传输过程中，而传输数据的能耗远远大于采集数据的能耗，因此利用有限的网络资源，在源节点与目的节点之间建立一条健壮的、节能的、高效的、低时延的路径，减少节点能耗、延长网络生命周期一直是WSN的研究热点[2-3]。

1 相关工作

根据拓扑结构不同，当前的路由协议主要分为平面路由与分层路由。在平面路由协议中网络中所有节点地位相同，节点数据经过多跳转发到达基站，网络健壮性好、易于维护，但当网络规模增大时，节点能耗与数据时延迅速增加，不利于网络扩展，已经不能应用于当前的大规模无线传感器网络中。而分簇路由以其良好的可扩展性、易维护性、低时延、高能效等特点，被广泛应用于大型无线传感器网络。

最经典的分簇路由是Heinemann等人提出的LEACH[4]分簇路由协议，其将网络划分为若干个簇，每个簇选举出一个簇首来负责簇内成员节点的管理与数据收集与转发；以“轮”作为网络的运行周期，每一轮更换一次簇首以均衡节点的能耗。但是LEACH仍存在许多缺点，例如：簇首的选举具有一定的随机性，无法保证簇首具有足够的能量完成簇内数据的收集与转发；节点分布的随机性，均匀分簇容易会导致簇首负载不均；簇首通过单跳的方式与基站通信，不适用于大规模网络。众多学者针对LEACH的缺点，提出了改进算法，为避免低能量节点被随机的选为簇首，文献[5]将节点的剩余能量引入到阈值公式中，缓解了低能量节点过早死亡的问题。EEUC[6]算法引入成簇半径的概念来控制簇的大小，使距离基站近的簇半径小，从而使簇首节约出能量用于数据的转发，由此来均衡节点的能耗。但是在大型的传感器网络中，节点并不是均匀分布的，在节点分布密集的区域，簇首的负载重，能量消耗大，EEUC算法依然存在节点能耗不均的状况。为了进一步均衡节点的能耗，文献[7]提出了一种非均匀分簇算法[8]，既考虑到节点的位置信息，又考虑到节点的分布密度情况。文献[9]引入“前置感知区域”的概念，在簇首节点的“前置感知区域”内根据节点的剩余能量以及位置信息选举附属簇首节点，减少了因为“能量回传”所造成的能量消耗，从而达到节约能耗的目的。文献[10]提出了一种提基于簇的无线传感器网络交会路由协议CRRP，用于缓解sink周围节点因转发任务重而能耗大的问题。

除此之外，众多学者将各种聚类算法应用在WSN的网络分簇中[11-14]，文献[15]采用k-means聚类算法进行簇首选举，并引入Mobile Agent对簇内数据进行收集以及融合处理。文献[16]将模糊逻辑的聚类算法用在分簇上，在均匀分环的基础上，将节点的能量、节点度、节点到基站的距离、环宽、启动能量等参数作为模糊规则器的输入，输出每一环的最优簇数以及节点成为簇首的竞争半径，从而进行不均匀分簇。文献[17]提出一种基于密度的聚类分析算法，其利用节点的局部密度差异来建立均衡分散的簇。文献[18]基于模糊规则算法考虑节点相对能量、相对密度以及相对中心度进行簇首选举，采用改进的蚁群算法进行簇间路由优化。

为了进一步减少数据传输过程中节点能量的消耗，同时兼顾节点间能耗的均衡以及网络的可扩展性，本文提出了一种可扩展的WSN分簇算法。在簇首选举阶段，综合考虑节点的剩余能量、节点度、价值度等因素；满足能量条件时，采用簇内簇首轮换的方式，减少成簇能耗；当新节点加入网络时，引入“入网许可值”的概念，来确定新节点要加入的簇。

2 网络模型与节点能耗模型

2.1 网络模型

为了方便研究，本文对无线传感器网络作如下假设：

1)节点随机分布在监控区域，一经部署位置不再发生变化，基站可以获知所有节点的位置信息；

2)网络中每一个节点都具有唯一标识的ID，节点初始能量、存储能力、处理能力、通信能力相同，节点可以感知自己的剩余能量，知道自己的位置坐标以及基站的位置坐标。

3)基站的位置固定，且计算能力以及能量不受限；

4)节点可以根据通信距离来调整通信功率的大小；

5)节点具有数据融合的能力，以减少需要传输的数据量。

2.2 节点能耗模型

如图1所示，本文采用文献[19]提出的一阶无线电模型，其中节点能耗包括：发射电路能耗、放大电路能耗以及接收电路能耗。

图1 一阶无线电模型

传感器节点发送kbit数据包的能耗为：

(1)

传感器节点接收kbit数据包的能耗为：

ERx(k)=k·Eelec

(2)

其中：d为数据的传输距离，Eelec为电路发送或接收单位bit数据的能耗，εfs与εmp分别为自由空间模型与多路径衰减模型功率放大所需要的能量，当传输距离小于d0时采用自由空间模型，当传输距离大于d0时采用多路径衰减模型，d0取值如公式(3)所示。

(3)

3 算法描述

3.1 网络分簇

1)网络候选簇首选举：

网络中候选簇首的选举采用公式(4)，T(i)为节点Ni的阈值，网络中的每个节点会产生一个0～1的随机数，与节点阈值进行比较，若随机数小于阈值则其被选择为候选簇首。

(4)

其中：P为节点当选为簇首的概率；Ei为节点Ni当前剩余能量，Eaver为当前网络中所有节点能量的平均值，剩余能量越大T(i)的取值就越高，节点被选中的概率就越大；r表示当前节点连续未当选簇首的轮数，r越大该节点被选为簇首的概率也就越大，r为0则表示该节点上轮刚刚当选过簇首，但是只要节点的剩余能量多，其可以继续被选作为簇首。

2)簇的组建:

候选簇首的选举完成之后，由普通节点根据其到候选簇首以和候选簇首到基站的距离来选择出其可以加入的簇首，然后根据可加入簇首的剩余能量、邻居节点度来确定最终要加入的簇首。其详细的步骤如下：

1)候选簇首广播自己的位置信息、剩余能量、邻居节点数。

2)普通节点根据公式(5)计算数据由簇首到基站的代价，选择代价值最小的3个候选簇首加入自己的候选簇首列表。

(5)

其中：dNi_CHj表示节点Ni到候选簇首CHj的距离，dCHj_BS表示候选簇首CHj到基站的距离。由公式(4)可知，数据传输所消耗的能量与数据的传输距离有关，簇内的通信距离一般较小，因此采用自由空间模型，将簇内通信代价最小问题转化为节点到簇首距离的平方值最小问题；簇首到基站的距离相对较远，因此采用多路径衰减模型，将簇首到基站通信代价最小问题转化为簇首到基站距离的四次方的最小化问题。

假设某个节点与其周围的候选簇首的分布如图2所示，根据公式(5)计算代价由小到大的顺序也是D、A、C、B，因此D、A、C三个候选簇首的信息被加入到该普通节点候选簇首列表中。

1.2 治疗方法 对照组患者采用甲氨蝶呤小剂量分次肌注联合米非司酮进行治疗，甲氨蝶呤剂量：0.4 mg·kg-1·d-1，5 d为一个疗程，米非司酮剂量100 mg，2次/d，连续服用3 d，剂量600 mg。观察组给予患者一次性甲氨蝶呤肌注给药联合米非司酮(100 mg，2次/d)进行治疗，甲氨蝶呤一次性剂量50 mg/m2，在患者给药4～7 d，如实验室检查血β-hCG下降幅度小于15%或持续上升，于第7天再次肌注同剂量甲氨蝶呤。

图2 簇首选择示意图

3)普通节点根据公式(6)从自己的候选簇首列表中选择ValueCHj取值最大的簇首作为自己的最终簇首。

(6)

其中：EChj为候选簇首CHj的当前剩余能量，Ech_aver为3个候选簇首能量的平均值，剩余能量越多ValueCHj的取值也就越大；NeiCH_Can(j)为候选簇首CHj的邻居节点的数量，Neiaver为3个候选簇首邻居节点的平均值。

4)普通节点加入选定的簇首，当所有的普通节点完成簇首选举时，未被选中的候选簇首和普通节点一样根据公式(5)与公式(6)选择簇首并加入。

5)簇的建立完成之后，为避免数据冲突，簇首为每一个成员节点分配TDMA时隙，成员节点根据时隙规则在规定的时隙与簇首进行通信。

其中，在簇首在时隙分配过程中所分配的时隙数大于簇内节点的数量，即预留若干时隙供新加入的节点的使用；当新节点申请入簇时，不需要等待当前簇周期的结束，也不要重新进行时隙的划分，既增加了网络的可扩展性，又提高了网络的运行效率，减少时延，节约能量。

3.2 簇内簇首调整

在每一轮簇首的选举以及簇的建立过程中，都需要广播消息以获取节点的信息，为了进一步减少能量消耗，本文所提算法采用簇内簇首轮换的方式。即当网络中所有簇首的能量都大于阈值Ea时，不需要在全网范围内重新进行簇首的选举。

在簇内数据收集的过程中，成员节点每轮向簇首发送自己的剩余能量信息，簇首计算自己的剩余能量是否大于簇内节点的平均能量，若大于则继续担任簇首，若小于根据簇内簇首选举方法进行新簇首的选择[14]，详细步骤如下所示。

(7)

(8)

其中：dij2为第i个簇内的第j个簇成员节点到其他成员节点距离平方的均值，(xj,yj)为该节点的位置坐标，Mi为第i个簇内的成员节点的个数，R为节点的通信距离，Eij表示第i个簇内的第j个簇成员节点的当前剩余能量，Ei_aver为簇内的平均能量值。由公式(7)(8)可知，剩余能量越多，与簇内通信代价越小，其被选为簇首的概率就会越大，该种簇内簇首轮换机制，既减少簇的重建所带来的能耗，又能保证节点能耗的均匀，防止个别节点因能耗过大而死亡。

2)当前簇首在簇内广播新簇首消息，并将TDMA时隙规则以及簇内成员的信息发送给新簇首，完成任务交接，当前簇首作为普通节点，沿用新簇首的时隙向新簇首发送数据。

3)簇内其他成员节点收到消息后，修改自己所维护的簇首信息，继续进行数据的采集与发送。

3.3 网络扩展

当新节点申请加入网络时，首先由新节点广播自己的加入请求消息，网络中的簇首收到请求消息后将自己的位置信息、簇内当前负载、剩余能量发送给新节点。新节点收到各簇首消息后，根据公式(9)选取Per(j)取值最大的簇首加入。

(9)

其中：dchj为新节点到簇首CHj的距离，Echj与Lchj分别为簇首CHj的剩余能量与当前负载即当前成员节点的个数，E0为节点的初始能量，1/p为网络内的平均簇成员数目。

新节点选定簇首后，向该簇首发送入网请求，簇首接受请求后，将预留的时隙分配给新节点，新节点正式成为簇成员开始进行数据的采集与发送。

4 仿真与分析

采用Python语言中的numpy、pandas库以及matplotlib库，对本文算法以及经典的LEACH、EEUC等算法在网络的生命周期、网络能耗以及节点能量的均衡性进行了对比以及可视化分析。

4.1 仿真环境与参数设置

仿真环境为100个节点随机分布在200*200的区域内，基站坐标为(100,200)，每轮簇首的数量占网络中存活节点的10%(p=0.1)。数据传输模型采用一阶无线模型，其中实验中涉及到的部分参其他数取值如表1所示。

表1 实验参数

4.2 实验结果分析

图3为网络运行到第10轮时节点的分布情况以及本文算法(AEECA)的成簇情况。由实验结果可知，簇首较均匀的分布在网络中，并没有出现簇首“扎堆”或“边缘化”的情况，负载相对比较均衡。这主要是因为在簇首的选举过程中不仅仅考虑到节点的剩余能量，还综合考虑了节点的位置信息、以及节点的邻居节点数量，使簇首的数量与节点的密度成正比。

图3 节点分布情况及成簇情况图

图4与图5分别为本文算法(AEECA)与LEACH算法、EEUC算法就网络生命周期指标以及网络中所有节点总能量所进行的仿真与对比。网络生命周期是衡量无线传感器网络质量的一个非常重要的指标。在本文的仿真实验中，以网络中节点的存活数量来表示网网络的生命周期。由仿真结果可知，3种算法的网络生命周期从长到短依次为AEECA、EEUC、LEACH。

图4 网络生命周期对比

图5 能耗对比

与LEACH算法比较，AEECA算法的能耗小的原因主要有以下几个：

1)在簇首选举过程中，LEACH算法每轮都要重新选择簇首，而AEECA采用的是一定条件下簇内簇首轮换的方式，节约了全网范围内进行簇首选举的能耗。

2)在簇的组建过程中，LEACH算法是节点选择距离自己近的簇首加入，而AEECA综合考虑了簇首距离基站的距离，簇首的剩余能量以及节点密度等因素，不仅可以促进节点间的负载均衡，还可以减少信息回传所带来的能耗。

图6对3种算法每轮的能耗作了仿真与对比，整体来看每轮能耗随着网络运行轮数的增加而减少，原因是网络中的存活的节点越来越少，另外LEACH算法每轮的能耗都比其他两种算法高，EEUC各轮的能耗比较均衡，AEECA大部分轮能耗维持在较低水平，小部分轮数能耗较高，原因是当簇内平均能耗低于阈值时，需要在全网范围内进行簇首选举，此时能耗则较高，其他轮则是采用簇内簇首轮换的方式进行的，能耗低于全网簇首选举。

图6 每轮能耗对比

综上所述，本文算法在网络分簇阶段，根据节点的剩余能量来进行候选簇首的选举，可以避免低能量节点当选簇首；在簇首的选举过程中，节点根据数据经各簇首转发至基站所经过路径的平方和，来选取转发代价最小的3个簇首作为自己的候选簇首，可以避免当簇首分布较偏的时候，数据因距离较远而带来的能耗过大问题。节点从3个候选簇首中，选取剩余能量大、邻居节点多的候选簇首作为自己的最终簇首，既保证了簇首具有较高的能量，又能保证簇首分布在节点相对集中的区域[20]。

为了增加网络的可扩展性，当新的就节点申请加入网络时，引入节点的入网许可值，综合考虑要加入簇的能量和距离，使得选择的簇头节点对于新入网节点而言，具有更好的健壮性。另外，基于簇的负载值的考虑，使得网络的负载分布更均匀。

5 结束语

本文在分析当前分簇算法的基础上，以减少能耗，增强网络的可扩展性为目的，提出了一种可扩展的无线传感器网络分簇算法，从网络分簇、簇内簇首选举、网络扩展3个部分对算法进行了描述与实验验证，结果表明本文所提算法可以较少网络能耗、均衡节点间的负载，延长网络的生命周期。