# Satellite Mission Instruction Sequence Generation Algorithm Using a Flexible Weighted Directed Graph

Authors: Zhang Yahang; Zhang Jiakai; Yang Mengfei; Yang Peiyao; Song Xiangshuai
Journal: International Journal of Aerospace Engineering
 (2021)

---

## Abstract

A satellite mission instruction generation algorithm based on a flexible weighted directed graph has been proposed. This algorithm can sort the instruction into sequence according to the instruction execution relationship with constraints, which can promote satellite operation performance of the ground station. Concepts like flexible edge, flexible zone, and implement zone were introduced, and the flexible weighted directed graph (FWDG) model was proposed. Based on this model, the satellite instruction sequence generation algorithm was designed. After practice and research, the result showed that according to the new algorithm, the instruction sequence can be consistent with all implement zones, consequently guaranteeing the correctness of the sequence.


---

## Body

## 1. Introduction

A low earth orbit remote sensing satellite with high resolution is the main channel to acquire ground information, which plays an increasingly important role in an earth optical and microwave survey [1]. A remote sensing satellite meets the users’ needs through “task planning+instruction generation” [2]. The missions of a low earth orbit remote sensing satellite are intermittent, diverse, and uncertain, because of orbit revisit characteristics, weather conditions, onboard electronic constraints, and ground receiving resources. It is one of the most concerned problems for users and also a research hotspot in the academic field that a large space system takes advantage of a mission planning system to optimize the satellite-ground resources and accomplish the most imaging tasks with the least resources [3].Lots of satellite task planning algorithms were presented based on artificial intelligence techniques [4]. Bensana et al. established the constraint satisfaction model and the integer programming model [5] and proposed the branch and bound algorithm and taboo search approximate algorithms to obtain the feasible solution. Hall and Magazine used a greedy algorithm and dynamic programming technique to solve a task programming model [6]. Vasquez and Hao map the SPOT5 satellite routine mission planning problem to a knapsack problem. Lin et al. use a Joseph-Louis Lagrange relaxation technique and tabu search algorithm to solve the imaging scheduling problem [7]. Mansour and Dessouky design the evolutionary algorithm and compare it with the traditional algorithm [8]. The main problem with these methods is that scheduling decisions cannot be changed dynamically. In References [9–11], the method of dynamically adjusting the results of planning such as task replanning is proposed, but the deviation between task planning and task execution cannot be considered.On this basis, the satellite instruction sequence generation algorithm based on the weighted directed graph (WDG) presented in References [12, 13] can sort the satellite instruction sequence according to the constraint relation, and the operation efficiency of the ground control center to the spacecraft is greatly reduced. However, the interval between the instruction nodes of the noncritical path may be extended by default when the topological sorting algorithm is applied to generate the instruction sequence; it does not consider the need for strict protection of the execution interval of some spacecraft instructions.In this paper, the concepts of directed acyclic flexible edge, flexible interval, and reasonable instruction execution interval of a directed acyclic graph are introduced, and a flexible weighted directed graph (FWDG) model is proposed to modify the instruction generation algorithm, and an instruction sequence generation algorithm based on the flexible weighted digraph is proposed. The FWDAG model is an essential module in onboard software, and it takes observation mission as input and instruction sequence as output, as shown in Figure1. The example shows that the modified algorithm can satisfy the spacecraft instruction execution interval.Figure 1
Relationship of the instruction module and onboard software modules.


## 2. Satellite Instruction Sequence Generation Algorithm Based on the Directed Graph Model

### 2.1. Directed Graph Model

The satellite mission instruction sequence is transformed into a digraph modelGV,E consisting of instructions and their constraints. Among them,
(1)
GraphG=V,E: source vertex represents the start of the task; sink vertex represents the end of the task(2)
V=V1,V2,V3,⋯,VN is the set of vertices of a directed graph; each vertex Vjj=1,2,⋯,N corresponds to an instruction. TIMEVi represents the execution time of the instruction(3)
E=E1,E2,⋯,EM is the set of edges of a directed graph, edges Ei=Vj⟶Vki=1,2,⋯,M;j,k=1,2,⋯,N represent instruction Vj preceding instruction Vk, Vj is the forward vertex of Vk, and Vk is the backward vertex of Vj; the length of the edge Li represents the execution time interval between two instructionsIn graphG, V is the set of vertices corresponding to all instructions contained in the task and E is the edge set corresponding to the instruction timing constraint that completes the task. In order to describe GV,E in detail, more symbols are introduced; they are as follows:N is the number of all vertices of a digraph GV,E.M is the number of all edges of a digraph GV,E.Source is the start of the instruction sequence for a task.Sink is the end of the instruction sequence for a task.VT0 is the instructions at time T0 (T0 is the beginning time of imaging).VT1 is the instructions at time T1 (T1 is the beginning time of data transfer).X=S,Xl,Xm,⋯, where S is the start time of a mission and Xl,Xm,⋯ is the interval between the instruction sequence Vl,Vm⋯ and the first instruction.


### 2.2. Task Instruction Sequence Generation Algorithm Based on the Digraph Model

In this section, we introduce the directed graph-based task instruction sequence generation algorithm [12]:Algorithm 1: Instruction sequence generation algorithm based on the directed acyclic graph model.
1. Hierarchizing the graphGV,E according to the following definition.(i) DefineSource as 0−layer vertex;(ii)1−layer vertices only take the 0−layer vertices as forward vertices;(iii)2−layer vertices only take the 1−layer vertices or Source as forward vertices;(v) ...(vi)n−layer vertices take Source, 1−layer, …, n−1−layer vertices as forward vertices;2. Start withSource, the earliest execution time interval ESTVi of each vertex Vi relative to Source is computed by layer;3. The earliest execution time interval ofSink relative to Source is the minimum execution time of the task instruction sequence;4. Starting fromSink, the latest execution time interval LSTVi of each vertex relative to Source is calculated in reverse step by step;5. For instructionVp like shutdown, the execution time delay Xp selects the earliest execution time interval relative to Source, and for instruction Vq like switch on, the execution time delay Xq selects the latest execution time interval relative to Source; Ensure that the command sequence satisfies the user’s task, starting as late as possible and shutting down as early as possible;6. The execution time of theSource vertices is the time T0 subtracts the earliest execution time of the Source to T0, which is also the start time S that the sequence starts to execute;7. …A unified instruction topological sequence can be generated finally by Algorithm1, after digraph modeling of a sensing task, according to the start time of the mission on the satellite, the interval of the basic instruction sequence, and the dependence of different instruction sequences.However, in the second and fourth steps of the algorithm, when the earliestESTVi and the latest LSTVi of each vertex are calculated, the default edge can be stretched [14, 15].According to the algorithm in [12, 13], for the model shown in Figure 2, if TV0=0, then
(1)TV0=0,ESTV1=5,ESTV2=7,ESTV3=maxESTV1+E3,ESTV2+E4=15,LSTV3=ESTV3=15,LSTV1=LSTV3−E3=11,LSTV2=LSTV3−E4=7,LSTV0=minLSTV1−E1,LSTV2−E2=0.Figure 2
Instruction model of the general weighted directed acyclic graph.Obviously, for verticesV2 and V1, we have ESTV1≠LSTV1 and ESTV2≠LSTV2.Algorithm1 holds the execution time TV1 and TV1 for V1 and V2, respectively, which is reasonable, as long as TV1∈ESTV1,LSTV1 and TV2∈ESTV2,LSTV2. If V1 is the shutdown instruction, according to Algorithm 1, TV1=ESTV1=5. But consider an application scenario in which there are certain instructions and intervals between instructions that are fixed; that is, some edges Ex cannot be stretched and shortened. In this paper, we call this “rigid edge,” denoted as RE.As shown in Figure3, the solid line RE3 indicates that the edge can be neither shortened nor stretched, and the dash line indicates that the edge can be stretched but cannot be shortened. Obviously, TV1 must be a fixed value; TV1=TV3−4=11. However, Algorithm 1 cannot take into account this constraint, and the calculated results cannot meet this requirement.Figure 3
Instruction model of the general weightedRE acyclic graph.


## 2.1. Directed Graph Model

The satellite mission instruction sequence is transformed into a digraph modelGV,E consisting of instructions and their constraints. Among them,
(1)
GraphG=V,E: source vertex represents the start of the task; sink vertex represents the end of the task(2)
V=V1,V2,V3,⋯,VN is the set of vertices of a directed graph; each vertex Vjj=1,2,⋯,N corresponds to an instruction. TIMEVi represents the execution time of the instruction(3)
E=E1,E2,⋯,EM is the set of edges of a directed graph, edges Ei=Vj⟶Vki=1,2,⋯,M;j,k=1,2,⋯,N represent instruction Vj preceding instruction Vk, Vj is the forward vertex of Vk, and Vk is the backward vertex of Vj; the length of the edge Li represents the execution time interval between two instructionsIn graphG, V is the set of vertices corresponding to all instructions contained in the task and E is the edge set corresponding to the instruction timing constraint that completes the task. In order to describe GV,E in detail, more symbols are introduced; they are as follows:N is the number of all vertices of a digraph GV,E.M is the number of all edges of a digraph GV,E.Source is the start of the instruction sequence for a task.Sink is the end of the instruction sequence for a task.VT0 is the instructions at time T0 (T0 is the beginning time of imaging).VT1 is the instructions at time T1 (T1 is the beginning time of data transfer).X=S,Xl,Xm,⋯, where S is the start time of a mission and Xl,Xm,⋯ is the interval between the instruction sequence Vl,Vm⋯ and the first instruction.


## 2.2. Task Instruction Sequence Generation Algorithm Based on the Digraph Model

In this section, we introduce the directed graph-based task instruction sequence generation algorithm [12]:Algorithm 1: Instruction sequence generation algorithm based on the directed acyclic graph model.
1. Hierarchizing the graphGV,E according to the following definition.(i) DefineSource as 0−layer vertex;(ii)1−layer vertices only take the 0−layer vertices as forward vertices;(iii)2−layer vertices only take the 1−layer vertices or Source as forward vertices;(v) ...(vi)n−layer vertices take Source, 1−layer, …, n−1−layer vertices as forward vertices;2. Start withSource, the earliest execution time interval ESTVi of each vertex Vi relative to Source is computed by layer;3. The earliest execution time interval ofSink relative to Source is the minimum execution time of the task instruction sequence;4. Starting fromSink, the latest execution time interval LSTVi of each vertex relative to Source is calculated in reverse step by step;5. For instructionVp like shutdown, the execution time delay Xp selects the earliest execution time interval relative to Source, and for instruction Vq like switch on, the execution time delay Xq selects the latest execution time interval relative to Source; Ensure that the command sequence satisfies the user’s task, starting as late as possible and shutting down as early as possible;6. The execution time of theSource vertices is the time T0 subtracts the earliest execution time of the Source to T0, which is also the start time S that the sequence starts to execute;7. …A unified instruction topological sequence can be generated finally by Algorithm1, after digraph modeling of a sensing task, according to the start time of the mission on the satellite, the interval of the basic instruction sequence, and the dependence of different instruction sequences.However, in the second and fourth steps of the algorithm, when the earliestESTVi and the latest LSTVi of each vertex are calculated, the default edge can be stretched [14, 15].According to the algorithm in [12, 13], for the model shown in Figure 2, if TV0=0, then
(1)TV0=0,ESTV1=5,ESTV2=7,ESTV3=maxESTV1+E3,ESTV2+E4=15,LSTV3=ESTV3=15,LSTV1=LSTV3−E3=11,LSTV2=LSTV3−E4=7,LSTV0=minLSTV1−E1,LSTV2−E2=0.Figure 2
Instruction model of the general weighted directed acyclic graph.Obviously, for verticesV2 and V1, we have ESTV1≠LSTV1 and ESTV2≠LSTV2.Algorithm1 holds the execution time TV1 and TV1 for V1 and V2, respectively, which is reasonable, as long as TV1∈ESTV1,LSTV1 and TV2∈ESTV2,LSTV2. If V1 is the shutdown instruction, according to Algorithm 1, TV1=ESTV1=5. But consider an application scenario in which there are certain instructions and intervals between instructions that are fixed; that is, some edges Ex cannot be stretched and shortened. In this paper, we call this “rigid edge,” denoted as RE.As shown in Figure3, the solid line RE3 indicates that the edge can be neither shortened nor stretched, and the dash line indicates that the edge can be stretched but cannot be shortened. Obviously, TV1 must be a fixed value; TV1=TV3−4=11. However, Algorithm 1 cannot take into account this constraint, and the calculated results cannot meet this requirement.Figure 3
Instruction model of the general weightedRE acyclic graph.


## 3. Instruction Generation Algorithm Based on the FWDAG Instruction Model

In order to meet the more realistic and strict requirements of a satellite instruction transmission time slot, we propose an instruction generation algorithm based on a flexible weighted directed acyclic graph (FWDAG).


### 3.1. FWDAG Instruction Model

For the more general case, some instruction intervals can be within a set interval. For example, instructionV1 must be executed after instruction V0 is completed 3~4s; then, obviously the interval 3,4 is the variable interval of E1. In this case, the concept of flexible interval edges is introduced into weighted directed acyclic graphs. The basic definitions are listed below:Flexible Edge. In a directed acyclic graph, the edges with variable weights are called flexible edges and are denoted as FE.Flexible Zone. The flexible interval of edge weight, which we call the flexible zone, is denoted as FZ. It is obvious that the rigid edge is a special flexible edge whose upper and lower limits of the flexible interval are equal.Implement Zone. In a directed acyclic graph, the time of a node changes within a reasonable range, which becomes a reasonable range of execution, referred to as the implement zone, recorded as IZ.Addition operation ofIZ and FZ: the addition operation of the implement zone and the flexible zone is defined as follows:
(2)IZ’=IZ+FZ=IZdown+FZdown,LZup+FZup.Subtraction operation ofIZ and FZ: the subtraction operation of the implement zone and the flexible zone is defined as follows:
(3)IZ’=IZ−FZ=IZdown−FZup,LZup−FZdownI0,+∞.Obviously, ifLZup<FZdown, IZ’=∅.In view of the above definition, the following theorem is proposed and proven.Theorem 1.
Suppose that the nodeVi in a directed acyclic graph has a precursor node Vpre, the corresponding flexible edge is FEpre, and the flexible zone is FZFEpre=FZFEpredown,FZFEpreup. If IZVpre=IZVpredown,LZVpreup has been determined, then IZVi=IZVpredown+FZFEpredown,LZVpreup+FZFEpreup.Proof.
Letx=TVpre, y=TFEpre, and z=TVi. According to the flexible edge constraints of FEpre, the objective function is z=x+y; here, x∈IZVpredown,IZVpreup and y∈FZFEpredown,FZFEpreup. According to the property of the linear equations with two unknowns, the range of the objective function z=x+y is IZVpredown+FZFEpredown,LZVpreup+FZFEpreup. And the range is continuous within its domain of definition IZVi=IZVpredown+FZFEpredown,LZVpreup+FZFEpreup.Inference 2.
Suppose that a nodeVi in a directed acyclic graph has J precursor nodes Vjpre, j=1,2,⋯,J. One of the implement zones IZVij of node Vjpre is determined by implement zone IZVjpre of each precursor and flexible zone FZFEj of FEj. All entries of this node determine the intersection of the execution ranges of this node, which is equal to the execution ranges of this node. That is, IZVi=∩j=0JIZVjpre+FZFEj.Theorem 3.
Suppose that the nodeVi in a directed acyclic graph has a backward node Vnext, the corresponding flexible edge is FEnext, and the flexible zone is FZFEnext=FZFEnextdown,FZFEnextup. If IZVnext=IZVnextdown,LZVnextup has been determined, then IZVi=LZVnextdown−FZFEnextup,IZVnextup−FZFEnextdown.Proof.
Letx=TVnext, y=TFEnext, and z=TVi. According to the flexible edge FEnext constraints, it has objective function z=x−y, x∈IZVnextdown,IZVnextup, and y∈FZFEnextdown,FZFEnextup. According to the property of the linear equations with two unknowns, the range of the objective function z=x−y is LZVnextdown−FZFEnextup,IZVnextup−FZFEnextdown, and the range is continuous within its domain of definition IZVi=LZVnextdown−FZFEnextup,IZVnextup−FZFEnextdown.Inference 4.
Suppose a directed acyclic graph has a nodeVi and J rear-driver nodes Vjnext, j=1,2,⋯,J. Each rear-driver node Vjnext implement zone IZVjnext and the flexible zone FZFEj of FEj determine an implement zone IZVij of node Vi; all entries of this node determine the intersection of the execution ranges of this node, which is equal to the execution ranges of this node. That is, IZVi=∩j=0JIZVjnext−FZFEj.


### 3.2. Instruction Generation Algorithm Based on FWDAG

In this paper, an instruction sequence generation algorithm based on the FWDAG model is proposed. A flexible edgesFE are generated by the dependence of instructions with n nodes.


## 3.1. FWDAG Instruction Model

For the more general case, some instruction intervals can be within a set interval. For example, instructionV1 must be executed after instruction V0 is completed 3~4s; then, obviously the interval 3,4 is the variable interval of E1. In this case, the concept of flexible interval edges is introduced into weighted directed acyclic graphs. The basic definitions are listed below:Flexible Edge. In a directed acyclic graph, the edges with variable weights are called flexible edges and are denoted as FE.Flexible Zone. The flexible interval of edge weight, which we call the flexible zone, is denoted as FZ. It is obvious that the rigid edge is a special flexible edge whose upper and lower limits of the flexible interval are equal.Implement Zone. In a directed acyclic graph, the time of a node changes within a reasonable range, which becomes a reasonable range of execution, referred to as the implement zone, recorded as IZ.Addition operation ofIZ and FZ: the addition operation of the implement zone and the flexible zone is defined as follows:
(2)IZ’=IZ+FZ=IZdown+FZdown,LZup+FZup.Subtraction operation ofIZ and FZ: the subtraction operation of the implement zone and the flexible zone is defined as follows:
(3)IZ’=IZ−FZ=IZdown−FZup,LZup−FZdownI0,+∞.Obviously, ifLZup<FZdown, IZ’=∅.In view of the above definition, the following theorem is proposed and proven.Theorem 1.
Suppose that the nodeVi in a directed acyclic graph has a precursor node Vpre, the corresponding flexible edge is FEpre, and the flexible zone is FZFEpre=FZFEpredown,FZFEpreup. If IZVpre=IZVpredown,LZVpreup has been determined, then IZVi=IZVpredown+FZFEpredown,LZVpreup+FZFEpreup.Proof.
Letx=TVpre, y=TFEpre, and z=TVi. According to the flexible edge constraints of FEpre, the objective function is z=x+y; here, x∈IZVpredown,IZVpreup and y∈FZFEpredown,FZFEpreup. According to the property of the linear equations with two unknowns, the range of the objective function z=x+y is IZVpredown+FZFEpredown,LZVpreup+FZFEpreup. And the range is continuous within its domain of definition IZVi=IZVpredown+FZFEpredown,LZVpreup+FZFEpreup.Inference 2.
Suppose that a nodeVi in a directed acyclic graph has J precursor nodes Vjpre, j=1,2,⋯,J. One of the implement zones IZVij of node Vjpre is determined by implement zone IZVjpre of each precursor and flexible zone FZFEj of FEj. All entries of this node determine the intersection of the execution ranges of this node, which is equal to the execution ranges of this node. That is, IZVi=∩j=0JIZVjpre+FZFEj.Theorem 3.
Suppose that the nodeVi in a directed acyclic graph has a backward node Vnext, the corresponding flexible edge is FEnext, and the flexible zone is FZFEnext=FZFEnextdown,FZFEnextup. If IZVnext=IZVnextdown,LZVnextup has been determined, then IZVi=LZVnextdown−FZFEnextup,IZVnextup−FZFEnextdown.Proof.
Letx=TVnext, y=TFEnext, and z=TVi. According to the flexible edge FEnext constraints, it has objective function z=x−y, x∈IZVnextdown,IZVnextup, and y∈FZFEnextdown,FZFEnextup. According to the property of the linear equations with two unknowns, the range of the objective function z=x−y is LZVnextdown−FZFEnextup,IZVnextup−FZFEnextdown, and the range is continuous within its domain of definition IZVi=LZVnextdown−FZFEnextup,IZVnextup−FZFEnextdown.Inference 4.
Suppose a directed acyclic graph has a nodeVi and J rear-driver nodes Vjnext, j=1,2,⋯,J. Each rear-driver node Vjnext implement zone IZVjnext and the flexible zone FZFEj of FEj determine an implement zone IZVij of node Vi; all entries of this node determine the intersection of the execution ranges of this node, which is equal to the execution ranges of this node. That is, IZVi=∩j=0JIZVjnext−FZFEj.


## 3.2. Instruction Generation Algorithm Based on FWDAG

In this paper, an instruction sequence generation algorithm based on the FWDAG model is proposed. A flexible edgesFE are generated by the dependence of instructions with n nodes.


## 4. Application Example

Figure4 is an instruction model of a satellite imaging task that is described by FWDAG. According to Algorithm 2, the procedure for calculating the graph above is
(4)IZV0=0,0,IZV1=0,+∞,IZV2=0,+∞,IZV3=0,+∞,IZV1.1=0,+∞,IZV2.1=0,+∞,IZVend=0,+∞,IZV1=IZV0+FZFE1=5,7,IZV2=IZV0+FZFE2=2,3,IZV3=IZV0+FZFE3=2,3,IZV1.1=IZV1+FZFE1.1=2,3+5,7=7,10,IZV2.1′=IZV2+FZFE2.1=2,3+2,9=4,12,IZV2.1=IZV3+FZFE3.1∩IZV2.1′=9,+∞∩4,12=9,12,IZVend′=IZV1.1+FZFE1.1.1=7,10+120,145=127,155,IZVend=IZV2.1+FZFE2.1.1∩IZVend′=14,22∩127,155=∅.Figure 4
FWDAG instruction model.Algorithm 2: An instruction sequence generation algorithm based on FWDAG.
1. The implement zoneIZV0=0,0 for the task starting node V0, The implement zone for all other nodes is set to IZVi=0,+∞;2. Starting fromV0, select a node with degree 0 (no precursor node) from the digraph as the current node Vi. According to equation (2), calculate implement zone of all the backward nodes of the current node whose degree edges are connected.3. According to Inference2, the implement zone of the new node calculated by step 2 is updated by “And operation”. If the result of “And operation” is “Empty”, operation will be quit.4. Deletes the current node and all flexible edges coming from this node.5. Repeat steps 2 to step 4, until there are no more nodes in the directed graph.6. Starting withVN, select a node from the directed graph with an outdegree of 0 (without a trailing node) as the current node Vi, according to equation (3), select TVi from IZVi according to the strategy of selecting node time (the last instruction is to select the earliest value, the start instruction is to be as late as possible, and the shutdown instruction is to be as early as possible), at the same time update the current node into all degrees edge connected to the precursor node implement zone;7. According to Inference4, the result of step 6 is updated by “And operation”. The result of “And operation” should not be “Empty”.8. Deletes the current node and all flexible edges that enter this node.9. Repeat steps 6 to step 8, until the node is no longer present in the directed graph.There is no solution to the program break.Obviously, according to the antenna pathV0⟶V1.1⟶Vend, the earliest execution time of Vend is 127, and according to the camera path V0⟶V2.1⟶V3, the latest execution time of Vend is 22; obviously, there is no solution. This means that there are conflicts among camera payload, attitude executable trajectory, and antenna executable path constraint. The period of antenna execution is very long, while the time of camera payload powered on cannot be too long. Hence, the camera standby instruction is inserted into the onboard system, to prolong the camera instruction path V0⟶V2.1⟶V3 and then to match the antenna path, as shown in Figure 5.Figure 5
Adjusted FWDAG instruction model.By the updated instruction model, according to Algorithm2, recalculated results are
(5)IZV0=0,0,IZV1=0,+∞,IZV2=0,+∞,IZV3=0,+∞,IZV1.1=0,+∞,IZV2.1=0,+∞,IZVend=0,+∞,IZV1=IZV0+FZFE1=2,3,IZV2=IZV0+FZFE2=2,3,IZV3=IZV0+FZFE3=2,3,IZV1.1=IZV1+FZFE1.1=2,3+5,7=7,10,IZV2.1′=IZV2+FZFE2.1=2,3+2,9=4,12,IZV2.1=IZV3+FZFE3.1∩IZV2.1′=9,+∞∩4,12=9,12,IZV2.1.1=IZV2.1+FZFE2.1.1=9,12+5,10=14,22,IZVend′=IZV1.1+FZFE1.1.1=7,10+120,145=127,155,IZVend=IZV2.1.1+FZFE2.1.1∩IZVend′=16,+∞∩127,155=127,155.According to the end node selection of the earliest execution time principle, then(6)TVend=127,LZVend=127,127,IZV1.1”=IZVend−FZFE1.1.1∩IZV1.1=0,7∩7,10=7,7,TV1.1=7,IZV1”=IZV1.1′′−FZFE1.1∩IZV1=0,2∩2,3=2,2,TV1=2,IZV01”=IZV1′′−FZFE1∩IZV0=0,0∩0,0=0,0,IZV2.1.1”=IZVend−FZFE2.1.1.1∩IZV2.1.1=0,125∩14,22=14,22.According to the end node selection of the earliest execution time principle, then(7)TV2.1.1=14,LZV2.1.1′′=14,14,IZV2.1”=IZV2.1.1′′−FZFE2.1.1∩IZV2.1=4,9∩9,12=9,9,TV2.1=9,IZV2”=IZV2.1′′−FZFE2.1∩IZV1=0,7∩2,3=2,3.According to the end node selection of the earliest execution time principle, then(8)TV2=2,LZV2′′=2,2,IZV02”=IZV2′′−FZFE2∩IZV0=0,0∩0,0=0,0,IZV3”=IZV2.1′′−FZFE3.1∩IZV3=0,2∩2,3=2,2,TV3=2,IZV03”=IZV2′′−FZFE2∩IZV0=0,0∩0,0=0,0,IZV0”=IZV01”∩IZV02”∩IZV03”=0,0,TV0=0.At last, all theTs were calculated:TV0=0, TV1=2, TV2=2, TV3=2, TV1.1=7, TV2.1=9, TV2.1.1=14, and TVend=127, and we get the satellite imaging mission’s command sequence.The purposed scheme and algorithm are to model the existing constraints and find the feasible solution of the instruction sequence under this constraint model, which not only meets the constraint requirements but also improves the task execution energy efficiency as much as possible. If the feasible solution of the instruction sequence cannot be found under the current constraint model, the algorithm will alert the designer. As for how to modify the constraint model, such as the weight of edges or the number of vertices, designers need to adjust the design according to the actual situation of satellite missions and their own experience, so as to adjust the FWDAG model, and finally ensure that the instruction system can find a feasible solution under the adjusted constraint model.


## 5. Conclusion

An instruction generation algorithm based on the flexible weighted directed acyclic graph is proposed. By introducing the concept of a flexible edge into the directed acyclic graph, the problem that the time interval of instruction execution is fixed in a certain variable region is solved, ensuring that the execution interval of the dependent instruction is within the preset range. The time complexity of the algorithm isOn=On+2e, where n is the number of nodes in the digraph model and e is the number of edges.



---

*Source: 4109118-2021-10-20.xml*