基于時間演進圖的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)