基于时间演进图的LEO星间切换实时预测及更新方法

胡欣，宋航宇，刘帅军，李秀华，王卫东，汪春霆



基于时间演进图的LEO星间切换实时预测及更新方法

胡欣1，宋航宇1，刘帅军1，李秀华1，王卫东1，汪春霆2

（1. 北京邮电大学电子工程学院，北京 100876；2. 中国电子科技集团公司第五十四研究所，河北 石家庄 050081）

为了解决低轨（LEO, low earth orbit）卫星时变拓扑以及用户运动交织带来的切换效率较低的问题，提出一种基于时间演进图（TEG, time evolving graph）的星间实时切换预测框架和最短路径动态更新算法。根据终端运动情况，从时间和空间这2个维度动态更新切换预测结果。所提方法适用于多种切换策略，具有较高的灵活性。仿真结果显示，所提方法可以有效地提高预测的准确性，同时避免不必要的切换。

LEO卫星网络；星间切换；时间演进图；最短路径动态更新算法

1 引言

卫星网络具有全球覆盖、移动性和可扩展性等优点，可以随时随地提供全球高效的广播和多播服务。经过几十年的快速发展，卫星通信系统已成为现代通信系统最重要的部分之一[1]。相比于地球同步轨道（GEO, geostationary earth orbit）卫星和中轨（MEO, medium earth orbit）卫星通信系统而言，LEO卫星具有较小的通信时延和传输损耗，多颗LEO卫星组成的星座可实现全球即时通信。因此，LEO卫星通信系统被视为最有发展前景的卫星通信系统。然而，由于LEO卫星星座位于低轨，相对地面具有较高的移动速度，其在地球表面的波束覆盖范围变化很快，一颗LEO卫星在指定区域内的覆盖时长仅为几分钟[2]。

为了确保实时通信，地面终端需在LEO卫星的波束之间以及卫星与卫星间频繁切换。目前，许多研究机构及研究学者等对波束间的切换问题已开展大量研究工作。文献[3]考虑了相邻卫星波束的服务时间相关性，提出了一个简单的分析框架，用于在具有相关服务时间的低轨卫星系统中对新呼叫和切换呼叫进行性能评估。文献[4]提出了一种基于扩展六边形覆盖模式的多波束覆盖方案，并给出了切换率的闭式表达式，得出了最优的波束形状参数。与波束间切换研究相比，目前关于星间切换的问题亟需开展深入研究，因此本文重点研究星间切换。关于星间切换，在基于仰角的LEO星间切换方面，文献[5-6]提出了硬切换和混合信道自适应切换方案。针对仰角、通信时长和空闲信道数的策略选择问题，文献[7]提出了基于动态多普勒切换优先级方法来评估不同卫星的切换策略（最长服务时间策略、最大仰角策略和基于空闲信道数策略）。在此基础上，文献[8]深入分析了LEO卫星星座覆盖时间特点，并首次提出了LEO卫星预期切换次数下限。文献[9]对上述卫星切换工作进行了总结，提出了一种基于静态图的LEO星座切换预测架构和方法，将切换过程建模为有向图中的最短路径问题，可适用于多种不同切换策略，且在终端静止情况下具有很好的切换预测效果。

现有研究[3-9]均假设LEO卫星通信链路稳定，却忽略了终端运动对切换造成的影响。然而，中、高速移动终端的运动可能会改变通信链路状态，使用静态分析方法对其切换进行研究会造成切换失败或额外增加切换次数，切换效率较低。为保证LEO场景下通信的连续性并避免乒乓效应，本文综合考虑了终端运动速度、卫星链路状态、卫星网络状态等因素，首先分析了终端运动速度对星间切换的影响，并将星间切换过程建模为求解TEG[10-11]的每个子图中从起始节点到终止节点的最短路径问题，根据TEG中子图之间的演进情况，从时间和空间这2个维度动态更新切换结果，提高切换预测结果的准确性。

2 LEO星座通信场景及切换预测建模

2.1 LEO星座通信场景描述

LEO星座与地面终端通信场景示意如图1所示。根据终端移动速度不同，可将终端定义为低速移动终端（如行人）、中速移动终端（如汽车）和高速移动终端（如高铁、飞机）。

终端用户通话时长定义为服从均值为的指数分布[12]，概率密度函数式为

在通话时长内，利用高斯−马尔可夫（GM, Gauss-Markov）模型[13]对终端运动行为建模，如式(2)和式(3)所示。

图2 单颗卫星与终端连接关系

本文只考虑星间切换，没有涉及波束间切换的问题，因此，本文只推导了单颗卫星对终端的覆盖时长。对于多波束卫星，每个波束对终端的覆盖时长的推导方式和单颗卫星的推导方式相同。

2.2 切换预测建模

图3 LEO星座动态时变网络切换预测模型

3 切换预测实时更新

3.1 动态更新时间

3.2 最短路径动态更新算法

由于终端的运动会造成卫星覆盖时长和卫星仰角的变化，卫星的空闲信道数等也会随时间变化，因此TEG中弧的权重也会动态变化。每个时隙更新时需从空间的维度重新进行权重和最优策略评估，完成对切换的预测更新。为降低空间维度的计算复杂度，本文提出了适用于多边权值动态变化的最短路径实时更新算法，仅更新每个子图的最短路径树（SPT, shortest path tree）中受影响的节点，即可有效提高计算效率。

本文算法需要经过预处理、入队操作、出队操作、节点更新这4个步骤。在本文的动态更新算法中，原最短路径树如图4的粗线所示，当弧上权值改变时，定义队列用来确定最大可能受影响的节点的集合。图5中用虚线圈出了最短路径受影响的节点，圈外的节点的最短路径不受影响[14]。

图4 原子图中的最短路径树

图5 更新后的最短路径树

为了方便描述，引入以下符号。

5) 定义1和2，在某一时隙有多条弧的权值变化时，将所有权值减小的弧加入1，将所有权值增大的弧加入2。

3.3 算法复杂度分析

表1 算法复杂度对比

4 仿真结果

4.1 仿真参数设置

仿真参数设置如表2所示。

表2 仿真参数设置

4.2 仿真结果分析

本文采用最长覆盖时间切换准则进行仿真，主要关注切换预测的准确性、切换失败率和不必要的切换率这3个指标。

图6 单颗卫星对终端覆盖时长下限值

2) 切换预测准确性：基于最长覆盖时间切换准则，将终端位置设在北京（40°N,116°E），终端的运动速度和方向服从式(2)和式(3)的GM模型，通话时长为30 min。图7~图10分别为终端速度平均值取0 m/s、100 m/s、300 m/s、500 m/s时仿真得出的全球星星座对终端的覆盖特性，表3~表6为对应的切换预测结果。在上述场景下，将本文TEG框架与文献[9]静态图方法的切换预测结果进行对比。在仿真开始时刻，当终端的接入星为卫星23时，对比图7和图9，文献[9]的预测结果将导致切换失败。在仿真开始时刻，当终端的接入星为卫星12时，对比图8和图10，文献[9]将导致不必要的切换。通过对比可以看出，当终端运动速度较大时，文献[9]忽略了终端的运动，导致其切换预测的结果不准确。本文通过对终端运动进行建模，并基于TEG框架动态更新切换预测结果，提升了切换预测的准确性。

图7 终端静止时的覆盖特性

表3 终端静止时的切换预测结果对比

图8 终端为100 m/s时的覆盖特性

表4 终端为100 m/s时的切换预测结果对比

图9 终端为300 m/s时的覆盖特性

表5 终端为300 m/s时的切换预测结果对比

图10 终端为500 m/s时的覆盖特性

表6 终端为500 m/s时的切换预测结果对比

3) 切换效率：切换失败率和不必要的切换率越高，则切换效率越低。为评估本文提出的TEG方法的切换效率，选取1 000个随机分布终端，终端通话时长为20 min，终端按照式(2)和式(3)用GM模型对终端运动行为进行建模，得到其速度大小和运动方向。

图11为终端在不同速度下，采用文献[9]中静态图预测方法与本文TEG预测方法的切换失败率对比。图11中横坐标为终端运动速度的平均值，纵坐标为切换失败率。从图11可以看出，2种切换预测方法的切换失败率都随终端的速度增大而增大，但本文的切换失败率要远小于文献[9]，如终端速度为300 m/s时，文献[9]方法的切换失败率为67%，本文算法的切换失败率仅为23%。

图11 切换失败率

图12为终端在不同速度下，采用文献[9]中静态图预测方法与本文TEG预测方法的不必要的切换率对比。图12中横坐标为终端运动速度的平均值，纵坐标为不必要的切换率。从图12可以看出，2种切换预测方法的不必要切换率都随终端的速度增大而增大，但本文的不必要切换率要远小于文献[9]，并且终端速度越大，本文算法的优势越明显，如终端速度为500 m/s时，文献[9]方法的不必要切换率为13.9%，本文算法的不必要切换率仅为4.1%。本文采取动态更新预测结果，根据图6和式(14)对不同运动速度的终端设置不同的时隙时长，再对切换预测结果进行动态更新。而文献[9]中静态图忽略了终端的运动，因此切换失败率和不必要切换率明显高于本文算法。通过对比可以看出，本文的切换预测方法的切换效率相比于静态图有很大程度的提升。

图12 不必要的切换率

5 结束语

星间切换问题是卫星移动通信中需要解决的关键问题，本文重点考虑了终端运动对星间切换的影响，并分析了单颗卫星对运动终端的覆盖时长。通过分析得出，当终端运动速度较高时，其将对切换预测结果产生较大影响。因此本文采用GM模型对终端运动进行建模，采用TEG模型对运动终端的星间切换进行建模分析，并提出一种最短路径动态更新算法来动态更新切换预测结果。仿真结果表明，本文的切换预测方法相较于静态图预测方法可以更准确地得到终端在不同运动速度下的切换路径，有效减少切换失败率和不必要的切换率。

[1] LI T, ZHOU H, LUO H, et al. SAT-FLOW: multi-strategy flow table management for software defined satellite networks[J]. IEEE Access, 2017, PP(99): 1.

[2] RAHMAN M, WALINGO T, TAKAWIRA F. Adaptive handover scheme for LEO satellite communication system[C]//IEEE Africon. 2015: 1-5.

[3] MUSUMPUKA R, WALINGO T M, SMITH J M. Performance analysis of correlated handover service in LEO mobile satellite systems[J]. IEEE Communications Letters, 2016, 20(11): 2213-2216.

[4] CHEN Y, FANG B, ZHANG S, et al. Satellite multi-beam coverage analysis for handover rate reduction[C]//The 2014 Sixth International Conference on Wireless Communications and Signal Processing (WCSP). 2014: 1-6.

[5] GKIZELI M, TAFAZOLLI R, EVANS B. Modeling handover in mobile satellite diversity based systems[C]//Vehicular Technology Conference. 2001: 131-135.

[6] GKIZELI M, TAFAZOLLI R, EVANS B G. Hybrid channel adaptive handover scheme for non-GEO satellite diversity based systems[J]. IEEE Communications Letters, 2001, 5(7): 284-286.

[7] PAPAPETROU E, KARAPANTAZIS S, DIMITRIADIS G, et al. Satellite handover techniques for LEO networks[J]. International Journal of Satellite Communications & Networking, 2010, 22(2): 231-245.

[8] SEYEDI Y, SAFAVI S M. On the analysis of random coverage time in mobile LEO satellite communications[J]. IEEE Communications Letters, 2012, 16(5): 612-615.

[9] WU Z, JIN F, LUO J, et al. A graph-based satellite handover framework for LEO satellite communication networks[J]. IEEE Communications Letters, 2016, 20(8): 1547-1550.

[10] WANG Y, ZHANG G, JIANG Z, et al. A novel routing algorithm design of time evolving graph based on pairing heap for MEO satellite network[C]// Vehicular Technology Conference. 2014: 1-5.

[11] LIU R, SHENG M, LUI K S, et al. An analytical framework for resource-limited small satellite networks[C]// IEEE Communications Letters. 2016: 388-391.

[12] 李广侠, 郦苏丹, 冯少栋. 切换保留信道与新呼叫排队相结合的LEO星座通信系统信道分配方案研究[J]. 通信学报, 2006, 27(9): 135-140.

LI G X, LI S D, FENG S D. Channel assigning scheme study in LEO constellation communication system combining handover reserving strategy and new call queuing[J]. Journal on Communications, 2006, 27(9): 135-140.

[13] ZHU X, LI M, XIA W, et al. A novel handoff algorithm for hierarchical cellular networks[J]. China Communications, 2016, 13(8): 136-147.

[14] XIAO B, CAO J, SHAO Z, et al. An efficient algorithm for dynamic shortest path tree update in network routing[J]. Journal of Communications & Networks, 2012, 9(4): 499-510.

Real-time prediction and updating method for LEO satellite handover based on time evolving graph

HU Xin1, SONG Hangyu1, LIU Shuaijun1, LI Xiuhua1, WANG Weidong1, WANG Chunting2

1. School of Telecommunication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China 2. The 54th Research Institute of China Electronics Technology Group Corporation, Shijiazhuang 050081, China

In order to solve the problem of low handover efficiency raised by the interwined impacts of time-varying topology of LEO satellites and terminal movement, a real-time satellite handover prediction framework based on time evolving graph and a shortest path dynamic updating method was proposed. This framework dynamically updated the handover prediction results from the temporal and spatial dimensions according to the terminal movement. The simulation results show that the framework can effectively improve the accuracy of the forecast and avoid the unnecessary handover.

LEO satellite network, satellite handover, time evolving graph, shortest path dynamic updating method

TN927

A

10.11959/j.issn.1000−436x.2018166

胡欣（1985−），男，湖北襄阳人，博士，北京邮电大学副教授、硕士生导师，主要研究方向为智能信号处理、空间和地面信息集成以及航空航天电子信息综合等。

宋航宇（1994−），女，河南洛阳人，北京邮电大学硕士生，主要研究方向为卫星移动通信、无线资源管理等。

刘帅军（1988−），男，河北邢台人，北京邮电大学博士生，主要研究方向为卫星移动通信、机器学习和动态资源管理等。

李秀华（1964−），女，天津人，博士，北京邮电大学副教授、硕士生导师，主要研究方向为物联网、纳米材料在电子及通信领域应用的研究等。

王卫东（1967−），男，内蒙古包头人，博士，北京邮电大学教授、博士生导师，主要研究方向为卫星通信、无线资源管理、物联网和信号处理等。

汪春霆（1965−），男，江西南昌人，博士，中国电子科技集团公司第五十四研究所研究员、博士生导师，主要研究方向为卫星通信。

2017−11−10；

2018−07−09

宋航宇，shy0815@bupt.edu.cn

国家自然科学基金资助项目（No.91438114）

The National Natural Science Foundation of China (No.91438114)