Optimization of digital multi-beamforming for space-based ADS-B using distributed cooperative coevolution with an adaptive grouping strategy

Xueyuan LI, Xuejun ZHANG,*, Yuanhao TAN, Jianxiang MA

a School of Electronic Information Engineering, Beihang University, Beijing 100191, China

b Beijing Laboratory for General Aviation Technology, Beihang University, Beijing 100191, China

c Beijing Key Management Laboratory for Network-based Cooperative Air Traffic Management,Beihang University,Beijing 100191,China

d The Beihang University International Center for Innovation in Western China, Chengdu 610218, China

KEYWORDS

Abstract Space-based Automatic Dependent Surveillance-Broadcast (ADS-B) technology can eliminate the blind spots of terrestrial ADS-B systems because of its global coverage capability.However, the space-based ADS-B system faces new problems such as extremely low Signal-to-Noise Ratio (SNR) and serious co-channel interference, which result in long update intervals.To minimize the position message update interval at an update probability of 95% with full coverage constraint,this paper presents an optimization model of digital multi-beamforming for space-based ADS-B.Then, a coevolution method DECCG_A&A is proposed to enhance the optimization efficiency by using an improved adaptive grouping strategy.The strategy is based on the locations of uncovered areas and the aircraft density under the coverage of each beam.Simulation results show that the update interval can be effectively controlled to be below 8 seconds compared with other existing methods, and DECCG_A&A is superior in convergence to the Genetic Algorithm (GA)as well as the coevolution algorithms using other grouping strategies.Overall, the proposed optimization model and method can significantly reduce the update interval,thus improving the surveillance performance of space-based ADS-B for air traffic control.

1.Introduction

Automatic Dependent Surveillance-Broadcast (ADS-B) has gradually become the core surveillance technology in the Air Traffic Control (ATC) field because of its flexible and convenient operation mode as well as its advantages of high accuracy and fast data update.1,2However, for most remote regions in the world, the installation of terrestrial ADS-B systems is neither cost-effective nor efficient.Taking advantage of the global coverage capability of the Low Earth Orbit (LEO)constellation, the space-based ADS-B system can provide global, continuous, and low-latency surveillance service for aircraft.3Unfortunately, the increase in communication distance and wider coverage will lead to extremely low Signal-to-Noise Ratio (SNR) and serious co-channel interference of ADS-B signals, which cannot meet the Required Surveillance Performance (RSP) in busy airspace.4To address those issues mentioned above, a lot of research has been carried out in recent years,mainly focusing on surveillance performance analysis, signal deinterleaving, and digital multibeamforming.

Specific to surveillance performance analysis, Zhang et al.evaluated the accuracy and integrity of the ADS-B information.5Garcia et al.analyzed the effect of co-channel interference on the update interval for space-based ADS-B messages, and established a model of the correct reception probability.6Flight tests and in-orbit technology verification were conducted in 2017 and 2018.7,8Based on Ref.6, Liu et al.introduced the Bit Error Rate (BER) in the aircraft-tosatellite link, and analyzed the relationship among the surveillance capacity, the BER and the required update interval.9,10Su et al.discussed the collision probability of space-based ADS-B signals based on homogeneous Poisson process in 2020.11The research on the analysis of surveillance performance laid a theoretical foundation for the study of multibeamforming methods.

To mitigate the degradation of the surveillance performance caused by co-channel interference, two categories of potential solutions have aroused researchers’ widespread interests.One is the deinterleaving algorithm for processing space-based ADS-B signals, and the other is the use of phased array antennas to spatially separate signals through the multi-beamforming method.In terms of deinterleaving algorithm, Wu et al.12proposed a method to separate the strong and weak pulses of the double interleaved signals.Wu et al.13presented an algorithm on a basis of accumulation and classification.Liu improved the classical Fast Independent Component Analysis (FastICA) algorithm by introducing a loose gene.14However, all these signal deinterleaving algorithms have strict requirements on SNR and computing, which make them difficult to be applied using limited resources of LEO satellites.

Numerous studies have shown that multi-beamforming is the most effective method to mitigate the co-channel interference in space-based ADS-B systems.Conventional beamforming methods based on adaptive criteria can be better used for beamforming of known signal Direction-of-Arrival (DOA)or specific channel conditions, but are not suitable for the detection of arbitrary direction in space-based ADS-B systems.15Bettray et al.designed fixed beams in seven directions by employing four independent antenna panels,and developed an engineering model of this multi-beam antenna for spacebased ADS-B.16Budroweit et al.presented the design and implementation of a multi-channel ADS-B receiver, and discussed the preliminary test results.17Yu et al.established an optimization model for update interval at the update probability of 95% under multi-beam coverage based on Ref.6, in which an adaptive multi-beamforming method was proposed based on the Genetic Algorithm (GA).Furthermore, they designed a Digital Beamforming (DBF) system integrating a 4×4 microstrip array antenna and a 16-channel receiver to reduce signal collisions.18,19Results of their optimization model verified that the beam coverage can be optimized to reduce the update interval according to aircraft distribution.However, their model did not take into account the coverage of all beams,nor the effects of different correct decoding probabilities of signals with different SNRs.In addition, the optimization of adaptive multi-beamforming based on GA is limited by the large parameter scale, and is easy to converge to a local optimum.

To solve the optimization problem mentioned above,Cooperative Coevolution (CC) methods have been proposed and have attracted increasing attention recently.Such methods have been widely used in flight conflict avoidance and Unmanned Aerial Vehicle (UAV) formation reconfiguration.20–22A critical step in the CC framework is parameter decomposition.Yang et al.proposed a CC framework based on a random grouping strategy,23which however cannot effectively solve the problem of interdependency among subcomponents.Wang et al.developed a CC algorithm based on variance priority24and Omidvar et al.investigated a CC algorithm based on the delta grouping strategy.25Yet these two grouping strategies are less efficient if there are more than one non-separable group of variables.Liu et al.recommended a distributed CC algorithm for UAV formation reconfiguration.This algorithm adopted an adaptive grouping strategy based on the variance of each UAV parameters and showed better optimization performance.26

Considering the full coverage constraint of the satellite,this paper analyzes the correct reception probability of space-based ADS-B signals, establishes a multi-beamforming optimization model, and proposed a CC algorithm called DECCG_A&A based on an improved adaptive grouping strategy.The main contributions of this paper are as follows:

(1) An optimization model of digital multi-beamforming for space-based ADS-B is proposed considering the system model and correct reception probabilities.The optimization model can minimize the update interval of position messages at an update probability of 95%under the full coverage constraint.

(2) A distributed CC method called DECCG_A&A is proposed to strategically optimize space-based ADS-B multi-beamforming.The method adopts a dynamic grouping strategy based on the direction of each beam,the mean center of the largest uncovered area, and the aircraft density covered by each beam.The method can effectively improve the algorithm performance and optimization efficiency.

(3) A simulation test that meets the real operation situation is conducted.The simulation scenario is designed conforming to the actual aircraft density distribution collected by Beihang Aviation Satellite-1.The simulation results show that the convergence performance of DECCG_A&A surpasses that of GA and other coevolution algorithms using existing grouping strategies.The core performance metrics, surveillance coverage and update interval, optimized by the proposed model and method, are superior to those in Ref.18.

(4) Based on the proposed optimization model and method,the effects of different parameters,such as the number of beams, the number of aircraft, and the transmit power,on the surveillance performance of space-based ADS-B are further analyzed.

The rest of this paper is organized as follows.Section 2 presents a multi-beamforming system model for space-based ADS-B.Section 3 analyzes the correct reception probability of ADS-B signals, and introduces an optimization model of digital multi-beamforming under the related constraints.Section 4 proposes a CC algorithm and an adaptive dynamic grouping strategy.The simulation results of our research are discussed in Section 5.Finally, conclusions are given in Section 6.

2.System model

This section presents the multi-beamforming reception system model for space-based ADS-B signals.It is derived that the SNRs of such signals are also derived according to the array element pattern,the position and attitude of the array antenna,and the aircraft position.

2.1.Digital multi-beamforming reception model for space-based ADS-B signals

The digital multi-beamforming reception scenario of spacebased ADS-B signals is shown in Fig.1.Each aircraft periodically broadcasts ADS-B signals on 1090 MHz, sending flight status information such as position, altitude, speed, and aircraft identification.27The space-based ADS-B system uses array antennas to receive ADS-B signals by generating multiple virtual beams through DBF and spatial filtering.The DBF significantly reduces the number of aircraft and the signal collision probability in one beam, thus improving surveillance performance.The satellite sends the flight status information back to the ground ATC automation systems through intersatellite links, satellite-ground link, and ground communication links to realize global ATC surveillance.

Assume that the ADS-B OUT transmitter of the aircraft uses an omnidirectional antenna, and the power normalized signal is denoted as sk, i.e.,.The received signals of the satellite array antenna can be written as28

Fig.1 Digital multi-beamforming reception scenario of spacebased ADS-B signals.

where hk?CNE×1is the discrete memoryless channel state from aircraft k to the satellite,Θ denotes the set of all aircraft in the satellite coverage area,Pkrepresents the transmit power of aircraft k, and n ～CN（0，σ2I） indicates the noise vector of the received signals.

Suppose the antenna on the satellite is a rectangular uniform planar array with NEarray elements.The satellite combines the received signals through the i - th weight vector, then the output signal after DBF can be written as

where (a) indicates the useful signal received from aircraft k,(b) represents the interference signals from other aircraft,and (c) denotes the noise.

Postulate that the noise remains independent of the useful signal.The k-th aircraft’s SNR ξk，iof the useful signal under the i-th beam can be expressed as

where σ2and ? are the noise power and the noise figure,respectively.

Enhancing the SNR will increase the correct decoding probability of ADS-B signals.However, the virtual digital beams generated by this method may lead to a large number of aircraft covered in the same beam,resulting in severe signal collisions.Then, the co-channel interference in Part (b) of Eq.(2)will make the correct reception probability of the useful signal much lower.To ensure sufficient SNRs yet reduce the effects of co-channel interference, the coverage of digital beams should be reasonably planned through a weight matrix.The weight matrix contains NbDBF vectors, which can be defined as

Combine the received signals of the satellite array antenna through W, then the output signal can be written as

2.2.Channel model

According to Eq.(3),the SNR ξk，ican be calculated as long as the channel state hkis determined.Assume that the channel between the aircraft and the satellite satisfies the free-space loss formula,the transmitting antenna of the aircraft is an omnidirectional antenna,and the receiving antenna of the satellite is a directional antenna.The channel state hkcan be modeled as

where gkis the equivalent channel gain,f（θk，φk）represents the array element pattern, and akindicates the array steering vector.

The position relationship and coordinate system of channel state analysis for space-based ADS-B digital multibeamforming are shown in Fig.2,where A denotes the aircraft k’s position, S denotes the satellite’s position, and C denotes the sub-satellite point.

As illustrated in Fig.2, the equivalent channel gain gkcan be written as

where γ=2 is the path loss exponent,pSA，kis the relative position vector from the satellite to aircraft k,and λ represents the wavelength of the signal.

The array element pattern f（θk，φk） indicates the amplitude gain in the incident direction, where θk?-90°，90°

The signal from aircraft k is incident in the pAS，kdirection,then the steering vector of the array antenna can be calculated as.

Fig.2 Position relationship and coordinate system.

where vmis the relative position vector from array element 1 to array element m, m ?[1 ，NE].

The channel state hkcan be obtained by introducing Eqs.(7)-(8) and the array element pattern into Eq.(6), then the SNR ξk，iof the received signal can be determined by Eq.(3).

3.Problem formulation

The update interval of position messages at the update probability of 95%is the key performance metric for the space-based ADS-B system, which is related to the correct reception probability.With the objective of minimizing the update interval,a digital multi-beamforming optimization model is proposed considering the coverage constraint of the satellite.

3.1.Correct decoding probability

As demonstrated in the standard established by Radio Technical Commission for Aeronautics (RTCA), the ADS-B signal uses binary Pulse Position Modulation (PPM) encoding, and the format is shown in Fig.3.27An ADS-B message lasts for 120 μs which contains an 8 μs preamble and a 112 μs data block.

Owing to the binary PPM adopted by the ADS-B signal,the BER can be written as29

where Q（?） is the Complementary Cumulative Distribution Function (CCDF) of the standard normal distribution.The probability that the error bits number of the ADS-B signal is n can be expressed as

ADS-B employs CRC with a check digit length of 24 bits and a minimum Hamming distance of 6, so it can achieve a maximum of 5 bits of error correction.We can get the correct decoding probability of ADS-B signals as

Fig.3 ADS-B signal format.27

3.2.Signal collision probability

Most of the avionic systems,such as Mode A/C transponders,Mode S transponders, and ADS-B 1090 ES surveillance systems, transmit Radio Frequency (RF) signals at 1090 MHz,which will cause co-channel interference between each other.6

Claim that aircraft k is covered by the i - th beam, where i ?[1 ，Nb], and the number of aircraft that will cause cochannel interference to aircraft k in the i - th beam is Nk，i.If the proportion of the aircraft equipped with the Mode A/C transponder is αA, the number of the aircraft equipped with the Mode A/C transponder that will cause co-channel interference to aircraft k in the i - th beam is Ak，i=Nk，iαA.Denote the emission rate of the Mode A/C transponder as vA,then the rate at which the interfering Mode A/C signals in the i - th beam reach the satellite is λA，k，i=Ak，ivA.Similarly, we have the parameters of ADS-B and Mode S: Bk，i=Nk，iαB,λB，k，i=Bk，ivB, Sk，i=Nk，iαS, and λS，k，i=Sk，ivS.

Suppose that each aircraft transmits signals statistically independently, each type of transmitter transmits signals in random bursts, and the signal number of each type arriving at the satellite per unit time obeys a Poisson distribution,6,19then the probability that m ADS-B signals arriving at the satellite from the i - th beam during time t can be expressed as

Similarly, the probability PA，k，i（m，t） or PS，k，i（m，t） can be expressed as

The durations of a single ADS-B signal, Mode A/C signal,and Mode S signal are denoted as τB, τA, and τS, respectively.In particular,the Mode S signal indicates the form of its short squitter.Then,the collision probability that one ADS-B signal from aircraft k collides with ηBother ADS-B signals,ηAMode A/C signals, and ηSMode S signals in the i - th beam can be derived as.

3.3.Correct reception probability

According to Eq.(11), the probability PD，k，ithat the ADS-B signal of aircraft k is correctly received by the i - th beam in a ‘‘clear sky” environment can be derived.In the presence of co-channel interference from other aircraft, the correct reception probability is related to the number and type of collision signals,in addition to PD，k，i.If the reception of one ADSB signal is not allowed to collide with other ADS-B signals or Mode S signals, which is a rather conservative assumption adopted in both Refs.6 and 10, then the correct reception probability of the ADS-B signal after collision with other ADS-B signals or Mode S signals is 0.For Mode A/C signals,the minimum reception probability of the ADS-B receiver in the case of interleaving 0 to 3 Mode A/C signals is specified by the standard.6,27Therefore, the reception probability of the signal from aircraft k in the i - th beam can be written as

Assume event Eη，k，iindicates that the ADS-B signal of aircraft k collides with other η signals at 1090 MHz in the i - th beam, and event ER，k，iindicates that the ADS-B signal of aircraft k is correctly received in the i - th beam, then the probability that the ADS-B signal of aircraft k can be correctly received after a collision with other η signals at 1090 MHz in the i - th beam is

where

Then,the probability that the ADS-B signal of aircraft k is correctly received in the i - th beam can be written as.

Note that when η ≥4, PRA，k，i（η ）=0, hence PRbi，kcan be expressed as

Assume aircraft k is covered by n out of all Nbbeams,then the correct reception probability of the k - th aircraft’s signal can be derived as18,30

3.4.Update interval and update probability of position messages

The update interval and update probability of position messages are core metrics for the ADS-B system.Denote the time interval for the aircraft sending ADS-B position messages as T,then the probability corresponding to the time interval Δt between the two adjacent correctly received signals can be expressed as

Therefore, we can get the probability distribution of the k - th aircraft’s position message update interval

where ??」 is the rounding down operator.The cumulative probability distribution of the update interval can be further derived as

Considering the total aircraft number of N covered by the satellite, the probability distribution of the average update interval of all aircraft within the coverage of the satellite can be expressed as

Therefore, we get the cumulative probability distribution.

Furthermore, the update interval at the update probability of 95%for ATC surveillance performance requirements can be expressed as

3.5.Objective function and constraints for optimization

According to the description above,the update interval Δt95%of position messages at the update probability of 95% within the satellite coverage can be obtained.To minimize the update interval, the digital multi-beamforming problem for spacebased ADS-B can be converted into a static optimization problem:

The amplitude and phase constraints of DBF vectors and the full coverage constraint within a given half angle of the satellite need to be satisfied.The elements wj，irelated to the j - th array element of the i - th beam can be expressed as Aj，iφj，i, where Aj，iis the excitation magnitude subject to Amin≤Aj，i≤Amax, and φj，iis the excitation phase subject to φmin≤φj，i≤φmax.Both Aj，iand φj，ineed to be optimized.Then, W can be expanded as

Therefore, the parameters to be optimized for the spacebased ADS-B digital multi-beamforming problem can be expressed as a 2NE×Nbdimensional matrix as

In this paper, we present the full coverage constraint.Denote the elevation and azimuth angle of the incident signal to the antenna array as EL and AZ, respectively, then the single-point coverage function for any position on Earth surface within the half angle of the satellite can be defined as

where PD，i（AZ，EL） is the correct decoding probability of the ADS-B signal broadcast at the corresponding position in the i - th beam under the condition of no co-channel interference.

Denote the desired half angle of satellite coverage as EL0,then a 360× （? EL0」+1）-dimensional coverage constraint matrix can be defined in Eq.(32)

If the required half angle EL0is fully covered by the satellite,the value of each element in C is 0.If an orientation within the half angle EL0is not covered,the value of the element in C corresponding to that orientation is 1.Thus, the full coverage constraint for a given half angle of the satellite can be defined as

where Ci，jis the element of the i - th row and j - th column in matrix C.Finally,the objective function for space-based ADSB digital multi-beamforming optimization can be expressed as

where δ is the full coverage penalty factor.Set δ as a sufficient positive integer, then Jextendwill get a very large value if Nbbeams do not cover the whole area within the given half angle.

4.Optimization framework

This section proposes a distributed coevolution approach called DECCG_A&A to address the problem that GA is not effective in solving large-scale parameter optimization.The approach uses an improved adaptive dynamic grouping strategy based on the locations of uncovered areas and aircraft density under the coverage of each beam.The process of DECCG_A&A is shown in Fig.4.

Fig.4 Flow chart of DECCG_A&A.

4.1.Adaptive grouping strategy

For the space-based ADS-B digital multi-beamforming, the optimization model proposed in this paper has two main objectives.The first objective is to achieve full coverage within the given half angle EL0, and the second is to minimize the update interval of position messages at the update probability of 95%while providing full coverage surveillance.To improve the convergence rate of the optimization algorithm, the adaptive grouping strategy proposed is built based on the following two criteria:

C1: the relative orientation between the mean center of the largest uncovered area and the direction of each beam.

C2: the aircraft density covered by each beam.

The parameters are first optimized by random grouping until all beams form several distinct uncovered regions.Then,grouping is performed by the strategy based on C1, which makes parameters converge to the state of complete coverage.Finally,the grouping strategy based on C2 is employed to optimize the update interval under the full coverage constraint.

4.1.1.Grouping strategy based on C1

The grouping strategy based on C1 can improve the efficiency of achieving full coverage within the half angle EL0of the satellite.The 2NE×Nb-dimensional parameters Ω to be optimized as defined in Eq.(30) can be written as

Assuming there are m uncovered regions,there will be m 8-connected regions within matrix C.31Denote the set of 8-connected regions as Λ= [Λ1，Λ2，???，Λm], then one of the 8-connected regions Λqcan be expressed as.

which indicates that the region contains uquncovered orientations.

where e is the eccentricity of Earth.Assume Λqmaxis the region that has the most uncovered orientations among m uncovered regions, then we have

where Npopis the number of individuals in the optimized population,and εiis the reference vector component generated by the i - th individual.εican be written as

where D′i，jis the Earth surface position that the j - th beam generated by the i - th individual points to, and C～i，qmaxis the mean center of the largest uncovered region generated by the i - th individual.Then, the decision vector ε～of the grouping strategy can be expressed as

The grouping strategy allows parameters Ω to be regrouped as.

where the g1- th subcomponent can be written as.

In addition, the following constraint should be satisfied:

4.1.2.Grouping strategy based on C2

The grouping strategy based on C2 is designed to improve the efficiency of minimizing the update interval.The reference vector μ of the grouping strategy can be defined as

The reference vector component μican be written as

where ρi，jis the aircraft density under the coverage of the j - th beam generated by the i - th individual.Then, the decision vector μ～can be expressed as

The grouping strategy allows parameters Ω to be regrouped as

where the g2- th subcomponent can be written as.

Besides, the following constraints should be satisfied:

The dimension of parameters Ω before grouping is 2NENb.After grouping by the two strategies, the parameters are regrouped into Nb-2 subcomponents with dimension of 6NE.The dimension of each subcomponent is effectively reduced.

4.2.Subcomponent optimization

In this paper,the self-adaptive differential evolution algorithm with neighborhood search(SaNSDE)is applied for subcomponent optimization.SaNSDE mainly contains three steps:mutation, crossover, and selection.The most obvious difference between SaNSDE and GA is mutation operation.

4.2.1.Mutation operation

SaNSDE mutation operation employs a differential strategy of which the mathematical expression can be expressed as

where i≠r1≠r2≠r3, xr1（ge） is the r1- th individual randomly selected in the ge- th generation population, xr2（ge） and xr3（ge）express similar meanings,yi（ge+1）denotes the mutant intermediate generated by the i - th individual in the ge- th generation population after mutation operation,χ ～N（0.5，0.5） represents a random variable subject to a Gaussian distribution,? ～C（1，0 ）indicates a random variable subject to a Cauchy distribution, and β ～U（0，1 ） is a random variable subject to a uniform distribution.

4.2.2.Crossover operation

Crossover operation is to selectively assign the genes in the chromosomes of the ge- th generation population xi（ge） or its mutant intermediate yi（ge+1） by crossover probability CR, and form the crossover intermediate zi（ge+1）.The gene assignment expression is defined as

4.2.3.Selection operation

Selection operation is to decide whether to select the crossover intermediate or previous generation population individuals into the next generation population by comparing fitness values.The expression can be represented as

where xi（ge+1）is the i - th individual in the （ge+1） - th generation population after one iterative cycle of SaNSDE algorithm, and f（?） denotes the objective function.

4.3.Cooperation schema of subcomponents

After subcomponent optimization, each subcomponent produces an intermediate result of optimization.The collaborative decisions of these results are reflected in the process of solving the fitness objective function.The process of the subcomponents’ cooperation schema is shown in Fig.5.

Fig.5 Process of the cooperation schema of subcomponents.

4.4.Computational complexity analysis

5.Simulation analysis

In this section, the convergence performance of DECCG_A&A and GA are compared.Then,the optimization results of space-based ADS-B digital multi-beamforming are analyzed.Furthermore, the coverage effect and surveillance performance obtained by the methods mentioned above are discussed.Finally, the surveillance performance of optimized beams with different beam numbers,different aircraft numbers and different transmit power are analyzed.

The simulation scenario adopted in this paper is based on the real aircraft data received from Beihang Aviation Satellite-1.According to the distribution of real aircraft, the number of the monitored aircraft is expanded to 3000 in the equal proportion.The parameters used in all experiments, as detailed in Table 1,refer to relevant standards and papers,10,27except for the parameters for the experiments analyzing the surveillance performance of optimized beams (as described in Section 5.4).

In addition, all methods based on the CC framework are implemented through multi-threaded programming, and optimization of all subcomponents is computed in parallel to reduce the calculation time.

5.1.Comparison of DECCG_A&A and GA

The first experiment in this paper compares the performance of DECCG_A&A and GA in solving the optimization problem of digital multi-beamforming for space-based ADS-B.

The convergence rate of DECCG_A&A and GA are shown in Fig.6.The convergence curve in red indicates the performance of DECCG_A&A, while the curve in blue representsthe performance of GA.We can find that DECCG_A&A is superior to GA in convergence performance.DECCG_A&A converges between roughly 60–65 generations to form full coverage beams and,gradually reduces the update interval of position messages at the update probability of 95%.GA, on the other hand, converges only when it approaches 150 generations, and the update interval is also significantly worse.

Table 1 Simulation parameters.

Fig.6 Comparison evolution curves of DECCG_A&A and GA.

Fig.7 Update interval and probability distribution of beams optimized by DECCG_A&A and GA.

Table 2 summarizes the statistics of the optimization results obtained after 20 independent runs of the two algorithms.It can be seen that DECCG_A&A converges to a better value with a probability of 100%, while the converge probability of GA is only 55%for achieving the full coverage.In addition,the best result of DECCG_A&A shows that the optimized beams can reach the update interval of 3.5 s, and even the worst result is about 3.8 s.All these results can guarantee full coverage of DECCG_A&A.The shortest update interval obtained by GA can only reach about 4.6 s,and the worst case is about 8 s.Since the value of the penalty factor δ is 1 × 106,the worst optimization result of GA is 7.10× 107,which indicates that there are 71 orientations that cannot be covered by the optimized beams, and the worst coverage rate is only 97.56%.

Fig.7 shows the update interval of position messages and its probability distribution for a typical beam optimization result of DECCG_A&A and GA, respectively.The gray bars and cyan lines show the probability distribution for differentupdate intervals, and the orange curves show the cumulative probability distribution of update interval.The optimized beams of DECCG_A&A provide a shorter update interval for space-based ADS-B surveillance service, with 3.735 s at the update probability of 95%, while the optimized beams of GA have an update interval of 7.192 s.

Table 2 Comparison of the results obtained by DECCG_A&A and GA.

Fig.8 Overall coverage of beams optimized by DECCG_A&A and GA.

Fig.8 shows the overall coverage of 9 beams for one typical optimization result of both algorithms,where the outer red line is the edge of the overall coverage area, the circle surrounded by short black vertical lines shows the range that needs to be covered by satellites, the small purple plus signs represent the positions of all aircraft, and the red pentagram indicates the position of the satellite.The coverage of each beam obtained by DECCG_A&A and GA is respectively shown in Figs.9 and 10, where the red line is the edge of the coverage area of the corresponding beam, and the circles surrounded by short black vertical lines, purple small plus signs, and red pentagrams indicate the same meaning as those in Fig.8.The edge of the coverage area is defined that the correct decoding probability of the ADS-B signal at that position is 90%without cochannel interference.The SNR of the signal received by the satellite can be derived to be 5.6 dB according to Eq.(11).

From Fig.8, we can see that the 9 beams optimized by DECCG_A&A can provide the full coverage with more margin within the given half angle EL0.However, the 9 beams optimized by GA just barely achieve the full coverage, and the intersection of the coverage area of each beam is exactly on the edge of the area.We can analyze the reason fromFig.9 that the beams optimized by DECCG_A&A have shorter update interval.There are more and smaller beams to cover a small part of the area with high aircraft density,such as beams 1,3,5,6,and 9.It can also be noticed that while the main lobe of some beams cover the non-busy airspace,the side lobes of these beams cover a part of the area with the highest aircraft density,such as beam 2,4,7,and 8.The side lobes of these beams form a very small coverage area in the busiest airspace,which can effectively reduce the update interval.Similarly, we can see from Fig.10 that the optimization results obtained by GA also have more beams to form coverage of areas with high aircraft density, such as beam 1, 3, 5, 6, and 9, but the side lobes of other beams are not well directed to the busiest airspace.The side lobes are larger, and thus contribute less to the reduction of the update interval.

Table 3 Comparison of results obtained by different grouping strategies.

Fig.11 Comparison evolution curves of distributed coevolution algorithms using different grouping strategies.

It can be concluded from the above analysis that compared with GA,DECCG_A&A has a faster convergence rate,higher convergence probability, shorter update interval, and better coverage performance in optimizing the digital multibeamforming problem for space-based ADS-B.

5.2.Comparison of DECCG_A&A and other coevolution algorithms based on different grouping strategies

The second experiment aims to verify whether the adaptive dynamic grouping strategy proposed in this paper contributes to the success of DECCG_A&A.In this experiment, DECCG_A&A is compared with other distributed coevolution algorithms based on random grouping, delta grouping, variance grouping, and single-beam grouping.After 20 independent runs, the best, worst, average, standard deviation, and success rates of the algorithms with different grouping strategies are statistically analyzed.The results are shown in Table 3.The convergence rates of the algorithms with different grouping strategies are illustrated in Fig.11.

It can be figured from Fig.11 that the convergence rate of the proposed adaptive dynamic grouping strategy is significantly faster than other grouping strategies.As shown in Table 3, all grouping strategies can make the optimization algorithm converge at a probability of 100% and achieve full coverage.The best, the worst, and the average values of the update interval obtained by using the proposed adaptive grouping strategy are preferable to those obtained by othergrouping strategies.The results obtained by the proposed grouping strategy or the delta grouping strategy are relatively stable with a standard deviation of about 0.1 s,while the optimization stability of the random grouping strategy is the worst with a standard deviation of 0.39 s.Overall, the distributed coevolution algorithm using the proposed adaptive dynamic grouping strategy has higher optimization performance and better optimization results than other algorithms using existing grouping strategies in optimizing the digital multibeamforming problem for space-based ADS-B.

Table 4 Comparison of different methods for digital multibeamforming adopted by space-based ADS-B.

5.3.Comparison of DECCG_A&A and existing methods

This section compares the effectiveness of DECCG_A&A with that of other existing methods,mainly including the method of fixed-beams with uniform distribution and the GA optimization method without the coverage constraint described in Refs.16,18;as well as the method of fixed-beams with uniform distribution under full coverage within the half angle EL0,which is currently widely used in the space-based ADS-B surveillance field.

Table 4 shows comparison of the parameters such as the update interval, the rate of coverage within the half-angle EL0,and the number of the uncovered aircraft after using each method.Fig.12 shows the overall coverage of the beams formed by different digital multi-beamforming methods, and Fig.13 shows the probability distribution and cumulative probability distribution corresponding to each update interval obtained by different methods.

From Table 4, we can see that the multiple beams formed without the coverage constraint cannot completely cover the area within the half angle EL0, and there exists aircraft for which ADS-B surveillance service cannot be provided.The update interval in this case is also the longest.In addition,the update interval obtained by the fixed beams with uniform distribution is relatively worse after considering the half angle EL0, compared with that obtained with GA and DECCG_A&A optimization methods.The model optimized by GA with the coverage constraint can reduce the update interval,while the model optimized by DECCG_A&A with the coverage constraint proposed in this paper can greatly reduce the update interval to 3.73 s.

Fig.12 Comparison of overall coverage of different digital multi-beamforming methods for space-based ADS-B.

It can also be illustrated from Figs.12 (c) and (e) that the method without the coverage constraint cannot achieve full surveillance coverage.Considering the coverage constraint,the results obtained by the fixed beams with uniform distribution,DECCG_A&A,and GA can achieve full coverage within the half-angle EL0and full coverage of all aircraft.However,the method of fixed beams with uniform distribution does not take the uneven distribution of aircraft density into account and does not have a targeted design for beams in busy airspace, which affect the update interval and reduce the continuity of surveillance.

Fig.13(a) shows the probability distribution of the update interval generated by different methods, and the Fig.13(b)shows the cumulative probability distribution.The beams obtained by DECCG_A&A with coverage constraint have a significantly higher update probability of the update interval at 1 s or 2 s than other methods, while a significantly lower update probability of the update interval that is greater than 3 s.We can see from the cumulative probability distribution that the update interval at the update probability of 95%obtained by DECCG_A&A is significantly better than that of other methods.In addition,we can also find that the update interval obtained by the method considering the coverage constraint is shorter than that of the methods without considering the coverage constraint.

5.4.Analysis of impacts of different parameters on performance of space-based ADS-B surveillance

Fig.13 Analysis of update interval of each digital multibeamforming method for space-based ADS-B.

Fig.14 Cumulative probability distribution of update interval with different parameters.

The above experiments demonstrate that the optimization model proposed with the coverage constraint and DECCG_A&A outperform other existing methods.In this section,the impact of different numbers of beams, different aircraft numbers, and different transmit power on the performance of space-based ADS-B surveillance will be further analyzed.

Fig.14 shows the cumulative distribution of the update interval with different parameters.Fig.14(a)shows the cumulative probability distribution curves of the update interval using different beam numbers with 3000 aircraft and transmit power Pk=125 W,and the corresponding performance analysis is presented in Table 5.Fig.14 (b) illustrates the cumulative probability distribution curves of update interval with 9 beams at 125 W transmit power for different aircraft numbers,and Table 6 shows the corresponding performance analysis.Fig.14 (c) figures the cumulative probability distribution curves of the update interval with 9 beams and 3000 aircraft with different transmit power, and the corresponding performance analysis is demonstrated in Table 7.

From Fig.14 (a), it can be seen that the more the beams used in the space-based ADS-B system,the shorter the update interval at the update probability of 95%.As summarized in Table 5,if there are enough beams and the aircraft have a high correct decoding probability, increasing the number of beams can effectively alleviate the co-channel interference of ADS-B signals and improve the correct reception probability by reducing the signal collision probability, and finally reduce the update interval.

From Fig.14 (b), we can see that more aircraft in the coverage area can lead to longer update intervals with the same number of beams and same transmit power.We can analyze from Table 6 that if the beam planning is appropriate,each aircraft in the coverage area has a high correct decoding probability.However, the increase in the number of aircraft will significantly increase the signal collision probability, which greatly affects the correct reception probability of ADS-B signals and reduces the update interval,and thus results in failure to meet ATC surveillance requirements.

It can be seen from Fig.14 (c) that the surveillance performance of the space-based ADS-B system does not become better with the increase in transmit power.We can see that if the transmit power of the aircraft takes the minimum standard of 70 W,the correct decoding probability is relatively low and the full coverage within the half angle EL0is not formed due to the limitation of the antenna gain.However,since the coverage of each beam is relatively small,the signal collision probability is also small.There is still a good update interval at the transmit power of 70 W.If the transmit power increases, the correct decoding probability of ADS-B signals improves while the co-channel interference of signals increases significantly.Once the transmit power increases to a certain level, the continued increase in power will cause serious co-channel interference,which results in a longer update interval.This situation indicates that it is not a good solution to only increase the transmit power when the number of aircraft increases in the future.It is necessary to design the beam number reasonably and optimizebeamforming to provide higher performance surveillance service.

Table 5 Surveillance performance data of different beam numbers.

Table 6 Surveillance performance data of different aircraft numbers.

Table 7 Surveillance performance data of different transmit power.

6.Conclusions

To address the optimization problem of digital multibeamforming for space-based ADS-B, this paper analyzes the correct decoding probability and the signal collision probability of space-based ADS-B signals, and derives the correct reception probability.Considering the full coverage constraint of the satellite, an optimization model is established to minimize the update interval of position messages at the update probability of 95%.In view of the large scale of parameters,a distributed coevolution algorithm DECCG_A&A is proposed based on an improved adaptive grouping strategy to strategically calculate the DBF vectors for space-based ADSB a week or more in advance.This algorithm adopts a grouping strategy based on the relative orientation of the mean center of the largest uncovered area and the direction of each beam, as well as the aircraft density covered by each beam.The following conclusions can be drawn based on the analysis of experiment results.

(1) Compared with GA and other distributed coevolution algorithms using existing grouping strategies, DECCG_A&A has a faster convergence rate and better optimization results when dealing with the digital multibeamforming optimization problem for space-based ADS-B.

(2) The optimization model proposed can effectively achieve full coverage, and has a shorter update interval compared to the methods ignoring the full coverage constraint.

(3) The increase in beam numbers can effectively minimize the update interval for space-based ADS-B surveillance service.Meanwhile, the increase in the number of aircraft will deteriorate the update interval.Increasing the transmit power of ADS-B signals to a certain extent can reduce the update interval.However,if the transmit power exceeds a certain level, the update interval will become longer instead.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.