Resolution of an Antenna-Satellite assignment problem by means of Integer Linear Programming

Resolution of an Antenna-Satellite assignment problem by means of Integer Linear Programming Rafael V´azquez1, Federico Perea2, Jorge Gal´an Vioque3 1Departamento de Ingenier´ıa Aeroespacial y Mec´anica de Fluidos. Universidad de Sevilla (Spain). [email protected]. 2Departamento de Estad´ıstica e Investigaci´on Operativa Aplicadas y Calidad. Universitat Polit`ecnica de Val`encia (Spain). pere[email protected] 3Departamento de Matem´atica Aplicada II e Instituto de Matem´aticas de la Universidad de Sevilla (Spain). [email protected] Abstract Ground station operators have to assign different antennas in their ground stations network to passes of satellites from customers that have requested the use of the network. However, for operators that support a high number of satellites, in many cases these requests yield conflicts (which appear when more than one satellite requests the same time slot on the same antenna). If there are many conflicts, the process of deconflicting (i.e., moving passes to other antennas or sites or cancelling them so that conflicts are avoided) is not very efficient when done manually, due to the large number of interacting requests. Thus, there is a need for an automatic tool that is able to manage the Antenna-Satellite assignment problem for a large number of passes, by considering the problem globally for a given time-frame (for instance, a week). In this paper we propose to address the deconfliction process by means of Integer Linear Programming. Models that take into account the basic deconflicting operations (moving antenna, moving site, shortening, or cancelling), are proposed and tested on real data provided by the company that posed this problem, yielding better results than the solutions obtained by their previous system. Keywords: Deconfliction, Integer Programming, Antenna-Satellite Allocation. Preprint submitted to Aerospace Science and Technology May 14, 2015 1. Introduction Satellite owners need the support of ground networks to be able to upload commands or download gathered data. Increasing data requirements are resulting in a considerable growth of requests of time allocation of satellite passes to ground antennas, particularly those located on strategic geographical locations—for instance, ground stations located close to the poles, which are more frequently accessible to satellite in sun-synchronous orbits (which includes the majority of Earth Observation Satellites, Barret and Curtis (1992)), and thus are experiencing a considerable increase of time allocation requests from customers. While ground networks continue to expand, and build sites in diverse locations throughout the world, the number of satellite customers continues to increase. Also, the appearance of distributed networks of small satellites (Schilling (2009)) could push the capabilities of the networks to the limit. The number of requests is leading to very complex problems of antenna-satellite allocation operations with several peculiarities, which make the assignment planning a cumbersome task if done by hand. The satellite-antenna assignment problem is often called “Satellite Range Scheduling” (SRS) problem, for which some strategies have already been proposed in the literature. Barbulescu et al. (2002) apply the SRS to the US Air Force Satellite Control Network (AFSCN) employing 100 satellites, 16 antennas, 9 stations, 500 requests per day, producing several schedules per day. The considered objective is the reduction of the number of conflicts (typically 120). The authors observed that genetic algorithms performed better. Barbulescu et al. (2004) analyze the SRS both empirically and formally, proving that the problem is NP-complete. They also provide new algorithms improving those in Barbulescu et al. (2002). Later, Barbulescu et al. (2006a) present the evolution of the problem in the last 10 years in the AFSCN. They analyze possible alternatives to the cost function such as minimizing the sum of overlaps. The same group of authors study more heuristics for the SRS in Barbulescu et al. (2006b), combining several algorithms. Chien et al. (2012) studies the concept of timeline and reviews the generic systems that have been developed. Clement and Johnston (2005) describe the SRS for the Deep Space Network (DSN) with 16 antennas, 20 spacecrafts, four-month time-frames, 1650 passes per week. They generate and repair schedules, describing the problem and heuristics for solving it with emphasis in the re-scheduling problem. Corrao et al. (2012) integrate Genetic Algorithms, Graph Theory and Linear Programming in order to build 2 conflict-free plans, and apply their approach to a case study obtained from a satellite service company. Lee et al. (2008) study the scheduling of a single geostationary satellite. Marinelli et al. (2011) formulates the problem as an ILP model, which is declared as infeasible. The problem is solved by means of a Lagrangian relaxation. As a case study they apply their approach to the station Galileo. Schmidt and Schilling (2009) consider academic problems consisting of satellites and stations distributed all over the Earth. They maximize redundancy in order to solve possible failures in communication. They solve a toy example with 6 satellites and 4 stations yielding 51 contact windows. Xhafa et al. (2013) use Struggle Genetic Algorithms and STK. Zhang et al. (2014) propose ant-colony algorithms, solving examples with 17 satellites, 11 to 13 antennas yielding around 400 passes. Zufferey et al. (2008) apply graph coloring algorithms over a set of 500 realistic instances. However, due in part to tradition, and in part to the complexities of the problem, manual elaboration of schedules are still usual procedure for ground networks managers. This problem has also arisen in the context of ground station networks (Schmidt et al. (2008); Bester (2009)) provided by research institutions for small satellites used for academic projects, which usually have some specific needs such as redundancy and flexibility, and therefore require specific algorithms. When planning, it must be taken into account that a given satellite can be supported just by a subset of the available antennas, and during specific time intervals which must be computed by using knowledge of the satellite orbit and the antenna geographical location and allowable positions of Azimuth- Elevation for the antenna (i.e. which region of the sky is accessible for the antenna). Each pass has a default antenna, which is the one requested by the user; this would be considered as the most preferred antenna. Since different users make requests independently of one another, preferred allocations may cause conflicts, i.e., time intervals where requests from different passes overlap on the same antenna. Such conflicts can be addressed by a number of alternatives. First, the preferred option would be reallocating some passes to compatible antennas located in the same site; other options would be changing the pass to another site (which could imply a considerable change in the previously allocated time of access if the new site is far away from the original site), shortening the pass (up to a minimum duration) to accommodate several passes, or, if no other options are available, canceling the pass. These operations might be available only for a subset of passes if there is a number of already allocated passes that must be honored (for instance for preferred 3 clients or previous commitments). It also must be taken into account that some satellites or customers could be of higher priorities than others. In this paper we propose the use of Integer Linear Programming (ILP) models to solve the problem of deconfliction posed by a ground network operator that manages several sites with dozens of antennas, from now on called “the company”. While the scheduling problem has been reported NP complete (Barbulescu et al. (2004)), using our models we have been able to solve in a reasonable time (less than a minute) real-world instances of the problem for realistic dimensions (thousands of passes over dozens of antennas) and time frames (a week) by using an open source ILP solver. The use of Integer Linear Programming modelling has proven fruitful for other space mission optimization problems, such as the problem of swath acquisition planning for multiple Earth Observation Satellites, see Gal´an- Vioque et al. (2011). The remainder of this paper is structured as follows. In Section 2, the problem is formally stated and the notation used throughout the paper is introduced. The different deconfliction objectives, and the resulting models are described in Section 3, formulated as Integer Linear Programming problems. Computational results, taken from real data, are analyzed in Section 4. We finish with some concluding remarks in Section 5. 2. Input data We next show which data are needed on satellites, antennas and passes and which computations are required to formulate the Antenna-Satellite assignment problem. 2.1. Input data The input data of the problem are: •The time-frame for the planning problem is an interval [T0, Tf] given by the initial and final times T0and Tf. At times we might refer to this interval as T(in our case, usually a week). •A set Sof satellites. The orbit of the satellites can be given in any conventional format, for instance given as Two-Line Elements (TLEs) for a certain epoch (which should be close to the time-frame to be able to precisely determine the passes). 4 •A set A={A1, ..., Ana}of antennas, given by their geographical locations. Antennas which are geographically close to each other are considered to be in the same site, whereas antennas located far away from each other are in different sites. For each antenna, we also assume that we know its admissible range of Azimuth-Elevation, which would depend on obstacles and local geography (for instance mountains) and the required minimum elevation above the horizon to avoid atmospheric effects. This is mathematically formulated as the set Ωa={(Az,El)} of accessible points in the sky given by their azimuths and elevations. •Other relevant input data include the minimum duration for a pass to be considered valid tminsa (which can depend on the satellite and antenna) and the set of compatible antenna-satellite pairs C ⊂ A × S. 2.2. Computation of passes The next step to formulate the problem is to calculate the set of possible passes for all satellites Sand antennas A. For each revolution of satellite s∈ S over the Earth we obtain a pass Pwhen there are time intervals of the form [t0, t1]⊂Tduring which a satellite is accessible for one or more antennas a∈ A, given that the duration of the accesses, t1−t0, is greater or equal than the minimum duration tminsa and the antenna is compatible with the satellite requirements, i.e. (a, s)∈ C. We assume that there is an antenna to which the pass is originally assigned; the possible antennas to which the pass can be assigned (different from the original one) are called alternative antennas. To compute the passes, the first step is to propagate the orbital elements of the satellites during the mission time-frame. This can be done using any of the many possible methods available in the literature, which incorporate more or less accurate models of orbit perturbations (see for instance Vallado and McClain (2007), and references therein). Once the elements are known at all times t∈T, the vector position ~rs(t) in the geographical reference frame (that rotates with the Earth) can be computed (Curtis (2009)), for all s∈ S. Then, using the antenna geographical coordinates the vector position of the antennas ~rafor all a∈ A can be also computed. Then, by projecting the relative position of the satellite with respect to the antenna, ~ras(t) = ~rs(t)−~raon the topocentric frame centered in the respective antenna, one can compute the azimuth and elevation for each compatible antennasatellite pair, (Azas(t), has(t)) for (a, s)∈ C. Each of the time intervals 5 in which (Azas(t), has(t)) ∈Ωafor at least the minimum duration tminsa constitutes an access which will give an alternative to the pass. Satellites will generate a pass only each time the groundtrack passes close to a given antenna (for most locations once or twice a day). Notice that oftentimes satellites will have sun-synchronous orbits since these are the most frequently used orbit for Earth Observation Satellites (due to constant lighting properties), which transmit large amounts of data and therefore constitute a large amount of the satellites requesting passes. Given that these satellites have almost-polar low orbits, it is advantageous to locate bases close to the poles of the Earth, since then one would obtain passes on most orbit revolutions (around 13 passes each day). 2.3. Additional input data for the passes Once the passes have been computed, we have sets P={P1, . . . , Pnp},A= {A1, ..., Ana}consisting of nppasses and naantennas, respectively. The time interval that each of these passes Picovers in a given antenna Akis given by the intervals [αi k, βi k]. Passes are classified as accepted or free. In the first case, the requested antenna and time slot are considered to be fixed, while for free passes, one is allowed to change the requested conditions (antenna requested, pass length), or even to cancel them in order to improve the conflicts status. The following parameters are additional input data for our problem: •F⊂ {1, . . . , np}is the set of free passes, i.e., passes which can be modified with respect to the original request. •pik : priority of pass Piin antenna Ak.pik < pi0kmeans that Piis more preferred than Pi0for antenna Ak. •aik : minimum length of time in which Pimust be active if antenna Ak is to get its data (Such length of time includes pre and post-processing times, which depend on the satellite-antenna pair.) •The binary parameter eik takes the value 1 if pass Piis originally requested to be assigned to antenna Ak. We assume that Pna k=1 eik = 1 for every pass Pi, that is, originally pass Piis assigned to one and only one antenna. •Ciis the set of antennas which have access and are compatible with pass Pi.The binary parameter cik takes value 1 if pass Pihas access 6 and is compatible with antenna Ak, and 0 otherwise. In other words, cik = 1 if and only if k∈Ci. •(αi k, βi k) is the period of time in which pass Pihas access to antenna Ak, k ∈Ci. 2.4. Computation of time intervals Once all the passes have been computed and the input data on the passes has been gathered, the formulation of the Antenna-Satellite assignment problem requires the analysis of the different time intervals in which, for a given antenna, possible passes can overlap. •For each antenna Ak, we consider the intersections of all possible intervals of time (αi k, βi k) of compatible passes. The result is ns(ns≤ 2np−1) intervals I1k, . . . , Insk,with lengths l1k, . . . , lnsk. The intervals are sorted in such a way that the beginning of interval Ij k is equal to the end of interval Ij−1,k, or larger if there is a “gap” during which no compatible passes exist for the antenna. •Sik ⊂ {1,2, . . . , ns}is the set of indices of the sorted intervals {Ijk, j = 1, ..., ns},in which Pican be active in antenna Ak. Taking into account the accepted (fixed) passes, in some intervals, the antenna will already be occupied by these accepted passes, and thus, by construction, for such intervals Ijk we have j6∈ Sik. We show a simplified example of such a timeline in Figure 1, which considers three passes (p1,p2and p3) and two antennas (A1and A2). For the sake of simplicity the passes could be located in either antenna with the same start and end times. From the figure we see that the beginning of p1 in either antenna is α11 =α12 =t0, the ending of p1is β11 =β12 =t2, and similarly for p2we have α21 =α22 =t1and β21 =β22 =t4, and for p3we have α31 =α32 =t3and β21 =β22 =t5. The resulting intervals for both antennas are I11 =I12 = [t0, t1], I21 =I22 = [t1, t2], I31 =I32 = [t2, t3], I41 =I42 = [t3, t4] and I51 =I52 = [t4, t5]. Assuming no passes are fixed we have S11 =S12 ={1,2},S21 =S22 ={2,3,4}and S31 =S32 ={4,5}, which means that the first pass spans (in either antenna) the time intervals 1 and 2, the second pass the time intervals 2, 3 and 4, and third pass the time intervals 4 and 5. If Figure 1 represents the originally proposed schedule then we see there is a conflict in antenna 1 between passes 1 and 2, which can 7 be trivially resolved either by moving pass 1 to antenna 2 (solution 1) or by switching antenna between passes 2 and 3 (solution 2), as show in Figure 2. I5 A1 A2 conflict p1 p3 p2 t0 t1 t2 t3 t4 t5 I1 I2 I3 I4 Figure 1: Simple example of construction of time intervals and conflict. t3 p2 p1 p3 solution 1 A2 A1 A2 A1 solution 2 p1 p3 p2 t4 t5t0 t1 t2 t3 t4 t5 I1 I2 I3 I4 I5 I1 I2 I3 I4 I5 t0 t1 t2 t3 p2 p1 p3 solution 1 A2 A1 A2 A1 solution 2 p1 p3 p2 t4 t5t0 t1 t2 t3 t4 t5 I1 I2 I3 I4 I5 I1 I2 I3 I4 I5 t0 t1 t2 Figure 2: Two possible solutions for the example. 3. ILP Models The models developed here aim at solving conflicts. A conflict is produced if there is an overlap, i.e if over the same time interval, two passes are assigned to the same antenna. Using our notation, this occurs when there exist an antenna Akand an interval Ijk such that X i∈P:j∈Sik eik >1. When conflicts are found, the company requires that one of the following three deconflicting operations is done: 8 1. Moving passes to a different antenna (see Section 3.1) which could be in the same site or in another site. 2. Shortening a pass time allocation on the antenna (Section 3.2). 3. Cancellation of passes (Section 3.3). These operations are written in order of preference, i.e., first, if possible, conflicts should be addressed by moving passes to antennas different to the default ones (and if possible within the same site). Only if conflicts exist after this operation, some passes should be shortened (taking into account the minimum duration of a pass). Still, if some conflicts persist, some passes (beginning with those with lower priority) should be canceled until a feasible solution is found. In what follows we formulate an integer linear programming (ILP) model that includes all the possible deconflicting operations and at the same time optimizing a performance index directly related with the priority of the different satellites. 3.1. Moving passes to a different antenna We address the problem of re-allocating free passes to antennas so that conflicts disappear. Priorities of the different passes are taken into account. Our ILP model uses the following binary variables: •For each i∈F, for each k∈Ci,i.e., for each free pass and compatible antenna, define the binary variable yik which takes the value 1 if pass Piis assigned to antenna Akand 0 otherwise. The constraints of the model would be: •Every free pass has to be assigned to one and only one antenna. X k∈Ci yik = 1,∀i∈F. (1) •For a given antenna Akand a time interval Ij k available for free passes, i.e., with ∪i∈FSik 6=∅,there should be no conflict among the nppasses. X i∈F:j∈Sik,k∈Ci yik ≤1,∀k, j :∪i∈FSik 6=∅.(2) 9 •To solve the resulting ILP problem, the free-software package Lpsolve solver was used. We have used version 5.5.2.0 for windows 32 bits( http://lpsolve.sourceforge.net/5.5/). •All experiments were run on a laptop, Intel Core i7 2 GHz and 4 GB of RAM memory, O.S. Windows 7 Professional 32 bits. The following straightforward conclusions to these results can be noted : •On average, 2605.2 passes were analyzed in each instance with 287.9 conflicts. The corresponding problems had 9154.7 variables and 9013.7 constraints. The average computational time required to solve these problems was 64.8 seconds. •Only 3.13% of passes were canceled. •Only 0.02% of passes were shortened (note however that many of the passes did not allow for shortening). •19.32% of passes were moved to other antennas (0.38% to other site). From the results cast in table 1 we can affirm that the algorithm proposed in this project provides a real time (around a minute) optimal solution for problems of considerable size (up to 4000 passes) that typically correspond to a full week of operation. The computation time does not correlate directly with the size or the number of conflicts but depends more on the complexity of the conflicts. The operation constraints and priorities have been efficiently integrated in the modeling and different adjustments can be achieved by tuning the cost weights according to the specifications of the passes. 5. Conclusions In this paper we have introduced Integer Linear Programming models to efficiently manage the scheduling of passes for a multi-antenna, multi-site ground network serving numerous customers. A dramatic growth in the number of requests has rendered manual scheduling planning virtually unfeasible. The aim of our methods is to solve conflicts in the best possible way while respecting preferred assignments and priorities. A conflict appears when, over 16 the same time interval, two or more passes are scheduled to the same antenna. Several possibilities can be applied to solve such conflicts: movement of passes to other antennas (possibly located on other sites), shortening of acquisitions or cancelation of passes. We have modeled these problems using a basic tool of operations research: Integer Linear Programming. Our models have been tested over a number of realistic instances provided by the ground network operator, which was previously scheduling the passes manually. Conversations with the company representatives let us know that the performance of our procedures exceeded the operator’s expectations in terms of speed and quality of solutions (few number of movements, even fewer number of cancelations) with respect to their previous manual system. Among future possible refinements, we could mention the inclusion of additional objectives, such as fairness criteria (penalizing multiple cancellations for the same customer) or the development of advanced tools such as adaptive online scheduling (which would imply an scheduler running online with capabilities such as including last-minute requests for passes as they come, or immediately adapting to dynamic constraints, for instance, antenna failures). Acknowledgments The authors acknowledge the cooperation of Taitus Software (www.taitussoftware.com) and its team and in particular its founder and CEO (Felipe Mart´ın Crespo), which introduced this problem to us and provided integration with its orbital mechanics visual software SaVoir. We also acknowledge the cooperation of Kongsberg Satellite Services AS (KSAT). JGV acknowledges financial support through grants MTM2012-31821 and P12-FQM-1658. References Barbulescu, L., Howe, A., Whitley, D., 2006a. Afscn scheduling: How the problem and solution have evolved. Mathematical and Computer Modelling 43, 1023–1037. Barbulescu, L., Howe, A. E., Watson, J. P., Whitley., L. D., 2002. Satellite range scheduling: A comparison of genetic, heuristic and local search. Lecture Notes in Computer Science 2439, 611–620. Barbulescu, L., Howe, A. E., Whitley, L. D., Roberts, M., 2006b. Understanding algorithm performance on an oversubscribed scheduling application. Journal of Artificial Intelligence Research 27, 577–615. 17 Barbulescu, L., Watson, J.-P., Whitley, L., Howe, A., 2004. Scheduling spaceground communications for the air force satellite control network. Journal of Scheduling 7, 7–34. Barret, E., Curtis, D., 1992. Introduction to Environmental Remote Sensing, 3rd Edition. Springer. Bester, M., 2009. Automated multi-mission scheduling and control center operations at uc berkeley. In: IEEE Aerospace conference. pp. 1–12. Chien, S. A., Johnston, M., Frank, J., Giuliano, M., Kavelaars, A., Lenzen, C., Policella, N., June 2012. In: The 12th International Conference on Space Operations. Stockholm, Sweden. Clement, B., Johnston, M. D., 2005. The deep space network scheduling problem. In: Press, A. (Ed.), IAAI. Pittsburgh, PA, USA. Corrao, G., Falone, R., Gambi, E., Spinsante, S., 2012. Ground station activity planning through a multi-algorithm optimisation approach. In: IEEE First AESS European Conference on Satellite Telecommunications (ESTEL). Rome, Italy. Curtis, H. D., 2009. Orbital Mechanics for Engineering Students, 2nd Edition. Butterworth-Heinemann. Gal´an-Vioque, J., V´azquez, R., Carrizosa, E., Vera, C., Perea, F., Mart´ın, F., 2011. Towards a visual tool for swath acquisition planning in multiplemission eoss. In: IWPSS 2011 Workshop Proceedings. Darmstad, Germany. Lee, S., Jung, W. C., Kim, J.-H., 2008. Task scheduling algorithm for the communication, ocean, and meteorological satellite. ETRI Journal 30 (1), 1–12. Marinelli, F., Nocella, S., Rossi, F., Smriglio, S., 2011. A lagrangian heuristic for satellite range scheduling with resource constraints. Computers & Operations Research 38, 1572–1583. Schilling, K., 2009. Earth observation by distributed networks of small satellites. In: International Conference on Instrumentation, Communications, Information Technology, and Biomedical Engineering (ICICI-BME). 18 Schmidt, M., Rybysc, M., Schilling, K., 2008. A scheduling system for small ground station networks. In: SpaceOps 2008 Conference hosted by ESA and EUMETSAT in association with AIAA. Schmidt, M., Schilling, K., July 2009. A scheduling system with redundant scheduling capabilities. In: Third IEEE International Conference on Space Mission Challenges for Information Technology. Pasadena, California, USA. Vallado, D., McClain, W., 2007. Fundamentals of Astrodynamics and Applications, 3rd Edition. Microcosm Press/Springer. Xhafa, F., Herrero, X., Barolli, A., Barolli, L., 2013. Evaluation of struggle strategy in genetic algorithms for ground stations scheduling problem. Journal of Computer and System Sciences 79, 1086–1100. Zhang, Z., Zhang, N., Feng, Z., 2014. Multi-satellite control resource scheduling based on ant colony optimization. Expert Systems with Applications 41, 2816–2823. Zufferey, N., Amstutz, P., Giaccari, P., 2008. Graph colouring approaches for a satellite range scheduling problem. Journal of Scheduling 11, 263–277. 19 Passes Conflicts Cancellations Shortenings Movements total (other site) Variables Constraints Time (s) 3356 537 116 1 839 (13) 8090 9322 64 3066 196 75 3 703 (5) 11219 12157 61 3356 231 94 0 517 (6) 12465 12245 73 3566 306 114 1 561 (11) 12360 12714 73 3470 253 100 0 557 (17) 12016 12788 80 3408 196 91 0 478 (5) 12289 12025 71 1573 68 0 0 487 (7) 7143 4467 64 384 33 21 0 101 (0) 1247 1075 22 1586 6 2 0 479 (2) 7892 4964 63 2287 1053 250 4 312 (35) 6820 8380 77 Table 1: Deconflicting results on 10 real scheduling problem instances. 20