frameless ALOHA: analysis of the physical layer effects
This study delves into the effects of frameless ALOHA on the physical layer in massive M2M communication systems. Covering topics such as random access based on rateless codes, noise, and capture scenarios, the research explores the intricacies of wireless communication technologies for future networks. Understand the challenges and advancements in wireless connectivity as we shape the future of M2M communication with a focus on access protocols, device interactions, and network optimization strategies.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
frameless ALOHA: analysis of the physical layer effects Petar Popovski Cedomir Stefanovic, Miyu Momoda Aalborg University Denmark
outline intro: massive M2M communication frameless ALOHA random access based on rateless codes noise and capture summary 2 / 32
the shape of wireless to come R1: today s systems R2: high-speed versions of today s systems R3: massive access for sensors and machines R4: ultra-reliable connectivity R5: physically impossible data rate Gbps R2 99% R5 Mbps R1 95% 99% kbps R4 99.999% R3 90-99% bps # devices 1 10 100 1000 1000 0 3 / 15
massive M2M it will be billions, but how many? o Ericsson figure is pointing to 50 billions o others are less ambitious massive variation in the requirements o traffic burstiness/regularity smart meter vs. event-driven surveillance camera o data chunk size single sensor reading vs. image o dependability requirements emergency data vs. regular update 4 / 32
defining massive M2M the total number of managed connections to individual devices is much larger than the average number of active connections within a short service period 5 / 32
access protocols for massive M2M massive M2M setup emulates the original analytical setup for ALOHA infinite population, maximal uncertainty about the set of active devices difference occurs if the arrivals are correlated short service period event time 6 / 32
how to make protocols for massive access predict the activation: account for the relations among the devices, group support, traffic correlation control the activation load control mechanisms our focus: improve the access capability of the protocols departure from collision is a waste put more burden on the BS 7 / 32
observations on random access useful when the devices have not interacted before the required flexibility is above a threshold use with caution in a static setup , the devices know each other , and a better strategy (learning, adaptation) can be used signaling, waste (error, collisions) may take a large fraction of the resources especially important for small data chunks 8 / 32
FRAMELESS ALOHA or rateless coded random access 9 / 32
slotted ALOHA essentially part of all cellular standards all collisions destructive only single slots contribute to throughput memoryless randomized selection of the retransmission instant 10 / 32
expanding ALOHA with SIC (successive interference cancellation) users send replicas in several randomly chosen slots same number of replicas per user throughput 0.55 with two repetitions per user frame of M slots time slots . . . E. Casini, R. De Gaudenzi, and O. Herrero, Contention Resolution Diversity Slotted ALOHA (CRDSA): An Enhanced Random Access Scheme for Satellite Access Packet Networks, Wireless Communica- tions, IEEE Transactions on, vol. 6, pp. 1408 1419, april 2007. . . . N users 11 / 32
how SIC is done each successfully decoded replica enables canceling of other replicas user 1 user 2 user 3 slot 1 slot 2 slot 3 slot 4 time 12 / 32
SIC and codes on graphs new insight - analogy with the codes-on-graphs - each user selects its no. of repeated transmissions according to a predefined distribution important differences - left degree can be controlled to exact values, right degree only statistically - right degree 0 possible (idle slot) check nodes . . . . . . variable nodes G. Liva, Graph-Based Analysis and Optimization of Contention Resolution Diversity Slotted ALOHA, IEEE Trans. Commun., Feb. 2011. 13 / 32
frameless ALOHA N users M slots idea: apply paradigm of rateless codes to slotted ALOHA: no predefined frame length slots are successively added until a criterion related to key performance parameters of the scheme is satisfied . . . . . . 14 / 32
frameless ALOHA overview time slots . . . . . . . . . single feedback used after M-th slot - M not defined in advance (rateless!) feedback when sufficient slots collected - for example, NR < N resolved users lead NR M to throughput of 15 / 32
frameless ALOHA stopping criterion Tmax N G M /N 1 Fraction of resolved users FR Instantaneous throughput TI 50 100 500 1000 5000 2.55 2.68 2.85 2.9 2.98 ALOHA in terms of (1) fraction of resolved users (2) instantaneous throughput 1.32 1.27 1.15 1.12 1.08 0.68 0.73 0.8 0.82 0.85 0.9 0.8 a typical run of frameless 0.7 0.6 3.12 1.05 0.87 0.5 (and-or tree evaluation) 0.4 TABLE I OPTIMAL TARGET DEGREEG , OPTIMAL NORMALIZED NUMBER OF SLOTSM /N IN FRAME, AND MAXIMAL AVERAGE THROUGHPUT Tmax, FOR THE GIVEN NUMBER OF USERSN 0.3 0.2 0.1 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 M/N degreeG andnormalizednumber of slotsM /N of theframe for which the corresponding maximal average throughput Tmax is achieved, for the given number of users N results can be used as guidelines for the design of framed ALOHA-basedscheme, wherethethelengthof theframe(i.e., contention period) is a priori fixed. Depending on the number of users in the system N, one should select the frame length equal to M and the target degree equal to G ; this selection of parameters results with the expected throughput equal to Tmax. In [6] it was shown that, for finite N , the achievable throughputs listed in Table I are higher than in the case of more involved framed ALOHA-based schemes [5], while in the same time, the average number of transmissions per user (8) is lower. However, our approach is frameless - the length of the contention period is not a priori fixed and it lasts until sufficiently high fraction of the users has been resolved. We elaboratetheguiding principlesfor terminating thecontention period in details in the next section. Fig. 2. Typical performance of the proposed scheme, N = 500, G = 2.85. genie-aided stopping criterion: stop when T is maximal heuristic stopping criterion: fraction of resolved users 4. These fraction should be chosen such that the (expected) throughput is maximized. FR is computed as: 16 / 32 NR N FR= , (15) where NR is the number of resolved users, which is tracked by the BS. Before proceeding with a more detailed analysis, in Fig. 2 we present a typical performance of the proposed scheme, expressed through the fraction of resolved users FR and instantaneous throughput TI (i.e., the number of resolved users divided by the number of elapsed slots), as the number of slots increases. The sharp increase in the performance parametersstemsfrom thewell-known threshold phenomenon characteristic for the iterative BP decoding [12], i.e., in our case SIC. Obviously, due to this sharp increase, the range in which the threshold on the fraction of resolved users could be placed is wide. Fig. 2 also illustrates why we chose to terminate the contention period based on FR, rather than TI. Specifically, FR is a monotonically increasing function, implying that FR will eventually reach any threshold V 1. Onetheother hand, TI isnot amonotonicfunctionand it may never reach the chosen threshold value5. B. Terminating the Contention Period In a rateless coding scenario, the natural criterion for terminating the transmission of encoded symbols is when the complete message has been decoded on the receiving end. However, due to the constraints of the proposed scheme, an analogous criterion, where the contention period terminates upon resolving all users, would lead to inefficient use of system resources (i.e., slots). Particularly, the probability of a user having degree 0 (i.e., not transmitting at all) is: C. Results We used a simulation based approach to find the optimal target degrees G and thresholds V that maximize the ex- pected throughput. Unless otherwise stated, all the presented resulted are obtained by running 1000 simulation repeats for each set of parameters6. Table II lists G , V and corresponding average fraction of resolved users FR, normalized number of slots in the contention period M /N, and maximal average throughputs Tmax that can be achieved. Comparing these results with the ones listed in Table I, it is obvious that, when the number of usersintherangeof hundred/thousand,theframelessapproach P [|u| = 0] = 0= e (1+ )G= e M NG (14) and it exponentially decays with M , with the decay constant G. As the values of G of interest are rather low, see Table II, (14) implies that the probability of user not transmitting and, therefore, not even having a chance to be resolved, decreases rather slowly with M . Consequentially, waiting for all users to become resolved would lead to prohibitively long contention periods. A more suitable approach for terminating the contention period would be to do it when the fraction of resolved users FR reaches the predefined threshold; this 5E.g., there is a always a that for a particularly bad instance of SIC evolution as the slots of the contention period elapse can happen, resulting with a maximal instantaneous throughput that is lower than the chosen threshold. 6Again, the presented results are rounded to the first two decimals. 4The presented results are rounded to the first two decimals.
analogy with the rateless codes structural selection of transmission probabilities operational stopping criterion based on target performance controlling of the degree distribution in the simplest case all the users have the same transmission probability 17 / 32
errorless case all users transmit with the same probability distribution no channel-induced errors pa=b slot access probability N is the average slot degree objective: maximize throughput by selecting and designing the termination criterion 18 / 32
9 period. In this section we elaborate the guiding principles for terminating the contention period. We develop analysis for the case when the noise can be neglected, see (2), and asses the impact of noise in Section IV-D. In a typical rateless coding scenario, the criterion for terminating the transmission of encoded symbols is when the complete message has been decoded on the receiving end. However, due to the constraints of the proposed scheme, an identical criterion, where the contention period terminates upon resolving all users, would lead to inefficient use of system resources (i.e., slots) and low throughputs. Particularly, the probability of a user being of degree 0 (i.e., not transmitting at all) is: P [|u| = 0] = 0= e (1+ )G= e M NG (12) and it exponentially decays with M , with the decay constant G. As shown in [8], and also due to the limitations of SIC [14], [15], the interesting values of G are rather low, implying that the probability of user not transmitting and, therefore, not even having a chance to be resolved, decreases rather slowly with M . In other words, waiting for all users to become resolved would lead to prohibitively long contention periods. On the other hand, our aim is to maximize the slot utilization and the expected throughput T. The key observation is that in coded random access it is not vital to resolve all the users in a single contention period, as the unresolved users can always be directed towards a newly initiated contention. Therefore, the contention period should ideally be terminated when the instantaneous throughput TI reaches its maximal value, postponing the unresolved users to a future contention period. If the contention is terminated at the M-th slot and the number of resolved users in the asymptotic analysis same time is NR, then TI can be computed as: probability of user resolution PR when the number of users N goes to infinity TI =NR M. (13) M is the number of elapsed slots A. Asymptotic Analysis The asymptotic behavior, when N , of the probability of user resolution PR and the expected throughput T: asymptotic throughput PR M/N= PR 1+ T = , (14) March 28, 2013 DRAFT 19 / 32
result of the AND-OR analysis 20 / 32
non-asymptotic behavior 21 / 32
termination and throughput simple termination: stop the contention if either is true FR V or T=1 50 0.83 0.82 0.75 0.97 2.68 0.83 100 0.84 0.84 0.76 0.95 2.83 0.87 500 0.88 0.87 0.76 0.9 2.99 0.88 1000 0.88 0.88 0.76 0.9 3.03 0.89 genie-aided (GA) termination the highest reported throughput for a practical (low to moderate) no. of users 22 / 32
average delay the rateless structure provides an elegant framework to compute the average delay of the resolved users average delay as a function of the total number of contention slots M the probability that a user is resolved after m slots is p(m) 23 / 32
average delay example slot access probability optimized for throughput maximization asymptotic analysis p(M) T M/N D(M)/N 0.928031 0.928193 0.874474 1.06145 observations average delay shifted towards the end of the contention period most of the users get resolved close to the end typical for the iterative belief-propagation NB: we have not optimized the protocol for delay minimization 24 / 32
noise induced errors plug in the noise the link of each individual user has a different SNR Yj= hiXij+Zj received signal in a slot example Yj=10X1j+X2 j+Zj if user 2 is resolved elsewhere and cancelled by SIC, the probability that slot j is useful is high situation opposite when user 1 removed by SIC, slot j less likely useful 25 / 32
capture effect (1) gives rise to intra-slot SIC in addition to inter-slot SIC typical model for the decoding process capture threshold received power of user i noise power Received power of interfering users 26 / 32
capture effect (2) the capture effect boost the SIC unresolved user resolved user with capture effect no capture effect capture can occur anew after every removal of a colliding transmission from the slot asymptotic analysis significantly complicated 27 / 32
capture effect: example narrowband system, valid for M2M: Rayleigh fading pdf of SNR for user i at the receiver long-term power control and the same expected SNR for every user 28 / 32
asymptotic analysis (1) 29 / 32
asymptotic analysis (2) high SNR => low b/SNR throughput is well over 1! throughput decreases as the capture threshold b increases low SNR => high b/SNR the achievable throughputs drop noise impact significant target slot degrees are higher compared the case without capture effect the capture effect favors more collisions 30 / 32
non-asymptotic results confirm the conclusions of the asymptotic analysis 31 / 32
summary high interest for massive access in the upcoming wireless M2M communication coded random access addresses the fundamental obstacle of collisions in ALOHA frameless ALOHA inspired by rateless codes, inter-slot SIC nontrivial interaction with capture and intra-slot SIC main future steps finite blocklength reengineer and existing ALOHA protocol into coded random access 32 / 32
