电子学报 ›› 2021, Vol. 49 ›› Issue (11): 2124-2132.DOI: 10.12263/DZXB.20201335

• 学术论文 • 上一篇    下一篇

低轨巨星座多品类业务流低复杂度分段路由方法

王宁远1,2, 刘亮1, 陈东1,2, 刘欢3, 郝时光1   

  1. 1.中国空间技术研究院通信与导航卫星总体部,北京 100094
    2.鹏城实验室,广东 深圳 518052
    3.北京空间机电研究所,北京 100094
  • 收稿日期:2020-11-26 修回日期:2021-08-24 出版日期:2021-11-25 发布日期:2021-11-25
  • 作者简介:王宁远 男,1993年生,安徽安庆人,博士研究生.2018年毕业于北京航空航天大学航空宇航科学与技术专业,同年进入中国空间技术研究院攻读博士学位,研究方向为通信卫星星座网络、星座资源管理等. E-mail:ningyuan.wang@foxmail.com
    刘 亮(通信作者) 男,1986年生,陕西西安人,博士,高级工程师.现任职于中国空间技术研究院通信与导航卫星总体部,主要研究方向为网络协议、编码理论及卫星通信. E-mail:liuliang1945@buaa.edu.cn
  • 基金资助:
    国家自然科学基金(61875230);国家重点研发计划(2020YFB1806102)

A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation

Ning-yuan WANG1,2, Liang LIU1, Dong CHEN1,2, Huan LIU3, Shi-guang HAO1   

  1. 1.Institute of Telecommunication and Navigation Satellites,China Academy of Space Technology,Beijing 100094,China
    2.Peng Cheng Laboratory,Shenzhen,Guangdong 518052,China
    3.Beijing Institute of Space Mechanics & Electricity,Beijing 100094,China
  • Received:2020-11-26 Revised:2021-08-24 Online:2021-11-25 Published:2021-11-25

摘要:

含有星间链路的低轨巨星座网络在全球多种业务回传至有限地理区域场景下会产生严重的网络拥塞问题,集中式的流量规划可以在一定程度上实现负载均衡.然而大规模网络规划的计算时间开销无法满足低轨星座的动态性要求.为此,本文提出了低复杂度的多品类流分段路由(MCFSR)算法,将星座-地面网络依据负载情况划分为两个分区,并在分区内对规划算法的精度与复杂度之间进行权衡,以达到降低算法整体复杂度的目的.同时,对于规划算法,本文提出了复杂度可调的改进的完全多项式时间近似(IFPTA)算法,用于分区内的路由规划,在计算复杂度不变的情况下使算法吞吐量更接近最优值.仿真结果证明了本文提出的MCFSR算法在巨星座场景下可以使多业务回传的总吞吐量接近最优,且时间复杂度开销远低于其他同类算法.

关键词: 低轨巨星座, 多业务回传, 负载均衡, 多品类流, 分段路由, 时间复杂度

Abstract:

The LEO mega-constellation network with inter-satellite links faces serious network congestion when multi-commodity traffics return to a limited geographical area from all over the world, which can be alleviated by centralized traffic planning. However, the computing time cost of large-scale network planning cannot meet the dynamic requirements of LEO constellation. Therefore, this paper proposes a low complexity Multi-Commodity Flow Segment Routing (MCFSR) algorithm, which divides the constellation-ground network into two zones according to different link payload, and balances between accuracy and complexity of the planning algorithm in each zone, so as to reduce the overall time complexity. Meanwhile, for the planning algorithm, this paper proposes an Improved Fully Polynomial Time Approximation (IFPTA) algorithm with adjustable precision and complexity for routing programming in each zone, which improves the planning accuracy without changing the computational complexity. Simulation results show that the total throughput of multi traffic backhaul programmed by proposed MCFSR algorithm approaches the optimal, with the time complexity far less than other similar algorithms.

Key words: LEO mega-constellation, multi-traffic backhaul, load balancing, multi-commodity flow, segment routing, time complexity

中图分类号: