Low-overhead online routing scheme for ultra-dense software-defined CubeSat networks
In a method for routing communications through a constellation ( 100 ) of a plurality of CubeSats orbiting a planet and responsive to a ground controller, the ground controller determines optimal tunnels ( 210 ) that include inter-satellite links ( 122 ) between CubeSats by: generating virtual nodes ( 110 ); generating the sub-satellite points ( 120 ) to correspond to points on a path through each virtual node that CubeSats follow; calculating an inter-satellite link from a sub-satellite point another sub-satellite point during a period from a time of initialization when the first sub-satellite point is at an entry point of the first virtual node until the first sub-satellite point is at an exit point; and generating an information packet describing the optimal tunnel ( 210 ) including inter-satellite links ( 122 ) that interconnect the sub-satellite points ( 120 ). The information packet transmitted from the ground controller to one of the CubeSats and is forwarded from one of the CubeSats to remaining CubeSats.
1. A method for routing communications through a constellation of a plurality of CubeSats orbiting a planet and responsive to a ground controller, comprising the steps of:
(a) determining by the ground controller at least one optimal tunnel that includes a plurality of inter-satellite links between CubeSats in the plurality of CubeSats by executing the steps of:
(i) generating a virtual network topology by partitioning an orbital surface around the planet into a plurality of Voronoi tessellations and designating each of the Voronoi tessellations as a virtual node;
(ii) generating the plurality of sub-satellite points so as to correspond to a plurality points on a path through each virtual node that CubeSats of the plurality of CubeSats follow as they transit through each virtual node;
(iii) for at least a portion of the plurality of sub-satellite points, calculating an inter-satellite link from a first sub-satellite point in a first virtual node to a second sub-satellite point in a different second virtual node during a period for any point of time from a time of initialization when the first sub-satellite point is at an entry point of the first virtual node until the first sub-satellite point is at an exit point of the first virtual node; and
(iv) generating an information packet describing the optimal tunnel that includes a plurality of inter-satellite links that interconnect a portion of the plurality of sub-satellite points during the period;
(b) transmitting the information packet from the ground controller to a selected one of the CubeSats; and
(c) forwarding the information packet from the selected one of the CubeSats to remaining ones of the CubeSats corresponding to sub-satellite points included in the tunnel.
2. The method of claim 1 , wherein each inter-satellite link has an associated distance and further comprising the step of calculating the distance on a per-orbital basis.
3. The method of claim 2 , wherein the step of calculating the distance is repeated at 0.01 second intervals.
4. The method of claim 1 , wherein each inter-satellite link has an associated reliability and further comprising the step of calculating the reliability on a per-orbital basis.
5. The method of claim 4 , wherein the step of calculating the reliability is repeated at 0.01 second intervals.
6. The method of claim 1 , wherein the tunnel is selected by executing the steps of:
1:
Input: Λ, β, G, i i , e i , d i , y l (i − 1), T i
2:
Output: X i
3:
X i ← Ø
4:
for t ← 1 to |T i | do
5:
if U OL (i, t) = min t∈Ti {U OL (i, t)}
then
6:
X i + X i ∪ {t}
7:
end if
8:
end for
9:
t ← 0
10:
while t < |X i | do
11:
if
∃
l
∈
t
:
y
l
(
i
-
1
)
+
w
l
d
i
c
l
❘
"\[LeftBracketingBar]"
X
i
❘
"\[RightBracketingBar]"
or
g
l
(
i
-
1
)
+
d
i
❘
"\[LeftBracketingBar]"
X
i
❘
"\[RightBracketingBar]"
>
c
l
then
12:
X i ← X i \ {t}
13:
if X i = Ø then
14:
break
15:
else
16:
t ← 0
17:
continue
18:
end if
19:
end if
20:
t ← t + 1
21:
end while
22:
if X i = Ø then
23:
return FAIL
24:
else
25:
return X i
26:
end if,
where: ∧ is an estimated optimal cost; β is a performance guarantee; G is an undirected graph corresponding to the constellation that includes the plurality of virtual nodes and a set of edges; i, i is an i th flow request; e i is an egress node; d i is a demand metric representing required bandwidth; y l is a normalized cost associated with a link; T i is a set of tunnels; X i is an optimal offline tunnel set; t is a tunnel; U OL (i, t) is a unity function; w l is a unit link flow cost; d i is a demand metric; and g l is a link capacity constraint.
7. A system for routing communications through a constellation of a plurality of CubeSats orbiting a planet, comprising:
(a) a ground controller to which at least a portion of the plurality of CubeSats is responsive, the ground controller configured to determine at least one optimal tunnel that includes a plurality of inter-satellite links between CubeSats in the plurality of CubeSats by executing the steps of:
(i) generate a virtual network topology by partitioning an orbital surface around the planet into a plurality of Voronoi tessellations and designate each of the Voronoi tessellations as a virtual node;
(ii) generate the plurality of sub-satellite points so as to correspond to a plurality points on a path through each virtual node that CubeSats of the plurality of CubeSats follow as they transit through each virtual node;
(iii) for at least a portion of the plurality of sub-satellite points, calculate an inter-satellite link from a first sub-satellite point in a first virtual node to a second sub-satellite point in a different second virtual node during a period for any point of time from a time of initialization when the first sub-satellite point is at an entry point of the first virtual node until the first sub-satellite point is at an exit point of the first virtual node; and
(iv) generate an information packet describing the optimal tunnel that includes a plurality of inter-satellite links that interconnect a portion of the plurality of sub-satellite points during the period; and
(b) the ground controller further configured to transmit the information packet from the ground controller to a selected one of the CubeSats,
wherein a selected one of the CubeSats is configured to forward the information packet to remaining ones of the CubeSats corresponding to sub-satellite points included in the tunnel.
8. The system of claim 7 , wherein each inter-satellite link has an associated distance and further comprising the step of calculating the distance on a per-orbital basis.
9. The system of claim 8 , wherein the step of calculating the distance is repeated at 0.01 second intervals.
10. The system of claim 7 , wherein each inter-satellite link has an associated reliability and further comprising the step of calculating the reliability on a per-orbital basis.
11. The system of claim 10 , wherein the step of calculating the reliability is repeated at 0.01 second intervals.
12. The system of claim 7 , wherein the tunnel is selected by executing the steps of:
1:
Input: Λ, B, G, i i , e i , d i , y l (i − 1), T i
2:
Output: X i
3:
X i ← Ø
4:
for t ← 1 to |T i | do
5:
if U OL (i, t) = min t∈Ti {U OL (i, t)}
then
6:
X i ← X i ∪ {t}
7:
end if
8:
end for
9:
t ← 0
10:
while t < |X i | do
11:
if
∃
l
∈
t
:
y
l
(
i
-
1
)
+
w
l
d
i
c
l
❘
"\[LeftBracketingBar]"
X
i
❘
"\[RightBracketingBar]"
or
g
l
(
i
-
1
)
+
d
i
❘
"\[LeftBracketingBar]"
X
i
❘
"\[RightBracketingBar]"
>
c
l
12:
X i ← X i \ {t}
13:
if X i = Ø then
14:
break
15:
else
16:
t ← 0
17:
continue
18:
end if
19:
end if
20:
t ← t + 1
21:
end while
22:
if X i = Ø then
23:
return FAIL
24:
else
25:
return X i
26:
end if,
where: ∧ is an estimated optimal cost; β is a performance guarantee; G is an undirected graph corresponding to the constellation that includes the plurality of virtual nodes and a set of edges; i i , is an i th flow request; e i is an egress node; d i is a demand metric representing required bandwidth; y l is a normalized cost associated with a link; T i is a set of tunnels; X i is an optimal offline tunnel set; t is a tunnel;
U OL (i, t) is a unity function; w l is a unit link flow cost; d i is a demand metric; and g l is a link capacity constraint.