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