close

Вход

Log in using OpenID

embedDownload
1
Maximum Sum Rate of Aloha with Capture
arXiv:1501.03380v1 [cs.IT] 13 Jan 2015
Yitong Li and Lin Dai, Senior Member, IEEE
Abstract
The sum rate performance of random-access networks crucially depends on the access protocol and receiver
structure. Despite extensive studies, how to characterize the maximum sum rate of the simplest version of random
access, Aloha, remains an open question. In this paper, a comprehensive study of the sum rate performance of
Aloha networks is presented. By extending the unified analytical framework proposed in [20], [21] from the classical
collision model to the capture model, the network steady-state point in saturated conditions is derived as a function
of the signal-to-interference-plus-noise ratio (SINR) threshold which determines a fundamental tradeoff between
the information encoding rate and the network throughput. To maximize the sum rate, both the SINR threshold
and backoff parameters of nodes should be properly selected. Explicit expressions of the maximum sum rate and
the optimal setting are obtained under various assumptions on the receiver model and channel conditions. The
analysis reveals that similar to the sum capacity of the multiple access channel, the maximum sum rate of Aloha
also logarithmically increases with the mean received signal-to-noise ratio (SNR), but the high-SNR slope is only
e−1 . Effects of backoff, multipacket reception, channel fading and power control on the sum rate performance of
Aloha networks are further discussed, which shed important light on the practical network design.
Index Terms
Random access, Aloha, sum rate, network throughput, backoff, capture model, collision model
The authors are with the Department of Electronic Engineering, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon Tong,
Hong Kong, China (email: yitongli2@student.cityu.edu.hk, lindai@cityu.edu.hk).
2
I. I NTRODUCTION
Random access provides a simple and elegant solution for multiple users to share a common channel.
Studies on random-access protocols date back to 1970s [1]. After decades of extensive research, random
access has found wide applications to Ethernet, IEEE 802.11 networks and wireless ad-hoc networks [2].
The minimum coordination and distributed control make it highly appealing for low-cost data networks.
In sharp contrast to the simplicity in concept, the performance analysis of random-access networks has
been known as notoriously difficult, which is mainly due to the lack of a coherent analytical framework.
Numerous models have been proposed based on distinct assumptions. According to the receiver structure,
they can be broadly divided into three categories:
1) Collision model: In the classical collision model, when more than one node transmit their packets
simultaneously, a collision occurs and none of them can be successfully decoded. A packet transmission is successful only if there are no concurrent transmissions. The collision model was first
proposed by Abramson in [1], and has been widely used in most of random-access studies [3]–[21].
2) Capture model: Though an elegant and useful simplification of receivers, the collision model could
be overly pessimistic if there exists a large difference of received power. It was first pointed out
by Roberts in [22] that even with multiple concurrent transmissions, the strongest signal could be
successfully detected as long as the signal-to-interference ratio (SIR) is high enough. It was referred
to as the “capture effect”, which has been extensively studied in [23]–[36]. With the capture model,
each node’s packet is decoded independently by treating others’ as background noise. A packet
can be successfully decoded as long as its received signal-to-interference-plus-noise ratio (SINR) is
above a certain threshold. It is clear that multiple packets can be decoded simultaneously if the SINR
threshold is sufficiently low.
3) Joint-decoding model: The capture model is essentially a single-user detector. Multiuser detectors,
such as Minimum Mean Square Error (MMSE) and Successive Interference Cancelation (SIC), have
been also applied to random-access networks [37]–[43]. By jointly decoding multiple nodes’ packets,
the efficiency can be greatly improved, though at the cost of receiver complexity.
Note that the capture model and the joint-decoding model both have the so-called “multipacket-reception
(MPR)” capability [44], [45], and have been referred to as the MPR model in many references [32], [36],
[37], [39]–[41], [43]. Here we distinguish them apart because they assume different receiver structures.
Compared to the capture model, although a sophisticated multiuser detector is much more efficient, it
3
may not be affordable to low-cost data networks. Therefore, in this paper, we specifically focus on the
performance analysis based on the capture model.
A. Maximum Network Throughput of Aloha
In random-access networks, due to the uncoordinated nature of transmitters, the number of successfully
decoded packets in each time slot varies from time to time. In the literature, the time average of the
number of successfully decoded packets per time slot is usually adopted as an important performance
metric, which is referred to as the network throughput.
The network throughput performance depends on a series of key factors including the receiver model
and protocol design. With the classical collision model, for instance, at most one packet can be successfully
decoded at each time slot. Therefore, the network throughput, which is also the fraction of time that an
effective output is produced in this case, cannot exceed 1. The maximum network throughput of Aloha
was shown to be only e−1 with the collision model [3], which indicates that over 60% of the time is wasted
when the network is either in collision or idle states. To improve the efficiency, Carrier Sense Multiple
Access (CSMA) was further introduced in [4], with which the network throughput can approach 1 by
reducing the sensing time. On the other hand, significant improvement in network throughput was also
observed when the capture model is adopted [23]–[27], [29], [30], [32], [33], [36]. Intuitively, with the
capture model, more packets can be successfully decoded by reducing the SINR threshold. The network
throughput is thus greatly improved, and may exceed 1 if the SINR threshold is sufficiently small.
Despite extensive studies, how to maximize the network throughput has been an open question for a long
time. In Abramson’s landmark paper [3], by modeling the aggregate traffic as a Poisson random variable
with parameter G, the network throughput of Aloha with the collision model can be easily obtained as
Ge−G , which is maximized at e−1 when G = 1. To enable the network to operate at the optimum point,
nevertheless, it requires the connection between the mean traffic rate G and key system parameters such
as transmission probabilities of nodes, which turns out to be a challenging issue. Various retransmission
strategies were developed to adjust the transmission probability of each node according to the number of
backlogged nodes to stabilize the network [5]–[8]. Yet most of them were based on the realtime feedback
information on the backlog size, which may not be available in a distributed network. Decentralized
retransmission control was further studied in [6], [10]–[12], where algorithms were proposed to either
estimate and feed back the backlog size [10], [12], or update the transmission probability of each node
recursively according to the channel output [6], [11].
4
The above analytical approaches were also applied to the capture model. By assuming Poisson distributed aggregate traffic, for instance, the network throughput was derived as a function of the mean
traffic rate G and the SIR threshold in [24], [25], [27] under distinct assumptions on channel conditions.
Similar to the case of collision model, the maximum network throughput can be obtained by optimizing
G, yet how to properly tune the system parameters to achieve the maximum network throughput remains
unknown. Retransmission control strategies developed in [5], [10] and [11] were further extended to the
capture model in [28], [29] and [30], respectively. To evaluate the network throughput performance for
given transmission probabilities of nodes, various Markov chains were also established in [23], [26], [33],
[36] to model the state transition of each individual user. The computational complexity, nevertheless,
sharply increases when sophisticated backoff strategies are further involved, which renders it extremely
difficult, if not impossible, to search for the optimal configuration to maximize the network throughput.
The difficulty originates from the modeling of random-access networks. As demonstrated in [21],
the modeling approaches in the literature can be roughly divided into two categories: channel-centric
[3]–[8], [10]–[12] and node-centric [9], [13]–[18]. By focusing on the state transition process of the
aggregate traffic, the channel-centric approaches capture the essence of contention among nodes, which,
nevertheless, ignore the behavior of each node’s queue and thus shed little light on the effect of backoff
parameters on the performance of each single node. With the node-centric approaches, on the other hand,
the modeling complexity becomes prohibitively high if interactions among nodes’ queues are further
taken into consideration. To simplify the analysis, a key approximation, which has been widely adopted
and shown to be accurate for performance evaluation of large multi-queue systems [46], is to treat each
node’s queue as an independent queueing system with identically distributed service time. The service
time distribution is still crucially determined by the aggregate activities of head-of-line (HOL) packets of
all the nodes, which requires proper modeling of HOL packets’ behavior.
In our recent work [20], [21], a unified analytical framework for two representative random-access
protocols, Aloha and CSMA, was established, where the network steady-state operating points were
characterized based on the fixed-point equations of the limiting probability of successful transmission of
HOL packets by assuming the classical collision model. Both steady-state points were derived as explicit
functions of key system parameters including the aggregate input rate, the number of nodes and the
transmission probabilities of nodes, which enable the characterization of stable regions and performance
optimization. In this paper, the proposed analytical framework is further extended to incorporate the
5
capture model. Specifically, we consider an n-node Aloha network, where each node always has packets
to transmit, and the received signal-to-noise ratios (SNRs) of nodes’ packets are exponentially distributed
with the same mean received SNR ρ. The network steady-state point, which is characterized as the single
non-zero root of the fixed-point equation of the limiting probability of successful transmission of HOL
packets, is found to be closely dependent on transmission probabilities of nodes, the SINR threshold µ
ˆ max is obtained as an explicit function
and the mean received SNR ρ. The maximum network throughput λ
of the SINR threshold µ and the mean received SNR ρ, which is shown to be monotonically increasing
as µ decreases or ρ increases. The optimal transmission probabilities of nodes to achieve the maximum
network throughput are also derived, and verified by simulation results.
B. Maximum Sum Rate of Aloha
From the information-theoretic perspective, random access can be regarded as a multiple access channel
with a random number of active transmitters. It is well known that the sum capacity of an n-user AdditiveWhite-Gaussian-Noise (AWGN) multiple access channel is determined by the received SNRs, i.e., Csum =
P
log2 (1 + ni=1 SNRi ). With random access, however, the number of active transmitters is a random
variable whose distribution is determined by the protocol and parameter setting. Moreover, to achieve
the sum capacity, a joint decoding of all transmitted codewords should be performed at the receiver side,
which might be unaffordable for random-access networks. Therefore, the sum rate performance of random
access becomes closely dependent on assumptions on the access protocol and receiver design.
There has been a great deal of effort to explore the information-theoretic limit of random-access
networks. For instance, the concept of rate splitting [47] was first introduced to Aloha networks in [38],
where a joint coding scheme was developed for the two-node case. If each node independently encodes
its information, [42] showed that the sum rate1 performance of Aloha networks can be improved by
adaptively adjusting the encoding rate according to the number of nodes and the transmission probability
of each node. [38] and [42] are based on the assumption of joint decoding of multiple nodes’ packets
at the receiver side. With the capture model, the effects of power allocation and modulation on the sum
rate of Aloha in AWGN channels were analyzed in [31] and [34], respectively. Queueing stability and
channel fading were further considered in [35], where the sum rates with various cross-layer approaches
were derived. In [19], by assuming that the channel state information (CSI) is available at the transmitter
1
Note that different terminologies were used in these studies. In [31], for instance, “average spectral efficiency” was used to denote the
sum rate of Aloha. In [19], [34], [35], [42], it was referred to as “throughput”.
6
side and the collision model is adopted at the receiver side, the scaling behavior of the sum rate of Aloha
as the number of nodes n goes to infinity was characterized, and shown to be identical to that of the sum
capacity of the multiple access channel.
Although various analytical models were developed in the above studies, many of them rely on numerical
methods to calculate the sum rate, and the high computational complexity makes it hard to further optimize
the sum rate. As we will demonstrate in this paper, the sum rate optimization of Aloha networks can be
decomposed into two parts: 1) For given information encoding rate R, or equivalently, SINR threshold
µ, the network throughput can be maximized by properly choosing the backoff parameters, i.e., the
transmission probabilities of each node. 2) As the information encoding rate and the maximum network
throughput are both functions of the SINR threshold µ, the sum rate can be further optimized by tuning
µ.
Specifically, we first focus on fading channels over which the received SNRs of nodes’ packets are
exponentially distributed with the same mean received SNR ρ. By assuming that all the nodes encode their
information independently at the same rate and each codeword lasts for one time slot, the maximum sum
rate of Aloha with the capture model is derived as a function of the mean received SNR ρ. It is shown
that similar to the sum capacity of the multiple access channel, the maximum sum rate of Aloha also
logarithmically increases with ρ, but the high-SNR slope is only e−1 . At the low SNR region, the maximum
sum rate is a monotonic increasing function of the number of nodes n, and approaches e−1 log2 e ≈ 0.5307
as n → ∞. To achieve the maximum sum rate, both the SINR threshold and the backoff parameters should
be carefully selected according to the mean received SNR ρ. Explicit expressions of the optimal SINR
threshold at different SNR regions are derived, and verified by simulations.
As the sum rate performance is critically determined by the assumptions on the receiver and channel
conditions, the analysis is further applied to the collision model and AWGN channels. Specifically, the
maximum sum rate of Aloha with the collision model over fading channels is further characterized, and
shown to be comparable to that with the capture model. It indicates that despite an overly pessimistic
estimation on the network throughput, the collision model serves as a good approximation for the capture
model when analyzing the sum rate performance of Aloha networks. To demonstrate the effect of fading,
we also derive the maximum sum rate of Aloha over AWGN channels, and the comparison corroborates
that fading always hurts if no CSI is available at the transmitter side. Finally, the analysis is extended to
incorporate distinct mean received SNRs of nodes.
7
The remainder of this paper is organized as follows. Section II presents the system model. Section III
focuses on the network throughput analysis, where the maximum network throughput and the optimal
backoff parameters are obtained as functions of the SINR threshold and the mean received SNR. The
maximum sum rate is derived in Section IV, and the effects of key factors, including backoff, multipacketreception capability, channel fading and power control, are discussed in Section V. Conclusions are
summarized in Section VI.
II. S YSTEM M ODEL
Consider a slotted Aloha network where n nodes transmit to a single receiver. All the nodes are
synchronized and can start a transmission only at the beginning of a time slot. For each node, assume
that it always has packets in its queue and each packet transmission lasts for one time slot. We ignore
the subtleties of the physical layer such as the switching time from receiving mode to transmitting mode
and the delay required for information exchange.
Let gk denote the channel gain from node k to the receiver, which can be further written as
gk = γk · hk .
(1)
hk is the small-scale fading coefficient of node k which varies from time slot to time slot2 and is modeled as
a complex Gaussian random variable with zero mean and unit variance. The large-scale fading coefficient
γk characterizes the long-term channel effect such as path loss and shadowing. Due to the slow-varying
nature, the large-scale fading coefficients are usually available at the transmitter side through channel
measurement and feedback.3 Let us first assume that uplink power control is performed to overcome the
effect of large-scale fading. Specifically, denote the transmission power of node k as P¯k . Then we have
P¯k · |γk |2 = P0 .
(2)
In this case, each node has the same mean received signal-to-noise ratio (SNR) ρ = P0 /σ 2 . The assumption
of uplink power control will be relaxed in Section V-D, where the analysis is extended to incorporate
distinct mean received SNRs.
Throughout the paper, we assume that the receiver always has perfect channel state information but
2
More specifically, we assume that the time slot length is equal to the channel coherence time.
In this paper, we assume perfect and instant feedback. The effect of feedback error and delay on the network performance of Aloha is
an interesting topic that deserves attention in the future study.
3
8
the transmitters are unaware of the instantaneous realizations of the small-scale fading coefficients. As
a result, each node independently encodes its information at a given rate R bit/s/Hz. Assume that each
codeword lasts for one time slot.4 At the receiver side, no joint decoding is performed among nodes’
packets or with previously received packets. Instead, each node’s packet is decoded independently by
treating others’ as background noise at each time slot. Such a simplified receiver has been widely adopted
in the literature [22]–[36] and is referred to as the “capture model”.
Let
µ = 2R − 1
(3)
denote the signal-to-interference-plus-noise ratio (SINR) threshold at the receiver. For each node’s packet,
if its received SINR exceeds the threshold µ, it can be successfully decoded and rate R can be supported
for reliable communications.5 Note that when the SINR threshold µ is sufficiently small, more than one
packets could be successfully decoded at each time slot. It is clear that the number of successfully decoded
packets in time slot t, denoted by Nt , is a time-varying variable. As a result, the total received information
rate, i.e., R · Nt bit/s/Hz, also varies with time. In this paper, we focus on the long-term system behavior
and define the sum rate as the time average of the received information rate:
T
1X
ˆ out ,
Rs = lim
R · Nt = R · λ
T →∞ T
t=1
(4)
where
T
1X
ˆ
λout = lim
Nt
T →∞ T
t=1
(5)
is the average number of successfully decoded packets per time slot, which is referred to as the network
throughput.
ˆ out depend on the SINR threshold µ.
Both the information encoding rate R and the network throughput λ
Intuitively, by reducing µ, more packets can be successfully decoded at each time slot, yet the information
encoding rate becomes smaller. Therefore, the SINR threshold µ should be carefully chosen to maximize
ˆ out is also crucially determined by the protocol design and
the sum rate. Note that the network throughput λ
4
Note that here we assume that each codeword only covers one channel coherence time period. Without coding over fading states, the
decoding delay is greatly reduced, but a certain rate loss is also caused, as we will show in Section IV-B and Section V-A.
5
More specifically, denote the received SINR of node k as SIN Rk . If log2 (1+SIN Rk ) > R, then by random coding the error probability
of node k’s packet is exponentially reduced to zero as the block length goes to infinity. Here we assume that the block length is sufficiently
large such that node k’s packet can be successfully decoded as long as SIN Rk ≥ µ.
9
backoff parameters. In the next section, we will specifically focus on the network throughput performance
of Aloha networks.
III. N ETWORK T HROUGHPUT
An n-node buffered Aloha network is essentially an n-queue-single-server system whose performance
is determined by the aggregate activities of the head-of-line (HOL) packets. Let us first characterize the
state transition process of HOL packets.
A. State Characterization of HOL Packets
The behavior of each HOL packet can be modeled as a discrete-time Markov process. As Fig. 1 shows,6
a fresh HOL packet is initially in State 0, and moves to State D if it does not transmit. Define the phase
of a HOL packet as the number of collisions it experiences. A phase-i HOL packet moves to State 0 if
its transmission is successful, and otherwise shifts to State min(K, i + 1), where K denotes the cutoff
phase. Intuitively, to alleviate the contention, nodes should reduce their transmission probabilities as they
experience more collisions. Therefore, we assume that the transmission probabilities {qi }i=0,...,K form a
monotonic non-increasing sequence.
q1 pt
q0 pt
0
1 q0
1 q0
Fig. 1.
q0 (1 pt )
q0 pt
1
q1 (1 pt )
1 q1
qK pt
q2 pt
2
q2 (1 pt )
1 q2
͙...q K 1 (1 pt )
K
1 qK pt
q0 (1 pt )
D
State transition diagram of an individual HOL packet in Aloha networks.
In Fig. 1, pt denotes the probability of successful transmission of HOL packets at time slot t.7 It can
6
Note that a similar Markov chain of the HOL packet was established in [20] where the transmission probability of each fresh HOL packet
was assumed to be 1. Here a new state, i.e., State D, is introduced to incorporate a general transmission probability of 0 < q0 ≤ 1 for each
fresh HOL packet.
7
Note that in Fig. 1, the probability of successful transmission of HOL packets at time slot t, pt , is assumed to be state independent.
Intuitively, given that a HOL packet is attempting to transmit, the probability that its transmission is successful is determined by the overall
activities of all the other HOL packets, rather than its own state. Therefore, no matter which state the HOL packet is currently staying at,
its probability of successful transmission depends on the attempt rate of other HOL packets at the moment, which is denoted as pt in Fig.
1. Although a rigorous proof of the validity of the above assumption is yet to be found, simulation results presented in Sections III-D and
IV-C will demonstrate the effectiveness of the proposed analytical model.
10
be easily shown that the Markov chain is uniformly strongly ergodic if and only if the limit
lim pt = p
(6)
t→∞
exists [48]. The steady-state probability distribution of the Markov chain in Fig. 1 can be further obtained
as
π0 =
and
πD =
1 − q0
π0 ,
q0
πi =
1
PK−1 (1 − p)i (1 − p)K
+
i=0
qi
pqK
,
(1 − p)i
(1 − p)K
π0 , i = 1, . . . , K − 1, πK =
π0 .
qi
pqK
(7)
(8)
Note that π0 is the service rate of each node’s queue as the queue has a successful output if and only if
the HOL packet is in State 0.
B. Steady-state Point in Saturated Conditions
If we regard an n-node buffered Aloha network as an n-queue-single-server system, the network
ˆ out is indeed the system output rate, which is equal to the aggregate input rate λ
ˆ if each
throughput λ
ˆ increases, the network will eventually
node’s buffer has a non-zero probability of being empty. As λ
become saturated where each node is busy with a non-empty queue. In this case, the network throughput
is determined by the aggregate service rate, i.e.,
ˆ out = nπ0 ,
λ
(9)
which, as (7) shows, depends on the steady-state probability of successful transmission of HOL packets
p. In this section, we will characterize the network steady-state operating point in saturated conditions
based on the fixed-point equation of p.
Specifically, for HOL packet j, let Sj denote the set of nodes which have concurrent transmissions. It
can be successfully decoded at the receiver side if and only if its received SINR is above the threshold
µ, i.e.,
P
Pj
Pk +σ2
k∈Sj
≥ µ, where Pk = P¯k |gk |2 denotes the received power, which is given by Pk = P0 |hk |2
by combining (1) and (2). Suppose that |Sj | = i. The steady-state probability of successful transmission
11
of HOL packet j given that there are i concurrent transmissions, rij , can be then written as
(
)
2
|hj |
rij = Pr P
≥µ ,
2
k∈Sj |hk | + 1/ρ
(10)
where ρ = P0 /σ 2 is the mean received SNR. With hk ∼ CN (0, 1), rij can be easily obtained as [24], [36]
µ
exp −
ρ
j
ri =
.
(11)
(µ + 1)i
The right-hand side of (11) is independent of j, indicating that all the HOL packets have the same
conditional probability of successful transmission. Therefore, we drop the superscript j, and write the
steady-state probability of successful transmission of HOL packets p as
p=
n−1
X
ri · Pr{i concurrent transmissions}.
(12)
i=0
In saturated conditions, all the nodes have non-empty queues. According to the Markov chain shown in
P
Fig. 1, the probability that the HOL packet is requesting transmission is given by (πD + π0 )q0 + K
i=1 πi qi ,
which is equal to π0 /p according to (8). Therefore, the probability that there are i concurrent transmissions
can be obtained as
n−1
(1 − π0 /p)n−1−i · (π0 /p)i .
Pr{i concurrent transmissions} =
i
(13)
By substituting (11) and (13) into (12), the steady-state probability of successful transmission of HOL
packets p can be obtained as
n−1
µ
µ
π0
p = exp −
· 1−
·
ρ
µ+1 p
for large n
≈
µ
nµ π0
,
exp − −
·
ρ µ+1 p
(14)
where the approximation is obtained by applying (1 − x)n ≈ exp (−nx) for 0 < x < 1.8 Finally, by
substituting (7) into (14), we have








 µ

nµ
1
p = exp − −
·
.

ρ µ + 1 PK−1 p (1 − p)i (1 − p)K 




+


i=0
qi
qK
(15)
The following theorem states the existence and uniqueness of the root of the fixed-point equation (15).
8
Note that with a small network size, i.e., n ≤ 5 for instance, the approximation error may become noticeable. It, nevertheless, rapidly
declines as the number of nodes n increases.
12
Theorem 1. The fixed-point equation (15) has one single non-zero root pA if {qi }i=0,...,K is a monotonic
non-increasing sequence.
Proof: See Appendix A.
As we can see from (15), the non-zero root pA is closely dependent on backoff parameters {qi }i=0,...,K .
Without loss of generality, let qi = q0 · Qi where q0 is the initial transmission probability and Qi is an
arbitrary monotonic non-increasing function of i with Q0 = 1 and Qi ≤ Qi−1 , i = 1, . . . , K. With the
cutoff phase K = 0, or the backoff function Qi = 1, i = 0, . . . , K, for instance, pA can be explicitly
written as
µ
nµ
pA = exp − −
q0 .
ρ µ+1
(16)
C. Maximum Network Throughput for Given µ and ρ
It has been shown in Section III-B that the network operates at the steady-state point pA in saturated
conditions. By combining (9) and (14), the network throughput at pA can be written as
ˆ out = (µ + 1) ·
λ
−pA ln pA pA
−
µ
ρ
,
(17)
where pA is an implicit function of the transmission probabilities qi , i = 0, . . . , K, which is given in (15).
It can be seen from (17) and (15) that the network throughput is crucially determined by the backoff
ˆ max = max{q } λ
ˆ out . The
parameters {qi }. In this section, we focus on the maximum network throughput λ
i
ˆ max and the corresponding optimal backoff
following theorem presents the maximum network throughput λ
parameters {qi∗ }.
Theorem 2. For given SINR threshold µ ∈ (0, ∞) and mean received SNR ρ ∈ (0, ∞), the maximum
network throughput is given by
ˆ max
λ
which is achieved at

µ
+
1
µ

1

if µ ≥ n−1
exp −1 −

µ ρ
=

nµ
µ

n exp −
otherwise,
−
µ+1 ρ
qi∗
=


qm Qi

1
if µ ≥
1
n−1
otherwise,
(18)
(19)
13
i = 0, . . . , K, where qm is given by

i K 


µ
µ
µ




1 − exp −1 −
exp −1 −
1 − exp −1 −
K−1


X
µ+1
ρ
ρ
ρ
qm =
+
.
·

nµ 
Q
Q
i
K





 i=0
(20)
Proof: See Appendix B.
ˆ max is a monotonic
(18) shows that for given SINR threshold µ, the maximum network throughput λ
increasing function of the mean received SNR ρ. As ρ → ∞, we have

µ + 1 −1

1

e
if µ ≥ n−1

µ
ˆ
lim λmax =
ρ→∞

nµ

n exp −
otherwise,
µ+1
(21)
ˆ max monotonically decreases
which approaches e−1 when µ ≫ 1. On the other hand, for given ρ, λ
as the SINR threshold µ increases, as Fig. 2a illustrates. With a lower µ, the receiver can decode more
packets among multiple concurrent transmissions, and thus better throughput performance can be achieved.
Corollary 1 shows that multipacket reception is possible if the SINR threshold µ is sufficiently small.
Corollary 1. 1) For µ ≥
2) For µ <
1
ˆ max > 1 if and only if 1 ≤ µ < 1 and ρ >
,λ
n−1
n−1
e−1
1
µ
ˆ max > 1 if and only if ρ >
,λ
nµ .
n−1
ln n −
µ+1
µ
.
µ+1
ln
−1
µ
Proof: See Appendix C.
As Fig. 2b illustrates, with n = 50, if the SINR threshold µ = 0.01 <
1
,
n−1
ˆ max > 1 when the
λ
mean received SNR ρ > −25.3dB according to Corollary 1. On the other hand, if µ = 0.5, we have
1
n−1
<µ<
1
e−1
ˆ max > 1 when the mean received SNR ρ > 7dB.
≈ 0.582. In this case, λ
D. Simulation Results
In this section, simulation results are presented to verify the preceding analysis. In particular, we
consider a saturated Aloha network with BEB, i.e., each node always has a packet to transmit, and the
transmission probabilities of each HOL packet are given by qi = q0 ·
1
,
2i
i = 0, . . . , K. Section III-B has
shown that it operates at the steady-state point pA , which is closely determined by the number of nodes n
and the backoff parameters {qi }. The expression of pA is given in (15) and verified by simulation results
14
2
2
10
10
1
1
10
10
0
0
10
ȜÖmax
ȜÖmax
10
-1
10
U = 0 dB
U = 10 dB
U = 20 dB
-2
10
-3
10
-2
P = 0.01
P = 0.5
P P 10
-3
10
-4
10 -4
10
-1
10
-4
-3
10
-2
10
1
n1
-1
10
ȝ
0
10
1
10
2
10
10
-30 -25.3 -20 -15 -10
(a)
-5
0
5 7 10
U (dB)
15
20
25
30
(b)
ˆ max versus SINR threshold µ. (b) Maximum network throughput λ
ˆ max versus mean received
Fig. 2. (a) Maximum network throughput λ
SNR ρ. n = 50.
presented in Fig. 3.9
ˆ out has
Fig. 4 illustrates the corresponding network throughput performance. The network throughput λ
been derived as a function of pA in (17), which varies with the backoff parameters. As we can see from
Fig. 4, the network throughput performance is sensitive to the setting of the initial transmission probability
q0 . According to Theorem 2, when the SINR threshold µ ≥
1
,
n−1
ˆ max
the maximum network throughput λ
ˆ max is achieved with qi =1, i = 0, . . . , K. The expressions
is achieved when q0 is set to be qm . Otherwise, λ
ˆ max and the corresponding optimal backoff parameters q ∗ are given in (18) and (19), respectively, and
of λ
i
verified by simulation results presented in Fig. 4.
ˆ max closely depends on
It can be also observed from Fig. 4 that the maximum network throughput λ
ˆ max under
the SINR threshold µ and the mean received SNR ρ. Fig. 5 presents the simulation results of λ
ˆ max increases as the mean received SNR
various values of µ and ρ. We can clearly see from Fig. 5 that λ
ρ grows or the SINR threshold µ decreases.
Note that in spite of the improvement on the network throughput performance by reducing the SINR
threshold µ, the information encoding rate that can be supported for reliable communications, i.e., R =
log2 (1 + µ), is quite low when µ is small. It is clear that the SINR threshold µ determines a tradeoff
between the network throughput and the information encoding rate. In the next section, we will further
study how to maximize the sum rate by properly choosing the SINR threshold µ.
9
In simulations, the steady-state probability of successful transmission of HOL packets pA is obtained by calculating the ratio of the
number of successful transmissions to the total number of attempts of HOL packets over a long time period, i.e., 108 time slots.
15
1
0.8
0.7
0.9
K=0
0.6
K=1
Analysis
Analysis
Simulation
Simulation
0.5
0.8
n = 30
pA
pA
0.7
0.4
K=3
0.3
Analysis
Simulation
Analysis
0.6
Simulation
0.5
0.2
n = 100
n = 50
Analysis
0.4
0.1
Analysis
Simulation
Simulation
0
0.01 0.1
0.2
0.3
0.4
0.5
q0
0.6
0.7
0.8
0.9
0.3
0.01 0.1
1
0.2
0.3
(a)
0.4
0.5
q0
0.6
0.7
0.8
0.9
1
(b)
Fig. 3. Steady-state operating point pA versus initial transmission probability q0 . (a) n = 50. µ = 1 and ρ = 10dB. (b) K = 0. µ = 0.01
and ρ = 0dB.
40
0.7
ȜÖmax=0.67
n 100
OÖmax
=37
35
0.6
n 50
OÖmax
=30
K=3
Analysis
Simulation
25
n 30
OÖmax
=22
K=0
0.4
Analysis
0.3
ȜÖ out
ȜÖ out
0.5
Simulation
20
n = 30
15
K=1
0.2
Analysis
n = 50
Simulation
0.1
Analysis
Simulation
10
5
denotes qm
0
0.04 0.07 0.15 0.2
0.3
0.4
0.5
q0
0.6
0.7
0.8
0.9
0
0.01
1
n = 100
Analysis
Simulation
Analysis
Simulation
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
q0
(a)
(b)
ˆ out versus initial transmission probability q0 . (a) n = 50. µ = 1 and ρ = 10dB. (b) K = 0. µ = 0.01 and
Fig. 4. Network throughput λ
ρ = 0dB.
IV. M AXIMUM S UM R ATE
It has been demonstrated in Section II that the sum rate of Aloha networks is determined by the
ˆ out . By combining (3) and (4), the maximum
information encoding rate R and the network throughput λ
sum rate can be written as
ˆ out .
ˆ out log (1 + µ) = max log (1 + µ) max λ
C = max λ
2
2
µ,{qi }
µ
{qi }
(22)
Section III further shows that if backoff parameters {qi } are properly selected, the network throughput
ˆ max , which is a function of the SINR threshold µ and the mean received SNR ρ. By
is maximized at λ
16
2
10
P P 1
10
Analysis
Simulation
Analysis
Simulation
0
ȜÖmax
10
-1
10
P Analysis
Simulation
-2
10
P -3
Analysis
Simulation
10
-4
10
-20
-15
-10
-5
0
5
U (dB)
10
15
20
25
30
ˆ max versus mean received SNR ρ under different values of SINR threshold µ. n = 50. K = 0 and
Fig. 5. Maximum network throughput λ
q0 = q0∗ .
combining (22) and Theorem 2, the maximum sum rate can be further written as
C = max f (µ),
µ>0
(23)
where the objective function f (µ) is given by

µ
µ+1

1

log (1 + µ) if µ ≥ n−1
exp −1 −

µ ρ 2
f (µ) =

µ
nµ

n exp −
log2 (1 + µ) otherwise.
−
µ+1 ρ
(24)
The following theorem presents the maximum sum rate and the optimal SINR threshold µ∗ .
Theorem 3. For given mean received SNR ρ ∈ (0, ∞), the maximum sum rate is
which is achieved at
 ∗
µh + 1
µ∗h


log (1 + µ∗h ) if ρ ≥ ρ0
exp −1 −

µ∗h ρ 2
C=

nµ∗
µ∗

n exp − ∗ l − l log2 (1 + µ∗l ) otherwise,
µl + 1
ρ
µ∗ =


µ∗h

µ∗
l
if ρ ≥ ρ0
(25)
(26)
otherwise,
where µ∗h and µ∗l are the roots of the following equations:
µ+1 1
+
µ = e,
(µ + 1) ρ
(27)
17
and
µ+1
n
+
µ + 1 = e,
(µ + 1) ρ
respectively, and
(28)
n
n
ln
n−1 n−1 .
ρ0 =
n
1 − (n − 1) ln
n−1
(29)
Proof: See Appendix D.
Note that ρ0 is a monotonic decreasing function of n ∈ [2, ∞), and limn→∞ ρ0 = 2. When the number
of nodes n is large, ρ0 is close to 3dB.
A. Optimal SINR Threshold µ∗
Theorem 3 shows that to achieve the maximum sum rate, the SINR threshold µ should be carefully
selected. Fig. 6a illustrates how the optimal SINR threshold µ∗ varies with the mean received SNR ρ. At the
1
low SNR region, i.e., ρ < ρ0 , for instance, we can obtain from (26) and (28) that µ∗ρ<ρ0 = µ∗l ≈ e−W0 (− n ) −1
for large n, where W0 (z) is the principal branch of the Lambert W function [49]. With a large number
of nodes n, µ∗ρ<ρ0 ≪ 1, implying that multiple packets can be successfully decoded. At the high SNR
region, we can obtain from (26-27) that µ∗ρ≥ρ0 = µ∗h ≈ eW0 (ρ) for large ρ. As we can see from Fig. 6a,
with ρ ≫ 1, the optimal SINR threshold monotonically increases with the mean received SNR ρ.
By combining (26) with Theorem 2, we can also obtain the maximum network throughput with µ = µ∗
as
ˆ µ=µ∗
λ
max
 ∗
µh + 1
µ∗h


if ρ ≥ ρ0
exp −1 −

µ∗h ρ
=

µ∗
nµ∗

n exp − ∗ l − l
otherwise.
µl + 1
ρ
(30)
ˆ µ=µ∗ linearly increases with the
As we can see from Fig. 6b, at the low SNR region, i.e., ρ < ρ0 , λ
max
number of nodes n. In this case, the optimal SINR threshold µ∗ρ<ρ0 = µ∗l is a monotonic decreasing
function of n, and thus more packets can be successfully decoded as n grows. For large n, we have
µ=µ∗
ˆ max,ρ<ρ
λ
≈ ne−1 according to (30). At the high SNR region, Fig. 6a has shown that the optimal SINR
0
threshold µ∗ρ≥ρ0 = µ∗h is much larger than 1, with which at most one packet can be successfully decoded
at each time slot. Therefore, the maximum network throughput quickly drops below 1, and eventually
approaches e−1 as ρ → ∞.
18
3
2
10
10
2
n 30
10
n 30
n 50
1
10
100
100
n
ȜÖ max
ȝ=ȝ*
n
0
ȝ*
n 50
1
10
10
-1
0
10
10
-2
10
-3
-1
10
-20
-15
-10
-5
0
5
10
U (dB)
15
20
25
10
-20
30
-15
-10
(a)
-5
0
5
U (dB)
10
15
20
25
30
(b)
∗
ˆ µ=µ
Fig. 6. (a) Optimal SINR threshold µ∗ versus mean received SNR ρ. (b) Maximum network throughput λ
max versus mean received SNR
ρ.
e 1 log 2 e
2.5
0.5
n 100
(25)
2
0.4
C (bit/s/Hz)
C (bit/s/Hz)
(31)
1.5
1
0.5
(32)
n 30
0.2
3
5
10
15
U (dB)
Large-n approximation
20
25
30
(a)
Fig. 7.
0.3
0.1
High SNR
approximation
0
(25)
0
-20
-15
-10
U (dB)
-5
0
3
(b)
(a) Maximum sum rate C at the high SNR region. (b) Maximum sum rate C at the low SNR region.
B. Maximum Sum Rate C
Similar to Section IV-A, let us take a closer look at the maximum sum rate C at different SNR regions.
1) ρ ≥ ρ0 : With ρ ≥ ρ0 , it has been shown in Section IV-A that the optimal SINR threshold µ∗ρ≥ρ0 =
µ∗h ≈ eW0 (ρ) for large ρ. The maximum sum rate in this case can be then approximated by
−W0 (ρ)
Cρ≥ρ0 ≈ 1 + e
eW0 (ρ)
log2 (1 + eW0 (ρ) ),
exp −1 −
ρ
(31)
19
for ρ ≫ 1. As Fig. 7a shows, the approximation (31) works well when the mean received SNR ρ is large,
i.e., ρ ≥ 15dB. Moreover, a logarithmic increase of the maximum sum rate C can be observed at the high
SNR region. The following corollary presents the high-SNR slope of C.
Corollary 2. limρ→∞
C
log2 ρ
= e−1 .
Proof: See Appendix E.
Recall that the high-SNR slope of the sum capacity of multiple access channels is 1 when single-antenna is
employed at both the transmitters and the receiver. To achieve the sum capacity, however, a joint decoding
of all received signals is required and the codewords should span multiple fading states. With the capture
model, in contrast, each node’s packet is decoded independently by treating others’ as background noise
at each time slot. When the mean received SNR is high, at most one packet can be successfully decoded
each time due to a large SINR threshold µ∗ ≫ 1. Corollary 2 shows that with the simplified receiver, the
high-SNR slope of the maximum sum rate of Aloha networks is significantly lower than that of the sum
capacity.
2) ρ < ρ0 : For ρ < ρ0 , it has been shown in Section IV-A that the optimal SINR threshold µ∗ρ<ρ0 =
1
µ∗l ≈ e−W0 (− n ) − 1 for large n. The corresponding maximum sum rate can be then approximated by
!
e−W0 (− n1 ) − 1
1
1
Cρ<ρ0 ≈ −nW0 −
exp −n 1 − eW0 (− n ) −
log2 e,
(32)
n
ρ
for n ≫ 1. As we can see from Fig. 7b, the approximation (32) works well when the number of nodes n
is large. The following corollary further presents the limiting maximum sum rate as n → ∞ at the low
SNR region.
Corollary 3. limn→∞ Cρ<ρ0 = e−1 log2 e.
Proof: See Appendix F.
Note that it has been shown in Section IV-A that with ρ < ρ0 , the maximum network throughput
ˆ µ=µ∗ ≈ ne−1 , which grows with the number of nodes n unboundedly. Although more packets can be
λ
max
successfully decoded as n increases, the information carried by each packet decreases due to a diminishing
information encoding rate, i.e., R = log2 (1 + µ∗ρ<ρ0 ) ≈
1
n
log2 e for large n. Therefore, as the number of
nodes n → ∞, the maximum sum rate reaches a limit that is independent of the mean received SNR,
as Corollary 3 indicates. It is in sharp contrast to the sum capacity of multiple access channels which
linearly increases with n and ρ at the low SNR region.
20
Rs (bit/s/Hz)
CU
=1.02
1
15 dB
U 15 dB
0.8
CU
Analysis
Simulation
=0.73
10 dB
0.6
CU
=0.53
0 dB
0.4
U
0.2
U 10 dB
0 dB
Analysis
Analysis
Simulation
Simulation
denotes P *
0
0.02
Fig. 8.
2 2.9
4
6
8
9.2 10
12
14
16
18
20
P
Sum rate Rs versus SINR threshold µ under different values of mean received SNR ρ. n = 50. K = 0 and q0 = q0∗ .
C. Simulation Results
In this section, simulation results are presented to verify the preceding analysis. Again we consider
a saturated Aloha network with the cutoff phase K = 0. Section III has shown that for given SINR
threshold µ and mean received SNR ρ, the initial transmission probability q0 should be set as q0∗ , which
is given in Theorem 2, to maximize the network throughput. Fig. 8 illustrates the corresponding sum rate.
We can clearly observe from Fig. 8 that the sum rate performance is sensitive to the SINR threshold
µ especially when the mean received SNR ρ is small. To achieve the maximum sum rate, µ should be
properly set according to the mean received SNR ρ. The expressions of the optimal SINR threshold µ∗
and the maximum sum rate C are given in Theorem 3, and verified by simulation results presented in
Fig. 8.
V. D ISCUSSIONS
So far we have shown that to optimize the sum rate performance of Aloha networks, the SINR threshold
µ and backoff parameters {qi } should be properly set according to the mean received SNR ρ, and the
maximum sum rate logarithmically increases with ρ with the high-SNR slope of e−1 . In this section, we
will further discuss how the performance is affected by key factors such as backoff, multipacket-reception
capability, channel fading and power control.
A. Effect of Backoff
Backoff is a key component of random-access networks. It has been shown in Sections III and IV
that to achieve the maximum sum rate, backoff parameters, i.e., the transmission probabilities {qi } of
21
nodes, should be carefully selected according to the number of nodes n and the mean received SNR ρ. In
many studies, however, nodes are supposed to transmit their packets with a fixed probability [23], [25],
[26], [33], [36]. To see how the rate performance of Aloha deteriorates without proper backoff, let us
assume that each node transmits its packet with a constant probability q at each time slot, i.e., qi = q,
i = 0, . . . , K. In this case, the network steady-state point in saturated conditions can be obtained from
(15) as
qi =q
pA
µ
nqµ
= exp − −
ρ µ+1
,
(33)
and the corresponding network throughput is
µ
nqµ
qi =q
ˆ
,
λout = nq exp − −
ρ µ+1
(34)
according to (17). The sum rate can be then written as
Rsqi =q
µ
nqµ
= nq exp − −
· log2 (1 + µ),
ρ µ+1
(35)
which is an increasing function of the mean received SNR ρ.
As ρ → ∞, it can be easily obtained from (35) that
˜ sqi =q
R
=
limρ→∞ Rsqi =q
log2 (1 + µ), with the maximum
nqµ
·
= nq exp −
µ+1
˜ qi =q = nq exp −nq 1 − eW0 (− nq1 ) · log2 e−W0 (− nq1 ) ,
max R
s
(36)
µ∗,qi =q = e−W0 (− nq ) − 1.
(37)
µ
which is achieved at
1
(37) shows that the optimal SINR threshold µ∗,qi=q monotonically decreases as the number of nodes n
grows. For large n ≫ 1, it can be easily obtained from (36-37) that µ∗,qi=q ≈
˜ sqi=q n≫1
max R
≈ e−1 log2 e.
µ
1
,
nq
and
(38)
Recall that it has been shown in Section IV-B that the maximum sum rate increases with the mean
received SNR ρ unboundedly. Here (38) indicates that with a constant transmission probability, the sum
rate converges to a limit that is much lower than 1 as ρ → ∞. It corroborates that proper backoff design
is indispensable for random-access networks.
22
It is interesting to note that when q = 1, all the nodes persistently transmit their packets, and the Aloha
network reduces to a typical multiple access channel. It is well known that for an n-user AWGN multiple
access channel, if the capture model is adopted at the receiver side10 and all the users have equal received
power, the sum rate approaches log2 e as n → ∞ [50]. Here we can see from (38) that an additional
factor of e−1 is introduced, which is mainly attributed to the effect of channel fading.11
B. Effect of Multipacket Reception
In this paper, we focus on the capture model where a packet can be successfully decoded at the receiver
side if and only if the received SINR is above the threshold µ. If µ is small enough, multiple packets can
be successfully decoded each time, and thus the network throughput performance is substantially enhanced
compared to the classical collision model where at most one packet can be successfully decoded at each
time slot. Such an improvement has been widely observed in the literature [23]–[27], [29], [30], [32],
[33], [36]. As we will demonstrate in this section, despite a prominent throughput increase brought by
multipacket reception, the maximum sum rate with the capture model is indeed comparable to that with
the collision model.
Specifically, let us consider the classical collision model where a packet transmission is successful only
if there are no concurrent transmissions. To support an information encoding rate of R bit/s/Hz, the SNR
threshold at the receiver side should be set to µ = 2R − 1. Appendix G shows that in this case, the
maximum sum rate is given by
C
collision
eW0 (ρ) − 1
= exp −1 −
· log2 (eW0 (ρ) ),
ρ
(39)
which is achieved when the SNR threshold is set to be µ∗,collision = eW0 (ρ) − 1. The corresponding
maximum network throughput is given by
ˆ µ=µ∗ ,collision
λ
max
eW0 (ρ) − 1
= exp −1 −
ρ
.
(40)
We can see from (40) that the maximum network throughput with the collision model is always smaller
W (ρ) −1
than e , and the factor exp − e 0 ρ −1 describes the throughput loss due to channel fading. As Fig.
9a shows, at the low SNR region, it is much lower than the maximum network throughput with the
10
It is also referred to as the “conventional CDMA receiver” in the literature.
Note that in this paper, each codeword is assumed to last for one channel coherence time period. Without coding over different fading
states, the channel fluctuations cannot be averaged out, thus leading to a significant rate loss compared to the AWGN case.
11
23
1
10
1
Capture model (30)
10
0
10
ȜÖ max
ȝ=ȝ*
C (bit/s/Hz)
Collision model (40)
-1
10
0
10
Capture model (25)
-2
10
Collision model (39)
-1
10
-20
-3
-15
-10
-5
0
5
U (dB)
10
15
20
25
30
10
-20
-15
-10
(a)
-5
0
5
U (dB)
10
15
20
25
30
(b)
Fig. 9. Network performance of Aloha with collision model and capture model over fading channels. n = 50. (a) Maximum network
throughput versus mean received SNR. (b) Maximum sum rate versus mean received SNR.
capture model that can be much higher than 1 thanks to multipacket reception. The gap is, nevertheless,
diminished as the mean received SNR ρ increases. Both of them approach e−1 as ρ → ∞.
In spite of the significant throughput improvement, only marginal gains on the sum rate performance can
be observed at the low SNR region. As Fig. 9b illustrates, the maximum sum rate with the collision model is
close to that with the capture model even when the mean received SNR ρ is small. As we have demonstrated
in Section IV-B, the maximum sum rate with the capture model is limited by e−1 log2 e ≈ 0.5307 with
ρ < ρ0 . The rate difference rapidly decreases as the mean received SNR ρ increases, indicating that
the collision model serves as a good approximation for the capture model when analyzing the sum rate
performance of Aloha networks.
C. Effect of Fading
Section IV has shown that with the capture model, the network throughput of Aloha over fading channels
can be much higher than e−1 , the maximum network throughput with the collision model in ideal channel
conditions. In the literature, it is sometimes mistaken as an improvement brought by fading channels [24],
[26], [27], [30]: the variation of the received power of nodes is enlarged due to fading, and thus the chance
that one of them can be captured, i.e., with much higher received power than others, is increased. As we
will demonstrate in this section, the gain comes from the receiver rather than the channel fading. If the
receiver model is fixed, both the maximum network throughput and the maximum sum rate of Aloha over
AWGN channels are always higher than that over fading channels.
24
Let us first assume that the capture model is adopted. Specifically, by setting the small-scale fading
coefficients |hk | = 1, k = 1, . . . , n, the steady-state probability of successful transmission of a HOL
packet given that there are i concurrent transmissions over AWGN channels can be easily obtained from
(10) as
riAW GN
= Pr
1
≥µ
i + 1/ρ
=


1

0
if i ≤ ⌊ µ1 − 1ρ ⌋
(41)
otherwise.
By substituting (41) and (13) into (12), the steady-state probability of successful transmission of HOL
packets can be written as



0
if ⌊ µ1 − ρ1 ⌋<0

1

⌊µ
− ρ1 ⌋ 

X n−1
p=
(1−π0 /p)n−1−i · (π0 /p)i = 1
if ⌊ µ1 − ρ1 ⌋≥n−1

i

i=0

k j
k j


1
1
1
1
I
,
+1
otherwise,
−
−
n−1−
1−π0 /p
µ ρ
µ ρ
(42)
where Ix (a, b) is the regularized incomplete beta function. Appendix H shows that with K = 0, the
maximum sum rate is given by
C AW GN



e−1 log2 (1 + ρ)
=

1

n log2 1 + n−1+ 1
if ρ ≥ ρ1
(43)
otherwise,
ρ
which is achieved when the SINR threshold is set to be



ρ
∗,AW GN
µ
=

1

 n−1+
1
if ρ ≥ ρ1
(44)
otherwise,
ρ
and the corresponding maximum network throughput is given by
ˆ µ=µ∗ ,AW GN =
λ
max
where ρ1 is the root of the following equation:
n log2


e−1

n
1
1+
n−1+
For large number of nodes n, ρ1 ≈ ee − 1.
1
ρ
!
if ρ ≥ ρ1
(45)
otherwise,
= e−1 log2 (1 + ρ).
(46)
25
1
10
2
10
1
ȝ=ȝ*
C (bit/s/Hz)
10
0
ȜÖ max
10
0
10
Fading Channel (30)
Fading Channel (25)
AWGN Channel (45)
AWGN Channel (43)
-1
-1
10
-20
-15
-10
-5
0
5
U (dB)
10
15
20
25
30
10
-20
-15
-10
-5
(a)
0
5
U (dB)
10
15
20
25
30
(b)
Fig. 10. Network performance of Aloha with the capture model over AWGN and fading channels. n = 50. (a) Maximum network throughput
versus mean received SNR. (b) Maximum sum rate versus mean received SNR.
GN
1
= n−1+
We can see from (44) that at the low SNR region, by setting the SINR threshold µ = µ∗,AW
1 ,
ρ<ρ1
ρ
k
j
we have µ1 − 1ρ = n − 1, with which all the packets can be successfully decoded according to (42).
To maximize the network throughput, all the nodes should transmit with probability 1, and thus the
maximum network throughput is equal to the number of nodes n. As n → ∞, the maximum sum rate
AW GN
Cρ<ρ
→ log2 e according to (43), which is consistent to the asymptotic sum rate of an n-user AWGN
1
multiple access channel with the capture model [50]. Recall that it has been shown in Section IV that in
the fading case, the maximum sum rate and the corresponding maximum network throughput at the low
SNR region are approximately given by e−1 log2 e and ne−1 , respectively, for large n. Both of them are
significantly lower than that over AWGN channels, as Fig. 10 illustrates.
GN
µ∗,AW
ρ≥ρ1
j
1
µ
1
ρ
k
At the high SNR region, by setting the SINR threshold µ =
= ρ, we have
= 0.
−
k
j
According to (42), with µ1 − ρ1 = 0, a packet can be successfully decoded if and only if there are no
concurrent transmissions. In this case, the receiver reduces to the collision model. The maximum network
throughput is then e−1 , and the maximum sum rate logarithmically increases with the mean received SNR
ρ with the high-SNR slope e−1 . As we can see from Fig. 10b, although the sum rates over AWGN and
fading channels have the same high-SNR slope, substantial gains are observed in the AWGN case.
If the collision model is adopted, the maximum network throughput of Aloha over perfect channel
conditions is well known to be e−1 . The maximum sum rate of Aloha over AWGN channels can be
then easily obtained as e−1 log2 (1 + ρ). We can clearly see from (39) that over fading channels, the
26
maximum sum rate is upper-bounded by e−1 log2 (eW0 (ρ) ) < e−1 log2 (1 + ρ). (40) also shows that the
corresponding maximum throughput is always smaller than e−1 . It corroborates that if CSI is not available
at the transmitter side, fading always hurts [50].
D. Effect of Power Control
So far we have focused on a homogeneous Aloha network where all the nodes have the same mean
received SNR ρ. In this section, the analysis will be extended to the heterogeneous case, where nodes in
the same group have identical mean received SNRs but SNRs differ from group to group.
Specifically, assume that n nodes are divided into M groups. Group i has ni nodes, and each node
in Group i has the mean received SNR ρi , i = 1, . . . , M. For HOL packet j, let Sj denote the set of
nodes that have concurrent transmissions. It can be successfully decoded at the receiver if and only if
P
j
its received SINR is above the SINR threshold µ, i.e., P
2 ≥ µ, where Pk denotes the received
k∈Sj Pk +σ
S
power of node k’s packet. Suppose that Sj = m=1,...,M Sjm , where Sjm denotes the set of nodes which
have concurrent transmissions in Group m, and |Sjm | = im , m = 1, . . . , M. The steady-state probability
of successful transmission of HOL packet j given that there are {im }m=1,...,M concurrent transmissions,
j
r{i
, can be then written as
m}
j
r{i
= Pr
m}



|hj |
PM
m=1
P
k∈Sjm
2
|hk |2 ·
ρm
ρj
+
j
Appendix I shows that with hk ∼ CN (0, 1), r{i
is given by
m}
µ
exp −
ρj
j
r{i
= QM
m}
m=1 (1
+
ρm
µ)im
ρj
1
ρj
≥µ


.
(47)

.
(48)
The steady-state probability of successful transmission of HOL packet j, p(j) , can be written as
p
(j)
=
n1
X
i1 =0
nj −1
···
X
ij =0
···
nM
X
iM =0
j
r{i
m}
·
M
Y
Pr{im concurrent transmissions in Group m}.
(49)
m=1
For each node in Group m, the probability that it is busy with the HOL packet requesting transmission
P
(m)
(m)
(m)
(m)
in saturated conditions is given by (πD + π0 )q0 + K
qi , which is equal to π0 /p(m) according
i=1 πi
27
to (8). Therefore, we have
Pr{im



nm −im im
(m)
(m)
1 − π0 /p(m)
· π0 /p(m)
concurrent transmissions in Group m} =

 nj −1 1 − π (j) /p(j) nj −1−ij · π (j) /p(j) ij
0
0
ij
nm
im
m 6= j
m = j.
(50)
By combining (48-50), the steady-state probability of successful transmission of HOL packet j can be
obtained as
p(j)
µ
= exp −
·
ρj
for large n1 ,...,nM
≈
(j)
µ
π0
1−
· (j)
µ+1 p
!nj −1
M
X
M
Y
(m)
µ
π0
1−
· (m)
µ + ρj /ρm p
m=1,m6=j
(m)
µ
π0
nm µ
exp − −
· (m)
ρj m=1 µ + ρj /ρm p
!
.
(51)
Finally, by substituting (7) into (51), we have

M
X
1
nm µ
 µ
(j)
p = exp − −
·
ρj m=1 µ + ρj /ρm PK−1 p(m) (1−p(m) )i
i=0
!nm
qi
+
(1−p(m) )
qK
K


.
(52)
We can see from (52) that in the heterogeneous case, HOL packets in different groups have distinct
(m)
steady-state probabilities of successful transmission. With M groups, M non-zero roots {pA }m=1,...,M
can be obtained by jointly solving M fixed-point equations given in (52). Note that nodes in the same
group have the same steady-state probability of successful transmission and thus the same throughput
performance. For each node in Group m, m = 1, . . . , M, the node throughput can be obtained from (7)
as
(m)
(m)
λout = π0
=
1
i
PK−1 1−p(m)
A
i=0
qi
+
(m) K
1−pA
,
(53)
(m)
pA qK
(m)
ˆ out = PM nm λout
.
and the network throughput is λ
m=1
To illustrate the above results, let us focus on the two-group case and assume that the cutoff phase
K = 0. The steady-state probabilities of successful transmission of HOL packets in Group 1 and Group
2 can be obtained from (52) as
(1)
pA
n1 µq0
n2 µq0
µ
−
= exp − −
ρ1
µ + 1 µ + ρ1 /ρ2
(54)
28
and
(2)
pA
µ
n1 µq0
n2 µq0
= exp − −
−
ρ2 µ + ρ2 /ρ1
µ+1
,
(55)
respectively. By combining (54-55) with (53), the node throughput can be obtained as
(1)
λout
,
(56)
.
(57)
µ
n1 µq0
n2 µq0
= q0 exp − −
−
ρ1
µ + 1 µ + ρ1 /ρ2
and
(2)
λout
µ
n1 µq0
n2 µq0
= q0 exp − −
−
ρ2 µ + ρ2 /ρ1
µ+1
(56-57) shows that the throughput performance is closely determined by the mean received SNRs. If the
two groups have equal mean received SNRs ρ1 = ρ2 = ρ, for instance, we can see from (54-55) that all the
(1)
(2)
HOL packets have the same steady-state probability of successful transmission, i.e., pA = pA . The node
(1)
(2)
(n1 +n2 )µq0
µ
throughput can be obtained from (56-57) as λout = λout = q0 exp − ρ −
. In this case, each
µ+1
node has an equal probability of accessing the channel, thus achieving the same throughput performance.
As the difference between ρ1 and ρ2 grows, nevertheless, the node throughput performance becomes
(1)
(2)
increasingly polarized. We can see from (54-55) that with ρ1 ≫ ρ2 , pA ≫ pA , which indicates that
much more packets from Group 1 can be successfully received than Group 2. The throughput performance
(1)
(2)
of nodes in Group 1 is then much better than that in Group 2, i.e., λout ≫ λout according to (56-57),
implying serious unfairness among nodes.
ˆ max = maxq λ
ˆ out does not have an explicit expression in general,
As the maximum network throughput λ
0
ˆ max · log (1 + µ). Fig. 11 illustrates
we can only numerically calculate the maximum sum rate C = maxµ λ
2
how the maximum sum rate C varies with the ratio of ρ1 and ρ2 by fixing the mean SNR of nodes
ρ¯ =
P2
m=1 nm ρm
P
2
m=1 nm
to 0dB, 10dB, 15dB and 20dB. It is interesting to note from Fig. 11 that with a large SNR
ratio ρ1 /ρ2 ≫ 1, the maximum sum rate is higher than that with ρ1 /ρ2 = 1, which suggests that despite
serious unfairness, the sum rate performance may be improved by introducing a large SNR difference
among nodes.
To see why, let us take a closer look at the network performance with ρ1 /ρ2 → ∞. In this case, the
ρ1 /ρ2 →∞
n1 µq0
µ
ˆ
network throughput can be obtained from (56-57) as λout
= n1 q0 exp − n1 +n2 ρ¯ − µ+1 , which ren1
ρ
/ρ
→∞
µ+1
µ
1
2
ˆ
duces to the throughput of Group 1. For large µ, it can be obtained that λmax
= µ exp −1 − n1 +n2 ρ¯
n1
o
n
ρ1 /ρ2 =1
ρ1 /ρ2 →∞
µ+1
µ
ˆ
ˆ
and λmax
= µ exp −1 − ρ¯ according to (18), which can be further written as λmax
(¯
ρ) =
29
1.6
U
1.4
20 dB
C (bit/s/Hz)
1.2
U 15dB
1
0.8
U 10 dB
0.6
0.4
1
Fig. 11.
U
100
200
300
400
500
U1 U 2
600
0 dB
700
800
900 1000
Maximum sum rate versus ρ1 /ρ2 for a two-group Aloha network. n1 = n2 = 25. K = 0.
1 /ρ2 =1 n1 +n2
1 /ρ2 =1
2
ˆ ρmax
ˆ ρmax
λ
( n1 ρ¯) > λ
(¯
ρ). As a result, for ρ¯ ≫ 1, we have C ρ1 /ρ2 →∞ (¯
ρ) = C ρ1 /ρ2 =1 ( n1n+n
ρ¯) >
1
C ρ1 /ρ2 =1 (¯
ρ). Intuitively, the channel efficiency is maximized by allocating all the resources to the strongest
node(s). Here we can see that even without a central controller for resource allocation, the fundamental
tradeoff between efficiency and fairness still holds true for random-access networks.
The tradeoff nevertheless becomes less significant when the network operates at the low SNR region.
It can be observed from Fig. 11 that with ρ¯ = 0dB, the maximum sum rate is insensitive to the SNR
ratio. It indicates that power control is desirable in this case, with which the fairness performance can be
improved without sacrificing the sum rate.
VI. C ONCLUSION
In this paper, the unified analytical framework proposed in [20], [21] is extended to incorporate the
capture model. By assuming that the received SNRs of nodes’ packets are exponentially distributed with
the same mean received SNR ρ in a saturated Aloha network, explicit expressions of the maximum network
throughput and the corresponding optimal backoff parameters are obtained, based on which the maximum
sum rate is derived by optimizing the SINR threshold µ. The analysis shows that with a low SNR, the
maximum sum rate linearly increases with the number of nodes n, and approaches e−1 log2 e as n → ∞.
At the high SNR region, a logarithmic growth of the maximum sum rate is observed as ρ increases, with
the high-SNR slope of e−1 . Effects of key factors, including backoff, receiver model, channel fading and
power control, on the sum rate performance are also studied.
The analysis sheds important light on the practical network design. For instance, it is demonstrated that
30
to achieve the maximum sum rate, the transmission probabilities of nodes should be carefully selected
according to the network size and the mean received SNR ρ. With a fixed transmission probability, the
sum rate may significantly deteriorate, and converges to a limit that is much lower than 1 as ρ → ∞.
Moreover, the throughput performance of each node is found to be closely dependent on its mean received
SNR. Although a large SNR difference among nodes may be beneficial to the sum rate performance, it
introduces serious unfairness. A uniform mean received SNR is shown to be crucial for achieving a good
balance between fairness and sum rate when the network operates at the low SNR region.
Note that the analysis is based on the capture model, which is essentially a single-user detector.
Performance gains on the maximum sum rate and network throughput can be expected if multiuser
detectors, such as SIC, are adopted. It is therefore important to further extend the analysis to incorporate
more advanced receiver structures. Moreover, this paper considers a saturated network, where the network
throughput is pushed to the limit, yet the mean queueing delay is infinite and the network could be
unstable. It is of great practical significance to further study the maximum sum rate of Aloha under
certain system constraints, such as stability or delay requirements. Finally, a key assumption throughout
the paper is that the nodes are unaware of the instantaneous realizations of the small-scale fading, and
they encode their packets independently at the same rate. It has been shown in the literature that if CSI
is available at the transmitter side, the network performance of Aloha can be significantly improved by
adaptively adjusting the transmission probability according to CSI [19], [39]. How to characterize the
maximum sum rate with CSI at the transmitter side is another interesting and challenging issue, which
deserves much attention in the future study.
A PPENDIX A
P ROOF
OF
T HEOREM 1
Proof: The right-hand side of (15) can be written as
µ
nµ
1
h(p) = exp − −
,
·
ρ µ + 1 g(p)
(58)
PK−1 p (1 − p)i
(1 − p)K
+
. Define q˜i = 1/qi , for 0 ≤ i ≤ K − 1, and q˜i = 1/qK for
where g(p) = i=0
qi
qK
i ≥ K. g(p) can be then written as
g(p) =
∞
X
i=0
p(1 − p)i q˜i = EX [˜
qX ] ,
(59)
31
where X is a geometric random variable with parameter p.
Suppose that 0 < p1 < p2 ≤ 1. Let X1 and X2 denote geometric random variables with parameters p1
and p2 , respectively. Then we have X1 ≥st X2 [51].12 As {qi } is a monotonic non-increasing sequence,
we have q˜X1 ≥st q˜X2 . We can then conclude from (59) that g(p1) ≥ g(p2 ). Therefore, g(p) is a monotonic
non-increasing function with respect to p, which indicates that h(p) is a monotonic non-increasing function
according to (58).
µ
nµ
µ
nµ
Moreover, as limp→0 h(p) = exp − −
· qK > 0 and limp→1 h(p) = exp − −
· q0 <
ρ µ+1
ρ µ+1
1, we can then conclude that (15) has a single non-zero root if {qi }i=0,...,K is a monotonic non-increasing
sequence.
A PPENDIX B
P ROOF
OF
T HEOREM 2
Proof: It is shown in (17) that the network throughput can be obtained as an explicit function of pA .
ˆ p = maxp ∈(0,1] λ
ˆ out and the corresponding optimal steady-state
The following lemma first presents λ
max
A
point p∗A .
ˆ p is given by
Lemma 1. For given SINR threshold µ ∈ (0, ∞) and mean received SNR ρ ∈ (0, ∞), λ
max
ˆp
λ
max
µ
µ+1
,
exp −1 −
=
µ
ρ
(60)
which is achieved at
p∗A
µ
.
= exp −1 −
ρ
(61)
ˆ out with respect to pA is given by − µ+1 < 0,
Proof: According to (17), the second-order derivative of λ
µpA
ˆ out is a strictly concave function of pA ∈ (0, ∞) with
for pA ∈ (0, ∞). Therefore, we can conclude that λ
one global maximum at p∗A , where p∗A is the root of
(µ + 1) ·
ˆ out
dλ
dpA
= 0, i.e.,
− ln pA − 1 1
−
µ
ρ
= 0,
(62)
which is given by (61). (60) can be obtained by substituting (61) into (17).
ˆ p , the backoff parameters {qi }i=0,...,K should
We can see from Lemma 1 and (15) that to achieve λ
max
be carefully selected such that pA = p∗A . For given backoff function Qi , the optimal initial transmission
12
X1 ≥st X2 denotes that a random variable X1 is larger than a random variable X2 in the usual stochastic order, i.e., Pr(X1 > x) ≥
Pr(X2 > x) for all x ∈ (−∞, ∞).
32
ˆ p can be easily obtained by combining (15) and (61) as (20).
probability qm for achieving λ
max
ˆ p is achievable for qi ∈ (0, 1], i = 0, . . . , K,
Note that qm should not exceed 1. Lemma 2 shows that λ
max
if and only if the SINR threshold µ ≥
1
.
n−1
ˆ p is achievable if and only if µ ≥
Lemma 2. λ
max
1
.
n−1
˜ i = 1/Qi , for 0 ≤ i ≤ K − 1, and Q
˜ i = 1/QK for i ≥ K. Let Y denote a geometric
Proof: Define Q
µ
. (20) can be then written as
random variable with parameter exp −1 −
ρ
qm =
µ+1
˜ Y ].
· EY [Q
nµ
(63)
˜ Y ] ≥ 1.
As Qi ≤ 1 for i = 0, 1, . . . , K, we have EY [Q
1
˜ Y ] = 1 and qm = µ + 1 ≤ 1. In this
, with Qi = 1 for i = 0, 1, . . . , K, we have EY [Q
n−1
nµ
can be achieved by setting q0 = qm .
1) if : if µ ≥
ˆp
case, λ
max
2) only if : if µ <
For µ <
1
,
n−1
1
ˆ p is not achievable.
, we have qm > 1 according to (63), which indicates that λ
max
n−1
ˆ p is not achievable for qi ∈ (0, 1], i = 0, . . . , K. The following lemma shows that
λ
max
ˆ max is always smaller than λ
ˆ p , which is achieved by
in this case, the maximum network throughput λ
max
setting qi = 1, i = 0, . . . , K.
Lemma 3. For given SINR threshold µ <
1
µ< n−1
ˆ max
λ
1
,
n−1
ˆ max is given by
the maximum network throughput λ
nµ
µ
,
= n exp −
−
µ+1 ρ
(64)
which is achieved at qi∗ = 1, i = 0, . . . , K.
Proof: According to (15), the initial transmission probability q0 can be written as
µ+1
µ
q0 =
− ln pA −
· z(pA ).
nµ
ρ
(65)
PK−1 pA (1 − pA )i (1 − pA )K
+
. Similar to g(p) in Appendix A, it can be proved that
where z (pA ) = i=0
Qi
QK
z (pA ) is a monotonic non-increasing function of pA ∈ (0, 1]. Note that − ln pA is also a monotonic
non-increasing function of pA ∈ (0, 1]. Therefore, we can conclude from (65) that pA is a monotonic
33
non-increasing function of q0 . With 0 < q0 ≤ 1, we can obtain from (15) that






 µ

nµ
1
pA ≥ exp − −
,
·

ρ µ + 1 PK−1 pA (1 − pA )i (1 − pA )K 




+
i=0
Qi
QK
(66)
where “=” holds when q0 = 1. Note that the backoff function Qi ≤ 1, i = 0, . . . , K. We can further
obtain from (66) that
µ
nµ
pA ≥ exp − −
ρ µ+1
,
(67)
where “=” holds when q0 = 1 and Qi = 1, i = 0, . . . , K.
1
When µ < n−1
, we can see from (67) that pA > exp − µρ − 1 = p∗A . According to the proof of Lemma
ˆ out is a monotonic decreasing function of pA when pA > p∗ . Therefore, in
1, the network throughput λ
A
n
o
ˆ out is maximized when pA is minimized, i.e., pA = exp − µ − nµ according to (67), which
this case, λ
ρ
µ+1
o
n
nµ
∗
into (17).
is achieved at qi = 1. (64) can be then obtained by substituting pA = exp − µρ − µ+1
Finally, (18) and (19) can be obtained by combining Lemma 1, Lemma 2 and Lemma 3.
A PPENDIX C
P ROOF
C OROLLARY 1
µ+1
µ
1
ˆ
Proof: 1) When µ ≥ n−1 , we have λmax = µ exp −1 − ρ according to (18).
µ
µ
1
1
> 0.
i) if : if n−1
> 1 if ρ > ln µ+1
≤ µ < e−1
, we have µ+1
exp
−1
−
µ
ρ
µ −1
1
ii) only if : if µ ≥ e−1
, we have µ+1
exp −1 − µρ ≤ exp − µρ < 1 for ρ > 0. On the other hand, if
µ
µ
µ+1
µ
≤ 1.
exp
−1
−
,
we
have
ρ ≤ ln µ+1
µ
ρ
−1
µ
1
ˆ max = n exp − nµ − µ according to (18).
2) When µ < n−1
, we have λ
µ+1
ρ
o
n
nµ
i) if : if ρ > ln n−µ nµ , we have n exp − µ+1
− µρ > 1.
µ+1
o
n
nµ
ii) only if : if ρ ≤ ln n−µ nµ , we have n exp − µ+1
− µρ ≤ 1.
OF
µ+1
A PPENDIX D
P ROOF
OF
T HEOREM 3
Proof: According to (23-24), we can rewrite the maximum sum rate as C = max (C1 , C2 ), where
µ+1
µ
· log2 (1 + µ),
exp −1 −
C1 = max
1
µ
ρ
µ≥ n−1
(68)
34
and
µ
nµ
C2 = max1 n exp −
· log2 (1 + µ).
−
µ+1 ρ
0<µ≤ n−1
(69)
Let us first focus on C1 .
1) Denote the objective function of (68) as f1 (µ) and let us first prove the following lemma.
Lemma 4. f1 (µ) is a monotonic decreasing function of µ ∈
global maximum at µ∗h , where µ∗h is the root of (27).
1
,∞
n−1
Proof: f1 (µ) is a continuously differentiable function of µ ∈
f (µ) can be written as
f1′ (µ)
if ρ < ρ0 . Otherwise, it has one
1
,∞
n−1
. The first-order derivative of
µ
log2 e · G1 (µ),
= exp −1 −
ρ
(70)
where
G1 (µ) =
1
1
1 1+µ
− 2 ln(1 + µ) − ·
ln(1 + µ).
µ µ
ρ
µ
(71)
It can be easily obtained from (71) that
lim1 G1 (µ) = (n − 1) − (n − 1)2 ln
µ→ n−1
n
n
n
− ln
,
n−1 ρ n−1
(72)
and
lim G1 (µ) = −∞.
µ→∞
(73)
Moreover, the first-order derivative of G1 (µ) can be obtained from (71) as
G′1 (µ)
for µ ∈
1
,∞
n−1
1
=− 2
µ
2+µ 2
1 1 ln(1 + µ)
− ln(1 + µ) −
−
< 0,
1+µ µ
ρ µ
µ2
(74)
1
, which indicates that G1 (µ) is a monotonic decreasing function of µ ∈ n−1
,∞ .
i) If ρ ≥ ρ0 , we can obtain from (72-73) that limµ→ 1 G1 (µ) ≥ 0 and limµ→∞ G1 (µ) < 0. As G1 (µ) is
n−1
1
1
, ∞ , such that G1 (µ) > 0
a monotonic decreasing function of µ ∈ n−1 , ∞ , there must exist µ∗h ∈ n−1
1
for µ ∈ n−1
, µ∗h and G1 (µ) < 0 for µ ∈ (µ∗h , ∞), where µ∗h is the root of G1 (µ) = 0, which is given
1
in (27). We can then obtain from (70) that f1′ (µ) > 0 for µ ∈ n−1
, µ∗h and f1′ (µ) < 0 for µ ∈ (µ∗h , ∞),
which indicates that f1 (µ) has one global maximum at µ∗h .
ii) If ρ < ρ0 , we can obtain from (72) that limµ→ 1 G1 (µ) < 0. As G1 (µ) is a monotonic decreasing
n−1
1
1
, ∞ . According to (70), we can conclude
function of µ ∈ n−1 , ∞ , we have G1 (µ) < 0 for µ ∈ n−1
35
that in this case f1 (µ) is a monotonic decreasing function as f1′ (µ) < 0 for µ ∈
1
,∞
n−1
According to Lemma 4, we can conclude that the optimal SINR threshold for C1 is
µ∗1 =


µ∗h


.
if ρ ≥ ρ0
1
n−1
(75)
otherwise.
2) For C2 , denote the objective function of (69) as f2 (µ) and let us first prove the following lemma.
1
Lemma 5. f2 (µ) is a monotonic non-decreasing function of µ ∈ 0, n−1
if ρ ≥ ρ0 . Otherwise, it has one
global maximum at µ∗l , where µ∗l is the root of (28).
1
. The first-order derivative of
Proof: f2 (µ) is a continuously differentiable function of µ ∈ 0, n−1
f2 (µ) can be written as
f2′ (µ)
n
nµ
µ
=
log2 e · G2 (µ),
exp −
−
(1 + µ)2
µ+1 ρ
(76)
where
G2 (µ) = (1 + µ) −
(1 + µ)2
+ n ln(1 + µ).
ρ
(77)
It can be easily obtained from (77) that
lim G2 (µ) = 1,
(78)
µ→0
and
n
n
1
lim1 G2 (µ) =
− n ln
− ·
n−1
n−1 ρ
µ→ n−1
n
n−1
2
ln
n
.
n−1
(79)
Moreover, the first-order derivative of G2 (µ) can be obtained from (77) as
G′2 (µ) = 1 −
1+µ
n
−
(1 + 2 ln(1 + µ)) < 0
1+µ
ρ
(80)
1
1
, which indicates that G2 (µ) is a monotonic decreasing function of µ ∈ 0, n−1
.
for µ ∈ 0, n−1
i) If ρ ≥ ρ0 , we can obtain from (79) that limµ→
G2 (µ) ≥ 0. As G2 (µ) is a monotonic decreasing
1
1
function of µ ∈ (0, n−1
], we have G2 (µ) ≥ 0 for µ ∈ 0, n−1
. According to (76), we can conclude that
1
.
in this case f2 (µ) is a monotonic non-decreasing function as f2′ (µ) ≥ 0 for µ ∈ 0, n−1
1
n−1
ii) If ρ < ρ0 , we can obtain from (78-79) that limµ→0 G2 (µ) > 0 and limµ→ 1 G2 (µ) < 0. As G2 (µ) is a
n−1
1
1
∗
, such that G2 (µ) > 0 for
monotonic decreasing function of µ ∈ 0, n−1 , there must exist µl ∈ 0, n−1
36
1
µ ∈ (0, µ∗l ) and G2 (µ) < 0 for µ ∈ µ∗l , n−1
, where µ∗l is the root of G2 (µ) = 0, which is given in (28).
1
We can then obtain from (76) that f2′ (µ) > 0 for µ ∈ (0, µ∗l ) and f2′ (µ) < 0 for µ ∈ µ∗l , n−1
, which
indicates that f2 (µ) has one global maximum at µ∗l .
According to Lemma 5, we can conclude that the optimal SINR threshold for C2 is
µ∗2
=



1
n−1

µ∗
l
if ρ ≥ ρ0
(81)
otherwise.
1
. As
3) By combining (75) and (81), we can see that if ρ ≥ ρ0 , C1 = f1 (µ∗h ) and C2 = f2 n−1
1
1
1
f2 n−1
= f1 n−1
and f1 n−1
≤ C1 , we have C1 ≥ C2 . Therefore, we can conclude that in this case
the maximum sum rate C = C1 and the optimal SINR threshold µ∗ = µ∗h .
1
1
and C2 = f2 (µ∗l ). As f1 n−1
= f2
On the other hand, if ρ < ρ0 , C1 = f1 n−1
1
n−1
and f2
1
n−1
≤
f2 (µ∗l ), we have C2 ≥ C1 . Therefore, we can conclude that in this case the maximum sum rate C = C2
and the optimal SINR threshold µ∗ = µ∗l .
A PPENDIX E
P ROOF
OF
C OROLLARY 2
Proof: We can easily obtain from (27) that limρ→∞ µ∗h = ∞ and
1
µ∗h
1 + µ∗h
∗
ln(1 + µ∗h ) = 1.
lim
ln µh = lim
+
ρ→∞ ρ
ρ→∞ µ∗
ρ
h
(82)
By combining (26), we have
lim µ∗ = lim µ∗h = ∞,
(83)
µ∗
µ∗
1
= lim h = lim
= 0.
ρ→∞ ρ
ρ→∞ ρ
ρ→∞ ln µ∗
h
(84)
ρ→∞
ρ→∞
lim
Moreover, by applying L’Hˆopital’s rule on the left-hand side of (82), we have limρ→∞
dµ∗h
(1 + ln µ∗h )
dρ
= 1,
which indicates that
dµ∗
(1 + ln µ∗ ) = 1.
ρ→∞ dρ
lim
(85)
Therefore, by combining (25) with (83-85), we can obtain that
log2 µ∗
ρ
C
= e−1 · lim
= e−1 · lim ∗
= e−1 .
ρ→∞ log2 ρ
ρ→∞ µ (1 + ln µ∗ )
ρ→∞ log2 ρ
lim
(86)
37
A PPENDIX F
P ROOF
OF
C OROLLARY 3
Proof: When ρ < ρ0 , the optimal SINR threshold µ∗ = µ∗l according to (26). We can easily obtain
from (28) that
lim µ∗l = 0.
(87)
n→∞
By combining (28) and (87), we can further obtain that
lim n log2 (1 + µ∗l ) = lim
n→∞
n→∞
log2 e
= log2 e,
1
µ∗l + 1
+
µ∗l + 1
nρ
(88)
and
µ∗l (µ∗l + 1)
nµ∗l
µ∗l
=
lim
−
= 1.
n→∞ µ∗ + 1
n→∞ ln(1 + µ∗ )
ρ
l
l
lim
(89)
Therefore, by combining (25) with (87-89), we can obtain that
lim Cρ<ρ0
n→∞
µ∗
nµ∗
= lim n exp − ∗ l − l
n→∞
µl + 1
ρ
log2 (1 + µ∗l ) = e−1 log2 e.
(90)
A PPENDIX G
D ERIVATION
OF
(39-40)
Based on the collision model, a packet transmission is successful if and only if there are no concurrent
transmissions and its received SNR is above the threshold µ. The steady-state probability of successful
transmission of HOL packets, p, can be then written as
p = Pr{no concurrent transmissions} · Pr{received SNR is above the threshold µ}.
(91)
It has been shown in Section III-B that in saturated conditions, the probability of a node being busy with
the HOL packet requesting transmission is equal to π0 /p. The probability that there are no concurrent
transmissions can be then obtained as
Pr{no concurrent transmissions} = (1 − π0 /p)n−1 .
(92)
38
Since the received SNR is exponentially distributed with mean ρ, the probability that the received SNR
is above the threshold µ is given by
µ
Pr{received SNR is above the threshold µ} = exp −
.
ρ
(93)
By substituting (92) and (93) into (91), we have
p = (1 − π0 /p)
n−1
µ for large n
µ nπ0
· exp −
≈ exp − −
,
ρ
ρ
p
(94)
which can be further written as


according to (7).

 µ
n


,
p = exp − −
K 
i
 ρ PK−1 p (1 − p)
(1 − p) 
+
i=0
qi
qK
(95)
By following a similar derivation in Appendix A, it can be proved that (95) has a single non-zero
root if {qi }i=0,...,K is a monotonic non-increasing sequence. Denote the non-zero root of (95) as pcA . The
ˆ collision = −pc ln pc −
network throughput can be then obtained as λ
out
A
A
pcA µ
ρ
by combining (9) and (94).
ˆ collision with respect to pc is − 1c < 0 for pc ∈ (0, ∞), λ
ˆ collision is
As the second-order derivative of λ
out
out
A
A
p
A
pcA
a strictly concave function of
∈ (0, ∞) with one global maximum at pc∗
A . It can be easily obtained
µ
µ
c∗
collision
ˆ
c
= exp −1 − ρ , which is achieved at pA = exp −1 − ρ , and is achievable for
that maxpA λout
µ ∈ (0, ∞). Therefore, we have
µ
collision
ˆ
λmax
= exp −1 −
.
ρ
(96)
With the information encoding rate R = log2 (1 + µ), the maximum sum rate can be written as
C
collision
µ
= max exp −1 −
µ>0
ρ
· log2 (1 + µ).
(97)
Let f (µ) denote the objective function of (97). It can be easily shown that f ′ (µ) ≥ 0 for µ ∈ (0, µ∗,collision]
and f ′ (µ) < 0 for µ ∈ (µ∗,collision , ∞), indicating that f (µ) has one global maximum at µ∗,collision , where
µ∗,collision is the root of (µ + 1)(µ+1)/ρ = e, which is given by
µ∗,collision = eW0 (ρ) − 1.
(39) and (40) can be then obtained by substituting (98) into (97) and (96), respectively.
(98)
39
A PPENDIX H
D ERIVATION
j
OF
(43-45)
According to (42), the network steady-state point in saturated conditions pA crucially depends on
k
1
1
−
. Let us specifically consider the following cases:
µ
ρ
1)
j
1
µ
−
1
ρ
k
< 0: It can be seen from (42) that pA = 0. In this case, no packet can pass through due to
an excessively high SINR threshold. Both the network throughput and the sum rate are 0.
j
k
1
1
2) µ − ρ ≥ n−1: It can be seen from (42) that pA = 1. In this case, all the packets can be successfully
ˆ out = nq0 by combining (7) and (9). To maximize the
decoded, and the network throughput is λ
network throughput, all the nodes should transmit with probability q0 = 1, and the maximum network
1
µ≤
1
ˆ maxn−1+ ρ = n. The corresponding sum rate is then n log2 (1 + µ), which is a monotonic
throughput is λ
1
increasing function of the SINR threshold µ, and is maximized when µ = n−1+
1 .
ρ
k
j
3) 0 ≤ µ1 − 1ρ < n − 1: It can be obtained from (42) and (7) that in this case, pA with K = 0 can be
written as
pA = I1−q0
1 1
1 1
n−1−
,
+1 .
−
−
µ ρ
µ ρ
(99)
The network throughput can be then obtained by combining (7), (9) and (99) as
1 1
1 1
ˆ
,
+1 ,
λout = nq0 I1−q0 n − 1 −
−
−
µ ρ
µ ρ
(100)
which has one global maximum at q0∗ , where q0∗ is the root of the following equation:
1−q0
Z
0
1
1
1
1
1
1
⌊ 1 − 1 ⌋+1
tn−2−⌊ µ − ρ ⌋ (1 − t)⌊ µ − ρ ⌋ dt = (1 − q0 )n−2−⌊ µ − ρ ⌋ q0 µ ρ .
(101)
The corresponding sum rate is then given by
1 1
1 1
Rs =
n−1−
,
+ 1 log2 (1 + µ).
(102)
−
−
µ ρ
µ ρ
j
k
Note that when 1+1 1 < µ ≤ ρ, µ1 − 1ρ = 0. In this case, the optimal transmission probability can be
nq0∗ I1−q0∗
ρ
obtained from (101) as q0∗ = n1 , and the maximum network throughput can be obtained from (100)
1
1
1+ ρ
ˆ max
as λ
<µ≤ρ
= (1 − n1 )n−1 ≈ e−1 for large number of nodes n. The corresponding sum rate is then
e−1 log2 (1 + µ), which is a monotonic increasing function of the SINR threshold µ, and is maximized
when µ = ρ.
40
Fig. 12 illustrates how the sum rate varies with the SINR threshold µ. It can be clearly observed from
Fig. 12 that there are two local maximum points at µ =
1
n−1+ ρ1
and µ = ρ, respectively. Which one
is the global maximum point is determined by the mean received SNR ρ. Let ρ1 denote the root of
1
(46). If ρ < ρ1 , we have n log2 1 + n−1+ 1 > e−1 log2 (1 + ρ). In this case, the maximum sum rate is
ρ
1
1
, which is achieved when the SINR threshold µ = n−1+
C = n log2 1 + n−1+
1
1 . Otherwise, µ = ρ is
ρ
ρ
the global maximum point, and the maximum sum rate is given by C = e−1 log2 (1 + ρ). It can be clearly
seen from Fig. 12 that for ρ = 5dB < ρ1 ≈ 11.5dB, µ =
1
n−1+ ρ1
is the optimal SINR threshold. When ρ
increases to 15dB, the maximum sum rate is achieved at µ = ρ.
Rs (bit/s/Hz)
Rs (bit/s/Hz)
1.5
2
CUAWGN
5 dB=1.45
=1.85
CUAWGN
15 dB
1.5
1
1
0.5
0 -4
10
-3
denotes
P
denotes
P
-2
10
10 0.02
0.5
1
n 1 U1
U
-1
0
10
10
3.2
1
10
0 -4
10
ȝ
-3
-2
10
10 0.02
(a)
Fig. 12.
denotes
P
denotes
P
-1
10
1
n 1 U1
U
0
10
1
10
2
31.6 10
ȝ
(b)
Sum rate of Aloha over AWGN channels versus SINR threshold. n = 50. K = 0 and q0 = q0∗ . (a) ρ = 5dB. (b) ρ = 15dB.
A PPENDIX I
D ERIVATION
Let Z =
PM
m=1
P
k∈Sjm
|hk |2 ·
ρm
ρj
OF
(48)
− |hj |2 /µ. According to (47), we have
j
r{i
= Pr {Z ≤ −1/ρj } .
m}
(103)
With hk ∼ CN (0, 1), the Laplace transform of Z can be written as
LZ (s) =

 im
M
Y
1
µ


·


µ − s m=1 1 + ρm s
ρj
.
(104)
41
By applying the partial fraction expansion and the inverse Laplace transform for s ≤ 0, we have
fZ (z) = µ exp(µz) ·
M
Y
m=1



im
1

ρm 
µ
1+
ρj
.
(105)
Finally, by combining (105) with (103), we have
j
r{i
=
m}
Z
−1/ρj
−∞
exp − ρµj
fZ (z)dz = Q
im .
M
ρm
µ
1
+
m=1
ρj
(106)
R EFERENCES
[1] N. Abramson, “The Aloha system: another alternative for computer communications,” in Proc. Fall joint Compet. Conf., vol. 44, pp.
281–285, Nov. 1970.
[2] J. F. Kurose and K. W. Ross, Computer Networking: A Top-Down Approach (5th Edition), Addison Wesley, 2009.
[3] N. Abramson, “Packet switching with satellites,” in Proc. Nat. joint Comput. Conf., vol. 42, pp. 695–702, Montvale, 1973.
[4] L. Kleinrock and F. Tobagi, “Packet switching in radio channels: Part I–carrier sense multiple-access modes and their throughput-delay
characteristics,” IEEE Trans. Commun., vol. 23, no. 12, pp. 1400–1416, 1975.
[5] A. Carleial and M. Hellman, “Bistable behavior of Aloha-type systems,” IEEE Trans. Commun., vol. 23, no. 4, pp. 401–410, Apr. 1975.
[6] S. Lam and L. Kleinrock, “Packet switching in a multiaccess broadcast channel: Dynamic control procedures,” IEEE Trans. Commun.,
vol. 23, no. 9, pp. 891–904, Sept. 1975.
[7] M. J. Feguson, “On the control, stability, and waiting time in a slotted ALOHA random-access system,” IEEE Trans. Commun., vol. 23,
no. 11, pp. 1306–1311, Nov. 1975.
[8] G. Fayolle, E. Gelenbe, and J. Labetoulle, “Stability and optimal control of the packet switching broadcast channel,” J. Assoc. Comput.
Machinery, vol. 24, no. 3, pp. 375–386, Jul. 1977.
[9] B. Tsybakov and W. Mikhailov, “Ergodicity of slotted Aloha systems,” Probl. Inform. Transmission, vol. 15, no. 4, pp. 301–312, 1979.
[10] V. A. Mikhailov, Method of Random Multiple Access, Candidate Engineering Thesis, Moscow Institute of Phy. and Tech., 1979.
[11] B. Hajek and T. Van Loon, “Decentralized dynamic control of a multiaccess broadcast channel,” IEEE Trans. Automat. Contr., vol. 27,
no. 3, pp. 559–569, Jun. 1982.
[12] R. Rivest, “Network control by Bayesian broadcast,” IEEE Trans. Inf. Theory, vol. 33, no. 3, pp. 323–328, May 1987.
[13] R. Rao and A. Ephremides, “On the stability of interacting queues in a multiple-access system,” IEEE Trans. Inf. Theory, vol. 34,
no. 5, pp. 918–930, Sep. 1988.
[14] V. Anantharam, “The stability region of the finite-user slotted Aloha protocol,” IEEE Trans. Inf. Theory, vol. 37, no. 3, pp. 535–540,
May 1991.
[15] W. Szpankowski, “Stability conditions for some distributed systems: Buffered random access systems,” Adv. Appl. Probab., vol. 26,
pp. 498–515, 1993.
[16] W. Luo and A. Ephremides, “Stability of n interacting queues in random-access systems,” IEEE Trans. Inf. Theory, vol. 45, no. 5, pp.
1579–1587, Jul. 1999.
[17] T. Wan and A. Sheikh, “Performance and stability analysis of buffered slotted Aloha protocols using tagged user approach,” IEEE
Trans. Veh. Technol., vol. 49, no. 2, pp. 582–593, Mar. 2000.
42
[18] G. Bianchi, “Performance analysis of the IEEE 802.11 distributed coordination function,” IEEE J. Sel. Areas Commun., vol. 18, no. 3,
pp. 535–547, Mar. 2000.
[19] X. Qin and R. Berry, “Distributed approaches for exploiting multiuser diversity in wireless networks,” IEEE Trans. Inf. Theory, vol. 52,
no. 2, pp. 392–413, Feb. 2006.
[20] L. Dai, “Stability and delay analysis of buffered Aloha networks,” IEEE Trans. Wireless Commun., vol. 11, no. 8, pp. 2707–2719, Aug.
2012.
[21] L. Dai, “Toward a coherent theory of CSMA and Aloha,” IEEE Trans. Wireless Commun., vol. 12, no. 7, pp. 3428–3444, Jul. 2013.
[22] L. G. Roberts, “Aloha packet system with and without slots and capture,” ARPANET Satellite System Note 8, NIC Document No. 11290,
Stanford Research Institute, 1972.
[23] C. Namislo, “Analysis of mobile radio slotted Aloha networks,” IEEE J. Sel. Areas Commun., vol. 2, no. 4, pp. 583–588, Jul. 1984.
[24] J. Arnbak and W. van Blitterswijk, “Capacity of slotted Aloha in Rayleigh-fading channels,” IEEE J. Sel. Areas Commun., vol. 5, pp.
261–269, Feb. 1987.
[25] D. Goodman and A. Saleh, “The near/far effect in local Aloha radio communications,” IEEE Trans. Veh. Technol., vol. 36, no. 1, pp.
19–27, Feb. 1987.
[26] I. Habbab, M. Kavehrad, and C. E. Sundberg, “Aloha with capture over slow and fast fading radio channels with coding and diversity,”
IEEE J. Sel. Areas Commun., vol. 7, no. 1, pp. 79–88, Jan. 1989.
[27] A. Sheikh, Y. D. Yao, and X. Wu, “The Aloha systems in shadowed mobile radio channels with slow or fast fading,” IEEE Trans. Veh.
Technol., vol. 39, no. 4, pp. 289–298, Nov. 1990.
[28] C. V. der Plas and J. P. M. G. Linnartz, “Stability of mobile slotted Aloha network with Rayleigh fading, shadowing, and near-far
effect,” IEEE Trans. Veh. Technol., vol. 39, no. 4, pp. 359–366, Nov. 1990.
[29] M. Peh, S. Hanly, and P. Whiting, “Random-access over fading channels,” in Proc. IEEE Globecom, San Francisco, CA, pp. 888–892,
Dec. 2003.
[30] M. Zorzi and R. Rao, “Capture and retransmission control in mobile radio,” IEEE J. Sel. Areas Commun., vol. 12, no. 8, pp. 1289–1298,
Oct. 1994.
[31] G. del Angel and T. Fine, “Information capacity and power control for slotted Aloha random-access systems,” IEEE Trans. Inf. Theory,
vol. 51, no. 12, pp. 4074–4090, 2005.
[32] J. Luo and A. Ephremides, “Power levels and packet lengths in random multiple access with multiple-packet reception capability,”
IEEE Trans. Inf. Theory, vol. 52, pp. 414–420, Feb. 2006.
[33] S. Rasool and A. U. H. Sheikh, “An approximate analysis of buffered S-Aloha in fading channels using tagged user analysis,” IEEE
Trans. Wireless Commun., vol. 6, no. 4, pp. 1320–1326, 2007.
[34] J. Wieselthier, G. D. Nguyen, and A. Ephremides, “Throughput (bits/sec/hz) of capture-based random-access systems with SINR channel
models,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2007, pp. 2401–2405.
[35] V. Naware and L. Tong, “Cross layer design for multiaccess communication over Rayleigh fading channels,” IEEE Trans. Wireless
Commun., vol. 7, no. 3, pp. 1095–1103, 2008.
[36] A. Dua, “Random access with multi-packet reception,” IEEE Trans. Wireless Commun., vol. 7, no. 6, pp. 2280–2288, Jun. 2008.
[37] T. Shinomiya and H. Suzuki, “Slotted Aloha mobile packet communication systems with multiuser detection in a base station,” IEEE
Trans. Veh. Technol., vol. 49, no. 3, pp. 948–955, 2000.
[38] M. Medard, J. Huang, A. Goldsmith, S. Meyn, and T. Coleman, “Capacity of time-slotted Aloha packetized multiple-access systems
over the AWGN channel,” IEEE Trans. Wireless Commun., vol. 3, no. 2, pp. 486–499, 2004.
43
[39] S. Adireddy and L. Tong, “Exploiting decentralized channel state information for random access,” IEEE Trans. Inf. Theory, vol. 51,
no. 2, pp. 537–561, Feb. 2005.
[40] V. Naware, G. Mergen, and L. Tong, “Stability and delay of finite-user slotted Aloha with multipacket reception,” IEEE Trans. Inf.
Theory, vol. 51, no. 7, pp. 2636–2656, Jul. 2005.
[41] R. Yim, N. Mehta, A. Molisch, and J. Zhang, “Dual power multiple access with multipacket reception using local CSI,” IEEE Trans.
Wireless Commun., vol. 8, no. 8, pp. 4078–4088, 2009.
[42] P. Minero, M. Franceschetti, and D. Tse, “Random access: An information-theoretic perspective,” IEEE Trans. Inf. Theory, vol. 58,
no. 2, pp. 909–930, 2012.
[43] A. Zanella and M. Zorzi, “Theoretical analysis of the capture probability in wireless systems with multiple packet reception capabilities,”
IEEE Trans. Commun., vol. 60, no. 4, pp. 1058–1071, 2012.
[44] S. Ghez, S. Verdu, and S. Schwartz, “Stability properties of slotted Aloha with multipacket reception capability,” IEEE Trans. Autom.
Control, vol. 33, no. 7, pp. 640–649, 1988.
[45] S. Ghez, S. Verdu, and S. Schwartz, “Optimal decentralized control in the random access multipacket channel,” IEEE Trans. Autom.
Control, vol. 34, no. 11, pp. 1153–1163, 1989.
[46] J. Y. Hui, Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Publishers, 1990.
[47] B. Rimoldi and R. Urbanke, “A rate-splitting approach to the Gaussian multiple-access channel,” IEEE Trans. Inf. Theory, vol. 42, no.
2, pp. 364–375, Mar. 1996.
[48] M. Iosifescu, Finite Markov Processes and Their Applications. Dover Publications, 2007.
[49] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, “On the Lambert W function,” Adv. Comput. Math., vol.
5, pp. 329–359, 1996.
[50] D. Tse and P. Viswanath, Fundamentals of Wireless Communication, Cambridge University Press, 2005.
[51] M. Shaked and J. G. Shanthikumar, Stochastic Orders, Springer Series in Statistics, 2007.
1/--pages
Пожаловаться на содержимое документа