Page 21 - ITUJournal Future and evolving technologies Volume 2 (2021), Issue 1

ITU Journal on Future and Evolving Technologies, Volume 2 (2021), Issue 1

Finally, we formulate a minimization problem by using We update each virtual queue X i (t) at each time slot t as
(10) as shown below
∑ X i (t + 1) = max [X i (t) − γ i , 0] + p i (t), (13)
min f r (12)a
p(t)
r∈R and each virtual queue Z u (t) as
s. t. p ≤ γ i , ∀i ∈ N, (12)b
i Z u (t + 1) = max [Z u (t) − µ u (t), 0] + δ u . (14)
¯ µ u ≥ δ u , u ∈ U, (12)c
Process X i (t) can be viewed as a queue with “arrivals”
p(t) ∈ P(t). (12)d
p i (t) and “service rate” γ i . Process Z u (t) can be also
viewed as a queue with “arrivals” δ u and “service rate”
4. PROPOSED APPROXIMATE SOLUTION µ u (t).
The problem in (12) includes time average constraints. We will show that the average constraints in (12)b and
In order to satisfy these constraints, we aim to develop a (12)c are transformed into queue stability problems.
policy that uses techniques different from standard opti‑ Then, we develop a dynamic algorithm and we prove that
mization methods based on static and deterministic mod‑ the algorithm satis ies Theorem 1 and achieves stability.
1
els. Our approach is based on Lyapunov optimization the‑ Lemma1. IfX i (t)andZ u (t)areratestable , thenthecon‑
ory [34]. straints in (12)b and (12)c are satis ied.
In particular, we apply the technique developed in [35] Proof. See Appendix B.
and further discussed in [34] and [36] in order to develop
a policy that ensures that the constraints in (12)b and Note that strong stability implies all of the other forms
(12)c are satis ied. of stability [34, Chapter 2] including the rate stability.
Each inequality constraint in (12)b and (12)c is mapped Therefore, the problem is transformed into a queue sta‑
to a virtual queue. We show below that the power con‑ bility problem. In order to stabilize the virtual queues
straint and minimum throughput constraints problems X i (t), ∀i ∈ N and Z u (t), ∀u ∈ U, we irst de ine the Lya‑
are transformed into queue stability problems. punov function as
Before describing the motivation behind the mapping 1 ∑ 1 ∑
2
2
of average constraints in (12)b and (12)c to virtual L(Θ(t)) = X (t) + Z (t), (15)
u
i
queues, let us recall one basic theorem that comes from 2 i∈N 2 u∈R
the general theory of stability of stochastic processes where Θ(t) = [{X i (t)} i∈N , {Z u (t)} u∈U ], and the Lya‑
[37]. Consider a system with K queues. The number punov drift as
of un inished jobs of queue i is denoted by q k (t), and
K ∆(Θ(t)) , E {L(Θ(t + 1)) − L(Θ(t))|Θ(t)} . (16)
q(t) = {q k (t)} k=1 . The Lyapunov function and the Lya‑
punov drift are denoted by L(q(t)) and ∆(L(q(t))) , The above conditional expectation is with respect to the
E {L(q(t + 1)) − L(q(t))|q(t)} respectively [37]. Below random channel states and the arrivals.
we provide the de inition of the Lyapunov function [37]. To minimize the time average of the desired cost f r (t)
De inition 1 (Lyapunov function): A function L : R K → R while stabilizing the virtual queues X i (t), ∀i ∈ N,
is said to be a Lyapunov function if it has the following Z u (t), ∀u ∈ U, we use the drift‑plus‑penalty minimization
properties approach introduced in [36]. The approach seeks to min‑
imize an upper bound on the following drift‑plus‑penalty
K
• L(x) ≥ 0, ∀x ∈ R ,
expression at every slot t
∑
• It is non‑decreasing in any of its arguments, ∆(Θ(t)) + V E {f r (t)|Θ(t)} , (17)
r∈R
• L(x) → +∞, as ||x|| → +∞.
where V > 0 is an “importance” weight to scale the
Theorem 1 (Lyapunov Drift). If there exist positive values penalty. An upper bound for the expression in (17) is
shown below
B, ϵ such that for all time slots t we have ∆(L(q(t)) ≤ B −
∑
K ∑
ϵ q k (t), then the system q(t) is strongly stable. ∆(Θ(t)) + V E{f r (t)|Θ(t)} ≤ B
k=1 r∈R
∑
The intuition behind Theorem 1 is that if we have a queue‑ + E{X i (t)(p i (t) − γ i )|Θ(t)}
ing system, and we provide a scheduling scheme such that i∈N
∑
the Lyapunov drift is bounded and the sum of the length + E{Z u (t)(δ u − µ u (t))|Θ(t)}
of the queues are multiplied by a negative value, then the
r∈R
system is stable. Our goal is to ind a scheduling scheme ∑
for which the inequality of Theorem 1 holds for our appli‑ + V E{f r (t)|Θ(t)}, (18)
cation. r∈R
Let {X i (t)} and {Z u (t)} be the virtual queues as‑ 1 A discrete time process Q(t) is rate stable if lim Q(t) = 0 with prob‑
i∈N u∈U t→∞ t
sociated with constraints (12)b and (12)c, respectively. ability 1 [34].

© International Telecommunication Union, 2021 5