《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > 一種基于PAM算法進行分簇的LEACH_P協(xié)議
一種基于PAM算法進行分簇的LEACH_P協(xié)議
2014年微型機與應(yīng)用第10期
劉基墻,,徐 鵬
華僑大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,,福建 廈門
摘要: 在LEACH協(xié)議的基礎(chǔ)上提出了一種LEACH_P算法,該算法使用基于劃分的聚類算法PAM對初始拓撲進行分簇,。首輪選擇距離簇質(zhì)心最近的節(jié)點作為簇頭,,后面各輪選擇簇頭鄰域內(nèi)剩余能量最大的節(jié)點作為簇頭。每當死亡節(jié)點增量達到節(jié)點總數(shù)的5%時,重新進行分簇,,同時簇頭領(lǐng)域半徑增大25%后再進行簇頭選擇,。仿真結(jié)果表明,LEACH_P算法分簇更加合理,,節(jié)點能耗更加均衡,,整個網(wǎng)絡(luò)生存周期(第一個節(jié)點死亡時間)延長了30%左右,有效地提升了網(wǎng)絡(luò)性能,。
Abstract:
Key words :

  摘  要: 在LEACH協(xié)議的基礎(chǔ)上提出了一種LEACH_P算法,,該算法使用基于劃分的聚類算法PAM對初始拓撲進行分簇。首輪選擇距離簇質(zhì)心最近的節(jié)點作為簇頭,,后面各輪選擇簇頭鄰域內(nèi)剩余能量最大的節(jié)點作為簇頭,。每當死亡節(jié)點增量達到節(jié)點總數(shù)的5%時,重新進行分簇,,同時簇頭領(lǐng)域半徑增大25%后再進行簇頭選擇,。仿真結(jié)果表明,LEACH_P算法分簇更加合理,,節(jié)點能耗更加均衡,,整個網(wǎng)絡(luò)生存周期(第一個節(jié)點死亡時間)延長了30%左右,有效地提升了網(wǎng)絡(luò)性能,。

  關(guān)鍵詞WSN路由協(xié)議,;LEACH;PAM算法,;MATLAB仿真

  傳感器技術(shù),、微機電系統(tǒng)、現(xiàn)代網(wǎng)絡(luò)和無線通信等技術(shù)的進步,,推動了具有現(xiàn)代意義的無線傳感器網(wǎng)絡(luò)的產(chǎn)生和發(fā)展[1]?,F(xiàn)在無線傳感器網(wǎng)絡(luò)已經(jīng)非常廣泛,,軍事,、環(huán)境監(jiān)測和預(yù)報、健康護理,、建筑物狀態(tài)控制等領(lǐng)域都可以看到無線傳感器網(wǎng)絡(luò)的影子,。無線傳感器網(wǎng)絡(luò)的自身特點決定了其特殊性,由于能量無法得到補充,,能量有限,,因此必須盡可能地節(jié)約能耗以延長節(jié)點的存活時間,節(jié)能降耗便成為了無線傳感器網(wǎng)絡(luò)研究中一個熱點,。本文在經(jīng)典的LEACH協(xié)議的基礎(chǔ)上提出了LEACH_P(LEACH based on PAM)協(xié)議,,通過MATLAB仿真驗證了其在均衡節(jié)點能耗上的有效性。

  1 LEACH協(xié)議

  LEACH[2]是最早提出的基于分簇的層次路由協(xié)議。普通節(jié)點的數(shù)據(jù)經(jīng)由各自簇頭節(jié)點傳給sink節(jié)點,,有效減少了整個網(wǎng)絡(luò)的能量消耗,。同時,簇頭的選舉使得各個節(jié)點都能在數(shù)輪之中當選一次簇頭,,均衡了簇頭的能量損耗,,有效地提高了網(wǎng)絡(luò)性能。據(jù)計算,,相比于一般的平面路由協(xié)議,,LEACH可以延長網(wǎng)絡(luò)周期約15%[3]。

  盡管如此,,LEACH協(xié)議仍然有以下不足:

  (1)簇的形成為先選舉簇頭再形成簇,,簇頭的選舉具有很大的隨機性,僅僅依靠生成的隨機數(shù)來決定是否成為簇頭,。

  (2)簇頭的選舉具有很大的隨機性,,任何節(jié)點只要其生成的隨機數(shù)小于閾值T(n)即可當選為簇頭,未考慮到節(jié)點的剩余能量,。

  (3)簇的形成過程實質(zhì)是先選出簇頭再根據(jù)簇頭形成簇,,由于之前的簇頭選舉沒有考慮到節(jié)點的物理位置,使得可能出現(xiàn)各個簇內(nèi)成員節(jié)點數(shù)目差距很大,。成員節(jié)點較多的簇內(nèi)簇頭能耗會非常大,,顯然不利于延長網(wǎng)絡(luò)的生存時間。

  2 PAM算法

  PAM算法是由KAUFMAN L和ROUSSENUW P J等人提出的一種中心點劃分聚類算法[4],。算法策略如下,。

  在數(shù)據(jù)集中隨機選擇k個對象作為中心點,其余節(jié)點皆為非中心點,。算法反復(fù)使用非中心點來試圖替換中心點,,基于各種可能的組合,估算聚類結(jié)果的質(zhì)量,。一個中心點Oi如果可以被一個非中心點對象Oh所代替,,那么這次迭代過程中的Oh將被作為新的中心點出現(xiàn)在下一輪迭代中,算法運算直至最終收斂,。

  非中心節(jié)點Oh試圖替換中心節(jié)點Oi時,, PAM算法為每一個非中心點Oj計算代價Cjih,Cjih的值存在以下4種情況,,如圖1所示,。

001.jpg

  (1)Oj屬于中心點Oi。如果Oi被Oh替換后,,Oj離另外一個中心點Om更近,,那么Oj加入Om,此時,Cjih=Distance(j,,m)-Distance(j,,i)。

  (2)Oj屬于中心點Oi,。如果Oi被Oh替換后,,Oj離Oh更近,那么Oj加入Oh,。此時,,Cjih=Distance(j,h)-Distance(j,,i),。

  (3)Oj屬于中心點Om。如果Oi被Oh替換后,,Oj還是離Om更近,,那么對象的隸屬關(guān)系保持不變。此時,,Cjih=0,。

  (4)Oj屬于中心點Om。如果Oi被Oh替換后,,Oj還是離Oh更近,,那么Oj加入Oh的簇。此時,,Cjih=Distance(j,,h)-Distance(j,m),。

  其中,,Distance(i,j)表示點i到點j的距離,,此處使用歐幾里得距離,。

  計算替換產(chǎn)生的總代價函數(shù)TC=Cjih,其中j為除節(jié)點h和i之外的其余所有節(jié)點,。如果TC<0,,說明替換后的中心點更接近簇的中心,分簇更加合理,,執(zhí)行中心節(jié)點的替換過程;否則,,不進行中心節(jié)點的替換,。

  LEACH_P協(xié)議是基于LEACH進行的改進,所以協(xié)議運行流程大致相同,同樣是以輪(round)為單位,。不同于LEACH協(xié)議的是,,LEACH_P改變了原來LEACH協(xié)議的先選舉簇頭再形成簇的構(gòu)造順序,改為先使用PAM算法對初始簇進行均勻分簇,,而后再進行簇頭的選舉,。之后分簇的結(jié)果將在一段較長的時間內(nèi)保持不變,直到死亡節(jié)點的增加數(shù)目達到一定量再重新進行分簇,。簇頭的選舉在每一輪結(jié)束后都會進行,。在每一輪的簇頭選舉過后,接著進行數(shù)據(jù)傳輸,,數(shù)據(jù)傳輸階段與LEACH協(xié)議完全一樣,,這里不再贅述??偟膩碚f,,LEACH_P協(xié)議包含簇的形成、簇頭選舉和數(shù)據(jù)傳輸三個部分,。下面著重介紹簇的形成和簇頭選舉兩個部分,。

  2.1 簇的形成

  簇的形成即對拓撲中的節(jié)點進行分簇,分簇后使得各個簇內(nèi)的節(jié)點分布更加緊湊,,有利于縮短數(shù)據(jù)傳輸距離,,節(jié)省數(shù)據(jù)傳輸時消耗的能量。分簇并不是每一輪都進行,,在協(xié)議運行開始時進行初始分簇,,之后只有當死亡節(jié)點數(shù)的增量達到一定量時,才會在下一輪開始時先重新分簇,,以此規(guī)避由于節(jié)點死亡帶來的簇頭節(jié)點負載不均衡,。使用PAM算法對原始拓撲進行分簇時,需要確定分簇的數(shù)目k,。k的值不能過大,,否則就不能最大化分簇路由帶來的能量節(jié)省。k的值也不能過小,,這樣會使單個簇頭需要負擔的簇內(nèi)節(jié)點過多,,簇頭節(jié)點能量消耗過快,也不利于整個網(wǎng)絡(luò)性能的提升,。根據(jù)參考文獻[5],,假設(shè)傳感器節(jié)點均為相似二維空間λ泊松分布,則可以得到最優(yōu)的簇頭節(jié)點百分比為:

  

11.png

  其中,,c為區(qū)域邊長的一半,,由節(jié)點總數(shù)即可求得分簇的數(shù)目,。

  分簇算法包括以下幾個步驟:

  (1)從初始數(shù)據(jù)集中隨機選擇k=p×N(節(jié)點總數(shù))個節(jié)點作為臨時中心點Oi。

  (2)將剩余節(jié)點依照距離最短原則選擇距離最近的臨時中心點加入其簇,。

  (3)選擇一個異于中心點Oi的非中心點Oh,,試圖用Oh替換Oi作為新的中心點。

  (4)計算替換產(chǎn)生的總代價TC,,如果TC<0,,則進行替換操作,此后Oh作為新的中心點存在,。

  (5)跳到步驟(3),,直達所有可能的“替換對”都進行替換試探完畢后停止,最終形成新的k個臨時中心點Oi,,一輪迭代過程完成,。

  (6)跳轉(zhuǎn)到步驟(2),進行下一輪的迭代,,直到達到迭代次數(shù),,跳轉(zhuǎn)到步驟(7)。

  (7)迭代過程完成,,中心點Oi選擇完畢,。

  (8)其余非中心點Oj根據(jù)到各個中心點Oi的距離選擇距離最近的中心點加入其簇。

  (9)分簇完畢,,形成k個簇,。

  2.2 簇頭選舉

  經(jīng)過分簇后,分出的各個簇節(jié)點數(shù)較為平均,,各個簇內(nèi)節(jié)點間間距較小,。簇頭選擇應(yīng)該兼顧簇頭節(jié)點的剩余能量和簇頭節(jié)點的位置。

  2.2.1 首輪簇頭選舉

  首輪由于所有節(jié)點的剩余能量大體相同,,簇頭的選擇基于節(jié)點剩余能量的考慮可以忽略,,主要從節(jié)點的位置考慮選舉簇頭。根據(jù)參考文獻[6],,當?shù)趇個簇內(nèi)的非簇頭節(jié)點向j傳輸數(shù)據(jù)時,,系統(tǒng)消耗的總能量取決于?撞dij2(簇內(nèi)距離較近,使用多路徑衰減模型),,盡量減小撞dij2即可實現(xiàn)節(jié)省能耗,。令第j個簇的簇頭節(jié)點的坐標為(Xj,Yj),,簇內(nèi)的非簇頭節(jié)點坐標為(Xn,,Yn),節(jié)點總數(shù)為M,,所以分簇數(shù)的個數(shù)為M×p,;簇j內(nèi)節(jié)點數(shù)目為Nj(包括簇頭),。計算得到第j個簇內(nèi)非簇頭節(jié)點到簇頭節(jié)點之間距離平方的數(shù)學(xué)期望:

  

6ML((}}4{BA{S7_JFJ5_YXA.jpg

  2.2.2 首輪之后輪次的簇頭選舉

  首輪之后輪次的簇頭選舉應(yīng)該綜合考慮到節(jié)點的剩余能量和節(jié)點的物理位置,。首輪之后的簇頭選擇策略是:以簇的中心(幾何中心)為中心點,,以半徑r作圓。在此圓中,,選擇剩余能量最多的節(jié)點作為簇頭,。首輪中,簇頭節(jié)點位置較為居中,,簇內(nèi)其余非簇頭節(jié)點到簇頭節(jié)點的距離不同,,而非簇頭節(jié)點的發(fā)送數(shù)據(jù)能耗與傳輸距離有直接關(guān)系。一輪過后,,靠近簇邊緣的節(jié)點剩余能量相對較小,,所以應(yīng)該選擇離簇頭近的節(jié)點作為簇頭。數(shù)輪過后,,離簇頭較近的節(jié)點可能都已經(jīng)當選過簇頭,,由于作為簇頭的能量耗損較大,此時整個簇頭的剩余能量區(qū)域分布情況是簇邊緣的節(jié)點剩余能量多,,簇中間的節(jié)點剩余能量較小,。此后應(yīng)該盡量選擇這些邊緣節(jié)點作為簇頭。LEACH_P協(xié)議的策略是每隔數(shù)輪N將半徑r增大20%,,每次增大的半徑幅度都為0.2r,,當半徑增大到2.5r后,再過一段時間,,半徑重新調(diào)整到r,,之后重復(fù)前面的步驟繼續(xù)進行??傊?,首輪之后的簇頭選擇是:在以各個簇中心為原點,以r為半徑的圓內(nèi)選擇剩余能量最大的節(jié)點作為簇頭,,間隔N輪后,,r增大20%,當半徑增大到2.5r后,,半徑重新回歸到r,,從頭再進行遞增。

  3 仿真分析

  本文使用MATLAB作為實驗工具進行仿真,。實驗中,,100個節(jié)點隨機分布在100×100的區(qū)域內(nèi),節(jié)點總數(shù)為100個,。匯聚節(jié)點sink位于拓撲的中心位置,,坐標為(50,,50)。節(jié)點當選為簇頭的概率p取0.05,。實驗中用到的其他主要參數(shù)如表1所示,,所采用的拓撲圖如圖2所示。

005.jpg

002.jpg

  圖2是使用LEACH_P協(xié)議進行首輪分簇的結(jié)果,??梢钥闯觯褂肞AM算法對初始拓撲圖進行聚類能夠取得比較好的聚類結(jié)果,。各個聚簇內(nèi)的節(jié)點數(shù)目比較平均,,簇的大小相似,這樣有利于簇頭節(jié)點均衡能耗,,各個簇頭的輪平均能耗更為接近,。

003.jpg

  本實驗主要從節(jié)點能量總耗費和死亡節(jié)點數(shù)對實驗進行分析。各輪總能量消耗圖如圖3所示,。LEACH_P協(xié)議和LEACH協(xié)議在各輪中的總能量耗損非常接近,,并且會在很長的一段時間內(nèi)保持這種趨勢。其中的原因是:使用PAM算法能夠帶來比較好的分簇結(jié)果,。但是,,即便如此,各輪中總的數(shù)據(jù)傳輸距離(包括簇內(nèi)節(jié)點到簇頭節(jié)點的距離和簇頭節(jié)點到簇內(nèi)節(jié)點的距離)大體相同,,所以總的能量耗損曲線基本上重合在一起,。在之后的340輪左右,LEACH_P(NEW)協(xié)議的曲線開始凸顯出來,,同時在之后的50輪中,,LEACH_P協(xié)議的總能耗會與LEACH協(xié)議的能耗進一步拉大,這是由于LEACH協(xié)議中各節(jié)點的剩余能量分布不均勻造成的,。LEACH分簇沒有考慮到節(jié)點的剩余能量和節(jié)點的地理位置,,進行分簇的結(jié)果又不盡理想,使得最終節(jié)點間的剩余能量差距較大,。仿真結(jié)束后,,會余下一些不能再次成簇的節(jié)點。下面通過分析剩余節(jié)點圖來補充說明圖3中最后50輪曲線變化的原因,。

004.jpg

  剩余節(jié)點對比圖如圖4所示,。LEACH協(xié)議第一個節(jié)點死亡的時間是在245輪左右,而LEACH_P協(xié)議則是在350輪左右,。LEACH_P協(xié)議使得整個網(wǎng)絡(luò)的生命周期延長了30%左右,。LEACH協(xié)議中節(jié)點死亡20%是在330輪左右,而LEACH_P協(xié)議則是在350輪,;LEACH協(xié)議中節(jié)點死亡率為80%經(jīng)歷的輪數(shù)為145輪,,而LEACH_P協(xié)議只有用30輪,。LEACH_P協(xié)議在如此短的時間內(nèi)節(jié)點大量死亡,是因為整個網(wǎng)絡(luò)的能量均衡效果比較好,,節(jié)點的剩余能量值接近,,單一節(jié)點的死亡預(yù)示其他節(jié)點的能量也快耗盡。網(wǎng)絡(luò)生命周期的延長原因也正是如此,,能量消耗能夠分擔到每個節(jié)點,,同時分擔的份額也較為平均,。而在LEACH中,,非均衡的能量損耗使得節(jié)點的剩余能量差異較大。均衡整個網(wǎng)絡(luò)的能量損耗到各個節(jié)點,,使得整個網(wǎng)絡(luò)的性能大幅提高,。圖4中,仿真結(jié)束后,,LEACH協(xié)議中剩余存活的節(jié)點達到13個,,LEACH_P中為5個,這也正是圖3中仿真結(jié)束后LEACH比LEACH_P協(xié)議剩余的能量多的原因,。

  本文在LEACH協(xié)議基礎(chǔ)上提出了LEACH_P算法,,通過PAM算法對拓撲進行分簇,之后再選舉簇頭,。仿真實驗證明了其在均衡節(jié)點能耗上取得了比較好的結(jié)果,,LEACH_P協(xié)議能夠利用整個網(wǎng)絡(luò)中的節(jié)點來均衡網(wǎng)絡(luò)能量損耗,使得整個網(wǎng)絡(luò)的生存周期提高了30%,,增強了網(wǎng)絡(luò)性能,。接下來的研究方向是如何在均衡能耗的前提下減少單輪網(wǎng)絡(luò)總能耗。

  參考文獻

  [1] 孫利民.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,,2005.

  [2] HEINZELMAN W,,CHANDRAKASAN A,BALAKBISHNAN H.Energy efficient communication protocol for wireless  micro-sensor network[C].Proceedings Of The 33rd Hawaii Interna-tional Conference on System Sciences,,Washington,,DC,IEEE Transactions on Computer Society,,2000:3005-3014.

  [3] HEINZELMAN W R,,CHANDRAKASAN A,BALAKRISHNANH.Energy-efficient communication protocol for wireless micro-sensor networks[C].Proceedings of HICSS’00,,Los Alamitos,,CA,USA,,IEEE Press,,2000.

  [4] KAUFMAN L,,ROUSSEEUW P J.Finding grouping in data:an introduction to cluster analysis[M].New York:John Wiley & Sons,1990.

  [5] BANDYOPADHYAY S,,COYLE E J.An energy efficient hi-erarchical clustering algorithm for wireless sensor networks[C].IEEE INFOCOM 2003,,Twenty-Second Annual Joint Conference of the IEEE Computer and Communications,IEEE Societies,,2003,,3:1713-1723.

  [6] 胡興華,駱堅,,譚珊珊,,等.固定簇的LEACH半徑自適應(yīng)簇頭改進算法[J].傳感技術(shù)學(xué)報,2011,,24(1):79-82.


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