基于生成樹的控制網(wǎng)最小獨(dú)立異步環(huán)搜索方法研究

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

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

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

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

1 生成樹算法

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

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

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

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

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

圖1 生成樹示意圖

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

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

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

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

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

2 最短路徑—Dijkstra算法

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

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

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

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

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

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

3 搜索原理及具體步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 算 例

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

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

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

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

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

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

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

圖4 觀測(cè)網(wǎng)圖

時(shí)段觀測(cè)站點(diǎn)一G01G02G03G10二G03G10G08G09三G08G09G06G07四G09G06G05G03五G05G03G02G04

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

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

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

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

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

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

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

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

6 結(jié) 語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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