《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > PTTC:無線傳感網(wǎng)絡(luò)分簇算法
PTTC:無線傳感網(wǎng)絡(luò)分簇算法
2016年電子技術(shù)應(yīng)用第9期
王智超
武昌理工學(xué)院 信息工程學(xué)院,,湖北 武漢430223
摘要: 分簇是延長無線傳感網(wǎng)絡(luò)壽命的有效技術(shù),。為此,提出了基于Prim的樹簇拓?fù)涞臒o線傳感網(wǎng)絡(luò)分簇PTTC算法。PTTC算法首先推導(dǎo)最優(yōu)的簇數(shù),,再計算節(jié)點被選為簇頭的平均概率。然后,結(jié)合節(jié)點的剩余能量以及被選為簇頭的頻率數(shù)選擇簇頭,最后利用Prim算法建立樹,,節(jié)點依據(jù)樹傳輸數(shù)據(jù),進(jìn)而提高能量利用率,,擴(kuò)延網(wǎng)絡(luò)壽命,。仿真結(jié)果表明,提出的PTTC算法平衡了節(jié)點間的能量消耗,,有效地延長了網(wǎng)絡(luò)壽命,。
中圖分類號: TN92;TP393
文獻(xiàn)標(biāo)識碼: A
DOI:10.16157/j.issn.0258-7998.2016.09.024
中文引用格式: 王智超. 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.
PTTC:Clustering algorithm for Wireless Sensor Networks
Wang Zhichao
Department of Information and Engineering,Wuchang University of Technology,,Wuhan 430223,,China
Abstract: 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.
Key words : Wireless Sensor Network;Clustering,;energy,;tree;Prim

0 引言

  無線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)中的傳感節(jié)點通常以隨機(jī)方式分布于網(wǎng)絡(luò),,并且這些節(jié)點的能量供應(yīng)具有有限性,,且能量更換不便。這種能量的局限性影響了網(wǎng)絡(luò)壽命,。因此,,能量有效利用是無線傳感網(wǎng)絡(luò)的研究熱點[1-2]。基于的網(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é)點劃分為簇,每個簇選舉一個簇頭CH,,其負(fù)責(zé)收集簇內(nèi)其他節(jié)點的數(shù)據(jù),,并向基站傳輸。LEACH算法在選擇簇頭CH時,,采用等概率算法,,即每個節(jié)點被選舉為簇頭CH的概率相同,在選擇簇頭時并沒有考慮節(jié)點的能量等其他信息,。

  文獻(xiàn)[4]提出了EDACH(Energy-Driven Adaptive Clus-

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

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

1 約束條件及能量模型

  1.1 約束條件

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

  QQ圖片20161114113612.png

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

  1.2 能量模型

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

   QQ圖片20161114113618.png

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

  相應(yīng)地,,節(jié)點接收l bit的消息所消耗的能量ERx:

  QQ圖片20161114113622.png

  其中QQ圖片20161114114126.jpgQQ圖片20161114114129.jpg分別為自由空間和多徑衰落的放大器因子。在本文中,,設(shè)定QQ圖片20161114114316.png和?著QQ圖片20161114114129.jpg=QQ圖片20161114114319.png,。此外,為了簡化能量計算,,假定所有消息包含相同的比特數(shù),,數(shù)據(jù)融合所消耗的能量QQ圖片20161114114425.pngQQ圖片20161114114430.jpg

2 PTTC算法

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

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

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

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

  QQ圖片20161114113626.png

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

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

  QQ圖片20161114113629.png

  其中QQ圖片20161114114649.jpgQQ圖片20161114114653.jpg分別表示簇頭CH的密度,、節(jié)點密度。且QQ圖片20161114114657.png,。此外,,QQ圖片20161114114700.png是泊松分布密度。QQ圖片20161114114703.png是節(jié)點數(shù),,其中A是監(jiān)測方形區(qū)域的面積,。k是簇頭個數(shù),,p表示節(jié)點被選舉為簇頭CH的概率。

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

  QQ圖片20161114113633.png

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

  依據(jù)式(5)和式(6),式(4)可表示為:

  QQ圖片20161114113637.png

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

  QQ圖片20161114113640.png

  其中dtoCH[7]:

  QQ圖片20161114113643.png

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

  QQ圖片20161114113647.png

  因此:

  QQ圖片20161114113651.png

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

  QQ圖片20161114113655.png

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

  QQ圖片20161114113658.png

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

  QQ圖片20161114113702.png

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

  QQ圖片20161114113705.png

  由于QQ圖片20161114115326.png,,可得QQ圖片20161114115329.png。式(15)的解便是最優(yōu)的簇頭個數(shù)kopt:

  QQ圖片20161114113708.png

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

  QQ圖片20161114113711.png

  2.2 簇頭CH的選擇

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

  QQ圖片20161114113715.png

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

  2.3 樹的構(gòu)建

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

圖像 001.png

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

  QQ圖片20161114113719.png

  其中QQ圖片20161114114956.jpg,、QQ圖片20161114114959.jpg棕2為權(quán)值系數(shù),Eresidual(i)表示節(jié)點的剩余能量,,d(i,,CH)表示節(jié)點離簇頭CH的距離。

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

圖像 002.png

3 性能分析

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

圖像 003.png

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

  3.1 能量消耗

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

圖像 004.png

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

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

圖像 005.png

4 總結(jié)

  本文提出了基于Prim的樹簇拓?fù)涞臒o線傳感網(wǎng)絡(luò)分簇PTTC算法,平衡能量消耗,,進(jìn)而提高網(wǎng)絡(luò)壽命,。首先,從優(yōu)化能量消耗角度,,推導(dǎo)了最優(yōu)簇頭個數(shù),,然后依據(jù)節(jié)點剩余能量、位置信息計算節(jié)點被選為簇頭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.

  

  


此內(nèi)容為AET網(wǎng)站原創(chuàng),,未經(jīng)授權(quán)禁止轉(zhuǎn)載。