面向数据聚集有向分簇算法在传感器网络中的应用

麦晓冬

(广东轻工职业技术学院，广州510300)

传感器网络中使用面向数据聚集算法，网络能量的节省通常通过分簇机制来完成。TEEN、LEACH和HEED等是传统的分组算法。动态分簇算法和分布式成簇算法等是目前出现的一些新的分簇算法，这些新的算法优化了簇头选择和节点能耗均衡性等方面，但是节点能量利用效率和网络中存在的数据回传问题却没有得到很好的优化。文章提出的有向分簇算法能很好的解决这些问题，此算法的思想是有效控制簇的结构，使网络中所有的节点传输方向全部都沿着接近Sink的方向进行，这样数据回传造成的能量浪费问题得到了解决，所以节点能量利用效率得就提高了［1-2］。

1 有向分簇的相关内容

数据回传 网络中所有的节点传输方向全部都沿着接近Sink的方向进行，部分数据沿着远离Sink节点的方向传输。

无向分簇 网络中所有的簇的结构没有固定的方向，任何节点都能是簇头。

有向分簇 传感器网络中簇的结构有固定的方向，节点上报的全部数据都沿着接近Sink的方向传输，簇内其他节点的位置都没有簇头的位置离Sink节点近。

无向分簇示意图如图1所示，有向分簇的示意图如图2所示。

图1 无向分簇示意图

通过图1可以看出，节点的数据没有完全沿着Sink的方向进行传输，存在数据回传问题，通过图2可以看出没有节点的数据沿着远离Sink的方向传输，不存在数据回传问题［3-4］。

图2 有向分簇示意图

有向分簇时，不但簇的划分区域是固定的，而且簇头也是唯一的。为了解决簇头节点的能量消耗不均衡问题，动态划分簇的区域，节点可以处于不同的簇中，不但能担任某一簇簇头，而且还能是其他的簇的普通节点。

2 有向分簇的能耗分析

设节点x向节点y发送nbit的数据，两节点之间的距离为L，则在传输过程中发送

能耗为Qtr(n，L)可表示为:

式(1)中，Qel是接收能量损耗;Qam是功放能耗;L0是阈值;如果满足L＜L0的条件则采用自由空间模型，该模型功率放大能耗系数为εfs;L≥L0时采用多经衰减模型，该模型功率放大能耗系数为εmp。

接收能耗Qr(n，L)可表示为:

根据上面所述能耗模型，下面对有向分簇的能耗特点进行了一般性的分析。设把某个区域划分为1个簇，这个簇中包含x个传感器节点，其中传感器节点y和Sink节点的距离是最近的，此距离设为Li;设L0是无线传输距离阈值，并且不小于任何两个节点之间的距离;族内任何一个节点的数据采集量都是一样的，假设都是sbit，同时把这些数据都传输到 Sink 节点［5-6］。

设节点y是簇头，节点数量为x，如果采用有向分簇，则总的数据传输能耗可表示为:

式(3)中:Qi→y是节点i发送给y的数据收发能耗;Lyi是此两个节点的距离;Qy→k是y发送给Sink节点的能耗。

无向分簇时，任何节点都能是簇头，这和有向分簇是不一样的。设簇内的节点o(o≠y)为簇头，其中o不等于y，设L0为节点o到Sink节点的距离，同时满足L0=Ly+ΔL的条件。此时簇头o的数据传输能耗可表示为:

两种不同分簇方法下的数据传输能耗之差为:

因传感器节点两两之间距离均小于L0，故

3 DCA算法设计

3.1 全局分簇算法

只有满足以下2个条件才行。

条件1分簇时，所有节点必须要进行当前能量的检测，此能量为Qc(i)(i=1，2，…，n)，同时还需要设定相应定时器，设hi=h0［Q0-Qc(i)/Q0］是时间长度，此式中h0是基准时间，

条件2如果x节点未收到其他节点发送的申请簇头消息HAM(Head Application Message)，或者虽然收到了y节点的HAM消息，前提是定时器截止，但y节点与Sink节点的距离Lyl比i节点到Sink节点的距离Lxl远，则x节点传出本身的HAM消息。

全局分簇的算法流程如下。

(1)根据hi=h0［Q0-Qc(i)/Q0］设置一个计数器timer;

(2)根据L0调整the signal power;

(3)C_timer(i)=0;S_CQM(i)=0;Timer_exp=0;

(4)当 C_timer(i)!=1＆Timer_exp==0

(5)N_HAM(i)=0;

(6)等待并接受HAM信息;

(7)假如节点x接收到节点y的HAM消息则N_HAM(i)=1;

(8)如果 N_HAM(i)==1＆Lyl＜Lxl，那么给节点y发送1个CAM信息且设S_CAM(i)=1;

其他情况使N_HAM(i)=0;

(9)如果S_CAM(i)==1则C_timer(i)=1;

(10)如果当前时间h＞hi则Timer_exp=1;

(11)如果 C_timer(i)!=1＆Timer_exp==1

则节点x发送出去一个HAM信息;

3.2 局部调整策略

簇头向簇内节点转发任务都是在分簇之后进行的。个别簇头节点的能量消耗可能会比较大，这是由节点部署密度和部署位置不同造成的。更换簇头可以让族内节点能量消耗达到平衡。可以通过2种方式更换簇头，第1种更换方式是重启全局性的分簇算法，第2种更换方式是对局部簇头进行调整。在只有少部分簇头节点消耗能量较多的情况下，用第2种更换方式即可，但是如果大部分簇头的消耗能量都很多的时候，则需要使用第1种方式对簇头进行更换，具体的步骤分为3步［8］:各个簇头首先自查本身的消耗能量情况。设x是其中的某个簇头，Qr(x)是这个簇头的初始能量，当前剩余能量为Qc(x)，若Qr(x)-Qc(x)＞(Q0((为调节参数)，此时假设的簇头x会向其他的节点和Sink节点发送一个信号，这个信号就是其不再担任簇头;然后节点x会选择加入其他的族，这个族是靠近自己的邻近簇，节点x原先所在的簇会重新选择一个簇头;最后Sink节点会把不再担任簇头的节点数Ns统计出来，如果出现Ns＞1/2Nt的情况(Nt是簇头总数)，此时原来存在的簇结构就会自动解散，同时在全网内重新选举簇头。

4 测试结果

文章使用的测试平台是OMNeT++。设节点所分布面积为1 km×1 km;各个节点的初始能量是3 J，数据量为1 kbit/min;Qel=50 nJ/bit，无线传输距离阈值L0=100 m;功率放大能耗系数 εfs和 εmp的取值为:εfs=10 pJ/(bit·m2)，εmp=0.001 3 pJ/(bit·m4)。试验中，如果节点的剩下的能量非常低的时候，也就是还达不到原始能量的5%，此时这个节点会被认为死亡。

DCA算法的性能受到了调节参数λ影响，实验测试了该影响，结果如图3和图4所示。由此可知，DCA算法的稳定成簇的时间越与参数λ的值及节点剩余能量的均方差成正比。而且，DCA算法的性能也受节点分布密度的影响。当节点密度较大时，簇头的能量消耗速度与稳定成簇时间成反比。

通过对图3和图4的分析，λ的值设置为0.1～0.2较为合理。

图3 稳定成簇时间受参数λ的影响

图4 参数λ对能量均衡性的影响

权衡考虑参数λ的取值结合图3和图4，λ的值设置为0.1～0.2较为合理。

图5 算法能量效率比较

GESC、HEED和DCA算法三种分簇算法的能量效率比较结果如图5所示。当数据传输量一定时，DCA算法有较低总能耗，是因为该算法消除了数据回传造成的能量浪费。所以节点有较高的平均剩余能量。

由图6可以看出当网络运行一定时间后，对HEED算法和GESC算法来说，虽然节点出现死亡的时间靠后，但节点死亡率上升很快。主要原因是因为这两种算法中节点能量利用较均衡，但在数据回传中能量浪费较多，一段时间后，许多节点会死亡。

图6 节点存活率比较

DCA算法和HEED算法以及GESC算法相比来说较死亡率上升的速度是非常缓慢的，但是节点死亡时间较早，这对网络的影响是可以忽略不计的，由此可知该算法可以延长网络的生存周期。

5 结论

作者针对现存传统分簇方法中存在的数据回传问题，文章分析有向分簇的能量高效性，提出了DCA算法，经过仿真实验，证实该算法确实能克服以往算法存在的不足，提高能量的利用率，并将其应用于面向数据聚集的传感器网络中。

［1］Yu Ming，Kin K Leung，Aniket Malvankar.A Dynamic Clustering and Energy Efficient Routing Technique for Sensor Networks［J］.IEEE Trans on Wireless Communications，2007，6(8):3069-3079.

［2］张品，孙岩.一种新的无线传感器网络DV-Hop算法［J］.电子器件，2010，33(1):117-120.

［3］尚凤军，Mehran Abolhasan，Tadeusz Wysocki.无线传感器网络的分布式能量有效非均匀成簇算法［J］.通信学报，2009，30(10):34-43.

［4］Dimokas N，Katsaros D，Manolopoulos Y.Energyefficient Distributed Clustering in Wireless Sensor Networks［J］.Journal of Parallel and Distributed Computing，2010，70:371-383.

［5］胡倩，陈新.分簇无线传感器网络中密度感知的自适应占空比机制的研究［J］.传感技术学报，2013，26(1):105-109.

［6］柳絮，李金宝，纪守领，等.传感器网络簇头选举与调度策略研究［J］.电子学报，2010，38(8):1770-1775.

［7］沈琳，是湘全.无线传感器网络中数据融合对分簇网络寿命的影响［J］.电子器件，2009，32(2)43-46.

［8］Heinzelman W R，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wirelessmicrosensor Networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660-670.