節(jié)點輪換的傳感器網(wǎng)絡(luò)生存期優(yōu)化算法

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

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

0 引 言

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

1 相關(guān)研究

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

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

2 網(wǎng)絡(luò)模型和問題描述

2.1 網(wǎng)絡(luò)模型

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

(1)網(wǎng)絡(luò)中無線傳感器節(jié)點分布模型為均勻分布；

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

(3)各節(jié)點能獨立工作，且都能完成相關(guān)的工作，并能根據(jù)需要實現(xiàn)不同狀態(tài)的轉(zhuǎn)換；

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

(5)網(wǎng)絡(luò)內(nèi)無線傳感器節(jié)點部署密度達(dá)到預(yù)定要求，并存在一定冗余，以滿足意外情況下目標(biāo)監(jiān)測能耗增多所需的要求。

2.2 問題描述

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

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

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

3 算法框架

3.1 算法設(shè)計

要對區(qū)域內(nèi)的目標(biāo)進(jìn)行分段監(jiān)測，使得滿足監(jiān)測質(zhì)量要求的節(jié)點之間進(jìn)行輪換，本文根據(jù)無線傳感器的剩余能量(E)和監(jiān)測質(zhì)量(Q)，定義質(zhì)能關(guān)系式如下

(6)

式中：β1和β2為比例系數(shù)，β1表示質(zhì)能關(guān)系中監(jiān)測質(zhì)量所占的比例因子，β2表示質(zhì)能關(guān)系中剩余能量所占的比例因子。質(zhì)能關(guān)系式是選擇監(jiān)測節(jié)點和進(jìn)行輪換的重要關(guān)系式。在輪換過程中優(yōu)先選擇質(zhì)能關(guān)系中R值較大的節(jié)點進(jìn)行監(jiān)測。

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

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

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

圖1 分段監(jiān)測節(jié)點

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

定義1 歷史能耗速率是無線傳感器在某工作狀態(tài)下能耗速率，與無線傳感器的工作狀態(tài)相關(guān)，它是根據(jù)這一工作狀態(tài)下的長時間里能耗所得的結(jié)果，用H表示。

為了對能量的利用進(jìn)行規(guī)劃，使得監(jiān)測時長達(dá)到規(guī)定的要求，本文根據(jù)感知能耗速率來調(diào)整無線傳感器的能量使用。

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

Va=δ1·H+δ2·F

(7)

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

F=Vn-1-Vn-2

(8)

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

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

當(dāng)Vn-1

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

根據(jù)感知能耗速率的大小，對網(wǎng)絡(luò)中能量的使用進(jìn)行調(diào)整，并做好監(jiān)測的輪換安排，使得對目標(biāo)的監(jiān)測時長達(dá)到預(yù)定的要求。設(shè)網(wǎng)絡(luò)規(guī)劃時對目標(biāo)的監(jiān)測能耗速率用Vp表示。

當(dāng)Va

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

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

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

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

對網(wǎng)絡(luò)中的盈余時間和欠缺時間進(jìn)行比較，當(dāng)Ts≥Td時，盈余時間不小于欠缺時間，對目標(biāo)的監(jiān)測時間將大于或等于規(guī)劃時長，能夠完成預(yù)期目的，無線傳感器網(wǎng)絡(luò)能夠完成規(guī)劃要求。

當(dāng)Ts

3.2 性能分析

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

圖2 投放50個節(jié)點

在圖2所示的結(jié)果中共有4個節(jié)點對目標(biāo)進(jìn)行分段監(jiān)測，在圖中使用方框標(biāo)記出來，這些節(jié)點輪換執(zhí)行監(jiān)測任務(wù)，4個節(jié)點分段監(jiān)測的時長將最大增加到單個節(jié)點監(jiān)測時長的4倍。

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

圖3 投放70個節(jié)點

4 仿真結(jié)果

為了檢驗EAMM算法的性能，采用Matlab仿真軟件對Leach算法和本文的EAMM算法進(jìn)行了比較實驗。為了模擬網(wǎng)絡(luò)環(huán)境的多樣性，測試不同環(huán)境下的網(wǎng)絡(luò)性能，做了不同參數(shù)的實驗。

(1)目標(biāo)監(jiān)測時長比較

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

圖4 監(jiān)測時長

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

(2)節(jié)點死亡數(shù)比較

無線傳感器在監(jiān)測和通信的過程中不斷地消耗能量，隨著能量的減少，無線傳感器將因能量的耗盡而死亡。網(wǎng)絡(luò)中的無線傳感器死亡時間出現(xiàn)得越早，數(shù)量越多，越不利于對目標(biāo)的監(jiān)測和數(shù)據(jù)收集。兩算法的節(jié)點死亡數(shù)結(jié)果如圖5所示。

圖5 死亡數(shù)

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

(3)網(wǎng)絡(luò)生存期比較

無線傳感器節(jié)點的存活數(shù)量越多，時間越長，網(wǎng)絡(luò)生存期也就越長，能夠采集數(shù)據(jù)并傳送到基站的時間也就越長。兩算法中無線傳感器節(jié)點存活數(shù)如圖6所示。

圖6 存活數(shù)

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

5 結(jié)束語

能量是無線傳感器網(wǎng)絡(luò)中的珍貴資源，特別是那些能夠?qū)δ繕?biāo)進(jìn)行有效監(jiān)測的節(jié)點能量。為了實現(xiàn)對目標(biāo)監(jiān)測時長的最大化，根據(jù)無線傳感器工作狀態(tài)下的能量消耗的歷史水平狀況和實時能耗，構(gòu)建監(jiān)測過程能量感知的消耗模式，對網(wǎng)絡(luò)中的能量進(jìn)行調(diào)整。構(gòu)建任務(wù)監(jiān)測過程進(jìn)行節(jié)點輪換的質(zhì)能關(guān)系式，對目標(biāo)的監(jiān)測自適應(yīng)地進(jìn)行輪換，通過多節(jié)點的時間接力來完成對目標(biāo)的長時間監(jiān)測，使得監(jiān)測時長盡可能地延長。仿真結(jié)果表明，本文構(gòu)建的監(jiān)測過程能耗感知的模型，無線傳感器在監(jiān)測過程中能夠?qū)δ芰康氖褂眠M(jìn)行調(diào)整和節(jié)點之間的輪換，達(dá)到或超過規(guī)劃的時長。