魏 穎，郭 魯

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

0 引言

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

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

1 粒子濾波算法

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

(1)

(2)

(3)

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

(4)

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

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

2 遺傳粒子濾波算法

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

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

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

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

2.2 遺傳粒子濾波算法

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

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

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

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

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

(5)

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

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

3 量子遺傳粒子濾波算法

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

(j=1,…,n)

(6)

(7)

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

(8)

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

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

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

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

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

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

(1)t=t+1 ；

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

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

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

End

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

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

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

Fori=1,…,K；

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

2)Fori=1,…,N；

(9)

歸一化權(quán)值:

(10)

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

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

(11)

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

(12)

5 算法仿真運(yùn)行和分析

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

(13)

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

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

(14)

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

圖2 目標(biāo)運(yùn)動(dòng)軌跡比較

圖3 目標(biāo)運(yùn)動(dòng)速在x軸的分量比較

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

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

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

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

6 結(jié)束語

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

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