一种增量部署太赫兹链路的巨型近地轨道星座网络路由算法
doi:
作者：叶进, 陈贵豪, 韦姿蓉, 单源超, 黄家玮.
单位：广西大学计算机与电子信息学院 南宁 530004
基金: 国家自然科学基金(62132022, U22A2021)
卫星互联网是近期计算机网络与通信领域的研究热点，路由是卫星互联网领域的基础性关键技术，开展卫星互联网路由技术研究具有重要的研究意义。
太赫兹是6G的关键频段，用于卫星通信具有很好的潜在应用前景，论文针对增量部署太赫兹链路的巨型LEO星座网络路由问题开展了深入研究，具有很好的前沿研究价值。
论文考虑到太赫兹链路的异构性，对增量部署太赫兹的LEO星座链路进行了通信建模，并在此基础上重构的带权时空图具有较好的实用性，在此基础上提出了自适应路由算法，仿真评估结果表明能有效解决因高速太赫兹链路而加剧的星间链路扭曲现象。
1星间链路扭曲拉长问题
在绝大多数传输场景中，星间链路(Inter-Satellite Link, ISL)传输模式是极有可能成为传播时延最低的一种，然而当地面终端设备处于特殊的相对地理位置时，会出现星间链路扭曲拉长的现象，且路径切换更加频繁，此时ISL传输模式次优于弯管转发(Bent-Pipe, BP)传输模式，因此，需要引入弯管转发+星间链路（BP+ISL）传输模式。以Starlink S1为例，在Toronto-Miami自北向南的传输场景中，路径会在星间链路扭曲时间窗内出现拉长的形态，如视频中所演示，图1为星间链路扭曲场景的定性描述。
图1 M点处于星间链路扭曲时间窗口场景
另一方面，将太赫兹频段引入星间链路后，部分链路的传输速率变高，低跳数场景下频繁出现星间扭曲现象，最终导致平均端到端时延相比于单独使用Ka频段有所升高。我们以Starlink S1为星座构型，设计验证性实验，图2为实验结果，可以看出，ISL和BP+ISL传输模式的平均端到端时延相比于单独使用Ka频段链路，均有所升高。可见星间链路扭曲拉长现象在增量部署太赫兹链路后变得更加严重，将影响数据的实时传输与及时交付。
图2 太赫兹增量部署引入的链路平均时延变化情况
为此，团队提出一种增量部署太赫兹链路的巨型近地轨道星座网络路由算法，以减轻星间链路扭曲带来的影响，保证数据传输的服务质量，降低传输时延。算法设计分为两个部分：
第一部分是增量部署太赫兹链路的时空图建模方法；
第二部分是在本文所构建的时空图基础之上，提出考虑弯管转发和星间链路相结合的自适应选择路由算法（routing algorithm for Adaptive Transmission Link Selection, ATLS），综合考虑链路容量、卫星剩余电量和终端设备地理位置多重因素，自适应选择合适的传输链路。
2所提时空图建模方法
【方法思想】
传统的“+Grid”星间链路连接模式过于固定，灵活性不足，因此本团队在“+Grid”星间链路连接模式的基础之上，引入按需连接的星间链路连接模式，用于克服跳数过高和时延的问题，增加连接的灵活性。基于此连接模式，构建本团队提出的时空图。
对于传输任务集合，首先按照任务完成时间升序排序，由最先开始任务和最后完成任务的时间戳，及时间间隔，确定时间片数量。时空图的横轴表示时间维度，t0+kτ为一个时间片，其中k∈N，在[t0+kτ，t0+(k+1)τ]这段时间间隔内，任意时刻下的时空快照图是固定的。对于每个时间片，任意节点的各个天线的连接通路表现为“+Grid”连接方式的星间链路（permanent ISL, pISL）、按需连接模式的星间链路（on-demand ISL, oISL）和星地链路(Ground-Satellite Link, GSL)，此类边为用于转发的转发链路，其余为当前时隙存储待转发的存储链路。
图3为传统的时空图结构，图4为本文所构建的时空图结构，可以看出，本团队提出的时空图相比于传统时空图，增加了虚线部分的oISL，即按需连接模式的星间链路，可以与周围潜在的邻居卫星节点建立连接，尽可能地拓展了可用带宽，提供了多条可能的传输通路，增加寻路的可选性。
图3 传统时空图结构
图4 本文时空图结构
【实验结果】
团队基于Hypatia网络模拟器对时空图的时间间隔取值进行模拟实验，以ISL变化错失率和时间片数量作为衡量指标，设置不同太赫兹链路在总链路的占比（THz Link Ratio, TLR），以Starlink S1为例，使用前述方法构建时空图，实验结果如下图所示。
图5 ISL变化错失率与时间片数量的关系
结果表明，当时间间隔τ取值为500ms时，时间片数量较低，同时ISL变化的错失率小于0.2，能够确保星座网络的整体正常运行。
3所提路由算法【算法思想】
为了解决上述星间链路扭曲拉长导致链路的传播时延增大的问题，本团队提出自适应选择传输链路的路由算法（ATLS）。基于前述时空图建模方法构建的时空图，本算法的目标是为一组任务集合寻找到一组单源-单目的节点的可行路径，最小化单任务的传输代价。
算法由两部分组成，其中，第1阶段是迭代比较路径代价，为所有单任务找到较优的传输路径；第2阶段是根据路径传输所需代价及路径剩余传输服务能力的计算结果，决定是否在时空图上分配该路径。
算法的主要步骤如下：
步骤1：将任务所有路径集合初始化为空。
步骤2：根据任务集合对全局时空图进行分割，得到子图 。
步骤3：初始化单任务从源节点到各节点的路径传输服务能力。
步骤4：基于最小代价优先的策略为单任务进行寻优迭代计算，在进行迭代比较路径代价时，考虑节点的经纬度关系以及链路属性，然后将相应节点加入单任务的路径集合。
步骤5：计算每个任务在任务路径上传输所需的代价，同时计算该任务路径上路径剩余传输服务能力，如果该路径资源充足，则对任务分配路径，同时更新路径的剩余传输服务能力；如果该路径资源不足，则不分配路径。
【实验结果】团队基于Hypatia网络模拟器对BP、ISL、BP+ISL及所提ATLS路由算法进行对比实验，在增量部署太赫兹链路的场景下，设置不同的太赫兹链路占比，对比这4种路由算法的任务完成时间、平均端到端时延、平均吞吐量及平均剩余电量。
图6 不同路由算法性能评价指标对比
结果表明，ATLS路由算法在任务完成时间、平均端到端时延、平均吞吐量上均优于仅基于最短时延的BP+ISL传输模式，并且平均剩余电量相比于BP+ISL，虽然能耗代价有所增加，但也在可容忍的范围之内，能够保证数据传输的低时延、高吞吐率。
4总结及展望
本团队针对增量部署太赫兹链路的巨型LEO星座网络中的星间链路扭曲拉长问题，提出一种增量部署太赫兹链路的时空图建模方法，及基于太赫兹时空图的自适应选择传输链路的路由算法。
该路由算法综合考虑了链路容量、卫星剩余电量和终端设备地理位置多重因素，自适应选择合适的传输模式，保证数据传输的服务质量，降低传输时延。
在不久的将来，将会出现全部署太赫兹链路的星座网络，随着星间太赫兹链路数量和速率剧增加，本文实现的路由算法需要进一步改进以适应这一变化，尽可能减少系统开销。在未来，还需要对随机接入、动态部署、随机移动的设备，对时空图的建模进行重新规划，对路由算法做出相应的调整。
美 编 | 高尚尚、余蓉
校 对 | 融媒体工作室
审 核 | 陈 倩
声 明
本文系《电子与信息学报》独家稿件，内容仅供学习交流，版权属于原作者。欢迎评论、转载和分享本公众号原创内容，转载请与本号联系授权，标注原作者和信息来源《电子与信息学报》。
本号发布信息旨在传播交流。如涉及文字、图片、版权等问题，请在20日内与本号联系，我们将第一时间处理。《电子与信息学报》拥有最终解释权。
融媒体平台 Convergence Media
申请加入微信群(备注姓名+单位+方向，商业勿扰)
欢迎关注
