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