An approach to multi-satellite TT&C resource scheduling based on multi-agent technology and comprehensive weighted priority determination method

The purpose of satellite tracking telemetry and control (TT&C) resource scheduling is to scientifically allocate limited ground TT&C resources, and to maximize the scheduled tasks of satellite TT&C through a certain scheduling method. Due to the sharp increase in satellite numbers, Traditional scheduling methods face challenges with more TT&C tasks, more resource competition and more emergencies. As the agent is independent, flexible, intelligent and distributed, we introduced agent technology to solve the problem. Combining characteristics of multi-satellite TT&C resource schedule with description method of attribute, interaction, rule and state on agent technology, we established four agent models: manager agent, station agent, equipment agent and task agent. Then, by analysing the requirements of satellite TT&C engineering, we proposed a comprehensive weighted priority determination method to determine TT&C resource allocation. Last, we simulated real application scenarios to validate this method. And it proves to be effective.


Introduction
TT&C resources scientific scheduling is one of the key elements to guarantee the TT&C engineering and security operating management of spacecraft. The research of Multi-Satellite TT&C Resource Scheduling (MSTCRS) has great engineering significance. It can reduce the huge cost of spacecraft TT&C management and TT&C resource construction management.
In this paper, we study how to schedule TT&C resources to make the limited ground TT&C resources play maximum application efficiency, so that the TT&C requirements of growing satellite numbers can be met. In recent years, the contradiction of TT&C station resources, satellites and TT&C requirements is intensified, which increases the complexity of MSTCRS. It also increases the probability of emergencies and the difficulty of manually adjusting scheduling plan. Meanwhile, the scheduling system is urgently required to respond quickly and output new scheduling plan with minimum changes and take the original scheduling plan constraints into account. Therefore, a flexible, intelligent and efficient resource scheduling method is needed.
Now there are many studies on MSTCRS such as constraint programming method, heuristic algorithm, AI algorithm and agent technology. Although National Aeronautics and Space Administration (NASA) and Air Force Institute of Technology (AFIT) [1][2][3] proposed constraint programming methods which can accurately describe the problem, the constraints they considered are very complex. European Space Agency (ESA) proposed a Lagrangian-based heuristic algorithm [4]. It a) Manager agent collects new tasks, and forwards them to task agent; b) Task agent preprocesses these tasks and sends them back to manager agent. c) Manager agent sends pre-processed tasks to station agents. d) Station agents send pre-processed tasks to equipment agents. e) Manager agent sends a resource allocation start signal to station agents. f) Station agents send the signal to their equipment agents. 3 g) Equipment agents get the signal and send optimal resources and corresponding tasks to station agent they belong to. h) Station agents make a preliminary judgment on these feedbacks and send evaluation results to manager agent. i) Manager agent makes a final judgment and feedback the evaluation result to station agents. j) Station agents forward it to equipment agents. k) Equipment agents update resources and send updating results to station agents. l) Station agents send them to manager agent.

Agent description
These agents are described as follows.

Manager agent.
Manager agent is the core role of MSTCRS, and manages TT&C resource scheduling and allocation. It is responsible for the unified reception and distribution of TT&C tasks, beginning of resource allocation, and the evaluation of optimal resources. The model of manager agent is described as follows: Manager={MID, MName, MbeforeTasks, MafterTasks}, Manager refers to manager agent which is unique. Its attributes are as follows: MID is identifier; Mname refers to name; MbeforeTasks refers to tasks to be scheduled; MafterTasks refers to tasks which have been preprocessed and filtered by task agent.

Task agent.
Task agent pre-processes tasks send from manager agent. Based on the approach we proposed, the pre-processing operations include deleting invalid tasks, converting periodic tasks and separable tasks into some one-time tasks based on their periodicity or task split constraints. Besides, since geostationary earth orbit (GEO) satellites are visible all day to ground TT&C equipment, we allocate resources for GEO satellite tasks during the preprocess stage. The model of task agent is as follows: Task={TID,TName, beforeTasks, afterTasks, hightTasks, failTasks, sucessTasks}. Task refers to task agent which is unique; TID is its identifier; Tname refers to task agent's name; beforeTasks refers to tasks to be scheduled; afterTasks is tasks filtered by the task agent; hightTasks is tasks of GEO satellites; failTasks is tasks failed to allocate resources and sucessTasks refers to tasks that successfully allocate resources.

Station agent.
TT&C Station is used to track, measure, telemeter, remote control and communicate with the spacecraft. It includes all the equipment in a certain area. Station agent manages the attribute information of the equipment agents belonging to it, receives and forwards tasks to be scheduled. It selects the optimal couple of tasks and matching resources sent by equipment agents. The station agent is described as follows: Station={Station 1 ,Station 2 ,…, Station i }. i refers to the number of station agent. Station i ∈Station denotes the i-th station agent. Station i ={ID i , Name i , Type i , Status i }, ID is a unique station agent identifier; Name refers to the station's name; Type is the category of TT&C station; Status is availability status of station.

Equipment agent.
TT&C equipment includes TT&C antennas, BBE, converter, etc. Equipment agent provides autonomous and intelligent management of equipment using status, TT&C capability, and TT&C resource allocation. The intelligent management of TT&C resource allocation refers to find all possible resources for tasks according to the constraints of MSTCRS and make up a two-tuple; Then selecting the optimal one from the two-tuple. Finally, updating the two-tuple and attribute information of the equipment agent according to the TT&C resource allocation result sent by manager agent. The management of TT&C equipment using status means that if the equipment is unavailable due to equipment failure or other reasons, all tasks not performed in the equipment are set as pending tasks and sent to the manager agent for replanning. The equipment agent is described as: Equipment={Equipment 1 ,Equipment 2 , …, Equipment j }, where j refers to the number of equipment agent. Equipmentj ∈Equipment is the j-th equipment agent. Equipmentj={ID j , Name j , DF j , Ur j , Status j , Starttime j , Endtime j , Station j , Pr j , St j , Servce j ,Etasks j , Ett j , Estt j }.ID is an equipment agent identifier; Name refers to the name of equipment; DF is frequency band; Ur is equipment's resource utilization; Status is using status; Starttime is start time for equipment availability; Endtime is end time for equipment availability; Station is the information of the TT&C station the equipment belongs to; Pr is equipment's priority; St is switch time; Servce refers to service capabilities. Etasks refers to all tasks of equipment. Ett refers to the two-tuple of tasks and their possible resources. Estt refers to the twotuple of tasks and their successful scheduled resources.

Entities.
In the above agents, the following entities are used: 1) Satellite which describes satellite attribute information, such as orbit type, lifetime, TT&C frequency band, operation phase, equipment preference, use attributes (manned, military, civilian), static priority; 2) Task that describes the attribute information of TT&C tasks, such as start time and end time of a task, task type (injected, TT&C's, orbital, general), task nature (normal, emergency), task category (combat, joint debugging), task periodicity, task duration; 3) User Preference which describes the preferences in the process of TT&C scheduling, such as time preference, equipment preference. 4) Visible Time Window describes the visible time segments of ground stations to satellites, during which the satellite can be measured and controlled. Its attributes are: start time, end time, duration, owning satellite, owning station, priority value, type of laps (rising, falling).

Analysis of the characteristics of MSTCRS
The MSTCRS problem is characterized by high complexity, high conflicts, and multiple constraints. It is mainly manifested in the following aspects: a) More satellites and fewer stations. b) Satellite, TT&C equipment and TT&C requirements are various, and have their own characteristics. c) There are many constraints in the scheduling process, such as time constraints, TT&C task constraints, TT&C equipment constraints, satellite constraints, etc. Based on the above analysis, the constraints of MSTCRS are as follows: a) A set of equipment tracks one satellite at a time until the end of the visible time window. b) One TT&C task can only select one visible time window to execute. c) Telemetry tasks and telecontrol tasks of a satellite can be performed in parallel. d) The frequency band of the TT&C equipment and the satellite must match with each other. e) There must be a time interval determined by the satellite's characteristics between two consecutive tasks of a same satellite. f) When two tasks in different satellites are executed continuously on a piece of equipment, the interval time between them is greater than or equal to the switching time of the equipment. g) The key issue of MSTCRS is to schedule visible time window to corresponding task. The scheduling target aims to maximize the satisfaction of TT&C tasks. Based on the constraint, the MSTCRS problem model can be described as: where, vt donates the set of visible time windows, task donates set of tasks, p i donates priority of task i , x ij donates whether visible time window vt j is allocated for task i , that is : and each task can only be executed once, that is ∑ ∈ ≤ 1 and ∈ ∩ ∈ ≠ Ø where, satellite is the set of satellites. Sf refers to frequency band of satellite. DF refers to frequency band equipment.
where tstart is the start time of task, tend is the end time of task. vtstart is the start of visible time widow. vtend is the end of visible time widow. tdur is the duration of task. St is the switch time of equipment.

Algorithm design
This section describes the algorithms in TT&C resource scheduling method proposed. The first algorithm is called Comprehensive Weighted Priority Determination Method (CWPDM) which determines the order of resource scheduling. CWPDM runs in running rules of agent. Then we describe the overall process of resource scheduling which is called Multi-Satellite TT&C Resource Scheduling Algorithm Based on Multi-Agent Technology and Comprehensive Weighted Priority Determination Method (MSTCRSA). In the method, agents are used as architecture. They are responsible for transmitting information such as task set, scheduling result, agent status, etc. CWPDM is one of running rules of agent and can select an optimal couple of task and resource. Before CWPDM begins, we assign priority values to factors that can affect resource scheduling results. The priority value is determined by the degree of impact on resource scheduling. The higher the priority is, the bigger the priority value is. Generally speaking, a spacecraft with the characteristic of LEO, short-life, military, new, etc., has higher priority. Then we calculate the comprehensive priority value of factors of each element in the two-tuple DATA which consists of tasks and possible resources allocated to them, and select the resource with the highest priority value to allocate for a task; if there are elements with the same priority value, we choose the one with fewer resource conflicts between visible time windows. The priority value and the items of influencing factors can be adjusted according to the requirements of person and resources. The factors that affect the static priority of resources in step (4) of CWPDM include the attributes of the tasks, such as task type, task nature, task category. And the attributes of the spacecraft, such as orbit type, lifetime, using attributes, the priority of equipment, etc.
The factors of dynamic resource priority in the step (4)  Output: SCHEDULE which is the result of TT&C resource scheduling. Prerequisites: Each Agent has been started and initialized.

Begin
(1)Manager agent gets MbeforeTasks from batch tasks that are newly created according to the TT&C requirements, tasks that need to reallocate resources due to equipment or satellite failures, and emergency tasks; (2)If the number of elements in the TT is not zero, and the number of MbeforeTasks is large, the tasks that have not been executed in the TT are integrated into MbeforeTasks to reallocate resources; (3)Manager agent sends MbeforeTasks to task agent to preprocess; (4)Manager agent sends MafterTasks processed by task agent to station agents; Station agents send them to their equipment agents; (5)According to the task constraints, time constraints, resource constraints, preferences and other factors, equipment agents allocates TT&C resources for these tasks to make up TTA, a two-tuple of tasks and resources allocated to tasks. Then, they traverse all visible time windows in the equipment agent and calculate the number of conflicts between visible time windows; (6)Traversing each element in the TTA and calculating its priority value according to CWPDM; (7)The elements in the TTA are compared with the elements in the TTB, a two-tuple likes TTA. Besides, when tasks have been allocated resources successfully and have not yet been executed in station, if resource contention occurs and the elements in the TTA have a higher priority, tasks are need to re-allocate resources. Then updating TTA, TTB, and merge them into TTA'; (8)While there are tasks that have not been allocated resources do (9) Manager agent sends the resource allocation signal to station agents, and station agents send it to equipment agents; (10) Each equipment agent receives the signal, and selects the element with the highest priority in the TTA' and feeds back it to the station agent it belongs to; (11) Each station agent selects the optimal element from its equipment agents according to CWPDM and equipment's resource utilization, and feeds it back to manager agent; (12) Manager agent selects the optimal one from the resource allocation results sent by all station agents, and feeds back the result to all station agents. Then station agents return it to equipment agents.
Each equipment agent receives the result, and then updates the elements in the TTA' and the priority of corresponding elements. After that, sending the message that resource update has occurred to the station agent it belongs to. Station agent feeds it back to the manager agent; (14) After receiving the messages from station agents, manager agent completes the resource allocation of a task, stores the element made up of task and the resource which is allocated to into SCHEDULE, and updates MafterTasks.

Experimental scenarios
The experimental scenarios are divided into two categories: Scenario 1: High-volume tasks from TT&C requirements; Scenario 2: some TT&C tasks that occur during the scheduling process. a) Data Preparation Satellite: 100 satellites which are simulated by STK according to real satellites' parameter information. Station: 20 ground stations. TT&C Task: the TT&C tasks of each satellite are basically 2 laps for ascending laps and 2 laps for descending laps every day. There are about 400 TT&C tasks every day, which simulates the supplydemand relationship of "more satellites and fewer stations".
Station's visible time window to satellite: STK produces visible time windows based on the satellite and station parameter information. b) Experiment Procedure Scenario 1: We prepare 4 groups of TT&C tasks. They are tasks of one day, three days, five days, and seven days. Then we use these data to do experiment to verify the efficiency of MSTCRSA, and record resource schedule results and running times.
Scenario 2: First, we prepare TT&C tasks of one day for 3 groups, and call MSTCRSA to allocate resources for them; Then we prepare 30 unexpected TT&C tasks for each group, and respectively call the traditional algorithm (TA) and MSTCRSA; Finally recording running time. TA is the method of multi-satellite TT&C resource scheduling without using agent technology.

Experimental Results
We analyze the experiment results from the following three aspects: the weighted satisfaction of TT&C tasks, the weighted resource utilization, and running time. 4 groups of data are used, and the experimental results are shown in the table below.   As shown above, Table 1 and Figure 2 are the experimental results of Scenario 1. It can be seen that task satisfaction is above 99%, and the resource utilization rate is above 80%. And as the number of tasks increases, the running time is line-like. MSTCRSA is suitable for the scene of high-volume TT&C tasks with "more satellites and fewer stations". When encountering unexpected situations as shown in Scenario 2, it can be seen from table 2 and figure 3 that the scheduling time of MSTCRSA is much less than TA and is only a quarter of TA. Figure4 is the gantt chart of scheduling results in scenario 1. It displays the time and equipment distribution. In summary, MSTCRSA proposed in this paper is highly efficient to solve the problem of MSTCRS.

Conclusion
In this paper, we analyze the characteristics and engineering requirements of MSTCRS, establish the agent optimization model, propose MSTCRSA to complete TT&C resource allocation, and simulate the real application scenario of "more satellites, fewer stations" to do experiments. Through large amount of experiments, MSTCRSA is proved to be efficient. It improves the efficiency, adaptability and the satisfaction degree of TT&C resource allocation. And it can solve the scheduling plan adjustment caused by perturbational factors during the execution of resource scheduling plan, and quickly output the new scheduling plan that takes into account the constraints of original scheduling plan.
In the future, we plan to further study influencing factors of MSTCRS and these factors' priority values.