一種GPS多徑時延估計的改進粒子濾波算法

張婷菲，趙 昀，王星然

(北京航空航天大學電子信息工程學院，北京100191)

0 引言

影響衛星導航定位精度的誤差源有許多，但隨著全球衛星導航系統(GNSS)的增強以及現代化程度的提高，許多誤差源的影響正在減少，多徑效應產生的誤差已經成為最重要的誤差源。

多徑是指衛星發射的信號通過非視線(Line of Sight，LOS)路徑到達接收機的現象。由此，接收機接收的信號是直達信號和多徑信號的疊加，導致產生額外的跟蹤誤差，進而影響到導航定位精度。尤其在城市環境建筑物比較密集形成眾多反射面，多徑效應更為嚴重。對多徑效應的抑制程度直接影響到定位精度以及導航性能。為了消除多徑影響，許多多徑抑制技術不斷地被開發出來，并在各類接收機中得到應用，如窄相關技術［1］、Strobe相關器技術和MEDLL技術等。

近十幾年，基于蒙特卡羅方法［2，3］和遞推貝葉斯估計［4］的粒子濾波(PF)算法［5］因其適用于非線性及非高斯噪聲問題求解而受到關注。文章提出了一種改進的粒子濾波算法——基于遺傳算法的粒子濾波GAPF。將遺傳算法引入粒子濾波框架，用于估計多徑時延，和標準粒子濾波算法相比，能有效增加粒子多樣性，克服粒子退化問題。運用遺傳算法的選擇、交叉和變異算子改進粒子樣本的多樣性，防止樣本空間在重采樣后出現退化，從而提高多徑時延的估計精度。此外，利用卡爾曼濾波對多徑信號的幅值實現估計。

首先，介紹了GPS多徑信號的模型，并針對采樣信號處理帶來的計算量大的問題，給出了信號向量壓縮方法;其次，介紹了遺傳算法，并給出了用遺傳算法改進粒子濾波用于估計多徑時延的步驟，以及結合卡爾曼濾波實現多徑幅度的估計;最后，對提出的算法進行仿真驗證。

1 GPS多徑信號模型

設GPS接收機接收到的基帶信號模型為:

式中，Nm為到達接收機信號路徑的總數;c(t)為擴頻碼序列;ai(t)和τi(t)分別為第i路信號的復數幅度(包含相位)和時延;n(t)為信道噪聲，n(t)～N(0，σ2)。將(m+kL)Ts(m=0，1，…，L－1)時刻的L個樣本作為LTs時間段內的整體觀測向量zk，同時假設ai(t)和τi(t)在這個時間段內保持不變，記為ai，k和 τi，k，則式(1)可離散化為:

式中，C(τk)= ［c(τ1，k)，c(τ2，k)，…，c(τNm，k)］，c(τi，k)為擴頻碼 c(t－ τi，k)的樣本向量。τk=［τ1，k，τ2，k，…，τNm，k］T和ak= ［a1，k，a2，k，…，aNm，k］T分別為待估計的時延向量和復數幅度向量;而sk=C(τk)ak為信號假設。

2 觀測向量壓縮

在本方法中，似然函數的求解至關重要，它表示系統狀態從τk－1轉移到τk對應的信號假設和觀測值zk的相似度，并由此決定各個粒子的權重。聯合似然概率分布可寫為［6］:

由于觀測向量zk包含了大量的樣本，直接使用式(3)來計算每個粒子的似然函數需要非常大的計算量，需要找到一個列數較少的正交壓縮矩陣Qc，使得壓縮后的觀測向量是待估計多徑信道的充分統計量，這樣壓縮后的信號測量模型變為:

式中，Ng為壓縮后觀測向量的維數，遠小于式(3)中的L。

3 基于遺傳算法的粒子濾波

3.1 遺傳算法

達爾文的進化論認為，生物都是在逐漸地適應其生存環境來延續生命的。物種個體的基本特征會被后代所繼承，但后代又不完全等同于父代。這些新的變化，若更能適應某一環境，則被保留下來，否則，將被淘汰。遺傳算法［7，8］主要包括 3個遺傳算子:選擇算子、交叉算子和變異算子。運用遺傳算法對得到的粒子空間進行重采樣，用選擇、交叉和變異3種遺傳算子產生出新的一代更接近真實狀態的粒子空間，從而可以保證粒子空間的多樣性，避免粒子的退化現象。

3.1.1 編碼

本文采用的二進制編碼方法是遺傳算法中最主要的一種編碼方法，它使用的編碼符號集是二值符號集0，{}1。二進制編碼符號串的長度與問題所需的求解精度有關。本文取編碼符號長度為14，對應的十進制變量能精確到小數點后4位。

3.1.2 選擇算子

遺傳算法使用選擇算子來對群體中的個體進行優勝劣汰操作:根據每個個體的適應度值大小選擇，適應度高的個體被遺傳到下一代群體中的概率大;適應度低的個體被遺傳到下一代群體中的概率較小。

本文中使用隨機遍歷抽樣方法進行選擇，算法說明如下:假設群體中有N個個體，FitV是一列向量，包含種群中個體適應度值(適應度用于衡量群體中各個個體在優化計算中能達到或接近或有助于找到最優解的優良程度)。通過獲得適應度向量FitV的累加和完成隨機遍歷抽樣的表格［SUM(FitV(1))…SUM(FitV(1∶i))…SUM(FitV(1∶N))］，產生N個在［0，SUM(FitV)］內相等的空間編號。產生一個［0，1］之間均勻分布的隨機數，通過比較產生的隨機數與向量累加和來決定被選擇的個體，比如，隨機數小于表格中的第i個值，那么第i個個體就被選中，否則，再產生一個隨機數，將它與表格中的第i+1個值進行比較，如此反復進行，直到選擇N個個體進入交叉步驟。

3.1.3 交叉算子

遺傳算法中利用交叉算子來產生新的個體。交叉，又稱為重組，對個體進行兩兩隨機配對，按較大的概率從群體中選擇2個個體，交換2個個體的某個或某些位。交叉概率一般取0.4～0.99。本文取0.7作為交叉概率，使用單點交叉。

3.1.4 變異

變異是以較小的概率對個體編碼串上的某個或某些位值進行改變，進而生成新個體，從而保持了粒子空間的多樣性。

變異概率一般取0.000 1～0.1。本文使用基本位變異，變異概率取0.05。

3.1.5 適應度函數的選擇

在遺傳算法中，適應度函數的選擇比較靈活，合理選擇適應度函數有利于算法收斂到全局最優解，否則，有可能收斂到局部最優。本文將前述的似然概率作為適應度函數。

3.2 遺傳算法改進粒子濾波

利用基于遺傳算法的粒子濾波估計多徑時延［9，10］，如圖 1 所示。

圖1 遺傳粒子濾波算法流程

主要步驟如下:

②預測。從k時刻的粒子權重集，利用狀態方程預測k+1時刻的粒子集

④遺傳算法重采樣。k=k+1，跳到第②步。

3.3 卡爾曼濾波估計多徑幅度

將改進粒子濾波用于解決非線性的多徑時延估計，對于線性的多徑信號幅度的估計，采用卡爾曼濾波算法［11］。

4 改進多徑估計算法的仿真驗證

仿真實驗利用導航信號模擬器產生100 s的數字中頻 GPS導航仿真信號。中頻頻率為1.405 MHz，采樣率為11MHz，載噪比C/N0為50 dB-Hz，四比特量化。

針對可見星14，在模擬器中加入14號星的一路同相多徑分量，多徑與直達信號的幅度比為0.5，對于多徑的時延，在0～1之間以均勻分布隨機產生的100個隨機數，單位為碼片，每個時延值持續時間為1 s。隨機產生的時延值隨時間變化的趨勢如圖2所示。

圖2 14號星多徑時延的變化

利用標準粒子濾波算法與遺傳粒子濾波算法分別估計出多徑的信道參數，并對它們的結果進行比較。這2種算法的時延估計結果與真實多徑時延的比較如圖3所示。這2種算法多徑時延估計的均方誤差比較如圖4所示［12］。分別結合標準粒子濾波和遺傳算法粒子濾波算法，利用卡爾曼濾波對信號幅度進行估計，得到多徑信號與直達信號的幅度比值，并對這2種算法的仿真結果進行比較，多徑信號幅度與直達信號幅度比值的估計結果分別如圖5(a)和圖5(b)所示。

圖3 PF與GAPF估計結果比較

圖4 PF與GAPF估計的均方根誤差比較

圖5 信號幅度估計結果

從上述的比較可以看出，遺傳粒子濾波算法的性能比標準的粒子濾波有較明顯改善，對仿真結果進行統計得出，改進的算法將多徑時延的估計精度提高了約130 ns(即0.13碼片)。

5 結束語

研究了基于改進粒子濾波算法的多徑估計方法。改進粒子濾波主要用來解決多徑的時延估計，而多徑信號的幅度，運用卡爾曼濾波來解決。針對標準的粒子濾波帶來的粒子退化問題，將遺傳算法用于粒子濾波的重采樣步驟，改善標準粒子濾波的粒子退化和多樣性下降現象。對上述多徑估計算法進行了基于導航信號模擬器的測試。通過對標準粒子濾波和改進粒子濾波算法的仿真結果進行比較分析，結果顯示本文提出的改進算法能夠提高多徑估計精度。

［1］周 非，黃順吉.利用窄帶相關進行多徑信號抑制分析［C］∥中國西部青年通信學術會議論文集，2005:669－674.

［2］DOUCET A，DE FREITAS N，GORDON N.Sequential Monte Carlo Methods in Practice［M］.Springer，New York，NY，USA，2001.

［3］LENTMAIER M，KRACH B，ROBERTSON P.Dynamic Multipath Estimation by Sequential Monte Carlo Methods［C］∥ Proceedings of ION GNSS 2007，Fort Worth，USA，2007:1 712 －1 721.

［4］LENTMAIER M，KRACH B，ROBERTSON P.Bayesian Time Delay Estimation of GNSS Signals in Dynamic Multipath Environments［M］.International Journal of Navigation and Observation，2008.

［5］BERTOZZI T.Timing Error Detector Using Particle Filtering［C］∥Signal Processing and Its Applications，2003.Proceedings Seventh International Symposium on 2003:491－494.

［6］KRACH B，LENTMAIER M.Efficient Soft-output GNSS Signal Parameter Estimation Using Signal Compression Techniques［C］∥Proceedings of the 3rd ESA Workshop on Satellite Navigation User Equipment Technologies(NAVITECH'06)，Noordwijk，the Netherlands，2006.

［7］周 明，孫樹棟.遺傳算法原理及其應用［M］.北京:國防工業出版社，1999.

［8］SCHMITT LOTHAR M.遺傳算法理論(二)［M］.Theoretical Computer Science(310)，2004:181 －231.

［9］林 愷，石江宏，鄧振淼.基于遺傳算法粒子濾波的多徑跟蹤［J］.電子測量技術，2012，35(2):50 －54.

［10］李翠蕓，姬紅兵.新遺傳粒子濾波的紅外弱小目標跟蹤與檢測［J］.西安電子科技大學學報(自然科學版)，2009，36(4):620 －623.

［11］RISTIC B，ARULAMPALAM S，GORDON N.Beyond the Kalman Filter:Particle Filters for Tracking Applications［M］.Artech House，Boston，Mass，USA，2004.

［12］SUH Y，KONISHI Y.Evaluation of Multipath Error and Signal Propagation in Complex 3D Urban Environments for GPS Multipath Identification［C］∥ ION GNSS 17th International Technical Meeting of the Satellite Division，2004.