Routing Optimization of Small Satellite Networks Based on Multi-commodity Flow

Abstract

As the scale of small satellite network is not large and the transmission cost is high, it is necessary to optimize the routing problem. We apply the traditional time-expanded graph to model the data acquisition of small satellite network so that we can formulate the data acquisition into a multi-commodity concurrent flow optimization problem (MCFP) aiming at maximizing the throughput. We use an approximation method to accelerate the solution for MCFP and make global optimization of routing between satellite network nodes. After the quantitative comparison between our MCFP algorithm and general augmented path maximum flow algorithm and exploring the detail of the algorithm, we verify the approximation algorithm’s reasonable selection of routing optimization in small satellite network node communication.

Y. Zhang—Foundation Item: Science and Technology on Communication Networks Laboratory Foundation Project; Aerospace Field Pre-research Foundation Project (060501).

1 Introduction

Recently, more and more small satellites are launched to carry out various space missions. Small satellites receive mission data from observable objects and send these data to the data processing center via ground stations or relay satellites [1]. As the scale of small satellite network is not large and the transmission cost is high, we need to optimize the routing and allocate the resources properly.

The time-expanded graph (TEG) is a useful tool to model the topology of network [2]. To deal with the challenges caused by the impacts of satellites’ movements during delivery process, Liu and Sheng apply the traditional time-expanded graph to model the data acquisition [3]. The delivery strategies and the data acquisition are formulated into an optimization problem to maximize the throughput. For the tiny topology with few satellites, the problems of routing and resources allocation have been emerged as a topic on multi-commodity problem (MCP). However, Liu and Sheng concentrate on the small satellite model using TEG instead of giving a practical algorithm to solve it.

Though finding an integer flow solution to the MCP is proved to be an NP-complete problem [4]. A polynomial time solution has been found through carrying Linear Programming by allowing fractional flows [5]. Moreover, researchers have concentrated on approximation schemes to speed up the solution. Following by Young in 1995 [7], Shahrokhi and Matula proposed a new algorithm for maximum concurrent flow problem (MCFP) in 1990 [6], whose algorithm was improved by Garg and Konemann in 1998 [8]. Garg and Konemann simplified the ideas of Young and built a framework for computing the MCFP. After that, Fleischer realized that an approximation of which commodity has the shortest path could be made in finding a shortest path between the source-sink pairs and extended the framework in 2000 [9]. She was able to describe an algorithm and its running time is independent of the number of the commodity in the MCFP problem. We will use a modified version of Fleischer’s algorithm to consider the problem.

In this paper, we first extend the TEG to put up the model of a small satellite topology. Our model builds on the framework proposed by Liu and Sheng [3]. Then we apply a polynomial time multi-commodity optimization algorithm to maximize the network throughput based on this graph model. Simulation results highlight the practicality of our algorithm and explore the detail of our algorithm on parameter and running time etc.

2 System Model and Optimal Algorithm

2.1 System Setup

We consider a Graph G, which represents a small satellite network (SSN). There are nodes $SN\, = \,\left\{ {s_{1} ,\,s_{2} ,\, \ldots ,\,s_{n} ,\, \ldots } \right\}$ and $TN\, = \,\left\{ {t_{1} ,\,t_{2} ,\, \ldots ,\,t_{n} ,\, \ldots } \right\}$ representing the source and destination of data and a number of missions $OM\, = \,\left\{ {om_{1} ,\,om_{2} ,\, \ldots ,\,om_{n} ,\, \ldots } \right\}$ to be completed over these nodes, where $om_{i} \, = \,\left[ {s_{i} ,\,t_{i} ,\,d_{i} } \right]$. Mission $om_{i}$ comprises source nodes which connects observable object $ob_{i}$, destination nodes which connects data processing center $dc_{i}$ and its demand $d_{i}$.

First we set our demands for each mission $om_{i}$. Small satellites which revolve around the earth at a low altitude of 350–1400 km acquire mission data when they moving into the coverage of the observable objects and the ground stations get the mission data via relay satellites or the small satellites directly in SSN. Then, the mission data is transmitted from the ground stations to the data processing center (DPC). As the small satellite can send mission data to a relay satellite or ground station only when it moves close to them due to the orbiting movements, the connectivity relationships between relay satellites (or ground stations) and small satellites are time varying. On the other hand, relay satellites locate on the geosynchronous orbit. That is, the connectivity relationships between relay satellites and ground stations are fixed.

The SSN consists:

• Source of data $SN\, = \,\left\{ {s_{1} ,\,s_{2} ,\, \ldots ,\,s_{n} ,\, \ldots } \right\}$.

• Observable objects $OB\, = \,\left\{ {ob_{1} ,\,ob_{2} ,\, \ldots ,\,ob_{n} ,\, \ldots } \right\}$.

• Small satellites $SS\, = \,\left\{ {ss_{1} ,\,ss_{2} ,\, \ldots ,\,ss_{n} ,\, \ldots } \right\}$.

• Relay satellites denoted by $RS\, = \,\left\{ {rs_{1} ,\,rs_{2} ,\, \ldots ,\,rs_{n} ,\, \ldots } \right\}$.

• Ground stations $GS\, = \,\left\{ {gs_{1} ,\,gs_{2} ,\, \ldots ,\,gs_{n} ,\, \ldots } \right\}$.

• A data processing center, denoted by $dc$.

• Destination of data $TN\, = \,\left\{ {t_{1} ,\,t_{2} ,\, \ldots ,\,t_{n} ,\, \ldots } \right\}$.

During each slot, the network topology of SSN is constant. But during slot transitions it could change instantaneously. We use TEG to capture the impact of satellites’ orbiting movements on data acquisition. We divide the plan horizon $\left[ {0,\,T} \right)$ into K slots with duration of $\tau \, = \,T/k$.

The TEG, denoted by $G\, = \,(V,\,E)$, is shown in Fig. 1. Here, $G\, = \,(V,\,E)$, is a directed graph that corresponds to a network topology with $K$ slots. The vertices of $G$ represent the copy of source nodes, destination nodes, small satellites, observable objects, ground stations, relay satellites and data process centers for each slot. That is $V\, = \,V_{s} \cup V_{ob} \cup V_{ss} \cup V_{gs} \cup V_{rs} \cup V_{dc} \cup V_{T}$.

Fig. 1.

An example of extending TEG to network model

Graph $G$ have five kinds of arcs: artificial arcs for $SN$ and $TN$, data collection arcs, data storage arcs, fixed link arcs and opportunistic link arcs. We use the artificial arcs to accumulate the total transmission data and set the data rate of such links infinity, $C\left( {dc_{j}^{k} ,\,t_{i} } \right)\, = \,\infty$, $C\left( {s_{i} ,\,ob_{j}^{k} } \right)\, = \,\infty$. The data collection arcs represent capability of small satellites gathering mission data from observable objects, $E_{dc} \, = \,\left( {ob_{i}^{k} ,\,ss_{j}^{k} } \right)$ and their capability equals the rate of mission data that small satellite $ss_{j}$ can collect from observable object $ob_{i}$ in the $k_{th}$ slot,

$$ C\left( {ob_{i}^{k} ,\,ss_{j}^{k} } \right)\, = \,r_{dc} $$

(1)

where $r_{dc}$ is the data collection rate of small satellites. The data storage arcs correspond to the capability of satellites, stations and data process centers to store data, which is defined as $E_{s} \, = \,\left\{ {\left( {v_{i}^{k} ,\,v_{i}^{k + 1} } \right)\left| {v_{i}^{k} \in } \right.V_{ss} \cup V_{rs} \cup V_{gs} \cup V_{dc} ,\,1\, \le \,k\, \le \,K\, - \,1} \right\}$. We set the capacity of data storage arc $\left( {ss_{i}^{k} ,\,ss_{i}^{k + 1} } \right)$ infinity, $C\left( {ss_{i}^{k} ,\,ss_{i}^{k + 1} } \right)\, = \,\infty$. Arcs $E_{fl} \, = \,\left\{ {\left( {rs_{i}^{k} ,\,gs_{i}^{k} } \right)\left| {1\, \le \,i\, \le \,RS,\,1\, \le \,k\, \le \,K} \right.} \right\} \cup \left\{ {\left( {gs_{i}^{k} ,\,dc^{k} } \right)\left| {1\, \le \,i\, \le \,GS,\,1\, \le \,k\, \le \,K} \right.} \right\}$ are fixed and link arcs denoted by $E_{ol} \, = \,\left\{ {\left( {ss_{i}^{k} ,\,vs_{j}^{k} } \right)\left| {ss_{i}^{k} \in V_{ss} ,\,vs_{j}^{k} \in V_{rs} \cup V_{gs} ,\,1\, \le \,k\, \le \,K} \right.} \right\}$ are opportunistic. Their capacity is the rate that mission data is able to be sent by the link,

$$ C\left( {vt_{i}^{k} ,\,vr_{j}^{k} } \right)\, = \,r\left( {vt_{i} ,\,vr_{j} } \right) $$

(2)

where $r\left( {vt_{i} ,\,vr_{j} } \right)$ is the data rate of link $\left( {vt_{i} ,\,vr_{j} } \right)$. Because high speed wired links connect the data process centers and ground stations, we can assume the data transmission rate of them are enough mass, that is $CD\left( {gs_{i}^{k} ,\,dc^{k} } \right)\, = \,\infty$.

2.2 Multi-commodity Algorithm

As according to transformation before, the impact of network dynamics on delivery process can be modeled mathematically using the extended TEG as Fig. 2. And the problem of routing optimization of small satellite network has been corresponding to a topic on a directed graph $G\, = \,(V,\,E)$ with $k$ pairs of demands $(s_{j} ,\,t_{j} )\,\,1\, \le \,j\, \le \,k$ and the capacities of the edges are denoted by $u:\,E \to R$ which is equivalent to multi-commodity flow problem (MCP).

Fig. 2.

Graph corresponding to the extended TEG in Fig. 1

For the MCP which concludes k source-sink demand pairs $(s_{j} ,\,t_{j} )$, as we use the rates to present the capacity of the edges, routing optimization of small satellite networks based on TEG come to a maximum concurrent flow problem (MCFP). The MCFP is a multi-commodity flow problem and all pairs of demands concurrently flow. For MCFP, the target is to assign flow to global route so that the ratio (termed the throughput) of the flow contributed between a pair equals to all pairs of demands. This assignment must not exceed the capacities of all the edges. Each commodity corresponds to a specified demand $d_{j} \left( {1\, \le \,j\, \le \,k} \right)$ in MCFP. Finding a flow that maximizes ratio of demands is our purpose. Letting $x(P)$ denote the quantity of the flow on path P, MCFP can be formulated as:

$$ \begin{array}{*{20}l} {\mathop {\hbox{max} }\limits_{s.t. \, } \quad \,\,\sum\limits_{P:e \in P}^{\lambda } {x(P) \le \, u(e)\quad \forall e} } \hfill \\ {\quad \quad \quad \sum\limits_{{P \in P_{j} }} {x(P) \ge \, \lambda d_{j} \quad \,\,\,\forall j} } \hfill \\ {\quad \quad \quad x(P) \ge 0\quad \quad \quad \quad \forall P} \hfill \\ \end{array} $$

(3)

Polynomial solution for this problem can be found by using Linear Programming. To make the solution faster, we use a modified version of a different approximation algorithm from Fleischer [9].

Letting $l(e)\, = \,\delta /u(e),$ $z_{j} \, = \,\min_{{P \in P_{j} }} l(P)$, $x\, \equiv \,0$ at first. The entire procedure is in phases and there are k iterations in each phase. The goal is routing $d_{j}$ units flow from $s_{j}$ to $t_{j}$ in iteration j in steps. We apply the Dijkstra’s shortest path algorithm with the length function and computes the shortest path P from $s_{j}$ to $t_{j}$ in iteration j. The minimum of the remaining demand and the bottleneck capacity of this path will be transmitted on P. Then the length $l(e)$ renews and we set $z_{j}$ the current minimum length of the path from $s_{j}$ to $t_{j}$. The algorithm stops until the function value $D(l)$ is upper than one, that is $\sum\nolimits_{e} {u(e)l(e)\, > \,1}$. A summary of the algorithm in Fig. 3, where we update the $l(e)$ by $1\, + \,\varepsilon \frac{u}{u(e)}$ and set $\delta \, = \,\left( {\frac{m}{1\, - \,\varepsilon }} \right)^{ - 1/\varepsilon }$.

Fig. 3.

Algorithm for MCFP

The algorithm required no more than $2k\,\log \,m(\log \,k\, + \,\frac{1}{{\varepsilon^{2} }})$ iterations and the total time required by the $\varepsilon$-approximate solution is in $O^{*} (\varepsilon^{ - 2} m(k\, + \,m))$ time. If $D(l)\, > \, = \,1$, then it will be sure that we can obtain at least $(1\, - \,3\varepsilon )$ times of the optimal solution by scaling the final flow by $\log_{1 + \varepsilon } 1/\delta$.

3 Simulations

As the scale of small satellite network is not large, we define three scenarios of small satellites network to explore the influence of topologies and after extending TEG, there are respectively twenty-two, twenty-five and twenty-eight nodes in the graph. We assume that the capacities of all edges in the graph are twenty, except the infinity edges defined before and we set several source-sink demand pairs corresponding to specific demands. To investigate the effect of different algorithms, we choose a general method called augmented path maximum flow algorithm that is using single commodity max-flow algorithm for each source-sink demand pairs in sequence and augmenting the residual network graph every time after the single commodity max-flow is implemented. Then we will compare our MCFP algorithm with the augmented path maximum flow algorithm.

Results of the two algorithms are shown in the Figs. 4 and 5. The augmented path maximum flow algorithm is able to obtain the maximum throughput between single source-sink nodes, it cannot collaboratively optimize the maximum flow path traffic for multiple source-sink node pairs and the optimization of routing performance cannot be achieved. With different node numbers and different source-sink node pair requests, the small satellite network throughput of our method based on TEG model is obviously larger than that obtained by using the augmented path maximum flow algorithm. Furthermore, comparing the results of two source-sink demand pairs and four source-sink demand pairs, the difference between the two algorithms is more obvious with four source-sink demands. We can see that the more complicated the topology is as well as the more demands it has, MCFP algorithm will have better effects than general solution.

Fig. 4.

Results of MCFP algorithm and augmented path maximum flow algorithm (k = 2)

Fig. 5.

Results of MCFP algorithm and augmented path maximum flow algorithm (k = 4)

Both Fig. 6 and Table 1 show the details for the algorithm to solve the TEG graph of a satellite network with 22 vertices and 36 edges.

Fig. 6.

Throughput vs. $\varepsilon$ with 20 nodes (k = 4)

Table 1. The change of $\varepsilon$

To explore the dependency on $\varepsilon$, we use the algorithm to solve a flow network of small satellite where the optimal throughout (OPT) is 9.9. OPT is marked as the gray horizontal line at the top in Fig. 6 and the closer to OPT $\varepsilon$ is, the better results we get. The figure also shows the $(1\, - \,3\varepsilon )$ approximation guarantee of the solution. The guarantee says that the algorithm will produce a flow F such that $(1\, - \,3\varepsilon )OPT\, \le \,F\, \le \,OPT$, where F is the size of the flow. This guarantee means that the algorithm will produce a flow that its throughput is extremely close to OPT, in another word, is above the guarantee line, and under the OPT line.

The values of $\varepsilon$, iterations, running time and throughput can be found in Table 1. To look in detail, as the number of $\varepsilon$ decreases, the algorithm needs more iterations and time to get the solution and the final throughput will be more optimal. From another point of view, if the network changes fast and requires making decision quickly and in time, choosing a reasonable $\varepsilon$ to achieve the balance of the running time and the accuracy is a wise choice.

4 Conclusion

We apply the traditional time-expanded graph to model the data acquisition of small satellite network and use an approximation method to accelerate the solution for MCFP and make global optimization of routing between satellite network nodes. The quantitative comparison between our MCFP algorithm and general augmented path maximum flow algorithm proves the algorithm achieving better throughput and being closer to the optimal solution. Exploring the detail of the algorithm, we conclude that we need to make a reasonable selection of parameter in our algorithm for satellite network nodes communication to achieve the balance of the running time and the accuracy.