基于主成分分析和Melkman算法的选星策略.pdf
《基于主成分分析和Melkman算法的选星策略.pdf》由会员分享,可在线阅读,更多相关《基于主成分分析和Melkman算法的选星策略.pdf(8页珍藏版)》请在咨信网上搜索。
1、第 40 卷 2023 年第 4 期上海航天(中英文)AEROSPACE SHANGHAI(CHINESE&ENGLISH)基于主成分分析和 Melkman算法的选星策略段吉蔚1,2,3,俞杭华1,2,刘会杰1,2,3(1.中国科学院 微小卫星创新研究院,上海 201203;2.中国科学院大学,北京 100049;3.上海科技大学 信息科学与技术学院,上海 201210)摘要:导航定位中的选星算法是一种关键技术,用于从卫星中选择合适数量和最佳几何分布的卫星以实现最佳定位精度。针对基于二维凸包算法的选星策略在三维卫星数据降维处理中忽略垂直方向高度位置信息的问题,提出了一种基于主成分分析(PCA)
2、和二维凸包 Melkman算法的选星策略。首先,通过 PCA 技术将三维卫星数据投影到新的二维坐标系,新的二维数据同时保留水平平面位置信息和垂直方向高度位置信息,旨在降低维度的同时最小化信息损失。在新坐标系下,数据经过预处理后,采用二维凸包 Melkman算法进行选星。实验结果显示:相较于直接投影到站心坐标系下的二维凸包选星算法,提出的选星算法不仅更准确地描述卫星的位置信息,使问题研究更加完备,还在保持相近仿真耗时的前提下,实现了较大的几何精度因子(GDOP)性能提升。关键词:选星策略;主成分分析(PCA);凸包;Melkman算法;几何精度因子(GDOP)中图分类号:TN 965 文献标志码
3、:A DOI:10.19328/ki.20968655.2023.04.008A Satellite Selection Strategy Based on Principal Component Analysis and Melkman AlgorithmDUAN Jiwei1,2,3,YU Hanghua1,2,LIU Huijie1,2,3(1.Innovation Academy of Microsatellites of Chinese Academy of Sciences,Shanghai 201203,China;2.University of Chinese Academy
4、of Sciences,Beijing 100049,China;3.School of Information Science and Technology,Shanghai Tech University,Shanghai 201210,China)Abstract:The satellite selection algorithm in navigation and positioning is a key technology used to select the appropriate number and optimal geometric distribution of sate
5、llites from the existing ones,aiming at achieving optimal positioning accuracy.In order to address the problem that the satellite selection strategy based on two-dimensional convex hull algorithms ignores the vertical height and position information in three-dimensional satellite data dimensionality
6、 reduction processing,a satellite selection strategy based on the principal component analysis(PCA)and two-dimensional convex hull Melkman algorithm is proposed.First,the PCA is used to project three-dimensional satellite data into a new two-dimensional coordinate system,which preserves both the hor
7、izontal plane position information and the vertical height position information,aiming at reducing dimensionality while minimizing information loss.In the new coordinate system,after preprocessing the data,the two-dimensional convex hull Melkman algorithm is used for satellite selection.The experime
8、ntal results show that,compared with the two-dimensional convex hull satellite selection algorithm directly projected into the station center coordinate system,the proposed satellite selection algorithm not only can describe the position information of satellites more accurately and thus make the pr
9、oblem research more complete,but also can achieve significant geometric dilution of precision(GDOP)performance improvement while maintaining similar simulation time.Key words:satellite selection strategy;principal component analysis(PCA);convex hull;Melkman algorithm;geometric dilution of precision(
10、GDOP)收稿日期:20230410;修回日期:20230507作者简介:段吉蔚(1998),男,硕士研究生,主要研究方向为卫星导航定位。通信作者:刘会杰(1972),男,博士,研究员,主要研究方向为信号特性分析与波形设计、阵列信号处理、自组织网络通信等。59第 40 卷 2023 年第 4 期上海航天(中英文)AEROSPACE SHANGHAI(CHINESE&ENGLISH)0引言 随 着 北 斗 卫 星 导 航 系 统(Beidou Navigation Satellite System,BDS)的全面运行,北斗、全球定位 系 统(Global Positioning System,G
11、PS)、Galileo和 Glonass 系统等 4 大全球卫星导航系统(Global Navigation Satellite System,GNSS)在轨卫星数量共计已超过百颗1。与利用单系统导航定位的方式相比,多系统融合定位可以充分利用多系统的可见卫星,实时可见卫星数量更多、分布更好,有利于提高导航定位服务的精度和可用性。然而,如果将多系统所有可见卫星均用于导航定位计算,虽然理论上定位精度最优,但计算效率降低,对应用终端的资源需求大,且严重影响导航定位的实时性。合适的选星策略可以在保证定位精度的同时,降低计算复杂度,提高导航定位的实时性,增强大多数 GNSS 应用。因此,对 GNSS 多
12、系统融合导航定位选星策略的研究具有重要的理论和实际意义。目前,选星算法的研究方向主要有以下 3 个方面。1)利用智能优化算法进行选星。文献 2 提出 了 一 种 基 于 灰 狼 优 化(Grey Wolf Optimizer,GWO)算法的快速选星方法,该算法利用自适应收敛因子和信息反馈机制,在局部寻优与全局搜索 之 间 实 现 平 衡。文 献3提 出 了 一 种 基 于 NSGA-算法的多目标快速选星方法,该算法通过不断的选择不同的遗传算子和效用函数做实验,最终选取一组合适的遗传算子和效用函数做出最优的选星决策,并且不依赖于卫星的几何位置分布,可适用于有障碍或者遮挡的复杂情况。文献 4 提出
13、了一种基于 K-means+聚类算法的快速选星算法,该方法优先选择仰角最大的一颗卫星后,对剩余卫星进行 K-means+聚类算法,然后在每个簇中选择一颗卫星,得到最终的选星组合。以上算法会导致较高的计算复杂度,增加选星所需要的时间,对实时性要求较高的应用场景可能不太适用。2)根据可见卫星的几何空间分布进行选星。文献 5 通过实验发现了可见星的空间分布规律,提出了一种基于卫星高度角和方位角进行分区筛选的快速选星算法。文献 6 根据最佳选星方案的卫星分布特性,通过利用卫星高度角和方位角信息进行区域划分,并引入代价函数筛选中仰角区域的卫星,从而得到最终的选星方案。文献 7 分析了几何精度因子(Geo
14、metric Dilution Precision,GDOP),与可见卫星布局的关系,确定各个卫星对 GDOP 的贡献值,选择贡献值大的卫星作为最终用于定位解算的卫星组合。3)利用计算几何学中的凸包算法进行选星。文献8 提出用三维凸包算法进行选星定位,虽然该算法考虑了卫星在三维空间中的分布,能够在选星过程中找到更有利于定位的卫星子集,但是三维凸包算法在计算时的复杂度较高,无法满足实时性的要求。因此为了提高实时性,文献 9 提出将三 维 卫 星 数 据 降 为 二 维,然 后 利 用 二 维 凸 包 Graham 算法进行快速选星,但是该选星算法将三维卫星数据直接投影到站心坐标系下的水平平面,但
15、可能会忽略高度方向上的影响,导致选择的卫星几何分布不够理想,从而影响定位精度。综上所述,基于二维凸包算法的选星策略在处理三维卫星数据降维时,常忽略垂直方向的高度位置信息,为解决该问题,本文提出了一种融合主成分 分 析(Principal Component Analysis,PCA)与 二维 凸 包 Melkman 算 法 的 选 星 策 略。该 策 略 利 用PCA 技术在降维过程中最大限度地减小信息损失,确保生成的二维数据不仅保留了原始三维数据的水平信息,还包含了高度方向的信息。在后续选星计算中,能更准确地描述卫星的位置信息,其对于选星策略至关重要。此外,本文采用时间复杂度较低 的 Mel
16、kman 算 法 进 行 选 星 计 算,以 提 高 选 星速度。1几何精度因子 GDOP 是卫星导航系统中一个重要指标,其代表卫星导航系统测距误差造成的接收机与空间卫星间的距离矢量放大因子10。导航卫星的定位误差的标准偏差定义如下:=GDOPUERE(1)式中:UERE为伪距测量误差。从式(1)可知,在伪距测量误差相同的情况下,导航定位精度完全由 GDOP 决定,卫星几何分布越优,GDOP 越小,导航精度越高。GDOP 的推导过程如下:H=cos1sin1cos1cos1sin1cosNcosNcosNsinNsinN(2)60第 40 卷 2023 年第 4 期段吉蔚,等:基于主成分分析和
17、 Melkman算法的选星策略式中:H为 BDS/GPS/GLONASS 中某单一卫星系统观测矩阵的前 3 列;为导航卫星的仰角;为导航卫星的方位角;N 为单一系统参与定位解算的卫星的数量。由 于 本 文 选 取 导 航 星 座 中 的 BDS、GPS 和GLONASS 这 3 个系统卫星进行选星,因此这里只考虑 BDS/GPS/GLONASS 组合导航系统的观测矩阵:G=HBDS1BDS0BDS0BDSHGPS0GPS1GPS0GPSHGLO0GLO0GLO1GLO(3)式中:1x、0 x(x为 BDS、GPS、GLONASS)分别为 k1 维的全 1、全 0 向量;k 为当前系统x用于定位
18、解算的卫星数量。则 GDOP可以表示为11GDOP=trace()GTG-1(4)GDOP数值与定位精度的关系见表 112。2基本原理 2.1主成分分析的原理PCA 方法的基本思想是通过将数据投影到最大方差的方向上,找到数据中最主要的模式和结构,并且保留尽可能多的信息13。利用 PCA 算法将三 维 卫 星 数 据 降 为 二 维 时,通 常 需 要 经 过 以 下步骤14-16:1)对原始数据进行标准化。假设有 n 个卫星数据样本,每个样本有 3 个特征(x,y,z),对于每个特征,计算其均值和标准差,然后将每个特征的值减去其均值,再除以其标准差,以使每个特征具有相同的权重,将标准化后的数据
19、整理为一个 n3的矩阵Xstd。以特征x为例,标准化的过程可以用以下公式描述:x=x-(5)式中:为特征x的均值;为特征x的标准差。2)计算标准化后的数据矩阵Xstd的协方差矩阵S。协方差矩阵可以用以下公式计算:S=1nXTstdXstd(6)3)对协方差矩阵进行特征值分解,得到特征值和特征向量。特征值和特征向量可以用以下公式计算:Svi=ivi(7)式中:vi为第i个特征向量;i为第i个特征向量对应的特征值。4)选择主成分。将特征值按降序排列,选取前 k 个最大特征值对应的特征向量作为数据降维后的新坐标系的基向量,组成新的特征向量矩阵Vk。在本文中,由于要将三维数据降为二维,因此k=2。5)
20、将原始数据投影到新的特征向量上,得到降维后的数据。新矩阵Y的每一行表示原始数据在新特征空间的坐标。Y=XstdVk(8)以上 5个步骤的流程如图 1所示。表 1GDOP与定位精度的评价关系Tab.1Evaluation relationship between the GDOP and positioning accuracyGDOP1122551010202050定位精度理想优秀良好中等一般差图 1PCA算法流程Fig.1Flowchart of the PCA algorithm61第 40 卷 2023 年第 4 期上海航天(中英文)AEROSPACE SHANGHAI(CHINESE&
21、ENGLISH)通过遵循上述 5个步骤,可以使用 PCA 算法将原始三维卫星数据有效地降至二维空间。由于该新的二维空间中的基向量是原始数据空间的线性组合,且相互正交,因此降维后的二维数据不仅保留了原始三维卫星数据的水平位置信息,还保留了高度位置信息,为后续选星计算提供了一个更精确地描述卫星位置信息的有效方式。2.2Melkman算法原理凸包的公式表达如下:在一个实数向量空间V中,对 于 给 定 集 合X,所 有 包 含X的 凸 集 的 交 集CH(X)被称为X的凸包17,即:CH(X):=X K VK(9)X的凸包CH(X)可以用X内所有点的线性组合来构造:CH(X):=j=1ntjxjxjX
22、,j=1ntj=1,tj0,1(10)二维凸包是将平面上给定的点集用一个最小的凸多边形包围的形状。对于二维凸包的计算,可以使用不同的算法来实现,包括暴力、Graham 扫描、Jarvis 步进、QuickHull 算法、Melkman 算法等18-21。其中,Melkman 算法的时间复杂度为 O(n),其比大多 数 其 他 算 法(如 Graham 扫 描 法、分 治 法 和 Andrews Monotone Chain Algorithm)的 O(nlogn)时间复杂度更低22,这意味着在处理二维凸包问题时,Melkman 算法可以更快地找到解决方案。因此本文采用 Melkman 算法进行
23、凸包计算。Melkman算法的核心思想是利用 Deque来维护凸包边界上的点。算法的具体步骤如下23:1)对输入数据进行预判断,确保至少有 3 个点。如果输入数据少于 3个点,则无法构成多边形,无需计算凸包。2)初 始 化 双 端 队 列(Double-ended Queue,Deque)。在所有点中找出具有最小 x 值的点 A,然后确定一个处理顺序,例如逆时针方向,计算剩余点与点 A 形成的向量与 y 轴负方向的夹角,再根据这些夹角将点集按从小到大的顺序进行排序,最后,将排序后的前两个点(点 A和点 B)加入 Deque。3)按顺序处理剩余的点,记当前处理的点为C。进行以下操作:检查队列的头
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 成分 分析 Melkman 算法 策略
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。