基于時(shí)間演進(jìn)圖的LEO星間切換實(shí)時(shí)預(yù)測(cè)及更新方法

胡欣，宋航宇，劉帥軍，李秀華，王衛(wèi)東，汪春霆

?

基于時(shí)間演進(jìn)圖的LEO星間切換實(shí)時(shí)預(yù)測(cè)及更新方法

胡欣1，宋航宇1，劉帥軍1，李秀華1，王衛(wèi)東1，汪春霆2

（1. 北京郵電大學(xué)電子工程學(xué)院，北京 100876；2. 中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081）

為了解決低軌（LEO, low earth orbit）衛(wèi)星時(shí)變拓?fù)湟约坝脩暨\(yùn)動(dòng)交織帶來(lái)的切換效率較低的問(wèn)題，提出一種基于時(shí)間演進(jìn)圖（TEG, time evolving graph）的星間實(shí)時(shí)切換預(yù)測(cè)框架和最短路徑動(dòng)態(tài)更新算法。根據(jù)終端運(yùn)動(dòng)情況，從時(shí)間和空間這2個(gè)維度動(dòng)態(tài)更新切換預(yù)測(cè)結(jié)果。所提方法適用于多種切換策略，具有較高的靈活性。仿真結(jié)果顯示，所提方法可以有效地提高預(yù)測(cè)的準(zhǔn)確性，同時(shí)避免不必要的切換。

LEO衛(wèi)星網(wǎng)絡(luò)；星間切換；時(shí)間演進(jìn)圖；最短路徑動(dòng)態(tài)更新算法

1 引言

衛(wèi)星網(wǎng)絡(luò)具有全球覆蓋、移動(dòng)性和可擴(kuò)展性等優(yōu)點(diǎn)，可以隨時(shí)隨地提供全球高效的廣播和多播服務(wù)。經(jīng)過(guò)幾十年的快速發(fā)展，衛(wèi)星通信系統(tǒng)已成為現(xiàn)代通信系統(tǒng)最重要的部分之一[1]。相比于地球同步軌道（GEO, geostationary earth orbit）衛(wèi)星和中軌（MEO, medium earth orbit）衛(wèi)星通信系統(tǒng)而言，LEO衛(wèi)星具有較小的通信時(shí)延和傳輸損耗，多顆LEO衛(wèi)星組成的星座可實(shí)現(xiàn)全球即時(shí)通信。因此，LEO衛(wèi)星通信系統(tǒng)被視為最有發(fā)展前景的衛(wèi)星通信系統(tǒng)。然而，由于LEO衛(wèi)星星座位于低軌，相對(duì)地面具有較高的移動(dòng)速度，其在地球表面的波束覆蓋范圍變化很快，一顆LEO衛(wèi)星在指定區(qū)域內(nèi)的覆蓋時(shí)長(zhǎng)僅為幾分鐘[2]。

為了確保實(shí)時(shí)通信，地面終端需在LEO衛(wèi)星的波束之間以及衛(wèi)星與衛(wèi)星間頻繁切換。目前，許多研究機(jī)構(gòu)及研究學(xué)者等對(duì)波束間的切換問(wèn)題已開(kāi)展大量研究工作。文獻(xiàn)[3]考慮了相鄰衛(wèi)星波束的服務(wù)時(shí)間相關(guān)性，提出了一個(gè)簡(jiǎn)單的分析框架，用于在具有相關(guān)服務(wù)時(shí)間的低軌衛(wèi)星系統(tǒng)中對(duì)新呼叫和切換呼叫進(jìn)行性能評(píng)估。文獻(xiàn)[4]提出了一種基于擴(kuò)展六邊形覆蓋模式的多波束覆蓋方案，并給出了切換率的閉式表達(dá)式，得出了最優(yōu)的波束形狀參數(shù)。與波束間切換研究相比，目前關(guān)于星間切換的問(wèn)題亟需開(kāi)展深入研究，因此本文重點(diǎn)研究星間切換。關(guān)于星間切換，在基于仰角的LEO星間切換方面，文獻(xiàn)[5-6]提出了硬切換和混合信道自適應(yīng)切換方案。針對(duì)仰角、通信時(shí)長(zhǎng)和空閑信道數(shù)的策略選擇問(wèn)題，文獻(xiàn)[7]提出了基于動(dòng)態(tài)多普勒切換優(yōu)先級(jí)方法來(lái)評(píng)估不同衛(wèi)星的切換策略（最長(zhǎng)服務(wù)時(shí)間策略、最大仰角策略和基于空閑信道數(shù)策略）。在此基礎(chǔ)上，文獻(xiàn)[8]深入分析了LEO衛(wèi)星星座覆蓋時(shí)間特點(diǎn)，并首次提出了LEO衛(wèi)星預(yù)期切換次數(shù)下限。文獻(xiàn)[9]對(duì)上述衛(wèi)星切換工作進(jìn)行了總結(jié)，提出了一種基于靜態(tài)圖的LEO星座切換預(yù)測(cè)架構(gòu)和方法，將切換過(guò)程建模為有向圖中的最短路徑問(wèn)題，可適用于多種不同切換策略，且在終端靜止情況下具有很好的切換預(yù)測(cè)效果。

現(xiàn)有研究[3-9]均假設(shè)LEO衛(wèi)星通信鏈路穩(wěn)定，卻忽略了終端運(yùn)動(dòng)對(duì)切換造成的影響。然而，中、高速移動(dòng)終端的運(yùn)動(dòng)可能會(huì)改變通信鏈路狀態(tài)，使用靜態(tài)分析方法對(duì)其切換進(jìn)行研究會(huì)造成切換失敗或額外增加切換次數(shù)，切換效率較低。為保證LEO場(chǎng)景下通信的連續(xù)性并避免乒乓效應(yīng)，本文綜合考慮了終端運(yùn)動(dòng)速度、衛(wèi)星鏈路狀態(tài)、衛(wèi)星網(wǎng)絡(luò)狀態(tài)等因素，首先分析了終端運(yùn)動(dòng)速度對(duì)星間切換的影響，并將星間切換過(guò)程建模為求解TEG[10-11]的每個(gè)子圖中從起始節(jié)點(diǎn)到終止節(jié)點(diǎn)的最短路徑問(wèn)題，根據(jù)TEG中子圖之間的演進(jìn)情況，從時(shí)間和空間這2個(gè)維度動(dòng)態(tài)更新切換結(jié)果，提高切換預(yù)測(cè)結(jié)果的準(zhǔn)確性。

2 LEO星座通信場(chǎng)景及切換預(yù)測(cè)建模

2.1 LEO星座通信場(chǎng)景描述

LEO星座與地面終端通信場(chǎng)景示意如圖1所示。根據(jù)終端移動(dòng)速度不同，可將終端定義為低速移動(dòng)終端（如行人）、中速移動(dòng)終端（如汽車）和高速移動(dòng)終端（如高鐵、飛機(jī)）。

終端用戶通話時(shí)長(zhǎng)定義為服從均值為的指數(shù)分布[12]，概率密度函數(shù)式為

在通話時(shí)長(zhǎng)內(nèi)，利用高斯?馬爾可夫（GM, Gauss-Markov）模型[13]對(duì)終端運(yùn)動(dòng)行為建模，如式(2)和式(3)所示。

圖2 單顆衛(wèi)星與終端連接關(guān)系

本文只考慮星間切換，沒(méi)有涉及波束間切換的問(wèn)題，因此，本文只推導(dǎo)了單顆衛(wèi)星對(duì)終端的覆蓋時(shí)長(zhǎng)。對(duì)于多波束衛(wèi)星，每個(gè)波束對(duì)終端的覆蓋時(shí)長(zhǎng)的推導(dǎo)方式和單顆衛(wèi)星的推導(dǎo)方式相同。

2.2 切換預(yù)測(cè)建模

圖3 LEO星座動(dòng)態(tài)時(shí)變網(wǎng)絡(luò)切換預(yù)測(cè)模型

3 切換預(yù)測(cè)實(shí)時(shí)更新

3.1 動(dòng)態(tài)更新時(shí)間

3.2 最短路徑動(dòng)態(tài)更新算法

由于終端的運(yùn)動(dòng)會(huì)造成衛(wèi)星覆蓋時(shí)長(zhǎng)和衛(wèi)星仰角的變化，衛(wèi)星的空閑信道數(shù)等也會(huì)隨時(shí)間變化，因此TEG中弧的權(quán)重也會(huì)動(dòng)態(tài)變化。每個(gè)時(shí)隙更新時(shí)需從空間的維度重新進(jìn)行權(quán)重和最優(yōu)策略評(píng)估，完成對(duì)切換的預(yù)測(cè)更新。為降低空間維度的計(jì)算復(fù)雜度，本文提出了適用于多邊權(quán)值動(dòng)態(tài)變化的最短路徑實(shí)時(shí)更新算法，僅更新每個(gè)子圖的最短路徑樹(shù)（SPT, shortest path tree）中受影響的節(jié)點(diǎn)，即可有效提高計(jì)算效率。

本文算法需要經(jīng)過(guò)預(yù)處理、入隊(duì)操作、出隊(duì)操作、節(jié)點(diǎn)更新這4個(gè)步驟。在本文的動(dòng)態(tài)更新算法中，原最短路徑樹(shù)如圖4的粗線所示，當(dāng)弧上權(quán)值改變時(shí)，定義隊(duì)列用來(lái)確定最大可能受影響的節(jié)點(diǎn)的集合。圖5中用虛線圈出了最短路徑受影響的節(jié)點(diǎn)，圈外的節(jié)點(diǎn)的最短路徑不受影響[14]。

圖4 原子圖中的最短路徑樹(shù)

圖5 更新后的最短路徑樹(shù)

為了方便描述，引入以下符號(hào)。

5) 定義1和2，在某一時(shí)隙有多條弧的權(quán)值變化時(shí)，將所有權(quán)值減小的弧加入1，將所有權(quán)值增大的弧加入2。

3.3 算法復(fù)雜度分析

表1 算法復(fù)雜度對(duì)比

4 仿真結(jié)果

4.1 仿真參數(shù)設(shè)置

仿真參數(shù)設(shè)置如表2所示。

表2 仿真參數(shù)設(shè)置

4.2 仿真結(jié)果分析

本文采用最長(zhǎng)覆蓋時(shí)間切換準(zhǔn)則進(jìn)行仿真，主要關(guān)注切換預(yù)測(cè)的準(zhǔn)確性、切換失敗率和不必要的切換率這3個(gè)指標(biāo)。

圖6 單顆衛(wèi)星對(duì)終端覆蓋時(shí)長(zhǎng)下限值

2) 切換預(yù)測(cè)準(zhǔn)確性：基于最長(zhǎng)覆蓋時(shí)間切換準(zhǔn)則，將終端位置設(shè)在北京（40°N,116°E），終端的運(yùn)動(dòng)速度和方向服從式(2)和式(3)的GM模型，通話時(shí)長(zhǎng)為30 min。圖7~圖10分別為終端速度平均值取0 m/s、100 m/s、300 m/s、500 m/s時(shí)仿真得出的全球星星座對(duì)終端的覆蓋特性，表3~表6為對(duì)應(yīng)的切換預(yù)測(cè)結(jié)果。在上述場(chǎng)景下，將本文TEG框架與文獻(xiàn)[9]靜態(tài)圖方法的切換預(yù)測(cè)結(jié)果進(jìn)行對(duì)比。在仿真開(kāi)始時(shí)刻，當(dāng)終端的接入星為衛(wèi)星23時(shí)，對(duì)比圖7和圖9，文獻(xiàn)[9]的預(yù)測(cè)結(jié)果將導(dǎo)致切換失敗。在仿真開(kāi)始時(shí)刻，當(dāng)終端的接入星為衛(wèi)星12時(shí)，對(duì)比圖8和圖10，文獻(xiàn)[9]將導(dǎo)致不必要的切換。通過(guò)對(duì)比可以看出，當(dāng)終端運(yùn)動(dòng)速度較大時(shí)，文獻(xiàn)[9]忽略了終端的運(yùn)動(dòng)，導(dǎo)致其切換預(yù)測(cè)的結(jié)果不準(zhǔn)確。本文通過(guò)對(duì)終端運(yùn)動(dòng)進(jìn)行建模，并基于TEG框架動(dòng)態(tài)更新切換預(yù)測(cè)結(jié)果，提升了切換預(yù)測(cè)的準(zhǔn)確性。

圖7 終端靜止時(shí)的覆蓋特性

表3 終端靜止時(shí)的切換預(yù)測(cè)結(jié)果對(duì)比

圖8 終端為100 m/s時(shí)的覆蓋特性

表4 終端為100 m/s時(shí)的切換預(yù)測(cè)結(jié)果對(duì)比

圖9 終端為300 m/s時(shí)的覆蓋特性

表5 終端為300 m/s時(shí)的切換預(yù)測(cè)結(jié)果對(duì)比

圖10 終端為500 m/s時(shí)的覆蓋特性

表6 終端為500 m/s時(shí)的切換預(yù)測(cè)結(jié)果對(duì)比

3) 切換效率：切換失敗率和不必要的切換率越高，則切換效率越低。為評(píng)估本文提出的TEG方法的切換效率，選取1 000個(gè)隨機(jī)分布終端，終端通話時(shí)長(zhǎng)為20 min，終端按照式(2)和式(3)用GM模型對(duì)終端運(yùn)動(dòng)行為進(jìn)行建模，得到其速度大小和運(yùn)動(dòng)方向。

圖11為終端在不同速度下，采用文獻(xiàn)[9]中靜態(tài)圖預(yù)測(cè)方法與本文TEG預(yù)測(cè)方法的切換失敗率對(duì)比。圖11中橫坐標(biāo)為終端運(yùn)動(dòng)速度的平均值，縱坐標(biāo)為切換失敗率。從圖11可以看出，2種切換預(yù)測(cè)方法的切換失敗率都隨終端的速度增大而增大，但本文的切換失敗率要遠(yuǎn)小于文獻(xiàn)[9]，如終端速度為300 m/s時(shí)，文獻(xiàn)[9]方法的切換失敗率為67%，本文算法的切換失敗率僅為23%。

圖11 切換失敗率

圖12為終端在不同速度下，采用文獻(xiàn)[9]中靜態(tài)圖預(yù)測(cè)方法與本文TEG預(yù)測(cè)方法的不必要的切換率對(duì)比。圖12中橫坐標(biāo)為終端運(yùn)動(dòng)速度的平均值，縱坐標(biāo)為不必要的切換率。從圖12可以看出，2種切換預(yù)測(cè)方法的不必要切換率都隨終端的速度增大而增大，但本文的不必要切換率要遠(yuǎn)小于文獻(xiàn)[9]，并且終端速度越大，本文算法的優(yōu)勢(shì)越明顯，如終端速度為500 m/s時(shí)，文獻(xiàn)[9]方法的不必要切換率為13.9%，本文算法的不必要切換率僅為4.1%。本文采取動(dòng)態(tài)更新預(yù)測(cè)結(jié)果，根據(jù)圖6和式(14)對(duì)不同運(yùn)動(dòng)速度的終端設(shè)置不同的時(shí)隙時(shí)長(zhǎng)，再對(duì)切換預(yù)測(cè)結(jié)果進(jìn)行動(dòng)態(tài)更新。而文獻(xiàn)[9]中靜態(tài)圖忽略了終端的運(yùn)動(dòng)，因此切換失敗率和不必要切換率明顯高于本文算法。通過(guò)對(duì)比可以看出，本文的切換預(yù)測(cè)方法的切換效率相比于靜態(tài)圖有很大程度的提升。

圖12 不必要的切換率

5 結(jié)束語(yǔ)

星間切換問(wèn)題是衛(wèi)星移動(dòng)通信中需要解決的關(guān)鍵問(wèn)題，本文重點(diǎn)考慮了終端運(yùn)動(dòng)對(duì)星間切換的影響，并分析了單顆衛(wèi)星對(duì)運(yùn)動(dòng)終端的覆蓋時(shí)長(zhǎng)。通過(guò)分析得出，當(dāng)終端運(yùn)動(dòng)速度較高時(shí)，其將對(duì)切換預(yù)測(cè)結(jié)果產(chǎn)生較大影響。因此本文采用GM模型對(duì)終端運(yùn)動(dòng)進(jìn)行建模，采用TEG模型對(duì)運(yùn)動(dòng)終端的星間切換進(jìn)行建模分析，并提出一種最短路徑動(dòng)態(tài)更新算法來(lái)動(dòng)態(tài)更新切換預(yù)測(cè)結(jié)果。仿真結(jié)果表明，本文的切換預(yù)測(cè)方法相較于靜態(tài)圖預(yù)測(cè)方法可以更準(zhǔn)確地得到終端在不同運(yùn)動(dòng)速度下的切換路徑，有效減少切換失敗率和不必要的切換率。

[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] 李廣俠, 酈蘇丹, 馮少棟. 切換保留信道與新呼叫排隊(duì)相結(jié)合的LEO星座通信系統(tǒng)信道分配方案研究[J]. 通信學(xué)報(bào), 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?），男，湖北襄陽(yáng)人，博士，北京郵電大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)橹悄苄盘?hào)處理、空間和地面信息集成以及航空航天電子信息綜合等。

宋航宇（1994?），女，河南洛陽(yáng)人，北京郵電大學(xué)碩士生，主要研究方向?yàn)樾l(wèi)星移動(dòng)通信、無(wú)線資源管理等。

劉帥軍（1988?），男，河北邢臺(tái)人，北京郵電大學(xué)博士生，主要研究方向?yàn)樾l(wèi)星移動(dòng)通信、機(jī)器學(xué)習(xí)和動(dòng)態(tài)資源管理等。

李秀華（1964?），女，天津人，博士，北京郵電大學(xué)副教授、碩士生導(dǎo)師，主要研究方向?yàn)槲锫?lián)網(wǎng)、納米材料在電子及通信領(lǐng)域應(yīng)用的研究等。

王衛(wèi)東（1967?），男，內(nèi)蒙古包頭人，博士，北京郵電大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾l(wèi)星通信、無(wú)線資源管理、物聯(lián)網(wǎng)和信號(hào)處理等。

汪春霆（1965?），男，江西南昌人，博士，中國(guó)電子科技集團(tuán)公司第五十四研究所研究員、博士生導(dǎo)師，主要研究方向?yàn)樾l(wèi)星通信。

2017?11?10；

2018?07?09

宋航宇，shy0815@bupt.edu.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.91438114）

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