1 Maximum Sum Rate of Slotted Aloha with Capture Yitong Li and Lin Dai, Senior Member, IEEE Abstract—The sum rate performance of random-access net- collision occurs and none of them can be successfully works crucially depends on the access protocol and receiver decoded.Apackettransmissionissuccessfulonlyifthere structure. Despite extensive studies, how to characterize the arenoconcurrenttransmissions.Thecollisionmodelwas maximum sum rate of the simplest version of random access, first proposed by Abramson in [1], and has been widely Aloha,remainsanopenquestion.Inthispaper,acomprehensive study of the sum rate performance of slotted Aloha networks used since then [3]–[21]. 5 is presented. By extending the unified analytical framework 2) Capture model: Though an elegant and useful simpli- 1 proposed in [20], [21] from the classical collision model to the fication of the receiver, the collision model could be 0 capture model, the network steady-state point in saturated con- overly pessimistic if there exists a large difference of 2 ditionsisderivedasafunctionofthesignal-to-interference-plus- received power. It was first pointed out by Roberts in c noise ratio (SINR) threshold which determines a fundamental e tradeoffbetweentheinformationencodingrateandthenetwork [22]thatevenwithmultipleconcurrenttransmissions,the D throughput.Tomaximize thesumrate, boththeSINRthreshold strongestsignalcouldbesuccessfullydetectedaslongas and backoff parameters of nodes should be properly selected. the signal-to-interference ratio (SIR) is high enough. It 7 Explicit expressions of the maximum sum rate and the optimal was referred to as the “capture effect”, which has been 1 settingareobtained,whichshowthatsimilartothesumcapacity extensivelystudiedin[23]–[36].With thecapturemodel, of themultipleaccess channel,themaximumsumrateofslotted ] Aloha also logarithmically increases with the mean received each node’s packet is decoded independently by treating T signal-to-noise ratio (SNR), but the high-SNR slope is only e−1. others’asbackgroundnoise.Apacketcanbesuccessfully I Effectsofbackoffandpowercontrolonthesumrateperformance decoded as long as its received signal-to-interference- . s of slotted Aloha networks are further discussed, which shed plus-noise ratio (SINR) is abovea certain threshold.It is c important light on the practical network design. [ clear that multiple packets may be successfully decoded Index Terms—Random access, slotted Aloha, sum rate, net- if the SINR threshold is sufficiently low. 3 work throughput, backoff, capture model 3) Joint-decoding model: Both the collision model and the v 0 capture model are essentially single-user detectors. Mul- 8 I. INTRODUCTION tiuser detectors, such as Minimum Mean Square Error 3 Random access provides a simple and elegant solution for (MMSE) and Successive Interference Cancelation (SIC), 3 multipleuserstoshareacommonchannel.Studiesonrandom- have been also applied to random-access networks [37]– 0 . access protocols date back to 1970s [1]. After decades of [43]. By jointly decoding multiple nodes’ packets, the 1 extensiveresearch,randomaccesshasfoundwideapplications efficiency can be greatly improved,though at the cost of 0 5 to Ethernet, IEEE 802.11 networks, Long-Term Evolution increased receiver complexity. 1 (LTE) cellular systems and wireless ad-hoc networks[2]. The Note that the capture model and the joint-decoding model : minimum coordination and distributed control make it highly both have the so-called “multipacket-reception (MPR)” ca- v i appealing for low-cost data networks. pability [44], [45], and have been referred to as the MPR X In sharp contrast to the simplicity in concept, the perfor- model in many references [30], [32], [37], [39]–[41], [43]. r mance analysis of random-access networks1 has been known Here we distinguishthem apartbecause theyassume different a as notoriously difficult, which is mainly due to the lack of a receiver structures. In this paper, we specifically focus on the coherent analytical framework. Numerous models have been performance analysis based on the capture model. proposed based on distinct assumptions. According to the receiver structure, they can be broadly divided into three A. Maximum Network Throughput of Slotted Aloha categories: Inrandom-accessnetworks,duetotheuncoordinatednature 1) Collision model: In the classical collision model, when oftransmitters,thenumberofsuccessfullydecodedpacketsin multiple nodes transmit their packets simultaneously, a each time slot varies from time to time. In the literature, the Manuscript received April 25, 2015; revised September 28, 2015 and averagenumberof successfully decodedpackets per time slot November 29, 2015; accepted December 5, 2015. The associate editor is usually adoptedas an importantperformancemetric, which coordinating the review of this paper and approving it for publication was is referred to as the network throughput. P.Popovski. ThisworkwassupportedbytheResearchGrantsCouncil(RGC)ofHong The network throughput performance depends on a series KongunderGRFGrantCityU112810andtheCityUStrategicResearchGrant of key factors including the receiver model and protocol 7004232. design. With the classical collision model, for instance, at The authors are with the Department of Electronic Engineering, City UniversityofHongKong,83TatCheeAvenue,KowloonTong,HongKong, mostonepacketcanbesuccessfullydecodedateachtimeslot. China(email:[email protected], [email protected]). Therefore, the network throughput, which is also the fraction 1Unless otherwise specified, throughout the paper we only consider syn- oftimethataneffectiveoutputisproducedinthiscase,cannot chronizedslottednetworkswherethetimeisdividedintomultipleslots,and nodestransmitatthebeginning ofeachtimeslot. exceed1. The maximumnetworkthroughputof slotted Aloha 2 wasshowntobeonlye−1 withthecollisionmodel[3],which categories:channel-centric[3]–[8],[10]–[12]andnode-centric indicatesthatover60%ofthetimeiswastedwhenthenetwork [9], [13]–[18]. By focusing on the state transition process of is either in collision or idle states. To improve the efficiency, the aggregate traffic, the channel-centric approaches capture CarrierSenseMultipleAccess(CSMA)wasfurtherintroduced the essence of contention among nodes, which, nevertheless, in [4], with which the network throughput can approach 1 ignore the behavior of each node’s queue and thus shed little by reducing the sensing time. On the other hand, significant light on the effect of backoff parameters on the performance improvement in network throughput was also observed when of each single node.With the node-centricapproaches,onthe the capture model is adopted [23]–[32]. Intuitively, with the other hand, the modeling complexity becomes prohibitively capture model, more packets can be successfully decoded by highifinteractionsamongnodes’queuesarefurthertakeninto reducing the SINR threshold. The network throughputis thus consideration. To simplify the analysis, a key approximation, greatly improved, and may exceed 1 if the SINR threshold is which has been widely adopted and shown to be accurate sufficiently small. forperformanceevaluationoflargemulti-queuesystems[46], Despite extensive studies, how to maximize the network is to treat each node’s queue as an independent queueing throughput has been an open question for a long time. In system with identically distributed service time. The service Abramson’s landmark paper [3], by modeling the aggregate time distribution is still crucially determinedby the aggregate trafficasaPoissonrandomvariablewithparameterG,thenet- activitiesofhead-of-line(HOL)packetsofallthenodes,which workthroughputofslottedAlohawiththecollisionmodelcan requires proper modeling of HOL packets’ behavior. beeasilyobtainedasGe−G,whichismaximizedate−1 when Inourrecentwork[20],[21],aunifiedanalyticalframework G=1.Toenablethenetworktooperateattheoptimumpoint for two representative random-access protocols, Aloha and formaximumnetworkthroughput,nevertheless,itrequiresthe CSMA,wasestablished,wherethenetworksteady-statepoints connection between the mean traffic rate G and key system were characterized based on the fixed-point equations of the parameterssuch as transmission probabilitiesof nodes, which limitingprobabilityofsuccessfultransmissionofHOLpackets turns out to be a challenging issue. Various retransmission byassumingtheclassicalcollisionmodel.Aswewillshowin strategies were developed to adjust the transmission proba- this paper, the proposed analytical framework can be further bility of each node according to the number of backlogged extended to incorporate the capture model, based on which nodestostabilize2 thenetwork[5]–[8].Yetmostofthemwere explicit expressions of the maximum network throughputand based on the realtime feedback information on the backlog the correspondingoptimal transmission probabilities of nodes size, which may not be available in a distributed network. will be derived. Decentralizedretransmissioncontrolwasfurtherstudiedin[6], [10]–[12], where algorithms were proposed to either estimate B. Maximum Sum Rate of Slotted Aloha and feed back the backlog size [10], [12], or update the transmission probability of each node recursively according From the information-theoretic perspective, random access to the channel output [6], [11]. can be regarded as a multiple access channel (MAC) with The above analytical approaches were also applied to the a random number of active transmitters. It is well known capture model. By assuming Poisson distributed aggregate that the sum capacity of an n-user Additive-White-Gaussian- traffic, for instance, the network throughput was derived as Noise (AWGN) MAC is determined by the received SNRs, a function of the mean traffic rate G and the SIR threshold in i.e., Csum = log2(1 + ni=1SNRi). With random access, [24], [25], [27] under distinct assumptions on channel condi- however,thenumberofactivetransmittersisarandomvariable P tions. Similar to the case of collision model, the maximum whosedistributionisdeterminedbytheprotocolandparameter network throughput can be obtained by optimizing G, yet setting. Moreover,to achieve the sum capacity, a joint decod- how to properly tune the system parameters to achieve the ing of all transmitted codewords should be performed at the maximumnetworkthroughputremainsunknown.Retransmis- receiverside, which mightbe unaffordablefor random-access sion control strategies developed in [5], [10] and [11] were networks. Therefore, the sum rate performance of random further extended to the capture model in [33], [28] and [29], access becomes closely dependent on assumptions on the respectively. To evaluate the network throughputperformance access protocol and receiver design. for given transmission probabilities of nodes, variousMarkov There has been a great deal of effort to explore the chainswere also established in [23], [26], [31], [32] to model information-theoretic limit of random-access networks. For the state transition of each individualuser. The computational instance,the conceptofratesplitting[47] wasfirstintroduced complexity,nevertheless,sharplyincreaseswhensophisticated toslottedAlohanetworksin[38],whereajointcodingscheme backoff strategies are further involved, which renders it ex- was developed for the two-node case. If each node indepen- tremely difficult, if not impossible, to search for the optimal dentlyencodesitsinformation,[42]showedthatthesumrate3 configuration to maximize the network throughput. performance of slotted Aloha networks can be improved by The difficulty originates from the modeling of random- adaptivelyadjustingtheencodingrateaccordingtothenumber access networks. As demonstrated in [21], the modeling ap- of nodes and the transmission probability of each node. [38] proaches in the literature can be roughly divided into two and [42] are based on the assumption of joint decoding of 2Note that various definitions of stability have been developed in the 3Note that different terminologies were usedin these studies. In[34],for literature. A widely adopted one is that a network is stable if the network instance, “average spectral efficiency” was used to denote the sum rate of throughput isequaltotheaggregate inputrate. slottedAloha.In[19],[35],[36],[42],itwasreferredtoas“throughput”. 3 TABLEI MAINNOTATIONS n Number of nodes ρ Mean received SNR µ SINR threshold R Information encoding rate of nodes ˆ λ Network throughput out p Steady-state probability of successful transmission of HOL packets K Cutoff phase of HOL packets {qi}i=0,...,K Transmission probabilities of nodes ˆ λmax Maximum network throughput C Maximum sum rate multiple nodes’ packets at the receiver side. With the capture oldandthe transmissionprobabilitiesofnodesshouldbe model, the effects of power allocation and modulation on the carefully selected according to the mean received SNR sum rate of slotted Aloha in AWGN channels were analyzed ρ. Explicit expressions of the optimal SINR threshold in [34] and [35], respectively. Queueing stability and channel and transmission probabilities are derived, and verified fading were further considered in [36], where the sum rates by simulations. with various cross-layer approacheswere derived. In [19], by NotethattheMACscenarioconsideredinthispapershould assumingthateachnodehasitsownchannelstateinformation be distinguished from the ad-hoc scenario which has been (CSI) and the collision model is adopted at the receiver side, extensivelystudiedinrecentyears[48]–[54].Incontrasttothe the scaling behavior of the sum rate of slotted Aloha as the MAC where multiple nodes transmit to a common receiver, number of nodes n goes to infinity was characterized, and multiple transmitter-receiver pairs exist in the ad-hoc case. shown to be identical to that of the sum capacity of MAC. Representative applications of the former one include cellular Although various analytical models were developed in the systems and IEEE 802.11 networks, where in each cell/basic- above studies, many of them rely on numerical methods to service-set, multiple users transmit to the base-station/access- calculatethesumrateunderspecificsettings.Itremainslargely point. The latter is usually considered in a wireless ad-hoc unknown how to maximize the sum rate by optimizing the network, such as wireless sensor networks. system parameters. As we will demonstrate in this paper, Theremainderofthispaperisorganizedasfollows.Section the sum rate optimization of slotted Aloha networks can be II presents the system model. Section III focuses on the decomposed into two parts: 1) For given information encod- network throughput analysis, where the maximum network ing rate R, or equivalently, SINR threshold µ, the network throughput and the optimal backoff parameters are obtained throughput can be maximized by properly choosing backoff as functions of the SINR threshold and the mean received parameters, i.e., the transmission probabilities of nodes. 2) SNR. The maximum sum rate is derived in Section IV, and As the information encoding rate and the maximum network simulation results are presented in Section V. The effects of throughput are both functions of the SINR threshold µ, the keyfactors,includingbackoffandpowercontrol,arediscussed sum rate can be further optimized by tuning µ. in Section VI. Conclusions are summarized in Section VII. Specifically, we characterize the maximum sum rate of Table I lists the main notations used in this paper. slotted Aloha with the capture model by considering an n- node slotted Aloha network where all the nodes transmit to a II. SYSTEMMODEL single receiver with the SINR threshold µ, and the received Consider a slotted Aloha network where n nodes transmit SNRs of nodes’ packets are assumed to be exponentially to a single receiver, as Fig. 1 illustrates. All the nodes are distributed with the mean received SNR ρ. The main findings synchronizedandcanstartatransmissiononlyatthebeginning are summarized below. ofatimeslot.Foreachnode,assumethatitalwayshaspackets in its buffer and each packet transmission lasts for one time 1) The network steady-state point in saturated conditions, slot.Weassumeperfectandinstantfeedbackfromthereceiver which is characterized as the single non-zero root of and ignore the subtleties of the physical layer such as the the fixed-point equation of the limiting probability of switchingtime fromreceivingmodeto transmittingmodeand successful transmission of HOL packets, is found to be the delay required for information exchange. closelydependentontransmissionprobabilitiesofnodes, Letg denotethe channelgainfromnodek to thereceiver, the SINR threshold µ and the mean received SNR ρ. k which can be further written as g =γ ·h . h is the small- 2) The maximum sum rate is derived as a function of the k k k k scale fadingcoefficientof node k which varies fromtime slot mean received SNR ρ. Similar to the sum capacity of to time slot4 and is modeled as a complex Gaussian random MAC, it also logarithmically increases with ρ, but the variable with zero mean and unit variance. The large-scale high-SNRslopeisonlye−1. Inthelow SNRregion,itis fadingcoefficientγ characterizesthelong-termchanneleffect a monotonic increasing function of the number of nodes k n, and approaches e−1log2e≈0.5307 as n→∞. 4More specifically, we assume that the time slot length is equal to the 3) Toachievethemaximumsumrate,boththeSINRthresh- channel coherence time. 4 HOL packet performed among nodes’ packets or with previously received packets.Instead,each node’spacketis decodedindependently Node 1 by treating others’ as backgroundnoise at each time slot, and a packetcan be successfully decodedif its received signal-to- Node 2 interference-plus-noiseratio (SINR) is above a certain thresh- old. Node 3 Let Receiver µ=2R−1 (2) denote the SINR threshold at the receiver. For each node’s Node n packet,ifits receivedSINRexceedsthe thresholdµ, itcan be successfully decodedand rate R can be supportedfor reliable Fig.1. Graphicillustration ofann-nodeslottedAlohanetwork. communications.7 Note that when the SINR threshold µ is sufficientlysmall,morethanonepacketscouldbesuccessfully decoded at each time slot. It is clear that the number of successfully decoded packets in time slot t, denoted by N , t is a time-varying variable. As a result, the total received q p q1pt q2pt qKpt information rate, i.e., R·Nt bit/s/Hz, also varies with time. q0pt T 0 t 0 q0(1(cid:16)pt) 1 q1(1(cid:16)pt) 2 q2(1(cid:16)pt)(cid:857)...qK(cid:16)1(1(cid:16)pt) K In this paper, we focus on the long-term system behavior 1(cid:16)q and define the sum rate as the time average of the received 0 information rate: 1(cid:16)q0 1(cid:16)q1 1(cid:16)q2 1(cid:16)qKpt t q0(1(cid:16)pt) R = lim 1 R·N =R·λˆ , (3) s i out t→∞ t i=1 Fig.2. StatetransitiondiagramofanindividualHOLpacketinslottedAloha X networks. where t 1 λˆ = lim N (4) out i such as path loss and shadowing. Due to the slow-varying t→∞ t i=1 nature,the large-scalefadingcoefficientsareusuallyavailable X is the average number of successfully decoded packets per at the transmitter side through channel measurement. Let us time slot, which is referred to as the network throughput. first assume that power control is performed to overcome the effectoflarge-scalefading.5 Specifically,denotethetransmis- Both the information encoding rate R and the network sion power of node k as P¯ . Then we have throughputλˆout depend on the SINR threshold µ. Intuitively, k by reducing µ, more packets can be successfully decoded at P¯k·|γk|2 =P0. (1) each time slot, yet the information encoding rate becomes smaller. Therefore, the SINR threshold µ should be carefully In this case, each node has the same mean receivedSNR ρ= chosen to maximize the sum rate. Note that the network P /σ2. The assumption of power control will be relaxed in 0 throughput λˆ is also crucially determined by the protocol Section VI-B, where the analysis is extended to incorporate out design and backoff parameters. In the next section, we will distinct mean received SNRs. specifically focus on the network throughput performance of Throughout the paper, we assume that the receiver always slotted Aloha networks. has perfect channel state information but the transmitters are unaware of the instantaneous realizations of the small- scalefadingcoefficients.Asaresult,eachnodeindependently III. NETWORK THROUGHPUT encodesitsinformationatagivenrateRbit/s/Hz.Assumethat each codewordlasts for onetime slot,6 and the capturemodel As Fig. 1 illustrates, an n-node buffered slotted Aloha is adopted at the receiver side. That is, no joint decoding is network is essentially an n-queue-single-serversystem whose performanceis determinedby theaggregateactivitiesofHOL 5In practical systems such as cellular systems, the base-station sends a packets. In this section, we will first characterize the state pilot signal periodically for all the users in its cell to measure their large- transitionprocessofHOLpackets,andthenderivethenetwork scalefadinggainsandadjusttheirtransmissionpoweraccordinglytomaintain constant mean received power. This process is usually referred to as open- steady-statepointinsaturatedconditionsasthesinglenon-zero loop power control. It should also be noted that in the ad-hoc scenario, rootof the fixed-pointequation of the steady-state probability the difference in the large-scale fading gains from a certain node and its interferers cannot be removed by power control as they may transmit to different receivers. In that case, nodes would have distinct mean received 7Morespecifically,denotethereceivedSINRofnodekasηk.Iflog2(1+ SNRswhichareclosely dependent ontheirspacial locations. ηk)>R,thenbyrandomcodingtheerrorprobability ofnodek’spacket is 6Note that here we assume that each codeword only covers one channel exponentially reduced to zero as the block length goes to infinity. Here we coherencetimeperiod.Withoutcodingoverfadingstates,thedecodingdelay assume that the block length is sufficiently large such that node k’s packet isgreatlyreduced,butacertainratelossiscaused,aswewillshowinSection can be successfully decoded as long as ηk ≥ µ. Note that this is an ideal IV-BandSectionVI-A.Recentstudieshavealsoshownthatsignificantgains case.Inpractice,thethresholdnotonlydependsontheinformationencoding canbeachieved byintroducing codingoversuccessive packets ofeachnode rate R, but also the error probability that is determined by the coding and [55]–[58],whichisreferred toas“coded randomaccess”[59]. decoding schemes. 5 of successful transmission of HOL packets. Finally, the max- is busy with a non-empty queue. In this case, the network imum network throughputwill be obtained by optimizing the throughputis determined by the aggregate service rate, i.e., transmission probabilities of nodes. λˆ =nπ , (7) out T which,as(5)shows,dependsonthesteady-stateprobabilityof A. State Characterization of HOL Packets successful transmission of HOL packetsp. In this section, we The behavior of each HOL packet can be modeled as a will characterize the network steady-state point in saturated discrete-timeMarkovprocess. AsFig. 2 shows,8 a fresh HOL conditions based on the fixed-point equation of p. packet is initially in State T, and moves to State 0 if it is not transmitted. Define the phase of a HOL packet as the Specifically,forHOLpacketj,letSj denotethesetofnodes number of collisions it experiences. A phase-i HOL packet which have concurrent transmissions. It can be successfully stays in State i if it is not transmitted. Otherwise, it moves to decoded at the receiver side if and only if its received SINR StateTifitstransmissionissuccessful,orStatemin(K,i+1) is above the threshold µ, i.e., k∈SPjjPk+σ2 ≥µ, where Pk = if the transmission fails, where K denotes the cutoff phase. P¯k|gk|2 = P0|hk|2 denotes thPe received power according to Note thatthe cutoffphase K can be anynon-negativeinteger. (1). Suppose that |S | = i. The steady-state probability of j When K =0, States 0 and K in Fig. 2 would be mergedinto successful transmission of HOL packet j given that there are one state, i.e., State 0. Intuitively, to alleviate the contention, i concurrent transmissions, rj, can be then written as i nodes should reduce their transmission probabilities as they experience more collisions. Therefore, we assume that the rj =Pr |hj|2 ≥µ , (8) transmissionprobabilities{qi}i=0,...,K formamonotonicnon- i ( k∈Sj|hk|2+ρ1 ) increasing sequence. P where ρ = P /σ2 is the mean received SNR. With h ∼ In Fig. 2, p denotesthe probabilityof successfultransmis- 0 k sionofHOLptacketsattimeslott.9Itcanbeeasilyshownthat CN(0,1), rij can be easily obtained as [24], [32] the Markov chain is uniformly strongly ergodic if and only if µ exp − the limit lim pt =p exists [60]. The steady-state probability rij = (µ(cid:16)+1)ρi(cid:17). (9) t→∞ distribution{πi} of the Markovchain in Fig. 2 can be further The right-handside of (9) is independentof j, indicating that obtained as all the HOL packets have the same conditional probability of πT = Ki=−01 (1−qip1)i+(1p−qpK)K , (5) jsu,cacnedssfwurlitteratnhsemsistesaiodny.-1s0taTteheprreofobraeb,ilwiteydorfopsutchceesssufpuelrtsrcarnips-t and P mission of HOL packets p as π = 1−pq0π . K =0 n−1 0 pq0 T p= r ·Pr{i concurrent transmissions}. (10) π = 1−q0π , π = (1−p)iπ , i=1,...,K−1, i π0 = (q10−p)KTπ .i qi T K ≥1 Xi=0 K pqK T In saturated conditions, all the nodes have non-empty (6) Notethatπ isthe servicerateofeachnode’squeueasthe queues. According to the Markov chain shown in Fig. 2, the T probability that the HOL packet is requesting transmission is queue has a successful output if and only if the HOL packet givenbyπ q + K π q ,whichisequaltoπ /paccording is in State T. T 0 i=0 i i T to (6). Therefore, the probability that there are i concurrent P transmissions can be obtained as B. Steady-state Point in Saturated Conditions Pr{i concurrent transmissions} By regarding an n-node buffered slotted Aloha network as n−1 n−1−i i an n-queue-single-serversystem, we can see that the network = 1− πT πT . (11) throughput λˆout is indeed the system output rate, which is (cid:18) i (cid:19)(cid:16) p (cid:17) (cid:16) p (cid:17) equal to the aggregate input rate λˆ if each node’s buffer has By substituting (9) and (11) into (10), the steady-state prob- a non-zero probability of being empty. As λˆ increases, the ability of successful transmission of HOL packets p can be network will eventually become saturated where each node obtained as n−1 8Note that a similar Markov chain of the HOL packet was established p=exp −µ · 1− µ · πT ρ µ+1 p in [20] where the transmission probability of each fresh HOL packet was assumedtobe1.HeretheoriginalState0issplitintotwostates,i.e.,StateT forl≈argen(cid:16)exp(cid:17) −(cid:16)µ − nµ · πT(cid:17) , (12) andState0,toincorporate ageneral transmissionprobability of0<q0≤1 ρ µ+1 p foreachfreshHOLpacket. n o 9Note that in Fig. 2, the probability of successful transmission of HOL where the approximationis obtained by applying(1−x)n ≈ 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 10NotethatherealltheHOLpacketshavethesameconditionalprobability transmission only depends on the attempt rate of other HOL packets at the ofsuccessfultransmissionbecausetheirmeanreceivedSNRsareassumedto moment,whichisdenotedaspt inFig.2. beequal. 6 102 102 101 101 100 100 (cid:214)(cid:540)max10-1 (cid:214)(cid:540)max10-1 10-2 (cid:85)=0dB 10-2 (cid:80)=0.01 (cid:85)=10dB (cid:80)=0.5 10-3 (cid:85)=20dB 10-3 (cid:80)(cid:3)(cid:32)(cid:3)(cid:20) (cid:80)(cid:3)(cid:32)(cid:3)(cid:24) 10-140-4 10-3 10-2 n1(cid:16)1 10-1 100 101 102 10--430-25.3-20 -15 -10 -5 0 57 10 15 20 25 30 (cid:541) (cid:85) (dB) (a) (b) Fig.3. Maximumnetworkthroughput λˆmax versus(a)SINRthreshold µand(b)meanreceived SNRρ.n=50. exp(−nx) for 0 < x < 1.11 Finally, by substituting (5) into maximum network throughput λˆ and the corresponding max (12), we have optimal backoff parameters {q∗}. i Theorem 2. For given SINR threshold µ∈(0,∞) and mean p≈exp−µρ − µn+µ1 · K−1p(1−1p)i (1−p)K . (13) received SNR ρ ∈ (0,∞), the maximum network throughput i=0 qi + qK is given by   The following theorem states the existence and uniqueness P µ+1exp −1− µ if µ≥ 1 of the root of the fixed-point equation (13). λˆ = µ ρ n−1 (16) max nexp −(cid:16)nµ − µ(cid:17) otherwise, Theorem1. Thefixed-pointequation(13)hasonesinglenon-  µ+1 ρ zero root pA if {qi}i=0,...,K is a monotonic non-increasing which is achievedat (cid:16) (cid:17) sequence. qˆ Q if µ≥ 1 q∗ = 0 i n−1 (17) Proof: See Appendix A. i (1 otherwise, As we can see from (13), the non-zero root p is closely A dependentonbackoffparameters{qi}i=0,...,K.Withoutlossof i=0,...,K, where qˆ0 is given by generality,let q =q ·Q where q is the initial transmission i 0 i 0 K−1 µ µ i exp −1− 1−exp −1− pfuronbctaiboinlitoyfaindwiQthiQis a=n a1rbaitnrdaryQm≤onoQtonic, nio=n-i1n,c.re.a.s,iKng. qˆ0 = µn+µ1 ·( (cid:16) ρ(cid:17)hQi (cid:16) ρ(cid:17)i 0 i i−1 i=0 X With the cutoffphaseK =0, orthe backofffunctionQi =1, 1−exp −1−µ K i=0,...,K, for instance, p can be explicitly written as + ρ . (18) A h (cid:16)QK (cid:17)i ) p =exp −µ − nµ q . (14) A ρ µ+1 0 Proof: See Appendix B. (cid:16) (cid:17) Eq. (16) shows that for given SINR threshold µ, the C. Maximum Network Throughput for Given µ and ρ maximumnetworkthroughputλˆ isamonotonicincreasing max It has been shown in Section III-B that the network oper- function of the mean received SNR ρ. As ρ→∞, we have ates at the steady-state point p in saturated conditions. By A µ+1e−1 if µ≥ 1 cwormittbeinniansg (7) and (12), the network throughputat pA can be ρl→im∞λˆmax =(nµexp − nµ otherwisne−,1 (19) µ+1 λˆ =(µ+1)· −pAlnpA − pA , (15) which approaches e−1 when(cid:16)µ≫1(cid:17). out µ ρ where p is an implicit func(cid:16)tion of the tran(cid:17)smission prob- On the other hand, for given mean received SNR ρ, λˆmax A monotonically decreases as the SINR threshold µ increases, abilities q , i = 0,...,K, which is given in (13). It can i as Fig. 3a illustrates. With a lower µ, the receiver can decode be seen from (15) and (13) that the network throughput more packets among multiple concurrent transmissions, and is crucially determined by the backoff parameters {q }. In i thus better throughput performance can be achieved. It can this section, we focus on the maximum network throughput be easily shown that multipacket reception is possible when λˆ = max λˆ . The following theorem presents the max {qi} out the SINR threshold µ is sufficiently small. Specifically, for µ ≥ 1 , λˆ > 1 if and only if 1 ≤ µ < 1 and ρ > 11Note that with a small network size, i.e., n ≤ 5 for instance, the n−1 max n−1 e−1 approximationerrormaybecomenoticeable.It,nevertheless,rapidlydeclines µ . Otherwise, λˆ >1 if and only if ρ> µ . asthenumberofnodesnincreases. lnµ+µ1−1 max lnn−µn+µ1 7 3 2 10 10 102 n(cid:32)30 n(cid:32)30 n(cid:32)50 n(cid:32)50 1 1 10 10 n (cid:32)100 n (cid:32)100 *(cid:541) 100 *=(cid:541)(cid:541)max (cid:540) -1 0 10 10 -2 10 xdenotes(cid:85)0 xdenotes(cid:85)0 -3 -1 10 10 -20 -15 -10 -5 0 3 5 10 15 20 25 30 -20 -15 -10 -5 0 3 5 10 15 20 25 30 (cid:85)(dB) (cid:85)(dB) (a) (b) Fig.4. (a)OptimalSINRthreshold µ∗ and(b)maximumnetworkthroughput λˆµm=axµ∗ versusmeanreceived SNRρ. As Fig. 3b illustrates, with n = 50, if the SINR threshold ThefollowingtheorempresentsthemaximumsumrateC and µ = 0.01 < 1 , λˆ > 1 when the mean received SNR the optimal SINR threshold µ∗. n−1 max ρ>−25.3dB.On the otherhand,if µ=0.5, we have 1 < n−1 Theorem 3. For given mean received SNR ρ ∈ (0,∞), the µ < 1 ≈ 0.582. In this case, λˆ > 1 when the mean e−1 max maximum sum rate is received SNR ρ>7dB. Note that in spite of the improvement on the maximum µ∗hµ+∗1exp −1− µρ∗h log2(1+µ∗h) if ρ≥ρ0 C = h network throughput by reducing the SINR threshold µ, the nexp −(cid:16)nµ∗l − µ∗l (cid:17)log (1+µ∗) otherwise, information encoding rate that can be supported for reliable  µ∗l+1 ρ 2 l (cid:16) (cid:17) (22) communications, i.e., R = log (1+µ), is quite low when µ 2 which isachieved at is small. It is clear that the SINR threshold µ determines a tradeoff between the network throughputand the information µ∗ = µ∗h if ρ≥ρ0 (23) encoding rate. In the next section, we will further study how (µ∗l otherwise, to maximize the sum rate by properly choosing the SINR where µ∗ and µ∗ are the roots of the following equations: threshold µ. h l µ+1 1 + (µ+1) ρ µ =e, (24) IV. MAXIMUM SUMRATE and In this section, we will derive the maximum sum rate and µ+1 n + (µ+1) ρ µ+1 =e, (25) the correspondingoptimal SINR threshold as functionsof the mean received SNR ρ, and discuss their characteristics at the respectively, and high SNR and lower SNR regions, respectively. n n ln Specifically, it has been demonstrated in Section II that ρ = n−1 n−1 . (26) 0 n 1−(n−1)ln the sum rate of slotted Aloha networks is determined by the n−1 informationencodingrateRandthenetworkthroughputλˆ . Proof: See Appendix C. out By combining (2) and (3), the maximum sum rate can be Note that ρ is a monotonic decreasing function of n ∈ 0 written as [2,∞), and lim ρ =2. When the number of nodes n is n→∞ 0 large, ρ is close to 3dB. 0 C = max λˆ log (1+µ) =max log (1+µ)maxλˆ . out 2 2 out µ,{qi}(cid:16) (cid:17) µ (cid:18) {qi} (2(cid:19)0) A. Optimal SINR Threshold µ∗ Section III further shows that if backoff parameters {q } i are properly selected, the network throughput is maximized Theorem 3 shows that to achieve the maximum sum rate, at λˆ , which is a function of the SINR threshold µ. By the SINR threshold µ should be carefully selected. Fig. 4a max combining (20) and Theorem 2, the maximum sum rate can illustrates how the optimalSINR threshold µ∗ varies with the be further written as C = maxµ>0f(µ), where the objective mean received SNR ρ. At the low SNR region, i.e., ρ < ρ0, function f(µ) is given by for instance, we can obtain from (23) and (25) that µ∗ρ<ρ0 = f(µ)= µ+µ1exp −1− µρ log2(1+µ) if µ≥ n−11 bµr∗lan≈che−oWft0h(cid:16)e−Ln1a(cid:17)m−b1erftoWrlafrugnectnio,nw[h6e1r]e.WIn0t(hzis)cisasthe,etphreinecffipecatl nexp −(cid:16)nµ − µ(cid:17)log (1+µ) otherwise. of the mean received SNR ρ becomes negligible, and µ∗  µ+1 ρ 2 ρ<ρ0 (cid:16) (cid:17) (21) reduces to a monotonic decreasing function of the number of  8 2.5 e(cid:16)1log e 2 0.5 (22) n(cid:32)100 2 (28) 0.4 (22) z)1.5 z) s/H s/H0.3 (29) bit/ bit/ ( ( C 1 C0.2 n(cid:32)30 0.5 0.1 High-SNR Large-n approximation approximation (cid:85)00=3 5 10 15 20 25 30 0-20 -15 -10 -5 0 (cid:85)0=3 (cid:85)(dB) (cid:85)(dB) (a) (b) Fig.5. (a)MaximumsumrateC atthehighSNRregion. (b)MaximumsumrateC atthelowSNRregion. nodes n. With a large n, µ∗ ≪ 1, implying that multiple Moreover, a logarithmic increase of the maximum sum rate ρ<ρ0 packets can be successfully decoded. C can be observed at the high SNR region. The following At the high SNR region, we can obtain from (23-24) that corollary presents the high-SNR slope of C. µ∗ =µ∗ ≈eW0(ρ) forlargeρ.AswecanseefromFig.4a, wρit≥hρ0ρ≫1h,theoptimalSINRthresholdµ∗ monotonically Corollary 1. limρ→∞ logC ρ =e−1. ρ≥ρ0 2 increases with the mean received SNR ρ. Proof: See Appendix D. By combining(23) with Theorem2, we can also obtainthe Recallthatthehigh-SNRslopeof theergodicsumcapacity maximum network throughput with µ=µ∗ as of MAC is 1 when single-antenna is employed at both the µ∗h+1exp −1− µ∗h if ρ≥ρ transmitters and the receiver. To achieve the ergodic sum λˆµ=µ∗ = µ∗h ρ 0 (27) capacity, however, a joint decoding of all received signals max nexp −(cid:16)nµ∗l − µ∗l (cid:17) otherwise. is required and the codewords should span multiple fading  µ∗l+1 ρ states.Withthecapturemodel,incontrast,eachnode’spacket (cid:16) (cid:17) Fig. 4b illustrates how the maximum network throughput  is decoded independently by treating others’ as background λˆµ=µ∗ varies with the mean received SNR ρ. As we can max noiseateachtimeslot. WhenthemeanreceivedSNRis high, see from Fig. 4b, at the low SNR region, i.e., ρ < ρ , the 0 atmostonepacketcanbesuccessfullydecodedeachtimedue effectof ρ is negligible,and λˆµm=axµ,∗ρ<ρ0 becomesa monotonic toalargeSINRthresholdµ∗ ≫1.Corollary1showsthatwith increasingfunctionofthenumberofnodesn.Inthiscase,the the simplified receiver, the high-SNR slope of the maximum optimalSINR thresholdµ∗ =µ∗ is decreased as n grows, ρ<ρ0 l sum rate of slotted Aloha networksis significantly lower than and thus more packets can be successfully decoded, though that of the sum capacity. each at a smaller information encoding rate. For large n, we have λˆµ=µ∗ ≈ne−1 according to (27). max,ρ<ρ0 AtthehighSNRregion,Fig.4ahasshownthattheoptimal C. Maximum Sum Rate C at Low SNR Region SINRthresholdµ∗ =µ∗ ismuchlargerthan1,withwhich asqltuoimtc.koTlsyhtedorrneoefpospreab,cektlhoeρewt≥ρcm10aa,nxabinmedhusemuvcecnneetustswafluolylrlkyaptdhperrocoouadgcehhdepsuatet−λˆe1µma=caahxµs,∗ρρti≥m→ρ0e olaprFtgioemranlρ.ST<IhNeρR0c,othrirrteehssphaoosnldbdeiµneng∗ρ<msρh0aoxw=imnµui∗lmn ≈Ssuecmet−ioWrna0t(cid:16)eI−Vc-n1aAn(cid:17) t−bhea1tthtfheoner approximated by ∞. C ≈−nW −1 B. Maximum Sum Rate C at High SNR Region ρ<ρ0 0 n 1 Similar to Section IV-A, let us take a closer look at the ·exp −n(cid:0) 1−(cid:1) eW0 −n1 − e−W0 −n!−1 log e, maximum sum rate C at different SNR regions.  (cid:16) (cid:17) ρ  2 (cid:18) (cid:19) With ρ ≥ ρ , it has been shown in Section IV-A that the 0   (29) optimal SINR threshold µ∗ = µ∗ ≈ eW0(ρ) for large ρ. ρ≥ρ0 h for n ≫ 1. As we can see from Fig. 5b, the approximation Themaximumsumrateinthiscasecanbethenapproximated (29) works well when the number of nodes n is large. The by followingcorollaryfurtherpresentsthelimitingmaximumsum C ≈ 1+e−W0(ρ) exp −1− eW0(ρ) log (1+eW0(ρ)), rate as n→∞ at the low SNR region. ρ≥ρ0 ρ 2 (cid:16) (cid:17) (cid:16) (cid:17) (28) Corollary 2. lim C =e−1log e. for ρ ≫ 1. As Fig. 5a shows, the approximation (28) works n→∞ ρ<ρ0 2 well when the mean received SNR ρ is large, i.e., ρ≥15dB. Proof: See Appendix E. 9 0.8 1 0.7 0.9 K=0 K=1 0.6 Analysis Analysis 0.8 Simulation Simulation 0.5 0.7 pA0.4 K=3 pA n=A3na0lysis Analysis 0.6 0.3 Simulation Simulation 0.5 0.2 n=50 n=100 0.4 Analysis Analysis 0.1 Simulation Simulation 0 0.3 0.01 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.01 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 q q 0 0 (a) (b) Fig.6. Steady-state pointpA versusinitial transmissionprobability q0.(a)n=50.µ=1andρ=10dB.(b)K=0.µ=0.01andρ=0dB. 0.7 40 (cid:540)ˆma=x0.67 (cid:79)(cid:214)mn(cid:32)a1x00=37 35 0.6 K= 3 (cid:79)(cid:214)mn(cid:32)ax50=30 0.5 Analysis Simulation 25 0.4 K= 0 (cid:79)(cid:214)mn(cid:32)ax30=22 ˆ(cid:540)out0.3 SAinmaulylasitsion (cid:214)(cid:540)out 20 n=30 15 Analysis K= 1 0.2 10 Simulation Analysis n=50 n=100 0.1 Simulation 5 Analysis Analysis denotesqˆ0 Simulation Simulation 0 0 0.040.070.150.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0.01 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 q q 0 0 (a) (b) Fig.7. Networkthroughput λˆout versusinitial transmission probability q0.(a)n=50.µ=1andρ=10dB.(b)K=0.µ=0.01andρ=0dB. Note that it has been shown in Section IV-A that with Section III-B has shown that the network operates at the ρ < ρ , the maximum network throughput λˆµ=µ∗ ≈ ne−1, steady-state point p , which is closely determined by the 0 max A which grows with the number of nodes n unboundedly. number of nodes n and the backoff parameters {q }. The i Although more packets can be successfully decoded, the expressionofp isgivenin(13)andverifiedbythesimulation A information carried by each packet decreases as n increases results presented in Fig. 6.12 due to a diminishing information encoding rate, i.e., R = Fig. 7 illustrates the corresponding network throughput log (1 + µ∗ ) ≈ 1 log e for large n. Therefore, as the performance. The network throughput λˆ has been derived 2 ρ<ρ0 n 2 out number of nodes n → ∞, the maximum sum rate reaches asa functionofp in(15)inSectionIII-C,whichvarieswith A a limit that is independent of the mean received SNR, as thebackoffparameters.AswecanseefromFig.7,thenetwork Corollary 2 indicates. It is in sharp contrast to the ergodic throughputperformanceissensitivetothesettingoftheinitial sum capacity of MAC which linearly increases with n and ρ transmissionprobabilityq .AccordingtoTheorem2,whenthe 0 at the low SNR region. SINR threshold µ ≥ 1 , the maximum network throughput n−1 λˆ is achieved when q is set to be qˆ . Otherwise, λˆ is max 0 0 max achieved with q =1, i = 0,...,K. The expressions of λˆ V. SIMULATION RESULTS andthecorrespoindingoptimalbackoffparametersq∗ aregimveanx i in (16) and (17), respectively, and verified by the simulation Inthissection,simulationresultswillbepresentedtoverify results presented in Fig. 7. the preceding analysis in Sections III and IV. In particular, It is further demonstrated in Section IV that as both the we consider a saturated slotted Aloha network with Binary ExponentialBackoff(BEB),i.e.,thetransmissionprobabilities of each node are given by the geometric series q = q · 1, 12In simulations, the steady-state probability of successful transmission i=0,...,K.Thesimulationsettingisthesameasithes0yste2mi of HOL packets pA is obtained by calculating the ratio of the number of successfultransmissionstothetotalnumberofattemptsofHOLpacketsover model and thus we omit the details here. alongtimeperiod, i.e.,108 timeslots. 10 Rs(bit/s/Hz) steady-state point in saturated conditions can be obtained C(cid:85)(cid:32)15 dB=1.012 from (13) as pqi=q =exp −µ − nqµ , and the correspond- A ρ µ+1 (cid:85)(cid:32)15 dB ing network throughput i(cid:16)s λˆqi=q =(cid:17)nqexp −µ − nqµ , 0.8 out ρ µ+1 C(cid:85)(cid:32)10 dB=0.73 ASnimaulylsaitsion according to (15). The sum rate can be th(cid:16)en written (cid:17)as 0.6 Rsqi=q = nqexp −µρ − µn+qµ1 · log2(1 + µ), which is an C(cid:85)(cid:32)0 dB=0.53 increasing function(cid:16)of the mea(cid:17)n received SNR ρ. 0.4 As ρ → ∞, it can be easily obtained that R˜qi=q = s 0.2 (cid:85)(cid:32)A0n adlBysis (cid:85)(cid:32)A10n adlyBsis limρ→∞Rsqi=q = nqexp −µn+qµ1 · log2(1 + µ), with the Simulation Simulation maximum (cid:16) (cid:17) 00.02 2 2.9 4 6 8 9.210 12 14denot1e6s(cid:80)*18 20 (cid:80) maxR˜qi=q =nqexp −nq 1−eW0 −n1q µ s (cid:16) (cid:17) (cid:18) (cid:18) (cid:19)(cid:19) rFeicge.i8v.edSSuNmRraρt.enR=sv5e0rs.uKsS=IN0Rathnrdesqh0ol=dµq0∗u.nderdifferentvaluesofmean ·log2e−W0(cid:16)−n1q(cid:17), (30) which is achieved at maximum network throughput and the information encoding µ∗,qi=q =e−W0 −n1q −1. (31) rate depend on the SINR threshold µ, the sum rate can be (cid:16) (cid:17) maximized by optimally choosing µ. We can clearly observe Eq. (31) shows that the optimal SINR threshold µ∗,qi=q from Fig. 8 that the sum rate performance is sensitive to the monotonically decreases as the number of nodes n grows. SINR threshold µ especially when the mean received SNR For large n ≫ 1, it can be obtained from (30-31) that ρ is small. To achieve the maximum sum rate, µ should be µ∗,qi=q ≈ 1 , and nq properly set according to ρ. The expressions of the optimal SINR threshold µ∗ and the maximum sum rate C are given maxR˜qi=qn≈≫1e−1log e. (32) s 2 µ inTheorem3, andverifiedbythesimulationresultspresented in Fig. 8. Recall that it has been shown in Section IV-B that the maximum sum rate increases with the mean received SNR ρ unboundedly. Here (32) indicates that with a constant VI. DISCUSSIONS transmissionprobability,thesumrateconvergestoalimitthat So far we have shown that to optimize the sum rate is much lower than 1 as ρ→∞. It corroboratesthat adaptive performanceof slotted Aloha networks,the SINRthresholdµ backoff is indispensable for random-access networks. and backoffparameters{q } should be properlyset according i It is interesting to note that when q = 1, all the nodes to the mean received SNR ρ, and the maximum sum rate persistently transmit their packets, and the slotted Aloha logarithmically increases with ρ with the high-SNR slope network reduces to a typical MAC. It is well known that for of e−1. In this section, we will further discuss how the an n-user AWGN MAC, if the capture model is adopted at performance is affected by key factors such as backoff and the receiver side and all the users have equal received power, power control. the sum rate approaches log e as n→∞ [62]. Here we can 2 see from (32) that an additional factor of e−1 is introduced, A. Effect of Adaptive Backoff which is mainly attributed to the effect of channel fading.14 Backoff is a key componentof random-access networks. It has been shown in Sections III and IV that to achieve the B. Effect of Power Control maximum sum rate, backoff parameters, i.e., the transmission So far we have focused on a homogeneous slotted Aloha probabilities {q } of nodes, should be adaptively tuned ac- i network where all the nodes have the same mean received cording to the number of nodes n and the mean received SNR ρ. In this section, the analysis will be extended to the SNR ρ.13 In many studies, however, nodes are supposed to heterogeneous case, where nodes in the same group have an transmittheirpacketswith a fixedprobability[23], [25], [26], identical mean received SNR but SNRs differ from group to [31], [32]. To see how the rate performance of slotted Aloha group. deteriorates without adaptive backoff, let us assume that each Specifically,assumethatnnodesaredividedintoM groups. nodetransmitsits packetwith a constantprobabilityq ateach Group m has n nodes, and each node in Group m has time slot, i.e., q =q, i=0,...,K. In this case, the network m i the mean received SNR ρ , m = 1,...,M. For HOL m 13Note that for practical random-access networks, the backoff parameters packet j, let Sj denote the set of nodes that have concurrent can be updated through the feedback from the common receiver. In IEEE transmissions. It can be successfully decoded at the receiver 802.11networks, forinstance, as eachnodeassociates withtheaccess-point if and only if its received SINR is above the SINR threshold (AP)uponjoiningthenetwork,theAPcancountthenumberofnodesthrough theMACheaderoftheframesentbyeachnode,calculatetheoptimalbackoff parameters, andbroadcastthem inthebeacon frameperiodically. Eachnode 14Notethatinthispaper,eachcodewordisassumedtolastforonechannel canthenupdateitsbackoffparametersaccordingtothereceivedbeaconframe. coherencetimeperiod.Withoutcodingoverdifferentfadingstates,thechannel Such a feedback-based update process can also be implemented in cellular fluctuations cannot be averaged out, thus leading to a significant rate loss systemswherethebase-station servesasthecommonreceiver ineachcell. comparedtotheAWGNcase.