On Random Access Control for Multipacket Reception S-ALOHA in Wireless Cellular Networks by Jun-Bae Seo B.Sc., Korea University, 2001 M.Sc., Korea University, 2003 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) June 2012 c Jun-Bae Seo, 2012 Abstract Studies on slotted ALOHA (S-ALOHA) systems have a long research history and been quite mature in the literature. However, this thesis revisits S-ALOHA systems by considering multipacket reception (MPR) channels, because previous studies are no longer applicable to MPR capable S-ALOHA systems due to the new random access channels (RACHs) of contemporary wireless cellular network standards. Particularly, it is dubious to apply the contention resolution algorithms (CRAs) developed so far for S-ALOHA systems to MPR S-ALOHA systems without any modification. Accordingly, this thesis proposes cross-layer CRAs and investigates the performance of some existing CRAs in MPR S-ALOHA systems in order to maximize the system throughput in tandem with stabilizing the system. Cross-layer CRAs proposed are based on estimating the system backlog information, which is obtained from multiple access interference (MAI) in the physical layer of Code Division Multiple Access (CDMA) MPR channel. Then, the proposed algorithms broadcast a retransmission probability in order to maximize the system throughput. The performance and the stability of the proposed algorithms are examined under various radio channel conditions. Compared to the proposed algorithms based on the system backlog information, the existing uniform backoff (UB) and exponential backoff (EB) algorithms are blind to such information. In order to understand the behaviour of these algorithms in MPR S-ALOHA, they are investigated with respect to various performance metrics and stability conditions. Additionally, the power ramping (PR) scheme is examined together with UB algorithm, ii Abstract in order to see whether it shows power capture effect in MPR S-ALOHA systems during a random access. Furthermore, the queueing performance of the MPR S-ALOHA system is investigated with an uplink traffic of the Markov Modulated Bernoulli Process (MMBP), when UB algorithm with retry limit is employed. It is also examined whether MPR S-ALOHA would be feasible for reserving a channel for a delay sensitive traffic. As a practical example, Semi-Persistent Scheduling (SPS) with initial random access in Long Term Evolution (LTE) is examined over MPR S-ALOHA, in which a traffic channel reservation for Voice-over IP (VoIP) is made at the onset of the ON period by a random access. iii Preface This thesis consists of both submitted and published works. I am the first author and principal contributor of all manuscript chapters. All chapters are co-authored with Dr. Victor C. M. Leung, who supervises the present thesis research. Journal Papers Accepted/Published • Jun-Bae Seo and Victor C. M. Leung, “Design and Analysis of Cross-Layer Contention Resolution Algorithms for Multi-Packet Reception Slotted ALOHA Systems,” IEEE Transactions on Wireless Communications, 10(3): 825–833, March 2011: This paper can be found in chapter 2. • Jun-Bae Seo and Victor C. M. Leung, “Design and Analysis of Backoff Algorithms for Random Access Channel in UMTS-LTE and IEEE 802.16 System,” IEEE Transactions on Vehicular Technology, 60(8): 3975-3989, Oct. 2011: This paper can be found in chapter 3. • Jun-Bae Seo and Victor C. M. Leung, “Queuing Performance of Multichannel SALOHA Systems with Correlated Arrivals,” IEEE Transactions on Vehicular Technology, 60(9): 4574-4586, Nov. 2011: This paper can be found in chapter 5. iv Preface Journal Papers Submitted • Jun-Bae Seo and Victor C. M. Leung, “Performance Modeling and Stability of SemiPersistent Scheduling with Initial Random Access in UMTS-LTE,” under revision: This paper can be found in chapter 6. • Jun-Bae Seo and Victor C. M. Leung, “On Power Ramping Scheme with Uniform Backoff Algorithm in LTE,” submitted to IEEE/ACM Transactions on Networking: This paper can be found in chapter 4. Conference Papers Published • Jun-Bae Seo and Victor C. M. Leung, “Effect of Retransmission Cutoff in S-ALOHA systems with Binary Exponential Backoff,” in Proceedings of IEEE Personal, Indoor and Mobile Radio Communications (PIMRC), pp. 1452-1456, Istanbul, Turkey, 2010. • Jun-Bae Seo and Victor C. M. Leung, “Analysis of an Exponential Backoff Algorithm in Multipacket Reception S-ALOHA system,” in Proceedings of IEEE International Conference on Communications (ICC), pp. 1-5, Cape Town, South Africa, 2010. • Jun-Bae Seo and Victor C. M. Leung, “A Distributed Contention Resolution Algorithm in Multi-Packet Reception ALOHA Systems,” in Proceedings of IEEE Global Communications Conference (Globecom), pp. 1-5, Honolulu, HI, US, 2009. • Jun-Bae Seo and Victor C. M. Leung, “Design and Analysis of Cross-Layer Contention Resolution Algorithms for Multi-Packet Reception Slotted ALOHA Systems,” in Proceedings of IEEE 18th International Conference on Computer Communications and Networks (ICCCN), pp. 1-6, San Francisco, CA, 2009. • Jun-Bae Seo and Victor C. M. Leung, “Design and Analysis of a Splitting Algorithm for a Multi-packet Reception S-ALOHA System,” in Proceedings of IEEE Wireless v Preface Communications & Networking conference (WCNC), pp. 1944-1949, Budapest, Hungary, 2009. • Jun-Bae Seo and Victor C. M. Leung, “Approximate Queueing Performance of a Multipacket Reception Slotted ALOHA System with an Exponential Backoff Algorithm,” in Proceedings of Communications and Networking in China (Chinacom’09), pp. 1-5, Xi’an, China, 2009. vi Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 MPR S-ALOHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Random Access in S-ALOHA Systems . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Access Control Algorithms . . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Stability of S-ALOHA . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.3 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Thesis Organization 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Table of Contents 2 Cross Layer Contention Resolution Algorithms . . . . . . . . . . . . . . 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1 System Model 2.2 Algorithm Design 2.3 Algorithm Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.1 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.2 System Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Numerical Results and Discussions . . . . . . . . . . . . . . . . . . . . . . 29 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3 Existing Backoff Algorithms for Single-Buffered Terminals . . . . . . . 36 3.1 3.2 Backoff Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.1.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.1.2 Uniform Backoff Algorithm in LTE . . . . . . . . . . . . . . . . . . 39 3.1.3 Binary Exponential Backoff Algorithm in IEEE 802.16 . . . . . . . 40 3.1.4 Access Prioritization by Persistence Value . . . . . . . . . . . . . . 41 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.2.1 Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2.2 Approximation on Correlated Backoff Processes . . . . . . . . . . . 44 3.2.3 Uniform Backoff Algorithm . . . . . . . . . . . . . . . . . . . . . . 44 3.2.4 Binary Exponential Backoff Algorithm . . . . . . . . . . . . . . . . 49 3.2.5 Stability 52 3.2.6 Access Prioritization Scheme 3.2.7 Dynamic Window Assignment Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 . . . . . . . . . . . . . . 58 3.3 Numerical Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 viii Table of Contents 4 Backoff Algorithm with Power Ramping in LTE . . . . . . . . . . . . . . 70 4.1 System Model : Retransmission Backoff with Power Ramping . . . . . . . 73 4.2 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.2.1 Performance Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.2.2 Correlation Coefficient on Backoff Process . . . . . . . . . . . . . . 79 4.2.3 Terminal-Assisted UB Algorithm (TAUBA) . . . . . . . . . . . . . 80 4.3 Numerical Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5 Queueing Performance of Multichannel ALOHA Systems . . . . . . . . 89 5.1 5.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.1.1 Uplink Traffic Source Model . . . . . . . . . . . . . . . . . . . . . . 93 5.1.2 Access Protocol and Backoff Algorithm . . . . . . . . . . . . . . . 96 . . . . . . . . . . . . . . . . . . . . . . 97 5.2.1 Approximation on Correlated Multi-queue . . . . . . . . . . . . . . 97 5.2.2 Multi-buffered Terminals . . . . . . . . . . . . . . . . . . . . . . . 98 5.2.3 Single-buffered Terminals . . . . . . . . . . . . . . . . . . . . . . . 107 Queueing Performance Evaluation 5.3 Numerical Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6 Semi-Persistent Scheduling in LTE . . . . . . . . . . . . . . . . . . . . . . 118 6.1 6.2 Models and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.1.1 Random Access for SPS Algorithm . . . . . . . . . . . . . . . . . . 123 6.1.2 Uplink Traffic Model . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6.1.3 Semi-Persistent Scheduling in LTE . . . . . . . . . . . . . . . . . . 127 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.2.1 Equilibrium Point Analysis . . . . . . . . . . . . . . . . . . . . . . 130 ix Table of Contents 6.2.2 Packet Dropping Probability . . . . . . . . . . . . . . . . . . . . . 137 6.3 Numerical Results and Discussions . . . . . . . . . . . . . . . . . . . . . . 140 6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 7 Conclusions and Future Work 7.1 Research Contributions 7.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 148 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 . . . . . . . . . . . . . . . . . . . . . . . . . 152 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 x List of Tables 3.1 Nomenclature for analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2 Nomenclature for DWA algorithm . . . . . . . . . . . . . . . . . . . . . . . 56 4.1 Throughput gain τp with β . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.1 Performance metrics with various backoff window sizes. 6.1 Symbols used in SPS algorithm with initial random access . . . . . . . . . 127 6.2 Stabilized system performance with various parameters . . . . . . . . . . . 142 . . . . . . . . . . 116 xi List of Figures 1.1 Instability of S-ALOHA with Bernoulli arrival. . . . . . . . . . . . . . . . . 6 1.2 Instability of S-ALOHA with Poisson arrival. . . . . . . . . . . . . . . . . . 7 1.3 Stability region of S-ALOHA with multi-buffered terminals. . . . . . . . . 11 1.4 Organization of this thesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 System performance under perfect power control . . . . . . . . . . . . . . . 29 2.2 System throughput under perfect power control. . . . . . . . . . . . . . . . 30 2.3 System stability by negative drift. . . . . . . . . . . . . . . . . . . . . . . . 31 2.4 Comparison of uncoded and BCH-coded system under imperfect power control 33 2.5 2 Performance of BCH-coded system under imperfect power control, σX = 1.5 dB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1 UB algorithm with different M and P . . . . . . . . . . . . . . . . . . . . . 57 3.2 Comparison of UB and BEB algorithms with different U and L. . . . . . . 59 3.3 Performance of BEB algorithm with different K, L and M. . . . . . . . . . 62 3.4 Access prioritization scheme of UB algorithm with differential p and U. . . 63 3.5 Access prioritization scheme of UB algorithm with differential p. . . . . . . 65 3.6 Access prioritization scheme of BEB algorithm with differential p and K. . 67 3.7 Performance comparison of UB algorithm with/without DWA algorithm. . 69 4.1 The effect of power ramping and U on the system performance. . . . . . . 82 xii List of Figures 4.2 The effect of the initial transmission power selection on the system performance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3 The correlation coefficient of M terminals’ backoff process. . . . . . . . . . 85 4.4 Performance of TAUBA against some static UB algorithms. . . . . . . . . 86 5.1 An uplink traffic model of Web-browsing. . . . . . . . . . . . . . . . . . . . 91 5.2 Effect of multichannel on multi-buffered system, p00 = 0.85, p11 = 0.65, U = 25, J = 3, K = 10. 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Performance comparisons of multi-buffered systems with various source correlation, p11 = 0.6, U = 20, K = 10. . . . . . . . . . . . . . . . . . . . . . . 108 5.4 Performance comparisons of single- (bufferless) and multi-buffered systems, p00 = 0.75, p11 = 0.6, U = 20, J = 6, K = 1. . . . . . . . . . . . . . . . . . 111 5.5 Performance comparisons of multi-buffered systems with different retry limit L, p00 = 0.85, p11 = 0.65, U = 20, K = 10. . . . . . . . . . . . . . . . . . . 113 5.6 Performance comparisons of multi-buffered systems with different window size U, p00 = 0.85, p11 = 0.65, L = 2, K = 10. . . . . . . . . . . . . . . . . . 115 6.1 Signal flow of SPS with SRI or with random access. . . . . . . . . . . . . . 119 6.2 State transition diagram of terminals with SPS algorithm with random access.129 6.3 Bistability of the system: Equilibrium function F (c0 ) and the state probability for c0 , πc0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.4 Comparison of PRMA and SPS with random access . . . . . . . . . . . . . 143 6.5 The effect of K on the system performance. . . . . . . . . . . . . . . . . . 145 6.6 The effect of U on the system performance . . . . . . . . . . . . . . . . . . 146 xiii List of Abbreviations ACK Acknowledgement AMR Adaptive Multi-rate BCH Bose and Ray-Chaudhuri BEB Binary Exponential Backoff BS Base Station CDMA Code Division Multiple Access CRA Contention Resolution Algorithm CSMA/CA Carrier Sense Multiple Access - Collision Avoidance DFT Delayed First Transmission DWA Dynamic Window Assignment eNodeB evolved NodeB EPA Equilibrium Point Analysis H-ARQ Hybrid Automatic Repeat Request HTTP Hyper-Text Transfer Protocol IFT Immediate First Transmission i.i.d. (statistically) independent, identically distributed FDD Frequency Division Duplexing LTE Long Term Evolution MAC Medium Access Control xiv List of Abbreviations MAI Multiple Access Interference MCS Modulation and Coding Scheme MIMO Multi-input Multi-output MMBP Markov Modulated Bernoulli Process MMPP Markov Modulated Poisson Process MPR Multi-packet Reception OFDMA Orthogonal Frequency Division Multiple Access PMF Probability Mass Function PN Pseudo-Noise POMDP Partially Observable Markov Decision Process PR Power Ramping PRACH Physical Random Access Channel PUSCH Physical Uplink Shared Channel PUCCH Physical Uplink Common Control Channel QoS Quality of Service RACH Random Access Channel RAP Random Access Preamble RAR Random Access Response SDMA Space Division Multiple Access SINR Signal-to-Interference plus Noise Ratio SPS Semi-Persistent Scheduling SR Scheduling Request SRI Scheduling Request Indicator TAUBA Terminal-Assisted Uniform Backoff Algorithm TCP Transmission Control Protocol xv List of Abbreviations TDD Time Division Duplexing UB Uniform Backoff UMTS Universial Mobile Telecommunication Systems UTRA UMTS Terrestrial Radio Access VoIP Voice-over IP WiMAX Worldwide Interoperability for Microwave Access WLAN Wireless Local Area Network xvi Acknowledgments First and foremost, I would like to thank my advisor, Professor Victor Leung, for his invaluable advice, warm encouragement and guidance, and enormous patience. He has improved the quality of my research and presentation by his constructive comments from the early stages of my research until the very end. I would like to thank Professor Vincent Wong for his advice and also the members of my doctoral committee, Dr. Lutz Lampe, Dr. Vikram Krishnamurthy, Dr. Sathish Gopalakrishnan, Dr. Norman Hutchinson, Dr. Jane Wang, Dr. Julian Cheng and Dr. Xianbin Wang for their advice and time. I would like to thank my undergraduate advisor Professor Hyong-Woo Lee for his guidance to graduate studies. I also want to thank my fellow labmates and friends at the Communications lab, the Department of Electrical and Computer Engineering at the University of British Columbia who helped me along the way, especially Mr. Haoming Li, Mr. Seyedali Hosseininezhad, Dr. Vahid Shah-Mansouri, Dr. Hu Jin, Dr. Jun-Su Kim and Dr. Seok Woo. Further, I would like to thank Dr. Ki-Dong Lee at LGE for his advice. I thank my friends at the University of British Columbia, Mr. Mohit Law, Mr. Dan-Sik Yoo, Mr. Tae-Sik Chae, Mr. Sang-Hoon Yeo, and Mrs. Jacqueline Stewart. Most importantly, I would like to thank my parents for their love and support. I thank God for providing me with everything along this way. This work was supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada and the University of British Columbia Graduate Fellowship. xvii Dedication With love, to my parents. xviii Chapter 1 Introduction In the past few years, wireless cellular network standards have evolved into the Third Generation Partnership Project (3GPP) Long-Term Evolution (LTE) and IEEE 802.16 Worldwide Interoperability for Microwave Access (WiMAX) systems. This is done by replacing code division multiple access (CDMA) with orthogonal frequency division multiple access (OFDMA). Furthermore, both systems have integrated various technologies into the physical layer of such OFDMA systems, such as adaptive modulation and coding scheme (MCS), and multi-input/multi-output (MIMO) antennas. These technological paradigm shifts not only increase wireless capacity, but also enable multipacket reception (MPR) capable random access channels (RACHs). Thus, it comes under question whether previous work on a single channel slotted ALOHA (S-ALOHA) is still valid for MPR capable S-ALOHA (simply MPR S-ALOHA). While the stability region of MPR S-ALOHA systems has been discussed in [1][2], the question still remains open how we can achieve the maximum stable throughput over an MPR S-ALOHA channel by providing system stability, or how efficiently some existing contention resolution algorithms (CRAs) used in a single channel S-ALOHA can work in MPR S-ALOHA. Thus, this thesis examines MPR S-ALOHA systems by investigating the following research questions in each chapter. 1. Given an MPR S-ALOHA system, can we construct a CRA with objectives of maximizing throughput (approaching optimal) in tandem with stabilizing the system? (Chapter 2) 1 Chapter 1. Introduction 2. In contrast to some CRAs proposed in the literature, window-based uniform backoff (UB) or binary exponential backoff (BEB) algorithms have been employed in contemporary communication standards where an MPR S-ALOHA is embedded. Then, how well do these algorithms work compared to the optimum performance? What are the stability conditions of these existing algorithms? (Chapter 3) 3. In LTE, a power ramping (PR) scheme is incorporated into UB algorithm. In Chapters 3-5, we ignore PR scheme by assuming that it helps to adjust the transmission power as an open loop power control that does not affect the system performance. This chapter will examine how effective the PR scheme can be, by showing a throughput gain per additional transmission power consumption by the PR scheme in comparison with throughput by non-PR scheme. We also propose a terminal-assisted uniform backoff algorithm (TAUBA) which controls the window size adaptively in the presence of PR scheme. (Chapter 4) 4. Queueing performance of S-ALOHA has been studied over past decades with respect to information-theoretic and queueing-theoretic perspectives. How does a terminal’s queueing process behave in an MPR S-ALOHA system? (Chapter 5) 5. MPR S-ALOHA is used for establishing (or reserving) a traffic or control channel in LTE. It is examined whether it would be feasible to employ MPR S-ALOHA to establish a Voice-over IP (VoIP) traffic channel by means of Semi-Persistent Scheduling (SPS) in LTE without violating delay constraint of VoIP. (Chapter 6) The next subsections introduce MPR S-ALOHA and the CRAs developed for a single channel S-ALOHA systems, respectively. Survey on the CRAs for MPR S-ALOHA will be given in Chapter 2. 2 Chapter 1. Introduction 1.1 MPR S-ALOHA MPR channels have been characterized in [1] as the probability that k among n packets simultaneously transmitted are successfully received, which is denoted by Ck,n for k ≤ n and n k=0 Ck,n = 1. MPR channels can be found in the following systems such as, the conventional CDMA systems, space division multiple access (SDMA) systems [3], and systems employing successive (or parallel) interference cancellation [4], iterative decoding or Hybrid Automatic Repeat reQuest (H-ARQ) [5], wherever multiuser detection is available in a RACH. With the current standards, such as LTE and IEEE 802.16 systems, an MPR channel is found in the RACH of each system. Each base station (BS) in the systems has a finite number of orthogonal random access preambles (RAPs) like pseudo-noise (PN) codes of CDMA. When terminals perform random access based on S-ALOHA, they randomly select one of the RAPs and transmit it to one of the OFDMA channels which can also be randomly selected. Upon receiving a unique RAP, the BS allocates an uplink channel to the terminal that selected it. Here, the RACH acts as a CDMA-OFDMA channel. Furthermore, if multiple terminals choose the same RAP, for the terminals that are successfully detected, the same uplink channel is allocated. This is called a code-collision in this thesis. However, LTE allows those terminals to transmit their messages (called Msg3 [6]) on the same uplink channel, by expecting that the collision of these messages would be resolved by H-ARQ. In LTE, random access is said to be successfully completed when terminals receive a contention resolution message after successfully transmitting Msg3. Therefore, another MPR channel is found in LTE, in which collisions are resolved by H-ARQ. 3 Chapter 1. Introduction 1.2 1.2.1 Random Access in S-ALOHA Systems Access Control Algorithms This section briefly introduces some well-known CRAs (i.e., access control algorithm, or backoff algorithm) for S-ALOHA system in the literature. In general, CRAs can be classified by whether the algorithm utilizes the system backlog information (by estimation) or not. Many researchers have developed CRA algorithms. The most well known and highly documented are Lam and Kleinrock [7], Hajek and van Loon [8], Kelly [9], and Rivest’s Bayesian broadcasting algorithm [10]. The maximum achievable throughput of these algorithms is e−1 = 0.368. A summary on these algorithms [7]-[9] can be found in [10]. One drawback of these algorithms is that they operate in a centralized way. It is noticeable that the centralized algorithms can be regarded as a Partially Observable Markov Decision Process (POMDP), in the sense that they make a control policy over a Markovian backlog process after observing the channel outcome. As a distributed algorithm, tree algorithms have been proposed by Capentanakis [11], Tsybakov and Mikhailov [12], and Hayes [13]. These algorithms and their variants are well documented in [14][15][16]. Especially, capacity bound and maximum achievable throughput of various tree algorithms in the literature are chronologically well summarized in [16]. One drawback of these algorithms is that newly arriving packets should be aware of the end of an ongoing contention resolution interval, i.e., synchronization issue. Maximum achievable throughput of a feasible tree algorithm so far known is 0.487 in [17][18]. Finally, there are window-based UB or BEB algorithms which will be described in Chapter 3. These algorithms are most practical in the sense that they work in a distributed manner and are easy to implement for various well-known systems, such as IEEE 802.3 Ethernet, IEEE 802.11 Wireless Local Area Network (WLAN), Universal Mobile Telecommunications Sys- 4 Chapter 1. Introduction tem (UMTS), LTE, IEEE 802.16 and IEEE 802.22. The maximum achievable throughput of these window-based (stabilizing) backoff algorithms is bounded by 0.368. In the next subsection, we briefly introduce the stability of S-ALOHA systems. 1.2.2 Stability of S-ALOHA This section provides a simple introduction on the stability of S-ALOHA systems. More details are found in the references given at the end of each subsection. Single-buffered terminals indicate that terminals can store only one packet in (re)transmission, while multibuffered terminals have finite queue to store incoming packets awaiting channel access. Note that the stability of BEB algorithm has been well summarized in [19]. Stability of the System with Single-Buffered Terminals In general, for the system with single-buffered terminals, bistability is found under the finite population model, while instability may occur under an infinite population model. In what follows, we assume that a newly generated packet is immediately transmitted, while backlogged packets are transmitted with probability p. Finite Population (Bernoulli Arrival): We illustrate the bistability of S-ALOHA systems with Bernoulli arrivals of newly generated packets [7][20]. Consider an S-ALOHA system, in which M terminals generate a packet with probability σ and transmit it with probability one in a slot. If the newly generated packet transmission is not successful, then (backlogged) terminals retransmit the packet with probability p. Then, the throughput of this system given n backlogged terminals is expressed by So (n) = (M − n)σ(1 − σ)M −1 (1 − p)n + (1 − σ)M −n np(1 − p)n−1 , (1.1) 5 Chapter 1. Introduction 0.4 0.35 So (n) 0.3 0.25 Si (n) Locally stable Equilibrium Point 0.2 Unstable Equilibrium Point 0.15 0.1 0.05 0 0 20 40 60 80 100 Backlogged terminals, n Figure 1.1: Instability of S-ALOHA with Bernoulli arrival. in which the first term shows the event that only one newly generated packet is transmitted, while n backlogged terminals do not retransmit their packet, and vice versa in the second term. The input rate of newly generated packets to this system given n backlogged terminal can be expressed as Si (n) = (M − n)σ. (1.2) Define an equilibrium point of this system as a point n∗ which satisfies Si (n∗ ) = So (n∗ ). (1.3) Fig. 1.1 illustrates Si (n) and So (n) of the system with σ = 0.003, p = 0.06, and M = 100, in which three points of n∗ are found. The system showing this behaviour is often called bistable, in which the throughput-delay performance at locally stable equilibrium point can be achieved only for some finite time period. If the system has a unique n∗ , it is called a stable system. Given M and σ, it is interesting to drive this system to have only one 6 Chapter 1. Introduction equilibrium point by controlling p. Infinite Population (Poisson Arrival): Now suppose an S-ALOHA system in which new packet arrival rate follows a Poisson distribution with rate λ. Let πn denote the stationary probability that the S-ALOHA system has n backlogged terminals. As before, newly generated packets will be transmitted with probability one. Thus, when at least two packets are transmitted, a collision occurs. Then πn satisfies the following balance equation: 1 n πn =πn (1 − p) a0 + πn 1− n j p (1 − p)n−k k k=0 a0 + πn (1 − p)n a0 (1.4) n n + πn+1 p(1 − p) a0 + πn−1 1 − (1 − p) n−1 a1 + πn−k ak , k=2 in which we have ak = λk exp−λ /k! and πn = 0 for n < 0. Finally, the normalization condition ∞ n=0 πn = 1 holds. As shown in [14][21], the ratio, πn+1 /πn , in (1.4) grows without bound as n → ∞. This implies that S-ALOHA system with infinite population model is always unstable. This can be qualitatively explained as follows [14][15]. Denote 0.4 0.35 Throughput 0.3 0.25 0.2 0.15 λ 0.1 0.05 0 −3 10 G1 −2 10 −1 10 G2 0 10 1 10 2 10 Offered Load (G) Figure 1.2: Instability of S-ALOHA with Poisson arrival. by G the expected number of new (λ) and retransmitted packets (per second). Then, the 7 Chapter 1. Introduction throughput of this S-ALOHA system is predicted by So = Ge−G . As we have seen in Fig. 1.1, we also depict So and Si = λ in Fig. 1.2. By small perturbation on the actual traffic rate around G1 , the system throughput moves around λ = G1 e−G1 . If a large perturbation causes the actual traffic to exceed G2 (which will occur with probability one), then So decreases below λ. Once it happens, the system never returns to the point (λ, G1 ), which means instability. Pakes’ Lemma (Foster’s theorem) We have seen previously bistability and instability of S-ALOHA system with finite and infinite population model, respectively. We now connect the previous two examples into Foster’s theorem (extended by Pakes’ lemma [22]) for an ergodic Markov chain [22][23]. If the following two conditions hold, it is sufficient for an irreducible, aperiodic homogenous Markov chain (whose state space is the set of nonnegative integers) to be ergodic: 1. |E[Bt+1 − Bt |Bt = m]| < ∞ for ∀m, 2. lim sup E[Bt+1 − Bt |Bt = m] < 0, m→∞ (1.5) in which Bt denotes the number of backlogged terminals at time t in S-ALOHA systems. We denote the second condition by d(m). In order for an S-ALOHA system with finite population model not to have bistability, there exists only one m∗ , which shows d(m) < 0 for m∗ < m ≤ M. If this would be found for a stable system with infinite population model, i.e., M → ∞, then the system backlog is bounded. More specifically, we can write 8 Chapter 1. Introduction for infinite population model (given Bt = m) Bt+1 m−1 m = m+1 m+k with probability mp(1 − p)m−1 a0 with probability (1 − p)m a1 + (1 − p(1 − p)m−1 )a0 with probability (1 − (1 − p)m )a1 with probability ak for k ≥ 2. According to (1.5), we have E[Bt+1 − Bt |Bt = m] = E[Bt+1 |Bt = m] − E[Bt |Bt = m] = (m − 1)mp(1 − p)m−1 a0 + m(1 − p)m a1 + (1 − p(1 − p)m−1 )a0 ∞ m + (m + 1)(1 − (1 − p) )a1 + k=2 (m + k)ak − m =λ − mp(1 − p)m−1 a0 − (1 − p)m a1 . Then, we should have m∗ for λ < m∗ p(1 − p)m ∗ −1 a0 + (1 − p)m a1 in order to stabilize the ∗ system. Stability of the System with Multi-Buffered Terminals In contrast with S-ALOHA systems with single-buffered terminals, we assume M terminals, each of which has a buffer of infinite size [2][24]. Denote by Qti the queue length process of the i-th terminal at time t. Then, a multidimensional stochastic process Qt = [Qt1 , . . . , QtM ] is defined as stable [24], if we have lim Pr[Qt < x] = F (x) and t→∞ lim F (x) = 1, (1.6) x→∞ 9 Chapter 1. Introduction in which x is a vector of length M. So far, bistability in S-ALOHA system with multibuffered terminals has not been discussed in the literature. We shall discuss this later in Chapter 5. Exact queueing analysis on this multidimensional queueing process in SALOHA system1 is found only in [2][26] where two terminals are considered in S-ALOHA and MPR S-ALOHA systems, respectively. All other works on queueing study for SALOHA systems and CSMA systems including WLAN in the literature are an approximation on this queueing process. In addition, it has been shown that this queueing process, Qt , is positively correlated [27]. This implies that terminals’ queue length could keep increasing, once they are congested, or vice versa. In order to achieve (1.6), each terminal’s queueing process in an S-ALOHA system should satisfy Loynes’ theorem [28], which means that the packet arrival rate to each terminal should be less than each terminal’s throughput, i.e., service rate. In [29] Rao and Ephremeides consider the maximum acceptable packet arrival rate in S-ALOHA systems, which maintains the stability, by introducing a dominant system where terminals with empty queue keep transmitting a dummy packet in order to interfere with other terminals with non-empty queue. As a result, if M terminals have identical new packet arrival rate (Poisson arrival with mean rate λ) and retransmission probability (p), it is shown that the maximum achievable throughput of this S-ALOHA system can be expressed as λ < p(1 − p)M −1 . As an example, we illustrate this in Fig. 1.3 for M = 20 and λ = 0.012. Note that this system can be stabilized for p1 < p < p2 . More details are found in [2][29]. Stability in MPR S-ALOHA Systems in This Thesis Throughout this thesis we assume that new packets are generated based on Bernoulli trials in the system with single-buffered and multi-buffered terminals under a finite population 1 For CSMA with collision detection, one can find queueing analysis in [20][25]. However, no queueing analysis is found for carrier-sense multiple access (CSMA) even with two terminals. 10 Chapter 1. Introduction 0.02 0.018 0.016 0.014 Throughput 0.012 λ 0.01 0.008 0.006 0.004 0.002 0 −3 10 p1 −2 10 p2 p −1 10 0 10 Figure 1.3: Stability region of S-ALOHA with multi-buffered terminals. model. Thus, the stability condition in an MPR S-ALOHA system with single-buffered terminals in Chapters 2, 3, and 4 is considered as a single equilibrium point, as we have introduced. In Chapter 5, we consider a multi-channel S-ALOHA system, in which M terminals have a buffer of finite size. Due to the assumption on finite queue length, (1.6) always holds. Furthermore, we consider retry limit, i.e., limiting the number of retransmissions of a packet in MPR S-ALOHA systems as in the standards such as LTE [6], WiMAX [30], UMTS [31], and WLAN [32]. Since packets are dropped due to such a retry limit, the maximum stable throughput of our interest can be defined as the maximum number of acceptable terminals in conjunction with mean packet arrival rate, while a predefined packet dropping probability is not violated. In addition, for the positive correlation of terminals’ backoff processes or terminals’ queueing processes, our theoretical evaluations on MPR S-ALOHA systems in Chapters 3-5 are based on statistically independent, identically distributed (i.i.d.) assumption on terminals’ backoff processes or queueing processes. We shall introduce the details on this approximation in Section 3.2.2, Section 4.2.2, and Section 5.2.1. 11 Chapter 1. Introduction 1.2.3 Fairness Fairness provision in random access control algorithms has been discussed mostly in mobile ad-hoc networks [33][34][35] with respect to proportional fairness of transmission rate based on utility optimization. In this thesis the fairness of an access algorithm is evaluated by the inverse of the variance of access delay. Suppose an access control algorithm, with which terminals experience finite mean and zero variance of access delay. Then, terminals using such an access algorithm experience constant access delay, once a packet is generated. Accordingly, in Chapter 3 we shall examine how UB and BEB algorithms behave in the second-order moment of access delay. 1.3 Contributions This thesis proposes novel CRAs and investigates the performance of some existing CRAs in MPR capable ALOHA. The contributions of each chapter is summarized as follows. 1. Chapter 2 considers novel centralized CRAs in CDMA MPR channels. The system employs a BS that constructs system backlog information from multiple access interference (MAI). Then, the BS broadcasts the retransmission probability for each slot to all mobile terminals within its coverage in order to maximize the expectation of the system throughput conditioned on the number of retransmitting terminals. Under perfect/imperfect power control, the performance of our algorithms and the system stability are evaluated by theoretical analysis and compared to simulations. 2. In contrast with various CRAs [7][8][10][36] proposed in the literature which are based on system backlog estimation, recent standards such as LTE and IEEE 802.16 systems have already adopted window-based backoff algorithms, UB and BEB algorithms with retry limit, respectively as CRA. Compared to the algorithms proposed 12 Chapter 1. Introduction in Chapter 2, UB and BEB algorithms do not take the backlog size into account. Thus, Chapter 3 examines how well these algorithms work in CDMA-OFDMA channels and what stability conditions these algorithms have. In addition, the access prioritization schemes are considered to provide different access classes differential performance. To this end, the system allows different access classes to use UB or BEB algorithm with different parameters. In order to optimize UB algorithm, this chapter considers a dynamic window assignment algorithm that is based on Bayesian broadcasting, in which the base station adaptively controls the window size of the UB algorithm for unsaturated traffic condition. 3. In Chapter 3, we ignore the impact of the PR scheme on the system throughput, by assuming that it works as an open loop power control in UMTS and LTE. Since it has been known that higher throughput can be achieved by power capture, Chapter 4 examines whether the PR scheme in LTE affects the system performance in conjunction with UB algorithm. This is done by constructing a metric called throughput gain per average transmission power additionally consumed by the PR scheme. 4. Chapter 5 considers the queueing performance of multichannel S-ALOHA, i.e. CDMAOFDMA channels, with UB algorithm. This work is an extension of a classical problem of queueing study on S-ALOHA system, which has a long research history. In contrast with previous work that considers only the independent arrival process, this study assumes a Markov modulated Bernoulli process (MMBP) as correlated arrivals over an uplink traffic. Our analysis and simulations show the system performance in relation to the source correlation, number of channels, window size and retry limit. The results from our study allow the parameters of UB algorithm to be properly chosen to meet the access-level quality of service requirements. 13 Chapter 1. Introduction !1'A.)"*B* !1'A.)"*C* !1'A.)"*F* !"#$$%&'()"*+,,)$$* !#-."#&*+&/#"0.12* 345464*'&/#"0.12* 7#"*$0-/&)*89:)");* .)"20-'&$* =)20%>)"$0$.)-.* =,1);9&0-/*?0.1* "'-;#2*',,)$$* !)-."'&0G);*+&/#"0.12$* H0$."089.);*+&/#"0.12$* I*@)$)"K'<#-*>"#.#,#&* I*>#?)"*@'2A0-/* I*0-,")'$)*J9)9)*&)-/.1* !1'A.)"*D* !1'A.)"*E* >#?)"*@'2A0-/* ?0.1*34*7#"*$0-/&)* 89:)");*.)"20-'&$* 34*'&/#"0.12* 7#"*29&<%89:)");* .)"20-'&$* Figure 1.4: Organization of this thesis. 5. In SPS of LTE [6], a terminal obtains a traffic channel at the beginning of the ON state of VoIP traffic by either random access or a dedicated control channel. Once a traffic channel is reserved, a terminal can transmit its VoIP packet periodically in the reserved traffic channel without additional control signalling during an entire ON period. Chapter 6 examines the feasibility of S-ALOHA in SPS of LTE as a way of establishing a traffic channel for VoIP. Since large random access delay in establishing a traffic channel may deteriorate the quality of VoIP traffic, we examine the maximum number of acceptable VoIP terminals without exceeding some delay constraint. 1.4 Thesis Organization As shown in Fig. 1.4, the rest of this thesis is organized as follows. Chapter 2 proposes novel centralized cross-layer CRAs in CDMA MPR channel and examine their performance and stability, under perfect/imperfect radio channel conditions. Chapter 3 examines the performance of the existing decentralized backoff algorithms such as UB and BEB algorithms, 14 Chapter 1. Introduction used in LTE and IEEE 802.16 systems, which can be compared to the CRAs proposed in Chapter 2. Furthermore, an optimal window size of UB algorithm based on backlog estimation is considered. In Chapter 4, we investigate the effectiveness of the PR scheme with UB algorithm. Chapter 5 considers the queueing performance of multi-buffered terminals in multichannel S-ALOHA with UB algorithm, which can be found in LTE random access channel. In particular, a correlated arrival over uplink by MMBP is assumed. Chapter 6 examines the performance of SPS in LTE, i.e., a reservation random access protocol, in which reservations requested by MPR S-ALOHA. In Chapters 3-6, the system model and its random access protocol are mostly based on LTE. The random access protocol of LTE is introduced in detail in Chapters 3 and 6. In addition, throughout Chapters 3-6 we only consider an ideal wireless channel, i.e., no bit error, while we take into account that power control errors and MAI are dominant in the wireless channel in Chapter 2. Chapter 7 summarizes the overall results and suggests some directions for future research. 15 Chapter 2 Cross Layer Contention Resolution Algorithms There exist extensive information theoretic studies on MPR S-ALOHA systems ([2] and references therein), e.g., in terms of maximum achievable stable throughput and capacity regions provided that the limiting queue distribution exists for each terminal. However, CRAs for MPR channels are less studied. Ghez et al. [36] examined a decentralized stable CRA, in which terminals estimate the current backlog size based on the binary channel feedback, i.e., empty or non-empty slot. However, estimation on new packet arrivals is not incorporated. In [4], Yu and Giannakis proposed a tree algorithm with successive interference cancellation. Although it achieves a 69% throughput efficiency without estimating backlog size, all collided packets need to be stored for successive interference cancellation. Sakakibara et al. [37] examined the bistability of ALOHA systems with various capture and MPR channels, but they did not consider how to control the retransmissions in order to avoid the bistability. Ngo and Krishnamurthy [38] investigated MPR S-ALOHA system in a non-cooperative game-theoretic perspective, in which terminals retransmit only when their channel states are above a certain threshold. In such a game-theoretic formulation, it should be assumed that each player, i.e., terminal has a priori knowledge of the number of players, which may not be practical in many wireless networks. In contrast to [4][36][37][38], we propose centralized cross-layer CRAs for immediate first transmission (IFT) and deferred first transmission (DFT) protocols in an MPR channel 16 Chapter 2. Cross Layer Contention Resolution Algorithms realized in a CDMA S-ALOHA system. Compared to the previous work reviewed above, a distinctive feature of our algorithms is the use of cross-layer information to estimate the system backlog size. More specifically, the BS measures the power of MAI in the physical layer, and estimates the backlog size and new packet arrivals in the medium access control (MAC) layer based on the measurements. The backlog estimation algorithms for S-ALOHA systems with and without MPR channels ([36] and reference therein) so far are mostly event-based distributed algorithms, in which terminals update backlog size, according to the events, e.g., the transmission success, failure or emptiness at each slot. To this end, terminals accessing an MPR channel should be aware of the channel state, so that they could update the current backlog size according to various events, e.g., the number of packets successfully transmitted with and without other interfering packets. However, our proposed algorithms relieve terminals’ processing burden and, as we shall see, they are not confined to conventional CDMA systems, but would be applicable to systems like [6][30] which use random access codes for terminal identification in random access control channels. Also, in [4][36], all terminals with or without a packet should monitor the feedback channel in order to keep track of the backlog size. In contrast, in the proposed algorithms terminals only need to monitor the feedback channel when they have packets to send. To demonstrate the robustness of the backlog size estimation, we further consider systems with imperfect power control. Based on such estimations, BS determines the retransmission probability to maximize the system throughput for every slot and broadcasts this information to the terminals. The performance and stability of the proposed algorithms are analyzed and compared to simulations. The organization of this chapter is as follows. Sections 2.1 and 2.2 introduce the system model and proposed algorithms, respectively. System performance and stability are analyzed in Section 2.3. Numerical results are presented in Section 2.4. Concluding 17 Chapter 2. Cross Layer Contention Resolution Algorithms remarks are given in Section 2.5. 2.1 System Model For this investigation we consider an MPR channel derived from a cellular CDMA system with a finite number of terminals in each cell. Time is divided into slots of a fixed length that is equal to one packet transmission time, and terminals transmit to the BS using SALOHA access over the uplink while the BS broadcasts to all terminals over the downlink. We assume that terminals have distinct PN signatures known by the BS [39] and that the BS receiver uses a bank of correlators for multiuser detection. Further, we assume that uplink and downlink channels have approximately the same path loss because, e.g., time division duplexing (TDD) is employed, or the shadowing of both links is strongly correlated in frequency division duplexing (FDD). At the end of each slot in which some terminals have sent packets, the BS determines which PN signatures (terminals) are successfully received, and broadcasts the following information over a downlink signalling channel to all terminals: 1. The IDs of terminals that successfully transmitted in the previous slot. The IDs of PN signatures could be also transmitted, instead of terminals’ IDs. 2. The retransmission probability, rt , for the next slot t, as determined by the algorithms proposed in the next section. 3. The signal power at the BS receiver required from a terminal for successful packet reception, and the transmission power of the current broadcast message. For the sake of simplicity, we assume that this feedback is immediate after an uplink slot ends and before the next slot begins. In practice there is a non-negligible feedback delay, 18 Chapter 2. Cross Layer Contention Resolution Algorithms which can be accommodated by considering the system as a time-multiplexed parallel slotted system [30][40]. We further assume that broadcasts from BS are always received by the terminals without errors. An active terminal that does not receive its ID in the BS broadcast at the end of its transmission slot regards itself as backlogged, and it will then retransmit in the next slot t with probability rt . Furthermore, each terminal in the cell measures the received power of the broadcast message and compares it with the transmission power specified in the message to estimate the path loss between the terminal and the BS, and uses this estimate for open loop uplink access power control. We denote the received signal from k terminals at the BS at time t by ψ(t). Further, let S, aj (t) and bj (t), respectively, denote the signal power required from each terminal at the BS receiver, the PN-signature signal of a data bit from the j-th terminal and the data bit limited to [0, Tb ]. We assume that aj (t) has unit energy and is generated at the rate of N chips (spreading gain) for each data bit. The received signal corresponding to data bits from k terminals is then expressed as k ψ(t) = j=1 2γj Saj (t − τj )bj (t − τj ) cos(2πfc (t − τj ) − ϕj ) + N (t), (2.1) where fc , τj and ϕj denote the carrier frequency, time delay of the j-th terminal relative to the beginning slot boundary, and phase of the j-th terminal, respectively. We assume that the power control error of the j-th terminal is given by a lognormal random variable, γj , whose corresponding normal random variable has zero mean and standard deviation σXj (= σX ) [41]. We also assume i.i.d. power control errors over all the terminals. Finally, N (t) denotes additive white Gaussian noise with zero mean and standard deviation σg . To obtain the data bit error probability in (2.1), we consider the output of a correlation 19 Chapter 2. Cross Layer Contention Resolution Algorithms receiver matched to the i-th terminal, which can be expressed as Tb ψ(t)ai (t) cos ωc t dt Zi = 0 = S Tb 2 √ k √ γi bi + Tb γj Ij,i N (t)ai (t) cos ωc tdt + 0 j=1,j=i (2.2) where bi ∈ [−1, +1] and Ij,i is assumed to be a Gaussian random variable with zero mean and variance of 1/3N [42]. It should be noted that each individual interference component may not be Gaussian distributed, but given a sufficiently large number of interference components the sum of these components can be assumed to be Gaussian distributed. Based on (2.2), we can express the conditional bit error probability given γˆk−1 , denoted by Pb|ˆγk−1 , as Pb|ˆγk−1 = Q √ where Q(y)=(1/ 2π) ∞ y exp−x 2 /2 random variables, i.e., γˆk−1 = 3N γˆk−1 , (2.3) dx. Additionally, γˆk−1 is the sum of k−1 i.i.d. lognormal k ˜j , j=1,j=i γ in which γ˜j (= γj /γi ) is a lognormal random variable whose corresponding normal random variable has zero mean and variance of σ 2 = 2 2σX . Note that with perfect power control, γ˜j is equal to one, in which case the bit error probability is given by Q( 3N/(k − 1)) [42]. In (2.3), we assume that the white Gaussian noise component is negligible. The bit error probability given k − 1 terminals’ transmissions, Pb|k−1, can be obtained by ∞ Pb|k−1 = Pb|ˆγk−1 fk−1 (y)dy (2.4) 0 where fk−1 (y) is the probability distribution of the sum of k − 1 i.i.d. lognormal distri2 butions with zero mean and variance σ ˆk−1 . By Wilkinson’s method [45], we write fk−1 (y) 20 Chapter 2. Cross Layer Contention Resolution Algorithms approximately as fk−1 (y) = √ 1 2πyˆ σ k−1 (ln y − µ ˆk−1 )2 2 2ˆ σk−1 e − (2.5) 2 in which µ ˆ k−1 and σ ˆk−1 are respectively expressed as 1 1 2 µ ˆk−1 = ln(k − 1) + σ 2 − σ ˆ 2 2 k−1 2 σˆk−1 = ln and 1 σ2 k − 2 e + k−1 k−1 . (2.6) Assume that a packet consists of Lb bits. Then, the packet success probability for an uncoded system with k terminals transmitting is given by Ps (k) = (1−Pb|k−1 )Lb . Throughout this chapter, we use the notation of a binomial distribution as B(i, n, p) = n i pi (1 − p)n−i . Then, we obtain the packet success probability for a coded system with a v-error-correcting code as Ps (k) = 2.2 v i=0 B(i, Lb , Pb|k−1). Algorithm Design We design CRAs based on centralized estimation of the system backlog and selection of the retransmission probability, rt , at the BS for the MPR channel modelled above. We consider two possible variations of the S-ALOHA protocol. In the IFT protocol, newly generated packets are transmitted with probability one, whereas in the DFT protocol they join the backlog without immediate initial transmissions. We present two CRAs, Algorithm 2.1 and Algorithm 2.2 for the IFT and DFT pro(I) tocols, respectively. In the algorithms, rt (D) or rt denote the retransmission probabilities broadcasted at time t for IFT or DFT protocol, respectively. The number of packets successfully transmitted at time t is denoted by ξt . The estimated backlog size, estimated and predicted number of newly transmitted packets at time t are respectively denoted by βt , 21 Chapter 2. Cross Layer Contention Resolution Algorithms ˆ t . Finally, ut denotes the estimated number of packets simultaneously transmitted λt and λ at time t. For both Algorithm 2.1 and 2.2, the retransmission probability rt is determined as follows: We denote Cj,k as the probability that j packets are successfully received among a total of k packets transmitted. Assuming that successful packet reception with probability Ps (k) is independent for each terminal, we can express Cj,k for an uncoded system as Cj,k = B (j, k, Ps (k)) . (2.7) The conditional system throughput given k packets for an uncoded system is given by k Ck = jCj,k . (2.8) j=0 Let c∗ denote the number of terminals that should be transmitting simultaneously to maximize C k , which is obtained by c∗ = argk max C k . (2.9) Now, suppose that βt backlogged terminals transmit their packets based on a Bernoulli process with probability rt . The mean number of transmissions from the βt backlogged terminals is βt rt = βt i=0 iB(i, βt , rt ), which is expected to be equal to c∗ . Accordingly, rt can be obtained as rt = min (c∗ /βt , 1) , (2.10) which sets rt to one when βt is less then c∗ . For an S-ALOHA system without MPR channel, i.e., c∗ = 1, one can readily find rt = 1/βt . Additionally, C c∗ represents the 22 Chapter 2. Cross Layer Contention Resolution Algorithms Algorithm 2.1 - CRA for IFT protocol 1: 2: 3: 4: 5: 6: (I) ˆ 1 = 0 and r = 0.5. Initialization: β0 = λ 1 Do the following at t = 1, 2, 3, . . . : Compute ut based on (2.13). (I) Estimate λt = max ut − rt · βt−1 , 0 . Update βt = max (βt−1 + λt − ξt , 0). Predict new arrival by a first-order AR model : ˆ t+1 = θλ ˆ t + (1 − θ)λt . λ (I) Broadcast rt+1 : (I) ˆ t+1 )/βt , 0 , 1 . r = min max (c∗ − λ t+1 maximum throughput or capacity of the MPR channel. For a coded system, c∗ is expressed as c∗ = argk max max L(v) C k (2.11) where L(v) denotes the code rate of a v-error-correcting code. Note that both c∗ and C c∗ are 2 functions of power control error σX , which requires the BS to know c∗ under power control errors. Additionally, c∗ also depends on the MPR channel. For practical implementation, we assume that the BS can estimate power control errors from the random access channel by comparing the measured power and the required power broadcasted. Then, BS uses one of the predetermined values of c∗ s (a table) according to the estimated power control errors. In order to estimate βt in (2.10), we first estimate the number of packets simultaneously transmitted at time t (denoted by ut ) and determine βt based on the IFT and DFT protocols. To this end, the BS measures the total received energy (before decorrelation) 23 Chapter 2. Cross Layer Contention Resolution Algorithms per bit. Given k packets transmitted, we can write this as Tb k−1 k 2 γj + 2S ψ(t) dt = Tb S 0 √ k j=1 j=1 √ γj ℓ=j+1 γℓ Ij,ℓ + Ne (2.12) in which all the terms related to N (t) are collectively denoted by Ne . Taking expectation on (2.12), we have 1 E Tb Tb 0 k 2 ψ(t) dt = S · E γj , (2.13) j=1 The second term in (2.12) vanishes in (2.13) due to the Gaussian assumption made in (2.2). Dividing (2.13) by S and rounding it, we can have an estimator ut for k and apply it in Step 2 of each algorithm. As in (2.5) and (2.6), the probability distribution of k j=1 γj can also be approximated as a lognormal distribution by Wilkinson’s method. Based on (2.9) and (2.13), each step of the algorithms can be explained as follows: In order to distinguish new and retransmission packets in Step 3, the number of packet retransmissions at time t is estimated as the product of rt and the previously estimated backlog βt−1 , i.e., the expected number of packet retransmissions from the previous backlog. By subtracting this from ut , we can estimate λt , the number of new packets at time t. Note that Step 3 is identical for both the IFT and DFT protocols2 . In Steps 4-5, the BS updates the current backlog by subtracting successfully transmitted packets and adding new arrivals, and then predicts new packet arrivals. By reserving some capacity for new packets in the IFT protocol, the BS determines rt in Step 6. However, in the DFT protocol, the backlog estimation is once more smoothed out in Step 4, and we add the predicted new arrivals to this backlog in Step 6. Capacity reservation for new arrivals is not needed. Regarding the algorithms, we have the following remarks: 2 (D) In Algorithm 2.2, this can be seen when both sides are multiplied by rt in Step 3. 24 Chapter 2. Cross Layer Contention Resolution Algorithms Algorithm 2.2 - CRA for DFT protocol (D) ˆ 0 = 0 and r = 0.5. Initialization: β0 = λ 1 Do the following at t = 1, 2, 3, . . . : 2: Compute ut based on (2.13). (D) 3: Estimate λt−1 = max ut /rt − βt−1 , 0 . 1: (D) and Update βt−1 = ρβt−1 + (1 − ρ) ut /rt βt = max (βt−1 − ξt , 0). ˆ t = θλ ˆ t−1 + (1 − θ)λt−1 . 5: Predict new arrival by λ (D) (D) ˆ t ), 1 . 6: Broadcast rt+1 as rt+1 = min c∗ /(βt + λ 4: 1. For simplicity, we ignore mobility of terminals or assume that they are either static or show very slow mobility compared to the processes for packet arrivals and successful transmissions. Then, the algorithms do not depend on time, but on the numbers of previous backlog and new packets, and we can assume that βt is a stationary process. 2. For new packets, λt can in practice depend on the total number of terminals residing in a cell, their mobility, population size and traffic characteristics and the current backlog. In Step 5 of each algorithm, the parameter θ ∈ (0, 1) is a smoothing factor of a first-order AR model. In Section 2.4, we show that the desired performance can be achieved by choosing θ > 0.95. 3. By using the equations of Steps 3-4 in the IFT protocol, we can express the evolution of the backlog over time as k j=0 (I) k (I) βt+k = βt−1 1 − rt+j + k−i (I) ϑt+i i=0 j=1 1 − rt+j (I) with ϑt+i = max rt+i βt−1+i + λt+i − ξt+i , 0 . The term rt+i βt−1+i +λt+i indicates the sum of the expected number of retransmissions and new packet arrivals. Therefore, ϑt+i denotes the remaining packets due to transmission failure. The first term on 25 Chapter 2. Cross Layer Contention Resolution Algorithms the right-hand side indicates the remaining backlogged terminals which would not retransmit at each time. The second term denotes the terminals which have failed to transmit and stayed in the backlog without further retransmissions. Note that ξt+i (I) (I) is a function of rt+i βt−1+i + λt+i . The algorithm chooses rt+i in order to minimize ϑt+i . As k→∞, the evolution of the backlog over time βt+k becomes smaller when (I) (I) (I) (I) (I) rt+j ≤ rt+j+1 and ϑt+i < rt+i βt−1+i . By using Step 6, we can rewrite rt+j ≤ rt+j+1 as λt+1 − λt − (βt−1 − βt ) ≤ 0. This means that the backlog’s decreasing rate should be greater than or equal to the new packet arrival rate. This corresponds to the negative drift condition in [46], which we shall see in Section 2.3.2. We also rewrite (I) ϑt+i < rt+i βt−1+i as λt+i < ξt+i . For λt+i = ξt+i the backlog does not change at all. 4. Since new packet arrivals become backlogged immediately in the DFT protocol, Step (D) ∗ ∗ 3 is based on ut = rt (βt−1 + λ∗t−1 ) in Algorithm 2.2 where βt−1 and λ∗t−1 are true values of backlog and new packet arrivals at time t − 1. In Step 4, based on a first(D) order AR model we simply smooth out βt−1 by ρ and ut /rt which contains noisy ∗ versions of βt−1 and λ∗t−1 . In other words, the previous estimation βt−1 is adjusted (D) by noisy observation ut /rt . 5. Since terminals have spatially orthogonal signature vectors in SDMA [3], (2.12) can be still valid for backlog estimation in SDMA. 26 Chapter 2. Cross Layer Contention Resolution Algorithms 2.3 2.3.1 Algorithm Evaluation Performance Measures The retransmission probability is said to be stationary if rt depends only on the state of the backlog process. For the IFT protocol, we can write (I) lim rt t→∞ = lim min max t→∞ ˆ t+1 (ǫa ) c∗ − λ ,0 ,1 , βt (ǫb ) ˆ t+1 (ǫa ) ≈ (M − m)p + ǫa and βt (ǫb ) ≈ m + ǫb when there in which as t→∞, we have λ are in total M terminals and m backlogged terminals. The variables ǫa and ǫb indicate the estimation errors for new arrivals and backlog size, respectively. When no estimation (I) (D) errors are assumed, we can write rm and rm for m backlogged terminals as (I) rm = min c∗ − (M − m)p ,1 m and (D) rm = min c∗ ,1 . m (2.14) Let qm,n denote the one-step state transition probability of the backlogged terminals, i.e., qm,n = Pr [βt+1 = n|βt = m]. Suppose that M terminals exist in a cell and that M − m terminals (except m backlogged terminals) generate new packets every slot each with probability p. For the IFT protocol, qm,n for 0 ≤ m, n ≤ M can be expressed as M v qm,n = v=0 k=0 (I) Ck,v B(l, M − m, p)B v − l, m, rm . (2.15) For the DFT protocol, we can obtain qm,n by m v qm,n = v=0 k=0 (D) Ck,v B(l, M − m, p)B v, m, rm (2.16) 27 Chapter 2. Cross Layer Contention Resolution Algorithms where l = n − m + k. We then write the state transition matrix for the system backlog as Q = [qm,n ], where qm,n is the element at the m-th row and n-th column. Further, we denote the stationary probability row vector by π = [πm ] for 0 ≤ m ≤ M, where πm denotes the probability that m backlogged terminals are in the system. We can obtain π by π = π · Q and π · e = 1, where e denotes a unit column vector whose length corresponds to π. We denote the throughput given m backlogs in the system by Sm . We can obtain Sm for the IFT protocol by M M v Sm = n=0 v=1 k=1 (I) kCk,v B(l, M − m, p)B v − l, m, rm . For the DFT protocol, one can get M m v Sm = n=0 v=1 k=1 (D) . kCk,v B(l, M − m, p)B v, m, rm For both the IFT and DFT protocols, the overall system throughput and the backlog delay are respectively obtained by S = M m=0 πm Sm and D = N /S, where N = M m=0 mπm is the average number of backlogged terminals in the system. 2.3.2 System Stability To evaluate the stability of the algorithm, we examine the negative drift condition d(m) [46] (introduced in Section 1.2.2), which is obtained by M d(m) = E[βt+1 − βt |βt = m] = n=0 (n − m)qm,n . (2.17) Clearly, we have d(0) > 0 and d(M) < 0. The system is said to be mono-stable if there exists a single state m which makes d(m) transit from positive to negative, and from such 28 Chapter 2. Cross Layer Contention Resolution Algorithms 10 3.5 3 2.5 2 IFT (ana.) IFT (sim.) DFT (ana.) DFT (sim.) 1.5 1 0.5 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 Backlog delay (slots) Throughput (packets/slot) 4 8 IFT (ana.) IFT (sim.) DFT (ana.) DFT (sim.) 6 4 2 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 p (a) Throughput vs. p. p (b) Backlog delay vs. p under perfect power control. Figure 2.1: System performance under perfect power control a state m, d(m) would not bounce back to positive again. If there are two states to make d(m) transit from positive to negative, the system is said to be bistable, and the backlog size oscillates between these two states. 2.4 Numerical Results and Discussions We use the spreading gain N = 16 and the packet length Lb = 255 in the following examples. Unless otherwise stated, population size M = 50, ρ = 0.95 in the DFT protocol, and the smoothing factor of estimating new packet arrivals is θ = 0.95 for both the IFT and DFT protocols. In all the figures, the curves with circles and triangles indicates IFT and DFT protocols, respectively. For verification, we build a simulation program with MATLAB. With perfect power control, we assume that each packet has unit power, while the power of each packet under imperfect power control follows lognormal random variables. At initialization, we set randomly some of M terminals as backlogged. Here, we do not 29 Chapter 2. Cross Layer Contention Resolution Algorithms 4 3 2.5 IFT, θ=0.95 IFT, θ=0.75 IFT, θ=0.55 DFT, θ=0.95 DFT, θ=0.75 DFT, θ=0.55 2 1.5 1 0.02 0.04 0.06 0.08 p 0.1 0.12 0.14 0.16 (a) Throughput with different θ. Throughput (packets/slot) Throughput (packets/slot) 3.5 3.5 3 2.5 IFT (ana) IFT (sim) DFT (ana) DFT (sim), ρ=0.95 DFT (sim), ρ=0.75 DFT (sim), ρ=0.55 DFT (sim), ρ=0.35 2 1.5 1 0.5 10 20 30 40 50 60 70 80 90 Number of terminals (b) Throughput with different ρ, p = 0.075. Figure 2.2: System throughput under perfect power control. include mobility of terminals and the radio link simulation for bit error probability. Therefore, packet success is determined by (2.4) in our simulation program. In particular, we averaged simulations of 30000 slots over 5 runs in Figs. 2.3(a) and 2.3(b). In Figs. 2.1(a)2.3(b), we characterize the performance of the proposed algorithms with perfect power control by varying p, θ and ρ, while in Figs. 2.4(a)-2.5(b) we examine the performance with imperfect power control. In Figs. 2.1(a) and 2.1(b), system throughput S and backlog delay D of the uncoded system with perfect power control are respectively depicted. The two figures show good agreement between analysis and simulations for p < 0.055 and p > 0.1, which means that performance of the algorithms with perfect power control is close to the upper bounds of the analytical models for these cases. In particular, Fig. 2.1(b) shows that the delay of DFT is slightly larger than that of IFT especially for p ≤ 0.07. It results from the fact that in the DFT protocol, new packets should join the backlog and wait, whereas the IFT protocol allows new packets to be transmitted immediately. For p > 0.07, the delays of 30 Chapter 2. Cross Layer Contention Resolution Algorithms 2 p p p p 6 0.07 (ana) 0.1 (ana) 0.07 (sim) 0.1 (sim) 0 −1 −2 p p p p p p 4 Negative drift Negative drift 1 = = = = = = = = = = 0.06 (ana) 0.07 (ana) 0.1 (ana) 0.06, ρ = 0.6 (sim) 0.07,ρ = 0.7 (sim) 0.1, ρ = 0.75 (sim) 2 0 −2 −3 −4 0 10 20 30 Backlog state 40 (a) Negative drift of IFT protocol. 50 −4 0 10 20 30 Backlog state 40 50 (b) Negative drift of DFT protocol. Figure 2.3: System stability by negative drift. IFT and DFT protocols converge, while S is saturated. In Figs. 2.2(a) and 2.2(b), we examine the effect of θ in IFT/DFT protocols and of ρ in DFT on S. Fig. 2.2(a) shows that S decreases for high p, when small θ is applied. This implies that the backlog size varies slowly. Particularly in Fig. 2.2(b) we examine S by varying M at p = 0.075. Note that the mean of traffic intensity in the system can be expressed by Mp. Accordingly, we can see almost identical S at p = 0.09 in Fig. 2.1(a) and at M = 60 in Fig. 2.2(b). For the effect of ρ in the DFT protocol, we can improve S at M = 50 by using ρ = 0.75. With smaller ρ, the enhancement of S is not significantly found. Moreover, S is slightly degraded with small ρ for large M. Note that in the analytical model, the evolution of the system backlog over time can be governed by the one step transition probability matrix Qn for n = 1, 2, . . . where n is the discrete time index. By spectral decomposition of Q, we can conjecture that the second largest eigenvalue3 of Q plays a critical role in explaining 3 The first largest eigenvalue of Q is always one due to stationarity. 31 Chapter 2. Cross Layer Contention Resolution Algorithms the transient behaviour and in representing the correlation of a Markov process [47], which models the backlog size here. Since ρ represents how much βt correlates to βt−1 in the first order AR model, we would choose ρ in proportion to the second largest eigenvalue of Q. In Figs. 2.3(a) and 2.3(b), we present the negative drift, d(m), of the analytical models with perfect knowledge on backlog size and simulations with perfect power control of IFT/DFT protocols, respectively. We choose p = 0.07 and p = 0.1, since the system is with the onset of saturation and in saturation at these values in Figs. 2.1(a) and 2.2(a). In Fig. 2.3(a), d(m) of analytical model in IFT protocol agrees quite well with that of simulation, and a single stable operating point is respectively found for p = 0.07 and 0.1. Note that negative drift for 0.07 < p < 0.1 lies between the lines depicted in Fig. 2.3(a). Fig. 2.3(b) shows d(m) in DFT protocol. Some differences between analytical and simulation results are found. In particular, d(m) goes to slightly positive at around m = 10 and becomes negative a few states away. Accordingly, two operating points are found, i.e., bistability. Even though such a bistability is found in DFT protocol, the system performance are not severely degraded as shown in Figs. 2.1(a)-2.2(b). This results from the fact that such two operating points are closely located and that the small positive increase of d(m) might be negligible. 2 In Figs. 2.4(a)-2.4(d), solid, dashed and dotted lines denote σX = 0.5 dB, 1 dB and 1.5 dB, respectively. In Figs. 2.4(a) and 2.4(b), imperfect power control is considered for an uncoded system. It is noticeable that c∗ and C c∗ become smaller due to high bit error probability, compared to the case with perfect power control. Accordingly, the larger the power control error, the lower S is observed. Additionally, the system becomes saturated when p > 0.05, because C c∗ is decreased. To measure throughput efficiency for the system with imperfect power control, we obtain the throughput efficiency by dividing the maximum of S in Fig. 2.4(a) by C c∗ . Then, the corresponding throughput efficiencies of an uncoded 32 Chapter 2. Cross Layer Contention Resolution Algorithms 50 1dB 1.5 0.25 dB 1.4 1.3 0.5 dB 1.2 1.1 1 0.02 0.04 0.06 0.08 0.1 (a) Throughput of uncoded system. 0.25dB 20 0.04 0.06 0.08 p 0.1 0.12 (b) Backlog delay of uncoded system. 2 25 1.8 ρ=0.95 1.6 1 dB 1.4 1.5 dB 1.2 1 0.8 0.04 0.06 1.5 dB 0.5 dB ρ=0.75 p 0.08 0.1 0.12 (c) Throughput of BCH-coded system. Backlog delay (slots) Throughput (packets/slot) 0.5dB 30 0 0.02 0.12 p 0.02 40 10 1 dB 0.9 0.8 Backlog delay (slots) Throughput (packets/slot) 1.6 20 1 dB 15 0.5 dB 10 5 0 0.02 ρ=0.95 ρ=0.75 0.04 0.06 p 0.08 0.1 0.12 (d) Backlog delay of BCH-coded system. Figure 2.4: Comparison of uncoded and BCH-coded system under imperfect power control 33 Chapter 2. Cross Layer Contention Resolution Algorithms 2 system with σX = 0.25, 0.5 and 1 (in dB) are 79%, 69% and 54%, respectively. Note that power control errors affect packet error probabilities as well as backlog estimation errors. In Figs. 2.4(c) and 2.4(d), S and D of Bose and Ray-Chaudhuri (BCH)-coded system (v = 8) are depicted. We obtain the throughput of a coded system by multiplying S by the coding rate L(v) in (2.11). Compared to S and D of an uncoded system, a coded system shows higher S and lower D for the same power control errors, e.g., 47% throughput 2 2 enhancement for σX = 1 dB. We obtain the throughput efficiency for σX = 0.5, 1 and 2 1.5 (dB) as 50.62%, 50.09% and 52.07%, respectively. For σX = 2 dB (not depicted), the algorithms show a throughput efficiency of 54%. Note that the throughput in Fig. 2.4(c) and Fig. 2.5(a) is normalized by multiplying coding rate, L(v). Additionally, we observe the role of ρ in the DFT protocol for a coded system. As previously mentioned, the performance of the algorithm for the DFT protocol becomes close to that for IFT protocol, when ρ is chosen as a value close to the second largest eigenvalue of Q in (2.16), particularly for small p as in Fig. 2.2(b). In Figs. 2.5(a)-2.5(b), the effect of error correcting capability, v, is examined for coding rate L(3) = 0.9, L(8) = 0.75 and L(14) = 0.57. We can obtain v by finding the argument v to maximize (2.11). In Fig. 2.5(b), the backlog delay, which means the time to be taken for sending 255 information bits in a coded system, is normalized by dividing D by L(v). While the normalized backlog delays for v = 8 and 14 are not distinguishable in Fig. 2.5(b), Fig. 2.5(a) shows that the system with v = 8 shows better throughput performance than others. 2.5 Summary In this chapter we have proposed throughput efficient cross-layer CRAs for IFT and DFT protocols in CDMA-based MPR S-ALOHA systems, in which MAI is exploited to estimate 34 Chapter 2. Cross Layer Contention Resolution Algorithms 1.2 50 v=8 v=14 Throughput 1 v=3 0.9 0.8 0.7 0.6 0.5 0.02 0.04 0.06 p 0.08 (a) Throughput. 0.1 0.12 v=3 Backlog delay (slots) 1.1 40 30 v=8 20 v=14 10 0 0.02 0.04 0.06 p 0.08 0.1 0.12 (b) Backlog delay. 2 Figure 2.5: Performance of BCH-coded system under imperfect power control, σX = 1.5 dB. the system backlog in the presence of power control errors. In the proposed algorithms, retransmission probability for backlogged terminals is chosen slot-by-slot to maximize the conditional expected system throughput. For the IFT and DFT protocols, the performance of the algorithms under perfect power control is close to that predicted by the analytical performance model without estimation errors. By examining negative drift, the algorithms are shown to be stable. For uncoded/coded systems under imperfect power control, system throughput decreases due to reduction of channel capacity. Especially, the throughput efficiency in coded systems is maintained over 50% up to power control error of 2 dB. 35 Chapter 3 Existing Backoff Algorithms for Single-Buffered Terminals The CRAs standardized in LTE and IEEE 802.16 systems employ a backoff algorithm with retry limit: UB in the case of LTE [6] and BEB in the case of IEEE 802.16 system [30]. Besides retry limits, each standard considers some access level priority in order to provide quality of service (QoS) at the MAC level among the services such as security services, public utilities, emergency service, e.g., rescue in a congested area [31]. In addition to prioritization in the access control, access priority can be further enhanced by differentiating some parameters of those backoff algorithms. In this chapter, we provide a comparative study on these backoff algorithms with retry limit and access priority differentiation. Previous work on backoff algorithms with retry limit can be categorized based on the design of the backoff algorithm, i.e., window-based or probability distribution-based, and the modeling assumptions, i.e., finite or infinite population, and saturated or unsaturated traffic condition. Kim [48] considered a frequency-hopped CDMA system under an infinite population model, in which uniform retransmission intervals are assumed. It has been shown that system stability can be achieved by controlling retry limit and the channel coding rate that affects the transmission success rate of a packet. Sakakibara et al. examined EB algorithm with retry limit in S-ALOHA systems [37][49]. Additionally, Liu [50] examined an EB algorithm in frequency-hopped S-ALOHA systems under a finite population with unsaturated traffic (FP/UST) model. The EB algorithm in [37][49][50], 36 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals which retransmits a packet with probability ri (≤ ri−1 ) after it has been unsuccessfully transmitted i − 1 times, is an approximate model for the widely-used window-based BEB backoff algorithm. While the system bistability has been extensively examined according to the retry limit in [37][49][50], packet delay and packet dropping probability have not been evaluated. In [19], Kwak et al. considered retry limit of window-based BEB in SALOHA under a finite population with saturated traffic (FP/ST) model. Similarly, Falla et al. [51], Vu et al. [52] and Chuck et al. [53] examined window-based BEB with retry limit for an IEEE 802.16 system under FP/ST. It should be noted that S-ALOHA system under FP/ST model always operates in a stable but inefficient region [37][49]. In contrast to [19][51][52][53] with FP/ST model, in this chapter we examine the performance of UB and BEB algorithms with retry limit under FP/UST model, which is closer to practical situations, and discuss their stability. For some access prioritization scheme in random access, Xiao [32] examined not only the effect of the retry limit of BEB algorithm in IEEE 802.11 system4 , but also considered prioritized access schemes by differentiating contention window size of BEB algorithm under FP/ST. Additionally, Angeles et al. [54] considered a prioritization scheme in S-ALOHA system by differentiating retransmission probability of high- and low-priority terminals. In comparison with [32][54], we consider the performance of UB and BEB algorithms with access priority and their stability under FP/UST model. Our comparative study of UB and BEB algorithms could provide a comprehensive understanding on the random access in LTE and IEEE 802.16 systems. The contributions of this chapter are three-fold. First, we examine UB and BEB algorithms with retry limit used in the RACHs of LTE and IEEE 802.16 system under FP/UST model for non-prioritized access. Secondly, we consider some prioritized access 4 The BEB algorithm in IEEE 802.11 systems decrements its backoff counter during idle channel, while the UB and BEB algorithms in wireless cellular networks [6][31] decrement its backoff counter regardless of channel status. 37 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals schemes by differentiating the persistence value [31] and other parameters of the UB and BEB algorithms. Thirdly, we extend an existing Bayesian broadcasting algorithm [55] into a dynamic window assignment (DWA) scheme in the UB algorithm, which is suitable for application in LTE. In this chapter, we ignore the physical characteristics of the OFDMCDMA channel in order to focus on the backoff algorithms in the MAC layer. The main results can be summarized as follows: 1. Under an FP/UST model, we obtain the stability conditions of the system with UB and BEB backoff algorithms with/without retry limit. In contrast to the previous work [37][49][50] showing that some approximate backoff algorithms exhibit bistability, our analysis shows that UB and BEB algorithms without retry limit do not have such a bistability characteristic. Instead, these backoff algorithms operate in either a stable or unstable manner. Thus, instead of controlling the retry limit to maintain system stability as in [37][49][50], we shall see that the retry limit provides a tradeoff between throughput and delay performance at the expense of the packet dropping probability. 2. In contrast to the extensive studies on BEB algorithms in the previous work [19][32][51][52] [53], we compare the performance of the UB algorithm standardized in LTE [6] against that of the BEB algorithm standardized in WiMAX [30], in terms of throughput, mean and variance of delay, and packet dropping probability given the retry limit. We show that UB can be designed to have a similar performance as BEB. It is also shown that UB achieves much smaller variances of total access delay than BEB. Note that the variance of the access delay is an important indicator of fair use of the channel by all terminals over time; i.e., a backoff algorithm showing a small variance in retransmission delay will support more even channel access by the terminals. 3. We examine some access prioritization schemes for the UB and BEB algorithms by 38 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals differentiating the persistence probability as specified in [6] and window size. It is shown that the persistence value effectively provides access prioritization, especially when the system is overloaded. 4. In [6], LTE allows the window size of UB algorithm to be dynamically changed by the eNodeB (a base station of LTE) according to network congestion5 . Our DWA scheme for the UB algorithm outperforms the existing mechanism in the RACH of LTE for static and time-varying traffic conditions, provided that orthogonality of RAPs are preserved. 3.1 3.1.1 Backoff Algorithms System Model The RACH of LTE and IEEE 802.16 systems have been introduced in Section 1.1. In both systems, if the number of retransmissions exceeds the maximum retry limit, the RAP is dropped in the MAC layer. This is reported to a higher layer. Once the RAP is successfully transmitted, the terminal can transmit a bandwidth request message for bandwidth reservation on the uplink channel that the BS has granted to it via the random access response (RAR) message in LTE or the uplink-map in IEEE 802.16 system. Upon each collision, terminals in each system conduct the following backoff algorithm. 3.1.2 Uniform Backoff Algorithm in LTE Each backlogged terminal draws randomly a backoff counter between 0 and U − 1. The backoff counter is then decremented by one at every slot, until it reaches zero. When the 5 In the UB algorithm of LTE [6], thirteen different window sizes from 0 and 960 msec are specified, which can be dynamically selected. 39 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals backoff counter is zero, the terminal selects a random real number between 0 and 1. As in [31], if this number is less than the persistence probability (or persistence value) p, the terminal transmits its packet; otherwise it postpones the packet transmission by repeating the above procedure in the next slot, until the packet is transmitted. When the packet is not successfully transmitted, i.e., the transmission encounters a collision, the terminal delays its retransmission again by a random time newly chosen between 0 and U − 1. This trial is repeated up to L times more, until the retransmission succeeds, or the terminal drops the packet and goes back to idle if the L + 1-th retransmission remains unsuccessful. Accordingly, fast resolution of collisions in RAP transmissions is expected to enable fast bandwidth reservations. Additionally in LTE, the window size of the UB algorithm, which is denoted by U hereafter and is assigned by the BS in the first RAR message, can be dynamically chosen according to network congestion. Thus, it is expected that controlling U appropriately can resolve collisions efficiently under some time-varying traffic condition. 3.1.3 Binary Exponential Backoff Algorithm in IEEE 802.16 Upon an unsuccessful packet transmission, the BEB algorithm increases the backoff window exponentially by doubling its size. Let Wi denote the backoff window size of the i-th backoff stage, which is determined by Wi = 2i W0 for 0 ≤ i ≤ K (3.1) where W0 is the minimum backoff window size. At the i-th backoff stage, the backlogged terminal randomly chooses a backoff counter in the range [0, Wi − 1] for 0 ≤ i ≤ K. Once chosen, the backoff counter is decremented every slot as in UB algorithm. When it reaches zero, the terminal transmits its packet. Upon transmission failure, the terminal increments the backoff stage by one and chooses the next backoff counter again. Although the retry 40 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals limit, L, is independent of K in [30], we assume here that the BEB algorithm retries L times additionally at the K-th stage. Upon the retransmission failure after total of L + 1 retransmissions at the K-th stage, it drops the packet. Thus, the maximum of total number of retransmissions is K + L + 1. 3.1.4 Access Prioritization by Persistence Value In order to provide access priority, UMTS includes eight access priority classes [31], each of which has a different persistence value p = Pi (N) = si · 2−(N −1) for 0 ≤ i ≤ 7. Note that the value of i can indicate a certain partition of the RACHs. The persistence scaling factor si is assumed to be a value between 0.2 and 0.9 by step of 0.1, and the dynamic persistence level N from 1 to 8 is broadcast regularly. If the persistence scaling factors are not broadcast, a default value of one is assumed. Once the backoff counter reaches zero, the terminal draws a real random number between 0 and 1. If this number is less than Pi (N), the terminal transmits a packet. Otherwise, it repeats this test until transmission. Note that two successive tests are separated by a certain time period called the T2 timer. We apply this access prioritization scheme to both UB and BEB algorithms to facilitate comparisons. 3.2 Performance Evaluation Before proceeding with our analysis, we summarize in Table 3.1 the notations defined previously, which will be used in this section. In the system model, we assume a finite population of M terminals. Each terminal can hold only one packet for transmission or retransmission until it is successfully received. A 41 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals Notation P M L U K ǫ ps pr pc p Table 3.1: Nomenclature for analysis Definition Number of orthogonal random access codes (preambles) Total number of terminals Retry limit of retransmissions Window size of uniform backoff algorithm Maximum stage of BEB algorithm, maximum window WK = 2K − 1 Probability that a packet is generated at an idle terminal every slot, i.e. Bernoulli trial with probability ǫ Transmission success probability of a packet Retransmission probability of a packet Code-collision probability of a packet, pc = 1 − ps Persistence probability (value) terminal that has no packet to transmit is said to be idle. An idle terminal generates a packet in every slot based on a Bernoulli trial with probability ǫ, i.e., unsaturated traffic condition. When a terminal has a packet to send, it immediately becomes backlogged by performing the backoff algorithm, i.e., it employs a DFT protocol. We finally assume that terminals can get feedback information for the RAP transmitted, e.g., success or failure, from the BS right before the next slot without any error, i.e., no feedback delay or error is taken into account. 3.2.1 Channel Model Suppose that a terminal among M terminals (re)transmits a packet with probability one. Then, its transmission success probability ps can be written as M −1 ps = n=0 1 n+1 n k=0 (k + 1)Λ(k + 1|n + 1, P ) Ω(n, M − 1, pr ), (3.2) in which the term in the bracket indicates the conditional throughput given n + 1 packets transmitted (including the packet of our interest). By dividing this term by n + 1, we get 42 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals the conditional transmission success probability given n + 1 packets. For the code-collision under perfect orthogonality condition among RAPs, we have Ck+1,n+1 = Λ(k + 1|n + 1, P ). Other channel models can be analyzed by replacing Ck+1,n+1 accordingly. Throughout this chapter, we denote the binomial probability distribution function with parameters b, L and p by Ω(b, L, p) = L b (p)b (1 − p)L−b . To see the probability that a terminal chooses a unique RAP, we define as Λ(k|v, Nc) the probability that k among v RAPs simultaneously transmitted are uniquely chosen among total of Nc RAPs, i.e., successful transmission probability of k out of v packets. Recall that backlogged terminals select one of P RAPs and transmit it. Then, we can obtain recursively Λ(k|v, P ) by [56] v Λ(k|v, P ) = m=0 Ω(m, v, 1/P )Λ(k − I(m − 1)|v − m, P − 1) (3.3) in which the indicator function I(x) equals one at x = 0 or zero elsewhere. Eq. (3.3) means that, by examining each of v packets transmitted in order, if a unique RAP is transmitted with probability Ω(1, v, 1/P ), it is counted as one success and we decrement k, v and P by one. Otherwise, we subtract from v a group of m duplicated RAPs, which occurs with probability Ω(m, v, 1/P ) for m = 1. Eq. (3.3) has the following initial conditions: Λ(0|1, 0) = 1, Λ(0|1, P ) = 0 for P ≥ 1, Λ(1|1, P ) = 1 for P ≥ 1, Λ(1|1, 0) = 0, Λ(1|v, 1) = 0 for v = 1, Λ(k|v, P ) = 0 for min(v, P ) < k, Λ(−1|v, P ) = 0 for any v and P . If P = 1, the channel is reduced to an S-ALOHA channel. In fact, Λ(k|v, P ) is related to the classical occupancy problem in [57], in which more general cases are considered. 43 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals 3.2.2 Approximation on Correlated Backoff Processes In order to model M terminals’ backoff algorithm (either UB or BEB) we should consider a multidimensional Markov process, bt = [bt1 , bt2 , · · · , btM ], in which bti denotes the backoff process of the i-th terminal at time t. In BEB algorithm we can have −1 ≤ bti ≤ K according to (3.1). Note that −1 indicates the state of a terminal having no packet to send. The stationary behaviour of bt can be written by lim Pr[bt1 = i1 , . . . , btM = iM ] for − 1 ≤ ij ≤ K, 1 ≤ j ≤ M. t→∞ (3.4) With slight abuse of notation, we denote by bi the stationary behaviour of the i-th terminal’s backoff process. If we are interested in the probability that n terminals have no packet while M − n terminals are in the backoff process, based on i.i.d. assumption on terminals’ backoff processes, we can write this as M!/(n!(M − n)!)Pr[bj = −1]n (1 − Pr[bj = −1])M −n , in which any terminal among M terminals can be the j-th terminal. This can be extended by a multinomial distribution for the event that ni terminals are in the i-th backoff stage for −1 ≤ i ≤ K. 3.2.3 Uniform Backoff Algorithm Define πE and πi,j for 0 ≤ i ≤ L and 0 ≤ j ≤ U − 1 as the stationary state probability that a terminal is idle and that a terminal is at the j-th backoff counter value of the i-th backoff stage, respectively. Then, we can write the state balance equation for πE as L−1 πE = (1 − ǫ)πE + p · ps πi,0 + pπL,0 . (3.5) i=0 44 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals We can write π0,j for 0 ≤ j ≤ U − 1 as π0,0 = (1 − p)π0,0 + π0,j = ǫ πE + π0,1 , U ǫ πE + π0,j+1 for 1 ≤ j ≤ U − 2, U and π0,U −1 = ǫ πE . U (3.6) We can also write πi,j for 1 ≤ i ≤ L and 0 ≤ j ≤ U − 1 as πi,0 = (1 − p)πi,0 + πi,j = ppc πi−1,0 + πi,j+1, U ppc ppc πi−1,0 + πi,j+1 for 1 ≤ j ≤ U − 2 and πi,U −1 = πi−1,0 . U U (3.7) Using (3.6) and (3.7), we rewrite πi,j for 0 ≤ i ≤ L as ǫ πi,0 = pic πE p and πi,j = pic Using the normalization condition πE + L i=0 U −j · ǫπE for 1 ≤ j ≤ U − 1. U U −1 j=0 1 U −1 + p 2 πE = 1 + ǫ (3.8) πi,j = 1, we can get πE as 1 − pL+1 c 1 − pc −1 . (3.9) Then, the retransmission probability pr can be expressed as L pr = p πi,0 i=0 1 − pL+1 c = ǫπE . ps (3.10) When L → ∞ in (3.9) and (3.10), we have the case without retry limit. To find the solution of pr satisfying (3.2) and (3.10) simultaneously, we construct a 45 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals function fU (pr ) with (3.2) and (3.10) as fU (pr ) = pr − 1 − (1 − ps )L+1 ǫπE . ps (3.11) Note that (3.11) is a function of pr , when we substitute (3.2) into (3.11) for ps . The solution of pr satisfying fU (pr ) = 0 is numerically found for 0 < pr < 1. If a unique pr is found, we have a stable system. Otherwise, the system is said to be either bistable or unstable. We shall discuss this in Section 3.2.5. As a performance metric, the system throughput τ in packets/slot can be obtained as M n kΛ(k|n, P )Ω(n, M, pr ). τ= (3.12) n=0 k=0 We then obtain the throughput for this channel, normalized with respect to the total number of codes, by τN = τ /P (packets/slot/code). The packet dropping probability Pd , due to reaching the retry limit, can be expressed as Pd = pc pπL,0 = pL+1 ǫπE , c (3.13) where pc is the code-collision probability. Note that Pd goes to zero as L → ∞. In order to obtain the mean packet transmission delay, i.e., access delay, some previous work [19][51][52] used the mean-value analysis. Instead, we use an absorbing Markov chain technique. First, we define the packet retransmission delay Di,j as the time for an absorbing process starting from the initial backoff counter value j at the i-th backoff stage to reach (i.e., be absorbed into) the idle state. As usual, we denote the expectation of a random variable by an overline, thus D i,j = E[Di,j ]. Note that, in the i-th backoff stage for 0 ≤ i ≤ L, the initial backoff counter value j is chosen uniformly from 0 ≤ j ≤ U − 1. 46 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals Define the mean access delay d as the mean time taken for a terminal to transmit a packet successfully, after it is generated. We can write d as U −1 U −1 , 2 (3.14) D i,j = E[1 + Di,j−1 ] = j + D i,0 (3.15) 1 d= U D 0,j = D 0,0 + j=0 in which we have used the following relation for 0 ≤ i ≤ L and 1 ≤ j ≤ U − 1. The first equality in (3.15) indicates that it always takes one slot for the absorbing process to go down by one to the next backoff counter value with probability one. Since the higher layer of a terminal will be informed upon packet dropping, we include the delay of the packets successfully transmitted and dropped in (3.14). We can write Di,0 for 0 ≤ i ≤ L − 1 as D i,0 ppc E =pps + (1 − p)E [1 + Di,0 ] + U 1 U −1 = + pc D i+1,0 + p 2 = U −1 (1 + Di+1,j ) j=0 1 U −1 + pc p 2 1 − pcL−i + pcL−i , 1 − pc (3.16) which indicates that the retransmission delay takes one slot with probability p × ps , when the backoff counter is zero. Further, when the persistence test is not passed with probability 1−p, it takes one more slot before the next persistence test. When a packet is retransmitted, but unsuccessful, the retransmission delay takes one slot and additional delay depending on the next backoff counter. We have D L,0 = 1 · p + (1 − p) 1 + D L,0 , (3.17) 47 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals which is simplified as D L,0 = 1/p. Using (3.15) and (3.17), one can get D i,0 for 0 ≤ i ≤ L−1 by D i,0 = 1 U −1 1 1 − pL−i+1 + pc 1 − pcL−i c 1 − pc p 2 . (3.18) In order to obtain the access delay variance, let d2 denote the second moment of the access delay, which is expressed by d2 1 = E U U −1 2 D0,j j=0 1 = U U −1 j=0 D 2 0,j = D 2 0,0 + (U − 1)D 0,0 + 2U 2 + 3U − 5 6 (3.19) where we have used j−1 D2 i,j 2 D i,k + D 2 i,0 = 2jDi,0 + j 2 + D 2 i,0 , = E[(1 + Di,j−1) ] = j + 2 (3.20) k=0 for 0 ≤ i ≤ L and 1 ≤ j ≤ U − 1. In the above, we can write D 2 i,0 for 0 ≤ i ≤ L − 1 as D2 i,0 =pps + (1 − p)E (1 + Di,0 ) 2 ppc E + U U −1 (1 + Di+1,j )2 j=0 U −1 =pps + (1 − p) 1 + 2Di,0 + D2 i,0 ppc U +2 + Di+1,j + U j=0 U −1 D 2 i+1,j , (3.21) j=0 which is the second moment of (3.16). By substituting (3.15) and (3.20) into (3.21), we can rewrite D2 i,0 1 = p 2U 2 + 3U − 5 1 + ppc 6 + 2(1 − p)Di,0 + ppc (U + 1)Di+1,0 + D 2 i+1,0 . (3.22) 48 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals Finally we have D 2 L,0 = 12 · p + (1 − p)E (1 + DL,0 )2 , (3.23) which is simplified as D 2 L,0 = 1/p 1 + 2(1 − p)D L,0 . The variance of the packet access 2 delay is obtained by dv = D 2 − D . 3.2.4 Binary Exponential Backoff Algorithm Let π ˆE and π ˆi,j denote the stationary state probability that a terminal has no packet and that a terminal is at the j-th backoff time of the i-th backoff stage, respectively, in the BEB algorithm. We can write a balance equation for π ˆE as K−1 π ˆE = (1 − ǫ)ˆ πE + pps π ˆ0,i + π ˆ0,K . (3.24) i=0 Substituting W0 for U in (3.6), we can get the balance equations for i = 0. We express π ˆi,j for 0 ≤ i ≤ K − 1 and 0 ≤ j ≤ Wi − 1 as π ˆi,0 = (1 − p)ˆ πi,0 + π ˆi,j = ppc π ˆi−1,0 + π ˆi,1 Wi ppc ppc π ˆi−1,0 + π ˆi,j+1 for 1 ≤ j ≤ Wi − 2 and π ˆi,Wi −1 = π ˆi−1,0 . Wi Wi Instead of Wi in (3.25), we use WK for π ˆi,j for K ≤ i ≤ K + L. For L = 0, (3.25) is valid for i = K. We can simplify (3.25) for 0 ≤ i ≤ K − 1 as ǫ ˆE π ˆi,0 = pic π p and π ˆi,j = pic Wi − j ǫˆ πE for 1 ≤ j ≤ Wi − 1. Wi (3.25) 49 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals We also have π ˆi,j for K ≤ i ≤ K + L ǫ π ˆi,0 = pic π ˆE p pic (WK − j) ǫˆ πE for 1 ≤ j ≤ WK − 1. WK and π ˆi,j = (3.26) By using the following normalization condition K+L WK −1 K−1 Wi −1 π ˆE + π ˆi,j = 1, π ˆi,j + i=0 j=0 i=K (3.27) j=0 we can get π ˆE = 1 + ǫ 1 − pcK+L+1 pc 2W0 (1 − (2pc )K−1 ) + p(1 − pc ) 2 1 − 2pc 1 − pcK−1 − 1 − pc pK (1 − pL+1 ) c + c 1 − pc WK − 1 2 (3.28) −1 . Denote by pˆr the retransmission probability for BEB algorithm, which can be expressed as K+L pr = p π ˆi,0 = i=0 1 − pcK+L+1 ǫˆ πE . ps (3.29) Since (3.2) is also valid for the BEB algorithm, as in (3.11), we can construct fB (pr ) with (3.2) and (3.29) as fB (pr ) = pr − 1 − pcK+L+1 ǫˆ πE ps (3.30) and then solve for fB (pr ) = 0. The system throughput is readily obtained by (3.12). The packet dropping probability can be obtained as Pd = pc pˆ πK+L,0 = pcK+L+1 ǫˆ πE . (3.31) 50 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals As we have seen before in (3.13), either large K or L makes Pd vanish. To analyze the delay performance of BEB algorithm, let Di,j denote the random variable of the packet retransmission delay starting from the j-th backoff counter of the i-th backoff window of BEB algorithm. Then, similarly to (3.14), the mean access delay, d, is expressed as d = D 0,0 + W0 − 1 . 2 (3.32) As in (3.16), we can express D i,0 for 0 ≤ i ≤ K + L − 1 by Di,0 =pps + (1 − p)E [1 + Di,0 ] + Wmin(i+1,K) −1 ppc Wmin(i+1,K) Wmin(i+1,K) − 1 1 = + pc Di+1,0 + p 2 E j=0 (1 + Di+1,j ) , (3.33) in which min(a, b) denotes the minimum of a and b. In (3.33) we have used D i,j = j + Di,0 and (3.1). Then, we have D i,0 = 1 pc − p 2 1 − pcK−1−i 1 − (2pc )K−1−i + pc W0 + D K−1,0pK−1−i . c 1 − pc 1 − 2pc (3.34) for 0 ≤ i ≤ K − 2. We can write D i,0 for K − 1 ≤ i ≤ K + L − 1 as Di,0 = 1 1 − pc WK − 1 1 + pc 1 − pK+L−i+1 1 − pcK+L−i c p 2 (3.35) where we have used D K+L,0 = 1/p. For both UB and BEB algorithms, as L → ∞, the respective derivations correspond to the algorithm without retry limit. 51 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals Now, the second moment of the access delay of the BEB algorithm can be expressed as d2 1 = W0 W0 −1 j=0 D 2 0,j = D 2 0,0 + D 0,0 + 0.5. (3.36) As in (3.21), we can write D 2 i,0 for 0 ≤ i ≤ K + L − 1 as D2 i,0 = pps + (1 − p)E (1 + Di,0 ) 2 + ppc Wmin(i+1,K) Wmin(i+1,K) −1 E j=0 (1 + Di+1,j )2 . (3.37) After some lengthy manipulation with D 2 i,j = 2jDi,0 + j 2 + D 2 i,0 for 0 ≤ i ≤ K + L and 1 ≤ j ≤ Wmin(i+1,K) − 1, we can rearrange (3.37) as D2 i,0 1 = p 1 + ppc 2 2Wmin(i+1,K) + 3Wmin(i+1,K) − 5 6 + ppc (Wmin(i+1,K) + 1)D i+1,0 + D 2 i+1,0 + 2(1 − p)D i,0 (3.38) . Finally we have D 2 K+L,0 = 1/p 1 + 2(1 − p)DK+L,0 . 3.2.5 Stability We discuss now the stability of these backoff algorithms especially for S-ALOHA channel, i.e., P = 1. Accordingly in what follows we use ps = (1 − pr )M −1 . For the system with P > 1, the following argument can be similarly applied. However, it might not seem obvious due to Ck,n in (3.2). The stability of either UB or BEB algorithm can be guaranteed, when a unique pr exists that solves (3.11) or (3.30). If multiple solutions are found, the system is said to be bistable, i.e., multiple equilibrium points. Finally, when no solution is found, the system is said to be unstable, i.e., backlog grows without bound. It is not difficult to prove the existence of the solution by showing fU (0) < 0 and fU (pr ) > 0 for some 0 < pr ≤ 1 in 52 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals UB algorithm. At pr = 0, we get fU (0) = −1/(1/ǫ + (1/p + 0.5(U − 1))). (3.39) As pr → 1, ps vanishes exponentially (pc → 1) due to M in (3.2). Then, we approximately write lim fU (pr ) = pr − pr →1 δU 1/ǫ + δU (1/p + 0.5(U − 1)) (3.40) with δU ≡ L + 1. If (3.40) becomes positive for 0 < pr ≤ 1, it implies an odd number of solutions of fU (pr ). Note that whether (3.40) is positive is mainly determined by U. Even for L → ∞ (no retry limit) the existence of the solution can be guaranteed, when a large U relative to M is chosen in (3.40). By the same token, for the BEB algorithm we have at pr = 0 fB (0) = −ǫp/(p + ǫ) < 0. (3.41) As pr → 1, we can write lim fB (pr ) = pr − pr →1 2δB . 2/ǫ + W0 2K (L + 1) + 2δB /p − (K + L + 2W0 ) (3.42) with δB ≡ K + L + 1. As before, we can have odd number of solutions of fB (pr ), if fB (pr ) > 0 for 0 < pr ≤ 1. Similar to U in (3.40), whether (3.42) is positive depends on K. Even some small K can guarantee that (3.42) is positive due to the exponential term in the denominator of (3.42). Letting ǫ → 1 and p → 1 and ignoring some negligible terms 53 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals in (3.42), we have approximately fB (pr ) ≈ pr − W0 δB K−1 2 (L + 1) . (3.43) For the BEB algorithm (W0 = 2) under saturated traffic condition (ǫ → 1), the solution always exists for some K. Until now, we have shown the existence of the solutions of fU (pr ) and fB (pr ). It is not easy to prove their uniqueness due to nonlinearity of fU (pr ) and fB (pr ). It is shown in [37][48][49][50] that applying a retry limit, i.e., limiting feedback to the channel input, can stabilize the system with a probability distribution-based backoff algorithm. If we show the stability of the system with window-based backoff algorithm without retry limit, i.e., L → ∞, it is reasonable to expect that the system with retry limit is also stable. From (3.9) and (3.11) we can rewrite the solution of fU (pr ) as pr = ps 1 − (1 − ps )L+1 ǫ , 1 U − 1 1 − pL+1 c 1+ǫ + p 2 ps (3.44) in which the terms with L vanishes, as L → ∞. We can simplify (3.44) as pr = ǫ/ [ps + ǫ (1/p + 0.5(U − 1))] . (3.45) Since ps = (1 − pr )M −1 is negligible for ǫ → 1 (i.e., saturated traffic condition) and large M, a unique pr can be determined, i.e. pr = 2/(U + 1) for p = 1. Although pr can be affected by (1 − pr )M −1 for unsaturated traffic condition, the uniqueness of pr can be found for large M. Similarly, letting L → ∞, we can approximately write the solution of fB (pr ) 54 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals for the BEB algorithm in (3.30) as pr = ǫ/ ps + ǫ 1/p + pc ps W0 (2K−1 − 1) + 0.5pK c (WK − 1) . (3.46) From (3.46) we get a unique pr = 2/(WK − 1), since we have ps → 0 (pc → 1) for saturated traffic and large M. Thus, window-based backoff algorithms, such as UB and BEB algorithms (even with large L, i.e., many retransmissions) show only either stable or unstable behaviour in accordance with U (for the UB algorithm) or K (for the BEB algorithm) and ǫ. Note that the bistability observed in [37][48][49][50] results from an approximate model of some window-based backoff algorithms, i.e., based on a (truncated) geometric distribution, not from window-based backoff algorithms. 3.2.6 Access Prioritization Scheme Consider C access priority classes, each of which consists of M [ν] terminals for 1 ≤ ν ≤ C. Hereafter, the superscript of a parameter indicates the access priority class. We can achieve [ν] access prioritization by differentiating p, U, K, L, or a combination of them. Let ps and [ν] pr denote the transmission success and retransmission probability of a terminal belonging [ν] to the ν-th access priority class. Then, we can obtain ps of both UB and BEB algorithms by M [1] p[ν] s = n[1] =0 M [ν] −1 ··· n[ν] =0 M [C] ··· n[C] 1 n+1 n[1] k [1] =0 n[C] ··· k [C] =0 (k + 1)Ck+1,n+1 Ω(n[ν] , M [ν] − 1, p[ν] r ) C × Ω(n[i] , M [i] , p[i] r ) (3.47) i=1,i=ν 55 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals Table 3.2: Nomenclature for DWA algorithm Definition Number of RAPs not transmitted at time t Number of RAPs successfully received at time t The estimated number of backlogged terminals at time t The estimated number of new packet arrivals at time t The window size is assigned at time t Smoothing factor Notation CE (t) CS (t) B(t) λt Ut β where k = C ν=1 k [ν] and n = C ν=1 n[ν] . For S-ALOHA channel with P = 1, we readily get p[ν] s = 1− C M [ν] −1 p[ν] r i=1,i=ν 1 − p[i] r M [i] . (3.48) [ν] We can obtain pr of both backoff algorithms for 1 ≤ ν ≤ C by substituting (3.48) into either (3.10) or (3.29), respectively. Then, the system throughput can be obtained as M [1] τ= n[1] =0 M [C] ··· n[1] n[C] =0 k [1] =0 n[C] ··· C k k [C] =0 ν=1 Λ k [ν] |, n[ν] , P Ω n[ν] , M [ν] , pr[ν] where the first summation holds for all possible combinations of n[ν] for 1 ≤ ν ≤ C. For P = 1, we have τ = C ν=1 τ [ν] , in which τ [ν] is expressed as C Ω 0, M [i] , p[i] r . τ [ν] = Ω 1, M [ν] , p[ν] r (3.49) i=1,i=ν We can also obtain the mean and variance of a packet retransmission delay by using (3.14), (3.19), (3.32) and (3.36) for both backoff algorithms, respectively. 56 0.4 50 0.35 45 40 0.3 35 0.25 0.2 M M M M M M M M 0.15 0.1 0.05 0 0 0.02 0.04 0.06 ǫ = = = = = = = = 0.08 40, P = 1 (a) 40, P = 4 (a) 100, P = 4 (a) 140, P = 4 (a) 40, P = 1 (s) 40, P = 4 (s) 100, P = 4 (s) 140, P = 4 (s) 0.1 d (slots) τ N (packets/slot/code) Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals 30 25 M M M M M M M M 20 15 10 5 0 0.12 (a) Normalized throughput 0.02 0.04 0.06 ǫ 0.08 40, P = 1 (a) 40, P = 4 (a) 100, P = 4 (a) 140, P = 4 (a) 40, P = 1 (s) 40, P = 4 (s) 100, P = 4 (s) 140, P = 4 (s) 0.1 0.12 (b) Mean of retransmission delay. 350 0.018 0.016 300 0.014 M = 40, P = 1 (a) 250 M = 40, P = 4 (a) 0.012 dv Pd 200 150 M M M M M M M M 100 50 0 0 = = = = = = = = 0.02 0.04 0.06 ǫ = = = = = = = = 0.08 40, P = 1 (a) 40, P = 4 (a) 100, P = 4 (a) 140, P = 4 (a) 40, P = 1 (s) 40, P = 4 (s) 100, P = 4 (s) 140, P = 4 (s) 0.1 0.12 (c) Variance of retransmission delay. M = 100, P = 4 (a) 0.01 M = 140, P = 4 (a) 0.008 M = 40, P = 1 (s) 0.006 M = 40, P = 4 (s) M = 100, P = 4 (s) 0.004 M = 140, P = 4 (s) 0.002 0 0 0.02 0.04 0.06 ǫ 0.08 0.1 0.12 (d) Packet dropping probability. Figure 3.1: UB algorithm with different M and P . 57 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals 3.2.7 Dynamic Window Assignment Algorithm The proposed dynamic window assignment algorithm is given as Algorithm 3.1, in which the variables are defined in Table 3.2. We assume that a BS uses a bank of matched filters, each of which tracks a specific RAP, so that in each time slot it can determine respectively the number of RAPs not transmitted and the number of RAPs received, CE (t) and CS (t). In the 2nd line of Algorithm 3.1, P − CE (t) − CS (t) is the number of RAPs unsuccessfully transmitted. The underlying idea of this dynamic window assignment algorithm is a simple extension of the existing Bayesian algorithm in multidimentional packet reservation multiple access [55], in which each terminal estimates B(t) first and then determines the retransmission probability by pr = min(1, R/B(t)). Here, R is the number of orthogonal resources, e.g., time slots in [55]. In the UB algorithm, we expect 1/Ut to approximate pr in the mean value. If there are P RAPs and B(t) backlogged terminals, we can determine Ut = max(1, B(t)/P ) under the assumption of perfectly orthogonal RAPs. Note that max(a, b) denotes the maximum of a and b. To this end, we estimate B(t) in the 7-th line as the same way in [55]. For P = 1, the backlog estimation is identical to Rivest’s algorithm [10]. In addition to backlog size estimation, we assign averaged Ut as shown in the 8-th line, in which ⌈x⌉ denotes the smallest integer not less than x. In practical implementation, Ut can be broadcast to terminals right before the next slot, or it is given via the first RAR message in LTE. Note that, if Pd is not sufficiently small, the estimation on the number of backlogged terminals becomes inexact due to packet dropping. 58 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals U = 20, L = 5 (a) U = 40, L = 5 (a) U = 20, L = 8 (a) K = 5, L = 0 (a) U = 20, L = 5 (s) U = 40, L = 5 (s) U = 20, L = 8(s) K = 5, L = 0 (s) τ (packets/slot) 0.35 0.3 0.25 0.2 0.15 120 100 80 d (slots) 0.4 60 U = 20, L = 5 (a) U = 40, L = 5 (a) U = 20, L = 8 (a) K = 5, L = 0 (a) U = 20, L = 5 (s) U = 40, L = 5 (s) U = 20, L = 8(s) K = 5, L = 0 (s) 40 0.1 20 0.05 0 0 0.5 1 1.5 2 Mǫ 2.5 3 0 0 3.5 (a) Throughput. U = 20, L = 5 (a) U = 40, L = 5 (a) U = 20, L = 8 (a) K = 5, L = 0 (a) U = 20, L = 5 (s) U = 40, L = 5 (s) U = 20, L = 8(s) K = 5, L = 0 (s) 2000 dv 1500 1 1.5 2 Mǫ 2.5 3 3.5 (b) Mean of retransmission delay. 0.012 0.01 0.008 Pd 2500 0.5 U = 20, L = 5 (a) U = 40, L = 5 (a) U = 20, L = 8 (a) K = 5, L = 0 (a) U = 20, L = 5 (s) U = 40, L = 5 (s) U = 20, L = 8(s) K = 5, L = 0 (s) 0.006 1000 0.004 500 0.002 0 0 0.5 1 1.5 2 Mǫ 2.5 3 3.5 (c) Variance of retransmission delay. 0 0 0.5 1 1.5 2 Mǫ 2.5 3 3.5 (d) Packet dropping probability. Figure 3.2: Comparison of UB and BEB algorithms with different U and L. 59 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals Algorithm 3.1 - Dynamic Window Assignment Algorithm 1: 2: 3: 4: 5: 6: 7: 8: Initialize λ0 = 0, U0 = 20, B(0) = 0 and do the following at t = 1, 2, . . . . if P − CE (t) − CS (t) = P then λt = P e−1 . else λt = 0.9λt + 0.1CS (t). end if B(t) = max 0, B(t − 1) + (e − 2)−1 (P − CE (t) − CS (t)) − (CE (t) + CS (t)) + λt . Ut = ⌈βUt−1 + (1 − β)B(t)/P ⌉. 3.3 Numerical Studies In order to validate our analysis, we built a simulation program with MATLAB. Each simulation is carried out for 20000 slots. In the following, we use W0 = 2 in the EB algorithm. In Figs. 3.1(a) to 3.7(d), the curves are obtained numerically from the equations given in the above analysis, while the symbols indicated the corresponding simulation results. 1. The effect of multichannel code-collisions : We first examine the effect of code-collision in the UB algorithm by varying P in Figs. 3.1(a)-3.1(d) where we have p = 1, U = 15 and L = 5. As expected, we can see that large P provides higher τN for large ǫ given M in Fig. 3.1(a) and better performances, e.g. d in Fig. 3.1(b). However, we check that the performances of M = 160 and P = 4 are identical to those of M = 40 and P = 1. Therefore, it can be concluded that, although a large P can increase the RACH capacity, intrinsic properties of the system performances do not change under perfect orthogonality assumption. 2. The effect of U, K and L in UB and EB algorithms : We examine UB and EB algorithms without priority classes, i.e., p = 1, C = 1 in S-ALOHA channel (P = 1) in order to see their own characteristics in accordance with the window size U, K and with retry limit L in Figs. 3.2(a)-3.3(d). The horizontal axis indicates the traffic load (Mǫ) with M = 70. In general, our analysis agrees well with simulations. However, we have found 60 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals that analytical and simulation results show some difference in the delay variance of BEB with small L values (≤ 3), while other performance metrics show good agreements between analysis and simulation given any set of parameters. When a larger L is used (L ≥ 4) in the BEB algorithm, we can find good agreement between analytical and simulation results in the delay variance. Our conjecture is that, when L becomes large, the process of our interest becomes memoryless, i.e., less dependent on lower stages with different window size. Comparing the UB and EB algorithms, we observe that UB with U = 20 (L = 5) and BEB with K = 5 (L = 0) show almost identical throughput (τ ), the mean access delay (d) and packet dropping probability (Pd ) in Figs. 3.2(a)-3.2(b) and 3.2(d), respectively. Accordingly, it can be concluded that by tuning the parameters, U, K and L properly, the UB algorithm can give similar τ , d and Pd as the BEB algorithm. However, we can find two distinct differences between the UB and BEB algorithms. Firstly, d of BEB in the under-loaded region (Mǫ < 0.45) is much smaller than that of UB, because lower backoff stages are more frequently utilized in BEB. It is noticeable that in the under-loaded region, τ and Pd of the two backoff algorithms do not show large differences. Secondly, the delay variance of BEB (dv ) is much worse than that of UB in Fig. 3.2(c), which might be caused by the exponentially increasing nature of backoff intervals in the BEB algorithm. In both algorithms, we can observe that the peak of dv occurs at the traffic load that gives the maximum τ . We can also find that, when the system becomes overloaded, i.e., pc → 1, d and dv of UB are respectively approximated as d = 0.5(L+1)U and dv = (L+1)(U 2 −1)/12. For BEB, we have d = 0.5 K i=0 Wi + 0.5LWK and dv = (1/12) K 2 i=0 (Wi − 1) + L(WK2 − 1)/12. For the effect of window size, i.e., U in the UB algorithm and K in the BEB algorithm, one can find an important tradeoff between the throughput-packet dropping probability pair and the mean and variance of delay particularly in the overloaded region 61 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals K K K K K K K K τ (packets/slot) 0.35 0.3 0.25 = = = = = = = = 5, L 5, L 8, L 5, L 5, L 8, L 5, L 5, L = = = = = = = = 0 5 0 0 5 0 5 5 (a) (a) (a) (s) (s) (s) (a) (s) 0.2 250 K K K K K K K K 200 d (slots) 0.4 0.15 150 = = = = = = = = 5, L 5, L 8, L 5, L 5, L 8, L 5, L 5, L = = = = = = = = 0 5 0 0 5 0 5 5 (a) (a) (a) (s) (s) (s) (a) (s) 100 0.1 50 0.05 0 0 0.5 1 1.5 2 Mǫ 2.5 3 0 0 3.5 (a) Throughput. 0.5 1 1.5 2 Mǫ 2.5 3 3.5 (b) Mean of retransmission delay. 5 10 0.012 K = 5, L = 0(a) 4 10 0.01 K = 5, L = 5(a) K = 8, L = 0(a) 3 10 0.008 dv Pd K = 5, L = 0(s) 2 10 K K K K K K K K 1 10 0 10 −1 10 K = 5, L = 5(s) 0.006 0 0.5 1 1.5 2 Mǫ = = = = = = = = 2.5 5, L 5, L 8, L 5, L 5, L 8, L 5, L 5, L 3 = = = = = = = = 0 5 0 0 5 0 5 5 (a) (a) (a) (s) (s) (s) (a) (s) 3.5 (c) Variance of retransmission delay. K = 8, L = 0(s) K = 5, L = 5(a) K = 5, L = 5(s) 0.004 0.002 0 0 0.5 1 1.5 2 Mǫ 2.5 3 3.5 3.6 (d) Packet dropping probability. Figure 3.3: Performance of BEB algorithm with different K, L and M. 62 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals p [1] = 1 (a) p [2] = 0.5 (a) U [1] = 20 (a) U [2] = 30(a) p [1] = 1 (s) p [2] = 0.5 (s) U [1] = 20 (s) U [2] = 30(s) 0.18 τ (packets/slot) 0.16 0.14 0.12 0.1 100 90 80 d (slots) 0.2 70 60 p [1] = 1 (a) p [2] = 0.5 (a) U [1] = 20 (a) U [2] = 30(a) p [1] = 1 (s) p [2] = 0.5 (s) U [1] = 20 (s) U [2] = 30(s) 50 0.08 40 0.06 0.04 30 0.02 20 0 0 0.5 1 1.5 2 Mǫ 2.5 3 10 0 3.5 (a) Throughput. 1000 dv 800 600 0.02 0.015 Pd p [1] = 1 (a) p [2] = 0.5 (a) U [1] = 20 (a) U [2] = 30(a) p [1] = 1 (s) p [2] = 0.5 (s) U [1] = 20 (s) U [2] = 30(s) 1200 1 1.5 2 Mǫ 2.5 3 3.5 (b) Mean of retransmission delay. 0.025 1400 0.5 p [1] = 1 (a) p [2] = 0.5 (a) U [1] = 20 (a) U [2] = 30(a) p [1] = 1 (s) p [2] = 0.5 (s) U [1] = 20 (s) U [2] = 30(s) 0.01 400 0.005 200 0 0 0.5 1 1.5 2 Mǫ 2.5 3 3.5 (c) Variance of retransmission delay. 0 0 0.5 1 1.5 2 Mǫ 2.5 3 3.5 (d) Packet dropping probability. Figure 3.4: Access prioritization scheme of UB algorithm with differential p and U. 63 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals (Mǫ > 0.45). In this region, larger U or K increases τ and reduces Pd at the expense of increasing the delay. Note that large U or K can stabilize the system for large M. Therefore, it might be desirable that U and K would be adjusted according to traffic load in order to minimize delay performance. For the effect of retry limit, larger L reduces Pd in UB and BEB algorithms, while other performance metrics get worse in the UB algorithm. In other words, UB with a smaller retry limit can provide better throughput and delay performance at the expense of increased packet dropping probability, in essence removing collisions by packet dropping. In the UB algorithm, L represents the number of retransmissions as well as the number of backoff stages. In contrast, we can allow more retransmissions in BEB without increasing the backoff stage, i.e., K + L. Thus, we additionally examine the effect of L in BEB algorithm in Figs. 3.3(a)-3.3(d). In these figures the line with black squares indicates the case with M = 100, whereas other lines and marks indicate the cases with M = 70. It is shown that increasing L given K in BEB improves τ and reduces Pd , while it increases the mean and variance of delay. The case with K = 8 and L = 0 improves τ much more in the overloaded region than the case with K = 5 and L = 5, while the former shows huge variance of delay in Fig.3.3(c). Note that at the same traffic load, τ and d with larger population size M = 100, depicted by the dash-dotted line with black squares, are worse than those with M = 70. 3. Access prioritization in the UB algorithm : In Figs. 3.4(a)-3.4(d), we present the performance of the prioritized access scheme with two priority classes for P = 1 as an example. We experiment with two prioritization schemes: One is to control the persistence probability of UB algorithm specified in [6], and the other one differentiates U. In the first scheme, we set p[1] = 1, p[2] = 0.5 and U [1] = U [2] = 20, while we have p[1] = p[2] = 1, U [1] = 20 and U [2] = 30 for the case of controlling U. In both cases, we have M [1] = M [2] = 35 and 64 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals 0.22 p [1] = p [2] = p [1] = p [2] = 0.2 125 0.16 100 d (slots) τ (packets/slot) 0.18 150 1 (a) 1/16 (a) 1 (s) 1/16 (s) 0.14 0.12 0.1 75 50 0.08 0.06 p [1] = p [2] = p [1] = p [2] = 25 0.04 0.02 0 0.5 1 1.5 Mǫ 2 2.5 3 (a) Throughput. 3.5 0 0 0.5 1 1.5 Mǫ 2 2.5 1 (a) 1/16 (a) 1 (s) 1/16 (s) 3 3.5 (b) Mean of retransmission delay. Figure 3.5: Access prioritization scheme of UB algorithm with differential p. L[1] = L[2] = 5. The horizontal axis of each figure denotes the traffic load of the sum of each priority class, i.e., Mǫ = i M [i] ǫ[i] . First, we note that the performance differentia- tion does not seem to be outstanding in the under-loaded region. We can see that access priority can be effectively provided in the overloaded region for both schemes. In Figs. 3.4(a)-3.4(b) where p[1] = 1 and p[2] = 0.5 are used, the performance differentiation in τ is not as distinguishable as d. To obtain a significant differentiated in τ , we decrease p[2] to 2−4 while keeping p[1] fixed at 1. The results are shown in Figs. 3.5(a)-3.5(b). The smaller p is used for the lower priority class, the larger performance differentiation is achieved in τ and d. Note that 1/p corresponds to the initial delay at each retransmission opportunities. Similarly, controlling U affects both throughput and delay performances. It should be noted that terminals with a high priority show a lower Pd , when prioritization is achieved by controlling p in comparison with controlling U as shown in Figs. 3.4(c)-3.4(d). In other words, controlling p provides terminals of high priority with better (more desirable) performance in all aspects. 65 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals 4. Access prioritization in the BEB algorithm : In Figs. 3.6(a)-3.6(d), we examine access prioritization in BEB with p and K for P = 1. As in Figs. 3.4(a)-3.4(d) for the UB algorithm, controlling p provides terminals of higher priority with better performance in all aspects. However, controlling K provides terminals of lower priority with lower Pd . Additionally, terminals with smaller K in BEB get both higher throughput and lower delay, while they have a higher packet dropping probability. In other simulations (not shown here) in which W0 is controlled, the same performance characteristics as controlling K are observed. Therefore, controlling p (initial access delay differentiation at each retransmission opportunity) gives higher priority terminals better performance in all aspects for both backoff algorithms. 5. Dynamic Window Assignment in UB algorithm : In Figs. 3.7(a)-3.7(b), we first test the DWA algorithm in static traffic condition in which ǫ does not change during the entire simulation. As an example, we set P = 3. It is observed that the algorithm achieves maximum throughput and minimum delay. In Figs. 3.7(c)-3.7(d), we set initial ǫ from 0.0031 to 0.095. Then we increase it by 1.8 times at the 10000-th slot. The results are obtained only from simulations and are time-averaged. Here, the horizontal axis indicates the average value of ǫ, e.g. ǫ = 0.0031(1 + 1.8)/2 = 0.0043. In such a time-varying traffic condition, the algorithm achieves the maximum throughput and the minimum delay as well. Thus, under the perfect orthogonality assumption and low Pd , it is concluded that 1/Ut can approximate the optimum retransmission probability mentioned in [10][55]. 6. Choice of UB and BEB : By controling the window size of the UB algorithm, it can achieve a similar throughput performance as the BEB algorithm. Since BEB self-adapts to the traffic load, it is incorporated in the IEEE 802.3 Ethernet and IEEE 802.11 WLAN standards, which are intended for networks that have no central controller for traffic load (backlog size) estimation. While BEB works in a distributed manner, it suffers from a 66 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals p [1] = 1 (a) p [2] = 0.5 (a) p [1] = 1 (s) p [2] = 0.5 (s) K [1] = 4 (a) K [2] = 6 (a) K [1] = 4 (s) K [2] = 6 (s) 0.18 τ (packets/slot) 0.16 0.14 0.12 0.1 0.08 300 p [1] = 1 (a) p [2] = 0.5 (a) p [1] = 1 (s) p [2] = 0.5 (s) K [1] = 4 (a) K [2] = 6 (a) K [1] = 4 (s) K [2] = 6 (s) 250 200 d (slots) 0.2 150 100 0.06 0.04 50 0.02 0 0 0.5 1 1.5 2 Mǫ 2.5 3 0 0 3.5 (a) Throughput. 0.5 1 1.5 Mǫ 2 2.5 5 0.018 p [1] = 1 (a) p [2] = 0.5 (a) p [1] = 1 (s) p [2] = 0.5 (s) K [1] = 4 (a) K [2] = 6 (a) K [1] = 4 (s) K [2] = 6 (s) 0.016 4 10 0.014 0.012 3 dv Pd 10 p [1] = 1 (a) p [2] = 0.5 (a) p [1] = 1 (s) p [2] = 0.5 (s) K [1] = 4 (a) K [2] = 6 (a) K [1] = 4 (s) K [2] = 6 (s) 2 1 10 0 10 0 0.5 1 1.5 2 Mǫ 2.5 3.5 (b) Mean of retransmission delay. 10 10 3 3 3.5 (c) Variance of retransmission delay. 0.01 0.008 0.006 0.004 0.002 0 0 0.5 1 1.5 2 Mǫ 2.5 3 3.5 (d) Packet dropping probability. Figure 3.6: Access prioritization scheme of BEB algorithm with differential p and K. 67 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals relatively high variance in access delay compared to UB. If a central controller is available and capable of estimating the backlog size, e.g., a BS in LTE, it may be preferable to use the UB algorithm due to its lower delay variance and equal throughput performance in comparison with the BEB algorithm. 3.4 Summary In this chapter, we have examined UB and BEB algorithms with retry limit for the random access channels in LTE and IEEE 802.16 systems, respectively. We have analyzed their performance in terms of throughput, mean and variance of packet retransmission delay and packet dropping probability, and examined the stability properties of both algorithms. We have shown that stability mainly depends on the uniform window size and the maximum backoff stage and also that systems employing these algorithms are either stable or unstable, but do not show bistability behaviour. Most of our analytical results have shown good agreement with simulations except the delay variance of systems with small retry limits. By adjusting the parameters of each backoff algorithm properly, the two algorithms show virtually identical throughput, but different delay variances. We have also shown that controlling the persistence probability provides effective access priority control with respect to various performance metrics. Finally, we have proposed a dynamic window assignment algorithm, which is a simple extension of an existing Bayesian broadcasting algorithm. The dynamic window assignment algorithm outperforms the existing backoff algorithms in any traffic condition, as long as perfect orthogonality assumption among random access code holds. 68 Chapter 3. Existing Backoff Algorithms for Single-Buffered Terminals 70 0.35 60 0.3 50 0.25 40 d τN 0.4 0.2 30 0.15 U = 20(a) U = 30(a) U = 20(s) U = 30(s) WA algorithm 0.1 0.05 0 0.02 0.04 ǫ 0.06 0.08 20 U = 20(a) U = 30(a) U = 20(s) U = 30(s) WA algorithm 10 0 0 0.1 (a) Throughput. 0.02 0.04 ǫ 0.06 0.08 0.1 (b) Mean of retransmission delay. 0.4 80 75 0.35 70 65 0.3 d τN 60 55 0.25 50 WA algorithm U = 20(s) U = 30(s) U = 40(s) 0.2 0.15 0 0.025 0.05 0.075 ǫ 0.1 (c) Throughput. 0.125 45 WA algorithm U = 20(s) U = 30(s) U = 40(s) 40 35 0 0.025 0.05 0.075 ǫ 0.1 0.125 (d) Mean of retransmission delay. Figure 3.7: Performance comparison of UB algorithm with/without DWA algorithm. 69 Chapter 4 Backoff algorithm with Power Ramping in LTE Capture effects due to the differences of the signal levels, times of arrival, or other properties of colliding packets at the receiver have been widely studied over the past decades [58][59][60][61] by examining system’s throughput and delay performances and stability under various capture models. In order to exploit the throughput gain by such capture effects, some transmission power selection schemes in S-ALOHA systems has been also proposed in [62][63][64][65], in which the transmission power is selected based on a PMF among a set of transmission powers. However, instead of selecting the transmission power optimally based on a PMF as in the literature, in a practical system such as LTE, terminals first estimate path loss from a downlink reference signal. Based on the assumption that path loss is symmetric over downand uplink, a terminal transmits its packet by adding additional power to a target received power in order to compensate for the estimated path loss. If such a packet transmission is not successful, the terminal retransmits its packet by increasing the transmission power previously used to the next level, which is called the PR scheme [6][66]. The rationale of this scheme is to increase the transmission success probability independent of a terminal’s location by meeting a target received power adaptively, while SINR is kept above a given threshold. However, the optimal PR step size and the number of steps remain to be determined. 70 Chapter 4. Backoff Algorithm with Power Ramping in LTE As previous work, in [63] Leung considered optimization problems of maximizing system throughput without exceeding some power constraint or minimizing the mean power consumption, while sustaining a minimum throughput under the perfect capture model, in which a packet with the strongest power level among packets simultaneously transmitted can capture the receiver, unless more than one packets of the strongest power level have been transmitted. In [64] LaMaire et al. considered optimization problems in order to maximize the capture probability with respect to the values of power levels and the probability distribution of selecting those values, when the number of terminals transmitting a packet under various capture models is known. Note that retransmission control is not considered in [63][64]. In [65] some power level selection algorithms with EB algorithm are considered under the saturated traffic condition, in which a finite number of terminals always have a packet to transmit. In [63][65], retransmitted packets from backlogged terminals are approximated by Poisson arrivals, regardless of finite or infinite user model. Especially, [67] examined the performance of various PR schemes with UB algorithm used in UMTS Terrestrial Radio Access (UTRA) by assuming an infinite user model. While the physical layer of UTRA is based on Wideband CDMA, in this thesis we are interested in LTE which physical layer is based on OFDMA. However, from the MAC layer’s viewpoint, the PR scheme with UB algorithm in UTRA [67] is almost identical to that of UMTS-LTE, except that the random access and the data transmission are separated over OFDMA subchannels in LTE. In contrast with [67], the main contribution of this are summarized as follows: 1. We evaluate the performance of the PR scheme with UB algorithm by assuming statistically independent, identically distributed (i.i.d.) backoff processes in the terminals, even though in reality terminals’ backoff processes with the PR scheme are correlated. By obtaining the correlation coefficient of terminals’ backoff processes 71 Chapter 4. Backoff Algorithm with Power Ramping in LTE from simulations, we show that the terminals’ backoff processes are so weakly (positively) correlated that the analysis based on i.i.d. assumption can agree well with simulations. 2. Under ideal channel conditions and assuming perfect path loss estimations, we show that the PR scheme is effective only when the SINR threshold is below −3 dB, compared to the system without the PR scheme. 3. In the PR scheme under consideration, a packet is dropped when a retransmission with the maximum transmit power is not successful. We define the capacity as the maximum acceptable number of terminals with a given packet arrival rate, which does not violate some specified packet dropping probability. We show that this capacity can be improved by the PR scheme with UB algorithm. 4. We incorporate the initial transmission power level selection based on a PMF in [63][64][65] into the PR scheme with UB algorithm. With respect to the average transmit power consumption and packet dropping probability, we show that the lowest-power-first transmission scheme is the most efficient compared to the other PMFs. 5. We propose a heuristic UB algorithm called a terminal-assisted UB algorithm (TAUBA) with PR, which helps a base station to estimate the backlog size based on the waitingtime information given in the packets successfully received. We show that TAUBA improves the system throughput close to its maximum and minimizes the packet dropping probability given any population size and packet arrival rate of each terminal, compared to static UB algorithms. The rest of this chapter is organized as follows. In Section 4.1, we introduce the PR scheme in UMTS-LTE. The performance analysis is presented in Section 4.2. We discuss 72 Chapter 4. Backoff Algorithm with Power Ramping in LTE some numerical examples in Section 4.3. Concluding remarks are given in Section 4.4. 4.1 System Model : Retransmission Backoff with Power Ramping As we shall see, the random access of LTE consists of two parts. The first part is to transmit a RAP, and the second part is to transmit the terminal’s specific data on the uplink channel obtained from the RAP transmission. When an accessing terminal performs the first part of the random access, it first estimates the path loss to the serving cell from downlink reference signal received power. Then, the terminal randomly chooses one of the orthogonal RAPs (i) and transmits it over a PRACH according to the PRACH configuration index. Let pt denote the i-th RAP’s transmission power for 1 ≤ i ≤ K, which is determined by [6] (i) pt = min(pmax , pR + ξL + (i − 1)∆p + O), (4.1) in which pmax , pR , ξL and ∆p denote the maximum preamble transmission power, the target preamble received power, the estimated path loss and the PR step size, respectively. The parameter O denotes an offset which is determined by the preamble format [68]. There are four different RAP formats which can be chosen based on the serving cell size. For analytical simplicity, we ignore this offset. Note that, if the path loss estimated by terminals is below a threshold, e.g., severe path loss, it is specified in [68] that the terminals add more power, e.g., 5 dB, to (4.1). In what follows, we assume that interference signals with severe pass loss can be neglected, so long as the total interference power due to MAI is sufficiently large and dominant. Denote by pi the received power of a RAP at the serving (i) cell, which is transmitted with power level pt . Under the perfect path loss estimation 73 Chapter 4. Backoff Algorithm with Power Ramping in LTE assumption, we can write pi for 1 ≤ i ≤ K as pi = pR + (i − 1)∆p, (4.2) in which pmax has been assumed to be equal to pK . Then, we can write the probability that a RAP received at power level pi can be successfully detected as Pr pi K j=1 nj pj + γ >β =I pi K j=1 nj pj + γ >β , (4.3) in which β and γ are the SINR threshold and other-cell interference, respectively. Addition(j) ally, nj denotes the number of terminals transmitting their RAP at power level pt . The function I(x) is an indicator function, which is one if x is satisfied, or zero elsewhere. Note in (4.3) that we assume that multiple access interference is the dominant factor that affects RAP detection. The serving cell now broadcasts over downlink the RAR message. This RAR message indicates the identifiers of the RAPs that have been successfully received and indicates the uplink data channel, called physical uplink shared channel (PUSCH), in which the successful terminals should transmit their messages in the second part of the random access as described in the next paragraph. If more than one terminals have transmitted the same RAP, and if the transmission power of their RAP would meet (4.3), all these terminals will find their random access successful. When a terminal having transmit(i) ted its RAP with power level pt does not find its RAP identifier in some RAR messages or within some specified time window, it regards its transmission as unsuccessful, i.e., implicit N-ACK. Then the terminal will perform the UB algorithm of window size U with PR scheme as follows. Note that the window size U is given in the RAR message. In the UB algorithm, the terminal randomly chooses a backoff counter between 0 and U − 1 and decrements this counter every slot. When this counter hits zero, the terminal transmits a 74 Chapter 4. Backoff Algorithm with Power Ramping in LTE (i+1) RAP with power level pt . Upon a retransmission failure, the terminal repeats this UB algorithm jointly with the PR scheme. Upon a failure at the K-th retransmissions, the terminal drops the random access and reports it to a higher layer. If the retransmission is successful, the terminal performs the second part of the random access as described below. In the second part of the random access, each terminal with a successful RAP transmission transmits a message with its unique identity in a PUSCH, by using H-ARQ. This will be given in Section 6.1.1. In this chapter we focus on the performance of the first part of the random access, i.e., the PR scheme with the UB algorithm. 4.2 4.2.1 Performance Evaluation Performance Metrics Suppose there are M terminals in a serving cell of LTE. We assume that one PRACH appears every slot, each corresponding to one RAP transmission time. A RAP is generated every slot in each terminal based on a Bernoulli trial with probability ǫ, and each terminal can accommodate only one RAP. Moreover, in contrast with implicit NACK for RAP transmission as described above, for analytical simplicity we assume that the explicit feedback from a serving cell regarding RAP transmissions, i.e., success or failure, is immediately broadcasted to the terminals without any error. Further, we assume that each terminal performs the UB algorithm, immediately after it has a packet, i.e., DFT. In what follows, we will use the terms packet and RAP interchangeably. Define πE and πi,j as the stationary state probability that a terminal has no packet and that a terminal is in the j-th backoff counter for 0 ≤ j ≤ U − 1 at the i-th back off stage for 1 ≤ i ≤ K. Further denote by ps,i the probability that a packet is successfully transmitted at the i-th back off 75 Chapter 4. Backoff Algorithm with Power Ramping in LTE stage. We then write the state balance equation for πE as K−1 πE = (1 − ǫ)πE + ps,i πi,0 + πK,0 . (4.4) i=1 In order to generalize our to include the transmission power selection based on a PMF in [63][64][65], we denote by li for 1 ≤ i ≤ K the probability that a terminal chooses the (i) i-th backoff stage with transmission power pt and starts the UB algorithm ( K i=1 li = 1), when a packet is generated. At the first backoff stage, we have π1,j = ǫl1 πE + π1,j+1 U for 0 ≤ j ≤ U − 2 and π1,U −1 = ǫl1 πE . U (4.5) We can write πi,j for 2 ≤ i ≤ K and 0 ≤ j ≤ U − 2 as πi,j = 1 − ps,i−1 ǫli πE + πi−1,0 + πi,j+1 . U U (4.6) For j = U − 1, we have πi,U −1 = ǫli 1 − ps,i−1 πE + πi−1,0 . U U (4.7) By some manipulation on (4.5)-(6.4), we can write πi,j as U −j ǫl1 πE for 0 ≤ j ≤ U − 1 and U U −j = ǫli πE + pc,i−1πi−1,0 for 2 ≤ i ≤ K and 0 ≤ j ≤ U − 1 U π1,j = (4.8) πi,j (4.9) 76 Chapter 4. Backoff Algorithm with Power Ramping in LTE with pc,i = 1 − ps,i . We can further simplify (4.8) and (4.9) as i−1 i−1 πi,j = ǫ U −j pc,j πE . lk li + U j=k k=1 By using the normalization condition, πE + U −1 j=0 πi,j K i=1 K = 1, we can get pc,j lk πE = 1 + ǫ 0.5(U + 1) 1 + i=2 k=1 −1 i−1 i−1 (4.10) . (4.11) j=k By assuming that terminals’ backoff processes are i.i.d., we can write the packet transmission success probability at the i-th backoff stage as K ps,i = Pr pi > β K nj pj + γ j=1 n0 +n1 +···+nK =M −1 (M − 1)! n πj,0j , π•n0 n0 !n1 ! · · · nK ! j=1 (4.12) in which π• denotes the probability that a terminal does not transmit a packet in a slot, i.e. π• = 1 − K j=1 πj,0 . Note that we have ps,1 = ps,2 = · · · = ps,K , if p1 = p2 = · · · = pK . We can now obtain the system throughput τ by nK n1 τ= n0 +n1 +···+nK =M i1 =0 ··· iK K (i1 + i2 + · · · + iK ) K j=1 M! n × π•n0 πj,0j = M n0 !n1 ! · · · nK ! j=1 nj ij nj −ij p p ij s,j c,j K ps,i πi,0 . (4.13) i=1 For the mean value of the packet retransmission delay (either successfully transmitted or dropped), we obtain the average backoff delay d by K−1 d = 0.5(U + 1) K−1 h li 1 + i=1 pc,j + 0.5(U + 1)lK , (4.14) h=i j=i 77 Chapter 4. Backoff Algorithm with Power Ramping in LTE in which we take it into consideration that 0.5(U + 1) slots are taken on average every backoff stage. Denote by Pd the packet dropping probability that a terminal drops the packet unsuccessfully transmitted after the K-th retransmission attempt. We can obtain Pd by Pd = pc,K πK,0 . (4.15) In addition, denote by p the average power consumption by a terminal. We obtain p by K p= K pi πi,0 / i=1 πi,0 . (4.16) i=1 The computational procedure is based on Brouwer’s fixed point theorem [69], which is as follows. We rewrite (4.11) and (4.12) respectively by (ℓ+1) πE (ℓ) (ℓ) (ℓ) F pc,1, pc,2 , · · · , pc,K−1 (ℓ) (ℓ+1) and (ℓ+1) Gi (πE pc,i ), (4.17) (ℓ) in which the superscript of πE and pc,j denotes the iteration index, ℓ = 0, 1, 2, . . . . By (0) (ℓ+1) setting pc,i = 0.5, we evaluate (4.17) iteratively until πE (ℓ) − πE < ε. It is noticeable that, for each ℓ, (M + K − 2)!/((K − 1)!(M − 1)!) evaluations on ps,i are needed in (4.12). The uniqueness of the solution in (4.17) can be guaranteed, if |∂F /∂πE | ≤ ν < 1. We check this in numerical evaluations on (4.17). We now evaluate the efficiency of the PR scheme compared to the system without PR. To this end, we define the throughput gain of the system with PR relative to the system without PR as τp (packets/slot/dBm) = (ˆ τ − τˇ)/(p − pR ), in which τˆ and τˇ denote τ of the system with PR and without PR based on (4.13), respectively. Furthermore, it has been shown that a system with a finite number of retransmissions is always stable in 78 Chapter 4. Backoff Algorithm with Power Ramping in LTE U M 20 30 40 15 50 60 70 60 25 70 6 0.0152 0.0116 0.0073 0.0040 0.0020 0.0006 0.0066 0.0053 Table 4.1: Throughput gain τp with β β (dB) 4 2 −1 −1.5 −2 0.0141 0.0387 −0.0440 −0.0301 −0.0320 0.0136 0.0348 −0.0015 0.0173 0.0230 0.0093 0.0225 0.0275 0.0466 0.0604 0.0046 0.0139 0.0311 0.0484 0.0633 0.0021 0.0073 0.0225 0.0385 0.0488 0.0012 0.0037 0.0154 0.0249 0.0353 0.0079 0.0228 0.0290 0.0504 0.0666 0.0061 0.0170 0.0313 0.0487 0.0647 −2.5 0.0622 0.0693 0.0999 0.0974 0.0723 0.0501 0.1107 0.0971 −3 0.0867 0.0764 0.1242 0.1239 0.0960 0.0707 0.1392 0.1285 Chapter 3, due to Pd in (4.15). Thus, we shall consider τ satisfying Pd ≤ 0.01 as a maximum achievable throughput of this system, or M satisfying Pd ≤ 0.01 as the maximally allowable M, denoted by M ∗ . 4.2.2 Correlation Coefficient on Backoff Process Finally, against the i.i.d assumption made in (4.12), we examine the correlation of M terminals’ backoff process via simulation. To this end, let bi denote the backoff stage of the i-th terminal every slot during a simulation. We set bi = 0 for the idle state and bi = j for the j-th backoff stage, i.e. j = 1, 2, . . . , K, respectively. As a time series, bi is collected for the i-th terminal during a simulation. Then we define the average correlation coefficient of a terminal’s backoff process to other terminals as 1 ̺= M(M − 1) M i=1 M E[(bi − E[bi ])(bj − E[bj ])] . V ar(bi ) V ar(bj ) j=1,j=i (4.18) in which V ar(x) denotes the variance of a random variable x, and we have −1 ≤ ̺ ≤ 1. For ̺ > 0, i.e., a positively correlated backoff process of M terminals, each terminal’s backoff process has a tendency to move up to higher backoff stage together with other terminals, or move back to the idle state together. For ̺ < 0, we expect that some terminals move 79 Chapter 4. Backoff Algorithm with Power Ramping in LTE Algorithm 4.1 - Terminal-Assisted Uniform Backoff Algorithm 1: 2: 3: 4: 5: 6: 7: 8: Initialize U0 = 20 (as an example) and broadcast it. Do the following at t = 1, 2, . . . . if Nt > 0 and Pt > 0 then t Ut = nint[(α Ut−1 + (1 − α) N1t N i=1 Wi )/sτ ]. else if Nt = 0 and Pt > 0 then Ut = min(nint[αu Ut−1 ], Umax ). else Ut = max(nint[αd Ut−1 ], Umin ). end if up to a higher backoff stage, while other terminals move back to the idle state. 4.2.3 Terminal-Assisted UB Algorithm (TAUBA) We now introduce TAUBA for the system with PR. To begin with, the symbols used in this algorithm are summarized below: - Wi : Waiting-time counter of the i-th terminal. - Ut : Window size of UB algorithm broadcasted by eNodeB at time t. - Nt : Number of packets successfully received at eNodeB at time t. - Pt : Total received powers of packets measured by eNodeB at time t. - sτ : Scaling factor of window size and sτ ≥ 1. - Umax (or Umin ): The maximum (or minimum) of window size. - α: Smoothing factor for Ut and 0 < α < 1. - αu : Increasing factor of Ut and αu > 1. - αd : Decreasing factor of Ut and 0 < αd < 1. 80 Chapter 4. Backoff Algorithm with Power Ramping in LTE In Algorithm TAUBA, the notation, nint[x], indicates the nearest integer function, which chooses the integer close to x. Every slot, eNodeB broadcasts Ut based on Algorithm TAUBA. Each terminal sets Wi = 0 for 1 ≤ i ≤ M, when it has no packet to send, or when its random access is terminated, either success or dropping a packet. Upon a packet arrival, the terminal conducts UB algorithm with Ut (randomly chooses a backoff counter between 0 and Ut ) and PR, while keeping on increasing its waiting-time counter by one at each slot. When the terminal (re)transmits its packet, it appends the waiting-time counter, Wi , to the packet. In practice, Wi can be appended to either RAP or Msg3. If eNodeB would receive the packet successfully, it can estimate the current backlog size by assuming that Wi from the packet successfully received would be proportional to the current backlog size. Note that more than one packet could be successfully received based on β in (4.3). Thus, if Nt > 1, eNodeB averages Wi over Nt . Additionally, we can use smaller window size than the actual backlog size for the system with Nt > 1 in order to allow more than one retransmissions. The 2nd and 3rd lines of Algorithm 4.1 reflect this. If the packet (re)transmission is not successful, say time t + ∆t, the terminal conducts UB algorithm with Ut+∆t in conjunction with PR. This is repeatedly done, until the terminal (K) would transmit the packet successfully or drops the packet after using pt . Therefore, Wi is a cumulative counter of summing up all the backoff counters used. Furthermore, every slot eNodeB measures the power of received packets so that it can detect heavily congested random channel, when Nt = 0 and Pt > 0. In this case, since eNodeB cannot have the information of Wi , it increases Ut by multiplying αu , which is expressed in the 4th and 5th lines. If Nt = Pt = 0, then eNodeB reduces its window size by multiplying αd , under the assumption that the random access channel becomes gradually idle. We explain in the next section how to select these parameters, α, αu , αd , sτ and so on. 81 Chapter 4. Backoff Algorithm with Power Ramping in LTE 1.1 35 1 30 0.8 25 0.7 0.6 0.5 d (slots) τ (packets/slot) 0.9 No PR, U = 10 (ana) U = 10 (ana) U = 15 (ana) 0.4 0.3 0.2 No PR, U = 10 (ana) U = 10 (ana) U = 15 (ana) U = 25 (ana) No PR, U = 10 (sim) U = 10 (sim) U = 15 (sim) U = 25 (sim) 20 15 U = 25 (ana) No PR, U = 10 (sim) U = 10 (sim) 10 U = 15 (sim) U = 25 (sim) 0.1 10 15 20 25 30 35 Number of terminals, M 40 5 10 45 15 (a) Throughput. 0.03 −87 U = 25 (ana) 45 U = 15 (ana) U = 25 (ana) U = 10 (sim) −87.5 U = 10 (sim) p (dBm) Pd 40 U = 10 (ana) U = 10 (ana) U = 15 (sim) U = 25 (sim) 0.015 U = 15 (sim) U = 25 (sim) −88 −88.5 0.01 −89 0.005 0 10 45 −86.5 No PR, U = 10 (ana) No PR, U = 10 (sim) 0.02 40 (b) Mean access delay. U = 15 (ana) 0.025 20 25 30 35 Number of terminals, M −89.5 15 20 25 30 35 Number of terminals, M 40 (c) Packet dropping probability. 45 −90 10 15 20 25 30 35 Number of terminals, M (d) Mean power consumption. Figure 4.1: The effect of power ramping and U on the system performance. 82 Chapter 4. Backoff Algorithm with Power Ramping in LTE 4.3 Numerical Studies We build a simulation program in MATLAB. Each simulation is carried out for 20000 slots and time-averaged. We set pR = −90 dBm, ∆p = 2 dB and ǫ = 0.095, unless otherwise stated. 1. Effect of SINR threshold: In Table 4.1, we examine τp against β with K = 5. The results in Table 4.1 are obtained by simulations. The validation of this simulation will be shown in Figs. 4.1(a)-4.2(d). In Table 4.1, some negative values imply that the system with PR is not better than that without PR. When M is increased, τp gradually dies out. We can improve τp by introducing larger U. We can see that PR is quite effective only when β ≤ −2.5 dB. In what follows, we set β = −3 dB in order to characterize the PR effect. 2. Effect of PR and U : In Figs. 4.1(a)-4.1(d), we examine the effect of PR and U on the system performances by comparing it with the system without PR. We set l1 = 1 and li = 0 for 2 ≤ i ≤ K and K = 4. While τ , M ∗ and d can be improved by PR as shown in Figs. 4.1(a)-4.1(c), more power consumption is needed as shown in Fig. 4.1(d), e.g. about 3.3 dBm at M ∗ = 34 in Fig. 4.1(d). Note that the terminals without PR always consume −90 dBm. When we increase U in the system with PR, we can see that larger U improves p and Pd significantly without significant increase of d. Moreover, U should be dynamically controlled, since larger U reduces τ and increases d for small M in Figs. 4.1(a) and 4.1(b). 3. Initial transmission power selection based on a PMF: In Figs. 4.2(a)-4.2(d), we consider a random transmission power selection scheme based on 1) Exponential decreasing selection (ES): li = 2−(i−1) l1 for 2 ≤ i ≤ K and 2) Uniform selection (US): li = 1/K for 1 ≤ i ≤ K for K = 4 and U = 15. It is shown that τ seems insensitive to the PMF of selecting initial transmission power in Fig. 4.2(a). The higher the probability of selecting 83 Chapter 4. Backoff Algorithm with Power Ramping in LTE 1.2 28 26 1.1 24 22 0.9 d (slots) τ (packets/slot) 1 0.8 20 18 16 0.7 14 l1 = 1 (ana) ES (ana) US (ana) l1 = 1 (sim) ES (sim) US (sim) 0.6 0.5 10 l1 = 1 (ana) ES (ana) US (ana) l1 = 1 (sim) ES (sim) US (sim) 15 20 25 30 35 Number of terminals, M 40 12 10 8 10 45 15 (a) Throughput. 0.018 0.016 0.014 40 45 (b) Mean access delay. −85.5 l1 = 1 (ana) ES (ana) US (ana) l1 = 1 (sim) ES (sim) US (sim) −86 −86.5 −87 p (dBm) 0.012 −87.5 Pd 0.01 0.008 −88 0.006 −88.5 0.004 −89 0.002 −89.5 0 10 20 25 30 35 Number of terminals, M 15 20 25 30 35 Number of terminals, M 40 (c) Packet dropping probability. 45 −90 10 l1 = 1 (ana) ES (ana) US (ana) l1 = 1 (sim) ES (sim) US (sim) 15 20 25 30 35 Number of terminals, M 40 45 (d) Mean power consumption. Figure 4.2: The effect of the initial transmission power selection on the system performance. 84 Chapter 4. Backoff Algorithm with Power Ramping in LTE 0.14 ǫ = 0.095, U = 10 ǫ = 0.095, U = 20 ǫ = 0.125, U = 10 No PR, K = 100 Correlation coeﬃcient, ̺ 0.12 0.1 ǫ = 0.125, U = 10 0.08 0.06 0.04 0.02 0 10 20 30 40 50 Number of terminals, M 60 70 Figure 4.3: The correlation coefficient of M terminals’ backoff process. pK , the lower d, the higher Pd and the higher p we observe especially for large M. In comparison with the improvement of τ and d, Pd and p in ES and US might be too much sacrificed. Although we do not depict the results for the saturated case, i.e., ǫ → 1, the behaviours based on the PMFs shown in Figs. 4.2(a)-4.2(d) are preserved. 4. Correlation: Fig. 4.3 depicts ̺ for K = 5 when PR is used. For the case without PR, we use ǫ = 0.125 and U = 10 and set K = 100 as the maximum number of retransmissions. It is found that each terminal’s backoff process is positively correlated, i.e., ̺ > 0. When PR is used, ̺ dies out as M increases, which is caused by packet dropping after failure of the K-th retransmission. Compared to U = 10, larger U = 20 makes ̺ lower for ǫ = 0.095, which means that larger U reduces collisions. When a large number of retransmissions are allowed (K = 100), ̺ becomes relatively higher than the cases with K = 5. However, we can see that ̺ does not exceed 0.135, which indicates that the backoff processes are very weakly correlated. Fig. 4.3 explains why our analysis based on i.i.d assumption agrees well with simulations. 5. TAUBA: In this example, we use K = 5, β = −3 (dB), ǫ = 0.075 and U0 = 10. For 85 Chapter 4. Backoff Algorithm with Power Ramping in LTE 70 1.2 U = 10 U = 20 U = 30 TAUBA 60 1 d (slots) τ (packets/slot) 50 0.8 0.6 0.4 40 30 20 0.2 0 10 U = 10 U = 20 U = 30 TAUBA 20 30 40 50 60 Number of terminals, M 10 70 0 10 80 (a) Throughput comparison. 30 40 50 60 Number of terminals, M 70 80 (b) Mean access delay comparison. 4 10 −85 −86 3 10 p (dBm) Variance of access delay 20 2 10 −87 −88 1 10 TAUBA U = 10 U = 20 U = 30 0 10 10 20 30 40 50 60 Number of terminals, M 70 U = 10 U = 20 U = 30 TAUBA −89 80 (c) Variance of access delay comparison. −90 10 20 30 40 50 60 Number of terminals, M 70 80 (d) Mean power consumption comparison. Figure 4.4: Performance of TAUBA against some static UB algorithms. 86 Chapter 4. Backoff Algorithm with Power Ramping in LTE the paratmeters of TAUBA, we set α = 0.95 and αd = 0.95 by assuming that the backlog size of this system slowly varies over time. When eNodeB observes Nt = 0 and Pt > 0 in some consecutive slots and use αu ≥ 2, some terminals just joining the ongoing contentions unexpectedly could have very large window size compared to actual backlog size. On the other hand, if we use αu close to one, the ongoing (congested) contentions may not be easily resolved. To avoid this, we use αu = 1.25. As we have seen that the maximum throughput of this system is close to 1.05 in Fig. 4.1(a), we set sτ = 1.05. Finally, we set Umin = 2 and Umax = 256, which implies that 8 bits are enough to describe Wi and Ut . For convenience, in Fig. 4.4(a) we call the range of population sizes before τ reaches the maximum, e.g., 10 ≤ M ≤ 40 for U = 20, the lightly loaded region; otherwise the heavily loaded region. Compared to static UB algorithms that use fixed values of U = 10, 20 or 30, TAUBA maximizes τ very close to the maximum (1.05) in the heavily loaded region, while τ of static UB algorithms decreases and goes to zero as M increases. Over the lightly loaded region, TAUBA improves τ compared to the static UB algorithms. For d and dv , TAUBA minimizes them in the lightly loaded region, while d and dv of TAUBA approach to the maxima of ds and dv s for the static UB algorithms in the heavily loaded region in Figs. 4.4(b) and 4.4(c). Note that these static UB algorithms with U = 10, 20 and 30, respectively, yield Pd = 0.023, 0.00927 and 0.0023 at M = 80 with delay performances shown in Figs. 4.4(b) and 4.4(c), while TAUBA achieves Pd < 10−5 for 10 ≤ M ≤ 80. In Fig. 4.4(d), we can see that TAUBA minimizes the mean power consumption in the heavily loaded region, while it consumes more power in the lightly loaded region. The use of different ǫ values does not change the performance behaviours of TAUBA as shown in Fig. 4.4(a)-4.4(d). In conclusion, based on very low Pd and the minimal use of p, it is conjectured that the window size of the first or possibly the second backoff stage of TAUBA is optimized to maximize τ particularly in the heavily loaded region. 87 Chapter 4. Backoff Algorithm with Power Ramping in LTE 4.4 Summary In this chapter we has examined the PR scheme with UB algorithm in LTE in conjunction with initial power transmission selection based on some PMFs, by assuming that uplink pathloss estimation is perfect. We have evaluated the performance of this system based on i.i.d assumption on M terminals’ backoff processes and compared it to simulation. The good agreements between analysis and simulation has been explained by weak positive correlation among M terminals’ backoff processes due to the retransmission limit built in the PR scheme. It is also shown that the PR scheme is effective, when the SINR threshold is less than −2.5 dB. In the PR scheme, throughput and delay are improved, while more terminals without violating Pd < 0.01 can be allowed at the cost of a higher average transmission power. In the probabilistic initial transmission power selection schemes given, τ is insensitive to the PMFs of selecting initial transmission power. Further, increasing the probability of selecting the highest power can increase Pd , while reducing d. Therefore, the LPFT is the most efficient one with respect to Pd and p. In the presence of the PR scheme, it is also needed to control U dynamically in order to maximize τ according to the number of backlogged terminals. To this end, we have proposed TAUBA, which estimates the backlog size based on terminals waiting-time counters and takes throughput gain by PR into account. By simulations, we have shown that TAUBA improves the system throughput close to its maximum and minimizes mean access delay and packet dropping. 88 Chapter 5 Queueing Performance of Multichannel ALOHA Systems Various Internet services, such as Web-browsing with rich and multimedia-embedded contents, networked gaming, interactive multimedia and telemedicine, have been gradually deployed over various wireless networks, e.g., IEEE 802.11 WLANs, UMTS, LTE and IEEE 802.16 WiMAX systems. Moreover, recent innovative advances of smart-phones and tablet personal computers have accelerated the emergence of new services, e.g., locationbased service. Such services are mostly carried by Web-browsing, which is emerging as one of the most widely used data applications over wireless and wireline networks [70]. It is well known that the traffic characteristics of Web-browsing depend on user behaviour, type of Web-browsers, interaction of the Transmission Control Protocol (TCP) senders and receivers, and versions of the Hyper-Text Transfer Protocol (HTTP), and exhibit long-range dependency [70][71][72]. These might make it difficult to develop a unifying source traffic model for evaluating the performance of wireless access networks. In this chapter, we consider uplink traffic in a wireless access system due to Web-browsing, generated by HTTP over TCP from the client in the mobile device to the Web-server in the fixed network. In this scenario, the uplink traffic generated at mobile terminals mostly consists of main/inline object requests and TCP Acknowledgements (ACKs) as shown in Fig. 5.1. It is shown that TCP SYN and Web-request are generated at the moments that the user initiates Web-browsing or requests an object, while most of TCP ACKs are 89 Chapter 5. Queueing Performance of Multichannel ALOHA Systems generated when main/inline objects are being downloaded. Once downloading of objects is completed, the user reads those objects and no uplink traffic is generated during this time, until the user initiates a new Web-request. This observation indicates that the Poisson or independent source model might not be suitable for modelling uplink traffic of Web browsing [71][73] especially in performance studies of random access protocols of wireless systems. Recently IEEE 802.11 WLANs have been widely deployed in hotspots to provide public Internet access. However, there is a growing demand for not only more bandwidth but anywhere always-on connectivity to the Internet. IEEE 802.16 systems and LTE are candidate solutions to meet such a demand. Particularly, the uplink access procedure in both IEEE 802.16 systems and LTE employs demand-assignment multiple access, in which a terminal transmits an orthogonal random access preamble in order to get an uplink channel where uplink bandwidth requests could be sent later. After the terminal receives a grant for an uplink bandwidth request, it could transmit actual data packets. However, due to such a 4-way handshake, TCP ACK transmissions are expected to suffer from long delays [74]. In order to improve the bandwidth request mechanism, IEEE 802.16 system employs a polling mechanism to solicit for uplink bandwidth request [30], while LTE adopts a dedicated scheduling request channel in which time-synchronized terminals are periodically scheduled for uplink bandwidth request transmissions [6][75][76]. However, uplink packets from Web-browsing, e.g., TCP SYN, Web-request and TCP ACKs, have very short lengths (e.g., small IP packet of 40 bytes), which makes it inefficient to employ the demand assignment multiple access procedure as described above to request bandwidth for each packet. Instead, it may be desirable to send these packets directly over the RACHs without adding to the traffic load of these channels. In this chapter, we consider uplink packet transmissions for Web-browsing (client to 90 Chapter 5. Queueing Performance of Multichannel ALOHA Systems Inline object Inline object ACK Inline object Main object TCP-SYN & Web-server Terminal (client) TCP-ACK TCP-ACK TCP-ACK TCP-ACK HTTP Reques t TCP-ACK HTTP Reques t TCP-SYN Base station Reading time ON period OFF period Figure 5.1: An uplink traffic model of Web-browsing. server traffic in Fig. 5.1) over the RACHs of LTE. Our investigation focuses on the contention resolution mechanism applied to the orthogonal random access preambles. Thus, our work will help the performance estimation of delivering delay-tolerant Webtraffic by random access in LTE. To capture the behaviours of the RACHs of LTE [6], which employ CDMA-OFDMA, we model the RACHs as a multichannel S-ALOHA system under the perfect orthogonality condition among random access preambles. We model the uplink traffic from Web-browsing by an N-state MMBP whose parameters could be matched to measured traffic [77][78]. While the uplink traffic statistics might depend on downlink traffic and user behaviour, this study focuses on the uplink MAC only, and the MMBP traffic model allows the effects of correlations between uplink packet arrivals on the MAC performance to be investigated. For more realistic system modelling, we also consider the collision resolution algorithm standardized in LTE [6], i.e., the UB algorithm with retry limit, operating in multi-buffered terminals, which have a finite queue size to buffer a number of uplink packets. There is a long research history of queuing studies on S-ALOHA systems with multi- 91 Chapter 5. Queueing Performance of Multichannel ALOHA Systems buffered terminals, even in conjunction with information-theoretical perspective [79][80] (and references therein). Since the evolution of terminals’ queuing processes over time is coupled with each other, analytical models, even approximate ones, which have been developed so far have mostly suffered from the curse of dimensionality. As good approximations, there are some analytical queuing models for multi-buffered terminals in S-ALOHA systems in [81][82][83]. However, none of these models considers correlated traffic arrivals or window-based backoff with retry limit. On the other hand, queuing models for multibuffered terminals have been developed [50][84][85] for IEEE 802.11 WLANs employing CSMA with collision avoidance (CSMA/CA) with binary exponential backoff. While previous work has mainly focused on constructing and validating queuing models, the impacts of retry limit or correlated traffic arrivals on the system performance have not been explored. Internet traffic like HTTP has been taken into account in the performance studies of multi-buffered terminals in IEEE 802.11 WLANs [86][87][88]. However, these queuing studies focus on the interaction between TCP senders and receivers, and assume infinite queue size and unlimited retransmissions. In contrast, our work takes into account of finite queue size, retry limit, and correlated traffic arrivals. In addition to these queuing studies [50][81][82][83][84][85], ALOHA systems with source traffic having long-range dependency have been examined in [89][90][91]. These studies commonly concluded that ALOHA systems with Poisson traffic arrivals show worst system performance than those with traffic having long-range dependency, which is contradictory to earlier results found in conventional queuing systems [92]. Note that the work in [89][90][91] is based only on simulations and does not consider the dynamics of windowbased backoff algorithms. In contrast to previous work, the main contributions of our work are summarized as follows : 1. We model the queuing process of multichannel S-ALOHA access with UB and retry 92 Chapter 5. Queueing Performance of Multichannel ALOHA Systems limit, and evaluate system performance in terms of system throughput, queue length and delay, probabilities packet dropping due to retry limit and packet blocking due to finite queue size, and mean and variance of packet retransmission time with respect to the degree of arrival correlation, number of channels, retry limit and uniform window size. Results are applicable to Web-browsing with uplink packets transmitted over the RACHs. 2. In contention resolution using UB in single-buffered terminals, it is known [15] that performance is optimized by dynamically changing the window size according to the number of backlogged terminals. We present simulation results to show that this optimization could not be applied to the system with multi-buffered terminals and correlated arrivals, in which case some fixed window size shows better performance. 5.1 5.1.1 System Model Uplink Traffic Source Model An N-state MMBP Model As previously mentioned, Web-browsing generates TCP-SYNs, Web-requests and TCP ACKs over the wireless uplink, as shown in Fig. 5.1. Note that the number of TCP ACKs depends on the amount of main/inline objects downloaded over downlink in conjunction with maximum transmission unit and the delayed ACK option. In addition, multiple TCP connections can be established during one HTTP session [70][71], or multiple Web-browsing sessions can be initiated by a user. Furthermore, parsing time could be considered between main and the first inline object downloading, which affects inter-arrival times between TCP ACKs generated during this ON period. On the other hand, no uplink traffic is generated when the user is reading the downloaded objects during the OFF period, which depends 93 Chapter 5. Queueing Performance of Multichannel ALOHA Systems on user-behaviour. Due to these conditions, it is not easy to draw meaningful statistical data from measurements on uplink traffic to characterize it. Without loss of generality, we assume that an N-state MMBP can capture the ON-OFF alternating behaviour of Web browsing shown in Fig. 5.1. Note that the parameters of a two-state MMBP have been matched to measured traffic data in [77][78] and references therein. Denote the underlying state transition matrix of an MMBP at every slot boundary by Q. The element of Q in the i-th row and the j-th column, denoted by qij for 0 ≤ i, j ≤ N −1, indicates the state transition probability from the i-th state to the j-th state. In each state, say the i-th state, a packet is generated by a Bernoulli trial with probability ǫi . Let row vector β denote the stationary state probability of this MMBP. It satisfies β = β · Q and β · eT = 1, in which e is a unit row vector, and T denotes a vector or matrix transpose. Throughout this chapter, the length of e conforms to the corresponding matrix or vector, which makes a matrix or vector product possible. Let diag[ǫi ] denote a diagonal matrix with elements ǫi for 0 ≤ i ≤ N − 1. Then, the mean and variance of the number of packets generated by this MMBP can be obtained by ǫ = e · diag[ǫi ] · β T and σǫ2 = ǫ(1 − ǫ), respectively. For characterization of the second order statistics of an MMBP, we consider the autocorrelation function of the number of packet arrivals. Denote by a(m) ∈ [0, 1] the number of packets generated at the m-th slot and by s(m) the source state at that slot, respectively. Then we can write the normalized auto-correlation function of the number of packet arrivals of MMBP as RN (n) = 1 E σǫ2 a(m+n) − ǫ a(m) − ǫ = 1 E a(m+n) a(m) − ǫ2 . 2 σǫ (5.1) where E[x] denotes the expectation of random variable x. We can write E a(m+n) a(m) for 94 Chapter 5. Queueing Performance of Multichannel ALOHA Systems n ≥ 1 by N −1 N −1 (m+n) (m) R(n) = E a a 1 1 = i=0 j=0 k1 =0 k2 =0 k1 k2 Pr a(m+n) = k2 |s(m+n) = j × Pr[a(m) = k1 |s(m) = i]Pr[s(m+n) = j|s(m) = i]Pr[s(m) = i] N −1 N −1 ǫj ǫi Pr[s(m+n) = j|s(m) = i]Pr[s(m) = i] = i=0 j=0 N −1 N −1 = i=0 j=0 ǫi ǫj q˜ijn βi = β · diag[ǫi ] · Qn · diag[ǫi ] · eT , (5.2) in which q˜ijn is the i-th row and the j-th column element of the n-step state transition probability matrix Qn . For n = 0, we can get N −1 N −1 1 2 R(0) = (m) k Pr[a = k|s (m) = i]Pr s (m) =i = i=0 k=0 ǫk βk , (5.3) k=0 which leads to RN (0) = 1. For simplicity of illustration, consider a two-state MMBP, with β0 = (1 − q11 )/(2 − q00 − q11 ) and β1 = 1 − β0 . In addition, we obtain the probability that a source is in the i-th state for n slots, ζi (n), and its mean, ti , for i = 0, 1 respectively by ζi (n) = piin−1 (1 − pii ) and ti = 1/(1 − pii ) (5.4) Particularly for an ON-OFF source (ǫ0 = 0 and ǫ1 = 0) as a special case, we can respectively characterize RN (n) and R(n) for n ≥ 1 by RN (n) = c · ω n and R(n) = ǫ2 + ǫ(ǫ1 − ǫ)ω n (5.5) where c = ǫ(ǫ1 − ǫ)/σǫ2 and ω = p00 + p11 − 1. If ǫ1 = 1, i.e., a packet is always generated 95 Chapter 5. Queueing Performance of Multichannel ALOHA Systems every slot during ON-state, we have simply RN (n) = ω n . Thus, for this two-state ON-OFF source, ω plays a key factor in characterizing the correlation on packet arrivals. Long-Range Dependence (or heay-tailed distribution) in TCP traffic model The long range dependence of a stochastic (or traffic) process can be characterized by its autocorrelation function (R(n)) as [93] R(n) = ς · n−κ for n → ∞ and 0 < κ < 1 (5.6) where ς > 0 is a constant. Compared to the short range dependency which decays exponentially as shown in (5.2), this decays hyperbolically. In [94] Andersen and Nielsen show how to construct a traffic with long-range dependence by superposing four 2-state Markov Modulated Poisson Processes (MMPPs) [95]. In the following queueing model in Section 5.2.2, MMPP traffic model can be easily incorporated. Due to MMBP traffic model, our queueing process is a block-structured Quasi-Birth-Death (QBD) process. However, our queueing process with MMPP traffic model becomes a blocked-structured M/G/1 type queue (or MMP P/G/1 queue), to which the block Gauss-Seidel iteration described later can be also applied with some modifications in order to obtain the stationary state probability, or the algorithm in [96] can be used. 5.1.2 Access Protocol and Backoff Algorithm This chapter also considers the random access protocol and the UB algorithm given in Section 1.1 and Section 3.2.1. The packet transmission success probability denoted by ps is also given in Section 3.2.1. 96 Chapter 5. Queueing Performance of Multichannel ALOHA Systems 5.2 5.2.1 Queueing Performance Evaluation Approximation on Correlated Multi-queue Let qi denote the queue size of the terminal i among M terminals in steady state. Assume that the arrival process and the backoff process for all terminals are identical. Suppose the joint probability that the queue size of k terminals selected from M terminals is greater than 0. Based on i.i.d. assumption on terminals’ queueing processes, this can be approximately written by M!/(k!(M − k)!)(Pr[qi > 0])k (1 − Pr[qi > 0])M −k , in which any terminal can be the i-th terminal. This is always less than or equal to the exact joint probability. In what follows, our analysis is based on the i.i.d assumption that leads to the RHS. However, in Section 5.3 we examine the correlation of M terminals’ queueing processes as follows. (t) Denote by qi a time series of queue length of the i-th terminal collected every slot during a simulation. Then, we measure the correlation coefficient ̺ over M terminals’ queueing process as 1 ̺= M(M − 1) M M i=1 j=1,j=i E (t) (t) qi − E qi Var (t) qi (t) (t) qj − E qj Var (t) qj . (5.7) For ̺ > 0 each terminal’s queue would increase or decrease together. For ̺ < 0 some of terminal’s queue would decrease, while the rest of them would increase. If our analysis might agree well with simulation, it can be said that the correlation of the queueing process is so weakly correlated. In addition, we have discussed the stability condition of multi-buffered terminals in an S-ALOHA system in Chapter 1. Due to finite buffer size, this system always satisfies (1.6). We also have seen the bistability of single-buffered terminals in an S-ALOHA system. If the system with multi-buffered terminals would have bistability, the probability that k out 97 Chapter 5. Queueing Performance of Multichannel ALOHA Systems of M terminals’ queue are not empty might have a bimodal distribution. As long as the analysis based on i.i.d. assumption agrees well with simulations, we can conjecture that this probability can be approximated by M!/(k!(M − k)!)(Pr[qi > 0])k (1 − Pr[qi > 0])M −k , which means no bistability in the S-ALOHA system with multi-buffered terminals. 5.2.2 Multi-buffered Terminals The state space of the queue in a given terminal can be described by {(k, j, i, u) : 0 ≤ k ≤ K, 0 ≤ j ≤ J − 1, 0 ≤ i ≤ N − 1, 0 ≤ u ≤ U − 1}, in which k, j, i and u respectively denote the number of packets in the queue, the j-th retransmission attempt, the i-th source traffic state and the u-th backoff counter in the terminal. Denote by ϕk = [ϕk,j,i,u] for 1 ≤ k ≤ K, 0 ≤ j ≤ J − 1, 0 ≤ i ≤ N − 1 and 0 ≤ u ≤ U − 1 the row vector of stationary state probability that at an arbitrary slot boundary a terminal has k packets in its queue, its backoff counter is at the u-th state, it is making the j-th retransmission attempt, and its traffic source is in state i. In each ϕk , ϕk,j,i,u is lexicographically ordered. Additionally, row vector ϕ0 = [ϕ0,i ] denotes the stationary probability that a terminal has no packet in its queue. The subscript i of ϕ0,i denotes the i-th source state for 0 ≤ i ≤ N − 1. For K ≥ 2, we can write a set of state balance equations for ϕk for 0 ≤ k ≤ K as follows: ϕ0 =ϕ0 Qb + ϕ1 C and ϕ1 = ϕ0 F + ϕ1 B + ϕ2 D, (5.8) for 2 ≤ k ≤ K − 1, (5.9) ϕk =ϕk−1 A + ϕk B + ϕk+1 D K ϕK =ϕK−1A + ϕK Ba ϕk eT = 1. T and ϕ0 e + (5.10) k=1 For K = 1, we have ϕ0 = ϕ0 Qb + ϕ1 C and ϕ1 = ϕ0 F + ϕ1 Ba (5.11) 98 Chapter 5. Queueing Performance of Multichannel ALOHA Systems where the matrix Qb is expressed by Qb = (I − diag[ǫi ]) · Q. (5.12) In the above, I denotes an identity matrix whose size conforms to that of diag[ǫi ]. The matrix Qb indicates the state transitions of a traffic source without a packet arrival. We can write an NJU × N matrix C in (5.8) as C= C0T C0T · · · C0T C1T T (5.13) J−1 where C0 and C1 are respectively given by C0 = Qb ⊗ cT0 and C1 = Qb ⊗ cT1 (5.14) and ⊗ denotes the Kronecker product of two matrices or of a matrix and a vector. The row vectors c0 and c1 of U elements can be expressed as c0 = [ps 0 0 · · · 0] and c1 = [1 0 0 · · · 0]. (5.15) For J = 1, we have C = C1 . In (5.14), C0 indicates the state transition of a traffic source with a successful packet transmission, while successful and unsuccessful packet transmissions are included in C1 . The N × NJU matrix F in (5.8) can be written as F = Qa ⊗ a 0 0 · · · 0 (5.16) J−1 where 0 denotes a zero matrix of N × NU size. Throughout this chapter, 0 denotes a block matrix of all zeros, whose size is appropriately chosen. The matrix Qa and the row vector 99 Chapter 5. Queueing Performance of Multichannel ALOHA Systems a can be expressed by Qa = diag[ǫi ] · Q and a = [1/U 1/U · · · 1/U] (5.17) where Qa denote the state transitions of a traffic source with a packet arrival. Before describing the matrices B, Ba , D and A, we define ζa,0 , ζa,1 , ζa,2 , ζb,0 , ζb,1 and ζb,2 as ζa,0 = Qa ⊗ θ0 , ζa,1 = Qa ⊗ θ1 , ζa,2 = Qa ⊗ θ2 ζb,0 = Qb ⊗ θ0 , ζb,1 = Qb ⊗ θ1 , ζb,2 = Qb ⊗ θ2 , and (5.18) in which θ0 , θ1 and θ2 are U × U matrices respectively given by 0 1 θ0 = 0 .. . 0 0 ··· ··· 0 p /U c 0 0 · · · · · · 0 1 0 · · · 0 , θ1 = 0 . .. .. . · · · .. . 0 0 1 0 0 · · · · · · pc /U ··· ··· 0 ··· ··· 0 .. . ··· ··· 0 0 0 (5.19) and θ2 = ps /U · · · · · · ps /U 0 ··· ··· 0 0 .. . ··· ··· 0 .. . 0 ··· ··· 0 0 0 . (5.20) We shall explain the physical meaning of the matrices in (5.18) below, while construct- 100 Chapter 5. Queueing Performance of Multichannel ALOHA Systems ing B, Ba , D and A matrices. We can write B as ζ + ζb,0 ζb,1 0 · · · a,2 ζa,2 ζb,0 ζb,1 0 ζ 0 ζb,0 ζb,1 a,2 .. .. B= . . 0 0 .. .. . . 0 0 ··· ζa,2 ζa,1 + ζa,2 0 0 0 ··· ··· ··· ··· ··· ··· 0 ··· ··· .. . 0 ··· .. . 0 ··· ··· 0 ζb,0 ··· ··· 0 0 0 0 , 0 0 ζb,1 ζb,0 (5.21) which indicates the state transition from k to itself, caused by events including backoff counter’s decrement without a packet arrival (ζb,0 ), successful transmission with a packet arrival (ζa,2 ), transmission failure without a packet arrival (ζb,1 ), transmission failure with a packet arrival at the last retransmission stage (ζa,1 ). When J = 1, we have B = ζb,0 + ζa,1 + ζa,2 . Next, the matrix D can be expressed as ζb,2 ζb,2 D= ζb,2 .. . ζb,1 + ζb,2 0 0 ··· ··· 0 0 0 · · · · · · 0 0 0 · · · · · · 0 . .. . · · · .. 0 0 ··· 0 0 (5.22) which represents the state transition from k + 1 to k packets in the queue, caused by one of the following events: a successful transmission without a packet arrival (ζb,2 ), or packet dropping upon L retransmissions (ζb,1 + ζb,2 ). For J = 1, we have D = [ζb,1 + ζb,2 ]. 101 Chapter 5. Queueing Performance of Multichannel ALOHA Systems Computational Procedure: (0) 1. Set ps = 0.5, do the following for ν = 1, 2, · · · . (a) : Construct the matrices, B, Ba , F , Qb , A and D. (0) (0) (b) : Set the initial probabilities, ϕ0 = ϕk = ((KJU + 1)N)−1 for 1 ≤ k ≤ K. (c) : For l = 1, 2, · · · , compute via block Gauss-Seidel iteration, using (5.24). (l+1) (l) Stop if ϕ0,i − ϕ0,i < εϕ for 0 ≤ i ≤ N − 1. (ν+1) (d) : Compute ps using (3.2) by substituting pr obtained from (5.26). (ν+1) (ν) (ν+1) 2. Stop if ps − ps < εp . Otherwise, go to (a) with ps . Finally, we can write the matrix A as ζ ζ 0 ··· a,0 a,1 0 ζa,0 ζa,1 0 0 ζa,0 ζa,1 0 . A = .. 0 0 ζa,0 . .. . . . 0 0 0 0 ··· ··· ··· ··· 0 ··· ζa,1 · · · .. . ··· ζa,0 0 0 0 0 0 ζa,1 ζa,0 (5.23) which represents the state transition from k to k + 1 packets in the queue, which is caused by one of the following events: backoff counter’s decrement with a packet arrival (ζa,0 ), or an unsuccessful transmission with a packet arrival (ζa,1 ). If J = 1, we have A = ζa,0 + ζa,1 . Finally, we have Ba = B + A. In order to obtain ϕk , we transform (5.8)-(5.10) into a block Gauss-Seidel iteration form 102 Chapter 5. Queueing Performance of Multichannel ALOHA Systems [97] as follows: (l+1) = ϕ1 C (I − Qb )−1 , (l+1) = ϕ0 (l+1) = ϕk−1 A + ϕk+1D (I − B)−1 (l+1) = ϕK−1 A (I − Ba )−1 . ϕ0 ϕ1 ϕk ϕK (l) (l+1) (l) F + ϕ2 D (I − B)−1 , (l+1) (l) (5.24) for 2 ≤ k ≤ K − 1 (l+1) For K = 1 we have (l+1) ϕ0 (l) (l+1) = ϕ1 C (I − Qb )−1 and ϕ1 (l+1) = ϕ0 F (I − Ba )−1 . (l+1) In (5.24) and (5.25), normalization is needed at each iteration l, i.e., ϕk η = (l+1) T K e . k=0 ϕk (5.25) (l+1) = ϕk /η and We are now in a position to obtain pr and ps . The retransmission probability pr can be expressed as K J−1 N −1 pr = ϕk,j,i,0. (5.26) k=1 j=0 i=0 which can be substituted back into (3.2). One can obtain the stationary probability ϕk by the computational procedure at the top of this page. As performance metrics, denote the mean number of packets buffered in a terminal and the waiting time of a packet by L and D, respectively. We can obtain K k ϕk eT . L= (5.27) k=1 103 Chapter 5. Queueing Performance of Multichannel ALOHA Systems By Little’s result, we can also obtain D by D= L (1 − PB )ǫ (5.28) which indicates the average delay of packets either successfully transmitted or dropped by retry limit. Denote the probability of packet dropping due to retry limit and the probability of packet blocking due to a full queue by PD and PB , respectively. Then, the total packet loss probability PL is given by PL = PD + PB , (5.29) in which the packet dropping probability PD is obtained by K N −1 P D = pc ϕk,J−1,i,0, (5.30) k=1 i=0 and the packet blocking probability PB is given by J−1 N −1 U −1 ϕK,j,i,u. PB = (5.31) j=0 i=0 u=0 The unnormalized system throughput τ (packets/slot) can be obtained by M n kΛ(k|n, P )Ω(n, M, pr ). τ= (5.32) n=0 k=0 We then obtain normalized throughput for this channel τ N (packets/slot/code) by τ N = τ /P . Finally we examine the mean busy period, B, which is the average time period from the time that a packet arrives at an empty queue to the time that the queue becomes 104 Chapter 5. Queueing Performance of Multichannel ALOHA Systems empty again. It is given by [98] B= x 1−ρ (5.33) where x and ρ are the mean packet service time and the system utilization, i.e. ρ = 1−ϕ0 eT . In order to obtain x, we denote by xk the probability that it takes k slots for a terminal to transmit a packet. Further we define a matrix S of size JU × JU for J ≥ 2 as θ θ 0 ··· 0 1 0 θ0 θ1 0 S= 0 0 θ0 θ1 .. .. . . 0 0 0 0 ··· 0 ··· 0 ··· 0 ··· 0 . ··· 0 0 θ0 (5.34) As shown in (5.34), S consists of the main and upper block-diagonal matrices, θ0 and θ1 , respectively. Other elements are all zeros. For J = 1, we have S = θ0 + θ1 . Due to DFT protocol, we have x1 = 0. We can write xk for k ≥ 2 as xk = as · S k−2 · cTs , (5.35) in which as and cs are respectively given by JU as = [ 1/U · · · 1/U 1/U 0 0 · · · 0 0 ] and cs = [ c0 c0 · · · c0 c1 ]. U (5.36) J−1 For J = 1, these U element vectors are modified as follows: as = [1/U 1/U . . . 1/U] and cs = [1 0 0 . . . 0]. One can obtain the generating function of xk as X(z) = ∞ k k=2 xk z = 105 Chapter 5. Queueing Performance of Multichannel ALOHA Systems P P P P P P P P P P τ (packets/slot) 1.2 1 0.8 = = = = = = = = = = 1 2 2 3 3 1 2 2 3 3 9 (a) (a) (a) (s) (s) (s) (s) (s) (s) (s) 8 7 q (packets) 1.4 0.6 τN 6 P P P P P P = = = = = = 1 2 3 1 2 3 (a) (a) (s) (s) (s) (s) 5 4 3 0.4 2 0.2 0 0 1 0.02 0.04 0.06 ǫ1 0.08 0.1 0 0 0.12 0.02 (a) Throughput. 0.35 0.3 0.25 0.04 0.06 ǫ1 0.08 0.1 0.12 (b) Mean queue length. P P P P P P = = = = = = 1 2 3 1 2 3 (a) (a) (s) (s) (s) (s) PL 0.2 0.15 0.1 0.05 0 0 0.02 0.04 0.06 ǫ1 0.08 0.1 0.12 (c) Packet loss probability. Figure 5.2: Effect of multichannel on multi-buffered system, p00 = 0.85, p11 = 0.65, U = 25, J = 3, K = 10. 106 Chapter 5. Queueing Performance of Multichannel ALOHA Systems z 2 a (I − zS)−1 c. Then we have x = X ′ (1) = a (I − S)−1 2I + S(I − S)−1 c. 5.2.3 (5.37) Single-buffered Terminals In this part we consider a system, in which a terminal can hold only one packet for transmission. A packet is generated by an MMBP as well, but only when a terminal is in the idle state. Intuitively, since packet arrivals are correlated only in the idle state, this system’s behaviour is identical to the system with an independent source whose average number of packet arrivals per slot is equal to that of MMBP. However, for comparison with the system with K = 1 previously introduced in Section 5.2.2, we deal with this system as follows: Denote by ϕ0 = [ϕ0,i ] and ϕ1 = [ϕ1,i,j,u] respectively the stationary state probability vector that a terminal has no packet in the i-th source state, and that a terminal is retransmitting a packet at the u-th backoff counter of the j-th retransmission attempt in the i-th source state. Define Qc and Qs by Qc = Q ⊗ cTs and Qs = Q ⊗ S (5.38) where cs is given by (5.36). Note that Qc and Qs describe the state transition of traffic source and packet retransmission process, while excluding the event of a packet arrival. Then, this system satisfies the following set of state balance equations: ϕ0 = ϕ0 Qb + ϕ1 Qc and ϕ1 = ϕ0 F0 + ϕ1 Qs (5.39) 107 Chapter 5. Queueing Performance of Multichannel ALOHA Systems 0.4 6 Bernoulli:(a) Bernoulli:(s) 5 p 00 = 0.65(a) 0.3 p 00 = 0.65(s) p 00 = 0.75(a) 0.25 p 00 = 0.75(s) 0.2 0.15 q (packets) τ (packets/slot) 0.35 4 Bernoulli:(a) Bernoulli:(s) p 00 = 0.65(a) p 00 = 0.65(s) p 00 = 0.75(a) p 00 = 0.75(s) 3 2 0.1 1 0.05 0 0 0.01 0.02 ǫ1 0.03 0 0 0.04 (a) Throughput. 0.08 0.07 PL 0.06 0.02 ǫ1 0.03 0.04 (b) Mean queue length. 350 Bernoulli:(a) Bernoulli:(s) p 00 = 0.65(a) p 00 = 0.65(s) p 00 = 0.75(a) p 00 = 0.75(s) Bernoulli:(a) Bernoulli:(s) p00 = 0.65(a) p00 = 0.65(s) p00 = 0.75(a) p00 = 0.75(s) 300 250 D (slots) 0.09 0.01 0.05 0.04 200 150 ω = 0.93, p00 = 0.98, p11 = 0.95 0.03 100 0.02 50 0.01 0 0 0.01 0.02 ǫ1 0.03 (c) Packet loss probability. 0.04 0 0 0.1 0.2 0.3 τ (packets/slot) 0.4 (d) Throughput vs. delay. Figure 5.3: Performance comparisons of multi-buffered systems with various source correlation, p11 = 0.6, U = 20, K = 10. 108 Chapter 5. Queueing Performance of Multichannel ALOHA Systems with normalization condition (ϕ0 + ϕ1 )eT = 1. The matrix F0 is written by F0 = Qa ⊗ as (5.40) where as is given by (5.36). We can get ϕ0 and ϕ1 by the similar way in (5.25) and ps by (3.2). We can write pr as N −1 J−1 pr = ϕ1,i,j,0. (5.41) i=0 j=0 The packet dropping probability is obtained by PD = pc N −1 i=0 ϕ1,i,L−1,0 . The retransmis- sion delay is obtained from (5.37). 5.3 Numerical Studies In order to verify our analysis, we build a simulation program with MATLAB. Each simulation result was obtained by a single run of 15000 slots, except Table 5.1. Each result in Table 5.1 was obtained by averaging 5 simulations, each running for 30000 slots. In the computational procedure for analytical results, we set εϕ = εp = 10−6 . For an independent Bernoulli process, we set ǫ0 = ǫ1 = 0 in the analysis and simulation with MMBP model. We use a two-state ON-OFF MMBP to model the uplink traffic of Web-browsing. Unless otherwise stated, we set P = 1, U = 20, J = 6, K = 10 and M = 100. We also set p00 > p11 by assuming that the mean duration of an OFF period, i.e., reading times of a user, is greater than that of an ON period in (5.4). In Figs. 5.2(a)-5.6(c), lines and symbols denote analytical and simulation results, respectively. 1. Effect of multichannel access: In Figs. 5.2(a)-5.2(c), we examine the effects of the number of parallel RACHs, P , on various performance metrics. Mostly, our analysis and 109 Chapter 5. Queueing Performance of Multichannel ALOHA Systems simulation agree well with each other. In particular, we compare the real throughput τ as well as the normalized throughput τ N for P = 1, 2, 3 in Fig. 5.2(a). As expected, a large P increases the maximum of τ by a factor of P in Fig. 5.2(a). Correspondingly, this improves q and PL in Figs. 5.2(b) and 5.2(c), respectively. However, when normalized with the number of channels, the maximum value of τ N remains unchanged, but is shifted toward the right for larger P . For single channel access, i.e., P = 1, τ goes to zero when q grows beyond one, as we can observe in Figs. 5.2(a) and 5.2(b). In contrast, Fig. 5.2(a) shows that under heavy traffic, some minimum level of throughput can be maintained when a larger value of P is employed. In other words, multichannel S-ALOHA access reduces collisions and accepts more packets by distributing the system load evenly over the available channels. 2. Effect of source arrival correlation: In Figs. 5.3(a)-5.3(d), we use two different p00 = 0.65 and 0.75 with fixed p11 = 0.6, i.e., source arrivals are positively correlated by ω = 0.25 and 0.35. We additionally depict the system performance with independent Bernoulli arrivals. As expected, the system performance is less saturated for larger p00 . While various performance metrics behave differently according to ω, we find that tradeoff curves of τ vs. D in Fig. 5.3(d) seem to be insensitive to ω. Based on the MMBP model, it is concluded that the system shows the same performance characteristics, as long as the same offered traffic ǫ is applied to each terminal irrespective of ω. Thus, referring to [89][90][91], Poisson arrival process could be used in conservative performance evaluation for multichannel S-ALOHA random access. 3. Single-buffered vs. multi-buffered terminals: We compare single-buffered and multibuffered systems with K = 1 in Figs. 5.4(a)-5.4(d). In the multi-buffered system with K = 1, incoming packets are blocked, while only one packet is in retransmission. However, packet blocking cannot occur in the single-buffered system, since packets are not generated 110 Chapter 5. Queueing Performance of Multichannel ALOHA Systems 0.4 0.35 Buﬀered (a) 100 0.3 Buﬀered (s) Buﬀerless (a) Buﬀerless (s) D (slots) τ (packets/slot) 120 Buﬀered (a) Buﬀered (s) Buﬀerless (a) Buﬀerless (s) 0.25 0.2 0.15 80 60 B (a) B (s) 40 0.1 20 0.05 0 0 0.01 0.02 ǫ1 0.03 0 0 0.04 (a) Throughput. 0.01 0.02 ǫ1 0.03 0.04 (b) Delay and busy period. −3 8 x 10 0.5 0.45 7 0.4 6 0.35 0.3 PB PD 5 4 0.25 0.2 3 0.15 2 Buffered (a) Buffered (s) Bufferless (a) Bufferless (s) 1 0 0 0.01 0.02 ǫ1 0.03 (c) Packet dropping probability. 0.04 0.1 0.05 0 0 0.01 0.02 ǫ1 0.03 0.04 (d) Packet blocking probability. Figure 5.4: Performance comparisons of single- (bufferless) and multi-buffered systems, p00 = 0.75, p11 = 0.6, U = 20, J = 6, K = 1. 111 Chapter 5. Queueing Performance of Multichannel ALOHA Systems during ongoing packet retransmissions. Therefore, PB in Fig. 5.4(d) refers to the multibuffered system. The performances of the two systems seem to be almost identical in Figs. 5.4(a)-5.4(c). We define the saturation point of ǫ1 as the value that maximizes τ . Fig. 5.4(d) shows that beyond the saturation point ǫ1 = 0.012, PB increases sharply over 10%. Note that a high PB can be prevented by using a large K. In addition, we depict the busy period B in Fig. 5.4(b), which sharply increases beyond the saturation point. It is observed that single-buffered and multi-bufferd systems show almost identical performances except PB . Referring to Figs. 5.2(a)-5.2(b) and 5.3(a)-5.3(b), when mean queue length exceeds one, the system throughput degrades severely except in the case of multichannel access. Accordingly, buffering arriving packets in S-ALOHA can be effective only in multichannel access. For single channel S-ALOHA, the single-buffered assumption may be enough to evaluate system performance except PB . 4. Effect of retry limit L and Correlation: As expected, the results in Figs. 5.5(a)5.5(c) indicate that more collisions occur with larger L values. For example, τ and q get worse in Figs. 5.5(a) and 5.5(b) beyond the saturation point ǫ1 = 0.0125. In other words, a small L tends to stabilize the system by dropping packets that have not been sent successfully after a small number of retransmissions. On the other hand, a large L prevents unnecessary early packet dropping for ǫ1 < 0.0125 in Fig. 5.5(c) and improves τ in Fig. 5.5(a) for 0.01 ≤ ǫ1 ≤ 0.0175. It is observed that unnecessary early packet dropping occurs predominantly in Fig. 5.5(c) for ǫ1 ≤ 0.0175 with L = 2. Thus, it can be concluded that τ and q can be improved by using a small L, at the expense of packet drops caused by the retry limit, while a large L helps to prevent unnecessary early packet drops at traffic levels below the saturation point. Note that PB becomes a dominant factor of PL beyond the saturation point, i.e., once the channel gets congested. As defined in (5.7), we now check the correlation coefficient ̺ by simulations according to J. We have ̺ = 2.5545 × 10−4 112 0.4 3.5 0.35 3 0.3 0.25 L = 5 (a) 0.2 L = 8 (a) L = 2 (s) 0.15 L = 5 (s) = = = = = = 2 5 8 2 5 8 (a) (a) (a) (s) (s) (s) 2 1.5 1 L = 8 (s) 0.1 0.5 0.05 0 0 L L L L L L 2.5 L = 2 (a) q (packets) τ (packets/slot) Chapter 5. Queueing Performance of Multichannel ALOHA Systems 0.01 0.02 ǫ1 0.03 0 0 0.04 0.005 (a) Throughput. 0.03 0.025 0.01 0.015 0.02 ǫ1 0.025 0.03 0.035 (b) Queue length. L L L L L L = = = = = = 2 5 8 2 5 8 (a) (a) (a) (s) (s) (s) PL 0.02 0.015 0.01 0.005 0 0 0.005 0.01 0.015 ǫ1 0.02 0.025 0.03 0.035 (c) Packet loss probability. Figure 5.5: Performance comparisons of multi-buffered systems with different retry limit L, p00 = 0.85, p11 = 0.65, U = 20, K = 10. 113 Chapter 5. Queueing Performance of Multichannel ALOHA Systems (J = 6), 0.0034 (J = 8), 0.027 (J = 10), 0.1073 (J = 12) for a Bernoulli arrival of ǫ1 = 0.01 and U = 20. When more retransmissions are allowed (larger J), the queueing process is more positively correlated. However, finite retransmissions keep ̺ small. For ǫ1 = 0.005 (smaller traffic load) and J = 12, we have ̺ = 0.0021, which indicates a very low positive correlation between terminals’ queues. It is concluded that the queueing process is so weakly (positively) correlated that the analysis based on i.i.d assumption can show agreement with simulations. 5. Effect of window size U : Fig. 5.6(a) shows that a large U improves effectively the minimum τ that the system can sustain at a high ǫ1 , while it increases q (and correspondingly D) and PL as shown in Figs. 5.6(b) and 5.6(c), respectively. This comes from the fact that a large U causes packets to be held longer in the terminal’s buffer, while spreading the retransmission opportunities over time. Under light traffic, i.e., when the channel is not saturated, a smaller U is preferable to reduce D. Even though larger U values might be favourable in order to improve τ in the saturated system as shown in Fig. 5.5(a), the resulting degradation in queuing performance at the terminal, as shown in Figs. 5.5(b) and 5.5(c), may not be acceptable in terms of meeting the user’s QoS requirements. Note that PB becomes much more dominant in PL beyond the saturation point for large U in Fig. 5.6(c) compared to the case for large L in Fig. 5.5(c). In summary, although small L and large U values yield better τ especially for the saturated channel, this is achieved at the expense of PL . For Web-browsing, loss of TCP-ACK packets or HTTP requests can be harmful to the users’ experience. In this regard, it may only be effective to transport such type of packets over a RACH with retry limit when the channel is lightly loaded, i.e., unsaturated. Finally, we test various window sizes with p00 = 0.98 and p11 = 0.8 in Table 5.1 in order to find the optimal U that maximizes τ and minimizes d through simulations. For 114 Chapter 5. Queueing Performance of Multichannel ALOHA Systems U U U U U U τ (packets/slot) 0.35 0.3 = = = = = = 30 50 70 30 50 70 10 (a) (a) (a) (s) (s) (s) 9 8 q (packets) 0.4 0.25 0.2 0.15 7 U U U U U U = = = = = = 30 50 70 30 50 70 (a) (a) (a) (s) (s) (s) 6 5 4 3 0.1 2 0.05 0 0 1 0.02 0.04 0.06 ǫ1 0.08 0.1 0 0 0.12 0.02 (a) Throughput. 0.7 0.6 0.5 0.04 0.06 ǫ1 0.08 0.1 0.12 (b) Queue length. U U U U U U = = = = = = 30 50 70 30 50 70 (a) (a) (a) (s) (s) (s) PL 0.4 0.3 0.2 0.1 0 0 0.02 0.04 0.06 ǫ1 0.08 0.1 0.12 (c) Packet loss probability. Figure 5.6: Performance comparisons of multi-buffered systems with different window size U, p00 = 0.85, p11 = 0.65, L = 2, K = 10. 115 Chapter 5. Queueing Performance of Multichannel ALOHA Systems comparison, we consider that the BS has perfect knowledge of the number of backlogged terminals in every slot, which is denoted by p. Based on this backlog information, the BS assigns U to be exactly the same as the current backlog size, which is known to be optimal for an S-ALOHA system with single-buffered terminals and Poisson arrivals [15]. Table 5.1 shows that backoff window assignment based on the exact backlog size does not yield optimal τ and d for multi-buffered terminals with correlated arrivals (M = 100, J = 5, K = 10, P = 1). In fact, under such conditions, the fixed assignment scheme, e.g., U = 15 for ǫ1 = 0.053 and U = 25 for ǫ1 = 0.056, can give much better performance. 6. End-to-End TCP performance: So far, we have discussed a single hop performance between a BS and terminals. In order to provide high and reliable end-to-end TCP performance, the system should provide low packet dropping probability and low access delay. Although the system shows quite different behaviours after its peak throughput performance, i.e. 0.368, in Figs. 5.2, 5.3, 5.5, and 5.6 given the parameters of UB algorithm, the system should operate before its throughput reaches peak performance. Table 5.1: Performance metrics with various backoff window sizes. U 5 10 15 25 35 45 55 p ρ 0.052 0.091 0.131 0.213 0.293 0.377 0.447 0.120 τ 0.283 0.304 0.311 0.315 0.319 0.316 0.322 0.306 ǫ1 = 0.053 d 11.57 22.09 33.50 59.79 89.47 126.97 168.66 31.64 ± 4.4 PD (%) 0.197 0.176 0.170 0.167 0.161 0.165 0.155 0.176 PB (%) 0 0 0 0 0 0.004 0.015 0 ρ 0.058 0.101 0.150 0.240 0.332 0.420 0.514 0.304 τ 0.272 0.289 0.283 0.291 0.292 0.294 0.293 0.289 ǫ1 = 0.056 d 12.33 23.62 37.42 65.93 101.36 144.82 199.78 106.35 ± 35.5 PD (%) 0.233 0.214 0.225 0.216 0.214 0.210 0.211 0.22 PB (%) 0 0 0 0 0.003 0.024 0.049 0.056 116 Chapter 5. Queueing Performance of Multichannel ALOHA Systems 5.4 Summary In this chapter, we have analyzed the queuing performance of a multichannel S-ALOHA system employing the UB algorithm with retry limit for contention resolution, which reasonably models the random access channels in LTE. The analytical model considers multibuffered terminals with an MMBP traffic source that closely models the uplink traffic of Web-browsing. We have presented results to show that S-ALOHA can be effectively used for uplink transmissions of small IP packets, if the random access channel is unsaturated. Once the system is saturated, the terminals queuing performance is severely degraded. The use of multichannel random access can effectively reduce such performance degradation as well as improve system throughput. Further, compared to the more complex MMBP traffic model, Poisson arrivals can be used for a conservative performance evaluation on singleand multi-bufferd terminals. Regarding the UB algorithm, we have observed that increasing the retry limit provides higher throughput and better queuing performance under light traffic load, while increasing the window size provides a higher throughput in a saturated channel, all at the expense of a higher packet loss rate. Users’ QoS requirements, e.g., for Web-browsing, may not be able to tolerate a high packet loss rate and should be taken into account when such traffic is sent over the random access channels. Finally, we have found that the optimal window size in the literature, based on perfect knowledge of the number of backlogged terminals, is not optimal for multi-buffered terminals with retry limit. 117 Chapter 6 Semi-Persistent Scheduling Algorithm in LTE LTE has emerged as a candidate for fourth generation (4G) cellular networks, which will meet explosive demands on wireless bandwidth by providing peak data rates of 300 Mbps over downlink with 4 × 4 MIMO antennas and 75 Mbps over uplink. In order to use these radio resources efficiently, LTE adopts two scheduling mechanisms. The first one is dynamic scheduling, which allocates radio resources dynamically based on each terminal’s buffer status and radio channel state information. The size of resources together with the MCS would be allocated to meet some QoS requirements. To support this algorithm, terminals must send to eNodeB (a base station in LTE) certain uplink reporting messages either via a random access channel, or via some dedicated control channels in order to inform eNodeB of associated buffer status and channel quality. Although this algorithm is expected to improve total radio resource utilization in the provisioning of QoS for each terminal, it could consume substantial control signaling overhead, particularly for traffic with small, periodic and semi-static packets, e.g., VoIP or TCP ACK packets. The second mechanism is called SPS, which allocates an uplink traffic channel periodically without any additional control message during a traffic burst, e.g., the ON period of a VoIP traffic stream. At the beginning of an SPS operation, an initial uplink traffic channel is obtained either by random access or via an assigned control channel, over which a periodic reservation is made. When an assigned control channel is used for reserving a traffic channel at the 118 Chapter 6. Semi-Persistent Scheduling in LTE beginning of SPS operation, an scheduling request (SR) indicator based on on/off keying is transmitted first in an assigned control channel, called the physical uplink common control channel (PUCCH) [99]. Then eNodeB allocates an uplink grant that allows the terminal to send a buffer status reporting message as shown in Fig. 6.1. Finally eNodeB grants a traffic channel to the terminal. When the SR indicator is not sent over PUCCH, H-ARQ ACK and negative-ACK (NACK), and radio channel quality indicator (CQI) can share this PUCCH. While SPS with SR indicator (SRI) over PUCCH can reduce channel setup times significantly, PUCCH for SRI may be wasted during long inactive periods of an application. On the other hand, when a terminal has lost time-synchronization during an inactive period, it is mandatory to perform random access at the beginning of the next SPS operation. Moreover, radio resource limitations for PUCCH would only allow applications with strict delay constraints to use the SPS with SRI. "*+,"-) .69)1#'&8$%88%+&) <=(%&>)5#'&1)) ?+#)-4@"#)81'148)#"=+#A&5) -4@"#)81'148)#"=+#A&5) <=(%&>)5#'&1)) ?+#)1#'B3)32'&&"() ))./.)0%12).32",4(%&5)6"74"81)9&,%3'1+#) "*+,"-) !"#$%&'() 6'&,+$)'33"88),"(':) !"#$%&'() 6;/)1#'&8$%88%+&) 6;6)'&,)4=(%&>)5#'&1)?+#)C85D) C85D)1#'&8$%88%+&) E+&1"&A+&)6"8+(4A+&)) 0%12)1#'B3)32'&&"() ./.)0%12)#'&,+$)'33"88) Figure 6.1: Signal flow of SPS with SRI or with random access. In SPS, the allocated traffic channel would be implicitly released when some empty transmission slots are found on the allocated traffic channel. This is called ‘implicit release after’, which is specified as either 2, 3, 4 or 8 transmissions [6]. Note that, in the SPS 119 Chapter 6. Semi-Persistent Scheduling in LTE operation, the size of resources and MCS are not changed, once they are allocated at the beginning of SPS. The allocation interval of the traffic channel is called the ‘SPS interval in uplink’ [6], which is specified as either 10, 20, 32, 40, 64, 80, 128, 160, 320 or 640 subframes. Note that VoIP traffic might typically use an SPS interval of 20 subframes [99], while other intervals might be used according to the uplink traffic characteristics. Hereafter, we denote the value of ‘implicit release after’ and ‘SPS interval in uplink’, respectively, by K and L. In SPS operation, K is used for detecting and confirming an ensuing silence period, or can help to hold the reserved traffic channel to prevent it from being released due to some packets being lost over the radio channel. However, a large K could cause low throughput of the reserved traffic channels. In this chapter, we investigate the feasibility of using SPS with initial random access for VoIP traffic in order to complement SPS with SRI, and characterize its performance based on K. While SPS in LTE can be used for VoIP traffic as well as possibly uplink web traffic, VoIP traffic scheduling algorithms have been also developed in IEEE 802.16 systems6 , which is another candidate for 4G networks. In [100], Lee et al. proposed a VoIP scheduling algorithm for IEEE 802.16 system, in which a terminal with VoIP traffic informs a BS of its voice traffic state through an uplink dedicated control channel. According to a one-bit indication in this dedicated control channel, BS allocates uplink resources to the terminal during ON periods of VoIP traffic and de-allocates them during OFF periods. Additionally, they proposed another VoIP scheduling algorithm [101], in which a bandwidth request is sent at the transition from OFF- to ON-state of VoIP traffic through the uplink resources periodically allocated by polling. In order to transmit the bandwidth request generated at the transition from OFF- to ON-state without random access, [100][101] considered VoIP scheduling algorithms with a control channel that is periodically allocated during OFF pe6 As in LTE, IEEE 802.16 systems are also based on OFDMA, in which some subcarriers are used for random access channels. Particularly, both systems employ a demand-assignment multiple access protocol consisting of 4-way handshaking procedure. 120 Chapter 6. Semi-Persistent Scheduling in LTE riods. In addition, when VoIP service is supported by an extended real-time polling service in IEEE 802.16 system, [102] examined signalling overhead and queuing performance of terminals and a base station. In order to prevent wastage of this dedicated uplink control channel [100] during OFF periods, Oh et al. [103] proposed a VoIP scheduling algorithm for IEEE 802.16 system that employs random access at the beginning of a talk spurt in order to obtain uplink resources. In this algorithm, uplink resources for VoIP traffic are periodically granted during ON periods, while silence descriptor frames are transmitted by random access during OFF periods. Note that VoIP scheduling with a dedicated control channel [100] and with random access [103] in IEEE 802.16 system is quite similar to SPS with SRI and with random access in LTE, respectively. When random access is used for reserving a traffic channel, its success may depend on contentions in the random access channels as well as current availability of traffic channels. When all traffic channels are currently occupied by other terminals, a requesting terminal will not be allocated a traffic channel even though the random access is successful. In this regard, [103] underestimates traffic channel assignment delay by assuming that the success of random access is independent of currently remaining traffic channels. In [104] Bi et al. consider that terminals use signalling channels at the beginning of VoIP talk spurts in an OFDMA system in order to obtain a traffic channel and then transmit VoIP packets in the reserved traffic channels once the signalling message would be granted, which is modelled by a tandem M/M/m queuing system. This model is also very close to SPS with SRI. In [105] Rinne et al. provide a simulation study for Evolved Universal Terrestrial Radio Access (E-UTRA) for VoIP and best effort traffic streams, in which the standards of physical and medium access layers are considered in detail. Particularly, SPS operation is compared with a fully dynamic scheduling algorithm with and without packet bundling7 , while round robin and 7 In packet bundling, multiple VoIP packets are bundled based on channel quality and then transmitted together over the downlink by a dynamic scheduler. 121 Chapter 6. Semi-Persistent Scheduling in LTE proportional fair channel-dependent scheduling algorithms are considered for BE traffic together with MIMO and some MCSs. Since the same MCS allocated at the beginning of a talk spurt would be used up to the end of the talk spurt, Jin et al. [106] consider an optimal MCS selection scheme with HARQ over a time-correlated fading channel with the objective of minimizing radio resource usage. In contrast with the previous work that have focused on some underlying transmission schemes at the physical layer, such as MCS and H-ARQ with imperfect channel conditions while considering dedicated control channel, in this chapter we consider the interdependence between random access and traffic channel occupancy of VoIP traffic when the SPS with random access is employed. Our contributions are summarized as follows. 1. We characterize the performance of SPS with initial random access in LTE in terms of random access throughput and delay, traffic channel throughput, and packet dropping probability with a given delay constraint. Based on these performance metrics, we obtain VoIP capacity as the number of terminals without violating some packet dropping probability. 2. We examine by simulations and analysis system stability caused by random access with UB algorithm in terms of the probability distribution of the number of backlogged terminals in the system. We then show how to mitigate bistability of the system. The remainder of this chapter is organized as follows. We introduce SPS with random access and make some assumptions in Section 6.1. In Section 6.2 we analyze this system by using Equilibrium Point Analysis (EPA) [20] as an approximation. We verify our analysis against simulations in Section 6.3. Concluding remarks are given in Section 6.4. 122 Chapter 6. Semi-Persistent Scheduling in LTE 6.1 6.1.1 Models and Assumptions Random Access for SPS Algorithm In addition to the description on the RACH in LTE in Section 1.1, we introduce more details in the specification of LTE RACH. In an LTE radio frame, each PRACH occupies six radio resource blocks8 (RBs) in the frequency domain. The PRACH appears periodically, as specified by the PRACH configuration index. For instance, one PRACH is found every two subframes when the PRACH configuration index is 12 [66]. At most one PRACH is allowed in a subframe, while only one PRACH is available in the frequency domain of a slot. Note that, in an LTE FDD frame structure, one radio frame of 10 msec consists of 10 subframes, each of which consists of two slots. Thus, one slot length is 0.5 msec, which corresponds to one packet transmission time. Each accessing terminal randomly chooses one of 64 orthogonal RAPs called Zadoff-Chu sequences and transmits it over a PRACH. Some of the RAPs would be reserved for contention-free random access, whereby eNodeB directly allocates them to some terminals. In SPS with initial random access, contention-based random access is used for reserving a traffic channel that is periodically allocated to a terminal. Suppose that P RAPs are available for contention-based random access. First the requesting terminal selects one of P RAPs at random and transmits it with initial power F in a PRACH. When multiple terminals transmit the same RAP in the same PRACH, a RAP collision occurs. Secondly, eNodeB broadcasts the RAR on the downlink control channel within a predefined time-window as shown in Fig. 6.1. From the RAR message terminals obtain the backoff parameter, U, timing advance command, the RAP identifier and the uplink RBs for the successful terminals to use. If a requesting terminal cannot find its RAP identifier, it regards itself as backlogged and increases its RAP transmission counter by one. If the counter is equal to the maximum number of allowed 8 Each radio RB is formed by 12 subcarriers. 123 Chapter 6. Semi-Persistent Scheduling in LTE preamble transmissions, denoted by RL , then the terminal drops its RAP retransmission and reports this to the higher layer. Otherwise, the terminal selects a random backoff time between 0 and U (msec), and delays its retransmission by the selected backoff time. When a terminal retransmits a RAP, it increases the RAP transmission power by ∆F , subject to the constraint that the RAP transmission power cannot exceed Fmax . This is called the power ramping scheme, which is repeated up to the maximum of RAP counter until the terminal transmits a RAP successfully. Third, a terminal finding its RAP identifier in the RAR message transmits a message called Msg3 [6] via H-ARQ conveying information such as a radio resource control (RRC) connection request, or tracking area update. We assume that the terminal’s buffer status reporting in Fig. 6.1 could be transmitted via Msg3 in SPS with random access in Fig. 6.1. If this message is successfully transmitted, eNodeB finally allocates a traffic channel, which the corresponding terminal will use periodically. Based on the random access procedure above [6][66], our assumptions are summarized as follows: A1) We assume that there are M terminals in this system, each of which has an infinite queue to store incoming VoIP packets. A2) Since LTE has various PRACH configurations, as an example we assume that one slot consists of one PRACH and D traffic OFDMA subcarriers, with each slot corresponding to one packet transmission time. A3) We assume perfect orthogonality among RAPs transmitted in the PRACH, i.e., no multiple access interference occurs between different RAPs. Therefore, the LTE random access channels can be regarded as a multichannel S-ALOHA system. Although the standard includes a power ramping scheme for RAP transmissions over the PRACH, we do not take power ramping into account to keep our model simple and tractable. 124 Chapter 6. Semi-Persistent Scheduling in LTE A4) In practice, when a RAP collision occurs, all the terminals that transmitted the same RAP will receive the same traffic channel to transmit SR requests. The eNodeB allows the RAP-colliding terminals to simultaneously transmit an Msg3 in the channel allocated to all of them [6], with the expectation that the collisions on this channel would be resolved by HARQ. If terminals cannot transmit Msg3 successfully up to the maximum of retransmissions of HARQ, they will repeat RAP transmission. We simplify our model by excluding Msg3 transmissions via HARQ. Moreover, we conservatively assume that a RAP collision destroys all transmissions involved and the corresponding terminals retransmit randomly selected RAPs based on UB algorithm after RAR reception. We further assume that a terminal gets an uplink traffic channel right after successful RAP transmission, skipping the Msg3 transmission. In fact, an Msg3 transmission after a successful RAP transmission merely adds a deterministic delay to the random access delay. A5) For a terminal transmitting a unique RAP, i.e., successful RAP transmission, its random access cannot be declared as successful if there is no traffic channel available for assignment to it. In this paper, a random access is said to be successful, when a terminal receives a traffic channel assignment after successful RAP transmission. Thus, a successful random access (different from a successful RAP transmission) is the synonym of a successful traffic channel reservation. Accordingly, the random access delay is defined as the time that is taken for a terminal to reserve a traffic channel successfully, after it transmits the first RAP. Furthermore, we assume that terminals get feedback on success or failure of random access, just after RAP (re)transmissions, without any error, i.e., right before the beginning of the next slot. A6) Compared to UB algorithm with retry limit [6], our analytical model uses UB algorithm with infinite retransmissions, RL = ∞. However, our simulation model 125 Chapter 6. Semi-Persistent Scheduling in LTE implements UB algorithm with retransmission limit for a better representation of a real system. A7) In addition to A5, if the number of terminals successfully transmitting RAPs, say z, is greater than the number of available traffic channels, say d, eNodeB randomly chooses d among z terminals and allocates them d traffic channels. Then, z − d terminals will be backlogged due to the lack of available traffic channels and will perform the backoff algorithm in A6, i.e., these terminals suffer from a reservation blocking. 6.1.2 Uplink Traffic Model When each VoIP packet is generated every 20 msec by an adaptive multi-rate (AMR) voice codec at 12.2 kbps [99], a total of 50 packets/sec are generated with the payload size of 31 bytes. We approximately model this VoIP traffic stream by a two-state MMBP [77]. We assume that in every slot a traffic source that is in the OFF-state may change its state to the ON-state with probability 1 − β, and a traffic source that is in the ON-state may change its state from to the OFF-state with probability 1 − α. This assumption gives average ON and OFF periods as 1/(1 − α) and 1/(1 − β) (slots), respectively. We further assume that one packet is always generated at the transition from the OFF-state to the ON-state, while a packet is generated every slot based on a Bernoulli trial with probability σ during the rest of the ON period. As in [107], in this paper we assume the average ON and OFF periods to be 1000 and 1350 (msec), which respectively correspond to α = 0.999 and β = 0.9993 for 1 msec slots. We also set σ = 0.05, which represents a 20 msec average inter-arrival time of VoIP packets during the ON periods. Particularly, after a terminal would reserve a traffic channel by random access, we assume in the next section that no more than one packet can be generated in the ON state during each transmission period 126 Chapter 6. Semi-Persistent Scheduling in LTE Table 6.1: Symbols used in SPS algorithm with initial random access Definition Number of orthogonal random access preambles Total number of terminals Window size of uniform backoff algorithm SPS interval in uplink. Allocated data channel appears every L + 1 slots Implicit release after. Maximum of allowed empty transmissions on an allocated traffic channel D Number of data channels σ The probability that a packet is generated in the ON state in slot α (β) The probability of VoIP traffic source being in the ON (OFF) state in a slot ci Number of backlogged terminals with window size i n Number of terminals with ON state of VoIP traffic source f Number of terminals with OFF state of VoIP traffic source t0 (t1 ) Number of terminals in the transmission state, when VoIP traffic source is in ON (OFF) state (k) Number of terminals with a reserved traffic channel. rij (k) The indexes, k, i and j correspond to Rij Notation P M U L K of L + 1 slots. 6.1.3 Semi-Persistent Scheduling in LTE To begin with, we summarize the symbols used in describing the SPS with initial random access in Table 6.1. Recall that, after the traffic channel reservation via random access, terminals transmit their VoIP packets in the allocated traffic channels every L + 1 slots. During this period, no more packets are generated in the ON-state. Thus, packet arrivals in the ON state of our MMBP model depends on the terminal’s reservation state. An allocated traffic channel is implicitly released, when K consecutive empty transmissions are observed in the allocated traffic channel. After the reserved traffic channel has been released, the terminal should perform random access again when it needs to send more VoIP packets. The SPS with initial random access we propose can be regarded as an extension of the packet reservation multiple access (PRMA) in [107], which is based on S-ALOHA 127 Chapter 6. Semi-Persistent Scheduling in LTE for a traffic channel reservation. Compared to the PRMA with P = D = K = 1 where a permission probability is used as a backoff algorithm, terminals in our model reserve a traffic channel by multichannel S-ALOHA (P ≥ 1, D ≥ 1, and K ≥ 1) and use UB algorithm. Fig. 6.2 shows the possible states of each terminal with respect to the random access, which can be explained as follows: 1. A terminal’s uplink traffic source behaves every slot based on MMBP model in Section 6.1.2. When the terminal has not started the random access to reserve a traffic channel, the state of the source is depicted by the ON- and the OFF-state in Fig. 6.2, which is also the state of the terminal. While the terminal does not have a reserved traffic channel, a transition from the OFF- to the ON-state (always accompanied by a VoIP packet arrival) or the arrival of a VoIP packet while the terminal is in the ONstate causes the terminal to contend for a traffic channel assignment by accessing the random access channel. This moves the terminals state to one of the contention states (CONi for 0 ≤ i ≤ U) based on the UB algorithm with delayed first transmission. 2. Once a terminal enters the CONi state for reserving a traffic channel, we assume that its VoIP source state is still in the ON state until a successful random access, as a VoIP source is unlikely to change its state during the signalling delay in [104]. Every slot a terminal in the CONi state moves into the CONi−1 state with probability one, according to the UB algorithm. Note that, while a terminal is in the CONi for 0 ≤ i ≤ U, packets can be generated. This will be discussed in detail in Sections 6.2.2. Terminals in the CON0 state will select a RAP randomly and transmit it in the PRACH. 3. When a terminal reserves a traffic channel, it moves from the CON0 state into the traffic transmission state, denoted by the TX0 state. The TX1 state indicates the 128 Chapter 6. Semi-Persistent Scheduling in LTE RES(0K, 2+1) RES(LK,0) RES(Lk,0) RES(L☎,)0 RES(21,)0 RES(LK,1) RES(Lk,1) RES(L✞,)1 RES(21,1) RES(LK, 2) RES(0K, 2) RES(Lk, 2) RES(0k,3) ● ● ● ● ● ● RES(L✆,)2 ● ● ● ● ● ● TX0 RES(2✄,)2 RES1( ,3) ! ● ● ● ● ● ● ! ! ! ● ● ● ● ● ● ! ● ● ● ● ● ● RES1(✧,0) TX1 RES(0K,3+✝) RES(LK,3) RES(0K,3) ON OFF RES(Lk,3) CON U RES(0k, ★) CONU −1 RES(L✂,)3 ● ● ●! RES(21,)3 CON1 RES1(✁, 4) CON 0 Figure 6.2: State transition diagram of terminals with SPS algorithm with random access. traffic transmission state in which the terminal’s voice traffic state is in the OFF state. 4. During L subsequent slots after the TX0 or the TX1 state, the terminal is said to (k) be in the i-th reservation state, which is denoted by the RESi,j for 1 ≤ i ≤ L and 1 ≤ k ≤ K (this superscript denotes the counter of the empty transmissions). Note that during these states the terminal can have a packet in the ON state of VoIP source, and some slots later VoIP source goes to the OFF state. Accordingly, the subscript j = 0 (1) denotes the ON (OFF) state of VoIP traffic source with a packet, while j = 2 (3) denotes the ON (OFF) state without a packet. (k) 5. Finally, the RES0,j state for 2 ≤ k ≤ K + 1 and j = 2, 3 represents an empty transmission on the traffic channel reserved for a terminal, which can be reached (k−1) from the RESL,j state without a packet arrival for j = 2, 3. 129 Chapter 6. Semi-Persistent Scheduling in LTE 6.2 Analysis 6.2.1 Equilibrium Point Analysis Based on Fig. 6.2, we denote the numbers of terminals in the ON-, the OFF-, the TX0 -, (k) (k) the TX1 -, the RESi,j - and the CONℓ states by N, F , T0 , T1 , Ri,j and Cℓ (called the state variable), respectively. The state space of this system can be represented by {Cℓ for (k) (k) 0 ≤ ℓ ≤ U, T0 , T1 , N, F, R1,j for 1 ≤ k ≤ K and j = 0, 2, 3, Ri,j for 1 ≤ k ≤ K, 2 ≤ i ≤ L (k) and 0 ≤ j ≤ 3, R0,j for 2 ≤ k ≤ K + 1, j = 2, 3}. If a multidimensional Markov chain is considered to describe M terminals’ states, the number of possible states could be as (k) large as M 2+U +1 (D + 1)K(5+4(L−1))+2 states in Fig. 6.2, in which T0 , T1 and Ri,j take the value from 0 to D. Typically we use M ≥ 70, U ≥ 10, L = 20, K ≥ 1 and D = 5 in Section 4.3. Instead of finding a joint probability of M terminals’ states, by using EPA we focus on the number of terminals in a state at equilibrium. In what follows, we first obtain a system equilibrium function denoted by F (c0 ), in which c0 is the number of terminals in the CON0 state at equilibrium. Then, we obtain the system performance metrics in terms of random access delay, throughput, and packet (front-end) dropping probability. To this end, we denote the equilibrium value of each state variable by small letters, cℓ , t0 , (k) t1 , n, f , ri,j , respectively. Additionally, we define the following row vectors, t = [t0 t1 ], (k) r1 (k) (k) (k) (k) (k) = r1,0 0 r1,2 r1,3 for 1 ≤ k ≤ K, ri (k) (k) (k) (k) (k) = ri,0 ri,1 ri,2 ri,3 for 1 ≤ k ≤ K and (k) 2 ≤ i ≤ L, r0 = r0,2 r0,3 for 2 ≤ k ≤ K + 1. Based on A2 the state transition occurs at each slot boundary. By assuming that the expected flow into and out of each state variable are equal [20], we construct the following state balance equations: First, at the (k) RESi,j state for 1 ≤ k ≤ K and 0 ≤ j ≤ 3, we have (k) r1 = t Hk−1 g, (k) ˆ r2 = t Hk−1 g h (k) and ri ˆ hi−2 = t Hk−1 g h for 3 ≤ i ≤ L, (6.1) 130 Chapter 6. Semi-Persistent Scheduling in LTE ˆ hL−2 u0 , and the matrices, g and h, ˆ are respectively expressed as in which H = g h α 1−α 0 0 0 0 0 0 ˆ= and h σα 0 (1 − σ)α 1 − α 1−β 0 0 β σα 0 (1 − σ)α 1 − α g= 1−β 0 0 β . (6.2) (1) In (6.1), for instance, r1 = t g indicates that the number of terminals in the TX0 - and the (1) TX1 state moves to one of the RES1,j state for j = 0, 2, 3 with probability g. The matrices h and u0 are expressed as α 1−α 0 0 1−β β 0 0 h= 0 (1 − σ)α 1 − α σα 1−β 0 0 β (k+1) For the RES0,j 0 0 0 0 and u0 = (1 − σ)α 1 − α 0 β . (6.3) state for j = 2, 3, we can write (k+1) r0 = t Hk for k = 1, 2, · · · , K. (6.4) We denote by Λ (r, c0 ) the number of packets which successfully reserve the remaining traffic channels by random access, given total of r currently reserved traffic channels and c0 terminals at the CON0 state. We can get the total number of reserved traffic channels r by K K (k) rL e4 r= k=1 =t k=1 ˆ L−2 e4 , Hk−1 g hh (6.5) 131 Chapter 6. Semi-Persistent Scheduling in LTE in which en represents a unit column vector whose length is n. At the TX0 - and the TX1 state we can write K K (k) rL u◦1 t0 = + Λ (r, c0 ) (k) rL u•1 , and t1 = (6.6) k=1 k=1 in which the column vectors, u◦1 and u•1 , are expressed as 1−α β and u•1 = 0 0 α 1−β u◦1 = σα 1−β . (6.7) Referring to Fig. 6.2, the left hand side and right hand side in (6.6) respectively indicate the expected flow out of t0 (or t1 ) and into t0 (or t1 ). Using (6.1), we can rewrite t1 in (6.6) as K t1 = t k=1 ˆ L−2 u• ⇒ t1 = a0 t0 + a1 t1 , Hk−1 g hh 1 (6.8) from which we have t1 = a0 /(1 − a1 )t0 . Note that the constants a0 and a1 are numerically determined. We then express t in terms of t0 as t = t0 w, (6.9) in which we have w = [1 a0 /(1 − a1 )]. By substituting (6.9) into (6.5), we can get r by K r r(t0 ) = t0 w k=1 ˆ L−2 e4 . Hk−1 g hh (6.10) 132 Chapter 6. Semi-Persistent Scheduling in LTE In (6.6) we can get Λ(r, c0) by c0 Λ(r, c0 ) = mr (z)Γ(z|c0 , P ), (6.11) z=1 in which mr (z) = min(z, max(D − r, 0)) is the conditional mean of successfully reserved traffic channels by random access, which is based on A7. Further, Λ(z|c0 , P ) is the probability that z among c0 terminals select a unique RAP given a total of P RAPs, which comes from A3 in the Section 6.1.1 and is given in (3.3). Due to fluid approximation of EPA, c0 is a real number for 0 ≤ c0 ≤ M in (6.11), which makes (6.11) computationally intractable. By assuming that the terminals at the CON0 state transmit their packet by a Poisson distribution with mean c0 , we rewrite (6.11) as ∞ k Λ(r, c0 ) = mr (z)Γ(z|k, P ) k=1 z=1 ck0 exp−c0 . k! (6.12) At the ON state we have (K+1) (1 − σ)αr0,2 = (σα + (1 − α)) n. (6.13) At the OFF state we can write (K+1) (1 − α)r0,2 (K+1) + βr0,3 + (1 − α)n = (1 − β)f. (6.14) At the CONU state we get 1 (K+1) (K+1) σα n + r0,2 + (1 − β) f + r0,3 + c0 − Λ(r, c0) = cU . U +1 (6.15) 133 Chapter 6. Semi-Persistent Scheduling in LTE At the CONi state for 0 ≤ i ≤ U − 1 we also get 1 (K+1) (K+1) + c0 − Λ(r, c0) + ci+1 = ci . + (1 − β) f + r0,3 σα n + r0,2 U +1 (6.16) Using (6.15) we can rewrite ci for 0 ≤ i ≤ U ci = U +1−i (K+1) (K+1) σα n + r0,2 + (1 − β) f + r0,3 + c0 − Λ(r, c0 ) . U +1 (6.17) At the CON0 state we then have (K+1) σα n + r0,2 (K+1) + (1 − β) f + r0,3 = Λ(r, c0), (6.18) in which the left hand side indicates the expected flow into the backlog states, i.e., CONi for 0 ≤ i ≤ U, while Λ(r, c0 ) indicates the expected output flow from the CON0 state. After some tedious manipulation on (6.13)-(6.18), we have (K+1) r0,2 (K+1) + r0,3 = Λ(r, c0 ) ⇒ t0 wHK e2 = Λ(r(t0 ), c0 ), (6.19) (K+1) in which (6.10) has been used. Eq. (6.19) means that the flow out of the RES0,2 (K+1) the RES0,3 - and state is equal to the flow out of the CON0 state. If we can express (6.19) as a function of c0 only, we can find a solution c0 of satisfying (6.19). Thus, we only need to express t0 as a function of c0 . To this end, we use the fact that the sum of the number of terminals distributed over each state should be equal to M, which is expressed as K L K+1 (k) t e2 + k=1 i=1 U (k) ri e4 + r0 e2 + k=2 ci + n + f = M. (6.20) i=0 134 Chapter 6. Semi-Persistent Scheduling in LTE From (6.13) and (6.14), we have (1 − σ)α (K+1) r and σα + (1 − α) 0,2 1 (1 − σ)α (K+1) (K+1) f= . (1 − α) 1 + r + βr0,3 1−β σα + (1 − α) 0,2 n= (6.21) (6.22) Then, we can get n + f = t0 w HK v e2 , (6.23) in which the matrix v is expressed by (1 − σ)α σα + (1 − α) v= 0 1−α (1 − β)(σα + (1 − α)) . β/(1 − β) (6.24) By substituting (6.18) into (6.17), we also have ci = ((U + 1 − i)/(U + 1))c0 . (6.25) Then, by substituting (6.1), (6.4), (6.23) and (6.25) into (6.20), we rewrite (6.20) as t0 = K w e2 + k=1 M − 0.5(U + 2)c0 L ˆ+ Hk−1 g + g h K ˆ hi−2 e4 + gh i=3 k=1 Hk e2 + HK v e2 = G(c0 ). (6.26) Finally by using (6.19) and (6.26), we can obtain F (c0 ) as F (c0 ) = G(c0 ) w HK e2 − Λ(r(G(c0 )), c0 ) = 0. (6.27) Some remarks on F (c0 ) can be given as follows: 135 Chapter 6. Semi-Persistent Scheduling in LTE 1. The solution(s) of (6.27), which is often called equilibrium point [20][107], can be numerically found for 0 ≤ c0 ≤ M. Hereafter, we denote the equilibrium point(s) by c∗0 . 2. The system stability can be guaranteed, when (6.27) has a unique c∗0 for 0 ≤ c0 ≤ M. If (6.27) has multiple solutions, the system is said to be unstable (including bistable). In order to estimate the bistability region of this system in terms of U or other system parameters, F (c0 ) should be at least thrice differentiable [108]. For our system, it is hard to find either a closed form solution of (6.27), or to find such bistability regions due to the recursive form and non-differentiability in (6.12). 3. When M is increased, F (c0 ) has multiple equilibrium points, which implies that the random access channel gets congested. Then, the backlog process oscillates between some local stable equilibrium points so that the throughput and delay performances at locally stable equilibrium points can be only obtained for some finite time period. Then, EPA analysis shows discrepancies against simulation, because the simulation results are time-averaged values, while EPA analysis represents the performance at an arbitrary equilibrium point among multiple points. This phenomenon has been observed in [20][107]. 4. For the multiple equilibrium points found by F (c0 ), sometimes it is difficult to confirm these points by simulation, because we cannot know prior how long the backlog process stays at each one of multiple equilibrium points in a simulation (See also [109]). In such cases, simulation run-time should be long enough to reflect this behaviour of the backlog process. The first exist time (FET) for a backlog process to become unstable starting from a stable region has been studied in S-ALOHA and PRMA systems [110][111]. However, it is only possible to obtain the FET when a 136 Chapter 6. Semi-Persistent Scheduling in LTE multidimensional Markov chain is used for describing M terminals’ states. In order to obtain the system performance metrics, we denote the throughput of the random access channel and the traffic channel by ζa and ζd . With c∗0 numerically obtained, we can respectively obtain ζa and ζd by ζa = Λ(r, c∗0) and ζd = t e2 . (6.28) Denote the random access delay by d (slots). Using Little’s result [20], one can get d by d = c/ζa = 0.5(U + 2)c∗0 /ζa where c denotes total number of backlogged terminals, i.e., c = (6.29) U i=0 ci . Additionally, we denote by PB the reservation blocking probability, i.e., random access failure due to lack of traffic channels. We can obtain PB by PB = Λ − ζa /Λ (6.30) where Λ is the mean number of RAPs successfully transmitted. This can be obtained by ∞ k Λ= k=1 z=1 6.2.2 z · Γ(z|k, P ) (c∗0 )k ∗ exp−c0 . k! (6.31) Packet Dropping Probability In what follows, we assume that the time scale of random access delay is small compared to that of the VoIP source so that VoIP source would not go back to the OFF state during the CONi state. Due to A1, incoming packets are stored without packet dropping occurring due to a full buffer. However, front-end packet dropping occurs when the waiting time 137 Chapter 6. Semi-Persistent Scheduling in LTE of a packet at the front-end of the buffer exceeds a delay constraint τ , the probability of which is denoted by Pd . Recall that random access is initiated at the state transition from the OFF- to the ON-state with one packet arrival. As more packets may arrive before a traffic channel is successfully reserved, the first few packets stored in the queue may be successively dropped if their waiting time exceeds τ before random access is successful, resulting in front-end clipping of a talk spurt. Denote by W the random variable of random access time (or delay) that the first packet at the beginning of a talk spurt in ongoing contention would experience. Additionally, the random variables of the remaining random access time of the first packet experienced by an arriving packet and that of the number of packets generated during the remaining random access time are denoted by Y and J, respectively. Then, we can write Pd as ∞ Pd = j=0 1 1(W > τ ) · Pr[W > τ ]Pr[J = j] 1+j j + i=1 1(Y + i · L > τ ) · Pr[Y + i · L > τ, J = j] , (6.32) in which indication function 1(x) is one if the condition x is satisfied, and zero otherwise. In (6.32) the first term depicts the dropping condition of the first packet, when its random access time exceeds τ . The second term denotes the mean number of dropped packets in the front of the queue, when the transmission time of each of J packets takes exactly L slots by SPS operation. Dividing the sum of these two terms by 1 + j yields the packet dropping probability given j + 1 arrivals including the first packet. In order to obtain (6.32), we first consider the PMF of W in (6.32). To this end, we consider an absorbing Markov chain which consists of an absorbing state A and the i-th backoff state, bi for 0 ≤ i ≤ U. If the absorbing state represents the successful random access, the random access time is then described by the absorption time that a Markov process will be absorbed into the 138 Chapter 6. Semi-Persistent Scheduling in LTE absorbing state, starting from one of the backoff states, bi for 0 ≤ i ≤ U. Denote by Q the state transition matrix for this Markov chain, in which the i-th row and the j-th column element of Q for 0 ≤ i and j ≤ U is denoted by qij , i.e., the state transition probability from bi to bj . We write qij as (1 − Ps )/(U + 1) if i = 0 and j = 0, · · · , U qij = 1 else if i = j − 1 for 0 ≤ i ≤ U 0 otherwise, in which the random access success probability is obtained by Ps = τa /c∗0 . We then write Pr[W = k] as Pr[W = k] = ξ (0) Qk−1 v T for k = 1, 2, · · · (6.33) in which two row vectors of length U + 1, ξ (0) and v T , are respectively expressed by (0) ξ (0) = [ξi ] for 0 ≤ i ≤ U and v = [Ps 0 0 . . . 0]. Since the backoff randomly starts from one of U + 1 states when a packet arrives while the terminal has not reserved a traffic (0) channel, we have ξi d= ∞ k=0 kPr[W = 1/(1 + U). Note that (6.33) can be verified also by (6.29), i.e., = k]. Denote by X the random access time experienced by an arriving packet during ongoing random access of the first packet. Based on the residual life time theory of M/G/1 queuing system in [112], the PMF of this specific random access time can be determined by Pr[X = x] = x/d Pr[W = x]. (6.34) 139 Chapter 6. Semi-Persistent Scheduling in LTE Since Y is uniformly distributed over X, we have Pr[Y = y|X = x] = 1 x for 1 ≤ y ≤ x. (6.35) Removing the conditioning in (6.35) by applying (6.34), we have y ∞ 1 Pr[Y = y] = Pr[Y = y|X = x]Pr[X = x] = d x=y+1 1− Pr[W = x] (6.36) x=0 where we have Pr[W = 0] = 0. We can rewrite (6.32) as ∞ Pd = j=0 1 j+1 j ∞ Pr[W = w] + w=τ +1 i=1 Pr[Y > max(τ − i · L, 0)|J = j] Pr[J = j], (6.37) in which (6.36) is applied. Since packets are generated based on Bernoulli trials with probability σ during the residual random access time of the first packet, we can obtain Pr[J = j] by ∞ Pr[J = j] = y=1 6.3 y j σ (1 − σ)y−j Pr[Y = y]. j (6.38) Numerical Results and Discussions In order to verify our analysis, we built a simulation model in MATLAB, in which one slot corresponds to 1 msec. We run each simulation for 150000 slots and time-average the results, with L = 20, τ = 50, and unlimited RL , unless otherwise stated. At the beginning of a simulation we randomly distributed M terminals over the ON-, the OFF-, and the CONℓ states for 0 ≤ ℓ ≤ U. The parameters of VoIP traffic are given in Section 6.1.2. 140 Chapter 6. Semi-Persistent Scheduling in LTE 1 0.8 0.6 1) 0.4 Probability distribution of c0 , πc0 0.2 2) 0 Locally Stable Equilibrium Point −0.2 −0.4 −0.6 0 Equilibrium function, F (c0 ) 5 10 15 c0 20 25 30 Figure 6.3: Bistability of the system: Equilibrium function F (c0 ) and the state probability for c0 , πc0 Note that VoIP capacity for SPS with initial random access is defined as the maximum of allowable terminals M without exceeding a predefined packet dropping rate. In the following examples, we consider one PRACH in a slot, which takes six radio RBs. Note that 18 terminals can typically use one PUCCH of one radio RB in SPS with SRI. Thus, 108 terminals can be supported by six RBs in SPS with SRI. Bistability: We first examine bistability of this system represented by (6.27). We denote the PMFs of c0 and c in the system by πc0 for 0 ≤ c0 ≤ M, which is obtained by simulations. In Fig. 6.3 we depict respectively F (c0 ) and two examples of πc0 for P = 2, D = 5, U = 10, K = 2, M = 100 and L = 20 obtained from two simulation runs. As F (c0) shows three roots of (6.27), we can observe two different distributions of πc0 , which implies bistability. As previously mentioned, we can obtain the system performances at locally stable equilibrium points for some finite time period in a simulation. To mitigate such a bistability, we consider three schemes. First, we apply a retry limit RL in simulations, which limits the number of retransmissions. If the number of retransmissions exceeds RL , the terminal drops the packet and gets back to the ON-state. We denote by Pr the 141 Chapter 6. Semi-Persistent Scheduling in LTE Table 6.2: Stabilized system performance with various parameters RL = 5, U = 10 RL = ∞, U = 15 RL = ∞, U = 10 P = 2, K = 2 P = 2, K = 2 P = 5, K = 2 ζd (packets/slot) 1.38 1.38 (Ana: 1.43) 1.41 (Ana: 1.44) d (slots) 6.92 9.87 (Ana: 9.5) 6.45 (Ana: 6.25) Pd × 100(%) 0.24 0.9 (Ana: 0.7) 0.11 (Ana: 0.1) Pr × 100(%) 0.50 0 0 probability that a packet is dropped due to this retry limit, which is given in the first column of Table 6.2. Secondly we control U, and thirdly increase P . The corresponding results are given in the second and third columns of Table 6.2. While increasing U or reducing RL also stabilize the system by dropping the packet forcibly, Pd and/or Pr would be sacrificed. Therefore we can conclude that increasing P from 2 to 5 is the most effective way to mitigate instability, by relieving congestion in the random access channel. Thus, a sufficient number of RAPs should be secured according to the number of VoIP traffic users, and then RL can be further applied to prevent bistability. On the other hand, a large U might not be desirable for delay-constrained applications, since it causes large random access delays. Note that the system shown in Fig. 6.3 is bistable with 100 terminals. However, it can be seen that 100 terminals can be supported with τ = 50 and 1% packet dropping rate in the two stabilized systems with U = 15, or with P = 5 shown in the second and third columns of Table 6.2. Comparison with PRMA: In Fig. 6.4, we compare the packet dropping rate, i.e., Pd × 100 (%), of SPS with random access (P = D = 2) against that of PRMA with U = 5 and K. Note that the original PRMA [107] uses a permission probability as the backoff algorithm, while the PRMA presented in Fig. 6.4 uses the UB algorithm. As expected, the VoIP capacity in SPS with random access is almost doubled under a 1% packet dropping rate due to increased P and D. The discrepancies between analysis and simulation at M = 26 in PRMA and M = 50 in SPS with random access can be explained by the fact that the 142 Chapter 6. Semi-Persistent Scheduling in LTE 2 PRMA (ana) Packet dropping rate (%) PRMA (sim) P = D = 2 (ana) 1.5 P = D = 2 (sim) 1 0.5 0 10 20 30 40 Number of terminals, M 50 Figure 6.4: Comparison of PRMA and SPS with random access systems have multiple equilibrium points with these population sizes. Thus, the simulation results are time-averaged values in bistable systems. While the VoIP capacity of PRMA depends only on a single parameter (permission probability in [107] or U here), that of SPS with random access depends on the parameters U, P , D and K. The effect of K: Recall that K is used for detecting a silence period. We examine the effects of K on the system performance with U = 10, and P = D = 5 in Figs. 6.5(a)6.5(d). In Fig. 6.5(a) we can observe that ζd slightly decreases due to longer holding times of traffic channels as K increases. While ζd shows good agreements between analysis and simulation results, this is not the case with the packet dropping rate and d, particularly for larger M and K in Figs. 6.5(b) and 6.5(c). Although the systems with those parameters are stable, EPA cannot evaluate system performance reliably. This is possibly caused by two reasons. First, by examining the PMF of the random access time, W , for M = 115 and M = 125 in Fig. 6.5(d), we can see that analysis and simulation results show some agreement for K = 1, while high fluctuations and disagreements are found either for K = 8 or for M = 125. When we increase K, the number of backlogged terminals 143 Chapter 6. Semi-Persistent Scheduling in LTE decreases as small as c∗0 < 0.1 in analysis and simulation. Although the difference of c∗0 between analysis and simulation (slightly underestimated by analysis) is quite small, the percentage of such differences is no longer negligible. In these cases, simulation results show a longer tail distribution of W than analytical results, which might cause mismatch between analytical and simulation results in Fig. 6.5(b). Secondly, even for a stable system, if the distribution of πc0 (or πc ) is asymmetric, then it might result in mismatch between analysis and simulation results because c∗0 in (6.27) represents only an averaged value for the equilibrium condition. In order to find K properly, we suggest the following cost function: maximize γ1 ζd (K) − γ2 Pd (K, τ ) K (6.39) where γ1 and γ2 are weighting factors, and ζd is the normalized traffic channel throughput, i.e., ζd (K) = ζd (K)/D. In this example, K = 2 might be favourable, because ζd gets lower with larger K. However, the weight in (6.39) should be considered depending on QoS requirements. The effect of window size U: With P = D = 5 and K = 1 we vary U from 5 to 15 and use τ = 40 and 50 in Figs. 6.6(a)-6.6(b). Fig. 6.6(a) depicts ζd , while the packet dropping rate is presented in Fig. 6.6(b). Smaller U (faster access) provides much lower Pd , while ζd is insensitive to U except U = 5 at M = 115 (highly congested). However, U = 5 causes the instability of the random access system for the system around M = 115 due to more frequent retransmissions which leads to congestion in the random access channels. As VoIP capacity with τ = 50, we can observe that maximally 130 terminals is acceptable with U = 15, while U = 10 can accept 130 VoIP terminals satisfactorily. We also observe Pd with a smaller τ = 40 (slots), i.e., tighter delay constraint, which shows lower quality of VoIP traffic. Although some simplifications have been made in our model, we can see that 70 terminals can be admitted. In addition, we simulate the system with P = 64, τ = 50, 144 2 1.8 1.6 K K K K K K K K 1.4 1.2 1 0.8 70 80 90 100 =1 =2 =4 =8 =1 =2 =4 =8 110 Number of terminals, M (ana) (ana) (ana) (ana) (sim) (sim) (sim) (sim) 120 0.7 0.6 0.5 0.4 130 0.2 70 8.5 8 90 =1 =2 =4 =8 =1 =2 =4 =8 (ana) (ana) (ana) (ana) (sim) (sim) (sim) (sim) 7 6.5 80 90 100 110 Number of terminals, M 120 (c) Mean random access delay. 130 100 110 Number of terminals, M 0.1 K K K K K K K K 7.5 6 70 80 120 130 (b) Packet dropping rate. Probability mass function of W 9 (ana) (ana) (ana) (ana) (sim) (sim) (sim) (sim) 0.1 10 9.5 =1 =2 =4 =8 =1 =2 =4 =8 0.3 (a) Throughput of traffic channels. Random access delay, d (slots) K K K K K K K K 0.8 Packet dropping rate (%) Throughput of traﬃc channel, ζd (packets/slot) Chapter 6. Semi-Persistent Scheduling in LTE K K K K K 0.08 = 1, M = 8, M = 1, M = 8, M = 8, M = 115 = 115 = 115 = 115 = 125 20 25 (ana) (ana) (sim) (sim) (sim) 0.06 0.04 0.02 0 0 5 10 15 Random access time, W 30 (d) PMF of random access times. Figure 6.5: The effect of K on the system performance. 145 2 3 Packet dropping rate (%) Throughput of traﬃc channel, ζd (packets/slot) Chapter 6. Semi-Persistent Scheduling in LTE 1.5 1 0.5 0 70 U U U U U U U U U = 10, τ = 50 (ana) = 10, τ = 40 (ana) = 5, τ = 50 (ana) = 15, τ = 50 (ana) = 10, τ = 40 (sim) = 10, τ = 50 (sim) = 5, τ = 50 (sim) = 15, τ = 50 (sim) = 10, P = 64 (sim) 80 90 100 110 120 Number of terminals, M 2.5 2 1.5 U U U U U U U U U = 10, τ = 40 (ana) = 10, τ = 50 (ana) = 5, τ = 50 (ana) = 15, τ = 50 (ana) = 10, τ = 40 (sim) = 10, τ = 50 (sim) = 5, τ = 50 (sim) = 15, τ = 50 (sim) = 10, P = 64 (sim) 1 0.5 130 (a) Throughput of random access and traffic channels. 0 70 80 90 100 110 120 Number of terminals, M 130 (b) Packet dropping rate. Figure 6.6: The effect of U on the system performance U = 10, i.e., total number of available RAPs in LTE. We present simulation result only for this system due to computational complexity in (6.12) for such large P . Even though the packet dropping rate in the system with P = 64 and U = 10 is improved compared to the system with P = 5 and U = 10 (the same backoff window size), it is noticeable that the system with P = 5 and U = 5 shows compatible low packet dropping rate until M = 115. This implies that, rather than just increasing P , more dynamic control of U can lead to large improvements of the packet dropping performance. 6.4 Summary In this chapter we have examined the feasibility of SPS with initial random access for VoIP traffic in LTE by constructing an approximate model based on EPA to analyze its performance. In particular we have shown the VoIP capacity as the number of VoIP terminals that can be accommodated without exceeding some packet dropping probability, 146 Chapter 6. Semi-Persistent Scheduling in LTE when initial random access is used. From our study, it can be conjectured that SPS with initial random access might be alternatively used, if the cost of PUCCH for SRI not used in the OFF period of an application would be expensive. We have also investigated the effect of K, the number of empty transmission slots before the reserved traffic channel is released, and the effect of U on VoIP capacity. Although our analytical model cannot provide reliable performance evaluations for large K, VoIP capacity have been estimated with various U and K = 1. We have shown also the instability of SPS with random access based on UB algorithm (without retry limit), and discussed how to stabilize the system. We can conclude that, while a retry limit can effectively stabilize the system at the expense of a reasonable Pr , optimal control on U would be more desirable. 147 Chapter 7 Conclusions and Future Work This chapter summarizes the results and highlights the contributions of this dissertation. The direction of future research is also given. 7.1 Research Contributions This thesis has proposed novel CRAs in an MPR S-ALOHA and examined the performance of existing CRAs with and without the PR scheme in MPR S-ALOHA for single- or multibuffered terminals. Further as a reservation protocol, the performance of SPS with initial random access in LTE has been also examined. Particularly, we have characterized the performance of UB and BEB algorithms for single- or multi-buffered terminals in Chapters 3-5 with respect to the following three aspects. First, we have evaluated the performance of these systems based on i.i.d. assumption on backoff or queueing processes and showed the correlation coefficient of these processes from simulation. This has shown that, due to retry limit, the positive correlation among these processes is so weak that the performance evaluation based on i.i.d. assumption can agree well with simulation. Secondly, compared to S-ALOHA systems without retry limit [27][29][81], due to packet loss by retry limit, the stabile capacity of S-ALOHA systems with retry limit should be understood by the maximum acceptable arrival rate without exceeding a predefined packet loss probability. Finally, the variance of access delay can be a metric to show access fairness in UB and BEB algorithms. The smaller variance the algorithms show, the more fair access we can 148 Chapter 7. Conclusions and Future Work achieve. The results in each chapter are summarized as follows. • In Chapter 2, two cross layer CRAs have been proposed in CDMA-based MPR SALOHA systems. When terminals are required to meet their transmission power via open loop power control, the proposed algorithms construct the system backlog information by measuring the power of MAI. Then, in the proposed algorithms, retransmission probability for a backlogged terminal is chosen slot-by-slot to maximize the conditional expected system throughput. For the IFT and DFT protocols, the performance of the algorithms under perfect power control is close to that predicted by the analytical performance model without estimation errors. For uncoded/coded systems under imperfect power control, system throughput decreases due to reduction of channel capacity. Specifically, the throughput efficiency in coded systems is maintained over 50% up to power control error of 2 dB. By examining FET and negative drift, the algorithms are shown to be stable. • In Chapter 3, two existing CRAs, i.e., UB and BEB algorithms with retry limit, have been examined for the RACHs in LTE and IEEE 802.16 systems, respectively. Their performances are presented in terms of throughput, mean, and variance of packet retransmission delay and packet dropping probability, and the stability properties of both algorithms are examined. It is shown that stability is highly dependent upon the uniform window size and the maximum backoff stage and that the systems employing these algorithms are either stable or unstable, but do not show bistability behaviour. In addition, by adjusting the parameters of each backoff algorithm properly, it is found that the two algorithms show virtually identical throughput, but different delay variances. It is also shown that controlling the persistence probability provides effective access priority control with respect to various performance metrics. Finally, 149 Chapter 7. Conclusions and Future Work a dynamic window assignment algorithm is proposed, which is a simple extension of an existing Bayesian broadcasting algorithm. The dynamic window assignment algorithm outperforms the existing backoff algorithms in any traffic condition as long as the perfect orthogonality assumption among random access code holds. • Chapter 4 has examined the PR scheme with UB algorithm in LTE in conjunction with initial power transmission selection based on some PMFs. It has been assumed that uplink pathloss estimation is perfect. As in Chapter 4, it is also observed that a weak positive correlation over each terminal’s backoff process results from the retry limit. By examining the throughput gain per average transmission power consumption, it is shown that the PR scheme is effective when the SINR threshold is less than −2.5 dB. It is found that the PR scheme improves throughput, delay, and capacity of RACH (number of terminals without violating Pd < 0.01) at the cost of the average transmission power. In probabilistic initial transmission power selection schemes, τ is insensitive to the PMFs of selecting initial transmission power. Further, increasing the probability of selecting the highest power can increase Pd , while reducing d. Therefore, the PR scheme of transmitting the lowest power first is the most efficient one with respect to Pd and p. In the presence of PR scheme, it is also needed to control U dynamically in order to maximize τ according to the number of backlogged terminals. To this end, we proposed TAUBA, which estimates backlog size based on waiting-time counter by terminals and takes throughput gain by PR into account. By simulation, we showed that TAUBA improved the system throughput close to its maximum and minimized mean access delay and packet dropping. • Chapter 5 has examined the queuing performance of a multichannel S-ALOHA system employing the UB algorithm with retry limit for contention resolution, which reasonably models the random access channels in LTE. It is shown that good agree150 Chapter 7. Conclusions and Future Work ments between the analysis based on i.i.d. assumption and simulation come from weak positive correlation over each terminal’s queueing process due to retry limit. The analytical model considers buffered terminals with an MMBP traffic source that closely models the uplink traffic of Web-uplink transmissions of small IP packets, if the random access channel is unsaturated. It is shown that, once the system is saturated, the terminals’ queuing performance is severely degraded. The use of multichannel random access can effectively reduce such performance degradation as well as improve the system throughput. Further, compared to the more complex MMBP traffic model, this study has shown that Poisson arrivals can be used for a conservative performance evaluation on single- and multi-buffered terminals. When testing the UB algorithm, it is observed that increasing the retry limit provides a higher throughput and better queuing performance under light traffic load, while increasing the window size provides a higher throughput in a saturated channel. However, it also results in a higher packet loss rate. Users’ QoS requirements, e.g., for Webbrowsing, may not be able to tolerate a high packet loss rate and thus, should be taken into account when such traffic is sent over the random access channels. Finally, it is found that the optimal window size in the literature, based on perfect knowledge of the number of backlogged terminals, is not optimal for buffered terminals with retry limit. • Chapter 6 has explored the feasibility of SPS with initial random access for VoIP traffic in UMTS-LTE by constructing an approximate performance model based on EPA, and presented the MAC layer performances of the SPS. The VoIP capacity (provided by SPS with initial random access) is presented as the number of VoIP terminals that can be accommodated without exceeding some packet dropping probability. From this study, it can be recommended that SPS with initial random access 151 Chapter 7. Conclusions and Future Work might be alternatively used, if the cost of PUCCH for SRI not used in the OFF period of an application would be expensive. The effect of K (the number of empty transmission slots before the reserved traffic channel is released) on VoIP capacity is examined. From the numerical studies, it is shown that, while a large K causes disagreements between analysis and simulations, it also results in high fluctuations in Pd . Based on the trade-off between ζd and Pd , it is determined that K = 2 is the optimal value in the given examples. This chapter has also examined the instability of SPS with random access based on UB algorithm (without retry limit), and how to stabilize the system. It is concluded that a retry limit can stabilize the system at the expense of a reasonable Pr , when the availability of 64 RAPs in the system is considered. 7.2 Suggestions for Future Work 1. Performance Modeling of Slotted p-Persistent CSMA systems By using an embedded Markov chain, this study proposes another performance model of slotted p-persistent CSMA systems for single-buffered terminals which have been examined by Takagi in 1983, Meditch in 1983, and Shoraby in 1987, respectively. This study is expected to show stability condition of slotted CSMA systems. 2. Random Access Control for Multi-buffered terminals In Chapter 5, we have shown that an optimal retransmission control for bufferless terminal cannot be used for buffered terminal. This study explores an optimal retransmission scheme for (unsaturated) buffered terminals. 3. Stable Throughput Region of Secondary Users in Cognitive Radios In Cognitive radios, secondary users opportunistically utilize the radio spectrums unused 152 Chapter 7. Conclusions and Future Work by primary users. The throughput of secondary users can be affected by their own contentions on unused spectrum as well as by primary users’ behaviour. This work is to examine the stable throughput region of secondary users given a Markovian behaviour of primary users. 4. Efficient Scheduling Scheme of Energy Harvesting Relay Network This work considers a relay node which stores energy recharged by surrounding environments in its energy queue. This relay node transmits information provided by sensors or machines over time-varying wireless channels. In this work, an energy efficient scheduling algorithm would be developed in order to minimize energy consumption and meet delay constraint of information. 153 Bibliography [1] S. Ghez, S. Verd´ u, and S. C. Schwartz, “Stability properties of slotted ALOHA with multipacket reception capability,” IEEE Trans. on Automatic Control, vol. 33, no. 7, pp. 640–649, July 1988. [2] V. Naware, G. Mergen, and L. Tong, “Stability and delay of finite-user slotted ALOHA with multipacket reception,” IEEE Trans. on Information Theory, vol. 51, no. 7, pp. 2636–2656, July 2005. [3] H. Jin and A. Acampora, “Performance of a tree-based collision resolution algorithm in cellular systems with smart antennas,” IEEE Trans. on Wireless Communications, vol. 6, no. 3, pp. 1143–1151, Mar. 2007. [4] Y. Yu and G. B. Giannakis, “High-throughput random access using successive interference cancellation in a tree algorithm,” IEEE Trans. on Information Theory, vol. 53, no. 12, pp. 4628–4639, November 2007. [5] Q. Zhang, T. F. Wong, and J. S. Lehnert, “Performance of a type-II Hybrid ARQ protocol in slotted DS-SSMA pakcet radio systems,” IEEE Trans. on Communications, vol. 47, no. 2, pp. 281–290, Feb. 1999. [6] 3GPP TS 36.321 V9.1.0, 3rd Generation Partnership Project; Evolved Universal Terrestrial Radio Access (E-UTRA) Medium Access Control (MAC) protocol specification., Dec. 2009. [7] S. S. Lam and L. Kleinrock, “Packet switching in a multiaccess broadcast channel: Dynamic control procedures,” IEEE Trans. on Communications, vol. COM-23, no. 9, pp. 891–904, Sep. 1975. [8] B. Hajek and T. van Loon, “Decentralized dynamic control of a multiaccess broadcast channel,” IEEE Trans. on Automatic Control, vol. AC-27, no. 3, pp. 559–569, June 1982. [9] F. P. Kelly, “Stochastic models of computer communication systems,” Journal of the Royal Statistical Society, Series B (Methodological), vol. 47, no. 3, pp. 379–395, 1985. [10] R. L. Rivest, “Network control by Bayesian broadcast,” IEEE Trans. on Information Theory, vol. IT-33, no. 3, pp. 323–328, May 1987. 154 Bibliography [11] J. J. Capentanakis, “Tree algorithm for packet broadcast channels,” IEEE Trans. on Information Theory, vol. IT-25, no. 5, pp. 505–515, Sep. 1979. [12] B. S. Tsybakov and V. A. Mikhailov, “Free synchronous packet access in a broadcast channel with feedback,” Probl. Information Transmission, vol. 14, no. 4, pp. 259–280, Oct.-Dec. 1978. [13] J. F. Hayes, “An adaptive technique for local distribution,” IEEE Trans. on Communications, vol. COM-26, no. 8, pp. 1178–1186, Aug. 1978. [14] R. Rom and M. Sidi, Multiple Access Protocols, Performance and Analysis. SpringerVerlag, 1990. [15] D. Bertsekas and R. Gallager, Data Networks. 2nd edition, Prentice-Hall, 1992. [16] M. L. Molle and G. C. Polyzos, “Conflict resolution algorithms and their performance analysis,” Department of Computer Science and Engineering, University of California, San Diego, Tech. Rep. Technical Report CS93-300, July 1993. [17] J. Mosel and P. A. Humblet, “A class of efficient contention resolution algorithms for multiple access,” IEEE Trans. on Communications, vol. 33, no. 2, pp. 145–151, Feb. 1985. [18] P. A. Humblet, “On the throughput of channel access algorithms with limited sensing,” IEEE Trans. on Communications, vol. 34, no. 4, pp. 345–347, April 1986. [19] B. J. Kwak, N. O. Song, and L. E. Miller, “Performance analysis of exponential backoff,” IEEE/ACM Trans. on Networking, vol. 13, no. 2, pp. 343–355, 2005. [20] S. Tasaka, Performance Analysis of Multiple Access Protocols. MIT Press, 1986. [21] G. Fayolle, E. Gelenbe, J. Labetoulle, and D. Bastin, “The stability problem of broadcast packet switching computer networks,” Acta Informatica, vol. 4, no. 1, pp. 49–53, 1974. [22] A. G. Pakes, “Some Conditions of Ergodicity and Recurrence of Markov Chains,” Operation Research, vol. 17, pp. 1058–1061, 1969. [23] F. G. Foster, “On the stochastic matrices associated with certain queuing processes,” Ann. Math. Statist., vol. 24, no. 3, pp. pp.355–360, 1953. [24] W. Szpankowski, “Stability conditions for some distributed systems: Buffered random access systems,” Adv. Applied Probability, vol. 26, no. 2, pp. 498–515, Jun. 1994. 155 Bibliography [25] H. Takagi and L. Kleinrock, “Mean packet queueing delay in a buffered two-user CSMA/CD system,” IEEE Trans. Comm., vol. COM-33, no. 10, pp. 1136–1139, Oct. 1985. [26] M. Sidi and A. Segall, “Two interfering queues in packet-radio networks,” IEEE Trans. Comm., vol. COM-31, no. 1, pp. 123–129, Jan. 1983. [27] V. Anantharam, “Stability region of the finite-user slotted ALOHA protocol,” IEEE Trans. on Information Theory, vol. 37, no. 3, pp. 535–540, May 1991. [28] R. M. Loynes, “The stability of a queue with nonindependant inter-arrival and service times,” Proc. Cambridge Philos. Soc., vol. 58, pp. 497–520, 1962. [29] R. Rao and A. Ephremides, “On the stability of interacting queues in a multi-access system,” IEEE Trans. on Information Theory, vol. 34, no. 5, pp. 918–930, 1988. [30] IEEE Standard for Local and metropolitan area networks, Part 16: Air Interface for Broadband Wireless Access Systems-Amendment for Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands (IEEE P802.16e/D7), April 2005. [31] 3GPP TS 25.321 V5.14.0, 3rd Generation Partnership Project; Medium Access Control (MAC) protocol specification., Sep. 2008. [32] Y. Xiao, “Performance analysis of priority scheme for IEEE 802.11 and IEEE 802.11e wireless LANs,” IEEE Trans. on Wireless Communications, vol. 4, no. 4, pp. 1506– 1515, March 2000. [33] K. Kar, S. Sarkar, and L. Tassiulas, “Achieving proportional fairness using local information in Aloha networks,” IEEE Trans. Automatic Control, vol. 49, no. 10, pp. 1858–1863, Oct. 2004. [34] X. Wang and K. Kar, “Cross-layer rate optimization for proportional fairness in multihop wireless networks with random access,” IEEE J. Selected Areas in Comm., vol. 24, no. 8, pp. 1548–1559, Aug. 2006. [35] D. Zheng and J. Zhang, “A two-phase utility maximization framework for wireless medium access control,” IEEE Trans. on Wireless Communications, vol. 6, no. 12, pp. 4299–4307, Dec. 2007. [36] S. Ghez, S. Verd´ u, and S. C. Schwartz, “Optimal decentralized control in the random access multipacket channel,” IEEE Trans. on Automatic Control, vol. 34, no. 11, pp. 1153–1163, November 1989. 156 Bibliography [37] K. Sakakibara, T. Seto, D. Yoshimura, and J. Yamakita, “Effect of exponential backoff scheme and retransmission cutoff on the stability of frequency-hopping slotted ALOHA systems,” IEEE Trans. on Wireless Communications, vol. 2, no. 4, pp. 714– 722, Jul. 2003. [38] M. H. Ngo and V. Krishnamurthy, “Game theoretic cross-layer transmission policies in multipacket reception wireless networks,” IEEE Trans. on Signal Processing, vol. 55, no. 5, pp. 1911–1926, May 2007. [39] J. Q. Bao and L. Tong, “A performance comparison between Ad Hoc and centrally controlled CDMA wireless LANs,” IEEE Trans. on Wireless Communications, vol. 1, no. 4, pp. 829–841, October 2002. [40] A. Brand and A. H. Aghvami, Multiple Access Protocols for Mobile Communications : GPRS, UMTS and Beyond. John Wiley & Sons, 2002. [41] M. G. Jansen and R. Prasad, “Capacity, throughput, and delay analysis of a cellular DS CDMA system with imperfect power control and imperfect sectorization,” IEEE Trans. on Vehicular Technology, vol. 44, no. 1, pp. 67–75, Feb. 1995. [42] R. M. Jr. and J. S. Lehnert, “Bit-to-Bit error dependence in slotted DS/SSMA packet systems with random signautre sequences,” IEEE Trans. on Communications, vol. 37, no. 10, pp. 1052–1061, Oct. 1989. [43] R. K. M. Jr. and J. S. Lehnert, “Packet throughput in slotted aloha ds/ssma radio systems with random signature sequences,” IEEE Trans. on Communications, vol. 40, no. 7, pp. 1223–1230, July 1992. [44] J. Cheng and N. C. Beaulieu, “Accurate ds-cdma bit-error probability calculation in rayleigh fading,” IEEE Trans. on Wireless Comm., vol. 1, no. 1, pp. 3–15, Jan. 2002. [45] S. C. Schwartz and Y. S. Yeh, “On the distribution function and moments of power sums with log-normal components,” Bell Sys. Tech. Journal, vol. 61, no. 7, pp. 1441– 1462, 1982. [46] A. B. Carleial and M. E. Hellman, “Bistable behavior of ALOHA-type systems,” IEEE Trans. on Communications, vol. COM-23, no. 4, pp. 401–410, Apr. 1975. [47] S. Q. Li and C. L. Hwang, “Queue response to input correlation functions: discrete spectral analysis,” IEEE/ACM Transactions on Networking, vol. 1, no. 5, pp. 522– 533, Oct. 1993. [48] S. W. Kim, “Frequency-hopped spread-spectrum random access with retransmission cutoff and code rate adjustment,” IEEE J. Selected Areas in Comm., vol. 10, no. 2, pp. 344–349, 1992. 157 Bibliography [49] K. Sakakibara, H. Muta, and Y. Yuba, “The effect of limiting the number of retransmission trials on the stability of slotted ALOHA systems,” IEEE Trans. on Vehicular Technology, vol. 49, no. 4, pp. 1149–1453, Jul. 2000. [50] Y. S. Liu, “Performance analysis of frequency-hop packet radio networks with generalized retransmission backoff,” IEEE Trans. on Wireless Communications, vol. 1, no. 4, pp. 703–711, 2002. [51] Y. P. Fallah, F. Agharebparast, M. R. Minhas, H. M. Alnuweiri, and V. C. M. Leung, “Analytical modeling of contention-based bandwidth request mechanism in IEEE 802.16 wireless networks,” IEEE Trans. on Vehicular Technology, vol. 57, no. 5, pp. 3094–3107, 2008. [52] H. L. Vu, S. Chan, and L. L. H. Andrew, “Performance analysis of best-effort service in saturated IEEE 802.16 networks,” IEEE Trans. on Vehicular Technology, vol. 59, no. 1, p. 460472, January 2010. [53] D. Chuck, K. Y. Chen, and J. M. Chang, “A comprehensive analysis of bandwidth request mechanisms in IEEE 802.16 networks,” IEEE Trans. on Vehicular Technology, vol. 59, no. 4, pp. 2046–2056, May 2010. ´ [54] M. E. R. Angeles, D. L. Rodr´ıguez, and F. A. C. P´erez, “Differentiated backoff strategies for prioritized random access delay in multiservice cellular networks,,” IEEE Trans. on Vehicular Technology, vol. 58, no. 1, pp. 381–397, Jan. 2009. [55] B. E. Brand and A. H. Aghvami, “Multidimensional PRMA with prioritized Bayesian broadcast - a MAC strategy for multiservice traffic over UMTS,” IEEE Trans. on Vehicular Technology, vol. 47, no. 4, pp. 1148–1161, November 1998. [56] Z. Zhang and Y. J. Liu, “Comments on the effect of capture on performance on multichannel slotted ALOHA system,” IEEE Trans. on Communications, vol. 41, no. 10, pp. 1433–1435, October 1993. [57] W. Feller, An Introduction to Probability Theory and Its Applications. John Wiley & Sons, 1970. [58] D. J. Goodman and A. A. M. Saleh, “The near/far effect in local ALOHA radio communications,” IEEE Trans. Veh. Tech., vol. VT-36, no. 1, pp. 19–27, Feb. 1987. [59] M. Zorzi and R. R. Rao, “Capture and retransmission control in mobile radio,” IEEE J. Selected Areas in Comm., vol. 12, no. 8, pp. 1289–1298, Oct. 1994. [60] B. Hajek, A. Krishna, and R. O. LaMaire, “On the capture probability for a large number of stations,” IEEE Trans. Comm., vol. 45, no. 2, pp. 254–260, Feb. 1997. 158 Bibliography [61] Y. Yu, X. Cai, and G. B. Giannakis, “On the instability of slotted Aloha with capture,” IEEE Trans. on Wireless Comm., vol. 5, no. 2, pp. 257–261, Feb. 2006. [62] C. C. Lee, “Random signal levels for channel access in packet broadcast networks,” IEEE J. Selected Areas in Comm., vol. SAC-45, no. 6, pp. 1026–1034, July 1987. [63] Y. W. Leung, “Mean power consumption of artificial power capture in wireless networks,” IEEE Trans. Comm., vol. 45, no. 8, pp. 957–964, Aug. 1997. [64] R. O. LaMaire, A. Krishna, and M. Zorzi, “On the randomization of transmitter power levels to increase throughput in multiple access radio systems,” Wireless Networks, vol. 4, pp. 263–277, March 1998. [65] B. Khoshnevis and B. H. Khalaj, “Optimum power selection algorithms in Aloha networks: Random deterministic approaches,” IEEE Trans. on Wireless Comm., vol. 6, no. 8, pp. 3124–3136, Aug. 2007. [66] 3GPP TS 36.213 V.9.2.0, 3rd Generation Partnership Project; Evolved Universal Terrestrial Radio Access (E-UTRA) Physical layer procedure, June 2010. [67] Y. Yang and T. S. P. Yum, “Analysis of power ramping schemes for UTRA-FDD random access channel,” IEEE Trans. Comm., vol. 4, no. 6, pp. 2688–2693, Nov. 2005. [68] 3GPP TS 36.211 V9.1.0, 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; Evolved Universal Terrestrial Radio Access (E-UTRA); Physical Channels and Modulation (Release 9), Apr. 2010. [69] P. Henrichi, Elements of Numerical Analysis. Wiley, 1964. [70] P. Tran-Gia, D. Staehle, and K. Leibnitz, “Source traffic modeling of wireless applications,” Int. J. Electron. Commun., vol. 55, no. 1, pp. 27–36, 2001. [71] H. K. Choi and J. O. Limb, “A behavioral model of Web traffic,” in 7th International Conference of Networking Protocol’ 99 (ICNP’99), 1999, pp. 327–334. [72] M. E. Crovella and A. Bestavros, “Self-similarity in World Wide Web traffic: Evidence and possible cause,” IEEE/ACM Trans. on Networking, vol. 5, no. 6, pp. 835–846, Dec. 1997. [73] Universal Mobile Telecommunications System (UMTS); Selection procedures for the choice of radio transmission technologies of the UMTS (UMTS 30.03 version 3.1.0), TR 101 112 V3.1.0, Nov. 1997. [74] B. Moon and J. Mo, “Optimizing uplink TCP-ACK transmission in WiMAX OFDMA systems,” IEEE Communications Letters, vol. 12, no. 4, pp. 256–258, April 2008. 159 Bibliography [75] “R1-070378, “UL resource request for LTE system,” Nokia, 3GPP TSG RAN WG1#47-bis, Sorento, Italy, January 15-19, 2007, available at http://www.quintillion.co.jp/3gpp/tsg ran/tsg ran2007/tsg ran wg1 rl1 1.html,” Tech. Rep. [76] R2-061990, “Random access collision probability and load estimates,” Motorola, 3GPP TSG-RAN WG2 LTE AH, available at http://www.quintillion.co.jp/3GPP/TSG RAN/TSG RAN2006/TSG RAN WG2RL2 6.htm. [77] C. H. Ng, L. Yuan, W. Fu, and L. Zhang, “Comments on methodology for traffic modeling using two-state Markov-modulated Bernoulli process,” Computer Communications, vol. 22, no. 13, pp. 1266–1273, 1999. [78] D. P. Heyman and D. Lucantoni, “Modeling multiple IP traffic streams with rate limits,” IEEE/ACM Trans. on Networking, vol. 11, no. 6, pp. 948–958, December 2003. [79] W. Luo and A. Ephremides, “Stability of interacting queues in random-access systems in random-access systems,” IEEE Trans. on Information Theory, vol. 45, no. 5, pp. 1579–1587, July 1999. [80] B. Shrader and A. Ephremides, “Random access broadcast: Stability and throughput analysis,” IEEE Trans. on Information Theory, vol. 53, no. 8, pp. 2915–2921, Aug. 2007. [81] T. N. Saadawi and A. Ephremides, “Analysis, stability, and optimization of slotted ALOHA with a finite number of buffered users,” IEEE Trans. Automatic Control, vol. ac-26, no. 3, pp. 680–689, June 1981. [82] T. Wan and A. U. Sheikh, “Performance and stability analysis of buffered slotted ALOHA protocols using tagged user approach,” IEEE Trans. on Vehicular Technology, vol. 49, no. 2, pp. 582–593, March 2000. [83] A. Dua, “Random access with multi-packet reception,” IEEE Trans. on Wireless Communications, vol. 7, no. 6, pp. 2280–2288, June 2008. [84] O. Tickoo and B. Sikdar, “Modeling queueing and channel access delay in unsaturated IEEE 802.11 random access mac based wireless networks,” IEEE/ACM Trans. on Networking, vol. 16, no. 4, pp. 878–891, Aug. 2008. [85] Y. Zheng, K. Lu, D. Wu, and Y. Fang, “Performance analysis of IEEE 802.11 DCF in imperfect channels,” IEEE Trans. on Vehicular Technology, vol. 55, no. 5, pp. 1648–1656, Sep. 2006. [86] D. Miorandi, A. A. Kherani, and E. Altman, “A queueing model for HTTP traffic over IEEE 802.11 WLANs,” Computer Networks, vol. 50, no. 1, pp. 63–79, 2006. 160 Bibliography [87] R. Bruno, M. Conti, and E. Gregori, “Throughput analysis and measurements in IEEE 802.11 WLANs with TCP and UDP traffic flows,” IEEE Trans. on Mobile Computing, vol. 7, no. 2, pp. 171–186, Feb. 2008. [88] O. Bhardwaj, G. V. V. Sharma, M. Panda, and A. Kumar, “Modeling finite buffer effects on TCP traffic over an IEEE 802.11 infrastructure WLAN,” Computer Networks, vol. 53, no. 16, pp. 2855–2869, Nov. 2009. [89] J. Aracil and L. Munoz, “Performance of Aloha channels under self-similar input,” Electronics Letters, vol. 33, no. 8, pp. 659–660, April 1997. [90] Z. Harpantidou and M. Paterakis, “Random multiple access of broadcast channels with pareto distributed packet interarrival times,” IEEE Personal Comm., vol. 5, no. 2, pp. 48–55, April 1998. [91] J. Gao and I. Rubin, “Analysis of a random-access protocol under long-rangedependent traffic,” IEEE Trans. on Vehicular Technology, vol. 52, no. 3, pp. 693–700, May 2003. [92] A. Erramilli, O. Narayan, and W. Willinger, “Experimental queueing analysis with long-range dependent packet traffic,” IEEE/ACM Trans. on Networking, vol. 4, no. 2, pp. 209–223, April 1996. [93] J. Beran, R. Sherman, M. S. Taqqu, and W. Willinger, “Long-range dependence in variable-bit-rate video traffic,” IEEE Trans. Comm., vol. 43, no. 2/3/4, pp. 1566– 1579, Feb./Mar./Arp. 1995. [94] A. T. Anderson and B. F. Nielsen, “A Markovian approach for modeling packet traffic with long-range dependence,” IEEE J. Selected Areas in Comm., vol. 16, no. 5, pp. 719–732, June 1998. [95] W. Fischer and K. Meier-Hellstern, “The Markov-modulated Poisson process (MMPP) cookbook,” Performance Evaluation, vol. 18, pp. 149–171, 1992. [96] A. Baiocchi and N. Blefari-Melazzi, “Steady-state analysis of the MMPP/G/1/K queue,” IEEE Trans. on Communications, vol. 41, no. 4, pp. 531–534, Apr. 1993. [97] W. J. Stewart, Introduction to Numerical Solution of Markov Chains. University Press, 1994. Princeton [98] H. Takagi, Queueing Analysis : volume 2, Finite systems. Elsevier Science Publishers, 1993. [99] H. Holma and A. Toskala, LTE for UMTS : OFDMA and SC-FDMA Based Radio Access. John Wiley & Sons Ltd, 2009. 161 Bibliography [100] H. Lee, T. Kwon, and D. H. Cho, “An enhanced uplink scheduling algorithm based on voice activity for VoIP services in IEEE 802.16d/e system,” IEEE Communications Letters, vol. 9, no. 8, pp. 691–693, Aug. 2005. [101] H. Lee, H. D. Kim, and D. H. Cho, “Smart resource allocation algorithm considering voice activity for VoIP services in mobile-WiMAX system,” IEEE Trans. on Wireless Communications, vol. 8, no. 9, pp. 4688–4697, Sep. 2009. [102] J. W. So, “Performance analysis of VoIP services in the IEEE 802.16e OFDMA system with inband signaling,” IEEE Trans. Veh. Tech., vol. 57, no. 3, pp. 1876– 1886, May 2008. [103] S. M. Oh, S. Cho, J. H. Kim, and J. Kwun, “VoIP scheduling algorithm for AMR speech codec in IEEE 802.16e/m system,” IEEE Communications Letters, vol. 12, no. 5, pp. 374–376, May 2008. [104] Q. Bi, S. Vitebsky, Y. Yang, Y. Yuan, and Q. Zhang, “Performance and capacity of cellular OFDMA systems with Voice-over-IP traffic,” IEEE Trans. on Vehicular Technology, vol. 57, no. 6, pp. 3641–3652, Nov. 2008. [105] M. Rinne, M. Kuusela, E. Tuomaala, P. Kinnunen, I. Kovacs, and K. Pajukoski, “A performance summary of the Evolved 3G (E-UTRA) for Voice Over Internet and best effort traffic,” IEEE Trans. on Vehicular Technology, vol. 58, no. 7, pp. 3661–3673, Sep. 2009. [106] N.-O. S. H. Jin, C. Cho and D. K. Sung, “Optimal rate selection for persistent scheduling with HARQ in time-correlated Nakagami-m fading channels,” IEEE Trans. on Wireless Communications, vol. 10, no. 2, pp. 637–647, Feb. 2011. [107] S. Nanda, D. J. Goodman, and U. Timor, “Performance of PRMA: A packet voice protocol for cellular systems,” IEEE Trans. on Vehicular Technology, vol. 40, no. 3, pp. 584–598, 1991. [108] S. Nanda, “Stability evaluation and design of the prma joint voice data system,” IEEE Trans. Comm., vol. 42, no. 5, pp. 2092–2104, May 1994. [109] S. Tasaka, “Stability and performance of the r-aloha packet broadcast system,” IEEE Trans. Computers, vol. C-32, no. 8, pp. 717–726, Aug. 1983. [110] L. Kleinrock and S. S. Lam, “Packet switching in a multiaccess broadcast channel: Performance evaluation,” IEEE Trans. Comm., vol. COM-23, no. 4, pp. 410–423, April 1975. [111] H. Qi and R. Wyrwas, “Markov analysis for prma performance study,” IEEE Vehicular Tech. Conf., vol. 2, pp. 1184–1188, 1994. 162 Bibliography [112] L. Kleinrock, Queueing Systems: Volume I – Theory. Wiley Interscience, New York, 1975. 163
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On random access control for multipacket reception...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On random access control for multipacket reception S-ALOHA in wireless cellular networks Seo, Jun-Bae 2012
pdf
Page Metadata
Item Metadata
Title | On random access control for multipacket reception S-ALOHA in wireless cellular networks |
Creator |
Seo, Jun-Bae |
Publisher | University of British Columbia |
Date Issued | 2012 |
Description | Studies on slotted ALOHA (S-ALOHA) systems have a long research history and been quite mature in the literature. However, this thesis revisits S-ALOHA systems by considering multipacket reception (MPR) channels, because previous studies are no longer applicable to MPR capable S-ALOHA systems due to the new random access channels (RACHs) of contemporary wireless cellular network standards. Particularly, it is dubious to apply the contention resolution algorithms (CRAs) developed so far for S-ALOHA systems to MPR S-ALOHA systems without any modification. Accordingly, this thesis proposes cross-layer CRAs and investigates the performance of some existing CRAs in MPR S-ALOHA systems in order to maximize the system throughput in tandem with stabilizing the system. Cross-layer CRAs proposed are based on estimating the system backlog information, which is obtained from multiple access interference (MAI) in the physical layer of Code Division Multiple Access (CDMA) MPR channel. Then, the proposed algorithms broadcast a retransmission probability in order to maximize the system throughput. The performance and the stability of the proposed algorithms are examined under various radio channel conditions. Compared to the proposed algorithms based on the system backlog information, the existing uniform backoff (UB) and exponential backoff (EB) algorithms are blind to such information. In order to understand the behaviour of these algorithms in MPR S-ALOHA, they are investigated with respect to various performance metrics and stability conditions. Additionally, the power ramping (PR) scheme is examined together with UB algorithm, in order to see whether it shows power capture effect in MPR S-ALOHA systems during a random access. Furthermore, the queueing performance of the MPR S-ALOHA system is investigated with an uplink traffic of the Markov Modulated Bernoulli Process (MMBP), when UB algorithm with retry limit is employed. It is also examined whether MPR S-ALOHA would be feasible for reserving a channel for a delay sensitive traffic. As a practical example, Semi-Persistent Scheduling (SPS) with initial random access in Long Term Evolution (LTE) is examined over MPR S-ALOHA, in which a traffic channel reservation for Voice-over IP (VoIP) is made at the onset of the ON period by a random access. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2012-06-11 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution 3.0 Unported |
DOI | 10.14288/1.0072824 |
URI | http://hdl.handle.net/2429/42473 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2012-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by/3.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2012_fall_seo_junbae.pdf [ 1.84MB ]
- Metadata
- JSON: 24-1.0072824.json
- JSON-LD: 24-1.0072824-ld.json
- RDF/XML (Pretty): 24-1.0072824-rdf.xml
- RDF/JSON: 24-1.0072824-rdf.json
- Turtle: 24-1.0072824-turtle.txt
- N-Triples: 24-1.0072824-rdf-ntriples.txt
- Original Record: 24-1.0072824-source.json
- Full Text
- 24-1.0072824-fulltext.txt
- Citation
- 24-1.0072824.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0072824/manifest