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