摘  要： 提出一種基于PEGASIS的路由改進算法，引入記憶和比較的方法尋找最優(yōu)可連接的節(jié)點，避免產(chǎn)生長鏈，從而導(dǎo)致部分節(jié)點因傳輸距離過大和耗能過多而過快死亡。給出了一種均衡各節(jié)點能耗的新簇頭選擇方案，對該模型的系統(tǒng)總能耗進行量化分析。通過仿真證明，該方案相對普通PEGASIS路由算法消耗能量更低，延長了網(wǎng)絡(luò)壽命。
關(guān)鍵詞： PEGASIS；能耗；記憶策略；能距比；無線傳感器網(wǎng)絡(luò)

    低功耗無線通信技術(shù)、微型傳感器技術(shù)和計算機嵌入式技術(shù)的迅猛發(fā)展，使各種大量無線傳感器自主構(gòu)建成無線傳感器網(wǎng)絡(luò)成為現(xiàn)實。在無線傳感器網(wǎng)絡(luò)中，由于其節(jié)點能量非常有限，無法進行補充，一旦節(jié)點能量耗盡，會給通信和信息的采集帶來嚴(yán)重的障礙。因此，如何構(gòu)建無線傳感器網(wǎng)絡(luò)來提高能量的有效性、延長網(wǎng)絡(luò)壽命、避免網(wǎng)絡(luò)分裂、均衡節(jié)點能耗、降低傳輸時延成為學(xué)者們討論的主要話題。本文以鏈?zhǔn)絇EGASIS協(xié)議為基礎(chǔ)，改進協(xié)議避免產(chǎn)生長鏈消耗過多能量，提出新的簇頭選擇方法，并進行量化研究。
1 協(xié)議分析及改進
1.1 協(xié)議知識
    PEGASIS協(xié)議是一種典型基于鏈狀結(jié)構(gòu)的路由協(xié)議，是LEACH協(xié)議的改進。PEGASIS算法的核心思想是利用貪婪算法生成一條單鏈，然后隨機選擇鏈中一個節(jié)點作為簇頭節(jié)點，為了延長網(wǎng)絡(luò)生命周期，每個節(jié)點只與最近的節(jié)點進行通信，然后將數(shù)據(jù)匯總給簇頭節(jié)點，由簇頭節(jié)點將數(shù)據(jù)發(fā)給基站。
    PEGASIS協(xié)議的成鏈過程按輪進行，首先從距離基站最遠的節(jié)點開始建鏈，將此節(jié)點作為端節(jié)點，然后查找它的最近節(jié)點，并將此最近節(jié)點加入鏈中，再由新加入的節(jié)點搜索除了原端點以外的最近節(jié)點，如此尋找下去，直到將所有節(jié)點形成一個單鏈，并且隨機選出簇頭節(jié)點。圖1為鏈形成的流程。其中END表示當(dāng)前節(jié)點，CHAIN表示形成的鏈。

    鏈中的數(shù)據(jù)發(fā)送模式為：簇頭節(jié)點首先給兩端節(jié)點發(fā)送一個TOKEN，然后兩端節(jié)點將收集到的數(shù)據(jù)發(fā)送給鏈中上一個節(jié)點，上一個節(jié)點接收到數(shù)據(jù)以后，融合自身的數(shù)據(jù)后再發(fā)送到上一個節(jié)點，直到兩邊都將數(shù)據(jù)發(fā)送給簇頭節(jié)點。簇頭節(jié)點最后融合兩邊收到的數(shù)據(jù)，再與基站進行通信。
    相比LEACH算法，PEGASIS路由算法減少了節(jié)點之間的通信平均距離，也不需要動態(tài)形成簇而產(chǎn)生的額外開銷，只有一個簇頭節(jié)點將數(shù)據(jù)傳送到基站，節(jié)省了能量的消耗。但是此方案也存在嚴(yán)重的缺點，圖2(a)為隨機生成的20個節(jié)點，圖2(b)為經(jīng)過PEGASIS路由算法后形成的鏈，從中可見，節(jié)點11與12、16與17、18與19之間的鏈路距離相對于別的節(jié)點間距離明顯偏大，因此會造成11、16、18這三個節(jié)點發(fā)送數(shù)據(jù)的耗能過大，導(dǎo)致這幾個節(jié)點過早死亡，阻斷通信。為了實現(xiàn)節(jié)能，必須改進這些長鏈鏈路，更新路由算法，在建鏈過程中防止長鏈產(chǎn)生。

1.2 改進協(xié)議
    針對以上提出的問題，已經(jīng)有學(xué)者提出了一種設(shè)立一個距離門限，每兩個節(jié)點之間的距離與門限值比較，根據(jù)節(jié)點間距離與門限的比較來確定把新節(jié)點加入鏈，還是繼續(xù)尋找其他節(jié)點[1]；參考文獻[2-3]提出一種分層樹成鏈的方法節(jié)能，但也沒有充分考慮長鏈問題；參考文獻[4]采用分區(qū)來避免長鏈，但沒有考慮部分簇頭輪換。
    本文提出一種記憶式的M-PEGASIS路由算法，其成鏈流程圖如圖3所示。該算法還是遵循PEGASIS協(xié)議算法，但是增加一個記憶比較模塊，即由距離基站最遠的節(jié)點N開始尋找入鏈，此時初始化記憶節(jié)點Mem為空（認(rèn)為任何節(jié)點和空節(jié)點的距離無窮大），找出距離N最近的節(jié)點N+1，隨后計算N+1與N以及記憶節(jié)點Mem的距離D和Dm，然后對兩個距離進行比較，如果D<Dm，則說明N+1與N的距離比N+1與記憶節(jié)點近，N+1與N連接，最后將N節(jié)點賦值給Mem節(jié)點，N+1節(jié)點賦值給N節(jié)點；反之則N+1節(jié)點與記憶節(jié)點連接，N+1賦值給N，Mem節(jié)點不變, 繼續(xù)進入循環(huán)尋找下一個入鏈節(jié)點。

    用此新方法分析圖2中節(jié)點11到節(jié)點12的長鏈，此時記憶節(jié)點Mem為節(jié)點10，當(dāng)前節(jié)點N為節(jié)點11，節(jié)點11尋找離它最近的未入鏈節(jié)點，找到節(jié)點12，并且算出到節(jié)點12的距離，然后再計算出節(jié)點12與記憶節(jié)點10之間的距離，發(fā)現(xiàn)到記憶節(jié)點10之間的距離明顯小于到當(dāng)前節(jié)點11的距離，因此，節(jié)點12與記憶節(jié)點10連接，此時節(jié)點12為當(dāng)前節(jié)點N，記憶節(jié)點依舊是10。圖4為無線傳感器網(wǎng)絡(luò)中，運用PEGASIS協(xié)議與運用M-PEGASIS協(xié)議的對比圖。很明顯，運用M-PEGASIS方法有效避免了長鏈的產(chǎn)生，為無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸節(jié)省了能量。
  
    
    取比值大的節(jié)點作為該輪通信的簇頭節(jié)點，考慮到簇頭節(jié)點與基站通信的耗能比普通節(jié)點多，故需要進行簇頭的輪換，簇頭輪換選擇機制也按照Q值的大小，簇頭節(jié)點每隔20輪通信檢測一次該Q值。當(dāng)該Q值降低到通信前Q值的50%時，該鏈啟動簇頭重選機制，重新根據(jù)Q值的大小排序選出新的簇頭節(jié)點。如此算法不但避免了某些節(jié)點耗能過多而過早死亡，造成網(wǎng)絡(luò)分裂，影響通信，還大大地增加了無線傳感器網(wǎng)絡(luò)壽命，均衡了各節(jié)點能量消耗。
2 量能分析
    在此量能分析中，假定基站位于眾節(jié)點的正上方，且各個節(jié)點的初始能量相同，遵循能量消耗與距離成正相關(guān)的關(guān)系，為了節(jié)省簇頭節(jié)點的能耗，延長簇頭節(jié)點的生命，將簇頭節(jié)點設(shè)定為距離基站最近的節(jié)點。在此模型中，假設(shè)鏈中共有c個節(jié)點，每一個節(jié)點傳輸?shù)臄?shù)據(jù)長度都是L bit，則除簇頭節(jié)點以外，本地通信中每個節(jié)點都進行了一次數(shù)據(jù)傳輸，不考慮節(jié)點內(nèi)部數(shù)據(jù)融合等其他時延，得到能耗公式推導(dǎo)如下：
    鏈內(nèi)本地能耗由下面兩部分組成：
  

3 仿真分析
    為了證實M-PEGASIS算法相比普通PEGASIS算法有更高的節(jié)能效果，對其進行相應(yīng)的仿真。在長寬各為50 m的正方形區(qū)域內(nèi)，隨機生成了100個節(jié)點，將基站的位置定在坐標(biāo)點(25，200)處，數(shù)據(jù)包長度為1 000 bit，采用參考文獻[6]中的能量映射模型，并且假設(shè)開始每個節(jié)點都具有相同的能量，用通信的輪數(shù)來表示節(jié)點的壽命。PEGASIS算法與M-PEGASIS算法的節(jié)點存活對比仿真結(jié)果如圖5、圖6、圖7所示。

    根據(jù)仿真結(jié)果可知，PEGASIS算法中，1%、20%、50%、100%節(jié)點死亡時間在700輪、1 100輪、1 200輪和1 380輪附近，此結(jié)果與參考文獻[7]中得出的結(jié)論相符。改進算法M-PEGASIS中，1%、20%、50%和100%節(jié)點死亡時間推遲到了1 600輪、1 680輪、1 800輪和1 890輪，這是由于當(dāng)簇頭Q值降低到通信前一半時引入簇頭輪換機制，所以出現(xiàn)第一個死亡節(jié)點的時間大大推遲了，但是當(dāng)死亡節(jié)點開始出現(xiàn)以后，此時各節(jié)點的能量普遍已經(jīng)很低，故節(jié)點死亡速度很快。即使這樣，在沒有增加算法復(fù)雜度的情況下，也使時間上有了40%～50%左右的提升。
    本文分析了經(jīng)典的鏈?zhǔn)絇EGASIS算法，雖然此算法相對于LEACH算法能耗方面有了很大的降低，但是還存在著很大的不足：(1)在節(jié)點比較多的情況下很容易產(chǎn)生長鏈，從而增加節(jié)點間傳輸?shù)木嚯x，增加了部分節(jié)點的能耗，導(dǎo)致這些節(jié)點過早的死亡，影響網(wǎng)絡(luò)效率；(2)鏈的簇頭選擇方式為隨機選擇，具有很大的不確定性，并且導(dǎo)致節(jié)點間能耗不均勻。分析了以上兩個缺點，本文提出了一種記憶式的改進路由算法，避免了成鏈過程中長鏈的產(chǎn)生，進而節(jié)約并均衡能耗。又對簇頭選擇的方式從節(jié)約能耗的角度加入了一定的選擇方法，進一步平衡了節(jié)點能耗，延長了網(wǎng)絡(luò)壽命。
    然而，基于此路由算法的無線傳感器網(wǎng)絡(luò)雖然能有效節(jié)約能量消耗，但也存在一定問題，當(dāng)在一個無線傳感器節(jié)點數(shù)目很大的傳感器集群中，運用此方法收集傳遞數(shù)據(jù)，往往會造成比較大的時延，形成一條帶分支的鏈也是一項很大的工作，并且隨著部分節(jié)點的死亡，Q值的降低，導(dǎo)致鏈的頻繁重構(gòu)，也是對網(wǎng)絡(luò)的一種巨大的消耗，更影響了網(wǎng)絡(luò)的健壯性，因此接下來還可以在成鏈方面有新的改進，例如對每條鏈的節(jié)點數(shù)目限定一個上限值，從而在數(shù)目巨大的傳感器網(wǎng)絡(luò)中形成多條子鏈，然后再將每個子鏈的簇頭按照同樣的路由算法形成一個父鏈，進一步適應(yīng)大型無線傳感器網(wǎng)絡(luò)集群。
參考文獻
[1] 余永昌，韋崗.無線傳感器網(wǎng)絡(luò)中基于PEGASIS協(xié)議的改進算法[J].電子學(xué)報，2008，36(7)：1309-1315.
[2] 王波，蔣衛(wèi)，孫燚.改進PEGASIS的分層鏈樹路由協(xié)議[J].計算機系統(tǒng)應(yīng)用，2009(12)：98-102.
[3] 吳聯(lián)芳，張昱，金心宇.基于模擬退火算法的無線傳感網(wǎng)PEGASIS算法[J].江南大學(xué)學(xué)報，2008，7(4)：438-442.
[4] 陳慧娜，唐明浩.基于PEGASIS的改進型WSN路由協(xié)議[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.