留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

地基伪卫星区域导航系统快速布设算法

张书雨 姚铮 陆明泉

张书雨, 姚铮, 陆明泉. 地基伪卫星区域导航系统快速布设算法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1355-1361. doi: 10.13203/j.whugis20160400
引用本文: 张书雨, 姚铮, 陆明泉. 地基伪卫星区域导航系统快速布设算法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1355-1361. doi: 10.13203/j.whugis20160400
ZHANG Shuyu, YAO Zheng, LU Mingquan. Rapid Configuration Algorithm for Ground-Based Pseudolite Navigation System[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1355-1361. doi: 10.13203/j.whugis20160400
Citation: ZHANG Shuyu, YAO Zheng, LU Mingquan. Rapid Configuration Algorithm for Ground-Based Pseudolite Navigation System[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1355-1361. doi: 10.13203/j.whugis20160400

地基伪卫星区域导航系统快速布设算法

doi: 10.13203/j.whugis20160400
基金项目: 

国家自然科学基金 61201190

详细信息

Rapid Configuration Algorithm for Ground-Based Pseudolite Navigation System

Funds: 

The National Natural Science Foundation of China 61201190

More Information
图(3)
计量
  • 文章访问数:  950
  • HTML全文浏览量:  46
  • PDF下载量:  269
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-03-07
  • 刊出日期:  2018-09-05

地基伪卫星区域导航系统快速布设算法

doi: 10.13203/j.whugis20160400
    基金项目:

    国家自然科学基金 61201190

    作者简介:

    张书雨, 硕士, 主要从事伪卫星导航研究。15801554418@139.com

    通讯作者: 姚铮, 博士, 副教授。yaozheng@tsinghua.edu.cn
  • 中图分类号: P228

摘要: 现有的几种地基导航伪卫星布局优化算法时间复杂度过高,无法满足应急场景下的伪卫星导航系统布设需求,为此提出了基于最大凸多面体准则的快速优化算法。该算法利用最大凸多面体准则,对所有可能布设伪卫星的位置进行评估,评估依据为能否对降低多用户几何精度因子加权均值产生较大贡献,评估结果将可布设伪卫星位置分为高贡献度顶星位置、高贡献度底星位置和低贡献度可剔除位置3类。评估后穷举高贡献度的顶星、底星组合,找到最优伪卫星布局。将该算法应用于常见不规则地形的伪卫星布设问题中,仿真结果表明,该算法能够得到全局最优解,且解算耗时较现有算法大幅减少,能够满足应急场景下伪卫星导航系统布设的实际应用需求。

English Abstract

张书雨, 姚铮, 陆明泉. 地基伪卫星区域导航系统快速布设算法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1355-1361. doi: 10.13203/j.whugis20160400
引用本文: 张书雨, 姚铮, 陆明泉. 地基伪卫星区域导航系统快速布设算法[J]. 武汉大学学报 ● 信息科学版, 2018, 43(9): 1355-1361. doi: 10.13203/j.whugis20160400
ZHANG Shuyu, YAO Zheng, LU Mingquan. Rapid Configuration Algorithm for Ground-Based Pseudolite Navigation System[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1355-1361. doi: 10.13203/j.whugis20160400
Citation: ZHANG Shuyu, YAO Zheng, LU Mingquan. Rapid Configuration Algorithm for Ground-Based Pseudolite Navigation System[J]. Geomatics and Information Science of Wuhan University, 2018, 43(9): 1355-1361. doi: 10.13203/j.whugis20160400
  • 全球卫星导航系统在各个领域得到了广泛和深入的应用。然而,全球卫星导航系统也有其不足之处如位于太空,易被发现和击毁;与用户的距离远,导航信号接收电平低,易被干扰或遮挡;少数卫星受影响将导致大范围的用户无法正常导航[1]。一旦发生应急情况,这些不足将对导航用户的正常使用构成威胁。通过布设地基伪卫星导航系统则可以摆脱这些问题。地基伪卫星导航系统利用布设在精确测定的地面已知位置的伪卫星网络,为覆盖区内的用户提供精确的导航信息[2]。它可以与卫星导航系统结合使用,也可以作为独立的导航系统为用户提供服务[3]。与卫星导航系统相比,它具有以下优势:基站成本低,易于大量生产和布设;位于地面,在远距离上难以发现和打击;用户接收信号电平较高,不易干扰。

    地基伪卫星导航系统的布设需要事先确定伪卫星星座[4]。在伪卫星数量有限的情况下,星座的优劣决定了系统的服务精度和抵抗干扰摧毁的能力[5]。文献[6]提出了一种单点用户快速选星准则,具体内容为:单点用户和若干可见卫星位置已知,以用户点和4颗以上卫星为端点的凸多面体体积越大,用户的几何精度因子越小,其定位精度越高。文献[7]利用文献[6]的结论,提出了在GPS与伪卫星的联合导航中针对单点用户的伪卫星最优布局搜索方法,但对于多颗伪卫星的布局问题,该方法无法得到全局最优解。文献[8]和文献[9]分别利用遗传算法和蚁群算法来解决针对多用户的多伪卫星独立导航系统布局的优化问题,但算法收敛较慢,局部搜索能力较弱,且交叉率、变异率、遗传模式等影响解算效率的重要参数的合理选择需要进行多次试验,无法直接得到最优解[10-11],不能满足实际应用需求。穷举法必然能够得到针对多用户的多伪卫星最优布局,但由于算法复杂度过高,无法满足实际应用需求,目前没有文献采用该方法解决相关问题。

    本文以多用户的几何精度因子加权均值为优化目标,提出一种基于最大凸多面体准则的优选搜索方法(optimization searching based on maximum convex-hull,OSMC)。该方法能够得到全局最优解,无须通过多次试验来确定重要参数,算法复杂度较低,能够满足实际应用需求。

    • 地基伪卫星导航系统布局优化需要考虑整个服务区域内所有用户可能出现的位置的精度因子(dilution of precision, DOP)值[12],要求能通过优化伪卫星布局使得服务区内的整体DOP加权平均值最小。在某确定服务区内进行伪卫星布局优化,需要事先确定该服务区内各用户点的权重,用户在某小区域的活动频度越高,该小区域的权重值就越高。

    • 对于任意形状的服务区,要进行布局优化计算,需要先网格化服务区,以建立数字模型。将伪卫星可布设区域划分为N个网格,用户可活动区域划分为M个网格,这M个用户可活动位置点的权重系数构成一个M维向量,可用伪卫星数量记为K,则输入条件为:

      $$ \left\{ \begin{array}{l} {S_u} = \left\{ {{\mathit{\boldsymbol{u}}_1},{\mathit{\boldsymbol{u}}_2} \cdots {\mathit{\boldsymbol{u}}_M}} \right\}\\ {S_s} = \left\{ {{\mathit{\boldsymbol{s}}_1},{\mathit{\boldsymbol{s}}_2} \cdots {\mathit{\boldsymbol{s}}_N}} \right\}\\ {\mathit{\boldsymbol{w}}_u} = {\left[ {{w_1}{w_2} \cdots {w_M}} \right]^{\rm{T}}} \end{array} \right. $$ (1)

      式中,Su是用户位置点位集合,含有M个用户可活动位置的三维坐标:

      $$ {\mathit{\boldsymbol{u}}_i} = {\left[ {{x_{{\mathit{\boldsymbol{u}}_i}}} \ {y_{{\mathit{\boldsymbol{u}}_i}}} \ {z_{{\mathit{\boldsymbol{u}}_i}}}} \right]^{\rm{T}}},i = 1,2 \cdots M $$ (2)

      Ss是可布设伪卫星位置点位集合,含有N个伪卫星可布设位置的三维坐标:

      $$ {\mathit{\boldsymbol{s}}_j} = {\left[ {{x_{{\mathit{\boldsymbol{s}}_j}}} \ {y_{{\mathit{\boldsymbol{s}}_j}}} \ {z_{{\mathit{\boldsymbol{s}}_j}}}} \right]^{\rm{T}}},j = 1,2 \cdots N $$ (3)

      wu为用户位置权重向量,各用户活动位置的重要程度由该向量确定,满足:

      $$ \sum {{w_i}} = 1,i = 1,2 \cdots M $$ (4)

      优化目标为最小化服务区内的多用户DOP加权均值,即:

      $$ {D_{{\rm{measure}}}} = \sum\limits_{m = 1}^M {{w_m} \cdot D\left( {{\mathit{\boldsymbol{C}}_s}} \right)} $$ (5)

      式中,Dmeasure为服务区内的多用户DOP加权均值;CsK×3的矩阵,表示含K颗伪卫星的星座,其行向量为K个不同的Su的元素;D(Cs)为第m个用户位置在某Cs星座下的精度因子。精度因子共有5种,分别为水平精度因子(horizontal dilution of precision, HDOP)H、垂直精度因子(vertical dilution of precision, VDOP)V、空间精度因子(position dilution of precision, PDOP)P、时间精度因子(time dilution of precision, TDOP)T以及几何精度因子(geometric dilu-tion precision, GDOP)G,相应的计算公式为:

      $$ \left\{ \begin{array}{l} H = \sqrt {{h_{11}} + {h_{22}}} \\ V = \sqrt {{h_{33}}} \\ P = \sqrt {{h_{11}} + {h_{22}} + {h_{33}}} \\ T = \sqrt {{h_{44}}} \\ G = \sqrt {{h_{11}} + {h_{22}} + {h_{33}} + {h_{44}}} \end{array} \right. $$ (6)

      式中,hii为站心坐标系中的权系数阵H的对角元素:

      $$ \mathit{\boldsymbol{H}} = {\left( {{\mathit{\boldsymbol{G}}^{\rm{T}}}\mathit{\boldsymbol{G}}} \right)^{ - 1}} $$ (7)
      $$ \mathit{\boldsymbol{G}} = \left[ {\begin{array}{*{20}{c}} { - \cos \theta _n^1\sin \alpha _n^1}&{ - \cos \theta _n^1\cos \alpha _n^1}&{ - \sin \theta _n^1}&1\\ { - \cos \theta _n^2\sin \alpha _n^2}&{ - \cos \theta _n^2\cos \alpha _n^2}&{ - \sin \theta _n^2}&1\\ \vdots &{}&{}& \vdots \\ { - \cos \theta _n^K\sin \alpha _n^K}&{ - \cos \theta _n^K\cos \alpha _n^K}&{ - \sin \theta _n^K}&1 \end{array}} \right] $$ (8)

      式中,αnKθnK分别为用户n对于某伪卫星分布中K颗伪卫星的方位角和俯仰角。

    • 目前能够对独立地基伪卫星导航系统布局进行优化的只有穷举算法和遗传算法。穷举法通过穷举所有可能的分布来找出使加权DOP最优的分布Cs。由式(1)~(8)可知,穷举法的时间复杂度为O(K×M×CNK)。在实际问题中,可用伪卫星数量K一般大于5小于10,用户可活动位置M和伪卫星可布设位置N值一般相等,数值为几百个或上千个。在应急场景伪卫星快速布设的问题中,穷举算法因消耗时间过长而无法满足实际应用需求。

      遗传算法能够快速得到良好的解,但对于任何一个具体的伪卫星布局问题,调整遗传算法的关键参数都会对解算结果的收敛效率产生较大的影响[13]。这些参数包括种群规模、编码长度、交叉概率、变异概率、中止条件等。如果初始种群数量过多,算法会占用大量系统资源;如果初始种群数量过少,算法很可能在编码过的遗传算法中忽略掉最优解。每个染色体的编码长度也影响到遗传算法的效率,过长则限制了变异的多样性,过短会降低变异的效率。太大的变异率会导致丢失最优解,而过小的变异率会导致算法过早地收敛于局部最优点。对于这些参数的选择,目前还没有实用的指导性结论,只能在具体的布局问题上,通过经验来选择较合适的参数。而在应急场景下的伪卫星布设问题里,不具备通过大量测试来积累经验的条件。

    • 由于伪卫星导航系统快速布设问题的初始条件具有随机性和即时性,网内可用伪卫星数量K和用户可活动位置数量M这两个参数一旦确定就需要始终使用,要降低算法复杂度,应当设法减小伪卫星可布设位置的选择范围N。值得注意的是,在卫星导航领域里,用户在选星时也并不是穷举当前可见卫星的所有组合,而是根据最大凸多面体准则,在确定1~2颗位于天顶的顶星后,将俯仰角较低且均匀围绕在用户四周的底星选择出来,被选出的卫星和用户位置点所构成的多面体体积越大,用户的DOP值就越小。根据最大凸多面体准则,对于让用户获得较小的DOP值,贡献大的卫星一般位于用户正上方或者俯仰角极低且均匀分布于四周,其他区域的卫星对于用户得到好的DOP值的贡献则很小。

      在实际应用场景中,需要布设伪卫星导航系统的地形虽然形状不规则,但绝大多数具有近似几何中心。量产导航伪卫星的架设高度一般为定值。那么对于服务区内某用户可活动位置而言,水平距离越远的伪卫星,仰角越小,反之亦然。因此,对于某用户可活动位置而言,对降低其DOP值贡献较大的伪卫星,一般为布设在近处的伪卫星和布设于服务区边缘地带的伪卫星,而布设在其他区域的大量伪卫星则很少出现在该用户的最大凸多面体上。因此,本文的思路是先将这些对帮助用户获得较小DOP值贡献小的伪卫星剔除,以减小算法复杂度O(K×M×CNK)中的N,从而降低计算量。

    • 根据输入条件(1),遍历M个用户可活动位置,利用最大凸多面体准则,对可布设伪卫星位置进行顶星、底星适用度评估。具体方法为:对于位置坐标为ui=[xui  yui  zui]T的用户i和位置坐标为sj=[xsj  ysj  zsj]T的可布设伪卫星位置j,计算相应的顶星适用度值A(i, j):

      $$ A\left( {i,j} \right) = \arctan \left( {\frac{{{z_{{\mathit{\boldsymbol{s}}_j}}} - {z_{{\mathit{\boldsymbol{u}}_i}}}}}{{\sqrt {{{\left( {{x_{{\mathit{\boldsymbol{s}}_j}}} - {x_{{\mathit{\boldsymbol{u}}_i}}}} \right)}^2} + {{\left( {{y_{{\mathit{\boldsymbol{s}}_j}}} - {y_{{\mathit{\boldsymbol{u}}_i}}}} \right)}^2}} }}} \right) $$ (9)

      A(i, j)与用户到伪卫星的仰角成正比。则对于所有用户可活动位置,伪卫星可布设位置j的顶星总适应度U(j)为:

      $$ U\left( j \right) = \sum\limits_{i = 1}^M {A\left( {i,j} \right)} $$ (10)

      顶星适应度最大的前l个伪卫星可布设位置,构成参与最优分布搜索的顶星集合Sup; 而总适应度排名在l之后的则属于低贡献度可剔除位置, 不需要参与最优化搜索。

      l过大会降低搜索效率,过小则可能漏掉最优分布,大量经验表明,在确保不会漏掉最优分布的前提下,顶星一般位于服务区中部1/3的范围内,即9%的面积内,故l取0.1N是合适的。

    • 对用户i而言,底星适用度值取决于伪卫星j是否位于最大凸包(maximum convex hull,MCH)上,即对于uisj,相应的底星适用度值B(i, j)为:

      $$ B\left( {i,j} \right) = \left\{ \begin{array}{l} 1,{\mathit{\boldsymbol{s}}_j} \in {S_{{\rm{MCH}}}}\\ 0,其他 \end{array} \right. $$ (11)

      式中,SMCH为在Ss上以ui为中心的MCH。则伪卫星位置j的底星总适应度D(j)为:

      $$ D\left( j \right) = \sum\limits_{i = 1}^M {B\left( {i,j} \right)} $$ (12)

      选择D(j)最大的前p个伪卫星可布设位置,构成参与最优分布搜索的底星集合Sdown。而底星适应度排名在p之后的则属于低贡献度可剔除位置, 不需要参与最优化搜索。

      p过大则降低搜索效率,过小则可能漏掉最优分布。由于服务区边缘的位置能获得更低的仰角,故底星数量一般不大于服务区边缘网点数量。总网点数量为N时,边缘网点数量为$\left\lfloor {2\sqrt N } \right\rfloor $,即p可取$\left\lfloor {2\sqrt N } \right\rfloor $。

      但在一般情况下,并不需要遍历每个用户位置求解D(j)。可以证明,在地基伪卫星布设问题中,如果伪卫星高度均相同,以任意用户点为中点找到的MCH均相同,且就是Ss水平投影下的MCH。那么,构成参与最优分布搜索的底星集合Sdown为:

      $$ {S_{{\rm{down}}}} = {\rm{MCH}}\left( {{S_s}} \right) $$ (13)

      其中,MCH(Ss)为在一个点集Ss中寻找到的MCH,目前有很多成熟的高效算法,如分治法[14]、格莱姆扫描法[15]等。

    • 经过上面的步骤,得到优选后的伪卫星可布设位置集合SdownSup,遍历集合中由任意K个不同元素构成的子集Csi,计算多用户几何精度因子加权均值:

      $$ D_{{\rm{measure}}}^i = \sum\limits_{m = 1}^M {{w_m} \cdot {D_m}\left( {\mathit{\boldsymbol{C}}_m^i} \right)} $$ (14)

      使Dmeasurei最小的Csi,即是所求的最优分布。

    • 仿真初始条件设置为:伪卫星架设高度10 m;各用户位置权重相等;可用组网伪卫星数量为4;可布设伪卫星位置范围为尺寸3 km左右的不规则图形,用户可活动范围无附加限制,即与伪卫星可布设范围相同。根据伪卫星高度与服务区尺寸比例,将服务区设置为包含44个伪卫星可布设位置、有近似几何中心的不规则地形,则仿真条件为:

      $$ \left\{ \begin{array}{l} M = N = 44\\ {z_{{\mathit{\boldsymbol{u}}_i}}} = {z_{{\mathit{\boldsymbol{s}}_j}}} = 0.01\left( {i = 1,2 \cdots M;j = 1,2 \cdots N} \right)\\ K = 4\\ {\mathit{\boldsymbol{w}}_u} = {\left[ {\frac{1}{{44}}\frac{1}{{44}} \cdots \frac{1}{{44}}} \right]^{\rm{T}}} \end{array} \right. $$ (15)

      图 1给出了初始条件下的伪卫星可布设位置水平分布和穷举法、OSMC法及遗传算法的最优搜索结果及相应的多用户加权DOP均值。图 1中,纵、横坐标为网格点编号。

      图  1  穷举法、OSMC法及遗传算法最优搜索结果

      Figure 1.  Optimal Search Results of Exhaustion, OSMC and Genetic Algorithm

      图 1所示,OSMC法与常规穷举法的解算结果完全一致,而遗传算法的解算结果与穷举法略有偏差,并未达到最优,证实了OSMC法解算结果的有效性。值得注意的是,由于本文提出的算法在评估可布设伪卫星位置时,按照文中提出的量化指标,将服务区位置分为3类:高贡献度顶星可选位置、高贡献度底星可选位置和低贡献度可剔除位置。那么,OSMC算法的主要实用范围为:在有近似几何中心的服务区内搜索最优伪卫星分布。对于一些不常见的极度不规则地形,如月牙形、Z字型等,无法分辨出近似的中心区域和边缘区域,本文提出的快速算法并不能确保得到最优解。工程上的几个实例也支撑这一结论。然而在实际应用中,绝大多数实际待布设环境均为有近似中心区域的不规则地形,故本文提出的快速算法在极度不规则地形上的不适用并未降低算法的实用价值。

    • 由于无法预先确定某初始条件下最优分布的多用户几何精度因子加权均值,遗传算法无法以优化目标达到某数值为终止条件,必须设置遗传代数,而其时间复杂度受人为设置的遗传代数的直接影响,故遗传算法的时间复杂度不具备比较价值。本文仅比较穷举法与OSMC法的时间复杂度。

      根据上文描述的OSMC法搜索流程,分析可得OSMC法的时间复杂度约为$O\left( {K \times M \times C_{\sqrt N }^{K - 1}} \right)$,优于常规的穷举法时间复杂度O(K×M×CNK),而且随着可用组网伪卫星数量K、用户活动范围M或者可布设伪卫星位置范围N的增加,OSMC法在时间复杂度上的优势将会越来越大。实际应用中,伪卫星可布设范围和用户可活动范围一般相同,下文将在用户活动范围及可布设伪卫星位置范围相同的条件下给出仿真结果。

      穷举法与OSMC法的解算时间主要用于计算特定用户在特定伪卫星分布下的几何精度因子。设可用组网伪卫星数量为4,伪卫星可布设位置范围N由80逐渐增加至1 600,比较20次DOP计算量,每次N增加80,用户可活动范围与伪卫星可布设范围一致。那么,仿真条件为:

      $$ \left\{ \begin{array}{l} K = 4\\ M\left( i \right) = 80 \times i,i = 1,2 \cdots 20\\ N\left( i \right) = M\left( i \right),i = 1,2 \cdots 20 \end{array} \right. $$ (16)

      穷举法和OSMC法需要计算单用户DOP值的次数如图 2所示。

      图  2  穷举法与OSMC法计算复杂度随服务区变化图

      Figure 2.  Algorithm Complexity of Exhaustion and OSMC Versus Service Area

      图 2中穷举法与OSMC法的DOP值计算量绝对数值相差过大,故本文对绝对数值取对数以便于观察比较。由图 2可知,OSMC法在计算量上要远小于传统的穷举法,而且随着伪卫星可布设位置范围的增加,OSMC法的计算效率优势将越来越明显,当伪卫星可布设位置数量由80逐步增加至1 600时,OSMC法的计算量由穷举法计算量的万分之一降低到千万分之一。

      假设伪卫星可布设位置N与用户可活动位置M始终等于400,可用组网伪卫星数量K由4到9逐渐增加,即仿真条件为:

      $$ \left\{ \begin{array}{l} K\left( i \right) = 3 + i,i = 1,2 \cdots 6\\ M = 400\\ N = M \end{array} \right. $$ (17)

      穷举法和OSMC法需要计算单用户DOP值的次数如图 3所示。图 3中,由于二者绝对数量相差过大,取对数以便于比较。可以看出,随着组网伪卫星数量K的增加,穷举法的计算量增加速度远高于评估穷举法。当组网伪卫星数量为9时,穷举法的计算量为OSMC法的1 012倍之多。

      图  3  穷举法与OSMC法计算复杂度随伪卫星变化图

      Figure 3.  Algorithm Complexity of Exhaustion and OSMC Versus Pseudolites

      在一次演习算例中,同样的初始条件和计算机配置,穷举法耗时15 min 20 s,OSMC法与穷举法得到了同样的最优分布结果,耗时2.7 s,满足了任务要求;而遗传算法耗时20.4 s得到解算结果,但未能得到最优分布。这一算例也验证了本文算法的有效性和实用性。

    • 应急场景下伪卫星导航系统快速布设具有重要意义。现有的伪卫星布局优化方法算法复杂度过高,成为限制应急场景下伪卫星导航系统快速布设的瓶颈。本文提出了一种快速优选搜索方法,利用目前全球卫星导航系统(global navigation satellite system,GNSS)用户选星中普遍使用的最大凸多面体准则对导航伪卫星进行评估,按照评估结果对可布设伪卫星位置进行优选,降低了最优布局搜索空间,从而缩短了最优布局的解算时间。仿真结果表明,对于实际应用中绝大部分有近似几何中心的服务区地形,该方法能够很好地适用,准确得到最优分布,且与现有算法相比,极大缩短了伪卫星导航系统最优布局的解算时间,解决了应急场景下伪卫星导航系统快速布设的瓶颈问题。

      随着伪卫星制造工艺的不断发展,地基伪卫星导航将在实践应用中占据越来越重要的地位,如何在GPS/伪卫星联合导航问题中搜索最优分布, 如何选择出具有一定抗毁性的伪卫星星座,将是下一步的研究方向。

参考文献 (15)

目录

    /

    返回文章
    返回