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

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

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

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

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

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

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