劉 勝，張青春，張?zhí)m勇

（哈爾濱工程大學(xué)自動(dòng)化學(xué)院，150001 哈爾濱）

聚類算法的GPS靜態(tài)單點(diǎn)定位方法

劉 勝，張青春，張?zhí)m勇

（哈爾濱工程大學(xué)自動(dòng)化學(xué)院，150001 哈爾濱）

為有效提高GPS靜態(tài)單點(diǎn)定位的精度，提出了一種基于模糊聚類算法和卡爾曼濾波算法的組合優(yōu)化方法.該方法首先對(duì)GPS實(shí)測(cè)數(shù)據(jù)進(jìn)行卡爾曼濾波，消除波動(dòng)較大的數(shù)據(jù)，然后應(yīng)用模糊C-均值聚類算法尋求聚類中心，以該聚類中心為最終定位坐標(biāo).實(shí)驗(yàn)結(jié)果表明，該組合優(yōu)化定位方法在降低定位成本的同時(shí)，可以有效提升GPS靜態(tài)單點(diǎn)定位精度，采用該方法得到的定位坐標(biāo)更接近于真實(shí)的地理坐標(biāo).

GPS;單點(diǎn)定位;卡爾曼濾波;模糊C-均值聚類

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

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

1 GPS單點(diǎn)定位原理

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

接收機(jī)測(cè)得的距離為偽距，存在一個(gè)固定但未知的鐘差，加上所求觀測(cè)點(diǎn)的三維位置坐標(biāo)，共4個(gè)未知數(shù)待求，故要實(shí)現(xiàn)單點(diǎn)定位至少須同時(shí)觀測(cè)4個(gè)GPS衛(wèi)星，以組成GPS定位基本方程，如圖1所示.

圖1 GPS單點(diǎn)定位

圖1中R為衛(wèi)星到接收機(jī)間的真實(shí)距離，ρ為偽距觀測(cè)值，τ為接收機(jī)鐘差，則觀測(cè)方程為

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

解算出的(Xs，Ys，Zs)為地心坐標(biāo)，可與常用的經(jīng)緯度坐標(biāo)(φ，λ，h)相互轉(zhuǎn)換為

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

已知，地球長(zhǎng)半徑a=6 378 137.07 m，地球短半徑b=6 356 752.48 m.

2 Kalman濾波模型及數(shù)據(jù)處理

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

根據(jù)以上分析，定義狀態(tài)向量為

離散化后的系統(tǒng)狀態(tài)方程與觀測(cè)方程為

式中:xk為狀態(tài)向量;Φk/k－1為狀態(tài)轉(zhuǎn)移矩陣;Γk－1為噪聲驅(qū)動(dòng)陣;wk－1為系統(tǒng)噪聲，其相應(yīng)協(xié)方差陣為Qk－1;zk為觀測(cè)向量;Hk為量測(cè)陣;vk為觀測(cè)噪聲，其相應(yīng)的協(xié)方差陣為Rk.根據(jù)牛頓方程可得離散化后的定常速模型參數(shù)為

由于本文研究靜態(tài)定位，因此無(wú)需速度信息，只需位置信息.所以

其后，需要對(duì)卡爾曼濾波的初值進(jìn)行適當(dāng)?shù)倪x取.根據(jù)卡爾曼穩(wěn)定性定理及濾波誤差方差陣的漸近性定理［8］:在系統(tǒng)初始狀態(tài)的統(tǒng)計(jì)特性不明了或不易獲得的情況下，可令=06×1，P0= αI6(α可為一個(gè)較大的常數(shù)).鑒于單點(diǎn)定位觀測(cè)數(shù)據(jù)的特征，取第1個(gè)坐標(biāo)點(diǎn)(x0，y0，z0)為初值，即，并取 P0=10I6.

因?yàn)楸疚乃捎玫腉PS數(shù)據(jù)輸出頻率為1 Hz，所以離散化后的采樣時(shí)間為T=1.經(jīng)過上文分析與設(shè)定，濾波計(jì)算采用定常系統(tǒng)卡爾曼濾波方程［9］

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

圖2 濾波前數(shù)據(jù)分布

圖3 濾波后數(shù)據(jù)分布

通過對(duì)比，卡爾曼濾波的確能夠消除較大的數(shù)據(jù)波動(dòng)，逼近GPS所測(cè)位置的真實(shí)坐標(biāo).當(dāng)然，濾波的目的是對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理，剔除波動(dòng)較大的數(shù)據(jù)，濾波后的數(shù)據(jù)是一個(gè)較小的區(qū)域，要得到高精度的坐標(biāo)位置，需要進(jìn)一步的數(shù)據(jù)處理.

3 模糊C-均值聚類算法確定坐標(biāo)中心

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

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

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

解決上述的數(shù)學(xué)規(guī)劃問題的算法步驟如下:

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

步驟1 計(jì)算U(k)

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

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

步驟2 計(jì)算V(k+1)

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

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

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

4 結(jié)果分析

實(shí)驗(yàn)采用的GPS數(shù)據(jù)為實(shí)測(cè)單點(diǎn)靜態(tài)定位原始數(shù)據(jù).真實(shí)地理信息位置為(126.673 596°E，45.772 053°N).GPS接收機(jī)，數(shù)據(jù)輸出頻率為1 Hz，共得到觀測(cè)數(shù)據(jù)520組.

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

圖5 濾波前聚類中心

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

圖6 濾波后聚類中心

圖7為濾波前后聚類中心位置與真實(shí)坐標(biāo)的對(duì)比圖.可以直觀的看出，采用卡爾曼濾波與模糊C-均值聚類算法相結(jié)合的方法，得到的聚類中心更接近于真實(shí)的地理坐標(biāo).提高了單點(diǎn)靜態(tài)GPS定位精度.

圖7 濾波前后聚類中心與真實(shí)坐標(biāo)對(duì)比

5 結(jié)論

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

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

［1］劉娣，薄煜明，鄒衛(wèi)軍.基于時(shí)間序列的GPS誤差建模及單點(diǎn)定位精度研究［J］.兵工學(xué)報(bào)，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靜態(tài)定位精度分析［J］.全球定位系統(tǒng)，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靜態(tài)單點(diǎn)定位的濾波方法比較［J］.南京理工大學(xué)學(xué)報(bào)，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濾波的精密單點(diǎn)定位［J］.地球科學(xué)與環(huán)境學(xué)報(bào)，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.

國(guó)家自然科學(xué)基金資助項(xiàng)目(51079033).

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

張青春，zhqch0126@126.com.

(編輯 張 紅)