Sage Journals: Discover world-class research

Abstract

In spacecraft networks, the time-varying topology, intermittent connectivity, and unreliable links make management of the network challenging. Previous works mainly focus on information propagation or routing. However, with a large number of nodes in the future spacecraft networks, it is very crucial regarding how to make efficient network topology controls. In this article, we investigate the topology control problem in spacecraft networks where the time-varying topology can be predicted. We first develop a model that formalizes the time-varying spacecraft network topologies as a directed space–time graph. Compared with most existing static graph models, this model includes both temporal and spatial topology information. To capture the characteristics of practical network, links in our space–time graph model are weighted by cost, efficiency, and unreliability. The purpose of our topology control is to construct a sparse (low total cost) structure from the original topology such that (1) the topology is still connected over space–time graph; (2) the cost efficiency ratio of the topology is minimized; and (3) the unreliability parameter is lower than the required bound. We prove that such an optimization problem is NP-hard. Then, we provide five heuristic algorithms, which can significantly maintain low topology cost efficiency ratio while achieving high reliable connectivity. Finally, simulations have been conducted on random space networks and hybrid low earth orbit/geostationary earth orbit satellite-based sensor network. Simulation results demonstrate the efficiency of our model and topology control algorithms.

Keywords

Spacecraft network satellite-based sensor network time-varying network topology control space–time graph cost efficiency ratio unreliability

Introduction

Space information research has added a new scientific and engineering era to the space exploration history. In most typical scenarios, ground stations use radio signal shot toward spacecraft antennas whenever they come into view. However, the service ability of the system is limited using such point-to-point mode. For instance, low earth orbit (LEO) satellite-based sensors usually have short visibility windows with ground stations, and hence most sensing data cannot be sent to the Earth timely. The immediate answer is to develop a spacecraft network that can be interconnected, standardized, and evolved over the future decades.^1–3 Such motivations led to the development of various spacecraft networking architectures which can support better service ability, for example, the Deep Space Network (DSN),⁴ Interplanetary Internet (IPN),⁵ and space information network (SIN).^6,7 In spacecraft networks, the time-varying topology, lack of continuous connectivity, unreliable links, and long propagation delays pose new challenges in management of the network. Recently, a lot of new routing algorithms have been proposed for spacecraft networks considering time-varying topology and intermittent connectivity.^8–11 However, little research has been done on how to maintain a time-varying spacecraft topology with low-cost efficiency ratio and low unreliability.

Network topology is always a key issue to the maintenance of any network system. It is especially important for spacecraft networks. The cost of each link in spacecraft network is very high both in terms of energy consumption (energy is precious for spacecraft) and monetary cost. Extensive research has been done in ground wireless network, especially in wireless sensor networks^12,13 and ad hoc networks.^14,15 These works mainly focus on how to build a low-cost structure from a static and connected original topology. However, in spacecraft networks, topologies are usually time-varying and may not have continuous connectivity which makes static topology methods unavailable. Fortunately, although spacecraft network is one kind of mobile networks with heterogeneous and independent nodes, the nodes in spacecraft networks do not move spontaneously. In contrast, with regular operation, each spacecraft has a predictable trajectory which can be computed well beforehand. For this kind of time-varying and predictable networks, the space–time graph model¹⁶ is quite suitable to capture both the temporal and spatial dimensions topology information. With this space–time graph which includes all possible temporal and spatial links, the topology control problem is to find a sparse sub-graph of the original space–time graph which can maintain the space–time connectivity between any two nodes while meeting other requirements, for example, minimizing the cost.

Huang et al.¹⁷ first studied the basic topology control problem in time-varying and predictable delay tolerant networks (DTNs). They proposed several heuristics topology control algorithms with the assumption that prediction of the network is perfect and links are all completely reliable. In spacecraft networks, this assumption is obviously too optimistic. Nodes in spacecraft networks may not maintain perfect links due to some reasons, for example, spacecraft antenna slewing and acquisition maneuvers, unknown space noise that degrades the signal-to-noise ratio (SNR), and system failures. Furthermore, although each spacecraft’s trajectory can be predicted based on historical orbit, the prediction cannot be perfect considering complicate celestial mechanics, and links may be shadowed by unknown celestial factors. Li et al.¹⁸ researched the DTNs topology control problem based on Huang’s work considering links may not be completely reliable. They improved Huang’s algorithms using probability of link reliability. But they only considered how to minimize the total cost of the DTNs as Huang’s work. In spacecraft networks, some links may be low cost (e.g. links with small size antenna, low power), but the efficiency (e.g. link capacity) of these links may be low as well. It is clearly not enough for spacecraft networks to consider low total network cost only. Efficiency of each link should also be considered. Shen et al.¹⁹ considered the time-varying and unreliable links in the neural networks, they subject to unreliable links in a unified way, but they paid more attention to the estimation error.

In this article, we study the topology control problem in time-varying spacecraft networks with unreliable links considering link cost efficiency ratio. The main contributions of this article are summarized as follows:

We develop a model that formalizes time-varying but predictable spacecraft network topologies as a directed space–time graph. In this new model, we remove the strong assumptions such as completely reliable links, perfect network prediction. Links in our model are weighted by cost, efficiency, and unreliability. The purpose of our spacecraft network topology control (SNTC) problem is to construct a sparse (low total cost) structure from the original topology such that (a) the topology is still connected over space–time graph; (b) the cost efficiency ratio of the topology is minimized; and (c) the unreliability parameter is lower than the required bound.

Then, we prove that such an optimization problem is NP-hard and then provide five heuristic algorithms that can significantly maintain low total cost efficiency ratio while achieving high reliable connectivity.

Extensive simulations have been conducted on random space networks and hybrid LEO/geostationary earth orbit (GEO) satellite-based sensor network. Simulation results demonstrate the efficiency of our model and topology control algorithms.

The rest of this article is organized as follows. Section “Related works” summarizes related works in spacecraft networks and modeling time-varying networks. Section “Topology model” gives a formal definition of the network model and notations. In section “Topology control problem,” we formally define the SNTC problem and prove its NP-hardness. Then, our proposed heuristics topology control algorithms are presented in section “Heuristic algorithms for SNTC problem.” Section “Simulation results and discussions” presents the simulation results over random space networks and LEO/GEO satellite network. Finally, we make conclusion in section “Conclusion.”

Related works

Spacecraft networks

Traditional space information system is usually one of two kinds:¹ either (1) using point-to-point links from ground stations to spacecrafts (e.g. satellite-based sensors and deep space explorer) or (2) relaying a data stream in bent-pipe communication applications (e.g. communication satellites). Neither approach uses network technologies. However, the service abilities of these systems are quite limited. The immediate answer is to develop a spacecraft network that can be interconnected, standardized, and evolved over the future decades. For example, if the LEO satellite-based sensors can be interconnected with GEO satellites, continuous sensing data stream can be download from GEO relay points.²⁰ The relay of GEO satellites eliminates the visibility bottleneck between LEO spacecrafts and ground stations. Furthermore, emerging applications for space missions require integrated and multi-function spacecraft networks supporting mobile or broadband communication, remote sensing, navigation, and so on. For instance, SIN is a new type of self-organizing system constituted of information systems of space, air, land, and sea.^6,7

Topologies of spacecraft systems using the two traditional kinds of communication mode are simple. System control solutions are usually based on manual commanding of the individual point-to-point links. As the number of spacecrafts grows, such a non-autonomous mechanism becomes unmanageable from the perspective of planning and commanding. An attractive option here is to construct an autonomous spacecraft network. NASA, ESA, and other space agencies are already planning the next generation of networked space architectures to support various current and future space missions. For example, NASA has proposed a number of realistic mid-term scenarios,²¹ including hybrid LEO/GEO satellite network.

The spacecraft networks are different from ground networks. Properties of them are summarized as follows, which we take into consideration when developing our topology model and control algorithms.

Predictable high mobility: spacecrafts are usually in high-speed motion, therefore, visibility opportunities between them change rapidly. However, since each spacecraft follows a predictable trajectory, the network topology varies in a predictable way. Hence, one can compute the time points when nodes come or go as well as the changes in link properties beforehand.

One or more central processing units are needed: all spacecrafts in the network are controlled by ground or space centers, which have substantial computational resources. This effectively allows one to compute the predictable factors and control the network autonomously.

Occurrences of unpredictable changes: the prediction of spacecraft networks cannot be perfect. Unpredictable changes can occur at any time in spacecraft networks, for example, due to solar flares, unknown space noise, or equipment failures. However, these unpredictable changes are uncommon. We take all the unpredictable changes as unreliability in our topology model. In section “Topology model,” we will discuss the unreliability parameters in detail.

Links are high cost with different efficiency: the cost of each link in spacecraft network is very high both in terms of energy consumption and monetary cost. Some links may be low cost (e.g. links with small size antenna, low power), but the efficiency (e.g. link capacity) of these links may be low as well. Efficiency of each link in the topology control should also be considered rather than only go after low total cost.

Modeling time-varying networks

Time-varying networks often vary over time: changes in network topology occur if nodes move around, appear, or disappear. However, a lot of works often ignore such dynamics over time domain. They simply model this time domain information by pure randomness, such as the well-known random walk mobility model,²² the aggregated graph model,^23,24 and the adaptive updating mechanism model.²⁵ However, various time-varying networks can be certain predicted, such as vehicular networks based on public buses,²⁶ mobile social networks,²⁷ and spacecraft networks.

The problem of how to model the predictable time-varying networks has been studied both in ground mobile networks^28,29 and space networks.¹¹ Xuan et al.³⁰ first investigated routing problem in a scheduled dynamic network. They adopted an evolving graph model to capture the time-varying characteristic of such dynamic networks. The evolving graph consists of an indexed time sequence of sub-graphs, where the sub-graph at a given index time point corresponds to the snapshot of the network topology. Then, Monteiro et al.³¹ also used evolving graph model to evaluate the routing protocols in time-varying spacecraft networks. Merugu et al.¹⁶ first considered the routing problem in time-varying networks using a space–time graph model. Cho and Byun³² presented an efficient action detection method that takes a space–time graph optimization approach for real-world videos, by using a space–time graph representing the entire action video. The space–time graph is one kind of directed graph which can capture both the temporal and spatial topology information. We adopt this space–time graph model in our work. In section “Topology model,” we will discuss it in detail. Liu and Wu³³ studied the routing problem in a cyclic mobispace using the space–time graph model too. However, except Huang et al.’s¹⁷ and Li et al.’s¹⁸ works as described in section “Introduction,” most of the previous works only focus on the routing problem in time-varying networks modeled by evolving graphs or space–time graphs. Furthermore, Huang and Li focused on DTNs and they did not consider the link efficiency in their works. In our work, we will investigate the topology control problem in time-varying spacecraft networks. We not only consider low total network cost but also consider the efficiency of each link.

Topology model

Space–time graph model

Let $V_{N} = {v_{1}, v_{2}, \dots, v_{N}}$ be the set of all individual nodes in the spacecraft network, where $N$ is the number of nodes. Different nodes correspond to different spacecrafts or ground stations. Assume that the time is divided into discrete time slots, such as ${T_{1}, T_{2}, \dots, T_{M}}$ , where M is the number of time slots. Each time slot corresponds to a snapshot of the network topology. The concept of snapshot was first informally introduced by Gounder et al.,³⁴ who used it to describe the mobility of an LEO satellite network. They explained that snapshot represents the network topology sample at a particular instance of time. We formalize the snapshot concept in spacecraft networks as follows. We associate the snapshot with a time interval, rather than a time instance.

Definition 1: time intervals and transitions

Let the topology management time T be divided into discrete time slots $T = {T_{1}, T_{2}, \dots, T_{M}}$ , where $M$ is the number of time slots. Each time slot $T_{m}$ is a time set. The elements of the set $T_{m}$ are called time points. For $t', t ″ \in T_{m}$ , and $t' < t ″$ , we use $[t', t ″)$ to represent the time interval ${t \in T_{m} | t' \leq t < t ″}$ . If $t'$ is the initial time point of a time slot $T_{m}$ , we call it transition point. Let $T_{m} = [t_{m - 1}, t_{m})$ , the set of all transition points is ${t_{0}, t_{1}, \dots, t_{M - 1}}$ .

Definition 2: snapshots

The predictable network topology during a time slot $T_{m} = [t_{m - 1}, t_{m})$ can be described by a directed graph $G^{m} = (V_{N}^{m}, E^{m})$ , where $V_{N}^{m}$ is the set of nodes during time slot $[t_{m - 1}, t_{m})$ , and a link $\vec{v_{i}^{m} v_{j}^{m}} \in E^{m}$ represents that node $v_{i}^{m}$ can transmit information $v_{j}^{m}$ during time slot $[t_{m - 1}, t_{m})$ , $i, j \in {1, \dots, N}$ . For $T_{m} \in T$ , a snapshot $S^{m} = (G^{m}, T^{m})$ represents the predictable network topology during time slot $[t_{m - 1}, t_{m})$ . The predictable evolution of the network can be described by a sequence of snapshots ${S^{1}, \dots, S^{m}, \dots, S^{M}}$ . The transition point $t_{m}$ represents the time point when the network topology evolves from $S^{m}$ to $S^{m + 1}$ .

As shown in Figure 1(a), the predictable evolution of the network can be described by a sequence of snapshots. However, this sequence of static snapshots is not convenient to be directly used in the analysis of topology control or network routing. For instance, some of the snapshots may not be connected, such as the first three snapshots in Figure 1(a), which makes the topology control and routing tasks challenging. Many existing works^23,24 use the aggregated graph as shown in Figure 1(b). In the aggregated graph, an edge exists if it has existed in any snapshots from $S^{1}$ to $S^{4}$ in Figure 1(a). Each link in the aggregated graph (Figure 1(b)) is weighted by the link’s occurring probability. For instance, link $\vec{v_{1} v_{2}}$ exists in snapshot $S^{1}$ and $S^{4}$ out of four snapshots, the occurring probability of link $\vec{v_{1} v_{2}}$ is 0.5, thus it is weighted by 0.5. The weighted parameters of other links are similar. However, this aggregated graph ignores the temporal topology information, which may cause failure of connection. For example, from Figure 1(b), there is a path $\vec{v_{5} v_{2} v_{4}}$ . But link $\vec{v_{5} v_{2}}$ only exists in the last snapshot. The link $\vec{v_{2} v_{4}}$ is already disconnected, although its occurring probability is 0.75.

Figure 1.

(a) The predictable evolution of the network can be described by a sequence of snapshots and (b) the sequence of snapshots can be modeled as an aggregated graph.

In this article, we use the space–time graph to model the time-varying spacecraft network. Instead of using aggregated graph, the sequence of snapshots is modeled as a space–time graph, which is a directed graph that can capture both the temporal and spatial topology information. Figure 2 illustrates the space–time graph of the same time-varying network in Figure 1(a).

Figure 2.

Space–time graph of the same time-varying network in Figure 1(a). A space–time path from the source node to the destination node is highlighted (in red and bold).

Definition 3: space–time graph

Let there be a timeline from $t_{0}$ to $t_{M}$ in the graph, where $T = [t_{0}, t_{M}]$ . For M time slots $T = {T_{1}, T_{2}, \dots, T_{M}}$ , let M + 1 layers of nodes be placed in the graph. The first M layers are placed at every transition points ${t_{0}, t_{1}, \dots, t_{M - 1}}$ in the timeline, the last layer is placed at time point $t_{M}$ . Thus, the vertex set $V$ in the graph is $V = {v_{i}^{m} | i = 1, \dots, N \land m = 0, \dots, M}$ , and there are $N (M + 1)$ nodes in the graph, that is, $| V | = N (M + 1)$ . The space between adjacent node layers corresponds to each time slot or snapshot. Then, temporal and spatial links are added between adjacent node layers. A temporal link (horizontal links in Figure 2) $\vec{v_{i}^{m - 1} v_{i}^{m}}$ connects the same node $v_{i} \in V_{N}$ , which represents node $v_{i} \in V_{N}$ storing the information during time slot $T_{m} = [t_{m - 1}, t_{m})$ . A spatial link $\vec{v_{i}^{m - 1} v_{j}^{m}} \land (i \neq j)$ represents that node $v_{i} \in V_{N}$ can transmit information to another node $v_{j} \in V_{N}$ during time slot $T_{m} = [t_{m - 1}, t_{m})$ . The link set $\vec{E}$ in the graph is $\vec{E} = {\vec{v_{i}^{m - 1} v_{j}^{m}} | i \in {1, \dots, N} \land m = 1, \dots, M}$ . This directed graph $\vec{G} = (V, \vec{E}, T)$ is defined as a space–time graph.

By defining the space–time graph $\vec{G}$ , any topology changes in the time-varying network can be captured using this directed graph. As shown in Figure 2, a space–time path from the source node $v_{6}$ to the destination node $v_{1}$ is highlighted. $v_{6}$ stores the information during the first time slot, then transmits it to $v_{4}$ during the second time slot, and so on. Notice that, only one-hop transmission is allowed during each time slot in this space–time graph model, that is, we assume the time slot is short enough. For instance, $v_{6}$ cannot transmit information to $v_{4}$ via $v_{5}$ during the first time slot. However, some links in the spacecraft may be very short. To allow multi-hop transmissions during a time slot, we can add virtual links to represent multi-hop transmissions during a single time slot. As shown in Figure 3, if path $\vec{v_{6} v_{5} v_{4}}$ during time slot is allowed, we add a virtual link $\vec{v_{6}^{0} v_{4}^{1}}$ in the space–time graph. In order to facilitate the analysis and topology design, hereafter, we assume multi-hop transmission during one single time slot is not allowed.

Figure 3.

A virtual link $\vec{v_{6}^{0} v_{4}^{1}}$ (in blue and bold) is added into the space–time graph.

Then, we can define the connectivity of the space–time graph. The connectivity of space–time graphs is quite different from that of static graphs.

Definition 4: connectivity of space–time graph

In a space–time graph $\vec{G} = (V, \vec{E}, T)$ , node $v_{i} \in V_{N}$ can connect to node $v_{j} \in V_{N} (i, j \in {1, \dots, N}, V_{N}$ is the set of all individual nodes in the spacecraft network, if and only if there exist one or more directed paths between $v_{i}^{0}$ and $v_{j}^{M}$ . For any pair of $v_{i}, v_{j} \in V_{N} (i, j \in {1, \dots, N})$ , if there exist one or more directed paths between $v_{i}^{0}$ and $v_{j}^{M}$ , space–time graph $\vec{G} = (V, \vec{E}, T)$ is connected.

The connectivity of $\vec{G}$ guarantees that the information can be transmitted between any pair of nodes in the network over time $T$ . Notice that, connectivity of $\vec{G}$ does not require that each snapshot is connected. For example, the first three snapshots in Figure 1(a) are not connected, but the corresponding space–time graph in Figure 2 is connected. In order to facilitate the analysis, hereafter, we assume that the original space–time graph $\vec{G} = (V, \vec{E}, T)$ of the spacecraft network is always connected over time T (T is long enough). The simplest way to check whether $\vec{G} = (V, \vec{E}, T)$ is connected over time T is to run N rounds (N is the number of nodes in the spacecraft network) of breadth-first search (BFS).³⁵ For each BFS, we check that whether $v_{i}^{0}$ , $i \in {1, \dots, N}$ , can reach every $v_{j}^{M}$ , $j = 1, \dots, N$ .

As a result, the space–time graph model combines independent snapshots of the time-varying network into an integrated graph by using temporal and spatial links. Based on the predictability of the time-varying network, the proposed model converts the dynamic topology to the static topology. This makes it easier to control the topology of a time-varying network.

Capturing the characteristics of spacecraft networks

In space networks, nodes are generally energy constrained. Low link cost is very important to keep the network running efficiently. Furthermore, only considering the total cost of the topology is not enough. Some links may be low cost (e.g. links with small size antenna and low power), but the efficiency (e.g. link capacity) of these links may be low as well. Finally, unreliability of fading wireless spacecraft links should be considered. So, links in our space–time graph model are weighted by cost, efficiency, and unreliability. We discuss them in detail as follows.

1. Cost: for each link $\vec{e} \in \vec{E}$ , there is a corresponding cost $c (\vec{e})$ . This cost can be energy consumption associated with transiting information on that link, or monetary cost to maintain that link. For temporal links, the cost corresponds to the energy consumption or monetary cost to store the data. The total cost of a space–time graph $\vec{G} = (V, \vec{E}, T)$ is the summation of all links’ cost, denoted by $c (\vec{G})$ , that is, $c (\vec{G}) = \sum_{\vec{e} \in \vec{E}} c (\vec{e})$ .

2. Efficiency: similarly, for each link $\vec{e} \in \vec{E}$ , there should be a corresponding efficiency $ε (\vec{e})$ . This efficiency can be associated with link capacity, delay, and so on. For each temporal link, the efficiency can be associated with storage space or memory access speed. The cost efficiency ratio of a link is denoted by $ϕ (\vec{e}) = c (\vec{e}) / ε (\vec{e})$ . The cost efficiency ratio of a space–time graph $\vec{G} = (V, \vec{E}, T)$ is the mean value of all links’ cost efficiency ratio, denoted by $ϕ (\vec{G})$ . That is, $ϕ (\vec{G}) = mea n_{\vec{e} \in \vec{E}} ϕ (\vec{e})$ . The cost efficiency ratio of a path $p^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ is the mean value of all links’ cost efficiency ratio in that path, that is

ϕ (p^{\vec{G}} (v_{i}^{0}, v_{j}^{M})) = \underset{\vec{e} \in p (v_{i}^{0}, v_{j}^{M})}{mean} ϕ (\vec{e})

(1)

3. Unreliability: as described in section “Spacecraft networks,” the prediction of spacecraft networks cannot be perfect. Considering the unreliability of fading wireless spacecraft links, we define the unreliability probability $u (\vec{e})$ for each link. For each spatial link, $u (\vec{e})$ represents the probability of transmission failure over link $\vec{e}$ . For each temporal link, $u (\vec{e})$ represents the probability of storage errors, but such errors are uncommon. Hence, it is fine to assume that all temporal links are perfect reliable, that is, $u (\vec{e}) = 0$ . In addition, we can get the unreliability probability of each link through link estimation techniques at the physical layers.³⁶ Obviously, the unreliability of a path $p^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ $(i, j \in {1, \dots, N})$ is

u (p^{\vec{G}} (v_{i}^{0}, v_{j}^{M})) = 1 - \underset{\vec{e} \in p^{\vec{G}} (v_{i}^{0}, v_{j}^{M})}{Π} (1 - u (\vec{e}))

(2)

In Figure 4, a simple weighted space–time graph with only two individual nodes is illustrated. Each link in this graph is weighted by $(c (\vec{e}), ε (\vec{e}), u (\vec{e}))$ . For instance, the cost of link $\vec{v_{1}^{0} v_{2}^{1}}$ is 5 and its efficiency and unreliability are 3 and 0.2, respectively. The cost efficiency ratio of path $p (v_{1}^{0}, v_{2}^{2}) = \vec{v_{1}^{0} v_{1}^{1} v_{2}^{2}}$ is 1.83, and its unreliability is 0.2. The total cost of the topology is 28, and its cost efficiency ratio is 1.79.

Figure 4.

A simple weighted space–time graph with only two individual nodes.

Then, we define the unreliability of space–time graph $\vec{G} = (V, \vec{E}, T)$ as follows.

Definition 5: unreliability of space–time graph

For each pair of nodes $v_{i}, v_{j} \in V_{N}$ , there exists a least unreliability path in $\vec{G} = (V, \vec{E}, T)$ , denoted by $p_{\min (u)}^{\vec{G}} (v_{i}, v_{j})$ . The unreliability of a space–time graph $\vec{G} = (V, \vec{E}, T)$ is the maximum unreliability among all $p_{\min (u)}^{\vec{G}} (v_{i}, v_{j})$ , $i, j \in {1, \dots, N}$ , that is

u (\vec{G}) = \max_{i, j \in {1, \dots, N}} u (p_{\min (u)}^{\vec{G}} (v_{i}, v_{j}))

(3)

In Figure 4, for each pair of nodes $v_{i}, v_{j} \in V_{2}$ , all $p_{\min (u)}^{\vec{G}} (v_{i}, v_{j})$ , $i, j \in {1, \dots, 2}$ , $u = {0, 0.1, 0.2, 0.3}$ , and $u (\vec{G}) = max {0, 0.1, 0.2, 0.3} = 0.3$ . Thus, the unreliability of this space–time graph is 0.3.

Topology control problem

In this section, we first define the SNTC problem based on the weighted space–time graph described earlier. Then, we prove such a topology optimization problem is NP-hard.

The problem

Generally speaking, denser topology leads to better connectivity and reliability. However, as described in section “Introduction,” it is too expensive to maintain dense topology in spacecraft networks. Hence, the SNTC aims to find a sparse connected topology with low cost efficiency ratio and certain reliability.

Definition 6: SNTC problem

Given a connected space–time graph $\vec{G} = (V, \vec{E}, T)$ , the purpose of SNTC is to construct a sparse (low total cost) sub-graph $\vec{H}$ from the original topology $\vec{G}$ such that (1) $\vec{H}$ is still connected over time T; (2) the cost efficiency ratio of $\vec{H}$ is minimized; and (3) the unreliability $u (\vec{H})$ is lower than the required bound $β$ .

Here, we assume that the given space–time graph $\vec{G} = (V, \vec{E}, T)$ is connected, and the required bound $β$ cannot be lower than $u (\vec{G})$ . Figure 5 illustrates two different topology control results of Figure 4. Both Figure 5(a) and (b) are sub-graphs of Figure 4. It is obvious that these sub-graphs are sparser but still connected over time. That is, each node can find a space–time path to any other node.

Figure 5.

Two different topology control results of Figure 4: (a) result 1 and (b) result 2.

Notice that, in SNTC, we only consider the topology from time slot T₁ to time slot T_M. It seems that packets should be generated at time $t_{0}$ . If a packet arrives at other time point $t_{m}$ , it may not be able to reach the destination in the end of the last time slot. However, in spacecraft networks, the predictable trajectories of spacecrafts are usually periodic and repeated. Hence, the routing is repeated. If time T is long enough, the delivery of packet still can be guaranteed in these cases. If we want the packet generated at any time point to be able to reach the destination at the end of T, we can naively construct a space–time graph for every possible starting time. This will roughly add a factor of T to the complexity of topology control. However, this problem is actually much easier than solving the SNTC problem we study here. Hereafter, the connectivity and unreliability are only considered for a fixed time period T.

Hardness of the problem

The topology control problems of space–time graphs are much harder than those of typical static graphs. For a static graph without temporal information, we can use the spanning tree algorithm³⁷ to keep the connectivity of the graph. However, the connectivity of space–time graph $\vec{G}$ does not require that each snapshot is connected. Hence, it is not possible to simply apply the spanning tree algorithm in each snapshot. We now prove the NP-hardness of SNTC problem by reduction from the directed Steiner tree (DST) problem.³⁸ NP-hardness (non-deterministic polynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, “at least as hard as the hardest problems in NP.” A simple example of an NP-hard problem is the subset sum problem.

The DST problem is a well-known NP-hard problem which can be described as follows. Given a directed graph $G = (V, E)$ , each link in the graph is weighted. Selecting a set of nodes U from V, that is, $U \subseteq V$ , and a root node $v_{r} \in V$ , the DST problem is to find a minimum weight out-branching tree $Γ$ (without loop) rooted at $v_{r}$ , such that all nodes in U are included in $Γ$ .

Theorem 1

The SNTC problem based on space–time graphs is an NP-hard problem.

Proof of Theorem 1

In order to prove SNTC problem is NP-hard, we show how to reduce the DST problem into the SNTC problem. As described earlier, in DST problem, the root $v_{r}$ needs to reach every node in $U \subseteq V$ . Let $U = {u_{1}, \dots, u_{D}}$ , D is the number of nodes in U. Correspondingly, an instance of SNTC problem is constructed as follows.

Assume that, in the DST problem, $h_{\max}$ is the maximum hop count (without loop) from root $v_{r}$ to all other nodes in $G = (V, E)$ . If the number of nodes in $G$ is $| V | = N$ , we have $h_{\max} < N$ . We first construct a space–time graph $\vec{G} = (V, \vec{E}, T)$ with $h_{\max}$ time slots. Hence, there are $h_{\max} + 1$ time layers of nodes in $\vec{G}$ . Let there be $N$ nodes ${v_{1}^{m}, \dots, v_{N}^{m}}$ in each time layer $t_{m}$ . Then, during each time slot $T_{m}$ , we add temporal link $\vec{v_{i}^{m - 1} v_{i}^{m}}$ weighted by 0 for all nodes, and add spatial link $\vec{v_{i}^{m - 1} v_{j}^{m}}$ if there exists link $\vec{v_{i} v_{j}}$ in the mth hop from the root in $G$ . Spatial link $\vec{v_{i}^{m - 1} v_{j}^{m}}$ has the same weight as $\vec{v_{i} v_{j}}$ in $G$ .

From this construction, it is easy to find that the solution of $\vec{G} = (V, \vec{E}, T)$ has the same total weight as the solution of DST in $G$ . Hence, we can take DST problem as a special case (0 weighed temporal links, time slots represent hops) of SNTC problem. Since the DST problem is NP-hard, and any algorithm for solving the SNTC problem will also solve the DST problem, so the SNTC problem is NP-hard.

Figure 6(a) illustrates a simple DST problem with six nodes. Figure 6(b) is the corresponding constructed space–time graph. In Figure 6(a), $v_{2}$ is the root node (the red node), and $U = {v_{4}, v_{5}}$ (blue nodes). The maximum hop count (without loop) from root $v_{r}$ to all other nodes in Figure 6(a) is 5, hence, there are five time slots in Figure 6(b). The red and bold links are the same solutions in G and $\vec{G}$ , respectively.

Figure 6.

Reduction from (a) the DST problem to (b) the SNTC problem. Red node is the root node and blue nodes are the destination nodes. Red and bold links are the corresponding solutions in DST and SNTC problems.

Heuristic algorithms for SNTC problem

Since we have proved that the SNTC problem based on weighted space–time graphs is NP-hard, we propose several heuristic algorithms to construct a sparse structure from the original topology while achieving the connectivity, cost, efficiency, and reliability requirements.

Union of reliable paths with least cost efficiency ratio

The idea of union of reliable paths with least cost efficiency ratio (URPLR) algorithm is to find all the reliable paths with least cost efficiency ratio (RPLR) for each pair of nodes $(v_{i}^{0}, v_{j}^{M})$ , $i, j \in N$ , in the space–time graph $\vec{G} = (V, \vec{E}, T)$ . Obviously, the union of these paths is a sparse sub-graph which can keep the connectivity and satisfies the requirement of SNTC problem. Where, the RPLR is the path with the least cost efficiency ratio among all paths between $v_{i}^{0}$ and $v_{j}^{M}$ , and the unreliability of this path is lower than the required bound $β$ . We denote this kind of path as $p_{\min (ϕ) \land u < β}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ . However, to find path $p_{\min (ϕ) \land u < β}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ in $\vec{G} = (V, \vec{E}, T)$ is the same as restricted shortest path problem,^39–41 which is a well-known NP-hard problem.

Reeves and Salama⁴² proposed a heuristic backward–forward method (BFM) algorithm to solve the restricted shortest path problem. They used the BFM algorithm to find a delay-constrained and least cost (DCLC) path in the graph. We adopt this BFM algorithm in our URPLR algorithm. The basic idea of BFM is as follows.

In order to find RPLR from node $v_{i}^{0}$ to $v_{j}^{M}$ . The path is constructed one node at a time, from the source node to the destination node. Any node at the head of the partially constructed path can choose to add one of only two alternative outgoing links. For example, head node $v_{i}^{0}$ first determines the least cost efficiency ratio path (LRP) $p_{LRP}^{\vec{G}} (v_{i}^{0}, v_{j}^{M}) = \vec{v_{i}^{0} v_{x}^{1} \dots v_{j}^{M}}$ and the least unreliable path (LUP) $p_{LUP}^{\vec{G}} (v_{i}^{0}, v_{j}^{M}) = \vec{v_{i}^{0} v_{y}^{1} \dots v_{j}^{M}}$ . Node $v_{x}^{1}$ is selected to construct the path if $u (p_{LRP}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})) < β$ , otherwise, $v_{y}^{1}$ is selected. Then, the selected node is taken as the head of current partially constructed path and goes on to select the next node. With these selections, a path from $v_{i}^{0}$ to $v_{j}^{M}$ is finally constructed, denoted by $p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ . As a result of a heuristic algorithm, path $p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ is not the optimal answer. However, Kuipers et al.⁴³ compared BFM with other existing methods. They pointed out that BFM is one of the most efficient methods. The computational complexity of BFM is lower, and it usually generates good quality path compared with the optimal. When there is one initial node and a set of destination nodes, the computational complexity of the BFM is basically three times^42,43 that of Dijkstra’s algorithm.⁴⁴

Our URPLR algorithm is based on the BFM. We use BFM to find all the RPLR for each pair of nodes $(v_{i}^{0}, v_{j}^{M})$ , and the union of these paths forms a sparse sub-graph which satisfies the requirement of SNTC problem. The detail of URPLR algorithm is described in Algorithm 1.

Algorithm 1 : Union of Reliable Paths with Least Cost Efficiency Ratio (URPLR)
1: Input:
2: $\vec{G} = (V, \vec{E}, T)$ , $\| V \| = N$ , $T = {T_{1}, T_{2}, \dots, T_{M}}$
3: Output:
4: $\vec{H} = (V, \vec{E'}, T)$
6: Begin:
7: $\vec{E'} \leftarrow \emptyset$
8: for all pair of $(v_{i}^{0}, v_{j}^{M}) \in V$ , $i, j \in {1, \dots, N}$ do
9: Find the reliable paths with least cost efficiency ratio $p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ in $\vec{G}$ using BFM
10: for all links $\vec{e} \in p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ do
11: if $\vec{e} \in p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M}) \land \vec{e} \notin \vec{E'}$ then
12: $\vec{E'} \leftarrow \vec{E'} \cup \vec{e}$
13: end if
14: end for
15: end for
16: Return $\vec{H}$

The time complexity of the URPLR algorithm is $O (N^{2} M (\log (NM) + N))$ because we need to compute $N^{2}$ RPLR for $N^{2}$ pairs of $(v_{i}^{0}, v_{j}^{M}) \in V$ , $i, j \in {1, \dots, N}$ . This can be achieved by running $N$ times of BFM algorithm. Notice that, there are $O (N (M + 1)) = O (NM)$ nodes and at most $O (N^{2} M)$ links in graph $\vec{G}$ , and the computational complexity of BFM algorithm is basically three times that of Dijkstra’s algorithm whose time complexity in $\vec{G}$ is $O (NM (\log (NM) + N))$ . Hence, the time complexity of the URPLR algorithm is $3 N \cdot O (NM (\log (NM) + N)) = O (N^{2} M (\log (NM) + N))$ .

Greed algorithm based on reliable paths with least cost efficiency ratio

In the greed algorithm based on reliable paths with least cost efficiency ratio (GRPLR) algorithm, we simply make a union of all the RPLR. However, this union may contain more links than necessary. Hence, we propose a greedy algorithm based on RPLR to improve the union process. The details of the GRPLR algorithm are described in Algorithm 2. Its basic idea is as follows. First, we need to guarantee the connectivity of $N^{2}$ pairs of nodes in $\vec{G} = (V, \vec{E}, T)$ , where $| V | = N$ , $T = {T_{1}, T_{2}, \dots, T_{M}}$ . Let $U = {(v_{i}^{0}, v_{j}^{M}) | i, j \in {1, \dots, N}}$ be the set of all the pairs of initial and destination nodes in $\vec{G}$ , $| U | = N^{2}$ . In each round, we find all the RPLR $p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ in $\vec{G}$ for every pair of nodes $(v_{i}^{0}, v_{j}^{M}) \in U$ , then we select the one whose cost efficiency ratio is the least among all these $p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ . Second, we add all the links in this selected path into sub-graph $\vec{H}$ and set the cost efficiency ratio $ϕ (\vec{e})$ of the corresponding links in $\vec{G}$ to 0. The pair of initial and destination nodes in the path is removed from U. Finally, after N² rounds of this procedure, all pairs of nodes $(v_{i}^{0}, v_{j}^{M})$ , $i, j \in {1, \dots, N}$ in $\vec{H}$ are connected by RPLR. Obviously, the topology result of the GRPLR method is sparser than the one of the URPLR method.

Algorithm 2 : Greed Algorithm Based on Reliable Paths with Least Cost Efficiency Ratio (GRPLR)
1: Input:
2: $\vec{G} = (V, \vec{E}, T)$ , $\| V \| = N$ , $T = {T_{1}, T_{2}, \dots, T_{M}}$
3: Output:
4: $\vec{H} = (V, \vec{E'}, T)$
5: Begin:
6: $\vec{E'} \leftarrow \emptyset$
7: $U \leftarrow {(v_{i}^{0}, v_{j}^{M}) \| i, j \in {1, \dots, N}}$ % $\| U \| = N^{2}$
8: while $U \neq \emptyset$ do
9: $P \leftarrow \emptyset$
10: for all pair of $(v_{i}^{0}, v_{j}^{M}) \in U$ do
11: Find the reliable paths with least cost efficiency ratio $p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ in $\vec{G}$ using BFM
12: end for
13: $P \leftarrow {p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M}) \| i, j \in {1, \dots, N}}$
14: $p_{LRP} \leftarrow \emptyset$
15: Find the least cost efficiency ratio path $p_{LRP}$ in $P$
16: $v_{x}^{0} \leftarrow$ initial node of $p_{LRP}$
17: $v_{y}^{M} \leftarrow$ destination node of $p_{LRP}$
18: for all links $\vec{e} \in p_{LRP}$ do
19: if $\vec{e} \in p_{LRP} \land \vec{e} \notin \vec{E'}$ then
20: $\vec{E'} \leftarrow \vec{E'} \cup \vec{e}$
21: $ϕ^{\vec{G}} (\vec{e}) \leftarrow 0$ in $\vec{G}$
22: end if
23: end for
24: $U \leftarrow U - (v_{x}^{0}, v_{y}^{M})$
25: while
26: Return $\vec{H}$

The time complexity of the GRPLR algorithm is $O (N^{4} M (\log (NM) + N))$ because in each round $3 O (N)$ times of Dijkstra’s algorithm is running on $\vec{G}$ and the number of the rounds is $| U | = N^{2}$ , that is, $3 O (N) \cdot O (NM (\log (NM) + N)) \cdot N^{2} = O (N^{4} M (\log (NM) + N))$ .

Union of LRP and RPLR

In this LRP&RPLR (union of LRP and RLRP) algorithm, we combine RPLR and LRP to construct the sub-graph $\vec{H}$ . There are two steps in this algorithm. The details of the LRP&RPLR algorithm are described in Algorithm 3. Its basic idea is as follows. In the first step, the unreliability bound $β$ is not considered. We find LRPs for each pair of initial and destination nodes $(v_{i}^{0}, v_{j}^{M}) \in U$ in $\vec{G}$ , where $U = {(v_{i}^{0}, v_{j}^{M}) | i, j \in {1, \dots, N}}$ . Then, we make a union of these LRPs and add the links of them to the sub-graph $\vec{H}$ . After the first step, each pair of initial and destination nodes $(v_{i}^{0}, v_{j}^{M})$ in $\vec{H}$ is connected, but the path $p_{LRP}^{\vec{H}} (v_{i}^{0}, v_{j}^{M})$ between $(v_{i}^{0}, v_{j}^{M})$ , $i, j \in {1, \dots, N}$ , may not satisfy the unreliability bound $β$ . Hence, in the second step, we check the unreliability parameter $u (p_{LRP}^{\vec{H}} (v_{i}^{0}, v_{j}^{M}))$ for each pair of initial and destination nodes in $\vec{H}$ . If $u (p_{LRP}^{\vec{H}} (v_{i}^{0}, v_{j}^{M})) \geq β$ , we find the reliable path with least cost efficiency ratio $p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ between $v_{i}^{0}$ and $v_{j}^{M}$ in $\vec{G}$ using BFM, and then directly add the links in $p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ into $\vec{H}$ . After the second step, the unreliability of $\vec{H}$ also satisfies the requirement.

Algorithm 3 : Union of Least Cost Efficiency Ratio Paths and Reliable Paths with Least Cost Efficiency Ratio (LRP&RPLR)
1: Input:
2: $\vec{G} = (V, \vec{E}, T)$ , $\| V \| = N$ , $T = {T_{1}, T_{2}, \dots, T_{M}}$
3: Output:
4. $\vec{H} = (V, \vec{E'}, T)$
5: Begin:
6: $\vec{E'} \leftarrow \emptyset$
7: $U \leftarrow {(v_{i}^{0}, v_{j}^{M}) \| i, j \in {1, \dots, N}}$ % $\| U \| = N^{2}$
8: for all pair of $(v_{i}^{0}, v_{j}^{M}) \in U$ do
9: Find the least cost efficiency ratio path $p_{LRP}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ in $\vec{G}$ using Dijkstra’s algorithm
10: for all links $\vec{e} \in p_{LRP}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ do
11: if $\vec{e} \in p_{LRP}^{\vec{G}} (v_{i}^{0}, v_{j}^{M}) \land \vec{e} \notin \vec{E'}$ then
12: $\vec{E'} \leftarrow \vec{E'} \cup \vec{e}$
13: end if
14: end for
15: end for
16: for all pair of $(v_{i}^{0}, v_{j}^{M}) \in U$ do
17: if $u (p_{LRP}^{\vec{H}} (v_{i}^{0}, v_{j}^{M})) \geq β$ then
18: Find the reliable paths with least cost efficiency ratio $p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ in $\vec{G}$ using BFM
19: if $\vec{e} \in p_{BFM}^{\vec{G}} (v_{i}^{0}, v_{j}^{M}) \land \vec{e} \notin \vec{E'}$ then
20: $\vec{E'} \leftarrow \vec{E'} \cup \vec{e}$
21: end if
22: end if
23: end for
24: Return $\vec{H}$

The time complexity of the LRP&RPLR algorithm is $O (N^{2} M (\log (NM) + N))$ because both the first and second steps need to run computation of least weight paths (Dijkstra’s algorithm or BFM algorithm) for $N$ times, that is, $N \cdot O (NM (\log (NM) + N)) + 3 N \cdot O (NM (\log (NM) + N)) = O (N^{2} M (\log (NM) + N))$ .

Greed algorithm based on link addition

The basic idea of greed algorithm based on link addition (GLA) algorithm is quite simple. It also has two steps. The first step is the same as Algorithm 3, that is, it starts from constructing a connected sparse topology without considering the unreliability bound $β$ . In the second step, we sort all links in $\vec{G}$ in ascending order of cost efficiency ratio. Then, link $\vec{e}$ is added into graph $\vec{H}$ if the unreliability parameter $u (\vec{H})$ (as defined in Definition 5) cannot satisfy the requirement yet. The details of the GLA algorithm are described in Algorithm 4.

Algorithm 4 : Greed Algorithm Based on Link Addition (GLA)
Input:
1: $\vec{G} = (V, \vec{E}, T)$ , $\| V \| = N$ , $T = {T_{1}, T_{2}, \dots, T_{M}}$
2: Output:
3: $\vec{H} = (V, \vec{E'}, T)$
4: Begin:
5: $\vec{E'} \leftarrow \emptyset$
6: $U \leftarrow {(v_{i}^{0}, v_{j}^{M}) \| i, j \in {1, \dots, N}}$ % $\| U \| = N^{2}$
7: for all pair of $(v_{i}^{0}, v_{j}^{M}) \in U$ do
8: Find the least cost efficiency ratio path $p_{LRP}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ in $\vec{G}$ using Dijkstra’s algorithm
9: for all links $\vec{e} \in p_{LRP}^{\vec{G}} (v_{i}^{0}, v_{j}^{M})$ do
10: if $\vec{e} \in p_{LRP}^{\vec{G}} (v_{i}^{0}, v_{j}^{M}) \land \vec{e} \notin \vec{E'}$ then
11: $\vec{E'} \leftarrow \vec{E'} \cup \vec{e}$
12: end if
13: end for
14: end for
15: Sort all links in $\vec{E}$ in ascending order of cost efficiency ratio
16: for all links $\vec{e} \notin \vec{E'}$ in the order do
17: if $u (\vec{H}) \geq β$ then
18: $\vec{E'} \leftarrow \vec{E'} \cup \vec{e}$
19: end if
20: end for
21: Return $\vec{H}$

The time complexity of the first step is $N \cdot O (NM (\log (NM) + N))$ . The sorting of all links in $\vec{G}$ can be done in $O (N^{2} M \log (N^{2} M))$ computations (with $O (N^{2} M)$ links). The for-loop in the second step can be done in $O (N^{2} M)$ times of least path weight computations $(u (\vec{H}))$ , that is $O (N^{2} M) \cdot O (N^{2} M (\log (NM) + N))$ . Hence, the time complexity of algorithm is $O (N^{2} M (\log (NM) + N)) + O (N^{2} M \log (N^{2} M)) + O (N^{4} M^{2} (\log (NM) + N)) = O (N^{4} M^{2} (\log (NM) + N))$ .

Greed algorithm based on link deletion

The last algorithm greed algorithm based on link deletion (GLD) is also a greedy algorithm. Compared with Algorithm 4 which adds links into $\vec{H}$ , it delete unnecessary links from $\vec{G}$ to get a sparse $\vec{H}$ , which satisfies the requirement. The details of the GLD algorithm are described in Algorithm 5. First, we just add all links in $\vec{G}$ into $\vec{H}$ . Then, we sort all the links in $\vec{H}$ in the descending order of cost efficiency ratio. For each link $\vec{e}$ in the order, link $\vec{e}$ is deleted if without this link $\vec{H}$ still satisfies the unreliability requirement. The time complexity of the GLD algorithm is also $O (N^{4} M^{2} (\log (NM) + N))$ because the sorting process needs $O (N^{2} M \log (N^{2} M))$ computations and the for-loop needs $O (N^{4} M^{2} (\log (NM) + N))$ computations.

Algorithm 5 : Greed Algorithm Based on Link Deletion (GLD)
1: Input:
2: $\vec{G} = (V, \vec{E}, T)$ , $\| V \| = N$ , $T = {T_{1}, T_{2}, \dots, T_{M}}$
3: Output:
4: $\vec{H} = (V, \vec{E'}, T)$
5: Begin:
6: $\vec{E'} \leftarrow \vec{E}$
7: Sort all links in $\vec{E'}$ in descending order of cost efficiency ratio
8: for all links $\vec{e} \in \vec{E'}$ in the order do
9: if $u (\vec{H} - \vec{e}) < β$ then
10: $\vec{E'} \leftarrow \vec{E'} - \vec{e}$
11: end if
12: end for
13: Return $\vec{H}$

Simulation results and discussions

In this section, we present several sets of simulation results to evaluate the effectiveness of five proposed algorithms. Two different scenarios are considered in our simulations, including random space networks and hybrid LEO/GEO satellite-based sensor network. We implement our five proposed algorithms (URPLR, GRPLR, LRP&RPLR, GLA, and GLD) jointly using MATLAB and system tool kit (STK). Furthermore, we compare our algorithm with Huang et al.’s¹⁷ algorithms (ULCP and GrdLCP) and Li et al.’s¹⁸ algorithms (UMCRP and GMCRP). As described in section “Introduction,” Huang’s algorithms only considered the total cost of the network, and Li’s algorithm did not consider the efficiency of links.

Simulation for random space networks

We now evaluate the abovementioned algorithms in a simulation setting that networks are randomly generated, independent of any specific spacecraft-network scenario. Here, we first generate a sequence of snapshots ${S^{1}, \dots, S^{m}, \dots, S^{M}}$ with 10 nodes $(N = 10)$ spreading over 10 time slots $(M = 10)$ . In each snapshot $S^{m}$ , we add link for every pair of nodes with a fixed probability $γ$ . That is, smaller $γ$ leads to sparser network topology. If $γ = 0$ , there will be no links in the network, and $γ = 1$ implies a complete graph in snapshot $S^{m}$ . Then, we model this sequence of snapshots ${S^{1}, \dots, S^{10}}$ in a space–time graph $\vec{G}$ with $N (M + 1) = 110$ nodes. Notice that, we assume the original space–time graph $\vec{G}$ is connected in this article. Hence, we check the connectivity of the generated $\vec{G}$ . If the generated space–time graph $\vec{G}$ is not connected, we discard it and only use those connected graphs in the simulation. Each link in the space–time graph $\vec{G}$ is then weighted by uniform random number as follows: (1) cost of each link is chosen from 10 to 50, (2) link efficiency is chosen from 1 to 10, and (3) link unreliability is chosen from 0.01 to 0.20. Finally, we implement the proposed algorithms on the graph $\vec{G}$ . For each set of simulation settings, we generate 100 random connected space–time graphs and report the average result.

In the first set of simulations, the density of network changes with the increase in probability $γ$ from 0.3 to 0.7. The unreliability bound $β = 0.4$ . Figure 7(a) shows the total cost ratio between topology control result $\vec{H}$ and the original graph $\vec{G}$ with the increase in $γ$ . Figure 7(b) shows total links number ratio between $\vec{H}$ and $\vec{G}$ . The ratio between $\vec{H}$ and $\vec{G}$ implies how much saving can be done by the topology control algorithms. Obviously, all algorithms can construct a sparse (low total cost) sub-graph $\vec{H}$ from the original topology $\vec{G}$ while maintaining the connectivity. Even when with the least network density $(γ = 0.3)$ , most algorithms expect that the GLA algorithm can save more than 55% total cost and 50% number of links. When the network is denser, the algorithms play a more important role. For $γ = 0.7$ , most algorithms can save more than 70% total cost and 60% number of links.

Figure 7.

Simulation results from random networks with different link densities ( $γ$ varies from 0.3 to 0.7) and fixed unreliability bound $β = 0.4$ . (a) Total cost ratio between $\vec{H}$ and $\vec{G}$ . (b) Total links number ratio between $\vec{H}$ and $\vec{G}$ . (c) Cost efficiency ratio of $\vec{H}$ . (d) Unreliability of $\vec{H}$ .

Comparing all the algorithms, we can find that (1) Huang’s algorithms (ULCP and GrdLCP) have the least costs because they only consider the total cost of the network; (2) the total cost of our algorithms is higher than Huang’s and Li’s (UMCRP and GMCRP) since our algorithms consider the link efficiency which is not mentioned in their algorithms; (3) GLA algorithm has the largest cost as it simply add too many low cost efficiency ratio links in the ascending order; (4) the cost of the LRP&RPLR algorithm is lower than URPLR because it combines LRP and URPLR; and (5) overall, GRPLR and GLD have the best cost performance among all our five proposed algorithms. Figure 7(c) shows the cost efficiency ratio of each sub-graph $\vec{H}$ generated by all the algorithms. Comparing all the algorithms, it is obvious that (1) the cost efficiency ratios of Huang’s and Li’s algorithms are much higher than our algorithms, and sometimes are higher than the original topology $\vec{G}$ ; (2) when the network is denser, our algorithms can achieve lower cost efficiency ratio since there are more proper links for selection; and (3) GRPLR and GLD have the best performance. Figure 7(d) shows the unreliability of each sub-graph $\vec{H}$ generated by all the algorithms. Obviously, Huang’s algorithms (ULCP and GrdLCP) cannot satisfy the unreliability bound requirement $β = 0.4$ , because they only consider the total cost of the network. Other algorithms can achieve the unreliability bound requirement, and the reliability performances of them are close. However, considering the cost efficiency ratio, our algorithms GRPLR, LRP&RPLR, and GLD are better choices. When the original topology $\vec{G}$ is sparse, for example, $γ = 0.3$ . In this case, the unreliability parameter of the original $\vec{G}$ is just lower than 0.4, but our algorithms can remove around 50% links, make the cost efficiency ratio about 20% lower than $\vec{G}$ , and still achieve the unreliability requirement.

In the second set of simulations, the link density of the original topology $\vec{G}$ is kept fixed at $γ = 0.5$ . We implement all the algorithms with different values of unreliability requirements, that is, $β$ varies from 0.3 to 0.7. From the simulation results shown in Figure 8, it is easy to observe that stricter unreliability requirement leads to higher cost efficiency ratio of our algorithms. When the unreliability requirement becomes weaker ( $β$ varies from 0.3 to 0.7), more links can be removed or be replaced by low cost efficiency ratio links. Notice that, in Figure 8(a), Huang’s (ULCP and GrdLCP) and Li’s algorithms (UMCRP and GMCRP) are not affected by the unreliability requirement. In addition, the GLA algorithm performs better when the unreliability requirement is weak $(β = 0.7)$ . Figure 8(b) shows the unreliability of each sub-graph $\vec{H}$ generated by all the algorithms. Our algorithm can always achieve the unreliability requirement.

Figure 8.

Simulation results from random networks with different unreliability bounds ( $β$ varies from 0.3 to 0.7) and fixed link density $γ = 0.5$ . (a) Cost efficiency ratio of $\vec{H}$ . (b) Unreliability of $\vec{H}$ .

So far, we only implement our algorithms in small-scale networks with 10 nodes $(N = 10)$ spreading over 10 time slots $(M = 10)$ . However, when the number of nodes or the number of time slots increase, all the algorithms need much more running time to find topology solutions. Hereafter, the running time of each algorithm is defined as the total time to find the topology solution $\vec{H}$ . In the third set of simulations, we implement all the algorithms over larger random networks with 50 nodes and 50 time slots, that is, in a space–time graph $\vec{G}$ with $N (M + 1) = 2550$ nodes. Different from the first two sets of simulations, link unreliability here is chosen from 0.01 to 0.05 because paths here are longer. All the other parameters are kept the same as previous two sets of simulations. Due to the long computing time (nearly 1 h for each space–time graph using Intel Core2 T9600 CPU with 4GB Random-Access Memory), we only generate five random connected space–time graphs and report the average result. Figure 9 shows the simulation result in larger networks with different link densities ( $γ$ varies from 0.3 to 0.6) and fixed unreliability bound $β = 0.4$ . Obviously, the conclusions in small-scale networks are still valid. Our algorithms can significantly reduce the cost efficiency ratio of the network. In Figure 9(b), we can see that every algorithm needs more running time for denser network. Huang’s algorithms (ULCP and GrdLCP) run most fast, because they only consider the total cost of the network. Our most fast algorithm is URPLR. It has similar running time with Li’s UMCRP algorithm. It is interesting that the GLD algorithm usually uses more running time than the GLA algorithm although the time complexities of them are the same $(O (N^{4} M^{2} (\log (NM) + N)))$ . This is mainly because the GLD algorithm repetitively computes the unreliability of the network if a link is deleted. That makes GLD iterates almost all links in $\vec{G}$ in the decreasing order of cost efficiency until the unreliability requirement cannot be satisfied. We also perform other simulations with different settings, for instance, various unreliability requirement, network sizes. The results and conclusions of these simulations are similar, so we omit them here due to space limit.

Figure 9.

Simulation result in larger networks with different link densities ( $γ$ varies from 0.3 to 0.6) and fixed unreliability bound $β = 0.4$ . (a) Cost efficiency ratio of $\vec{H}$ . (b) Running time of each algorithm.

Simulation for hybrid LEO/GEO satellite-based sensor networks

LEO satellite-based sensors are increasingly used in the Earth observations. The high-resolution measurements of these LEO satellite-based sensors generate substantial quantities of scientific data that must be transmitted to the ground station. However, due to the low orbit (400–900 km altitude), LEO satellite usually has small visibility windows (around 10 min) with ground stations. These small visibility windows reduce the communication chance between LEO satellite-based sensors and ground stations and result in a communication bottleneck. To address this problem, many space agencies have proposed the use of GEO satellites as stationary relay points, for example, the Transformational Satellite Communications System (TSAT)^45,46 and NASA’s LEO/GEO satellite network proposal.²¹ GEO satellites usually have long visibility windows with LEO satellites, and GEO satellites are always visible to the ground stations. Hence, the relay of GEO satellites can eliminate the communication bottleneck and provide a continuous, flexile, data-stream downlink for LEO satellite-based sensors. This new, more complex, spacecraft network topology is time-varying and predictable. It cannot be managed using traditional, manually commanded, point-to-point communication. The topology control of it is important.

As shown in Figure 10, in this simulation scenario, we consider a hybrid LEO/GEO satellite-based sensor network with three GEO satellites, six LEO satellite-based sensors, and three ground stations. Both LEO and GEO satellites are operated in Walker Constellation.⁴⁷ The detailed orbit parameters of each satellite are described in Table 1. We use 554 km as the altitude of LEO satellites because the recursive period⁴⁸ of orbits with this altitude is 1 day. Furthermore, LEO satellite-based sensors are usually in sun-synchronous orbit,⁴⁸ so the inclination of the orbit is 97.5°. The longitudes of three GEO satellites’ foot node are 110°E, 10°W, and 130°W, respectively. The locations of ground stations are shown in Table 2. The downward beam-width of each GEO satellite and LEO satellite is 18° and 129.9°, respectively.

Figure 10.

Architecture of hybrid LEO/GEO satellite-based sensor network.

Table 1.

Parameters of satellite nodes.

Orbit parameter	LEO	GEO
Number of planes	2	1
Number of satellites per plane	3	3
Inter-plane spacing	1	0
RAAN spread (°)	180	360
Altitude (km)	554	35,786
Eccentricity	0	0
Inclination (°)	97.5	0

LEO: low earth orbit; GEO: geostationary earth orbit; RAAN: right ascension of the ascending node.

Orbit epoch: 1 July 2015 12:00:00 UTCG.

Table 2.

Ground station locations.

Ground station	Latitude	Longitude
Beijing	40°N	116°E
Hawaii	19°N	155°W
Paris	48°N	2°E

Therefore, possible links in this network are shown in Figure 11(a), which form the LEO/GEO network topology among all nodes. For clarity, not all possible links are shown here (e.g. inter-LEO and GEO satellite links). Since all ground stations are connected by Internet, we can use a virtual node to replace them (in STK, ground stations are combined into a constellation). Figure 11(b) shows the corresponding space–time graph model of Figure 11(a), where three ground stations are merged into one single virtual node. Notice that, unlike the connectivity from nodes to all other nodes in random networks, we only concern the connectivity from LEO satellites to the ground stations. Each link of space–time graph in this simulation is weighted as follows. For all spatial links: (1) link cost is proportional to the average distance of two vertices during one time slot; (2) link efficiency is randomly chosen from 1 to 10; and (3) link unreliability is randomly chosen from 0.01 to 0.05. For all temporal links, we assume that they have zero cost and perfect reliability, that is, both the cost efficiency ratio and unreliability are 0. Since the cost efficiency ratio of each temporal link is 0, we only compute the cost efficiency ratio of spatial links here.

Figure 11.

Topology of hybrid LEO/GEO satellite-based sensor network: (a) the network topology with with time-varying links and (b) the corresponding space–time graph.

In this simulation, we use STK to calculate node parameters (e.g. position, etc.) and link parameters (e.g. range, duration, etc.). Then, node and link parameters generated from STK are exported to MATLAB for further processing and analysis. Figure 12 shows a snapshot from STK scenario. The start epoch and stop epoch of the STK scenario are 1 July 2015 12:00:00 UTCG and 2 July 2015 12:00:00 UTCG, respectively, that is, 24-hduration. We divide this 24 h into 144 topology management time equally, that is, there are 144 space–time graphs with $T = 10 \min$ . Then, we further divide this $T = 10 \min$ into 10 time slots. That is, for each space–time graph, $M = 10$ . Our simulation result is the statistic average of these 144 space–time graphs. Notice that, in some space–time graphs, one LEO satellite cannot be covered by any GEO satellites. That is, the connectivity between LEO satellite and ground station cannot be guaranteed. In this condition, this LEO node stores the information and waits for the next space–time graph.

Figure 12.

A snapshot of the STK scenario.

Figure 13 shows the simulation results over this LEO/GEO satellite network, the unreliability bound here is $β = 0.07$ . Similar conclusions which are consistent with those in random space networks can be drawn from these following results. First of all, our algorithms can significantly reduce the total cost/links usage of the LEO/GEO satellite network while maintaining low network cost efficiency ratio. Obviously, our proposed heuristic algorithms can solve the SNTC problem well. Furthermore, the cost efficiency ratio of Huang’s and Li’s algorithms is much higher than our algorithms, and even higher than that without control. Because our algorithms consider the link efficiency which is not mentioned in their algorithms. Last but not least, all proposed algorithms can satisfy the unreliability requirement, except for ULCP and GrdLCP algorithms. Because ULCP and GrdLCP algorithms only consider the total cost of the network. This simulation also confirms the efficiency of our proposed algorithms in the real-world spacecraft network.

Figure 13.

Simulation results on the LEO/GEO satellite network $(β = 0.07)$ .

Conclusion

We studied the topology control problem in predictable time-varying spacecraft networks with unreliable links, using a space–time graph model weighted by cost, efficiency, and unreliability. Compared with most existing models, this model includes both temporal and spatial topology information. We first proved that this topology control problem is NP-hard, then we proposed five heuristic algorithms. Different from previous works, our algorithms not only consider the total cost of the network topology but also consider the cost efficiency ratio and unreliability. Simulation results from random space networks and hybrid LEO/GEO satellite-based sensor network demonstrated the efficiency of our proposed algorithms.

However, it is also seen that our algorithms still have some limitations: (1) we have assumed that only one-hop transmission is allowed during each time slot in this space–time graph model, which makes multi-hop to be transformed to virtual links; (2) we still assumed that the predictions of links and unreliability are feasible, hence the performance may degrade when unpredictable events happen. Therefore, in our future works, we will (1) design more efficient space–time graph model which allows multi-hop in one time slot; (2) design algorithms to adapt the unpredictable events rather than take them as unreliable probability.

Footnotes

Handling Editor: Kavita Pandey

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by Innovative Foundation for Young Scholars of Space Engineering University under Grant No. 2019-017.

ORCID iD

Wei Zhang

References

Mukherjee

Ramamurthy

. Communication technologies and architectures for space network and interplanetary internet. IEEE Commun Surv Tut 2013; 15: 881–897.

Bhasin

Hayden

. Architecting communication network of networks for space system of systems. In: Proceedings of the IEEE system of systems engineering conference (SOSE), Singapore, 2–4 June 2008, pp.1–7. New York: IEEE.

Liu

. A feasible mesh-based architecture and protocol model of space information network. In: Proceedings of the IEEE geoscience and remote sensing conference (IITA-GRS), Qingdao, China, 28–31 August 2010, pp.529–531. New York: IEEE.

Cesarone

Abraham

Deutsch

. Prospects for a next-generation deep-space network. P IEEE 2007; 95: 1902–1915.

Akyildiz

Akan

Chen

, et al. The state of the art in interplanetary internet. IEEE Commun Mag 2004; 42: 108–118.

Zhang

, et al. A novel proposal of architecture and network model for space communication network. In: Proceedings of the IAF 65th international astronautical congress (IAC), Toronto, ON, Canada, 29 September–3 October 2014, pp.1–7. Paris: International Astronautical Federation.

Zhang

Gou

, et al. A hierarchical autonomous system based topology control algorithm in space information network. KSII T Internet Inf 2015; 9: 3572–3593.

Zhao

Sun

, et al. Dynamic fault-tolerant routing based on FSA for LEO satellite networks. IEEE T Comput 2013; 62: 1945–1958.

Shrader

Babikyan

Jones

, et al. Rate control for network-coded multipath relaying with time-varying connectivity. IEEE J Sel Area Comm 2011; 29: 1106–1117.

10.

Song

Chao

Yang

, et al. TLR: a traffic-light-based intelligent routing strategy for NGEO satellite IP networks. IEEE T Wirel Commun 2014; 13: 3380–3393.

11.

Fischer

Basin

Eckstein

, et al. Predictable mobile routing for spacecraft networks. IEEE T Mobile Comput 2013; 12: 1174–1187.

12.

Youn

Lee

. Topology control algorithm considering antenna radiation pattern in three-dimensional wireless sensor networks. Int J Distrib Sens N 2014; 10: 801519.

13.

Chiwewe

Hancke

. A distributed topology control technique for low interference and energy efficiency in wireless sensor networks. IEEE T Ind Inform 2012; 8: 11–19.

14.

Nishiyama

Ngo

Ansari

, et al. On minimizing the impact of mobility on topology control in mobile ad hoc networks. IEEE T Wirel Commun 2012; 11: 1158–1166.

15.

Chinara

Rath

. Topology control by transmission range adjustment protocol for clustered mobile ad hoc networks. Int J Distrib Sens N 2011; 2011: 1–10.

16.

Merugu

Ammar

Zegura

. Routing in space and time in networks with predictable mobility. Atlanta, GA: Georgia Institute of Technology, 2004, pp.1–13.

17.

Huang

Chen

Zhu

, et al. Topology control for time-evolving and predictable delay-tolerant networks. IEEE T Comput 2013; 62: 2308–2321.

18.

Chen

Huang

, et al. Reliable topology design in time-evolving delay-tolerant networks with unreliable links. IEEE T Mobile Comput 2015; 14: 1301–1314.

19.

Shen

Zhu

Zhang

, et al. Extended dissipative state estimation for Markov jump neural networks with unreliable links. IEEE T Neur Net Lear 2017; 28(2): 346–358.

20.

Fouad

Using LEO-GEO cross-link to enhance LEO satellite communication coverage area. In: Proceedings of system simulation and scientific computing (ICSC), Beijing, China, 10–12 October 2008, pp.882–887. New York: IEEE.

21.

NASA Space Communication Architecture Working Group. NASA Space Communication and Navigation Architecture recommendations for 2005–2030, https://syzygyengineering.com/2007/SCAWG_Report.pdf (accessed 27 November 2015).

22.

. Distributional convergence of intermeeting times under the generalized hybrid random walk mobility model. IEEE T Mobile Comput 2010; 9: 1201–1211.

23.

Yuan

Cardei

Predict and relay: an efficient routing in disruption-tolerant networks. In: Proceedings of the tenth ACM international symposium on mobile ad hoc networking and computing (MobiHoc), New Orleans, LA, 18–21 May 2009, pp.95–104. New York: ACM.

24.

Lindgren

Doria

Schelen

. Probabilistic routing in intermittently connected networks. ACM SIGMOBILE Mob Comput Commun Rev 2003; 7: 19–20.

25.

Hua

Dong

, et al. Distributed fault-tolerant time-varying formation control for second-order multi-agent systems with actuator failures and directed topologies. IEEE T Circuits-II 2018; 65(6): 774–778.

26.

Acer

Giaccone

Hay

, et al. Timely data delivery in a realistic bus network. IEEE T Veh Technol 2012; 61: 1251–1265.

27.

Nazir

Seneviratne

Time critical content delivery using predictable patterns in mobile social networks. In: Proceedings of computational science and engineering (CSE), Vancouver, BC, Canada, 29–31 August 2009, pp.1066–1073. New York: IEEE.

28.

Ying

Shakkottai

. Scheduling in mobile ad hoc networks with topology and channel-state uncertainty. IEEE T Automat Contr 2012; 57: 2504–2517.

29.

Liang

Haas

. Predictive distance-based mobility management for multidimensional PCS networks. IEEE ACM T Network 2003; 11: 718–732.

30.

Xuan

Ferreira

Jarry

. Computing shortest, fastest, and foremost journeys in dynamic networks. Int J Found Comput S 2003; 14: 267–285.

31.

Monteiro

Goldman

Ferreira

. Performance evaluation of dynamic networks using an evolving graph combinatorial model. In: Proceedings of wireless and mobile computing, networking and communications (WiMob), Montreal, QC, Canada, 19–21 June 2006, pp.173–180. New York: IEEE.

32.

Cho

Byun

. A space-time graph optimization approach based on maximum cliques for action detection. IEEE T Circ Syst Vid 2016; 26(4): 661–672.

33.

Liu

. Practical routing in a cyclic MobiSpace. IEEE ACM T Network 2011; 19: 369–382.

34.

Gounder

Prakash

Abu-Amara

Routing in LEO-based satellite networks. In: Proceedings of the emerging technologies symposium of wireless communications and systems (ETWCS), Richardson, TX, 13 April 1999, pp.1–6. New York: IEEE.

35.

Silvela

Portillo

. Breadth-first search and its application to image processing problems. IEEE T Image Process 2001; 10: 1194–1199.

36.

Booton

Dickens

. Method of estimating satellite link quality in a time slotted tactical UHF SATCOM system. In: Proceedings of IEEE military communications conference (MILCOM), San Diego, CA, 18–20 November 2013, pp.628–633. New York: IEEE.

37.

Kwok

Constantinides

Siu

. An efficient recursive shortest spanning tree algorithm using linking properties. IEEE T Circ Syst Vid 2004; 14: 852–863.

38.

Zosin

Khuller

. On directed Steiner trees. In: Proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, 6–8 January 2002, pp.59–63. New York: ACM.

39.

Joksch

. The shortest route problem with constraints. J Math Anal Appl 1966; 14: 191–197.

40.

Wang

Crowcroft

. Quality-of-service routing for supporting multimedia applications. IEEE J Sel Area Comm 1996; 14: 1228–1234.

41.

Xie

Yang

Kim

. Reconfigurable routing protocol for free space optical sensor networks. Sensors 2012; 12: 4824–4845.

42.

Reeves

Salama

. A distributed algorithm for delay-constrained unicast routing. IEEE ACM T Network 2000; 8: 239–250.

43.

Kuipers

Korkmaz

Krunz

, et al. Performance evaluation of constraint-based path selection algorithms. IEEE Network 2004; 18: 16–23.

44.

Bondy

Murty

USR

. Graph theory. London: Springer, 2008.

45.

Adachi

Zambre

Pulliam

, et al. Network management approach for the TSAT network. In: Proceedings of IEEE military communications conference (MILCOM), San Diego, CA, 16–19 November 2008, pp.1–7. New York: IEEE.

46.

Vanderpoorten

Cohen

Pino

, et al. Transformational satellite communications system (TSAT) lessons learned: perspectives from TSAT program leaders. In: Proceedings of IEEE military communications conference (MILCOM), Orlando, FL, 29 October–1 November 2012, pp.1–6. New York: IEEE.

47.

Zhao

Guo

. An autonomous navigation study of walker constellation based on reference satellite and inter-satellite distance measurement. In: Proceedings of IEEE Chinese guidance, navigation and control conference (CGNCC), Yantai, China, 8–10 August 2014, pp.2553–2557. New York: IEEE.

48.

Yang

. Long-term evolution and control for sun-synchronous and recursive orbit. Spacecr Eng 2008; 17: 26–30.

Efficient topology control for time-varying spacecraft networks with unreliable links

Abstract

Keywords

Introduction

Related works

Spacecraft networks

Modeling time-varying networks

Topology model

Space–time graph model

Definition 1: time intervals and transitions

Definition 2: snapshots

Definition 3: space–time graph

Definition 4: connectivity of space–time graph

Capturing the characteristics of spacecraft networks

Definition 5: unreliability of space–time graph

Topology control problem

The problem

Definition 6: SNTC problem

Hardness of the problem

Theorem 1

Proof of Theorem 1

Heuristic algorithms for SNTC problem

Union of reliable paths with least cost efficiency ratio

Greed algorithm based on reliable paths with least cost efficiency ratio

Union of LRP and RPLR

Greed algorithm based on link addition

Greed algorithm based on link deletion

Simulation results and discussions

Simulation for random space networks

Simulation for hybrid LEO/GEO satellite-based sensor networks

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References