[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
Fuzzy Overclustering: Semi-Supervised Classification of Fuzzy Labels with Overclustering and Inverse Cross-Entropy
Next Article in Special Issue
Control of Microalgae Growth in Artificially Lighted Photobioreactors Using Metaheuristic-Based Predictions
Previous Article in Journal
Plant Leaf Detection and Counting in a Greenhouse during Day and Nighttime Using a Raspberry Pi NoIR Camera
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Sensors
Volume 21
Issue 19
10.3390/s21196660
sensors-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Study of Distributed Earth Observation Satellites Mission Scheduling Method Based on Game-Negotiation Mechanism

by
Lihao Liu
1,
Zhenghong Dong
2,*,
Haoxiang Su
1 and
Dingzhan Yu
1
1
Graduate School, Space Engineering University, Beijing 101416, China
2
School of Space Information, Space Engineering University, Beijing 101416, China
*
Author to whom correspondence should be addressed.
Sensors 2021, 21(19), 6660; https://doi.org/10.3390/s21196660
Submission received: 19 July 2021 / Revised: 19 September 2021 / Accepted: 2 October 2021 / Published: 7 October 2021
(This article belongs to the Special Issue Metaheuristic Algorithms–an Effective Way to Optimize the Behaviour of the Dynamical System)
Browse Figures
Figure 1
<p>Scheduling solution.</p> "> Figure 2
<p>Solution coding scheme.</p> "> Figure 3
<p>Emergency targets inserted into the initial solution.</p> "> Figure 4
<p>State update of scheduling plan.</p> "> Figure 5
<p>Test scenario example.</p> "> Figure 6
<p>Payoff and scheduling time. Histogram shows the payoff of different algorithms’ optimization results, while the curve shows the scheduling time.</p> "> Figure 7
<p>Comparison of scheduling time between DMSA and CPSOA.</p> "> Figure 8
<p>Gantt chart of dynamic scheduling.</p> ">
Versions Notes

Abstract

:
While monolithic giant earth observation satellites still have obvious advantages in regularity and accuracy, distributed satellite systems are providing increased flexibility, enhanced robustness, and improved responsiveness to structural and environmental changes. Due to increased system size and more complex applications, traditional centralized methods have difficulty in integrated management and rapid response needs of distributed systems. Aiming to efficient missions scheduling in distributed earth observation satellite systems, this paper addresses the problem through a networked game model based on a game-negotiation mechanism. In this model, each satellite is viewed as a “rational” player who continuously updates its own “action” through cooperation with neighbors until a Nash Equilibria is reached. To handle static and dynamic scheduling problems while cooperating with a distributed mission scheduling algorithm, we present an adaptive particle swarm optimization algorithm and adaptive tabu-search algorithm, respectively. Experimental results show that the proposed method can flexibly handle situations of different scales in static scheduling, and the performance of the algorithm will not decrease significantly as the problem scale increases; dynamic scheduling can be well accomplished with high observation payoff while maintaining the stability of the initial plan, which demonstrates the advantages of the proposed methods.

1. Introduction

Driven by the need of more accurate, reliable, and frequent data to study earth science related issues, space engineering industry [1,2,3,4] is facing an architectural change of paradigm. Distributed Satellite Systems (DSS) encompassing several interacting spacecraft are leading the way in applications where monolithic satellites have become obsolete in terms of risk, cost, or even performance [5]. One typical instance is distributed earth observation satellites (DEOS), which involves fleet of satellites to detect the Earth’s surface and lower atmosphere to obtain information [6]. Though with more satisfied revisit times, coverage of larger areas and higher resolution, DEOS constellations are facing new challenges, the core of which is how to coordinate the mission plans for numbers of satellites that are generally heterogeneous [7].
During the past decades, researchers have carried out extensive research on centralized methodologies. Satellites mission planning are usually designed to be executed on the ground with the premise that all the observation requests and resource information are updated in a centralized way. Researchers use methods such as ant colony algorithm [8,9,10], simulated annealing algorithm [11,12], genetic algorithm [13,14,15], tabu search algorithm [16,17,18], etc. to handle the scheduling problem. Although optimal solutions can be obtained under certain circumstances, it is not practical to apply the methods above directly in distributed satellite mission planning due to the following drawbacks. Firstly, computation and memory cost could be extremely expensive as the number of satellites and observation requests increase. Time consumption in one planning period is so high that it cannot satisfy the need for rapid response. Secondly, there is always a time delay between satellites and ground stations; when emergencies (resource malfunctioning, observation failure, etc.) occur onboard, it will take time for mission planning center (MPC) to be informed, which leads to missed observation opportunities. Moreover, these methods always have difficulties in handling situations where observation requests are generated online. Whenever changes occur, the planning process should be resumed completely, which may create conflict with the executed missions in progress and lead to waste of time and resources. Finally, this kind of architecture does not fit the trend of decentralized way of system management and control, and malfunction in the central point may lead to the whole system’s failure. Consequently, new methods using a self-organized mechanism to make DSS work in a more resilient, flexible, and adaptable way are in urgent need, by which a system-level optimal can be reached when agents in the system cooperate with each other based on local and exchange information.
To address the issue above, modeling DSS as multi-agent systems (MAS) is a common trend in many experimental and academic works. The European Space Agency [19] (ESA) has implemented multi-agent system (MAS) technologies in Earth Observation (EO) constellations. Unlike traditional heuristic methods that are well-suited and designed for a fixed number of missions and satellites, multi-agent methods allow for an adaptability and scalability that is not comparable [20]. Other similar work [21,22,23] shows how MAS-related applications can improve system performance and provide negotiation-based self-organizing mechanisms as means to enhance the autonomy of a system. We can find that, after implementing the MAS framework, the definitions of coordination rules or mechanisms can directly determine the quality of DSS. Luckily, game theory [24,25,26], which focuses on cooperation and conflict between rational players, can be perfectly utilized in this kind of problem, and we can see considerable applications of game theory, including unmanned aerial vehicle (UAV), sensor web, electricity management, job scheduling, etc. For example, study [27] introduces game theory based flight control algorithms run by each autonomous UAV to satisfy the need of speedy and dynamic adjustments to swarm operations. Study [28] addresses the cooperation problem in underwater acoustic sensor network (UASN) using game theory-based clustering scheme to balance network energy consumption. Study [29] presents a real-time implementation of a multi-agent-based game theory model for microgrid market operations to monitor, control, and perform the reverse auction process of distributed energy resources (DER). In addition, as more complex systems recently emerged in the real world, networked game theory also gained prominence and showed great potential for application in socio-ecological systems [30], networked systems [31], project management [32], etc., but surprisingly, relatively little study has focused on implementing game theory in DEOS.
Moreover, dynamic scheduling which focuses on quick response to emergency observation requests, is also a practical issue for EOS applications. Perberton et al. [33] listed four key dynamic elements that can make an impact on change of satellite scheduling plan, namely, mission observation opportunity changes, resource changes, new mission insertion, and scheduling parameter changes, but they did not propose any related models or algorithms. Other related studies seem to reveal a major concern regarding this problem, which is how to consider the adjustability brought by those dynamic elements to the initial plan. Some researchers [34,35] have implemented a complete reprogramming algorithm to solve this problem, but the new plan generated is greatly different from the original one, which may create conflict with the executed missions in progress and lead to waste of time and resources. Cui [16] proposed a multi-satellite dynamic mission scheduling model and used a dynamic scheduling algorithm based on mission priority. When a new mission arrives, this approach will respectively conduct insert, reallocation, and replacement operations to reschedule the plan according to mission priority. Other similar works [36,37,38] propose some mechanisms or strategies to solve the dynamic scheduling problem; overall, these methods reduce the complexity of the dynamic adjustment and maintain the stability of the initial scheduling plan, but the efficiency and scalability can be further improved.
The overall goal of this paper is to design a distributed mission scheduling architecture that can meet the mission-level scheduling needs of heterogeneous multi-satellite earth observation system in both static and dynamic environments. Specifically, we see each satellite as a rational player and convert the satellite mission scheduling into a cooperative game. Aiming at finding a near global optimal solution in a decentralized way, this paper presents a distributed mission scheduling model, which guarantees convergence to a Nash equilibrium. Moreover, we propose a distributed mission scheduling algorithm along with two improved optimization algorithms for satellite mission scheduling in both static and dynamic environments. Finally, case studies are presented to demonstrate the effectiveness of the proposed methods.

2. DEOS Mission Scheduling Model

2.1. Problem Description

The purpose of DEOS mission scheduling is to allocate satellite resources to observation requests to maximize observing revenue while minimizing the resource consumption. Satellite earth observation activities are affected by satellite orbits, payload parameters, platform maneuvering, and other factors. A satellite’s access to the area has periodic characteristics, and only a limited area can be observed at the same time. When the number of satellites and the demands for user observations increase, multi-satellite mission scheduling will turn into a complex combination optimization problem. In order to utilize satellite resources adequately and efficiently, a satellite mission scheduling system must take both resources and user needs into cautious consideration beforehand and output a reasonable scheduling plan without conflicts. For future reference, main notations are defined in Table 1.
Considering the actual DEOS system, this paper makes the following reasonable simplifications and assumptions for the mission scheduling process:
(1)
The observation task involved in this paper refers to the observation of point targets on the ground by satellites using different types of payloads, and a target only needs to be observed once.
(2)
A single satellite carries only one payload. This paper considers two types of payloads, visible light and synthetic aperture radar (SAR). The satellite only executes one mission at one time. Once the mission starts, no interruption is considered.
(3)
Each satellite has computing and processing capabilities, and there is a real-time communication link between the satellites, which can meet the needs of mutual communication and information transmission at any time.
(4)
The situation of satellite orbit maneuver is not considered.

2.2. Scheduling Problem Modeling

2.2.1. Model Constrains

On the basis of the above symbolic parameters, the constraints considered in this paper include:
(1)
Visible window constraints. The satellite payload must be visible to target, and the window duration must not be less than the mission observation time.
∀ i ∈ { 1 , … , n } , j ∈ { 1 , … , m } , s t i j ∈ S t , ∃ w k ∈ W s b t i j ≥ w b t k , s e t i j ≤ w e t k , D u r i j ≤ w d t k
(2)
Slew angle constraints. During task switch, the slew angle cannot exceed the maximum slew angle of satellite.
∀ i ∈ { 1 , … , n } , j ∈ { 1 , … , m } s a i j ≤ s a i
(3)
Task preparation time constraints. The interval between two tasks (the time interval from the end of the previous task to the beginning of the next task) must not be less than the payload preparation time.
∀ i ∈ { 1 , … , n } , j ∈ { 1 , … , m } , s t i j , s t i j + 1 ∈ S t s b t i j + 1 − s e t i j ≥ P r e i j + 1 P r e i j + 1 = ( s a i j + 1 − s a i j ) / S a s i
(4)
Energy constraints. The accumulation of energy consumed by a single satellite to execute tasks and switch tasks cannot exceed the upper limit of the energy storage of the satellite.
∀ i ∈ { 1 , … , n } , j ∈ { 1 , … , m } ∑ j = 1 n u m i P i j ≤ p o w i P i j = D u r i j × P t i + P r e i j × P s i
(5)
Storage capacity constraints. The accumulation of storage consumed by a single satellite to execute tasks cannot exceed the upper limit of the storage capacity of satellite.
∀ i ∈ { 1 , … , n } , j ∈ { 1 , … , m } ∑ j = 1 n u m i D i j ≤ s t o i
(6)
Lighting constraints. This paper mainly considers two types of payloads: visible light camera and synthetic aperture radar. SAR can be observed in the full orbital period, and visible light camera can only observe within a certain sun elevation angle. The sun elevation angle needs to meet the following formula.
∀ l ∈ { 1 , … , k } , i ∈ { 1 , … , n } S u n ( l ) ≥ S u n A n g i
(7)
Payload type constraints. The target must be observed by the payload of the required type.
∀ i ∈ { 1 , … , n } , j ∈ { 1 , … , m } , s t i j ∈ S t P a y l i = R e q j
(8)
Resolution constraints. The resolution of satellite observing the target should not be lower than the users’ requirement.
∀ i ∈ { 1 , … , n } , j ∈ { 1 , … , m } , s t i j ∈ S t s r i ≤ t r j

2.2.2. Scheduling Solution

The purpose of scheduling is to find an optimal execution plan for satellites that can maximize the payoff of observing targets. From the scheduling plan, the tasks of a satellite can be arranged in a timeline, and each satellite will know exactly the execution and termination time of observation, as shown in Figure 1. It is noteworthy that all the scheduling plan needs to satisfy the model constraints in Section 2.2.1 to make it executable.
During a scheduling period, observation opportunities are strictly limited by observation windows. We naturally number the observation windows and use metaheuristic algorithms to find optimal combinations so as to deconflict and output an executable scheduling plan. In this paper, we define a 6-tuple to record an observation chance to one target of a certain satellite, namely, [Window ID, Target ID, Satellite ID, Observation Start Time, Observation End Time, Observation Slew Angle]. The scheduling solution consists of numbers of (the length of solution is the number of targets) these tuples, and detailed execution information of the scheduling plan can be indexed from the observation windows set.

2.3. Optimization Objective of Satellite Mission Scheduling

Satellite mission scheduling is a combined optimization problem with multiple constraints and objectives. Through scheduling, we want to obtain a solution that not only prioritizes observing high-value targets (high priority) and a high task completion rate but also ensures less energy consumption among satellites. Based on this consideration, we set following sub-goals and use a linear weighted sum method to set the optimization objective for solving this model:
(1)
Sub-objective 1: Maximize the priority of the target observations.
y 1 = a × M a x ( ∑ i = 1 n ∑ j = 1 n u m i X i j × p r i o j ) / ∑ j = 1 m p r i o j
(2)
Sub-objective 2: Maximize the number of target observations.
y 2 = b × M a x ∑ i = 1 n ∑ j = 1 n u m i X i j / m
(3)
Sub-objective 3: Balance resource usage among satellites.
y 3 = c × M i n ∑ i = 1 n P i y 3 = c · M i n ∑ i = 1 n P i
On the basis of the above three sub-goals, the total optimization goal of this paper is obtained by a linear weighted sum method.
y = α × y 1 + β × y 2 + γ × y 3
Due to different measurements of priority, task execution number, and energy consumption, it cannot be directly evaluated at the same time. This paper introduces the dimensional parameters a, b, and c to unify each index, and the values are a = 1/4, b = 1, and c = 1/5, in order to ensure that the benefit of observing a target must be higher than the loss of energy consumption. In equation (12), α, β, and γ are weight indicators, and the sum of them is 1. The value of the weight determines the importance of the sub-objective in the overall optimization goal. This paper takes the priority of the task as the key factor, and we set α = 0.7, β = 0.2, and γ = 0.1.

3. Distributed Mission Scheduling Model

3.1. Game Model of DEOS

To achieve efficient system coordination among multiple satellites, this paper sees the DEOS as a multi-agent system and converts multi-satellite mission planning into a game problem G = (N, {Ai}, {Ui}), where N = S is the set of players (agents) in a game. Every satellite si∈S in this game is seen as a ‘rational player’ (agent), whose rationality is embodied in that it will continuously adjust its own action strategy ai in response to the action strategy adopted by opponents, so as to maximize its own payoff Ui. Action ai is the scheduling plan that is only executed by the i-th satellite, and it is a subset of the overall scheduling solution defined in Section 2.2.2. As shown in Figure 1, the sub-solution for Sat1 represents the current action adopted by the 1st satellite in that scenario. In addition, A = ∏i∈N Ai represents the set of joint actions taken by the entire system in one round of the game. For simplicity of expression, let a−i = (a1,…, ai−1, ai+1,…, an) be the action profile other than si. To terminate iterations of gaming, we introduce Nash Equilibrium to our model.
Definition 1.
(Nash Equilibrium [39]) For a game problem G = (N, {Ai}, {Ui}), for any player i∈N, we call a∗ a Nash equilibrium, when it satisfies:
U i ( a i ∗ , a − i ∗ ) = max a i ∈ A i U i ( a i , a − i ∗ )
In iterations of reaching Nash equilibrium of a multi-satellite game, each satellite modifies its own action without directly interfering with other satellites. Due to the optimization objective setting in Section 2.3, each satellite will try to ‘capture’ as many unscheduled targets as possible to gain a higher individual payoff and meanwhile pay close attention to targets that have been scheduled by others to avoid repeated observation. The gaming process will continue to run until the system reaches a balance when all individuals are unable to obtain higher payoffs by changing their own actions. It is noteworthy that after each round of the game, each satellite must inform other satellites of its action to maintain the consistency of cognition. In Section 2.1, we assume that each satellite with the same payload can interact in real time through inter-satellite links, which provides a basis for the future optimization based on Nash equilibrium.

3.2. DMSA Based on Nash Equilibrium

For the generalization of the problem, in distributed mission scheduling algorithm (DMSA, as shown in Algorithm 1), we set n finite memory tables of length L that record the historical actions adopted by each player si and denote them by Memit = (memi1; memi2; …, memiL) and (i = 1,2,…,n), respectively, whose initialization is defined to be empty. When optimization begins, every player will be randomly allocated several targets and generate its own action space Ai. In each round of gaming, all the players exchange information, and each player selects its action; ai∈Ai is by the adaptive particle swarm optimization algorithm (APSOA) in static scheduling or by the adaptive tabu-search algorithm (ATSA) in dynamic scheduling, both of which will execute constrains check and deconflict process and thus calculate current payoff Ui(t) in (12). As Equations defined in (9)–(11) are the overall optimization sub-objectives of scheduling, when calculating current payoff Ui(t) of each satellite in (12), the variable n is set as (1) and the best response BRit as
B R i t = arg max a i t ∈ A i U i ( a i t , a − i ∗ )
Then, each individual will compare current BRit with last BRit−1 (or ait−1) recorded in the memory table and follow the greedy strategy to select the one with higher payoff as current action ait. After recording ait into the bottom of memory table as newest memi, the DMSA will check whether the number of elements in the current memory table is greater than length L, and if so, si will delete the oldest element (the memi1) to obtain an updated fixed-length Memit and then reallocate those allocated but unscheduled targets to neighbors (neighboring satellites refer to satellites with the same payload, and we assume they can send information to each other directly at any time). The gaming will continue to process until recorded actions of all players’ memory tables stay consistent for L rounds, which means all satellites are unable to obtain higher returns through their own plan adjustments.
Algorithm 1 DMSA
Input: Satellites Set S, Targets Set T, memory length L, Observation Windows Set W.
Output: Overall Scheduling Plan
Procedure:
1.for each round of Game, g = 1,2,3…, do
2.    for each satellite si∈S, simultaneously do
3.        Receive information from neighbors;
4.        Calculate and select Ui, BRit by APSOA/ATSA;
5.        Find received targets that haven’t been scheduled;
6.        Send unscheduled targets to neighbors;
7.        Update Memit of each si;
8.    end for
9.end for

3.3. APSOA for Single Satellite Scheduling

3.3.1. Solution Coding Scheme

Coding scheme is directly related to the design of model and efficiency of algorithm. In the data preprocessing stage, observation windows defined in Section 2.2.2 are calculated and numbered, and each window can be uniquely indexed by a window ID. As observation can only happen during the window time period, an optimal scheduling solution is actually a combination of observation windows that not only satisfy the model constrains but maximize the observation payoff. In this paper, the solution coding is organized in a chromosome manner with gene fragments on it (the number of gene fragments is equal to the total number of targets). In each gene, there is a non-negative decimal number which corresponds to the observation window ID (0 indicates that the current target has not been scheduled for observation). For satellites with the same payload type, they share the same sub-solution coding (the length of sub-solution is equal to the number of targets with the required observation type), the final overall solution will be the accumulation of sub-solutions with same payload type, and connections of sub-solutions with different payload types, as shown in Figure 2.

3.3.2. APSOA Procedure

In static scheduling when all observation requests are proposed beforehand, the optimization results in each round of the game will have an impact on the overall scheduling plan of the system. In order to improve the solving efficiency and final payoff of the distributed optimization algorithm, each satellite needs to output a satisfactory sub-plan in a relatively short time. This paper designs an APSOA, whose inertia weight parameter λ will be adaptively adjusted as the iterations evolve, so that the solving speed will gradually increase, and convergence will occur as soon as possible.
λ = λ max − ( λ max − λ min ) ⋅ t T max
where Tmax is the maximum iteration number, t is the current iteration number, λmin is the minimum inertia weight parameter, and λmax is the maximum inertia weight parameter. The pseudo code of the APSOA is shown in Appendix A.

3.3.3. Static Scheduling Evaluation

The evaluation methods for static scheduling mainly include three indicators: the first one is the overall payoff of the scheduling plan (Payoff), and the second one is the mission completion rate (CR). These two indicators mainly reflect the profit of the satellite mission execution plan. The third one is the running time (RT), which mainly reflects the solving speed of the optimization algorithm.

3.4. ATSA for Dynamic Scheduling

Dynamic scheduling occurs when emergency missions arrive or change of initial plan is required. This section presents an ATSA to solve this problem. Before introducing the algorithm, we firstly analyze what will happen to the solution when an emergency comes up.

3.4.1. Impact of Emergency on Initial Solution

New Mission Arrival

Newly arrived missions are the most frequent cases of emergency conditions. When emergency happens, such as natural disaster monitoring, public health incidents, or when new targets with high priority appear, new targets are added to observation requests. It is unpractical to put newly arrived missions into a new target set and reschedule them as regular circumstances because the scheduling plan with regards to new targets might conflict with the initial plan in the same execution period. Therefore, new targets should be considered as a whole with old ones; in other words, new genes representing newly arrived targets will be numbered subsequently and inserted at the bottom of the initial solution; the solution structure update is shown in Figure 3.

Change of Scheduling Plan

Sometimes, when some targets cannot be observed as required due to weather condition or satellite resources malfunction, these targets should be rescheduled without disturbing the undergoing plan of satellites that are properly functioning. In other words, most targets can be normally executed as initially planned, while those failed missions should update their solution state (replace the window ID with 0) and reschedule, as shown in Figure 4.

3.4.2. ATSA Procedure

Above all, after emergency happens, we can see that the new solution updates its structure and state based on the initial one. In dynamical scheduling, remaining satellite resources will be allocated to unscheduled tasks. Because resources between different satellites are independent of each other, the impact of the solution improvement is also limited to those satellites assigned new targets. Based on the above factors, we do not perform an entirely new round of search and optimization for every gene in ATSA but only focus on those targets that have not been scheduled. On that basis, we design a method which will call TS multiple times and adaptively update its searching strategy and solution structure (such as iteration number, neighborhood solution structure, etc.) during the optimization process. This method can be continuously trimming the search space to improve the computational efficiency as well as the quality of the solution at an acceptable cost. The pseudo code of the ATSA is shown in Appendix B.

3.4.3. Dynamic Scheduling Evaluation

The goal of dynamic scheduling is to complete emergency tasks with high revenue while maintaining the integrity of initial plan. Therefore, several indicators are defined to evaluate the performance of algorithm, including the completion rate (CR), priority execution rate (PR), initial plan change rate due to newly arrived targets (IR), and emergency execution rate (ER). The evaluation function is defined as follows:
f = C R + P R + ( 1 − I R ) + E R 4 C R = n 2 / n ′ P R = ∑ i = 1 n 1 p i / ∑ i = 1 n ′ p i I R = d 3 / n 1 E R = d 4 / ( d 1 + d 2 )
where n’ is the total number of targets, n1 is the number of targets executed in the initial plan, n2 is the number of targets observed after dynamic scheduling, d1 is the number of newly arrived targets, d2 is the number of targets in the initial plan that fail to execute due to emergency, d3 is the number of targets of the initial plan that change due to emergency, and d4 is the total number of emergency targets that execute after dynamic scheduling.

3.5. Convergence Analysis for DMSA

In this section, we present theoretical analysis on convergence for DMSA. The analysis is conducted in two steps. Firstly, the existence of Nash Equilibrium should be demonstrated. It is well known that every game with a finite number of players and action profiles has at least one Nash equilibrium [39]. In a game model of DEOS, it is clear that the numbers of satellites and scheduling plans are finite, so a Nash Equilibrium must exist.
Secondly, we should prove that DMSA will stably converge to an optimal solution from any initial plan. According to the distributed optimization strategy proposed in this paper, when the inter-satellite communication is unblocked, a consensus can be reached among different satellites, and the optimization results of satellites in each round of the game are independent of each other. Therefore, after t rounds of gaming, the payoff F of the entire system is
F = ∑ i = 1 N U i t ( a i )
From the perspective of formula (17) alone, it seems that it only needs to ensure that each individual’s payoff Uit is the current optimal to guarantee the overall global optimal performance. In fact, due to the “short-sighted” characteristics, each player can only obtain a local optimal solution based on the current partial information, while the accumulation of the local optimal does not necessarily represent the system-level optimal. Therefore, this article adopts the greedy rule, so that after rounds of gaming, each player will compare its Uit with previous action ait−1′s payoff and always select one with larger payoff as new action ait. Consequently, the payoff of each player must be “non-decreasing”, namely,
∀ i ∈ { 1 , … , n } , ∀ t U i t ( a i t ) ≥ U i t - 1 ( a i t − 1 )
From the definition of scheduling payoff, it can be seen that the total payoff in a scenario is upper bounded. Along with the existence of Nash equilibrium, through each iteration of “non-decreasing” execution, as long as the number of iterations can be guaranteed, the distributed optimization will be stabilized. In other words, ‘stability’ means that all the individual payoffs will remain unchanged for the remaining rounds of gaming, therefore leading to a system-level balance. This is also the inspiration for setting a memory table for each satellite; the length of L should be set based on the overall requirements of scheduling: when L is small, coordination can be reached with shorter computation time, but scheduling effects rely heavily on the initial targets allocation; when L is large, a more satisfactory solution can be obtained with higher computation cost; when L is infinitely large, a Nash Equilibrium must be reached. To conclude, by setting a proper L in real world application, DMSA can be balanced between efficiency and effectiveness, the scheduling solution can stably converge to a local optimum, or even the global optimum.

4. Results and Discussion

To evaluate the effectiveness of the proposed methods, this section conducts several simulation experiments. We set up test scenarios in STK software by adding different numbers and types of EOSs, payloads, and targets, as shown in Figure 5. Mission requests (including targets geographical locations, observation types, priority, resolution requirement, etc.) are generated worldwide by a random uniform distribution. During the simulation period (from 8 March 2021 16:00 to 9 March 2021 16:00, universal time coordinated), the observation satellites composed of a Walker constellation in a 600 km height sun-synchronous orbit (the inter plane true anomaly increment is 2°, the RAAN increment is 4.5°) are automatically generated. We can modify the scale of scenarios by adjusting the number of satellites in an orbital plane and orbital plane number to adjust the size of the constellation.

4.1. Case Study for DMSA in Static Scheduling

4.1.1. Scenario Setting

The experimental cases involve several scenarios that include different numbers of satellites, different types of observations, and different distributions of observation targets. The number of mission targets ranges from 30 to 200. The target positions are randomly generated within the range of latitude −60~60°, and the observation type and priority (1~5) are randomly generated; the number of satellites ranges from 3 to 16. The type of satellites payloads in the constellation are randomly generated. The payload setting parameters are shown in Table 2.

4.1.2. Algorithm Parameters Initializing

On the data preprocessing stage, the satellites and targets information in the scenario is imported into STK in batches by MATLAB, and the visible window information of payload and target is obtained through the visible analysis and calculation of STK. On this basis, the adaptive PSO algorithm is then called for task scheduling. The main parameters of the PSO algorithm are set as follows: particle population set to 50, PSO maximum iteration number set to 100, acceleration coefficients c1 = c2 = 1.5, inertia weighted parameter λmax = 0.9, λmin = 0.4. The indication of early termination is that best fitness value of population has not been improved for 15 consecutive generations. The length of memory table L is set as 5.

4.1.3. Typical Algorithms for Comparison

This paper selects the centralized genetic algorithm (CGA) [40], the centralized particle swarm algorithm (CPSOA) [41], and the centralized tabu search algorithm (CTSA) [16] and compares their performances in different cases with the DMSA proposed in this paper.

4.1.4. Simulation Results Analysis

The simulation results of different cases are shown in Table 3. Generally speaking, with the increase in the number of satellites and the number of targets, the overall planning payoff is on the rise, but due to the increase in the complexity of the problem, the scheduling process also consumes more time.

Comparison and Analysis for Performances of Optimization Algorithms

From the perspective of search strategies among mentioned algorithms, CPSOA and CGA are both global search algorithms, while CTSA focuses on searching local solution space. From Figure 6, we can see that, when the problem scale is small, there is little difference between performances of different algorithms; due to CTSA’s local search strategy, it has a considerable advantage in calculation speed over other centralized scheduling algorithms. With the increase of the problem scale, the superiority of the CPSOA’s strong global search ability is reflected. In all experimental cases, CPSOA can output a scheduling plan with the highest payoff and completion rate, while CGA and CTSA fall much more easily into a local optimum.

Comparison and Analysis for Scheduling Method

From the perspective of scheduling methods, though the overall payoff will be lower than that of centralized scheduling, the distributed mission scheduling method has significant advantages in scheduling time. This is because the method of assigning targets to individuals for single-satellite scheduling is helpful in reducing the search areas of solution space, thereby improving the solving efficiency. Comparing the scheduling time between CPSOA and DMSA (as shown in Figure 7), we can see that when the scale of the problem increases, DMSA will not experience a sharp increase in scheduling time like CPSOA. Moreover, only the number of satellites increases while the number of targets remains unchanged, and the scheduling time of DMSA does not increase significantly, which fully demonstrates the advantages of the distributed system using decentralized management and control, that is, the addition or deletion of nodes will not affect the stability of the system. Individuals in the system can maintain contact and collaboration with each other through communication, while simultaneously remain relatively independent, which can greatly enhance the flexibility and robustness of the distributed system.

4.2. Case Study for DMSA in Dynamic Scheduling

4.2.1. Scenario Setting

To verify the effectiveness of DMSA in dynamic scheduling, we set up several cases that involve emergency circumstances. In the first scenario, 30 initial point targets are randomly generated; target parameters are shown in Table 4. Moreover, another 5 high priority targets are added as emergency missions to test the dynamic scheduling algorithm, as shown in Table 5. We set a constellation of 2 orbital planes with 3 EOSs on each plane, payload types (visible light and microwave) and resolution of the EOSs are also randomly generated, as shown in Table 6.

4.2.2. Algorithm Parameters Initializing

For the initialization of ATSA, the length of the tabu list is dynamically determined by the maximum number of unscheduled tasks in the current solution (larger number leads to longer length), and the neighborhood scale is set to 5. The TS global maximum iteration number is set to 150, and the local maximum iteration number is set adaptively according to times of calling different TS (later iteration leads to smaller local maximum iteration number). The global early termination indication is that the task completion rate (the proportion of scheduled task in all tasks that can be observed) reaches at least 98%.

4.2.3. Simulation Results Analysis

After iterations of APSOA in static scheduling, the initial plan is output, as shown in Table 7. In the initial plan, visible light Target17 is not allocated any satellite resources because of limitation in time window (the target cannot be observed by any optical payload satellite due to lighting constraints). Then, we set an emergency circumstance where a satellite malfunction occurs: Target8, Target12, and Target21 cannot be observed as planned. Moreover, 5 emergency targets with high priority are added. After dynamic scheduling, for those initial targets with malfunction problems, microwave Target8 and Target12 are rescheduled to new satellite resources with new time windows; visible light Target30 is deleted from plan due to limited time window. For those newly arrived missions, all targets except for the visible light Target31 are directly inserted to new scheduling plan. Target31 is deleted because it cannot be observed by any satellite.
As shown in Table 8, it can be seen that in this scenario, 29 of 30 targets are scheduled under regular circumstances. After dynamic scheduling, 91.4% of targets are observed with only 10.3% change to the initial plan, 89.3% of priorities are executed, 75% of emergency targets are allocated satellite resources, and the evaluation function value is 0.86. The number of targets executed by optical satellites (S2, S5, and S6) are 4, 3, 4, while the number of SAR satellites (S1, S3, and S4) are 8, 6, 7. It indicates that missions are allocated in a balanced way among satellites; the scheduling result is shown in Figure 8. It is noteworthy that unscheduled targets are all visible light targets, and during the whole scheduling period, Target17 and Target31 cannot be observed by any optical satellites. Moreover, because the Walker constellation is on the sun-synchronous orbit, Target30 can only be observed by S2 for once. Consequently, missed observing opportunity in the initial plan will lead to failure of observation after dynamic scheduling. Therefore, the result shows that the algorithm can efficiently make adjustments after an emergency happens and guarantee the stability of the initial scheduling plan. Targets with high priority and sufficient observation windows will be scheduled with satisfactory effect.
Several more experimental cases are conducted in this section to verify the effectiveness of the proposed method. Six scenarios with different satellites and resources are setup, and the evaluation function defined in Section 3.4.3 is performed to evaluate the scheduling results. Computational complexity is measured by the elapsed CPU time. Detailed evaluation results are shown in Table 9.
It shows that as the scale of the scenarios increases, the elapsed CPU times of both regular and dynamic scheduling exhibit an increasing trend. The average CR of 0.953 indicates our method can schedule most of the targets in the scenarios. It is noteworthy that PR is always higher than CR, and the average ER is 0.948, both of which indicate that targets with high priority are more likely to be scheduled. The IR is related to the proportion of emergency targets to initial targets, we can see that in the 3rd scenario where the proportion is the largest ((10 + 20)/50 × 100% = 60%), the change to initial plan after dynamic scheduling is also the largest. The running times of dynamic scheduling are much shorter than those of static scheduling, and this is because the strategy in ATSA will trim the searching space which leads to a quicker convergence.
Some may be concerned that our trimming method is reducing computational complexity at the cost of losing potential to find a global optimum, but we can see the CR and PR values are both at satisfactory level. Every time ‘old’ TS stops its iteration and updates its solutions’ structure, the ‘new’ TS searches the observation set again and tries new windows combinations of unscheduled targets. A new revenue check and de-conflict process will be calculated to see whether the scheduled targets can be substituted or deleted due to insertion of new ones, which can exploit new parts of the searching space. Moreover, the tabu list will memorize the last ‘moves’ and avoid repeated search, which helps to prevent easy convergence to a local optimal.

5. Conclusions and Future Work

Aiming at efficient mission scheduling for earth observation distributed satellite systems, this paper addresses the problem by learning from game theory. We firstly propose DMSA which views each satellite as a rational player that focuses on maximizing its payoff through cooperation with neighbors, and we adopt the idea of Nash Equilibrium to guarantee convergence to a near global optimal scheduling plan. To achieve static and dynamic scheduling circumstances, we propose APSOA and ATSA, respectively, and set experimental cases to evaluate their effectiveness. The simulation results show that, in static scheduling, our method can effectively overcome the shortcomings of centralized methods in large-scale mission scheduling scenarios, such as a sharp increase in scheduling time and slow convergence. The distributed mission scheduling method can flexibly deal with different scales of problem scenarios. The algorithm performance will not decrease significantly with the increase in the problem scale and can stably and efficiently obtain the near global optimal solution whose performance is slightly lower than that of the centralized scheduling. In dynamic scheduling, high priority targets will take precedence in execution, and most of the emergency targets will be dynamically scheduled in a relatively short time without major changes to the initial plan. To conclude, the proposed method yields a high scheduling revenue and low scheduling cost and provides a way of solving the DEOS scheduling problem with scalability, adaptability, efficiency, and effectiveness. It has potential to be further applied to more complex scenarios.
In future work, we will introduce new constraints and update our optimization strategy to make the scheduling model more comprehensive and robust and study the emergency demand analysis mechanism to transform user needs with precision and efficiency. Moreover, we will explore the distributed collaborative scheduling mechanism with restricted communication environments to meet the demands of more complex satellite scheduling problems in the real world.

Author Contributions

L.L. is the director of the corresponding contents. Conceptualization, L.L. and Z.D.; methodology, L.L. and H.S.; data processing, D.Y. and H.S.; validation, H.S.; review and editing, D.Y. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

The data that support the findings of this study are available from the corresponding author upon reasonable request.

Acknowledgments

The authors would like to thank the Qian Xuesen Laboratory, CAST, and Changchun Institute of Optics, Fine Mechanics, and Physics (CIOMP), Chinese Academy of Sciences for providing the technical guidance. Comments from the anonymous reviewers and the editor are also gratefully appreciated.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A

The pseudo code for APSOA is shown as follows:
Algorithm A1 APSOA
Input: Targets Set Ti, acceleration coefficients c1,c2, inertia weighted parameters,
last action ait−1, last payoff Uit−1,
Output: Uit, BRit
Procedure:1. Randomly generate current swarm according to Ti;
2. Insert last action ait−1 to current swarm;
3. for each iteration g = 1,2… do
4.    for each particle p = 1,2… do
5.        De-conflict and calculate the profit;
6.        Compare and substitute the individual optimal and global optimal;
7.        Update particle’s location and velocity in (16);
8.        Boundary condition processing;
9.    end for
10. end for
11. Compare the best Uit of swarm with Uit−1, and select a with
higher Ui as BRit;
v i j ( t + 1 ) = λ · v i j ( t ) + c 1 r 1 ( t ) [ p i j ( t ) − x i j ( t ) ] + c 2 r 2 ( t ) [ p g j ( t ) − x i j ( t ) ] x i j ( t + 1 ) = x i j ( t ) + v i j ( t + 1 )
where particle population P = (X1, X2,…, XN) is randomly generated, and each particle Xi = (xi1, xi2,…, xiD) is a solution that will be further iterated. D is the dimension of the solution (it refers to the number of targets in this paper), and all the components in Xi together determine the position of Xi. Each particle has a velocity Vi = (vi1, vi2,…, viD); velocity controls the speed and direction of particle evolution. The individual optimal so far is pbest = (pi1, pi2,…, piD), and the global optimal is gbest = (g1,g2,…,gD).

Appendix B

The pseudo code for ATSA is shown as follows:
Algorithm A2 ATSA
Input: Targets Set Ti, neighborhood size Ca, termination parameters, last action ait−1,last payoff Uit−1,
Output: Uit, BRit
Procedure:
1. for each satellite s = 1,2… do
2.    Find allocated but unscheduled targets and update solution structure;
3.    for each global iteration g = 1,2… do
4.        Initialize local iteration parameters, including tabu list length, localmaximum iteration number, etc.;
5.        for each local iteration l = 1,2… do
6.           Generate the neighborhood solution and calculate payoff respectively, and retain the solution with maximum as candidate solution;
7.           Update the current solution with candidate solution and best solutionso far with the candidate solution if aspiration judgement is satisfied;
8.           Update tabu-list;
9.        end for
10.   end for
11. end for
12. Compare the best Uit with Uit−1, and select a with higher Ui as BRit;

References

  1. Araguz, C.; Llaveria, D.; Lancheros, E.; Bou-Balust, E.; Camps, A.; Alarcon, E.; Lluch, I.; Matevosyan, H.; Golkar, A.; Tonetti, S. Optimized Model-Based Design Space Exploration of Distributed Multi-Orbit Multi-Platform Earth Observation Spacecraft Architectures. IEEE: Big Sky, MT, USA, 2018; Volume 2008, pp. 1–16. [Google Scholar]
  2. Rajah, P.M.; Prokopenko, M.; Wang, P.; Price, D. On Decentralised Clustering in Self-Monitoring Networks. In Proceedings of the fourth International Joint Conference on Autonomous Agents & Multiagent Systems, New York, NY, USA, 25 July 2005; Volume 2005, pp. 1175–1176. [Google Scholar]
  3. Abbott, D.; Doyle, B.; Dunlop, J.; Farmer, T.; Hedley, M.; Herrmann, J.; James, G.; Johnson, M.; Joshi, B.; Poulton, G. Development and Evaluation of Sensor Concepts for Ageless Aerospace Vehicles: Development of Concepts for an Intelligent Sensing System; NASA STI Progarm: Langley, WA, USA, 2002. [Google Scholar]
  4. Prokopenko, M.; Wang, P.; Price, D. Towards Adaptive Clustering in Self-monitoring Multi-agent Networks. In Proceedings of the International Conference on Knowledge-Based Intelligent Information & Engineering Systems, Melbourne, Australia, 14–16 September 2005; Volume 2005. [Google Scholar]
  5. Araguz, C.; Bou-Balust, E.; Alarcon, E. Applying autonomy to distributed satellite systems: Trends, challenges, and future prospects. Syst. Eng. 2018, 21, 401–416. [Google Scholar] [CrossRef]
  6. Zhang, S.; Xiao, Y.; Yang, P.; Liu, Y.; Chang, W.; Zhou, S. An Effectiveness Evaluation Model for Satellite Observation and Data-Downlink Scheduling Considering Weather Uncertainties. Remote Sens. 2019, 11, 1621. [Google Scholar] [CrossRef] [Green Version]
  7. Sun, C.; Wang, X.; Liu, X. Distributed Satellite Mission Planning via Learning in Games. In Proceedings of the 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Miyazaki, Japan, 7–10 October 2018; Volume 2018. [Google Scholar]
  8. Iacopino, C.; Palmer, P.; Policella, N.; Donati, A.; Brewer, A. How ants can manage your satellites. Acta Futur. 2014, 9, 57–70. [Google Scholar]
  9. Kilic, S.; Ozkan, O. Ant colony optimization approach for satellite broadcast scheduling problem. In Proceedings of the 2017 8th International Conference on Recent Advances in Space Technologies (RAST), Istanbul, Turkey, 19–22 June 2017; pp. 273–277. [Google Scholar]
  10. Tripp, H.; Palmer, P. Stigmergy based behavioural coordination for satellite clusters. Acta Astronaut. 2010, 66, 1052–1071. [Google Scholar] [CrossRef]
  11. Wu, G.; Liu, J.; Ma, M.; Qiu, D. A two-phase scheduling method with the consideration of task clustering for earth observing satellites. Comput. Oper. Res. 2013, 40, 1884–1894. [Google Scholar] [CrossRef]
  12. Bunkheila, F.; Circi, C. Innovative Satellite Scheduling Method Based on Genetic Algorithms and Simulated Annealing and Related Mission Planner. EP Patent 3406531, 24 May 2018. [Google Scholar]
  13. Xhafa, F.; Sun, J.; Barolli, A.; Biberaj, A.; Barolli, L. Genetic algorithms for satellite scheduling problems. Mob. Inf. Syst. 2012, 8, 351–377. [Google Scholar] [CrossRef] [Green Version]
  14. Greco, C.; Gentile, L.; Filippi, G.; Minisci, E.; Vasile, M.; Bartz-Beielstein, T. Autonomous generation of observation schedules for tracking satellites with structured-chromosome GA optimisation. In Proceedings of the 2019 IEEE Congress on Evolutionary Computation (CEC), Wellington, New Zealand, 10–13 June 2019; pp. 497–505. [Google Scholar]
  15. Mansour, M.A.; Dessouky, M.M. A genetic algorithm approach for solving the daily photograph selection problem of the SPOT5 satellite. Comput. Ind. Eng. 2010, 58, 509–520. [Google Scholar] [CrossRef]
  16. Cui, J.; Zhang, X. Application of a multi-satellite dynamic mission scheduling model based on mission priority in emergency response. Sensors 2019, 19, 1430. [Google Scholar] [CrossRef] [Green Version]
  17. Bianchessi, N.; Cordeau, J.-F.; Desrosiers, J.; Laporte, G.; Raymond, V. A heuristic for the multi-satellite, multi-orbit and multi-user management of earth observation satellites. Eur. J. Oper. Res. 2007, 177, 750–762. [Google Scholar] [CrossRef]
  18. Vasquez, M.; Hao, J.-K. A “logic-constrained” knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite. Comput. Optim. Appl. 2001, 20, 137–157. [Google Scholar] [CrossRef]
  19. Ocon, J. Multi-agent frameworks for space applications. In Proceedings of the SpaceOps 2010 Conference Delivering on the Dream Hosted by NASA Marshall Space Flight Center and Organized by AIAA, Huntsville, AL, USA, 25–30 April 2010; p. 2069. [Google Scholar]
  20. Wang, C.; Li, J.; Jing, N.; Wang, J.; Chen, H. A Distributed Cooperative Dynamic Task Planning Algorithm for Multiple Satellites Based on Multi-agent Hybrid Learning-ScienceDirect. Chin. J. Aeronaut. 2011, 24, 493–505. [Google Scholar] [CrossRef] [Green Version]
  21. Bonnet, J.; Gleizes, M.P.; Kaddoum, E.; Rainjonneau, S.; Flandin, G. Multi-satellite mission planning using a self-adaptive multi-agent system. In Proceedings of the 2015 IEEE 9th International Conference on Self-Adaptive and Self-Organizing Systems, Cambridge, MA, USA, 21–25 September 2015. [Google Scholar]
  22. Hess, J.A.; Saunders, D.; Cobb, R.G.; Zagaris, C. Autonomous Cooperative Optimal Control of Multi-Agent Satellite Formations. In Proceedings of the 2020 AAS/AIAA Astrodynamics Specialist Virtual Lake Tahoe Conference, Lake Tahoe, CA, USA, 9–12 August 2020. [Google Scholar]
  23. Araguz, C.; Closa, M.; Bou-Balust, E.; Alarcon, E. A Design-Oriented Characterization Framework for Decentralized, Distributed, Autonomous Systems: The Nano-Satellite Swarm Case. In Proceedings of the 2019 IEEE International Symposium on Circuits and Systems (ISCAS), Sapporo, Japan, 26–29 May 2019. [Google Scholar]
  24. Kuhn, H.W. Classics in Game Theory; Princeton University Press: Princeton, NJ, USA, 1997. [Google Scholar]
  25. Başar, T. Game Theory: Historical Overview. In Encyclopedia of Systems and Control; Baillieul, J., Samad, T., Eds.; Springer: London, UK, 2013. [Google Scholar] [CrossRef]
  26. Nash, J.F. Non-Cooperative Games; Annals of Mathemtics; Princeton University: Princeton, NJ, USA, 1951; pp. 286–295. [Google Scholar]
  27. Kusyk, J.; Uyar, M.U.; Ma, K.; Samoylov, E.; Boksiner, J. Artificial intelligence and game theory controlled autonomous UAV swarms. Evol. Intell. 2020, 1–18. [Google Scholar] [CrossRef]
  28. Xing, G.; Chen, Y.; Hou, R.; Dong, M.; Ma, M. Game Theory-based Clustering Scheme for Energy Balancing in Underwater Acoustic Sensor Networks. IEEE Internet Things J. 2021, 8, 9005–9013. [Google Scholar] [CrossRef]
  29. Cintuglu, M.H.; Martin, H.; Mohammed, O.A. Real-Time Implementation of Multiagent-Based Game Theory Reverse Auction Model for Microgrid Market Operation. IEEE Trans. Smart Grid 2017, 6, 1064–1072. [Google Scholar] [CrossRef]
  30. Kasthurirathna, D.; Piraveenan, M. Emergence of scale-free characteristics in socio-ecological systems with bounded rationality. Sci. Rep. 2015, 5, 10448. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  31. Kasthurirathna, D.; Piraveenan, M.; Uddin, S. Modeling networked systems using the topologically distributed bounded rationality framework. Complexity 2016, 21, 123–137. [Google Scholar] [CrossRef]
  32. Piraveenan, M. Applications of Game Theory in Project Management: A Structured Review and Analysis. Mathematics 2019, 7, 858. [Google Scholar] [CrossRef] [Green Version]
  33. Pemberton, J.C.; Greenwald, L. On the need for dynamic scheduling of imaging satellites. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci. 2002, 34, 165–171. [Google Scholar]
  34. Bensana, E.; Lemaitre, M.; Verfaillie, G. Earth observation satellite management. Constraints 1999, 4, 293–299. [Google Scholar] [CrossRef]
  35. Gabrel, V.; Vanderpooten, D. Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite. Eur. J. Oper. Res. 2002, 139, 533–542. [Google Scholar] [CrossRef]
  36. Dishan, Q.; Chuan, H.; Jin, L.; Manhao, M. A dynamic scheduling method of earth-observing satellites by employing rolling horizon strategy. Sci. World J. 2013, 2013, 1–11. [Google Scholar] [CrossRef] [PubMed]
  37. He, L.; Liu, X.-L.; Chen, Y.-W.; Xing, L.-N.; Liu, K. Hierarchical scheduling for real-time agile satellite task scheduling in a dynamic environment. Adv. Space Res. 2019, 63, 897–912. [Google Scholar] [CrossRef]
  38. Wang, J.; Zhu, X.; Yang, L.T.; Zhu, J.; Ma, M. Towards dynamic real-time scheduling for multiple earth observation satellites. J. Comput. Syst. Sci. 2015, 81, 110–124. [Google Scholar] [CrossRef]
  39. Jiang, A.X.; Leyton-Brown, K. A Tutorial on the Proof of the Existence of Nash Equilibria; University of British Columbia Technical Report TR-2007-25.pdf; University of British Columbia: Vancouver, BC, Canada, 2009; p. 14. [Google Scholar]
  40. Song, Y.J.; Wang, P.; Zhang, Z.S.; Xing, L.N.; Chen, Y.W. An Improved Genetic Algorithm for Multi-Satellite Mission Planning Problem; Control Theory & Applications: Guangzhou, China, 2019; pp. 1391–1397. [Google Scholar]
  41. Han, Y.; Luo, J.; Xu, X. On the Constellation Design of Multi-GNSS Reflectometry Mission Using the Particle Swarm Optimization Algorithm. Atmosphere 2019, 10, 807. [Google Scholar] [CrossRef] [Green Version]
Sensors 21 06660 g001 550
Figure 1. Scheduling solution.
Figure 1. Scheduling solution.
Sensors 21 06660 g001
Sensors 21 06660 g002 550
Figure 2. Solution coding scheme.
Figure 2. Solution coding scheme.
Sensors 21 06660 g002
Sensors 21 06660 g003 550
Figure 3. Emergency targets inserted into the initial solution.
Figure 3. Emergency targets inserted into the initial solution.
Sensors 21 06660 g003
Sensors 21 06660 g004 550
Figure 4. State update of scheduling plan.
Figure 4. State update of scheduling plan.
Sensors 21 06660 g004
Sensors 21 06660 g005 550
Figure 5. Test scenario example.
Figure 5. Test scenario example.
Sensors 21 06660 g005
Sensors 21 06660 g006 550
Figure 6. Payoff and scheduling time. Histogram shows the payoff of different algorithms’ optimization results, while the curve shows the scheduling time.
Figure 6. Payoff and scheduling time. Histogram shows the payoff of different algorithms’ optimization results, while the curve shows the scheduling time.
Sensors 21 06660 g006
Sensors 21 06660 g007 550
Figure 7. Comparison of scheduling time between DMSA and CPSOA.
Figure 7. Comparison of scheduling time between DMSA and CPSOA.
Sensors 21 06660 g007
Sensors 21 06660 g008 550
Figure 8. Gantt chart of dynamic scheduling.
Figure 8. Gantt chart of dynamic scheduling.
Sensors 21 06660 g008
Table
Table 1. Parameter and label definitions.
Table 1. Parameter and label definitions.
NotationDefinitionNotationDefinition
SS = {s1, s2,…, sn,…}, where S represents the set of satellites, n represents the number of satellites.PaylPayl = {Payl1, Payl2…Payli,…}, where Payl represents set of payloads, i corresponding satellite serial number.
DurijDurij represents the imaging duration time required when the i-th satellite executes the j–th task.PreijPreij represents the payload preparation time required to switch from last task when the i-th satellite executes the j–th task.
PowPow = {pow1, pow2…powi,…}, where Pow represents the energy set of the satellite, i represents the corresponding satellite serial number.PijPij represents the energy consumed whenthe i-th satellite executes the j–th task, Pi is the total energy consumption of the i-th satellite.
StoSto = {sto1, sto2…stoi,…}, where Sto represents the storage set of the satellite, i represents the corresponding satellite serial number.DijDij represents the storage consumed whenthe i-th satellite executes the j–th task.
SASA = {sa11, sa12…saij,…}, where SA represents the slew angle set of the satellite, saij represents the slew angle when the i-th satellite executes the j–th task, sai represents the maximum slew angle of the i-th satellite.PtiPti represents the energy consumption per unit time of the i-th satellite during task execution.
SasiSasi represents the slew angle change per unit time of the i-th satellite during task switch.PsiPsi represents the energy consumption per unit time of the i-th satellite during task switch.
WW = {w1, w2… wk,…}, where W represents observation windows set, k represents the number of the windows, wk = [wbtk, wetk, wdtk], wk represents the k-th time window, wbtk represents the start time, wetk represents the end time, wdtk represents the duration.StSt = {st1, st2… stk,…}, where St represents the time information set of satellites execution, m represents the number of tasks, stij = [sbtij,setij], where sttj represents the time information of the i-th satellite executing the j–th task, sbtij represents the execution start time after schedule, setij represents the end time.
TT = {t1, t2…tm,…}, where T represents the set of targets, m represents the serial number of targets.ReqReq = {req1, req2…reqj,…}, where Req represents the set of observation type requests, j represents the corresponding target serial number.
NumNum = {num1, num2… numi,…}, where Num represents the number of tasks that are executed by the satellite, i represents the corresponding satellite serial number.PrioPrio = {prio1, prio2…priom,…}, where Prio represents the set of targets priority, m represents the serial number of targets.
SunSun(l) represents the minimum sun elevation angle in l window period.maxPmaxP is the initial power of a satellite.
TRTR = {tr1, tr2…trm,…}, where TR represents the set of targets’ resolution requirement, m represents the serial number of targets.SRSR = {sr1, sr2…srn,…}, where SR represents the set of satellites’ resolution, n represents the serial number of targets.
XXij represents the decision variables of satellites, j represents corresponding target serial number, i represents corresponding satellite serial number. Value 1 denotes that target j has been observed by the i-th satellite, value 0 denotes that the target has not been scheduled.SunAngSunAngi represents the minimum sun elevation angle of the i-th satellite carrying an optical payload.
Table
Table 2. Payload parameters.
Table 2. Payload parameters.
ParametersOptical PayloadParametersSAR Payload
SensorTypeSimpleConicMinElevationAngle15.2°
FOV5°MaxElevationAngle51.9°
SlewRange−40~40°ForwardExclusionAngle5.7°
LightingSunAng > 15°AftExclusionAngle8.6°
Table
Table 3. Simulation results in different cases.
Table 3. Simulation results in different cases.
Case
No.		CaseDMSACGACPSOACTSA
SatTarProfitCRRT(s)ProfitCRRT(s)ProfitCRRT(s)ProfitCRRT(s)
No.1630190.934.619.80.979.620.20.9732.9200.955.3
No.265031.20.964.829.30.9021.531.60.9638.730.40.947.8
No.3610064.20.9917.159.40.9645.464.5148.859.30.9121.2
No.4810060.70.9819.957.90.9256.261.60.9878.657.20.8620.8
No.5815091.90.8728.293.80.89126.698.90.96168.590.30.8531.2
No.61615093.40.9128.895.30.93272.6100.31370.790.10.8443.7
No.716200123.60.9329.7121.20.91353.3126.21468.2119.40.8748.6
Table
Table 4. Initial target parameters.
Table 4. Initial target parameters.
Target IDPriorityGeographical PositionObservation TypeResolution Requirement
Target14(113° W, 56° N)microwave0.7
Target24(176° W, 43° N)microwave0.8
Target34(121° W, 29° S)visible light0.5
Target43(40° W, 11° S)microwave0.8
Target54(113° E, 49° S)microwave0.7
Target65(160° W, 55° S)visible light0.6
Target74(32° E, 26° N)microwave0.8
Target82(89° E, 33° S)microwave0.9
Target 93(153° W, 27° S)microwave0.9
Target103(112° E, 12° S)microwave0.9
Target115(36° W, 19° S)visible light0.4
Target124(9° W, 60° N)microwave0.8
Target132(7° W, 47° N)visible light0.5
Target144(119° W, 51° N)microwave0.8
Target152(78° E, 43° N)microwave0.9
Target164(89° W, 9° N)microwave0.8
Target174(141° E, 2° S)visible light0.5
Target182(42° W, 32° N)visible light0.4
Target191(17° W, 49° N)visible light0.6
Target205(78° E, 37° S)microwave0.7
Target213(15° E, 18° N)visible light0.5
Target222(43° E, 28° N)microwave0.7
Target232(151° E, 4° N)microwave0.9
Target244(137° W, 18° N)microwave0.8
Target254(49° W, 44° N)visible light0.5
Target262(13° W, 44° S)microwave0.9
Target271(46° W, 45° N)microwave0.8
Target283(113° E, 19° N)visible light0.3
Target292(171° W, 44° S)visible light0.3
Target304(35° W, 58° N)visible light0.4
Table
Table 5. Emergency targets parameters.
Table 5. Emergency targets parameters.
Target IDPriorityGeographical PositionObservation TypeResolution Requirement
Target315(102° W, 18° S)visible light0.4
Target325(45° W, 17° N)microwave0.8
Target335(7° E, 30° N)microwave0.7
Target345(110° E, 32° S)microwave0.7
Target355(86° W, 54° S)visible light0.6
Table
Table 6. Satellite Information.
Table 6. Satellite Information.
S1S2S3S4S5S6
TypeSarOptSarSarOptOpt
Resolution0.50.30.70.70.50.3
Table
Table 7. Initial scheduling plan.
Table 7. Initial scheduling plan.
Target IDPrioritySatellite IDStart TimeEnd Time
Target14S40:33:270:37:36
Target24S414:42:5214:49:05
Target34S522:48:5322:51:50
Target43S32:08:032:13:17
Target54S317:52:2417:58:03
Target65S50:33:250:36:08
Target74S110:22:5010:29:23
Target82S49:01:199:07:56
Target93S412:48:3012:54:09
Target103S14:06:204:12:45
Target115S617:23:4217:26:11
Target124S323:12:3023:15:20
Target132S516:01:2216:04:26
Target144S49:58:5610:01:40
Target152S117:45:3317:51:46
Target164S118:19:3918:25:49
Target174unscheduled//
Target182S214:42:1514:44:01
Target191S617:05:2617:07:41
Target205S319:32:2119:38:55
Target213S211:32:1411:33:18
Target222S411:59:1212:05:39
Target232S313:29:0713:35:10
Target244S19:48:149:49:59
Target254S618:43:4118:46:45
Target262S112:18:2212:20:52
Target271S32:21:502:24:20
Target283S67:44:527:47:51
Target292S222:53:3422:56:37
Target304S214:34:5214:37:03
Table
Table 8. Dynamic scheduling plan.
Table 8. Dynamic scheduling plan.
Target IDPrioritySatellite IDOperationStart TimeEnd Time
Target82S4→S1reschedule17:27:0617:29:43
Target124S3→S1reschedule11:52:4811:56:00
Target304S2→nonedelete//
Target315unscheduleddelete//
Target325S3insert15:48:5415:52:55
Target335S4insert15:11:4915:18:07
Target345S4insert7:28:317:30:58
Target355S2insert16:29:5816:32:00
Table
Table 9. Simulation results of dynamic scheduling.
Table 9. Simulation results of dynamic scheduling.
Case
No.		Satellite
Number		Initial Targets
Number		Malfunction
Targets		Newly
Arrived
Targets		CRPRIRERRun Time of Initial Plan(s)Run Time of Dynamic Plan(s)Evaluation
Function
No.1325050.9670.969014.21.20.98
No.26505100.9500.9740.1020.8675.31.50.92
No.385010200.9710.9810.220.9676.12.40.92
No.4810015300.9150.9320.1960.91118.73.70.89
No.51210015350.9330.9380.1880.9620.25.30.91
No.61620020400.9790.9810.120.98331.48.10.96
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Liu, L.; Dong, Z.; Su, H.; Yu, D. A Study of Distributed Earth Observation Satellites Mission Scheduling Method Based on Game-Negotiation Mechanism. Sensors 2021, 21, 6660. https://doi.org/10.3390/s21196660

AMA Style

Liu L, Dong Z, Su H, Yu D. A Study of Distributed Earth Observation Satellites Mission Scheduling Method Based on Game-Negotiation Mechanism. Sensors. 2021; 21(19):6660. https://doi.org/10.3390/s21196660

Chicago/Turabian Style

Liu, Lihao, Zhenghong Dong, Haoxiang Su, and Dingzhan Yu. 2021. "A Study of Distributed Earth Observation Satellites Mission Scheduling Method Based on Game-Negotiation Mechanism" Sensors 21, no. 19: 6660. https://doi.org/10.3390/s21196660

APA Style

Liu, L., Dong, Z., Su, H., & Yu, D. (2021). A Study of Distributed Earth Observation Satellites Mission Scheduling Method Based on Game-Negotiation Mechanism. Sensors, 21(19), 6660. https://doi.org/10.3390/s21196660

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop