摘 要： 在LEACH協(xié)議的基礎(chǔ)上提出了一種LEACH_P算法，該算法使用基于劃分的聚類算法PAM對(duì)初始拓?fù)溥M(jìn)行分簇,。首輪選擇距離簇質(zhì)心最近的節(jié)點(diǎn)作為簇頭,，后面各輪選擇簇頭鄰域內(nèi)剩余能量最大的節(jié)點(diǎn)作為簇頭。每當(dāng)死亡節(jié)點(diǎn)增量達(dá)到節(jié)點(diǎn)總數(shù)的5%時(shí),，重新進(jìn)行分簇,，同時(shí)簇頭領(lǐng)域半徑增大25%后再進(jìn)行簇頭選擇。仿真結(jié)果表明,，LEACH_P算法分簇更加合理,，節(jié)點(diǎn)能耗更加均衡，整個(gè)網(wǎng)絡(luò)生存周期（第一個(gè)節(jié)點(diǎn)死亡時(shí)間）延長(zhǎng)了30%左右,，有效地提升了網(wǎng)絡(luò)性能,。
關(guān)鍵詞： WSN路由協(xié)議,；LEACH；PAM算法,；MATLAB仿真
傳感器技術(shù),、微機(jī)電系統(tǒng)、現(xiàn)代網(wǎng)絡(luò)和無(wú)線通信等技術(shù)的進(jìn)步,，推動(dòng)了具有現(xiàn)代意義的無(wú)線傳感器網(wǎng)絡(luò)的產(chǎn)生和發(fā)展[1]?，F(xiàn)在無(wú)線傳感器網(wǎng)絡(luò)已經(jīng)非常廣泛，軍事,、環(huán)境監(jiān)測(cè)和預(yù)報(bào),、健康護(hù)理、建筑物狀態(tài)控制等領(lǐng)域都可以看到無(wú)線傳感器網(wǎng)絡(luò)的影子,。無(wú)線傳感器網(wǎng)絡(luò)的自身特點(diǎn)決定了其特殊性,，由于能量無(wú)法得到補(bǔ)充，能量有限,，因此必須盡可能地節(jié)約能耗以延長(zhǎng)節(jié)點(diǎn)的存活時(shí)間,，節(jié)能降耗便成為了無(wú)線傳感器網(wǎng)絡(luò)研究中一個(gè)熱點(diǎn)。本文在經(jīng)典的LEACH協(xié)議的基礎(chǔ)上提出了LEACH_P(LEACH based on PAM)協(xié)議,，通過(guò)MATLAB仿真驗(yàn)證了其在均衡節(jié)點(diǎn)能耗上的有效性,。
1 LEACH協(xié)議
LEACH[2]是最早提出的基于分簇的層次路由協(xié)議。普通節(jié)點(diǎn)的數(shù)據(jù)經(jīng)由各自簇頭節(jié)點(diǎn)傳給sink節(jié)點(diǎn),，有效減少了整個(gè)網(wǎng)絡(luò)的能量消耗,。同時(shí)，簇頭的選舉使得各個(gè)節(jié)點(diǎn)都能在數(shù)輪之中當(dāng)選一次簇頭,，均衡了簇頭的能量損耗,，有效地提高了網(wǎng)絡(luò)性能。據(jù)計(jì)算,，相比于一般的平面路由協(xié)議,，LEACH可以延長(zhǎng)網(wǎng)絡(luò)周期約15%[3]。
盡管如此,，LEACH協(xié)議仍然有以下不足：
(1)簇的形成為先選舉簇頭再形成簇,，簇頭的選舉具有很大的隨機(jī)性，僅僅依靠生成的隨機(jī)數(shù)來(lái)決定是否成為簇頭,。
(2)簇頭的選舉具有很大的隨機(jī)性,，任何節(jié)點(diǎn)只要其生成的隨機(jī)數(shù)小于閾值T(n)即可當(dāng)選為簇頭，未考慮到節(jié)點(diǎn)的剩余能量,。
(3)簇的形成過(guò)程實(shí)質(zhì)是先選出簇頭再根據(jù)簇頭形成簇,，由于之前的簇頭選舉沒(méi)有考慮到節(jié)點(diǎn)的物理位置，使得可能出現(xiàn)各個(gè)簇內(nèi)成員節(jié)點(diǎn)數(shù)目差距很大,。成員節(jié)點(diǎn)較多的簇內(nèi)簇頭能耗會(huì)非常大,，顯然不利于延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間,。
2 PAM算法
PAM算法是由KAUFMAN L和ROUSSENUW P J等人提出的一種中心點(diǎn)劃分聚類算法[4]。算法策略如下,。
在數(shù)據(jù)集中隨機(jī)選擇k個(gè)對(duì)象作為中心點(diǎn),，其余節(jié)點(diǎn)皆為非中心點(diǎn)。算法反復(fù)使用非中心點(diǎn)來(lái)試圖替換中心點(diǎn),，基于各種可能的組合，估算聚類結(jié)果的質(zhì)量,。一個(gè)中心點(diǎn)Oi如果可以被一個(gè)非中心點(diǎn)對(duì)象Oh所代替,，那么這次迭代過(guò)程中的Oh將被作為新的中心點(diǎn)出現(xiàn)在下一輪迭代中，算法運(yùn)算直至最終收斂,。
非中心節(jié)點(diǎn)Oh試圖替換中心節(jié)點(diǎn)Oi時(shí),， PAM算法為每一個(gè)非中心點(diǎn)Oj計(jì)算代價(jià)Cjih，Cjih的值存在以下4種情況,，如圖1所示,。
(1)Oj屬于中心點(diǎn)Oi。如果Oi被Oh替換后,，Oj離另外一個(gè)中心點(diǎn)Om更近,，那么Oj加入Om，此時(shí),，Cjih=Distance（j,，m）-Distance（j，i）,。
(2)Oj屬于中心點(diǎn)Oi,。如果Oi被Oh替換后，Oj離Oh更近,，那么Oj加入Oh,。此時(shí)，Cjih=Distance（j,，h）-Distance（j,，i）。
(3)Oj屬于中心點(diǎn)Om,。如果Oi被Oh替換后,，Oj還是離Om更近，那么對(duì)象的隸屬關(guān)系保持不變,。此時(shí),，Cjih=0。
(4)Oj屬于中心點(diǎn)Om,。如果Oi被Oh替換后,，Oj還是離Oh更近,，那么Oj加入Oh的簇。此時(shí),，Cjih=Distance(j,，h)-Distance(j，m),。
其中,，Distance（i，j）表示點(diǎn)i到點(diǎn)j的距離,，此處使用歐幾里得距離,。
計(jì)算替換產(chǎn)生的總代價(jià)函數(shù)TC=Cjih，其中j為除節(jié)點(diǎn)h和i之外的其余所有節(jié)點(diǎn),。如果TC<0,，說(shuō)明替換后的中心點(diǎn)更接近簇的中心，分簇更加合理,，執(zhí)行中心節(jié)點(diǎn)的替換過(guò)程,；否則，不進(jìn)行中心節(jié)點(diǎn)的替換,。
LEACH_P協(xié)議是基于LEACH進(jìn)行的改進(jìn),，所以協(xié)議運(yùn)行流程大致相同，同樣是以輪（round）為單位,。不同于LEACH協(xié)議的是,，LEACH_P改變了原來(lái)LEACH協(xié)議的先選舉簇頭再形成簇的構(gòu)造順序，改為先使用PAM算法對(duì)初始簇進(jìn)行均勻分簇,，而后再進(jìn)行簇頭的選舉,。之后分簇的結(jié)果將在一段較長(zhǎng)的時(shí)間內(nèi)保持不變，直到死亡節(jié)點(diǎn)的增加數(shù)目達(dá)到一定量再重新進(jìn)行分簇,。簇頭的選舉在每一輪結(jié)束后都會(huì)進(jìn)行,。在每一輪的簇頭選舉過(guò)后，接著進(jìn)行數(shù)據(jù)傳輸,，數(shù)據(jù)傳輸階段與LEACH協(xié)議完全一樣,，這里不再贅述?？偟膩?lái)說(shuō),，LEACH_P協(xié)議包含簇的形成、簇頭選舉和數(shù)據(jù)傳輸三個(gè)部分,。下面著重介紹簇的形成和簇頭選舉兩個(gè)部分,。
2.1 簇的形成
簇的形成即對(duì)拓?fù)渲械墓?jié)點(diǎn)進(jìn)行分簇，分簇后使得各個(gè)簇內(nèi)的節(jié)點(diǎn)分布更加緊湊，有利于縮短數(shù)據(jù)傳輸距離,，節(jié)省數(shù)據(jù)傳輸時(shí)消耗的能量,。分簇并不是每一輪都進(jìn)行，在協(xié)議運(yùn)行開(kāi)始時(shí)進(jìn)行初始分簇,，之后只有當(dāng)死亡節(jié)點(diǎn)數(shù)的增量達(dá)到一定量時(shí),，才會(huì)在下一輪開(kāi)始時(shí)先重新分簇，以此規(guī)避由于節(jié)點(diǎn)死亡帶來(lái)的簇頭節(jié)點(diǎn)負(fù)載不均衡,。使用PAM算法對(duì)原始拓?fù)溥M(jìn)行分簇時(shí),，需要確定分簇的數(shù)目k。k的值不能過(guò)大,，否則就不能最大化分簇路由帶來(lái)的能量節(jié)省,。k的值也不能過(guò)小，這樣會(huì)使單個(gè)簇頭需要負(fù)擔(dān)的簇內(nèi)節(jié)點(diǎn)過(guò)多,，簇頭節(jié)點(diǎn)能量消耗過(guò)快，也不利于整個(gè)網(wǎng)絡(luò)性能的提升,。根據(jù)參考文獻(xiàn)[5],，假設(shè)傳感器節(jié)點(diǎn)均為相似二維空間λ泊松分布，則可以得到最優(yōu)的簇頭節(jié)點(diǎn)百分比為：
其中,，c為區(qū)域邊長(zhǎng)的一半,，由節(jié)點(diǎn)總數(shù)即可求得分簇的數(shù)目。
分簇算法包括以下幾個(gè)步驟：
(1)從初始數(shù)據(jù)集中隨機(jī)選擇k=p×N（節(jié)點(diǎn)總數(shù)）個(gè)節(jié)點(diǎn)作為臨時(shí)中心點(diǎn)Oi,。
(2)將剩余節(jié)點(diǎn)依照距離最短原則選擇距離最近的臨時(shí)中心點(diǎn)加入其簇,。
(3)選擇一個(gè)異于中心點(diǎn)Oi的非中心點(diǎn)Oh，試圖用Oh替換Oi作為新的中心點(diǎn),。
(4)計(jì)算替換產(chǎn)生的總代價(jià)TC,，如果TC<0，則進(jìn)行替換操作,，此后Oh作為新的中心點(diǎn)存在,。
(5)跳到步驟(3)，直達(dá)所有可能的“替換對(duì)”都進(jìn)行替換試探完畢后停止,，最終形成新的k個(gè)臨時(shí)中心點(diǎn)Oi,，一輪迭代過(guò)程完成。
(6)跳轉(zhuǎn)到步驟(2),，進(jìn)行下一輪的迭代,，直到達(dá)到迭代次數(shù)，跳轉(zhuǎn)到步驟(7),。
(7)迭代過(guò)程完成,，中心點(diǎn)Oi選擇完畢。
(8)其余非中心點(diǎn)Oj根據(jù)到各個(gè)中心點(diǎn)Oi的距離選擇距離最近的中心點(diǎn)加入其簇,。
(9)分簇完畢,，形成k個(gè)簇,。
2.2 簇頭選舉
經(jīng)過(guò)分簇后，分出的各個(gè)簇節(jié)點(diǎn)數(shù)較為平均,，各個(gè)簇內(nèi)節(jié)點(diǎn)間間距較小,。簇頭選擇應(yīng)該兼顧簇頭節(jié)點(diǎn)的剩余能量和簇頭節(jié)點(diǎn)的位置。
2.2.1 首輪簇頭選舉
首輪由于所有節(jié)點(diǎn)的剩余能量大體相同,，簇頭的選擇基于節(jié)點(diǎn)剩余能量的考慮可以忽略,，主要從節(jié)點(diǎn)的位置考慮選舉簇頭。根據(jù)參考文獻(xiàn)[6],，當(dāng)?shù)趇個(gè)簇內(nèi)的非簇頭節(jié)點(diǎn)向j傳輸數(shù)據(jù)時(shí),，系統(tǒng)消耗的總能量取決于?撞dij2（簇內(nèi)距離較近，使用多路徑衰減模型）,，盡量減小撞dij2即可實(shí)現(xiàn)節(jié)省能耗,。令第j個(gè)簇的簇頭節(jié)點(diǎn)的坐標(biāo)為（Xj，Yj）,，簇內(nèi)的非簇頭節(jié)點(diǎn)坐標(biāo)為（Xn,，Yn），節(jié)點(diǎn)總數(shù)為M,，所以分簇?cái)?shù)的個(gè)數(shù)為M×p,；簇j內(nèi)節(jié)點(diǎn)數(shù)目為Nj（包括簇頭）。計(jì)算得到第j個(gè)簇內(nèi)非簇頭節(jié)點(diǎn)到簇頭節(jié)點(diǎn)之間距離平方的數(shù)學(xué)期望：
2.2.2 首輪之后輪次的簇頭選舉
首輪之后輪次的簇頭選舉應(yīng)該綜合考慮到節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的物理位置,。首輪之后的簇頭選擇策略是：以簇的中心（幾何中心）為中心點(diǎn),，以半徑r作圓。在此圓中,，選擇剩余能量最多的節(jié)點(diǎn)作為簇頭,。首輪中，簇頭節(jié)點(diǎn)位置較為居中,，簇內(nèi)其余非簇頭節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的距離不同,，而非簇頭節(jié)點(diǎn)的發(fā)送數(shù)據(jù)能耗與傳輸距離有直接關(guān)系。一輪過(guò)后,，靠近簇邊緣的節(jié)點(diǎn)剩余能量相對(duì)較小,，所以應(yīng)該選擇離簇頭近的節(jié)點(diǎn)作為簇頭。數(shù)輪過(guò)后,，離簇頭較近的節(jié)點(diǎn)可能都已經(jīng)當(dāng)選過(guò)簇頭,，由于作為簇頭的能量耗損較大，此時(shí)整個(gè)簇頭的剩余能量區(qū)域分布情況是簇邊緣的節(jié)點(diǎn)剩余能量多,，簇中間的節(jié)點(diǎn)剩余能量較小,。此后應(yīng)該盡量選擇這些邊緣節(jié)點(diǎn)作為簇頭。LEACH_P協(xié)議的策略是每隔數(shù)輪N將半徑r增大20%，每次增大的半徑幅度都為0.2r,，當(dāng)半徑增大到2.5r后,，再過(guò)一段時(shí)間，半徑重新調(diào)整到r,，之后重復(fù)前面的步驟繼續(xù)進(jìn)行,。總之,，首輪之后的簇頭選擇是：在以各個(gè)簇中心為原點(diǎn),，以r為半徑的圓內(nèi)選擇剩余能量最大的節(jié)點(diǎn)作為簇頭，間隔N輪后,，r增大20%,，當(dāng)半徑增大到2.5r后，半徑重新回歸到r,，從頭再進(jìn)行遞增,。
3 仿真分析
本文使用MATLAB作為實(shí)驗(yàn)工具進(jìn)行仿真。實(shí)驗(yàn)中,，100個(gè)節(jié)點(diǎn)隨機(jī)分布在100×100的區(qū)域內(nèi),，節(jié)點(diǎn)總數(shù)為100個(gè)。匯聚節(jié)點(diǎn)sink位于拓?fù)涞闹行奈恢?，坐?biāo)為(50,，50),。節(jié)點(diǎn)當(dāng)選為簇頭的概率p取0.05,。實(shí)驗(yàn)中用到的其他主要參數(shù)如表1所示，所采用的拓?fù)鋱D如圖2所示,。
圖2是使用LEACH_P協(xié)議進(jìn)行首輪分簇的結(jié)果,。可以看出,，使用PAM算法對(duì)初始拓?fù)鋱D進(jìn)行聚類能夠取得比較好的聚類結(jié)果,。各個(gè)聚簇內(nèi)的節(jié)點(diǎn)數(shù)目比較平均，簇的大小相似,，這樣有利于簇頭節(jié)點(diǎn)均衡能耗,，各個(gè)簇頭的輪平均能耗更為接近。
本實(shí)驗(yàn)主要從節(jié)點(diǎn)能量總耗費(fèi)和死亡節(jié)點(diǎn)數(shù)對(duì)實(shí)驗(yàn)進(jìn)行分析,。各輪總能量消耗圖如圖3所示,。LEACH_P協(xié)議和LEACH協(xié)議在各輪中的總能量耗損非常接近，并且會(huì)在很長(zhǎng)的一段時(shí)間內(nèi)保持這種趨勢(shì),。其中的原因是：使用PAM算法能夠帶來(lái)比較好的分簇結(jié)果,。但是，即便如此，各輪中總的數(shù)據(jù)傳輸距離（包括簇內(nèi)節(jié)點(diǎn)到簇頭節(jié)點(diǎn)的距離和簇頭節(jié)點(diǎn)到簇內(nèi)節(jié)點(diǎn)的距離）大體相同,，所以總的能量耗損曲線基本上重合在一起,。在之后的340輪左右，LEACH_P(NEW)協(xié)議的曲線開(kāi)始凸顯出來(lái),，同時(shí)在之后的50輪中,，LEACH_P協(xié)議的總能耗會(huì)與LEACH協(xié)議的能耗進(jìn)一步拉大，這是由于LEACH協(xié)議中各節(jié)點(diǎn)的剩余能量分布不均勻造成的,。LEACH分簇沒(méi)有考慮到節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的地理位置,，進(jìn)行分簇的結(jié)果又不盡理想，使得最終節(jié)點(diǎn)間的剩余能量差距較大,。仿真結(jié)束后,，會(huì)余下一些不能再次成簇的節(jié)點(diǎn)。下面通過(guò)分析剩余節(jié)點(diǎn)圖來(lái)補(bǔ)充說(shuō)明圖3中最后50輪曲線變化的原因,。
剩余節(jié)點(diǎn)對(duì)比圖如圖4所示,。LEACH協(xié)議第一個(gè)節(jié)點(diǎn)死亡的時(shí)間是在245輪左右，而LEACH_P協(xié)議則是在350輪左右,。LEACH_P協(xié)議使得整個(gè)網(wǎng)絡(luò)的生命周期延長(zhǎng)了30%左右,。LEACH協(xié)議中節(jié)點(diǎn)死亡20%是在330輪左右，而LEACH_P協(xié)議則是在350輪,；LEACH協(xié)議中節(jié)點(diǎn)死亡率為80%經(jīng)歷的輪數(shù)為145輪,，而LEACH_P協(xié)議只有用30輪。LEACH_P協(xié)議在如此短的時(shí)間內(nèi)節(jié)點(diǎn)大量死亡,，是因?yàn)檎麄€(gè)網(wǎng)絡(luò)的能量均衡效果比較好,，節(jié)點(diǎn)的剩余能量值接近，單一節(jié)點(diǎn)的死亡預(yù)示其他節(jié)點(diǎn)的能量也快耗盡,。網(wǎng)絡(luò)生命周期的延長(zhǎng)原因也正是如此,，能量消耗能夠分擔(dān)到每個(gè)節(jié)點(diǎn)，同時(shí)分擔(dān)的份額也較為平均,。而在LEACH中,，非均衡的能量損耗使得節(jié)點(diǎn)的剩余能量差異較大。均衡整個(gè)網(wǎng)絡(luò)的能量損耗到各個(gè)節(jié)點(diǎn),，使得整個(gè)網(wǎng)絡(luò)的性能大幅提高,。圖4中，仿真結(jié)束后,，LEACH協(xié)議中剩余存活的節(jié)點(diǎn)達(dá)到13個(gè),，LEACH_P中為5個(gè)，這也正是圖3中仿真結(jié)束后LEACH比LEACH_P協(xié)議剩余的能量多的原因,。
本文在LEACH協(xié)議基礎(chǔ)上提出了LEACH_P算法,，通過(guò)PAM算法對(duì)拓?fù)溥M(jìn)行分簇,，之后再選舉簇頭。仿真實(shí)驗(yàn)證明了其在均衡節(jié)點(diǎn)能耗上取得了比較好的結(jié)果,，LEACH_P協(xié)議能夠利用整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)來(lái)均衡網(wǎng)絡(luò)能量損耗,，使得整個(gè)網(wǎng)絡(luò)的生存周期提高了30%，增強(qiáng)了網(wǎng)絡(luò)性能,。接下來(lái)的研究方向是如何在均衡能耗的前提下減少單輪網(wǎng)絡(luò)總能耗,。
參考文獻(xiàn)
[1] 孫利民.無(wú)線傳感器網(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] 胡興華,，駱堅(jiān),，譚珊珊，等.固定簇的LEACH半徑自適應(yīng)簇頭改進(jìn)算法[J].傳感技術(shù)學(xué)報(bào),，2011,，24（1）：79-82.