# Dynamic Relay Satellite Scheduling Based on ABC-TOPSIS Algorithm

Authors: Shufeng Zhuang; Zhendong Yin; Zhilu Wu; Xiaoguang Chen
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Tracking and Data Relay Satellite System (TDRSS) is a space-based telemetry, tracking, and command system, which represents a research field of the international communication. The issue of the dynamic relay satellite scheduling, which focuses on assigning time resource to user tasks, has been an important concern in the TDRSS system. In this paper, the focus of study is on the dynamic relay satellite scheduling, whose detailed process consists of two steps: the initial relay satellite scheduling and the selection of dynamic scheduling schemes. To solve the dynamic scheduling problem, a new scheduling algorithm ABC-TOPSIS is proposed, which combines artificial bee colony (ABC) and technique for order preference by similarity to ideal solution (TOPSIS). The artificial bee colony algorithm is performed to solve the initial relay satellite scheduling. In addition, the technique for order preference by similarity to ideal solution is adopted for the selection of dynamic scheduling schemes. Plenty of simulation results are presented. The simulation results demonstrate that the proposed method provides better performance in solving the dynamic relay satellite scheduling problem in the TDRSS system.


---

## Body

## 1. Introduction

Tracking and Data Relay Satellite System (TDRSS) is a system which can provide service of data relaying, continuous tracking, and TT&C (telemetry, tracking, and command) for the spacecrafts of LEO (Low Earth Orbit) and MEO (Middle Earth Orbit) and also between spacecrafts and ground stations. As a space-based telemetry, tracking, and command system, the TDRSS represents a research field of the international communication field. To keep pace with the development of earth observation, military reconnaissance, and deep space exploration in the field of aeronautics and astronautics, the data transmission of the relay satellite presents the characteristics of large capacity, high speed, and relay tasks diversification [1]. It is in turn necessary to improve the time resource utilization of the relay satellite for processing tasks.The dynamic relay satellite scheduling is that the task plan management center of the relay satellite allocates the time resource of the relay satellite for different user tasks scientifically, according to the priority and duration of user tasks. Thus in the limited time resource, the high priority sum of the scheduled tasks can be achieved. The issue of the dynamic relay satellite scheduling, which focuses on assigning time resource to user tasks, has been an important concern in the TDRSS system [2]. Different from the static scheduling, even if the initial scheduling scheme has been generated, the tasks from user satellites may be changed in the dynamic scheduling. Therefore, the initial scheduling scheme cannot satisfy the new tasks requests. In this case, the scheduling alternatives need to be regenerated and a new appropriate scheme should be selected to replace the initial scheduling scheme. The selected scheme in the dynamic scheduling is output as the final dynamic relay satellite scheduling scheme. In summary, the detailed process of the dynamic relay satellite scheduling consists of two steps: the initial relay satellite scheduling and the selection of dynamic scheduling schemes. The initial relay satellite scheduling problem is a NP-hard optimization problem with the constraints of tasks attribute, time resource, and the visual time windows between relay satellite and user satellites, and this motivates us to take swarm intelligence algorithms into account.As a branch of natural inspired algorithms, the theory of swarm intelligence is proposed and becomes a hot spot to solve the optimization problems in various areas [3]. The essence of swarm intelligence algorithms focuses on the natural phenomena of biological groups. And up to now, a variety of swarm intelligence algorithms for different biological groups have been presented, such as genetic algorithm (GA), simulated annealing (SA), ant colony optimization (ACO), particle swarm optimization (PSO), and artificial bee colony (ABC) algorithm [4, 5]. Among them, the artificial bee colony (ABC) algorithm is an intelligence-optimized algorithm deriving from the illumination of bees’ foot-seeking behavior. Due to its less parameters and strong robustness, the ABC algorithm is widely used in various areas [6]. For example, in [7], the ABC algorithm is successfully applied to solve the classical optimization problem: the traveling salesman problem. Moreover, the ABC algorithm has been applied in other aspects, such as flow shop scheduling problem [8, 9], dynamic job shop scheduling problem [10], clustering approach [11, 12], signal processing [13], and image processing [14, 15]. For the relay satellite scheduling problem, genetic algorithm is applied to generate the scheduling scheme in [16]. However, tasks priority has not been considered. After that the ACO algorithm for satellite control resource scheduling problem is presented in [17], but not for the relay satellite system. In [18], the ACO algorithm is used to solve the relay satellite scheduling problem, and the performances of ACO, GA, and SA algorithm are provided. In the relevant research, the ABC algorithm has not been mentioned and applied for relay satellite scheduling.After the completion of the initial relay satellite scheduling, the initial scheduling scheme may not be implemented immediately. And the tasks set is likely to change, which causes the variation of the relay satellite scheduling scheme. In this case, the dynamic scheduling scheme needs to replace the initial scheduling scheme. The goal of the dynamic scheduling is to select a new modified scheme, which not only has the high priority sum of the scheduled tasks, but also has the minimum schemes variation in comparison with the initial scheduling scheme. Therefore, the selection of dynamic scheduling schemes can be treated as a multiple attribute decision making (MADM) problem.The technique for order preference by similarity to ideal solution (TOPSIS) is an efficient method in dealing with MADM problems [19–21]. The critical principle of TOPSIS is to rank the alternatives according to the distance between alternatives to ideal solution [22, 23]. The alternative with the minimum distance from the positive ideal solution and the maximum distance from the negative ideal solution is chosen as the best alternative. For the last several years, the method of TOPSIS is widely applied in various fields, such as manufacturing [24], military [25], product design [26], resource allocation, and resource selection [27, 28]. As a helpful decision rule, the TOPSIS method is suitable for solving the selection problem of the dynamic scheduling schemes.In this paper, the research content focuses on the dynamic relay satellite scheduling in the TDRSS system. In detail, a new efficient scheduling algorithm ABC-TOPSIS based on artificial bee colony (ABC) and technique for order preference by similarity to ideal solution (TOPSIS) is first proposed, in order to solve the dynamic relay satellite scheduling. First, the artificial bee colony (ABC) algorithm is utilized to solve the initial relay satellite scheduling. Then by the quantization of the schemes variation between initial scheduling scheme and dynamic scheduling scheme, the selection of dynamic scheduling schemes is converted from multiple objective decision making (MODM) problem into multiple attribute decision making (MADM) problem. Thus, TOPSIS is applied to solve the selection of dynamic scheduling schemes when the tasks set proposed by user satellites has changed.The rest of this paper is organized as follows. In Section2, the dynamic relay satellite scheduling system is introduced. The ABC-TOPSIS algorithm is developed to solve the dynamic relay satellite scheduling in Section 3. In Section 4, the performance of the proposed ABC-TOPSIS algorithm is shown. The conclusions are drawn in Section 5.


## 2. Dynamic Relay Satellite Scheduling System

In the dynamic relay satellite scheduling system, the relay satellite receives tasks requests from different user satellites, including low-orbit imaging satellite, electronic satellite, and measurement satellite. Without considering the contents of the tasks, the main differences between the tasks are the duration and the priority. The purpose of the relay satellite scheduling is to allocate the time resource of the relay satellite reasonably and to generate the scheduling scheme which meets the expected target. The specific implementation process consists of two parts: the initial relay satellite scheduling and the selection of dynamic scheduling schemes. The dynamic relay satellite scheduling system diagram is shown in Figure1.Figure 1
Dynamic relay satellite scheduling system diagram.The initial relay satellite scheduling generates the daily work plan of the relay satellite. Firstly, the tasks proposed by user satellites are preprocessed to calculate the available time windows and to assign the priority. Then, the initial relay satellite scheduling model is established based on the constraint conditions and the time resource information. Finally, the initial relay scheduling model is solved by the specific scheduling algorithm. Thus the scheduling scheme can be derived and delivered to perform.Since the relay satellite is not always ready to schedule tasks, after the generation of the initial relay satellite scheduling scheme, the initial scheduling scheme cannot be implemented immediately. In this period, the tasks set would be changed dynamically: some tasks have been canceled, and some new tasks have been added. In this case, the variation of the tasks set leads to the changes in the initial relay satellite scheduling. In view of the changes of the tasks requests, a new corresponding dynamic relay satellite scheduling scheme needs to be generated. The dynamic scheduling scheme not only aims at making full use of the time resource of the relay satellite and maximizing the scheduled tasks priority sum as the initial scheduling scheme, but also minimizes the variation between the initial scheme and the dynamic scheme.The process of the dynamic relay satellite scheduling is summarized in two steps, which are the initial relay satellite scheduling and the selection of dynamic scheduling schemes. Figure2 shows the flow chat of the dynamic relay satellite scheduling based on the proposed ABC-TOPSIS algorithm.Figure 2
Flow chat of the dynamic relay satellite scheduling based on the proposed ABC-TOPSIS algorithm.


## 3. Scheduling Strategy Based on ABC-TOPSIS Algorithm

### 3.1. Mathematical Model of Initial Relay Satellite Scheduling Problem

In the initial relay satellite scheduling problem, the relay satellite has the mission of handing the tasks proposed by the user satellites. The key object is to allocate the time resource of the relay satellite for user tasks and achieve the maximum priority sum. Since the relay satellite is not always visible to user satellites, the significant constraint is that there are time windows between the relay satellite and user satellites. The tasks must be completed only within the given visual time windows. In order to establish the mathematical model of the initial relay satellite scheduling problem, some model parameters are declared as follows.


#### 3.1.1. Model Parameters

The set of the tasks is set toR=r1,r2,…,rn, where n is the number of tasks that need to be scheduled. The set of the priority of the tasks is expressed as P=p1,p2,…,pn and the set of the duration of the tasks is D={d1,d2,…,dn}. The set C={c1,c2,…,cn} represents the task contribution, which is the function of task priority pi and task duration di. Also the task decision variables are denoted by the set X={x1,x2,…,xn}, where xi∈{0,1}, i=1,2,…,n. The decision variable xi=1 represents that the task ri has been scheduled by the relay satellite, and xi=0 means that the task ri has not been scheduled.In addition, the visual time windows and time resource of the relay satellite are declared. The time interval set[SE]=si1,ei1,si2,ei2,…,sik,eik presents the set of visual time windows of the relay satellite which serve the task ri, where k is the number of visual time windows, siτ is the start time, and eiτ is the end time. The time resource of the relay satellite is denoted by the time interval TS,TE, where TS is the start time and TE is the end time.


#### 3.1.2. Objective Function

The objective of the initial relay satellite scheduling is to obtain an optimal tasks service scheme, which, in other words, means the maximization of the sum of the contribution of the scheduled tasks. The objective function of the initial relay satellite scheduling can be described as(1)max∑i=1nxici,where(2)xi=1,riis scheduled0,unless,ci=Fpi,di,ci∞1di.


#### 3.1.3. Constraints

The constraints of the initial relay satellite task scheduling are given as follows.(3)Ts≤Ti≤TE,Ts≤Ti+di≤TE(4)Ti≥siτ1≤τ≤kifxi=1(5)Ti+di≤eiτ1≤τ≤kifxi=1.For ∀ri∈[r1,rn], ∀rj∈[r1,rn], i≠j(6)Ti≥Tj+djorTi+di≤Tj,where Ti is the start execution time of the task ri. Constraints (3), (4), and (5) bound the time period for the tasks. Constraint (3) represents that tasks whose duration, more than the length of the relay satellite time resource, cannot be scheduled. Constraint (4) and constraint (5) imply that the tasks must be scheduled only within the given visual time windows. Constraint (6) means that, at the same time, the relay satellite can only handle one task. The time resource is incapable of being shared by multiple tasks at the same time. If the current task is not yet completed, new tasks cannot be executed.As expressed in Section3.1.1, the task contribution variable is the function of task priority pi and task duration di. To simplify the model solving process, it is assumed that the construction of the feasible solution is based on the time sequence. After the end of the current task, the new task will be scheduled immediately for execution. Therefore, the time resource of the relay satellite can be fully utilized. In this case, the task contribution variable is only related to the task priority. Then the objective function (1) is simplified as(7)max∑i=1nxipi.


### 3.2. Initial Relay Satellite Scheduling Based on ABC Algorithm

Since the optimization problem in (7) is generally a NP-hard combinatorial problem, this requires an efficient optimization algorithm for the initial relay satellite scheduling. In this section, the artificial bee colony algorithm is applied to solve the relay satellite scheduling problem.The artificial bee colony (ABC) algorithm is an intelligence-optimized algorithm deriving from the illumination of bees’ foot-seeking behavior. There are three kinds of roles in the bee swarm intelligence model, which are scout bees, onlooker bees, and employed bees. In the beginning, without prior knowledge, all bees are identified as scout bees with the behavior of the random search around hives. The richness of the food sources is compared and the relatively rich food source is selected as the searching routes of employed bees [29]. Then the employed bees take charge of searching food around the food sources in their memory; after that, they share the food amount information with the onlooker bees by dancing in the nearby hive. Then the onlooker bees would select employed bees to follow according to the information provided by employed bees [30]. The artificial bee colony algorithm for the initial relay satellite scheduling problem can be described as follows.(1) Define the transition probability of scout bees and onlooker bees Pri,k,t, which means the probability that the task ri is scheduled in thekth visual time window at the momentt.The transition probability of scout bees can be expressed as(8)Pri,k,t=piα1/diβ∑ri∈allowk,tpiα1/diβ,ri∈allowk,t0,ri∉allowk,t,where pi is the priority of the task ri and di is the duration of the task ri. α and β are the weight factors. The set allow k,t represents the allowed tasks set for scheduling. According to (8), the task with higher priority and shorter duration has higher probability to be scheduled.The transition probability of onlooker bees is written as(9)Pri,k,t=piα1/diβφγ∑ri∈allowk,tpiα1/diβφγ,ri∈allowk,t0,ri∉allowk,t,where φ represents the leading factor, which is the leading information generated by employed bees. The corresponding weight is denoted as γ.(2) In the ABC algorithm, pseudo-random proportion rule is adopted, which can be described as follows:(a) generate a uniformly distributed random numberq in the interval [0,1],(b) ifq≤q0 (q0 is a fixed parameter value), then (10)ri=arg⁡maxri∈allowk,t⁡Pri,k,t,(c) ifq>q0, then choose the task according to Pri,k,t.(3) In each iteration, the optimal solution is set as the position of employed bees. Then, the employed bees release the leading information to attract the onlooker bees. After each iteration, the leading factor is updated. The updated rules can be described as(11)φj+1=φj+qg∗Ccur,where j is the current iteration. qg represents the leading factor update increase coefficient. And Ccur is the normalized fitness, which is defined as follows.(12)Ccur=fitmax∑n=1SNfitn,where fitn is the fitness of the nth solution. The calculation equation is expressed as (13)fitn=1+fn,fn>011+absfn,fn<0.In (13), fn is the optimal solution till current iteration in the ABC algorithm for the objective function (7).(4) In order to avoid the excessive accumulation of leading factor, the leading factor range is limited to [φmin, φmax].(14)φj+1=φj,φmin≤φj≤φmaxφmax,φj>φmaxφmin,φj<φmin.The ABC algorithm is terminated when it reaches the maximum number of iterations [12] and the scheduling scheme with the maximum priority sum is the final output result for the initial relay satellite scheduling problem. As is seen from the above, in the ABC algorithm, the scout bees search the solution space-based on the constraint conditions, which ensures the randomness and avoids falling into the local optimal solution. The employed bees correspond to the optimal solution till current iteration. They keep the elite feature and maintain attraction to the onlooker bees. The onlooker bees select employed bees to follow according to the leading information. The prospect of the mechanism is to import positive feedback and guarantee the convergence of the algorithm. Through the coordination of three kinds of bees, the ABC algorithm achieves the effective optimization ability of randomness and convergence.


### 3.3. Selection of Dynamic Scheduling Schemes Based on TOPSIS Algorithm

After the generation of the initial relay satellite scheduling scheme, it waits for the implementation of the relay satellite. Generally, the initial relay satellite scheduling scheme would not be made any adjustments. However, in fact, since the variation of the user satellites requirements, some of the tasks that have been proposed may be canceled. Or in addition, some new tasks are inserted, especially some high priority tasks. The change of the tasks has a direct impact on the set of the tasksR. What is more, the parameter sets of the tasks priority P and tasks duration D also change, respectively. In this case, the initial scheduling scheme cannot be performed completely. In consideration of the changes of the tasks requests, it is necessary to make the dynamic adjustment and to generate a new corresponding dynamic relay satellite scheduling scheme based on the initial scheduling scheme.Under the dynamic condition, the adjustment of the initial scheduling scheme must follow certain principles. No matter how the tasks set changes, one of the major objectives is to achieve the high tasks priority sum. The other objective is to minimize the variation between initial scheme and dynamic scheme. Once the initial scheduling scheme is generated, the user satellites will receive the tasks implementation plan from the relay satellite. And the tasks, which are scheduled, enter the state of pending execution. Then the user satellites may make the corresponding work arrangements for tasks. Therefore a large-scale dynamic adjustment is bound to affect the user satellites’ future decision.Based on the above analysis, the dynamic scheduling problem is a multiple objective decision making (MODM) problem. One objective of the dynamic scheduling is to allocate the time resource of the relay satellite for user tasks and achieve the maximum priority sum. The other is to select a new dynamic scheduling scheme, which has the minimal change to the initial scheduling scheme.In order to facilitate solving the multiple objective decision making problem of the dynamic relay satellite scheduling, firstly it is essential to quantize the schemes variation between the initial scheduling scheme and the dynamic scheduling scheme. Assume that the tasks set scheduled in the initial scheduling scheme is denoted asRini, while the tasks set scheduled in the dynamic scheduling scheme is expressed as Rdyn. The variableChange(r) indicates whether the task r changes between the initial scheduling scheme and the dynamic scheduling scheme. The variableChange(r) is defined as the following equation. (15)Changer=0,r∈Riniandr∈Rdyn1,r∈Riniandr∉Rdyn.Thus, the schemes variation between the initial scheduling scheme and the dynamic scheduling scheme can be written as(16)VAR=∑r∈RiniChangerThe solving process of the dynamic scheduling problem is to select a new modified scheme, which has the minimum schemes variation in comparison with the initial scheduling scheme. The detailed steps are given as follows.(1) When the change of the tasks set happens after initial scheduling, reorganize the model parameters of the sets, and use the ABC algorithm to generate several new dynamic scheduling schemes as Section 3.2. The dynamic scheduling schemes set is denoted as S={s1,s2,…,sa}, where a is the number of the new dynamic scheduling schemes. The scheduled tasks priority sum set of the dynamic scheduling schemes is written as P(s)=ps1,ps2,…,psa.(2) Compare the new dynamic scheduling schemes with the initial scheduling scheme, and calculate the schemes variations for all newly generated scheduling schemes with reference to the initial scheduling scheme, according to (15) and (16). And the schemes variations set is represented as VAR(s)=vars1,vars2,…,varsa.(3) After the completion of step (1) and step (2), the dynamic scheduling problem is transformed from multiple objective decision making (MODM) problem into multiple attribute decision making (MADM) problem. The MADM problem of the dynamic scheduling can be denoted as (17)DRs∈SPs,VARs.The dynamic scheduling problem can be depicted as the use of the decision ruleDR to choose a best scheduling scheme from the set S, in accordance with the attribute P(s) and VAR(s). In this paper, the TOPSIS (Technique for Order Preference by Similarity to an Ideal Solution) algorithm is adopted as the decision rule DR for the dynamic scheduling, which is described as follows.(a) Construct normalized decision matrix(18)Zij′=fij∑i=1afij2,where i∈{1,2…,a} and j∈{1,2}. fij is thejth attribute value of the scheme i. fi1=p(si), and fi2=var(si).(b) Construct the weighted normalized decision matrix(19)Zij=wjZij′,where wj is the weight value of thejth attribute. The value wj represents the importance of each attribute.(c) Determine the positive ideal solution (PIS) and negative ideal solution (NIS)(20)PIS=maxi⁡Zij∣j=1,mini⁡Zij∣j=2NIS=mini⁡Zij∣j=1,maxi⁡Zij∣j=2.(d) Calculate the separation measures of each alternatives from the PIS and NIS(21)CiPIS=∑j=12Zij-PISj2CiNIS=∑j=12Zij-NISj2.(e) Calculate the relative closeness of theith scheduling scheme with respect to the ideal solution(22)Ci=CiNISCiPIS+CiNIS.The set of the dynamic scheduling schemes can now be ranked according to the descending order ofCi. By using the value Ci, we can get the appraisal ranks for each scheme. The maximum value of Ci corresponds to the best dynamic scheduling scheme.


## 3.1. Mathematical Model of Initial Relay Satellite Scheduling Problem

In the initial relay satellite scheduling problem, the relay satellite has the mission of handing the tasks proposed by the user satellites. The key object is to allocate the time resource of the relay satellite for user tasks and achieve the maximum priority sum. Since the relay satellite is not always visible to user satellites, the significant constraint is that there are time windows between the relay satellite and user satellites. The tasks must be completed only within the given visual time windows. In order to establish the mathematical model of the initial relay satellite scheduling problem, some model parameters are declared as follows.


### 3.1.1. Model Parameters

The set of the tasks is set toR=r1,r2,…,rn, where n is the number of tasks that need to be scheduled. The set of the priority of the tasks is expressed as P=p1,p2,…,pn and the set of the duration of the tasks is D={d1,d2,…,dn}. The set C={c1,c2,…,cn} represents the task contribution, which is the function of task priority pi and task duration di. Also the task decision variables are denoted by the set X={x1,x2,…,xn}, where xi∈{0,1}, i=1,2,…,n. The decision variable xi=1 represents that the task ri has been scheduled by the relay satellite, and xi=0 means that the task ri has not been scheduled.In addition, the visual time windows and time resource of the relay satellite are declared. The time interval set[SE]=si1,ei1,si2,ei2,…,sik,eik presents the set of visual time windows of the relay satellite which serve the task ri, where k is the number of visual time windows, siτ is the start time, and eiτ is the end time. The time resource of the relay satellite is denoted by the time interval TS,TE, where TS is the start time and TE is the end time.


### 3.1.2. Objective Function

The objective of the initial relay satellite scheduling is to obtain an optimal tasks service scheme, which, in other words, means the maximization of the sum of the contribution of the scheduled tasks. The objective function of the initial relay satellite scheduling can be described as(1)max∑i=1nxici,where(2)xi=1,riis scheduled0,unless,ci=Fpi,di,ci∞1di.


### 3.1.3. Constraints

The constraints of the initial relay satellite task scheduling are given as follows.(3)Ts≤Ti≤TE,Ts≤Ti+di≤TE(4)Ti≥siτ1≤τ≤kifxi=1(5)Ti+di≤eiτ1≤τ≤kifxi=1.For ∀ri∈[r1,rn], ∀rj∈[r1,rn], i≠j(6)Ti≥Tj+djorTi+di≤Tj,where Ti is the start execution time of the task ri. Constraints (3), (4), and (5) bound the time period for the tasks. Constraint (3) represents that tasks whose duration, more than the length of the relay satellite time resource, cannot be scheduled. Constraint (4) and constraint (5) imply that the tasks must be scheduled only within the given visual time windows. Constraint (6) means that, at the same time, the relay satellite can only handle one task. The time resource is incapable of being shared by multiple tasks at the same time. If the current task is not yet completed, new tasks cannot be executed.As expressed in Section3.1.1, the task contribution variable is the function of task priority pi and task duration di. To simplify the model solving process, it is assumed that the construction of the feasible solution is based on the time sequence. After the end of the current task, the new task will be scheduled immediately for execution. Therefore, the time resource of the relay satellite can be fully utilized. In this case, the task contribution variable is only related to the task priority. Then the objective function (1) is simplified as(7)max∑i=1nxipi.


## 3.1.1. Model Parameters

The set of the tasks is set toR=r1,r2,…,rn, where n is the number of tasks that need to be scheduled. The set of the priority of the tasks is expressed as P=p1,p2,…,pn and the set of the duration of the tasks is D={d1,d2,…,dn}. The set C={c1,c2,…,cn} represents the task contribution, which is the function of task priority pi and task duration di. Also the task decision variables are denoted by the set X={x1,x2,…,xn}, where xi∈{0,1}, i=1,2,…,n. The decision variable xi=1 represents that the task ri has been scheduled by the relay satellite, and xi=0 means that the task ri has not been scheduled.In addition, the visual time windows and time resource of the relay satellite are declared. The time interval set[SE]=si1,ei1,si2,ei2,…,sik,eik presents the set of visual time windows of the relay satellite which serve the task ri, where k is the number of visual time windows, siτ is the start time, and eiτ is the end time. The time resource of the relay satellite is denoted by the time interval TS,TE, where TS is the start time and TE is the end time.


## 3.1.2. Objective Function

The objective of the initial relay satellite scheduling is to obtain an optimal tasks service scheme, which, in other words, means the maximization of the sum of the contribution of the scheduled tasks. The objective function of the initial relay satellite scheduling can be described as(1)max∑i=1nxici,where(2)xi=1,riis scheduled0,unless,ci=Fpi,di,ci∞1di.


## 3.1.3. Constraints

The constraints of the initial relay satellite task scheduling are given as follows.(3)Ts≤Ti≤TE,Ts≤Ti+di≤TE(4)Ti≥siτ1≤τ≤kifxi=1(5)Ti+di≤eiτ1≤τ≤kifxi=1.For ∀ri∈[r1,rn], ∀rj∈[r1,rn], i≠j(6)Ti≥Tj+djorTi+di≤Tj,where Ti is the start execution time of the task ri. Constraints (3), (4), and (5) bound the time period for the tasks. Constraint (3) represents that tasks whose duration, more than the length of the relay satellite time resource, cannot be scheduled. Constraint (4) and constraint (5) imply that the tasks must be scheduled only within the given visual time windows. Constraint (6) means that, at the same time, the relay satellite can only handle one task. The time resource is incapable of being shared by multiple tasks at the same time. If the current task is not yet completed, new tasks cannot be executed.As expressed in Section3.1.1, the task contribution variable is the function of task priority pi and task duration di. To simplify the model solving process, it is assumed that the construction of the feasible solution is based on the time sequence. After the end of the current task, the new task will be scheduled immediately for execution. Therefore, the time resource of the relay satellite can be fully utilized. In this case, the task contribution variable is only related to the task priority. Then the objective function (1) is simplified as(7)max∑i=1nxipi.


## 3.2. Initial Relay Satellite Scheduling Based on ABC Algorithm

Since the optimization problem in (7) is generally a NP-hard combinatorial problem, this requires an efficient optimization algorithm for the initial relay satellite scheduling. In this section, the artificial bee colony algorithm is applied to solve the relay satellite scheduling problem.The artificial bee colony (ABC) algorithm is an intelligence-optimized algorithm deriving from the illumination of bees’ foot-seeking behavior. There are three kinds of roles in the bee swarm intelligence model, which are scout bees, onlooker bees, and employed bees. In the beginning, without prior knowledge, all bees are identified as scout bees with the behavior of the random search around hives. The richness of the food sources is compared and the relatively rich food source is selected as the searching routes of employed bees [29]. Then the employed bees take charge of searching food around the food sources in their memory; after that, they share the food amount information with the onlooker bees by dancing in the nearby hive. Then the onlooker bees would select employed bees to follow according to the information provided by employed bees [30]. The artificial bee colony algorithm for the initial relay satellite scheduling problem can be described as follows.(1) Define the transition probability of scout bees and onlooker bees Pri,k,t, which means the probability that the task ri is scheduled in thekth visual time window at the momentt.The transition probability of scout bees can be expressed as(8)Pri,k,t=piα1/diβ∑ri∈allowk,tpiα1/diβ,ri∈allowk,t0,ri∉allowk,t,where pi is the priority of the task ri and di is the duration of the task ri. α and β are the weight factors. The set allow k,t represents the allowed tasks set for scheduling. According to (8), the task with higher priority and shorter duration has higher probability to be scheduled.The transition probability of onlooker bees is written as(9)Pri,k,t=piα1/diβφγ∑ri∈allowk,tpiα1/diβφγ,ri∈allowk,t0,ri∉allowk,t,where φ represents the leading factor, which is the leading information generated by employed bees. The corresponding weight is denoted as γ.(2) In the ABC algorithm, pseudo-random proportion rule is adopted, which can be described as follows:(a) generate a uniformly distributed random numberq in the interval [0,1],(b) ifq≤q0 (q0 is a fixed parameter value), then (10)ri=arg⁡maxri∈allowk,t⁡Pri,k,t,(c) ifq>q0, then choose the task according to Pri,k,t.(3) In each iteration, the optimal solution is set as the position of employed bees. Then, the employed bees release the leading information to attract the onlooker bees. After each iteration, the leading factor is updated. The updated rules can be described as(11)φj+1=φj+qg∗Ccur,where j is the current iteration. qg represents the leading factor update increase coefficient. And Ccur is the normalized fitness, which is defined as follows.(12)Ccur=fitmax∑n=1SNfitn,where fitn is the fitness of the nth solution. The calculation equation is expressed as (13)fitn=1+fn,fn>011+absfn,fn<0.In (13), fn is the optimal solution till current iteration in the ABC algorithm for the objective function (7).(4) In order to avoid the excessive accumulation of leading factor, the leading factor range is limited to [φmin, φmax].(14)φj+1=φj,φmin≤φj≤φmaxφmax,φj>φmaxφmin,φj<φmin.The ABC algorithm is terminated when it reaches the maximum number of iterations [12] and the scheduling scheme with the maximum priority sum is the final output result for the initial relay satellite scheduling problem. As is seen from the above, in the ABC algorithm, the scout bees search the solution space-based on the constraint conditions, which ensures the randomness and avoids falling into the local optimal solution. The employed bees correspond to the optimal solution till current iteration. They keep the elite feature and maintain attraction to the onlooker bees. The onlooker bees select employed bees to follow according to the leading information. The prospect of the mechanism is to import positive feedback and guarantee the convergence of the algorithm. Through the coordination of three kinds of bees, the ABC algorithm achieves the effective optimization ability of randomness and convergence.


## 3.3. Selection of Dynamic Scheduling Schemes Based on TOPSIS Algorithm

After the generation of the initial relay satellite scheduling scheme, it waits for the implementation of the relay satellite. Generally, the initial relay satellite scheduling scheme would not be made any adjustments. However, in fact, since the variation of the user satellites requirements, some of the tasks that have been proposed may be canceled. Or in addition, some new tasks are inserted, especially some high priority tasks. The change of the tasks has a direct impact on the set of the tasksR. What is more, the parameter sets of the tasks priority P and tasks duration D also change, respectively. In this case, the initial scheduling scheme cannot be performed completely. In consideration of the changes of the tasks requests, it is necessary to make the dynamic adjustment and to generate a new corresponding dynamic relay satellite scheduling scheme based on the initial scheduling scheme.Under the dynamic condition, the adjustment of the initial scheduling scheme must follow certain principles. No matter how the tasks set changes, one of the major objectives is to achieve the high tasks priority sum. The other objective is to minimize the variation between initial scheme and dynamic scheme. Once the initial scheduling scheme is generated, the user satellites will receive the tasks implementation plan from the relay satellite. And the tasks, which are scheduled, enter the state of pending execution. Then the user satellites may make the corresponding work arrangements for tasks. Therefore a large-scale dynamic adjustment is bound to affect the user satellites’ future decision.Based on the above analysis, the dynamic scheduling problem is a multiple objective decision making (MODM) problem. One objective of the dynamic scheduling is to allocate the time resource of the relay satellite for user tasks and achieve the maximum priority sum. The other is to select a new dynamic scheduling scheme, which has the minimal change to the initial scheduling scheme.In order to facilitate solving the multiple objective decision making problem of the dynamic relay satellite scheduling, firstly it is essential to quantize the schemes variation between the initial scheduling scheme and the dynamic scheduling scheme. Assume that the tasks set scheduled in the initial scheduling scheme is denoted asRini, while the tasks set scheduled in the dynamic scheduling scheme is expressed as Rdyn. The variableChange(r) indicates whether the task r changes between the initial scheduling scheme and the dynamic scheduling scheme. The variableChange(r) is defined as the following equation. (15)Changer=0,r∈Riniandr∈Rdyn1,r∈Riniandr∉Rdyn.Thus, the schemes variation between the initial scheduling scheme and the dynamic scheduling scheme can be written as(16)VAR=∑r∈RiniChangerThe solving process of the dynamic scheduling problem is to select a new modified scheme, which has the minimum schemes variation in comparison with the initial scheduling scheme. The detailed steps are given as follows.(1) When the change of the tasks set happens after initial scheduling, reorganize the model parameters of the sets, and use the ABC algorithm to generate several new dynamic scheduling schemes as Section 3.2. The dynamic scheduling schemes set is denoted as S={s1,s2,…,sa}, where a is the number of the new dynamic scheduling schemes. The scheduled tasks priority sum set of the dynamic scheduling schemes is written as P(s)=ps1,ps2,…,psa.(2) Compare the new dynamic scheduling schemes with the initial scheduling scheme, and calculate the schemes variations for all newly generated scheduling schemes with reference to the initial scheduling scheme, according to (15) and (16). And the schemes variations set is represented as VAR(s)=vars1,vars2,…,varsa.(3) After the completion of step (1) and step (2), the dynamic scheduling problem is transformed from multiple objective decision making (MODM) problem into multiple attribute decision making (MADM) problem. The MADM problem of the dynamic scheduling can be denoted as (17)DRs∈SPs,VARs.The dynamic scheduling problem can be depicted as the use of the decision ruleDR to choose a best scheduling scheme from the set S, in accordance with the attribute P(s) and VAR(s). In this paper, the TOPSIS (Technique for Order Preference by Similarity to an Ideal Solution) algorithm is adopted as the decision rule DR for the dynamic scheduling, which is described as follows.(a) Construct normalized decision matrix(18)Zij′=fij∑i=1afij2,where i∈{1,2…,a} and j∈{1,2}. fij is thejth attribute value of the scheme i. fi1=p(si), and fi2=var(si).(b) Construct the weighted normalized decision matrix(19)Zij=wjZij′,where wj is the weight value of thejth attribute. The value wj represents the importance of each attribute.(c) Determine the positive ideal solution (PIS) and negative ideal solution (NIS)(20)PIS=maxi⁡Zij∣j=1,mini⁡Zij∣j=2NIS=mini⁡Zij∣j=1,maxi⁡Zij∣j=2.(d) Calculate the separation measures of each alternatives from the PIS and NIS(21)CiPIS=∑j=12Zij-PISj2CiNIS=∑j=12Zij-NISj2.(e) Calculate the relative closeness of theith scheduling scheme with respect to the ideal solution(22)Ci=CiNISCiPIS+CiNIS.The set of the dynamic scheduling schemes can now be ranked according to the descending order ofCi. By using the value Ci, we can get the appraisal ranks for each scheme. The maximum value of Ci corresponds to the best dynamic scheduling scheme.


## 4. Simulation Results

In this section, the performances of the proposed dynamic scheduling method ABC-TOPSIS are shown in the following simulation results. Assume a system with a relay satellite and 10 user satellites. Each user satellite has 3 tasks requests. Thus the number of tasks is 30. The total time resource of the relay satellite is set to 100 minutes. The relay satellite arranges two visual time windows for each user satellite. The tasks priority and duration are set between 1 and 15. Table1 shows the initial scheduling parameters.Table 1
Scheduling parameters.
User satellite Time windowsof relay satellite/minute Duration of each task/minutes Priority of each task Satellite 1 [ 10   30 ]  [ 70   95 ] [ 11   9   6 ] [ 4   6   6 ] Satellite 2 [ 15   35 ]  [ 50   80 ] [ 13   8   7 ] [ 13   5   8 ] Satellite 3 [ 12   32 ]  [ 60   96 ] [ 10   4   5 ] [ 2   14   8 ] Satellite 4 [ 5   25 ]  [ 55   70 ] [ 7   6   10 ] [ 5   9   10 ] Satellite 5 [ 17   36 ]  [ 40   62 ] [ 11   6   4 ] [ 11   6   4 ] Satellite 6 [ 8   50 ]  [ 55   70 ] [ 8   5   8 ] [ 7   7   7 ] Satellite 7 [ 30   55 ]  [ 80   93 ] [ 10   8   5 ] [ 9   8   5 ] Satellite 8 [ 22   43 ]  [ 66   88 ] [ 9   9   6 ] [ 6   15   9 ] Satellite 9 [ 20   50 ]  [ 80   99 ] [ 7   12   9 ] [ 5   12   7 ] Satellite 10 [ 18   38 ]  [ 45   78 ] [ 10   5   8 ] [ 10   3   8 ]Figure3 shows a generated initial scheduling scheme with the ABC algorithm. In the ABC algorithm for the initial relay satellite scheduling, the number of bees is set to 100, and the maximum number of iterations is 50. q0 = 0.9, qg =0.1, the weight factors α,β, and γ are set to 1.5. The leading factor range values φmin and φmax are equal to 0.5 and 8, respectively. In Figure 3, the yellow lines represent the visual time windows between relay satellite and user satellites. In addition, the black lines are the scheduled tasks. The length of the black lines corresponds the duration of tasks. The detailed tasks scheduled sequence is shown in Table 2. It can be seen that the time resource of the relay satellite is fully utilized with the constraints of time windows. Moreover, the initial scheduling scheme achieves the optimal solution with the priority sum of scheduled tasks equaling to 122.Table 2
Scheduled tasks.
Scheduled task User satellite Priority Duration/minute R 3 Satellite 4 10 [ 5   15 ] R 2 Satellite 3 14 [ 15   19 ] R 3 Satellite 2 8 [ 19   26 ] R 2 Satellite 6 7 [ 26   31 ] R 3 Satellite 8 9 [ 31   37 ] R 2 Satellite 7 8 [ 37   45 ] R 2 Satellite 5 6 [ 45   51 ] R 1 Satellite 10 10 [ 51   61 ] R 2 Satellite 4 9 [ 61   67 ] R 3 Satellite 3 8 [ 67   72 ] R 3 Satellite 1 6 [ 72   78 ] R 2 Satellite 8 15 [ 78   87 ] R 2 Satellite 9 12 [ 87   99 ]Figure 3
Scheduling result based on ABC algorithm.Table3 compares the performances between ABC, ACO, SA, and GA algorithms for the initial scheduling. The total iteration times of four algorithms are all set to 50. According to Table 3, the ABC and ACO algorithms obtain the optimal priority sum, while the SA and GA algorithms fall into the local optimal solution. The ACO and GA algorithms take larger iteration times to converge, with respect to the ABC and SA algorithm. Therefore, with the comprehensive comparison of the convergence and optimization ability, the ABC algorithm turns to be more effective than other three algorithms. This is mainly due to the reasons that, in the ABC algorithm, scout bees, onlooker bees, and employed bees perform own duties efficiently. The scout bees search the solution space randomly based on the constraint conditions, which ensures the randomness and avoids falling into the local optimal solution. The employed bees keep the elite feature and maintain attraction to the onlooker bees, which guarantee the convergence of the algorithm.Table 3
Performance of ABC, ACO, SA, and GA algorithms.
Algorithm Optimal priority sum Iteration times for convergence GA 108 30 SA 110 7 ACO 122 30 ABC 122 16In addition, in order to compare the performances of ABC, ACO, SA, and GA algorithms more fully, the simulation experiments are carried on for four relay satellite scheduling cases, which are listed as follows.Scheduling Case  1. Time resource of the relay satellite is set to 100 minutes, the number of user satellites is arranged to 10, the number of time windows is 20, and the number of tasks is 30.Scheduling Case  2. Time resource of the relay satellite is set to 100 minutes, the number of user satellites is arranged to 15, the number of time windows is 30, and the number of tasks is 45.Scheduling Case  3. Time resource of the relay satellite is set to 150 minutes, the number of user satellites is arranged to 15, the number of time windows is 45, and the number of tasks is 45.Scheduling Case  4. Time resource of the relay satellite is set to 150 minutes, the number of user satellites increases to 15, the number of time windows is 45, and the number of tasks is 60.Tables4–7 compare the performances between ABC, ACO, SA, and GA in different scheduling situations.Table 4
Algorithms performance in scheduling case 1.
Algorithms ABC ACO SA GA Optimal priority sum 122 122 110 108 Worst priority sum 119 118 94 92 Average of priority sum 121.6 121.1 108.6 100.6 Standard deviation of priority sum 0.926 0.948 4.645 6.875Table 5
Algorithms performance in scheduling case 2.
Algorithms ABC ACO SA GA Optimal priority sum 129 129 115 113 Worst priority sum 126 124 108 106 Average of priority sum 128.4 127.5 112.3 110.6 Standard deviation of priority sum 1.021 1.143 2.658 3.073Table 6
Algorithms performance in scheduling case 3.
Algorithms ABC ACO SA GA Optimal priority sum 179 179 166 154 Worst priority sum 172 170 154 148 Average of priority sum 178.2 177.5 162.8 152.4 Standard deviation of priority sum 1.244 1.357 4.381 5.251Table 7
Algorithms performance in scheduling case 4.
Algorithms ABC ACO SA GA Optimal priority sum 197 197 183 177 Worst priority sum 190 187 173 165 Average of priority sum 195.8 195.5 179.2 172.6 Standard deviation of priority sum 1.446 1.575 4.036 4.539From Tables4–7, it is clear that the algorithms of SA and GA fall into local optimal solution and obtain a relatively low priority sum, while the ABC and ACO algorithms both achieve a high priority sum. Then by comparison of average and standard deviation values of priority sum, ABC appears to be more stable and efficient than ACO.After the generation of the initial scheduling scheme, the tasks set would be changed dynamically: some tasks have been canceled, and some new tasks have been added. In this case, the variation of the tasks set leads to the change in the initial relay satellite scheduling. Once the change of the tasks set happens after initial scheduling, reorganize the model parameters of the sets, and use the ABC algorithm to generate several new dynamic scheduling schemes. In the following simulation, the number of alternatives of the new dynamic scheduling is 50.Figure4 shows the selection results of the dynamic scheduling schemes by the ABC-TOPSIS method. Assume the variation of tasks requirements is that 2 new tasks are inserted. The priorities of 2 new tasks are 5 and 15, while the durations are 3 minutes and 6 minutes, respectively. The weight value of each attribute wj is set to 0.5 equally. The total 50 alternatives are presented in a scatter plot in accordance with the schemes variation and schemes priority sum. In addition, the value near the scatter in Figure 4 represents the number of alternatives. In Figure 4, the best selection alternative by ABC-TOPSIS is marked in red, and the worst selection alternative by ABC-TOPSIS is marked in blue. Therefore, the schemes variation value VAR in (16) of the best dynamic scheme is only 1, which is a small change between initial scheme and dynamic scheme. Meanwhile, the best scheme achieves the high tasks priority sum of 132. The best alternative is then identified as the final dynamic scheduling scheme.Figure 4
Schemes priority sum versus scheme variation.Figures5 and 6, respectively, show the schemes variation VAR and the schemes priority sum between the initial scheduling scheme and the dynamic scheduling scheme versus the variation of the tasks set. When the variation value of the tasks set is −n, it means that n tasks are canceled from the initial tasks set. Meanwhile, when the variation value of the tasks set is n, it means that n tasks are inserted into the initial tasks set. In the simulation, the variation of the tasks sets from −3 to 7. ABC-SAW is the method that combines artificial bee colony (ABC) and simple additive weighting (SAW). From Figures 5 and 6, it can be seen that the ABC-TOPSIS method obtains the smaller schemes variation and a little bit lower priority sum in comparison with ABC-SAW. The ABC-TOPSIS method provides better performance in obtaining the small schemes variation, while the ABC-SAW method has more emphasis on the high priority sum.Figure 5
Schemes variation versus variation of the tasks set.Figure 6
Schemes priority sum versus variation of the tasks set.The dynamic relay satellite scheduling is treated as a multiple attribute decision making (MADM) problem. The two attributes are the schemes variation and priority sum. In order to compare the performances of ABC-TOPSIS and ABC-SAW clearly, a comprehensive evaluation valueCE is introduced, which is defined as follows.(23)CE=absVAR0-absPS0VAR0=VARTSPS0=PSvPS,where TS is the number of scheduled tasks in the initial scheduling scheme. PS is the priority sum of scheduled tasks in the initial scheduling scheme. PSv is the schemes priority sum variation between the initial scheduling scheme and the dynamic scheduling scheme. Since the value CE takes into account the relative values of schemes variation and priority sum, it is able to effectively evaluate the performance of ABC-TOPSIS and ABC-SAW. The method with lower CE would provide better performance in solving the dynamic relay satellite scheduling problem.Figure7 compares the evaluation index CE of ABC-TOPSIS and ABC-SAW. The ABC-TOPSIS method proposed in this paper achieves the relatively lower CE than ABC-SAW, which proves that the ABC-TOPSIS has better performance in solving the dynamic scheduling problem. The ABC-SAW method uses weighting addition operation for different attributes, which leads to the result that it is sensitive to the large attribute value. In the dynamic scheduling problem, the value of the tasks priority sum is larger than the value of the schemes variation. Thus, the ABC-SAW would select the dynamic scheme with high priority sum. And the scheme variation attribute received less attention.Figure 7
CE versus variation of the tasks set.


## 5. Conclusion

In this paper, an efficient method ABC-TOPSIS for the dynamic relay satellite scheduling is proposed. The detailed process of the dynamic relay satellite scheduling consists of two steps: the initial relay satellite scheduling and the selection of dynamic scheduling schemes. In the first step, the initial relay satellite scheduling mathematical model is established as a NP-hard combinatorial problem. The artificial bee colony (ABC) algorithm is applied to solve the initial scheduling problem and to generate the initial scheduling scheme with high tasks priority sum. In the second step, the selection of dynamic scheduling schemes is considered as a multiple attribute decision making (MADM) problem, which aims at achieving the high tasks priority sum and the small variation between initial scheme and dynamic scheme. Therefore, the technique for order preference by similarity to ideal solution (TOPSIS) is performed for the selection of dynamic scheduling schemes. The simulation results show that, in contrast with the other approach, the ABC-TOPSIS is an effective and reasonable dynamic scheduling method.



---

*Source: 3161069-2016-11-09.xml*