A Novel Dynamic Multi-source Multi-sink Flow Algorithm over the Satellite Networks

Abstract

The multi-source multi-sink maximum flow problem can be of great significance in guiding network optimization, service scheduling, and capacity analysis. With intermittent connectivity and time-dependence characteristics of satellite networks, the existing flow algorithms for multi-source multi-sink without temporal dimension involvement can no longer maintain high efficiency in satellite networks. To overcome the problem, we propose a novel dynamic multi-source multi-sink flow algorithm. Specially, the storage time-aggregated graph (STAG) is adopted to depict the time-varying properties of satellite networks. Then, a novel dynamic multi-source multi-sink flow (DMMF) algorithm is proposed to enhance the satellite networks’ resource utilization. At last, the simulation is conducted, and the results with obvious network performance gain verifies our proposed DMMF algorithm.

Supported by organization x.

1 Introduction

The multi-source multi-sink maximum flow problem can effectively represent the maximum transmission ability of networks and assign data flow, and has great guiding value in network optimization, capacity analysis and service scheduling [2]. However, with the time-varying topology and no persistent paths for source-destination nodes in satellite networks [3], it will be more difficult to find efficient dynamic multi-source multi-sink flow in satellite networks with temporal-dimension involved. As shown in Fig. 1, without precise description of time-varying satellite network resources (i.e. transmission resources, storage resources), static-graph based maximum flow algorithm can no longer keep efficient [1, 4, 5]. To be more specific, with the network topology shown in Fig. 1 and $\{\{\mathbb {S},\mathbb {D}\},\{\mathbb {A},\mathbb {B}\}\}$ being the two source-sink node pairs, the maximum flow calculated by the static-graph based algorithm [4] for $\{\mathbb {S},\mathbb {D}\}$ is 3 and for $\{\mathbb {A},\mathbb {B}\}$ is 0. In fact, with storage resources involved and considerate analysis of the relationship between the two flows, the maximum flow for $\{\mathbb {S},\mathbb {D}\},\{\mathbb {A},\mathbb {B}\}$ can be 3 respectively.

Fig. 1.

A simple illustration of satellite network topology within 3 time intervals

Hence, we will propose a novel dynamic multi-source multi-sink algorithms for satellite networks to enhance the transmission capacity of satellite networks. First, the storage time aggregated graph based on our previous work [7] is adopted to depict the network topology of satellite networks with temporal-dimension involvement. Then the feasibilities of flows with different source-node pairs are carefully considered and the special constraints are derived. Then based on the dynamic two-commodity maximum combined flow in our previous work [9], we propose the heuristic novel DMMF algorithm, which can effectively increase the network transmission ability among different source-sink node pairs compared with the existing algorithms. For completeness and clearness, one virtual satellite network with time-vary topology is constructed, and the performance of our proposed DMMF algorithm is verified by comparing with other flow assignment algorithms.

2 Satellite Networks Model

With the trajectories of satellites predictable, the communication windows among satellites could be precisely obtained. Based on the predictable feature and reasonable assumptions, we adopted storage-time aggregated graph [7] to model the time-varying resources (i.e. satellites’ storage resources, communication windows, data transmission capacity of links) of satellite networks.

Specifically, given time horizon $T=[t_0,t_n]$, and the specific satellites which the satellite networks consist of, the communication windows between satellites can be predicted from STK. With the communication time windows among satellites obtained and reasonable assumptions, the undirected STAG = $\{T,\mathcal {V},\mathcal {E},\mathcal {C}_{u,v}(T),\mathcal {N}_{v}(T), \mathcal {S}_\mathcal {V}|u\in \mathcal {V},v\in \mathcal {V},(u,v)\in \mathcal {E} \}$ is assorted to model the satellite networks:

• $T=[t_0, t_n]$, a time horizon of the satellite networks, which is not the life time of satellite networks. We split $[t_0,t_n]$ into n small time intervals $\{\tau _1,...,\tau _p,...,\tau _n\}$, where $\tau _p = (t_{p-1},t_{p}]$ and during each small time interval $\tau$, the topology of the satellite network is fixed.

• $\mathcal {V}$, the set of the nodes (satellites).

• $\mathcal {E}$, the set of undirected edges, where $(u,v) \in \mathcal {E}$ holds if and only if the contact time window between satellite u and v during T is nonzero.

• $\mathcal {C}_{u,v}(T) = \{c_{u,v}(\tau _1),...,c_{u,v}(\tau _p),...,c_{u,v}(\tau _n)\}$, is a capacity time series set for each link $(u,v) \in \mathcal {E}$, where $c_{u,v}(\tau _p) = \int _{t_{p-1}}^{t_p}{w_{u,v}(t)}dt$, and $w_{u,v}(t)$ depict the link capacity of edge (u, v) at time instant t. Note that even if links of satellite works are not directional, flows themselves are directional.

• $\mathcal {N}_{v}(T) = \{N_{v}(\tau _1,\tau _2),...,N_{v}(\tau _p,\tau _{p+1}),...,N_{v}(\tau _{n-1,n}) \}$, a node storage time series set, where $N_{v}(\tau _p,\tau _{p+1})$ records the storage resources utilization of each node $v \in \mathcal {V}$ from $\tau _{p}$ to $\tau _{p+1}$. And the storage resources correspond to maximum amount of data one node can store from one small time interval to the adjacent one.

• $\mathcal {S}_\mathcal {V}$, a storage resource set, where the storage resources of each satellite $v \in \mathcal {V}$ at time instant $t_0$ is denoted as $s_{v}$.

To be more explicit, one simple satellite network (S, D, B, A) within 3 time intervals is depicted by undirected STAG shown in Fig. 2 as further illustration.

Fig. 2.

Satellite network modeled by undirected STAG within 3 time intervals

3 Feasible Multi-source Multi-sink Flow Definitions in STAG

Unlike the static flow definitions with the links’ directed capacity determined and just considered in networks with fixed topology, there are some remarkable differences here for the feasible and dynamic multi-source multi-sink flow in the undirected STAG = $\{T,\mathcal {V},\mathcal {E},\mathcal {C}_{u,v}(T),\mathcal {N}_{v}(T), \mathcal {S}_\mathcal {V}|u\in \mathcal {V},v\in \mathcal {V},(u,v)\in \mathcal {E} \}$ without loops and parallel edges. With $\{{\mathbb {S}_k,\mathbb {D}_k}\}$ being the $k_{th}$ source-sink node pair, then the flow of the $k_{th}$ source-sink node pair from u to v within T can be noted as:

$$\begin{aligned} f_{u,v}^{k}(T) = \sum _{q=1}^{n}{f_{u,v}^{k}(\tau _q)}, \end{aligned}$$

(1)

where $f_{u,v}^{k}(\tau _q)$ means the flow of $k_{th}$ source-sink nodes from u to v within $\tau _q$.

Then with the h source-sink nodes given as $\{(\mathbb {S}_1,\mathbb {D}_1),...,(\mathbb {S}_k,\mathbb {D}_k),...,(\mathbb {S}_h, \mathbb {D}_h)\}$, the total flow of the h source-sink nodes is:

$$\begin{aligned} sum = F_{\mathbb {S}_1,\mathbb {D}_1}^{1} (T)+ ... + F_{\mathbb {S}_k,\mathbb {D}_k}^{k}(T) + ... + F_{\mathbb {S}_h,\mathbb {D}_h}^{h}(T), \end{aligned}$$

(2)

where the total flow of the $k_{th}$ source-sink nodes is:

$$\begin{aligned} F_{\mathbb {S}_k,\mathbb {D}_k}^{k}(T) = \sum _{v \in \mathbb {V}}{f_{\mathbb {S}_k,v}^{k}(T)} - \sum _{v \in \mathbb {V}}{f_{v,\mathbb {S}_k}^{k}(T)}. \end{aligned}$$

(3)

With the definitions given above, the specific constraints for h source-sink node pairs in the undirected STAG should be satisfied as follows:

Capacity Constraints: Note that the speciality of the undirected graph is that flow assignment of each source-sink node pairs between two nodes can only be single directed. To be more explicit:

$$\begin{aligned} |f_{u,v}^{k}(\tau _p)| \times |f_{v,u}^{k}(\tau _p)| = 0, \forall p \in [1,n], \forall k\in [1,h], \end{aligned}$$

(4)

where the flow assignment $f_{u,v}^{k}(\tau _p)$ and $f_{v,u}^{k}(\tau _p)$ should be non-negative. And with the direction rule of each source-sink flow assignment, in undirected STAG:

$$\begin{aligned} 0 \le \sum _{k=1}^{h}{f_{u,v}^k(\tau _{p})} + \sum _{k=1}^{h}{f_{v,u}^k(\tau _p)} \le c_{u,v}^{\tau _p}, \forall p \in [1,n]. \end{aligned}$$

(5)

Node Storage Transfer Constraints: For $k_{th}$ source-sink determined flow ($\forall k \in [1,h]$), within $\tau _1$:

$$\begin{aligned} {{ \sum _{v \in \mathcal {V}}{f_{v,u}^{k}(\tau _1)} } - { \sum _{v \in \mathcal {V}}{f_{u,v}^{k}(\tau _1)} }} = N_{u}^{k}(\tau _1,\tau _2). \end{aligned}$$

(6)

Naturally, during the next time intervals $\forall p \in [2,n-1]$:

$$\begin{aligned} {{ \sum _{v \in \mathcal {V}}{f_{v,u}^{k}(\tau _p)} }+ N_{u}^{k}(\tau _{p-1},\tau _p) - { \sum _{v \in \mathcal {V}}{f_{u,v}^{k}(\tau _p)} }} = N_{u}^{k}(\tau _p,\tau _{p+1}). \end{aligned}$$

(7)

With simple mathematical operations, the storage transfer constraints within T can be easily obtained as:

(8)

Storage Resource Constraints: And with the constraints of each source-sink flow satisfied, there exists the following storage resource constraints:

$$\begin{aligned} \left\{ \begin{aligned}&{0 \le N_{v}^{k}(\tau _p,\tau _{p+1})\le s_{v}, \forall k \in [1,h], \forall p \in [1,n-1]}.\\&{0 \le \sum _{k=1}^{h}{N_{v}^{k}(\tau _p,\tau _{p+1})} \le s_{v}, \forall p \in [1,n-1]}. \end{aligned} \right. \end{aligned}$$

(9)

Flow Conservation: Then for each source-sink node pair determined flow, there exits the following flow conservation:

$$\begin{aligned} \sum _{v \in \mathcal {V}}{f_{u,v}^{k}(T)} - \sum _{v \in \mathcal {V}}{f_{v,u}^{k}(T)} = \left\{ \begin{aligned}&{F_{\mathbb {S}_k,\mathbb {D}_k}^{k}(T), u = \mathbb {S}_k},\\&{0, u \ne \mathbb {S}_k,\mathbb {D}_k},\\&{-F_{\mathbb {S}_k,\mathbb {D}_k}^{k}(T), u = \mathbb {D}_k}. \end{aligned} \right. \end{aligned}$$

(10)

With the above constraints for feasible DMMF in undirected STAG, it’s more complicated to obtain a rather-efficient feasible DMMF in undirected STAG compared with the static graph. Mechanical re-conduct of time-varying maximum flow solution can result in severe network resources waste.

4 Heuristic Multi-source Multi-sink Flow Algorithm

The multi-commodity flow algorithm is a NP-hard problem and has been proved in [6], and it will be more difficult to solve in the disruption tolerant satellite networks. To enhance the transmission ability in satellite networks, we have solved the dynamic maximum single-commodity [7, 8], two-commodity flow problem [9] in our previous works. To overcome the problem of efficient dynamic multi-source multi-sink flow assignment problem, a heuristic DMMF algorithm is proposed based on the efficiency of the maximum dynamic two-commodity flow, which can be shown in Algorithm 1.

With respect to the dynamic two-commodity maximum flow DCF algorithm, adopted in the same undirected STAG and with extra storage resource constraints involvement, the DCF algorithm can be perfectly transformed here to solve the efficient DMMF assignment problem as following. For completeness and clarity, the maximum dynamic two-commodity algorithm is presented as Algorithm 2. And the detailed construct, perform and adjust process and the corresponding proving process in Algorithm 2 can be found in our previous work [9].

The overall solution for efficient DMMF flow algorithm is to recursively decompose multi-source multi-sink flow problem into logically dynamic two-commodity maximum flow problem.

Fig. 3.

(a) Topology of the virtual constructed network. (b) Flow assignment of the priority-based single commodity maximum flow algorithm. (c) Flow assignment of our DMMF.

5 Simulation

To further verify the performance of our proposed dynamic multi-source multi-sink flow assignment algorithm, we consider one virtual satellite network with 12 satellites and 3 source-sink node pairs during an hour, and the length of each small time interval $\tau$ is set as 20 min, which can be seen from Fig. 3(a). Note that the network is virtual and constructed based on the time-varying characteristics. As shown in Fig. 3(b), the trivial solution for multi-source multi-sink flow problem is to repeat applying the STAG-based temporal single-commodity algorithm, and the flow result is 8 and there is no flow for the third commodity (X, Y). And with our two-commodity based DMMF algorithm, the flow assignment can increase to 12, and the flow assignment for (X, Y) is also 4, which can be explained as our algorithm involved the coupling relationship between different source-sink node pairs. To be more explicit, the link and node resources are assigned jointly among multi source-sink nodes.

6 Conclusion

In this paper, we propose a STAG-based DMMF for satellite networks to efficiently assign the network flow and increase resource utilization. We construct one effective algorithm of multi-source multi-sink flow assignment, which is based on the efficiency of the undirected STAG and the dynamic maximum two-commodity flow algorithms. With the feasibility of flow assignment carefully considered, we decompose the multi-source multi-sink flow assignment problem into maximum dynamic two-commodity flow problem over the time-varying satellite networks.