基于數理統計方法搜索GPS所有異步環

張西軍，張志文，陳樂然，石　勇

(1.沈陽市勘察測繪研究院，遼寧沈陽110004；2.重慶市勘測院，重慶400020)

?

基于數理統計方法搜索GPS所有異步環

張西軍1，張志文1，陳樂然1，石勇2

(1.沈陽市勘察測繪研究院，遼寧沈陽110004；2.重慶市勘測院，重慶400020)

摘要：異步環是GPS基線質量檢查的重要內容，以便于發現解算粗差，評估GPS平差的質量及精度。利用數理統計的方法，通過GPS測站點在不同時段的重復情況，利用重復點作為異步環搜索的起始點，利用樹形搜索的方法判斷重復點之間能否構成異步環，在此基礎上從GPS基線向量中抓取基線組成異步環，可以快速、無遺漏地搜索出所有的異步環。通過實例驗證，取得了很好的效果。

關鍵詞：異步環；索引點；樹形搜索；基線向量

異步環是GPS基線解算的一個重要指標，也是粗差探測的常用檢測量[1-2]。通常異步環邊數越少、環長越小，可靠性越好，若其檢驗合格，就可以保證大環的質量合格[3]。異步環的確定可以通過手工方式完成，但是工作量巨大，并且容易遺漏。現在各種GPS數據處理軟件可以搜索異步環，但是目前商業軟件難以搜索所有的異步環，難以提供可靠的基線計算質量檢查信息。并且當前軟件的GPS異步環檢查方法大多基于圖形搜索閉合環，在閉合環的基礎上判斷是否該環是異步環，計算效率比較低。

目前異步環搜索主要基于圖論的，根據GPS基線的連接結構，首先搜索出基線環，然后根據環中基線的時段數判斷該環是否為獨立環、閉合環[4-5]。計算機自動搜索閉合環的算法主要有鄰接矩陣變換方法、深度優先搜索算法、生成樹和余樹算法[6]。目前有學者在利用GPS基線構建的Delaunay三角網基礎上，判斷GPS基線的異步環[7-9]，該方法的優點是搜索速度很快，但是不能搜索所有的異步環。COSA軟件利用廣度優先遍歷的思想提出了線性的生成樹算法和最短路徑算法，并且優化了閉合環的搜索算法，使得在大規模測量網中最小獨立閉合環的搜索效率得到顯著的提高[10-11]。以上的異步環搜索算法均基于基線圖形關系，根據圖形邊、點結構，利用算法進行搜索。該方法的最大特點是難以搜索所有異步環，并且算法較為復雜[12]。本文基于數理統計的原理，提出基于索引點搜索所有GPS最小異步環的算法。首先根據GPS基線分時段的特點，判斷出哪些點可能組成異步環，然后利用這些索引點搜索是否存在基線，利用搜索出的基線組成閉合環即為異步環。本文算法原理清晰易懂，方法明確，能夠搜索出所有的異步環或者最小異步環。利用該算法編寫的GPS基線檢查程序已經運用于生產，取得了很好的效果。

1算法基本思想

1.1　最小異步環的條件

由不同時段GPS基線組成的閉合環稱為異步環，最小異步環應滿足以下3個條件：

1)閉合環的組成基線來源于不同的觀測時段；

2)閉合環中包含的邊數最少，即任一基線所在的異步環，是該基線所能組成的異步環中邊數最少的；

3)邊數相同的閉合環，取長度最短的。

滿足以上3個條件的閉合環叫做最小異步環。三邊組成的異步環是最小異步環中最簡單的，本文重點討論三邊異步環的搜索方法。

1.2　異步環搜索原理

基于點索引搜索所有GPS異步環的原理非常簡單：規則1：組成異步環至少需要3個以上端點；規則2：任一端點一定來源于兩個時段。現將模型進行簡化，從中找到搜尋異步環的基本規律，假設某個GPS控制網觀測了3個時段，網型如圖1所示。

圖1　異步環搜索基本原理

一、二時段之間重合點為B，二、三時段之間重合點為E，一、三時段之間重合點為D，則一、二、三時段的異步環只能從BDE之間的基線進行判斷。首先判斷不同時段之間重合點是否3個以上，如果存在3個點，將B，D，E設為3個時段之間異步環的索引點，從基線數據庫中抓取基線，直接組成異步環。該算法的最大優點是從點入手，充分發現基線網中點線關系，能夠無遺漏地搜索出基線網中的所有異步環。

1.3　點索引法樹形搜索異步環算法

點索引法樹形搜索異步環算法的主要步驟為：首先搜索出N個時段之間的重復點，利用重復點之間樹形分析法判斷能否構成異步環，如果能夠順利到達終點，說明該串樹枝能夠形成異步環。為了便于分析，本文討論3個時段之間異步環的搜索方法。

第1步：選擇索引點。

選取3個時段i,j,k，三時段的GPS觀測點如表1所示。

表1　GPS觀測時段

3個時段之間重復點如表2所示。

表2　三時段之間重復點

第2步：樹形搜索異步環。

本文樹形搜索算法思想來源于GIS中的四叉樹算法，即將需要搜索的內容按照一個參考根部分成幾個層次，本例中以i·j時段的F點作為根部，離根部由近及遠分成i·j,j·k,k·i 3個層次，一次搜索，如果能夠順利到達最后一個層次，一條完整的樹枝代表一個異步環，如圖2所示。

圖2　樹形搜索算法搜索異步環組成節點

樹枝1到達第2層次時出現同名重復點，搜索停止；

樹枝2，3，4順利到達第3層次，并且沒有出現同名重復點，搜索成功；

樹枝5在第3層次時出現同名點，搜索停止；

最后綜合，得到i,j,k三時段的所有異步環為F-G-A-F、F-G-H-F、F-H-A-F 3個異步環。

第3步：利用異步環點抓取基線。

在第2步搜索出所有異步環之后，需要向基線向量中抓取異步環基線。以F-G-A-F異步環為例，F-G基線端點F在i和j時段中，端點G存在于j和k時段中，如存在F-G基線向量，只能向j時段去抓取。以此類推可得到異步環F-G-A-F：F-G(j時段)、G-A(k時段)、A-F(i時段)。通過樹形圖可以發現異步環基線抓取的規律，如圖3所示。

圖3　利用樹形搜索抓取異步環基線

異步環的每條基線根據端點所在時段判斷，兩端點GPS站點在3個時段中均設站觀測，但是會同時出現在一個時段中，該時段的基線即為組成異步環的基線向量。因此3個時段中的所有異步環如下：

F-G-A-F：F-G(j時段)、G-A(k時段)、A-F(i時段)；

F-G-H-F：F-G(j時段)、G-H(k時段)、H-F(i時段)；

F-H-A-F：F-H(j時段)、H-A(k時段)、A-F(i時段)。

至此，異步環搜索完成。通過該算法的講解，自始至終沒有用到圖形的知識，完全用數理統計的方法。該方法充分利用了基線向量的特征，由點入線，搜索出GPS觀測時段間的所有異步環。

1.4　算法流程

基于索引點搜索所有GPS異步環算法流程如圖4所示。

圖4　異步環搜索流程

2算例分析

在KANP城市GPS框架網測量工程中，按照C級網技術要求布設18個站點(見圖5)，網基線平均邊長為18.97 km，覆蓋面積約1000 km2。

圖5　實例GPS控制網網型分布

對GPS控制網進行完基線解算后，進行異步環檢查。GPS網分6個時段進行觀測，每時段布點情況如表3所示。

表3　GPS觀測點時段分布

利用基于索引點搜索所有GPS異步環算法編寫的程序共檢測出122條三邊異步環，監測情況如表4所示，可以很方便地檢查出是否有超限的異步環。

表4　實例控制網異步環部分搜索結果

3結束語

本文利用數理統計的方法，通過基線時段間重復點搜索GPS異步環，能夠非?？煽勘憬莸厮阉鞯剿械漠惒江h，為衡量GPS基線質量提供了非常可靠的保障。本算法原理簡潔明快，便于編程處理，可以廣泛應用于生產實踐，并且在KANG、FAKU等控制網解算中取得了良好的效果。

多邊異步環搜索方法，只是給出了搜索方法和搜索流程，暫時沒有程序實現。本文在實踐中，主要搜索了三邊異步環，沒有搜索多邊異步環，在以后的科研生產中將予以實踐，并希望能夠得到完善的理論模型。

參考文獻：

[1]郭際明,王磊,羅年學,等.一種改進的測量控制網最小獨立環搜索算法[J].武漢大學學報(信息科學版),2011,36(5):593-595.

[2]張全德,張鵬,陳現軍,等.國家第三期一等水準網施測方案研究[J].測繪工程,2012,21(6):1-3.

[3]李振,朱鋒.利用信息矩陣算法搜索GPS網的最短獨立閉合環[J].武漢大學學報(信息科學版),2012,37(7):839-842.

[4]王金嶺,李陸勛.控制網最小閉合環信息自動生成算法[J].測繪通報,1995(1):11-15.

[5]徐昌榮,鄭俊濤,陳艷梅.基于邊界結點的GPS 控制網邊界異步環自動搜索算法[J].測繪科學,2012,37(3):31-32.

[6]王鵬磊,劉長星,張健,等.基于改進的生成樹和余樹算法控制網最小獨立閉合環搜索算法研究[J].大地測量與地球動力學,2014,34(1):113-117.

[7]徐昌榮,葛山運.基于Delaunay三角網的GPS控制網同步環和異步環自動搜索算法研究[J].大地測量與地球動力學,2011,31(1):55-58.

[8]羅三明,黃曲紅,王西寧,等.控制網最小獨立閉合環自動搜索算法研究[J].大地測量與地球動力學,2009,29(6):93-96.

[9]葉寶,陳義.基于邊集數組的最小獨立閉合環搜索算法實現[J].測繪通報,2010(12):37-39.

[10]周凌焱,劉成龍,張強,等.基于深度和廣度優先算法相結合的閉合環自動搜索方法研究[J].測繪工程,2014,23(5):24-28.

[11]馬洪磊,劉成龍,余樂義,等.一種高效的最小獨立閉合環自動搜索算法[J].測繪工程,2014,23(8):70-72.

[12]游為,范東明,付淑娟.最短獨立閉合環與附合路線的快速搜索方法[J].測繪科學,2009,34(4):139-140.

[責任編輯：劉文霞]

Searching for all GPS non-simultaneous observation loops based on mathematical statistics

ZHANG Xi-jun1,ZHANG Zhi-wen1,CHEN Le-ran1,SHI Yong2

(1.Shenyang Geotechnical Investigation & Surveying Research Institute,Shenyang 110004,China;2.Chongqing Survey Institute,Chongqing 400020,China)

Abstract：Non-simultaneous observation loop serves as an important part of GPS baseline quality checks in order to find solver gross error,and assess the quality and accuracy of GPS adjustment.In this paper,first it finds duplicate GPS observation sites from different times,then uses these points as the index points,and these index points using a tree search algorithm can search all of the GPS observation points which compose non-simultaneous observation loops.Finally,it selects the baselines from the GPS baseline vector to compose the non-simultaneous observation loop.The method used in this paper is verified with examples,and achieves good results.

Key words：non-simultaneous observation loop；point indexing；tree search；baseline vector

作者簡介：張西軍(1983-)，男，碩士研究生.

收稿日期：2014-11-07

中圖分類號：P228

文獻標識碼：A

文章編號：1006-7949(2015)12-0025-04