1

Asymptotically Optimal Resource Block Allocation
With Limited Feedback

arXiv:1710.07617v1 [] 20 Oct 2017

Ilai Bistritz, Student Member, IEEE and Amir Leshem, Senior Member, IEEE

Abstract
Consider a channel allocation problem over a frequency-selective channel. There are K channels (frequency
bands) and N users such that K = bN for some positive integer b. We want to allocate b channels (or resource
blocks) to each user. Due to the nature of the frequency-selective channel, each user considers some channels to be
better than others. Allocating each user only good channels will result in better performance than an allocation that
ignores the selectivity of the channel. The optimal solution to this resource allocation problem can be computed
using the Hungarian algorithm. However, this requires knowledge of the numerical value of all the channel gains,
which makes this approach impractical for large networks. We suggest a suboptimal approach, that only requires
knowing what the M -best channels of each user are. We find the minimal value of M such that there exists an
allocation where all the b channels each user gets are among his M -best. This leads to feedback of significantly less
than one bit per user per channel. For a large class of fading distributions, including Rayleigh, Rician, m-Nakagami
and others, this suboptimal approach leads to both an asymptotically (in K) optimal sum-rate and an asymptotically
optimal minimal rate. Our non-opportunistic approach achieves (asymptotically) full multiuser diversity and optimal
fairness, by contrast to all other limited feedback algorithms.

Index Terms
Resource Allocation, Multiuser Diversity, Channel State Information, Random Bipartite Graphs.

I. I NTRODUCTION
The problem of multiple users accessing a common medium is a central issue in every communication network
[1]–[3]. The most common access schemes in practice are orthogonal transmission techniques such as TDMA,
FDMA , CDMA and OFDMA [4], [5]. Modern communication networks allocate each user a number of resource
blocks, each consisting of several OFDMA subcarriers that need not be adjacent [6].
Ilai Bistritz is with the Faculty of Engineering, Bar-Ilan University, Ramat-Gan, Israel, e-mail: ilaibist@gmail.com.
Amir Leshem is with the Faculty of Engineering, Bar-Ilan University, Ramat-Gan, Israel, e-mail: leshema@biu.ac.il.
This research was supported by the Israel Ministry of Science and Technology under grant 3-13038 and by a joint ISF-NRF research grant
number 2277/16.

2

When using a frequency division technique in a frequency-selective channel, not all channels have the same
quality. Furthermore, since different users have different positions, the channel gains of users in a given frequency
band are independent. This introduces a resource allocation problem between users and frequency bands (channels).
Theoretically, if the exact knowledge of all these channel gains were available, an optimal solution for this resource
allocation could be computed. The performance gain that can be achieved by solving this problem over a frequency
allocation that ignores the channel gains is known as multiuser diversity [7].
In FDD systems, the base station can only have knowledge of the channel gain of each user if all users transmit
this information directly. In TDD systems, the base station can estimate the channel gain of a given user from the
reciprocity of the channel. However, the base station must estimate the channel gains in all frequencies, not just
the currently used ones, so a wideband transmission is required from each user. These transmissions need to be
coordinated between users so that they will not collide. Moreover, although the channels are indeed reciprocal, the
RF circuits are not, which calls for a calibration process [8].
As networks grow and bandwidth expands, the number of channels increases significantly. This is typical of
OFDMA systems that tend to have a large number of subcarriers. For example, in LTE [6] there are from 128 to
2048 subcarriers in the downlink for each user. This implies that reporting the channel state information (CSI) to
the base station (BS) inflicts a large communication overhead that makes such a scheme infeasible.
This paper deals with a channel allocation task with K channels where N users simultaneously demand b
channels for each. This occurs when users are backlogged; i.e., always have packets to transmit. This represents a
non-opportunistic approach where the base station waits for a queue of N users to form and only then computes a
good allocation for all the users in the queue. When users leave the network and others replace them, the allocation
is updated accordingly.
We propose a novel limited feedback scheme that significantly reduces feedback overhead compared to state
of the art techniques [9]–[11]. The proposed technique provides a provably both asymptotically optimal sum-rate
and max-min fairness (which none of the current methods provide). The proof applies to a wide range of fading
distributions that includes Rayleigh, Rician and m-Nakagami. Our technique uses ~0.85 bits per channel per user
as of for K = N = 20, and ~0.52 bits per user per channel for K = 512 and N = 128.
In our approach, users only need to feed back the indices of their M -best channels, and not their numerical
values. If M is large enough, there is a high probability of an allocation of users to channels where each user gets
b channels, all of which are from his M -best channels. We prove that for M ≥ (b + 1) (1 + ε) ln K , for ε > 0,

this probability approaches one as K → ∞. While our approach is asymptotic, the probability that such a perfect
matching allocation exists exceeds 99.99% for K = 128 channels and N = 10 users.
Figure 1 presents a toy example of our system with N = K = 4. Each user transmits the indices of his M best

3

channels to the base station. The base station constructs a preferences matrix, computes a perfect matching in the
resulting bipartite graph and transmits back the allocated channel to each user.
The existence of a perfect matching allocation relies on the theory of random bipartite graphs. We define a
novel random bipartite graph where each user is represented by b vertices (“agents”) in the graph, all of which are
connected to the M -best channels of this user on the other side of the graph. We prove that this bipartite graph
has a perfect matching, with high probability. Due to its dependent edges, our random bipartite graph is not an
Erdős–Rï¿œnyi graph. Consequently, proving the existence of a perfect matching requires revisiting the original
proof. Our proof is in the spirit of the original result by Erdős and Rï¿œnyi for random bipartite graphs [12]. A
generalization of our results to the case of unequal numbers of channels between users can be achieved using the
same techniques. It is omitted due to the complicated formalism. However, we present simulations that indicate
that our results are also valid in this case.
Throughout this paper, we use the term “channel”. This may represent several united subcarriers in the case
where the coherence bandwidth is large and they are highly correlated (e.g., a resource block). In other words,
a “channel” is a designed unit that should optimally be the smallest independent resource block in terms of the
statistics of the corresponding channel gain.

A. Related Work
There is extensive literature on OFDMA resource allocation (see the surveys in [13], [14] and the references
therein). These allocations deal with the subcarrier assignment and the power allocation over these subcarriers. The
state of the art algorithms achieve a close to optimal sum-rate with reduced computational complexity compared
to the optimal solution. In many studies, it has been shown that an equal power allocation between the subcarriers
of each user achieves very close to optimal performance [15]–[20]. Hence, the problem of subcarrier allocation
appears to be much more significant than that of power allocation. However, all these approaches assume that users
estimate their CSI perfectly and feed all of it back to the BS. While this assumption may be reasonable for small
networks, it is highly infeasible for large networks with a large number of subcarriers, such as LTE [6].
In order to overcome the need for the whole CSI to exploit the selectivity of the channel, many works have
suggested suboptimal schemes with limited feedback. For an excellent overview of limited feedback systems, see
[21]. The state of the art algorithms consider an opportunistic scheduling approach, where each available channel
is assigned to a user with a high instantaneous channel gain [9]–[11], [22].
In [9]–[11] each user transmits one bit per channel to indicate if the corresponding channel gain exceeds a
threshold, while in [22] each user transmits the highest-rate modulation scheme he can support out of a discrete set
of schemes (which requires more than one bit per channel). In [23], [24], channels are grouped together into clusters

4

and only the information about the quality of each cluster is transmitted by the user. This grouping approach limits
the amount of multiuser diversity that can be achieved, so that the reduced feedback has a performance cost. This
cost is avoided if the grouped subcarriers are highly correlated, but in this case the multiuser diversity is smaller.
We argue that for highly correlated channels, using grouping cannot be considered a real feedback reduction, since
assigning two bits to two highly correlated subcarriers is a waste of feedback to begin with. In this work we use
the term “channel” to refer to the smallest group of uncorrelated subchannels, which can be considered a kind of
grouping.
In [25], the grouping and thresholding approaches were combined to achieve a feedback of less than one bit
per user per channel, which leads to a compromise of suboptimal performance (even asymptotically). In [26], the
M -best channels approach was used for opportunistic scheduling. Users are arranged in a queue, and each of them

transmits the indices his M -best channels to the BS. The BS sequentially assigns each user the best channel from
these M channels if it is available, and a random channel if none of them are.
All these approaches are opportunistic in nature and as such suffer from an inherent unfairness. Some of the
methods have suggested obtaining some degree of fairness by designing the scheduler [9]–[11], [24], at the cost of
a reduced sum-rate. In order to get a comparable sum-rate with a proportional fairness scheduler, each user needs
to wait until he is chosen as the “opportunistic user”. Therefore, fairness can only be maintained by introducing
very large delays for users, which is far from being desirable or practical.
The rationale behind the opportunistic approach is to exploit the multiuser diversity. By contrast, here we argue
that this widespread approach is too conservative and that achieving multiuser diversity should not come at the
expense of fairness. We argue that fairness is undermined because all these approaches schedule a user for each
channel separately. Somewhat surprisingly, when analyzing all the channels together, each user is very likely to
be “an opportunistic choice” for some channel. This calls for a more sophisticated mathematical analysis of the
random matchings between users and channels as we employ in this paper, in contrast to the simplistic arguments
dealing with one user at a time.
In contrast to [10], [11], [25], [26], our work is not limited to the case of Rayleigh-fading channels, but applies
to a much broader class of exponentially-dominated tail distributions. Besides Rayleigh fading, this class includes
Rician, m-Nakagami and others.
Another disadvantage of the thresholding approach is that it requires the BS or the users to know the fading
distribution to compute the optimal threshold. Our M -best channels approach does not require any knowledge or
model of the fading distribution on the part of the users or the BS.
In [27]–[29], a distributed channel allocation for Ad-Hoc networks was introduced, based on a carrier-sensing
multiple access (CSMA) scheme and a thresholding approach for the channel gains. Although considering a different

5

scenario, the analysis in [27]–[29] also used a random bipartite graph, albeit a very simplified one. The random
bipartite graph in [27]–[29] was an Erdős–Rï¿œnyi graph (i.e., existence of edges is independent), for which perfect
matching existence results are well known [12]. There are no perfect matching existence results that can be employed
for our graph, so a novel analysis is required. Our random bipartite graph differs from an Erdős–Rï¿œnyi graph
in two key ways. First, we use the M -best channels approach instead of the thresholding approach. This means
that each user node is connected to exactly M channel nodes, and not only in average. Second, we allow for an
allocation of b > 1 channels for each user, which leads to b identical vertices. These two characteristics mean that
the edges in our random bipartite graph are not independent. Moreover, the analysis in [27]–[29] was limited to
bounded channel gains and only proved the asymptotic optimality of the expected sum-rate. In contrast, we prove
asymptotic optimality for the random sum-rate in probability. More importantly, we prove asymptotic optimality
for the random minimal rate in probability.
Nevertheless, the work in [27]–[29] does provide us with a particularly useful algorithm. In [27], an efficient
method to compute a perfect matching for every given bipartite graph was introduced. It requires a time complexity


of O K log22 K instead of O K 3 for the Hungarian algorithm [30]. Since this computation has to be done
repeatedly in the network, this major saving in computation time can make our scheme practical in cases where
the Hungarian algorithm is not.
The existence of perfect matching allocations is closely related to the pure Nash equilibrium (NE) of interference
games. In our previous work [31] we designed a game where all pure NE are an almost (or an exact) perfect
matching between users and channels. We assumed that each user was allocated a single channel. The results of
this paper can be exploited to generalize our previous results to the case of b > 1 channels per user.

B. Outline
The remainder of this paper is organized as follows. In Section II we formulate our channel allocation problem
and define the user-channel bipartite graph. In Section III we prove that as K → ∞, the probability that a perfect
matching exists in the user-channel graph approaches one for M ≥ (b + 1) (1 + ε) ln K (Theorem 3) and that it
cannot approach one for smaller M (Lemma 4). This perfect matching is an allocation where each user gets
b of his M -best channels. In Section IV we suggest an efficient algorithm for the BS to compute this perfect

matching. In Section V we prove that a perfect matching allocation asymptotically attains both an optimal sumrate and max-min fairness (Theorem 7). Section VI provides simulation results that support our analytical findings,
compares our algorithm to state of the art algorithms and shows that our results hold for a more general model.
Finally, Section VII concludes the paper.

6

Users

Channels

Base Station
1

1

2

2

3

3

4

4

Fig. 1. The System

II. P ROBLEM F ORMULATION
In our model, there are N users that are served by a BS that has K channels for allocation. This can either
be the downlink or the uplink. Figure 1 depicts a toy example of our system with K = N = 4. We assume that
K = bN for some positive integer b and that each user is allocated b channels. The parameter b, which we treat as

given, can be optimized beforehand. A generalization of our analysis to a different number of channels per user is
possible using a more cumbersome proof. We later demonstrate in simulations that our scheme works just as well
in this case. Our assumptions on the channel gains are summarized as follows:

Channel Gains Assumptions
1) For each user n, the channel gains gn,1 , ..., gn,K are K i.i.d random variables. Channel gains of different
users are independent. This is a widespread assumption in the channel allocation literature [11], [25], [26].
However, in contrast to [10], [11], [25], [26], we do not assume Rayleigh fading or that the channel gains of
different users are identically distributed.
2) Each user can perfectly measure each of his K channel gains. This widespread assumption [10], [11], [23]–
[26] is necessary so that each user can evaluate his M -best channels. In modern devices, multichannel sensing
has become common practice that can be easily achieved by a beacon sent from the base station or other
standard estimation techniques. Our approach does not require users to transmit this entire information to the
base station.
3) Channel gains are quasi-static, such that the coherence time is larger than the time it requires to feed back
the partial CSI (i.e., block-fading). This is also a very common assumption [9]–[11], [22], [23], [25], [26],
since the multiuser diversity can only be exploited only in scenarios where this assumption holds.

We assume that the transmission power is the same in each channel, so no water-filling technique is used. This
assumption is later justified both analytically and in simulations that show that the water-filling gain is negligible

7

in our model for all practical SNR values. This has been verified for many similar scenarios [15]–[20].
An allocation a is a mapping from a user index to his set of allocated channels. Denote by An the set of allocated
channels of user n in allocation a. We want to solve the following combinatorial optimization problem
max
a

PN

n=1 Rn (An )

s.t

An

T

(1)

Am = ∅ ∀n, m , n 6= m , |An | = b , ∀n

where the first constraint means that each channel is allocated to a single user (orthogonal transmission) and the
second constraint states that each user is allocated exactly b channels.
The achievable rates of the users in bits per channel use, {Rn } , are defined as
!
2 P
X
gn,k
n
Rn (An ) =
log2 1 +
N0

(2)

k∈An

where Pn is the transmission power of user n and N0 is the variance of the Gaussian noise in his receiver.
For the remainder of this paper, we think of each user as having b agents, each of whom is allocated a single
channel. This allows us to introduce the following reduction for the problem
max
π

bN
X

Ri ({π (i)})

(3)

i=1

where π is a permutation of the agent indices. This is a combinatorial optimization problem with (bN )! possible

solutions. Somewhat surprisingly, this problem can be solved with complexity O b3 N 3 using a method that is
known as the Hungarian algorithm [30]. Beside computing the optimal solution of (3) for benchmark purposes, the
Hungarian algorithm provides us the basis for our proof strategy for the existence of a perfect matching (PM).
Our approach is that each user transmits only the indices of his M -best channels, without their numerical value.
The information available at the BS using this limited feedback can be summarized using a bipartite graph defined
as follows.
Definition 1. A user-channel graph Γ is a balanced bipartite graph consisting of a user nodes set N and a channel
nodes set K. Every user n ∈ N has b user nodes (“agents”) and every channel has a single channel node. An edge
is connected between ni ∈ N and k ∈ K if and only if channel k is one of the M -best channels for user n. A PM
allocation corresponds to a PM in this graph.
From the perspective of the theory of random bipartite graphs, our graph is not typical. Each left side node has
exactly M edges whereas each right side node may have any degree. Additionally, groups of b consecutive left
side edges are connected to the exact same right side edges. In particular, this means that edge existence is not
independent and that the graph is not an Erdős–Rï¿œnyi graph. This is why a novel proof for the existence of a

8

U1
1
U1
1

U2

1

3

2
2
U2
3

4
U3

1

2

U1

2

1
3

1
2

4
4

3

2
U2

U3
5

4

3

5
6

5

4

6

5
6

U4

3

4

7

6
7

8

8

Fig. 2. User-channel graphs

PM is needed.
Examples of user-channel graphs can be seen in Figure 2. In the left graph N = 3 and b = 2. A PM exists that
consists of the grey edges. In the right most graph N = 2 and b = 2. No user is connected to channel 4 so no PM
can exist. In the central graph, N = 8 and b = 2. Although each channel is connected to at least two user nodes, a
PM does not exist. No matter which two channels are allocated to nodes 1 and 2, nodes 3 and 4 will be left with
only one desired channel for both of them.
The following example shows that the Hungarian Algorithm (or any other sum-rate maximization approach) does
not provide a fairness guarantee for the users, whereas our algorithm does.
Example 2. Consider the following K × K rates matrix for the case of b = 1, where un,k is the rate of user n in
channel k. Let δ > 0.








U =






δ 1 1 ···

1

1 2 1 ···

1

δ 1 1 ···
.. .. .. . .
.
. . .

1
..
.

δ 1 1 ···

1














For this case, the Hungarian algorithm assigns channel k to user k for each k, resulting in a sum-rate of K + δ
and a minimal rate of δ. Our PM approach assigns each user one of his M best-channels. If 2 ≤ M ≤ K − 1,
our algorithm results in a sum-rate of K and a minimal rate of 1. For a small enough δ, we obtain only a slight
reduction in the sum-rate while having a dramatically better minimal rate.

9

III. A SYMPTOTIC E XISTENCE

OF

PM A LLOCATIONS

In this section, our goal is to show that a PM allocation, where each user only gets M -best channels, exists. There
is a natural trade-off for the parameter M . A large value of M increases the probability that a PM allocation exists
at the cost of reduced performance, since the M -best channel gets worse as M increases. Hence, it is important to
identify the smallest value of M for which a PM exists.
The main theorem of this paper is stated as follows:
Theorem 3 (Main Theorem). Let K = bN for a positive integer b. Let EK be the event that a PM, where each
user gets b channels that are among his M -best, does not exist. If M ≥ (b + 1) (1 + ε) ln K for some ε > 0 then,
for large enough K ,
Pr (EK ) ≤

1
K

ε+ ε+1
b

√
π be3
+
12

1
K

(4)

3 ε+1
3
ε+ 2 b
2

Thus, a PM exists with a probability that approaches one as K → ∞. Furthermore, if ε ≥ 1, then the indicator of
EK converges to zero almost surely.

Proof: See Appendix A.
The implication of the above theorem is that the feedback requirement of our algorithm is
per user per channel. For M = (b + 1) (1 + ε) ln K , this is O



log22 K
K

1
K



log2 

K
M



 bits


, instead of a quantization of q bits per

user per channel which an approach that requires the whole N K channel gains needs. Additionally, already for

N = K = 20 and M = 9 (ε = 0.5), we require ~0.85 bits per user per channel, which is less than the one bit per

user per channel required by all thresholding approaches (such as in [9]–[11]). For these values, more than 99% of
the channel realizations have a PM. For N = 64, b = 4, K = 256 and M = 56 (ε = 1) our method requires ~0.75
bits per user per channel and more than 99.9% of the channel realizations have a PM. For N = 128, b = 4 and
K = 512 and M = 63 (ε = 1) we require ~0.52 bits per user per channel and more than 99.99% of the channel

realizations have a PM.
For a PM to exist, every channel should be one of the M -best channels for at least one user. The following lemma
shows that for this to occur, M must grow with respect to K (faster than b ln K ) and that M = b (1 + ε) ln K is
enough for that purpose. Note that the feedback communication overhead also decreases with M , which further
justifies using the smallest M such that a PM is still likely to exist.
Lemma 4. Let K = bN for a positive integer b. Let M > 0. Denote by E the event in which there is a channel
which is not one of the M -best channels for any user.
1) If M ≤ b ln K then lim Pr (E) ≥ 12 .
K→∞

2) If M ≥ b (1 + ε) ln K and ε > 0 then lim Pr (E) = 0.
K→∞

10

Proof: See Appendix A.
IV. A SYMPTOTIC

OPTIMALITY OF

PM A LLOCATIONS

In the previous section we showed that M = (b + 1) (1 + ε) ln K , for some ε > 0, is enough to guarantee that
a PM allocation exists. In this section we show how good this PM allocation actually is. This has to do with the
extent to which the M -best channel of each user is worse than his best channel. This definitely depends on the
distribution of the channel gains. Luckily, all of the fading distributions used in practice tend to belong to the
following class:
Definition 5 (Exponentially-Dominated Tail Distribution). Let X be a random variable with a CDF FX . We say
that X has an exponentially-dominated tail distribution if there exist α > 0, β ∈ R , λ > 0, γ > 0 such that
lim

x→∞

1 − FX (x)
=1
αxβ e−λxγ

(5)

The following simple proposition validates that the Rayleigh, m-Nakagami, Rice and Normal distributions have an
exponentially-dominated tail.
Proposition 6. The Rayleigh, m-Nakagami, Rice and Normal distributions are exponentially-dominated tail distributions.
Proof: See Appendix A.
The following theorem establishes the asymptotic optimality of a PM allocation for exponentially-dominated tail
fading distributions. This optimality is both in the sum-rate and in the minimal rate senses.
Theorem 7 (Sum Rate and Fairness Optimality Theorem). Let the channel gains be the i.i.d. variables gn,1 , ..., gn,K
, for each n. If, for each n and k ,gn,k has an exponentially-dominated tail and M = (b + 1) (1 + ε) ln K for some
ε > 0, then the ratio of the sum-rate of the worst PM allocation to the sum-rate of the optimal allocation converges

to one in probability; i.e.,
min
plim
K→∞

a∈P

max
a∈A

PN

n=1 Rn (an )

PN

n=1 Rn (an )

=1

(6)

where P is the set of PMs in the user-channel graph, A is the set of all possible allocations of channels to users,
and plim denotes convergence in probability. Furthermore, the ratio of the minimal rate in the worst PM to the
maximal rate in the optimal allocation also converges to one in probability; i.e.,
minminRn (an )
plim

a∈P n

K→∞ maxmaxRn (an )
a∈A

n

= 1.

(7)

11

Proof: Denote by gn,(i) the i-th smallest channel gain among gn,1 , ..., gn,K . We have




2
2
PN
gn,(K−M
gn,(K−M
+1) Pn
+1) Pn
R
(a
)
1
+
min
log
n
n
b
1
+
log
n=1
2
2
N0
n=1
N0
a∈P


 ≥ n

≥
PN
2
2
PN
gn,(K)
Pn
gn,(K)
Pn
max n=1 Rn (an )
1
+
1
+
b
log
max
log
2
2
n=1
N0
N0
a
min

PN

(8)

n

In Theorem V.5 in [32] we proved that the last term in (8) converges to one in probability as K → ∞, provided
that gn,1 , ..., gn,K have an exponentially-dominated tail.
Note that Theorem 7 has a stronger argument than simply asymptotic optimality of the sum-rate and the minimal
rate. Observe that the denominator in (7) consists of the best rate a user can receive in any allocation, even an
allocation that only favors him. This rate is achieved when user n is allocated his best b channels from out of the
entire K channels. Hence, we conclude that even the user with the minimal rate, in all possible PM allocations,
achieves asymptotically full multiuser diversity.
The max-min fairness of (7) also holds for agents, which leads to the following corollary.
Corollary 8. Let K = bN for a positive integer b. The ratio between the rate achieved by water-filling to that of
an equal power allocation converges in probability to one as K → ∞.
o
n
∗
the set of optimal transmission powers given for the channel gains {gn,k }. We have
Proof: Denote by Pn,k






2
2
2
P
gn,(K−M
gn,(K−M
Pn
gn,k
+1) Pn
+1) Pn
1
+
min
log
1
+
log
1
+
log
2
2
2
k∈An
k∈An
N0
N0
N0

 ≥ P

 ≥ n


2
2
∗
2
P
Pn
gn,(K)
Pn
gn,(K)
Pn,k
gn,k
(a)
1
+
max
log
2
k∈An log2 1 +
k∈An log2 1 +
N0
N0
N0
P

(9)

n

∗ for
If the channel gains are increased from gn,k to gn,(K) for each k and the transmission powers are kept as Pn,k

each k, then the sum-rate obviously increases. If for the increased channel gains the optimal power allocation is
o
n
∗
, the sum-rate will further increase. The optimal power allocation for K identical channel
used instead of Pn,k

gains of gn,(K) is an equal power allocation. These arguments yield inequality (a), together with the fact that in a
2 ≥ g2
PM allocation with parameter M we have gn,k
n,(K−M +1) for each k .

V. C OMPUTATION

OF A

PM A LLOCATION

Given the feedbacked information, the base station can construct the user-channel bipartite graph. Then, a PM
allocation can be computed by finding a PM in this graph. This can be done efficiently by using the simplified


log2 (K)
for an Erdős–Rï¿œnyi
auction algorithm [27], [29]. The expected time complexity of this algorithm is O Klog(pK)


2
K log (K)
bipartite random graph with edge probability p, and can be improved to O log(log(K))
by reducing the density of
the graph. A factor of O (log (K)) comes from the computations in each iteration of the algorithm. However, in

contrast to the case in [27], [29], our random bipartite graph is not an Erdős–Rï¿œnyi graph. We show in simulations
that the actual time complexity is even slightly better.

12

Algorithm 1 The simplified auction algorithm
Initialization - hk = 0, ∀k ∈ K and set the matching to be empty M = ∅.
1) While |M| < K do
a) Choose an unassigned agent i.
b) Assign agent i the channel with the minimal hk he is connected to, denoted emin .
c) Add the edge emin to M.
d) Delete from M any previous edge connected to emin .
e) hk = hk + 1.

VI. S IMULATION R ESULTS
In this section, we demonstrate our analytical results using numerical simulations. We also validate the fact
that our findings hold in a broader model that includes correlated channels and an allocation of unequal numbers
of channels to users. All the rates are measured in bits per second, assuming that the bandwidth of a channel
o
n
2
is 15kHz (as in LTE [33]). We used a Rayleigh fading network; i.e.,{gn,k } are Rayleigh distributed and gn,k

are exponentially distributed. In each experiment, we ran 100 random realizations of the channel gains. Unless

otherwise states, the transmission powers were chosen such that the mean SNR for each link was 20dB. We used
the Hungarian algorithm to compute the optimal sum-rate solution.

A. Uncorrelated Channels
In this subsection, the channel gains were uncorrelated with parameter λ = 1 for all exponential variables. We
used the parameter M = ⌈1.5 (b + 1) ln (K)⌉ and ran the simulations for N = 10, 25, 50, 75, 100. We found that
for every realization a PM existed. This implies that our asymptotic results are valid for as low as N = 10.
In Figure 3, the mean and minimal rates are presented as a function of N for uncorrelated channels. We used
b = 4. It is evident that the performance of the PM allocation was close to the performance of the optimal allocation.

As anticipated by our results, it improved with N . We can also see that the minimal rate of the optimal allocation
was good, which was to be expected. The chance of a single user getting b = 4 bad channels is smaller than in
the case of b = 1. The random allocation rates, which can be thought of as the result of an allocation that ignores
the CSI, were far behind. This effect is crucial especially for the minimal rate. In [11], the base station assigns
each channel to one of the users that exceeded a certain threshold (possibly with defined priorities between users).
In order to make the algorithm competitive in the minimal rate sense as well, each time multiple users exceeded
the threshold, we allocated the channel to the user with the minimal number of channels thus far. We used b = 4,
so K = 4N . Our mean rate is slightly better than that of [11] for all N ≥ 20. The minimal rate of [11] is much
lower (~78% of ourminimal
 rate), and does not increase with N while our minimal rate does. Last but not least,
K
 bits per user channel (0.81 for N = 10 and 0.52 for N = 200), while [11] always
we require K1 log2 
M

13

550

500

kbit/sec

450
PM Allocation
Hungarian
Chen
Random Allocation

400

350

300

250

200
10

20

30

40

50

60

70

80

90

100

N

Fig. 3. Achievable rates as a function of N for uncorrelated channels. Solid lines represent the mean rates and dashed lines the minimal
rates.

requires one bit per user per channel (exceeded the threshold or not). Hence, our algorithm outperforms [11] both
in terms of performance and feedback communication overhead.
In Figure 4, we compare our algorithm also to that of [26], which has two versions. This algorithm assigns
a single channel to each user, so we had choose b = 1. We used the same M = ⌈3 ln (K)⌉ for our algorithm
and that of [26]. The mean rate of the set-best version is very similar to ours, with exactly the same feedback
communication overhead. The mean-rate in the ordered-best version is a little better than our mean-rate, but has a
significant feedback cost. For N = K = 20, the ordered-best requires ~2.25 bits per user per channel, while the
set-best (and our approach) requires ~0.87 bits per user per channel. For N = K = 100, the ordered-best requires
~0.98 bits per user per channel , while the set-best and our approach require ~0.55 bit per user per channel.
However, our major anticipated advantage is in the minimal rate. The minimal rate of [26] is very close in both
versions and is only about ~70% of our minimal rate, and decreases with N while our minimal rate increases. The
minimal rate of [11] converges to zero, since for N = K , the probability that some users will not be allocated a
channel is high.
To show the tightness of our selected M we now demonstrate the threshold phenomena for the existence of a
PM. We reduced M to M = ⌈b ln (K)⌉ instead of M = ⌈1.5 (b + 1) ln (K)⌉. The probability of a PM decreased
sharply to about 0.5 even for 100 users. The probabilities of existence of a PM are presented in Table I. This
demonstrates the sharp transition in Lemma 4.
In Figure 5, we present the rates as a function of b for N = 30. All the rates increased almost linearly with b,
and the ratio of the rates of a PM allocation to the optimal allocation rates remained almost constant for all b. This
implies that the results of Figure 3 are similar for each b value.

14

140

120

kbi t /sec

100

Hungarian
PM Allocation
Chen
Leinonen Set
Leinonen Ordered

80

60

40

20

0
20

30

40

50

60

70

80

90

100

N

Fig. 4. Achievable rates as a function of N compared to Leinonen’s Algorithm, Chen’s Algorithm and the Hungarian Algorithm. Solid lines
represent the mean rates and dashed lines the minimal rates.
TABLE I
E XISTENCE OF PM

N
Pr (E ∗ )

10
0.56

ALLOCATIONS AS A FUNCTION OF

25
0.45

50
0.64

75
0.59

N

FOR

M = ⌈b ln (K)⌉.

100
0.52

B. Correlated Channels
In this subsection, we used correlated resource blocks as the channels, each consisting of 12 subcarriers. The
rates are normalized per subcarrier. We used the Extended Pedestrian A model (EPA, see [33]) for the excess tap
delay and the relative power of each tap. In this model, the channel gains of different users are not identically
distributed, which is the practical scenario. We used N = 32, 64, 96, 128.
Figure 6 shows the mean and minimal rates as a function of N averaged over 100 realizations and with b = 4.
The essential difference with correlated channels is that the diversity decreases; namely, adjacent channels are likely
to be good or bad together. This makes the multiuser diversity gain lower and as a result the rates are lower, and
look like the rates of the uncorrelated fading for smaller values of N . Additionally, this reduced diversity lead us to
choose M = ⌈2 (b + 1) ln (K)⌉, since a higher M is needed for a PM to exist in the correlated user-channel graph.
Indeed, we always found PMs for this choice of M . However, a larger M makes the PM allocation rates lower.
Nevertheless, these rates are still close to the optimal rates and get closer as N increases. Given these experimental
results, we conjecture that our analytical results can be extended to the case of correlated channels
In Figure 7, we present the rates for correlated resource blocks the with b = 1. Note that both [26] and [11]
assumed uncorrelated channels and identically distributed channel gains. In a thresholding approach, a different
threshold can be used for each user, compromising mean-rate for fairness. However, since the minimal rate of [11]
converges to zero anyway, we chose the threshold in order to optimize the mean-rate. As shown, the results are
similar those of Figure 3, and the feedback overhead comparison is of course the same. The main difference is that
the minimal rate of all methods is lower. This does not represent a degradation for any of the algorithms, since

15

1600

O  A

P 
R  !"#$%&'(

1400
1200

kbit/sec

1000
800
600
400
200
0

2

4

6

8

10

12

b

Fig. 5. Achievable rates as a function of b for N = 20. Solid lines are used for the mean rates and dashed lines for the minimal rates.

with non-identically distributed channel gains, the minimal rate user is the user with the worst global conditions.
In our method, the minimal rate is still significantly better than those of [26] and [11], since this minimal rate user
got one of his best channels (even though all of them were relatively bad).
550
500
450

kbit/sec

400
350
300

Hungarian
PM Allocation
Random

250
200
150
20

40

60

80

100

120

140

N

Fig. 6. Achievable rates as a function of N for correlated channels. Solid lines represent the mean rates and dashed lines the minimal rates.

80
70

kbi t /sec

60

PM Allocation
Leinonen Set
Leinonen Ordered

50

C)*+

40
30
20
10
0
20

40

60

80

100

120

140

N

Fig. 7. Achievable rates as a function of N for correlated channels, compared to state of the art algorithms. Solid lines represent the mean
rates and dashed lines the minimal rates.

C. Unequal Channel Allocation
In this subsection, we allocated users a different number of channels, by dividing them into four classes.
Specifically,

N
4

of the users were allocated a single channel,

N
4

two channels,

N
4

three channels and

N
4

four channels.

16

We used Mi = ⌈3.75 ln (K)⌉ for all users, which amounts to using the average b in M = ⌈1.5 (b + 1) ln (K)⌉.
Such a differentiation might occur if different users require a different quality of service (QoS). We simulated 100
realizations for each value from N = 12, 20, 48, 72, 100. PMs still existed in all realizations. We ran another 100
realizations with correlated resource blocks, in the same manner as in Figure 6 and used M = ⌈5 ln (K)⌉ for all
users. Figure 8 shows the empirical CDFs of the rates for the four classes, for uncorrelated channels and correlated
resource blocks, with N = 100 and N = 128. Note that the PM allocation rates are quite concentrated and most of
the users get similar rates. These rates are always better than those of a random allocation, and close the optimal
allocation rates. These results confirm our belief that our analysis can be generalized to the case of an unequal
allocation, which is further supported by our proof itself.

1

1

1

b=2

50

100

0

150

0

100

kbit/sec

400

6,-

kbit/sec

800

0.5

0

100

0

150

0

0

500

1000

1500

kbit/sec

200

300

400

1

b=4

0.5

0
200

100

kbit/sec

b=3
F(x)

F(x)
200

50

1

b=4

0.5

0

0

0.5

kbit/sec

1

b=3
F(x)

0

300

kbit/sec

1

0

200

0.5

F(x)

0

0.5

F(x)

0.5

b=2

b=1
F(x)

F(x)

F(x)

b=1

0

1

400

./0

kbit/sec

800

0.5

0

0

500

1000

1500

kbit/sec

Fig. 8. Empirical CDFs of the rates for different classes of users with N = 100, for uncorrelated channels (left) and correlated resource
blocks (right). Solid lines are used for optimal rates, dashed lines for the PM allocation rates and dotted lines for the random allocation
rates.

D. Water-Filling Gain
In all the above results, water-filling over the b channels of each user had a negligible gain in terms of kbps. To
be exact, it never improved any of the rates by more than 0.01 kbps. This is consistent with our analytical result
in Corollary 8. We repeated our experiment for an SNR of 10dB, b = 6 and M = ⌈2 (b + 1) ln (K)⌉, where the
water-filling gain should be more significant than with our original parameters. We used N = 20, 30, 40, 50. In
Figure 9 we present, using a semi-log scale, the water-filling gain as a function of N together with the corresponding
mean rates. Clearly, even with SNR of 10dB, this gain did not exceed 0.1 kbps for either the Hungarian algorithm
or our PM allocation, which is less than 0.03% of the mean rates.

17

3

10

2

10

W4 5789 : ;< =>?@BDEFGH
Mean Rate I JK LMNQSTUVXY
Z[ \]^_ ` abcdefghi
Mean Rate j klmnopqrs

1

kbi t /sec

10

0

10

31

10

22

10

13

10

20

25

30

35

40

45

50

N

Fig. 9. The water-filling gain in kbps as a function of N

E. Computational Complexity
In Figure 10, we present the convergence times of the simplified auction algorithm as a function of N (for b = 4)
and of b (for N = 30). It is evident that the convergence time behaved very similarly to 5N and 35b respectively.
This hints that the actual convergence time may behave like O (bN ) = O (K), so the time complexity is conjectured
to be O (K logK).
500

tuvwxyz{|}~ 


400
300

Iterati ons

200
100
0
10

20

30

40

50

60

70

80

90

100

N
500

 


400
300
200
100
0

2

4



8

10

12

b

Fig. 10. Convergence time of the simplified auction algorithm as a function of N .

VII. C ONCLUSIONS
In this paper we suggested an approach aimed at achieving the multiuser diversity gain for resource block
allocation under the frequency-selective channel. Our approach requires knowledge of the indices of the M -best
channels for each of the N users, instead of the whole N K channel gains.
We showed that M = (b + 1) (1 + ε) ln (K) for a positive ε is sufficient to guarantee that a PM allocation,
where each user gets all his b channels from his M -best channels, asymptotically exists. For this value of M , our
suboptimal approach was shown to be asymptotically optimal for a broad class of fading distributions, both in the
sum-rate and max-min senses.
Our algorithm is the first limited feedback algorithm that has provably asymptotic optimality both of the sum-rate
and the minimal rate. It also requires significantly less feedback than the state of the art algorithms that achieve

18

a good sum-rate. Hence, it constitutes a major step toward achieving the multiuser diversity gain of a selective
channel in practice.
A future direction could involve trying to lift the assumption of i.i.d. channel gains by only assuming m-dependent
channel gains and using the techniques presented in [34].
A PPENDIX A
P ROOFS
For our results, we need the following simple proposition.


Proposition 9. For each 0 ≤ l ≤ K , we have













l
M






K



M






≤


l M
.
K

Proof:






l
M
K
M




=

l!
(l−M )!
K!
(K−M )!



=

M
Q

i=1
M
Q

i=1

(l − M + i)

(K − M + i)

 M
M
M
−1
Y
Y
l−M +i
l−j
l
=
=
≤
K −M +i
K − j (a) K
i=1

where (a) comes from the fact that if l < K then f (x) =
l−j
K−j

≤

l
K

(10)

j=0

l−x
K−x

is monotonically decreasing for all x < K , so

for each 0 ≤ j < M .

A. Proof of Lemma 4
Proof: Denote by Ek the event in which channel k is not one of the M -best channels for any of the users.
We want to bound from below and above the probability that there exists a channel that is not good for any of the
S
users; i.e., the probability of E = k Ek . Due to the i.i.d. assumption on the channel gains and their independency
N
. From the union bound we obtain that
between users we have Pr (Ek ) = 1 − M
K
!


[
M N
Pr (E) = Pr
Ek ≤ K 1 −
.
(11)
K
k

Since 1 −


M N
K

decreases with M , using M ≥ b (1 + ε) ln K leads to



K

b (1 + ε) ln K b
M N
≤ lim K 1 −
= lim Ke−(1+ε) ln K = 0
lim Pr (E) = lim K 1 −
K→∞
K→∞
K→∞
K→∞
K
K

(12)

19

Now we want to bound from below the probability of a PM. We do so by using the inclusion-exclusion principle.
We use the following lower bound
Pr

[
k

Ek

!

≥

X
i

Pr (Ek ) −

X

k1 ,k2



\
Ek2 .
Pr Ek1

(13)

By direct counting of the number of user-channel graphs with two undesired channels we obtain


K−2

 N











M
X
\
K


 
Ek2 = 
Pr Ek1
 


2
k1 ,k2


K
 
 
M


Since 

K
2





 is the number of choices for these two channels, 


edges of each agent and 
9.We obtain

K

M

N


K2
≤
(a) 2

K −2
M



2
1−
K

M K
b

(14)



 is the number of combinations of the

is the total number of user-channel graphs. Inequality (a) is from Proposition

Pr (E) = Pr

[
k

Ek

!



 K

2 Mb
M N K2
−
1−
≥K 1−
K
2
K

(15)

Obviously, Pr (E) decreases with M . Hence, using M = b ln K , we conclude that
!
K



2 K ln K
b ln K b
K2
=
1−
K 1−
−
K
2
K

lim Pr (E) ≥ lim

K→∞

K→∞



K 2 −2 ln K
1
− ln K
lim Ke
−
e
= . (16)
K→∞
2
2

B. Proof of Theorem 3
Proof: The bipartite graph can also be represented using a K × K preferences matrix U . Our matrix U is
a simplified binary matrix where un,k = 0 if channel k is one of the M -best channels of agent n and un,k = 1
otherwise. It consists of

K
b

submatrices of b identical rows each, and exactly M zeros at each row. We want to show

that the probability that the Hungarian algorithm on U converges after one iteration approaches one as K → ∞;
hence the resulting cost is zero, which represents a PM in the equivalent bipartite graph. Denote by Ql (K, M ) the
probability that U can be covered by K − l − 1 rows and l columns such that all its zeros are covered, and that
there is no smaller l with this property. We want to upper bound Ql (K, M ) for each l. Now observe that if U is
covered such that a row is covered but one of its identical rows is not, this means that U could be covered without

20

this row cover. Hence, if the row covers do not include all the identical rows, they are redundant. This means that
only values of K − l − 1 (or l + 1) that are a multiple of b should be considered, and Ql (K, M ) = 0 for all other
values. We proceed by counting the number of combinations of each such matrix



Ql (K, M ) ≤ 



K



K
b



K



l

K
b
l+1
b






K
M


 K−l−1
b







K
M



l
M
K
b

 l+1
b




=



K
l




  l+1
b



K
b
l+1
b

l






 M


 





K


M

(17)




 is the number of combinations for the index of the K − l − 1 covered rows and the l
l+1
l
b
covered columns. Now
we have to count the combinations for the structure of the covered and uncovered rows.

 K−l−1
b
K

is the number of combinations for K − l − 1 covered rows with exactly M zeros in
The factor 
M
each. We are left with l + 1 rows that we know can be covered by l columns, and no less than l. Hence each of

 l+1
b
l

such rows. Finally, the
these rows has zeros only in these l columns, so there can be no more than 
M

 Kb
K
 is the number of combinations of a matrix with M zeros in each row, that constitute the
denominator 
M
whole probability space.
where 

For l = K − 1 we get


M
M
1 bK
≤ Ke− b
QK−1 (K, M ) ≤ K 1 −
K
(b)
(a)

where (a) follows from Proposition 9 and (b) from the inequality 1 −


1 K
K

(18)

≤ e−1 . Note that for l = 1, ..., M − 1

it is trivial that Ql (K, M ) = 0 since each row has exactly M zeros. For the rest of the proof we assume that
M < l ≤ K − 2. For these values, we have





K
K
K

 b  = l + 1 

K
−
l
l+1
l
l+1
b



where in (a) we used 

K
l



≤

q

Khb ( Kl )
1
2
,
l
2πl(1− K )

K
b
l+1
b



≤

(a)

√

1
b
2π (K − l) 1 −

 2K (1+ b )hb (
l+1
1

l+1
K

)

(19)

K

which is valid for all 0 < l < K (where hb is the binary

21

entropy function, see [35, page 666]). Combining the above we obtain from (17) the following upper bound
√

Ql (K, M ) ≤

b
l+1
K

2π (K − l) 1 −

(a)

K (1+ 1b )hb ( l+1
K )

2



l
K

 M (l+1)
b

√

≤

(b)

b

2π (K − l) 1 −

where (a) is due to Proposition 9 and (19) and (b) due to 1 −

K−l
K

 eln(2)K (1+ b )hb (
1

l+1
K

≤ e−

K−l
K

l+1
K

M
(K−l)(l+1)
)− Kb
(20)

. We want to find the maximal value

of this bound as a function of l. Define the auxiliary function


1
f (x) = ln (2) K 1 +
b

since

dKhb ( x+1
K )
dx

= log2



K
x+1



hb



x+1
K



M
−
b



1
1M 2 M
x −
1−
x+
K
bK
b

(21)


− 1 we have

df (x)
=
dx



 


1
M
K
1
2 M
1+
−1 −
ln
1−
+ x
b
x+1
b
K
b K

(22)

and

so for any x ∈

h

(b+1)K
M

1 + 1b
1 + 1b
2M
d2 f (x)
=
−
−
+
.
2
dx
K −x−1 x+1
bK
i
2
f (x)
≥ 0. If x ≥ K −
− 1, K − (b+1)K
−
1
we have d dx
2
M

(23)
(b+1)K
M

− 1 then for M ≥

(b + 1) (1 + ε) ln (K) we get, for large enough K that
df (x)
≥
dx

also if M < x ≤

(b+1)K
M





2b + 2
1 M
1
1−
−
− 1+
ln (K − 1) ≥ 0
M
K
b
b

(24)

− 1 then for M ≥ (b + 1) (1 + ε) ln (K) we get from (22), for large enough K



 


1
M
K
1
2
1+
−1 −
(25)
ln
1−
+ 1 + ≤ 0.
b
M
b
K
b
i
h
i
(b+1)K
− 1, K − (b+1)K
−
1
,
increasing
in
K
−
−
1,
K
−
2
and decreasing in
M
M

df (x)
≤
dx

h
So f (x) is convex in (b+1)K
M
h
i
M, (b+1)K
− 1 . We conclude that the maximum of f (x) must be attained at the borders l = M, K − 2.
M
Observe that for all l <

K
2

Khb



l
K

where in (a) we used log2 1 −



l
K





K
K
l
− (K − l) log2 1 −
= l log2
≤ 2l + l log2
l
K (a)
l
2l
≥ −K
which is true for l ≤

K
2.

(26)

Now we substitute x = M, K − 2 in f (x) to

22

obtain






1
M +1
M2
1
M3 M
f (M ) = ln (2) 1 +
−
Khb
−
1−
+
b
K
b
K
bK
b





K
M2
1
M3
1
≤
2 ln (2) M + (M + 1) ln
−
1−
+
≤ 1+
b
M +1
b
K
bK (b)
(a)






1
1
M
1
M 1+
3+ 1+
ln K −
1−
(27)
b
M
b+1
K
where (a) is from (26) and (b) is for large enough K due to M ≥ (b + 1) (1 + ε) ln (K). Next

 

1
M (K − 1) (K − 2) M (K − 2)2 M
1
+
−
≤
Khb
−
f (K − 2) = ln (2) 1 +
b
K
b
K
b
K
b (a)




1
2M
1
1+
(ln K + 2 ln (2)) −
1−
(28)
b
b
K
where (a) is from hb 1 −

1
K

that for each l = 1, ...K − 2



= hb

1
K



. Hence for large enough K (28) is larger than that in (27). We conclude





2M
1
1
(ln K + 2 ln (2)) −
1−
≤
f (x) ≤ maxf (x) ≤ 1 +
x
b
b
K






1
1
3− 1+
ln (K) 2 (1 + ε) 1 −
−1 ≤
b
K



3
1
1 + ε ln (K) (29)
≤ 3− 1+
b
2
(a)
where (a) is true for large enough K such that

1
K

≤ 2ε . Denote by EK the event in which a PM does not exist.

We conclude by the union bound that
Pr (EK ) ≤

√
K−2
X
1
bK
−M
QK−1 (KM ) +
Ql (K, M ) ≤ ε + Ke b +
ef (l) ≤
K
2π (K − l) (K − l − 1)
l=M
l=M
√
√
K−2
∞
X
M
1
bK f (K−2)
bK f (K−2) X 1
−
−M
e
e
≤
≤ Ke b +
Ke b +
2π
2π
k2
(K − l − 1)2 (a)
l=M
k=1
√
1
1
π be3
+
(30)
3 ε+1
ε+ ε+1
3
2
12
b
K
K 2 ε+ b
P
where (a) from substituting k = K − l and adding terms to the sum. Note that if ε ≥ 1 then ∞
K=1 Pr (EK ) < ∞.
K−2
X

Hence, by the Borel-Cantelli lemma, the probability that an infinite number of events from {EK } will occur is

zero. Hence, we conclude that the indicator of EK converges almost surely to zero.

23

C. Proof of Proposition 6
x2

Proof: For the Rayleigh distribution we have FX (x) = 1 − e− 2σ2 , so we simply have
β = 0,γ = 2 and λ =

1
2σ2 .

lim

fX (x)
1 − FX (x)

= lim 
.
γ
β
−λx
αβ
x→∞
αx e
αλγ − xγ xβ−1+γ e−λxγ

For an m-Nakagami distribution with parameter Ω > 0, the PDF is fX (x) =
mm−1
Γ(m)Ωm−1 ,

= 1 for α = 1,

Now observe that From l’Hï¿œpital’s [36, Page 109] rule we obtain

x→∞

α=

1−FX (x)
αxβ e−λxγ

β = 2m − 2,γ = 2 and λ =

m
Ω.

(31)

x2
2mm
2m−1 e− m
Ω
.
Γ(m)Ωm x

We choose

Substituting this in (31) yields
m

m

2

2m
2m−1 e− Ω x
fX (x)
Γ(m)Ωm x


= 1.
= lim 
lim 
m
αβ
x→∞
x→∞
2mm
β−1+γ e−λxγ
2m−1 e− Ω x2
αλγ − αβ
x
x
−
γ
2
m
x
x
Γ(m)Ω
2

For the Rice distribution we have fX (x) =

+v
x − x 2σ
2
σ2 e

Substituting this in (31) yields
2

2

+v
x − x 2σ
2
I0 xv
2e
σ
σ2

lim 
x→∞
β−1+γ e−λxγ
αλγ − αβ
xγ x



=

(a)

2

I0

xv
σ2



. We choose α = σ

p

v
2π ,

β = − 12 ,γ = 2 and λ =

v √ − (x−v)
2σ2
2π xe
lim

pv
x2
x→∞ 1
α √ − 2σ
xe 2
σ
2π + 2x2
1
σ

(32)

1
2σ2 .

2

p

I0 ( xv )
where (a) follows since lim σ σ−2 xv2 = 1. For a Gaussian distribution we have fX (x) =
x→∞ √πxv e 2σ
q
σ2
choose α = 2π , β = −1,γ = 2 and λ = 2σ1 2 . Substituting this in (31) yields
1

=

1. (33)

1
2
√ 1 e− 2σ2 x .
2
2πσ

We

2

√ 1 e− 2σ2 x
fX (x)
2πσ2


= 1.
lim 
= lim 
γ
αβ
x→∞
x→∞ √ 1
α
− 2σ12 x2
β−1+γ
−λx
αλγ − xγ x
+
e
e
x2
2πσ2

(34)

R EFERENCES
[1] Q. Zhao and B. M. Sadler, “A survey of dynamic spectrum access,” Signal Processing Magazine, IEEE, vol. 24, no. 3, pp. 79–89,
2007.
[2] M. Hasan, E. Hossain, and D. Niyato, “Random access for machine-to-machine communication in LTE-advanced networks: issues and
approaches,” IEEE Communications Magazine, vol. 51, no. 6, pp. 86–93, 2013.
[3] K. Akkarajitsakul, E. Hossain, D. Niyato, and D. I. Kim, “Game theoretic approaches for multiple access in wireless networks: A
survey,” IEEE Communications Surveys & Tutorials, vol. 13, no. 3, pp. 372–395, 2011.
[4] K. Seong, M. Mohseni, and J. M. Cioffi, “Optimal resource allocation for OFDMA downlink systems,” in 2006 IEEE International
Symposium on Information Theory, 2006.
[5] W. Zhao, S. Wang, and J. Guo, “Efficient resource allocation for OFDMA-based device-to-device communication underlaying cellular
networks,” in Communications in China (ICCC), 2015 IEEE/CIC International Conference on, 2015.
[6] A. Ghosh, J. Zhang, J. G. Andrews, and R. Muhamed, Fundamentals of LTE. Pearson Education, 2010.

24

[7] T. Yoo and A. Goldsmith, “Optimality of zero-forcing beamforming with multiuser diversity,” in Communications, 2005. ICC 2005.
2005 IEEE International Conference on, 2005.
[8] J.-C. Guey and L. D. Larsson, “Modeling and evaluation of MIMO systems exploiting channel reciprocity in TDD mode,” in Vehicular
Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th, vol. 6, 2004, pp. 4265–4269.
[9] D. Gesbert and M.-S. Alouini, “How much feedback is multi-user diversity really worth?” in Communications, 2004 IEEE International
Conference on, vol. 1, 2004, pp. 234–238.
[10] S. Sanayei and A. Nosratinia, “Opportunistic downlink transmission with limited feedback,” IEEE Transactions on Information Theory,
vol. 53, no. 11, pp. 4363–4372, 2007.
[11] J. Chen, R. A. Berry, and M. L. Honig, “Large system performance of downlink OFDMA with limited feedback,” in Information
Theory, 2006 IEEE International Symposium on, 2006, pp. 1399–1403.
[12] P. Erdos and A. Renyi, “On random matrices,” Magyar Tud. Akad. Mat. Kutató Int. Közl, vol. 8, no. 455-461, p. 1964, 1964.
[13] E. Yaacoub and Z. Dawy, “A survey on uplink resource allocation in OFDMA wireless networks,” IEEE Communications Surveys &
Tutorials, vol. 14, no. 2, pp. 322–337, 2012.
[14] S. Sadr, A. Anpalagan, and K. Raahemifar, “Radio resource allocation algorithms for the downlink of multiuser OFDM communication
systems,” IEEE Communications Surveys & Tutorials, vol. 11, no. 3, pp. 92–106, 2009.
[15] L. M. Hoo, B. Halder, J. Tellado, and J. M. Cioffi, “Multiuser transmit optimization for multicarrier broadcast channels: asymptotic
FDMA capacity region and algorithms,” IEEE Transactions on Communications, vol. 52, no. 6, pp. 922–930, 2004.
[16] K. Kim, Y. Han, and S.-L. Kim, “Joint subcarrier and power allocation in uplink OFDMA systems,” IEEE Communications Letters,
vol. 9, no. 6, pp. 526–528, 2005.
[17] W. Yu and J. M. Cioffi, “Constant-power waterfilling: performance bound and low-complexity implementation,” IEEE Transactions on
Communications, vol. 54, no. 1, pp. 23–28, 2006.
[18] W. Yu, G. Ginis, and J. M. Cioffi, “Distributed multiuser power control for digital subscriber lines,” Selected Areas in Communications,
IEEE Journal on, vol. 20, no. 5, pp. 1105–1115., 2002.
[19] I. C. Wong and B. L. Evans, “Optimal downlink OFDMA resource allocation with linear complexity to maximize ergodic rates,” IEEE
Transactions on Wireless Communications, vol. 7, no. 3, pp. 962–971, 2008.
[20] J. Jang and K. B. Lee, “Transmit power adaptation for multiuser OFDM systems,” IEEE Journal on selected areas in communications,
vol. 21, no. 2, pp. 171–178, 2003.
[21] D. J. Love, R. W. Heath, V. K. Lau, D. Gesbert, B. D. Rao, and M. Andrews, “An overview of limited feedback in wireless communication
systems,” IEEE Journal on selected areas in Communications, vol. 26, no. 8, pp. 1341–1365, 2008.
[22] Y. S. Al-Harthi, A. H. Tewfik, and M.-S. Alouini, “Multiuser diversity with quantized feedback,” IEEE Transactions on Wireless
Communications, vol. 6, no. 1, pp. 330–337, 2007.
[23] I. Toufik and H. Kim, “MIMO-OFDMA opportunistic beamforming with partial channel state information,” in Communications, 2006.
ICC’06. IEEE International Conference on, vol. 12, 2006, pp. 5389–5394.
[24] P. Svedman, S. K. Wilson, L. J. Cimini, and B. Ottersten, “Opportunistic beamforming and scheduling for OFDMA systems,” IEEE
Transactions on Communications, vol. 55, no. 5, pp. 941–952, 2007.
[25] J. Chen, R. A. Berry, and M. L. Honig, “Limited feedback schemes for downlink OFDMA based on sub-channel groups,” IEEE Journal
on Selected Areas in Communications, vol. 26, no. 8, pp. 1451–1461, 2008.
[26] J. Leinonen, J. Hämäläinen, and M. Juntti, “Performance analysis of downlink OFDMA resource allocation with limited feedback,”
IEEE Transactions on Wireless Communications, vol. 8, no. 6, pp. 2927–2937, 2009.
[27] O. Naparstek and A. Leshem, “A fast matching algorithm for asymptotically optimal distributed channel assignment,” in Digital Signal
Processing (DSP), 2013 18th International Conference on, 2013.

25

[28] ——, “Fully distributed optimal channel assignment for open spectrum access,” IEEE Transactions on Signal Processing, vol. 62, no. 2,
pp. 283–294, 2014.
[29] ——, “Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random
graphs,” in Random Structures & Algorithms.

Wiley Online Library, 2014.

[30] C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity.

Courier Corporation, 1998.

[31] I. Bistritz and A. Leshem, “Asymptotically optimal distributed channel allocation: a competitive game-theoretic approach,” in
Communication, Control, and Computing (Allerton), 2015 53nd Annual Allerton Conference on, 2015.
[32] ——, “Game theoretic dynamic channel allocation for frequency-selective interference channels,” arxiv preprint.
[33] E. LTE, “Evolved universal terrestrial radio access (e-utra); base station (bs) radio transmission and reception (3gpp ts 36.104 version
8.6. 0 release 8), july 2009,” ETSI TS, vol. 136, no. 104, p. V8, 2009.
[34] I. Bistritz and A. Leshem, “Game theoretic resource allocation for m-dependent channel with application to OFDMA,” in The 42nd
IEEE International Conference on Acoustics, Speech and Signal Processing, 2017.
[35] T. M. Cover and J. A. Thomas, Elements of information theory.
[36] W. Rudin et al., Principles of mathematical analysis.

John Wiley & Sons, 2012.

McGraw-hill New York, 1964.

