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

張西軍，張志文，陳樂(lè)然，石　勇

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

?

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

張西軍1，張志文1，陳樂(lè)然1，石勇2

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

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

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

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

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

1算法基本思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1　GPS觀測(cè)時(shí)段

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

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

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

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

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

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

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

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

最后綜合，得到i,j,k三時(shí)段的所有異步環(huán)為F-G-A-F、F-G-H-F、F-H-A-F 3個(gè)異步環(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時(shí)段中，端點(diǎn)G存在于j和k時(shí)段中，如存在F-G基線向量，只能向j時(shí)段去抓取。以此類推可得到異步環(huán)F-G-A-F：F-G(j時(shí)段)、G-A(k時(shí)段)、A-F(i時(shí)段)。通過(guò)樹(shù)形圖可以發(fā)現(xiàn)異步環(huán)基線抓取的規(guī)律，如圖3所示。

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

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

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

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

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

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

1.4　算法流程

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

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

2算例分析

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

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

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

表3　GPS觀測(cè)點(diǎn)時(shí)段分布

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

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

3結(jié)束語(yǔ)

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

[12]游為,范東明,付淑娟.最短獨(dú)立閉合環(huán)與附合路線的快速搜索方法[J].測(cè)繪科學(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

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

收稿日期：2014-11-07

中圖分類號(hào)：P228

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

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