聚類算法的GPS靜態單點定位方法

劉 勝，張青春，張蘭勇

（哈爾濱工程大學自動化學院，150001 哈爾濱）

聚類算法的GPS靜態單點定位方法

劉 勝，張青春，張蘭勇

（哈爾濱工程大學自動化學院，150001 哈爾濱）

為有效提高GPS靜態單點定位的精度，提出了一種基于模糊聚類算法和卡爾曼濾波算法的組合優化方法.該方法首先對GPS實測數據進行卡爾曼濾波，消除波動較大的數據，然后應用模糊C-均值聚類算法尋求聚類中心，以該聚類中心為最終定位坐標.實驗結果表明，該組合優化定位方法在降低定位成本的同時，可以有效提升GPS靜態單點定位精度，采用該方法得到的定位坐標更接近于真實的地理坐標.

GPS;單點定位;卡爾曼濾波;模糊C-均值聚類

GPS(Global Positioning System)的定位精度受很多因素影響，諸如電離層延時誤差、多徑延時誤差等，這些因素所導致的定位精度在很多場合不能滿足用戶的要求［1］.因此，消除誤差，提高 GPS的定位精度，已成為人們研究的熱點.目前，提高靜態單點定位精度的研究工作，主要有:1)利用差分技術，基準站的GPS差分信號接收機，將得到的GPS定位誤差修正值發送至用戶接收機，并對用戶接收機的定位結果進行修正;2)單點自主式定位技術，采用各種濾波算法，對接收機實測的數據進行實時或事后處理，以濾除各類誤差影響［2－3］.差分 GPS技術的應用受工作區的限制且成本較高.因此，研究提高成本較低的GPS單點自主式定位精度的方法是一項有意義的工作.

在濾波算法上，比較常用的有最小二乘法、卡爾曼濾波、自適應濾波及粒子濾波等.杜曉輝等［4］分別將最小二乘法和卡爾曼濾波應用于靜態單點定位并比較了二者的定位誤差，證明卡爾曼濾波算法可以有效的利用噪聲統計特征對坐標量進行估計，得到較好的定位精度;K.Yedukondalu等［5］應用最小均方差(LMS)自適應濾波算法對GPS信號多徑效應誤差進行消除，證明該方法可以有效降低多徑效應誤差，提高定位精度.本文從實際應用的角度出發，提出一種基于卡爾曼濾波和模糊C-均值聚類的組合優化定位方法.該方法首先對GPS采集到數據進行卡爾曼濾波，消除波動較大的數據，然后采用模糊C-均值聚類算法確定數據中心，得到高精度的坐標點.

1 GPS單點定位原理

GPS的定位原理，其依據是測量學中的空間距離后方交會.通過觀測GPS衛星，可以獲得衛星的位置及衛星到觀測點的距離.以此位置為圓心，距離為半徑做球面，多個球面的相交點，便是所求觀測點的位置.在實際的觀測過程中，接收機觀測所得的衛星到觀測點的距離包含了接收機鐘與衛星鐘之間的鐘差所帶來了的誤差，并非衛星到觀測點的實際的距離，故稱之為偽距［6］.

接收機測得的距離為偽距，存在一個固定但未知的鐘差，加上所求觀測點的三維位置坐標，共4個未知數待求，故要實現單點定位至少須同時觀測4個GPS衛星，以組成GPS定位基本方程，如圖1所示.

圖1 GPS單點定位

圖1中R為衛星到接收機間的真實距離，ρ為偽距觀測值，τ為接收機鐘差，則觀測方程為

式中:假定偽距觀測值ρ已通過星歷中的電離層延遲和對流層延遲修正;(Xs，Ys，Zs)為衛星的瞬時地心坐標，可通過衛星星歷電文求得;(Xp，Yp，Zp)為接收機的地心坐標，即所求量.

解算出的(Xs，Ys，Zs)為地心坐標，可與常用的經緯度坐標(φ，λ，h)相互轉換為

式中:e為橢球第1偏心率;n為橢球卯酉圈曲率半徑.設橢球長半徑為a，短半徑為b，那么

已知，地球長半徑a=6 378 137.07 m，地球短半徑b=6 356 752.48 m.

2 Kalman濾波模型及數據處理

靜態單點定位模型，可近似認為定常速度模型，以待測點的位置和速度作為狀態變量.為便于觀測數據的處理，假定系統噪聲和測量噪聲為高斯白噪聲，有針對性的分析濾波后的效果［7］.通常情況下可將其視為一個線性系統，采用最小二乘法或卡爾曼濾波的方法進行數據處理.

根據以上分析，定義狀態向量為

離散化后的系統狀態方程與觀測方程為

式中:xk為狀態向量;Φk/k－1為狀態轉移矩陣;Γk－1為噪聲驅動陣;wk－1為系統噪聲，其相應協方差陣為Qk－1;zk為觀測向量;Hk為量測陣;vk為觀測噪聲，其相應的協方差陣為Rk.根據牛頓方程可得離散化后的定常速模型參數為

由于本文研究靜態定位，因此無需速度信息，只需位置信息.所以

其后，需要對卡爾曼濾波的初值進行適當的選取.根據卡爾曼穩定性定理及濾波誤差方差陣的漸近性定理［8］:在系統初始狀態的統計特性不明了或不易獲得的情況下，可令=06×1，P0= αI6(α可為一個較大的常數).鑒于單點定位觀測數據的特征，取第1個坐標點(x0，y0，z0)為初值，即，并取 P0=10I6.

因為本文所采用的GPS數據輸出頻率為1 Hz，所以離散化后的采樣時間為T=1.經過上文分析與設定，濾波計算采用定常系統卡爾曼濾波方程［9］

濾波前數據如圖2所示，可以看到未濾波的GPS原始數據，波動范圍比較大，經度范圍為［126.673 2°，126.673 9°］;緯度范圍為［45.771 7°，45.772 7°］.經卡爾曼濾波后數據分布如圖3所示，經度控制在［126.673 55°，126.673 65°］范圍內;緯度控制在［45.771 9°，45.772 1°］范圍內.

圖2 濾波前數據分布

圖3 濾波后數據分布

通過對比，卡爾曼濾波的確能夠消除較大的數據波動，逼近GPS所測位置的真實坐標.當然，濾波的目的是對原始數據進行預處理，剔除波動較大的數據，濾波后的數據是一個較小的區域，要得到高精度的坐標位置，需要進一步的數據處理.

3 模糊C-均值聚類算法確定坐標中心

經過卡爾曼濾波后的坐標值全都處在空間內較小的鄰域內，但是還不能提供可以使用的定位值.模糊C-均值聚類算法［10］是基于目標函數的聚類算法，該算法沿著目標函數減小的方向進行迭代，具有良好的收斂性，能夠對數據進行分類，并找出聚類中心.根據本文所述，GPS數據不需分類，僅需確定聚類中心即可.因此，在本文中采用模糊C－均值聚類方法確定坐標中心.

設 X={x1，x2，…，xn}?Rs是數據集，n為數據集元素個數，c為聚類中心數(1＜c＜n)，dij=‖xi－Vj‖為樣本點xi和聚類中心Vj的歐式距離，Vj?Rs(1 ＜ j＜ c).uij為第i個樣本屬于第j個中心的隸屬度，U=［uij］為一個n×c矩陣，V=［V1，V2，…，Vc］是一個 s × c矩陣.

這里m為權重系數(m ＞1)，研究表明，m的最佳選擇范圍為［1.5，2.5］，通常m=2是比較理想的取值［11］.

解決上述的數學規劃問題的算法步驟如下:

起始 選取 ε ＞0，初始聚類中心 V(0)，令k=0，

步驟1 計算U(k)

如果存在i，r使得dir(k)＞0，則

如果存在 i，r使得 dir(k)=0，則令

步驟2 計算V(k+1)

步驟3 如果‖V(k+1)－V(k)‖ ＜ε則停止，否則令k=k+1，回到步驟1.最終得到的V即為聚類中心矩陣.

將模糊C-均值聚類方法，結合本文實際.在卡爾曼濾波的基礎上，采用基于數據密度的模糊C-均值聚類方法，直接將GPS數據劃分為一類，m取值為2，最后確定數據中心.其算法流程如圖4所示.

圖4 模糊C-均值聚類算法流程

4 結果分析

實驗采用的GPS數據為實測單點靜態定位原始數據.真實地理信息位置為(126.673 596°E，45.772 053°N).GPS接收機，數據輸出頻率為1 Hz，共得到觀測數據520組.

首先，對原始數據直接應用模糊C-均值聚類算法，得到未濾波數據的聚類中心.其坐標值為(126.673 614°E，45.772 026°N)，如圖5 所示.

圖5 濾波前聚類中心

然后，對原始數據進行卡爾曼濾波，將濾波后的數據進行模糊C-均值聚類運算，得到濾波后聚類中心.其坐標值為(126.673 586°E，45.772 061°N).如圖6所示.

圖6 濾波后聚類中心

圖7為濾波前后聚類中心位置與真實坐標的對比圖.可以直觀的看出，采用卡爾曼濾波與模糊C-均值聚類算法相結合的方法，得到的聚類中心更接近于真實的地理坐標.提高了單點靜態GPS定位精度.

圖7 濾波前后聚類中心與真實坐標對比

5 結論

1)提出了基于卡爾曼濾波和模糊C-均值聚類算法的單點定位組合優化方法.理論分析和實驗結果證明該方法可以有效提升GPS靜態單點定位精度，同時大大降低定位成本，是一種較好的單點定位算法.

2)對于卡爾曼濾波，采用定常速模型.對GPS定位數據處理結果顯示，該模型可以有效利用噪聲的統計特征，得出較小的估計誤差.經該模型去噪后求取的聚類中心，更接近真實的地理坐標，證明了該模型是合理有效的.

［1］劉娣，薄煜明，鄒衛軍.基于時間序列的GPS誤差建模及單點定位精度研究［J］.兵工學報，2009，30(6):825－828.

［2］TU Xianqin，MENG Qinghai，YI Dong-un，et al.Evaluation of kinematic airborne GPS data processing using precise point positioning approach［C］//2012 International Conference on Computer Science and Electronic Engineering.Washington，DC:IEEE Computer Society，2012:63－68.

［3］GAO Y.Canadian high precision real-time gps correction service and real-time atmosphere and deformation monitoring［R］.Wuhan:CPGPS Workshop，2008.

［4］杜曉輝，任章.基于卡爾曼濾波的GPS靜態定位精度分析［J］.全球定位系統，2008(5):47－51.

［5］YEDUKONDALU K，SARMA A D，SRINIVAS S V.Multipath mitigation using LMS adaptive filtering for GPS applications［C］//IEEE-Applied Electromagnetics Conference(AEMC-2009).Washington，DC:IEEE Xplore，2009:14－16.

［6］WANG Huihui，ZHAN Xingqun，ZHANG Yanhua.Geometric dilution of precision for GPS single-point positioning based on four satellites［J］.Journal of Systems Engineering and Electron Ics，2008，19(5):1058 －1063.

［7］孫罡，王昌明，張愛軍.GPS靜態單點定位的濾波方法比較［J］.南京理工大學學報，2011，35(1):80－85.

［8］JWO DahJing，WANG Shenghung.Adaptive Fuzzy strong tracking extended Kalman filtering for GPS navigation［J］.IEEE Sensors Journal，2007，7(5):778 －789.

［9］聶建亮，張雙成，徐永勝.基于抗差Kalman濾波的精密單點定位［J］.地球科學與環境學報，2010，32(2):218－220.

［10］HUNG Chih-cheng，KULKARNI S，KUO Bor-chen.A new weighted Fuzzy C-means clustering algorithm for remotely sensed image classification［J］.IEEE Journal of Selected Topics in Signal Processing，2011，5(3):543－553.

［11］PAL N R，PAL K，KELLER J M，et al.A possibilistic Fuzzy C-means clustering algorithm［J］.IEEE Transactions on Fuzzy Systems，2005，13(4):517 －530.

A method of GPS static single point positioning based on clustering algorithm

LIU Sheng，ZHANG Qing-chun，ZHANG Lan-yong

(School of Automation，Harbin Engineering University，150001 Harbin，China)

This paper presents a combination method based on fuzzy C-means clustering algorithm and Kalman filter，which effectively improves the GPS static point positioning accuracy.Firstly，the latitude and longitude data collected by GPS was filtered by Kalman filtering，which could eliminate large fluctuations in the data.Secondly，the fuzzy C-means clustering algorithm was used to find the clustering center as the final positioning coordinate.The experimental result shows that，this method can effectively promote the degree of accuracy of GPS static single point positioning with low cost，and the coordinates of the positioning is more close to the true geographical coordinates.

GPS;Single point positioning;Kalman filter;Fuzzy C-means clustering algorithm

P228.4

A

0367－6234(2012)11－0071－04

2012－02－13.

國家自然科學基金資助項目(51079033).

劉 勝(1957—)，男，教授，博士生導師.

張青春，zhqch0126@126.com.

(編輯 張 紅)