基于PEGASIS 的無線傳感器網絡路由協議改進

王海浪，張玲華，2

（1.南京郵電大學通信與信息工程學院，南京 210023；2.南京郵電大學 江蘇省通信與網絡技術工程研究中心，南京 210023）

0 概述

無線傳感器網絡（Wireless Sensor Network，WSN）［1］是一種由數量眾多的傳感器節點自組織而成的網絡，節點通過把數據發送給具有信息處理功能的基站（Base Station，BS）完成信息采集，WSN 可以用于軍事行動、環境監測、醫療健康等領域［2-3］。傳感器節點為了實現信息采集功能，需要在信息采集、數據處理、信息傳遞等過程中消耗節點自身的能量，但是目標節點周圍的環境復雜性和節點數目的龐大性，決定了其不可能在為部署之后的節點進行二次充能和節點的補充［4］，因此傳感器系統的能量會逐漸耗盡，整個網絡最終將走向死亡。因此，如何促進節點的能耗均衡從延長網絡的生命周期，是研究無線傳感器網絡需要考慮的關鍵問題［5］。

由于節點能量和網絡通信能力的限制，如果讓所有節點均和基站直接進行數據傳輸，節點的能量會急劇衰耗，并且會在一定程度上降低網絡的傳輸效率，使延時增大。針對這些問題，國內外研究人員提出分簇的思想。低能量自適應分層分簇（Low Energy Adaptive Clustering Hierarchy，LEACH）協議［6-7］從整個網絡中隨機選取一定數目的簇頭進行信息整合和發送，從而減少節點損耗，但是當距離基站較遠的節點當選簇頭時會造成節點提前死亡。傳感器信息系統能量高效聚集（Power-Efficient Gathering in Sensor Information System，PEGASIS）協議［8-10］減少了LEACH 協議中頻繁的簇頭選舉所帶來的能量損耗，采用輪流當選頭節點的策略進行數據傳輸，但是網絡通信時延較大，當出現傳輸信息的方向和基站位置相反的情況時，會額外增加能耗。文獻［11］提出EPEGASIS 協議，提出移動匯聚技術并通過設置多個閾值來保護即將死亡的節點，平衡了節點間的能量消耗，緩解了因靠近基站的節點在接收鄰居節點信號時產生的熱點問題。但在實際應用中，移動節點容易受到環境因素的影響。文獻［12］提出改進的HCTRP-PEGASIS 路由協議，在成鏈階段綜合傳感器的通信半徑、當前節點周圍密度等因素進行鏈的建立，可以產生較少的數據冗余和較低能耗的傳輸鏈，但有較大的通信延遲。文獻［13］提出能量有效鏈形成算法解決經典PEGASIS 協議貪婪算法中由于某些節點的遠距離數據傳輸所導致的能量消耗不平衡問題，可以避免長鏈的產生，但同樣沒有解決網絡時延較長的問題。文獻［14］提出新型簇頭選舉方式（PEGASIS Novel-Select-Head，PEGASISNSH）的改進協議，該協議始終優先選取距離基站最近的節點作為頭節點，直至當前頭節點死亡才開始下一個頭節點的選取，選取頭節點的策略相對簡單，但沒有很好地均衡能量和降低網絡延遲。

在融合LEACH 協議中多個簇頭思想的基礎上，本文提出一種基于PEGASIS 的剩余能量距離分 區（Residual Energy Distance Partition，REDP）協議，將每個區域內節點的剩余能量、節點到基站的距離、各區域平均能量等多個影響因素作為網絡中頭節點選取條件，從而減少頭節點的更換次數。此 外，對LEACH協議、PEGASIS協議、PEGASISNSH 協議［14］與本文協議進行對比分析，證明本文協議的有效性。

1 系統模型

1.1 網絡模型

基于網絡模型對WSN 做如下的設定［15］：

1）所有的節點除了有可以區分自身和其他節點的唯一標識之外，其他屬性如初始能量、數據融合能力、通信計算能力等完全相同。

2）節點可以根據節點之間的位置或者節點接收到的信號大小確定節點之間的間距和位置信息。

3）在網絡開始運行前，在各個區域隨機地部署傳感器節點，且節點部署后的位置不會改變。

4）基站位于網絡中心，具有穩定的能量供應，但是其余的節點能量有限，不能二次充能。

基于以上設定，本文網絡模型如圖1 所示。

圖1 本文網絡模型Fig.1 Network model in this paper

1.2 網絡能耗模型

本文所有協議的網絡能耗模型均采用一階無線電能耗模型［16-17］，網絡中鄰居節點之間傳遞數據時的能量損耗模型如圖2 所示。

圖2 節點能耗模型Fig.2 Node energy consumption model

從圖2 可以看出節點在進行數據傳輸時的能量消耗過程，其中Eelec為節點在接收或者發送每比特數據時消耗的能量，ETX和ERX分別代表發送數據包和接收數據包所需要的能量消耗，Ed代表數據在傳輸過程中的能量損耗，如式（1）所示，根據傳輸路徑的不同，節點能耗模型分為多徑衰落模型和自由空間模型，當傳輸距離小于閾值d0時為自由空間模型，反之為多徑衰落模型。

其中：εfs和εamp分別代表自由空間模型和多徑衰落模型中的能量損耗因子。在計算傳輸過程中的能耗時，根據節點之間的距離采取不同的能耗策略，其中d0的計算公式如式（2）所示：

對當前節點來說，每一個節點除了在發送和接收信號時消耗能量，還需要對接收的信號進行數據融合，將接收的數據包融合為相同長度的數據包，節點融合一個長度為Kb 的數據包所消耗的能量EDA的表達式如式（3）所示：

其中：Eda代表每比特的數據融合所消耗的能量。

結合PEGASIS 協議在傳輸過程中的特點，除了鏈中末端的節點之外，所有的節點都要進行數據接收、數據融合、數據傳輸等至少3 個過程，因此每一個節點在完成每一輪傳輸過程時需要消耗的總能量E(i)如式（4）和式（5）所示，其中式（5）是結合式（1）、式（3）和式（4）所得。

2 經典PEGASIS 協議

2.1 PEGASIS 協議原理

PEGASIS 協議是一種基于鏈狀結構的路由傳輸協議，是對經典LEACH 協議的改進。此協議包含鏈的形成階段、頭節點的選取階段和數據傳輸階段3 個階段［18］，最后由本輪所選取的頭節點將本網絡的所有信息傳遞給基站，完成一輪數據采集［19］。

2.2 鏈的形成階段

PEGASIS 協議在將整個網絡中的節點成鏈時，為保證每一個節點的通信距離最小，總是從距離基站最遠的節點開始形成鏈［20］。采用貪心算法，將找到所有存活節點中距離當前節點最近的節點作為下一個節點，當串起所有存活的節點成一個網絡時，鏈的形成階段結束。

2.3 頭節點的選取階段

PEGASIS 協議中頭節點的選取策略是將網絡中節點進行編號，根據編號輪流當選頭節點，在第i輪時，當選頭節點的編號為imodn［21］。采用這種選取策略可以使整個網絡中的節點均有機會當選為頭節點［22］，在一定程度上能夠實現能量的均衡消耗。

如圖3 所示為經典的PEGASIS 協議在第1 輪時網絡成鏈的示意圖，所有節點隨機地部署在整個網絡中，BS 位于整個網絡的中心，從圖3 可以看出從距離基站最遠的34 號節點開始成鏈，到47 號節點結束，并且在第1 輪時所選取的頭節點正是編號為1 的節點。

圖3 PEGASIS 協議第1 輪網絡成鏈圖（節點總數n=100）Fig.3 Network forming chain diagram of PEGASIS protocol in the first round（total number of nodes n=100）

2.4 數據傳輸階段

PEGASIS 協議的數據傳輸階段采用Token（令牌）控制機制［23-24］，如圖4 所示，網絡中存在6 個傳感器節點，編號分別為N1、N2、N3、N4、N5、N6。假設在當前輪N4 為頭節點，在數據傳輸時頭節點N4 把Token 沿著鏈傳遞給鏈的末尾N1，N1 將含有本節點采集信息的數據包傳遞給N2，N2在接收數據之后結合自身采集的信息，并進行數據融合，形成一個相同長度的數據包，然后按照相同流程經過節點N3 傳遞給頭節點N4，此時頭節點又將Token 傳遞給N6，然后按照相同的流程把數據包傳遞給頭節點N4，N4將數據包進行融合后發送給基站，本輪的數據傳輸結束。

圖4 PEGASIS 協議數據傳輸過程Fig.4 Process of PEGASIS protocol data transmission

3 PEGASIS-REDP 協議

傳統的PEGASIS 協議采用輪流方式當選頭節點，沒有綜合頭節點距離基站的距離和頭節點剩余的能量問題，因此會在傳遞信息的過程中出現部分剩余能量較少或者距離基站較遠的節點當選頭節點的現象，造成能耗增加。針對這些問題，根據經典協議對PEGASIS-REDP 協議進行改進。

3.1 區域劃分

雖然在經典的PEGASIS 協議成鏈過程中，通常采用貪心算法尋找最近的節點成鏈，但結果也有差鏈和優鏈之分［25］，如圖3 中的17 號和61 號節點即是利用貪心算法形成的差鏈。經過多次仿真結果分析可知，網絡區域越大，就越容易在成鏈的過程中產生差鏈。為避免出現2 個節點間距離過大的差鏈情況發生，本文對網絡進行分區，縮短成鏈過程中節點之間的距離。

分區分為均勻分區和非均勻分區，非均勻分區類似于LEACH 協議中的分簇［26］，普通節點只根據與簇頭的距離遠近情況選取距離最近的簇頭并加入網絡中，但當區域內節點密度較大時，簇內節點數目會急劇增加，導致出現頭節點的能耗加快、節點提前死亡的問題。均勻分區可以很好地解決因為簇內節點數目過多而造成節點提前死亡的問題，在每一個區域內設置相同數目的節點，從而保證區域內節點隨機分布時節點密度相同，以均衡能耗，延長節點的死亡時間。

因此，PEGASIS-REDP 協議提出對整個網絡空間進行均勻分區，并且采用將每個區域單獨成鏈的策略，縮短在差鏈形成時節點之間的距離，從而減少傳輸能耗。

3.2 剩余能量和距離因子

PEGASIS-REDP 協議在區域內選取頭節點時，不再采取輪流當選頭節點的方式，而是綜合考慮節點距離基站的距離d、節點剩余能量Ei、區域內平均能量Eavg等因素。Eavg的表達式如式（6）所示：

其中：Eij表示在第j個區域內編號為i的節點能量；mj表示第j個區域內存活的節點數。

在選取頭節點的過程中，總是從距離基站最近的節點開始當選頭節點，不會頻繁地在每一輪中更換頭節點，且只有當前輪頭節點的剩余能量滿足更換條件時才更換頭節點。因此可以保證在頭節點能量剩余的情況下，始終距離基站最近。如圖5 所示是在第1 輪時采用PEGASIS-REDP 協議分區成鏈的示意圖，其中6 號、50 號、69號和97 號這4 個節點因為距離基站最近，所以在第1 輪中被選取為每一個區域的頭節點。

圖5 PEGASIS-REDP 協議第1 輪網絡成鏈圖（節點總數n=100）Fig.5 Network forming chain diagram of PEGASIS-REDP protocol in the first round（total number of nodes n=100）

圖6 和圖7 分別是在同一網絡部署條件下采用PEGASIS-REDP 協議時，網絡運行到第1 000 輪和第1 100 輪的網絡成鏈圖。

圖6 PEGASIS-REDP 協議第1 000 輪網絡成鏈圖（節點總數n=100）Fig.6 Network forming chain diagram of PEGASIS-REDP protocol in the 1 000th round（total number of nodes n=100）

圖7 PEGASIS-REDP 協議第1 100 輪網絡成鏈圖（節點總數n=100）Fig.7 Network diagram of PEGASIS-REDP protocol in the 1 100th round（total number of nodes n=100）

由圖5～圖7 可對比分析得出：

1）每一輪均會重新組鏈，但有些節點因為能量耗盡而死亡時就不再參與到網絡成鏈中。

2）當前一輪的頭節點在當前輪不滿足能量因子要求時，會重新進行頭節點的選取，但是選取時仍然是選取距離基站較近的節點。

因此，可以從頭節點到基站的傳輸距離上達到降低傳輸能耗的目的。

3.3 PEGASIS-REDP 協議流程

PEGASIS-REDP 協議流程如下：

1）整個網絡進行分區，在每個區隨機部署等量的節點，并對節點進行初始能量賦值；

2）基站向全網廣播信息，網絡內的節點接收信息，計算并記錄自身與基站的距離；

3）統計每個區域內存活的節點和剩余能量；

4）將每個區內存活的節點成鏈，并記錄節點順序和節點之間的距離；

5）找出距離基站最近的節點并將其作為頭節點，判斷節點是否滿足能量閾值和剩余能量的條件，如果滿足條件則確定為當前輪的頭節點，如果不滿足則找到距離基站次近的節點作為頭節點；

6）開始進行數據傳輸，根據網絡傳輸模型進行數據傳輸和接收數據包時的能耗計算；

7）一輪完成，將每個區域內的節點剩余能量和存活的節點進行統計；

8）若網絡中節點未全部死亡，則返回第3 步，若網絡中所有的節點死亡則結束。

PEGASIS-REDP 協議流程如圖8 所示。

圖8 PEGASIS-REDP 協議流程Fig.8 Procedure of PEGASIS-REDP protocol

4 實驗結果與分析

本文在MATLAB 2018a 平臺上進行仿真實驗，由于PEGASIS 協議是在LEACH 基礎上的改進，且PEGASIS-REDP也融合了LEACH 協議中多簇頭的思想，因此本文對LEACH、PEGASIS、PEGASIS-NSH、PEGASIS-REDP 協議在網絡存活節點、節點的剩余能量以及網絡延遲方面進行分析和比較，網絡模型的參數設置見表1。

表1 網絡參數設置Table 1 Network parameter settings

4.1 網絡延遲對比

PEGASIS-REDP 協議采用了分區策略，分區后每個區域內節點數目相對于PEGASIS 協議網絡中節點數目大大減少，在不同區域內可以單獨完成信息采集，將結果單獨傳輸給基站。因此采用分區可以很好地解決網絡延遲問題。

由網絡參數模型可知，節點處理信息能力相同，設2 個鄰居節點之間進行數據接收、數據融合和數據發送所消耗的總時間為ti，則PEGASIS 協議一輪數據傳輸總耗時TP的表達式如式（7）所示：

PEGASIS-REDP 協議一輪數據傳輸總耗時TREDP表達式如式（8）所示：

其中：j表示劃分區域的數目。

假設每一個節點在傳遞數據包過程中節點在接收、融合和發送過程共需要1 ms。由圖9 可以看出，相比于PEGASIS 協議傳遞整個網絡的數據包的延遲時間，PEGASIS-REDP 協議將整個網絡的延遲時間減少了約300%。這是因為PEGASIS-REDP 協議采用的是將整個區域進行分區的策略，在數據傳輸的過程中，數據包可以在各個區內單獨進行信息傳遞并發送給基站，所以PEGASIS-REDP協議可以很好地改善整個網絡的延遲。在實現成本方面，雖然與經典的PEGASIS 協議相比，PEGASIS-REDP 協議多出3 個頭節點，但是網絡中普通節點會減少3 個，且PEGASISREDP協議中每一次區域內頭節點的選取均是選擇距離基站最近的節點，可以在傳輸數據包的同時將能量損耗達到最小。

圖9 網絡延時對比Fig.9 Comparison of network delay

4.2 網絡剩余能量對比

經典協議PEGASIS 在每一輪都會進行頭節點的更換，PEGASIS-REDP 協議相比于經典協議引入了距離因子dmin、最小能量閾值Emin和剩余能量因子Ei，只有在滿足更換條件時才進行頭節點的更換，不會頻繁更換頭節點，且只選擇距離基站最近的節點來傳輸信息，因此可以均衡網絡能耗。

不同協議的網絡剩余能量隨輪數變化情況如圖10 所示。從圖10 中可以看出PEGASIS-REDP協議的網絡剩余能量始終優于LEACH 協議、PEGASIS 協議和PEGASIS-NSH 協議。當網絡能耗為50%時，LEACH、PEGASIS 和PEGASIS-NSH 協議分別運行了281 輪、484輪和498 輪，而PEGASISREDP 協議運行了525 輪，相比于這3 種協議分別延遲了86.8%、8.5%和5.4%。當能量消耗為90%時，LEACH、PEGASIS和PEGASIS-NSH 協議分別運行了601 輪、926 輪和940 輪，PEGASIS-REDP 運行了988 輪，相比于其他3個協議分別延遲了64.4%、6.7%和5.1%。

圖10 不同協議的網絡剩余能量Fig.10 Network residual energy of different protocols

綜合以上可知，PEGASIS-REDP 協議在均衡網絡能量方面要優于LEACH、PEGASIS 和PEGASIS-NSH協議，這是因為PEGASIS-REDP 協議在選取頭節點的過程中，不會頻繁更換頭節點，且引入了最小能量閾值和剩余能量作為頭節點的更換條件，從而均衡了整個網絡的能耗。

4.3 存活節點對比

經過多次實驗并取平均值，4 種協議的網絡存活節點關系如圖11 和表2 所示。

圖11 不同協議的存活節點數隨輪數的變化Fig.11 Variation of the number of surviving nodes with the number of rounds of different protocols

表2 不同協議在相同死亡節點數時運行的輪數Table 2 Number of rounds of different protocols running at the same number of dead nodes

從圖11 可以看出，PEGASIS-REDP 協議在相同輪數下存活的節點數始終多于其他協議。對表2 進行數據分析得到：PEGASIS-REDP 協議在第10 個節點死亡時運行了864 輪，相比于LEACH 協議的350 輪、PEGASIS 協議的563輪和PEGASIS-NSH 協議 的585 輪分別延遲了147%、53.5% 和47.7%；PEGASIS-REDP 協議在20%節點死亡時的輪數為1 010 輪，相比于LEACH 協議的418 輪、PEGASIS 協議的735輪和PEGASIS-NSH 協議的751 輪，分別延遲了141.6%、37.4%和34.5%。由圖10 可以看出，當有50%節點死亡時整個網絡剩余的能量已經不足95%，因此本文以50%節點死亡時的輪數作為網絡的生存時間，此時PEGASIS-REDP 協議的網絡生命周期為1 115 輪，相比于LEACH 協議的602 輪、PEGASIS 協議的932輪和PEGASIS-NSH 協議的983 輪，分別延遲了85.2%、19.6%和13.4%。

綜上所述，PEGASIS-REDP 協議在延遲節點死亡的輪數和延長網絡存活時間上優于LEACH 協議、PEGASIS 協議和PEGASIS-NSH 協議。這是因為PEGASIS-REDP 協議采用分區策略，每次頭節點的選取總是選擇在節點能量滿足要求的前提下，并選擇距離基站最近的節點作為頭節點進行數據發送，很好地均衡了距離基站的距離和節點剩余的能量，因此可以有效延遲節點死亡的輪數，延長整個網絡的生存時間。

5 結束語

本文針對經典的PEGASIS 協議存在的問題提出PEGASIS-REDP 協議，通過對整個網絡進行分區，并選取多個頭節點的方法進行數據傳輸，在每個區域采用優先尋找距離基站最近的節點作為頭節點的策略。實驗結果表明，與LEACH、PEGASIS、PEGASIS-NSH 協議相比，PEGASIS-REDP 協議可以有效減少整個網絡的延遲，均衡整個網絡的能量消耗，延遲節點死亡的輪數及延長網絡的生存時間。雖然在成鏈階段依靠分區縮小網絡范圍縮短了差鏈形成的距離，但仍然可能出現差鏈的情況。下一步將設置距離閾值因子，利用貪心算法尋找下一個距離當前節點最近的節點，當此節點間的距離大于所設定的距離閾值時，則重新尋找鄰居節點，從而對成鏈過程中的差鏈進行優化。