摘 要： 傳統(tǒng)衛(wèi)星導(dǎo)航定位中廣泛采用四面體體積最大法來選擇星座，該方法以犧牲定位精度提高星座選擇速度。本文提出了基于雅可比法計(jì)算幾何精度因子，以幾何精度因子最小為依據(jù)選擇星座的新算法。仿真結(jié)果表明，新算法既能滿足實(shí)時(shí)性的定位要求，又可以不犧牲精度。
關(guān)鍵詞： 幾何精度因子；快速星座選擇；四面體體積最大法；雅可比法
?
衛(wèi)星導(dǎo)航定位技術(shù)在現(xiàn)代測繪、航天和國防等領(lǐng)域都有廣泛應(yīng)用。國際上，很多國家都在建設(shè)自己的導(dǎo)航定位系統(tǒng)，如美國的GPS、俄羅斯的GLONASS、英國的Nexstar、歐盟的GNSS-1和GNSS-2等[1-2]。國內(nèi)現(xiàn)已建立了北斗一代導(dǎo)航定位系統(tǒng)，目前正在建設(shè)北斗二代導(dǎo)航定位系統(tǒng)。隨著導(dǎo)航定位的廣泛應(yīng)用，人們對導(dǎo)航定位的精度要求也越來越高。
?導(dǎo)航定位的精度主要與兩個(gè)因素有關(guān)[3]：(1)接收機(jī)的精度，即測距誤差；(2)相對接收機(jī)而言，衛(wèi)星的幾何構(gòu)形。由衛(wèi)星幾何位置決定的對用戶測距誤差的放大程度，稱之為幾何精度因子，簡稱GDOP(Geometric Dilution of Precision)[2]，合理地選擇導(dǎo)航衛(wèi)星組合使其GDOP最小，定位誤差也就會(huì)降到最小。目前廣泛使用的星座選擇算法是四面體體積最大法[4]，該算法不直接計(jì)算GDOP，而只計(jì)算四顆衛(wèi)星構(gòu)成的四面體體積，從而避免了矩陣求逆的復(fù)雜運(yùn)算，減小了處理器的負(fù)荷，提高了處理速度。雖然滿足星座選擇的實(shí)時(shí)性要求，但犧牲了定位精度。
當(dāng)前，處理器已取得了很大發(fā)展，處理能力極大提高，處理器對算法的限制有一定放寬，人們對定位精度有了更高的要求，所以對定位精度的改善成為當(dāng)前星座選擇算法首要指標(biāo)。本文提出了用雅可比法計(jì)算GDOP，然后根據(jù)GDOP實(shí)現(xiàn)星座選擇的新算法，并比較了新算法與傳統(tǒng)的四面體體積最大法在定位精度和處理速度兩個(gè)方面的性能指標(biāo)。通過仿真表明，新算法既能滿足實(shí)時(shí)性定位要求，又不犧牲精度。
1 GDOP計(jì)算公式
GDOP的定義式為：
其中，H是觀測矩陣。衛(wèi)星導(dǎo)航系統(tǒng)至少要有四顆衛(wèi)星來進(jìn)行定位計(jì)算,典型情況采用四星定位,此時(shí)GDOP還可表示為[5]：
2 傳統(tǒng)星座選擇算法
按照式(1)計(jì)算GDOP，并根據(jù)GDOP最小的原則選擇星座需要每次進(jìn)行矩陣的轉(zhuǎn)置、相乘及求逆運(yùn)算。上世紀(jì)70年代，由于當(dāng)時(shí)硬件平臺(tái)處理速度的限制，需要算法的運(yùn)算量小，工程應(yīng)用上采用了被稱之為四面體體積最大法的星座選擇算法。四面體體積最大法以式(2)為依據(jù)簡化計(jì)算。由式(2)可知，四面體體積與GDOP成反比，隨著V的增加，A的變化一般不大。為此，工程實(shí)現(xiàn)上用計(jì)算四面體體積V的方法代替直接計(jì)算GDOP，并以此作為星座選擇的依據(jù)。
由上述分析可以看出，最大四面體體積法實(shí)際上是以犧牲定位精度為代價(jià)來換取星座選擇速度，這種做法在硬件處理器難以滿足的情況下，也不失為一種比較好的實(shí)現(xiàn)方法。但隨著處理器的發(fā)展以及人們對精度要求的提高，需要一種能夠?qū)崟r(shí)完成的精度更高的算法。
3 新的星座選擇算法
式（4）將矩陣求逆的復(fù)雜運(yùn)算換為求對稱實(shí)矩陣的特征值。這樣，就可以用對稱實(shí)矩陣求特征值的雅可比快速算法。
雅可比法求對稱矩陣特征值的基本思想就是通過平面旋轉(zhuǎn)變換矩陣對實(shí)對稱矩陣A進(jìn)行正交變化，使A的非對角線元素趨于0，這樣A的對角線的元素趨于A的特征值。
用雅可比法求實(shí)對稱矩陣A的特征值步驟如下：
(1)令S=In，（In為單位矩陣）。
(2)在A中選取非對角線元素中絕對值最大者，設(shè)為αpa。
(3)若|αpa|<ε，則迭代過程結(jié)束，此時(shí)對角線元素αpa(i=0，1，…n-1)為A的特征值λi。否則，繼續(xù)下一步。
(4)計(jì)算平面旋轉(zhuǎn)矩陣的元素及其變換后的矩陣A1的元素。
? (5)S=S·R(p，q，θ)，轉(zhuǎn)(2）。
4 算法性能對比分析
在n階對稱矩陣中共有(n2-n)/2個(gè)非主對角元素要被消去，而每消去一個(gè)非主對角元素需要2n個(gè)元素進(jìn)行旋轉(zhuǎn)變換，對一個(gè)元素進(jìn)行旋轉(zhuǎn)變換需要2次乘法和1次加法。因此，一輪計(jì)算的時(shí)間復(fù)雜度為2n2(n-1)次乘法和n2(n-1)次加法。大量實(shí)驗(yàn)數(shù)據(jù)仿真說明，對于4階對稱矩陣采用過關(guān)雅可比算法，不超過22輪就可以收斂。圖1為采用過關(guān)雅可比算法的4階方陣的收斂輪數(shù)圖。
?
(1)運(yùn)算開銷和時(shí)間開銷
對于9顆可見衛(wèi)星選擇其中4顆的最佳組合，需要計(jì)算C94=126次GDOP。運(yùn)算開銷和時(shí)間開銷如表1所示。
?
雖然新運(yùn)算開銷和時(shí)間開銷都比較大，但是采用當(dāng)前的器件完成選星所需時(shí)間為微秒級（如TI公司的TMS320C6455 DSP實(shí)現(xiàn)需要約50μs)，能夠滿足導(dǎo)航定位中的實(shí)時(shí)性要求。
??? (2)定位精度
由于GDOP與坐標(biāo)系無關(guān)[6]，為便于說明問題, 本部分直接引用文獻(xiàn)[7]結(jié)果，選定在地心慣性坐標(biāo)系中。不失一般性，任取地面一點(diǎn)為(5 439.7，3 140.6，1 107.6)，在某一時(shí)刻可見的9 顆GPS衛(wèi)星，其前5顆的位置如表2。
從1～5號星中選4 顆計(jì)算其體積并用雅可比法計(jì)算其GDOP，結(jié)果如表3所示。由表3可知， 隨GDOP增大體積變大，若用最大四面體體積法選擇，就會(huì)選擇體積最大的(1，2，3，5)號衛(wèi)星組合，而實(shí)際上(1，2，3，4)號衛(wèi)星組合的GDOP最小，是在1～5號衛(wèi)星中選擇4顆的最佳組合。
?
最大四面體體積法選擇的(1，2，3，5)組合對測距誤差放大3.637 7倍，而新算法選擇的(1，2，3，4)組合對測距誤差放大3.330 4倍，定位精度提高了約10%。
傳統(tǒng)最大四面體體積法在選擇星座時(shí)，忽略了A的影響，所以往往不能選擇出最佳星座組合。本文提出了雅可比法計(jì)算GDOP，然后根據(jù)最小GDOP選擇最佳星座組合的算法，給出了算法流程，并基于TMS320C6455 DSP仿真實(shí)現(xiàn)，證明了此算法能滿足當(dāng)前導(dǎo)航定位的實(shí)時(shí)性要求。相對于傳統(tǒng)方法，其定位精度提高近10%。同時(shí)，該算法計(jì)算出來的(GDOP)2也可以用于定位系統(tǒng)信息融合的自主完好性監(jiān)測(RAIM)。采用雅可比法時(shí)間復(fù)雜度會(huì)隨著幾何觀測矩陣H的行數(shù)增加（選擇星座數(shù)增加）而呈3次冪增加。在定位精度要求很高時(shí)，需要選擇多顆（大于4）衛(wèi)星以提高定位精度，可以采用雅可比并行算法選擇最佳星座組合，通過多核（n核）并行處理來減少時(shí)間復(fù)雜度，其時(shí)間復(fù)雜度為將降低為雅可比法的1/n。但此方法對硬件要求高，雅可比法能基本滿足精確度和實(shí)時(shí)性要求。
參考文獻(xiàn)
[1] 王廣運(yùn)，陳增強(qiáng).GPS精密測地系統(tǒng)原理.北京：測繪工業(yè)出版社，1988.
[2] 張守信.GPS衛(wèi)星測量定位理論與應(yīng)用.長沙：國防科技大學(xué)出版社，1996.
[3] SOOBER.G.[德]著，衛(wèi)星大地測量學(xué)[M].賴錫安譯.北京：地震出版社，1998.
[4] 鄭作亞，黃珹，馮初剛，等.4顆衛(wèi)星情況的幾何優(yōu)化法修正.天文學(xué)報(bào)，2003，3（44）：311-317.
[5] 言中，丁子明.衛(wèi)星無線電導(dǎo)航[M].北京：國防工業(yè)出版社，1989.
[6] 叢麗，ABIDAT A I，談?wù)怪?衛(wèi)星導(dǎo)航幾何因子的分析和仿真.電子學(xué)報(bào)，2006，12(34)：2204-2208.
[7] 劉會(huì)杰，張乃通.基于GDOP的最優(yōu)定位星座性能研究.高技術(shù)通訊，2000(1)：43-47.