陳 波，高成發(fā),管玉琦

(1.東南大學(xué) 交通學(xué)院，江蘇 南京 211189；2.黑龍江省恒信測繪有限公司，黑龍江 哈爾濱 150050)

GNSS控制網(wǎng)異步環(huán)是指由不同步觀測基線組成的閉合環(huán)，最小異步環(huán)邊數(shù)及閉合差是評價控制網(wǎng)基線向量觀測精度的重要指標(biāo)。由于人工找尋異步環(huán)十分低效，故編寫出計算機(jī)算法，自動搜索出所有最小獨立閉合環(huán)十分重要(閉合環(huán)中除去同步環(huán)即為異步環(huán))。目前，學(xué)者對此工作的研究主要有3個方向：基于迭代加深搜索的算法[1]、基于生成樹的算法和基于Delaunay三角形的搜索算法，其中第二種方法較第一種方法搜索的閉合環(huán)的完整性更好[2]，第三種方法是一種新方法，搜索速度很快，但是完整性也得不到保障[3]。

對于基于生成樹的最小閉合環(huán)搜索算法，近年來有許多學(xué)者對其進(jìn)行了研究與改進(jìn)，其大體思路都是先進(jìn)行寬度優(yōu)先搜索(或類似的算法)得到生成樹，再通過添加余枝進(jìn)行最短路徑計算的方式得到最小獨立閉合環(huán)。目前各位學(xué)者針對最小獨立異步環(huán)搜索算法所發(fā)表的論文大多精講過程中的某一部分，并且對于有些細(xì)節(jié)問題討論的較少。實際上要完成這項工作，其過程是相當(dāng)繁瑣的，初學(xué)者在閱讀大量文獻(xiàn)后也不容易對此形成完備的認(rèn)識。本文將對此方法原理及如何實現(xiàn)進(jìn)行詳細(xì)的闡述，包括生成樹算法、最短路徑搜索算法、利用生成樹及最短路徑搜索算法進(jìn)行最小獨立異步環(huán)搜索的原理及實現(xiàn)方法和同步環(huán)自動搜索方法，并以一個實例進(jìn)行驗證，以幫助初學(xué)者順利完成這些工作。

1 生成樹算法

對于一個含有n個點和m條觀測基線的GNSS網(wǎng)(不考慮重復(fù)基線)，其獨立閉合環(huán)個數(shù)為m-n+1個[4]。在閉合環(huán)搜索算法中，首先將測站視作節(jié)點，基線向量視作邊(去除方向性)，把GNSS控制網(wǎng)看作一個由點和線(邊)組成的網(wǎng)圖。生成樹算法即是在網(wǎng)圖中建立一個“樹”，該樹具有以下特點：

1)連通圖中所有結(jié)點；

2)不包含任何閉合環(huán)；

3)從圖中任意一點均可以連通到其他所有點。

把構(gòu)成該樹的邊稱為樹枝，網(wǎng)中剩余的邊為余枝，易知余枝數(shù)為m-n+1，即為獨立閉合環(huán)數(shù)。如圖1所示，在網(wǎng)圖中有一個生成樹，實線為樹枝，虛線為余枝。

圖1 生成樹示意圖

生成樹的建立有很多種方法，這里介紹寬度優(yōu)先搜索算法，其實現(xiàn)步驟如下：

1)為了使生成的樹更為簡單，首先需遍歷所有邊，記錄下各邊的兩個端點，找出出現(xiàn)次數(shù)最多的點，該節(jié)點即為樹的第一個點；

2)從樹的第一個節(jié)點開始，將與該節(jié)點相連的所有邊及這些邊的另一個端點加入到樹中；

3)從新加入的節(jié)點開始，遍歷與這些節(jié)點相連的各邊，如邊的另一個端點不在樹中，則將該邊和端點加入到樹中；

4)重復(fù)步驟3)，直到所有的點都在樹中，則得到所需要的樹。

2 最短路徑—Dijkstra算法

Dijkstra算法是計算機(jī)科學(xué)中一種重要的算法，是一種典型的單源最短路徑算法，其目的是計算從一個節(jié)點到網(wǎng)中其他所有節(jié)點的最短路徑，也是基于生成樹搜索最小獨立閉合環(huán)過程中需要反復(fù)用到的一種算法。它是由荷蘭計算機(jī)科學(xué)家Dijkstra于1959年提出的，并因此命名。其主要特點是以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止。

設(shè)有一個網(wǎng)圖G，表示G中有頂點集合V和邊集合E，每條邊有自己的長度，圖中的源點為v(即從該節(jié)點出發(fā)，計算出它到其余各節(jié)點的最短路徑)，其他點為u。把網(wǎng)圖中的頂點集合V分成兩個子集合，分別是S和U，S表示已經(jīng)求出最短路徑(從該點到v的最短路徑長度)的頂點集合，U表示其余未確定最短路徑的頂點集合，一開始S中只有一個點v。S和U中每個頂點都有一個對應(yīng)的長度，表示從v到u只經(jīng)過S中頂點的最短路徑，若只經(jīng)過S中包含的頂點，從v不能到達(dá)u，則f(u)=∞。依據(jù)最短路徑的長度遞增次序依次把U中的頂點加入到S中，過程中保持v到S中各點的最短路徑都小于v到U中任意頂點的最短路徑長，直到所有的頂點都在S中。其算法步驟為：

1)一開始，S中只有節(jié)點v，S={v}，U中包含其他所有的節(jié)點，這些節(jié)點中，與v相連的u，f(u)有數(shù)值，與v不相連的u，f(u)=∞；

2)從U中選擇一個f(k)最小的節(jié)點k，將節(jié)點k加入到S中，此時S中增加一個節(jié)點，U中減少一個節(jié)點；

3)以k為新的中間點，計算U中各節(jié)點u到v的距離，若從v經(jīng)過節(jié)點k到節(jié)點u的距離小于原先的(此路徑不經(jīng)過節(jié)點k)，則將f(u)修改為新的經(jīng)過節(jié)點k的距離；

4)重復(fù)步驟2)和3)，直到U為空集，此時得到源點v到網(wǎng)圖中各節(jié)點u的最短路徑。

3 搜索原理及具體步驟

利用生成樹和Dijkstra算法可以進(jìn)行獨立閉合環(huán)的搜索，其原理是：

1)在GNSS網(wǎng)絡(luò)中建立生成樹之后，余枝的個數(shù)等于獨立閉合環(huán)的個數(shù)；

2)每一條余枝的兩個端點通過樹(以樹為網(wǎng)圖，如圖2所示)進(jìn)行最小路徑搜索可以得到一條路徑，該路徑與余枝所在的邊組合即形成一個閉合環(huán)；

圖2 以樹為網(wǎng)圖進(jìn)行最小路徑搜索示意圖

3)由于由此得到的每一個閉合環(huán)中該余枝所在的邊是別的閉合環(huán)所沒有的，所以這些閉合環(huán)都是獨立的。

基于以上三點，可以得到網(wǎng)中所有的獨立閉合環(huán)，而為了得到最小獨立閉合環(huán)，需要在搜索閉合環(huán)的同時對樹進(jìn)行擴(kuò)充。同時需要指出的是，在此運用中，最短路徑搜索過程中的路徑的長度計算應(yīng)當(dāng)以邊的個數(shù)代替，在邊數(shù)相同時考慮路徑的長度。具體步驟如下：

1)以GNSS控制網(wǎng)中測站為點，基線為邊，建立生成樹；

2)遍歷所有的余枝，以每條余枝的一個端點為源點，以當(dāng)前的樹為網(wǎng)圖，通過Dijkstra算法計算出該端點通過樹到達(dá)該余枝的另一個端點的最短路徑，與余枝本身形成閉合環(huán)；

3)找出步驟2)中得到的閉合環(huán)中最小的一個(邊數(shù)最少，邊數(shù)相同時長度最短者)，這個閉合環(huán)為一個最小閉合環(huán)，將其相應(yīng)的余枝添加到樹上，得到新的當(dāng)前樹，余枝數(shù)減1；

4)重復(fù)步驟2)和3)，直到余枝數(shù)為0，所有的基線都在樹上，此時已經(jīng)得到所有的最小獨立閉合環(huán)。

這些獨立閉合環(huán)中含有部分同步環(huán)，故去除掉其中屬于同步環(huán)的閉合環(huán)之后，剩余的閉合環(huán)就是最小獨立異步環(huán)。若考慮重復(fù)基線的影響，應(yīng)當(dāng)在搜索出最小獨立閉合環(huán)之后，按照重復(fù)基線情況列舉出所有可能的閉合環(huán)基線組合情況，再判斷組合情況是否屬于同步環(huán)，最終得到最小獨立異步環(huán)。

4 同步環(huán)的自動搜索

對于同步環(huán)的自動搜索，目前學(xué)者對這項工作研究較少，各平差軟件的說明中也未對此進(jìn)行詳細(xì)的描述。同步環(huán)搜索是在提取出同步觀測基線的基礎(chǔ)上進(jìn)行的，本文提出一種方法，可以有效地提取出同步基線。

1)讀取各基線觀測的開始時刻和停止時刻，找到觀測開始時刻最早的基線v1，記錄下其開始時刻bt，結(jié)束時刻et。

2)遍歷所有基線，判斷其是否開始時刻早于et并且結(jié)束時刻晚于bt，若是，則該基線與v1是同步觀測基線，記這組同步觀測基線為V。

3)在遍歷時進(jìn)行判斷，若某基線屬于V，同時若其開始時刻晚于bt，則將bt修改為該基線開始時刻，若其結(jié)束時刻早于et，則將et修改為該基線結(jié)束時刻，再進(jìn)行下面的遍歷。

4)遍歷結(jié)束即V提取完成，從此時的et往后尋找開始時間最早的基線，記錄下其開始時刻bt，結(jié)束時刻et，重復(fù)上述步驟，直到所有的基線都屬于某一同步觀測基線組。

5 算 例

基于以上原理及方法，作者編寫了計算機(jī)程序進(jìn)行異步環(huán)的自動搜索，編程語言是C++，編程平臺是Visual Studio 2015。計算機(jī)程序的實現(xiàn)思路分為以下幾個部分：

1)讀取基線向量文件，本文讀入的是天寶公司的文件。ASC基線向量文件，對于最小獨立異步環(huán)搜索工作，需要讀取基線向量的起止點名、起止時刻和基線長度信息，建議以容器的方式存儲數(shù)據(jù)。

3)建立生成樹，通過不斷以樹為網(wǎng)進(jìn)行最短路徑搜索并對樹進(jìn)行擴(kuò)充的方式搜索出所有的最小獨立閉合環(huán)，具體步驟如前文所述。

4)根據(jù)重復(fù)基線情況將第3步中搜索出的閉合環(huán)，分解為不同的閉合環(huán)組合(如圖3所示)。剔除掉這些閉合環(huán)組合中屬于第2步搜索出的同步環(huán)的組合，即得到最小獨立異步環(huán)。

圖3 含重復(fù)基線閉合環(huán)分解示意圖

算例數(shù)據(jù)來源于南京市玄武湖及周邊地區(qū)短基線GNSS觀測網(wǎng)，網(wǎng)內(nèi)共有10個測站，4臺接收機(jī)分5個時段觀測，共有30條基線，基線平均長度在1 km左右。

觀測網(wǎng)如圖4所示，各時段觀測站點如表1所示，可以看出網(wǎng)中共有重復(fù)基線6條(圖4中加粗線段)，根據(jù)接收機(jī)數(shù)和觀測時段數(shù)可以計算出最小獨立閉合環(huán)數(shù)為15(基線數(shù)-重復(fù)基線數(shù)-測站數(shù)+1)，獨立基線數(shù)為15。

圖4 觀測網(wǎng)圖

時段觀測站點一G01G02G03G10二G03G10G08G09三G08G09G06G07四G09G06G05G03五G05G03G02G04

計算機(jī)程序自動搜索的同步觀測環(huán)如表2所示，共有20個同步環(huán)。本算例共有5個觀測時段，每個時段有4個測段，故同步環(huán)數(shù)，程序自動搜索結(jié)果完全正確。

表2 同步環(huán)搜索結(jié)果

計算機(jī)程序自動搜索出的最小獨立閉合環(huán)如表3所示，共有15個閉合環(huán)，觀察網(wǎng)圖可知，這些閉合環(huán)之間互相獨立，且環(huán)的長度是在滿足互相獨立的前提下最短的。

表3 最小獨立閉合環(huán)搜索結(jié)果

表3中的大部分閉合環(huán)中存在重復(fù)基線(第4個和第14個閉合環(huán)中不包含重復(fù)基線，這兩個閉合環(huán)屬于同步觀測環(huán))，根據(jù)重復(fù)基線情況得到42種基線閉合環(huán)組合。這42種基線組合中有一部分屬于表2種所列的同步觀測環(huán)，除去這些同步環(huán)，可以得到27個異步環(huán)，即為最小獨立異步環(huán)。至此，計算機(jī)自動搜索最小獨立異步環(huán)的工作全部完成。

本算例最小獨立異步環(huán)搜索結(jié)果如表4所示，表4中幾個序號位于同一單元格中表示這幾個異步環(huán)包含的測站相同但是包含的基線不同(由于重復(fù)基線的存在)。計算機(jī)程序運行結(jié)果如圖5和圖6所示，本程序為作者編寫的GNSS網(wǎng)平差軟件的一部分，圖5給出的是軟件讀入基線向量文件之后的顯示界面，圖6給出的是軟件自動搜索出最小獨立異步環(huán)并計算對應(yīng)的閉合差后的顯示結(jié)果。

表4 最小獨立異步環(huán)搜索結(jié)果

圖5 計算機(jī)軟件讀入基線向量后的顯示界面

6 結(jié) 語

本文以GNSS控制網(wǎng)為例，詳細(xì)闡述基于生成樹的控制網(wǎng)最小獨立異步環(huán)的計算機(jī)自動搜索方法，介紹整個搜索流程中涉及的各個問題，能夠幫助初學(xué)者對此項工作形成完備的認(rèn)識并自主編程實現(xiàn)。

圖6 計算機(jī)軟件搜索最小獨立異步環(huán)后顯示界面

[1] 白征東. GPS網(wǎng)中最小獨立閉合環(huán)的自動搜索[J]. 測繪科學(xué), 1994(2):18-21.

[2] 鄒進(jìn)貴, 馮晨. 控制網(wǎng)最小獨立閉合環(huán)搜索算法研究[J]. 地理空間信息, 2008, 6(6):97-99.

[3] 張西軍, 張志文. 基于索引點的GPS異步環(huán)搜索算法[J]. 測繪科學(xué), 2016, 41(6):126-129.

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

[5] 國家測繪局測繪標(biāo)準(zhǔn)化研究所.全球定位系統(tǒng)(GPS)測量規(guī)范:GB/T 18314—2009[S]．北京：中國標(biāo)準(zhǔn)出版社，2009.

[6] 徐孝凱, 王鳳祿. 數(shù)據(jù)結(jié)構(gòu)簡明教程[M]. 北京：清華大學(xué)出版社, 2005.

[7] 高成發(fā), 胡伍生. 衛(wèi)星導(dǎo)航定位原理與應(yīng)用[M]. 北京：人民交通出版社, 2005.

[8] 陶本藻. 自由網(wǎng)平差[J]. 工程勘察, 1999(3):42-45.

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

[10] 黃觀文. GPS精密單點定位和高精度GPS基線網(wǎng)平差研究及其軟件實現(xiàn)[D]. 西安：長安大學(xué), 2008.

[11] 袁衛(wèi)東. 最小生成樹的算法及其應(yīng)用[J]. 科學(xué)技術(shù)與工程, 2009, 9(15):4409-4412.

[12] 陳玉瑩. 控制網(wǎng)最小獨立閉合環(huán)的搜索算法[J]. 工程勘察, 2010, 38(5):65-69.

[13] 李征航. GPS測量與數(shù)據(jù)處理[M]. 武漢：武漢大學(xué)出版社, 2005.

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

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