简介

随着连续运行参考站（CORS）技术的快速发展，测绘、地震等行业及城市已相继建立了CORS ，GAMIT/GLOBK 软件因其数据处理结果精度高、运算速度快、自动化处理程度高、源代码开放等特点，已成为高精度基准控制网数据处理的首选软件。在我国的GPS 测量规范中要求做重复基线与独立闭合环检核，而GAMIT/GLOBK 软件没有此功能，这对矛盾给利用该软件做高精度数据处理的生产部门带来一定困难，那么如何快速自动生成GAMIT 基线网的重复基线与独立闭合环。GAMIT 软件以同步环为单位形成全组合基线，基线数量大，若是全部基线参与组网搜索闭合条件，运算效率太低且形成的冗余闭合条件过多。结合GAMIT 基线网特点，认真分析各种基线网型结构，灵活应用图论学科中相关概念与算法，摸索出一套完整的GAMIT 基线网最简异步环搜索算法，该算法思路清晰简单，可以保证所有检核条件均被找出又相互独立，基于此算法开发的软件经过实践验证结果是完整可靠的1。

基线网的图论分析图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物间特定的联系，就得到了描述这个“图”的几何形象，换言之，图由点集和连接这些点的边集组成。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。显而易见，基线网就是 “图”，所以可利用图论相关概念与算法对基线网搜索异步环。

最小生成树：在一个连通图G 中，如果取它的全部顶点和一部分边构成一个子图g，若g 中的边将图G 中的所有点连通又不形成回路，则称子图g 是原图G 的一棵生成树；若该生成树中的所有边权值之和是生成树中的最小，则称该生成树为图的最小生成树（下文中简称最小树）。余树：在一个连通图G 中去掉一棵生成树的所有边，剩余边称为余树，余树中每一条边称为余枝，一条余枝代表着可形成一个闭合环。

最短路径：把图中两个互异顶点之间的一条路径上所经过的边权值之和定义为该路径的带权路径长度，而两个顶点之间可能不止一条路径，把带权路径长度最短的那条路径称为最短路径。

为了应用图论中的算法对基线网求解，也就是搜索最简独立闭合环，首先需要将基线网“图”化。图的实质是一个二维矩阵，所以把基线网“图”化，也就是将其“矩阵”化，而矩阵在计算机中是以数组形式存储的，所以需要将基线存储进一个二维数组。首先将基线网中的点统一编号，假设有m 个点，编号从1 到m；然后建立一个m 行、m 列的数组，并给所有数组元素赋一极大值，例如9999；最后将基线信息赋给数组，例如编号为i、j 的两个点间有基线，则数组中两个元素赋予基线权值。经过这样三步操作后，基线网就被“图”化了，灵活应用最小树、余树、最短路径的概念与算法就可以搜索最简独立闭合环了2。

最简异步环算法分析不同组网基线选择方法比较众所周知，GAMIT 是逐时段进行基线网解，同一时段的观测点两两之间均形成基线，同步环闭合差为零，所以要检核基线质量必须通过异步环闭合差，所谓异步环即组成闭合环的基线来自于不同观测时段，重复基线是最简形式的异步环。所以针对GAMIT基线网特点，可以将GPS 测量规范中提到的重复基线与独立闭合环统称为异步环，利用相同的算法搜索。要形成异步环就需要把每一时段的基线连成大网，再搜索异步环，所以如何选取组网基线是关键，下面对各种选取基线的方式进行逐一分析，取用最优方式。

（1）所有基线参与组网

即将GAMIT 解算出的所有基线参与组网，这样会有很多冗余基线，大幅度增加搜索闭合环的工作量，且形成很多多余闭合条件（同步环），图形结构复杂凌乱，计算速度慢，所以一般不采用。

（2）边界基线参与组网

即选取边界基线参与组网，在计算几何学科中将点集边界线称为凸壳，此方式忽略了同时段观测点集的内部点，会造成闭合条件的遗漏。第一时段观测了A、B、C、D、E 五个点，第二时段观测了C、D、E、F 四个点，其中实线为第一时段基线，虚线为第二时段基线，若仅选取边界基线参与组网， 则可形成三个异步环：A1B1-B1D1-D2E2-E2C2-C1A1 、C2E2-E2D2-D1C1 、C1D1-D2F2-F2C2，因为GAMIT 解算基线的同步环闭合差为零，所以三个异步环化简后实质为一个异步环C1D1-D2C2。

（3）可组成三角网的基线参与组网

即选取可组成三角网的基线参与组网，在计算几何学科中有多种算法可自动生成点集三角网，因为选取的基线冗余多，会多组成闭合条件，致使搜索的异步环相互间不完全独立，但不会遗漏闭合条件。

（4）独立基线参与组网

只选取同一时段的独立基线参与组网

即有m个点，则有m-1 条独立基线可将所有点连接起来却不形成闭合环。因为独立基线的选取方式多种多样，可以由一点跟其它点相连(星型式)、可以逐点首尾相接（接龙式）、可以选取最小树（即选取的独立基线长度相加后最短）等，不同的选取方式组成的闭合条件是不一样的，但依据GAMIT 解算的同时段基线可以相互线性表示的特点，不同的闭合条件经过化简后实质是一样的。因为选取的都是独立基线，所以组成的闭合条件是相互独立又完备的。参照第一个示例，选取不同的独立基线，组成闭合环并分析：经过对上面三个基线网的分析，可以看到无论怎样选择独立基线，形成的闭合条件只有两个，经过化简后形成的异步环或一样或相互之间可以线性标出，所以选取独立基线组成独立异步环是最佳方式，可以保证搜索到的异步环既不遗漏又不多余。

独立闭合环的自动生成算法选取独立基线组好基线网后，依照下面的算法搜索独立闭合环。

第一步：将控制点统一编号，若有m 个点，则编号为1-m；

第二步：将点编号带给GPS 网中每一条基线两端端点，并给每一条基线赋一权值，这样就可以保证每条基线凭借两端端点编号和权值唯一确定；

第三步：建立一个行列方阵，按前面讲到的方法将GPS 基线网矩阵化，对于多时段基线只将第一条基线权值赋给矩阵元素；

第四步：基于形成的矩阵查找最小树；

第五步：依据基线两端点编号和权值，在基线网中去掉组成最小树的基线，剩下的基线就是多余观测量，可称之为余树，一条多余基线代表着可形成一个闭合环。

第六步：由最小树生成一矩阵，逐一寻找所有多余基线两端点在矩阵中的最短路径，组成闭合环，将其中最小闭合环输出，并将相应多余基线放回矩阵，即给矩阵中与其端点对应的元素赋予该基线权值，同时从余树中删除；反复搜索、放回、删除，直到余树成空为止。

基线网最简异步环自动生成程序流程前面详细介绍了基线网的选取方法、独立闭合环的搜索算法、闭合环化简程序，下面对GPS 基线网最简异步环自动生成程序流程做一梳理。

第一步：逐时段选取独立基线；

第二步：将所有时段的独立基线连成大网，搜索异步环，若有m 个点，n 条基线，则可以搜索到n-m+1 个独立异步环；

第三步：对搜索的异步环进行化简；

第四步：计算化简后的异步环闭合差1。

总结针对GAMIT 软件解算的GPS 基线网的异步环自动生成算法，依照此算法开发的程序可自动快速搜索独立异步环并计算闭合差，有很好的实用价值，解决了GAMIT 软件不生成异步环而规范中又有此项要求的矛盾。本文中介绍的闭合环搜索算法简单、清晰，参照此算法也可以编写水准网、重力网闭合环生成程序3。