節點輪換的傳感器網絡生存期優化算法

李蘭英，蔣維成，周 玲，胡曉玲

(成都理工大學工程技術學院 電子信息與計算機工程系，四川 樂山 614000)

0 引 言

無線傳感器常部署在野外無人值守的環境[1,2]。由于監測過程的特殊性，無線傳感器常是一經部署就不再改變。受設備的限制，無線傳感器自身攜帶的能量有限，而數據采集和通信都需要能量，這樣能量就成為無線傳感器網絡中的珍貴資源。為了增加網絡中的能量資源，無線傳感器的數量和密度都要達到一定要求，以保持能量的冗余，更好發揮其功能，提高系統的可靠性，使監測順利進行下去，減少意外因素導致的失敗。有時單個無線傳感器的能量無法完成對目標監測的時長，需要眾多節點來實現對目標的分段監測，通過時間接力才能達到規定的時長。如區域中某密度下能量僅維持5天的監測網絡，無線傳感器的密度增加就可以增加監測的時間，在密度增加兩倍后，監測時間可能延長到10天，大大增加了對目標的監測時長，提高了性能。這對于環境險惡、部署難度大的無線傳感器網絡，可以減少部署次數，節約成本。但是隨著網絡中無線傳感器數量的增加，也增加了網絡管理的難度和復雜性，如何在復雜的監測環境中安排好監測節點之間的輪換，保證任務順利執行下去，使得對目標的監測達到規定的要求，并高效地利用能量，使得監測網絡的有效期得以延長。這對無線傳感器網絡來說具有重要意義。

1 相關研究

無線傳感器網絡中常采用分簇方式對網絡中的節點進行管理。文獻[3]依據距離匯聚節點的遠近以及節點數量進行網絡分層，根據分層網絡中簇頭節點的位置和節點的剩余能量選擇每個分層的中心節點，采用分層聚類與節點管理機制降低無線傳感器網絡的能耗。文獻[4]根據節點剩余能量和位置信息選擇簇頭，均衡能量消耗，延長網絡生存期。文獻[5]根據傳感器節點的剩余能量和位置信息等參數優化簇頭選取，簇頭與中繼節點之間利用單跳和多跳相結合的傳輸形式，減少節點間的通信開銷，延長網絡壽命。文獻[6]提出一種多跳無線傳感器網絡分簇算法，提高節點能量利用的效率，優化網絡數據傳輸。群智算法被用于無線傳感器網絡的路由優化中[7,8]，文獻[9]采用最優路徑度量公式改進信息更新策略，提出了一種改進蟻群算法的無線傳感器網絡路由方法，來均衡節點能耗，延長網絡的生命周期。文獻[10]采用均勻聚類成簇的方法，各簇進行壓縮的分布式數據收集，通過建立骨干樹將數據傳輸至Sink節點，降低網絡傳輸量，節約能耗。

這些算法針對無線傳感器網絡中能量的利用進行優化，使得能量的利用率提高了，但無法保證對目標的監測時間長度達到具體的要求，實現對目標的長時間監測。為此，本文提出了基于節點輪換的能量感知監測方法(energy-aware monitoring method，EAMM)，使得區域中擔任監測任務的無線傳感器節點能夠自動進行輪換，對目標進行分段監測，實現總監測時間的極大增加，根據過去一段時間的能量消耗來對即將的能量使用進行調整，合理地規劃無線傳感器的能量利用，使得對目標的監測時長達到要求，盡可能地延長網絡生存有效期，以求監測時長最大化。

2 網絡模型和問題描述

2.1 網絡模型

網絡中無線傳感器的個數為m，用集合N表示。假設這m個無線傳感器節點 (b1,b2…bm) 均勻地隨機部署在二維平面內，對于任一無線傳感器i∈N(i=b1,b2…bm)，部署后位置確定，可由GPS或北斗導航系統獲得其位置信息。若無線傳感器i的位置表示為 (xi,yi)，監測目標的位置為 (x0,y0)，無線傳感器網絡具有以下性質：

(1)網絡中無線傳感器節點分布模型為均勻分布；

(2)各節點是同構的，具有相同的功能和初始能量，初始能量均為e0；

(3)各節點能獨立工作，且都能完成相關的工作，并能根據需要實現不同狀態的轉換；

(4)任意節點的通信范圍覆蓋其所在的監測區域，并能與區域內的節點和相鄰區域中的節點進行通信，這樣監測數據可以一跳或多跳傳送到Sink節點，且相鄰節點間的通信范圍均在有效通信半徑之內，根據文獻[11,12]的能耗模型，通信能耗較小，可以節省能量；

(5)網絡內無線傳感器節點部署密度達到預定要求，并存在一定冗余，以滿足意外情況下目標監測能耗增多所需的要求。

2.2 問題描述

無線傳感器網絡根據監測質量的要求，在目標附近一定范圍內選取無線傳感器節點進行監測，受地理位置的影響，區域內的無線傳感器對目標的監測可能存在差異，但均符合質量要求。無線傳感器i所在的位置與監測質量(Q)之間存在一定的關系，用Qi=f(xi,yi) 表示。若用Tij表示無線傳感器i在第j輪中對目標監測的時間長度，網絡中無線傳感器對目標監測的總時長由各輪次的監測時間段組成，總共有u輪次。Ei表示無線傳感器i的剩余能量。設監測質量的最低要求為q0，對目標的監測時間要求達到規劃值t0。監測網可以描述如下

式(1)和式(2)分別滿足監測質量和時長的要求，式(3)中的tmax為理想化條件下能量所能維持的最長監測時間，追求對目標的監測時長最大化，使得監測時長盡可能趨近于tmax，網絡的效益就越高。

式(4)中Si表示無線傳感器i能否被選作監測節點，如果能選作監測節點，則Si=1，否則Si=0。要實現對目標監測的時間最長，區域中能夠擔任對目標監測的節點，它們的能量均消耗完，這樣能量均在網絡生存有效期內利用，能量的利用效率最高。

3 算法框架

3.1 算法設計

要對區域內的目標進行分段監測，使得滿足監測質量要求的節點之間進行輪換，本文根據無線傳感器的剩余能量(E)和監測質量(Q)，定義質能關系式如下

(6)

式中：β1和β2為比例系數，β1表示質能關系中監測質量所占的比例因子，β2表示質能關系中剩余能量所占的比例因子。質能關系式是選擇監測節點和進行輪換的重要關系式。在輪換過程中優先選擇質能關系中R值較大的節點進行監測。

從質能關系式可以得知，對于相同監測質量的兩無線傳感器i和j，存在Qi=Qj，而當剩余能量不同時，滿足Ei

而對于相同的剩余能量條件下的兩無線傳感器i和j，存在Ei=Ej，而當監測質量不同時，滿足Qi

由以上分析可得，根據目標所在的位置，對其周圍滿足監測條件的無線傳感器節點集，結合各節點的剩余能量狀況，自適應地進行選擇，使得對目標監測所需的能量分散在眾多的節點之間，通過這些無線傳感器節點對目標進行時間上的分段監測，通過時間接力實現對目標監測總時長的增加。如圖1所示，O點為目標所在位置，對于距離均為R1的A、B兩點，首先選擇能量較多的B進行監測，在B的能量消耗一定程度之后，再選擇A點，而A監測一定時間后，可以選擇半徑為R2的C點進行監測，這樣對目標的監測就可以由多個節點輪流執行，使得目標監測的能量消耗均衡化，監測時長也變成單個節點的多倍，監測時長得到大幅增加。

圖1 分段監測節點

文獻[13]指出無線傳感器在不同的工作狀態下，能耗是不相同的，無線傳感器的能耗跟工作狀態相關。無線傳感器處于某種工作狀態，就可以知道一段時間內的能量消耗。

定義1 歷史能耗速率是無線傳感器在某工作狀態下能耗速率，與無線傳感器的工作狀態相關，它是根據這一工作狀態下的長時間里能耗所得的結果，用H表示。

為了對能量的利用進行規劃，使得監測時長達到規定的要求，本文根據感知能耗速率來調整無線傳感器的能量使用。

定義2 感知能耗速率由無線傳感器的歷史能耗速率和實時變化速率兩部分組成，采用式(7)表示

Va=δ1·H+δ2·F

(7)

式中：F為實時變化速率，δ1和δ2為比例系數，δ1表示感知能耗速率中歷史能耗速率所占的比例因子，δ2表示感知能耗速率中實時變化速率所占的比例因子。

F=Vn-1-Vn-2

(8)

當Vn-1>Vn-2時，則(Tn-1,Tn)時段的能耗速率要比(Tn-2,Tn-1)時段的能耗速率要大，能量消耗是增加的趨勢，感知下一個時段(Tn,Tn+1)的能耗會增大。因而實時能耗速率進行調整，在歷史能耗速率的基礎上增加一定的量，使得感知能耗速率的值增大。此時，由式(8)可以得知，有Vn-1-Vn-2>0，因而式(7)是在能耗速率的基礎上增加一定量，是對能耗速率的加大。

當Vn-1=Vn-2時，則(Tn-1,Tn)時段的能耗速率與(Tn-2,Tn-1)時段的能耗速率是相同的，能耗消耗保持在一個穩定的水平狀態，感知在下一個時段(Tn,Tn+1)也將保持當前穩定的能耗狀態。此時，由式(8)可以得知，有Vn-1-Vn-2=0，因而式(7)是維持能耗速率的水平。

當Vn-1

通過以上分析，能耗速率在過去的時間里不論是增大、不變或減少，式(7)都能夠很好地表達在(Tn,Tn+1)時段的能耗狀態。

根據感知能耗速率的大小，對網絡中能量的使用進行調整，并做好監測的輪換安排，使得對目標的監測時長達到預定的要求。設網絡規劃時對目標的監測能耗速率用Vp表示。

當Va

定義一個變量為盈余時間Ts，用于記錄監測過程中的盈余時間，當有盈余能量時，把盈余時間進行累加。監控無線傳感器的能量消耗，當能量消耗ΔE時，立即進行輪換，并記錄這輪的延長時間t′s，并更新盈余時間Ts=Ts+t′s。

當Va>Vp時，感知能耗速率比規劃能耗速率要大，由于感知能耗速率Va的增大，由式(7)可以得知，在(Tn,Tn+1)時段消耗的能量將比規劃的能量要大，無線傳感器存在能量的欠缺，欠缺能量為Ed=(Va-Vp)·(tn+1-tn)，在這種情況下對目標的監測輪換將提前進行，避免能量的過度消耗，節點提前死亡。提前輪換時間為t′d=(Va-Vp)·(tn+1-tn)/Va。

定義一個變量為欠缺時間Td，用于記錄監測過程中的欠缺時間，當有欠缺能量時，把欠缺時間進行累加。監控無線傳感器的能量消耗，當能量消耗ΔE時，立即進行輪換，并記錄這輪的欠缺時間t′d，并更新欠缺時間Td=Td+t′d。

當Va=Vp時，感知能耗速率與規劃能耗速率相匹配，能量恰好被利用完。此時，不存在盈余時間，也沒有欠缺時間。

對網絡中的盈余時間和欠缺時間進行比較，當Ts≥Td時，盈余時間不小于欠缺時間，對目標的監測時間將大于或等于規劃時長，能夠完成預期目的，無線傳感器網絡能夠完成規劃要求。

當Ts

3.2 性能分析

本文的EAMM算法構建質能關系式，對目標進行輪換監測。本文對算法的性能進行了仿真實驗。在60×60 m2的區域中均勻隨機地投放50個無線傳感器，目標周圍一定范圍內的無線傳感器可以對目標進行有效的監測。目標所在位置為圖中“*”標記處，如圖2所示。

圖2 投放50個節點

在圖2所示的結果中共有4個節點對目標進行分段監測，在圖中使用方框標記出來，這些節點輪換執行監測任務，4個節點分段監測的時長將最大增加到單個節點監測時長的4倍。

圖3是同樣的區域中投放70個無線傳感器結果，區域中無線傳感器的密度增大，對目標進行有效監測的無線傳感器數量也將增加，在圖3中共有6個節點對目標進行分段監測，這樣就可能最大增加到單個節點時長6倍。表明EAMM算法使得監測時長極大地增加了，并且根據目標的位置選擇區域內的合適的節點進行監測，并能夠自適應地安排這些節點進行輪換，實現對目標的長時間監測。

圖3 投放70個節點

4 仿真結果

為了檢驗EAMM算法的性能，采用Matlab仿真軟件對Leach算法和本文的EAMM算法進行了比較實驗。為了模擬網絡環境的多樣性，測試不同環境下的網絡性能，做了不同參數的實驗。

(1)目標監測時長比較

相同的能量條件下，對目標的監測時間越長，算法的性能越高，能量的利用效率也就越有效。在100×100 m2的區域中分別投放100個、180個、240個無線傳感器，兩算法在這3種環境下的結果如圖4所示。圖中橫坐標表示的是區域中投放無線傳感器的數量?？v軸表示的是輪次，是網絡中對目標的監測時間長度。

圖4 監測時長

從圖4可以看出，EAMM算法在這3種情況下對目標的監測時長都要比Leach算法要長，并且在區域中無線傳感器密度增加時，EAMM算法的優勢更加明顯。這主要是因為Leach算法只是采取簡單的分簇機制對簇內節點進行管理，可能出現較多節點對目標的重復監測，浪費了能量，從而縮短對目標的監測時間，這在無線傳感器的密度增大時更加嚴重。而EAMM算法中對目標監測進行了有效管理，安排好了這些節點監測時段之間的輪換，并對能量的使用進行調整，使得監測時長得到增加，因而EAMM算法中對目標的監測時長優勢比較明顯。

(2)節點死亡數比較

無線傳感器在監測和通信的過程中不斷地消耗能量，隨著能量的減少，無線傳感器將因能量的耗盡而死亡。網絡中的無線傳感器死亡時間出現得越早，數量越多，越不利于對目標的監測和數據收集。兩算法的節點死亡數結果如圖5所示。

圖5 死亡數

從圖5可以看出EAMM算法節點出現死亡的時間比Leach算法要遲，并且在相同的時間里死亡的無線傳感器數量要少得多。EAMM算法根據質能關系式在監測節點之間進行輪換，把監測的能量分散在眾多的節點之間，有利于能量的均衡化，避免節點能耗過多，提前死亡，因而EAMM算法節點死亡的出現時間要遲，死亡數量也要少。

(3)網絡生存期比較

無線傳感器節點的存活數量越多，時間越長，網絡生存期也就越長，能夠采集數據并傳送到基站的時間也就越長。兩算法中無線傳感器節點存活數如圖6所示。

圖6 存活數

從圖6可以看出，在相同的時間里，EAMM算法中無線傳感器節點存活數量均比Leach算法要多，因而EAMM算法的網絡生存期比Leach算法要長。這主要是EAMM算法中存在對能量消耗的規劃利用，當對目標的監測能耗速率過快時，啟用冗余節點的能量幫助完成監測，從而避免了節點的能耗過大，節點可以存活的時間就更長。因此，EAMM算法中節點的存活數要多，網絡生存期也就越長。

5 結束語

能量是無線傳感器網絡中的珍貴資源，特別是那些能夠對目標進行有效監測的節點能量。為了實現對目標監測時長的最大化，根據無線傳感器工作狀態下的能量消耗的歷史水平狀況和實時能耗，構建監測過程能量感知的消耗模式，對網絡中的能量進行調整。構建任務監測過程進行節點輪換的質能關系式，對目標的監測自適應地進行輪換，通過多節點的時間接力來完成對目標的長時間監測，使得監測時長盡可能地延長。仿真結果表明，本文構建的監測過程能耗感知的模型，無線傳感器在監測過程中能夠對能量的使用進行調整和節點之間的輪換，達到或超過規劃的時長。