Optimization of Communication Path Planning Method for Low Earth Orbit Constellation Based on Dijkstra Algorithm

YIN Shuming; XUE Chengcheng; HAO Liyun; ZHANG Xinjun

doi:10.11959/j.issn.2096-8930.2024028

您当前的位置：

首页 >

文章列表页 >

Optimization of Communication Path Planning Method for Low Earth Orbit Constellation Based on Dijkstra Algorithm

Special Issue: Wireless Network Technology for Integrated Communication, Navigation, Remote Sensing, and Computing | 更新时间：2024-12-11

- Optimization of Communication Path Planning Method for Low Earth Orbit Constellation Based on Dijkstra Algorithm
- Space-Integrated-Ground Information Networks Vol. 5, Issue 3, Pages: 55-60(2024)
- 作者机构：
  
  北京空间信息传输中心，北京 102300
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-8930.2024028
  CLC： TN92
- Received：07 May 2024，
  
  Revised：2024-08-30，
  
  Published：20 September 2024
- 稿件说明：
移动端阅览
尹曙明,薛成宬,郝利云等.基于Dijkstra算法的低轨星座通信路径规划方法优化[J].天地一体化信息网络,2024,05(03):55-60.

YIN Shuming,XUE Chengcheng,HAO Liyun,et al.Optimization of Communication Path Planning Method for Low Earth Orbit Constellation Based on Dijkstra Algorithm[J].Space-Integrated-Ground Information Networks,2024,05(03):55-60.
尹曙明,薛成宬,郝利云等.基于Dijkstra算法的低轨星座通信路径规划方法优化[J].天地一体化信息网络,2024,05(03):55-60. DOI： 10.11959/j.issn.2096-8930.2024028.

YIN Shuming,XUE Chengcheng,HAO Liyun,et al.Optimization of Communication Path Planning Method for Low Earth Orbit Constellation Based on Dijkstra Algorithm[J].Space-Integrated-Ground Information Networks,2024,05(03):55-60. DOI： 10.11959/j.issn.2096-8930.2024028.

摘要

低轨星座网络的通信路径规划存在网络拓扑复杂、网络资源利用易不平衡的问题。针对这两个问题，兼顾时延、负载和任务优先级，利用有权图来表征实际的卫星以及相互之间的连通关系，基于Dijkstra算法提出一种改进的优化路径规划方法。该方法通过先分组并行后串行的设计减少规划耗时，通过实时更新拓扑和规划路径的方式解决算法难以适应低轨星座网络动态变化的问题。STK和Python的仿真结果表明，本文提出的方法动态稳定性较好、优化路径规划准确、规划耗时比原始算法平均缩短了约70%。

Abstract

Complex network topologies and unbalanced uses of network resources are key problems in communication path planning for low earth orbit constellations. To address these issues

an optimization path planning method considering time delays

loads and task priorities was proposed. In this method

weighted graphs were used to characterize interconnections between satellites

and Dijkstra algorithm was improved to implement parallel computing and adapt to dynamically changing networks of low earth orbit constellations. Results of simulations based on STK and Python demonstrated that the method presented by this paper performs well in terms of dynamic stability and plans optimization paths accurately

and the planning time decreased by about 70% on average compared with the original algorithm.

关键词

Keywords

references

吴巍 . 天地一体化信息网络发展综述 [J ] . 天地一体化信息网络 , 2020 , 1 ( 1 ): 1 - 16 .

WU W . Survey on the development of space-integrated-ground information network [J ] . Space-Integrated-Ground Information Networks , 2020 , 1 ( 1 ): 1 - 16 .

姜燕丽 , 刘晓娟 , 张雪梅 , 等 . 低轨卫星互联网发展问题研究 [J ] . 数字通信世界 , 2018 ( 8 ): 21 - 22 .

JIANG Y L , LIU X J , ZHANG X M , et al . Research on the development of LEO satellite Internet [J ] . Digital Communication World , 2018 ( 8 ): 21 - 22 .

O’CALLAGHAN J . Amazon successfully launches its prototype Kuiper satellites [J ] . New Scientist , 2023 , 260 ( 3460 ): 14 .

吴树范 , 王伟 , 温济帆 , 等 . 低轨互联网星座发展研究 [J ] . 北京航空航天大学学报 , 2024 , 50 ( 1 ): 1 - 11 .

WU S F , WANG W , WEN J F , et al . Review on development of LEO Internet constellation [J ] . Journal of Beijing University of Aeronautics and Astronautics , 2024 , 50 ( 1 ): 1 - 11 .

MARKOVITZ O , SEGAL M . Seam-aware location-based random walk routing algorithms for low orbit satellite constellations [C ] // Proceedings of the 2021 17th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob) . Piscataway : IEEE Press , 2021 : 351 - 356 .

JIANG D D , WANG F , LV Z H , et al . QoE-aware efficient content distribution scheme for satellite-terrestrial networks [J ] . IEEE Transactions on Mobile Computing , 2023 , 22 ( 1 ): 443 - 458 .

DIJKSTRA E W . A note on two problems in connexion with graphs [J ] . Numerische Mathematik , 1959 , 1 ( 1 ): 269 - 271 .

HART P E , NILSSON N J , RAPHAEL B . A formal basis for the heuristic determination of minimum cost paths [J ] . IEEE Transactions on Systems Science and Cybernetics , 1968 , 4 ( 2 ): 100 - 107 .

STENTZ A . Optimal and efficient path planning for partially-known environments [C ] // Proceedings of the 1994 IEEE International Conference on Robotics and Automation . Piscataway : IEEE Press , 1994 : 3310 - 3317 .

Views

271

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Decentralized Architecture for 6G Space-Integrated- Ground Network

Research on Architecture of Real-Time Satellite Remote Sensing System Based on Communication and Remote Sensing Integration

Satellite Communication Testing Method Based on Ground Integrated Monitoring Verification System

New Approach of Integration Space-Ground: Hotspots, Challenges, and Key Technologies of Direct-to-Smartphone

Lightweight Design Strategy and Performance Optimization of Spaceborne Core Network

Related Author

ZHANG Qianhua

SUN Junshuai

LIU Yan

ZHAO Yun

YAN Ruidong

ZHAO Chenqian

KANG Shaoli

SUN Xiaonan

Related Institution

之江实验室

Zhejiang University

State Key Laboratory of Satellite Network

Shanghai Key Laboratory of Satellite Network

Shanghai Satellite Network Research Institute Co.,Ltd.

⁰