基于量子遺傳粒子濾波的無線傳感器網(wǎng)絡(luò)的目標(biāo)跟蹤算法的研究

魏 穎，郭 魯

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

0 引言

無線傳感器網(wǎng)(WSN,wireless sensor network)是21世紀(jì)最重要的前沿技術(shù)之一，目標(biāo)跟蹤是無線傳感器網(wǎng)絡(luò)的一個主要研究領(lǐng)域，如交通監(jiān)測，捕捉戰(zhàn)爭狀態(tài)等。例如，將一個測試目標(biāo)放置在布置傳感器的地點內(nèi)，它運動時，通過傳感器測量，然后反饋到跟蹤系統(tǒng)，以此接近預(yù)估目標(biāo)的位置[1]。粒子濾波(PF,particle filter) 是一種蒙特卡羅算法，它是基于遞推計算的序列算法，不受非線性等因素的限制，適用于所有的測量模型以及狀態(tài)轉(zhuǎn)換模型，基本思想是在當(dāng)前系統(tǒng)狀態(tài)分布中隨機抽取一些加權(quán)的粒子，通過計算對系統(tǒng)的下一個狀態(tài)進行更新和估計，所以在無線傳感器的目標(biāo)跟蹤中，上述方法比較適合，但不足之處是存在粒子群出現(xiàn)退化現(xiàn)象[2]。如何對多個傳感器的測量值進行有效的處理，以實現(xiàn)對目標(biāo)的精確跟蹤。粒子濾波算法在多次迭代后會退化，即只有少數(shù)粒子具有較大的權(quán)重，而大多數(shù)粒子的權(quán)重很小，幾乎為零，這會消耗大量的時間。這些時間消耗是在大多數(shù)權(quán)重小的粒子上，這些粒子對系統(tǒng)狀態(tài)的評估幾乎沒有影響。這類問題通常下列的方法解決：首先是改善意義重大函數(shù)，其次是對粒子重新采樣。粒子回收是處理粒子衰變的重要手段。粒子累積分布、系統(tǒng)采樣和節(jié)余采樣是常用的重采樣算法。以上的方法主要改善粒子退化效率來解決粒子降解的問題。在新的取樣之后，多次選擇重要性高的粒子，因此，粒子的多樣性已經(jīng)失去了一些，即所謂的粒子缺失。那么在跟蹤目標(biāo)時，一旦監(jiān)測的準(zhǔn)確性不高或目標(biāo)丟失，系統(tǒng)很可能不能自動會聚。本文通過提供一種基于遺傳算法的再采樣策略來解決粒子退化問題，同時存儲有用的粒子。利用進化機制保證粒子群優(yōu)化過程中局部的多樣性，并且處理粒子算法中粒子退化的缺陷。本文對于粒子濾波跟蹤算法的粒子衰退問題給出了一種量子遺傳的粒子濾波跟蹤算法[3-5]。量子遺傳算法(QGA,quantum genetic algorithm) 的染色體由量子密碼決定。因此，通過量子門戶用于在重疊態(tài)上執(zhí)行進化操作。結(jié)果顯示，算法能夠保護種群的多樣性，節(jié)省時間。計算通過量子并行性加速收斂速度。

為此，文章應(yīng)用基于量子遺傳粒子濾波(QGPF,quantum genetic particle filter) 的無線傳感器目標(biāo)跟蹤算法[6]。把量子遺傳算法加入到傳統(tǒng)粒子濾波中，用來增加樣品組的多樣性，減少樣品組的衰退。縮短監(jiān)測時間和提高監(jiān)測能力后續(xù)行動。實驗結(jié)果表明，算法具有顯著的優(yōu)點。

1 粒子濾波算法

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

(1)

(2)

(3)

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

(4)

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

在現(xiàn)有的重采樣算法中，選擇高權(quán)重粒子進行更新，然而粒子的多樣性將丟失。因此，基于粒子濾波算法的遺傳算法被插入到重采樣過程中。通過使用交叉和變異等運算符來確保粒子多樣性的方法。可以保持對粒子權(quán)重選擇和演變過程的高適應(yīng)性。它能很好地適應(yīng)顆粒重量的選擇和發(fā)展上這樣就實現(xiàn)了粒子的有效性。

2 遺傳粒子濾波算法

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

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

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

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

2.2 遺傳粒子濾波算法

進行重采樣GAPF的算法，其算法運行過程可以描述如下：

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

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

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

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

(5)

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

Step6：令a=a+1，在下一時刻重新轉(zhuǎn)Step2。

3 量子遺傳粒子濾波算法

量子遺傳粒子濾波算法(QGA)是在算法中加入遺傳算法同時在計算的概率變化算法結(jié)合量子計算概念和理論基礎(chǔ)上，更增強了優(yōu)點，保護了良好的種群多樣性。它對染色體進行編碼通過量子比特的概率深度計算，從而達(dá)到了使染色體能夠體現(xiàn)出多個狀態(tài)的重疊。然后通過量子旋轉(zhuǎn)門和非量子門更新染色體，以優(yōu)化種群。QGA群體由比特編碼的量子染色體組成。量子遺傳算法中較小的信息單位是量子比特。與傳統(tǒng)的比特相比，它不僅可以是0或1的狀態(tài)，也可以是重復(fù)出現(xiàn)的狀態(tài)。因為這個原因具有多樣性。個體數(shù)為n，則用長度為m的種群代表量子染色體。

(j=1,…,n)

(6)

(7)

式中,量子轉(zhuǎn)子為：

(8)

4 基于量子遺傳粒子濾波(QGPF)的無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法

QGPF算法優(yōu)化的整個過程如圖1所示。

圖1 QGPF算法優(yōu)化過程

圖1中，F(xiàn)(t)代表量子編碼的第t代種群，Q(t)代表第t代的所有構(gòu)造染色體種群，L(t)代表第t代量子旋轉(zhuǎn)門。QGPF算法優(yōu)化實現(xiàn)過程如下：

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

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

(1)t=t+1 ；

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

(3)針對每個狀態(tài)計算其適應(yīng)度；改變方法，利用量子門L(t)迭代更新總體P(t)以保持總體F(t+1)；

(4)保存最佳個體及觀察其狀況。

End

下面是算法的具體實行步驟:

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

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

Fori=1,…,K；

1)收到M個獨立量測。

2)Fori=1,…,N；

(9)

歸一化權(quán)值:

(10)

3)量子遺傳優(yōu)化；此方法的優(yōu)化過程允許從最佳重量的樣本中獲得樣本集。

4)對狀態(tài)進行估計；

(11)

對協(xié)方差進行估計：

(12)

5 算法仿真運行和分析

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

(13)

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

衡量跟蹤精度通常用均方根誤差來計算值的大小來表示，它是反映目標(biāo)跟蹤算法中跟蹤效果好壞的指標(biāo)，本文的采用三種算法普通粒子濾波算法與遺傳粒子濾波算法和量子遺傳粒子濾波算法，通過它們的跟蹤均方根誤差計算數(shù)值和對比曲線來分析性能好壞,跟蹤均方根誤差計算公式如式(14):

(14)

在仿真實驗中比例取0.7，通過運行，得到本次實驗中三種算法的狀態(tài)跟蹤曲線如圖2所示。

圖2 目標(biāo)運動軌跡比較

圖3 目標(biāo)運動速在x軸的分量比較

圖4 目標(biāo)運動速度在y軸的分量比較

由圖2可知,PF算法和GAPF算法遠(yuǎn)離目標(biāo)。QGPF算法更為接近目標(biāo)。但PF算法GAPF算法比QGPF 算法跟蹤精度稍低。PF算法和GAPF算法不能精確跟蹤，跟蹤誤差大，跟蹤精度明顯降低，而本文提出的GAPF算法則能夠補充上面的不足，能很好地實現(xiàn)穩(wěn)定跟蹤，效果很明顯。PF，GAPF、QGPF 算法運行時間分別是56.16 s,46.71 s和30.46 s。全面比較后，QGPF算法計算時間最短。由于其本身的優(yōu)越性，QGPF算法可以提高實時監(jiān)控的有效性。通過圖3和圖4可以發(fā)現(xiàn)，跟蹤精度與粒子數(shù)有關(guān)，粒子數(shù)越多，跟蹤精度越高，但隨著粒子數(shù)的增加，時間越長，因此，量子遺傳粒子濾波可以減少所需粒子數(shù)，減少工作時間。本文改進算法的跟蹤均方誤差小于PF和GAPF算法，由于QGPF算法引入了上述方法，因此它可以有效地提高算法的效率。在樣本改進了粒子的多樣性，提高了算法的可追溯性。使用PF算法、GAPF算法和QGPF 算法分別進行了99次仿真試驗，可以得出目標(biāo)位置和速度的均方根誤差，3種濾波算法的均方根誤差由表1所示。

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

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

6 結(jié)束語

本文涉及的量子遺傳粒子濾波的無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法，該算法用于粒子采樣，粒子恢復(fù)和粒子多樣性是在保留優(yōu)良粒子的基礎(chǔ)上進行的，理論分析和實驗結(jié)果表明，該方法能有效地解決粒子退化問題，為了避免粒子的稀缺性，該算法的整體濾波效果優(yōu)于普通粒子濾波。它只需要少量的粒子，其效果相當(dāng)于大多數(shù)粒子的普通粒子過濾的精度。同時，顯著提高了顆粒過濾器算法的計算速度。有效縮短了微粒過濾器與實際應(yīng)用的距離。并且跟蹤的正確率會保持穩(wěn)定的同時，粒子的數(shù)量也會降低，以此減少運行時間，能夠較好的應(yīng)用于實時跟蹤。

與過去的跟蹤算法相比，該算法在速度、效率和功能上都有明顯的優(yōu)勢。本文提出的算法具有較高的實用價值。因此能夠更好的適應(yīng)于工程應(yīng)用。本文將 QGA 引入 PF 中，提高了粒子的多樣性，有效地解決了粒子濾波嚴(yán)重的退化問題。同時由于量子的在運行時具有并行性，其跟蹤的實時性有了大大提高。通過目標(biāo)在有效監(jiān)測區(qū)域內(nèi)仿真運行實驗證明，能有效精準(zhǔn)跟蹤目標(biāo)。但是，粒子濾波算法本身計算量比較大，耗費能量多，這對于能量有限的無線傳感器網(wǎng)絡(luò)是嚴(yán)峻的考驗，解決跟蹤精度的問題和同時減少能量消耗的問題，這還需要進一步研究。