摘 要： 提出一種基于PEGASIS的路由改進算法，引入記憶和比較的方法尋找最優可連接的節點，避免產生長鏈，從而導致部分節點因傳輸距離過大和耗能過多而過快死亡。給出了一種均衡各節點能耗的新簇頭選擇方案，對該模型的系統總能耗進行量化分析。通過仿真證明，該方案相對普通PEGASIS路由算法消耗能量更低，延長了網絡壽命。
關鍵詞： PEGASIS；能耗；記憶策略；能距比；無線傳感器網絡
低功耗無線通信技術、微型傳感器技術和計算機嵌入式技術的迅猛發展，使各種大量無線傳感器自主構建成無線傳感器網絡成為現實。在無線傳感器網絡中，由于其節點能量非常有限，無法進行補充，一旦節點能量耗盡，會給通信和信息的采集帶來嚴重的障礙。因此，如何構建無線傳感器網絡來提高能量的有效性、延長網絡壽命、避免網絡分裂、均衡節點能耗、降低傳輸時延成為學者們討論的主要話題。本文以鏈式PEGASIS協議為基礎，改進協議避免產生長鏈消耗過多能量，提出新的簇頭選擇方法，并進行量化研究。
1 協議分析及改進
1.1 協議知識
PEGASIS協議是一種典型基于鏈狀結構的路由協議，是LEACH協議的改進。PEGASIS算法的核心思想是利用貪婪算法生成一條單鏈，然后隨機選擇鏈中一個節點作為簇頭節點，為了延長網絡生命周期，每個節點只與最近的節點進行通信，然后將數據匯總給簇頭節點，由簇頭節點將數據發給基站。
PEGASIS協議的成鏈過程按輪進行，首先從距離基站最遠的節點開始建鏈，將此節點作為端節點，然后查找它的最近節點，并將此最近節點加入鏈中，再由新加入的節點搜索除了原端點以外的最近節點，如此尋找下去，直到將所有節點形成一個單鏈，并且隨機選出簇頭節點。圖1為鏈形成的流程。其中END表示當前節點，CHAIN表示形成的鏈。
鏈中的數據發送模式為：簇頭節點首先給兩端節點發送一個TOKEN，然后兩端節點將收集到的數據發送給鏈中上一個節點，上一個節點接收到數據以后，融合自身的數據后再發送到上一個節點，直到兩邊都將數據發送給簇頭節點。簇頭節點最后融合兩邊收到的數據，再與基站進行通信。
相比LEACH算法，PEGASIS路由算法減少了節點之間的通信平均距離，也不需要動態形成簇而產生的額外開銷，只有一個簇頭節點將數據傳送到基站，節省了能量的消耗。但是此方案也存在嚴重的缺點，圖2(a)為隨機生成的20個節點，圖2(b)為經過PEGASIS路由算法后形成的鏈，從中可見，節點11與12、16與17、18與19之間的鏈路距離相對于別的節點間距離明顯偏大，因此會造成11、16、18這三個節點發送數據的耗能過大，導致這幾個節點過早死亡，阻斷通信。為了實現節能，必須改進這些長鏈鏈路，更新路由算法，在建鏈過程中防止長鏈產生。
1.2 改進協議
針對以上提出的問題，已經有學者提出了一種設立一個距離門限，每兩個節點之間的距離與門限值比較，根據節點間距離與門限的比較來確定把新節點加入鏈，還是繼續尋找其他節點[1]；參考文獻[2-3]提出一種分層樹成鏈的方法節能，但也沒有充分考慮長鏈問題；參考文獻[4]采用分區來避免長鏈，但沒有考慮部分簇頭輪換。
本文提出一種記憶式的M-PEGASIS路由算法，其成鏈流程圖如圖3所示。該算法還是遵循PEGASIS協議算法，但是增加一個記憶比較模塊，即由距離基站最遠的節點N開始尋找入鏈，此時初始化記憶節點Mem為空（認為任何節點和空節點的距離無窮大），找出距離N最近的節點N+1，隨后計算N+1與N以及記憶節點Mem的距離D和Dm，然后對兩個距離進行比較，如果D<Dm，則說明N+1與N的距離比N+1與記憶節點近，N+1與N連接，最后將N節點賦值給Mem節點，N+1節點賦值給N節點；反之則N+1節點與記憶節點連接，N+1賦值給N，Mem節點不變, 繼續進入循環尋找下一個入鏈節點。
用此新方法分析圖2中節點11到節點12的長鏈，此時記憶節點Mem為節點10，當前節點N為節點11，節點11尋找離它最近的未入鏈節點，找到節點12，并且算出到節點12的距離，然后再計算出節點12與記憶節點10之間的距離，發現到記憶節點10之間的距離明顯小于到當前節點11的距離，因此，節點12與記憶節點10連接，此時節點12為當前節點N，記憶節點依舊是10。圖4為無線傳感器網絡中，運用PEGASIS協議與運用M-PEGASIS協議的對比圖。很明顯，運用M-PEGASIS方法有效避免了長鏈的產生，為無線傳感器網絡的數據傳輸節省了能量。
取比值大的節點作為該輪通信的簇頭節點，考慮到簇頭節點與基站通信的耗能比普通節點多，故需要進行簇頭的輪換，簇頭輪換選擇機制也按照Q值的大小，簇頭節點每隔20輪通信檢測一次該Q值。當該Q值降低到通信前Q值的50%時，該鏈啟動簇頭重選機制，重新根據Q值的大小排序選出新的簇頭節點。如此算法不但避免了某些節點耗能過多而過早死亡，造成網絡分裂，影響通信，還大大地增加了無線傳感器網絡壽命，均衡了各節點能量消耗。
2 量能分析
在此量能分析中，假定基站位于眾節點的正上方，且各個節點的初始能量相同，遵循能量消耗與距離成正相關的關系，為了節省簇頭節點的能耗，延長簇頭節點的生命，將簇頭節點設定為距離基站最近的節點。在此模型中，假設鏈中共有c個節點，每一個節點傳輸的數據長度都是L bit，則除簇頭節點以外，本地通信中每個節點都進行了一次數據傳輸，不考慮節點內部數據融合等其他時延，得到能耗公式推導如下：
鏈內本地能耗由下面兩部分組成：
3 仿真分析
為了證實M-PEGASIS算法相比普通PEGASIS算法有更高的節能效果，對其進行相應的仿真。在長寬各為50 m的正方形區域內，隨機生成了100個節點，將基站的位置定在坐標點(25，200)處，數據包長度為1 000 bit，采用參考文獻[6]中的能量映射模型，并且假設開始每個節點都具有相同的能量，用通信的輪數來表示節點的壽命。PEGASIS算法與M-PEGASIS算法的節點存活對比仿真結果如圖5、圖6、圖7所示。
根據仿真結果可知，PEGASIS算法中，1%、20%、50%、100%節點死亡時間在700輪、1 100輪、1 200輪和1 380輪附近，此結果與參考文獻[7]中得出的結論相符。改進算法M-PEGASIS中，1%、20%、50%和100%節點死亡時間推遲到了1 600輪、1 680輪、1 800輪和1 890輪，這是由于當簇頭Q值降低到通信前一半時引入簇頭輪換機制，所以出現第一個死亡節點的時間大大推遲了，但是當死亡節點開始出現以后，此時各節點的能量普遍已經很低，故節點死亡速度很快。即使這樣，在沒有增加算法復雜度的情況下，也使時間上有了40%～50%左右的提升。
本文分析了經典的鏈式PEGASIS算法，雖然此算法相對于LEACH算法能耗方面有了很大的降低，但是還存在著很大的不足：(1)在節點比較多的情況下很容易產生長鏈，從而增加節點間傳輸的距離，增加了部分節點的能耗，導致這些節點過早的死亡，影響網絡效率；(2)鏈的簇頭選擇方式為隨機選擇，具有很大的不確定性，并且導致節點間能耗不均勻。分析了以上兩個缺點，本文提出了一種記憶式的改進路由算法，避免了成鏈過程中長鏈的產生，進而節約并均衡能耗。又對簇頭選擇的方式從節約能耗的角度加入了一定的選擇方法，進一步平衡了節點能耗，延長了網絡壽命。
然而，基于此路由算法的無線傳感器網絡雖然能有效節約能量消耗，但也存在一定問題，當在一個無線傳感器節點數目很大的傳感器集群中，運用此方法收集傳遞數據，往往會造成比較大的時延，形成一條帶分支的鏈也是一項很大的工作，并且隨著部分節點的死亡，Q值的降低，導致鏈的頻繁重構，也是對網絡的一種巨大的消耗，更影響了網絡的健壯性，因此接下來還可以在成鏈方面有新的改進，例如對每條鏈的節點數目限定一個上限值，從而在數目巨大的傳感器網絡中形成多條子鏈，然后再將每個子鏈的簇頭按照同樣的路由算法形成一個父鏈，進一步適應大型無線傳感器網絡集群。
參考文獻
[1] 余永昌，韋崗.無線傳感器網絡中基于PEGASIS協議的改進算法[J].電子學報，2008，36(7)：1309-1315.
[2] 王波，蔣衛，孫燚.改進PEGASIS的分層鏈樹路由協議[J].計算機系統應用，2009(12)：98-102.
[3] 吳聯芳，張昱，金心宇.基于模擬退火算法的無線傳感網PEGASIS算法[J].江南大學學報，2008，7(4)：438-442.
[4] 陳慧娜，唐明浩.基于PEGASIS的改進型WSN路由協議[J].計算機工程，2010，36(19)：134-136.
[5] Cui Shuguag，GOLDSMITH A J，BAHAI A.Energy constrained modulation optimization for coded systems[C].Proc.of IEEE GLOBECOM’03.2003.
[6] HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.An application specific protocol for wireless mirco-sensor networks[J].IEEE Tram Wireless Communications，2002，1(4)：660-670
[7] LINDSEY S，CAULIGI S.Raghavendra PEGASIS：powerefficient gathering in sensor information systems[C].Conference Proceedings，2002.