0 引言

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

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

　　文献[4]提出了EDACH(Energy-Driven Adaptive Clus-

　　tering 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：

　　其中和分别为自由空间和多径衰落的放大器因子。在本文中，设定和?着=。此外，为了简化能量计算，假定所有消息包含相同的比特数，数据融合所消耗的能量。

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]：

　　其中分别表示簇头CH的密度、节点密度。且。此外，是泊松分布密度。是节点数，其中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导数，并令其等于零：

　　由于，可得。式(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所示。

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

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

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

3 性能分析

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

　　此外，选择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失效，致使无法工作，导致数据丢失。

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.