低轨巨星座多品类业务流低复杂度分段路由方法
A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation
- 电子学报 2021年49卷第11期 页码：2124-2132
- 作者机构：
1.中国空间技术研究院通信与导航卫星总体部，北京 100094
2.鹏城实验室，广东深圳518052
3.北京空间机电研究所，北京 100094
- 作者简介：
[ "王宁远 男，1993年生，安徽安庆人，博士研究生.2018年毕业于北京航空航天大学航空宇航科学与技术专业，同年进入中国空间技术研究院攻读博士学位，研究方向为通信卫星星座网络、星座资源管理等. E-mail:ningyuan.wang@foxmail.com" ]
[ "刘 亮（通信作者） 男，1986年生，陕西西安人，博士，高级工程师.现任职于中国空间技术研究院通信与导航卫星总体部，主要研究方向为网络协议、编码理论及卫星通信. E-mail:liuliang1945@buaa.edu.cn" ]
- 基金信息：国家自然科学基金(61875230);国家重点研发计划(2020YFB1806102)
DOI：10.12263/DZXB.20201335
中图分类号： TN915.41;TP393.4收稿：2020-11-26，
修回：2021-08-24，
纸质出版：2021-11-25
- 稿件说明：
移动端阅览
王宁远,刘亮,陈东等.低轨巨星座多品类业务流低复杂度分段路由方法[J].电子学报,2021,49(11):2124-2132.
WANG Ning-yuan,LIU Liang,CHEN Dong,et al.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.
王宁远,刘亮,陈东等.低轨巨星座多品类业务流低复杂度分段路由方法[J].电子学报,2021,49(11):2124-2132. DOI： 10.12263/DZXB.20201335.
WANG Ning-yuan,LIU Liang,CHEN Dong,et al.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. DOI： 10.12263/DZXB.20201335.
摘要
含有星间链路的低轨巨星座网络在全球多种业务回传至有限地理区域场景下会产生严重的网络拥塞问题，集中式的流量规划可以在一定程度上实现负载均衡.然而大规模网络规划的计算时间开销无法满足低轨星座的动态性要求.为此，本文提出了低复杂度的多品类流分段路由（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.
关键词
Keywords
references
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 .
宋海丰 . 国外新兴低轨通信星座发展态势分析 [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)
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 .
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 .
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 .
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 .
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 .
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 .
Shmoys D B . Cut problems and their application to divide-and-conquer [J]. Approximation Algorithms for NP-Hard Problems , 1997 : 192 - 235 .
Shahrokhi F , Matula D W . The maximum concurrent flow problem [J]. Journal of the ACM (JACM) , 1990 , 37 ( 2 ): 318 - 334 .
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 .
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 .
Karakostas G . Faster approximation schemes for fractional multicommodity flow problems [J]. ACM Transactions on Algorithms (TALG) , 2008 , 4 ( 1 ): 1 - 17 .
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 .
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 .
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 .
黄建洋 , 兰巨龙 , 胡宇翔 , 等 . 一种基于分段路由的多路径流传输机制 [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)
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 .
Boyd Stephen , Vandenberghe Lieven . Convex optimization [J]. IEEE Transactions on Automatic Control , 2006 , 51 ( 11 ): 1859 - 1859 .
0
浏览量
22
下载量
0
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies