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]?；?a class="innerlink" href="http://forexkbc.com/tags/簇" title="簇" target="_blank">簇的網(wǎng)絡(luò)結(jié)構(gòu)是延長(zhǎng)網(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 Clus-

　　tering 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)測(cè)區(qū)域,。傳感節(jié)點(diǎn)周期地形成簇,，并且有足夠的傳輸功率將數(shù)據(jù)傳輸至基站BS。所有傳感節(jié)點(diǎn)是同構(gòu)的,，具有相同數(shù)據(jù)處理能力,，并且每個(gè)節(jié)點(diǎn)具有唯一的識(shí)別號(hào)?；緵]有能量限制,，且一般遠(yuǎn)離監(jiān)測(cè)區(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：

　　其中和分別為自由空間和多徑衰落的放大器因子。在本文中,，設(shè)定和?著=,。此外，為了簡(jiǎn)化能量計(jì)算,，假定所有消息包含相同的比特?cái)?shù),，數(shù)據(jù)融合所消耗的能量,。

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直接通信,，也加速了能量消耗。因此,，需要對(duì)簇頭個(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è)長(zhǎng)度為l的信號(hào),。每個(gè)簇內(nèi)節(jié)點(diǎn)的平均數(shù)[7]：

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

　　不失一般性，假定基站BS位于監(jiān)測(cè)區(qū)域的中心,。因此,，簇頭CH離監(jiān)測(cè)區(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)而能量消耗最少。因此,，對(duì)式(14)求關(guān)于k導(dǎo)數(shù),，并令其等于零：

　　由于，可得,。式(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ù),。對(duì)于節(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消息識(shí)別節(jié)點(diǎn)ID,，并記錄簇內(nèi)成員節(jié)點(diǎn)號(hào)，最終形成簇,。

　　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所示。

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

　　其中,、棕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),。

3 性能分析

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

　　此外,，選擇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ù)丟失。

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ù)傳輸效率。

　　參考文獻(xiàn)

　　[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.