基于K均值聚類的新型選星算法

董天寶，唐 健，曾芳玲

(國(guó)防科技大學(xué)電子對(duì)抗學(xué)院，安徽 合肥 230037)

1 引言

目前，隨著各國(guó)衛(wèi)星系統(tǒng)的不斷發(fā)展與更新，天空中可利用的衛(wèi)星數(shù)量不斷增加，使得用戶對(duì)可見衛(wèi)星的可選擇性增加，為導(dǎo)航定位提供了便利，但是同時(shí)也對(duì)選星的準(zhǔn)確性和時(shí)效性提出了新的挑戰(zhàn)，也大大提高了接收機(jī)數(shù)據(jù)處理的負(fù)載能力。在利用衛(wèi)星進(jìn)行導(dǎo)航定位時(shí)，影響定位精度的因素主要有兩個(gè)：一是，接收機(jī)精度及環(huán)境因素產(chǎn)生的觀測(cè)誤差；二是，可見衛(wèi)星的空間幾何分布[1]。衛(wèi)星導(dǎo)航定位的第一個(gè)步驟就是選取空間分布較好的衛(wèi)星，只有選取的衛(wèi)星組合適當(dāng)，才能提高導(dǎo)航定位的精度。因此，研究選取空間分布較好的可見衛(wèi)星在導(dǎo)航定位方面具有很大的意義。

當(dāng)前國(guó)內(nèi)外選星的研究對(duì)象大多是針對(duì)單個(gè)衛(wèi)星系統(tǒng)，傳統(tǒng)的選星算法主要有四種[2]：最佳幾何精度因子法、最大矢端四面體體積法、最大正交投影法和綜合法。這四種選星算法都是對(duì)所有的可見衛(wèi)星進(jìn)行遍歷來計(jì)算出最佳的衛(wèi)星組合，因此它們的計(jì)算量都非常大，導(dǎo)致選星的時(shí)效性有所欠缺，所以沒有被應(yīng)用到實(shí)際的工程應(yīng)用中。隨著研究的不斷深入，針對(duì)傳統(tǒng)選星算法的不足又發(fā)展出了多種選星算法，文獻(xiàn)[3]提出的基于高度角和方位角的快速選星算法通過對(duì)不同數(shù)量的衛(wèi)星的仰角和方位角進(jìn)行分析，然后進(jìn)行選星，計(jì)算了衛(wèi)星組合的GDOP值，并研究總結(jié)了頂座衛(wèi)星和底座衛(wèi)星的選取方法；文獻(xiàn)[4]通過研究GDOP與衛(wèi)星幾何布局的關(guān)系，提出了幾何布局選星法，選星的時(shí)效性較好，但是存在GDOP值偏離較大的問題；文獻(xiàn)[5，6]在選取仰角最大和最小的衛(wèi)星的基礎(chǔ)上，通過判斷剩余可見衛(wèi)星對(duì)GDOP值的貢獻(xiàn)值進(jìn)行選星，避免了矩陣的求逆運(yùn)算，算法運(yùn)算量大幅減小，選星的時(shí)效性有所提高，但選星的精度有待進(jìn)一步提高。此外，還有模糊選星法[7]、六星選星法[8]、組合系統(tǒng)的快速選星算法[9]和基于空間均勻分區(qū)的快速旋轉(zhuǎn)分割的選星算法[10]等。這些算法或多或少都存在不足之處，有的算法過于復(fù)雜導(dǎo)致選星時(shí)效性較差，有的算法的精確性略差。比如文獻(xiàn)[3]中提到的快速選星算法在利用方位角進(jìn)行選星時(shí)，在第1顆底座衛(wèi)星方位角的基礎(chǔ)上強(qiáng)制性地加上固定的角度作為選星的標(biāo)準(zhǔn)，就會(huì)存在“扎堆”現(xiàn)象(存在多顆距離相距較近且分布相對(duì)集中的衛(wèi)星，且沒有分布在相對(duì)應(yīng)的方位角，從而只有少量衛(wèi)星分布在預(yù)定角度附近)，這就會(huì)導(dǎo)致只有少量的衛(wèi)星參與選星。

本文針對(duì)上述問題，兼顧算法的時(shí)效性和精確性，提出了一種基于K均值聚類的新型選星算法，該算法將可見衛(wèi)星的方位角進(jìn)行聚類，從每一類的衛(wèi)星中選取一顆衛(wèi)星，重點(diǎn)解決了衛(wèi)星的“扎堆”現(xiàn)象，大幅度降低了選星算法的運(yùn)算量，選星的時(shí)效性和準(zhǔn)確性都能夠滿足用戶的導(dǎo)航定位的要求。

2 基于GDOP的選星算法原理

衛(wèi)星的定位精度可以表示為用戶測(cè)量的偽距誤差的標(biāo)準(zhǔn)差與幾何精度因子GDOP值的乘積[11]，即

Δx=Δρ·GDOP

(1)

其中，Δx表示用戶定位精度的誤差的標(biāo)準(zhǔn)差；Δρ表示用戶測(cè)量的偽距誤差的標(biāo)準(zhǔn)差；GDOP表示幾何精度因子。從上式可以看出，在Δρ已知時(shí)，Δx∝Δρ。因此，選星時(shí)選取GDOP值最小的衛(wèi)星組合更有利于定位精度的提高。文獻(xiàn)[12]指出，只有當(dāng)衛(wèi)星組合的GDOP值小于6的情況下才能夠滿足用戶的定位要求。也就是說天空中的衛(wèi)星分布相對(duì)分散的情況下，定位才夠準(zhǔn)確，衛(wèi)星的仰角必須大于5°，因?yàn)槿绻l(wèi)星的仰角太小，會(huì)由于大氣層的折射等因素的影響，造成多徑效應(yīng)，導(dǎo)致測(cè)量偽距存在差異，從而影響定位精度。

衛(wèi)星導(dǎo)航系統(tǒng)GDOP的表達(dá)式為

(2)

其中，H為衛(wèi)星導(dǎo)航系統(tǒng)的觀測(cè)矩陣。

觀測(cè)矩陣H可以表示為

(3)

其中，cosα、cosβ和cosγ是用戶到衛(wèi)星連線的三個(gè)方向角的余弦值如圖1所示。

圖1 衛(wèi)星相對(duì)于用戶的分布位置

對(duì)于單系統(tǒng)而言，當(dāng)選取的衛(wèi)星數(shù)量為4顆時(shí)，GDOP還可以表示為[13，14]

(4)

3 新型選星算法

3.1 算法原理分析

K均值(K-means)聚類算法是最著名的一種聚類算法，它是一種以距離為評(píng)判標(biāo)準(zhǔn)的數(shù)據(jù)分析方法，可以根據(jù)N個(gè)數(shù)據(jù)對(duì)象D={x1，x2，…，xN}的屬性劃分為K個(gè)簇Gk(m=1，2，…，K)。其中，K

(5)

其中，Ji表示第i簇的目標(biāo)函數(shù)。從上式中可以看出，Ji的值取決于Gi的幾何特性和ck的幾何位置。對(duì)于xk和ci的歐氏距離可以表示為

(6)

則式(5)可以表示為

(7)

其中，ci為第i簇的均值向量

(8)

同時(shí)可以定義二維隸屬矩陣uik∈{0，1}。如果第k個(gè)數(shù)據(jù)對(duì)象xk屬于第i簇，則uik=1；否則，uik=0。并且，uik滿足以下條件

(9)

對(duì)于GPS衛(wèi)星系統(tǒng)，地球某一地點(diǎn)任意時(shí)刻天空中可見衛(wèi)星數(shù)量平均為十幾顆，數(shù)量較少，將其仰角作為數(shù)據(jù)對(duì)象計(jì)算速度較快，適用于K均值聚類算法。具體的選星流程分為以下幾步：

對(duì)于GPS衛(wèi)星系統(tǒng)，地球某一地點(diǎn)任意時(shí)刻天空中可見衛(wèi)星數(shù)量平均為十幾顆，數(shù)量較少，將其仰角作為數(shù)據(jù)對(duì)象計(jì)算速度較快，適用于K均值聚類算法。具體的選星流程分為以下幾步：

1) 確定選星的相關(guān)參數(shù)。根據(jù)實(shí)際的定位需求確定選星的數(shù)量，并兼顧仰角的限定值，防止仰角過小造成測(cè)量的偽距差變大。假設(shè)共需要K(K

2) 計(jì)算衛(wèi)星仰角和方位角。讀取衛(wèi)星的星歷文件，根據(jù)軌道參數(shù)計(jì)算所有衛(wèi)星的位置，并根據(jù)衛(wèi)星與用戶的位置計(jì)算出衛(wèi)星的方位角A={a1，a2，….aN}及仰角E={e1，e2，….eN}，其中N為所有GPS衛(wèi)星的數(shù)量；

3) 選取第一顆衛(wèi)星。選取仰角E大于5°的衛(wèi)星作為可見衛(wèi)星(設(shè)共有n顆可見衛(wèi)星)，并將仰角E最大的衛(wèi)星作為第一顆衛(wèi)星；

4) 利用K均值聚類算法從剩余可見衛(wèi)星中選取K-1顆衛(wèi)星。將剩余可見衛(wèi)星的方位角A組成向量集D={a1，a2，….an-1}。具體可以分為以下幾個(gè)步驟：

a) 從數(shù)據(jù)對(duì)象集D中隨機(jī)選擇K-1個(gè)樣本作為初始的K-1個(gè)聚類中心C={c1，c2，…，cK-1}；

b) 計(jì)算數(shù)據(jù)對(duì)象ai(i=1，2，…，l-1)和各個(gè)聚類中心ck(k=1，2，…，K-1)的距離d(ai，ck)，找到距離聚類中心ck最近的ai，并將其放入簇Gk，此時(shí)便將衛(wèi)星共劃分為K-1個(gè)簇Gi(i=1，2，…K-1)；

c) 對(duì)于簇G中的數(shù)據(jù)對(duì)象重新計(jì)算新的聚類中心ck(k=1，2，…，K-1)，并更新簇Gk；

d) 計(jì)算每個(gè)樣本數(shù)據(jù)到聚類中心最小距離平方和：

(10)

如果S收斂，則終止計(jì)算，并輸出簇Gk。否則，返回第二步循環(huán)計(jì)算，一般循環(huán)3～4次即可達(dá)到終止條件；

e) 從K-1個(gè)簇中分別選取一顆衛(wèi)星，最后共選出K顆衛(wèi)星；

5) 計(jì)算該衛(wèi)星組合的GDOP值。

選星結(jié)束后，將該衛(wèi)星組合的GDOP值與最佳GDOP法比較，判斷選星的準(zhǔn)確性。假設(shè)需選取K顆衛(wèi)星用戶定位，新型選星算法的流程圖如圖2所示。

圖2 新型選星算法流程圖

3.2 算法原理分析

為了使選星算法更具說服性，實(shí)驗(yàn)利用MATLAB軟件，通過讀取三個(gè)時(shí)刻的GPS廣播星歷文件進(jìn)行衛(wèi)星的位置的解算，排除仰角小于5°的衛(wèi)星后再進(jìn)行選星。仿真結(jié)果顯示，位處合肥市(31.86°N，117.27°E)的用戶在三個(gè)衛(wèi)星參考時(shí)刻分別可以接收到的衛(wèi)星數(shù)量為7顆、10顆和10顆，三個(gè)星歷參考時(shí)刻分別是2020年2月25日0時(shí)(時(shí)刻1)、2020年2月26日0時(shí)(時(shí)刻2)和2020年2月27日0時(shí)(時(shí)刻3)。如表1、表2和表3所示為三個(gè)衛(wèi)星參考時(shí)刻衛(wèi)星仰角和方位角的信息。

表1 時(shí)刻1可見衛(wèi)星的仰角及方位角

表2 時(shí)刻2可見衛(wèi)星的仰角及方位角

表3 時(shí)刻3時(shí)可見衛(wèi)星的仰角及方位角

根據(jù)上述三個(gè)時(shí)刻衛(wèi)星的方位角和仰角，利用本選星算法將可見衛(wèi)星的方位角進(jìn)行聚類，在三個(gè)時(shí)刻分別選取4顆衛(wèi)星用于導(dǎo)航定位，并利用MATLAB軟件進(jìn)行仿真，計(jì)算衛(wèi)星組合的GDOP值并記錄算法的運(yùn)行時(shí)間，如表4所示為本選星算法和最佳GDOP值法兩種選星算法的比較，如圖3～圖5所示為本選星算法的選星仿真圖。

綜合選星過程和仿真結(jié)果對(duì)本選星算法進(jìn)行性能分析，結(jié)合表4可以看出：

1) 定位精度高。時(shí)刻1兩種算法的選星編號(hào)相同，時(shí)刻2和時(shí)刻3選取的衛(wèi)星中均只有一顆選星編號(hào)不同，雖然兩種算法計(jì)算的GDOP值略有不同，但兩者差異很小。所選衛(wèi)星組合得GDOP值雖然不是最佳的，但是GDOP值的最大偏離度不超過5%，且GDOP都小于6，定位精度能夠滿足用戶的定位的需求。

3) 本算法同樣適用于多衛(wèi)星系統(tǒng)。對(duì)于單衛(wèi)星系統(tǒng)而言，可見衛(wèi)星的數(shù)量還是相對(duì)較少，衛(wèi)星的可選擇性較差。對(duì)于多衛(wèi)星系統(tǒng)而言，衛(wèi)星的可選擇性增加，K均值聚類算法的聚類對(duì)象增加，從而選星的精度相對(duì)于單系統(tǒng)會(huì)大大提高，而算法的運(yùn)算量幾乎沒有變化，可以大大減少選星時(shí)間。

圖3～圖5為三個(gè)時(shí)刻的選星仿真結(jié)果圖，圖中標(biāo)注的數(shù)字為排除仰角最大衛(wèi)星后剩余可見衛(wèi)星的PRN號(hào)，由于在利用K均值算法進(jìn)行選星時(shí)，只對(duì)衛(wèi)星的方位角進(jìn)行聚類，所以圖中只顯示了衛(wèi)星的方位角信息。選星時(shí)，選取仰角大于5°的衛(wèi)星作為可見衛(wèi)星，將可見衛(wèi)星的仰角劃分為3個(gè)簇，從每一簇中分別選出一顆仰角最低的衛(wèi)星。從這三張圖中可以看出，當(dāng)可見衛(wèi)星存在空間分布不均勻的現(xiàn)象時(shí)，通過本算法進(jìn)行選星后，衛(wèi)星分布較分散，降低了衛(wèi)星“扎堆”現(xiàn)象對(duì)選星造成的影響。

表4 兩種選星算法的比較

圖3 時(shí)刻1選星仿真圖

圖4 時(shí)刻2選星仿真圖

圖5 時(shí)刻3選星仿真圖

4 總結(jié)

本文在衛(wèi)星空間分布的基礎(chǔ)上通過對(duì)可見衛(wèi)星的方位角進(jìn)行聚類劃分，提出了一種基于K均值聚類的新型選星算法，并給出了具體的選星步驟。該算法以提供盡可能小的GDOP值的衛(wèi)星組合為原則，利用K均值聚類算法對(duì)三個(gè)時(shí)刻的可見衛(wèi)星的方位角進(jìn)行劃分，最后利用MATLAB軟件進(jìn)行仿真。仿真結(jié)果表明，該算法得到的幾何精度因子與最佳GDOP法得到的幾何精度因子相差很小，能夠滿足用戶的定位需求；該算法的運(yùn)算量大大較小，避免了傳統(tǒng)選星算法需要大量的矩陣乘法和矩陣求逆的問題，運(yùn)行時(shí)間大大減少，降低了算法的復(fù)雜度，提高了選星的時(shí)效性，所以該算法有較好的選星性能，可以快速準(zhǔn)確地選星，同時(shí)該算法適用于多衛(wèi)星系統(tǒng)選星。