# Energy-Efficient Network Transmission between Satellite Swarms and Earth Stations Based on Lyapunov Optimization Techniques

Authors: Weiwei Fang; Yuan An; Kaidi He; Jiancheng Li; Baohua Wang; Jing Li; Qiancheng Wang; Qiwang Guo
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The recent advent of satellite swarm technologies has enabled space exploration with a massive number of picoclass, low-power, and low-weight spacecraft. However, developing swarm-based satellite systems, from conceptualization to validation, is a complex multidisciplinary activity. One of the primary challenges is how to achieve energy-efficient data transmission between the satellite swarm and terrestrial terminal stations. Employing Lyapunov optimization techniques, we present an online control algorithm to optimally dispatch traffic load among different satellite-ground links for minimizing overall energy consumption over time. Our algorithm is able to independently and simultaneously make control decisions on traffic dispatching over intersatellite-links and up-down-links so as to offer provable energy and delay guarantees, without requiring any statistical information of traffic arrivals and link condition. Rigorous analysis and extensive simulations have demonstrated the performance and robustness of the proposed new algorithm.


---

## Body

## 1. Introduction

To enable robust space exploration, astronautic scientists are exploiting principles and techniques that can help spacecraft systems become more resilient through self-organizing and automatic adaptation. Inspired by the swarming behaviors of animals in nature [1], they have recently proposed to build the swarm-based satellite system that is comprised of a large number of picoclass, low-power, and low-weight satellite units working together for space exploration tasks [2]. Typical projects include NASA ANTS (autonomous nanotechnology swarm) [3], ESA APIES (asteroid population investigation and exploration swarm) [4], and DARPA System F6 (future, fast, flexible, fractionated, free-flying spacecraft) [5].As shown in Figure1, a swarm typically consisted of several subswarms, which are temporal groups organized to perform a particular task. Each swarm group has a group leader (i.e., “ruler”) and a large number of “workers” carrying some specialized instruments. The ruler is responsible for coordinating its workers to cooperate on area monitoring and data gathering. Besides, there are some “messengers” in the swarm to coordinate communications among rulers, works, and earth stations. Although with different roles and responsibilities, all these three types of units rely mainly on the power from sun for data gathering, processing, and communication. However, the on-board solar panels cannot be very large for small-size satellites [6]. Thus, it is of great necessity to take energy efficiency into account when designing such satellite swarms.Figure 1
Illustration of a small satellite swarm in System F6 [5].To address the energy challenges of satellite swarms [7], we propose a novel online control algorithm based on Lyapunov optimization techniques [8] to make traffic dispatching decisions in the context of satellite-ground communications, which offers significant potentials on reducing energy consumption for data transmission over UDLs (up-down-links). Specifically, this algorithm aims to reduce energy consumption by making control decisions on (1) how to dispatch the traffic load from the workers over ISLs (intersatellite-links) to the messengers and (2) how to choose the best link from several available UDLs of a given messenger to transmit the aggregated data from this messenger to ground. Our algorithm does not require any prior knowledge of the system statistics or any prediction on traffic arrivals and link condition. Moreover, it is computationally efficient and easy to be implemented in the practical systems. It can obtain a time-average energy consumption within a deviation of O
(
1
/
V
) from optimality, while bounding the traffic queue backlog by O
(
V
), where V is a nonnegative control parameter representing a design knob of the energy-delay tradeoff, that is, how much we will emphasize the energy minimization compared to the system stability. We thoroughly analyze the performance of this algorithm with rigorous theoretical analysis. We also demonstrate its optimality, stability, and robustness, by extensive simulation experiments. To our knowledge, prior work has not yet studied the above energy-saving issue for satellite swarms, and our use of the Lyapunov framework for solving this issue is also novel.The rest of this paper is organized as follows: Section2 describes the theoretical model and formulates the optimization problem. Section 3 presents the proposed online control algorithm and provides an analysis on its performance bound and robustness. Section 4 analyzes the simulation results. Finally, Section 5 concludes the paper.


## 2. Problem Formulation

We consider a satellite swarm, as shown in Figure2, which has I heterogeneous workers denoted by W
=
{
W
1
,
…
,
W
I
}, as well as J homogeneous messengers denoted by M
=
{
M
1
,
…
,
M
J
}. For ease of reference, important notations are summarized in Notations section. The whole swarm system operates in discrete time with unit time slots t
∈
{
0,1
,
2
,
…
}. In every time slot t, we denote by A
i
(
t
) the amount of newly generated data at W
i, where A
(
t
)
=
(
A
1
(
t
)
,
…
,
A
I
(
t
)
) denotes the arrival vector. We assume that A
(
t
) are independently identically distributed (i.i.d.) over time slots with E
{
A
(
t
)
}
=
λ
≜
(
λ
1
,
…
,
λ
I
). We also assume that there exists a finite maximum A
max
⁡ such that 0
≤
A
i
(
t
)
≤
A
max
⁡ for all t and all i
∈
{
1
,
…
,
I
}. However, we do not assume any prior knowledge of the statistics of A
i
(
t
), and the traffic arrivals can be unpredictable and time-varying.Figure 2
Abstract architecture of the satellite swarm system.In a swarm, a workerW
i continuously gathers and temporally stores data information obtained by specialized exploring instruments. It then decides how to distribute the queued data to the messengers for transmitting to ground. To model this decision, we use μ
i
j
(
t
) to denote the amount of data traffic sent from W
i to M
j at time t and use μ
i
(
t
)
=
(
μ
i
1
(
t
)
,
…
,
μ
i
J
(
t
)
) to denote the vector of traffic load dispatching rates at W
i. We assume that, in every t, μ
i
(
t
) must be drawn from some general feasible set R
i; that is, μ
i
(
t
)
∈
R
i for all t, and each set R
i contains the constraint that 0
≤
∑
j
=
1
J
μ
i
j
(
t
)
≤
μ
max
⁡ for some finite maximum μ
max
⁡. This assumption is quite general; for example, μ
i
j
(
t
)
=
0, for all t representing that M
j cannot process data from W
i due to some reasons.The current satellite swarm prototypes generally use two different technologies for data communication, that is, the commercial-off-the-shelf wireless technology (e.g., IEEE 802.11) for intersatellite communications within the swarm [9] and the high-frequency microwave wireless technology (e.g., UHF/C/X/Ku/Ka band) for satellite-ground communications between swarm messengers and earth stations [10]. It is obvious that the latter can bring about energy consumption considerably higher than the former [7] and has significant impacts on the energy consumption and operational lifetime of the messengers. In the same time slot, a messenger may have more than one accessible earth station at different locations, and the UDLs between them have distinct communication characteristics, including available duration and error rate [11]. Hence, there exist opportunities for energy saving for the swarm by scheduling data transmission onto messengers having available UDLs currently with high quality and low cost. Let α
j
(
t
) denote the decision of messenger M
j on the UDL selection in time slot t. Then, the service rates (i.e., throughput) of messenger M
j for slot t can be given as X
j
(
t
)
=
X
j
(
α
j
(
t
)
). We assume a maximum transmission rate X
max
⁡, regardless of α
(
t
), so that 0
≤
X
j
(
t
)
≤
X
max
⁡. Besides, the energy consumption for transmitting data for M
j in slot t can be given as
(1)
f
j
(
t
)
=
K
*
X
j
(
t
)
1
-
E
j
(
t
)
,
where K is the coefficient of energy consumption for transmitting per unit data, and E
j
(
t
)
=
E
j
(
α
j
(
t
)
) is the error rate of selected UDL of M
j in slot t [12]. Note that this is a simple throughput-based energy consumption model used in wireless communication, and more accurate models can be used instead if necessary [13].LetQ
(
t
)
=
(
W
i
(
t
)
,
M
j
(
t
),  i
∈
{
1
,
…
,
I
},  j
∈
{
1
,
…
,
J
}
),  t
=
0,1
,
…, be the vector denoting the data traffic queued at the workers and the messengers at time slot t; we can capture the following queueing dynamics over time:
(2)
W
i
(
t
+
1
)
=
max
⁡
⁡
[
W
i
(
t
)
-
∑
j
=
1
J
‍
μ
i
j
(
t
)
,
0
]
+
A
i
(
t
)
,
(3)
M
j
(
t
+
1
)
=
max
⁡
[
M
j
(
t
)
-
X
j
(
t
)
,
0
]
+
∑
i
=
1
I
‍
μ
i
j
(
t
)
.In the following, we assume that satellites can estimate the unfinished traffic load in their queues accurately, and the case when such estimation has errors will be discussed in Section3. Throughout the paper, we use the following definition of queue stability:
(4)
Q
¯
≜
lim
⁡
T
→
∞
1
T
∑
t
=
0
T
-
1
‍
[
E
{
∑
i
=
1
I
‍
W
i
(
t
)
}
+
E
{
∑
j
=
1
J
‍
M
j
(
t
)
}
]
<
∞
.Our objective is to design a flexible and robust online control algorithm that automatically adapts to the time-varying systems by making decisions onμ
i
j
(
t
) and α
j
(
t
) for solving the stochastic minimization problem as follows:
(5)
min
⁡
μ
i
j
,
α
j
(
t
)
F
¯
≜
lim
⁡
T
→
∞
1
T
∑
t
=
0
T
-
1
‍
E
{
∑
j
=
1
J
‍
f
j
(
t
)
}
s
.
t
.
0
≤
A
i
(
t
)
≤
A
max
⁡
,
∀
i
∈
{
1
,
…
,
I
}
,
∀
t
0
≤
∑
j
=
1
J
‍
μ
i
j
(
t
)
≤
μ
max
⁡
,
∀
i
∈
{
1
,
…
,
I
}
,
∀
t
0
≤
X
j
(
α
j
(
t
)
)
≤
X
max
⁡
,
∀
j
∈
{
1
,
…
,
J
}
,
∀
t
Q
¯
<
∞
.However, traditional techniques, for example, Markov decision theory and dynamic programming, require substantial statistics of system dynamics and suffer from high computational complexity [8]. By comparison, the recently developed Lyapunov optimization technique has shown its efficacy and efficiency in designing online control algorithms for solving problems of joint system stability and performance optimization on stochastic networks, especially communication and queueing systems. To achieve this, network algorithms are designed to make control actions that greedily minimize a bound on the following drift-plus-penalty expression in each time slot t:
(6)
Δ
(
t
)
+
V
F
(
t
)
,
where Δ
(
t
) (Lyapunov drift) represents the congestion state of queue backlog, F
(
t
) denotes the objective function to be optimized, and V is a nonnegative weight that is chosen as desired to affect a performance tradeoff between backlog reduction and penalty minimization. Unlike the traditional techniques, Lyapunov optimization does not require knowledge of the statistics of relevant stochastic models to make online control decisions. The Lyapunov optimization algorithms commonly have a better computational complexity and are easy to be implemented in practical systems. By now, this technique has been applied in solving many stochastic network optimization problems, including workload/resource scheduling among data centers [14], power management in smart grid [15], and energy/throughput optimization for wireless systems [16]. In the following section, we will present an online control algorithm to solve problem in (5) based on the Lyapunov optimization framework.


## 3. Online Control Algorithm

LetQ
(
t
)
≜
(
W
(
t
)
,
M
(
t
)
) be a concatenated vector of all W
i
(
t
) and M
j
(
t
) queues. As a scalar measure of all the queue lengths, a quadratic Lyapunov function, which is a scalar measure of network congestion [8], can be defined as follows:
(7)
L
(
Q
(
t
)
)
≜
1
2
∑
i
=
1
I
‍
[
W
i
(
t
)
]
2
+
1
2
∑
j
=
1
J
‍
[
M
j
(
t
)
]
2
.Then, the one-slot conditional Lyapunov driftΔ
(
Q
(
t
)
) is defined as
(8)
Δ
(
Q
(
t
)
)
≜
E
[
L
(
Q
(
t
+
1
)
)
-
L
(
Q
(
t
)
)
∣
Q
(
t
)
]
.If control decisions are made in every slott to greedily minimize Δ
(
Q
(
t
)
), then all backlogs are consistently pushed towards a lower congestion state, which intuitively maintains system stability [8]. However, the objective energy consumption function to be minimized should also be incorporated. Thus, following the drift-plus-penalty framework in Lyapunov optimization [8], we design the control algorithm to make decisions on μ
i
j
(
t
) and α
j
(
t
) to minimize upper bound on the following drift-plus-penalty term in each time slot:
(9)
Δ
(
Q
(
t
)
)
+
V
E
{
∑
j
=
1
J
f
j
(
t
)
∣
Q
(
t
)
}
.A key derivation step is to obtain an upper bound on this term, which is defined as follows.Theorem 1 (drift-plus-penalty bound).
Under any control algorithm, the drift-plus-penalty expression has the following upper bound for allt, all possible values of Q
(
t
), and all parameters V
≥
0:
(10)
Δ
(
Q
(
t
)
)
+
V
E
{
∑
j
=
1
J
‍
f
j
(
t
)
∣
Q
(
t
)
}
≤
B
+
E
{
∑
i
=
1
I
‍
W
i
(
t
)
A
i
(
t
)
∣
Q
(
t
)
}
+
E
{
∑
i
=
1
I
‍
∑
j
=
1
J
‍
μ
i
j
(
t
)
[
M
j
(
t
)
-
W
i
(
t
)
]
∣
Q
(
t
)
}
+
E
{
∑
j
=
1
J
‍
[
V
f
j
(
t
)
-
M
j
(
t
)
X
j
(
t
)
]
∣
Q
(
t
)
}
,
where B
=
(
I
(
A
max
⁡
2
+
μ
max
⁡
2
)
+
J
(
X
max
⁡
2
+
I
μ
max
⁡
2
)
)
/
2.Proof.
Squaring both sides of the queueing dynamic (2) and using the fact that, for any Q
≥
0, b
≥
0, A
≥
0, (
max
⁡
[
Q
-
b
,
0
]
+
A
)
2
≤
Q
2
+
A
2
+
b
2
+
2
Q
(
A
-
b
), we have
(11)
[
W
i
(
t
+
1
)
]
2
≤
[
W
i
(
t
)
]
2
+
[
A
i
(
t
)
]
2
+
[
∑
j
=
1
J
‍
μ
i
j
(
t
)
]
2
+
2
W
i
(
t
)
[
A
i
(
t
)
-
∑
j
=
1
J
‍
μ
i
j
(
t
)
]
.
Summing the above overi
=
1
,
…
,
I and using the fact that A
i
(
t
)
≤
A
max
⁡ and ∑
j
=
1
J
μ
i
j
(
t
)
≤
μ
max
⁡, we have
(12)
∑
i
=
1
I
‍
{
[
W
i
(
t
+
1
)
]
2
-
[
W
i
(
t
)
]
2
}
≤
I
(
A
max
⁡
2
+
μ
max
⁡
2
)
+
2
∑
i
=
1
I
‍
W
i
(
t
)
[
A
i
(
t
)
-
∑
j
=
1
J
‍
μ
i
j
(
t
)
]
.
Repeating the above steps for the queueM
j
(
t
), and by using the fact that 0
≤
X
j
(
t
)
≤
X
max
⁡, we have
(13)
∑
j
=
1
J
‍
{
[
M
j
(
t
+
1
)
]
2
-
[
M
j
(
t
)
]
2
}
≤
J
(
X
max
⁡
2
+
I
μ
max
⁡
2
)
+
2
∑
j
=
1
J
‍
M
j
(
t
)
[
∑
i
=
1
I
‍
μ
i
j
(
t
)
-
X
j
(
t
)
]
.
Combining these two bounds together, and taking the expectation with respect toQ
(
t
) on both sides, we arrive at the following one-slot conditional Lyapunov drift Δ
(
Q
(
t
)
):
(14)
Δ
(
Q
(
t
)
)
≤
B
+
E
{
∑
i
=
1
I
‍
W
i
(
t
)
A
i
(
t
)
∣
Q
(
t
)
}
+
E
{
∑
i
=
1
I
‍
∑
j
=
1
J
‍
μ
i
j
(
t
)
[
M
j
(
t
)
-
W
i
(
t
)
]
∣
Q
(
t
)
}
-
E
{
∑
j
=
1
J
‍
M
j
(
t
)
X
j
(
t
)
∣
Q
(
t
)
}
,
where B
=
(
I
(
A
max
⁡
2
+
μ
max
⁡
2
)
+
J
(
X
max
⁡
2
+
I
μ
max
⁡
2
)
)
/
2.
Now adding to both sides the penalty expression, that is, the termV
E
{
∑
j
=
1
J
f
j
(
t
)
∣
Q
(
t
)
}, proves the theorem.Minimizing the right-hand-side of (10) is equivalent to minimizing E
{
∑
i
=
1
I
∑
j
=
1
J
μ
i
j
(
t
)
[
M
j
(
t
)
-
W
i
(
t
)
]
∣
Q
(
t
)
}
+
E
{
∑
j
=
1
J
[
V
f
j
(
t
)
-
M
j
(
t
)
X
j
(
t
)
]
∣
Q
(
t
)
} under the same constraints in (5). Thus, we can design the online control algorithm as in Algorithm 1.Algorithm 1:Online control algorithm.
(1)Workers-to-Messengers Traffic Distribution: At time slot t, each W
i solves for μ
i
j
(
t
) to maximize
∑
j
=
1
J
μ
i
j
(
t
)
[
W
i
(
t
)
-
M
j
(
t
)
]
(2)Messengers-to-Stations UDL Selection: At time slot t, each M
j chooses α
j
(
t
) to minimize
V
f
j
(
t
)
-
M
j
(
t
)
X
j
(
t
)
(3)Queue Update: Update the queues W
i
(
t
) and M
j
(
t
) using (2) and (3).The following theorem presents bounds on the time-average energy cost and queue backlogs achieved by the proposed new algorithm.Theorem 2 (algorithm performance).
DefineΛ as the set of all rate vectors that satisfy the constraints in (5). For any rate vector λ
∈
Λ, suppose there exists an ϵ
>
0 such that λ
+
ϵ
1
∈
Λ; then under the online control algorithm one has
(15)
Q
¯
≜
lim
⁡
T
→
∞
1
T
∑
t
=
0
T
-
1
‍
[
E
{
∑
i
=
1
I
‍
W
i
(
t
)
}
+
E
{
∑
j
=
1
J
‍
M
j
(
t
)
}
]
≤
B
+
V
F
¯
max
⁡
ϵ
,
(16)
F
¯
≜
lim
⁡
T
→
∞
1
T
∑
t
=
0
T
-
1
‍
E
{
∑
j
=
1
J
‍
f
j
(
t
)
}
≤
F
¯
*
+
B
V
.
Here F
¯
max
⁡ and F
¯
* are the maximal value and the optimal value for the cost defined in (5), respectively, and 1 denotes the vector of all 1’s.Proof.
According to Caratheodory’s theorem [8, 14], we can easily prove that there exists a randomized stationary control policy π that chooses feasible control decisions μ
i
j
(
t
) and α
j
(
t
), independent of the current queue backlogs, and achieves the following guarantees:
(17)
E
{
∑
j
=
1
J
‍
f
j
π
(
t
)
}
=
F
¯
*
,
E
{
A
i
π
(
t
)
}
=
E
{
∑
j
=
1
J
‍
μ
i
j
π
(
t
)
}
,
E
{
∑
i
=
1
I
‍
μ
i
j
π
(
t
)
}
=
E
{
X
j
π
(
t
)
}
.
Because in every time slott, our implementation seeks to minimize the right-hand-side of the drift-plus-penalty expression in (10):
(18)
Δ
(
Q
(
t
)
)
+
V
E
{
∑
j
=
1
J
‍
f
j
(
t
)
∣
Q
(
t
)
}
≤
B
+
V
E
{
∑
j
=
1
J
‍
f
j
†
(
t
)
∣
Q
(
t
)
}
+
E
{
∑
i
=
1
I
‍
W
i
(
t
)
[
A
i
(
t
)
-
∑
j
=
1
J
‍
μ
i
j
†
(
t
)
]
∣
Q
(
t
)
}
+
E
{
∑
j
=
1
J
‍
M
j
(
t
)
[
∑
i
=
1
I
‍
μ
i
j
†
(
t
)
-
X
j
(
α
j
†
(
t
)
)
]
∣
Q
(
t
)
}
,
where f
j
†
(
t
), μ
i
j
†
(
t
), and α
j
†
(
t
) are the resulting decisions and attributed values under any alternative (possibly randomized) policy (denoted by †). Now since λ
+
ϵ
1
∈
Λ, it can be known from (17) that there exists a stationary and randomized policy π
′ that achieves the following:
(19)
E
{
∑
j
=
1
J
‍
f
j
π
′
(
t
)
}
=
F
¯
*
(
λ
+
ϵ
1
)
,
E
{
A
i
π
′
(
t
)
}
=
E
{
∑
j
=
1
J
‍
μ
i
j
π
′
(
t
)
}
-
ϵ
,
E
{
∑
i
=
1
I
‍
μ
i
j
π
′
(
t
)
}
=
E
{
X
j
π
′
(
t
)
}
-
ϵ
.
Here F
¯
*
(
λ
+
ϵ
1
) is the minimum cost corresponding to the rate vector λ
+
ϵ
1. Plugging (19) into the right-hand-side of (18) yields
(20)
Δ
(
Q
(
t
)
)
+
V
E
{
∑
j
=
1
J
‍
f
j
(
t
)
∣
Q
(
t
)
}
≤
B
+
V
F
¯
*
(
λ
+
ϵ
1
)
-
ϵ
∑
i
=
1
I
‍
W
i
(
t
)
-
ϵ
∑
j
=
1
J
‍
M
j
(
t
)
.
Now we can take expectations on both sides overQ
(
t
) to get
(21)
E
{
L
(
Q
(
t
+
1
)
)
-
L
(
Q
(
t
)
)
}
+
V
E
{
∑
j
=
1
J
‍
f
j
(
t
)
}
≤
B
+
V
F
¯
*
(
λ
+
ϵ
1
)
-
ϵ
E
{
∑
i
=
1
I
‍
W
i
(
t
)
}
-
ϵ
E
{
∑
j
=
1
J
‍
M
j
(
t
)
}
.
Rearranging the terms, and using the fact that0
≤
F
¯
*
(
λ
+
ϵ
1
)
≤
F
¯
max
⁡, we get that
(22)
E
{
L
(
Q
(
t
+
1
)
)
-
L
(
Q
(
t
)
)
}
+
ϵ
(
E
{
∑
i
=
1
I
‍
W
i
(
t
)
}
+
E
{
∑
j
=
1
J
‍
M
j
(
t
)
}
)
≤
B
+
V
F
¯
max
⁡
.
Summing the above overt
=
0,1
,
…
,
T
-
1, rearranging the terms, using the fact that L
(
Q
(
t
)
)
≥
0 for all t, and dividing both sides by ϵ
T, we have
(23)
1
T
∑
t
=
0
T
-
1
‍
[
E
{
∑
i
=
1
I
‍
W
i
(
t
)
}
+
E
{
∑
j
=
1
J
‍
M
j
(
t
)
}
]
≤
B
+
V
F
¯
max
⁡
ϵ
,
which proves (15) by taking limit as T
→
∞.
To prove (16), using (21), we have
(24)
V
E
{
∑
j
=
1
J
‍
f
j
(
t
)
}
≤
V
F
¯
*
(
λ
+
ϵ
1
)
+
B
.
Summing the above overt
=
0
,
…
,
T
-
1, and dividing both sides by T
V, we have
(25)
1
T
∑
t
=
0
T
-
1
‍
E
{
∑
j
=
1
J
‍
f
j
(
t
)
}
≤
F
¯
*
(
λ
+
ϵ
1
)
+
B
V
,
which proves (16) by taking limit as T
→
∞ and letting ϵ
→
0.As mentioned in Section2, this algorithm needs to know the concatenated queue backlog Q
(
t
) to make control decisions. In practice, when this is not available, we use estimated values. The following theorem shows that the algorithm is robust when it makes control decisions based on the queue backlog estimates Q
^
(
t
) that differ from the actual queue backlogs.Theorem 3 (algorithm robustness).
Suppose there exists anϵ
>
0 such that λ
+
ϵ
1
∈
Λ. Also suppose there exists a constant c
e, such that at all time t, the estimated backlog sizes W
^
i
(
t
), M
^
j
(
t
), and the actual backlog sizes W
i
(
t
), M
j
(
t
) satisfy |
W
^
i
(
t
)
-
W
i
(
t
)
|
≤
c
e and |
M
^
j
(
t
)
-
M
j
(
t
)
|
≤
c
e. Then under the algorithm, one has
(26)
Q
¯
≜
lim
⁡
T
→
∞
1
T
∑
t
=
0
T
-
1
‍
[
E
{
∑
i
=
1
I
‍
W
i
(
t
)
}
+
E
{
∑
j
=
1
J
‍
M
j
(
t
)
}
]
≤
B
′
+
V
F
¯
max
⁡
ϵ
,
F
¯
≜
lim
⁡
T
→
∞
1
T
∑
t
=
0
T
-
1
‍
E
{
∑
j
=
1
J
‍
f
j
(
t
)
}
≤
F
¯
*
+
B
′
V
.
Here B
′
=
B
+
2
c
e
(
I
A
max
⁡
+
I
μ
max
⁡
+
J
I
μ
max
⁡
+
J
X
max
⁡
).Proof.
It suffices to show that usingW
^
i
(
t
), M
^
j
(
t
), we still minimize the right-hand-side of the drift expression in (10) to within some additive constant. Denote e
i
W
(
t
)
=
W
^
i
(
t
)
-
W
i
(
t
) and e
j
M
(
t
)
=
M
^
j
(
t
)
-
M
j
(
t
). Suppose now W
^
i
(
t
) and M
^
j
(
t
) are used to carry out the algorithm; then we see that we try to minimize
(27)
Obj
(
Q
^
(
t
)
)
≜
V
E
{
∑
j
=
1
J
‍
f
j
(
t
)
∣
Q
(
t
)
}
+
E
{
∑
i
=
1
I
‍
W
^
i
(
t
)
[
A
i
(
t
)
-
∑
j
=
1
J
‍
μ
i
j
(
t
)
]
∣
Q
(
t
)
}
+
E
{
∑
j
=
1
J
‍
M
^
j
(
t
)
[
∑
i
=
1
I
‍
μ
i
j
(
t
)
-
X
j
(
t
)
]
∣
Q
(
t
)
}
≜
V
E
{
∑
j
=
1
J
‍
f
j
(
t
)
∣
Q
(
t
)
}
+
E
{
∑
i
=
1
I
‍
W
i
(
t
)
[
A
i
(
t
)
-
∑
j
=
1
J
‍
μ
i
j
(
t
)
]
∣
Q
(
t
)
}
+
E
{
∑
j
=
1
J
‍
M
j
(
t
)
[
∑
i
=
1
I
‍
μ
i
j
(
t
)
-
X
j
(
t
)
]
∣
Q
(
t
)
}
+
E
{
∑
i
=
1
I
‍
e
i
W
(
t
)
[
A
i
(
t
)
-
∑
j
=
1
J
‍
μ
i
j
(
t
)
]
∣
Q
(
t
)
}
+
E
{
∑
j
=
1
J
‍
e
j
M
(
t
)
[
∑
i
=
1
I
‍
μ
i
j
(
t
)
-
X
j
(
t
)
]
∣
Q
(
t
)
}
.
Now denote the minimum value ofObj
(
Q
(
t
)
) to be Ob
j
*, that is, the minimum of the right-hand-side of (10) with Q
(
t
), and denote the minimum value of Obj
(
Q
^
(
t
)
) to be Ob
j
‡. Then using the fact that |
e
i
W
(
t
)
|
≤
c
e and |
e
j
M
(
t
)
|
≤
c
e, and the fact that |
A
i
(
t
)
-
∑
j
=
1
J
μ
i
j
(
t
)
|
≤
A
max
⁡
+
μ
max
⁡, |
∑
i
=
1
I
μ
i
j
(
t
)
-
X
j
(
t
)
|
≤
I
μ
max
⁡
+
X
max
⁡ (since |
a
-
b
|
≤
|
a
|
+
|
b
|), we know that
(28)
Ob
j
‡
≤
Ob
j
*
+
E
{
∑
i
=
1
I
‍
e
i
W
(
t
)
[
A
i
(
t
)
-
∑
j
=
1
J
‍
μ
i
j
(
t
)
]
∣
Q
(
t
)
}
+
E
{
∑
j
=
1
J
‍
e
j
M
(
t
)
[
∑
i
=
1
I
‍
μ
i
j
(
t
)
-
X
j
(
t
)
]
∣
Q
(
t
)
}
.
Using this and (27), we see that
(29)
V
E
{
∑
j
=
1
J
‍
f
j
‡
(
t
)
∣
Q
(
t
)
}
+
E
{
∑
i
=
1
I
‍
W
i
(
t
)
[
A
i
(
t
)
-
∑
j
=
1
J
‍
μ
i
j
‡
(
t
)
]
∣
Q
(
t
)
}
+
E
{
∑
j
=
1
J
‍
M
j
(
t
)
[
∑
i
=
1
I
‍
μ
i
j
‡
(
t
)
-
X
j
(
α
j
‡
(
t
)
)
]
∣
Q
(
t
)
}
≤
Ob
j
*
+
2
c
e
(
I
A
max
⁡
+
I
μ
max
⁡
+
J
I
μ
max
⁡
+
J
X
max
⁡
)
.
Heref
j
‡
(
t
), μ
i
j
‡
(
t
), and α
j
‡
(
t
) are the actions taken by the policy based on Obj
(
Q
^
(
t
)
). This completes the proof. This shows that (10) holds with Q
(
t
) replaced by Q
^
(
t
) and B replaced by B
′
=
B
+
2
c
e
(
I
A
max
⁡
+
I
μ
max
⁡
+
J
I
μ
max
⁡
+
J
X
max
⁡
). The rest of the proof follows similarly as the proof of Theorem 2.


## 4. Performance Evaluation

### 4.1. Simulation Setup

We evaluate the proposed new algorithm with extensive simulations under realistic settings. We simulate a satellite swarm consisting of 5 homogeneous messengers and 50 heterogeneous workers. In every time slot, each messenger can choose to use a specific UDL from at least 3 candidates for transmitting data to ground. According to [17, 18], we set X
j
(
t
)
∈
[
50,150
] Mb, e
j
(
t
)
∈
[
10
%
,
70
%
] for all j
∈
{
1
,
…
,
J
} and t
=
0,1
,
…, and K
=
100 J. We assume the data arrivals at worker i follow Poisson processes with λ
i
=
10 Mb, and μ
max
⁡
=
20 Mb.To fully investigate the algorithm performance, we compare it with an intuitive online algorithm called LBMin. In LBMin, each worker dispatches all its data to the messenger currently with the smallest queue backlog, while each messenger chooses the UDL with the lowest energy cost for satellite-ground communication. It represents the current task processing practices in computing and network systems [14, 19]. According to Theorem 2.4 in [8], we use a simple control policy to enforce that ∑
τ
=
0
t
-
1
‍
X
j
(
τ
)
≥
∑
τ
=
0
t
-
1
‍
∑
i
=
1
I
‍
μ
i
j
(
τ
) for each j
∈
{
1
,
…
,
J
} and t
=
0,1
,
…, so as to guarantee the rate stability of queue M
j.


### 4.2.  Experimental Results

We conduct the following analysis on critical factors to characterize their impacts on the algorithm performance.(1) Impact of control parameterV: we fix T
=
500 time slots and conduct experiments with different values of V. From the results shown in Figures 3, 4, and 5, we can observe that, by choosing a small V initially, the time-average energy cost is quite big whereas it can be significantly reduced later by increasing the value of V and finally converge to the minimum level for larger values of V. This quantitatively corroborates Theorem 2 in that the proposed algorithm can approach the optimal cost with a diminishing gap (
1
/
V
) (captured by (16)). However, increasing V leads to the almost linear growth of time-average queue backlog and average delay (captured by (15)). In general, V in the algorithm controls the [
O
(
1
/
V
,
O
(
V
)
)
] tradeoff between energy cost and service delay. This enables the algorithm to obtain an elastic performance bound by adjusting V within a desired cost and delay constraints.Figure 3
Time-average energy cost under differentV value (T
=
500).Figure 4
Time-average queue backlog under differentV value (T
=
500).Figure 5
Average service delay under differentV value (T
=
500).(2) Impact of long-term time slotT: in Figure 6, we fix V
=
1,3
,
10,20, respectively, and vary T from 50 time slots to 600 time slots, which is a sufficient range for exploring the characteristics of different time-scales of long-term processing. The time-average energy cost only fluctuates within [
-
2.72
%
,
+
0.99
%
], [
-
1.32
%
,
+
0.76
%
], [
-
1.24
%
,
+
3.04
%
], and [
-
1.17
%
,
+
3.68
%
] for V
=
1,3
,
10,20, respectively. Therefore, we can know that changing T has relatively less impact on the energy cost, and the proposed new algorithm can guarantee stable performance over time.Figure 6
Time-average energy cost under differentT and V value.(3) Characterizing algorithm robustness: as mentioned in Section2, the proposed new algorithm needs to know the amount of traffic load of each worker. Now we explore the influence of estimation errors on the performance of this algorithm. For each worker, we add a random estimation error (±
50
%, uniformly distributed) to the amount of traffic load in its queue. We let the algorithm make all the control decisions based on the traffic input with random errors under different values of V. In Figures 7–9, we use the results on the original data without estimation errors as the baseline and show the differences in energy cost, queue backlog, and service delay due to injected estimation errors. Figure 7 indicates that for all V values we experimented with, the difference (due to errors) in energy cost is between −1.36% and 0.78%. In Figure 8, the difference in queue backlog is between −9.30% and 11.55%. As shown in Figure 9, changes in service delay caused by estimation errors are small, that is, about −1.49 to 1.25 time slots. To conclude, this algorithm is robust to estimation errors of traffic load, as revealed by Theorem 3.Figure 7
The impact of estimation errors on time-average energy cost.Figure 8
The impact of estimation errors on time-average queue backlog.Figure 9
The impact of estimation errors on average service delay.(4) Algorithm comparison: we choose to compare LBMin to the proposed new algorithm whenV
=
20. As shown in Figure 10, the performance gap on energy cost between them is almost neglectable, that is, about 0.13% to 0.26%. The reason is that the proposed algorithm has approached the optimal energy consumption when V
=
20, as indicated by Figure 3. However, we can find from Figure 11 that the proposed algorithm outperforms LBMin on system throughput at all times. With T varying from 50 to 600 time slots, the difference grows from about 4.64% to 11.44%. That is because LBMin takes no consideration of the throughput issue. In conclusion, the proposed algorithm is able to consume nearly the same energy with LBMin to transmit more satellite data to ground over time.Figure 10
Comparison on time-average energy cost under differentT (V
=
20).Figure 11
Comparison on time-average throughput under differentT (V
=
20).


## 4.1. Simulation Setup

We evaluate the proposed new algorithm with extensive simulations under realistic settings. We simulate a satellite swarm consisting of 5 homogeneous messengers and 50 heterogeneous workers. In every time slot, each messenger can choose to use a specific UDL from at least 3 candidates for transmitting data to ground. According to [17, 18], we set X
j
(
t
)
∈
[
50,150
] Mb, e
j
(
t
)
∈
[
10
%
,
70
%
] for all j
∈
{
1
,
…
,
J
} and t
=
0,1
,
…, and K
=
100 J. We assume the data arrivals at worker i follow Poisson processes with λ
i
=
10 Mb, and μ
max
⁡
=
20 Mb.To fully investigate the algorithm performance, we compare it with an intuitive online algorithm called LBMin. In LBMin, each worker dispatches all its data to the messenger currently with the smallest queue backlog, while each messenger chooses the UDL with the lowest energy cost for satellite-ground communication. It represents the current task processing practices in computing and network systems [14, 19]. According to Theorem 2.4 in [8], we use a simple control policy to enforce that ∑
τ
=
0
t
-
1
‍
X
j
(
τ
)
≥
∑
τ
=
0
t
-
1
‍
∑
i
=
1
I
‍
μ
i
j
(
τ
) for each j
∈
{
1
,
…
,
J
} and t
=
0,1
,
…, so as to guarantee the rate stability of queue M
j.


## 4.2.  Experimental Results

We conduct the following analysis on critical factors to characterize their impacts on the algorithm performance.(1) Impact of control parameterV: we fix T
=
500 time slots and conduct experiments with different values of V. From the results shown in Figures 3, 4, and 5, we can observe that, by choosing a small V initially, the time-average energy cost is quite big whereas it can be significantly reduced later by increasing the value of V and finally converge to the minimum level for larger values of V. This quantitatively corroborates Theorem 2 in that the proposed algorithm can approach the optimal cost with a diminishing gap (
1
/
V
) (captured by (16)). However, increasing V leads to the almost linear growth of time-average queue backlog and average delay (captured by (15)). In general, V in the algorithm controls the [
O
(
1
/
V
,
O
(
V
)
)
] tradeoff between energy cost and service delay. This enables the algorithm to obtain an elastic performance bound by adjusting V within a desired cost and delay constraints.Figure 3
Time-average energy cost under differentV value (T
=
500).Figure 4
Time-average queue backlog under differentV value (T
=
500).Figure 5
Average service delay under differentV value (T
=
500).(2) Impact of long-term time slotT: in Figure 6, we fix V
=
1,3
,
10,20, respectively, and vary T from 50 time slots to 600 time slots, which is a sufficient range for exploring the characteristics of different time-scales of long-term processing. The time-average energy cost only fluctuates within [
-
2.72
%
,
+
0.99
%
], [
-
1.32
%
,
+
0.76
%
], [
-
1.24
%
,
+
3.04
%
], and [
-
1.17
%
,
+
3.68
%
] for V
=
1,3
,
10,20, respectively. Therefore, we can know that changing T has relatively less impact on the energy cost, and the proposed new algorithm can guarantee stable performance over time.Figure 6
Time-average energy cost under differentT and V value.(3) Characterizing algorithm robustness: as mentioned in Section2, the proposed new algorithm needs to know the amount of traffic load of each worker. Now we explore the influence of estimation errors on the performance of this algorithm. For each worker, we add a random estimation error (±
50
%, uniformly distributed) to the amount of traffic load in its queue. We let the algorithm make all the control decisions based on the traffic input with random errors under different values of V. In Figures 7–9, we use the results on the original data without estimation errors as the baseline and show the differences in energy cost, queue backlog, and service delay due to injected estimation errors. Figure 7 indicates that for all V values we experimented with, the difference (due to errors) in energy cost is between −1.36% and 0.78%. In Figure 8, the difference in queue backlog is between −9.30% and 11.55%. As shown in Figure 9, changes in service delay caused by estimation errors are small, that is, about −1.49 to 1.25 time slots. To conclude, this algorithm is robust to estimation errors of traffic load, as revealed by Theorem 3.Figure 7
The impact of estimation errors on time-average energy cost.Figure 8
The impact of estimation errors on time-average queue backlog.Figure 9
The impact of estimation errors on average service delay.(4) Algorithm comparison: we choose to compare LBMin to the proposed new algorithm whenV
=
20. As shown in Figure 10, the performance gap on energy cost between them is almost neglectable, that is, about 0.13% to 0.26%. The reason is that the proposed algorithm has approached the optimal energy consumption when V
=
20, as indicated by Figure 3. However, we can find from Figure 11 that the proposed algorithm outperforms LBMin on system throughput at all times. With T varying from 50 to 600 time slots, the difference grows from about 4.64% to 11.44%. That is because LBMin takes no consideration of the throughput issue. In conclusion, the proposed algorithm is able to consume nearly the same energy with LBMin to transmit more satellite data to ground over time.Figure 10
Comparison on time-average energy cost under differentT (V
=
20).Figure 11
Comparison on time-average throughput under differentT (V
=
20).


## 5. Conclusions

In this paper, we propose a new algorithm based on Lyapunov optimization, to reduce the energy consumption on satellite-ground communications for satellite swarm systems. Our approach incorporates traffic scheduling actions on ISLs between workers and messengers and on UDLs between messengers and earth stations, so as to transmit data on high-quality, low-cost UDLs to ground. Through analysis and simulations, we show that this algorithm has provable performance bounds and is very effective in reducing energy costs of satellite-ground communication. We also show that this algorithm can guarantee stable performance over time and is robust to traffic load estimation errors. Moreover, it is computationally efficient and easy to implement in large practical swarming systems.



---

*Source: 254326-2014-09-28.xml*