基于动态分簇的集中式数据存储算法

魏瑜瑶， 陈宏滨

(桂林电子科技大学 信息与通信学院，广西 桂林 541004)

无线传感器网络[1](wireless sensor networks，简称WSNs)产生的数据增长迅速，因此数据的存储对于资源有限的传感器网络是一个重要的研究课题。无线传感器网络中的数据存储[2]，根据存储位置的不同分为集中式存储[3]、本地存储和分布式存储。集中式存储中所有采集到的感知数据都被传输到sink节点，查询直接从sink节点获取数据。因为sink节点的能量和存储空间不受限制，数据可以长时间保存，并且查询便利，所以适用于查询相对频繁的网络，缺点是sink节点周围节点的数据会快速耗尽，形成网络瓶颈。本地存储中传感器产生的感知数据存储在节点自身的存储器，但用户的查询请求在网络中使用泛洪路由[4]，能量消耗过多，查询时间长，节点死亡导致数据丢失。在分布式存储[5-7]中，感知到的数据不一定存储在本地，而存储在由某种机制确定的其他节点，查询请求使用相同的机制路由到存储节点获取数据，从而避免了泛洪，大量相同类型的数据产生会导致相应的存储节点出现热点问题，并且复杂的信息中介机制也会耗费额外的能量。

从网络拓扑结构的角度，可以将无线传感器网络的路由协议分为平面路由协议和层次路由协议[8]。层次路由在提高无线传感器网络的能量有效性以及网络扩展方面具有极大优势，适合无线传感器网络的实际应用。经典的层次路由协议是LEACH协议[9]，它将网络中的节点分为若干簇，每簇有一个簇头收集和处理簇内的数据，簇头周期性地发送融合处理后的数据到sink节点。因为数据融合后传送到sink节点可以减少数据的传输量，从而节省网络的能耗，所以LEACH协议也适用于无线传感器网络的集中式数据存储。已有很多文献针对LEACH协议的簇头优化[10]和传输数据的路径进行优化[11]，为此，从组簇角度改进LEACH，提出一种基于动态分簇的集中式数据存储算法。

1 系统模型

基于动态分簇的集中式数据存储算法的存储节点和查询节点均为sink节点，选取的簇头为簇内数据的暂时存储节点，周期性地向sink节点发送所收集数据。

1.1 网络模型

N个传感器节点随机分布在M×M的正方形区域，针对此网络给出如下假设：

1)传感器节点部署后不再移动；

2)网络中只存在一个sink节点，部署在一个固定位置，通过其发起查询请求，且sink节点的能量和存储容量不受限；

3)除sink节点外，其他节点是同构的，且具有相同的初始能量、存储容量和计算能力；

4)簇内节点到簇头节点、簇头节点到sink节点都是单跳，节点可根据距离调整无线发射功率。

1.2 代价模型

1)节点i单位时间采集数据的存储代价为

Cstore(i)=rd(i)sdC(i,h)+αrd(i)sdC(h,o)，

(1)

其中：rd(i)为节点i单位时间内采集感知数据的次数；sd为每次采集到的感知数据；C(i,h)为节点i传输单位数据到簇头h的代价，包括节点i和簇头h的通信代价；C(h,o)为簇头h传输单位数据到sink节点o的通信代价；α∈(0,1]为数据融合比率，用来模拟数据融合的效果。节点i的存储代价由节点传输数据到簇头和簇头传输融合后的数据到sink节点的代价共同决定。

2)网络中节点i和j之间的通信代价与路由路径长度成正比，路由路径长度定义为欧氏距离。两节点之间的距离越大，通信代价越大。

2 基于动态分簇的存储算法

基于动态分簇的数据存储算法基于LEACH协议，LEACH中网络按“轮”运行，每轮由簇的建立和稳定2个阶段组成。在建立阶段，网络完成簇头的选取和簇的自组织形成；稳定阶段中，簇成员按照轮流工作机制发送数据给簇头，簇头将收集的簇内数据进行融合处理后传输给sink节点。稳定工作一段时间后，进行下一轮的簇头选取和簇的形成，开始新一轮的网络运行，直到网络生命周期停止。本算法同样分为簇头选取、簇的形成和稳定工作阶段，簇头的选取在LEACH的基础上考虑了节点的剩余能量，簇形成阶段与LEACH的有所不同，簇形成根据距离簇头的远近和设置的存储代价作为判断条件进行初步组簇，然后考虑簇成员数目进行簇成员的动态调整，调整之后分簇成功，进入簇的稳定工作阶段。

2.1 簇头的选取机制

在分簇的网络结构中，簇头不仅采集自身产生的感知数据，还作为簇成员数据的临时存储节点，将收集的数据进行处理和融合，并将融合后的数据发送给sink节点集中存储，簇成员将采集的感知数据在规定的时隙内发送数据给所属簇头，所以簇头比簇成员要完成更多的任务，能量消耗得更快。LEACH中，簇头的选取是随机的，未考虑节点的剩余能量，若能量较低的节点被选为簇头，会导致节点更快死亡，因此簇头的选取原则应考虑节点当前的能量。选取簇头的阈值计算式为

(2)

其中：p为簇头占比；r为当前轮数；G为当前轮转周期内未当选过簇头的节点集合；Ei,res为节点i当前的剩余能量；Einit为节点的初始能量。

当节点i产生的随机数小于阈值T(i)时，节点i成为簇头。因为阈值公式中加入了节点剩余能量的因素，所以能量大的节点有更大概率成为簇头，从而改善能量较小的节点成为簇头的情形，使得网络中的负载能够均匀分摊在每个节点上，延长网络的生命周期。

2.2 簇形成阶段

2.2.1 簇初步形成

节点当选为簇头后，在网络中广播自己成为簇头的消息，等待簇成员的加入。在该阶段中，引入节点的存储代价模型。网络中已经得到k个簇头的集合为{h1,h2,…,hk}，非簇头节点通过接收每个簇头发来的消息，能够得到簇头与节点的距离为{d1,d2,…,dk}，找到距离最近的簇头hx(1≤x≤k)，判断节点i通过簇头hx的存储代价Cstore,hx(i)是否小于节点i直接将数据存储到sink节点的代价Cstore,sink(i)。判断条件为

Cstore,hx(i)

(3)

其中：

(4)

Cstore,sink(i)=rd(i)sdC(i,o)。

(5)

若满足式(3)的判断条件，则选择加入簇头hx，成为其备选簇成员；若不满足该条件，则寻找距离该节点次近的簇头，满足条件即可加入。若节点i发现所有簇头对应节点都不满足式(3)条件，则加入距离最近的簇头成为备选簇成员。

加入节点的存储代价的判断条件，使节点通过簇头传送数据到sink节点是有效的。有的节点通过距离最近的簇头的存储代价并不满足式(3)，可通过次近簇头达到条件。如果节点距离簇头过远，存储代价的判断条件亦不满足。这是因为节点通过簇头传送数据到sink节点的存储代价综合考虑了节点到簇头和簇头到sink节点的通信代价。

经过初步分簇，簇头hj(1≤j≤k)已经具有备选簇成员的基本信息，备选簇成员数为hj,num，进行簇成员的动态调整，确定最终簇成员。

2.2.2 簇成员的动态调整

当簇规模过大时，簇头的能量消耗大，网络中的节点负载不均衡，所以对每个簇的簇成员进行动态调整，簇内的备选簇成员节点选择性退出或簇内加入节点，改善网络中簇规模过大或过小的情况，进而实现簇与簇之间的能耗均衡。

簇成员数阈值为：

(6)

(7)

其中λ和η为预先设定的簇成员数的调整因子。当hj,num>V1时，即簇头hj所拥有的备选簇成员个数超过阈值V1，簇hj为较大簇；当hj,num

初步分簇后，如果较大簇和较小簇都存在于网络中，首先进行较大簇内簇成员的调整。实现步骤为：

1)当簇hj为较大簇时，需要节点的退出使得该簇变为正常簇。退出的节点i可加入簇hz满足的条件为：

(8)

簇hz是正常簇或极小簇，并且退出的节点i通过簇头hz的存储代价小于或等于通过原簇头hj的存储代价。簇hj可退出的节点数为t1，退出t1个节点可使较大簇hj变为正常簇，簇hz可加入的个数为j1，节点加入后不能使其变成较大簇。

2)簇头hj找到距离最近的hz，簇hz是正常簇或极小簇，计算可加入簇hz的节点数。簇头hj找出距离簇头hz较近且满足退出条件的节点，向其发出转换簇头消息，得到消息的节点解除原簇头hj的备选簇成员关系，成为簇头hz的备选簇成员。若退出节点达到t1，则在该阶段簇hj已经退出完毕;若未达到t1，找到距离次近的极小簇或正常簇，节点继续退出，直到退出节点数达到t1。

3)当簇hj节点退出t1，该簇已变成正常簇，在网络中广播簇成员变更消息，等待其他簇的节点调整；当较大簇hj遍历其他簇后，发现未成功退出t1个节点后，不再参与其他簇的动态调整，向现有的备选簇成员发送允许加入消息，备选簇成员成为簇hj的最终簇成员，该簇分簇成功，在网络中广播成簇成功消息，簇hj进入数据的采集和存储阶段。

如果较大簇都动态调整后，较小簇还存在于网络中，应进行较小簇内簇成员的调整。实现步骤为：

1)当簇hj为较小簇时，需要节点的加入使得该簇变为正常簇。加入节点所在的簇hz应满足的条件为：

(9)

簇hz是正常簇，并且被选簇成员节点i通过簇头hj的存储代价小于或等于通过原簇头hz的存储代价。簇hj节点可以加入的节点数为j2，加入j2个节点可以使较小簇hj变为正常簇，簇hz可以退出的节点为t2，节点退出后不能使其变成较小簇。

2)簇头hj找到距离最近的hz，簇头hz计算出可以加入簇hj的节点数，簇头hz找出距离簇头hj较近且满足退出条件的节点，向其发出转换簇头消息。若节点加入数已经达到j2，则该阶段簇hj已经补充完毕；若未达到j2，找到距离次近的正常簇，节点继续加入，直到节点加入数达到j2。

3)较小簇hj遍历过所有正常簇后，不论是否有满足条件的节点加入，都向现有的备选簇成员发送允许加入消息，现有的备选簇成员成为簇hj的最终簇成员，广播成簇成功消息，该簇进入数据的采集和存储阶段。

网络中所有较小簇都经过节点的调整后，所有簇将不再进行调整，网络全面进入数据采集和存储阶段。一轮过后，重新按照簇头选取、簇初步形成和簇成员的动态调整实现动态分簇，簇形成后再次进入簇稳定工作阶段。簇头收集的簇成员的数据暂时存储并融合处理，传送到sink节点进行永久存储，当查询时直接在sink节点内部检索。

3 仿真实验和结果分析

3.1 参数设置

为验证本算法的合理性和有效性，采用MATLAB平台进行仿真，同时在相同网络实验参数设置下，与LEACH、DCHS[12]协议下的集中式数据存储进行实验对比。采用文献[10]的能量消耗模型计算集中式存储的能量消耗。实验参数设定如下：在100 m×100 m的正方形区域中随机分布100个传感器节点，sink节点的坐标为(0,0)，节点的初始能量为0.5 J，无线收发电路的消耗能量Eelec为50 nJ/bit，自由空间模型中功率放大器的能耗比例系数εfs为10 pJ/(bit·m2)，多径模型中功率放大器的能耗比例系数εmp为0.001 3 pJ/(bit·m4)，数据包为4 000 bit，簇头占比p为0.05，代价模型中通信代价由传输1 bit数据的能耗来计算，rd为1，sd为1，α为0.5，簇成员数调节因子λ为0.25，η为0.25。

3.2 结果分析

图1为LEACH分簇的拓扑结构，图2为本算法的拓扑结构。从图1可看出，LEACH在簇形成时节点加入到距离最近的簇头，有较大簇和较小簇。从图2可看出，较小簇和较大簇已经变为正常簇，这是因为本算法在簇初步形成后，会进行节点的动态调整，经过簇成员的退出和重新加入，较大簇和较小簇变为正常簇，使得簇规模更加均匀。

图1 LEACH协议的拓扑结构

图2 本算法的拓扑结构

图3 3种算法的网络生命周期

图3为LEACH、DCHS和本算法的网络生命周期。DCHS协议是选簇头时考虑了节点的剩余能量，簇形成与LEACH一致。从图3可以看出，LEACH协议下的集中式数据管理，第1个节点死亡轮数为407，DCHS的第1个节点死亡轮数为512，本算法第1个节点死亡轮数为618，较LEACH和DCHS分别提高了51.8%和20.7%。这表明除了簇头的优化可以延长生命周期，本算法通过动态调整簇成员的退出或加入，优化簇规模，使得簇之间的负载更加均衡，因此大部分节点在生命周期后期死亡。

图4为LEACH、DCHS和本算法的网络总能耗。从图4可看出：DCHS比LEACH的能耗小，这是因为选取簇头时加入了节点的剩余能量，使得负载分摊在网络的每个节点；本算法比LEACH和DCHS总能耗都小，是因为除了在簇头选取阶段考虑节点的剩余能量的因素外，簇形成阶段综合考虑了存储代价和距离簇头远近的因素，使节点通过簇头发送数据到sink节点是有效的，同时动态成簇阶段分簇更加均匀，簇之间的能耗更加均衡，使得全网总能耗更低。

图4 3种算法的网络总能耗

4 结束语

为了均衡网络负载、延长网络的生命周期，提出一种基于动态分簇的集中式数据存储算法。选取簇头时考虑节点的剩余能量，可以均衡网络节点的负载；LEACH协议未对节点数据存储到sink节点进行优化，本算法中节点综合考虑存储代价和距离簇头远近的因素初步成簇，考虑簇规模不能太大也不能太小，动态调整簇成员节点的加入或退出，可以进一步优化簇的规模，使得簇与簇之间的能耗更加均衡；动态分簇成功后进入数据的采集和存储阶段。仿真实验结果表明，本算法相比于LEACH协议下的集中式数据存储算法，更加节省能量和均衡负载，从而延长网络的生命周期。但本算法只考虑簇头单跳到sink节点，更适合规模较小的无线传感器网络，将动态分簇应用到大规模网络是下一步的研究方向。