WSN 目標跟蹤場景中基于能耗約束的傳感器選擇算法①

王會勤 付春玲 胡振濤 劉先省 金 勇

(*河南大學計算機與信息工程學院 開封475004)

(**河南大學物理與電子學院 開封475004)

(***黃淮學院 駐馬店463000)

0 引言

無線傳感器網(wǎng)絡(wireless sensor networks,WSN)是由大量微傳感器構成的自組織無線網(wǎng)絡系統(tǒng),具有傳感器節(jié)點小型化、成本低、容錯率高等優(yōu)點,已在車輛導航、災難恢復、航空和醫(yī)療保健等領域獲得廣泛應用[1-4]。目標跟蹤是無線傳感器網(wǎng)絡最重要的應用之一,由于傳感器節(jié)點傳感、通信和計算資源有限,采用合理的傳感器管理方法可在保證跟蹤精度的同時降低WSN 能耗[5-6]。

為了減少通訊傳輸?shù)哪芰肯?文獻[7,8]通過對傳感器接收到的數(shù)據(jù)進行壓縮量化,將條件后驗克拉美羅界(conditional posterior Cramér-Rao lower bounds,CPCRLB)作為節(jié)點選擇的優(yōu)化準則,激活最優(yōu)傳感器節(jié)點進行目標跟蹤任務。在監(jiān)測概率約束的節(jié)點觀測模型下,文獻[9]將工作的傳感器節(jié)點測量數(shù)據(jù)量化,提高目標觀測精度。但是由于對原始監(jiān)測數(shù)據(jù)進行了量化壓縮,目標軌跡估計沒有利用實際觀測信息,因此該方法難以直觀描述選擇傳感器的跟蹤性能。文獻[10]采用簇頭隨機選擇方法,構建動態(tài)分簇結構,并適時調(diào)整分簇策略,降低WSN 總能耗,但該方法難以保證WSN 能量均衡。文獻[11,12]以測量誤差協(xié)方差矩陣跡為目標函數(shù),將懲罰項描述為節(jié)點選擇矩陣列數(shù)與節(jié)點選擇次數(shù)的和,利用交替向量乘子法來解決此優(yōu)化問題,但運算復雜度較高。文獻[13,14]利用擴展卡爾曼濾波算法(extended Kalman filter,EKF)最小化估計誤差,該方法以測量誤差協(xié)方差矩陣的跡為目標函數(shù),以卡爾曼增益矩陣的列為懲罰稀疏項,通過構造等式約束和增廣拉格朗日函數(shù),利用交替向量乘子法求解,但該方法未考慮WSN 能量均衡且運算復雜度較高。

針對上述問題本文提出一種基于估計精度和能耗約束的WSN 目標跟蹤傳感器選擇算法,以估計協(xié)方差矩陣的跡和傳感器量測能耗函數(shù)之和為目標函數(shù),以傳感器量測能量閾值為約束條件,將卡爾曼濾波增益矩陣及傳感器量測能耗矩陣為待優(yōu)化變量,解決WSN 目標跟蹤過程中的傳感器選擇問題,平衡網(wǎng)絡的估計精度和能量消耗。

本文對使用符號的定義如下:大寫粗體字母如F表示矩陣,小寫粗體字母如x表示向量,‖·‖2表示向量的2 范數(shù),1 表示全1 向量或矩陣,[·]T、[·]-1分別表示矩陣或向量的轉(zhuǎn)置和矩陣的逆,tr(·)表示矩陣的跡,▽為一階導數(shù)算子運算,card(·)為集合勢。

1 問題描述

考慮圖1 場景模型,在大小為A×A的二維監(jiān)測區(qū)域內(nèi),隨機分布M個靜止傳感器節(jié)點,選擇部分傳感器節(jié)點在時間T內(nèi)對沿區(qū)域?qū)蔷€勻速直線運動的目標進行跟蹤,假設每個傳感器節(jié)點都能夠選擇開啟測量目標位置。

圖1 場景模型圖

在t=1,…,T時刻,目標狀態(tài)可由四維狀態(tài)向量xt=[x(t),y(t),vx(t),vy(t)]T表示,其中x(t)和y(t)分別表示t時刻目標在水平與垂直方向上的位置坐標,vx(t) 和vy(t) 分別表示t時刻目標在水平與垂直方向上的速度值。假設目標運動模型如下:

其中,F為運動狀態(tài)轉(zhuǎn)移矩陣,ωt為均值為零、協(xié)方差矩陣為Q的加性高斯噪聲,且

式中,Δt是測量時間間隔,τ為過程噪聲參數(shù)。

假設節(jié)點i的位置坐標為mi=[xi yi]T,有效監(jiān)測覆蓋面積為以節(jié)點位置為圓心、半徑為ri的圓形區(qū)域。當目標出現(xiàn)在節(jié)點的有效監(jiān)測覆蓋范圍內(nèi)時,就可以獲得目標與監(jiān)測節(jié)點的距離信息。假設目標在t時刻的位置坐標為Lt=[x(t),y(t)]T,則t時刻節(jié)點i和目標間的距離為

即當hi,t≤ri時,且傳感器節(jié)點i剩余能量高于剩余能量閾值Esur時,傳感器節(jié)點i作為候選節(jié)點,可選擇開啟進行目標測量。隨著目標運動,目標移動出傳感器節(jié)點感測范圍,hi,t ＞ri時,傳感器節(jié)點停止監(jiān)測目標任務,進入休眠模式。不失一般性,本文假設所有傳感器節(jié)點有效監(jiān)測覆蓋面積相等。

2 傳感器管理優(yōu)化算法

在傳感器網(wǎng)絡目標跟蹤系統(tǒng)中,合理高效的傳感器管理方法可在保證跟蹤精度的同時降低WSN能耗。而采用多跳方式,利用簇頭轉(zhuǎn)發(fā)數(shù)據(jù)能有效降低網(wǎng)絡內(nèi)節(jié)點能耗,起到延長網(wǎng)絡壽命的作用[15]。本文所提傳感器選擇流程如圖2 所示。

圖2 傳感器選擇流程框圖

2.1 簇頭選擇

為了提高目標的跟蹤精度及節(jié)省網(wǎng)絡能量消耗,本文采用動態(tài)選擇簇頭的方法。當目標開始進入監(jiān)測區(qū)域內(nèi)時,由于獲取的目標信息較少,跟蹤誤差較大,因此此時選擇簇頭節(jié)點時優(yōu)先考慮能耗因素,選擇距離目標最近的傳感器節(jié)點作為簇頭節(jié)點,進行工作節(jié)點的測量數(shù)據(jù)收集和融合,減少傳感器節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)能耗與簇頭收集數(shù)據(jù)能耗。然后工作傳感器節(jié)點利用EKF 濾波算法進行目標狀態(tài)估計,簇頭收集工作傳感器節(jié)點對目標的估計狀態(tài),并將狀態(tài)估計信息轉(zhuǎn)發(fā)給下一簇頭。隨著目標運動,當此簇頭節(jié)點移動出目標被監(jiān)測范圍時,選擇下一簇頭。定義預測簇頭能量函數(shù)公式如下:

其中,G(t) 為t時刻的候選工作節(jié)點集合。若傳感器節(jié)點j選為簇頭,則其余傳感器節(jié)點i(i=1,2,…)card(G(t)) -1 轉(zhuǎn)發(fā)數(shù)據(jù)到簇頭j的總能量為fCH(j),rij為傳感器節(jié)點i到傳感器節(jié)點j之間的距離,αc為已知路徑衰減因子,l2為轉(zhuǎn)發(fā)數(shù)據(jù)大小,er為接收1 位數(shù)據(jù)的能耗,ed為傳感器節(jié)點j決定的已知路徑能量特性。

因此為了節(jié)省網(wǎng)絡能耗,應選擇預測簇頭能量最少的傳感器節(jié)點作為簇頭節(jié)點,以使傳感器節(jié)點進行轉(zhuǎn)發(fā)數(shù)據(jù)、簇頭收集數(shù)據(jù)的能量最小,即選擇t時刻的簇頭節(jié)點為

2.2 節(jié)點選擇

假設傳感器節(jié)點在測量過程中受到擾動噪聲干擾,則t時刻的N個候選傳感器節(jié)點對目標的測量可表示為

其中ψt是測量噪聲,假設其為零均值的高斯噪聲,協(xié)方差矩陣R=σ21N×N。

由于本文觀測模型是非線性的,因此采用EKF進行目標狀態(tài)估計。在EKF 預測階段,計算狀態(tài)一步預測值:

求解一步預測狀態(tài)協(xié)方差陣:

更新階段,首先對非線性系統(tǒng)模型進行一階泰勒展開,Ht=是測量函數(shù)h(·)在時間t上關于預測狀態(tài)的聯(lián)合雅可比矩陣。

更新協(xié)方差矩陣:

計算濾波增益:

為了節(jié)省網(wǎng)絡能耗,應選擇較少的工作傳感器節(jié)點進行目標跟蹤,且為了得到較高的跟蹤精度,本文以后驗估計協(xié)方差矩陣Pt|t的跡tr(Pt|t) 最小為目標函數(shù),其中估計協(xié)方差矩陣Pt|t=(I-KtHt)Pt|t-1,以卡爾曼增益為優(yōu)化問題的解,目標函數(shù)為

式(10) 僅在選擇節(jié)點個數(shù)方面進行優(yōu)化以節(jié)省能耗,而選擇目標監(jiān)測過程中使用能量較少的節(jié)點可以更有效地節(jié)省網(wǎng)絡能量消耗。假設量測單位目標狀態(tài)變化量需要量測能量‖e‖2,e=(ex,ey,evx,evy)T,其中ex、ey和evx、evy分別表示位置和速度的量測能量分量,且ex=ey=2evx=2evy。約束傳感器節(jié)點i測量目標狀態(tài)變化所用的能量不高于傳感器節(jié)點用來量測目標的可用參考能量(E0)i,E0∈RN,超出參考能量的額外能量表示為Ei,Ei∈RN。因此將式(11)添加到式(10)的約束條件中:

其中,

是t時刻與t-1 時刻的目標估計狀態(tài)變化量,為t時刻目標狀態(tài)預測向量。顯然應該避免消耗傳感器節(jié)點的額外能量,因此有必要在式(10)的目標函數(shù)中添加與額外能量相關的懲罰項,于是優(yōu)化問題式(10)表示為如下形式。

懲罰函數(shù)q(·)=‖·‖2,λ為正則化參數(shù)。當選擇工作的傳感器節(jié)點產(chǎn)生額外能量E時,消耗的E越多,則對目標函數(shù)的懲罰越大,即目標函數(shù)值越大,表示此選擇的工作傳感器節(jié)點不是所求最優(yōu)選擇方案。相反,具有最少能量消耗的最少選擇傳感器節(jié)點個數(shù)的方案,其目標函數(shù)最小,可平衡精度和能量消耗。

由于式(13)中目標函數(shù)和約束條件都為凸形式,因此本文問題式(13)為標準凸問題,可以利用凸優(yōu)化工具包直接求解,其計算復雜度為O(N3)[16]。

3 仿真結果與分析

與仿真有關的場景和參數(shù)分別如圖1 和表1 所示。本文算法在位置均方根誤差(root mean square error,RMSE)和網(wǎng)絡累積消耗能量方面與文獻[4]、文獻[9]、文獻[14]中的算法進行了對比。簇頭和節(jié)點的能耗模型和參數(shù)均與文獻[17]一致。RMSE公式如下所示:

表1 仿真參數(shù)設定

其中Mc為蒙特卡羅仿真次數(shù)。

RMSE 隨時間變化對比圖如圖3 所示。從圖3可以看出,當開始利用傳感器節(jié)點進行監(jiān)測時,所有算法的誤差都較大,RMSE值較高,估計精度較差。隨著目標運動,采樣次數(shù)逐漸增加,所有算法的RMSE降低,估計精度增加。本文所提算法由于監(jiān)測范圍約束,選擇傳感器節(jié)點與其他算法相比距離目標顯然較近,量測誤差較小,在大多數(shù)監(jiān)測時間內(nèi)的RMSE值較其他算法低。

圖3 RMSE 對比

為了驗證所提算法節(jié)省能耗的有效性,本文在網(wǎng)絡累積消耗能量方面與其他算法進行對比,結果如圖4所示。

圖4 累積能量消耗對比

所有算法初始網(wǎng)絡總能量均為100 J。當運行時間相同時,本文所提算法的能量消耗低于其他3種算法,剩余能量高于其他算法。這是由于轉(zhuǎn)發(fā)數(shù)據(jù)能耗是無線傳感器網(wǎng)絡的主要能量消耗,且轉(zhuǎn)發(fā)能耗隨距離呈正相關關系,而所提算法轉(zhuǎn)發(fā)數(shù)據(jù)僅在監(jiān)測范圍內(nèi)進行。隨著運行時間增加,4 種算法的網(wǎng)絡能耗都逐漸增加,對應的累積能量消耗曲線都在不斷上升,剩余能量不斷減少。當運行時間結束時,所提算法與其他3 種算法相比能量消耗最少,剩余能量最多,相比其他算法,本文算法有效地節(jié)省了網(wǎng)絡能耗。

為了準確分析所提算法的傳感器節(jié)點能量使用情況,本文在傳感器節(jié)點剩余能量分布情況方面進行了分析。結果如圖5 和圖6 所示。

圖5 剩余能量分布

圖6 能量分布等高線

從圖5 可以看出,由于進行目標測量和數(shù)據(jù)轉(zhuǎn)發(fā),在目標運動軌跡附近的傳感器節(jié)點剩余能量比距目標軌跡較遠的傳感器節(jié)點少,使用能量多,其使用能量分布等高線如圖6 所示。由于監(jiān)測范圍約束,傳感器節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)時距離較短,因此整個網(wǎng)絡運行中轉(zhuǎn)發(fā)數(shù)據(jù)能量平均較小,實現(xiàn)了能量均衡。

4 結論

針對WSN 中利用傳感器節(jié)點進行目標跟蹤過程中的能量優(yōu)化問題,本文提出了一種基于能耗約束的傳感器選擇算法,以估計協(xié)方差矩陣的跡與傳感器量測能耗函數(shù)的和為目標函數(shù),以節(jié)點量測能量閾值為約束條件,將卡爾曼濾波增益矩陣和能耗矩陣作為問題的解,解決了WSN 目標跟蹤過程中的傳感器選擇問題。同以往的算法相比,本文所提算法能節(jié)省網(wǎng)絡能量,實現(xiàn)網(wǎng)絡能量均衡。未來的工作將致力于研究多個目標運動時傳感器節(jié)點選擇,以便提高無線傳感器網(wǎng)絡的節(jié)點利用率。