基于快速M(fèi)H變異的遺傳粒子濾波的WSN目標(biāo)跟蹤

魏 穎，郭 魯

(沈陽(yáng)工學(xué)院 信息與控制學(xué)院，遼寧 撫順 113122)

0 引言

無(wú)線傳感器網(wǎng)(WSN, wireless sensor network)是21世紀(jì)最重要的前沿技術(shù)之一，它的網(wǎng)絡(luò)連接是通過(guò)無(wú)線通信實(shí)現(xiàn)的，通過(guò)本身的一些傳感裝置檢測(cè)并感知相應(yīng)的環(huán)境數(shù)據(jù)，實(shí)現(xiàn)信息的相互融合。目標(biāo)跟蹤是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)主要研究領(lǐng)域，如交通監(jiān)測(cè)，捕捉戰(zhàn)爭(zhēng)狀態(tài)等。例如，將一個(gè)測(cè)試目標(biāo)放置在布置傳感器的地點(diǎn)內(nèi)，它運(yùn)動(dòng)時(shí)，通過(guò)傳感器測(cè)量，然后反饋到跟蹤系統(tǒng)，以此接近預(yù)估目標(biāo)的位置[1]。粒子濾波(PF,particle filter) 是一種蒙特卡羅算法，它是基于遞推計(jì)算的序列算法，基本思想是在當(dāng)前系統(tǒng)狀態(tài)分布中隨機(jī)抽取一些加權(quán)的粒子，通過(guò)計(jì)算對(duì)系統(tǒng)的下一個(gè)狀態(tài)進(jìn)行更新和估計(jì)，適用于所有的測(cè)量模型以及狀態(tài)轉(zhuǎn)換模型，所以在無(wú)線傳感器的目標(biāo)跟蹤中，上述方法比較適合[2]。粒子濾波算法在多次迭代后會(huì)退化，即只有少數(shù)粒子具有較大的權(quán)重，而大多數(shù)粒子的權(quán)重很小，幾乎為零，這會(huì)消耗大量的時(shí)間。這類(lèi)問(wèn)題通常下列的方法解決：首先是改善意義重大函數(shù)，其次是對(duì)粒子重新采樣。以上的方法主要改善粒子退化效率來(lái)解決粒子降解的問(wèn)題。在新的取樣之后，多次選擇重要性高的粒子，因此，粒子的多樣性已經(jīng)失去了一些，即所謂的粒子缺失。那么在跟蹤目標(biāo)時(shí)，一旦監(jiān)測(cè)的準(zhǔn)確性不高或目標(biāo)丟失，系統(tǒng)很可能不能自動(dòng)會(huì)聚。本文通過(guò)利用進(jìn)化機(jī)制保證粒子群優(yōu)化過(guò)程中局部的多樣性，并且處理粒子算法中粒子退化的缺陷。本文對(duì)于粒子濾波跟蹤算法的粒子衰退問(wèn)題給出了一種快速M(fèi)H變異遺傳的粒子濾波跟蹤算法[3]?？焖費(fèi)H變異遺傳算法是在遺傳粒子濾波算法上，加入遺傳進(jìn)化思想，利用快速移動(dòng)粒子交叉次數(shù)和變異算子，同時(shí)與賭輪選擇一起產(chǎn)生了一種新的遺傳算法,更快地提取到反映目標(biāo)概率特征的典型粒子。結(jié)果顯示，該算法能夠保護(hù)種群的多樣性，節(jié)省時(shí)間，加速收斂速度。

為此，文章用MHGAPF特指用快速M(fèi)H變異遺傳重采樣算法的PF算法的無(wú)線傳感器目標(biāo)跟蹤算法。把快速M(fèi)H變異遺傳算法加入到傳統(tǒng)粒子濾波中，用來(lái)增加樣品組的多樣性，減少樣品組的衰退?？s短監(jiān)測(cè)時(shí)間和提高監(jiān)測(cè)能力后續(xù)行動(dòng)。實(shí)驗(yàn)結(jié)果表明，算法具有顯著的優(yōu)點(diǎn)[3]。

1 粒子濾波算法

粒子濾波是在蒙特卡洛提出的方法上改進(jìn)的算法。該算法使用一類(lèi)的隨機(jī)加權(quán)估量器(也稱(chēng)為粒子)來(lái)類(lèi)似的后概率密度u(xk|z1:k)。

(1)

(2)

(3)

通過(guò)上述的公式，代入式(2)，可以確定粒子顯著性的遞歸公式(4):

(4)

通過(guò)公式(3)和式(4)形成了一種基于粒子過(guò)濾算法的方法，其中重采樣算法可以減緩傳統(tǒng)粒子過(guò)濾算法中粒子所出現(xiàn)的問(wèn)題。

在現(xiàn)有的重采樣算法中，選擇高權(quán)重粒子進(jìn)行更新，然而粒子的多樣性將丟失。因此，基于粒子濾波算法的遺傳算法被插入到重采樣過(guò)程中。通過(guò)使用交叉和變異等運(yùn)算符來(lái)確保粒子多樣性的方法?？梢员３謱?duì)粒子權(quán)重選擇和演變過(guò)程的高適應(yīng)性。它能很好地適應(yīng)顆粒重量的選擇和發(fā)展上這樣就實(shí)現(xiàn)了粒子的有效性[4]。

2 遺傳粒子濾波算法

2.1 粒子集合的編碼、遺傳操作

把遺傳算法引進(jìn)到粒子濾波算法中，可以在粒子群優(yōu)化中引進(jìn)新的個(gè)體。粒子群多樣性繼續(xù)保持。粒子濾波的精度和魯棒性有效的提升，所以稱(chēng)為遺傳粒子濾波。為了保證計(jì)算速度，采用十進(jìn)制編碼。遺傳交叉和變異等過(guò)程是在十進(jìn)制的基礎(chǔ)上進(jìn)行的。

通過(guò)引進(jìn)遺傳進(jìn)化理念，可以獲得新的基因過(guò)濾樣品。粒子被視為染色樣品，每個(gè)粒子的相應(yīng)加權(quán)系數(shù)被用作染色體樣品的適應(yīng)性函數(shù)。染色體標(biāo)準(zhǔn)粒子濾波算法解決了選擇過(guò)程中粒子退化和耗盡的問(wèn)題。并且交叉引用和基因突變算法。通過(guò)選擇和交叉操作，后代可以繼承和調(diào)整每個(gè)顏色樣本的相應(yīng)匹配功能的大小，而父系一代的變化可以沿著進(jìn)化方向發(fā)展。也就是說(shuō)，從總體優(yōu)化的角度來(lái)發(fā)展。

遺傳操作的原始種群一般是在隨機(jī)時(shí)刻生成的粒子群，這個(gè)粒子群通過(guò)初始狀態(tài)方程計(jì)算得到的。個(gè)體的適應(yīng)性決定目標(biāo)和模板之間的相似性程度，其被選中的可能性越大是由于其相似度越大，被保留的可能性越大。根據(jù)一定的概率選擇一對(duì)交叉運(yùn)算。最后，有概率的選取對(duì)象進(jìn)行十進(jìn)制漸變。然而個(gè)體的多樣性通過(guò)交叉和變異來(lái)增強(qiáng)，以防止局部解被混淆[5-6]。

2.2 遺傳粒子濾波算法

進(jìn)行重采樣GAPF的算法，其算法運(yùn)行過(guò)程可以描述如下：

Step1:在原始種群粒子中u(x0)中采樣M個(gè)粒子xi0，i=1，2，…，m；

Step2: 計(jì)算a時(shí),我們通過(guò)前面的定義狀態(tài)的轉(zhuǎn)移方程來(lái)刻的粒子更新xia，i=1，2，…，m；

Step3: 通過(guò)量測(cè)方程計(jì)算a時(shí)刻集中各個(gè)新粒子的權(quán)值xia，i=1，2，…，m；

Step4:同時(shí)要考慮到權(quán)值系數(shù)較大的粒子，也就是重要度較高的粒子選擇和粒子的多樣性，經(jīng)過(guò)一系列的基因操作，最后決定粒子適應(yīng)度是通過(guò)權(quán)值系數(shù)大小來(lái)判定，權(quán)值系數(shù)大的則保留下來(lái)，并且繼續(xù)迭代出經(jīng)過(guò)優(yōu)化的粒子群，完成粒子重新采集[7]。

(5)

Step5：計(jì)算a時(shí)刻的狀態(tài)估計(jì)；

Step6：令a=a+1，在下一時(shí)刻重新轉(zhuǎn)步驟(2)。

3 快速M(fèi)H變異遺傳粒子濾波算法

MCMC(Markov Chain Monte Carlo)是一種隨機(jī)生成算法，它隨機(jī)選擇后驗(yàn)概率密度函數(shù)模型。該算法產(chǎn)生樣本速度慢，原因是由于它從全局抽樣，因此，V.Cevher[7]提出了一種更好的MH快速算法，該算法以另一種方式生成樣本。 這樣我們就可以有效地防止粒子運(yùn)動(dòng)的速度，并加速全局的收斂?？焖費(fèi)H算法由兩部分組成：排序重組和經(jīng)典MH更新，主要步驟描述如下：

算法1:快速M(fèi)H更新

1)設(shè)定一個(gè)粒子集N

2)對(duì)于前M-Nt個(gè)粒子(新粒子集)中運(yùn)用算法2得到更新后的前M-Nt個(gè)粒子。

3)從更新后的粒子集合中前M-Nt個(gè)粒子均勻抽取Nt個(gè)候選粒子，重新組合成大小為M的粒子集合。

算法2：經(jīng)典MH更新是隨機(jī)變量φ的樣本，它是通過(guò)構(gòu)造一個(gè)平穩(wěn)分布為π(φ)的馬爾可夫鏈來(lái)獲得的，通過(guò)這些樣本就可以作各種統(tǒng)計(jì)推斷，其主要步驟描述如下：

1)初始化目標(biāo)分布函數(shù)π(φ)和隨機(jī)值φ；

2)產(chǎn)生一個(gè)候選φ′，根據(jù)一個(gè)特定的轉(zhuǎn)移函數(shù)(建議密度)進(jìn)行擾動(dòng)，如:

g(φ,φ′)=g(|φ-φ′|)∝exp[(φ-φ′)2/(2γ2)]

(6)

3)計(jì)算接受率:

B(φ,φ′)=min[π(φ′/x)g(φ′,φ)/(π(φ/x)g(φ,φ′)),1]

(7)

4)按照u-U(0,1)采樣；

5)如果u≤B(φ,φ′)，則φk+1=φ′，否則，φk+1=φ。

用跳轉(zhuǎn)頻度Tjump來(lái)選擇是否需要排序重組，因此可以控制排序重組的頻度。經(jīng)過(guò)快速M(fèi)H更新后，后驗(yàn)概率大的粒子作為初始隨機(jī)值產(chǎn)生新粒子的可能性更大，可以產(chǎn)生更符合分布函數(shù)π(φ)的φ′來(lái)取代初始值φ。在快速M(fèi)H的遺傳突變重采樣算法執(zhí)行期間，可以對(duì)運(yùn)算算法進(jìn)行修改，以使粒子更符合狀態(tài)的概率密度函數(shù)的分布。 新遺傳算法的實(shí)現(xiàn)的重采樣步驟為：

1)編碼方式：PF狀態(tài)估計(jì)是連續(xù)參數(shù)進(jìn)行優(yōu)化的過(guò)程。通常采用二進(jìn)制編碼，但是在編碼過(guò)程中，有點(diǎn)缺陷就是會(huì)造成編碼串過(guò)長(zhǎng)，并且需要再解碼為實(shí)數(shù)，整體計(jì)算運(yùn)行時(shí)間長(zhǎng)，影響學(xué)習(xí)的精度。為了克服上述缺點(diǎn)，本文直接用實(shí)數(shù)矩陣方式，有利于遺傳算子的對(duì)應(yīng)位置操作，大大簡(jiǎn)化計(jì)算過(guò)程，加快運(yùn)行速度。

3)遺傳算子:

(1)選擇：用賭輪法選擇，適應(yīng)度大的粒子被選擇的概率大。

(2)交叉：以概率Pc作父輩染色體的交叉，交叉算子采用算術(shù)相加[7]。

快速M(fèi)H變異遺傳重采樣流程，如圖1所示。基于快速M(fèi)H變異的新遺傳粒子濾波完整算法描述如下：

算法3：新遺傳粒子濾波器算法(NGRPF)

2)令k=1:K進(jìn)行濾波更新：

粒子狀態(tài)預(yù)測(cè)與更新:

(8)

粒子權(quán)值歸一化:

(9)

計(jì)算:

(10)

判斷是否需要重采樣。

新遺傳重采樣。

4 快速M(fèi)H變異遺傳粒子濾波的無(wú)線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法

應(yīng)用上述算法解決衰敗現(xiàn)象，其基本思想是：粒子濾波產(chǎn)生的每一個(gè)粒子都被視為一個(gè)染色體，利用快速M(fèi)H變異遺傳算法對(duì)樣本集進(jìn)行了優(yōu)化。

MHGAPF算法優(yōu)化的整個(gè)過(guò)程如圖2所示。

圖2中，F(xiàn)(t)代表粒子編碼的第t代種群，Q(t)代表第t代的所有構(gòu)造染色體種群。MHGAPF算法優(yōu)化實(shí)現(xiàn)過(guò)程如下：

4)反復(fù)執(zhí)行算法：

While( 條件為真一直執(zhí)行，不滿(mǎn)足終止條件)do //最終用遺傳中最大迭代數(shù)為結(jié)束條件Begin

②t=t+1；

③先后依次測(cè)量種群F(t)中的個(gè)體，以獲得一組狀態(tài)Q(t) ；

④針對(duì)每個(gè)狀態(tài)計(jì)算其適應(yīng)度；

改變方法，快速M(fèi)H變異粒子迭代更新總體P(t)以保持總體F(t+1)；

⑤保存最佳個(gè)體及觀察其狀況。

End

下面是算法的具體實(shí)行步驟:

①全部傳感器節(jié)點(diǎn)向執(zhí)行MHGAPF以定位和跟蹤目標(biāo)的Sink節(jié)點(diǎn)發(fā)送測(cè)量信息。本文中假定不同傳感器節(jié)點(diǎn)之間的觀測(cè)值是無(wú)關(guān)聯(lián)的，相互獨(dú)立的。具體算法實(shí)現(xiàn)如下：

②粒子更新和權(quán)值更新

Fori=1,…,K；

1)收到M個(gè)獨(dú)立量測(cè)。

2)Fori=1,…,N；

(11)

歸一化權(quán)值:

(12)

③快速M(fèi)H變異粒子優(yōu)化；此方法的優(yōu)化過(guò)程允許從最佳重量的樣本中獲得樣本集。

④對(duì)狀態(tài)進(jìn)行估計(jì)；

(13)

對(duì)協(xié)方差進(jìn)行估計(jì)：

(14)

5 算法仿真與分析

本文在進(jìn)行分析時(shí)，只考慮單個(gè)目標(biāo)在有效的檢測(cè)區(qū)域內(nèi)做勻速直線運(yùn)動(dòng)。其中，它的測(cè)量方程和運(yùn)動(dòng)狀態(tài)方程如下：

(15)

針對(duì)PF濾波算法、GAPF濾波算法和MHGAPF濾波算法3種方法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)中具體的做法是在保留最高重要度權(quán)值的基礎(chǔ)上，經(jīng)過(guò)遺傳操作后，某一部分的新權(quán)重應(yīng)大于原始值，否則在下一次迭代過(guò)程中將保留原始粒子。

衡量跟蹤精度通常用均方根誤差來(lái)計(jì)算值的大小來(lái)表示，它是反映目標(biāo)跟蹤算法中跟蹤效果好壞的指標(biāo)，本文的采用3種算法：普通粒子濾波算法、遺傳粒子濾波算法、MHGAPF遺傳粒子濾波算法，通過(guò)它們的跟蹤均方根誤差計(jì)算數(shù)值和對(duì)比曲線來(lái)分析性能好壞,跟蹤均方根誤差計(jì)算公式如下式[8-10]，

(16)

在仿真實(shí)驗(yàn)中比例取0.71，通過(guò)運(yùn)行，得到本次實(shí)驗(yàn)中3種算法的狀態(tài)跟蹤曲線如圖3所示。

由圖3可知, PF算法和MHGAPF算法遠(yuǎn)離目標(biāo)。PF算法和GAPF算法跟蹤誤差大，PF算法跟蹤精度最低，其次是GAPF算法。PF算法和GAPF算法不能精確跟蹤，而本文提出的MHGAPF算法則能夠補(bǔ)充上面的不足，可以能很好地實(shí)現(xiàn)穩(wěn)定跟蹤，效果很明顯。MHGAPF算法比PF算法、GAPF算法更為接近目標(biāo)，跟蹤精度稍高些，可以能很好地實(shí)現(xiàn)穩(wěn)定跟蹤，效果很明顯。通過(guò)圖4和圖5可以發(fā)現(xiàn)，PF濾波的速度估計(jì)誤差最大，GAPF 濾波效果稍好些，MHGAPF能最好地估計(jì)目標(biāo)運(yùn)動(dòng)速度。PF，GAPF、MHGAPF 算法運(yùn)行時(shí)間分別是50.16 s,42.18 s和29.16 s。全面比較后，跟蹤精度與粒子數(shù)有關(guān)，粒子數(shù)越多，跟蹤精度越高，但隨著粒子數(shù)的增加，時(shí)間越長(zhǎng)，因此，減少工作時(shí)間。MHGAPF算法計(jì)算時(shí)間最短。由于其本身的優(yōu)越性，MHGAPF算法可以提高實(shí)時(shí)監(jiān)控的有效性。本文3種濾波算法PF算法、GAPF算法和MHGAPF 算法分別進(jìn)行了120次仿真試驗(yàn)，可以得出目標(biāo)位置和速度的均方根誤差，3種濾波算法的均方根誤差由表1所示。

表1 3種濾波算法的均方根誤差

由表1可知，與GAPF算法和PF算法相比MHGAPF算法位置和算法速度的中均方根誤差最低，其中PF算法的跟蹤精度最低，MHGAPF跟蹤精度最高，進(jìn)一步表明MHGAPF算法具有良好的跟蹤性能。

由圖6可知，本文算法的跟蹤精度優(yōu)于PF 和GAPF算法。由于MHGAPF是通過(guò)服從狀態(tài)后驗(yàn)概率分布的粒子集合來(lái)進(jìn)行狀態(tài)估計(jì)，對(duì)于非高斯噪聲的干擾不敏感，因此其曲線并沒(méi)有較大的波動(dòng)。而標(biāo)準(zhǔn)PF的RMSE曲線卻變得更加曲折，且跟蹤精度變低。

6 結(jié)束語(yǔ)

本文提出了一種基于MH快速變異的新遺傳粒子濾波算法，并將其用于目標(biāo)跟蹤和無(wú)線傳感器檢測(cè)。 該算法用于粒子采樣，提出了一種快速的MH算法來(lái)生成變異粒子，并且最優(yōu)粒子在初始粒子集中的較小范圍內(nèi)移動(dòng)。 由于根據(jù)后驗(yàn)概率密度函數(shù)創(chuàng)建新粒子，因此可以保證新添加的粒子的效率，并在保留優(yōu)良粒子的基礎(chǔ)上實(shí)現(xiàn)粒子的多樣性，從而濾波功能得到極大改善。理論分析和實(shí)驗(yàn)結(jié)果表明，該方法能有效地解決粒子退化問(wèn)題，該算法的整體濾波效果優(yōu)于普通粒子濾波，在速度、效率和功能上都有明顯的優(yōu)勢(shì)，能夠較好地應(yīng)用于實(shí)時(shí)跟蹤[11-12]。本文提出的算法具有較高的實(shí)用價(jià)值，因此，能夠更好地適應(yīng)于工程應(yīng)用。但是，粒子濾波算法本身計(jì)算量比較大，耗費(fèi)能量多，這對(duì)于能量有限的無(wú)線傳感器網(wǎng)絡(luò)是嚴(yán)峻的考驗(yàn)，解決跟蹤精度的問(wèn)題和同時(shí)減少能量消耗的問(wèn)題，這還需要進(jìn)一步研究[13-14]。