0 引言

　　無線傳感網絡WSNs(Wireless Sensor Networks)中的傳感節(jié)點通常以隨機方式分布于網絡，并且這些節(jié)點的能量供應具有有限性,，且能量更換不便,。這種能量的局限性影響了網絡壽命。因此,，能量有效利用是無線傳感網絡的研究熱點[1-2],。基于簇的網絡結構是延長網絡壽命的有效算法,。

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

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

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

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

1 約束條件及能量模型

　　1.1 約束條件

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

　　其中rfirst_death表示網絡內第一個失效節(jié)點所發(fā)生的輪數,。

　　1.2 能量模型

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

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

　　相應地,，節(jié)點接收l bit的消息所消耗的能量ERx：

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

2 PTTC算法

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

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

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

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

　　其中l(wèi)表示每個數據包中的比特數,。N1是簇內的節(jié)點數。EDA表示融合數據所消耗的能量,，dtoBS表示簇頭CH離基站的距離,。

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

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

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

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

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

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

　　其中dtoCH[7]：

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

　　因此：

　　據此,，每一輪內一個簇所消耗的能量Ecluster：

　　一輪內所有簇所消耗的總能量Etotal：

　　依據式(7),、式(11)、式(12),，式(13)可轉換為：

　　需要得到最優(yōu)的簇頭個數,，進而能量消耗最少。因此,，對式(14)求關于k導數,，并令其等于零：

　　由于,，可得。式(15)的解便是最優(yōu)的簇頭個數kopt：

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

　　2.2 簇頭CH的選擇

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

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

　　2.3 樹的構建

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

　　在PTTC算法中,，節(jié)點i的權值Weight(i)：

　　其中,、棕2為權值系數，Eresidual(i)表示節(jié)點的剩余能量,，d(i,，CH)表示節(jié)點離簇頭CH的距離。

　　利用Prim算法建立的樹簇網絡結構如圖2所示,。形成了樹簇結構后,，便可開始進行數據傳輸。葉節(jié)點向父節(jié)點傳輸數據,。融合了自己數據后,，父節(jié)點再將數據傳輸到它的父節(jié)點。

3 性能分析

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

　　此外，選擇LEACH,、 EDACH,、EECHS與提出的PTTC算法進行同步仿真，比較這4個算法在失效簇頭CH數,、第一個節(jié)點失效所發(fā)生的輪數FND(First Node Die)和一半活動節(jié)點所在的輪數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算法，平衡能量消耗,，進而提高網絡壽命,。首先，從優(yōu)化能量消耗角度,，推導了最優(yōu)簇頭個數,，然后依據節(jié)點剩余能量、位置信息計算節(jié)點被選為簇頭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.