PTTC：无线传感网络分簇算法*

王智超

(武昌理工学院 信息工程学院，湖北 武汉 430223)

PTTC：无线传感网络分簇算法*

王智超

(武昌理工学院 信息工程学院，湖北 武汉 430223)

分簇是延长无线传感网络寿命的有效技术。为此，提出了基于Prim的树簇拓扑的无线传感网络分簇PTTC算法。PTTC算法首先推导最优的簇数，再计算节点被选为簇头的平均概率。然后，结合节点的剩余能量以及被选为簇头的频率数选择簇头，最后利用Prim算法建立树，节点依据树传输数据，进而提高能量利用率，扩延网络寿命。仿真结果表明，提出的PTTC算法平衡了节点间的能量消耗，有效地延长了网络寿命。

无线传感网；簇；能量；树；普里姆算法

0　引言

无线传感网络 WSNs(Wireless Sensor Networks)中的传感节点通常以随机方式分布于网络，并且这些节点的能量供应具有有限性，且能量更换不便。这种能量的局限性影响了网络寿命。因此，能量有效利用是无线传感网络的研究热点[1-2]。基于簇的网络结构是延长网络寿命的有效算法。

文献[3]提出了基于低能量自适应簇结构算法(Low-Energy Adaptive Clustering Hierarchy，LEACH)，这是典型的簇结构算法。在LEACH中，传感节点划分为簇，每个簇选举一个簇头CH，其负责收集簇内其他节点的数据，并向基站传输。LEACH算法在选择簇头CH时，采用等概率算法，即每个节点被选举为簇头CH的概率相同，在选择簇头时并没有考虑节点的能量等其他信息。

文献[4]提出了EDACH(Energy-Driven Adaptive Clustering Hierarchy)算法。EDACH算法采用代理节点策略，一旦原簇头CH失效，代理节点就担任当前的簇头CH。随后，文献[5]提出了EECH(Energy Efficient Clustering Hierarchy)算法。EECH算法将能量高的节点赋予被选举为簇头CH的概率更高。此外，簇头CH采用多跳转发策略向基站传输数据。文献[6]提出了基于LEACH的改进算法EECHS。EECHS算法考虑了节点的剩余能量、距离信息选择簇头CH。然而，这些算法并没有从全局角度，考虑簇的分布情况。

据此，本文提出一种新的分簇 PTTC(Prim based Tree Topology Clustering algorithm for Wireless Sensor)算法。PTTC算法在选择簇头CH时，考虑了节点的剩余能量、节点被选举为簇头CH的频率以及被选举为簇头的概率。仿真结果表明，提出的PTTC算法能够有效地降低能量消耗，提高网络寿命，并提高数据传输效率。

1　约束条件及能量模型

1.1约束条件

考虑 N个传感节点si，i=1，2，…，N随机分布于监测区域。传感节点周期地形成簇，并且有足够的传输功率将数据传输至基站BS。所有传感节点是同构的，具有相同数据处理能力，并且每个节点具有唯一的识别号。基站没有能量限制，且一般远离监测区域。同时将时间划分等间隔的轮，每轮执行一次PTTC算法，并产生簇头。此外，网络寿命LT被定义为：

其中 rfirst_death表示网络内第一个失效节点所发生的轮数。

1.2能量模型

引用文献[6]的无线电模型。为了推导每类节点的能量消耗情况，基于传输距离的不同，采用两种信道模型：自由空间和多径衰落。相距为 d的两节点间传输 l bit的数据信息所消耗的能量：

其中 Eelec为运行发射器或接收器的能量消耗。dth为距离门限值，其决定信道模型。由于在同一簇内，簇头CH离簇内成员节点的距离小，一般采用自由空间模型，而簇头与基站BS相距较远，采用多径衰落模型。

相应地，节点接收l bit的消息所消耗的能量 ERx：

其中 εfs和 εmp分别为自由空间和多径衰落的放大器因子。在本文中，设定 Eelec=50 nJ/bit、εfs=10 pJ/bit/m2和 εmp= 0.001 3 pJ/bit/m4。此外，为了简化能量计算，假定所有消息包含相同的比特数，数据融合所消耗的能量 EDA=5 nJ/bit/signal。

2　PTTC算法

首先，计算最优的簇头CH个数。若簇头CH个数过少，一些传感节点需要向远处的CH传输数据耗，加大了能量消耗；反之，若簇头CH个数过多，多数节点需要与BS直接通信，也加速了能量消耗。因此，需要对簇头个数CH进行优化。

其次，每个传感节点成为簇头CH的概率应不相同，应依据各自节点的信息决定其概率。若低能量的节点被选举为簇头CH，由于簇头CH任务繁重，其能量将很快耗尽，这必然缩短了网络寿命。因此，需要依据最优的簇头CH个数和节点的剩余能量决定一个门限值，进而合理地选择簇头CH。

2.1最优簇头数 kopt

为了减少能量消耗，从簇头CH的能量消耗角度推导簇头CH个数的最优值。簇头CH承担了3项任务：数据接收、数据整合、将融合后的数据传输至基站BS。由于簇头CH与基站BS相距较远，采用多径衰落信道模型。据此，每轮簇头 CH消耗的能量 ECH：

其中l表示每个数据包中的比特数。N1是簇内的节点数。EDA表示融合数据所消耗的能量，dtoBS表示簇头 CH离基站的距离。

为了融合所有数据，每个簇头CH需要处理n/kopt个长度为 l的信号。每个簇内节点的平均数[7]：

其中 λ0、λ1分别表示簇头 CH的密度、节点密度。且 λ1= pλ，p=k/n。此外，λ=λ0+λ1是泊松分布密度。n=λ×A是节点数，其中A是监测方形区域的面积。k是簇头个数，p表示节点被选举为簇头CH的概率。

不失一般性，假定基站BS位于监测区域的中心。因此，簇头CH离监测区域的平均距离：

其中D1表示泊松分布变量，表征簇头CH离基站的距离，且(x，y)是簇头的位置坐标。PA表示在区域 A内簇头CH的概率密度。

依据式(5)和式(6)，式(4)可表示为：

由于每个簇内成员节点需要向它的簇头CH传输l bit的数据，假定它们间的距离表示为 dtoCH。不失一般性，dtoCH比较短，采用自由空间信道模型。因此，每个簇内成员节点所消耗的能量 Enon-CH：

其中 dtoCH[7]：

其中L1为泊松变量，表示簇内成员节点至簇头距离。因此簇内成员节点离簇头的平均距离E[L1]：

据此，每一轮内一个簇所消耗的能量 Ecluster：

一轮内所有簇所消耗的总能量 Etotal：

依据式(7)、式(11)、式(12)，式(13)可转换为：

需要得到最优的簇头个数，进而能量消耗最少。因此，对式(14)求关于k导数，并令其等于零：

由于n=λ(4a4)，可得。式(15)的解便是最优的簇头个数 kopt：

因此，节点成为簇头的概率 popt：

2.2簇头CH的选择

LEACH算法采用随机机制选择簇头CH，这使得簇头CH分布不均匀，也导致节点能量消耗不平衡，降低了网络寿命。为此，PTTC算法引用3个参数选择簇头CH。第一参数就是剩余能量，其次是轮数，最后是节点已被选为簇头的轮数。对于节点i，其被选为簇头概率T(i)：

其中：Cch表示目前节点被选为簇头的次数，Eresidual表示节点的剩余能量，Einit为节点的初始能量，r为轮数。一旦被选举为簇头CH，节点就向邻居节点广播通告消息Mes_adver。当其他节点接收了Mes_adver消息后，就向该簇头CH回复，并发送加入该簇消息Mes_join。接收了Mes_join消息后，簇头CH就依据Mes_join消息识别节点ID，并记录簇内成员节点号，最终形成簇。

2.3树的构建

形成簇后，再利用普里姆(Prim)算法构建树。假定N={V，E}表示连通网络。首先从一顶点h出发，再选择与它关联的具有最小权值的边(h，v)，然后将其顶点加入到生成树的顶点集合U中。以后每一步均从一个顶点在U中而另一个顶点不在U中的各条边中选择权值最小的边(u，v)，并把该边加入到生成树的边集中，把它的顶点加入到集合U中。一直重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。普里姆(Prim)算法建立最小spanning树的示例如图1所示。

图1　基于普里姆构建最小 spanning树的过程

在PTTC算法中，节点i的权值Weight(i)：

其中 ω1、ω2为权值系数，Eresidual(i)表示节点的剩余能量，d(i，CH)表示节点离簇头CH的距离。

利用Prim算法建立的树簇网络结构如图2所示。形成了树簇结构后，便可开始进行数据传输。叶节点向父节点传输数据。融合了自己数据后，父节点再将数据传输到它的父节点。

图2　树簇结构

3　性能分析

利用 MATLABR2012b建立仿真平台。考虑100 m× 100 m的区域，基站位于区域中心位置，具体仿真参数如表1所示。每次实验重复50次，取平均值作为最终数据。仿真时间为500 s。

表1　仿真参数

此外，选择 LEACH、EDACH、EECHS与 提 出 的PTTC算法进行同步仿真，比较这4个算法在失效簇头CH数、第一个节点失效所发生的轮数FND(First Node Die)和一半活动节点所在的轮数HNA(Half of the Nodes alive)、能量消耗速度以及数据丢失率。

3.1能量消耗

表2列举了4个算法的能量消耗情况。从表2可知，在能量消耗了近50%时，提出的PTTC算法已运行至1 000多轮，而LEACH、EDACH和EECHS分别运行了477轮、478和729轮。从能量消耗数据可知，PTTC算法比LEACH、EDACH算法的能量消耗利用率分别提升了127.0%、126.6%。例如，在运行 800轮时，提出的 PTTC算法仅消耗了22%能量，而LEACH、EDACH分别消耗了48.6%、47.5%能量。

3.2数据丢失率

图3比较了4个算法的数据丢失率情况。如图3所示，提出PTTC算法的数据包丢失率最低，这主要是因为它在选择簇头CH时从全局考虑了剩余能量，并且使得簇头CH分布更均匀,同时建立树簇结构，提高了数据传输效率。而LEACH算法的数据丢失率最高，这也进一步证实随机选择簇头容易导致簇头CH失效，致使无法工作，导致数据丢失。

表2　能量消耗与运行轮数间的关系

图3　数据丢失率

4　总结

本文提出了基于Prim的树簇拓扑的无线传感网络分簇PTTC算法，平衡能量消耗，进而提高网络寿命。首先，从优化能量消耗角度，推导了最优簇头个数，然后依据节点剩余能量、位置信息计算节点被选为簇头CH的概率，再形成簇。最后，利用 Prim算法，构建树，形成树簇结构，并依据树簇拓扑传输数据。仿真结果表明，提出的 PTTC算法比 LEACH算法的能量利用率提升了近127.0%，数据丢失率降低了近50%，有效地提升了网络寿命和数据传输效率。

[1]YOUNIS O,FAHMY S.HEED：A hybrid，energy-efficient，distributed clustering approach for ad hoc sensor networks[J].IEEE Trans.Mobile Comput.，2014，3(4)：366-379.

[2]KUMAR P，SINGH M P，TRIAR U S.A review of routing protocols in wireless sensor network[J].International Journal of Engineering Research&Technology，2012，1(4)：1-14.

[3]HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy-efficient communication protocol for wireless micro-sensor networks[C].In Proc.HICSS，2000：1-10.

[4]KIM K T，YOUNG H Y.Energy-driven adaptive clustering hierarchy(EDACH)for wireless sensor networks[J].LNCS，2005，38(23)：1098-1107.

[5]HU Y，LI W，KANG Z.Study on energy efficient hierarchical routing protocols of wireless sensor network[C].In Proc.ICIE，2009：325-328.

[6]RAY A，DE D.Energy efficient clustering hierarchy protocol for wireless sensor network[C].in Proc.ICCIA，2011：1-4.

[7]FOSS S G，ZUYEV S A.On a voronoi aggregative process related to a bivariate poisson process[J].Advances in Applied Probability，1996(28)：965-981.

PTTC：Clustering algorithm for Wireless Sensor Networks

Wang Zhichao
(Department of Information and Engineering，Wuchang University of Technology，Wuhan 430223，China)

Clustering in WSNs is an effective technique for prolonging the network lifetime.Therefore,Prim based tree topology Clustering algorithm for wireless sensor networks(PTTC)is proposed in this paper.PTTC algorithm decides optimal number of clusters,and calculate the probability of optimum number of cluster head.After that,PTTC algorithm introduces current energy and the count that the node has been selected as CH to stochastically select the CH.Finally,the tree in cluster is computed by Prim algorithm, and the data is transmitted among tree.This improves the energy efficient and longer network lifetime.Simulation shows that PTTC algorithm effectively reduces and balances the energy consumption among the nodes,and thus significantly extends the network lifetime.

Wireless Sensor Network；Clustering；energy；tree；Prim

TN92；TP393

A

10.16157/j.issn.0258-7998.2016.09.024

湖北省教育厅科学技术研究项目(B2015280)

2016-02-22)

王智超(1979－)，男，硕士，讲师，主要研究方向：智能计算、软件工程。

中文引用格式：王智超.PTTC：无线传感网络分簇算法[J].电子技术应用，2016，42(9)：91-94.

英文引用格式：Wang Zhichao.PTTC：Clustering algorithm for Wireless Sensor Networks[J].Application of Electronic Technique，2016，42(9)：91-94.