METHOD FOR TASK PLANNING OF SPACE INFORMATION NETWORK BASED RESOURCE INTERCHANGE

Abstract

Disclosed is a method for task planning of a space information network based on resource interchange. The method includes: initializing basic parameters of the space information network; dividing a planning horizon into K time slots of equal length, and constructing a resource time-varying graph for the space information network; sampling a feasible resource combination space of each task, and obtaining a candidate resource combination set comprised of the resource combinations with independence greater than or equal to a threshold n; calculating a conflict relation between resource combinations, and constructing a resource combination conflict graph; obtaining a maximum independent set of the resource combination conflict graph to obtain a global planning result; and searching a neighborhood of the global planning result, and completing a local adjustment of a task planning scheme through the resource interchange, to complete the task planning based on characteristics of the resource interchange.

Claims

1. A method for task planning of a space information network based on resource interchange, comprising: step 1: initializing basic parameters of the space information network; step 2: dividing a planning horizon into K time slots of equal length, where a length of each time slot is ti, and constructing a resource time-varying graph G.sub.K(V, A) for the space information network, where V and A respectively represent a set of vertices and a set of resource arcs in the resource time-varying graph; step 3: sampling a feasible resource combination space of each task om.sub.i∈OM, and obtaining a candidate resource combination set, denoted by P.sub.i, comprised of the resource combinations with independence greater than or equal to a threshold n; step 4: calculating a conflict relation between resource combinations, and constructing a resource combination conflict graph RCG(P.sub.C, E.sub.C), where P.sub.C and E.sub.C respectively represent a set of vertices and a set of edges of the resource combination conflict graph; step 5: obtaining a maximum independent set of the resource combination conflict graph, and completing large-scale global task planning based on a candidate resource combination, to obtain a global planning result; and step 6: searching a neighborhood of the global planning result, and completing a local adjustment of a task planning scheme through the resource interchange, to complete the task planning based on characteristics of the resource interchange.

2. The method according to claim 1, wherein the basic parameters of the space information network comprise a set of Earth observation satellites OS, a set of relay satellites RS, a set of ground stations GS, a data processing center dc, a set of observation targets OB, a set of tasks OM, and a planning horizon T.

3. The method according to claim 1, wherein the step 4 comprises: step 4a: adding each candidate resource combination in set p.sub.se=∪.sub.1≤i≤|OM|P.sub.i as a vertex in the resource combination conflict graph; and step 4b: for any pair of vertices p.sub.i,k and p.sub.j,l in the resource combination conflict graph, adding an edge between vertices p.sub.i,k and p.sub.j,l if resource combinations p.sub.i,k and p.sub.j,l have a conflict relation or satisfy i=j and k≠l, where p.sub.i,k represents a k-th candidate resource combination of the task om.sub.i.

4. The method according to claim 1, wherein the step 5 comprises: step 5a: initializing an output set P.sub.su=∅; step 5b: sorting all vertices in P.sub.C based on respective degrees in a descending order, and selecting a vertex p.sub.0 with the largest degree; step 5c: adding the vertex p.sub.0 with the largest degree to the output set P.sub.su; step 5d: deleting vertex p.sub.0 and all the vertices adjacent to p.sub.0 from P.sub.C, and deleting all the edges associated with the deleted vertices from E.sub.C; and step 5e: proceeding to the step 5b if P.sub.C≠∅; otherwise, outputting the set P.sub.su, and obtaining, based on P.sub.su, a set of planned tasks and a resource allocation scheme of the planned tasks.

5. The method according to claim 1, wherein the step 6 comprises: step 6a: obtaining the resource time-varying graph G.sub.K(V, A) and a subgraph G.sub.K′(V′, A′) that has removed resource arcs represented by resources occupied by planned tasks, and obtaining a set of tasks OM.sub.y that is successfully planned and a set of tasks OM.sub.w that has not been planned; step 6b: calculating resource shortage degrees of all tasks in OM.sub.w, and sorting the resource shortage degrees from high to low; step 6c: initializing a counter n=1; step 6d: finding an idle resource combination for the n-th task om.sub.n in OM.sub.w through the resource interchange; step 6e: increasing the counter n by 1; and step 6f: proceeding to the step 6d when n is smaller than or equal to |OM.sub.w|; otherwise, outputting the set of tasks OM.sub.y.

6. The method according to claim 5, wherein the step 6d comprises: step 6d1: finding a feasible resource combination Pd.sub.n with the least resources occupied by planned tasks for task om.sub.n, and setting Pz.sub.n as representing a set of resources occupied by the planned tasks and in Pd.sub.n; step 6d2: traversing each resource arc a∈Pz.sub.n; for the task that occupies resource arc a, denoted by fom(a), re-allocating a new resource combination for fom(a) through resource interchange, so that the resource arc a is no longer occupied;; and if the resource interchange succeeds, updating G.sub.K′(V, A′), and deleting resource a from Pz.sub.n; otherwise, skipping to the step 6e; and step 6d3: finding a path p.sub.n from ob.sub.n.sup.┌ts.sup.n.sup./τ┐ and dc.sup.└te.sup.n.sup./τ┘ in G.sub.K′(V′, A′) as the new resource combination allocated to task om.sub.n, updating G.sub.K′(V′, A′), and adding task om.sub.n to the set OM.sub.y.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0029] FIG. 1 is a schematic diagram illustrating a scenario used by the present disclosure;

[0030] FIG. 2 is an overall flowchart of the present disclosure;

[0031] FIG. 3 is a resource time-varying diagram in the present disclosure;

[0032] FIG. 4 is a flowchart illustrating a sampling algorithm of a resource combination;

[0033] FIG. 5 is a resource combination conflict diagram in the present disclosure;

[0034] FIG. 6 is a flowchart illustrating an algorithm for completing a large-scale global task planning based on a conflict relation between candidate resource combinations; and

[0035] FIG. 7 is a flowchart illustrating an algorithm for completing a local adjustment of a task planning scheme based on resource interchange.

DESCRIPTION OF EMBODIMENTS

[0036] The present disclosure will be further described in detail below in combination with the accompanying drawings.

[0037] With reference to FIG. 1 and FIG. 2, a method for task planning of a space information network based on resource interchange according to the present disclosure includes the following steps.

[0038] At step 1), basic parameters of the space information network are initialized.

[0039] The basic parameters of the space information network include a set of Earth observation satellites OS={os.sub.1, os.sub.2, . . . }, a set of relay satellites RS={rs.sub.1, rs.sub.2, . . . }, a set of ground stations GS={gs.sub.1, gs.sub.2, . . . }, a data processing center dc, a set of observation targets OB={ob.sub.1, ob.sub.2, . . . }, a set of tasks OM={om.sub.1, om.sub.2, . . . } and a planning horizon T.

[0040] At step 2), a planning horizon T is divided into K time slots of equal length, where a length of each time slot is τ, and a resource time-varying graph G.sub.K(V, A) for the space information network is constructed, where V and A respectively represent the set of vertices and the set of resource arcs in the resource time-varying graph. The resource time-varying graph G.sub.K(V, A) for the space information network is a K-layered directed graph.

[0041] The set of vertices V in the resource time-varying graph contains a set of duplicates of all nodes in the space information network in different time slots. That is, V=V.sub.OB∪V.sub.IM∪V.sub.PS∪V.sub.ST∪V.sub.RS∪V.sub.GS∪V.sub.DC, where V.sub.OB, V.sub.IM, V.sub.PS, V.sub.ST, V.sub.RS, V.sub.GS and V.sub.DC respectively correspond to a set of duplicate vertices in each time slot of observation targets, observation satellite imagers, processors, transceivers and storage units, relay satellites, ground stations and data processing center.

[0042] The set of resource arcs A in the resource time-varying graph contains different types of resources in a network. That is, A=A.sub.O∪A.sub.L∪A.sub.S∪A.sub.C, where A.sub.O, A.sub.L, A.sub.S, and A.sub.C respectively represent a set of observation arcs, a set of transmission arcs, a set of storage arcs, and a set of calculation arcs.

[0043] At step 3), the feasible resource combination space of each task om.sub.i∈OM is sampled, and a set of resource combinations P.sub.i with independence greater than or equal to a threshold n is determined as a candidate resource combination set.

[0044] Specifically, step 3) includes the following steps.

[0045] At step 3a), obtaining a set of resources in which the maximum degree of independence of each task om.sub.i is not smaller than n is modeled as an optimization problem:

[00001]$P1\text{:}\max \underset{p\in P_{a,i}}{.Math.}{x}_p.$

[0046] That is, the number of elements in the candidate resource combination set is maximized, where P.sub.a,i represents a set of all feasible resource combinations of the task om.sub.i, and x.sub.p represents a Boolean variable.

[0047] At step 3a1), constraint C1 is added to restrict that the same resource can only be used by one resource combination in n time slots. That is, independence between any two resource combinations with x.sub.p=1 is at least n:

[00002]$C1\text{:}Z\left(p_1,p_2\right)⩾n,\forall p_1,p_2\in \left\{p.Math.x_p=1,p\in P_{a,i}\right\};$

[0048] At step 3a2), constraint C2 is added. x.sub.p being equal to 1 means that a resource combination p is within the set of candidate resources; otherwise, the resource combination p is not within the set of candidate resources:

[00003]$C2\text{:}{x}_p\in \left\{0,1\right\}.$

[0049] Referring to FIG. 4, a resource combination sampling algorithm is designed based on the optimization problem P1 in 3a):

[0050] At step 3b), P.sub.i=∅ is initialized.

[0051] At step 3c), each resource arc a in a time slot from ┌ts.sub.i/τ┐ to └te.sub.i/τ┘ in the resource time-varying graph is traversed. If a is a storage arc, a weight w(a) of the resource arc a is set to 0; otherwise, w(a) is set to the number of resource arcs whose degree of independence from a is smaller than n.

[0052] At step 3d) a shortest path from a source node ob.sub.i.sup.┌ts.sup.i.sup./τ┐ to a destination node dc.sup.└te.sup.i.sup./τ┘ on the resource time-varying graph is obtained and recorded as p.sub.s. Let P.sub.i=P.sub.i∪{p.sub.s}.

[0053] At step 3e), each resource arc a in p.sub.s is traversed. If a is an observation arc, a calculation arc or a transmission arc, all resource arcs whose degree of independence from a is smaller than n are deleted from G.sub.K(V, A).

[0054] At step 3f), if there is still a path between ob.sub.i.sup.┌ts.sup.i.sup./τ┐ and dc.sup.└te.sup.i.sup./τ┘ in the resource time-varying graph, skip to step 3c); otherwise, output a candidate resource combination P.sub.i.

[0055] At step 4), a conflict relation between resource combinations is calculated, and a resource combination conflict graph RCG (P.sub.C, E.sub.C) is constructed, where P.sub.C and E.sub.C respectively represent a set of vertices and a set of edges of the resource combination conflict graph.

[0056] Specifically, step 4) includes the following steps.

[0057] At step 4a), p.sub.i,k is set as representing the k-th candidate resource combination of task om.sub.i. For resource combinations p.sub.i,k and p.sub.j,l, if one of the following conditions is met:

(i) resources (v.sub.m1.sup.r, v.sub.n1.sup.r)∈p.sub.i,k and (v.sub.m2.sup.t, v.sub.n2.sup.t)∈p.sub.j,l existing, and v.sub.m1.sup.r=v.sub.m2.sup.t v.sub.m1.sup.r∈V.sub.ST being satisfied; and
(ii) resources (v.sub.m1.sup.r, v.sub.n1.sup.r)∈p.sub.i,k and (v.sub.m2.sup.t, v.sub.n2.sup.t)∈p.sub.j,l existing, and v.sub.n1.sup.r=v.sub.n2.sup.t v.sub.n1.sup.r∈V.sub.IM∪V.sub.RS∪V.sub.GS being satisfied;

[0058] The resource combinations p.sub.i,k and p.sub.j,l are defined to conflict with each other.

[0059] At step 4b), the resource combination conflict graph RCG (P.sub.C, E.sub.C) as illustrated in FIG. 5 is constructed based on the conflict relationship between the resource combinations at step 4a), where P.sub.C and E.sub.C respectively represent the set of vertices and the set of edges of the resource combination conflict graph. Specifically, step 4b) includes the following steps.

[0060] At step 4b1), the candidate resource combination in a set p.sub.se=∪.sub.1≤i≤|OMP.sub.i is added as a vertex in the resource combination conflict graph.

[0061] At step 4b2), for any pair of vertices (p.sub.i,k and p.sub.j,l) in the resource combination conflict graph, if resource combinations p.sub.i,k and p.sub.j,l conflict with each other, or i=j and k≠l, an edge is added between vertices p.sub.i,k and p.sub.j,l.

[0062] At step 5), a maximum independent set of the resource combination conflict graph is obtained, and large-scale global task planning based on a candidate resource combination is completed, to obtain a global planning result.

[0063] Specifically, referring to FIG. 6, step 5) includes the following steps.

[0064] At step 5a), output set P.sub.su=∅ is initialized.

[0065] At step 5b), all vertices in P.sub.C are sorted based on their degree in a descending order, and a vertex p.sub.0 with the largest degree is selected.

[0066] At step 5c), the vertex p.sub.0 with the largest degree is added to output set P.sub.su.

[0067] At step 5d), the vertex p.sub.0 and all the vertices adjacent to the vertex p.sub.0 are deleted from P.sub.c, and all the edges associated with the deleted vertices are deleted from E.sub.C.

[0068] At step 5e), if P.sub.C≠∅, the method proceeds to step 5b); otherwise, the set P.sub.su is outputted, and a set of planned tasks and a resource allocation scheme of the planned tasks are obtained based on P.sub.su.

[0069] At step 6), a neighborhood of the global planning result is searched, and a local adjustment of a task planning scheme is completed through the resource interchange, to complete the task planning based on characteristics of the resource interchange.

[0070] Specifically, step 6) includes the following steps.

[0071] At step 6a), the resource time-varying graph G.sub.K(V, A) and its subgraph G.sub.K′(V′, A′) that has removed the resource arcs represented by the resources occupied by planned tasks are obtained, and the set of tasks that are successfully planned and the set of tasks that have not been planned, which are respectively denoted by OM.sub.y and OM.sub.w, are obtained.

[0072] At step 6b), resource shortage degrees of all tasks in OM.sub.w are calculated, and the resource shortage degrees are sorted from high to low.

[0073] The minimum number of resources occupied by all feasible task combinations of the task om.sub.i is defined as the resource shortage degree

[00004]${\eta }_i=\underset{p_{i,k}\in P_i}{\min }{\eta }_{i,k}$

of the task, where η.sub.i,k represents the number of resources occupied by the planned task for the k-th resource combination of om.sub.i. A specific process of obtaining the resource shortage degree is as follows.

[0074] At step 6b1), weights are assigned to the observation arcs, storage arcs, and calculation arcs on the resource time-varying graph G.sub.K(V, A). If a resource corresponding to the arc is already occupied by the planned task, the weight of the arc is assigned to 1; otherwise, the weight is assigned to 0.

[0075] At step 6b2), a path between ob.sub.i.sup.┌ts.sup.i.sup./τ┐ and dc.sup.└te.sup.i.sup./τ┘ is obtained by using a shortest path algorithm. A path length is the resource shortage degree η.sub.i of the task.

[0076] On a basis of the resource shortage degree obtained in (6b), the algorithm as illustrated in FIG. 7 for completing the local adjustment of the task planning scheme based on the resource interchange is designed.

[0077] At step 6c), a counter n=1 is initialized.

[0078] At step 6d), an idle resource for the n-th task om.sub.n in OM.sub.w is found through the resource interchange.

[0079] At step 6e), the counter n is increased by 1.

[0080] At step 6f), if n is smaller than or equal to |OM.sub.w|, the method proceeds to step 6d); otherwise, task set OM.sub.y is outputted.

[0081] Specifically, step 6d) includes the following steps.

[0082] At step 6d1), a feasible resource combination Pd.sub.n with the least resources occupied by planned tasks for the task om.sub.n is found, and Pz.sub.n denotes the set of resources occupied by the planned tasks and in Pd.sub.n.

[0083] At step 6d2), each resource arc a∈Pz.sub.n is traversed. For a task fom(a) that occupies the resource arc a, a new resource combination for the task fom(a) is re-allocated through the resource interchange, so that the resource arc a is no longer occupied. If the resource interchange succeeds, G.sub.K′(V′, A′) is updated, and a resource a is deleted from the set of resources Pz.sub.n; otherwise, skip to step 6e).

[0084] At step 6d3), a path p.sub.n from ob.sub.n.sup.┌ts.sup.n.sup./τ┐ and dc.sup.└te.sup.n.sup./τ┘ is found in G.sub.K′(V′, A′) as the new resource combination allocated to task om.sub.n, G.sub.K′(V′, A′) is updated, and task om.sub.n is added to set OM.sub.y.

[0085] The above description is only a specific example of the present disclosure. Obviously, it is possible for those skilled in the art to make various modifications and changes in form and details without departing from the principle and structure of the present disclosure after understanding the content and principle of the present disclosure. However, these modifications and changes based on the concept of the present disclosure are still within the protection scope of the attached claims of the present disclosure.