摘  要： 提出一種基于PEGASIS的路由改進(jìn)算法,，引入記憶和比較的方法尋找最優(yōu)可連接的節(jié)點(diǎn),，避免產(chǎn)生長(zhǎng)鏈，從而導(dǎo)致部分節(jié)點(diǎn)因傳輸距離過大和耗能過多而過快死亡,。給出了一種均衡各節(jié)點(diǎn)能耗的新簇頭選擇方案,，對(duì)該模型的系統(tǒng)總能耗進(jìn)行量化分析。通過仿真證明,，該方案相對(duì)普通PEGASIS路由算法消耗能量更低,，延長(zhǎng)了網(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ò)來提高能量的有效性,、延長(zhǎng)網(wǎng)絡(luò)壽命,、避免網(wǎng)絡(luò)分裂、均衡節(jié)點(diǎn)能耗,、降低傳輸時(shí)延成為學(xué)者們討論的主要話題,。本文以鏈?zhǔn)絇EGASIS協(xié)議為基礎(chǔ)，改進(jìn)協(xié)議避免產(chǎn)生長(zhǎng)鏈消耗過多能量,，提出新的簇頭選擇方法,，并進(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),，為了延長(zhǎng)網(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之間的鏈路距離相對(duì)于別的節(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)這些長(zhǎng)鏈鏈路，更新路由算法,，在建鏈過程中防止長(zhǎng)鏈產(chǎn)生,。

1.2 改進(jìn)協(xié)議
    針對(duì)以上提出的問題，已經(jīng)有學(xué)者提出了一種設(shè)立一個(gè)距離門限,，每?jī)蓚€(gè)節(jié)點(diǎn)之間的距離與門限值比較，根據(jù)節(jié)點(diǎn)間距離與門限的比較來確定把新節(jié)點(diǎn)加入鏈,，還是繼續(xù)尋找其他節(jié)點(diǎn)[1],；參考文獻(xiàn)[2-3]提出一種分層樹成鏈的方法節(jié)能，但也沒有充分考慮長(zhǎng)鏈問題,；參考文獻(xiàn)[4]采用分區(qū)來避免長(zhǎng)鏈,，但沒有考慮部分簇頭輪換。
    本文提出一種記憶式的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,，然后對(duì)兩個(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的長(zhǎng)鏈,，此時(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é)議的對(duì)比圖。很明顯,，運(yùn)用M-PEGASIS方法有效避免了長(zhǎng)鏈的產(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輪通信檢測(cè)一次該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)的能耗,，延長(zhǎng)簇頭節(jié)點(diǎn)的生命，將簇頭節(jié)點(diǎn)設(shè)定為距離基站最近的節(jié)點(diǎn),。在此模型中,，假設(shè)鏈中共有c個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)長(zhǎng)度都是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é)能效果,，對(duì)其進(jìn)行相應(yīng)的仿真。在長(zhǎng)寬各為50 m的正方形區(qū)域內(nèi),，隨機(jī)生成了100個(gè)節(jié)點(diǎn),，將基站的位置定在坐標(biāo)點(diǎn)(25，200)處,，數(shù)據(jù)包長(zhǎng)度為1 000 bit,，采用參考文獻(xiàn)[6]中的能量映射模型，并且假設(shè)開始每個(gè)節(jié)點(diǎn)都具有相同的能量,，用通信的輪數(shù)來表示節(jié)點(diǎn)的壽命,。PEGASIS算法與M-PEGASIS算法的節(jié)點(diǎn)存活對(duì)比仿真結(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算法,，雖然此算法相對(duì)于LEACH算法能耗方面有了很大的降低，但是還存在著很大的不足：(1)在節(jié)點(diǎn)比較多的情況下很容易產(chǎn)生長(zhǎng)鏈,，從而增加節(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)路由算法,，避免了成鏈過程中長(zhǎng)鏈的產(chǎn)生,，進(jìn)而節(jié)約并均衡能耗。又對(duì)簇頭選擇的方式從節(jié)約能耗的角度加入了一定的選擇方法,，進(jìn)一步平衡了節(jié)點(diǎn)能耗,，延長(zhǎng)了網(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),，也是對(duì)網(wǎng)絡(luò)的一種巨大的消耗,，更影響了網(wǎng)絡(luò)的健壯性，因此接下來還可以在成鏈方面有新的改進(jìn),，例如對(duì)每條鏈的節(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.