基于能量有效的水下分布式粒子濾波跟蹤算法

毛玉明

摘 要： 為降低水下無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法能耗并提高定位精度，提出基于能量有效的分布式粒子濾波跟蹤算法（EEPF算法）。EEPF算法通過能量有效的最優(yōu)分布式動態(tài)成簇機制和啟發(fā)式能量有效的調(diào)度算法來平衡水下節(jié)點間的能耗，延長網(wǎng)絡(luò)生存期，并在預(yù)測、濾波、重采樣階段對粒子濾波算法進行改進，在保障期望目標(biāo)跟蹤精度的同時降低了運算能耗。仿真結(jié)果表明，EEPF算法是一種輕量級的能量有效的目標(biāo)跟蹤算法，該算法能耗低，網(wǎng)絡(luò)存活時間長，且跟蹤精度較傳統(tǒng)粒子濾波算法有了較大提高。

關(guān)鍵詞： 能量有效； 粒子濾波； 跟蹤算法； 目標(biāo)跟蹤

中圖分類號： TN929.5?34； TP212.9 文獻標(biāo)識碼： A 文章編號： 1004?373X（2017）23?0023?04

Abstract： In order to reduce the energy consumption and improve the tracking accuracy of the target tracing algorithm for underwater WSN， an energy?efficient distributed particle filtering tracing algorithm for three?dimensional wireless sensor networks is proposed. The algorithm is used to balance the energy consumption among the underwater sensor nodes and prolong the network lifespan by means of the energy?efficient optimal distributed dynamic clustering mechanism and heuristic energy?efficient scheduling algorithm. The particle filtering algorithm is improved in the stages of forecasting， filtering and resampling， which can reduce the energy consumption in operation while maintaining the expected target tracking precision. The simulation results show that the algorithm is a lightweight energy?efficient target tracing algorithm， has low energy consumption， long network lifespan， and higher tracking accuracy than the traditional particle filtering algorithm.

Keywords： efficient energy； particle filtering； tracing algorithm； target tracing

0 引 言

隨著無線傳感器網(wǎng)絡(luò)的大規(guī)模應(yīng)用，對移動目標(biāo)進行定位和跟蹤成為研究的熱點之一。我國海岸線較長，海防線安全至關(guān)重要，新型水下無人武器裝備由于其體積小、重量輕、運動噪聲低等特點，很容易突破常規(guī)、落后的水下防線而侵入到我國近岸區(qū)，實施偵察乃至攻擊行動。水下無線傳感器網(wǎng)絡(luò)以其隱蔽性好，靈敏度高，分布式部署和可覆蓋面積大等特點，很容易捕捉到進入其監(jiān)測區(qū)的小型機動目標(biāo)，利用水下無線傳感器網(wǎng)絡(luò)對整個海岸線進行監(jiān)控，及時跟蹤、定位敵方武器裝備至關(guān)重要。

水下無線傳感器網(wǎng)絡(luò)屬于典型的三維網(wǎng)絡(luò)，且水下節(jié)點使用電池供電，更換電池極為困難，因此能量有效性是設(shè)計的重點[1]。目前無線傳感器網(wǎng)絡(luò)跟蹤算法主要有基于位置預(yù)測的目標(biāo)跟蹤算法、基于傳送樹的目標(biāo)跟蹤算法、基于卡爾曼濾波的目標(biāo)跟蹤算法和基于粒子濾波的目標(biāo)跟蹤算法[2]。

雖然現(xiàn)有算法基本滿足了目標(biāo)跟蹤的需求，但是始終無法解決跟蹤精度與網(wǎng)絡(luò)能耗相矛盾的問題，因此在保障期望目標(biāo)跟蹤精度的同時，如何降低網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生存期是研究的重點。

本文針對水下無線傳感器網(wǎng)絡(luò)，提出一種基于能量有效的分布式粒子濾波跟蹤算法（Energy?efficient Tracing Algorithm Based on Particle Filter for Three?dimensional Wireless Sensor Networks，EEPF）。EEPF算法引入節(jié)點的可信度并采用動態(tài)分簇策略，設(shè)計合理的數(shù)據(jù)傳輸方式，平衡網(wǎng)絡(luò)中各節(jié)點的能耗，并在預(yù)測、濾波、重采樣階段對粒子濾波進行改進，最后通過仿真驗證其有效性。

1 粒子濾波算法

粒子濾波算法是一種通過蒙特卡洛的模擬實現(xiàn)遞歸貝葉斯濾波的方法，粒子濾波算法通過尋找在空間傳播的隨機粒子并對概率密度函數(shù)進行近似，以隨機粒子的均值代替積分運算，從而獲得狀態(tài)最小方差分布，粒子濾波算法具有不受線性化誤差和高斯噪聲假定限制的特點，是解決非線性和非高斯問題的一種重要的方法，無線傳感器網(wǎng)絡(luò)中的運動目標(biāo)大部分具有非線性、非高斯的特點，因此粒子濾波算法在目標(biāo)跟蹤領(lǐng)域有著廣泛的應(yīng)用[3?4]。

基本粒子濾波算法包括預(yù)測、更新、權(quán)值計算和重采樣四個階段，下面對基本粒子濾波算法進行說明，在己知初始分布和似然函數(shù)的情況下，基本粒子濾波算法過程如下[5?8]：

（1） 初始化：[k=0]時刻，從先驗分布[P（x0）]中抽取[N]個粒子產(chǎn)生樣本粒子集[x（i）0i=1，2，…，N]。endprint

（2） 序貫重要采樣：首先從重要性函數(shù)中采集[N]個粒子得到粒子集[x（i）ki=1，2，…，N，]計算出每個粒子的權(quán)值[ω（i）k=ω（i）k-1Pzkx（i）kPx（i）kx（i）k-1qx（i）kx（i）k-1，zk，]然后計算每個粒子的歸一化權(quán)值參數(shù)[ω（i）k=ω（i）kj=1Nω（j）k]。

（3） 重采樣：計算有效采樣尺度信息[Neff=N1+Varω（i）k，]當(dāng)[Neff]小于設(shè)定閾值時，進行重采樣得到新粒子集，若不需要則進入下一步。

（4） 輸出：輸出一組粒子[x（i）t，ω（i）ti=1，2，…，N，]得到當(dāng)前時間后驗均值估計[xk=1Nk=1kx（i）kω（i）k]。

在基本粒子濾波算法中，重采樣減弱了退化效應(yīng)，但退化現(xiàn)象仍存在，限制了算法并行運算的能力，并且因為重要權(quán)重值被復(fù)制多次，會導(dǎo)致粒子多樣性的損失，另外，靠增加粒子數(shù)目來減小退化現(xiàn)象會影響計算的實時性。因此，為了減少樣本貧乏現(xiàn)象減少權(quán)值方差，使預(yù)估結(jié)果更好地逼近后驗概率密度分布，需要進一步改進基本粒子濾波算法。

2 基于能量有效的分布式粒子濾波跟蹤算法

2.1 最優(yōu)分布式動態(tài)成簇機制

EEPF算法采用動態(tài)成簇機制，利用節(jié)點可信度來選擇簇頭節(jié)點，并使剩余能量較低的節(jié)點轉(zhuǎn)入休眠，有效平衡各節(jié)點能耗，具體過程如下：

（1） 節(jié)點感知到監(jiān)測目標(biāo)進入相應(yīng)的感知區(qū)域時，向周圍區(qū)域廣播“成簇”信息，激活能感知到監(jiān)測目標(biāo)的節(jié)點，并各自計算節(jié)點可信度。

（2） 設(shè)[di]為節(jié)點[i]到跟蹤目標(biāo)的距離，當(dāng)節(jié)點與跟蹤目標(biāo)之間的距離超過一跳范圍時，將[di]置為1，即目標(biāo)節(jié)點未在該節(jié)點監(jiān)測范圍內(nèi)；[ki]為節(jié)點[i]與目標(biāo)之間的跳數(shù)；[Ei]為節(jié)點[i]的剩余能量，節(jié)點[i]的可信度[Bi]的計算公式如下：

選擇可信度[Bi]最大的節(jié)點作為目標(biāo)所在區(qū)域的簇頭節(jié)點，保證簇頭節(jié)點盡量靠近跟蹤目標(biāo)及自身的能量充足，有效避免距離目標(biāo)過遠且能量充足的節(jié)點作為簇頭節(jié)點，此類節(jié)點在跟蹤過程中，信號傳遞能耗過大且易受噪聲干擾。

（3） 在目標(biāo)移動過程中，根據(jù)目標(biāo)的運動狀態(tài)，設(shè)定計時器[t，]當(dāng)時間到達時，對目標(biāo)節(jié)點附近的錨節(jié)點重新計算可信度[Bi，]重新選舉簇頭，并將可信度[Bi]小于設(shè)定閾值[TB]的錨節(jié)點轉(zhuǎn)入休眠狀態(tài)。這樣保證簇頭是與跟蹤目標(biāo)最近的能量充足節(jié)點，防止跟蹤目標(biāo)因做急速的轉(zhuǎn)彎或感知節(jié)點沒電而丟失跟蹤目標(biāo)的現(xiàn)象。

（4） 進入下一個跟蹤周期時，當(dāng)前簇頭節(jié)點將移動節(jié)點的狀態(tài)估計信息轉(zhuǎn)發(fā)給下一個簇頭節(jié)點，無需所有的節(jié)點都參與此過程，減少數(shù)據(jù)處理量，降低網(wǎng)絡(luò)能耗。

2.2 EEPF算法

在粒子濾波基本算法中，首先需要預(yù)估起始點位置。如果缺少目標(biāo)先驗信息，將會在整個監(jiān)控區(qū)域內(nèi)隨機抽取粒子，產(chǎn)生[N]個粒子生成樣本粒子集，每個粒子的權(quán)值都設(shè)為[1N，]這種方式使用了更多的粒子參與定位，增加了計算成本。EEPF算法采用節(jié)點可信度得到預(yù)估起始點，增強粒子濾波先驗粒子抽取的先驗準(zhǔn)確性，更加接近真實的初始目標(biāo)分布。

節(jié)點密度對序貫重要采樣中的重要性函數(shù)選擇形式有較大影響。對于節(jié)點密度過小的情況，可以通過重采樣獲得足夠數(shù)量的樣本，因為EEPF算法選取的節(jié)點狀態(tài)較好，只需較少的樣本數(shù)就可以達到一定精度，因此，EEPF算法采用自適應(yīng)采樣數(shù)NA，自適應(yīng)采樣數(shù)NA跟分簇覆蓋面積、簇區(qū)內(nèi)的節(jié)點數(shù)、錨節(jié)點密度有很大關(guān)系，其定義公式為：

EEPF算法的實現(xiàn)過程如下：

Step1：探測節(jié)點探測目標(biāo)出現(xiàn)在監(jiān)測區(qū)域。

Step2：按照節(jié)點可信度選擇簇頭節(jié)點并計算自適應(yīng)的采樣數(shù)NA。

Step3：算法初始化：選取[N]個可信度最大的節(jié)點組成初始粒子集[x（i）0i=1，2，…，N，]初始權(quán)重為[1N。]

Step4：重要性采樣：首先刷新節(jié)點的可信度[Bi，]選取簇頭；然后根據(jù)節(jié)點可信度信息進行重要性采樣，選擇可信度大的節(jié)點對樣本進行補充，按照節(jié)點可信度采集[N]個粒子得到粒子集[x（i）ki=1，2，…，N，]將先驗分布作為提議分布計算出每個粒子的權(quán)值[ω（i）k，]然后計算每個粒子的歸一化權(quán)值參數(shù)[ω（i）k]。

Step5：重采樣：計算有效采樣尺度信息[Neff—，]當(dāng)[Neff—]超過設(shè)定閾值或者達到NA時，進入下一步，否則進行重采樣得到新粒子集。

Step6：狀態(tài)預(yù)估與結(jié)果輸出：輸出一組粒子[x（i）t，ω（i）ti=1，2，…，N，]得到當(dāng)前時間后驗均值估計[Xk—，]當(dāng)前簇頭節(jié)點轉(zhuǎn)發(fā)跟蹤目標(biāo)狀態(tài)信息給下一時刻動態(tài)區(qū)域的簇頭節(jié)點。

3 仿真分析

應(yīng)用Matlab平臺對EEPF算法和PF算法進行仿真分析比較，移動目標(biāo)符合隨機移動模型，節(jié)點能耗主要包括自身能耗、通信能耗和計算能耗，通信能耗包括功率放大器能耗和電路能耗，節(jié)點能耗絕大部分消耗在通信模塊上，通常1 b的信息傳輸100 m距離所需的能量，大約相當(dāng)于執(zhí)行3 000條計算指令所消耗的能量，仿真實驗主要考慮通信能耗和計算能耗，將節(jié)點自身消耗能耗忽略不計，當(dāng)節(jié)點能量小于0.2 J時，節(jié)點不能正常工作，宣布死亡，仿真參數(shù)如表1所示。

3.1 定位誤差

將EEPF算法與PF算法在相同的仿真參數(shù)設(shè)置下，對同一目標(biāo)進行追蹤仿真，運行60個時間段后，定位誤差如圖1所示。從圖1中可以看出EEPF算法和PF算法在運行的開始階段誤差都較大，EEPF算法經(jīng)過7 s的運行后，誤差迅速下降，最終趨于穩(wěn)定，在9 m左右波動；而PF算法剛開始運行時，其定位誤差就遠高于EEPF算法，經(jīng)過12 s的運行，算法的定位誤差才趨于穩(wěn)定，在13 m左右波動。產(chǎn)生上述現(xiàn)象的原因是：EEPF算法在重要性采樣時根據(jù)不斷更新的節(jié)點可信度生成采樣樣本，而PF算法是在整個空間內(nèi)隨機進行采樣，因此，EEPF算法生成的采樣樣本更接近跟蹤目標(biāo)，另外，因自適應(yīng)采樣數(shù)的應(yīng)用使EEPF算法能更迅速地降低算法的誤差。endprint

3.2 節(jié)點密度

在不同節(jié)點密度下，分別對EEPF算法和PF算法進行仿真，仿真結(jié)果如圖2，圖3所示。

從圖2中可以看出，當(dāng)節(jié)點密度[Sd]從1變化到3時，對于EEPF算法來說誤差曲線變化趨勢大致相同，都是在7 s后算法誤差趨于穩(wěn)定，三種節(jié)點密度下的均方根誤差相差在5 m左右，證明節(jié)點密度增加或減少對EEPF算法影響較小，分析具體原因為算法在初始階段和重要性采樣階段使用了與監(jiān)測目標(biāo)關(guān)聯(lián)緊密的高可信度粒子，因此EEPF算法在低節(jié)點密度下也能取得較好的定位精度。從圖3中可以看出，PF定位誤差在節(jié)點密度為1時，誤差比較大，也反映了應(yīng)用先驗分布作為提議分布的缺點，采樣的精度較低。

3.3 采樣數(shù)

粒子濾波算法的定位精度與算法設(shè)定的采樣數(shù)有著極大的關(guān)系，仿真方案為了驗證在不同采樣數(shù)下兩種算法的平均定位誤差，將采樣數(shù)從500逐步增加至2 000，間隔為100，經(jīng)過100次獨立仿真后定位誤差求得平均值，仿真結(jié)果如圖4所示。

仿真結(jié)果表明，PF算法和EEPF算法隨著采樣數(shù)的增加定位誤差逐步降低，當(dāng)采樣數(shù)從500升高到1 000次時，定位誤差下降最快；超過1 000次的采樣頻率后，定位誤差減小趨勢變緩，整體來看，采樣數(shù)對EEPF算法的定位誤差影響較小，這與EEPF算法的采樣數(shù)采用自適應(yīng)參數(shù)NA和概率密度函數(shù)選用節(jié)點可信度參數(shù)有關(guān)；而采樣次數(shù)對PF算法影響較大，雖然增加采樣次數(shù)可以提高跟蹤的精度，但是也增加了節(jié)點能耗，因此，對兩種定位算法的能耗做了仿真，具體如圖5所示。

從圖5中可知，當(dāng)網(wǎng)絡(luò)消耗總能量為1 700 J時，PF算法中的節(jié)點全部死亡，而EEPF網(wǎng)絡(luò)中還有約5.6%的節(jié)點能正常工作，從曲線可分析出EEPF算法消耗的總能量遠小于PF算法，EEPF算法延長了整個網(wǎng)絡(luò)的生存周期。

4 結(jié) 論

EEPF算法從定位性能與節(jié)點能耗平衡出發(fā)，采用最優(yōu)動態(tài)分簇策略，將節(jié)點的位置、信號強度與能量引入節(jié)點的可信度，并動態(tài)生成簇，在重要采樣環(huán)節(jié)使用自適應(yīng)的采樣數(shù)，并將節(jié)點可信度作為提議分布，減少了運算量，提高了定位跟蹤算法的魯棒性和網(wǎng)絡(luò)的能量利用率，是一種輕量級的水下定位跟蹤算法。仿真實驗表明，EEPF算法在定位跟蹤精度上相對于PF算法有較大提高，且該算法網(wǎng)絡(luò)整體能耗較低，延長了網(wǎng)絡(luò)的生存周期，有效提高了對目標(biāo)的跟蹤效果。

參考文獻

[1] 周帆，江維，李樹全，等.基于粒子濾波的移動物體定位和追蹤算法[J].軟件學(xué)報，2013，24（9）：2196?2213.

[2] 陳菲琪，吳曉丹.基于粒子濾波的多目標(biāo)跟蹤研究[J].計算機仿真，2010，27（6）：147?150.

[3] 彭遠芳，黃曉峰.無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法研究[J].計算機仿真，2012，29（5）：122?125.

[4] 何常勝，夏曉峰.基于分布式模糊邏輯推理的WSN分簇算法[J].現(xiàn)代電子技術(shù)，2016，39（5）：67?72.

[5] QIU Yinghui， LIU Chao. Modelling and stimulation of target tracking and localization in wireless sensor network [J]. Tehnicki vjesnik， 2014， 21（2）： 233?238.

[6] 周紅波，邢昌風(fēng)，耿伯英，等.基于粒子濾波的二元無線傳感器網(wǎng)絡(luò)分布式目標(biāo)跟蹤研究[J].傳感技術(shù)學(xué)報，2010（2）：274?278.

[7] 王嘉，付敬奇.基于APIT和粒子濾波的無線移動節(jié)點定位算法研究[J].傳感器與微系統(tǒng)，2011，30（9）：72?75.

[8] DING Hui. Application of wireless sensor network in target detection and localization [J]. Telkomnika， 2013， 11（10）： 5734?5740.endprint