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

doi:10.12263/DZXB.20201335

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

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

王宁远¹^,², 刘亮¹, 陈东¹^,², 刘欢³, 郝时光¹

^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 WANG¹^,², Liang LIU¹, Dong CHEN¹^,², Huan LIU³, Shi-guang HAO¹

^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

摘要/Abstract

摘要：

含有星间链路的低轨巨星座网络在全球多种业务回传至有限地理区域场景下会产生严重的网络拥塞问题，集中式的流量规划可以在一定程度上实现负载均衡.然而大规模网络规划的计算时间开销无法满足低轨星座的动态性要求.为此，本文提出了低复杂度的多品类流分段路由（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

中图分类号:

TN915.41

王宁远, 刘亮, 陈东, 刘欢, 郝时光. 低轨巨星座多品类业务流低复杂度分段路由方法[J]. 电子学报, 2021, 49(11): 2124-2132.

Ning-yuan WANG, Liang LIU, Dong CHEN, Huan LIU, Shi-guang HAO. A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation[J]. Acta Electronica Sinica, 2021, 49(11): 2124-2132.

图/表 7

图1 低轨星座多点回传模型

图2 基于多品类流的分段路由（MCFSR）算法

表 1 星座参数

参数	数值
轨道面数	20	24	28	32
每轨卫星数	20	24	28	32
轨道倾角	90°
相位因子	0
星间链路带宽（Gbps）	$C I S L = 1$
星地链路带宽（Gbps）	$C U = C D = 4$

表 1 星座参数

参数	数值
轨道面数	20	24	28	32
每轨卫星数	20	24	28	32
轨道倾角	90°
相位因子	0
星间链路带宽（Gbps）	$C I S L = 1$
星地链路带宽（Gbps）	$C U = C D = 4$

图3 全球业务分部及接收站分布

图4 不同地面站分布下的算法最大容量对比

图5 不同算法的时间复杂度对比

图6 重负载区大小与位置对吞吐量的影响

参考文献 19

1	Di B, Song L, Li Y, et al. Ultra-dense LEO: Integration of satellite access networks into 5G and beyond[J]. IEEE Wireless Communications, 2019, 26(2): 62 - 69.
2	宋海丰.国外新兴低轨通信星座发展态势分析[J].国际太空,2018,(5):17 - 22.
	Song Hai-feng. Analysis on situation of foreign emerging LEO communication satellite constellations[J]. Space International, 2018,(5): 17 - 22.(in Chinese)
3	Liu J, Shi Y, Fadlullah Z M, et al. Space-air-ground integrated network: A survey[J]. IEEE Communications Surveys & Tutorials, 2018, 20(4): 2714 - 2741.
4	Zhang N, Zhang S, Yang P, et al. Software defined space-air-ground integrated vehicular networks: Challenges and solutions[J]. IEEE Communications Magazine, 2017, 55(7): 101 - 109.
5	Albulet M. Spacex non-geostationary satellite system: Technical information to supplement schedules-Attachment to fcc application sat-loa-20161115-00118[R]. Federal Commun Commission, Washington DC, USA, Tech Rep SAT-LOA-20161115-00118, 2016.
6	Del Portillo I, Cameron B G, Crawley E F. A technical comparison of three low earth orbit satellite constellation systems to provide global broadband[J]. Acta Astronautica, 2019, 159: 123 - 135.
7	Jun X, Lu W, Zhang G. Traffic modeling and simulation of broadband LEO satellite communication system[A].IOP Conference Series: Materials Science and Engineering[C]. IOP Publishing, 2018, 452(4): 042082.
8	Jia Z, Sheng M, Li J, et al. Joint HAP access and LEO satellite backhaul in 6G: Matching game-based approaches[J]. IEEE Journal on Selected Areas in Communications, 2020, 39(4): 1147 - 1159.
9	Shmoys D B. Cut problems and their application to divide-and-conquer[J]. Approximation Algorithms for NP-Hard Problems, 1997: 192 - 235.
10	Shahrokhi F, Matula D W. The maximum concurrent flow problem[J]. Journal of the ACM (JACM), 1990, 37(2): 318 - 334.
11	Leighton T, Makedon F, Plotkin S, et al. Fast approximation algorithms for multicommodity flow problems[J]. Journal of Computer and System Sciences, 1995, 50(2): 228 - 243.
12	Garg N, Koenemann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems[J]. SIAM Journal on Computing, 2007, 37(2): 630 - 652.
13	Karakostas G. Faster approximation schemes for fractional multicommodity flow problems[J]. ACM Transactions on Algorithms (TALG), 2008, 4(1): 1 - 17.
14	Filsfils C, Nainar N K, Pignataro C, et al. The segment routing architecture[A].2015 IEEE Global Communications Conference (GLOBECOM)[C]. USA: IEEE, 2015. 1 - 6.
15	Davoli L, Veltri L, Ventre P L, et al. Traffic engineering with segment routing: SDN-based architectural design and open source implementation[A].2015 Fourth European Workshop on Software Defined Networks[C].USA: IEEE, 2015. 111 - 112.
16	Bhatia R, Hao F, Kodialam M, et al. Optimized network traffic engineering using segment routing[A].2015 IEEE Conference on Computer Communications (INFOCOM)[C].USA: IEEE, 2015. 657 - 665.
17	黄建洋,兰巨龙,胡宇翔,等. 一种基于分段路由的多路径流传输机制[J]. 电子学报, 2018, 46(6):1488 - 1495.
	Huang Jian-yang, Lan Ju-long, Hu Yu-xiang, et al. A segment routing based multipath flow transmission mechanism[J]. Acta Electronica Sinica, 2018, 46(6):1488 - 1495.(in Chinese)
18	Liu W, Tao Y, Liu L. Load-balancing routing algorithm based on segment routing for traffic return in LEO satellite networks[J]. IEEE Access, 2019, 7: 112044 - 112053.
19	Stephen Boyd, Lieven Vandenberghe. Convex optimization[J]. IEEE Transactions on Automatic Control, 2006, 51(11):1859 - 1859.

[1]	李鹏, 闵慧, 罗爱静. 基于动态图的PPI网络构建和复合物挖掘算法研究[J]. 电子学报, 2021, 49(8): 1489-1497.
[2]	崔子熙, 胡宇翔, 兰巨龙, 王雨. 基于流分类的数据中心网络负载均衡机制[J]. 电子学报, 2021, 49(3): 559-565.
[3]	刘剑锋, 孙力帆, 普杰信, 何子述, 王燕玲. 基于刚性约束的双移动机器人协同定位[J]. 电子学报, 2020, 48(9): 1777-1785.
[4]	江小玉, 李贵洋, 周悦, 胡金平, 李慧. 基于负载均衡的纠删码修复流水线[J]. 电子学报, 2020, 48(5): 930-936.
[5]	刘焕淋, 胡浩, 陈勇, 杜君丹, 向敏. 联合能耗与负载均衡的虚拟网络映射方法[J]. 电子学报, 2019, 47(12): 2488-2494.
[6]	黄建洋, 兰巨龙, 胡宇翔, 马腾. 一种基于分段路由的多路径流传输机制[J]. 电子学报, 2018, 46(6): 1488-1495.
[7]	于倡和, 兰巨龙, 胡宇翔. 软件定义网络一致性协同更新算法[J]. 电子学报, 2018, 46(10): 2341-2346.
[8]	胡涛, 张建辉, 邬江, 何为伟, 江逸茗, 赵伟. SDN中基于分布式决策的控制器负载均衡机制[J]. 电子学报, 2018, 46(10): 2316-2324.
[9]	方馨蔚, 陈庶樵, 江逸茗, 任泽荣. 一种内容中心网络中的热区控制及内容调度缓存算法[J]. 电子学报, 2017, 45(5): 1182-1188.
[10]	曹政才, 林诚然, 黄冉. 带等待时间约束并行机调度问题的Copula分布估计算法[J]. 电子学报, 2017, 45(12): 2949-2956.
[11]	梁常建, 李永明. 具有模糊时态的广义可能性线性时序逻辑的模型检测[J]. 电子学报, 2017, 45(12): 2971-2977.
[12]	黄建洋, 兰巨龙, 胡宇翔, 马腾. 一种SDN中基于SR的多故障恢复与规避机制[J]. 电子学报, 2017, 45(11): 2761-2768.
[13]	陶晓玲, 韦毅, 王勇. 一种基于分层多代理的云计算负载均衡方法[J]. 电子学报, 2016, 44(9): 2106-2113.
[14]	盛洁, 马冬. 异构无线网络业务接入多目标优化控制算法[J]. 电子学报, 2016, 44(2): 282-288.
[15]	赵湘宁. 一种基于信号机制的能量感知地理路由算法[J]. 电子学报, 2015, 43(5): 965-973.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 19

相关文章 15

编辑推荐

Metrics