文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.09.024
中文引用格式： 王智超. 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.
0 引言
無線傳感網絡WSNs(Wireless Sensor Networks)中的傳感節點通常以隨機方式分布于網絡，并且這些節點的能量供應具有有限性，且能量更換不便。這種能量的局限性影響了網絡壽命。因此，能量有效利用是無線傳感網絡的研究熱點[1-2]?；?a class="innerlink" href="http://www.cowatch.cn/tags/簇" title="簇" target="_blank">簇的網絡結構是延長網絡壽命的有效算法。
文獻[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.