Predictive Decision and Reliable Accessing for UAV Communication in Space-Air-Ground Integrated Networks

Bowen Zeng,Zhongshan Zhang,Xuhui Ding,Xiangyuan Bu,Jianping An

School of Information and Electronics,Beijing Institute of Technology,Beijing 100081,China

Abstract: The cooperation of multiple Unmanned Aerial Vehicles (UAVs) has become a promising scenario in Space-Air-Ground Integrated Networks(SAGINs) recently due to their widespread applications,where wireless communication is a basic necessity and is normally categorized into control and nonpayload communication (CNPC) as well as payload communication.In this paper, we attempt to tackle two challenges of UAV communication respectively on establishing reliable CNPC links against the high mobility of UAVs as well as changeable communication conditions, and on offering dynamic resource optimization for Quality-of-Service(QoS)guaranteed payload communication with variable link connectivity.Firstly, we propose the concept of air controlling center (ACC), a virtual application equipped on the infrastructure in SAGINs,which can collect global information for estimating UAV trajectory and communication channels.We then introduce the knapsack problem for modelling resource optimization of UAV communication in order to provide optimal access points for both CNPC and payload communication.Meanwhile, using the air controlling information,predictive decision algorithm and handover strategy are introduced for the reliable connection with multiple access points.Simulation results demonstrate that our proposal ensures an approximate always-on reliable accessing of communication links and outperforms the existing methods against high mobility,sparse distribution,and physical obstacles.

Keywords: space-air-ground integrated networks;UAV communication; air communication controlling;predictive decision;reliable accessing

I.INTRODUCTION

Unmanned aerial vehicles (UAVs), also known as drones or unmanned aircraft systems (UASs), have become research hotspots recently because they are widely applied in not only battlefields, but also commerce, industry, and public safety.The long list of UAV applications is generally summarized by packet delivery, film-making, drone fleet show, air communication access or relay,precision agriculture,disaster management,and real-time monitoring[1-5].To cater to more and more complex missions in these various application scenarios,multiple UAVs are organized to form groups as a swarm.Compared with the single UAV,a UAV swarm owns advantages on the extension of communication coverage,the flexibility on mission assignment as well as the survivability in harsh environments.

For a UAV swarm, wireless communication is one of the basic requirements, which is commonly categorized into control and non-payload communication(CNPC)as well as payload communication[5-7].CNPC ensures the safe UAV flight operations by exchanging safety-critical information such as flight status reports, sensed safety-distance warnings, and airtraffic messages.Despite consuming low bandwidth occupations, CNPC is delay-sensitive with less than 50 ms required.Payload communication is normally related to mission-oriented data with high-volume link bandwidths required,e.g.,photographs,videos.

To satisfy the requirements of both CNPC and payload communications, UAVs need to achieve seamless connectivity,high reliability,and high throughput against their high mobility in three-dimension (3D)free space and changing network topology [3, 8-10].Hence, three alternative communication technologies are introduced including satellite-assisted UAV-tosatellite (U2S) communication, UAV-to-UAV (U2U)communication in Uav Ad hoc NETworks(UANETs),and UAV-to-ground(U2G)communication with cellular infrastructures enabled.

Wide coverages around the global are the biggest advantage of satellites to assist UAV communication via U2S links.Besides,satellites offer navigation and positioning functions.However, satellite links commonly suffers from high propagation loss and delay due to long space-air/ground distance as well as limited power, and expensive costs [11, 12].UANET is a decentralized and dynamically self-organized style of networking for peer-to-peer UAV communication,which can support robust and flexible U2U communication for UAVs in a small scale,but fail for the massive UAV swarm with high difficulty in realizing reliable communication against intermittent links.Fifthgeneration (5G) Cellular networks enable UAV communication with almost ubiquitous coverage in urban areas with 10 Gb/s data rates and 1 ms latency,which are promising to meet with the requirements of both CNPC and payload communications except for rural areas such as oceans,deserts,and forests however.In these scenarios,satellites can provide extra connection supports by the wide communication coverage.

Hence, in order to achieve reliable UAV communication, all the U2S, U2U, and U2G communication technologies ought to be integrated together.In this paper, we focus on the communiction accessing and seamless handover for UAVs in the spaceair-ground integrated networks (SAGIN) [13-15], a multi-dimension heterogeneous network with satellite,aerial,and territorial segments.Also,the QoS(Quality of Service)of payload communications is considered.

1.1 Related Works

Current research indicates that UANET may be a feasible style of networking to realize reliable communication[16-18].Compared to all-to-one direct communication with a base station (BS),UANET can provide U2U links to reach the BS hop by hop, and thus breaks through the range restriction of BS.However, UANET is faced with many challenges on the reliable communication design including intermittent links, changeable network topology,and territorial obstacles.

Gankhuyaget al.[19]proposed robust and reliable predictive protocol (RARP) for U2U communication in UANET with the assistance of hybrid omnidirectional and directional antennas.By predicting the location and trajectory of neighbor nodes on omnidirectional transmissions, UAVs can establish directional links with their communication targets and keep tracking them.Once the directional links break,omnidirectional scanning and prediction will be called up to rebuild them.Similar idea of using directional antennas and location prediction for reliable UAV communication is also proposed in DMAC[20],LODMAC[21],and PPMAC[22]protocol.

Directional antenna is a promising technology for UAV communication with the limited energy baecause it forms the radio of a beam towards a conic zone range rather than over all-round areas to sharply decrease the power assumption [23].The key issue of using directional antennas for reliable UAV communication is how to predict location coordinates accurately and efficiently by acquiring location information.In other word, the performance of RARP depends on the accuracy and freshness of the location information collected from local neighbor nodes.However,severe interferences may stop UAVs from collecting enough location messages when large-scale UAVs are deployed.They sharply reduce the predictive accuracy and thus,deteriorate the reliability of UAV directional communication.Besides, UAVs have to disseminate location messages frequently for location tracking of their communication targets.Normally,the frequency is related to the mobility of UAVs.When UAVs fly at high speeds, They have to exchange overweight location messages to update their flying trajectories quickly,which increase overheads.Therefore, the mechanism of distributed message collection in RARP and similar methods becomes the performance bottleneck of reliable UAV communication regarding the high mobility.On the other hand, lacking in global monitoring,UANET is unable to optimize the network resources dynamically and efficiently.

Wenet al.[24] proposed an asynchronous distributed optimization algorithm for delay-constrained path selection.The algorithm requires only local channel information and outdated messages to optimize link capacity and end-to-end delay for UANET.This algorithm ignores the unfavorable effects of largescale network nodes and takes too much time for convergence in the opitmization.Because of the selforganized characteristic of UANET,the nodes are selfish so that they only consider the local optimization instead of the global one.Even worse,they will compete with each other and require a distributed consensus decision algorithm such as game theory[25].However,considering the dynamic topology, UAVs are hard to reach a consensus decision in time, especially in a large-scale network.

Beyond the limitation of ad hoc networking, our work attempts to achieve reliable accessing and seamless connectivity of UAV communication with the assistance of SAGIN infrastructures such as 5G Base Stations(BSs),territorial mobile access points(APs),and low-earth-orbit (LEO) satellites.We firstly propose to utilize the air control center in SAGIN to manage the UAV communication.It is a virtual application deployed on accessing communication infrastructures(5G-BSs,mobile APs,and LEO satellites),which can collect the global UAV information on flight operations and network resources for decision making on selecting optimal access points for UAVs.Instead of passively rebuilding U2U links after the breakdown in UANET,SAGIN infrastructures proactively provide extra U2S and U2G links and act as the relays for UAVs to communication with each other.Hence, if any UAV owns at least one U2S/U2G link accessing to the SAGIN infrastructures,all the UAVs can establish reliable paths with each other though in-network U2U links are broken.

1.2 Contributions

The main contributions of our work are threefold:

1.To the best of our knowledge, this paper is the first to introduce the virtual application of air control center (ACC) in SAGIN for UAV communication.By gathering the global information and making decisions for both current and future states of UAV networks for handover, ACC provides the nearly always-on connection between UAVs and the SAGIN infrastructures to establish reliable CNPC links in most application scenarios.In addition, ACC executes an optimization algorithm to maximize the overall network capacity with the delay constraint.It is updated dynamically to deal with the mobility of UAV and variable communication conditions.

2.In order to choose the optimal access points for UAVs, we introduce the classic knapsackproblem model to formulate the optimization of UAV communication with SAGIN infrastructures to maximize the overall link capacity with the low-latency constrained.

3.With the estimations of channel models, link capacity,and delay as the input parameters,we propose the predictive decision algorithm to provide the sets of optimal access infrastructures in the current and future time slots for the UAV.Accordingly,the handover strategy is proposed to further enhances the reliable communication with seamless connectivity by the smooth transitions among soft handover, tracking hard handover and nontracking hard handover.

1.3 Paper Organization

The remaining of this paper is organized as follows.We firstly describe the system structure and ACC operation in Section II, and formulate the mathematical modelling for the resource optimization problem of UAV communication on link capacity and delay in Section III, which is then mapped to a classic 0-1 knapsack problem.Based on the solution,we present the proposed algorithms in Section IV including the predictive decision algorithm and access point handover strategy.Section V presents the simulation results and the analysis of our proposal compared with the existing methods.Finally, the conclusion is summarized in Section VI.

II.SYSTEM STRUCTURE AND AIR CONTROLLING CENTER

2.1 System Structure

As shown in Figure.1,the ACC-based UAV communication system is consisted of the application layer,network switching layer,and accessing layer.

Figure 1. System structure.

Application layer includes the air controlling of UAVs, platform management of the system as well as the data service in UAV payload communication,where air controlling is the most vital application provided by ACC.ACC is a virtual application deployed on infrastructures in SAGIN except for UAVs, which collects the information of flights and communication links in the UAV network,and accordingly makes decisions on choosing the optimal communication infrastructures accessing to UAVs.In detail,three kinds of messages are collected from UAVs:

i)Flight operation messages:position(latitude,longitude, and altitude), velocity, heading in flight, and UAV ID number.All the information comes from onboard devices of the UAV, e.g., the position information is attained by the Global Navigation Satellite System(GNSS).

ii) Network flow monitoring messages:link bandwidth(W),average packet size(K),and average transmission rate of data flow(F).

iii) Auxiliary supporting messages:meteorological database, automatic environmental observation system,and electronic map.

The network switching layer bridges UAV applications with accessing infrastructures and aims to offer the multi-task switching between the air controlling on CNPC links and the data service on payload communication links.

The accessing layer provides dynamic access management for reliable communication between UAVs and infrastructures against the intermittent connections.More details on dynamic access management are described in Section IV.For simplicity, we select 5G-BSs, mobile APs, and LEO satellites respectively as the static ground,mobile ground,and spatial infrastructures of SAGIN in this paper.

2.2 Air Controlling Center

The operations of ACC are illustrated in Figure 2 step by step among UAVs,SAGIN infrastructures,and ACC.Note that the SAGIN infrastructures are denoted as APs(Access Points).

Figure 2. Temporal operation steps of ACC.

Figure 3. Spatial operation steps of ACC.

I.Periodically, UAVs broadcast messages piggybacking the information of flight operations, network flow monitoring, and auxiliary supporting around the accessible counterparts and APs in SAGIN.Equipped on these APs,ACC gathers the information for decision making on choosing the APs available for all the UAVs.

II.When a UAV fails to establish or maintain communication links,it has to broadcast request message to inform accessible APs for rebuilding or recovery.

III.Before APs receive the request message, ACC calculates and updates the set of APs accessible to the UAV.After that,ACC will additionally provides the sets of predictive APs in the future time slots with the estimated information of the UAV.These predictive results ensure the quick response to rebuild or recover connections in case of the abrupt link breakdown.

IV.According to the accessing strategy, one in the set of APs sends response messages to the UAV for accessing.Note that accessing strategies are optional, where the minimum-delay one may be picked up for the delay-sensitive CNPC communication for instance.

V.After receiving the response message, the UAV rebuilds or resumes the communication link with the AP.As simply exemplified in Figure.3, we assume AP-3 is the most suitable access point with the minimum-delay link currently.However,considering the moving direction of the UAV flying path and changing communication conditions,AP-4 may become the most suitable one in the future.The handover of the UAV from AP-3 to AP-4 will be operated if the delay of the link between the UAV and AP-4 is minimum, or the link between the UAV and AP-3 is broken.More details on the handover strategy will be demonstrated in Section IV.

III.PROBLEM FORMULATION

In this section, we focus on choosing the optimal accessing infrastructures dynamically for the UAVs against mobility and changing conditions, in order to maximize the overall capacities of communication links with the constraint of the maximal average latency threshold.This problem of dynamic optimization can be mapped to a NP-complete knapsack one with the complexity of polynomial time.Furthermore,we simplify the problem by introducing more restrictions.The communication channel models of UAVto-Ground(U2G)and UAV-to-Satellite(U2S)are discussed in bybrid Line-of-Sight (LoS) path and Non-Line-of-Sight (NLOS) paths, which are depicted in Figure.4 and followed by the expression of link capacity and delay.For brevity,the time vector of some variables or parameters and the index of UAV is ignored in this section.

Figure 4. Channel models.

3.1 Channel Models

U2G channel modelIn Figure.4,a UAV emits radio signals towards the BS and mobile AP firstly through the free space on the LoS (Light-of-Sight) path until reaching the obstacles in the city, and then through the urban environments on the NLoS (Non-Light-of-Sight) path with shadowing and scattering caused by these obstacles, which attenuate the signal strength.Considering hybird LoS and NLoS conditions,we introduce the model of RF(Radio Frequency)propagation over urban environments[26]and calculte the average path loss of U2G links as follows

wherehis the altitude of UAV,riis the horizontal distance between the UAV and the infrastructure denoted asIi.PLoS(h,ri)andPNLoS(h,ri)are the probability of LoS and NLoS path[27]forIirespectively and are formulated as follows

whereθiis the elevation angle ofIiand is calculated byaandbare parameters of Sigmoid function, a closely approximated model of LoS path.Besides,the channel models with LoS and NLoS links satisfy whereηLoSandηNLoSare the mean additional losses for LoS and NLoS,cis the velocity of light,is the carrier frequency of U2G signals,anddiis the euclidean distance between the UAV andIi,which is calculated by

According to Eq.(2), (3), (4), (5) the average path loss of U2G links in Eq.(1)is formulated in(6)

where

U2S channel modelWe introduce a narrow-band channel model with OFDM transmission for U2S communication[28,29].In this model,the LEO satellite is equipped with uniform planar array (UPA) ofNx × Ny.Considering the wide coverage and expensive bandwidth of the satellite communication for UAVs,we assume that each UAV keeps only one U2S link.Compared with the NLoS one,the LoS path predominates for satellite communication over Ka-band and thus,the frequency domainNx×Nychannel matrix of U2S link is formulated as follows:

whereαis the complex channel attenuation function due to gaseous, cloud, rain or other meteorological conditions;is the carrier frequency of U2S signals;ψiandφiare respectively the azimuth and elevation directions of angles of departure (AoDs) from the satelliteIi, depicted in Figure.4;A(ψi,φi)∈CNx×Nyis the array response matrix,whose(nx,ny)-th element is shown as follows:

where 1 ≤nx≤Nx,1 ≤ny≤Ny,nx,ny ∈N+.

3.2 Link Capacity

Interference prediction [24, 30] is introduced to capture the mobility of UAVs for the calculation of the link capacity.We assume thatfd(di(t)) is the probability density function of the distancedi;di(t)is a function of distance between the UAV andIi;g(h(t),di(t)) is the channel model;t0is the current time and Δτis the period of information gathering by ACC.According to[24],the mean interference prediction between the UAV andIiis formulated as

wheret=t0+Δτand

Considering the multipoint accessing of the UAV,the signal-interference-noise-ratio (SINR) can be expressed in directional-antenna communication model as

Hence, the link capacity between the UAV andIi,denoted asCi,is formulated as

whereWiis the bandwidth of the link withIi.

3.3 Delay

Both propagation and queue delays are considered for the UAV payload communication links withIiand are respectively denoted asand.satisfies

whereandare respectively the time of receiving and transmission the air controlling message within the interval Δτfromt0to(t0+Δτ).

For the queue delay, an M/G/1 queue model is introduced [31].In this model, all packets have an exponentially distributed length with a mean ofKibit for the infrastructureIi.Since the arrival process normally follows the Poisson distribution,an approximate queuing delay for the link between the UAV andIiduring interval Δτcan be expressed as

whereFiis the average rate of data flows forIiand thus,FiΔτis the aggregated payloads over the link.

Hence, according to Eq.(12) and (13), the delay of the communication link between the UAV andIiis formulated as

3.4 Knapsack-Like Problem

In the UAV communication model for knapsacklike problem as depicted in Figure.5, we suppose that there areMaccessing infrastructures, denoted asI1,I2,...,Ii,...,IM ∈Mwhere 1≤i ≤|M|,i ∈N+; and there areNUAVs, denoted asU1,U2,...,Uj,...,UN ∈ Nwhere 1≤ j ≤|N|, j ∈N+.M,Nare respectively the set of accessing infrastructures and UAVs with indexi,jand size|M|,|N|.Note thatM=MG+MS,whereMGis the set of ground infrastructures (5GBSs and mobile APs) andMSis the set of satellites.The air controlling messages betweenIiandUjare collected and delivered on the CPNC links in a period of Δτby ACC.For the UAVUj, the parameters in the messages are as follows:i) relative physical distancesd1j,d2j,...,dij,...,dMj,calculated by the longitude, latitude, and velocity of the UAV;ii) received signal strength indication (RSSI)RSSI1j,RSSI2j,...,RSSIij,...,RSSIMj;iii) the communication range of the UAVRj;iv)the received signal strength threshold of the UAVTHRj;v) the flying altitude of the UAVhj;vi) the current timet0when the message is sent;vii)the time of transmitting and receiving the air controlling message

Figure 5. UAV communication model for the knapsack-like problem.

To transfer the dynamic optimization of UAV communication, we attempt to map the UAV communication optimization into the knapsack problem as follows:i)a UAV can be regarded as a knapsack;ii)accessing infrastructures are like a set of optional items ready for being packed in a knapsack.iii) the capacity of communication links is regraded as the value of items;iv) the latency of communication links is regarded as the weight of items.

Hence,the optimization problem for UAVUjis formulated as

whereCijis the capacity of the payload communication link betweenIiandUjas expressed in Eq.(11);Delayijis the delay of the payload communication link betweenIiandUjas expressed in Eq.(14);Dmaxis the maximum tolerant delay to ensure the QoS of UAV applications;δijrepresents the amount of choosingIiforUj.Normally,there exists only one communication link between a UAV and an accessing infrastructure so that the optimization can be simplified as a 0-1 knapsack problem and thus,δisatisfiesδij ∈{0,1}.Hence,the set{δij·Ii,1≤i ≤|M|}represents the optimal accessing infrastructures for UAVUj.

A dynamic programming solution is utilized for this classic 0-1 knapsack-like problem and described in Algorithm 1.Before the recursion execution of dynamic programming,the input parametersDelayijandDmaxshould be scaled in a scaling factorε ∈(0,1), and rounded in the upper bound of integers.The scaling value ofDmaxis denoted asD.The scaling operations can reduce the time complexity of the solution.Besides, the chosen accessing infrastructures in each recursion of dynamic programming are recorded in the temporary arrayQ, where the rowqiwith the maximum valueCmaxinPare the result and is denoted as ({δij ·Ii,1≤i ≤|M|},Cmax).The complexity of this solution is polynomial time and expressed byO((|M|+1)·D)considering two loops at Line 1 and Line 6.

Actually,Not all theMinfrastructures can establish communication links directly with the UAVUj,unless these links satisfy three restrictions as follows:

i) The communication range of Uj, denoted as Rj:

The UAV is normally power-constrained and limited within a communication range beyond which the connection will disrupt.To ensure the reliable communication between the UAVUjand the ground accessing infrastructureIi,their physical distancedijshould be smaller thanRj.

ii)The threshold of received signal strength:When flying in the low altitude through obstacles on the ground, the UAV have to suffer from the shadowing losses in the communication with 5G-BSs or mobile APs.Also, their links between the UAV and a satellite will be attenuated by cloud, rain or other meteorological conditions.Hence, above-threshold RSSI is imperative for reliable UAV communication.

iii)The maximum sighted range on the ground, denoted as Rs(h):When the UAV flys in a high altitude,the LoS direct communication link may not exist due to the curvature of the Earth.To avoid this problem,the UAVUjin a height ofhjis required to keep a shorter physical distance towards the accessing infrastructures thanRs(hj),which is formulated as

Algorithm 1. The solution of 0-1 knapsack-like problem.Input: |M|,Delayij,Cij(i=1,2,...,|M|),Dmax Output: ({δij ·Ii,1 ≤i ≤|M|},Cmax)Create a temporary array Q to record the sets of chosen accessing infrastructures for UAV Uj in the recursion,whose size is|M|;Create a temporary list Dij and D for the scaling of delay where 1 ≤i ≤|M|;1: for i=0,1,2,...,|M|do 2: Dij =「ε·Delayij■3: end for 4: D =「ε·|M|·Dmax■5: Create a temporary array P for dynamic programming,whose size is|M|×D;6: for i=0,1,2,...,|M|do 7: for d=0,1,2,...,D do 8: if Dij >d then 9: P[i,d]=P[i-1,d]10: else 11: P[i,d] = max{P[i - 1,d],Cij + P[i -1,d-Dij]}12: end if 13: end for 14: Record the chosen accessing infrastructures{δij ·Ii,1 ≤i ≤|M|}in the row qi of Q;15: end for 16: Find the qi with the maximum ofimages/BZ_184_1958_1845_1969_1890.pngimages/BZ_184_1969_1811_2017_1856.png|M|i=1 Cij·δij in P,i.e.,({δij ·Ii,1 ≤i ≤|M|},Cmax);17: return result

whereRErepresents the average radius of the Earth.

In a nutshell, these restrictions for the UAVUjat timet0can be expressed as follows

Accordingly, we can attain a more compact set of accessing infrastructures to establish direct communication links with the UAVUjat timet0.These infrastructures are denoted as a time-varying setMj(t0)⊆Mand the link capacityCijin Eq.(15)satisfies

We consider the time vector in the equation, and hence Eq.(15) can be simplified for UAVUjat timet0as follows:

whereMj(t0) follows the restrictions of Eq.(17), (18) and (19), whileCij(hj,dij,t0,Δτ) andDelayij(hj,dij,t0,Δτ)are respectively simplified asCij(t0) andDelayij(t0).Therefore, the solution of this 0-1 knapsack problem can be expressed as the set{δij(t0)·Ii,1≤i ≤|Mj(t0)|}, which indicates the optimal accessing infrastructures of UAVUjatt0.

IV.PROPOSED ALGORITHMS

In this section, we present thepredictive decision algorithmexecuted by the air control center(ACC).As illustrated in 1,ACC can provide the parameters from flight operation, network flow monitoring, and auxiliary supporting messages based on the air controlling applications as the input for the algorithm.Using the algorithm, ACC is not only able to make current decisions, but also the predictive ones for reliable accessing and resource optimization of UAV communications.With the predictive decisions, we then propose theaccess-point handover strategyfor the seamless connectivity of UAV communication.

Figure.6 describes an application scenario by the predictive decision algorithm in 2D spatial-temporal dimensions,where five APs in the SAGIN infrastructures and four predictive time slots are considered for a UAV.AP-1,AP-2,AP-3,and AP-4 represent territorial 5G infrastructures and AP-5 represents a satellite.

Figure 6. Descriptions of spatial-temporal 2D predictive decision.

In the time slot 0, ACC outputs the set of chosen APs for the UAV by solving the knapsack-like problem whose input parameters are collected from current broadcast information from UAVs, i.e., link capacity and delay.The chosen APs are AP 1-4, which are marked in blue in Figure.6.Among these APs,the UAV choose the one by the strategy with different QoS requirements, e.g., the UAV build the link with AP-3 by following the minimum-delay strategy.

Figure 7. Handover state transitions.

In light of the relative mobility between the UAV and APs with changing communication conditions,predictive decisions on the chosen APs in time slot 1-4 are given for quick response to resume the broken link or rebuild another one according to the handover strategy.In time slot 4, the UAV has to connect with the only AP-5(satellite)with more delays because no territorial APs are available within the coverage.

4.1 Predictive Decision

Predictive decision algorithm aims to offer a sequence of approximate-optimal accessing infrastructures available for the UAV in the future time slots as illustrated in Algorithm 2.

At the current time denoted ast0ort0+lΔτwherel= 0, ACC collects the information by air controlling applications as the input parameters for predictive decision algorithm, including the value ofdij,hj,ψij,φij,t0,Δτ,RSSIij,Rj,THRj,Kij,Fijat timet0;as well as the presupposed value of predictive time lengthL.Lindicates the depth of time for the prediction, namely, the biggerLis, the larger the time scale of the prediction of the decision making on optimal accessing points for UAV communication.The outputs of the algorithm are a sequence of the sets of opitmal APs and expressed as

Algorithm 2. Predictive decision.Input: dij,hj,ψij,φij,t0,Δτ,RSSIij,Rj,THRj,τtij,τrij,Ki,Fi,L.Output:{δij(t0 +lΔτ)·Ii,1 ≤i ≤|Mj(t0 +lΔτ)|}, l =0,1,2,...,L.1: for l=0,1,2,...,L do 2: if l=0 then 3: •Step 1-1: Calculate the set Mj(t0)with the restriction of Eq.(17),(18),(19).4: •Step 1-2: From the remaining accessing infrastructures Ii ∈Mj(t0),calculate the U2G channel loss LU2G and the U2S channel matrix HU2S in Eq.(6)and(7).5: • Step 1-3: Based on the result of Step 1-2,calculate the link capacity and delay in Eq.(11)and(14).6: •Step 1-4: Calculate the set{δij(t0)·Ii,1 ≤i ≤|Mj(t0)|}in Eq.(21)at the current time t0.7: else 8: • Step 2-1: Update the predictive value of dij(t0 + lΔτ), hj(t0 + lΔτ), ψij(t0 +lΔτ), φij(t0+lΔτ)and αij(t0+lΔτ).9: • Step 2-2: Calculate the set Mj(t0 +lΔτ)with only the restriction of Eq.(17),(19).10: •Step 2-3: According to the predictive value in Step 2-1, calculate the U2G channel loss LU2G and the U2S channel matrix HU2S in Eq.(6)and(7).11: • Step 2-4: Based on the result of Step 2-2,calculate the link capacity and delay in Eq.(11)and(14).12: •Step 2-5: Calculate the set{δij(t0+lΔτ)·Ii,1 ≤i ≤|Mj(t+lΔτ)|}in Eq.(15)at the time of t0+lΔτ, l=1,2,...,L.13: end if 14: end for 15: return result

wherel= 0,1,2,...,L.The set forl= 0 represents the optimal APs in the current time slott0and the sets forl= 1,2,...,Lrepresent a sequence of different ones in the future time slotst0+lΔτ.Hence,two cases inl= 0 andl= 1,2,...,Lare respectively discussed and calculated in the current and predictive decisions.In Algorithm 2, Step 1-4 gives the set in current time slot by solving the simplified 0-1 knapsack-like problem in Eq.(21).

To attain the predictive output results, Algorithm 2 updates the value of key parameters at the predicted time by estimating the trajectory of UAVs and the channel attenuation due to various meteorological conditions in Step 2-1.The proposals on UAV trajectory planning and analysis of satellite channel model incorporating weather effects [32, 33] are utilized in the estimations.The updated parameters include the relative physical distancesdij, the flying height of UAVhj,the azimuth and elevation directions of AoDsψij,φijfor satellites and the channel attenuation functionαij.Note that in Step 2-2,Mj(t0+lΔτ) represents a time-varying set with only the restrictions of Eq.(17), (19) since ACC is hard to predict the real-time RSS accurately.Using these values,the predictive results are finally calculated in the future time slots in Step 2-5.

The time complexity of Algorithm 2 is analyzed below.Step 1-1,1-2,and 1-3 takeO(1)time in performing mathematical calculations, while Step 1-4 costsO((|M|+1)·D) time by solving the knapsack-like problem as illustrated in Algorithm 1.Similarly,Step 2-2, 2-3, 2-4, and 2-5 needO((|M|+1)·D) time.Regarding theL+ 1 loops, the time complexity isO((L+1)·(|M|+1)·D).

4.2 Access Point Handover

To ensure the seamless UAV connectivity in SAGIN,ACC is required to keep tracking on multiple APs and to switch dynamically between them for UAVs considering their mobility and changing communication conditions.Predictive decision algorithm provides the optimal APs in the future time slots for the tracking.Based on the predictive results, we propose the handover strategy to realize the seamless connectivity of UAVs by switch the handover states among soft handover, tracking hard handover, and non-tracking hard handover.The handover strategy is shown in Algorithm 3 and the state transitions are described in Figure.7,whose driven interval is Δτ.

We make two assumptions for the handover strategy.Firstly,due to the scarce communication resources and sparse distribution of satellites, we assume that there exists only one U2S link for a UAV.Also,the satellite can provide the last CNPC link for tracking a UAV in unfavourable communication conditions where there exists no accessible ground infrastructures.Secondly,we assume the predictive time lengthLis long enough to cover any interval of the non-tracking hard handover so that the UAV can resume the link with the predictive optimal APs in the handover transitions.

Algorithm 3. Access point handover Strategy.Input: {δij(t0 + lΔτ) · Ii,1 ≤ i ≤ |Mj(t0 +lΔτ)|}, l=0,1,2,...,L Output: MSSj (t0 + lΔτ) for soft handover,MTHS j (t0 + lΔτ) for tracking hard handover or MNHS j (t0+lΔτ)for non-tracking hard handover(l=1,2,...,L).1: for l=1,2,...,L do 2: Calculate the set Mresvj , where Mresv(t0 +lΔτ) = {δij(t0 +lΔτ)·Ii}∩{δij(t0 +(l-1)Δτ)·Ii}, 0 ≤i ≤|Mresvj (t0+lΔτ)|3: if|Mresv j (t0+lΔτ)| ≥1 in Mresvj (t0+lΔτ)then 4: if|Mresv j (t0+lΔτ)|>1 in Mresvj (t0+lΔτ)then 5: Soft handover:6: if {δij(t0 + lΔτ) · Ii} ̸= {δij(t0 + (l -1)Δτ)·Ii}then 7: Calculate the predictive set of soft handover access points at t0 + lΔτ:MSS j (t0 + lΔτ), where MSSj (t0 +lΔτ) = {δij(t0 + lΔτ) · Ii,1 ≤i ≤|Mj(t0+lΔτ)|}-Mresvj (t0+lΔτ)8: UAV Uj decides on whether to switch the access points or not at t0+lΔτ according to MSS j (t0+lΔτ)9: end if 10: else 11: Tracking hard handover:12: UAV Uj chooses the only access point at t0+lΔτ,i.e.,the satellite Ii,which is denoted as the set MTHSj (t0 + lΔτ) where MTHS j (t0+lΔτ)=Ii.13: end if 14: else 15: Non-tracking hard handover:16: UAV Uj glides without connecting with any access points at t0+lΔτ,and thus the set of access points in this case is denoted as MNHS and satisfies MNHS j =∅.j 17: end if 18: end for 19: return result

where 00+lΔτ)|.

(t0+lΔτ)|represents the amount of nonhandover reserved APs, by which the algorithm decides on the handover state as follows:

Soft handoverWhen(t0+lΔτ)|>1,more than one infrastructures are available for the UAVUjto connect with.Ujcan attempt to build a new communication link meanwhile holding the old one in the handover which is seamless andsoftbecause the UAV always maintain the connections with SAGIN infrastructures in this process.The set in soft handover(t0+lΔτ)is formulated as{δij(t0+lΔτ)·Ii,1≤i ≤|Mj(t0+lΔτ)(t0+lΔτ).

Tracking hard handoverConsidering the mobility and changing communication conditions,the UAV cannot always keep the state of soft handover.In other words, it has to cut off the old link with the original AP firstly and then rebuilds a new one.This kind of handover is regardedhardsince the UAV connections with APs are changed unsmoothly, which will cause communication interruptions.However, due to the wide coverage,a satellite can still be accessible although all the ground infrastructures fail to establish links with the UAV.When0+lΔτ)|= 1,only one satellite,which is denoted asIifor instance,is attachable to connect with UAVUjand thus, the UAV can establish a U2S CNPC link withIi.By this link, ACC keeps on tracking the UAV so that it can collect the latest parameters continuously for predictive decisions.

Non-tracking hard handoverWhen(t0+lΔτ)|= 0, UAVUjcannot establish any communication link with the SAGIN infrastructure.In this case,even the satellite fails to build a direct connection to track the UAV and hence, it will just glide blindly for an interval of at least 2Δτwithout air controlling.However, with the assistance of predictive decision,there will be available accessing infrastructures after the blind gliding, and hence the state of non-tracking hard handover will be switched to tracking hard handover or soft handover as shown in Figure.7.

Figure 8. A simulation scenario to validate our proposal against unfavourable conditions, e.g., relative mobility, obstacle blocking,and no ground infrastructures.

Figure 9. Real-time data loss rate (RDLR) vs.time for U2U,U2G,U2S communications.

The time complexity of Algorithm 3 is analyzed below.The calculation of the settakesO(1)time and the calculations in all the handover state costO(1)time with only set operation.Hence, the time complexity isO(L)withLloops considered.

V.SIMULATION RESULTS

To evaluate the performance of our proposals, we introduce the NS-3, an open-source network simulator for the simulation of multiple UAV communication in SAGINs.The main simulation parameters are demonstrated in Table 1.Our algorithms are coded in C++with the simulation performed on an Intel i7-7700 CPU @ 3.6 GHz, 64 bit Ubuntu 20.04 LTS system,16 G RAM computer.

Table 1. Table of Simulation Parameters.

The simulations are twofold.Firstly, a simplified scenario is designed to simulate different communication environments for UAV communication in SAGIN to evaluate the real-time data losses.Secondly,we introduce the cumulative parameters to evaluate the performance of reliability among our proposal,RARP,and the asynchronous distributed algorithm in various scenarios with random factors.In these scenarios,different numbers of territorial base stations are deployed in the uniform distribution, while obstacle blocks are randomly placed.Besides,random way-point is introduced as the mobility model of UAVs.For accurate evaluations, these experiments are performed twenty times each with different random seeds and the simulation results are shown in the mean values.

5.1 Real-Time Data Losses in A Simplified Scenario

We design a simulation scenario to initially validate whether our proposal work or not to achieve reliable UAV communication with the assistance of SAGIN infrastructures against three different unfavourable conditions,including the relative mobility between UAVs,the physical obstruction of direct signal propagation from buildings or mountains, and unavailable territorial fixed infrastructures in rural areas.As described in Figure.8, this scenario is composed of three phases with 220 seconds in total, including relativemobility phase(0-90 s),obstacle-blocking phase(90-150 s), and none-ground-infrastructure phase (150-220 s) with 3 UAVs, 6 ground base stations, and one HAP deployed within an area of 4500×10500×5000m3.

Respectively, UAV-1, UAV-2, and UAV-3 locate at the coordinate of (0, 2750), (0, 1750), and (2250,2250).UAV-1 starts to fly with an angle of 36.87 degrees until the 50th second and then changes the angle to 0 degree, while UAV-2 starts to fly at an angle of -36.87 degrees until the 50th second and then changes the angle to 0 degree.At the 50th second,UAV-3 starts to fly with the angle of 0 degree.All of them keep the altitude of 1000 m.BS-1, BS-2, BS-3,BS-4,BS-5,and BS-6 are respectively deployed at the coordinate of (1250, 2750), (1250, 1750), (5250,3750), (5250, 2750), (5250, 1750), and (5250, 750)with wire links connected.For simplicity, we place a fixed High-Altitude Platform (HAP) to guarantee the access at any time instead of the LEO satellite to avoid the irrelevant effects of its mobility.The HAP locates at the coordinate of (8750, 2250) with the altitude of 5000m.Besides,24 solid blocks with the size of 500×500×1200m3are respectively placed as the obstacles in Figure.8.

In the simulation, UAV-1 sends 400 UDP packets every one second to UAV-2.UAV-3 acts as a relay.The received packets with a delay beyond 500 milliseconds are considered lost.Real-time Packet Loss Rate (RPLR) is introduced to evaluate the reliability of UAV communication, which is defined as the ratio between the number of loss packets at the current timet,and the number of sending packets att-1.RPLR is calculated every one second in the simulations.

Independent UAV communication with U2U links,BS-assisted UAV communication wtih U2U and U2G links, and SAGIN-infrastructure-assisted UAV communication with U2U, U2G, and U2S links are compared in the simulation scenario.RARP [19] is introduced in the independent UAV communication to achieve reliable and robust U2U links against relative mobility,which is illustrated in Section 1.1.Our proposed predictive decision algorithm with the handover strategy is used in the latter two cases.

The results are shown in Figure.9.From 0 to the 50th second, UAV-1 and UAV-2 are moving away from each other.Their relative mobility with increasing distance causes data losses.At around the 20th second, the received signal strength is too low to be encoded correctly so that the data packets on the U2U link are all lost and the RDLR becomes 1 in the independent UAV communication.Thanks to the reliable accessing to BS-1 and BS-2 by our proposal,the data losses of the other two communication modes are almost zero.From the 50th to the 90th second, UAV-3 joins in the UAV swarm and then acts as a relay between UAV-1 and UAV-2.Besides,their relative locations keep invariant.Hence, the RDLR decreases to zero in the independent UAV communication.After the 90th second,physical obstacles appear in the simulation scenario and block the U2U links.Therefore,the packets in the independent UAV communication is totally lost in the 90-110 s,120-140 s,160-180 s,190-210 s.These obstacles simulate the buildings in the city or mountains around the suburb.By our proposal,UAV communication links can survive in these obstacles by BS-3,BS-4,BS-5,and BS-6 to keep very low data losses from 90 to 150 s.From the 150th to the 220th second, however, the RDLR of BS-based UAV communication becomes 1 without the assistance of base stations.This phase simulates the rural areas or oceans without the fixed territorial infrastructures deployed.With the wide coverage of the satellite, only the SAGIN-assisted UAV communication can avoid total data losses.

Figure 10. MTR vs.speed of UAVs without obstacles.

Figure 11. MTR vs.speed of UAVs with obstacles.

Therefore,the simulation results initially prove that our proposal can achieve few data losses in UAV communication with the assistance of SAGIN infrastructure against the relative mobility with increasing distances, the physical blocking in signal propagations,and rural areas without territorial infrastructures.

5.2 Cumulative Evaluation of Reliability

In the following experiments, we introduce the message timeout ratio (MTR) and average end-to-end(E2E)delay to evaluate whether our proposal ensures reliable UAV communication or not by accessing to the infrastructures in SAGIN and to prove that it outperforms the comparisons, i.e., RARP [19] and the asynchronous distributed algorithm[24].

MTR is defined as the ratio between the number of packets over timeout threshold and total number of packets in the transmissions.Average E2E delay is the mean value of the transmission time between the senders and receivers in the whole simulation time.Note that retransmissions are included.Lower average E2E delay not only shows better performance in delayconstraint applications,but also implies lower percent of retransmissions.Besides, the number and spatialdistribution of the chosen APs in the knapsack-like optimization may affect the performances of MTR and delay.To evaluate the affection,we set 0,4,and 16 territorial base stations respectively for the simulations.Additionally,obstacles,high mobility,and sparse distribution are three main factors that weaken the reliability of UAV communication.Therefore,we consider different numbers of UAVs at different speeds in the scenarios with or without obstacles in the simulations.The obstacles are 500×500×2500m3blocks and randomly deployed in the scenario.

5.2.1 The mobility of UAVs

Normally, high relative mobility among UAVs leads to frequent link interruptions, and thus increase timeout packets and retransmissions.Hence, we compare the performance of MTR and average E2E delay by our proposal,RARP,and the asynchronous distributed algorithm with the UAVs flying at the speeds ranging from 10 to 50 m/s.

RARP enables the local maintenance and passive repair to intermittent U2U links.This method achieves quick recovery of old links,but reacts slowly to rebuild the new ones in lack of the global information of the whole UAV swarm.Hence, it only works well in the scenarios with frequent time-variable link breakdowns due to physical obstacles or relative mobility.

The asynchronous distributed algorithm attempts to select the optimal routing paths dynamically with outdated channel information to reduce E2E delay and timeout transmission messages.However, the mobility of UAVs is not considered in the optimization,which decreases the convergence rate of the algorithm and thus causes slow reaction to the link breakdowns.Also, the mobility leads to rapid changing network topology.A lack of the latest information will deteriorate the performance of the algorithm.

Our proposal includes both the global ACC-based predictive decision on selecting the optimal access points among SAGIN infrastructures with the mobility and changing communication conditions considered,and handover strategy to switch the links between the UAVs and access points seamlessly.The predictive results provide available assess points in both current and future time slots for UAVs to easily recover from old links or build new ones with smooth handover against the changing communication environments.To this end, our proposal overcomes the weakness of RARP on the slow reaction to build new links,and performs better than asynchronous distributed algorithm against changing communication environments due to high mobility.

The results of MTR and average E2E delay for different speeds of UAVs are shown in Figure.10,11 and Figure.12, 13 respectively with their averages presented in Table 2 and 3.The curves of MTR tend to rise as the increase of UAV speeds for all the methods in Figure.10 and 11.Because the UAVs with higher speeds will move beyond the range of their packet senders more easily,and thus leads to more failures of U2U links.To this end, the percent of lost messages will increase.Compared with RARP and the asynchronous distributed algorithm, our proposal sharply reduces timeout packets.Averagely,the reduction percent achieves up to 84.32%in the scenario without obstacles and 80.83%with obstacles in Table 2(BS=4).Additionally, our proposal performs differently for 0,4,and 16 base stations in the scenarios with obstacles.In Figure.11, the MTR in the scenario with 16 base stations is the lowest because more base stations pro-vide better and more accessing choices for UAVs to overcome the bad effects from obstacles.Even if in the scenario with only one satellite (i.e., 0 base stations),our proposal is still workable and performs better than RARP and asynchronous distributed algorithm.

Table 2. MTR vs.speed([10,5,50]m/s),number of UAVs=60.

Table 3. Average E2E delay vs.speed([10,5,50]m/s),number of UAVs=60.

Both Figure.12 and Figure.13 demonstrate that the average E2E delay increases as UAVs fly at higher speeds for all three methods.Because the link quality between UAVs with faster speeds tends to deteriorate and leads to more retransmissions, hence increasing the transmission delays at the intermediate relay nodes.Among the three methods, RARP performs the worst for not considering the optimization of delay in recovering transmission paths.As shown in Table 3, our proposal (BS = 4) achieves approximate performance to the asynchronous distributed algorithm and outperforms RARP by more than 24%on average for two reasons.Firstly, the delay is considered in the selection of optimal access points by solving the knapsack-like problem.Secondly, predictive decision and handover strategy reduce data retransmissions in UAV communication,and thus achieve lower E2E delay.In addition, obstacles affect little on the performance of average E2E delay.Because the link breakdowns caused by obstacles are instantaneous and easy to be recovered in a short time.

Figure 12. Delay vs.speed of UAVs without obstacles.

Figure 13. Delay vs.speed of UAVs with obstacles.

5.2.2 The Density of UAVs

Low density normally extends the relative distances between UAVs and reduces the successful connection rate of intermediate nodes for multi-hop UAV communications.We compare the MTR and average E2E delay in UAV communication by the methods mentioned above.The simulation results are depicted in Figure.14,15 and Figure.16,17 respectively with their averages presented shown in Table 4 and 5.

Figure 14. MTR vs.number of UAVs without obstacles.

Figure 15. MTR vs.number of UAVs with obstacles.

Figure 16. Delay vs.number of UAVs without obstacles.

Table 4. MTR vs.number of UAVs([30 40 50 60]),speed=50 m/s.

Table 5. Average E2E Delay vs.number of UAVs([30 40 50 60]),speed=50 m/s.

MTR decreases as the number of UAVs increases for all three methods where our proposal performs the best.In detail,our proposal(BS=4)outperforms the asynchronous distributed algorithm by 83.02% without obstacles and 72.81% with obstacles on average.Because the potential access points based on SAGIN infrastructures provide extra U2S or U2G links for UAVs, and thus increase successful connection rates.Also, both the predictive decision algorithm and handover strategy offer proactive reactions towards link breakdowns and sharply reduce the timeout messages.

Furthermore,the MTR of UAV communication becomes lower with more base stations.And obstacles will deteriorate the performance of MTR in UAV communications as shown in Figure.15,since they block the potential intermediate relays.Therefore, more base stations are helpful to decrease the MTR and improve the performance of our proposal, especially in the scenarios with obstacles as shown in Figure.14.

Figure.16 demonstrates that our proposal achieves the approximate performance to asynchronous distributed algorithm and outperforms RARP by 26.66%(BS = 4) as shown in Table 5.However, in Figure.17, the performance of our proposal with BS = 0 becomes worse than asynchronous distributed algorithm.The reason is mainly from the signal blocking of obstacles.Few assistances from ground base stations(BS = 0 indicates no ground SAGIN infrastructures)and low density of UAV nodes lead to higher delay as well.The signal blocking of obstacles increases the possibility of link breakdowns and reduce available APs with lower delay for the knapsack-like optimization in the predictive decision algorithm.Also,the obstacles prevent the establishment of potential direct U2U links,hence increasing the multi-hop data relaying among UAVs with higher delay.Besides,without the assistance of ground base stations,our proposal works worse naturally with few available APs for accessing.In addition, fewer UAVs in the simulation scenario further reduce the direct U2U links,and thus deteriorate the performance as well.More UAVs can alleviate the high delay.When 60 UAVs are deployed,our proposal with BS=0 performs almost the same as the asynchronous distributed algorithm in Figure.17.

Figure 17. Delay vs.number of UAVs with obstacles.

VI.CONCLUSION

In this paper,we have proposed predictive decision algorithm for reliable UAV communication in SAGIN with handover strategy to ensure the seamless connectivity.Also, the dynamic optimization of both link capacity and delay are considered in the predictive decisions by the mobility and channel estimations.Firstly,we propose the concept of air controlling center to collect and update global information of UAVs,and to make decisions on selecting the optimal access points for UAV accessing.We then introduce the knapsack-like problem to model the optimization that maximizes the overall link capacities with the limitation of the maximal average delay threshold of these links.Based on the knapsack-like solution, we have proposed predictive decision algorithm to decide on the sets of optimal access points both at current and predictive future time as the output results.Using the results, we have then proposed the handover strategy for UAVs to maintain the approximately always-on connections with SAGIN infrastructures by switching handover states seamlessly.Simulation results have demonstrated that our proposal outperforms the existing methods and achieves reliable UAV communication against high mobility, sparse distribution, and physical obstacles.

ACKNOWLEDGEMENT

This work is supported by the the National Key Research and Development Program of China under No.2019YFB1803200 and National Natural Science Foundation of China under Grants 61620106001.