Towards a throughput-optimal routing algorithm for data collection on satellite networks

Abstract

To perform Earth observation, more and more satellites are equipped with high-resolution sensors like hyperspectral imagers, which generate data at tens of Gbps. Researchers aim to maximize the volume of data available for use on the ground in near-real time. To achieve this goal, many solutions have recently been proposed to perform data collection through satellite networks. Most of these solutions have so far been focusing on either source rate control and load balancing, or heuristic routing. However, optimizing routing together with resources allocation is critical for improving delivery performance. In this paper, we challenge the fact that transmission paths have to be built under high link variability with limited resources, and develop a throughput-optimal solution based on the utility maximization framework. For delay performance, we embed a distance factor into the objective of the framework and derive a geographic-location-aware backpressure algorithm. Further, we exploit transmission opportunities missed by backpressure-type algorithms to accelerate data transfer. The simulation results show that our algorithms are able to deliver large volumes of data in time, and scale well in all scenarios tested.

Keywords

Satellite networks data collection throughput optimality routing algorithm backpressure

Introduction

With technological advances of on-board scientific instruments, there has been a boom in the volume of data collected by satellites¹. In particular, hyperspectral imagers or synthetic aperture radars on earth observation satellites generate data at tens of Gbps². Traditionally, a source satellite has had to carry imagery or sensor data until the availability of a direct ink to a ground station, which takes tens of minutes. In order to make this volume of data available for use on the ground in near real time, a satellite network is required to forward the data. Typically, the network comprises a number of Low Earth Orbit (LEO) satellites, which include the source nodes, and Geostationary Earth Orbit (GEO) satellites (see Figure 1). With the existence of Inter-Satellite Links (ISLs), it is possible to find at least one route for any source to a ground sink.

Figure 1.

A network for data collection consists of a Geostationary Earth Orbit (GEO) satellite and Low Earth Orbit (LEO) satellites connected via ISLs. The GEO satellite can relay data from LEO satellites to the ground station.

This satellite network is expected to serve a variety of data collection missions (e.g. disaster surveillance, weather forecast) that demand high throughput and reasonable end-to-end delays. However, while this network increases connectivity, it does not necessarily yield desirable delivery performance. There are several factors that affect the performance. First, multiple sources are generating traffic simultaneously, which imposes a great demand on the network. Second, transmission paths have to be built under high link variability with limited nodal power. Consequently, a path’s throughput is easily deteriorated by emerging bottlenecks during transmission, since link capacities vary as nodes move. Third, due to the incompatible input and output rates, some nodes’ buffers occasionally suffer overload, which might induce packet loss. In particular, the traffic pattern of many-to-one or many-to-several data collection makes nodes near to the sink liable to congestion. In light of these factors, one can design a routing algorithm that dynamically adjusts paths based on link capacities and enhances it with a load-balanced scheme^3,4. But according to our empirical results⁵, this type of solution breaks the internal connection between path selection and node resources (e.g power, buffer), which deflates the network throughput region. Therefore, optimization of routing together with resource allocation is critical for improving delivery performance.

In this paper, we are interested in the design of routing algorithms on satellite networks that achieve long-term throughput optimality as well as desirable end-to-end delays. We formulate the throughput objective in terms of the mean flow rates provided to the data collection. For end-to-end delays, we introduce a cost function that describes the total amount of resources used by all flows in the network. Specifically, we add up weighed traffic loads on all links, of which the weight measures the distance of the next hop to the destination. In this way, end-to-end delays can be tightly regulated. Our goal is to optimize the objectives under resources constraints. Basically, we consider three types of resources: links, power, and queues. During transmission, the existence of a link is constrained by the network connectivity, and its capacity is decided by the transmitting power, which obeys a nodal power limit. Meanwhile, all queues’ lengths should be bounded for network stability. Then, we solve this optimization problem by exploring three arguments: exogenous arrival load, link transmitting load, and link transmitting power, and derive our algorithms that connect path selection and resource allocation. Compared with the well-known backpressure-type technique^6,7, our algorithms manage to achieve a balance that preserves throughput optimality with reasonable end-to-end delay characteristics. Our contributions are summed as follows.

We develop a utility maximization framework that seamlessly embeds a distance factor, which supports general metrics (e.g. hop, geographic distance, link weight). This framework decouples routing decision from link variability by allocating power dynamically for activated links.

We propose a geographic-location-aware backpressure algorithm derived from the framework for satellite networks. This solution not only maintains the long-term optimality of backpressure policy, but also brings down loops and unnecessary exploring of routes to a great extent.

We further define and exploit transmission opportunities missed by the backpressure-type algorithm. In order to seize these opportunities, we adaptively modify backpressure (backlog differential) according to the trend of a neighbor’s backlog change. This enables us to pump packets faster to the sink direction. Also, a related loop reduction scheme is introduced considering local minima.

Finally, we develop a simulation platform and demonstrate that traditional backpressure algorithms fail to meet the requirement of data collection on satellite networks. Our algorithms are able to deliver packets in time, and scale well in all scenarios tested. We also show that there is a tradeoff between power consumption and end-to-end delays on the selection of the GEO relaying.

The rest of the paper is organized as follows. In Section ‘Related work’, we briefly review related works. Section ‘System model’ introduces our system model for the hybrid satellite network. We propose our framework and derive the geographic (geographic-location-aware) backpressure algorithm in Section ‘Throughput-optimal and delay-aware cross-layer algorithm’. Then in Section ‘Opportunistic transmission beyond backpressure’, we upgrade our solution by reducing transmission opportunities missed. The evaluations in different scenarios are conducted on our simulation platform in Section ‘Evaluation’. The conclusion is given in the final section.

Related work

Maximize throughput for satellite networks

There has been a long-standing interest^8–10 in maximizing data transfer for satellite networks. Most work focuses on the design of constellation parameters^11,12 and advocates the utilization of ISLs^13,14. For the remainder, there are efforts on developing routing and scheduling algorithms^8,9,15 for maximizing throughput. These proposals are either heuristic attempts or evaluated only in simplified simulation scenarios. None of them backtrack to a concrete theoretical framework. Also, we notice that a group of work^3,4,16 enhances routing algorithms for satellite networks with load balancing schemes. Their throughput performance relies on passive route adjustment to congestion or traffic prediction. Moreover, the idealized traffic distribution and topology assumptions limit the algorithm scalability. Besides, there are routing algorithms^17,18 designed for the above hybrid satellite network. Regardless of throughput performance, few consider to decouple link variability from routing decisions for better responsiveness to traffic load. Therefore, these drawbacks motivate us to seek an alternative approach grounded in network throughput optimization theory.

Backpressure algorithm

The backpressure algorithm, also known as ‘MaxWeight’, has brought theoretical prosperity^6,7 for backpressure-based stochastic optimization. The improvement of its framework is still continuing¹⁹. Basically, it uses the maximum backlog differentials as link weights. With a maximum-weight matching, it can schedule and route any input traffic within the network capacity region stably²⁰. It provably maximizes throughput, which can be derived by either Lyapunov drift⁶ or Lagrange duality²¹.

However, poor performance in delivery rate and end-to-end delay is the Achilles’ heel of the backpressure-type algorithms, due to loops or extensive exploring of routes. To restrict detours, researchers^6,21,22 incorporate the shortest path concept into the traditional backpressure algorithm. Enhanced backpressure routing is proposed by Neely⁶ via a shortest path bias, which is used in a heuristic manner. In Ying, Shakkottai, Reddy et al.²², the routing problem is formulated by minimizing the average number of hops between sources and destinations. Accordingly, the queue structure on each node is expanded for hop information. Though its delay improvement is significant, in a dynamic topology it has to frequently reconstruct queues based on the updates of the employed shortest path algorithm. Similarly, in Bui, Srikant and Stolyar²¹, a shorter path is preferred by minimizing total link rate. Its routing decision is affected by backlog differential minus a threshold. But the selection of the threshold is non-trivial especially in a dynamic network. To address the loop problem, in Xiong, Li, Eryilmaz et al.²³, the authors define the running average net rate of commodity traffic traversing a link, and restrict network topology by eliminating links with zero net rate. In this way, route construction is loop-free. But unnecessary detours still exist.

Essentially, the backpressure algorithm requires gradients to pump flows. When input traffic is low or packets spread out in the network, flows easily get stuck due to low gradients. Thus, several algorithms are proposed to maintain the gradients for flows, in order to reduce delays. In Moeller, Sridharan, Krishnamachari et al.²⁰, Backpressure Collection Protocol (BCP) uses finite queues and drops packets when a queue is full. Then the discards are placed into the corresponding underlying virtual queue so as to keep the gradient. Cooperating with the Last-In-First-Out (LIFO) queue policy, the later packets are sent over the existing gradient. The utility-delay tradeoff analysis of LIFO backpressure is given in Huang, Moeller, Neely et al.²⁴. In Athanasopoulou, Bui, Ji et al.²⁵, shadow queues are proposed to activate links in decoupled routing and scheduling. To maintain gradients, the arrival rate of a shadow queue is enlarged by a certain coefficient of the actual rate. However, from our experimental results, we find that those transforms of gradients are not flexible enough in a dynamic network.

Besides, under the Network Utility Maximum (NUM) framework, authors try to directly incorporate end-to-end delays into either the constraints or the objective^26,27, which are approximately calculated based on queue theory. However, it cannot effectively capture delay characteristics when routes overlap. In Li and Eryilmaz²⁸, the deadline constraint per packet is considered, which again changes the queuing discipline. We notice that there is recent work^29–31 closer to ours. In Hu, Yuanan, Dongming et al.²⁹, for satellite networks, utility optimal scheduling is proposed. In Jiao, Tian, Zhang et al.³⁰, to improve delay and energy efficiency, GRAdient-assisted energy-efficient backPrEssure (GRAPE) uses the hop distance to the sink as the gradient, and combines it with nodes’ residual energy. Also, the combination of geographic and backpressure routing is explicitly proposed in Núñez-Martínez, Baranda and Mangues-Bafalluy³¹. However, the differences are that we focus on the dynamics of satellite networks and provide a general theoretical framework based on NUM. The location-aware-backpressure routing is a natural outcome from the framework. Moreover, none of above work exploits the transmission chances missed by the backpressure-type algorithm.

System model

Consider a multihop satellite network comprising one GEO, multiple LEO nodes, and one ground station (sink). A GEO node can connect to the sink anytime and concurrently support E $(E > 0)$ LEO nodes accessing. We assume that LEO nodes move in polar orbits, in which the satellite’s mean visibility time per orbit revolution is at a maximum. A LEO node has its downlink only as it overflies the sink. With ISLs, a LEO node can forward data to its neighbors (GEO or LEO). We consider the scenarios where there always exists at least one route to the sink for each LEO node. The collection mission requires timely and complete delivery of a large amount of data to the sink.

Assume that time is slotted and a satellite’s position is fixed within a slot. Define the network topology at slot t as a directed graph $(N, L)$ , where $N$ and ℒ are node set and link set respectively. Let $< i, j >$ denote the directed link from node i to j, where $< i, j > \in L$ and $i, j \in N$ .

Connectivity constraint and link length

Let $α$ be the angular of the LEO orbit sector, in which communication between a LEO node i and the GEO node g is possible. Then, we have the LEO–GEO connectivity constraint

\sum_{i \underset{β \leq \frac{α}{2}}{\in N}} I_{{< i, g > \in ℒ}} \leq E

(1)

where I is the indication function, $β$ is the angular formed by node i and node g in the center of the earth. $β$ is calculated as

β = \arccos (\cos θ \cos ϕ \cos (φ - ψ) + \sin θ \sin ϕ)

where $(θ, φ)$ and $(ϕ, ψ)$ give the latitude and longitude of node i and those of node g, respectively. As node i moves, the length $L_{ig}$ of link $< i, g >$ varies as

L_{i g} = {[H_{LEO}^{2} + H_{GEO}^{2} - 2 H_{LEO} H_{GEO} \cos β]}^{1 / 2}

where $H_{LEO}$ and $H_{GEO}$ are the distances of LEO and GEO to the earth center, respectively. Likewise, the connectivity constraint and length for link LEO-sink can be obtained in the same way, which is skipped here.

For ISLs between LEO nodes, assume that a LEO node only contacts its immediate neighbors if any: intra-orbit and inter-orbit neighbors. The lengths of the two types of ISLs are

L_{i j} = {\begin{matrix} H_{LEO} {[2 - 2 \cos (\frac{2 π \cdot orbit_num}{LEO_num})]}^{1 / 2}, intra - orbit \\ H_{LEO} {[2 - 2 \cos (\frac{π}{LEO_num})]}^{1 / 2} \cos θ, inter - orbit \end{matrix}

where $LEO_num$ represents the number of LEO nodes and $orbit_num$ is the number of the orbits. Note that the length of an intra-orbit link is constant while that of an inter-orbit link is a function of the node’s latitude $θ$ .

Power constraint and link capacity

The total power of node i is $P_{i}^{tot}$ . The assigned transmitting power for $< i, j >$ is $P_{ij} [t]$ at slot t, which follows

\begin{array}{l} \sum_{j : 〈 i, j 〉 \in ℒ} P_{i j} [t] \leq P_{i}^{tot} \\ P_{i j} [t] \geq 0 \end{array}

(2)

Let $P [t] = (P_{ij} [t {])}_{i, j}$ denote the vector of assigned powers. Assume that ISLs are orthogonalized. The channel condition of a link is mainly decided by free-space path loss $η_{ij}$ over $L_{ij}$

η_{i j} = {[χ / (4 π L_{i j})]}^{2}

where $χ$ denotes the wavelength. Then, we have the aggregated gain of the link $< i, j >$

γ_{i j} = \frac{G \cdot ξ \cdot η_{i j}}{V}

where G models spreading/beamforming gain, $ξ$ models the SNR-gap that reflects a particular modulation and coding scheme, and V is background noise power. Thus, the transmission rate of link $< i, j >$ is upper-bounded by link capacity

c_{ij} = B \cdot \log (γ_{ij} \cdot P_{ij} [t] + 1)

(3)

where B is base-band bandwidth. Considering link capacity, the network can be also defined as $(N, L, c)$ , where $c = (c_{ij})_{i, j}$ .

Traffic model and flow constraint

Source traffic

At the beginning of slot t, for node i, there are $X_{i}^{d} [t]$ exogenous packets that are injected and destined for d ( $d \in N$ ). Assume that $X_{i}^{d} [t]$ is a stationary ergodic stochastic process and satisfies

\begin{matrix} 0 \leq X_{i}^{d} [t] \leq X_{max} \\ X_{i}^{i} [t] = 0 \end{matrix}

(4)

The vector of exogenous arrival numbers is denoted as $X [t]$ . The corresponding packet arrival rate is denoted by $x_{i}^{d} = lim_{t \to \infty} 1 / t \sum_{τ = 0}^{t} E (X_{i}^{d} [τ])$ . We then have the vector of exogenous arrival rates as $x = (x_{i}^{d})_{i, d}$ .

Traffic over a link

At slot t the number of transmitted packets over link $< i, j >$ for destination d is given as $R_{ij}^{d} [t]$ , determined by routing policy. It satisfies

\begin{matrix} \sum_{d} R_{ij}^{d} [t] \leq c_{ij} \\ 0 \leq R_{ij}^{d} [t] \leq R_{max} \end{matrix}

(5)

The vector of $R_{ij}^{d} [t]$ is $R [t]$ . We also assume that $R_{ij}^{d} [t]$ is a stationary ergodic stochastic process and the link rate for d is defined as $r_{ij}^{d} = lim_{t \to \infty} 1 / t \sum_{τ = 0}^{t} E (R_{ij}^{d} [τ])$ . Let $r = (r_{ij}^{d})_{i, j, d}$ denote the vector of all rates.

Then, the flow conservation constraint is given as

\sum_{j : < i, j > \in L} r_{ij}^{d} - \sum_{n : < n, i > \in L} r_{ni}^{d} - x_{i}^{d} \geq 0

(6)

Objective

Given above constraints, we aim to develop a cross-layer solution that controls $(X [t], R [t], P [t])$ to maximize network throughput and provide a high delivery rate and low end-to-end delays. The throughput is measured by $x_{s}^{d}$ for source–destination pair $(s, d)$ . We reuse the objective of NUM as a part of ours

\max \sum_{d, s} U_{s d} (x_{s}^{d})

(7)

where $U_{sd} (x_{s}^{d})$ is the utility function associated with $(s, d)$ and is assumed to be strictly concave, non-decreasing and continuously differentiable on $[0, X_{\max}]$ .

For the other two metrics, we assign undelivered packets (e.g. trapped in loop) with high end-to-end delay penalties, and focus on the minimization of end-to-end delays. Note that it is not feasible to formulate the end-to-end delay as a function of the arrival and service processes for a large-scale multi-hop network²³. Thus, we utilize link rate $r_{ij}^{d}$ that regulates the end-to-end delay for d to form the remainder of the objective

max - \sum_{d, < i, j > \in L} C_{jd} (r_{ij}^{d})

(8)

where $C_{jd} (r_{ij}^{d})$ is the cost function of selecting j as the next hop for d with rate $r_{ij}^{d}$ . In Bui, Srikant and Stolyar²¹, $C_{jd} (r_{ij}^{d}) = r_{ij}^{d}$ , which is not tight enough to reduce end-to-end delays. Next we will introduce our framework with a novel delay-aware cost function.

Throughput-optimal and delay-aware cross-layer algorithm

In this section, we first propose our throughput-optimal and delay-aware framework, combing utility maximization and cost minimization. Then, we decompose our original problem into rate control, routing, and power allocation. Accordingly, we develop a cross-layer solution for satellite networks, which maintains the throughput optimality and has desirable delay performance.

Throughput-optimal and delay-aware framework

Cost function

In order to regulate end-to-end delays in a tight fashion, we define $C_{jd} (r_{ij}^{d})$ as

C_{jd} (r_{ij}^{d}) ≜ r_{ij}^{d} \cdot D_{i} (‖ ρ_{d} - ρ_{j} ‖)

(9)

where $ρ_{d}$ and $ρ_{j}$ are the position vectors of node d and node j respectively, $‖ ρ_{d} - ρ_{j} ‖$ gives the distance between two nodes, and $D_{i} (\cdot)$ is a non-negative and non-decreasing function. The distance calculation depends on how the position vector is defined. For example, the vector may have one dimension and contain the current minimum hop count to the sink. To simplify the notation, we substitute $D_{i} (‖ ρ_{d} - ρ_{j} ‖)$ with $D_{ij}^{d}$

D_{ij}^{d} \geq 0

(10)

The intuition behind the cost function is that, while the link rate is a resource cost of the transmission, the distance to the sink is deemed as a delay cost after the transmission. Because, if defined properly, the distance usually indicates how long packets will linger in the network. For example, in a static network, the minimum hop count estimates the duration monotonously. But, in a dynamic network, the hop count easily becomes invalid as the topology changes. Thus, we will discuss the distance definition for satellite networks in the algorithm.

4.1.2 Problem formulation

Under the constraints given in the system model, we control the triple $(X [t], R [t], P [t])$ to achieve the objective combining equations (7) and (8).

\begin{array}{l} \max_{{X [t], R [t], P [t]}} \sum_{d, s \in N} U_{s d} (x_{s}^{d}) - \sum_{d \in N, < i, j > \in ℒ} r_{i j}^{d} \cdot D_{i j}^{d} \\ s . t . equations (1) to (6) and (10) \end{array}

(11)

Let ${X^{*} [t], R^{*} [t], P^{*} [t]}$ denote the set of optimal solutions to equation (11), and define $x^{*} = lim_{t \to \infty} \frac{1}{t} \sum_{τ = 0}^{t} (X^{*} [τ])$ and $r^{*} = lim_{t \to \infty} \frac{1}{t} \sum_{τ = 0}^{t} (R^{*} [τ])$ . Note that $x^{*}$ is unique due to the assumption of $U_{sd} (x_{s}^{d})$ , while $r^{*}$ belongs to a set of optimal link rates. Since there is no interference, each node independently decides $P^{*} [t]$ after its routing. Thus, we temporarily continue without $P [t]$ , which will not affect the optimal solution.

Cross-layer decomposition

To solve problem (11), we assign a Lagrange multiplier $q_{i}^{d}$ $(q_{i}^{d} \geq 0)$ for each constraint in (6). Then, we can obtain a partial Lagrange dual objective function $PD (q)$ about the vector of the multipliers q .

\begin{matrix} PD (q) = & max_{{X [t], R [t]}} \sum_{d, s} U_{sd} (x_{s}^{d}) - \sum_{d, < i, j > \in L} r_{ij}^{d} \cdot D_{ij}^{d} \\ + \sum_{d, i} q_{i}^{d} (\sum_{j : < i, j > \in L} r_{ij}^{d} - \sum_{n : < n, i > \in L} r_{ni}^{d} - x_{i}^{d}) \\ = & max_{{X [t], R [t]}} \sum_{s, d} (U_{sd} (x_{s}^{d}) - q_{s}^{d} x_{s}^{d}) \\ + \sum_{d, < i, j > \in L} r_{ij}^{d} (q_{i}^{d} - q_{j}^{d} - D_{ij}^{d}) \\ s . t . equations (1) to (5) and (10) \end{matrix}

(12)

We can take $q_{i}^{d}$ as the implicit cost at node i for destination node d. Then, the dual problem becomes

min_{q \geq 0} PD (q)

(13)

Because $PD (q)$ is convex, we can solve equation (13) by using the subgradient method

\begin{matrix} \begin{matrix} q_{i}^{d} [t + 1] = {q_{i}^{d} [t] - \frac{1}{K} \frac{\partial PD}{\partial q_{i}^{d}}}^{+} \\ = {q_{i}^{d} [t] - \frac{1}{K} [\sum_{j : < i, j > \in L} r_{ij}^{d} [t] - \sum_{n : < n, i > \in L} r_{ni}^{d} [t] - x_{i}^{d} [t]]}^{+} \end{matrix} \end{matrix}

(14)

where $1 / K$ is a positive step size, $r_{ij}^{d} [t] = R_{ij}^{d} [t]$ and $x_{i}^{d} [t] = X_{i}^{d} [t]$ . According to Slater’s condition, there exist $(q, X^{*} [t], R^{*} [t])$ such that $(X^{*} [t], R^{*} [t])$ is the optimal solution to the original problem in equation (11). Then, given $q_{s}^{d}$ , we can decompose the original problem into a rate control problem

\begin{array}{l} P 1 : \max_{{X [t]}} \sum_{s, d} (U_{s d} (x_{s}^{d}) - q_{s}^{d} x_{s}^{d}) \\ s . t . equation (4) \end{array}

(15)

and a routing problem

\begin{array}{l} P 2 : \max_{{R [t]}} \sum_{d, < i, j > \in ℒ} r_{i j}^{d} (q_{i}^{d} - q_{j}^{d} - D_{i j}^{d}) \\ s . t . equations (1), (5), and (10) \end{array}

(16)

At each iteration of equation (14), by solving equations (15) and (16), we can obtain the joint corresponding rate control and routing policy.

Given the link capacity in equation (3), $R [t]$ in the objective in equation (11) is determined by the power allocation $P [t]$ . Then, the problem in equation (16) becomes an independent standard concave maximization problem for each node i

\begin{array}{l} P 3 : \max_{{P [t]}} \sum_{d, j : < i, j > \in ℒ} \log (γ_{i j} \cdot P_{i j} [t] + 1) \cdot (q_{i}^{d^{*}} - q_{j}^{d^{*}} - D_{i j}^{d^{*}}) \\ s . t . equation (2) \end{array}

(17)

where $d^{*}$ is decided by the routing policy.

Cross-layer control policy

The cross-layer control policy is the solution to the problems decomposed above, and provides a guideline of designing the corresponding algorithm. Assume that each node maintains a queue for each destination d and its length at time slot t is denoted by $Q_{i}^{d} [t]$ . Each queue evolves as

\begin{matrix} Q_{i}^{d} [t + 1] = \\ {Q_{i}^{d} [t] - [\sum_{j : < i, j > \in L} R_{ij}^{d} [t] - \sum_{n : < n, i > \in L} R_{ni}^{d} [t] - X_{i}^{d} [t]]}^{+} \end{matrix}

(18)

From equations (14) and (18), we know that $Q_{i}^{d} [t] = K \cdot q_{i}^{d} [t]$ .

The policy needs to guarantee the network stability, which means the queue length for any destination inside a node must be finite

lim su p_{t \to \infty} \frac{1}{t} \sum_{τ = 0}^{t} E (Q_{i}^{d} [τ]) < \infty, \forall i, d \in N

4.3.1 Rate control

For the problem in equation (15), based on the queue length for destination d, we control the flow injection from source node s as²³

E (X_{s}^{d} [t] | Q_{s}^{d} [t]) = min {U_{sd}^{' - 1} (Q_{s}^{d} [t] / K), X_{max}}

(19)

The rate for a destination is decided by the queue length of the destination at source nodes, which controls input load within the network capacity.

Routing

For the problem in equation (16), its solution resembles the traditional backpressure algorithm and the difference is the selection of candidate queues for transmission. At slot t, from its set $N_{i}$ $(N_{i} \subset N)$ of contactable neighbors and the destination set $C_{i}$ $(C_{i} \subset N)$ , node i selects neighbor $j^{*}$ ( $j^{*} \in N_{i}$ ) as the next hop of data from queue $Q_{i}^{d^{*}} [t]$ ( $d^{*} \in C_{i}$ )

\begin{matrix} (d^{*}, j^{*}) = \arg max_{d, j} q_{i}^{d} [t] - q_{j}^{d} [t] - D_{ij}^{d} \\ = \arg max_{d, j} Q_{i}^{d} [t] - Q_{j}^{d} [t] - K \cdot D_{ij}^{d} \end{matrix}

(20)

Then, for multiple destinations and contactable neighbors, we repeat the above selection from $N_{i} \ {j^{*}}$ and $C_{i} \ {d^{*}}$ until either becomes the null set. The corresponding weight of link $< i, j^{*} >$ is defined as

w_{i j^{*}} [t] = max {Q_{i}^{d^{*}} [t] - Q_{j^{*}}^{d^{*}} [t] - K \cdot D_{i j^{*}}^{d^{*}}, 0}

(21)

and the transmitting rate of link $< i, j^{*} >$ is

R_{i j^{*}}^{d^{*}} [t] = {\begin{matrix} c_{i j^{*}}, if w_{i j^{*}} [t] > 0 \\ 0, otherwise \end{matrix}

(22)

Power allocation

We first transform the problem in equation (17) into

min \sum_{j : < i, j > \in L} - w_{ij} [t] \cdot \ln (P_{ij} [t] + 1 / γ_{ij})

(23)

and assign Lagrange multipliers $ν_{i}$ and $λ_{j}$ associated with the two inequalities in constraint equation (2). Then, the Lagrange function is

\begin{matrix} L (P [t], λ, ν) & = \sum_{j : < i, j > \in L} - w_{ij} [t] \cdot \ln (γ_{ij} \cdot P_{ij} [t] + 1) \\ - \sum_{j : < i, j > \in L} λ_{j} \cdot P_{ij} [t] \\ + ν \cdot (\sum_{j : < i, j > \in L} P_{ij} [t] - P_{i}^{tot}) \end{matrix}

Because the problem in equation (23) satisfies Slater’s condition, Karush–Kuhn–Tucker conditions give

\begin{matrix} P^{*} [t] \geq 0, 1^{T} P^{*} [t] = P_{i}^{tot}, λ_{j}^{*} P_{ij}^{*} [t] = 0 \\ \frac{\partial L (P^{*} [t], λ^{*}, ν^{*})}{\partial P^{*} [t]} = 0 \end{matrix}

From the above gradient equation, we can derive

λ_{j}^{*} = ν^{*} - \frac{w_{ij} [t]}{1 / γ_{ij} + P_{ij}^{*} [t]}

By eliminating the slack variable $λ_{j}^{*}$ and discussing the range of $ν^{*}$ , we have

P_{ij}^{*} [t] = max {0, \frac{w_{ij} [t]}{ν^{*}} - \frac{1}{γ_{ij}}}

Then, we solve $\sum_{j} max {0, \frac{w_{ij} [t]}{ν^{*}} - 1 / γ_{ij}} = P_{i}^{tot}$ by using the water-filling approach. The solution is found as follows

P_{ij}^{*} [t] = {\begin{matrix} \frac{w_{ij} [t] \cdot (P_{i}^{tot} + \sum_{k : w_{ik} [t] > 0} 1 / γ_{ik})}{\sum_{k : w_{ik} [t] > 0} w_{ik} [t]} - \frac{1}{γ_{ij}}, & w_{ij} [t] > 0 \\ 0, & w_{ij} [t] = 0 \end{matrix}

(24)

From equation (24), we can see that the power of each link is assigned according to link weight and channel state.

Geographic backpressure algorithm

We present our algorithm based on above cross-layer control policy.

Basic procedure

Briefly, each node controls its exogenous input at the transport layer according to equation (19), in which we choose $\log (x_{s}^{d})$ as utility functions. Then, at the network layer, each node makes a one-to-one match between a destination and one of its neighbors, using equation (20) until no more selection. For the link layer, the link is activated according to equation (22) and is assigned with full link capacity, which is further decided by the power allocation in equation (24).

Geographic backpressure

Differently from the traditional backpressure algorithm, we introduce a distance factor as a cost in equation (9) into the backlog differential calculation. In Athanasopoulou, Bui, Ji et al.²⁵, an M-backpressure algorithm is proposed based on the maximum differential backlog minus parameter M, forcing flows to shorter routes. Although M looks similar as $K \cdot D_{ij}^{d}$ in equation (20), it only serves a constant threshold without differentiating neighbors. For example, if a node has two neighbors with the same differential backlogs but different distances to the sink, the M-backpressure algorithm may choose the unpromising one with longer distance.

Nevertheless, $K \cdot D_{ij}^{d}$ gives a chance to bring routing metrics (e.g. hop, geographic distance, link weight) into the backpressure routing decision. For the satellite network, we prefer the geographic information for its responsiveness to the dynamics. Note that $K \cdot D_{ij}^{d}$ serves as a dynamic threshold. If the value is large, it would induce unnecessary delays under light traffic loads. Moreover, if absolute distances used, it is unfair for packets towards farther destinations.

Algorithm 1: Geographic Backpressure.
Input: For node i, at slot t, { $Q_{i}^{d} [t - 1], Q_{j}^{d} [t - 1]$ , $ρ_{d}, ρ_{j}, P_{i}^{tot}$ $}_{j, d}$ , $j \in N_{i}$ , $d \in C_{i}$
Output: ${X_{i} [t], R_{i} [t], P_{i} [t]}$
1 Calculate $X_{i}^{d} [t]$ using equation (19)
2 Update the ranks of neighbors’ distances using equation (25)
3 while $N_{i} \neq \emptyset$ and $C_{i} \neq \emptyset$ do
4 Match $d^{}$ to $j^{}$ using equation (20)
5 $N_{i} \ {j^{}}$ , $C_{i} \ {d^{}}$
6 end
7 Activate links with positive weights using equation (22)
8 Allocate power $P_{i} [t]$ using equation (24)
9 Set the link rate $R_{i} [t]$
10 return ${X_{i} [t], R_{i} [t], P_{i} [t]}$
11 Update and distribute $Q_{i}^{d} [t]$ and $ρ_{i}$ to neighbors

In fact, to select the next hop, a node only compares values within its current neighbor set. Therefore, instead of absolute distances, we use the relative rank of neighbors’ distances

D_{i} (‖ ρ_{d} - ρ_{j} ‖) \overset{Δ}{=} \underset{j \in N_{i}}{rank} (‖ ρ_{d} - ρ_{j} ‖) - 1

(25)

where $rank (\cdot)$ gives the rank of distance $‖ ρ_{d} - ρ_{j} ‖$ in the neighbor set $N_{i}$ sorted in ascending order. We minus one to start the rank from zero, considering the principle of positive backpressure link activation. With the same backpressure, the rank of distances guarantees that the link weight of a neighbor nearer to the destination is larger than those of farther neighbors. This effectively restricts the spread of packets. The details of the above procedure are given in Algorithm 1.

Theorem 1. Geographic backpressure algorithm stabilizes the network $(N, L, c)$ , if there exists any solution ${X [t], R [t], P [t]}$ that stabilizes the network $(N, L, c - ε)$ , $\forall ε ≻ 0$ .

Proof. See Appendix 1.

Remark: The improvement of delay performance demands compensation from network capacity. In the theorem, it reflects on $ε$ . However, it does not change the throughput optimality of the proposed algorithm.

Opportunistic transmission beyond backpressure

In this section, based on the geographic backpressure algorithm, we further exploit transmission opportunities missed by backpressure-type algorithms. First, we employ three examples to motivate the utilization of missed transmission chances. Then, we design a scheme to recognize these opportunities and accordingly enhance our proposed algorithm. In addition, a related loop reduction scheme is introduced considering local minima.

Motivation

First, consider the last hop in the network. Traditional backpressure algorithms, even at the direct neighbor of a sink, do not guarantee forwarding packets straight to the destination. In our scenario, the sink node is a ground station. Recall that the last hop in our scenario could be a downlink with limited duration. Hence, it is expensive to have packets lingering around a sink. In order to push packets faster, neighbor i ( $i \in N_{d}$ ) should keep a higher backpressure towards the sink d. Simply, it can be realized by assigning a constant negative backlog (i.e. $q_{d}^{d} < 0$ ) to the sink, which avoids possible detour in the case when $q_{j}^{d} = 0$ $(j \in N_{i}, j \neq d)$ . Note that our distance bias can also prevent this last-hop problem.

However, taking a closer check on other hops, we find that the distance bias is not always effective to push packets. We demonstrate this problem in Figure 2. At the beginning slot t, three packets are injected at node 2 heading for sink S. The capacity of each link is one packet per slot. For the geographic backpressure algorithm, let $K = 2$ and $D_{ij}^{d} \in {0, 1}$ . The distance bias successfully keeps packets moving in the right direction, with five slots to finish transmission. For the traditional backpressure algorithm, it takes at least six slots, and most likely packets would be trapped in loops. However, as marked out by a dashed square, we intend to show that there is a transmission opportunity missed by our algorithm, which can further reduce delivery delays. This opportunity is based the observation that packet c could replace packet b without increasing the backlog of node 1. This indicates that it could benefit transmission to jump out of the principle of positive backpressure link activation, as long as backlogs are stable. Nevertheless, the question is how node 2 can recognize such an opportunity.

Figure 2.

An example of the geographic backpressure algorithm ( $K = 2$ , $D_{ij}^{d} \in {0, 1}$ ) on a line network. At the beginning of slot t, there are three packets at node 2, heading for sink node S. Each link can only transmit one packet each slot.

Before answering the question, we give another example to show the necessity of seizing the opportunity. As shown in Figure 3, node 2 and node 3 are sources that are relayed by node 1 (e.g. GEO node) to the sink with a high-capacity link, which is common in our scenario. Because the aggregated rate of link 2-1 and link 3-1 does not exceed that of link 1-S. Ideally, sources can transmit at their full rates. But from the resulting table on the right, it not only confirms the existence of missed chances, but also reveals unfairness to the low-rate source (i.e. node 3). That means a low-rate source is more likely to miss opportunities, and its delay would grow significantly as the number of flows (partly) sharing its path increases. However, if node 3 takes missed chances, its backlog can stabilize sooner than node 2, say from slot 4. Therefore, it is important to devise a scheme to capture the underutilized capacity beyond positive backpressure.

Figure 3.

An example of transmission opportunities missed by backpressure-type algorithms. Node 2 and node 3 are injected at 2 packets/slot and 1 packets/slot, respectively. The capacities of link 2-1, link 3-1 and link 1-S are 2 packets/slot, 1 packets/slot, and 3 packets/slot, respectively. The table on the right gives the backlog changes of three nodes in the first eight slots.

Opportunity-aware scheme

To answer the question, we first define a slot set with missed transmission opportunities. For node i, its corresponding slot set is given as

\begin{matrix} O_{i} = {t | Q_{i}^{d} [t] > 0 \\ Q_{i}^{d} [t] - Q_{j}^{d} [t] \leq 0 \\ \sum_{m} R_{jk}^{m} [t + 1] + min {c_{ij}, Q_{i}^{d} [t]} \leq c_{jk} \\ D_{ij}^{d} = D_{jk}^{d} = 0 \\ \forall d, \exists j \in N_{i}, \exists k \in N_{j}} \end{matrix}

(26)

Basically, it describes that at slot $t + 1$ there exists a neighbor j of node i, which has enough remaining transmission capacity, though node i does not transfer its packets due to non-positive backpressure at slot t. Also we constrain neighbors by $D_{ij}^{d} = D_{jk}^{d} = 0$ to avoid detour. In the example of Figure 2, we have $O_{2} = {t + 2}$ , while $O_{2} = {2}$ and $O_{3} = {2, 4, 6}$ in Figure 3. From the third condition of the definition, in order to take the chance at slot t, node i has to be notified about the exact remaining capacity of its neighbor j in next slot. However, it is unlikely to achieve that at an acceptable cost.

In above examples, we can see that they all have a fluent downstream in common. The fluency results from either nearby sink nodes or high-capacity links. As shown in the first example, a negative backlog can be seen as a credit to a sink node, which eliminates lingering packages. Similarly, we should give credits to those nodes that can forward packets quickly. Let $σ_{i}^{d} [t]$ denote the assigned credit of node i for destination d at slot t. If $σ_{i}^{d} [t] < 0$ , it indicates that node i would have remaining capacity with high probability. Then, we use the credit to affect the link activation. The weight calculation in equation (21) becomes

w_{ij} [t] = max {Q_{i}^{d} [t] - Q_{j}^{d} [t] - K \cdot D_{ij}^{d} - σ_{j}^{d} [t], 0}

(27)

Consequently, even if the backlog difference is zero, a negative $σ_{i}^{d} [t]$ could help to active those links, as expected in the examples above. However, similarly to $K \cdot D_{j}^{d}$ , $σ_{i}^{d} [t]$ should not dominate the equation, so that the network stability can still hold. Thus, it is critical to design a proper way to update the value. Intuitively, $σ_{i}^{d} [t]$ is closely related to the trend of backlog change. If the trend goes down, $σ_{i}^{d} [t]$ should be less than zero; otherwise, $σ_{i}^{d} [t] \geq 0$ . For node i, its most recent and handy backlog change is $Δ Q_{i}^{d} [t] = Q_{i}^{d} [t] - Q_{i}^{d} [t - 1]$ . Usually $Δ Q_{i}^{d} [t]$ goes up and down alternately around zero due to the behavior of backpressure-type algorithms. It does not reflect the trend. Hence, we use an exponential filter to update $σ_{i}^{d} [t]$

σ_{i}^{d} [t] = δ_{1} \cdot σ_{i}^{d} [t - 1] + δ_{2} \cdot Δ Q_{i}^{d} [t]

(28)

where $δ_{1} + δ_{2} = 1$ and $δ_{1} > δ_{2}$ . If not specifically mentioned, $δ_{1} = 0.9$ and $δ_{1} = 0.1$ . Also, we optimistically set $σ_{i}^{d} [0] = - c_{ij}$ , where j satisfies $D_{ij}^{d} = 0$ , so that each node initially has credits to transmit. In the example of Figure 2, $σ_{1}^{s} [t] = - 1$ and then at slot $t + 2$ we have link weight $w_{21} [t + 2] = 0.72$ . Thus, link 2-1 is activated so that only four slots are required to finish the transmission. Meanwhile, for the example in Figure 3, this approach can increase the total throughput by 25%, from 16 packets to 20 packets within eight slots as shown in Figure 4.

Figure 4.

First eight slots by using assigned credit for link activation. The total throughput is increased by 25% from 16 packets to 20 packets.

Implementation Node i updates its own $σ_{i}^{d} [t]$ for each d locally. Each slot, despite actual backlogs $Q_{i}^{d} [t]$ , every node advertises $σ_{i}^{d} [t]$ . The reason that we do not just advertise $Q_{i}^{d} [t] + σ_{i}^{d} [t]$ is that $σ_{i}^{d} [t]$ might not get involved in the weight calculation due to the fourth condition in equation (26). They need their receivers, node i’s neighbor j, to make a decision according to $K \cdot D_{ji}^{d}$ .

Loop reduction scheme

Distance bias can effectively avoid unnecessary detours, thus potentially cutting down loops. However, in a dynamic network, there could be special cases such as isolation and local minima. Also, concerning multiple random sources, it is possible that a neighbor node could send back packets just transferred by the current node, due to their backpressure variation. Therefore, loops still exist and hinder further improvement on delays. Note that loops are also waste of resource in our scenario since links between satellites are limited and expensive (e.g. pointing and adjusting).

However, we are not going to design a sophisticated method to eliminate loops. Rather, we prefer to use a simple mechanism to lower the impact of loops to an acceptable extent. Through experiments we find most loops are between two neighbors. To reduce such one-hop loops, we record the node ID of the last hop, say node i, in the packet header. Its neighbor node j receives packets from node i for sink d. Instead of completely forbidding transferring back, in case of local minima, we adjust the link weight towards node i according to $σ_{i}^{d} [t]$ .

Implementation Let us continue with the case that j receives packets from i. If $σ_{i}^{d} [t] < 0$ , node j sets $σ_{i}^{d} [t] = | Δ Q_{i}^{d} [t] |$ before weight calculation. Our intuition is that it is less easy to activate a link towards a last-hop neighbor if the neighbor keeps the backlog value of last slot. If $σ_{i}^{d} [t] \geq 0$ , then $Q_{i}^{d} [t]$ is most likely to be larger than $Q_{i}^{d} [t - 1]$ . But if $σ_{i}^{d} [t] < 0$ , then $Q_{i}^{d} [t]$ is decreasing. Thus node j needs to virtually increase $Q_{i}^{d} [t]$ by adding absolute change $| Δ Q_{i}^{d} [t] |$ so that $Q_{i}^{d} [t] \geq Q_{i}^{d} [t - 1]$ . Because $Q_{i}^{d} [t - 1] > Q_{j}^{d} [t - 1]$ , if no other packets towards d are injected, we will have $Q_{i}^{d} [t] \geq Q_{j}^{d} [t]$ . Then, link j–i will not be activated. Also, the distance bias curbs sending back to neighbors with $D_{ji}^{d} > 0$ .

These two schemes only need incremental change based on Algorithm 1. We refer to enhanced Algorithm 1 as ‘Geographic Backpressure Plus’.

Evaluation

To validate the feasibility of the proposed algorithms for data collection on satellite networks, we conduct three groups of simulations on the ns-2 network simulator. We mainly examine the delivery rate, end-to-end delay, and energy consumption of the algorithms. We use a hybrid constellation mentioned and corresponding parameters are listed in Table 1. The LEO constellation uses polar orbits, in which there are no ISLs across the seam. A LEO node can communicate with the GEO node with an elevation larger than 15°. The GEO satellite can relay at most 20 LEO nodes simultaneously through ISLs. We adjust the locations of the GEO node and the ground sink node to ensure the existence of a direct link between them. Nodes periodically send probes to detect and maintain neighbors. All links are orthogonalized. Link capacity c depends on power allocation and link length. Also, the link error rate is zero.

Table 1.

Hybrid constellation parameters

Parameters	GEO	LEO
Altitude	35800 km	780 km
Orbit type	Equator	Polar
Inclination	0°	86°
Orbit number	1	8
Satellite number	1	64
Max ISL number	20	5

We select 10 LEO satellites as source nodes. Half source nodes need to send packets across the seam. Similarly to Chen, Liu and Hu³², source traffic follows an i.i.d. two-state Markov-modulated Poisson process MMPP-2 $(0.01, 0.01, λ_{1}, λ_{2})$ , where $λ_{1} = 2 λ_{2}$ , and the average rate is $1.5 λ_{2}$ ; packet size is 1 KB. Let $Λ = 1.5 λ_{2} / c$ , $Λ \in [0.1, 1]$ . We vary $Λ$ to control traffic load in the simulation. Each node’s buffer is large enough that, except for intentionally discarded packets, there is no packet loss due to buffer overflow. Each simulation has 500 slots and is repeated independently 50 times with a 96% confidence interval.

Without ISLs to the GEO node

We first consider a scenario without GEO relaying, which increases the difficulty of routing. We compare our algorithms with other algorithms: traditional backpressure (Traditional BP), float-queue-based backpressure (i.e. BCP), and pure geographic (Geographic). Specifically, the threshold of buffer size for BCP is 10 KB. We use the terms Geographic BP and Geographic BP Plus to represent the two algorithms proposed, respectively. Each node runs one of these algorithms to make a routing decision at the beginning of a slot.

Delivery rate is an important test to apply a backpressure-type algorithm on satellite networks. A low delivery rate could lead to a failure of recovering a sensor image. It is considered a waste for such resource-limited networks. From Figure 5a we observe that distance bias is able to maintain 100% delivery rate, though Geographic BP is a little bit lower. This is because Geographic BP does not prevent one-hop loops, and a small number of packets is trapped due to non-positive backpressure. Nevertheless, Geographic BP’s delivery rates are steadily higher than those of Traditional BP and BCP. Without distance bias, neither of them can completely deliver all packets. Their delivery rates drop as traffic load gets lighter.

Figure 5.

Delivery rate, average number of hops, average end-to-end delay, Cumulative Density Function (CDF) of end-to-end delays of traditional backpressure, Backpressure Collection Protocol (BCP), pure geographic, geographic backpressure, and geographic backpressure plus, as traffic load varies.

Then, we examine the average number of hops and average end-to-end delay of delivered packets. The former metric reflects how diversely a backpressure-type algorithm chooses a path, compared with the path formed by Geographic routing, which has the lowest average number of hops, as expected. In Figure 5b, the values of Geographic BP and Geographic BP Plus both raise marginally from Geographic routing, while those of Traditional BP and BCP are much higher and increase as traffic load decreases.

However, in view of queuing delay, fewer hops do not necessarily mean a better end-to-end performance. Therefore, the latter metric depicts whether the combination of backpressure and geographic routing helps to reduce the delay. In Figure 5c, the trends of Traditional BP and BCP keep consistent with those in Figure 5b, which indicates that the number of hops dominates end-to-end delays. Meanwhile, the significant growth of Geographic routing’s delays, from 12 slots to over 150 slots, proves that the over-utilization of a shorter path does not scale well under high traffic load. In contrast, Geographic BP and Geographic BP Plus both grow slowly but no more than 85 slots. In order to show their difference on delay performance, we give the CDF of end-to-end delays when $Λ = 0.4$ and $Λ = 1.0$ in Figure 5d. Basically, Geographic BP Plus has steeper slope than Geographic BP, which means that Geographic BP Plus has better end-to-end delay performance.

Last, we measure total power consumption as the overhead of each algorithm. From Figure 6, Traditional BP and BCP similarly have the highest power consumption, while Geographic BP and Geographic routing keep the lowest value. Because each slot Geographic BP Plus seizes more transmission opportunities beyond positive-backpressure-activation policy, it has slightly higher power consumption than Geographic BP. But, with the better end-to-end performance, we consider the extra consumption a worthwhile cost.

Figure 6.

Power consumption of traditional backpressure, BCP, pure geographic, geographic backpressure, and geographic backpressure plus as traffic load varies.

To sum up, the traditional backpressure-type routing algorithm and its modified version without distance bias are not suitable for satellite networks. At the same time, the complement approach is necessary to refine the geographic-location-aware backpressure algorithm, in order to improve the end-to-end performance. Next, we further evaluate the proposed algorithms in another two scenarios, which are important for data collection missions.

With ISLs to the GEO node

Generally, the relay of a GEO node can reduce hops and benefit end-to-end delays. But the long ISL distance would increase link cost. Thus, there exists a tradeoff between delay and power consumption for a path to go through GEO or not. The traditional backpressure algorithm only takes a GEO neighbor as a normal candidate, and is unable to dynamically change its rank. Meanwhile, the pure geographic algorithm prefers a GEO node and easily leads to congestion. Still they are not qualified in this scenario. Hence, we only give the comparison of Geographic BP and Geographic BP Plus.

In Figure 7a, it illustrates the end-to-end delays distributions of two algorithms with or without the GEO node when $Λ = 0.4$ and $Λ = 1.0$ . Each box with whiskers describes the minimum value, maximum value, 25th, 50th, and 75th percentile of the values. It is clear that Geographic BP Plus effectively brings down the maximum values up to 43%, compared with Geographic BP. Also, the existence of the GEO node helps to reduce delays for both algorithms. Yet, in Figure 7b, we witness expensive power consumptions for the cases with ISLs to the GEO node. Geographic BP Plus consumes a little more than Geographic BP. Though power conservation is beyond our discussion scope, it is essential to route with energy-awareness, which we will explore in the future work.

Figure 7.

The minimum value, maximum value, 25th, 50th, and 75th percentile of end-to-end delays, and power consumption of geographic backpressure and geographic backpressure plus with or without GEO as traffic load equals 0.4 and 1.0.

Without ISLs among LEO nodes

Finally, we consider a scenario that is the opposite of the first one. ISLs among LEO nodes are removed and four LEO nodes with persistent ISLs to the GEO are selected as source nodes. Hence, packets have to be sent through the GEO node. We plot the end-to-end delay distribution and power consumption in Figure 8a and Figure 8b, respectively. The two algorithms are also compared with or without ISLs among LEO nodes as $Λ = 0.4$ and $Λ = 1.0$ . The results show that Geographic BP Plus keeps its superiority over Geographic BP on end-to-end delays and the difference between their power consumptions is small. Moreover, the existence of ISLs among LEO nodes increases delays for both algorithms. This is because, when traffic load is not heavy, an alternative transmission path, instead of GEO relaying, through multi-hop LEO nodes would raise the delay. Thus, if power consumption is not the major concern, GEO relaying should be encouraged. For Geographic BP Plus, it can achieve this by updating $σ_{i}^{d} [t]$ .

Figure 8.

Conclusion

Data collection on satellite networks is a challenging task that requires compatible throughput and delay performance. In this paper, we model the designing of the data collection algorithm as a cross-layer control optimization problem. It essentially tackles the tradeoff between the two metrics and achieves a balance that maintains throughput optimality with reasonable delay characteristics.

To achieve this, we unify throughput utility and delay cost into the objective. By decomposition, we solve the problem and derive the rate-control, routing, and power allocation policies, which provide provable throughput optimality. Then, we specify the delay cost function and develop our geographic-location-aware backpressure algorithm. Moreover, considering scarcity of link resource, we exploit opportunities missed by backpressure-type algorithm to accelerate transmissions. As a result, the end-to-end delay is regulated in a tight fashion without sacrificing throughput optimality. In future work, we will optimize the energy consumption of special nodes in the network, such as GEO satellites, to extend our power allocation policy.

Footnotes

Proof of Theorem 1

Proof. Because the routing decision is based on the queue lengths, distance, and link states at slot t, the queue evolving ${Q [t]}$ is a Markovian procedure. We define a Lyapunov function of $Q [t]$ as

L (Q [t]) = \sum_{n, d} (Q_{n}^{d} [t {])}^{2}

and the corresponding Lyapunov drift over T slots is

\begin{matrix} E (L (Q [t + T]) - L (Q [t]) | Q [t]) \\ = E (\sum_{n, d} {(Q_{n}^{d} [t + T])}^{2} - {(Q_{n}^{d} [t])}^{2} | Q [t]) \end{matrix}

According to the queue evolution

\begin{matrix} Q_{n}^{d} [t + T] \leq {(Q_{n}^{d} [t] - \sum_{τ = t}^{t + T - 1} \sum_{j : < n, j > \in L} R_{nj}^{d} [τ])}^{+} \\ + \sum_{τ = t}^{t + T - 1} (\sum_{i : < i, n > \in L} R_{in}^{d} [τ] + X_{n}^{d} [τ]) \end{matrix}

Then

\begin{matrix} \begin{matrix} {(Q_{n}^{d} [t + T])}^{2} - {(Q_{n}^{d} [t])}^{2} \\ \leq {(\sum_{τ = t}^{t + T - 1} \sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [τ])}^{2} - 2 Q_{n}^{d} [t] \sum_{τ = t}^{t + T - 1} \sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [τ] \\ + {(\sum_{τ = t}^{t + T - 1} (\sum_{i : 〈 i, n 〉 \in L} R_{in}^{d} [τ] + X_{n}^{d} [τ]))}^{2} \\ + 2 (Q_{n}^{d} [t] - \sum_{τ = t}^{t + T - 1} \sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [τ]) + \\ \cdot (\sum_{τ = t}^{t + T - 1} (\sum_{i : 〈 i, n 〉 \in L} R_{in}^{d} [τ] + X_{n}^{d} [τ]])) \end{matrix} \\ \begin{matrix} \leq {(\sum_{τ = t}^{t + T - 1} \sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [τ]])}^{2} \\ + {(\sum_{τ = t}^{t + T - 1} (\sum_{i : 〈 i, n 〉 \in L} R_{in}^{d} [τ] + X_{n}^{d} [τ]))}^{2} \\ - 2 Q_{n}^{d} [t] \sum_{τ = t}^{t + T - 1} (\sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [τ] - \sum_{i : 〈 i, n 〉 \in L} R_{in}^{d} [τ] - X_{n}^{d} [τ]) \end{matrix} \end{matrix}

Thus

(29)

\begin{matrix} E (L (Q [t + T]) - L (Q [t]) | Q [t]) \\ \leq \sum_{n, d} E ((\sum_{τ = t}^{t + T - 1} \sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [τ {])}^{2} \\ + (\sum_{τ = t}^{t + T - 1} (\sum_{i : 〈 i, n 〉 \in L} R_{in}^{d} [τ] + X_{n}^{d} [τ]))^{2}) \\ - 2 \sum_{n, d} Q_{n}^{d} [t] \cdot E (\sum_{τ = t}^{t + T - 1} (\sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [τ] \\ - \sum_{i : 〈 i, n 〉 \in L} R_{in}^{d} [τ] - X_{n}^{d} [τ]) | Q [t]) \\ \leq Z - 2 \sum_{n, d} Q_{n}^{d} [t] \cdot E (\sum_{τ = t}^{t + T - 1} (\sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [τ] \\ - \sum_{i : 〈 i, n 〉 \in L} R_{in}^{d} [τ] - X_{n}^{d} [τ]) | Q [t]) \end{matrix}

where

\begin{matrix} Z = N^{2} T^{2} {(R_{max}^{in} + R_{max}^{out} + X_{max})}^{2} \\ R_{max}^{out} = max_{n, t} {\sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [t]} \\ R_{max}^{in} = max_{n, t} {\sum_{i : 〈 i, n 〉 \in L} R_{in}^{d} [t]} \end{matrix}

The negative part on the right of equation (29) is

(30)

\begin{matrix} - 2 \sum_{n, d} Q_{n}^{d} [t] \cdot E (\sum_{τ = t}^{t + T - 1} (\sum_{j : 〈 n, j 〉 \in L} R_{nj}^{d} [τ] \\ - \sum_{i : 〈 i, n 〉 \in L} R_{in}^{d} [τ] - X_{n}^{d} [τ]) | Q [t]) \\ = 2 \sum_{τ = t}^{t + T - 1} \sum_{n, d} Q_{n}^{d} [t] \cdot E (X_{n}^{d} [τ] | Q [t]) \\ - 2 \sum_{τ = t}^{t + T - 1} \sum_{〈 i, j 〉 \in L, d} E (R_{ij}^{d} [τ] | Q [t]) \cdot (Q_{i}^{d} [t] - Q_{j}^{d} [t]) \end{matrix}

because there exists a solution ${X [t], R [t], P [t]}$ for the network $(N, L, c - ε)$ . Apparently, this solution can also stabilize the network $(N, L, c)$ . Thus, the solution policy has a drift bound that leads to stability. For network $(N, L, c)$ under geographic backpressure policy, we can compare the negative part of equation (30) with the solution’s.

\begin{matrix} - \sum_{τ = t}^{t + T - 1} \sum_{< i, j > \in L, d} E (R_{ij}^{d} [τ] | Q [t]) \cdot (Q_{i}^{d} [t] - Q_{j}^{d} [t]) \\ \geq - \sum_{τ = t}^{t + T - 1} \sum_{< i, j > \in L, d} c_{ij} \cdot (Q_{i}^{d} [t] - Q_{j}^{d} [t]) \\ \geq - \sum_{τ = t}^{t + T - 1} \sum_{< i, j > \in L, d} c_{ij} \cdot (Q_{i}^{d} [t] - Q_{j}^{d} [t]) \\ - (ε (Q_{i}^{d} [t] - Q_{j}^{d} [t]) - (c_{ij} + ε) D_{ij}^{d}) \\ = - \sum_{τ = t}^{t + T - 1} \sum_{< i, j > \in L, d} (c_{ij} + ε) \cdot (Q_{i}^{d} [t] - Q_{j}^{d} [t] - K \cdot D_{ij}^{d}) \\ = - \sum_{τ = t}^{t + T - 1} \sum_{< i, j > \in L, d} E_{Geographic} (R_{ij}^{d} [τ] | Q [t]) \\ \cdot (Q_{i}^{d} [t] - Q_{j}^{d} [t] - K \cdot D_{ij}^{d}) \\ \geq - \sum_{τ = t}^{t + T - 1} \sum_{< i, j > \in L, d} E_{Geographic} (R_{ij}^{d} [τ] | Q [t]) \\ \cdot (Q_{i}^{d} [t] - Q_{j}^{d} [t]) \end{matrix}

where we let $K \cdot D_{ij}^{d} \leq \frac{ε}{c + ε} (Q_{i}^{d} [t] - Q_{j}^{d} [t]) .$ Hence, the Lyapunov drift under the geographic backpressure policy is more negative than the drift from the given solution that stabilizes the network $(N, L, c)$ . Thus, the drift bound applies to the geographic backpressure policy, which proves the theorem.

Academic Editor: Sangheon Pack

Declaration of conflicting interests

The authors declare that there is no conflict of interest.

Funding

This research is sponsored by the National Science Foundation of China (grant number 91438102) and the National Defense Science and Technique Innovation Foundation of the Chinese Academy of Science (grant number CXJJ-15S128).

References

Greda

Knüpfer

Heckler

. A satellite multibeam antenna for high-rate data relays. In: 32nd ESA workshop on antennas for space applications, Noordwijk, the Netherlands, 5–8 October 2010. Noordwijk, the Netherlands: ESTEC.

Lansing

Lemmerman

Walton

. Needs for communications and onboard processing in the vision era. In: IEEE international geoscience and remote sensing symposium, Toronto Canada, 24–28 June 2002, vol. 1, pp. 375–377. New York, NY: IEEE.

Nishiyama

Tada

Kato

. Toward optimized traffic distribution for efficient network capacity utilization in two-layered satellite networks. IEEE Trans Veh Technol 2013; 62(3): 1303–1313.

Yuan

Chen

Liu

. A load-balanced on-demand routing for LEO satellite networks. J Network 2014; 9(12): 3305–3312.

Chen

Wang

Liu

. Load balanced routing protocol for double-layered satellite networks. J Astronaut 2012; 6: 010.

Neely

MJ.

Dynamic power allocation and routing for satellite and wireless networks with time varying channels. PhD Thesis, Massachusetts Institute of Technology, 2003.

Georgiadis

Neely

Tassiulas

Resource allocation and cross-layer control in wireless networks. Delft, The Netherlands: Now Publishers Inc, 2006.

Sun

Modiano

Routing strategies for maximizing throughput in LEO satellite networks. IEEE J Sel Areas Commun 2004; 22(2): 273–286.

Wang

Sheng

Lui

. Maximum lifetime routing with guaranteed throughput in LEO satellite networks. In: IEEE 26th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC), Hong Kong, 30 August–2 September 2015. New York, NY: IEEE.

10.

Liu

Sheng

Lui

. Capacity analysis of two-layered LEO/MEO satellite networks. In: 81st IEEE vehicular technology conference, Glasgow, Scotland, 11–14 May 2015, pp. 1–5. New York, NY: IEEE.

11.

Johnston

Haslam

Trachtman

. SB-SAT-persistent data communication LEO spacecraft via the Inmarsat-4 GEO constellation. In: Advanced satellite multimedia systems conference and 12th signal processing for space communications workshop, Baiona, Scotland, 11–14 May 2015, pp. 21–28. New York, NY: IEEE.

12.

Katona

Berioli

. Design of circular orbit satellite link for maximum data transfer. In: IEEE international conference on communications, Kyoto, Japan, 5–9 June 2011, pp. 1–6. New York, NY: IEEE.

13.

Lange

Heine

Motzigemba

. Roadmap to wide band optical GEO relay networks. In: Military communications conference, Orlando, Florida, USA, 29 October–1 November 2012, pp. 1–5. New York, NY: IEEE.

14.

Chern

Hong

Chien

. Design and application of inter-satellite link in weather observation constellation. J Mar Sci Technol 2012; 20(4): 472–477.

15.

Lin

Long

. A buffer-limited maximum throughput routing algorithm for satellite network. In: 22nd IEEE international conference on telecommunications, Sydney, Australia, 27–29 April 2015, pp. 378–383. New York, NY: IEEE.

16.

Kawamoto

Nishiyama

Kato

. A delay-based traffic distribution technique for multi-layered satellite networks. In: wireless communications and networking conference, 2012, pp. 2401–2405. IEEE.

17.

Yuan

Wang

. A multicast routing algorithm for GEO/LEO satellite ip networks. In: IEEE 11th International Conference on Dependable, autonomic and secure computing, Chengdu, China, 21–22 December 2013, pp. 595–599. New York, NY: IEEE.

18.

Jin

. A novel routing design in the IP-based GEO/LEO hybrid satellite networks. Int J Satell Commun Networking 2016. DOI: 10.1002/sat.1174.

19.

Supittayapornpong

Neely

MJ.

Achieving utility-delay-reliability tradeoff in stochastic network optimization with finite buffers. In: IEEE conference on computer communications, Kowloon, Hong Kong, 26 April–1 May 2015, pp. 1427–1435. New York, NY: IEEE.

20.

Moeller

Sridharan

Krishnamachari

. Routing without routes: The backpressure collection protocol. In: 9th ACM/IEEE international conference on information processing in sensor networks, Stockholm, Sweden, 12–15 April, 2010, pp. 279–290. New York, NY: ACM.

21.

Bui

Srikant

Stolyar

. Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing. In: IEEE conference on computer communications, Rio de Janeiro, Brazil, 19–25 April 2009, pp. 2936–2940. New York, NY: IEEE.

22.

Ying

Shakkottai

Reddy

. On combining shortest-path and back-pressure routing over multihop wireless networks. IEEE/ACM Trans Networking 2011; 19(3): 841–854.

23.

Xiong

Eryilmaz

. Delay-aware cross-layer design for network utility maximization in multi-hop networks. IEEE J Sel Areas Commun 2011; 29(5): 951–959.

24.

Huang

Moeller

Neely

. LIFO-backpressure achieves near-optimal utility-delay tradeoff. IEEE/ACM Trans Networking 2013; 21(3): 831–844.

25.

Athanasopoulou

Bui

. Back-pressure-based packet-by-packet adaptive routing in communication networks. IEEE/ACM Trans Networking 2013; 21(1): 244–257.

26.

Ronasi

Mohsenian-Rad

Wong

. Delay–throughput enhancement in wireless networks with multipath routing and channel coding. IEEE Trans Veh Technol 2011; 60(3): 1116–1123.

27.

Qiu

Bai

Xue

Towards optimal rate allocation in multi-hop wireless networks with delay constraints:A double-price approach. In: IEEE international conference on communications, Ottawa, Canada, 10–15 June 2012, pp. 5280–5285. New York, NY: IEEE.

28.

Eryilmaz

Scheduling for end-to-end deadline-constrained traffic with reliability requirements in multihop networks. IEEE/ACM Trans Networking 2012; 20(5): 1649–1662.

29.

Yuanan

Dongming

. Utility optimal scheduling in degree-limited satellite networks. J Comput Info Sys 2014; 9(9): 3723–3731. Hong Kong: Binary Information Press.

30.

Jiao

Tian

Zhang

. A gradient-assisted energy-efficient backpressure scheduling algorithm for wireless sensor networks. Int J Distrib Sens Netw 2015, http://dx.doi.org/10.1155/2015/46506

31.

Núñez-Martnez

Baranda

Mangues-Bafalluy

A self-organized backpressure routing scheme for dynamic small cell deployments. Ad Hoc Networks 2015; 25: 130–140.

32.

Chen

Liu

Towards an end-to-end delay analysis of LEO satellite networks for seamless ubiquitous access. Sci China Inf Sci 2013; 56(11): 1–13.