1

Utility Optimal Scheduling for Coded Caching
in General Topologies
Richard Combes, Asma Ghorbel, Mari Kobayashi, and Sheng Yang
LSS, CentraleSupélec

arXiv:1801.02594v1 [] 8 Jan 2018

Gif-sur-Yvette, France

{firstname.lastname}@centralesupelec.fr

Abstract
We consider coded caching over the fading broadcast channel, where the users, equipped with a
memory of finite size, experience asymmetric fading statistics. It is known that a naive application of
coded caching over the channel at hand performs poorly especially in the regime of a large number
of users due to a vanishing multicast rate. We overcome this detrimental effect by a careful design
of opportunistic scheduling policies such that some utility function of the long-term average rates
should be maximized while balancing fairness among users. In particular, we propose a threshold-based
scheduling that requires only statistical channel state information and one-bit feedback from each user.
More specifically, each user indicates via feedback whenever its SNR is above a threshold determined
solely by the fading statistics and the fairness requirement. Surprisingly, we prove that this simple
scheme achieves the optimal utility in the regime of a large number of users. Numerical examples show
that our proposed scheme performs closely to the scheduling with full channel state information, but at
a significantly reduced complexity.

I. I NTRODUCTION
Content delivery applications such as video streaming are envisioned to represent nearly 75%
of the mobile data traffic by 2020 [1]. The skewness of the video traffic together with the
ever-growing cheap on-board storage memory suggests that the quality of experience can be
improved by caching popular content close to the end-users in wireless networks. Recent works
have studied the gains provided by caching under various models and assumptions (see e.g. [2],
This work was partly supported by Huawei Technologies France.

2

[3] and references therein). In this work, we consider content delivery using coded caching [2]
in a wireless network where a server is connected to K users each equipped with a cache of
finite memory. By a careful design of sub-packetization and cache placement, it is possible to
create a multicast signal simultaneously useful for many users and thus decrease the delivery
time. More specifically, it has been proved that the delivery time to satisfy K distinct requests
converges to a constant in the regime of a large number K of users. In other words, the sum
content delivery rate, defined as the total amount of requested bits divided by the delivery time,
grows linearly with K. This striking result has motivated a number of follow-up works in order
to study coded caching in more realistic scenarios (see e.g. [2, Section VIII]).
Albeit conceptually and theoretically appealing, the promised gain of coded caching relies on
some unrealistic assumptions (see. e.g. [4]). In particular, [5]–[7] have revealed that the scalability
of coded caching is very sensitive to the behavior of the multicast rate supported by the bottleneck
link. It is worth recalling that the multicast capacity of the fading broadcast channel is limited
by the channel quality of the weak users, i.e., the users whose channel gain is the smallest.
Focusing on the case of the i.i.d. quasi-static Rayleigh fading channel, the works [5], [8] further
showed that the long-term sum content delivery rate does not grow with the system dimension
if coded caching is naively applied to this channel. In fact, the long-term average multicast rate
of the i.i.d. Rayleigh fading channel vanishes, as it scales as O( K1 ) as K → ∞, [9]. When the
users experience asymmetric fading statistics, the long-term average multicast rate is essentially
limited by the users with poor channel statistics. Therefore, the performance of coded caching
may degrade even further, since nearly the whole resource is wasted to enable the weak users
to decode the common message. These observations have inspired a number of recent works
to overcome these drawbacks [5]–[8], [10]–[13]. The works [5], [8], [10]–[12] have considered
the use of multiple antennas, while [14], [15] have proposed several interference management
techniques. Other recent works have studied opportunistic scheduling [5]–[7] in this context.
Finally, the interplay between the fairness and the gain of coded caching has been studied in a
recent work [7]. Although both the current work and [7] consider the same channel model and
address a similar question, they differ in their objectives and approaches. In [7], a new queueing
structure has been proposed to deal jointly with admission control, routing, as well as scheduling
for a finite number of users. The performance analysis built on the Lyapunov theory. The current
work highlights the scheduling part and provides a rigorous analysis on the long-term average
per-user rate in the regime of a large number of users.

3

As a non-trivial extension of [5], [6], we study opportunistic scheduling in order to achieve a
scalable sum content delivery while ensuring some fairness among users. To capture these two
contrasted measures, we formulate our objective function by an alpha-fairness family of concave
utility functions [16]. Our main contributions of this work are three-fold:
1) We propose a simple threshold-based scheduling policy and determine the threshold as
a function of the fading statistics for each fairness parameter α. Such threshold-based
scheme exhibits two interesting features. On the one hand, the complexity is linear in
K and significantly reduced with respect to the original problem where the search is done
over K 2 variables. On the other hand, a threshold-based policy does not require the exact
channel state information but only a one-bit feedback from each user. Namely, each user
indicates whether its measured SNR is above the threshold set before the communication.
A special case of the symmetric fading and the sum rate objective (α = 0), our proposed
scheme boils down to the scheme in [5], [6].
2) We prove that the proposed threshold-based scheduling policy is asymptotically optimal in
Theorem 3. Namely, the utility achieved by our proposed policy converges to the optimal
value as the number of users grows. The proof of Theorem 3 involves essentially three
steps. First, we characterize the lower and upper bounds on the long-term average rate of
each user. Second, we prove that the size of the selected user set grows unbounded as the
number of users grows. Finally, we prove the convergence of the utility value.
3) Our numerical experiments show that the proposed scheme indeed achieves a near-optimal
performance. Namely, it converges to the selection scheme with full channel knowledge
as the number of users and/or SNR increases. Such scheme is therefore appropriate for a
large number of users. In addition, the multicast rate is less sensitive to the user in the
worst fading condition in the large SNR regime. Furthermore, the speed of convergence
increases with the memory size and/or α-fair parameter. In fact, Property 1 in subsection
III-B justifies the impact of the memory.
The remainder of the paper is organized as follows. Section II provides the system model
and Section III formulates the fair scheduling problem as maximizing the α-fair utility. In
Section IV, we define the optimal policy as well as a class of threshold-based policies with
reduced complexity. In Section V, we state and prove the main result, that is, the thresholdbased scheduling policy achieves the optimal utility in the regime of a large number of users. We

4

Fig. 1. System model with K = 3.

further characterize the threshold-based policy for different fairness criteria. Section VI provides
numerical examples to validate our analysis in previous sections and compare the performance
of the proposed threshold-based policy with other schemes.
Throughout the paper, we use [k] to denote the set of integers {1, . . . , k}, and f (x) ∼ g(x)
f (x)
x→∞ g(x)

means that lim

P

a.s.

= 1. We use the notation → to denote convergence in probability and →

to denote almost sure convergence.
II. S YSTEM M ODEL
We consider a content delivery system where a server with N files wishes to convey the
requested files to K users over a wireless downlink channel. We assume that N files are of
equal size of F bits and have equal popularity, while each user has a cache of size M F bits,
where M ≥ 1 denotes the cache size measured in files. We often use the normalized cache size
denoted by m = M/N . In this work, we focus on the regime of a large number of files, i.e.,
N ≥ K, and assume that the requests from the users are all distinct. Further, each user can
prefetch some content to fill their caches during off-peak hours, prior to the actual request. We
consider mainly the decentralized caching scheme of [17], where each user independently caches
a subset of mF bits of file i, chosen uniformly at random for i = 1, . . . , N under the memory
constraint of M F bits. By letting Wi|J denote the sub-file of Wi stored exclusively in the cache

5

memories of the user set J, the cache memory Zk of user k after decentralized caching is given
by
Zk = {Wi | J : ∀J ⊆ [K], ∀J 3 k, ∀i ∈ [N ]}.

(1)

Once the user requests are revealed, the server generates and sequentially conveys the codewords
intended to each subset of users. Namely, assuming that user k requests file Wk for all k, the
codeword intended to the subset J is given by
VJ = ⊕k∈J Wk|J\{k} ,

(2)

where ⊕ denotes the bit-wise XOR operation. The main idea here is to create a codeword useful
to a subset of users by exploiting the receiver side information established during the placement
phase. It has been shown for decentralized caching in [17] that the delivery time, or the number
of multicast transmissions, needed to satisfy K distinct demands over the error-free shared link
is
T (m, K) = (1 − m)

1 − (1 − m)K
.
m

(3)

In order to ensure reliable delivery in a wireless channel, the codewords described in (2)
should then be encoded with a proper channel code in the physical layer. In this work, the
physical layer is modeled as a single-antenna quasi-static fading Gaussian broadcast channel.
Specifically, we assume that the channel state remains constant during the transmission of any
channel codeword, or, equivalently, any physical layer frame. Let us focus on the transmission t,
where t can be considered as the frame index. For a given channel codeword x (t) ∈ Cn , user k
receives
q
y k (t) = h̃k (t) x (t) + w k (t),

(4)

x(t)k2 ≤ nP ; {h̃k (t)}k are the fading gains
where the input satisfies the power constraint kx
independently distributed over users1 ; w k (t) ∼ NC (0, In ) is the additive white Gaussian noise
assumed to be independent and identically distributed across time and users. For simplicity, we
define hk = P h̃k assumed to be exponentially distributed with mean γk . We assume that each
user k knows its channel realization hk . In addition, we are particularly interested in the longterm behavior (e.g., time span of hours or days) of the system. To simplify such analysis, we
1

Note that the phase of the channel coefficient is ignored since each receiver can rotate the signal to remove the phase.

6

further assume that the channel coefficient of each user changes to an independent realization
from codeword to codeword according to the same distribution, i.e., hk (t) is i.i.d. over t for a
given k.
It is well-known that the multicast capacity of the channel at hand, or the common message
rate, is given by


h) = log 1 + min hj
Rmc (h
j∈[K]

(5)

and is limited by the user in the worst channel condition. It has been proved in [8] that such
limitation is detrimental for a scalable content delivery network. To see this, let us first define the
sum content delivery rate when coded caching is applied directly to the fading broadcast channel.
In order to satisfy the distinct demands from K users, or to complete in total KF demanded
bits, we need to send T (m, K)F bits over the wireless link. The corresponding transmission
takes

T (m,K)F
h)
Rmc (h

units of time. As a result, the sum content delivery rate of a naive application of

coded caching for a given channel realization h is given by
K
h)
Rmc (h
T (m, K)

(6)

measured in [bits/second/Hz]. For convenience, we call such a naive application as the “baseline” (“bl”) scheme where the base station serves all K users with the multicast rate limited
by the worst user as in (5). The corresponding (long-term) average sum content delivery rate is
given by
Rsum,bl (K) =

K
h)].
E[Rmc (h
T (m, K)

(7)

To gain an insight into the harmful effect, let us consider the case of symmetric fading statistics
h)] vanishes as O(1/K) for K → ∞ [9],
(γk = γ, ∀k). The average multicast capacity E[Rmc (h
the average sum content delivery rate converges to a constant, yielding a non-scalable system.
More precisely, we recall the following result.
Proposition 1. The long-term average sum content delivery rate of baseline scheme is given by
 
K
K
K
γ
Rsum,bl (K) =
e E1
,
(8)
T (m, K)
γ
R +∞ −xt
where we define the exponential integral function E1 (x) = 1 e t dt. As K → ∞, we have
Rsum,bl (K) ∼

γm
.
1−m

(9)

7

Proof. Refer to appendix A.
This negative result motivates us to study some opportunistic scheduling strategy which
benefits both from the coded caching gain and the diversity of the underlying wireless channel,
while ensuring certain fairness among users.
III. P ROBLEM F ORMULATION
In this section, we first review the fading Gaussian broadcast channel where the transmitter
wishes to convey 2K − 1 mutually independent messages, each intended to a subset of users. We
recall the capacity region achieved by superposition encoding and provide the optimal power
allocation. This serves as the ultimate upper bound on the fair scheduling problem. Then, we
formulate our objective function by an alpha-fair family of concave utility functions.
A. Capacity region of the fading Gaussian broadcast channel
In this subsection, we review Theorems 1 and 2 of [6], [7] which serve as the upper bound
of more practical scheduling policies considered shortly. It readily follows that the channel in
(4) for a given channel realization h is a degraded Gaussian broadcast channel. Without loss of
generality, let us assume h1 ≥ · · · ≥ hK . Let us consider that the transmitter wishes to convey
2K − 1 mutually independent messages, denoted by {MJ }, where MJ denotes the message
intended to the users in subset J ⊆ [K]. Each user k must decode all messages {MJ } for J 3 k.
K −1

By letting RJ denote the multicast rate of the message MJ , we say that the rate-tuple R ∈ R2+

is achievable if there exists some encoding and decoding functions such that decoding error
probability can be arbitrarily small with large codeword length n. The capacity region is defined
as the set of all achievable rate-tuples and is given by the following theorem.
h) of a K-user degraded Gaussian broadcast channel with
Theorem 1. The capacity region Γ (h
fading gains h1 ≥ · · · ≥ hK and 2K − 1 independent messages {MJ } is given by
P
X
1 + hk kj=1 βj
, k = 2, . . . , K,
RK ≤ log
P
1 + hk k−1
j=1 βj
K:k∈K⊆[k]
for non-negative variables {βk } such that

PK

k=1

(10)

βk ≤ 1.

Proof. The proof is quite straightforward and is based on rate-splitting and the private-message
region of degraded broadcast channel. For completeness, see details in Appendix B.

8

h), we consider the weighted
In order to characterize the boundary of the capacity region Γ (h
sum rate maximization given as
X

max

h)
r ∈Γ (h

θJ rJ .

(11)

J:J⊆[K]

By exploiting a simple property of the capacity region, the problem at hand can be cast into a
simpler problem as summarized below.
Theorem 2. The weighted sum rate maximization with 2K − 1 variables in (11) reduces to a
simpler problem with K variables, given by
f (β) =

K
X

θ̃k log

k=1

1 + hk

Pk

βj

1 + hk

Pk−1

βj

j=1

j=1

,

(12)

where θ̃k denotes the largest weight for user k
θ̃k =

max θK .

(13)

K:k∈K⊆[k]

Proof. Refer to Appendix C.
B. Application to coded caching
By performing coded caching to the user subset J, the total number of bits to be multicast
to satisfy |J| distinct demands is equal to T (m, |J|)F . By letting RJ denote the multicast rate
of the codewords intended to user subset J, the per-user rate after applying coded caching to
subset J is given by

1
R
T (m,|J|) J

for any user in J. By simultaneously applying coded caching

over different subset of users, the per-user data rate is given by
X
1
RJ .
Uk =
T (m, |J|)

(14)

J:k∈J⊆[K]

Using (14), the weighted sum of the individual user rates

PK

k=1 τk Uk ,

for any {τk }1≤k≤K , can

be rewritten as:
K
X

τk Uk =

k=1

K
X

τk

k=1

=

J:k∈J⊆[K]

X
J:J⊆[K]

1
RJ
T (m, |J|)

(15)

τk
RJ
T (m, |J|)
k:k∈J

(16)

θJ RJ ,

(17)

X X
J:J⊆[K]

=

X

9

where θJ =

P

k:k∈J τk
.
T (m,|J|)

Hence the problem can be reduced to that of the previous subsection.

Throughout the paper we use three facts concerning the mapping T which are stated below.
Property 1. T (m, k) converges to T (m, ∞) ,

1−m
m

when k → ∞. The larger m is, the faster

it converges.
Property 2. T (m, k) is an increasing function of k and so T (m, 1) ≤ T (m, k) ≤ T (m, ∞).
Property 3.

k
T (m,k)

is an increasing function of k.

C. Objectives
Since implementing superposition encoding is complex, we now restrain ourselves to practical
schemes which, for each channel realization h , select a group of users J ⊂ {1, ..., K} to perform
the delivery scheme of [17] to J at rate log(1 + minj∈J hj ). Consider π a scheduling policy,
which is a mapping from (R+ )K to the set of subsets of {1, ..., K}. For a channel realization
h) ⊂ {1, . . . , K} for transmission,
h = (h1 , . . . , hK ), the policy π chooses a group of users Jπ (h
where the transmission strategy is the one described in previous sections. We denote by Π the
set of admissible policies. Given the policy π and channel realization h , user i is served at the
rate given by


h)}
1{i ∈ Jπ (h
log 1 + min
hj ,
h)
h)|)
j∈Jπ (h
T (m, |Jπ (h

(18)

h)| and the minimal channel
so that the rate depends on both the size of the selected group |Jπ (h
gain minj∈Jπ (hh) hj among the chosen users. It is noted that for a fixed value of minj∈Jπ (hh) hj ,
h)| due to Property 2, while for a
the rate (18) is a decreasing function of the group size |Jπ (h
fixed group size, the rate (18) is an increasing function of minj∈Jπ (hh) hj .
Under policy π, the long-term average rate of user i is the expectation of the instantaneous
data rate over the channel realizations h :


h)}
1{i ∈ Jπ (h
π
log(1 + min
hj ) .
Ui = E
h)
h)|)
j∈Jπ (h
T (m, |Jπ (h
We are interested in utility-optimal scheduling, where the goal is to maximize some utility
function of the long-term rates. We restrict our attention to α-fair allocations [16], namely,
(
)
K
X
1
π ? ∈ argmax
gα (Uiπ )
(19)
K i=1
π∈Π

10

with
gα (x) =



 x1−α −1 ,

if α 6= 1,


log(x),

if α = 1.

1−α

It is noted that α 7→ gα (x) is continuous for any fixed x since limα→1

x1−α −1
α−1

= log(x). It is also

noted that α = 0 corresponds to the sum rate maximization gα (x) = x − 1, α = 1 corresponds
to proportional fairness gα (x) = log(x), and α → +∞ corresponds to max-min fairness.
IV. FAIR SCHEDULING
In this section we study scheduling algorithms for our setting, where, for each channel
realization, a group of users are selected for transmission, with the goal of maximizing some
utility function of the long term user rates.
A. Optimal policy
The optimal policy π ? depends only on the channel gain statistics, γ1 , ..., γK , however it is
usually impractical to compute it due to the difficulty to maximize over π ∈ Π. A practical approach is to use an iterative scheme. Assume that time is slotted, where h (t) = (h1 (t), ..., hK (t))
is the vector of channel gains at time t. Consider the iterative algorithm which at time slot t
selects the group:
(
h(t), t) ∈ argmax
J(h
J⊆[K]

K

X 1{i ∈ J}
1
log(1 + min hj (t))
j∈J
T (m, |J|)
ui (t)α
i=1

)
,

(20)

where u (t) = (u1 (t), ..., uK (t)) is the vector of empirical data rates up to time t, and obeys the
recursive equation:


h(t), t)}
1
1{i ∈ J(h
ui (t + 1) =
tui (t) +
log(1 + min hj (t)) .
h,t)
h(t), t))|)
j∈J(h
t+1
T (m, |J(h
Proposition 2. Under the above scheme u (t) converges almost surely to a utility optimal
allocation:

K
1 X
gα (ui (t)) →a.s.
t→∞ max
π∈Π
K i=1

(

)
K
1 X
gα (Uiπ ) .
K i=1

Proof. The above scheme is an example of a general class of schemes called gradient scheduling
schemes. The above result follows from a straightforward application of the results of [18] which
proves the asymptotic optimality of gradient scheduling schemes.



11

Therefore, utility-optimal scheduling can be achieved simply by applying the above scheme
during a large number of time slots. By corollary, we deduce an alternative characterization of
the optimal policy which is essential to prove our main result.
Corollary 1. The following scheme yields a utility optimal scheduling:
)
(
K
X
1{i ∈ J}
1
?
h) ∈ argmax
log(1 + min hj )
.
J (h
?
j∈J
T (m, |J|)
(Uiπ )α
J
i=1
Proof. The result holds as a consequence of proposition 2, by letting t → ∞ in (20). Equation
(20) indeed defines which group is selected by the above iterative scheme as t → ∞.



B. Threshold policies and complexity
We also introduce a sub-class of policies called threshold policies. We say that policy π ∈ Π
is a threshold policy with threshold c if, for any channel realization h it selects all users with a
channel gain larger than c, that is:
h) = {i = 1, . . . , K : hi ≥ c}.
Jπ (h
While threshold policies are in general suboptimal, they can be implemented with minimal
complexity. Indeed, computing the solution of (20) can be done in time O(K 2 ), by sorting h and
searching over the possible values of |J| and minj∈J hj (see appendix D for more details). On
the other hand, computing a threshold policy requires O(K) time. Furthermore, while computing
(20) requires all users to report the value of their channel gain h1 (t), ..., hK (t) up to a given
accuracy, implementing a threshold policy simply requires user to report 1 bit of information
which is 1{hi (t) ≥ c}.
Surprisingly, as stated in Theorem 3 of next section, a well designed threshold policy in fact
become optimal when the number of users K grows large, so that utility optimal scheduling can
be achieved with both linear complexity O(K) and 1-bit feedback.
V. FAIR SCHEDULING FOR A LARGE NUMBER OF USERS
In this section, we consider utility optimal scheduling when the number of users K grows
large. We show that threshold policies become optimal in this regime. Our result is general and
applies to any value of α ≥ 0 as well as heterogeneous users where the channel gains statistics
γ1 , ..., γK are arbitrary as long as they are bounded. We denote by γ = mini γi and γ = maxi γi .
As a corollary, we compute the optimal threshold policy in closed form as a function of γ1 , ..., γK ,
so that the system is indeed tractable.

12

A. Main result
We first state Theorem 3, the main technical contribution of this work. That is, as the number
of users grows large (K → ∞), a well designed threshold policy become utility optimal, and
that the optimal threshold may be derived explicitly as a function of the channel gains statistics
γ1 , ..., γK .
Theorem 3. Consider the solution of the optimization problem:
(
)
K


X
c
1
−
gα log(1 + c)e γi
,
c? ∈ argmax
K
c≥0
i=1

(21)

and π the threshold policy with threshold c? . Then the long term data rates under π are:
Uiπ =

?
1
−c
log(1 + c? )e γi + o(1) , K → ∞.
T (m, ∞)

Furthermore, π is asymptotically optimal, in the sense that:
)
(
K
K
X
1 X
1
gα (Uiπ ) = max
gα (Uiπ ) + o(1) , K → ∞.
π∈Π
K i=1
K i=1
The proof of theorem 3 is long and technical, and is fully detailed in the next subsections. A
summary of the proof technique is found in subsection V-F.
B. Optimal threshold
We now show that, for α ≥ 1 the optimal threshold defined in (21) reduces to the maximization
of a concave function, so that it can be computed efficiently using a local search method such
as Newton’s method.
Proposition 3. Consider c? the optimal threshold as defined in (21). For α = 1, the optimal
threshold is given by:
PK

c? = eW0 (K(

i=1 (1/γi ))

−1

) − 1,

with W0 the Lambert W function. For α ≥ 1, the optimal threshold is the unique solution to the
equation:
PK

i=1

(1 + c) log(1 + c) = P
K

e

−

c(1−α)
γi

1 −
i=1 γi e

c(1−α)
γi

.

13

Proof. In all cases, it is noted that 0 < c? < ∞. Consider α = 1. By definition, since gα (x) =
log(x):
(

)
K
X
c
1
−
gα (log(1 + c)e γi ) ,
c? ∈ argmax
K i=1
c≥0
(
)
K
c X 1
.
= argmax log log(1 + c) −
K i=1 γi
c≥0
Since c 7→ log log(1 + c) is strictly concave, mapping c 7→ log log(1 + c) − Kc

PK

1
i=1 γi

is strictly

concave, hence it admits a unique local maximum which is c? . The optimal threshold c? is thus
the unique point at which the derivative is null. Differentiating we get:
!−1
K
X
1
.
(1 + c? ) log(1 + c? ) = K
γ
i=1 i
The result follows by definition of the Lambert function W0 .
Now consider α > 1, so that 1 − α < 0. By definition, since gα (x) =
)
(
K
X
c
1
−
gα (log(1 + c)e γi ) ,
c? ∈ argmax
K i=1
c≥0
(K
)
X
c(1−α)
−
= argmin
log(1 + c)1−α e γi
,
c≥0

x1−α −1
:
1−α

i=1

(
= argmin (1 − α) log log(1 + c) + log
c≥0

K
X

c(1−α)
− γ
i

e

!)
,

i=1

where we took the logarithm to obtain the last expression. Now, since α > 1, c 7→ (1 −
P
c(1−α) 
− γ
K
i
(log-sum-exp function, see [19]).
α) log log(1 + c) is convex, and so is c 7→ log
i=1 e
Hence the above admits a single local minimum, which equals c? and may be found by solving:
PK − c(1−α)
e γi
(1 + c) log(1 + c) = P i=1
.
c(1−α)
K 1 − γ
i
i=1 γi e

C. Proof element 1: lower bound on the rates
The first step towards proving Theorem 3 is to show that the rates allocated by α-fair schedul?

?

ing are upper and lower bounded by two constants, so that mini 1/(Uiπ )α and maxi 1/(Uiπ )α
are of the same order even as K → ∞. This is in fact the step of the proof which is the most
involved.

14

Proposition 4. There exists 0 < C1 (γ, γ) < C2 (γ, γ) < ∞ such that for all K ≥ 0 and all
i = 1, . . . , K:
?

C1 (γ, γ) ≤ Uiπ ≤ C2 (γ, γ).
?

?

Proof. Without loss of generality, we may order users to ensure U1π ≤ ... ≤ UKπ . Throughout
?

the proof we consider the optimal policy π ? and, to ease notation, we denote Uiπ by Ui . We
define the function:
K

X 1{i ∈ J}
1
f (J, h ) =
log(1 + min hj )
.
j∈J
T (m, |J|)
(Ui )α
i=1

(22)

As shown in corollary 1, under the optimal policy π ? , the chosen group is
h) ∈ arg
J? (h

max

J⊂{1,...,K}

f (J, h ).

As a first step, we control the chosen group J? , in an alternative system when user 1 is ignored. We
h) ∈ arg maxJ⊂{2,...,K} f (J, h ), the maximizer of f if user 1 is ignored. Denote by Ū =
define J?1 (h
PK
Ū
1
i=2 (Ui )α , the sum of weights of all users except user 1. Define z = 2T (m,∞) log(1 + γ log 2).
We now prove the following inequality:
h), h ) ≤ z) ≤
P (f (J?1 (h

1
.
2

h) = {i ≥ 2 : hi ≥ γi log 2}. Let us lower bound f (J1 (h
h), h ). By definition,
Define the group: J1 (h
h) implies hj ≥ γj log 2 ≥ γ log 2, hence:
j ∈ J1 (h
log(1 + γ log 2) ≤ log(1 + min hj ),
h)
j∈J1 (h

h)), we obtain the lower bound:
and further using Property 2 implying T (m, ∞) > T (m, J1 (h
K

X 1{hi ≥ γi log 2}
1
h), h ).
log(1 + γ log 2)
≤ f (J1 (h
T (m, ∞)
(Ui )α
i=2
Define the random variable:
K

X 1{hi ≥ γi log 2}
1
.
Z=
log(1 + γ log 2)
T (m, ∞)
(Ui )α
i=2
h), we have f (J?1 (h
h), h ) ≥ f (J1 (h
h), h ), so that:
By definition of J?1 (h
h), h ) ≤ f (J?1 (h
h), h ).
Z ≤ f (J1 (h

15

Since hi follows an exponential distribution with mean γi , we have P(hi ≥ γi log 2) =

1
2

and

since the channel realizations are independent across users, the random variables 1{hi ≥ γi log 2}
and 1{hi0 ≥ γi0 log 2} are independent whenever i 6= i0 . Therefore:
K

X P(hi ≥ γi log 2)
1
log(1 + γ log 2)
E(Z) =
= z,
α
T (m, ∞)
(U
)
i
i=2
and Z is a weighted sum of Bernoulli independent random variables with mean

1
2

so that Z is

symmetrical, i.e. Z −z has the same distribution as z −Z. Therefore: P(Z ≤ z) = P(Z ≥ z) =

1
2

and:
h), h ) ≤ z) ≤ P(Z ≤ z) =
P (f (J?1 (h

1
.
2

We now control the value of mini∈J?1 (hh) hi . Choose any c1 , c2 such that both of the conditions
below are satisfied:
T (m, 1)
(i) log(1 + c1 ) <
log(1 + γ log 2); and
2T (m, ∞)
R∞
2T (m, ∞) c2 (log(1 + y)/γ)e−y/γ dy
1
≤ .
(ii)
T (m, 1) log(1 + γ log 2)
4
It is noted that we may indeed choose c1 , c2 in that way since c 7→ log(1 + c) is increasing and
R∞
vanishes for c = 0, and since c 7→ c (log(1 + y)/γ)e−y/γ dy is decreasing and vanishes for
c → ∞. It is also noted that c1 c2 may be chosen only based on the value of γ and γ and m.
h), h ) ≥ z. If this event occurs, using the facts
Assume that mini∈J?1 (hh) hi ≤ c1 and that f (J?1 (h
h)|) ≥ T (m, 1) since Property 2,
that (a) log(1 + mini∈J?1 (hh) hi ) ≤ log(1 + c1 ), and (b) T (m, |J?1 (h
PK 1{i∈J?1 (hh)}
and (c) that i=1 (Ui )α ≤ Ū , we obtain the upper bound:
h), h ) ≤
f (J?1 (h

Ū
log(1 + c1 ).
T (m, 1)

h), h ) ≥ z we have z ≤
In summary, if mini∈J?1 (hh) hi ≤ c1 and f (J?1 (h

Ū
T (m,1)

log(1 + c1 ) and

replacing z with its definition:
Ū
Ū
log(1 + γ log 2) ≤
log(1 + c1 ),
2T (m, ∞)
T (m, 1)
which is equivalent to
T (m, 1)
log(1 + γ log 2) ≤ log(1 + c1 ),
2T (m, ∞)
h), h ) ≥ z implies
a contradiction with (i) the definition of c1 . We have hence proven that f (J?1 (h
mini∈J?1 (hh) hi ≥ c1 .

16

h), h) ≥ z. If this event occurs, using the
Now assume that mini∈J?1 (hh) hi ≥ c2 and that f (J?1 (h
facts that
h)}
h)} ≤ log(1 + hi )1{i ∈ J?1 (h
(a) log(1 + min
hj )1{i ∈ J?1 (h
?
h)
j∈J1 (h

≤ log(1 + hi )1{hi ≥ c2 },
h)|) ≥ T (m, 1) since Property 2, we obtain
h) implies hi ≥ c2 , and (b) T (m, |J?1 (h
since i ∈ J?1 (h
the upper bound:
h), h ) ≤
f (J?1 (h

X log(1 + hi )1{hi ≥ c2 }
1
≡ Z 0.
α
T (m, 1) i≥2
(Ui )

h), h ) ≤ Z 0 . Let us upper
h), h ) ≥ z implies z ≤ f (J?1 (h
In summary mini∈J?1 (hh) hi ≥ c2 and f (J?1 (h
bound the expectation of Z 0 . Since hi has exponential distribution with mean γi we have:
Z ∞
E(log(1 + hi )1{hi ≥ c2 }) =
(log(1 + y)/γi )e−y/γi dy
c
Z 2∞
≤
(log(1 + y)/γ)e−y/γ dy.
c2

Hence:
E(Z 0 ) ≤

Ū

R∞
c2

(log(1 + y)/γ)e−y/γ dy
T (m, 1)

.

Using Markov’s inequality, we get:
0

P (Z ≥ z) ≤

≤

2T (m, ∞)

E(Z 0 )

z
R∞
c2

(log(1 + y)/γ)e−y/γ dy

T (m, 1) log(1 + γ log 2)

1
≤ ,
4
using the definition of c2 for the final inequality.

17

In conclusion, we have proven that:




?
h), h ) ≤ z
P min
hi 6∈ [c1 , c2 ] = P min
hi 6∈ [c1 , c2 ]; f (J1 (h
h)
h)
i∈J?1 (h
i∈J?1 (h


?
h), h ) ≥ z
+ P min
hi 6∈ [c1 , c2 ]; f (J1 (h
h)
i∈J?1 (h


?
?
h), h ) ≥ z
h), h ) ≤ z) + P min
hi 6∈ [c1 , c2 ]; f (J1 (h
≤ P (f (J1 (h
h)
i∈J?1 (h


?
?
h), h ) ≥ z
h), h ) ≤ z) + P min
hi ≥ c2 ; f (J1 (h
= P (f (J1 (h
?
h)
i∈J1 (h

≤ P (Z ≤ z) + P (Z 0 ≥ z)
≤

1 1
3
+ = ,
2 4
4

hence:

P


min
hi ∈ [c1 , c2 ]
?

h)
i∈J1 (h

1
≥ .
4

The second step involves lower bounding U1 , using the previous result on the fluctuations of
h) depends solely on h2 , ..., hK ,
mini∈J?1 (hh) hi . We will use the four following facts: (a) Since J?1 (h
the event mini∈J?1 (hh) hi ∈ [c1 , c2 ] is independent of h1 , (b) When both mini∈J?1 (hh) hi ∈ [c1 , c2 ],
h) since
and h1 > c2 , then 1 ∈ J? (h

1
(U1 )α

≥ maxi≥2

1
(Ui )α

and mini∈J? (hh) hi ≤ c2 ≤ h1 . Indeed,

h), for any i ∈ J? (h
h) we have f (J? (h
h) \ {i} ∪ {1}, h) > f (J? (h
h), h), a contradiction
if 1 6∈ J? (h
h) is a maximizer of J 7→ f (J, h ), (c) Since h1 has exponential distribution with mean
since J? (h
h)|) ≤ T (m, ∞) since
γ1 ≥ γ, P(h1 ≥ c2 ) = e−c2 /γ1 ≥ e−c2 /γ and (d) We have T (m, |J? (h
Property 2.
Putting (a), (b), (c) and (d) together we get:
1
log(1 + c1 )P( min
hi ∈ [c1 , c2 ], h1 ≥ c2 )
h)
i∈J?1 (h
T (m, ∞)
1
log(1 + c1 )P( min
hi ∈ [c1 , c2 ])P(h1 ≥ c2 )
=
h)
i∈J?1 (h
T (m, ∞)
1
1
≥
log(1 + c1 )e−c2 /γ ≡ C1 (γ, γ).
T (m, ∞) 4

U1 ≥

18

Furthermore, for any i = 1, ..., K:
1
E(log(1 + hi ))
T (m, 1)
1
≤
log(1 + E(hi ))
T (m, 1)
1
log(1 + γi )
=
T (m, 1)
1
≤
log(1 + γ) ≡ C2 (γ, γ).
T (m, 1)

Ui ≤

We have proven that:
C1 (γ, γ) ≤ Ui ≤ C2 (γ, γ)
for all i = 1, ..., K and all K as announced.



D. Proof element 2: asymptotic size of J
h) of large
From the first proof element we deduce the second one, that is, only groups J? (h
size are chosen with high probability as the number of users grows. In turn this implies that
P

h)|) → T (m, ∞). This result is important, since it allows to take T (m, |J? (h
h)|) out
T (m, |J? (h
K→∞

of the equation when it comes to controlling which users are selected by the optimal policy.
Proposition 5. For all J ≥ 0 we have:
h)| ≥ J) → 1.
P(|J? (h
K→∞

P

h)|) → T (m, ∞).
Furthermore, T (m, |J? (h
K→∞

Proof. Consider the following group of users:
h) = {i ≥ 1 : hi ≥ γi log 2}.
J(h
h), h) =
Let us lower bound the value of f (J(h

1
T (m,|J|)

log(1 + minj∈J hj )

PK

1{i∈J}
i=1 (Ui )α

as defined

h)) ≤ T (m, ∞) due to Property 2, (b) i ∈ J(h
h) implies
in (22). Using the facts that (a) T (m, J(h
hi ≥ γi log 2 ≥ γ log 2 so that mini∈J(hh) hi ≥ γ log 2 and (c) Ui ≤ C2 (γ, γ) so that
1
C2 (γ,γ)α

we obtain the lower bound:
K
log(1 + γ log 2) X
h), h ).
1{hi ≥ γi log 2} ≤ f (J(h
C2 (γ, γ)α T (m, ∞) i=1

1
(Ui )α

≥

19

h), h), using the facts that (a) T (m, J(h
h)) ≥ T (m, 1) due
Let us upper bound the value of f (J? (h
to Property 1, (b) Ui ≥ C1 (γ, γ) so that

1
(Ui )α

≤

1
C1 (γ,γ)α

and (c) mini∈J? (hh) hi ≤ maxi=1,...,K hi ≤

γ maxi=1,...,K (hi /γi ) we obtain:
h), h ) ≤ |J? (h
h)|
f (J? (h

log(1 + γ maxi=1,...,K (hi /γi ))
.
C1 (γ, γ)α T (m, 1)

h) is a maximizer of J 7→ f (J, h ) we have f (J(h
h), h ) ≤ f (J? (h
h), h ), and the two
Since J? (h
previous inequalities imply:
T (m, 1)
log(1 + γ log 2)
T (m, ∞)



C1 (γ, γ)
C2 (γ, γ)

α

PK

1{hi ≥ γi log 2}
h)|.
≤ |J? (h
log(1 + γ maxi=1,...,K (hi /γi ))
i=1

To finish the proof, we prove that:
PK

1{hi ≥ γi log 2}
a.s.
→ ∞.
log(1 + γ maxi=1,...,K (hi /γi )) K→∞
i=1

Since h1 /γ1 , ..., hK /γK are i.i.d exponentially distributed with mean 1, we have P(hi ≥ γi log 2) =
1
2

and the law of large numbers gives:
K
1 X
P 1
1{hi ≥ γi log 2} → .
K→∞ 2
K i=1

Since

1
4

< 21 , we have for K → ∞, with high probability,
K
X

1{hi ≥ γi log 2} ≥

i=1

K
.
4

Furthermore,
P( max (hi /γi ) ≥ 2 log K) = 1 − P( max (hi /γi ) ≤ 2 log K)
i=1,...,K

i=1,...,K

=1−

K
Y

P(hi /γi ≤ 2 log K)

i=1



1
=1− 1− 2
K

K
→ 0.

K→∞

Thus for K → ∞, with high probability, we have
max (hi /γi ) ≤ 2 log K.

i=1,...,K

Hence, the following occurs with high probability:

α
T (m, 1) C1 (γ, γ)
K
h)|.
log(1 + γ log 2)
≤ |J? (h
T (m, ∞) C2 (γ, γ)
log(1 + 2γ log K)

20

Since

K
→
log log K K→∞

∞, this implies that, for all J ≥ 0:
h)| ≥ J) → 1.
P(|J? (h
K→∞

Therefore, for any J ≥ 0:
h)|) ≤ T (m, ∞)) → 1.
P (T (m, J) ≤ T (m, |J? (h
K→∞

This holds for all J, which proves the second statement.



E. Proof element 3: convergence to a deterministic equivalent
The last proof element is to show that, when K → ∞, maximizing f (J, h ) reduces to a
simpler, deterministic optimization problem, which we call a “deterministic equivalent” of the
original problem. Define the following mapping:
K
1 X 1{i ∈ J}
φ(J, h ) = log(1 + min hj )
,
j∈J
K i=1 (Ui )α

which corresponds to the value of

T (m,∞)
f (J, h )
K

when |J| goes to infinity. Further define ψ:

K
1 X 1{hi ≥ c}
,
ψ(c, h ) = log(1 + c)
K i=1 (Ui )α

which is the value of φ when selecting only users whose channel realization is larger than c. It
is noted that when K → ∞, we have
max

J⊂{1,...,K}

φ(J, h ) = max ψ(c, h ).
c≥0

Indeed, if minj∈J hj = c for some c, then all users i such that hi ≥ c should be included in J
in order to maximize φ(J, h ). Hence maximizing φ(J, h ) over all subsets of users J reduces to
a simple, one-dimensonnal search over the value of minj∈J hj = c, that is maximizing ψ(c, h )
over c ≥ 0. We are now left to control the value of the random quantity maxc≥0 ψ(c, h ), which
is not straightforward since its maximizer arg maxc≥0 ψ(c, h ) is typically a random variable as
well. For a fixed value of c, we define Ψ (c) which is the expected value of ψ(c, h):
K
1 X e−c/γi
Ψ (c) = E(ψ(c, h )) = log(1 + c)
.
K i=1 (Ui )α

We will show that Ψ constitutes a deterministic equivalent, in the sense that maximizing ψ(c, h )
over c ≥ 0 for a fixed value of h yields, asmptotically with high probability, the same outcome
as maximizing Ψ (c) over c ≥ 0. In other words, a concentration phenomenon occurs as the

21

number of users grows large and channel opportunism does yield any gains over choosing all
users whose channel realization is above a fixed threshold.
Proposition 6. We have:
P

max ψ(c, h ) → max Ψ (c).
c≥0

K→∞ c≥0

Proof. We first show that, for any fixed c, ψ(c, h) is concentrated around Ψ (c) when K → ∞.
Since (a) the channel realizations h1 , ..., hK are independent across users, and (b) var(1{hi ≥
c}) ≤ 1, and (c) Ui ≥ C1 (γ, γ) for i = 1, ..., K, we have:
var(ψ(c, h )) =
≤

K
log(1 + c)2 X var(1{hi ≥ c})
K2
(Ui )2α
i=1

log(1 + c)2
→ 0.
KC1 (γ, γ)2α K→∞

Hence, Chebychev’s inequality proves that
P

ψ(c, h ) → E(ψ(c, h )) = Ψ (c).
K→∞

We may now lower bound maxc≥0 ψ(c, h ) as follows. Consider c̃ ∈ arg maxc≥0 Ψ (c), then we
P

have ψ(c̃, h ) ≤ maxc≥0 ψ(c, h ) and since ψ(c̃, h ) → Ψ (c̃) = maxc≥0 Ψ (c), this proves that, for
K→∞

all  > 0:


P max Ψ (c) −  ≤ max ψ(c, h)
→ 1.
c≥0

c≥0

K→∞

We now upper bound maxc≥0 ψ(c, h). We do so by splitting [0, +∞) into a finite number of
intervals and control the behaviour of c 7→ ψ(c, h ) in those intervals. Consider  > 0 fixed.
Define δ > 0, and L ≥ 0 such that both of the following conditions
Z ∞
1
(i)
(log(1 + y)/γ)e−y/γ dy ≤
C1 (γ, γ)α Lδ

are satisfied:

,
2

δ

≤ .
α
C1 (γ, γ)
2
R∞
Such a choice is always possible since Lδ (log(1 + y)/γ)e−y/γ dy vanishes for Lδ → ∞. Further
(ii)

define:
m` =



maxc∈[(`−1)δ,`δ] ψ(c, h )

if ` = 1, ..., L


maxc∈[Lδ,+∞) ψ(c, h )

if ` = L + 1.

It is noted that m1 , ..., mL+1 are random variables and that:
max ψ(c, h ) =
c≥0

max

`=1,...,L+1

m` .

22

We may now upper bound the value of each m` individually. First consider c ∈ [(` − 1)δ, `δ],
then we have:
K
1 X 1{hi ≥ (` − 1)δ}
ψ(c, h ) ≤ log(1 + `δ)
.
K i=1
(Ui )α

= ψ((` − 1)δ, h )
K
1 X 1{hi ≥ (` − 1)δ}
+ (log(1 + `δ) − log(1 + (` − 1)δ))
K i=1
(Ui )α

δ
,
C1 (γ, γ)α

≤ ψ((` − 1)δ, h) + ,
2
≤ ψ((` − 1)δ, h ) +

since c 7→ log(1+c) is increasing, c 7→ 1{hi ≥ c} is decreasing, log(1+`δ) ≤ log(1+(`−1)δ)+δ,
and Ui ≥ C1 (γ, γ) for i = 1, ..., K. We have proven that:
m` ≤ ψ((` − 1)δ, h ) +


, ` = 1, ..., L
2

and since
P

ψ((` − 1)δ, h) → Ψ ((` − 1)δ) ≤ max Ψ (c) , ` = 1, ..., L,
c≥0

K→∞

we have that:
P(m` ≤ max Ψ (c) + ) → 1 , ` = 1, ..., L.
c≥0

K→∞

Now consider c ∈ [Lδ, ∞). We have the upper bound:
ψ(c, h ) ≤

K
X
1
log(1 + hi )1{hi ≥ Lδ} ≡ Y,
KC1 (γ, γ)α i=1

using the fact that Ui ≥ C1 (γ, γ) for i = 1, ..., K and:
log(1 + c)1{hi ≥ c} ≤ log(1 + hi )1{hi ≥ c}
≤ log(1 + hi )1{hi ≥ Lδ}.

23

Hence mL+1 ≤ Y , and we control the first and second moment of Y to show that Y is
concentrated around its expectation. By definition of L and δ, since hi has exponential distribution
with mean γi :
K
X
1
E(Y ) =
E(log(1 + hi )1{hi ≥ Lδ})
KC1 (γ, γ)α i=1
K Z ∞
X
1
(log(1 + y)/γi )e−y/γi dy,
=
KC1 (γ, γ)α i=1 Lδ
Z ∞
1
≤
(log(1 + y)/γ)e−y/γ dy
α
C1 (γ, γ) Lδ

≤ ,
2

and since h1 , ..., hK are independent:
K

X
1
var(Y ) = 2
var(log(1 + hi )1{hi ≥ Lδ})
K C1 (γ, γ)2α i=1
Z +∞
1
≤
(log(1 + y)2 /γ)e−y/γ dy → 0
2α
K→∞
KC1 (γ, γ)
0
using the fact that for i = 1, .., .K:
var(log(1 + hi )1{hi ≥ Lδ}) ≤ E(log(1 + hi )2 1{hi ≥ Lδ}2 )
≤ E(log(1 + hi )2 )
Z +∞
(log(1 + y)2 /γi )e−y/γi dy
=
0
Z +∞
≤
(log(1 + y)2 /γ)e−y/γ dy.
0

Hence Chebychev’s inequality shows that Y

P

→ E(Y ) ≤ 2 , from which we deduce:

K→∞

P(mL+1 ≤ ) → 1.
K→∞

So combining both cases, we have that:
P(m` ≤ max Ψ (c) + ) → 1 , ` = 1, .., L + 1.
c≥0

K→∞

We have proven that, for all  > 0:
P(max Ψ (c) −  ≤ max ψ(c, h ) ≤ max Ψ (c) + ) → 1,
c≥0

P

c≥0

and maxc≥0 ψ(c, h ) → maxc≥0 Ψ (c) as announced.
K→∞

c≥0

K→∞



24

F. Putting it all together
We now complete the proof of Theorem 3. From proposition 6, asymptotically with high
probability, utility optimal scheduling can be realized by selecting a threshold policy, where
the threshold c? is a maximizer of the deterministic mapping Φ. Under a theshold policy with
threshold c? , the rate of user i is given by:


1
?
?
log(1 + c )1{hi ≥ c } ,
Ui = E
T (m, J(c? ))
where J(c? ) is the number of users whose channel realization is above c? :
K
X

?

J(c ) =

1{hi ≥ c? }.

i=1

We have:

Ui − E

1
log(1 + c? )1{hi ≥ c? }
T (m, ∞)



?

≤ log(1 + c )E



1
1
−
T (m, ∞) T (m, J(c? ))

From the law of large numbers:
K
?
J(c? )
1 X
−c
a.s.
≥
1{γ(hi /γi ) ≥ c? } → e γ > 0,
K→∞
K
K i=1
a.s.

therefore J(c? ) → ∞. Hence
K→∞

1
1
a.s.
→
?
T (m, J(c )) K→∞ T (m, ∞)
and

E

1
T (m, J(c? ))


≤

1
, K ≥ 1,
T (m, 1)

so we apply Lebesgue’s theorem to yield:


1
1
E
−
→ 0.
T (m, ∞) T (m, J(c? )) K→∞
We have proven that:

Ui → E
K→∞

=

1
log(1 + c? )1{hi ≥ c? }
T (m, ∞)

?
1
−c
log(1 + c? )e γi .
T (m, ∞)




.

25

The value of c? may be retrieved from the fact that applying theshold policy with threshold c?
P
maximizes the utility K1 K
i=1 gα (Ui ), hence:
(
!)
K
− γc
X
i
1
log(1
+
c)e
c? ∈ argmax
gα
,
K i=1
T (m, ∞)
c≥0
(
)
K

1 X 
− γc
= argmax
gα log(1 + c)e i
.
K i=1
c≥0
This completes the proof of Theorem 3.
VI. N UMERICAL E XPERIMENTS
In this section, we illustrate the performance of the various schemes defined in the previous
sections through numerical experiments. For each scheme, we compute the long term average
P
data rates of each user U1 , ..., UK , and the corresponding utility K1 K
i=1 gα (Ui ), which is our
objective function. The considered schemes are recalled below.
•

Superposition: At each slot t, this scheme solves the weighted sum rate maximization
K −1

h(t)) ⊆ R2+
problem in Γ (h

, using Theorem 2:
1
i∈J uα
i (t)

P
R sp (h
h(t), t) = arg max

R∈Γ (h
h(t))

X
J:J⊆[K]

θJ (t)RJ with θJ (t) =

T (m, |J|)

,

where ui (t) is the mean empirical rate up to time t for user i. The average rate of user i is
"
#
X
1
h(t), t) .
Usp,i = lim E
Rsp,J (h
t→∞
T
(m,
|J|)
J:i∈J
•

Selection with full CSIT: At each slot t, this scheme selects the subset of users
(
)
K
X
1
1{i ∈ J}
h(t), t) = argmax
Jsc (h
log(1 + min hj (t))
.
α
j∈J
T (m, |J|)
u
(t)
i
J⊆[K]
i=1
The average rate of user i is:


1
h(t), t)} .
log(1 + min hj (t))1{i ∈ Jsc (h
Usc,i = lim E
t→∞
h(t),t)
h(t), t)|)
j∈Jsc (h
T (m, |Jsc (h

•

h(t)) =
Threshold-based selection: At each slot t, this scheme selects the subset of users Jth (h
{i : hi (t) ≥ c? }, where c? is the threshold given by (21), and depends only on the channel
statistics γ1 , ..., γK . The average rate of user i is:


1
h(t))} .
Uth,i = E
log(1 + min hj (t))1{i ∈ Jth (h
h(t))
h(t))|)
j∈Jth (h
T (m, |Jth (h

26

•

Baseline: At each slot t, this scheme selects the subset of users {1, ..., K}, and the average
rate of user i is:
Ubl,i



1
=
E log(1 + min hj (t)) .
1≤j≤K
T (m, K)

In all scenarios, we divide users into two classes of K/2 users each: strong users with γk = P
and weak users with γk = 0.2P . For each figure we consider a normalized cache size of
m = [0.1, 0.6]. In Figs. 2, 4 and 6 we plot the utility versus K for α = 0, α = 1 and α = 2
respectively at P = 10 dB. In Figs. 3, 5 and 7 we plot the utility versus P for α = 0, α = 1
and α = 2 respectively with K = 20 users. We draw the following conclusions:
•

Complexity: As seen in Figs. 2 and 3, superposition encoding outperforms all the others
schemes at the price of a very high complexity of O(2K ) compared to other schemes whose
complexity is polynomial: O(K 2 ) for the selection scheme with full CSIT and O(K) for
the threshold-based selection scheme.

•

Number of users K: From Figs. 2, 4 and 6, the performance of the threshold-based scheme is
as good as full CSIT selection scheme for a sufficiently large K, as predicted by Theorem 3.
In Fig. 2, corresponding to α = 0, the average per user rate of the baseline scheme vanishes
as the number of users increases for both small and large cache size as predicted by
Proposition 1. For α = 1 and α = 2, the utility of the baseline scheme decreases with
the number of users. On the contrary, the utility of all the other schemes converges to a
constant as K grows for all α.

•

Power constraint P : We observe in Figs. 3, 5 and 7 that the performance of full CSIT
selection, threshold-based selection and baseline schemes becomes identical for large P ,
which is expected since in that case the multicast rate is not limited by users with small
channel gains. Therefore, all users are selected. Note that [6, proposition 2] proves that the
full CSIT selection scheme coincides with the baseline scheme in the large P regime for
α = 0.

•

Memory size m: Figs. 2-7 show that the gap between the threshold-based scheme and the
full CSIT scheme decreases with the memory size. Such a behavior is justified by Property
1 stating that the function k → T (m, k) converges to

1−m
m

faster as the memory size m

increases.
•

Alpha-fairness α: We now consider the performance as a function of the fairness parameter
α. We notice that the gap between the selection with full CSIT and the threshold-based

27

selection decreases as the parameter α increases. This is because both schemes tend to
coincide with the baseline scheme, or max-min scheduler as α → ∞.
In summary, remarkably, even for a relatively reasonable number of users, say K ≥ 50, the
threshold-based selection scheme ensures near optimal performance, with both 1-bit feedback
and linear complexity O(K), which makes this scheme appealing for practical implementation.

Fig. 2. Average per user rate vs K for α = 0, P = 10dB and Fig. 3. Average per user rate vs P for α = 0, K = 20 and
m = [0.1, 0.6].

m = [0.1, 0.6].

Fig. 4. Utility vs K for α = 1, P = 10dB and m = [0.1, 0.6]. Fig. 5. Utility vs P for α = 1, K = 20 and m = [0.1, 0.6].

28

Fig. 6. Utility vs K for α = 2, P = 10dB and m = [0.1, 0.6]. Fig. 7. Utility vs P for α = 2, K = 20 and m = [0.1, 0.6].

VII. C ONCLUSION
Recent works have revealed that the theoretical gain of coded caching is sensitive to the
behavior of the multicast rate of the underlying channel and might vanish in the regime of a
large number of users. In order to overcome such detrimental effect, we have studied opportunistic scheduling schemes for coded caching over the asymmetric fading broadcast channel.
For the alpha-fairness utility function of the long-term average rates, we have proposed a simple
threshold-based scheduling policy, which requires only statistical channel knowledge and can be
implemented by a simple one-bit feedback from each user. Our striking result, through rigorous
and rather involved analysis, demonstrates that such threshold-based policy is asymptotically
optimal as the number of users grows. Additionally, the numerical examples show that our
proposed policy incurs a negligible loss with respect to the optimal scheduling scheme (requiring
full channel knowledge) for a reasonable number of users, i.e., between 20 to 100 users depending
on the fairness parameter and the memory size.
R EFERENCES
[1] C. V. N. Index, “Global mobile data traffic forecast update, 2015-2020,” Cisco white paper, 2015.
[2] M. A. Maddah-Ali and U. Niesen, “Fundamental limits of caching,” IEEE Transactions on Information Theory, vol. 60,
no. 5, pp. 2856–2867, 2014.
[3] K. Shanmugam, N. Golrezaei, A. G. Dimakis, A. F. Molisch, and G. Caire, “Femtocaching: Wireless content delivery
through distributed caching helpers,” IEEE Transactions on Information Theory, vol. 59, no. 12, pp. 8402–8413, 2013.
[4] G. Paschos, E. Baştuğ, I. Land, G. Caire, and M. Debbah, “Wireless caching: Technical misconceptions and business
barriers,” IEEE Communications Magazine, vol. 54, no. 8, pp. 16–22, 2016.

29

[5] K.-H. Ngo, S. Yang, and M. Kobayashi, “Scalable Content Delivery with Coded Caching in Multi-Antenna Fading
Channels,” to appear in IEEE Transactions on Wireless Communications, 2017.
[6] A. Ghorbel, K.-H. Ngo, R. Combes, M. Kobayashi, and S. Yang, “Opportunistic content delivery in fading broadcast
channels,” IEEE Global Communications Conference (GLOBECOM), Singapore, November 2017.
[7] A. Destounis, M. Kobayashi, G. Paschos, and A. Ghorbel, “Alpha fair coded caching,” 2017 15th IEEE International
Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), Paris, France, May 2017.
[8] K.-H. Ngo, S. Yang, and M. Kobayashi, “Cache-Aided Content Delivery in MIMO Channels,” in 2016 54th IEEE Annual
Allerton Conference on Communication, Control, and Computing (Allerton), Chicago, USA, September 2016.
[9] N. Jindal and Z.-Q. Luo, “Capacity limits of multiple antenna multicast,” in 2006 IEEE International Symposium on
Information Theory, pp. 1841–1845, 2006.
[10] S. P. Shariatpanahi, S. A. Motahari, and B. H. Khalaj, “Multi-server coded caching,” IEEE Transactions on Information
Theory, vol. 62, no. 12, pp. 7253–7271, 2016.
[11] J. Zhang and P. Elia, “Fundamental limits of cache-aided wireless BC: Interplay of coded-caching and CSIT feedback,”
IEEE Transactions on Information Theory, vol. 63, no. 5, pp. 3142–3160, 2017.
[12] S. P. Shariatpanahi, G. Caire, and B. H. Khalaj, “Multi-Antenna Coded Caching,” in 2017 IEEE International Symposium
on Information Theory (ISIT), pp. 2113–2117, Aachen, Germany, June 2017.
[13] ——, “Physical-layer schemes for wireless coded caching,” arXiv preprint arXiv:1711.05969, 2017.
[14] S. S. Bidokhti, M. Wigger, and R. Timo, “Noisy broadcast networks with receiver caching,” arXiv preprint
arXiv:1605.02317, 2016.
[15] J. Zhang and P. Elia, “Wireless coded caching: A topological perspective,” in 2017 IEEE International Symposium on
Information Theory (ISIT), pp. 401–405, Aachen, Germany, June 2017.
[16] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” IEEE/ACM Transactions on Networking (ToN),
vol. 8, no. 5, pp. 556–567, 2000.
[17] M. A. Maddah-Ali and U. Niesen, “Decentralized coded caching attains order-optimal memory-rate tradeoff,” IEEE/ACM
Transactions on Networking (TON), vol. 23, no. 4, pp. 1029–1040, 2015.
[18] A. L. Stolyar, “On the asymptotic optimality of the gradient scheduling algorithm for multiuser throughput allocation,”
Operations research, vol. 53, no. 1, pp. 12–25, 2005.
[19] S. Boyd and L. Vandenberghe, Convex optimization.

Cambridge university press, 2004.

[20] A. El Gamal and Y.-H. Kim, Network information theory.

Cambridge university press, 2011.

A PPENDIX
A. Proof of Proposition 1
The content delivery rate is:
Rsum,bl (K, γ) =

K
E(log(1 + min hk )).
k=1,...,K
T (m, K)

30

Since (hk )k=1,...,K are i.i.d. exponentially distributed with mean γ, mink=1,...,K hk is also exponentially distributed with mean Kγ . Hence:
 
 Z
E log 1 + min hk
=
k=1,...,K

+∞


γ 
e−x log 1 + x dx
K
0
 
K
K
= e γ E1
,
γ

which yields statement (i).
When K → ∞ we have
Z +∞

K
T (m,K)
−x

e
0

∼

Km
1−m

and

γ 
γ
log 1 + x dx ∼
K
K


Z

+∞

0

xe−x dx =

γ
.
K

Replacing yields statement (ii).
When γ → ∞,

K
γ

→ 0. Since E1 (x) ∼ log(1/x) for x → 0 we obtain statement (iii).

B. Proof of Theorem 1
Let MK be the message for all the users in K ⊆ [K] and of size 2nRK . We first show the
converse. It follows that the set of 2K − 1 independent messages {MK : K ⊆ [K], K 6= ∅} can
be partitioned as
K
[

{MK : k ∈ K ⊆ [k]}.

(23)

k=1

We can now define K independent mega-messages Mk0 := {MK : k ∈ K ⊆ [k]} with rate
P
Rk0 :=
K: k∈K⊆[k] RK . Note that each mega-message k must be decoded at least by user k
0
) must lie inside the private-message capacity region of
reliably. Thus, the K-tuple (R10 , . . . , RK

the K-user BC. Since it is a degraded BC, the capacity region is known [20], and we have
Pk
1
+
h
k
j=1 βj
Rk0 ≤ log
(24)
Pk−1 , k = 2, . . . , K,
1 + hk j=1 βj
P
for some βj ≥ 0 such that K
j=1 βj ≤ 1. This establishes the converse.
To show the achievability, it is enough to use rate-splitting. Specifically, the transmitter first
assembles the original messages into K mega-messages, and then applied the standard K-level
superposition coding [20] putting the (k − 1)-th signal on top of the k-th signal. The k-th signal
has average power βk , k ∈ [K]. At the receivers’ side, if the rate of the mega-messages are inside
0
the private-message capacity region of the K-user BC, i.e., the K-tuple (R10 , . . . , RK
) satisfies

(24), then each user k can decode the mega-message k. Since the channel is degraded, the users 1

31

to k − 1 can also decode the mega-message k and extract its own message. Specifically, each
user j can obtain MJ (if J 3 j), from the mega-message k when J ⊆ K and k ∈ K ⊆ [k]. This
completes the achievability proof.
C. Proof of Theorem 2
The proof builds on the simple structure of the capacity region. We first remark that for a
given power allocation of other users, user k sees 2k−1 messages {MJ } for k ∈ J ⊆ [k] with
equal channel gain. For a given power allocation {βk }, the capacity region of these messages
is a simple hyperplane characterized by 2k−1 vertices Cke i for i = 1, . . . , 2k−1 , where Ck is the
sum rate of user k in the RHS of (10) and e i is a vector with one for the i-th entry and zero
for the others. Therefore, the weighted sum rate is maximized for user k by selecting the vertex
corresponding to the largest weight. This holds for any k.
D. Complexity of selection scheme with full CSIT
h(t), t)
Assume that h1 (t) ≥ ... ≥ hK (t), i.e. h (t) has been previously sorted. Define k = max J(h
h(t), t)|. Let νk be a permutation on {1, ..., k}
the index of the worst user and the set size s = |J(h
h(t), t) is a maximizer of (20):
such that uνk (1) (t) ≤ ... ≤ uνk (k) (t). Since J(h
K

K

X 1{i ∈ J}
h(t), t)}
log(1 + hk (t))
log(1 + hk (t)) X 1{i ∈ J(h
=
max
J⊆[K]:|J|=s,max J=k
T (m, s)
ui (t)α
T (m, s)
ui (t)α
i=1
i=1
s

log(1 + hk (t)) X
1
=
.
T (m, s)
(uνk (i) (t))α
i=1
This implies:
h(t), t) = {νk (1), ..., νk (s)}.
J(h
h(t), t) can be computed by sorting h (t) and u (t), (with complexity O(K log(K))
Hence J(h
using quick sort), and searching over the possible values of k = 1, ..., K and s = 1, ..., K (with
h(t), t) takes time O(K 2 ).
complexity O(K 2 )). Thus, finding J(h

