王智超

(武昌理工學(xué)院 信息工程學(xué)院，湖北 武漢 430223)

PTTC：無線傳感網(wǎng)絡(luò)分簇算法*

王智超

(武昌理工學(xué)院 信息工程學(xué)院，湖北 武漢 430223)

分簇是延長無線傳感網(wǎng)絡(luò)壽命的有效技術(shù)。為此，提出了基于Prim的樹簇拓?fù)涞臒o線傳感網(wǎng)絡(luò)分簇PTTC算法。PTTC算法首先推導(dǎo)最優(yōu)的簇?cái)?shù)，再計(jì)算節(jié)點(diǎn)被選為簇頭的平均概率。然后，結(jié)合節(jié)點(diǎn)的剩余能量以及被選為簇頭的頻率數(shù)選擇簇頭，最后利用Prim算法建立樹，節(jié)點(diǎn)依據(jù)樹傳輸數(shù)據(jù)，進(jìn)而提高能量利用率，擴(kuò)延網(wǎng)絡(luò)壽命。仿真結(jié)果表明，提出的PTTC算法平衡了節(jié)點(diǎn)間的能量消耗，有效地延長了網(wǎng)絡(luò)壽命。

無線傳感網(wǎng)；簇；能量；樹；普里姆算法

0　引言

無線傳感網(wǎng)絡(luò) WSNs(Wireless Sensor Networks)中的傳感節(jié)點(diǎn)通常以隨機(jī)方式分布于網(wǎng)絡(luò)，并且這些節(jié)點(diǎn)的能量供應(yīng)具有有限性，且能量更換不便。這種能量的局限性影響了網(wǎng)絡(luò)壽命。因此，能量有效利用是無線傳感網(wǎng)絡(luò)的研究熱點(diǎn)[1-2]?；诖氐木W(wǎng)絡(luò)結(jié)構(gòu)是延長網(wǎng)絡(luò)壽命的有效算法。

文獻(xiàn)[3]提出了基于低能量自適應(yīng)簇結(jié)構(gòu)算法(Low-Energy Adaptive Clustering Hierarchy，LEACH)，這是典型的簇結(jié)構(gòu)算法。在LEACH中，傳感節(jié)點(diǎn)劃分為簇，每個(gè)簇選舉一個(gè)簇頭CH，其負(fù)責(zé)收集簇內(nèi)其他節(jié)點(diǎn)的數(shù)據(jù)，并向基站傳輸。LEACH算法在選擇簇頭CH時(shí)，采用等概率算法，即每個(gè)節(jié)點(diǎn)被選舉為簇頭CH的概率相同，在選擇簇頭時(shí)并沒有考慮節(jié)點(diǎn)的能量等其他信息。

文獻(xiàn)[4]提出了EDACH(Energy-Driven Adaptive Clustering Hierarchy)算法。EDACH算法采用代理節(jié)點(diǎn)策略，一旦原簇頭CH失效，代理節(jié)點(diǎn)就擔(dān)任當(dāng)前的簇頭CH。隨后，文獻(xiàn)[5]提出了EECH(Energy Efficient Clustering Hierarchy)算法。EECH算法將能量高的節(jié)點(diǎn)賦予被選舉為簇頭CH的概率更高。此外，簇頭CH采用多跳轉(zhuǎn)發(fā)策略向基站傳輸數(shù)據(jù)。文獻(xiàn)[6]提出了基于LEACH的改進(jìn)算法EECHS。EECHS算法考慮了節(jié)點(diǎn)的剩余能量、距離信息選擇簇頭CH。然而，這些算法并沒有從全局角度，考慮簇的分布情況。

據(jù)此，本文提出一種新的分簇 PTTC(Prim based Tree Topology Clustering algorithm for Wireless Sensor)算法。PTTC算法在選擇簇頭CH時(shí)，考慮了節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)被選舉為簇頭CH的頻率以及被選舉為簇頭的概率。仿真結(jié)果表明，提出的PTTC算法能夠有效地降低能量消耗，提高網(wǎng)絡(luò)壽命，并提高數(shù)據(jù)傳輸效率。

1　約束條件及能量模型

1.1約束條件

考慮 N個(gè)傳感節(jié)點(diǎn)si，i=1，2，…，N隨機(jī)分布于監(jiān)測區(qū)域。傳感節(jié)點(diǎn)周期地形成簇，并且有足夠的傳輸功率將數(shù)據(jù)傳輸至基站BS。所有傳感節(jié)點(diǎn)是同構(gòu)的，具有相同數(shù)據(jù)處理能力，并且每個(gè)節(jié)點(diǎn)具有唯一的識別號。基站沒有能量限制，且一般遠(yuǎn)離監(jiān)測區(qū)域。同時(shí)將時(shí)間劃分等間隔的輪，每輪執(zhí)行一次PTTC算法，并產(chǎn)生簇頭。此外，網(wǎng)絡(luò)壽命LT被定義為：

其中 rfirst_death表示網(wǎng)絡(luò)內(nèi)第一個(gè)失效節(jié)點(diǎn)所發(fā)生的輪數(shù)。

1.2能量模型

引用文獻(xiàn)[6]的無線電模型。為了推導(dǎo)每類節(jié)點(diǎn)的能量消耗情況，基于傳輸距離的不同，采用兩種信道模型：自由空間和多徑衰落。相距為 d的兩節(jié)點(diǎn)間傳輸 l bit的數(shù)據(jù)信息所消耗的能量：

其中 Eelec為運(yùn)行發(fā)射器或接收器的能量消耗。dth為距離門限值，其決定信道模型。由于在同一簇內(nèi)，簇頭CH離簇內(nèi)成員節(jié)點(diǎn)的距離小，一般采用自由空間模型，而簇頭與基站BS相距較遠(yuǎn)，采用多徑衰落模型。

相應(yīng)地，節(jié)點(diǎn)接收l bit的消息所消耗的能量 ERx：

其中 εfs和 εmp分別為自由空間和多徑衰落的放大器因子。在本文中，設(shè)定 Eelec=50 nJ/bit、εfs=10 pJ/bit/m2和 εmp= 0.001 3 pJ/bit/m4。此外，為了簡化能量計(jì)算，假定所有消息包含相同的比特?cái)?shù)，數(shù)據(jù)融合所消耗的能量 EDA=5 nJ/bit/signal。

2　PTTC算法

首先，計(jì)算最優(yōu)的簇頭CH個(gè)數(shù)。若簇頭CH個(gè)數(shù)過少，一些傳感節(jié)點(diǎn)需要向遠(yuǎn)處的CH傳輸數(shù)據(jù)耗，加大了能量消耗；反之，若簇頭CH個(gè)數(shù)過多，多數(shù)節(jié)點(diǎn)需要與BS直接通信，也加速了能量消耗。因此，需要對簇頭個(gè)數(shù)CH進(jìn)行優(yōu)化。

其次，每個(gè)傳感節(jié)點(diǎn)成為簇頭CH的概率應(yīng)不相同，應(yīng)依據(jù)各自節(jié)點(diǎn)的信息決定其概率。若低能量的節(jié)點(diǎn)被選舉為簇頭CH，由于簇頭CH任務(wù)繁重，其能量將很快耗盡，這必然縮短了網(wǎng)絡(luò)壽命。因此，需要依據(jù)最優(yōu)的簇頭CH個(gè)數(shù)和節(jié)點(diǎn)的剩余能量決定一個(gè)門限值，進(jìn)而合理地選擇簇頭CH。

2.1最優(yōu)簇頭數(shù) kopt

為了減少能量消耗，從簇頭CH的能量消耗角度推導(dǎo)簇頭CH個(gè)數(shù)的最優(yōu)值。簇頭CH承擔(dān)了3項(xiàng)任務(wù)：數(shù)據(jù)接收、數(shù)據(jù)整合、將融合后的數(shù)據(jù)傳輸至基站BS。由于簇頭CH與基站BS相距較遠(yuǎn)，采用多徑衰落信道模型。據(jù)此，每輪簇頭 CH消耗的能量 ECH：

其中l(wèi)表示每個(gè)數(shù)據(jù)包中的比特?cái)?shù)。N1是簇內(nèi)的節(jié)點(diǎn)數(shù)。EDA表示融合數(shù)據(jù)所消耗的能量，dtoBS表示簇頭 CH離基站的距離。

為了融合所有數(shù)據(jù)，每個(gè)簇頭CH需要處理n/kopt個(gè)長度為 l的信號。每個(gè)簇內(nèi)節(jié)點(diǎn)的平均數(shù)[7]：

其中 λ0、λ1分別表示簇頭 CH的密度、節(jié)點(diǎn)密度。且 λ1= pλ，p=k/n。此外，λ=λ0+λ1是泊松分布密度。n=λ×A是節(jié)點(diǎn)數(shù)，其中A是監(jiān)測方形區(qū)域的面積。k是簇頭個(gè)數(shù)，p表示節(jié)點(diǎn)被選舉為簇頭CH的概率。

不失一般性，假定基站BS位于監(jiān)測區(qū)域的中心。因此，簇頭CH離監(jiān)測區(qū)域的平均距離：

其中D1表示泊松分布變量，表征簇頭CH離基站的距離，且(x，y)是簇頭的位置坐標(biāo)。PA表示在區(qū)域 A內(nèi)簇頭CH的概率密度。

依據(jù)式(5)和式(6)，式(4)可表示為：

由于每個(gè)簇內(nèi)成員節(jié)點(diǎn)需要向它的簇頭CH傳輸l bit的數(shù)據(jù)，假定它們間的距離表示為 dtoCH。不失一般性，dtoCH比較短，采用自由空間信道模型。因此，每個(gè)簇內(nèi)成員節(jié)點(diǎn)所消耗的能量 Enon-CH：

其中 dtoCH[7]：

其中L1為泊松變量，表示簇內(nèi)成員節(jié)點(diǎn)至簇頭距離。因此簇內(nèi)成員節(jié)點(diǎn)離簇頭的平均距離E[L1]：

據(jù)此，每一輪內(nèi)一個(gè)簇所消耗的能量 Ecluster：

一輪內(nèi)所有簇所消耗的總能量 Etotal：

依據(jù)式(7)、式(11)、式(12)，式(13)可轉(zhuǎn)換為：

需要得到最優(yōu)的簇頭個(gè)數(shù)，進(jìn)而能量消耗最少。因此，對式(14)求關(guān)于k導(dǎo)數(shù)，并令其等于零：

由于n=λ(4a4)，可得。式(15)的解便是最優(yōu)的簇頭個(gè)數(shù) kopt：

因此，節(jié)點(diǎn)成為簇頭的概率 popt：

2.2簇頭CH的選擇

LEACH算法采用隨機(jī)機(jī)制選擇簇頭CH，這使得簇頭CH分布不均勻，也導(dǎo)致節(jié)點(diǎn)能量消耗不平衡，降低了網(wǎng)絡(luò)壽命。為此，PTTC算法引用3個(gè)參數(shù)選擇簇頭CH。第一參數(shù)就是剩余能量，其次是輪數(shù)，最后是節(jié)點(diǎn)已被選為簇頭的輪數(shù)。對于節(jié)點(diǎn)i，其被選為簇頭概率T(i)：

其中：Cch表示目前節(jié)點(diǎn)被選為簇頭的次數(shù)，Eresidual表示節(jié)點(diǎn)的剩余能量，Einit為節(jié)點(diǎn)的初始能量，r為輪數(shù)。一旦被選舉為簇頭CH，節(jié)點(diǎn)就向鄰居節(jié)點(diǎn)廣播通告消息Mes_adver。當(dāng)其他節(jié)點(diǎn)接收了Mes_adver消息后，就向該簇頭CH回復(fù)，并發(fā)送加入該簇消息Mes_join。接收了Mes_join消息后，簇頭CH就依據(jù)Mes_join消息識別節(jié)點(diǎn)ID，并記錄簇內(nèi)成員節(jié)點(diǎn)號，最終形成簇。

2.3樹的構(gòu)建

形成簇后，再利用普里姆(Prim)算法構(gòu)建樹。假定N={V，E}表示連通網(wǎng)絡(luò)。首先從一頂點(diǎn)h出發(fā)，再選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(h，v)，然后將其頂點(diǎn)加入到生成樹的頂點(diǎn)集合U中。以后每一步均從一個(gè)頂點(diǎn)在U中而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u，v)，并把該邊加入到生成樹的邊集中，把它的頂點(diǎn)加入到集合U中。一直重復(fù)執(zhí)行，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。普里姆(Prim)算法建立最小spanning樹的示例如圖1所示。

圖1　基于普里姆構(gòu)建最小 spanning樹的過程

在PTTC算法中，節(jié)點(diǎn)i的權(quán)值Weight(i)：

其中 ω1、ω2為權(quán)值系數(shù)，Eresidual(i)表示節(jié)點(diǎn)的剩余能量，d(i，CH)表示節(jié)點(diǎn)離簇頭CH的距離。

利用Prim算法建立的樹簇網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。形成了樹簇結(jié)構(gòu)后，便可開始進(jìn)行數(shù)據(jù)傳輸。葉節(jié)點(diǎn)向父節(jié)點(diǎn)傳輸數(shù)據(jù)。融合了自己數(shù)據(jù)后，父節(jié)點(diǎn)再將數(shù)據(jù)傳輸?shù)剿母腹?jié)點(diǎn)。

圖2　樹簇結(jié)構(gòu)

3　性能分析

利用 MATLABR2012b建立仿真平臺?？紤]100 m× 100 m的區(qū)域，基站位于區(qū)域中心位置，具體仿真參數(shù)如表1所示。每次實(shí)驗(yàn)重復(fù)50次，取平均值作為最終數(shù)據(jù)。仿真時(shí)間為500 s。

表1　仿真參數(shù)

此外，選擇 LEACH、EDACH、EECHS與 提 出 的PTTC算法進(jìn)行同步仿真，比較這4個(gè)算法在失效簇頭CH數(shù)、第一個(gè)節(jié)點(diǎn)失效所發(fā)生的輪數(shù)FND(First Node Die)和一半活動(dòng)節(jié)點(diǎn)所在的輪數(shù)HNA(Half of the Nodes alive)、能量消耗速度以及數(shù)據(jù)丟失率。

3.1能量消耗

表2列舉了4個(gè)算法的能量消耗情況。從表2可知，在能量消耗了近50%時(shí)，提出的PTTC算法已運(yùn)行至1 000多輪，而LEACH、EDACH和EECHS分別運(yùn)行了477輪、478和729輪。從能量消耗數(shù)據(jù)可知，PTTC算法比LEACH、EDACH算法的能量消耗利用率分別提升了127.0%、126.6%。例如，在運(yùn)行 800輪時(shí)，提出的 PTTC算法僅消耗了22%能量，而LEACH、EDACH分別消耗了48.6%、47.5%能量。

3.2數(shù)據(jù)丟失率

圖3比較了4個(gè)算法的數(shù)據(jù)丟失率情況。如圖3所示，提出PTTC算法的數(shù)據(jù)包丟失率最低，這主要是因?yàn)樗谶x擇簇頭CH時(shí)從全局考慮了剩余能量，并且使得簇頭CH分布更均勻,同時(shí)建立樹簇結(jié)構(gòu)，提高了數(shù)據(jù)傳輸效率。而LEACH算法的數(shù)據(jù)丟失率最高，這也進(jìn)一步證實(shí)隨機(jī)選擇簇頭容易導(dǎo)致簇頭CH失效，致使無法工作，導(dǎo)致數(shù)據(jù)丟失。

表2　能量消耗與運(yùn)行輪數(shù)間的關(guān)系

圖3　數(shù)據(jù)丟失率

4　總結(jié)

本文提出了基于Prim的樹簇拓?fù)涞臒o線傳感網(wǎng)絡(luò)分簇PTTC算法，平衡能量消耗，進(jìn)而提高網(wǎng)絡(luò)壽命。首先，從優(yōu)化能量消耗角度，推導(dǎo)了最優(yōu)簇頭個(gè)數(shù)，然后依據(jù)節(jié)點(diǎn)剩余能量、位置信息計(jì)算節(jié)點(diǎn)被選為簇頭CH的概率，再形成簇。最后，利用 Prim算法，構(gòu)建樹，形成樹簇結(jié)構(gòu)，并依據(jù)樹簇拓?fù)鋫鬏敂?shù)據(jù)。仿真結(jié)果表明，提出的 PTTC算法比 LEACH算法的能量利用率提升了近127.0%，數(shù)據(jù)丟失率降低了近50%，有效地提升了網(wǎng)絡(luò)壽命和數(shù)據(jù)傳輸效率。

[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

湖北省教育廳科學(xué)技術(shù)研究項(xiàng)目(B2015280)

2016-02-22)

王智超(1979－)，男，碩士，講師，主要研究方向：智能計(jì)算、軟件工程。

中文引用格式：王智超.PTTC：無線傳感網(wǎng)絡(luò)分簇算法[J].電子技術(shù)應(yīng)用，2016，42(9)：91-94.

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