Scheduling Optimization of Space Object Observations for Radar

Xiongjun Fu, Liping Wu, Chengyan Zhang and Min Xie

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

The orbital elements of space objects provide collision warning and can be used to adjust the launch window of satellites, space stations and spacecraft. The observation of low earth orbit (LEO) objects are mainly carried out using ground-based radars. The effectiveness of space observation radar can be reflected by the ability of new object discovery, observation efficiency, the accuracy of measurement and orbit determination, the quality of radar imaging, and the recognition rate. Specifically, the higher the number of space objects with determined parameters observed in the same time, the higher is the observation efficiency of radar.

It turns out to be an optimization problem to improve the performance of space observation on the constraint of radar resources. There are many previous studies on radar resources management for multiple target detection. G. Van Keuk[1]and Yinfei Fu[2]studied task scheduling for ground-based phased array radar and wireless sensor networks respectively; to select the subset of jobs to be processed during the given planning period and determining the starting time and scan-off angle for each selected job, M.R. Taner[3]studied the problem of scheduling the searching, verification, and tracking tasks of a ground-based three-dimensional military surveillance radar. They scheduled tasks to realize radar resource optimization for common targets, while the issue of observing more targets to improve efficiency was not considered. For space objects, the priori orbital elements can be utilized for observation and tracking, and further optimization can be implemented by prearrangement of observation order. Zhongchao Xu[4]scheduled the space objects according to requirement and equipment constraint to improve the observation efficiency of facilities, without utilizing orbital elements. Hua Liang[5]made simulations on observation objects arrangement using prior orbital elements, while the actual constraints and realizability of facilities were not considered.

Phased array radars with the characteristics of beam agility track multiple objects seamlessly, while the mechanical scan radar has a single beam, and its antenna servo system has the characteristic of inertia. Therefore, for a ground- based mechanical scanning radar, it is necessary to arrange multiple objects observation scheduling reasonably, considering the requirement of observation rate. While the observation scheduling is optimized, the number of observation objects can be maximized during a period of observation time, and a high precision performance for orbit determination can be achieved.

This letter presents an observation scheduling algorithm for multiple objects based on semi-random search. The observation scheduling is screened by a designed fitness function. Additionally the connection time pair (CTP) and the tracks between two objects are determined for mechanical scanning radar. The multiple target observation is equivalent to long-time single target observation, so highly efficient observation is obtained. The scheme of scheduling optimization is shown in Fig.1.

Fig.1 Scheme of scheduling optimization

1 Optimization of the Initial Observation Scheduling Based on Semi-random Search

The visibility of each object should be determined first for an object set to be observed.We define “observation session” as a period of continuous operating time of radar and “observation bin” as a fraction of time. Observation bin is the increment of time to assign observation tasks. Observation session can be uniformly divided into a series of successive observation bins.

Referred to space object parameters provided by satellite situation report (SSR) and two-line element (TLE)[6], the visible object set can then be obtained by analyzing the constraints such as relative position between radar and objects, transmitting power and visual angle. Range, azimuth and elevation (RAE) of all visible objects can be calculated using the simplified general perturbations (SGP4) model[7], and then the visible objects in each observation bin can be obtained.

Designate an object for each observation bin utilizing a random search method and considering the constraints on multiple objects observations. This random search with constraints is called a semi-random search. Initial observation scheduling can so be obtained by using semi-random search. The constraints here mainly refer to observation strategy. The factors include the observation rate (observingLrevolutions duringMdays), object priority and minimum or maximum observation time per revolution or arc. Observation rate is determined by the principle of orbital altitude stratification, importance of objects and the requirement of orbit determination accuracy or radar imaging resolutions[8]. Object priority is set according to observation requirement, the more important the objects are, the higher their priority.For mechanical scanning radar, the servo system constraints should also be considered, which include the elevation range of the antenna, its angular velocity range and angular acceleration range in azimuth and elevation.

“Highest Priority First” and “Earliest Deadline First” are the two main strategies proposed to generate initial observation scheduling by this semi-random search method. “Highest Priority First” refers to the condition that low-priority objects can be selected only after all the high-priority objects are successfully observed. The priority of one object will be adjusted to minimum if its observation rate requirement has been met. Select one object randomly if several objects have the same priority. “Earliest Deadline First” specifies that the object whose observation time expires the earliest should be selected first. The so-called “expired time” is the last time the moment in which the object could be observed in the current revolution.

For mechanical scanning radar, the strategy “Frontier First” should be considered.This refers to the condition that the next neighboring object which becomes present along the scan of antenna beam steering is selected. In this way the burden of antenna servo is reduced. If several objects are the frontier objects, we select one object randomly.

Initial observation scheduling is generated by simulations.Fig. 2 shows the simulation results of 7 objects.

Observation interval：17/12/2013 0:00:00-8:20:00; international number of objects： 01616,04331,22652,22692,23787,27560,27868,32955; time of observation bin is 10 s; number of bins forward search cross：10; time of mean observation span： 6h; priority of each object is 1; observation rateM,L(observeLtimes duringMdays)=(1,1).

Fig.2 Schematic of observation scheduling generation

In Fig. 2, ordinate object1…object7 are the objects mentioned above, and the black blocks represent that the objects are visual to radar.Ordinate observation scheduling 1 and observation scheduling 2 are the results of observation scheduling generation, and the object to be observed corresponding to each observation bin is arranged.

2 Optimization of CTP Based on GA and Track Design for Mechanical Scanning

For the mechanical scanning radar, further optimization is needed due to its inertia of the servo system. The realizability of connection between two objects should be paid attention to. CTP between two adjacent objects in observation order can be optimized using GA, and the tracks in the spare time are designed, following which the seamless observation for multiple targets can be achieved.

The observation on TDM mode for multiple objects is shown in Fig.3.Tobis the minimum observation time of each object;Tspis the spare time without target observation;t′e,iis the end of observation zone of objecti,t′s,i+1is the beginning of observation zone of objecti+1. The end time of objecti, denoted asA, can be set anywhere witht′e,i. The start time of objecti+1, denoted asB, can be set anywhere withint′s,i+1. {A,B} is defined as TCP.Tiis the track of attenna beam from objectito objecti+1.

Fig.3 Observation on TDM mode for multiple objects

GA is an optimization algorithm imitating natural selection and genetic mechanism[9].Genetic algorithm with its evolution mutation strategy has strong global search capability[11]. It operates selection operator, crossover operator and mutation operator on initial population generated randomly. The optimal or local optimal solution can be obtained according to the appropriate fitness function. The selection operator combines the means of best individual preservation and fitness proportionate selection[10]. Crossover operator is a manner of two-point crossover, the cross position randomly generated must be located at the end area of an observation arc. Time increment is mutated by mutation operator at a certain probability to ensure its diversification.

In this paper, GA is applied to optimize CTP by adjusting time increment.Ninitial observation scheduling lead toNobservation scheduling optimized. A final observation scheduling can be determined according to experimental requirement and the value of each element in fitness function. Some factors are required to be considered in the fitness function. The maximum of each factor is 1 for the convenience of weighting.

2.1 Efficiency factors

② Object observation ratio:β=Nob/Nt, whereNobis the number of objects observed,Ntis the total number of objects during observation session.

2.2 Performance factors

① The normalized variance of observation time for each arc:λ=1/(1+varw), where varw=var (Tarc) is the variance of observation time for each arc.

Orbit accuracy requirements, image quality and image resolution requirements can be expressed by performance elements.

2.3 Equipment consumption factor

① The normalized times of beam direction reentrant:ρ=Ma/Mm, whereMais the reentrant time of beam steering trend for observing another object,Mmis the maximum time.

So the fitness function is

(1)

whereq1,q2,…,q6are the weighting coefficients and set by experience.

For each new individual generated, it is verified that the constraints are satisfied in the genetic process. The optimization procedure of CTP using GA is shown in Fig.4.

Fig.4 Optimization procedure of CTP

For mechanical scanning radar, the observation scheduling could be used for multiple target seamless observation only if the azimuth and elevation information of beam in spare time are appended in. Therefore, after the final observation scheduling is determined, the tracks of antenna beam should be designed according to the constraints of the servo system. The track is expressed in Fig.3. The principles of kinematics should be obeyed here. Rotational angular velocity and acceleration should be as small as possible to get smoothed track when motion displacement and spare time are fixed.

The entire scheduling process of multiple objects is completed when all the tracks of antenna beam steering are determined.Finally, the RAE time sequence comprising multiple objects can be obtained, and it can be used as the guidance for the radar observation.

3 Outdoor Experiment and Performance Evaluation

3.1 Overview of the outdoor experiment

The outdoor experiment was carried out on December 17, 2013 using an S-band high-precision observation and measurement radar. This mechanical scanning radar is armed with a Cassegrain antenna and operated on data guidance mode in the experiment. The latest TLE and SSR are adopted.

In the experiment, in order to keep the antenna from being damaged when tracking multiple objects automatically, some parameters value of servo system were reduced by 0.9 times, such as azimuth angular velocity/angular acceleration and elevation angular velocity/angular acceleration. The parameters of antenna servo system are shown in Tab.1.

Tab.1 Parameters of antenna servo system

The experiment was performed with number of objects which could be observed 559, observation session 08:00-10:00,minimum observation time per arc 30 s, observation time range per revolution [180,600] s, observation bin 30 s,observation rate {M,L}={2,2}, times of genetic iteration 200,species size 21,maximum ratio of optimal individual 0.92,mutation probability 0.005, the weighting coefficients in fitness function {q1,q2,q3,q4,q5,q6}={2,3,1,1,1,1}. Here, observation rate and the maximum ratio of optimal individual are set by engineering requirements for space objects observation;times of genetic iteration is determined by experiments, while the times of genetic iteration is over 200, the optimization results will not be better, considering time spent and optimization results, the times of genetic iteration is set 200; mutation probability is set by engineering experience; weighting coefficients are set by experience and engineering requirements, for example,q1is effective observation time ratio, the more important the objects are, theq1is bigger;q3is the average displacement of antenna steering in the spare time, considering the servo system,q3should not be taken too big, or the servo system will be damaged easily.

3.2 Results of the experiment

The effective observation time are 81.48 min within 120 min. 78 objects are expected to be observed in the optimized scheduling, and they were all observed successfully in the experiment. The number of times of antenna direction reentrantMais 52. As an example, the RAE time sequence of 3 objects observed in a 2 min interval is shown in Tab.2. And the statistics of scheduling results of outdoor experiments are shown in Tab.3.

Tab.2 Scheduling results (08:00:00-10:00:00)

3.3 Performance evaluation

78 objects were observed within 120 min, which means the observation efficiency of this mechanical scanning radar is over 10 times higher than that of scanning radar before. The minimum observation time is 20 s and the minimum antenna latency time is 15 s, more than 30 objects can be observed within one hour. The effective tracking time ratio is close to 70%, which means the spare time is lower than one third. If the minimum observation time is 20 s, the maximum observation time is 60 s and the minimum antenna latency time is 15 s. 30 objects could be observed within 30 minutes, and the radar could observe one object in one minute.

Tab.3 Statistics of scheduling results of outdoor experiments

It is verified by more experiments that the expected performance can be obtained by adjusting the weighting factors of the fitness function and other parameters. However, the weighting factors of the fitness function can be optimized by using Greedy algorithm to make the fitness function achieve the maximum in the future.

4 Conclusion

A scheduling optimization algorithm for multi-target observation based on TDM is proposed using priori orbital information of objects. The optimized observation scheduling is obtained by a semi-random search and fitness function screening when using phased array radar. For a mechanical scanning radar, the CTP between objects is optimized via GA and the tracks of antenna beam in the spare time are designed additionally. The issue of scheduling optimization of space object observations by radar was validated during anoutdoor experiment. The experiment results showed that the observation efficiency of the mechanical scanning radar has improved significantly. An important observation here is that if the number of measured targets was big enough and the observation time of each object was shorter, the effective utilization of observation time would be higher. Different optimization results can be obtained by adjusting parameters (like the weighting of coefficients of the fitness function) for different demands such as orbit determination and imaging.

[1] Van Keuk G, Blackman S S. On phased-array radar tracking and parameter control[J]. IEEE Trans Aerosp Electron Syst,1993,29(1):186-194.

[2] Fu Yinfei, Ling Qing.Distributed sensor allocation for multi-target tracking in wireless sensor networks[J]. IEEE Trans Aerosp Electron Syst, 2012, 48(4):3538-3553.

[3] Taner M R, Karasan O E. Scheduling beams with different priorities on a military surveillance radar[J]. IEEE Trans Aerosp Electron Syst, 2012,48(2):1725-1739.

[4] Xu Zhongchao, Huang Yongxuan. A scheduling method for cataloging observation tasks based on greedy algorithm[J]. Journal of Spacecraft TT&C Technology, 2012, 1(1):89-94.(in Chinese)

[5] Liang Hua, Niu Wei.Design and implementation of measurement resource scheduling for space object catalog[J].Journal of Spacecraft TT&C Technology, 2012, 31(1):84-88.(in Chinese)

[6] Space-track. Two line element data [EB/OL].(2013-12-16). http:∥www.space-track.org.

[7] Cho C H, Lee B S.NORAD TLE type orbit determination of LEO satellites using GPS navigation solutions[J].J Astron Space Sci, 2002, 19(3):197-206.

[8] Li Yuanxin, Wu Bin. Study on determination of observation requirements in space objects catalog maintenance [J]. Journal of Spacecraft TT&C Technology, 2005, 24(1): 26-33.(in Chinese)

[9] Capraro C T, Bradaric I, Capraro G T. Using genetic algorithms for radar waveform selection[C]∥IEEE Radar Conference, Rome, Italy,2008.

[10] Arabas J, Bartnik L,Opara K. DMEA-an algorithm that combines differential mutation with the fitness proportionate selection[C]∥IEEE Symposium on Differential Evolution (SDE),Paris, France, 2011.

[11] Wang Shoukun, Li Delong, Guo Junjie, et al. Robot stereo vision calibration method with genetic algorithm and particle swarm optimization [J]. Journal of Beijing Institute of Technology, 2013, 22(2): 213-220.