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

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

?

基于數(shù)理統(tǒng)計方法搜索GPS所有異步環(huán)

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

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

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

關(guān)鍵詞：異步環(huán)；索引點(diǎn)；樹形搜索；基線向量

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

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

1算法基本思想

1.1　最小異步環(huán)的條件

由不同時段GPS基線組成的閉合環(huán)稱為異步環(huán)，最小異步環(huán)應(yīng)滿足以下3個條件：

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

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

3)邊數(shù)相同的閉合環(huán)，取長度最短的。

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

1.2　異步環(huán)搜索原理

基于點(diǎn)索引搜索所有GPS異步環(huán)的原理非常簡單：規(guī)則1：組成異步環(huán)至少需要3個以上端點(diǎn)；規(guī)則2：任一端點(diǎn)一定來源于兩個時段?，F(xiàn)將模型進(jìn)行簡化，從中找到搜尋異步環(huán)的基本規(guī)律，假設(shè)某個GPS控制網(wǎng)觀測了3個時段，網(wǎng)型如圖1所示。

圖1　異步環(huán)搜索基本原理

一、二時段之間重合點(diǎn)為B，二、三時段之間重合點(diǎn)為E，一、三時段之間重合點(diǎn)為D，則一、二、三時段的異步環(huán)只能從BDE之間的基線進(jìn)行判斷。首先判斷不同時段之間重合點(diǎn)是否3個以上，如果存在3個點(diǎn)，將B，D，E設(shè)為3個時段之間異步環(huán)的索引點(diǎn)，從基線數(shù)據(jù)庫中抓取基線，直接組成異步環(huán)。該算法的最大優(yōu)點(diǎn)是從點(diǎn)入手，充分發(fā)現(xiàn)基線網(wǎng)中點(diǎn)線關(guān)系，能夠無遺漏地搜索出基線網(wǎng)中的所有異步環(huán)。

1.3　點(diǎn)索引法樹形搜索異步環(huán)算法

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

第1步：選擇索引點(diǎn)。

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

表1　GPS觀測時段

3個時段之間重復(fù)點(diǎn)如表2所示。

表2　三時段之間重復(fù)點(diǎn)

第2步：樹形搜索異步環(huán)。

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

圖2　樹形搜索算法搜索異步環(huán)組成節(jié)點(diǎn)

樹枝1到達(dá)第2層次時出現(xiàn)同名重復(fù)點(diǎn)，搜索停止；

樹枝2，3，4順利到達(dá)第3層次，并且沒有出現(xiàn)同名重復(fù)點(diǎn)，搜索成功；

樹枝5在第3層次時出現(xiàn)同名點(diǎn)，搜索停止；

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

第3步：利用異步環(huán)點(diǎn)抓取基線。

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

圖3　利用樹形搜索抓取異步環(huán)基線

異步環(huán)的每條基線根據(jù)端點(diǎn)所在時段判斷，兩端點(diǎn)GPS站點(diǎn)在3個時段中均設(shè)站觀測，但是會同時出現(xiàn)在一個時段中，該時段的基線即為組成異步環(huán)的基線向量。因此3個時段中的所有異步環(huán)如下：

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時段)。

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

1.4　算法流程

基于索引點(diǎn)搜索所有GPS異步環(huán)算法流程如圖4所示。

圖4　異步環(huán)搜索流程

2算例分析

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

圖5　實例GPS控制網(wǎng)網(wǎng)型分布

對GPS控制網(wǎng)進(jìn)行完基線解算后，進(jìn)行異步環(huán)檢查。GPS網(wǎng)分6個時段進(jìn)行觀測，每時段布點(diǎn)情況如表3所示。

表3　GPS觀測點(diǎn)時段分布

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

表4　實例控制網(wǎng)異步環(huán)部分搜索結(jié)果

3結(jié)束語

本文利用數(shù)理統(tǒng)計的方法，通過基線時段間重復(fù)點(diǎn)搜索GPS異步環(huán)，能夠非?？煽勘憬莸厮阉鞯剿械漠惒江h(huán)，為衡量GPS基線質(zhì)量提供了非?？煽康谋Ｕ?。本算法原理簡潔明快，便于編程處理，可以廣泛應(yīng)用于生產(chǎn)實踐，并且在KANG、FAKU等控制網(wǎng)解算中取得了良好的效果。

多邊異步環(huán)搜索方法，只是給出了搜索方法和搜索流程，暫時沒有程序?qū)崿F(xiàn)。本文在實踐中，主要搜索了三邊異步環(huán)，沒有搜索多邊異步環(huán)，在以后的科研生產(chǎn)中將予以實踐，并希望能夠得到完善的理論模型。

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

[責(zé)任編輯：劉文霞]

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

文獻(xiàn)標(biāo)識碼：A

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