一種新的多星座接收機冷啟動可見星搜索算法

金春楊，范勝林，候 豆

（南京航空航天大學，南京211106）

一種新的多星座接收機冷啟動可見星搜索算法

金春楊，范勝林，候 豆

（南京航空航天大學，南京211106）

為改善多星座接受機冷啟動耗時過長的問題，在新的冷啟動條件下，分析多星座接收機的冷啟動過程，提升可見星搜索效率，并且為了能夠應對復雜的遮蔽情況，提出一種新的可見星搜索算法。該算法依據已搜索的可見星縮小剩余衛星的范圍，并分為4個階段，采取不同的處理方法與搜索次序。仿真實驗得出結論，在理想與遮蔽情況下，新算法均能有效縮短冷啟動耗時。

多星座；冷啟動；可見星搜索；搜索次序

0 引言

目前，各GNSS得到大力發展，在軌可用衛星的數量大增［1-2］，多星座組合定位同步發展。多星座包括美國的GPS、俄羅斯的GLONASS、歐盟的GALIEO和中國的北斗等。較之傳統的單星座定位，多星座組合定位的可用性、可靠性和精度等性能大幅提升［3-4］。但是，接收機的冷啟動耗時也隨衛星數量的增加而增加。

冷啟動時，接收機對可見星、Doppler頻移和碼相位進行三維搜索［5］。通常將Doppler頻移和碼相位的二維搜索過程稱為捕獲，接收機將在這二維空間中找到一個待檢測點達到有效峰值［6］，并開始跟蹤。已有大量文獻研究如何加快捕獲，例如采用硬件并行等方式［7-8］。而對于可見星的搜索，文獻較少［9-10］。不論是快速的捕獲，還是快速的搜索可見星，都有利于減少冷啟動耗時。

傳統的冷啟動條件是時間、用戶粗略位置、星歷、歷書皆未知。而實際情況下，時間與歷書往往是已知并可用的，但用戶粗略位置、星歷未知，仍然存在三維的不確定度，稱為新的冷啟動條件。針對新的冷啟動條件，分析多星座接收機的冷啟動過程與提升可見星搜索效率的關鍵所在，并為應對復雜的遮蔽情況，提出一種新的可見星搜索算法。若無特別說明，后文中的冷啟動均指這種新的冷啟動。

1 冷啟動過程

接收機冷啟動的目的在于兩點，一是盡快地搜索到必要數量的可見星以獲得首次定位結果，二是搜索所有可見星。單星座時，兩者的差異不大。但在多星座時，兩者的差異十分明顯，并且出于多星座接收機提高精度的初衷，后者應被更多地考慮。多星座接收機冷啟動可見星搜索的大致次序可分為以下兩種：

1）優先搜索到首次定位所需衛星，讀取星歷，首次定位，然后根據用戶位置縮小可見星的搜索范圍并搜索到剩余的所有可見星，讀取星歷，首次精確定位。

2）不依賴用戶位置，直接搜索到所有可見星，讀取星歷，首次精確定位。

接下來以首次精確定位時間（冷啟動耗時）為標準，分析比較兩種次序的優劣與各自的適用情況。讀取第一、第二數據塊的平均耗時為24s，設單次捕獲（載波頻率與碼相位）的平均耗時為T，多星座衛星總數為N，第一種次序平均搜索衛星總數為M1，第二種次序平均搜索衛星總數為M2，M2＞M1。T與接收機的相關器數量和捕獲算法有關，N與選取的星座有關，M1/N、M2/N由衛星搜索算法自身決定。由于第一種次序借助了用戶位置縮小搜索范圍，根據理想情況下可見星情況推測，M1/N大約為 0.4，M2/N的范圍為0.4～1。 這里需要說明的是，在同一時刻，接收機采用所有硬件資源只針對同一顆衛星進行捕獲的方式，而非同時對多顆衛星進行各自的捕獲，以盡可能縮短T。當然，捕獲到某顆衛星的某個頻點后，某個通道就被專門用于跟蹤此衛星的此頻點，不再參與對其他衛星的捕獲。因為這種串行的搜索方式才能夠運用已有的搜索結果輔助決定之后的搜索次序，以避免不必要的搜索，而并行的搜索方式卻使得各自的搜索結果是獨立的并且無法相互輔助?？梢娦撬阉魉惴ǖ哪康恼且o出串行搜索的最優次序。

忽略定位解算等其他耗時，由于有兩次不重疊的讀取星歷的過程，第一種次序的冷啟動耗時為：

第二種次序的冷啟動耗時為：

兩者之差為：

式（3）中，第一項24反映讀取第一、第二數據塊的耗時，第二項（M2－M1）·T（必大于0）反映搜索耗時的差異。可以看出，如果讀星歷的耗時比重越大，則越應考慮使用第二種次序。不論采用第一種還是第二種次序，為縮短冷啟動耗時，都可以采用減小T的方式。而在（M2－M1）固定的情況下，隨著T的減小，Δt將變大，也就是更可能采用第二種次序。并且如果可以設計特定的算法使得M2更加接近M1，不但減小t2，也會使得Δt變大，同樣更可能采用第二種次序。在第二種次序的基礎上，提出一種新的衛星搜索算法。因此，新算法的適用條件是：Δt＞0。

2 一種新的可見星搜索算法

文獻[9]提出了一種動態可見星搜索算法，在理想無遮蔽的情況下可有效減少冷啟動耗時。該算法引入平均可見度的概念，某顆衛星的平均可見度由自身位置與備選用戶粗略位置的集合共同決定，優先搜索平均可見度最大的衛星。該算法本身不能區分衛星不可見是由于地球遮蔽或是物體遮蔽，所以在實際有遮蔽情況下，極易退化為全星搜索。為解決這一問題，文獻[10]提出了一種魯棒動態可見星搜索算法。該算法在平均可見度的基礎上，引入遮蔽概率和置信度的概念，在一定程度上解決實際有遮蔽情況下算法退化的問題，但是并未給出詳實的遮蔽情況分析與仿真驗證。本節提出一種新的可見星搜索算法，新算法假設t和歷書由外部給定，并不再如同文獻[9]和文獻[10]中簡單地給出可見度估計準則、并按降序搜索，而是將冷啟動分為4個不同的階段。第一階段搜索初始衛星組，第二階段搜索邊緣衛星組，第三階段外延、內縮搜索，第四階段搜索剩余衛星，每個階段按照不同的準則確定搜索次序。

2.1 可見星搜索算法原理

可見星搜索算法能夠降低冷啟動耗時的實質是避免搜索理論已不可見的衛星，即縮小剩余衛星的可能范圍，算法的效率主要由搜索次序與實際情況決定。從這個角度來說，文獻[9]和文獻[10]的問題在于過度地壓縮剩余衛星的范圍，從而退化為全星搜索，新算法將快速、合理地給出剩余衛星的最小范圍。

在冷啟動過程中，某一顆衛星是否被遮蔽是無法判斷的。而文獻[9]將不可見的搜索結果全部判斷為地球遮擋，文獻[10]的算法引入遮蔽概率與置信度的概念，但是仍然不能徹底排除誤判的可能。為應對各種復雜的遮蔽情況，新算法將不再根據不可見的搜索結果對剩余衛星做剔除，只根據搜得的可見星做處理，從而排除誤判的可能。這使得算法對于遮蔽情況具有極強的魯棒性，但是同時會損失一定的效率。為彌補這部分的效率損失，也為提高整體的效率，需要設計特定的搜索次序以提升效率。

提升搜索效率的關鍵，首先在于盡快地搜索到第一顆可見星，為此設計第一階段；其次在于快速地確定最外圍的可見星，為此設計第二階段和第三階段。需要說明的是，搜索到第一顆可見星之后，按照一般的思路會搜索其附近的衛星，但這不利于縮小剩余衛星的范圍，因為越接近的衛星，對于縮小剩余衛星范圍的作用越是重疊。并且，當遮蔽情況較為復雜時，可見星附近的衛星未必是可見的。另外，由于只根據可見的搜索結果縮小剩余衛星的范圍，那么，最外圍的可見星就確定了剩余衛星的最小范圍，盡快確定最外圍的可見星，也就是盡快縮小剩余衛星的范圍。

在提出4個階段之前，先說明算法如何根據一顆可見星剔除理論不可見的衛星：設某顆可見星為SV1，另一顆待檢驗衛星為SV2，已知兩者在ECEF中瞬時坐標，選取過SV1、SV2和地心3個點的截面，如圖1所示。

圖1中，r表示地球平均半徑，h1、h2分別表示SV1、SV2距地心瞬時高度，α表示接收衛星信號最小仰角，β表示假設臨界情況時SV1與SV2的夾角，βreal表示實際夾角。β由式（4）得出：

圖1 剔除理論不可見星Fig.1 Rejecting theoretically invisible stars

如果βreal＞β，則SV2理論已不可見。

在此基礎上，提出以下4個階段。

第一階段為搜索初始衛星組，初始衛星組的構造方法基于以下前提：

1）理想情況下，以地心為體心，大致構成正四面體的4顆衛星。更準確地說，是地心到衛星連線之間的角度關系與正四面體體心到頂點連線之間的角度關系相一致的4顆衛星，其中必有一顆可見，并可以自然地推廣到正六面體、正八面體等。

2）當一顆衛星不可見時，其他衛星的（地心到衛星）向量與該衛星的夾角越小，則受遮蔽的可能性就越大。

初始衛星組的構造方法如下：首先根據前提1找到4顆衛星，它們在ECEF中的空間向量分別與以下 4 個空間向量（1，1，1）、（1，－1，－1）、（－1，1，－1）、（－1，－1，1）的夾角最小，理想無遮蔽情況下，其中必有一顆可見。需要說明的是，這組空間向量只是符合正四面體角度關系的一例，也可以選擇另一組空間向量，只要滿足角度關系即可。如果這4顆衛星都不可見，說明這4個方向受到遮蔽，根據前提2，之后選取的空間向量應盡可能避之。并結合前提1，按照以下4個空間向量（－1，－1，－1）、（－1，1，1）、（1，－ 1，－1）、（1，1，－1），搜索新的4顆衛星。如果仍都不可見，則按以下 6 個空間向量搜索（1，0，0）、（0，1，0）、（0，0，1）、（－1，0，0）、（0，－ 1，0）、（0，0，－1）。以此類推，新的空間向量盡可能避開舊的空間向量，并使用必要的數量以保證理想情況下必有一顆可見。在對這些衛星搜索的過程中，一旦有某顆星可見，則退出第一階段，進入第二階段。

第二階段為搜索邊緣衛星組，邊緣衛星組的構造方法如下：

設第一顆可見星的星下點為位置P，選取在P當地坐標系中的仰角處于一個特殊范圍內的衛星，作為邊緣衛星組。這個范圍的下限是接受衛星信號的最小仰角，上限是在最小仰角基礎上加20°（僅作舉例，可適當調整）。設仰角下限為α1，上限為α2，待檢驗衛星距地心高度為h，地球平均半徑為r，第一顆可見星為SV1，待檢驗衛星為SV2，βreal表示實際夾角，如何確定SV2是否屬于邊緣衛星組，如圖2所示。

圖2 構建邊緣衛星組Fig.2 Constructing the group of edge stars

圖2中，β1、β2分別表示SV1與SV2的夾角上限與下限，由式（5）得出：

如果β2＜βreal＜β1，則SV2進入邊緣衛星組。

第三階段為外延、內縮搜索。在第二階段的基礎上，如果某顆邊緣衛星可見，該衛星將大幅地縮小剩余衛星的范圍。為進一步縮小剩余衛星的范圍，則應沿著第一顆可見星到該衛星的連線方向，搜索更外圍的衛星，直到搜索結果為不可見，這是外延搜索；如果某顆邊緣衛星不可見，該衛星并不能縮小剩余衛星的范圍，為找到其附近的可見星，則應沿著該衛星到第一顆可見星的連線方向，搜索更內部的衛星，直到搜索結果為可見，這是內縮搜索。為盡快縮小剩余衛星范圍，顯然，應先進行外延搜索，再進行內縮搜索。

第四階段為搜索最后剩余的衛星，在此階段的搜索次序已不再重要，需要做的就是把剩余衛星逐個搜索，可按任意次序。

總之，算法在第一階段快速搜索到第一顆可見星，在第二、三階段搜索衛星并快速確定剩余衛星的合理的最小范圍，在第四階段搜索最后剩余的衛星。

2.2 算法流程

圖3 算法流程圖Fig.3 Flowchart of algorithm

圖3為算法流程圖。其中，剩余理論仍可見衛星的更新沒有直接給出，初始搜索衛星組的具體細節與升序表的構造見2.1節。圖中有所省略，內縮搜索可由外延搜索類推，沒有重復給出。

3 仿真驗證

算法由Matlab仿真驗證，共有的仿真條件如下：1）星座由GPS、GLONASS、GALIEO、BEIDOU組成，共93顆衛星；2）TLE文件由www.celestrack.com獲得，獲取時間為2016年10月12日；3）用戶位置設定為南京（32.05°N，118.78°E）； 4）仿真時間的日期設定為2016年第300天（UTC）。

在共有的仿真條件之上，分4種遮蔽情況：1）理想無遮蔽；2）低仰角遮蔽，在用戶坐標系中的仰角低于30°的衛星不可見；3）單壁遮蔽，在用戶坐標系中x坐標大于107m的衛星不可見；4）峽谷遮蔽，在用戶坐標系中x坐標在（－107m，107m）區間之外的衛星不可見。

對于每種遮蔽情況，分別選取仿真日期當天的24個整點進行仿真驗證，結果如圖4所示。

圖4 4種情況的仿真結果Fig.4 Simulation results of 4 situations

由圖4可以看出，隨著整點時間變化，算法的搜索次數存在一定范圍的波動，但保持穩定。4種遮蔽情況下，可見星數量不同，算法的效率也有所差異，但搜索次數都明顯小于衛星總數，都能夠有效減少冷啟動耗時。

4種情況下算法的性能如表1所示。

表1 4種情況下算法的性能Table 1 Algorithm performance of 4 situations

4 結論

在多星座的背景下，為盡可能地減少冷啟動耗時，并應對復雜的遮蔽情況，提出一種新的衛星搜索算法。算法只根據可見的搜索結果縮小剩余衛星的范圍，并通過第一階段快速地搜索到第一顆可見星，進而通過第二、三階段快速地獲得剩余衛星合理的最小范圍。因此，算法對于遮蔽情況具有極強的魯棒性，并保持高效。較之文獻[9]和文獻[10]，算法為多星座接收機提供更魯棒、更高效的冷啟動方案。接下來將進一步研究，在遮蔽較為嚴重的情況下，如何保持并提高可見星的搜索效率。

[1]Davis L A，Enge P K，Gao G X.Global navigation satellite systems[M].Washington D.C：National Academic Press， 2012.

[2]Hofmann-Wellenhof B，Lichtenegger H，Wasle E.GNSS-global navigation satellite systems： GPS，GLONASS，Galileo，and more[M].New York： Springer，2007.

[3]Huang B，Yao Z，Guo F，et al.STARx-a GPU based multi-system full-band real-time GNSS software receiver[C].ION GNSS，2013： 1549-1559.

[4]Joerger M，Neale J，Pervan B，et al.Measurement error models and fault-detection algorithms for multi-constellation navigation systems[C].Position Location and Navigation Symposium，2010： 927-946.

[5]Rycroft M J.Understanding GPS：principles and application[J].Journal of Atmospheric and Solar-Terrestrial Physics，1997，59（5）： 598-599.

[6]Misra P，Enge P.Global positioning system： signals，measurements，and performance[M].Lincoln： Ganga-Jamuna Press，2011.

[7]Lin D M，Tsui J B Y.Acquisition schemes for SofWare GPS receiver[C].Proceedings of International Technical Meeting of the Satellite Division of the Institute of Navigation，1985： 317-325.

[8]Van Nee D J R，Coenen A J R M.New fast GPS code-acquisition technique using FFT[J].Electronics Letters，1991，27（2）： 158-160.

[9]Chen K T.A dynamic satellite search scheduling for GNSS super constellation[C].Proceedings of the 21stInternational Technical Meeting of the Satellite Division of the Institute of Navigation ION GNSS，2008.

[10]Zhou H，Yao Z，Lu M.A robust dynamic satellitesearching algorithm for multi-constellation GNSS receivers[M].Berlin： Springer-Verlag，2015.

A New Visible?star?searching Algorithm for the Cold?start of the Multi?constellation Receiver

JIN Chun-yang，FAN Sheng-lin，HOU Dou

（Nanjing University of Aeronautics and Astronautics，Nanjing 211106）

Analyse the cold-start process of the multi-constellation receiver and the key to enhance the efficiency of the visible-star-searching to reduce the cold-start time of the multi-constellation receiver under the new cold-start condition.In addition，a new visible-star-searching algorithm is proposed to solve the complex masking problem.The algorithm narrows the scope of the remaining satellites only according to visible-stars which have been acquired，and is divided into four sections with different processing methods and searching sequences.The simulation experiment is conducted and the conclusion is that the new algorithm is captive to reduce the cold-start time whenever the situation is ideal or with the masking problem.

multi-constellation receiver； cold-start； visible-star-searching； searching sequence

P228.4

A

1674-5558（2017）01-01384

10.3969/j.issn.1674-5558.2017.06.005

2017-04-06

金春楊，男，碩士，導航、制導與控制專業，研究方向為多星座組合定位。