王會(huì)勤 付春玲 胡振濤 劉先省 金 勇

(*河南大學(xué)計(jì)算機(jī)與信息工程學(xué)院 開(kāi)封475004)

(**河南大學(xué)物理與電子學(xué)院 開(kāi)封475004)

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

0 引言

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

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

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

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

1 問(wèn)題描述

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

圖1 場(chǎng)景模型圖

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

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

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

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

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

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

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

圖2 傳感器選擇流程框圖

2.1 簇頭選擇

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

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

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

2.2 節(jié)點(diǎn)選擇

假設(shè)傳感器節(jié)點(diǎn)在測(cè)量過(guò)程中受到擾動(dòng)噪聲干擾,則t時(shí)刻的N個(gè)候選傳感器節(jié)點(diǎn)對(duì)目標(biāo)的測(cè)量可表示為

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

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

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

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

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

計(jì)算濾波增益:

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

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

其中,

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

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

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

3 仿真結(jié)果與分析

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

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

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

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

圖3 RMSE 對(duì)比

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

圖4 累積能量消耗對(duì)比

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

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

圖5 剩余能量分布

圖6 能量分布等高線

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

4 結(jié)論

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