Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Multi-antenna and receiver slotted ALOHA packet radio systems with capture Lau, Chiew Tong 1990

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1990_A1 L38.pdf [ 9MB ]
Metadata
JSON: 831-1.0065461.json
JSON-LD: 831-1.0065461-ld.json
RDF/XML (Pretty): 831-1.0065461-rdf.xml
RDF/JSON: 831-1.0065461-rdf.json
Turtle: 831-1.0065461-turtle.txt
N-Triples: 831-1.0065461-rdf-ntriples.txt
Original Record: 831-1.0065461-source.json
Full Text
831-1.0065461-fulltext.txt
Citation
831-1.0065461.ris

Full Text

M U L T I - A N T E N N A A N D R E C E I V E R S L O T T E D A L O H A P A C K E T RADIO SYSTEMS W I T H C A P T U R E By Chiew Tong Lau B . Eng., Lakehead University, 1983 M . A . Sc., The University of British Columbia, 1985 A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF D O C T O R OF P H I L O S O P H Y in T H E F A C U L T Y OF G R A D U A T E STUDIES D E P A R T M E N T OF E L E C T R I C A L ENGINEERING We accept this thesis as conforming to the required standard T H E UNIVERSITY OF BRITISH C O L U M B I A May 1990 © Chiew Tong Lau, 1990 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of EAJECTRvcAl. E.dCxdEea.ydq The University of British Columbia Vancouver, Canada D a t e MAN 3.\ , I1<\0 DE-6 (2/88) Abstract The problem of data transmission in a packet radio system with one central base station and a number of mobile/stationary terminals is addressed. More specifically, the effects of possible collisions between packets on the inbound channel are investigated. Schemes which can be used to improve the performance are studied. The use of capture to improve the performance of slotted ALOHA systems is dis-cussed. For a power group division scheme proposed by Metzner in which a capture effect is artificially induced, it is shown that in the two power group case, the higher power packet needs only be able to tolerate interference from up to three lower power packets in order to realize most of the achievable improvement of the infinite capture model. The evaluation of the performance for more than two power groups is also considered. A packet radio system in which a capture effect exists due to the fact that mobiles will generally be at different distances from the base station is also investigated. A number of different capture and spatial distribution models are discussed. Methods for evaluating the probability qi of successful reception when there are i contending transmitters are examined. It is shown that a generalized capture model can be used to estimate qi for an example system which uses non-coherent frequency shift keying modulation. This model can be applied to other systems as well. In most practical systems, the mobiles cannot get arbitrarily close to the base station. The effects of this constraint on qi is examined. The dependence of the capture probability for a test mobile on its distance from the base station is also analyzed. The use of multiple directional antennas and receivers in a slotted ALOHA system in ii which the signals from the different transmitters are received with more or less the same powers is analyzed. It is shown that the performance of the system can be substantially improved by using directional antennas and multiple receivers. Results indicate that fewer than five antennas per receiver are required in order to achieve most of the achievable performance. A finite population Markov model is used to evaluate the performance of a mult i-antenna and receiver slotted A L O H A system in a mobile radio environment in which the signal power levels from different mobiles are no longer equal. The effects of three different antenna patterns, background noise and Rayleigh fading are studied. Here again, numerical results indicate that substantial gains are possible with the use of several antennas and receivers. It is also found that the dynamic behaviour of the system is improved. The selection of the antennas to be connected to the receivers becomes an issue if the number of receivers at the base station is less than the number of antennas . Four antenna selection schemes are compared for three different channel models, assuming an ideal antenna pattern. It is found that the scheme which selects the antennas with the largest received signal powers is nearly optimum. The effects of using a more practical non-ideal antenna pattern are also discussed. iii Table of Contents Abstract i i List of Tables ix List of Figures xi Acknowledgement xvi i 1 Introduction 1 2 Review of Related Work and Some Preliminaries 6 2.1 Random Access Techniques 6 2.1.1 Pure A L O H A 6 2.1.2 Slotted A L O H A 7 2.1.3 Carrier Sense Multiple-Access (CSMA) 7 2.1.4 Busy-Tone Multiple-Access ( B T M A ) 8 2.1.5 Tree Algorithms 9 2.2 Spatial Distribution of Mobile Users 9 2.2.1 Uniform spatial traffic density 9 2.2.2 Bell-shaped spatial traffic density . 10 iv 2.3 Channel Models 12 2.3.1 Channel Model 1 12 2.3.2 Channel Model 2 13 2.3.3 Channel Model 3 13 2.4 Antenna Patterns 14 3 Capture Effect in Packet Radio Systems 17 3.1 A Power Group Division Scheme in an Infinite Capture Environment . . 17 3.2 A Power Group Division Scheme in a Finite Capture Environment . . . . 18 3.2.1 Results for two power groups 19 3.2.2 Extension to more than two power groups 22 3.3 Capture Effect in a Mobile Radio Environment 24 3.3.1 Capture models 25 3.3.2 Spatial distribution of mobiles 26 3.4 Analysis of Capture Probabilities and Numerical Results 27 3.4.1 Capture model 1 27 3.4.2 Capture model 2 31 3.4.3 Numerical results 35 3.5 Probability of Successful Reception for a N C F S K System 37 3.6 Throughput for a Slotted A L O H A System 44 3.7 Effect of Puncturing the Spatial Traffic Density Function 46 v 3.7.1 Capture model 1 47 3.7.2 Capture model 2.1 50 3.8 Distance Dependence of Capture Probabilities 54 4 A M A R Slotted A L O H A System with Stationary Users 58 4.1 Performance Analysis 58 4.2 Numerical and Simulation Results 61 5 A M A R Slotted A L O H A System wit h Mobile Users 65 5.1 Markovian Model 66 5.2 Conditional Probabilities of Success 71 5.3 Numerical Results 73 5.3.1 Effects of increasing M and Nr 73 5.3.2 Effects of different antenna radiation patterns 74 5.3.3 Effects of changing the capture ratio 75 5.3.4 Effects of puncturing the spatial traffic density 77 5.3.5 Effects of background noise 78 5.3.6 Effects of Rayleigh fading 81 5.3.7 Effects of different user mobility models 82 5.4 Dynamic Behaviour 84 5.5 Effects of a Finite Antenna Selection Time 89 vi 6 Antenna Selection in a M A R System 93 6.1 Analysis of four Antenna Selection Schemes 93 6.1.1 Derivation of P(S |7) 95 6.1.2 Throughput evaluation 100 6.1.3 Numerical results 105 6.2 Practical Considerations 110 6.2.1 Effects of background noise I l l 6.2.2 Effects of Rayleigh fading 117 6.2.3 Effects of using a non-ideal antenna 121 6.2.4 Effects of different user mobility models 124 7 Conclusions 127 Bibl iography 130 Appendices 136 A Bounds on Truncation Errors 136 A . l Truncation Error for q i t MI, m o d e l I 136 A.2 Truncation Error for q: NCFSK 137 A.3 Truncation Error for q ^ p u n c t u r e d bell, m o d e l I 137 A.4 Truncation Error for q i t p u n c t u r e d bell, m o d e l 2.1 138 A.5 Truncation Error for P(S|7) 138 vii B Bounds on Capture Probabil i ty 142 B . l Bounds on MI, m o d e l 1 142 B.2 Bounds on q^ NCFSK 144 C Asymptot ic Value of P(S| 7,rj) 146 D Numer ica l Evaluation of the i-fold Convolution 148 D . l Convolution of a Truncated Function 148 D.2 Convolution Using Fast Fourier Transform 149 E Exper iment on Capture Effect 152 F Simulation Programs Used in Thesis 157 F . l A Two Power Group A L O H A Simulation Program 157 F.2 A n Infinite Population M A R Slotted A L O H A (Poisson Input Traffic) Sim-ulation Program 163 F.3 A n Infinite Population M A R Slotted A L O H A (Poisson Channel Traffic) Simulation Program 172 F.4 A Finite Population M A R Slotted A L O H A Simulation Program 180 F.5 A Simulation Program for Estimating qj\i 188 viii List of Tables 3.1 Channel traffic and maximum throughput as a function of the number iV 1 ) 2 of tolerable interferers 21 3.2 Comparison of simulation and analytical results for a two power group slotted A L O H A system with N1<2 = 2 22 3.3 The values of and the bound on e for different values of i with a2 = 2 and 6 = 2 (model 1 and bell-shaped spatial traffic density) 30 3.4 The lower and upper bounds on (NCFSK) for different values of i. . . 43 6.1 P(S|7) and bound on |c 5 | for different values of 7 98 6.2 Lower and upper bounds on throughput for Schemes 1, 2, 3 and 4, with iVP = 1, M = 8 and p = 0.1 104 6.3 Memory requirements for Scheme 1 with non-ideal antennas 122 6.4 Throughput for Scheme 1 with sine pattern antenna, c = 4, M = 2 and Nr = 1 122 6.5 Comparison of throughputs for M M 1 and M M 2 with c = 4, p = 0.1, sine antenna pattern, antenna selection Scheme 2 and channel model 1 126 6.6 Comparison of throughputs for M M 1 and M M 2 with c = 4, p = 0.1, sine antenna pattern, antenna selection Scheme 2 and channel model 3 126 ix D . l Lower and upper bounds on the throughput of the four antenna selection schemes with channel model 3 150 F . l C P U time for the two power group A L O H A simulation program. Number of time slots processed = 105 157 F.2 C P U time for the infinite population M A R A L O H A simulation program (Poisson input traffic). Number of time slots processed = 105 163 F.3 C P U time for the infinite population M A R slotted A L O H A simulation program (Poisson channel traffic). Number of time slots processed = 10 4. 172 F.4 C P U time for the finite population M A R slotted A L O H A simulation pro-gram. Number of time slots processed = 5 x 104 180 x L i s t o f F i g u r e s 2.1 Uniform and bell-shaped spatial traffic density functions 11 2.2 Antenna radiation patterns (four sectors) 16 3.1 Maximum throughput, Smax, as a function of the number of power groups, fc 19 3.2 Maximum throughput, Smaxi as a function of the Group 2 power, T 2 . . . 24 3.3 Piecewise linear function, g(z), as a function of the signal-to-interference ratio, z, for fixed c and different values of a 34 3.4 Probability of successful reception, qi, as a function of the number of con-tending transmitters, t , for capture model 1, using /? = 4 36 3.5 Probability of successful reception, qi, as a function of the number of con-tending transmitters, i, for capture model 2.1 37 3.6 Probability of successful reception, (ft, as a function of the number of con-tending transmitters, i, for capture model 2(PL) with bell-shaped spatial density model 38 3.7 Probability of successful reception, qi0, a s a function of capture ratio, c, for capture model 2(PL) with bell-shaped spatial traffic density model. . 39 xi 3.8 Probability of successful reception, ^ , as a function of the number of con-tending transmitters, i, for capture model 2(PL) with uniform spatial den-sity model 40 3.9 Probability of successful reception, g,-, as a function of the number of con-tending transmitters, i, for capture models 1, 2.1 and 2(PL) with c = 4 and both spatial traffic densities 41 3.10 Probability of successful reception, <j;, as a function of the number of con-tending transmitters, i, for a NCFSK system 42 3.11 Throughput 5 as a function of pQ for capture model 1 with c = 4, N = 50 and pr = 10po 45 3.12 Throughput 5 as a function of p0 for capture model 2.1 and 2(PL) with c = 4, N = 50 and pr = 10p„ 46 3.13 Probability of successful reception, ft, as a function of the number of con-tending transmitters, i, for capture model 1 with a 2 = 2 50 3.14 Probability of successful reception, ft, as a function of the number of con-tending transmitters, t, for capture model 2.1 with c = 4 51 3.15 Throughput, S, as a function of pa for capture model 2.1 with punctured bell-shaped spatial traffic density, c = 4, N = 50 and pr = 10po 53 3.16 Dependence of probability of capture on distance, r t , of test mobile from the base station. Finite population model with TV = 50, pP = 10po, c = 4 and uniform spatial traffic density assumed 56 xii 3.17 Dependence of probability of capture on distance, r t , of test mobile from the base station. Finite population model with N = 50, pr — 10po, c = 4 and bell-shaped spatial traffic density assumed 57 4.1 Throughput, S, as a function of channel traffic, G, for iV r = 1 and 2 and M = 1,2,4 and 8. The points with 99 percent confidence intervals are obtained by simulations in which the input traffic is Poisson 62 4.2 Maximum throughput, S as a function of the number of regions, M , for Nr = 1 to 8 63 5.1 State transition of a terminal 67 5.2 State diagram 68 5.3 Throughput, 5, as a function of channel traffic, G, for N = 100, pr = 10po, c = 4 and antenna pattern: sine function 74 5.4 Throughput, S, as a function of channel traffic, G, for N = 100, pr = 10po, c = 4 and antenna pattern: ainc-cos function 75 5.5 Throughput, 5, as a function of channel traffic, G, for N = 100, pT = 10po, c = 4 and antenna pattern: red function 76 5.6 Maximum throughput, S, as a function of the number of sectors, M, for N = 100 and c = 4 77 5.7 Maximum throughput, S as a function of capture ratio, c, for N = 100 and antenna pattern: sine function 78 5.8 Throughput, 5 as a function of channel traffic, G, with p = 0.05, N = 100, pr = 10po, c — 4 and antenna pattern: sine function 79 xiii 5.9 Throughput, 5 , as a function of channel traffic, G, with n = 0.2, N = 100, pr = 10po> c = 4 and antenna pattern: sine function 80 5.10 Throughput, S, as a function of channel traffic, G, with n = 1.0, N = 100, pr = 1 0 p o , c = 4 and antenna pattern: sine function 81 5.11 Throughput, S, as a function of channel traffic, G, with Rayleigh fading, N = 100, pr = 10po, c = 4 and antenna pattern: sine function 83 5.12 Throughput, 5 as a function of channel traffic, G, for mobility model 2, N = 100, Pr = 10p o , c = 4, sine antenna pattern and channel model 1. . . 84 5.13 Throughput, 5 as a function of channel traffic, G , for mobility model 2, N = 100, pr = 10po, c = 4, sine antenna pattern and channel model 3. . . 85 5.14 Expected drift, dn, and steady-state occupancy probability, 7 r n , as a func-tion of the number of R-mode users for N = 100, Nr = 1, p0 = 0.01, Pr = 0.1, c = 4 and antenna pattern: sine function 87 5.15 Expected drift, dn, and steady-state occupancy probability, 7T n, as a func-tion of the number of R-mode users for N = 100, iV r = 2, pa = 0.01, Pr = 0.1, c = 4 and antenna pattern: sine function 88 5.16 Average number of R-mode users as a function of pa for TV = 100, pr = 1 0 p o , c = 4 and antenna pattern: sine function 89 5.17 Expected drift, dn, and steady-state occupancy probability, 7rn, as a func-tion of the number of R-mode users for N = 100, JV"P = 1, pa = 0.005, pr = 0.9, c = 4 and antenna pattern: sine function 90 5.18 Maximum channel utilization, t 7 m a x , as a function of the number of sectors, M , for N = 100 and c = 4 92 xiv 6.1 Probability of success given the received power, P(S|7), for p — 0 99 6.2 Probability of success given the received power, P(S|7), for p = 0.1. . . . 100 6.3 Throughput, S, as a function of channel traffic per sector, g, for Scheme 1 with c = 4 and p = 0 106 6.4 Throughput, S, as a function of channel traffic per sector, g, for Scheme 2 with c = 4 and p = 0 107 6.5 Throughput, S, as a function of channel traffic per sector, g, for Scheme 3 with c = 4 and p = 0 108 6.6 Throughput, S, as a function of channel traffic per sector, g, for Scheme 4 with c = 4 and p = 0 109 6.7 Throughput, S, as a function of channel traffic per sector, g, with c = 4 and p = 0 110 6.8 Probability of success, Pj(S), if the sector with jth largest received power is selected, as a function of g for c = 4, p = 0 and M = 8 I l l 6.9 Probability of success, Pj(S), if the sector with j t h smallest non-zero received power is selected, as a function of g for c = 4, p = 0 and M — 8. 112 6.10 Throughput, 5, as a function of channel traffic per sector, g, with c = 4 and p = 0.1 113 6.11 Throughput, 5, as a function of channel traffic per sector, g, with c = 4, p = 0 and ?/ = 0.2 115 6.12 Throughput, 5, as a function of channel traffic per sector, g> with c = 4, p = 0 and 77 = 0.5 116 xv o 6.13 Throughput, S, as a function of channel traffic per sector, g, with c = 4, p = 0 n = 0.2 and actual background noise = 0.4 118 6.14 Throughput, 5, as a function of channel traffic per sector, g, with Rayleigh fading, c = 4, p = 0 and rj = 0 120 6.15 Throughput, 5, as a function of channel traffic per sector, g, with Sine antenna pattern, c = 4, p = 0 and n = 0 123 6.16 Throughput, 5, as a function of channel traffic per sector, g, with Sine antenna pattern, c = A, p — 0.1, n = 0.2 and Rayleigh fading 125 D . l Probability of success given the received power, P(S |7) , for p = 0 and channel model 3 151 E. l Setup of the experiment on capture effect 153 E.2 Schematic diagram of a F S K modem 154 E.3 Bit error rate as a function of test signal power, rt, with and without interfering signal 156 xvi Acknowledgement I am grateful to my research supervisor, Dr. Cyri l Leung, who has provided me with many helpful suggestions and constant supervision. I would also like to thank the following people: Dr. Hyong Lee for his useful suggestions, Dr. Son Vuong and Dr. Victor Leung for reviewing this thesis, Mr . Ron Jeffrey for setting up the experiment on capture effect and my wife and family for their support. This research was partially supported by N S E R C grant A-1731 and a University of Brit ish Columbia graduate fellowship. xvii Chapter 1 Introduction Data communication over VHF/UHF mobile radio channels has attracted a great deal of commercial and research interest in the last decade. There is a wide variety of existing and planned systems whose operation depends on the ability to efficiently send data over a radio channel. Examples include cellular telephone systems [1], mobile data terminals [2] and 'tetherless' communication systems of the future [3]. Mobile data terminals are now commonly used by many businesses as well as public safety agencies. Compared to analog (voice) communication, digital communication can provide greater accuracy and lead to higher employee productivity. It also allows the mobile user to have direct access to a computerized data base without the intervention of a human operator. Due to the bursty nature of computer traffic, the use of a dedicated channel would result in a very inefficient usage. In a data communication system in which the subscribers are mostly mobile terminal users, an effective way to communicate is to use packet switching techniques over a broadcast radio channel [4-7]. The term "packet radio" is often used to describe such a system. The message to be transmitted is first divided into data blocks. From each data block, a data packet is formed by attaching a header which contains source and destination addresses, control information and parity check bits. Since a packet occupies the channel for only a short time, packets from different users can share the same channel. The allocation of channel time to different users is governed by the channel access protocol. There are a number of different types of channel access 1 Chapter 1. Introduction 2 protocols, e.g. fixed assignment techniques and random access techniques. Random access techniques are usually preferred for systems with bursty traffic. The principal advantage of using these techniques is that they are efficient when operated under light to moderate traffic [8]. On the inbound channel in a packet radio system consisting of a central base station and a number of mobile user terminals, a packet collision occurs whenever two or more users transmit at about the same time. This results in a destruction of possibly all the packets arriving at the base station, thereby reducing the efficiency. One of the simplest protocols for channel access is pure ALOHA [9] in which a user can transmit a packet of data any time it desires. In order to increase the protocol efficiency, several schemes have been suggested for reducing the probability of a collision, e.g. Slotted ALOHA, CSMA, CSMA-CD, BTMA and Tree Algorithm [10-19]. The choice of a channel access scheme usually depends on network topology, perfor-mance requirements and cost [7]. In a mobile radio environment in which a full connec-tivity of mobile terminals cannot be achieved, activity-sensing schemes such as CSMA may be inferior to the ALOHA scheme due to the existence of "hidden" terminals [20]. Most of the collisions can be avoided by having the base station transmit a busy tone on the outbound channel whenever the inbound channel is busy [13]. This busy-tone channel requires additional bandwidth. In this thesis, we study a new scheme in which multiple base station directional antennas and receivers, as well as "capture" effects, are used to improve performance on the inbound channel. A slotted ALOHA protocol is assumed even though the same technique could also be used with other protocols. The model studied assumes that the mobiles are randomly distributed on a circular plane centered at the base station. The circular plane is divided into a number, M, of sectors. The base station has M directional Chapter 1. Introduction 3 antennas each aiming at one sector. Also available at the base station is a number, Nr, of receivers.1 Channel access time is divided into slots. At the beginning of a time slot, Nr of the antennas are selected and connected to the receivers. Once made, such connections last until the end of the time slot. The signals from the Nr selected antennas are processed in the hope that Nr distinct data packets can be successfully decoded. The signal on the remaining M — Nr antennas are by necessity ignored. It is assumed that acknowledgements from the base station are received perfectly by the mobile users. This assumption is reasonable because the station usually transmits at a higher power level than a mobile; besides, there is no contention on the outbound channel. The thesis is organized as follows: In Chapter 2 some earlier works on the random access protocols and signal propaga-tion are reviewed. First, some channel access techniques including pure ALOHA, slotted ALOHA, CSMA, CSMA-CD, BTMA and Tree Algorithms are briefly described. Next, we consider two models of spatial traffic density functions; namely, a uniform spatial traffic density function and a bell-shaped spatial traffic density function. Three channel models are also discussed: a channel with flat terrestrial propagation, a channel with a constant background noise power and a channel with Rayleigh fading. Finally, several models of the radiation patterns of directional antennas are described. It has been found that the existence of a capture effect results in performance improve-ments in random access protocols [10,21-43]. The capture effect refers to the capability of the receiver to successfully decode a packet in the presence of a number of contending packets. In Chapter 3, the effect of capture on performance in a number of different systems is analyzed. We first study a system in which the existence of a capture effect is 1For economic reasons, the number of receivers may be less than the number of sectors. In practice, there are usually at least two receivers at the base station: one main and one back-up receiver. Chapter 1. Introduction 4 artificially created by dividing the users into different power groups. Next, we consider capture effects which arise naturally, such as in a mobile radio environment. The proba-bility qi of successful reception in a mobile radio random access channel with i contending mobiles transmitting to a central base station is studied for a number of different capture and spatial distribution models. It is shown that a generalized capture model can be used to estimate ft for an example system which uses non-coherent frequency shift key-ing modulation. This model can be applied to other systems as well. An example of the use of the ft's in the throughput evaluation of a finite population slotted ALOHA system is given. In most practical systems, the mobiles cannot get arbitrarily close to the base station. The effect of this constraint on ft is examined. Finally, the dependence of the capture probability for a test mobile on its distance from the base station is obtained. We begin our study of Multi-Antenna and Receiver (MAR) slotted ALOHA systems in Chapter 4. Here we consider the case where there is no capture, i.e. a packet is suc-cessfully decoded if it is the only transmitted packet; otherwise, no packet is successfully decoded. The channel is assumed to be noiseless and the received signal strength from each user is assumed to be more or less constant. The receiver is then able to select the sector (or region) which has only one active user by measuring the received signal strength. The performance of this simple model is analyzed. In Chapter 5 , a finite population Markovian model is used to evaluate the throughput performance of a MAR slotted ALOHA system. A packet radio environment is assumed so that the received signal strengths from different mobiles are no longer equal. The performance improvement which results from the use of multiple antennas and receivers, as well as a capture effect, is studied. Results are presented to illustrate how the through-put is affected by the number of antennas and receivers, the capture ratio, the radiation pattern of the base station receiving directional antennas, the presence of background Chapter 1. Introduction 5 noise and Rayleigh fading. The dynamic behaviour of the system is also investigated. The issue of how the Nr out of M antennas are selected is treated in Chapter 6. Here, a number of antenna selection schemes including the optimum and some sub-optimum but simpler-to-implement selection schemes are analyzed under the assumption that the antenna pattern is ideal. The effects of background noise, Rayleigh fading and a non-ideal antenna pattern are also considered. The main contributions of the thesis are summarized in Chapter 7, which also lists a number of suggestions for further research. Chapter 2 Review of Related Work and Some Preliminaries Some related earlier works are reviewed in this chapter. First, several random access techniques are briefly described. Next, we address two models of spatial distribution of mobile users; namely, uniform and bell-shaped spatial traffic densities. Then, a number of channel models including flat terrestrial propagation loss, background noise and Rayleigh fading are described. Finally, we consider three different antenna radiation patterns which will be used in the evaluation of system performance in subsequent chapters. 2.1 Random Access Techniques 2.1.1 Pure ALOHA This is the simplest random access technique [9]. Each terminal transmits as soon as a packet arrives. It then waits for an acknowledgement from the receiver. If no acknowl-edgement arrives after some timeout interval, the terminal retransmits its packet after some random time interval. Since each terminal transmits its packet independently, there is a possibility that two or more packets will collide at the receiver. It is assumed that all the packets involved in a collision are destroyed. The probability of collision increases with the input traffic. The theoretical maximum throughput of the system, based on the assumption that the channel traffic has a Poisson distribution, is found to be ^ w 0.184. 6 Chapter 2. Review of Related Work and Some Preliminaries 7 2.1.2 Slotted A L O H A Packet synchronization is employed in the slotted ALOHA scheme in order to reduce the likehood of a collision [10]. Any terminal which has a packet ready to send will start transmitting only at the beginning of a slot. In this case, no partial collisions can occur. The theoretical maximum throughput is improved to j « 0.368. 2.1.3 Carrier Sense Multiple-Access ( C S M A ) CSMA employs a listen-before-talk technique to access a common channel [11]. A ter-minal listens to the channel to determine if there is any on-going transmission. It then decides whether to transmit or not based on the protocol used: 1. Nonpersistent CSMA If the terminal senses no carrier on the channel, the transmission is made; otherwise, it waits until some later time and repeats the same procedure. 2. 1-persistent CSMA If the terminal senses no carrier on the channel, the transmission is made; otherwise, it continues to monitor until the channel is free and then transmits its packet. 3. p-persistent CSMA Step 1. If the terminal senses no carrier on the channel, it transmits with probability p\ with probability (1 — p) it delays its decision as to whether to transmit to the next time slot and performs step 2. If the channel is busy, the terminal continues to monitor until the channel becomes idle and then repeats step 1. Chapter 2. Review of Related Work and Some Preliminaries 8 Step 2. If the channel is free, step 1 is repeated; otherwise, the terminal waits for some random number of time slots before repeating step 1. In a CSMA system, the probability of a collision is reduced. However, a collision is still possible due to finite propagation delays and detection times. In the event of a collision, there is no point in completing the transmission of the whole packet. One way of detecting a collision is to use the listen-while-talk technique [12]. In the CSMA-CD (collision detection) scheme, the transmitting terminal listens to its own transmitted message. A collision is detected when the message is garbled. The transmission is then immediately aborted and the retransmission procedure is engaged. The throughput is improved by cutting down on the collision time. 2.1.4 Busy-Tone Multiple-Access ( B T M A ) In many situations, especially in the mobile radio network, not all terminals in the network can hear each other's transmission (terminals hidden from each other but not from the base station). Due to the existence of the hidden terminals, the performance of a CSMA system can be badly degraded [13]. A technique known as BTMA [13] has been proposed to overcome the hidden terminal problem. A similar scheme, namely Idle-Signal Casting Multiple Access with collision detection (ICMA-CD), has also been proposed [17]. In the BTMA scheme, the available channel bandwidth is divided into a message channel and a busy tone channel. Any terminal that has a packet ready to transmit must check the status of the message channel by sensing carrier on the busy tone channel. The base station will transmit a busy tone signal on the busy tone channel if it senses the message channel is busy, i.e. a terminal is transmitting. Since all terminals can receive Chapter 2. Review of Related Work and Some Preliminaries 9 the busy tone signal from the station whenever the message channel is being used, the hidden terminal problem would therefore be lessened. 2.1.5 Tree Algorithms In the above random access schemes, terminals with new packets are permitted to trans-mit . regardless of whether or not there are old packets in some terminals waiting for retransmissions. In the Tree Algorithms [14], no new packet is allowed to be transmit-ted if there are packets waiting for retransmissions, i.e. terminals with new packets are permitted to transmit only after the initial collision has been resolved using some col-lision resolution algorithm ( C R A ) . One simple C R A is as follows: after a collision, all terminals involved toss a fair coin. A terminal whose toss is H E A D retransmits in the next slot, whereas one whose toss is T A I L retransmits after the collision, if any, among H E A D terminals has been resolved. The maximum system throughput using this simple C R A is 0.347. Higher throughput can be achieved by using some dynamic C R A [14, 8] (maximum throughputs of 0.43 and 0.46). 2.2 Spatial Distribution of Mobile Users Two models of the spatial distribution of the mobile users are now described. 2.2.1 Uniform spatial traffic density-It is commonly assumed that the mobile terminals are uniformly distributed over a cir-cular plane of radius Rm centered at the base station. The uniform spatial traffic density function is Chapter 2. Review of Related Work and Some Preliminaries 10 0 < r < Rn (2.1) otherwise [Rm where G = Gu(r)2nr dr is the total average channel traffic per time slot. The Jo probability distribution function (P.D.F.) of the distance R between a mobile and the base station is given by FR(r) £ 7 J GU(X)2TTX dx, 0, 0 < r < Rm otherwise = < 0 < r < Rr 0, otherwise (2.2) and the corresponding probability density function (p.d.f.) is Mr) = { IT ST ' 0, 0<r<Rm otherwise. (2.3) 2.2.2 Bell-shaped spatial traffic density The uniform spatial traffic density described in Section 2.2.1 can be approximated by a bell-shaped spatial traffic density function [31] centered at the base station, i.e., Chapter 2. Review of Related Work and Some Preliminaries 11 c o •a >» in C Bell-shaped Uniform \ N \ \ \ \ \ \ \ \ \ \ \ \ — — 0 Rm Distance Figure 2.1: Uniform and bell-shaped spatial traffic density functions. The corresponding P.D.F. and p.d.f. of the distance R between a mobile and the base station are FR{T) = erf •V/TT / r > 2 \Rms 0 < r < co and / * ( r ) = ^ - e T I J C J , 0 < r < oo, (2.5) (2.6) where er/(y) = f^ e x' dx is the error function [44]. The two spatial traffic density functions are shown in Figure 2.1. Chapter 2. Review of Related Work and Some Preliminaries 12 2.3 Channel Models The performance of the MAR slotted ALOHA system will be studied using the three different channel models described below. 2.3.1 Channel Model 1 In the flat terrain mobile radio environment, three kinds of waves exist at the receiving end; namely, a direct wave, a reflected wave and a surface wave. The surface wave is usually neglected at frequencies above 300 MHz because the energy absorbed by the earth increases with frequency. One existing model [45, 46] for the received signal power that is made up of direct and reflected waves is Tr = Tt9r9t {^J (2.7) where Tr and Tt are the received and transmitted powers, gr and gt are the receiver and transmitter antenna gains, hr and ht are the receiver and transmitter antenna heights, and r (much greater than hr and ht) is the distance between the transmitter and the receiver. It is assumed that each mobile terminal uses an omnidirectional antenna and transmits at a constant power. The receiver antenna gain gr depends on the orientation angle 0 of the transmitter. The received signal power T r is given by r , ( « . r ) = ± $ r (2.8) Chapter 2. Review of Related Work and Some Preliminaries 13 where kr is a constant which depends on 1%, gti hr and ht. We can normalize the received signal power by letting kr = 1 and gr{9) = 1 at 0 = 0. 2.3.2 Channel Model 2 In practice, the receiver antenna will inevitably pick up some noise together with the received signal. In addition, the receiver itself may generate noise. For a receiver with a fixed bandwidth operating at a constant temperature, it is reasonable to assume that the background noise power is constant. The second channel model is used to examine the effect of background noise on the performance of the system. As in model 1, it is assumed that the transmitted signal is received with power, Tr, as given by (2.8). In addition, the received signal contains a noise component with normalized power rj. This means that the actual noise power T n is rf times the signal power received from a mobile which is at distance Rm from the base station, i.e. r. = , ^ . (2.9) tn 2.3.3 Channel Model 3 It has been established [47, 48] that in most urban areas, propagation of VHF/UHF radio waves takes place mostly by diffraction or reflection by obstacles in the vicinity of the mobile. Under certain conditions, it can be shown that the short-term amplitude of the received signal is well approximated by a Rayleigh distribution. To include the effects of this Rayleigh fading, the third channel model assumes that the received signal amplitude is Rayleigh distributed with a mean determined by the Chapter 2. Review of Related Work and Some Preliminaries 14 fiat-terrestrial propagation model. This third model results in the received signal power having an exponential distribution with a mean, p, given by (2.8), i.e. frM = ^ e~i. (2.10) 2.4 Antenna Patterns Three different antenna patterns will be considered. 1. Red function: 9r(8) = 2 — U — 2 0, otherwise (2.11) where gr is the normalized power gain, 0 is the orientation angle and 0BW is the half-power beamwidth. This is the model of an ideal antenna. Although no real antenna can be represented by a red function, equation (2.11) is considered for comparative purposes. 2. Sine function: *(*) = A Ts ^ (2-12) (2.78 0\\ 6Bw J where gr, 0 and 0BW are as denned in (2.11). Some antenna patterns can be modelled approximately by a sine function [49]. Figure 2.2 (solid lines) shows four antennas aiming at different directions with 0BW = 90°, each antenna having a radiation pattern as defined by (2.12). Chapter 2. Review of Related Work and Some Preliminaries 15 It is preferable that the gain fall off rapidly at the two half-power angles ± ^ i £ . and remain as low as possible outside the main lobe. This would reduce any interference from outside the required coverage zone (in this example, the required coverage zone is a quadrant) of an antenna. 3. Sinc-cos function: sin 11.35 (cos ( ^ ) - l ) ] = . ' / / : B \ V j . (2-i3) 11.35 (cos ( ^ ) - 1) where gr, 9 and BBW are as defined in (2.11). This function has a steeper gain fall-off rate at the half-power angles compared to the sine function (Figure 2.2 in dashed lines). Chapter 2. Review of Related Work and Some Preliminaries 16 Figure 2.2: Antenna radiation patterns (four sectors). Chapter 3 Capture Effect in Packet Radio Systems In a packet radio system, the signal received at the base station from a given terminal will be subject to attenuation (a function of the base-to-terminal distance) and possibly fading. When packets from different terminals collide, it is possible that the packet with the strongest received signal strength will be captured 1 by the receiver [10,21-37]. The capability of the receiver to capture a signal depends on the type of modulation as well as the coding scheme used [39]. In this chapter, we study the performance improvement due to capture effect in a number of different systems. We first consider a system in which a capture effect is induced by having the users transmit their packets at different power levels. We then focus on a capture effect which exists naturally in a mobile radio environment. The differences in performance arising from a number of different capture and spatial distribution models are analyzed. 3.1 A Power Group Division Scheme in an Infinite Capture Environment It has been shown [21] that a capture effect can be artificially created which results in an improved throughput 2. Specifically, the throughput performance of an A L O H A system is improved by dividing the users into a number of groups {1, 2, • • •, k} with different 1It is assumed that the captured packet is successfully decoded. 2Throughput is defined as the average number of successfully received packets per time slot. 17 Chapter 3. Capture Effect in Packet Radio Systems 18 powers {Ti, r 2 , • • •, I \} where Ti > T 2 > • • • > I V It is assumed that the signal from the different users are subject to a constant attenuation. The improvement comes about as a result of the assumption that in the event of a collision between a group i packet and any number of packets transmitted by users in groups with higher indices, the group i packet can still be successfully decoded. This amounts to an infinite capture effect. If two or more group i packets collide, they are assumed to be destroyed. It is shown in [21] that the maximum system throughput Smax increases with the number of power groups k according to Smax = e~Gl (3.1) where = 1 — e - G ' + » , i = 1,2,... ,k — 1, is the optimum channel traffic for group i and G\ = 1. Figure 3.1 is a plot of the maximum system throughput as a function of k. With two power groups (fc = 2), the maximum throughput of a slotted A L O H A system can be increased from 0.368 to 0.531 (about 44 percent maximum throughput improve-ment). The maximum throughput approaches unity as fc tends to infinity. However, the convergence is slow; for example, 18 different power groups are needed in order to achieve a 90 percent maximum throughput. A maximum throughput of 95 percent requires 37 different power groups. 3.2 A Power Group Division Scheme in a Finite Capture Environment We now analyze the performance of the power group division scheme in a finite capture environment [50]. It is assumed that only a certain level of interference with a group i packet by other lower power group users can be tolerated. Beyond this point, decoding Chapter 3. Capture Effect in Packet Radio Systems 19 o I i i I i i 1 i i I i i 1 t i I i i 1 4 7 10 13 16 19 Number of power groups Figure 3.1: Maximum throughput, Smax, as a function of the number of power groups, k. of the group i packet becomes ineffective. 3.2.1 Results for two power groups Consider a slotted ALOHA system with user groups 1 and 2 and corresponding powers Ti and T 2 . Let iV 1 ( 2 denote the number of group 2 interferers which can be tolerated by a group 1 packet. Also let Si and Gi, i = 1,2, denote the throughput (average number of successful packets per time slot) and the average channel traffic (measured in number of packets per slot) for group i users. Assuming that the channel traffic is Poisson, we obtain Chapter 3. Capture Effect in Packet Radio Systems 20 S i = G\ e Gl Pr{no more than Ni<2 group 2 packets} = Gi e~G> £ =1 e~G* (3.2) 3=0 3' and S2 = G2 e °2 Pr{no group 1 packet} = G2e-G*e-Gl. (3.3) The partial derivatives of Si and £2 with respect to Gi and G2 are given by d b l (1 - Gi) e"°» £ - f e " G 2 (3-4) dGi v dG2 1 £ 0v i! j ! / = - ^ e _ G l ^ r e " G 2 (3-5) ||- = e'-°' (3.6) | ^ = ( l - G a ) e - ° ' e - ^ . (3.7) The values of Gi and t7 2 which maximize S = (£1 + S2) can then be obtained by setting and equal to 0. For Ni<2 — 1, we get the following set of linear equations G a ( l + G 2 ) = 1 C7 2 ( l + C71) = 1. (3.8) (3.9) Chapter 3. Capture Effect in Packet Radio Systems 21 G{ G\ c >-'l,max c '-'max 0 G\ + G*2 = \ S\,max 4" S2,max — e e"1 1 0.618 0.618 0.291 0.180 0.470 2 0.623 0.801 0.318 0.193 0.511 3 0.628 0.919 0.330 0.196 0.526 4 0.631 0.976 0.335 0.196 0.530 5 0.632 0.995 0.336 0.196 0.531 oo 0.632 1.000 0.336 0.196 0.531 Table 3.1: Channel traffic and maximum throughput as a function of the number JVii2 of tolerable interferers. Solving (3.8) and (3.9) simultaneously yields G\ = G\ = v ^~ 1 and a maximum through-put Smax = 0.47. For i \ r 1 > 2 > 2, a set of non-linear equations is obtained and can be solved numerically. The optimum values of G\, G2, 5i, 5 2 and 5 for different values of JV1)2 are shown in Table 3.1. The case 7V1>2 = 0 corresponds to the classical slotted ALOHA system, whereas 7V1)2 = oo corresponds to the "infinite capture" assumption used in [21]. It can be seen that the maximum throughput Smax approaches its asymptotic value (^1,2 = oo) quite rapidly. For iV l i 2 = 2, 5 m o x is within 4 percent of its asymptotic value. The value of JV1)2 in an actual system will be determined by the powers Ti , T 2 and the capture ratio c. The significance of c is that if the received power of a signal is greater than c times the total interference, then it can be successfully decoded. As an example if c = 4, Ti = 10W and T 2 = 1W, JV1)2 = [^-J = 2 where [xj = greatest integer less than or equal to x. The throughput values calculated using (3.2) and (3.3) and those estimated by a Monte Carlo simulation in which the input traffic is Poisson are compared in Table 3.2 Chapter 3. Capture Effect in Packet Radio Systems 22 Simulation results Analytical results using (3.2) and (3.3) input traffic channel traffic output traffic group 1 group 2 Gi G2 Si s 2 Si s 2 0.1 0.10 0.1105 0.1297 0.0985 0.1010 0.0989 0.1020 0.2 0.10 0.2630 0.1533 0.2000 0.1007 0.2021 0.1011 0.3 0.10 0.5137 0.2113 0.2992 0.0999 0.3069 0.1023 0.1 0.15 0.1109 0.2069 0.0986 0.1507 0.0991 0.1505 0.2 0.15 0.2583 0.2549 0.1994 0.1504 0.1990 0.1526 0.3 0.15 0.5128 0.3735 0.2994 0.1512 0.3051 0.1539 Table 3.2: Comparison of simulation and analytical results for a two power group slotted A L O H A system with 7Y 1 ) 2 = 2. for i V i ^ = 2. A listing of the simulation program is given in Appendix F . l . The results in Table 3.2 were obtained assuming a retransmission window of 80 slots. The 99 percent confidence intervals for the channel and output traffic are within 7 percent of the mean values. It might be noted that for normal operation, i.e. Gi < G\ and G2 < G\, it is reasonable to assume that the channel traffic is Poisson. 3.2.2 Extension to more than two power groups The results of Section 3.2.1 can be generalized to the case of k > 2 power groups. For a given set of group powers {Ti, r 2 , • • • ,Tfc} and capture ratio c, the number Nij of group j (> i) interferers which can be tolerated by a group i packet is a function of the number of interferers from other groups {i + 1, i + 2, • • •, j — 1, j + 1, • • • ,&}. The set of allowable values for N^j must satisfy Chapter 3. Capture Effect in Packet Radio Systems 23 i=»+i c The equations for the throughputs are Sk = Gk e~Gl- e-G>-Sk-i = Gk-i e" Ji=0 *1' e ii=0 ' l ' h=0 111 where and A^ fc—i,k—»+l,max — cTk. J,=0 *»• (3.11) (3.12) n+i-k-l n = fc — i + 2, fc — i + 3, (3.13) As an example, we consider the case & = 3. For given minimum and maximum power levels r 3 and Tit a value for T 2 can be selected which yields the highest throughput S = Si + S2 + S3. Figure 3.2 shows the maximum throughput (over G\, G2 and <J3) as a function of r 2 , for = 100, T3 = 1 and c = 4. As can be seen T 2 = y/TiT3 = 10 yields a good throughput of about 0.60. The corresponding value with infinite j£ is 0.626. It is conjectured that a good choice for the intermediate group powers {r 2, r 3, • • •, r^ .x} given Ti and Tk is to choose the powers such that = ^ = • • • = JAJ- = • • • = fpy> as long as Chapter 3. Capture Effect in Packet Radio Systems 24 0.8 0 4 ' 1 1 I . i i i I i i i , 1 i , 1 , * 0 20 40 60 80 100 Group 2 power Figure 3.2: Maximum throughput, Smax, as a function of the Group 2 power, T 2 . the resulting NijtTa&x is not less than 1. The resulting group powers {Ti ,T 2 , • • •, Tj,} form a geometric series with a common ratio rg = ( f j - ) 1 ^ - The intermediate group power is given by Ti = Tlr^1. (3.14) 3.3 Capture Effect in a Mobile Radio Environment In the case where all packets are transmitted with the same power, a capture effect can still exist as a result of path attenuation and/or fading. In the remainder of this chapter, we study a number of capture and spatial traffic density models in a mobile radio environment in which signals are subject to path attenuation [51]. Chapter 3. Capture Effect in Packet Radio Systems 25 Suppose that all the mobile users transmit at a constant power. Since the mobile users will be at different distances from the base station, their respective received signal powers will not be the same. In the event of a collision between the data packets, it may still be possible for the receiver to successfully decode the packet with the highest signal strength. It is assumed that the received signal powers are more or less constant over a packet duration. The performance improvement in various systems which results from the ability of the receiver to capture a signal has been studied in [10,21-43]. 3.3.1 Capture models Two capture conditions for a packet from mobile t have been commonly assumed, namely: r t > c r i , ; = 1 , 2 , j ^ t (3.15) and Tt>c J2 ri> (3-16) where i is the number of on-air packets, P*, k = 1,2, is the received power of mobile k, and c is the capture ratio. Condition (3.15) results in a somewhat optimistic model. However, its use [10,21-27] often leads to simpler analytic derivations. Condition (3.16) has been used in [28-37]. Here, we introduce a capture condition in which successful decoding of a test packet is a probabilistic function of the test signal-to-interference ratio Z denned by (3.17) Chapter 3. Capture Effect in Packet Radio Systems 26 where I \ n t == £ Tj. For a given value of Z, the probability that a test packet from mobile t is successfully decoded is P(S\z)={ 0, z < 1 (3.18) 9(z), z>l where g(z) is a function which depends on the type of modulation and coding used. It might be noted that the use of spread-spectrum systems could allow successful decoding even for values of Z less than unity. It can be seen that condition (3.16) is a special case of (3.18) with P(S|z) = u(z — c) where u(z) is the unit step function. For convenience, we will refer to condition (3.15) as capture model 1. The conditions implied by (3.18) and (3.16) will be termed capture models 2 and 2.1 respectively. Model 2 will be used to examine the sensitivity of the probability qi of successful reception given i contending packets to deviations from model 2.1. 3.3.2 Spatial distribution of mobiles The probability of capture qi will also depend on the spatial distribution of the mobiles around the base station. It is assumed that the locations of the mobiles are independent random variables. Two models for the spatial distribution of mobiles as described in Section 2.2 are considered. We can normalize the distance between a mobile and the base station to Rm. The p.d.f. of the normalized distance R for a uniform spatial distribution of mobiles is Chapter 3. Capture Effect in Packet Radio Systems 27 2r, 0 < r < 1 (3.19) 0, otherwise and for a bell-shaped spatial distribution of mobiles is /a(r) = 2r e~*r\ 0 < r < oo. (3.20) These two density functions will be used to illustrate the dependence of ft on the spatial distribution of the mobiles. 3.4 Analysis of Capture Probabilities and Numerical Results In this section, we examine the capture probability ft for the different capture and spatial distribution models discussed previously. Clearly, q0 = 0 and ft = 1. So in the sequel, the expressions derived for ft will apply for i = 2,3,4, • • •. 3.4.1 Capture model 1 We first derive a general expression for ft for capture model 1. Here, it is possible to consider a more general normalized received power to distance relationship of the form (3.21) Chapter 3. Capture Effect in Packet Radio Systems 28 In (2.8), the value of 0 is 4. In practice, the power loss factor /? can vary between 2 and 5 depending on the terrain. Note from (3.21) and (3.15) that a test packet from mobile t is assumed to be suc-cessfully received if and only if Ri >ctRt, j = 1,2, • • • ,i, (3.22) where a = c£. Thus we have /•oo qi = i fRt(rt) Pr{R1,R2,-,Rt_1,Rt+1,-,Ri > art} drt Jo roo r roo "I«—1 = i jo / B , ( r « ) [ y ^ /^(r,-)^-] drt. (3.23) We now consider the evaluation of (3.23) for the uniform and bell-shaped spatial traffic density functions. Uniform spatial traffic density The distances R\, R2, • • •, Ri are independent, identically distributed random variables with common p.d.f. as in (3.19). Substituting (3.19) in (3.23) yields drt qi = i J° 2rt[j 2TJ dri = i Jj 2rt [ l - a 2 r t 2 ] , _ 1 drt Chapter 3. Capture Effect in Packet Radio Systems 29 = i 3=0 a' 2j + 2 i + i (3.24) * f{\ (—1V'+ 1 i Using the identity ]T] ^  .J —. ^ ^ = . ^  ^ ([52], equation 0.155.1), ft can be written as <H = - r , i > 1. a ' (3.25) Thus when there are two or more contending packets, the probability of capture with model 1 is independent of the number of contending packets! Bell—shaped spatial traffic density Here, the common p.d.f. of {Ru R2, • • •, Ri} is given by (3.20). Using (3.20) in (3.23) we obtain qi = * f°° , t f p w 4 T _ 1 2 r t e " r « y Irje'^i dr, drt = i J 2rte~*T* |er/ - {f Jo c | ^-o?r\ e *x f (V* 2 erfc I ~2~a x (3.26) where erfc(y) = -^L / ~ e dx is the complementary error function [44]. Equation (3.26) Chapter 3. Capture Effect in Packet Radio Systems 30 i ?» Bound in (3.27) 2 0.59033 1.305 x 10~8 4 0.52492 7.473 x 10~21 6 0.51200 3.210 x 10" 3 3 8 0.50712 1.226 x 10~45 10 0.50474 4.389 x 10~58 Table 3.3: The values of ft and the bound on e for different values of i with a 2 = 2 and 6 = 2 (model 1 and bell-shaped spatial traffic density). can be readily evaluated using a numerical integration routine. It is shown in Ap-pendix A . l that the truncation error t\ which results from setting the upper limit of the integral in (3.26) to 6 is upperbounded by erfc a26 er/c V^-b (3.27) To illustrate how effective the bound in (3.27) is, we consider a typical example with a 2 = 2. Table 3.3 shows the values of qi and the bound on 6i for different values of i with 6 = 2. It can be seen that the truncation error is negligible even for a small value of 6. In Appendix B . l , it is shown that lim ft = c Hence, the asymptotic value of ft is the same as with the uniform spatial traffic density model. This asymptotic value increases with (3 and decreases with c. The lower bound derived in Appendix B . l also indicates that the ft for the bell-shaped spatial traffic density model is at least as big as that for the uniform spatial traffic density model. Chapter 3. Capture Effect in Packet Radio Systems 31 3.4.2 Capture model 2 From (3.17) and (3.18), we can write roo <li = iJl fziz) 9(z) dz. (3.28) The p.d.f. of Z is given by roo fz(z) = / fz,rint(z,fint) dlint (3.29) Jo where fz,rint(z,fint) = /r„r < n <(7t, 7mt) | J \ * a n d J ( | ) i s t h e Jacobian of the coordinate transformation from x to y [53]. Uniform spatial traffic density Using (2.8, with krgr{9) = 1) and (3.19), the common p.d.f. f r . u n i f o r m d ) of the received powers {ri,r2, • • • can be derived as follows: fr,uniform(lf) = /«(»") dr dT i 3 o, 7 > 1 otherwise. (3.30) The evaluation of ft is complicated by the fact that it is difficult to obtain a closed-form expression for the p.d.f. of r , n t (given by the (i —l)-fold convolution of f r , u n i } o r m { l ) i f f ^ u n i f o r m i l ) ) when t is large. Our approach is to use a Monte Carlo simulation (see Appendix F .5) to obtain values for ft which will then be compared to the case of the bell-shaped spatial traffic density function for which analytic results can be obtained. Chapter 3. Capture Effect in Packet Radio Systems 32 Bell—shaped spatial traffic density Equations (2.8, with krgr($) = 1) and (3.20) can be used to obtain the common p.d.f. / r , 6en ( 7 ) of the received powers { ] ? i , r2 , • • • The result is / r , 6e « ( 7 ) = 4 V 7 > 0 . (3.31) The p.d.f. of Tint = ^2 Tj is given by the (i — l)-fold convolution of fr^ud) and can be written as [31] i — 1 - 3 _ *(»-i) 2 /r.-.,(7int) = -ir-linl *~ ^  • (3.32) The Jacobian of the coordinate transformation from [7t,7int] to [z,7tnt] is given by -Z,7mt = Dei 8z By* at B*tint Stint . Bit d-Ji„.t = Bet 1 7mt 1 lint •yt Tin* (3.33) where D e i [ X ] denotes the determinant of the matrix [ X ] . From (3.33) and (3.17), equa-tion (3.29) can be written as Chapter 3. Capture Effect in Packet Radio Systems 33 r o o fz(z) = / fr,(Zfint) /r i n,(7mt) tint <*7mt- (3.34) J o Substituting (3.31) and (3.32) into (3.34), we obtain t - 1 3 i — 1 3 — i - 1 roo _ w JO J<*7 tnt Jo _ 3 Z 2 n z - V + ( i - l ) 2 ' We now consider the special case of a piecewise linear g(z) defined by (3.35) 0, z < c i | 4- a(z — c ) , c x < z < c 2 1, z > c 2 (3.36) where C i = c — ^ , c 2 = c + ^ and a > 2 ( c - i ) ' We w u ^ r e ^ e r t o t n * s c a s e a s m ° d e l 2(PL). Figure 3.3 shows g(z) for a given c and different values of a. The lowest value of a results from the assumption that P(S|z) = 0 for z < 1. Using (3.35) and (3.36) in (3.28) yields U = i(i — 1) j fC2 i Z~5 7T i 11 f°° Z~2" — ac + - dz + / — — dz 21 Jci 1 + (i - l ) 2 z az Ic, 1 + (t - 1)2Z L i. , 1 \ _ 1 fc2 a z 2 — ( a c — j)z 2 + (» - I) 2 ir(» - 1) I Jei (i - I ) " 2 + dz + f°° z~% L (i -1)-2 + z -dz (3.37) Chapter 3. Capture Effect in Packet Radio Systems 34 c •s OH Vi VI <D O o 3 Vi •s Xi I 1 c Signal-to-interference ratio Figure 3.3: Piecewise linear function, g(z), as a function of the signal-to-interference ratio, z, for fixed c and different values of a. 2i [ /•>/« ax 2 - (ac - \) , /•«> (ix f r V * a x 2 - ( c - | ) r (i - 1 ) - 2 + x> +1 7r(i-l){J^cT i l ) " 2 2 ^ (» - I ) " 2 + x 2 J 2 i J a ^ - v ^ T ) f _ _ L +ac_i) (arctan: 1 7T I I i V(i-i)2 ' 2 A (»--i)Vsr arctanj-.—* _ } + arctan——* _ > . (3.37a) (i-lJv^y ( t - l ) v ^ J The asymptotic value of ft is given by (3.38) The expression for ft for capture model 2.1 can be obtained by letting a —• oo in Chapter 3. Capture Effect in Packet Radio Systems 35 (3.37). In this case, C\ = c2 = c and the first integral is zero, thus i(i - 1) i oo Z 2 dz Qi,model 2.1 — 7T 1 + (i - l ) 2 z 2i = —arctan ( (3.39) with asymptotic value lim qi,model 2.1 2 (3.40) 3 . 4 . 3 N u m e r i c a l results We now compare the ft values for the capture and spatial distribution models discussed so far. In Figure 3.4, ft is plotted for capture model 1 with (3 = 4, for both the uniform and bell-shaped spatial densities and different values of the capture ratio. It can be seen that the bell-shaped spatial traffic density model yields a slightly higher probability of successful reception. The asymptotic value of ^ is quite rapidly approached. Figure 3.5 is a plot of ft for capture model 2.1. The curves for the uniform spatial traffic density model represent simulation results with 99 percent confidence intervals as shown. The bell-shaped spatial traffic density curve is obtained from (3.39). As in the case of capture model 1, the bell-shaped spatial traffic density model yields a slightly higher ft value than the uniform spatial traffic density model. From Figure 3.5, the asymptotic ft values for the two spatial traffic density models appear to be the same, i.e. Figure 3.6 shows the ft values for capture model 2(PL) with the bell-shaped spatial traffic density model. Curves for different values of a and c are given. For given values 2 Chapter 3. Capture Effect in Packet Radio Systems 36 c •8 4> 8 o o a t/5 o 0.8 0.6 0.4 0.2 Bell-shaped spatial density " v\ ]n\ ~~ Uniform spatial density — c = 2 " 11 ~ V \ | i — c = 4 c = 10 10 20 Number of contending transmitters 30 Figure 3.4: Probability of successful reception, c/<, as a function of the number of con-tending transmitters, t , for capture model 1, using (3 = 4. of c and t, qi decreases with a. This follows from the fact that the p.d.f. of the test signal-to-interfence ratio, fz(z), is a monotonically decreasing function of z. However, there is little difference in qi as the slope a increases from 1 to infinity. This indicates that qi is not very sensitive to the exact shape of the g(z) curve, especially for large c, since fz{z) is small for large z. This is illustrated in Figure 3.7. The corresponding qi curves for capture model 2(PL) with the uniform spatial traffic density model are shown in Figure 3.8. For small values of t, they are somewhat lower than those in Figure 3.6. The differences become negligible for large values of t. The qi curves for capture models 1, 2.1 and 2(PL) with both uniform and bell-shaped spatial traffic densities are compared in Figure 3.9 for c = 4. Chapter 3. Capture Effect in Packet Radio Systems 37 0 ' 1 1 ' 1 ' ' 1 1—1 I L_J 1—1 I I I I I 1 I I I 1 L_l I I I 0 10 20 30 Number of contending transmitters Figure 3.5: Probability of successful reception, qi, as a function of the number of con-tending transmitters, i , for capture model 2.1. 3.5 Probabili ty of Successful Reception for a N C F S K System In this section, we examine how capture model 2(PL) can be used to estimate the proba-bility of successful reception for a system with a given P(S|z) curve. We use as example a simplified model of a system employing non-coherent frequency shift keying (NCFSK) modulation. In addition, the bell-shaped spatial traffic density model will be used. We assume that the total interfering signal is Gaussian. This is reasonable when the number of interferers is large but will yield pessimistic results when the number is small [54]. Using this simplified model, the bit error rate (BER) for NCFSK modulation is given by Chapter 3. Capture Effect in Packet Radio Systems 38 c •s OH U 8 cn 1 (4-1 O a - 10° c •= 4 ^ B 6 f l - 8 - E H H 3 - B - & B a -B-Q-Q-B-B-B-B B " " O 8 8 8 8 g- 8 8 O O 8 8 11 B ^"^"^-O-G-O-B- B B B -B-O-D-O-B-B- & B -B •Q-O-O-G-f] " ~ -8 8 8 8 0 0 0 8 10 -L_J l _ l I L. 10 20 Number of contending transmitters 30 Figure 3.6: Probability of successful reception, ft, as a function of the number of con-tending transmitters, i , for capture model 2(PL) with bell-shaped spatial density model. (3.41) A more accurate B E R value can be obtained using the results in [54]. However, our main purpose here is to determine how closely capture model 2(PL) can estimate ft, given a P(S |z ) curve. We will therefore use the simplified model and assume that bit errors are independent to conveniently obtain P(S |z) , the probability that a packet of length L contains no bit errors, as Chapter 3. Capture Effect in Packet Radio Systems 39 10° 1 ' l _ J I L a—2---o-— -A-B-_ l I I I I l — l L 101 Capture ratio 102 Figure 3.7: Probability of successful reception, qio, as a function of capture ratio, c, for capture model 2(PL) with bell-shaped spatial traffic density model. p(s\z) = (i - Pby (3.42) Substituting (3.42) and (3.35) in (3.28), we can write TT h 1 + (» - l)2Z \ 2 ) 2i(» — 1) f°° 1 7T J\ 1 + (» - 1)2X2 2 t(»-i) r» l / i _ s i \ i J — ^ k i + ( i - i ) ^ v - r 2 ) d x + e > i ,»\ - 2 / (3.43) Chapter 3. Capture Effect in Packet Radio Systems 40 0 10 20 30 Number of contending transmitters Figure 3.8: Probability of successful reception, ft, as a function of the number of con-tending transmitters, i , for capture model 2(PL) with uniform spatial density model. where e2 is the truncation error which results from setting the upper limit of the integral to 6. It is shown in Appendix A.2 that the value of e2 is lower and upperbounded by Ii ( 1 1 2t 1 ,„ 1 A . — 1 e 2 j arctan— -rr < c 2 < —arctan-r-. -rr. (3-44) 7T \ 2 / ( i —1)0 rr {t — l)b Using (3.43) and (3.44), the values of g,- can be evaluated accurately by an appropriate choice of b. This is illustrated in Table 3.4 where 6 = 6 and L = 500. The ft curves for L = 100, 200 and 500 are plotted in Figure 3.10. It is shown in Appendix B.2 that ft Chapter 3. Capture Effect in Packet Radio Systems 41 e •s g CO CO s CA o I 0.8 0.6 0.4 0.2 Bell-shaped spatial density Uniform spatial density model 2.1 -i ' 1 ' i i_ _!__] I I 1_J ' 1 ' 1 ' I L I I I L 10 20 Number of contending transmitters 30 Figure 3.9: Probability of successful reception, as a function of the number of con-tending transmitters, i, for capture models 1, 2.1 and 2(PL) with c = 4 and both spatial traffic densities. can also be lower and upperbounded by i - 1 Si < * < t - l SL, (3.45) where SL=l£(L)(-2r M e \ ~7TerJc To apply model 2(PL), we have to first select appropriate values of c and a (see Figure 3.3). The value of c is taken to be the value of z at which the P(S|z) expression in (3.42) has value 0.5, namely Chapter 3. Capture Effect in Packet Radio Systems 42 0 ' ' ' 1 1 I I I ' 1 I L _ l I I I I I I I 1 l — J 0 10 20 30 Number of contending transmitters Figure 3.10: Probability of successful reception, qi, as a function of the number of con-tending transmitters, t, for a NCFSK system. (3.46) or CNCFSK = -2 In [2 (l - 0.5r)]. (3.47) The value of a is chosen so that the piecewise linear P(S|z) line is tangent to (3.42) at c = CNCFSK, namely &NCFSK = Chapter 3. Capture Effect in Packet Radio Systems 43 l lower bound on ft upper bound on ft 2 0.35989080 0.35989160 4 0.24592095 0.24592149 6 0.22178242 0.22178291 8 0.21134094 0.21134141 10 0.20551828 0.20551873 30 0.19140641 0.19140683 Table 3.4: The lower and upper bounds on ft (NCFSK) for different values of i. L / 1 \ i _ 1 = i^ - r " 1 ) e"f- (3-48) Substituting (3.47) into (3.48) yields " N C F S K = j (2* - l) . (3.49) The ft values using c and a as given by (3.47) and (3.49) in (3.37a) are plotted as dashed curves in Figure 3.10. It can be seen that the results agree closely with the curves obtained from (3.43). This indicates once again that the exact shape of g(z) is of minor importance. Even though we treated the specific example of an NCFSK system, the technique can be readily extended to any system for which the P(S|z) curve can be derived or measured. Chapter 3. Capture Effect in Packet Radio Systems 44 3.6 Throughput for a Slotted ALOHA System In this section, we use the approach described in [55, 30] to evaluate the throughput for a finite population slotted A L O H A system under the different capture and spatial distribution models of Section 3.4. Consider a slotted A L O H A system3 with a base station surrounded by N mobiles. A mobile can be in an (O)rigination, (T)ransmission or (R)etransmission mode. At the beginning of a time slot, a mobile terminal is in either O-mode or R-mode. A transition to the T-mode occurs with probabilities p„ and pr respectively. At the end of a time slot, a mobile which was in the T-mode reverts back to the O-mode (if its packet is successfully received) or to the R-mode (if its packet is not successfully received). Such a system can be described by a homogeneous Markov chain with N + 1 states corresponding to the number of R-mode mobiles at the end of a time slot. Given p0, pT and ft, the throughput 5, denned as the average number of successful transmissions per time slot, can be evaluated [30]. The results are plotted in Figures 3.11 and 3.12. In both figures, the following parameter values are used: N = 50, c = 4 and pr — 10po. Figure 3.11 shows the throughput for capture model 1 as a function of p„. It can be seen that the bell-shaped spatial traffic density tends to have a higher throughput than the uniform spatial traffic density near the peak of the S vs p0 curve, but the difference is relatively small. For comparison, the throughput for the classical slotted A L O H A system with no capture (i.e. ft = | ^ ^ J ^ ^ ) is also shown. The value of S for large p0 is lowerbounded by q5o = 0.5. Figure 3.12 compares the throughput curves for model 2.1 with the bell-shaped and uniform spatial densities. As in the case of model 1, the bell-shaped spatial traffic 3 T h i s i s a s p e c i a l c a s e o f t h e f i n i t e p o p u l a t i o n s l o t t e d A L O H A s y s t e m w i t h m u l t i p l e a n t e n n a s a n d r e c e i v e r s d e s c r i b e d i n C h a p t e r 5. Chapter 3. Capture Effect in Packet Radio Systems 45 0.8 Bell-shaped spatial density, model 1 A -Uniform spatial density, model 1 e-No capture -ffl—a 10v 10'' 10" Figure 3.11: Throughput S as a function of p0 for capture model 1 with c = 4, N = 50 and pr = 10po. density gives a slightly higher throughput. Also shown are the curves for model 2(PL) with a = 1 and a = | . As would be expected from Figure 3.12, there is very little difference between the curves for model 2.1 and model 2(PL) with a = 1. The value of S for large p„ is lowerbounded by q5o = 0.32. A comparison of Figures 3.11 and 3.12 shows that systems with capture are not only capable of much higher throughput; the throughput also degrades gracefully under overload conditions. Chapter 3. Capture Effect in Packet Radio Systems 46 0.8 3 QH J3 bo s 0.6 Bell-shaped spatial density, model 2(PL), a «= 1 * Bell-shaped spatial density, model 2(PL), a = £ — - A Bell-shaped spatial density, model 2.1 • Uniform spatial density, model 2.1 e IO" t i i l i t 1<r Po 10" Figure 3.12: Throughput 5 as a function of p„ for capture model 2.1 and 2(PL) with c = 4, TY = 50 and pr = 10po. 3.7 Effect of Puncturing the Spatial Traffic Density Function The spatial traffic density functions described in Section 2.2 assume that the mobiles can be arbitrarily close to the base station. Here we consider the effects of puncturing these functions to model practical situations in which there is always a minimum normalized distance separation, p, between the mobiles and the base station. The normalized uniform spatial traffic density function of (2.1) is then modified to Chapter 3. Capture Effect in Packet Radio Systems 47 Gu(r,p) = < <T^J> P < r < 1 0, otherwise. (3.50) The p.d.f. of the normalized distance R (see equation (3.19)) is changed to (3.51) P<r<l 0, otherwise. The normalized punctured bell-shaped spatial traffic density function is obtained by modifying (2.4) to Gb(r,p) = { •w erfc o, p < r < oo otherwise (3.52) with corresponding normalized distance p.d.f. Mr) = < o, p < r < oo otherwise. (3.53) 3.7.1 Capture model 1 For the punctured uniform spatial traffic density function, the probability qi, i > 1, is given by •faMrt)\f Mrj)dr} Jp IVart » - l drt Chapter 3. Capture Effect in Packet Radio Systems 48 = < •7> & [!Lt Y^dr3]%-1 drtt 0, • — ot otherwise. (3.54) which, after evaluation, can be written as o, p < 1 r — a otherwise. (3.55) As expected, for p = 0, (3.55) reduces to (3.25). For 0 < p < ~ and a > 1, we have l - a 2 p 2 <!-/>", (3.56) so that the value of <ft in (3.55) approaches zero as i tends to infinity. For the punctured bell-shaped spatial traffic density function, the probability qi is given by roo I" roo I*—1 qi = if fR,b(rt) / fR,b(rj) dr}- drt Jp Wart xe <x erfc I —z-a x \ 4 i dx. (3.57) Equation (3.57) can be evaluated using a numerical integration routine. A bound on the truncation error e3 which results from setting the upper limit of the integral in (3.57) Chapter 3. Capture Effect in Packet Radio Systems 49 to 6 is derived in Appendix A.3. Since erfc(y) is a decreasing function of y, we can upperbound ft in (3.57) by e"?*2 dx = i erfc (^aV) er i-l »-i (3.58) where 5 = V-p—r^-. For a given value of p, 0 < p < ^ and a > 1, there is an integer J > 0 such that £ < y£y. Thus, for i > I, we have 6 < t + 1 (t + 1) < iS'1 (» + l ) f < ttf" 1. (3.59) The inequality in (3.59) indicates that the upper bound (3.58) decreases with i for large enough values of i. Hence, the value of ft in (3.57) approaches zero as t tends to infinity. The expressions in (3.55) and (3.57) for p = 0, 0.05 and 0.1 are plotted in Figure 3.13. It can be seen that for both spatial distribution models, puncturing reduces the value of ft. The most noticeable effect is in the asymptotic value lim ft. As would be expected, for p = 0, this limit is y^, but for any p > 0 and a > 1, the limit is zero. In the latter case, the rate at which the limit is approached is governed by the value of p. Chapter 3. Capture Effect in Packet Radio Systems 50 1 p = 0.1 0.2 0 1 1 1 1 1 l 0 10 20 30 Number of contending transmitters Figure 3.13: Probability of successful reception, ft, as a function of the number of con-tending transmitters, i, for capture model 1 with a 2 = 2. 3.7.2 Capture model 2.1 The effect of puncturing for capture model 2.1 is illustrated in Figure 3.14. The curves for the uniform spatial traffic density are obtained using a Monte Carlo simulation (A listing of the simulation program is given in Appendix F.5). The 99 percent confidence intervals for the simulation values are shown. In the case of the bell-shaped density, we can write (3.60) Chapter 3. Capture Effect in Packet Radio Systems 51 Number of contending transmitters Figure 3.14: Probability of successful reception, ft, as a function of the number of con-tending transmitters, i , for capture model 2.1 with c = 4. where Tp is the received power from a mobile at distance p, i.e. r p = p~\ (3.6i) The function / r (7) is the common "punctured" p.d.f. of the received powers {Ti, T2, • • •, Ti} obtained by modifying (3.31) to _ 3 2 erfc {^-p2) Chapter 3. Capture Effect in Packet Radio Systems 52 and frinXf) is the "punctured" p.d.f. of Tint = £ Tj which is given by frint(7) = / T *(7). (3-63) The p.d.f. of Tint in the range 0 < 7 < Tp can be expressed as (see Appendix D . l ) 3 _»('-i) 2 ^ ) = T & ( 3 - 6 4 ) Substituting (3.61), (3.62) and (3.64) into (3.60) yields (3.65) where e4 is the truncation error which results from setting the upper limit of the integral to b. A n upper bound on the error £4 is derived in Appendix A.4. The effect of a non-zero value of p is similar to that observed for capture model 1. The throughput curves of the slotted A L O H A system described in Section 3.6 for p = 0, 0.05 and 0.1 are shown in Figure 3.15. For values of p„ in the normal operating Chapter 3. Capture Effect in Packet Radio Systems 53 1 Po Figure 3.15: Throughput, S, as a function of pQ for capture model 2.1 with punctured bell-shaped spatial traffic density, c = 4, N = 50 and pr = 10po. range, i.e. below the value at which the throughput is maximized, there is no notice-able difference due to puncturing. For higher values of p0, puncturing can reduce the throughput by a substantial amount. Chapter 3. Capture Effect in Packet Radio Systems 54 3.8 Distance Dependence of Capture Probabilities The probability of a mobile terminal capturing the base station receiver depends on the distance, r t , between them. In this section, we calculate this probability P(C\rt). Let the probability that a test packet originating at distance rt from the base station will capture the receiver in the presence of n interferers be denoted by P(C\rt, n). For capture model 1, we have P(C\rt,n) = P r{a l l n interferers are at least at distance art from the base station}. (3.66) For the punctured uniform spatial traffic density, P(C\rt,n) can be written as P(C\rt,n) = < 0, otherwise = < o, P<n<h otherwise. (3.67) For the punctured bell-shaped spatial traffic density, P(C\rt,n) = [£tf*»(r)dr\ erfc fyy/nc) e r / c ( ^ ) (3.68) For capture model 2.1, Chapter 3. Capture Effect in Packet Radio Systems 55 P(C\rt,n) = Pr | r i n t < j , where l t = r t~4. (3.69) For the punctured uniform spatial traffic density, P(C\rt,n) is obtained by Monte Carlo simulation. For the punctured bell-shaped spatial traffic density, we can write P(C\rt,n) For both capture models, we can write P(C|r t) = £ P ( n ) P(C\run) (3.71) n where P(n) is the probability of n interferers. In (3.71) it is assumed that the number of interferers is independent of the location of the test mobile. The P{C\rt) curves for capture models 1 and 2.1 with the punctured uniform spatial traffic density are plotted in Figure 3.16. The same finite population model described in Section 3.6 is used here. The probability of n interferers is given by P{n) = j > m t (™) (" I fjpfr - Pr)m-kPn0-k(l - Po)N-m-n+k, (3.72) where irm is the probability that there are m R-mode terminals in the system. Two sets 21 Jo erfc (jr2y/iFc) erfc ( (3.70) Chapter 3. Capture Effect in Packet Radio Systems 56 Figure 3.16: Dependence of probability of capture on distance, r t , of test mobile from the base station. Finite population model with N = 50, pr = 10po, c = 4 and uniform spatial traffic density assumed. of curves corresponding to p0 = 0.01 and p0 = 0.015 are shown. Each set consists of four curves, two for each capture model. The two curves are for p = 0 and 0.1. It can be seen that the probability of capture drops off quite rapidly as the test mobile initially moves away from the base station. As it approaches a normalized distance of unity, the curves level off at a value determined mostly by p0. Similar observations can be made from Figure 3.17 which shows P(C\rt) for capture models 1 and 2.1 with the punctured bell-shaped spatial traffic density. It should be emphasized that the non-zero value of the limiting capture probability is a result of the number of mobiles being held constant (at 50). If the number of mobiles per unit area is fixed and spread over an infinite plane, Chapter 3. Capture Effect in Packet Radio Systems 57 1 Bell-shaped spatial density, model 2.1 <\ Bell-shaped spatial density, model 1 Po=0.0J p0= 0.015 0 0 0.5 1 1.5 2 Distance Figure 3.17: Dependence of probability of capture on distance, r t, of test mobile from the base station. Finite population model with N = 50, pr = 10pOi c = 4 and bell-shaped spatial traffic density assumed. then the capture probability would decrease to zero as the test mobile moved away from the base station. Chapter 4 A M A R Slotted A L O H A System with Stationary Users In this chapter, we study the performance improvement which can be obtained in a slotted A L O H A channel with stationary users by the use of directional antennas and multiple receivers [56]. Here a system in which the signals from the different transmitters are received with more or less the same powers is considered. Applications include earth stations transmitting to a satellite or a terrestrial radio system such as described in [9] in which the powers of the transmitters are chosen so as to equalize their signal strengths at the receiver site. 4.1 Performance Analysis We consider a slotted A L O H A system in which the coverage area is divided into M regions. A t the receiving site, there are M directional antennas each aiming at one region. Transmissions by users in different regions do not interfere with each other1. However, packets originating from the same region during a given time slot completely destroy each other. It is assumed that the channel is noiseless and there is no signal fading. A t the beginning of a time slot, the signal strength at each of the M antennas is measured to determine which signals can be decoded successfully. Obviously, one should choose the region which has only one active user. We also assume that at the receiving site there is a maximum of Nr receivers which can be connected to the antennas. 1 I n p r a c t i c e , t h i s is v a l i d a s l o n g as M i s not v e r y l a r g e . 58 Chapter 4. A MAR Slotted ALOHA System with Stationary Users 59 Let S and G denote the throughput (average number of successfully received packets per time slot) and the average channel traffic (measured in number of packets per slot) respectively. Define the average channel traffic per region as g = G/M. Assuming that the channel traffic is Poisson, we have Pr {a given region has 1 active user} = g e 8 = Pt- (4.1) Further, assuming that the channel traffic in the different regions are independent, we have Pr {exactly m of the M regions has 1 active user} = / ^ j p™ (1 — p,)M m . (4.2) The throughput is then given by \M-m = £ minim, tf,) (M) p? (1 - p.)M~m. (4.3) Its first derivative with respect to pt is 8S dp. ? M (M\ - = X m i M M , i v r ) ^ m j p r 1 ( i - p . ) J l f " m " 1 ( ^ - M p . ) Chapter 4. A MAR Slotted ALOHA System with Stationary Users 60 Nr-l M = J2 ™Q(m) + £ NrQ(m) M M M = £ Q N + £ <?M + • • • + E (4-4) m=l m=2 m=NT where Q(m) = ( ^ ) p ™ ~ ^ l - p J M ~ m _ 1 ( ™ - M > » ) - T n e expression Q(m) has the following properties. 1. l£Q(m) < 0, then Q(i) < 0, i = 1,2, • • •, m - 1. Proo/ -It is obvious that (Y)?^1 ~ P . ) M ~ i _ 1 > 0, 0 < i < M. For Q(m) < 0, we must have m — Mp, < 0 and if i < m, then < 0. Q.E.D. 2. If Q(m) > 0, then > 0, j = m + l , m + 2, • • •, M. Proo/: Since Q(m) > 0, we know that m — Mpt > 0. If j > m, then Q(i ) > 0. Q.E.D. M 3. £ Q(m) > 0, 1 < k < M. m=fc Proo/; The proof will be by induction. Let k be an integer between 1 and M — 1. Assume M M that £ Q(fn) > 0. We want to show that £ Q{m) ^ 0- We can write Chapter 4. A MAR Slotted ALOHA System with Stationary Users 61 Af Af E Q{m) = E Q(m) ~ Q(k). (4.5) m=fc+l m=k Af If Q(k) < 0, then ]T Q(m) > 0. If <?(Jfe) > 0, then from property 2, we have m=fc+l Af Q(m) > 0 for m > k + 1. Hence X] Q(m) ^ °-Af We also note that ^ Q{m) > 0 as follows: m = l Af Af f M \ E < ? W = E [ )V?-\l-V.)M-m-\rn-MVt) m = l m = l \ m / = M l ,C - i 1 ) y r l ( i - ? - ) ' \ A f - m - l E L h C ( i - p . ) M " m 1 m = l \ m M E ( M r - ( i - a 1 - p. L feo = M ( l - p , ) M - 1 > 0. (4.6) This completes the proof. Property 3 indicates that J-j^ - is non-negative. This implies that 5" is a monotonically increasing function of pt and is maximized when g = 1, regardless of the value of Nr. 4.2 Numerical and Simulation Results Figure 4.1 shows how the throughput changes with the channel traffic for M = 1,2,4 and 8 and Nr = 1 and 2. The case of Nr = 1 and M = 1 corresponds to the standard Chapter 4. A MAR Slotted ALOHA System with Stationary Users 62 2 10"1 10° 101 Channel traffic Figure 4.1: Throughput, 5", as a function of channel traffic, G, for 7Yr = 1 and 2 and M = 1,2,4 and 8. The points with 99 percent confidence intervals are obtained by simulations in which the input traffic is Poisson. Chapter 4. A MAR Slotted ALOHA System with Stationary Users 63 Nr = 8 Nr = 7 Nr = 6 — N r = 5 jy^^^—- Nr = 4 Nr = 3 Nr = 2 Nr= 1 1 1 1 i 1 i i i 1 I ' ' ' ' i ' ' ' ' i ' ' ' > i ' ' ' ' " 0 5 10 15 20 25 30 Number of regions Figure 4.2: Maximum throughput, S as a function of the number of regions, M, for 7VP = 1 to 8. slotted ALOHA channel with a maximum throughput, Smax, of !• = 0.368. It can be seen that Smax increases with M, even though for large M the incremental change is small. Increasing M to 2 yields an Smax of 0.60, an increase of about 63 percent. A further increase to 4 gives an additional Smam improvement of only 40 percent. With Nr = 2 and M = 2, Smax — 0.736. The value of Smax can be increased to 1.31, an increase of 78 percent, by using M = 4 directional antennas. As expected, the maximum value of the throughput occurs at G = M. Figure 4.2 is a plot of the maximum throughput as a function of M for different values of Nr. It might be noted that fewer than 5 antennas per receiver are required to obtain a maximum throughput of at least 90 percent of the maximum achievable throughput Chapter 4. A MAR Slotted ALOHA System with Stationary Users 64 (0.9JV r). In the throughput analysis of Section 4.1, the channel traffic is assumed to be Poisson. The throughput curves, assuming that the input traffic is Poisson, were obtained using a Monte Carlo simulation. The retransmission scheme used is that a packet involved in a collision during a given time slot is retransmitted in the next jth slot where j is a number selected at random from {1,2, • • • , & } . The throughput curves with k = 50 are depicted in Figure 4.1. The 99 percent confidence intervals are also shown. It can be seen that the Poisson channel traffic assumption is quite valid in the normal range of operation. For the values of channel traffic near and above the level at which the throughput is maximum, the throughput curves cannot be obtained by simulation for the following reason: As the input traffic approaches its maximum value, the number of unsuccessful packets in the system increases. As a result the system becomes unstable, i.e., the number of unsuccessful packets in the system becomes unbounded. Chapter 5 A M A R Slotted A L O H A System with Mobile Users In this chapter, we consider a mobile radio environment in which the signals from the different transmitters are no longer equal. A slotted ALOHA system is assumed. In the model studied [57], it is assumed that N mobiles are randomly distributed around the base station. To improve performance on the inbound (mobile-to-base station) channel, the area around the base station is divided into M sectors. The station has M directional antennas each aiming at one sector. Also available at the station is a number, Nr, of receivers. Channel access time is divided into slots. At the beginning of a time slot, Nr of the antennas are selected and connected to the receivers. Once made, such connections last until the end of the time slot. When i, 0 < i < N, packets are transmitted to the base station in a time slot, it is possible for the station to correctly receive up to Nr packets. The probability that j, 1 < j < Nr, out of i contending packets are correctly received will be denoted by q^. The values {qj\i} depend on M, the capture model, the spatial distribution of the terminals and the types of antennas used. Here, a uniform spatial traffic density and capture model 2.1 as described in Sections 2.2.1 and 3.3.1 are assumed. Given gj|,-, a Markovian model can be formulated. 65 Chapter 5. A MAR Slotted ALOHA System with Mobile Users 66 5.1 Markovian Model It is assumed [30, 55, 58] that each terminal is in either O-mode or R-mode at the end of a time slot (see Figure 5.1). Let n, 0 < n < N, be the number of R-mode terminals in the system at the end of a time slot. The number n is a state of the homogeneous finite (N + 1 states) Markov chain depicted in Figure 5.2 where ir^m is the one-step transition probability that the number of R-mode terminals moves from n to m and i r n is the probability that there are n R-mode terminals in the system. Given p0, pr and qj\i, and assuming all terminals are independent, the transition probability •Kn,m can be obtained as follows. (i) m < n — Nr The number of R-mode terminals cannot decrease by more than JVr because each receiver can correctly decode at most one packet per time slot. As a result, we have 7Tn,m = 0, 771 < 71 - Nr. (5.1) (ii) m — n — NT The number of R-mode terminals decreases by exactly JVr when no O-mode terminal changes to T-mode and out of the i, Nr < i < n, R-mode terminals which change into T-mode, there are NT successful transmissions. The probability that exactly Nr out of t transmissions are successful is qNT\i- Therefore, we can write *n,m = E (")(! - Vr)n-yr { ( l " Po)"^*} > m = 71 — Nr. (5.2) i=NT W Chapter 5. A MAR Slotted ALOHA System with Mobile Users 67 time time slot O-mode: Terminal generates and transmits a new packet at the beginning of the next time slot with probabibty p0. T-mode: It is transmitting a packet. R-mode: It has unsuccessfully tried to send a packet and is waiting for retransmission in a future slot. The probability that a R-mode terminal retransmits at the beginning of the next time slot is pr. Figure 5.1: State transition of a terminal. (iii) m = n — Nr + 1 The number of R-mode terminals decreases by Nr — 1. This happens when one of the following events occurs. E v e n t NT — 1. No O-mode terminal changes to T-mode, z, JV*r — 1 < i < n, R-mode terminals change to T-mode and there are Nr — 1 successful transmissions. The probability that out of the i transmissions, exactly Nr — 1 will be successful is Chapter 5. A MAR Slotted ALOHA System with Mobile Users 68 *0,N TN,N-Nr Figure 5.2: State diagram. Event JV r. One O-mode terminal changes to T-mode, t, Nr — 1 < i < n, R-mode termi-nals change to T-mode and there are Nr successful transmissions. The probability that out of the t + 1 transmissions, exactly Nr will be successful is gjvr|;+i-We therefore have N x n j (1 - P o ) " - " " 1 J V f c W i } , m = n-Nr + l. (5.3) In general, the backward transition probability i r n , m , m < n , can be expressed as: Chapter 5. A MAR Slotted ALOHA System with Mobile Users 69 7 r n ' m = | m = n-j, j = 1 , 2 , . . . , N R 0, m < n — Nr. (5.4) (iv) m> n The number of R-mode terminals changes to m, where m > n, when one of the following events occurs. E v e n t 0. Exactly m — n O-mode terminals change to T-mode, i, 0 < i < n, R -mode terminals change to T-mode and there is no successful transmission. The probability that out of the i + m — n transmissions, none will be successful is NT 1 — E 9 j | » + m - n -E v e n t j, j = 1 , 2 , ...,Nr. Exactly m — n + j O-mode terminals change to T-mode, h 0 < i < n, R-mode terminals change to T-mode and there are j successful transmissions. The probability that out of the i + m — n + j transmissions, exactly j will be successful is t 7 j | j + m _ n + J - . We can therefore write E I ? ) ( i - i v r ^ E Nr 7T, n,m N-n »=o \m-n + j a _ \ N — m — j „m—n+j' i rN-n> N — m _m—n o N r 1 ~ E ?j'l«'+m-r J = 1 m > n. (5.5) Chapter 5. A MAR Slotted ALOHA System with Mobile Users 70 Equations (5.4) and (5.5) allow us to calculate ir1^m, 0 < n < N and 0 < m < N. The steady-state probabilities 7 r n , n = 0 , 1 , . . . , JV, can be obtained by solving the following system of linear equations (see Figure 5.2) 7T0,1 TTl.l • • • • KN,I - -f 1 * 0 , J V *"l,iV • 7TJV T A T (5.6) and iv E ^ n = l , 0 < 7 T n < l . (5.7) n = 0 The conditional probability that there are exactly j i , 1 < j < Nr, successful trans-missions per time slot given n R-mode terminals in the system can be expressed as p(j\n) = Pr[ j successful transmissions | n R-mode terminals] = | f ( \ n ) ( i - p . r ^ (5.8) From (5.8), the probability mass function of the number of successful transmissions per time slot can be obtained p(j) = Pr[ j successful transmissions] N = E*»p(j», I < ; < i v - P . (5.9) n = 0 The average number of R-mode terminals (i.e. backlogged users) in the system is Chapter 5. A MAR Slotted ALOHA System with Mobile Users 71 fl=2>7TN (5.10) n=0 and the throughput is 3=0 Alternatively, when the system is in equilibrium, the throughput (i.e. the output traffic) is equal to the new input traffic so that S = (N- R)Po. (5.12) 5.2 C o n d i t i o n a l Probabi l i t ies of Success The problem of determining the set {gj|»}, 1 < j < Nr, 1 < i < N, to be used in the model of Section 5.1 is now examined. As an example, consider the case of channel model 1 with M = 1 and 7YP = 1 (i.e. one sector and one receiver). Let the p.d.f. of the received power from any terminal be denoted by fr{j)- Let Tt be the power of a test packet. This packet will capture the receiver if the following condition is satisfied (capture model 2.1) Tt > cTint (5.13) where c is the capture ratio and Tint= E (5.14) 3=h&t Chapter 5. A MAR Slotted ALOHA System with Mobile Users 72 is the total interference power. Assuming all the packet signals are independent, the p.d.f. of the random variable Tint will be the (i — l)-fold convolution of fr("f), i-e. /r,,.(7) = M7)*" 1 . (5-15) The probability that the test packet t will be successfully received is Vr[t\i] = r Pr [r i n t < ?]/r(7)<*7 (5-16) JO where PrfTint < ]^ = J / r ( 7 ) 8 " _ 1 ^ 7 ' The probabiUty that there is one successful J o transmission given i contending packets is written as i Pr[i|i], i > 1 (5.17) 1, i = 1. The problem of getting a closed form expression for even for a one-sector (M = 1) slotted A L O H A system [30] becomes difficult for i > 3. It might be noted that a closed form expression (3.39) can be obtained for q\\i when the uniform spatial traffic density assumption is replaced by the bell-shaped spatial traffic density defined by (2.4). Even in this case, it is difficult to obtain a closed form expression for when M > 1. Therefore in the numerical results to be presented in Section 5.3, the set of probabilities {<7j|i} are estimated using the Monte Carlo simulation described in Appendix F.5. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 73 5.3 Numerical Results The above results are now used to determine the throughput as a function of various system parameters. The assumptions made in obtaining the numerical results are: 1. The N mobile terminals are uniformly distributed within a circle, of radius Rm, centered at the base station. 2. The terminals are equipped with omnidirectional antennas. 3. From the M antennas at the base station, the Nr antennas with the highest received powers are selected. 4. The selection time is negligible compared to the duration of a slot. In Section 5.5, the effect of a finite antenna selection time is considered. 5.3.1 Effects of increasing M and Nr Figure 5.3 is a plot of the throughput against the channel traffic G = Rpr + (N — R)p0 for various values of NT and M with N = 100, pr = 10po and c = 4 for channel model 1. The antenna pattern is the sine function (except for the case M = 1, in which an omnidirectional antenna is used) and the half-power beamwidth 6BW = ^ as described in Section 2.4. For a fixed value of iV P , increasing the number of sectors M results in higher throughput. The improvement which results from increasing Nr can also be seen from Figure 5.3. Greater improvements occur for higher number of sectors. Similar observations can be seen in Figures 5.4 and 5.5 for systems with the sinc-cos and ideal antenna patterns. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 74 Channel traffic Figure 5.3: Throughput, S, as a function of channel traffic, G, for N = 100, pr = 10po, c = 4 and antenna pattern: sine function. 5.3.2 Effects of different antenna radiation patterns A plot of the maximum throughput as a function of the number of sectors, M , for Nr = 1 and 2 using three different antenna patterns, namely sine, sinc-cos and rect functions, is shown in Figure 5.6. For Nr = 1, there is little difference in using the three types of antennas. In the case of Nr = 2, the system with ideal (rect function) antennas outperforms the ones with sine and sinc-cos function antennas. The main reason is that Chapter 5. A MAR Slotted ALOHA System with Mobile Useis 75 10" Channel traffic Figure 5.4: Throughput, 5", as a function of channel traffic, G , for N = 100, pT = 10po, c = 4 and antenna pattern: sinc-cos function. with ideal antennas a packet can never be captured by two receivers at the same time since there is no overlap in coverage area when ideal antennas are used. 5.3.3 Effects of changing the capture ratio The maximum throughput performance as a function of the capture ratio for various values of M with Nr = 1 and 2 is depicted in Figure 5.7. The antenna pattern is a sine Chapter 5. A MAR Slotted ALOHA System with Mobile Users 76 10" Channel traffic Figure 5.5: Throughput, 5, as a function of channel traffic, G, for N = 100, pr = 10po, c = 4 and antenna pattern: rect function. function. It can be seen that the throughput decreases with increasing c. The reason is as follows: The condition for capture is Tt > c l \ n t . Given Tt and Tint, increasing c will only make the capture condition more difficult to satisfy. This results in a lower throughput. Also, for a fixed value of M , the difference between the Nr = 1 and Nr = 2 curves decreases as the capture ratio increases. Note also that for the case of a non-ideal antenna pattern such as the sine function, and infinite capture ratio, the throughput will not be improved by increasing M and Nr. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 77 3 4 5 6 Number of sectors Figure 5.6: Maximum throughput, S, as a function of the number of sectors, M, for N = 100 and c = 4. 5.3.4 Effects of puncturing the spatial traffic density The above numerical results assume that the N mobile terminals are uniformly dis-tributed within a circle (of radius Rm) centered at the base station, i.e., the mobiles can get arbitrarily close to the base station. The throughput curves, assuming that there is a minimum distance separation, p (normalized to Rm), between the mobiles and the base station are shown in Figure 5.8. The main effect is that at high values of G, there is a Chapter 5. A MAR Slotted ALOHA System with Mobile Users 78 Capture ratio Figure 5.7: Maximum throughput, S as a function of capture ratio, c, for N = 100 and antenna pattern: sine function. decrease in the throughput. 5.3.5 Effects of background noise In the presence of background noise (channel model 2), the condition for capture in (5.13) is modified to Chapter 5. A MAR Slotted ALOHA System with Mobile Users 79 1.4 1.2 3 OH bt) 3 O 0.6 0.4 0.2 10" Nr = 2,M = 8 Nr = 2,M=4 Nr = 2, M = 2 - - B -Nr=1,M = 8 —0— Nr-1,M=4 — A — Nr= 1, M = 2 — B — N r = 1 , M « 1 — e — 10° Channel traffic 10' Figure 5.8: Throughput, S as a function of channel traffic, G, with p = 0.05, N = 100, pr = 10po, c = 4 and antenna pattern: sine function. r t > c (r„ + r i n t), ( 5 . 1 8 ) where T n is the noise power given by ( 2 . 9 ) . The throughput curves with n = 0 . 2 and 1.0 (TJ is the normalized noise power as denned in ( 2 . 9 ) ) are shown in Figures 5 .9 and 5.10 respectively. Comparing Figures 5 . 3 , 5 .9 and 5 . 1 0 , it can be seen that for a fixed value of G, the throughput S decreases with rj as would be expected. For 77 = 0 . 2 , the reduction Chapter 5. A MAR Slotted ALOHA System with Mobile Users 80 10 u Channel traffic 10' Figure 5.9: Throughput, S, as a function of channel traffic, G, with 77 = 0.2, N = 100, p r = 10po, c = 4 and antenna pattern: sine function. in throughput is quite modest whereas for n = 1.0 it is much greater. For larger values of G, the throughput with noise approaches the no-noise throughput because the channel becomes contention rather than noise limited. On the other hand, for small values of G, the background noise can lead to a drastic reduction in throughput. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 81 0 I i i 1 — i — i — i — i — i I i I I I i i 10"1 10° 101 Channel traffic Figure 5.10: Throughput, S, as a function of channel traffic, G, with rj = 1.0, N = 100, pr = 10po, c = 4 and antenna pattern: sine function. 5.3.6 Effects of Rayleigh fading The throughput curves with Rayleigh fading (channel model 3) are shown in Figure 5.11. In obtaining these results, it is assumed that the fading processes experienced by a mobile in a given time slot at the M base station antennas are independent Rayleigh random variables, each with the same means as in the flat-terrestrial propagation model (channel model 1). The assumption of independence would be reasonable as long as Chapter 5. A MAR Slotted ALOHA System with Mobile Users 82 the separation between antennas is large compared to the R F carrier wavelength. A comparison of Figures 5.3 and 5.11 shows that Rayleigh fading causes a small increase in the throughput for moderate values of channel traffic. For low channel traffic values, there is little difference between the fading and no-fading curves. Also at high values of G , the difference decreases. The reason why there is a throughput improvement due to Rayleigh fading is as follows: Suppose that all mobiles are distributed on a ring centered at the base station, i.e. all mobiles are at the same distance from the base station. In the absence of fading, a packet cannot be successfully received if there is a collision. With Rayleigh fading, packets from different mobiles are received at different signal power levels; as a result, it may be possible for the receiver to decode the packet with the strongest power level. 5.3.7 Effects of different user mobility models The results presented so far assumed that the locations of the mobiles in each time slot are random. To see how sensitive the throughput is to the movement of the mobiles, we consider two different mobility models. (i) In mobility model 1 ( M M 1 ) , the location of a mobile for each packet transmission or retransmission is random. (ii) In mobility model 2 ( M M 2 ) , the mobile stays fixed from the start of transmission of a data packet until that packet is successfully received. Simulation results for M M 2 with channel model 1 are shown in Figure 5.12. The throughput with M M l (Figure 5.3) is generally higher than that with M M 2 . For low channel traffic values, the throughputs are almost the same. However, as the channel traffic is increased, the throughput with M M l degrades much more gracefully. This is to be expected since when a bad collision (i.e. one which results in the destruction of Chapter 5. A MAR Slotted ALOHA System with Mobile Users 83 1.4 1.2 1 *—' 3 OH 0-8 to 3 P ^ 0.6 0.4 0.2 0 10"1 10° 10 1 Channel traffic Figure 5.11: Throughput, S, as a function of channel traffic, G, with Rayleigh fading, N = 100, pr = 10po, c = 4 and antenna pattern: sine function. all packets involved) occurs, it is likely to persist longer with M M 2 than with MMl. A similar behaviour occurs with channel model 3, as can be seen from Figures 5.13 and 5.11. For M M 2 with channel model 2, the steady-state throughput is zero. The reason is that whenever a mobile is at a distance where its received signal power at the base station is less than cv, this mobile will never have its packet received successfully. As a result, the channel traffic increases and the throughput eventually drops to zero. Nr = 2, M - 8 - O -Nr = 2, M = 4 - - A -Chapter 5. A MAR Slotted ALOHA System with Mobile Users 84 3 D< _c bo 3 O 1.4 1.2 0.8 0.6 0.4 0.2 Nr = 2, M = 8 — -O— Nr = 2, M = 4 Nr = 2, M=>2 - - B -Nr= 1, M = 8 —0— Nr» 1, M =4 —A— Nr=1,M = 2 — B — Nr = 1, M » 1 —e— 10" Channel traffic 10' Figure 5.12: Throughput, S as a function of channel traffic, G, for mobility model 2, N = 100, pr = 10po, c = 4, sine antenna pattern and channel model 1. 5.4 Dynamic Behaviour The steady-state performance of the system was examined in Section 5.1. It is known [55, 58] that standard ALOHA systems generally exhibit "bistable" behaviour and thus steady-state performance measures do not always adequately characterize such systems. Here, the notion of expected drift [58] will be used to study the dynamic behaviour of the MAR ALOHA system. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 85 Channel traffic Figure 5.13: Throughput, S as a function of channel traffic, t7, for mobility model 2, N = 100, pr = 10po, c = 4, sine antenna pattern and channel model 3. The expected drift from state n is defined as N dn = E ( M _ N ) *n,m- (5.19) m=0 With the same set of assumptions as in Section 5.3, the expected drift dn and steady-state occupancy probability irn with Nr = 1 and 2 can be plotted as in Figures 5.14 Chapter 5. A MAR Slotted ALOHA System with Mobile Users 86 and 5.15 respectively. For both figures, a Sine function antenna pattern is assumed. A point at which the expected drift is zero is called an equilibrium point for the system. Furthermore if at such a point the slope of the expected drift curve is negative, we have a stable equilibrium point. This is because small deviations from this point result in statistical drifts which tend to move the system back to it. On the other hand, a positive slope corresponds to an unstable equilibrium point. The expected drift curves in Figure 5.14 and 5.15 show that for the values of poy pr and c used, there is only one stable equilibrium point. The improvement in the dynamic behaviour of the system as M and Nr are increased can be easily seen. The average number, i?, of backlogged users (i.e. those in the retransmission mode) is plotted in Figure 5.16 for different values of Nr and M. In all cases, it can be seen that R increases sharply as pa is increased beyond a certain threshold value. With these curves, it is convenient to use a threshold value corresponding to an average backlog of 10 users. For Nr = 1, the threshold value increases from p0 = 0.0058 (corresponding to an input traffic, Npa, of 0.58 erlang) to 0.0082 (Npa = 0.82 erlang) as M increases from 1 to 8. For Nr = 2, the increase is from p0 = 0.0065 (NpQ = 0.65 erlang) to 0.012 (Npa = 1.2 erlangs) as M increases from 2 to 8. Figure 5.17 shows some expected drift curves in which bistable behaviour, namely the existence of two stable equilibrium points, can be seen. The standard A L O H A system, i.e. one with no capture capabilities and M = 1, exhibits extreme bistable characteristics with stable equilibrium points near 1 and 100 R-mode users; there is also an unstable equilibrium point near 2. The stable equilibrium point near 100 is undesirable since it corresponds to a congested system in which most of the users are in the retransmission mode. When the capture effect is taken into account, the undesirable stable equilibrium point moves down to 35. With two sectors, i.e. M = 2, it moves down further to 11. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 87 0.8 0.6 0.4 0.2 Standard ALOHA — M -8 M = 4 --M = 2 -• M = 1 — 0 Att>(5<D'6&>drflrgnt)^!)00o'flfA'fldoO^TDiB 10 20 30 40 50 60 70 Number of R-mode terminals 100 Figure 5.14: Expected drift, dn, and steady-state occupancy probability, 7rn, as a function of the number of R-mode users for N = 100, NR = 1, p0 = 0.01, pr = 0.1, c = 4 and antenna pattern: sine function. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 88 W 0.5 -0.5 K V A N-. M = 8 M = 4 M=2 10 20 30 40 50 60 70 80 90 100 .-3 •§ a C M >^  o C M 3 O *-» I •a CO 0.8 0.6 0.4 0.2 M»8 M .4 M = 2 1—•- • i 10 20 30 40 50 60 70 80 90 100 Number of R-mode terminals Figure 5.15: Expected drift, dn, and steady-state occupancy probability, 7 r n , as a function of the number of R-mode users for N = 100, JVr = 2, p0 = 0.01, pr = 0.1, c = 4 and antenna pattern: sine function. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 89 100 Figure 5.16: Average number of R-mode users as a function of p0 for N = 100, pr = 10po, c = 4 and antenna pattern: sine function. For larger values of M , the system has only one stable equilibrium point with a small number of R-mode users. 5.5 Effects of a Finite Antenna Selection Time Ideally, the throughput approaches Nr as M tends to infinity. However, in the case of a finite antenna selection time, a larger M implies that a longer antenna selection time is Chapter 5. A MAR Slotted ALOHA System with Mobile Users 90 Figure 5.17: Expected drift, dn, and steady-state occupancy probability, 7rn, as a function of the number of R-mode users for N = 100, Nr = 1, p„ = 0.005, pr = 0.9, c = 4 and antenna pattern: sine function. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 91 needed. By including the antenna selection time in the analysis, the value of M which maximizes the system utilization 1 can be determined. Consider a system with channel bandwidth W Hz and packet size T seconds. A t the beginning of a time slot, the received power at every base station directional antenna is measured sequentially by switching from one antenna to another. The measurement of the received power at each antenna begins 4r seconds after the switch is closed, where r = pp-. This delay is included to reduce disturbance from switching transients. Assuming that transients decay exponentially with time t, i.e. Vtrant, K e~', then at t = 4r, Vtranti drops to less than 2 percent of the maximum value. It is also necessary that the switch remains closed for a period long enough to accurately measure the average received power at the antenna. We assume that each measurement takes 10T seconds [59]. The antenna selection time is then given by (5.20) where Tp is the processing time which is usually very small compared to r . The channel utilization can be written as U = S. (5.21) As an example, consider W — 25 kHz, T = 0.03125 second (i.e. packet length = 500 bits at a data rate of 16 kbps) and Tp is neligible. Using (5.20), (5.21) and the values of S obtained in Section 5.3, the channel utilization is plotted as a function of the number of sectors M in Figure 5.18. A comparison of Figures 5.18 and 5.6 shows that an increase in the number of sectors does not always improve the performance. Utilization is denned as the product of the throughput and (1 — v), where v is the fraction of a slot used for antenna selection purposes. Chapter 5. A MAR Slotted ALOHA System with Mobile Users 92 Figure 5.18: Maximum channel utilization, Umax, as a function of the number of sectors, M, for N = 100 and c = 4. Chapter 6 Antenna Selection in a M A R System In this chapter, we consider a slotted A L O H A system which has M directional antennas and 7Yr receivers at the base station. If Nr < M, the selection of the antennas to be connected to the receivers becomes an issue. A number of antenna selection schemes are studied in this chapter [60]. The throughput performance of the optimum selection rule is compared with those of some sub-optimum but simpler-to-implement selection rules, assuming an ideal antenna pattern. The effects of background noise, Rayleigh fading and a non-ideal antenna pattern are also considered. 6.1 Analysis of four Antenna Selection Schemes In evaluating system performance, we assume an idealized antenna pattern as denned by (2.11). Thus transmissions from mobiles in different sectors do not interfere with each other. The effects of using a non-ideal antenna pattern are considered in Section 6.2.3. We also assume a bell-shaped spatial traffic density with puncturing as described in Section 3.7. In this section the throughput, 5, defined as the average number of successfully received packets per time slot, for a number of different antenna selection schemes is obtained for channel model 1. The capture condition implied by (3.16) is assumed. The choice of antennas is based on the received signal power. The selection schemes considered 93 Chapter 6. Antenna Selection in a MAR System 94 are: Scheme 1: Optimum scheme which yields the highest throughput; in this scheme, the Nr sectors with the maximum a posteriori (MAP) probabilities of successful packet reception are chosen. Scheme 2: The Nr (out of M) antennas with the largest received signal powers are chosen. Scheme 3: Let the number of antennas with non-zero received signal powers be Na. If Na > Nr, then choose the iV r smallest non-zero power sectors. If Na < Nr, then choose all Na non-zero power sectors; note that in this case the performance will be the same regardless of whether the remaining (7YP — Na) receivers are used or not. Scheme 4: From the Na antennas with non-zero received signal powers, a number Nr of them are selected at random. Although Schemes 2, 3 and 4 will generally be inferior to Scheme 1, they are easier to implement. Unlike Schemes 2, 3 and 4 which require only knowledge of the received signal power level at each antenna, Scheme 1 also requires the MAP probabilities of successful packet reception which depends on the capture ratio and the average channel traffic level. Of course, many other antenna selection schemes are possible. For example, if Nr = 2, one could choose the antennas with the largest received power and the smallest non-zero received power. To evaluate the throughput, we will use P(S|7), the probability of successfully de-coding a packet (in some given sector) given the received signal power is 7 . Note that we can use a normalized power, i.e. set kr = 1 and g(6) = 1 in (2.8), for this calculation. Chapter 6. Antenna Selection in a MAR System 95 6.1.1 Derivation of P ( S | 7 ) First the conditional p.d.f. of the received power given i active users is derived. The p.d.f. of the normalized distance (over Rm) between a mobile and the base station is given by (3.53), namely erfc o, W) --T* e *T , p < r < oo otherwise. (6.1) From (2.8), the normalized received power is 7 = r 4 . Using a transformation of variables, we can obtain the p.d.f. of the received power for 1 active user as follows / ( 7 | t = l) = fR(r) dr 07 -a 2 e r / c ( ^ p 2 J 0, e *y, 0 < 7 < p~4 otherwise. (6.2) Assuming the locations of the mobiles are independent and the total received power for i active users is the sum of the received power for each user, the p.d.f. of the received power for i active users is given by the i-fold convolution of / ( 7 | i = 1). In the interval 0 < 7 < p~4, this i-fold convolution is given by Chapter 6. Antenna Selection in a MAR System 96 For 7 > ip~4, the i-fold convolution is zero. In the interval p~4 < 7 < ip~4, it is difficult to obtain a closed-form expression for the convolution. However, in the following analysis, we will use /(7 |i) in the range 0 < 7 < p~4 to obtain a fairly tight lower bound on the throughput. The next step is to consider P(S |7, i ) , the conditional probability of success given that there are i active users in the sector and the received power is 7. Let 7t and 7;nt = 7 — 74 be the received power of some test packet and that of the interfering packets respectively. Then P ( S | 7 , i ) t Pr{ a test packet is successful |7 , i } % Pr{7t > c 7i n t j 7, %} i P r { 7 t > c (7 - 7t) I 7, i) * P r(7t > -~T7 I 7,*'} c + 1 (6.4) Finally, we have 00 *(S|7) £ P ( i | 7 ) P ( S | i , 7 ) »=i ^ P(Q/(7l«) • r /(7l7t>0/(7t|t) h /(7) % /(7io /(7) /(7) (6.5) Chapter 6. Antenna Selection in a MAR System 97 where P( i ) = 9-e-" (6.6) ' - F <6'7> /(7I7..0 = / ( 7 - 7 . K - 1 ) , < > 1 (6.8) OO /(7) = E ^ ( i ) / ( 7 l i ) . (6-9) In (6.6), it is assumed that the channel traffic is Poisson. The validity of this assumption was verified using Monte Carlo simulation with Poisson input traffic (see Appendix F.2 for program listing and simulation results). The integral in (6.5) can be evaluated using a numerical integration routine. The infinite sums in (6.5) and (6.9) can be lowerbounded by truncating each one to u terms. It is shown in Appendix A.5 that the resulting error, e5, in P(S|7) is bounded by » < » + ' > ' 47 exp erfc u-1 - E »=0 erfc ( ^ p2 ) u - l j=o \_erfc\^fp>) 3 + t! (6.10) To illustrate how small this error is, Table 6.1 lists the values of P(S|7) and the bound on |e 5 | for different values of 7 with g = 8, p = 0.1 and u = 32. In Appendix C, it is shown that the probability P(S|7) approaches one as 7 tends to infinity for p = 0. This means that there is likely to be one active user which is very close to the base station when the received power is very large. In the case of p > 0 where the maximum received power per user is p~4, P (SJ7) = 0 for 7 > ^^p~4. Chapter 6. Antenna Selection in a MAR System 98 7 J°(S|7) bound on €5 IO1 0.0781 3.8480 x IO" 4 6 102 0.1612 6.1489 x 10~ 1 4 IO 3 0.5916 7.7383 x IO" 1 1 IO 4 0.8714 1.5688 x IO" 1 0 Table 6.1: P (S | 7 ) and bound on |e5| for different values of 7 . Note that when there is no capture effect, i.e. c = 00, a packet is successfully received if and only if it is the only one which was transmitted in its time slot and sector. Then *(S |7) *>(!) /(7|1) / (7) 00 » E ! e «•» t = 0 « [erfc ( f ?)]\ -1 0, , 0 < 7 < p - 4 otherwise. (6.11) Differentiating P(S | 7 ) in (6.11) with respect to 7 , we obtain ^ ( S | 7 ) = - [ p ( s i 7 ) r 2 f : ^ - ( i + 2 ) e 4^ ^ u i ! 4 7 2 [ e r / c ( ^ p 2 ) ] * (6.12) It can be easily seen that the expression in (6.12) is negative for 0 < 7 < p - 4 . Thus, in this case Scheme 3 is optimum. In other words, the sector which is most likely to have one and only one active user is the one with the lowest non-zero received power. Figure 6.1 shows the probability of success given the received signal power 7 as a function of 7 for c = 4 and 00, p = 0 and g = 0.5,1,2,4 and 8. As expected, the curves Chapter 6. Antenna Selection in a MAR System 99 10"1 10° 10 1 10 2 1 0 3 1 0 4 1 0 s Received power Figure 6.1: Probability of success given the received power, P(S |7), for p = 0. for c = oo are monotonically decreasing functions of 7. Thus, selecting the antenna with the smallest non-zero received signal power yields the highest probability of success. For c = 4, the curves are not monotonically increasing or decreasing. However, they have one minimum and indicate that during any given time slot, the sector with the highest probability of success is either the one with the largest power or the one with the smallest non-zero power. The P(SJ7) curves for p = 0.1 are plotted in Figure 6.2. A comparison of Figures 6.1 Chapter 6. Antenna Selection in a MAR System 10"1 10° 101 102 103 104 105 Received power Figure 6.2: Probability of success given the received power, P(S |7), for p = 0.1. and 6.2 shows that there is little difference between the two sets of P(S |7) curves in the range 0 < 7 < p~4. 6.1.2 Throughput evaluation The P(S |7) versus 7 curves (for given values of c and g) can be used to evaluate the throughput of the antenna selection schemes discussed earlier. 100 Chapter 6. Antenna Selection in a MAR System 101 Scheme 1 To calculate the throughput for Scheme 1, we first use a mapping h : {7} —• {A} to transform the generally non-monotone P(S|7) curve (see Figure 6.1) into a monotone increasing P(S|A) curve. This is done in such a way that different values of 7 with the same P(S|7) value, say p*, are mapped into a single value of A which, for convenience, is set to p*. The probability distribution of the random variable A (which takes on value A) can be determined numerically from knowledge of the distribution of T as specified by (6.9) and the mapping h. The throughput is then evaluated using the procedure described below for Scheme 2 with 7 replaced by A. Scheme 2 : Without loss of generality, let us assume that the M received signal powers have been ordered, i.e. Tt > T 2 > • • • > TM. Then the C.D.F. of the j t h largest signal power is given by [61] FriMT,.{l)= E (l)niY^-Fh)}M-\ (6-13) i=M-j+l \ 1 / where F(~y) is the integral of the p.d.f. in (6.9). The probability of success given the jth. largest signal is selected is P,(S) = jT P (S | 7 ) ^ „ , . ( 7 ) . (6-14) NT The throughput for Scheme 2 is then obtained as £ -Pj(S). Chapter 6. Antenna Selection in a MAR System 102 Scheme 3 The throughput for Scheme 3 can be evaluated in a way similar to Scheme 2. The only modification required is to use, in (6.14), the C .D.F . of the j t h smallest non-zero received power ft*_<7) = E p ) e - ' [ i - « - ' ] M - i g ( M ; i ) ^ ( 7 ) ' [ i - F r ( 7 ) r - i - ' + t (My*[l-e-.f-' (6.15) i=M-j+l  v 1 where Fr(7) = F^ll-t' 1S ^ n e C.D.F. of the received signal power given that it is non-zero. It is understood that if there are JVa antennas with non-zero powers, then Tjttman = 0, for j > Na. Schemes 2 and 3 can be viewed as special cases of the following mixed selection scheme: Step 1 : Select the Ni antennas with largest powers. Step 2 : Connect as many of the remaining (Nr — iVj) receivers as possible to any as yet unselected non-zero power antenna in inverse order of power level. The C .D.F . of the fcth largest signal power Tk (as selected in Step 1) is M / M \ KM = E ^ ' l l - ^ f , * = l ,2 , . . . , JVi (6.16) i=M-k+l \ 1 I and that of the fcth signal power Tpii+k ( a s selected in Step 2) is Chapter 6. Antenna Selection in a MAR System 103 £) M . - ' l l - . f " ' , k = l,2,-~,lfr-N,. (6.17) i=Af-^,-fc+l \ 1 / The probabihty of success for the jth selected antenna in this scheme is P,(S) = r P ( S | 7 ) ^ r . ( 7 ) , i = l,2,.-.,/NTr, (6.18) »/ 0 NT and the resulting throughput is £ -Pj(S)-Scheme 4 : Here again the throughput can be evaluated as for Scheme 2; but in (6.14), Fp^, m{j) is replaced by the C.D.F. Fpi Tandom(j) of the jth signal power, 1 < j < Nr, which is randomly chosen from among the (Na — J + 1) remaining non-zero signal powers. This C.D.F. is given by t=0 \ 1 / t=Af- i+l \ 1 I (6.19) For all the four schemes, the evaluation of the probability of success, P,(S), requires knowledge of / (7|i) in the range 0 < 7 < 00, whereas (6.3) only gives /(7I1) in the range 0 < 7 < p~A• However, we can lowerbound P,(S) by assuming P(S|7) = 0 for 7 > p - 4 , i.e. Chapter 6. Antenna Selection in a MAR System 104 Scheme 1 Scheme 2 Scheme 3 Scheme 4 g lower upper lower upper lower upper lower upper bound bound bound bound bound bound bound bound 0.5 0.9353 0.9353 0.8837 0.8838 0.9108 0.9108 0.8827 0.8828 1.0 0.9373 0.9373 0.8503 0.8507 0.8831 0.8831 0.8068 0.8069 2.0 0.8948 0.8949 0.8111 0.8127 0.7620 0.7620 0.6531 0.6533 4.0 0.8009 0.8019 0.7662 0.7726 0.4299 0.4299 0.4611 0.4619 8.0 0.7060 0.7105 0.6871 0.7127 0.0998 0.0998 0.3241 0.3273 Table 6.2: Lower and upper bounds on throughput for Schemes 1, 2, 3 and 4, with Nr = 1, M = 8 and p - 0.1. P i(S)> j" ^ ( 8 1 7 ) ^ ( 7 ) . (6-20) J o The integral in (6.20) can be evaluated numerically. The difference £ between -P,(S) and the lower bound is given by f = f* P(S| 7) dFrfr) < 1 - F r > - 4 ) . (6.21) To illustrate how good the lower bound is, Table 6.2 shows the values of the lower and upper bounds on the throughput obtained using (6.20) and (6.21) for all the four schemes with Nr = 1, M = 8 and p = 0.1. Chapter 6. Antenna Selection in a MAR System 105 6.1.3 Numerical results The results of Sections 6.1.1 and 6.1.2 will now be used to determine the throughput as a function of various system parameters. The assumptions made in obtaining the numerical results are: 1. The terminals are equipped with omnidirectional antennas. 2. The antenna selection time is negligible compared to the duration of a slot. 3. The received signal powers are more or less constant over the duration of a slot. The throughput, S, as a function of channel traffic per sector, g, curves for Scheme 1 with c = 4, Nr = 1 and 2, M = 1,2,4 and 8, are shown in Figure 6.3. Two sets of curves are given: one is for the bell-shaped spatial traffic density function described by (2.4), and the other is for a uniform traffic density over an unit circle. It might be noted that the throughput for the system with the bell-shaped spatial traffic density is slightly greater than that with the uniform spatial traffic density. The reason is that some users are further away from the base station in the bell-shaped spatial traffic density case than in the uniform spatial traffic density case, thereby generating less interference. However, the difference is small for g values below the optimum level. Similar behaviour can be observed from the curves shown in Figures 6.4, 6.5 and 6.6 for Schemes 2, 3 and 4. The throughputs of the four schemes for c = 4, Nr = 1 and 2 and M = 1,2,4 and 8 are plotted in Figure 6.7. As expected, Scheme 1 outperforms the other three selection schemes. Scheme 3 performs poorly once the optimum channel traffic level, g", is exceeded. However, for g < g*, there is little difference in the throughputs for all four schemes. Chapter 6. Antenna Selection in a MAR System 106 3 CX 3 O 2.2 2 1.8 Bell-shaped spatial density Uniform spatial density Channel traffic per sector Figure 6.3: Throughput, S, as a function of channel traffic per sector, g, for Scheme 1 with c = 4 and p = 0. In Figure 6.8, the probability of success, P,(S), if the sector with the jth. largest received power is selected, is shown. The throughput of a scheme in which the sectors with the iVr largest received powers are selected is given by the sum (6.22) Chapter 6. Antenna Selection in a MAR System 107 2.2 2 1.8 3 d , (JO 3 s Bell-shaped spatial density Uniform spatial density i i i 1 1 1 10 1 Channel traffic per sector Figure 6.4: Throughput, S, as a function of channel traffic per sector, g, for Scheme 2 with c = 4 and p — 0. For the values of M and c considered, it can be seen that one should choose the sectors with largest received powers in order to maximize the throughput. The increase in throughput obtainable with each additional receiver at a given value of g can be seen. The probability of success, Pj(S), if the sector with the jih smallest non-zero received power is selected, is shown in Figure 6.9. For small values of g, the curves in Figures 6.8 and 6.9 are almost identical for the following reason: at low g, it is likely that JV0 < 7Yr. Hence, the same 7Ya antennas with non-zero received power will be selected. The Chapter 6. Antenna Selection in a MAR System 108 2.2 2 1.8 1.6 1.4 1 1.2 | 1 0.8 0.6 0.4 0.2 0 10"1 10° 101 Channel traffic per sector Figure 6.5: Throughput, S, as a function of channel traffic per sector, g, for Scheme 3 with c = 4 and p = 0. throughput of a scheme in which the sectors with the Nr smallest non-zero received powers are selected is again given by (6.22). In calculating the throughput for a mixed scheme, e.g. in which the Ni sectors with largest powers and the i V P — Ni sectors with smallest non-zero powers are chosen, we cannot in general simply add the corresponding probabilities of success. This is because the first set of Ni and the second set of Nr — TVj sectors may have common elements. Chapter 6. Antenna Selection in a MAR System 109 2.2 2 1.8 1.6 1.4 D £ 1.2 3 I ' 0.8 0.6 0.4 0.2 0 10"1 10° 101 Channel traffic per sector Figure 6.6: Throughput, S, as a function of channel traffic per sector, g, for Scheme 4 with c = 4 and p = 0. The numerical results presented so far in this section assumed that the mobiles can get arbitrarily close to the base station (i.e. p = 0). This assumption may be unreasonable in practice. The throughput curves, assuming that there is a minimum distance separation between the mobiles and the base station are shown in Figure 6.10. The main effect is that at high values of g, there is a decrease in the throughput. Bell-shaped spatial density Uniform spatial density Chapter 6. Antenna Selection in a MAR System 110 2.2 3 OH JS W) 3 O Scheme 1 Scheme 2 Scheme 3 Scheme 4 101 Channel traffic per sector Figure 6.7: Throughput , S, as a function of channel traffic per sector, g, wi th c = 4 and p = 0. 6.2 Practical Considerations In this section, the effects of background noise, Rayleigh fading and a non-ideal antenna pattern are discussed. T w o different user mobil i ty models are also compared. Chapter 6. Antenna Selection in a MAR System 111 Channel traffic per sector Figure 6.8: Probability of success, Pj(S), if the sector with jih largest received power is selected, as a function of g for c = 4, p = 0 and M = 8. 6.2.1 Effects of background noise In the presence of the background noise with normalized power n (channel model 2), the capture condition is modified to 7t>cL+ 7 i ) . (6-23) Chapter 6. Antenna Selection in a MAR System 112 Channel traffic per sector Figure 6.9: Probability of success, P,(S), if the sector with jfth smallest non-zero received power is selected, as a function of g for c = 4, p = 0 and M — 8. The conditional probability of success given that there are i active users in the sector and the received signal and noise powers are 7 and 77 is given by P(S|7,77, i) = i Pr{ a test packet is successful I7, n,i } = i P r { 7 t > c ( 7 ^ + 77) | 7,77, i) = i P r { 7 t > ^ ± ! i | 7 , 7 7 , i } c + 1 Chapter 6. Antenna Selection in a MAR System 113 3 g Scheme 3 Scheme 4 J 1—_J 1_J I L. 101 Channel traffic per sector Figure 6.10: Throughput, S, as a function of channel traffic per sector, g, with c = 4 and p = 0.1. J V4-1 = i P f(l\lt,V,i)f{lt\r],i) /(7 | i ? , » ) <*7t (6.24) where 7 is the received power excluding noise. The probability P(S 17,77) is then written as Chapter 6. Antenna Selection in a MAR System 114 i=i t=i oo P{i) f(l\i) • P /(7l7«,»7,0 f(tt\v,i) , h /(7) % • > / ( T W , o 74 _ ~ P(Q /(71») . r /(7l7«,0 / M O j . , - § /(T) T C T R ) — * * - { 6 - 2 5 ) In (6.25), it is assumed that n is independent oft, 7 and 7 t . Following the approach in Section 6.1.2, the throughput of the four antenna selection schemes can be evaluated. The throughput curves for 77 = 0.2 and 0.5 are shown in Figures 6.11 and 6.12 respectively. Comparing Figures 6.7, 6.11 and 6.12, it can be seen that for a fixed value of g, the throughput decreases with 77 as would be expected. The reduction in throughput due to noise is greater for Schemes 3 and 4 than for Schemes 1 and 2. For large values of g, the throughput with noise approaches the no-noise throughput because the channel becomes contention rather than noise limited. On the other hand, for small values of <7, the background noise can lead to a drastic reduction in throughput, especially for Schemes 3 and 4. There are situations in which the exact value of 77 may not be known. Figure 6.13 shows the throughput curves for the system when the actual background noise is twice the assumed 77 value of 0.2. The curves for Scheme l a 1 were obtained by Monte Carlo simulation in which the M A P probabilities of successful packet reception for 77 = 0.2 were used. When the actual background noise changes to 0.4, this scheme no longer yields the highest throughput as can be seen from the figure. The throughputs for Schemes 2 and 3 were evaluated numerically. In Scheme 2, the use of an inaccurate value of 77 does not ^ h e selection rule for this scheme is similar to that of Scheme 1 except that the .P(S|7) curves for T) = 0.2 (instead of 0.4) are used. Chapter 6. Antenna Selection in a MAR System 115 Figure 6.11: Throughput, 5 , as a function of channel traffic per sector, 5, with c = 4, p = 0 and 7] = 0.2. Chapter 6. Antenna Selection in a MAR System 116 Figure 6.12: Throughput, 5, as a function of channel traffic per sector, g, with c = p = 0 and n — 0.5. 4, Chapter 6. Antenna Selection in a MAR System 117 change the Nr antennas which would be selected. Thus the curves for Scheme 2 can be obtained merely by using n = 0.4. The throughput for Scheme 3 is obtained by selecting the 7Yr smallest power antennas. In Scheme 4, since Nr out of M antennas are selected at random, the throughput curves are the same as those for a system with the same channel traffic per sector, g and M = Nr. Comparing Figures 6.11 and 6.13, it can be seen that, depending on which antenna selection scheme is being used, uncertainty about the value of w can have a significant effect on the throughput of a system operating in the normal channel traffic range. The throughput reduction is greater for Schemes 1/la, 3 and 4 than for Scheme 2. The throughput for Scheme 2 decreases by about 10 percent when the background noise increases from 0.2 to 0.4, an increase of 100 percent. The corresponding throughput reduction for Scheme 3 and 4 can be as high as 50 to 100 percent! The throughput of Scheme l a is moderately lower than that of Scheme 2, with greater degradation near the peak. A t high values of g, there is little effect on the throughputs of all the four schemes due to the increase in the background noise. 6.2.2 Effects of Ray le igh fading To study the effect of Rayleigh fading (channel model 3), we consider the case where p — 0 and r) = 0. Here, the same capture condition as in (3.16) is used. The p.d.f. of the received power for one active user can be written as Chapter 6. Antenna Selection in a MAR System 118 Figure 6.13: Throughput, S, as a function of channel traffic per sector, g, with c = 4, p = 0 i) — 0.2 and actual background noise = 0.4. Chapter 6. Antenna Selection in a MAR System 119 \pK ( 7 T \ - f (6.26) Assuming that the locations of the mobiles are independent, the p.d.f. of the received power for i active users is given by the i-fold convolution of /(7 | i =1). For i = 2, we have / ( 7 | * = 2) = /(7l»=l)®/(7l« = l) (6.27) Using ([62], equation 14.290), we get / ( 7 l - 2 ) = -1 T 2(7-2*) + 8(7+!)' 2 (7+f)2v^ +T' 7 > 0. (6.28) It is difficult to obtain a closed form expression for f(-y\i) for i > 2. For the results to be presented in this section, the values of /(7 | i) were computed numerically using the algorithm described in Appendix D.2. Given the values of f(l\i), the analysis in Section 6.1 can be used to evaluate the throughput of the four schemes in a Rayleigh fading environment. Figure 6.14 shows the Chapter 6. Antenna Selection in a MAR System 120 2.2 2 1.8 1.6 1.4 D £ 1-2 w> 3 0.8 0.6 0.4 0.2 0 10"1 10° 101 Channel traffic per sector Figure 6.14: Throughput, 5, as a function of channel traffic per sector, g, with Rayleigh fading, c = 4, p — 0 and n = 0. throughput of the four schemes for c = 4 and various values of Nr and M. A comparison of Figures 6.7 and 6.14 shows that there is a small throughput improvement due to the Rayleigh signal fading for all four schemes. For example, the maximum throughput for Scheme 2 with M = 8 and Nr = 2 increases from 1.68 to 1.72. Scheme 1 Scheme 3 Scheme 2 Scheme 4 1 i i i i i i i I I i i i i Chapter 6. Antenna Selection in a MAR System 121 6.2.3 Effects of using a non-ideal antenna In practice, transmissions from mobiles in different sectors will interfere with each other due to non-ideal antenna patterns. In this section, we consider a non-ideal antenna pattern which can be modelled by a sine function as in (2.12), i.e. 9r(0) = sin ( 2 . 7 8 e\ 2.78 e 8B w (6.29) where gr and 0 are as defined in (2.11) and $BW is the half-power beamwidth. Here, the received signal powers { 7 1 , 7 2 , • • •, 7Af} oi the M antennas are no longer independent. Instead of using P(S | 7 ) as in Section 6.1.1, a set of (jjQ M-dimensional throughput versus { 7 1 , 7 2 , • • • , 7M} curves is needed for antenna selection Scheme 1. It is difficult to derive an analytic expression for these throughput curves. One alternative is to obtain approximate throughput curves using a Monte Carlo simulation. If the range of jm, m = 1,2, •• • , M, is divided into b intervals, a storage area of size (Jf>)bM is required. Table 6.3 illustrates how the storage size increases with Nr and M for b = 81, corresponding to the following intervals for ~fm: 0 to 10~ 2, 10"2 to 10~ 1 - 9, 10 - 1 - 9 to 10~ 1 - 8, • • •, 10 5 - 8 to 10 5 - 9 and 10 5 - 9 to 00. Due to the large memory requirements for M > 4, simulation results were obtained only for M = 2 and Nr — 1 with b = 81. The throughput for Scheme 1 with associated 99 percent confidence intervals are tabulated in Table 6.4. The throughput curves for Schemes 2, 3 and 4 obtained by Monte Carlo simulation (see Appendix F.3 for program listing) are depicted in Figure 6.15. It can be seen that Scheme 2 outperforms Scheme 3 and 4. Comparing Figures 6.7 and 6.15, for Nr = 1, there is little degradation in the throughput of Scheme 2 with the sine antenna pattern. Chapter 6. Antenna Selection in a MAR System 122 Nr M storage size 1 2 1.3 x 10 3 1 4 1.7 x 10 8 1 8 1.5 x 10 1 6 2 4 2.5 x 108 2 8 5.2 x 10 1 6 Table 6.3: Memory requirements for Scheme 1 with non-ideal antennas. Channel traffic per sector g Throughput S 0.5 0.5636 ±0.0060 1.0 0.6706 ±0.0042 2.0 0.6071 ±0.0050 4.0 0.4996 ±0.0041 8.0 0.4512 ±0.0068 Table 6.4: Throughput for Scheme 1 with sine pattern antenna, c = 4, M = 2 and K = 1. However, there is a substantial reduction in throughput for Scheme 2 with Nr = 2. The reason is that when a packet is received from a mobile which is very close to the base station, there is a high probability that the two receivers will be connected to antennas for adjacent sectors and they will both capture the same packet. For Schemes 3 and 4, there is a sharp reduction in throughput when the sine pattern antenna is used. The throughput curves for Schemes 2, 3 and 4 with p = 0.1, n = 0.2 and Rayleigh fading are shown in Figure 6.16. A comparison of Figures 6.16 and 6.15 indicates that for the parameter values used, there is a small throughput reduction for Scheme 2 when the effects of puncturing, background noise and Rayleigh fading are included. For Schemes 3 Chapter 6. Antenna Selection in a MAR System 123 Figure 6.15: Throughput, 5, as a function of channel traffic per sector, g, with Sine antenna pattern, c = 4, p = 0 and rj — 0. Chapter 6. Antenna Selection in a MAR System 124 and 4, the drop in throughput is sharper. 6.2.4 Effects of different user mobility models In calculating the numerical results presented so far, it is understood that the locations of different mobiles are independent. It is also assumed that the locations of a mobile at its successive transmission time slots are statistically independent (mobility model M M l as in Section 5.3.7). To determine how sensitive the throughput is to the movement of the mobiles, we also consider mobility model M M 2 . In M M 2 , the location of a mobile is fixed from the time it starts transmitting a packet until such time that the packet is successfully received. A Monte Carlo simulation (see Appendix F.2 for program listing) was used to obtain the throughputs for the two mobility models. Tables 6.5 and 6.6 compare the throughputs of the two mobility models for channel models 1 and 3. It can be seen that the channel traffic in M M 2 is slightly higher than those in M M l for the same input traffic (input traffic levels presented in the tables are about 80 percent of the maximum values). The combination of channel model 2 and mobility model 2 results in an unstable system with a steady-state throughput which is zero as discussed in Section 5.3.7. Chapter 6. Antenna Selection in a MAR System 125 2.2 r 2 7 1 8 L Scheme 2 Scheme 3 1.6 - Scheme 4 1.4 '-3 Channel traffic per sector Figure 6.16: Throughput, S, as a function of channel traffic per sector, g, with Sine antenna pattern, c = 4, p = 0.1, t] — 0.2 and Rayleigh fading. Chapter 6. Antenna Selection in a MAR System 126 M Input traffic Mobility model 1 Mobili ty model 2 G S G S 1 1 0.45 0.8129 ±0.0397 0.4460 ±0.0069 0.8780 ±0.0392 0.4477 ±0.0059 2 1 0.52 0.9523 ±0.0390 0.5154 ±0.0079 1.0375 ±0.0470 0.5168 ±0.0057 4 1 0.59 1.0721 ±0.0347 0.5905 ±0.0054 1.0987 ±0.0309 0.5876 ±0.0072 8 1 0.68 1.2718 ±0.0393 0.6737 ±0.0073 1.2863 ±0.0419 0.6713 ±0.0097 2 2 0.60 1.0546 ±0.0421 0.5982 ±0.0086 1.0920 ±0.0517 0.5992 ±0.0079 4 2 0.79 1.3190 ±0.0343 0.7928 ±0.0073 1.3000 ±0.0367 0.7874 ±0.0088 8 2 0.88 1.3420 ±0.0312 0.8764 ±0.0097 1.3372 ±0.0278 0.8759 ±0.0116 Table 6.5: Comparison of throughputs for M M l and M M 2 with c = 4, p = 0.1, sine antenna pattern, antenna selection Scheme 2 and channel model 1. M NT Input traffic Mobility model 1 Mobility model 2 G S G S 1 1 0.45 0.7542 ±0.0344 0.4493 ±0.0089 0.7578 ±0.0428 0.4487 ±0.0092 2 1 0.52 0.9005 ±0.0238 0.5189 ±0.0051 0.9364 ±0.0358 0.5211 ±0.0080 4 1 0.59 1.0126 ±0.0421 0.5853 ±0.0077 1.0471 ±0.0418 0.5866 ±0.0097 8 1 0.68 1.2743 ±0.0410 0.6788 ±0.0093 1.3044 ±0.0532 0.6789 ±0.0099 2 2 0.60 0.9526 ±0.0217 0.5997 ±0.0079 0.9502 ±0.0307 0.5964 ±0.0081 4 2 0.79 1.2691 ±0.0295 0.7872 ±0.0081 1.3719 ±0.0375 0.7954 ±0.0092 8 2 0.88 1.3356 ±0.0255 0.8775 ±0.0108 1.3692 ±0.0177 0.8778 ±0.0054 Table 6.6: Comparison of throughputs for M M l and M M 2 with c = 4, p = 0.1, sine antenna pattern, antenna selection Scheme 2 and channel model 3. Chapter 7 Conclusions The performance improvements due to the existence of a capture effect in a number of different multiple access systems were analyzed. A power group division scheme proposed by Metzner for improving the throughput of a slotted A L O H A system has been studied for the case of a finite capture environment. It was shown that in the two power group case, the higher power group packet needs only be able to tolerate interference from up to three lower power group packets in order to realize most of the achievable improvement of the infinite capture model. The evaluation of the performance for more than two power groups was also considered. For given minimum and maximum power levels, a method for selecting the intermediate group powers was given. A number of different capture and spatial distribution models were applied to the problem of a number of mobile users accessing a central base station over a common non-fading channel. Methods for evaluating the probability ft of capture when there are i contending transmitters were examined. The sensitivity of ft to both the capture model and the spatial distribution model was discussed. It was found that there is little difference between the qi values for a uniform and a bell-shaped spatial density model, with the latter yielding slightly higher values. The asymptotic values of qi for large i are the same for both spatial density models. The probability of capture is more sensitive to the capture models considered, namely capture models 1 and 2(PL). However, variants of capture model 2(PL) result in ft values which are not significantly different. The use of 127 Chapter 7. Conclusions 128 capture model 2(PL) in estimating ft for a simplified N C F S K system was described. In most practical systems, there is a minimum distance separation between the base station and the mobiles. It was found that such a constraint reduces ft and can have a significant negative effect on the throughput under heavy traffic conditions. The probability of a test mobile capturing the base station receiver as a function of their distance separation has also been evaluated. The idea of using multiple directional antennas and receivers at the base station was applied to a system in which signals from the different transmitters are received with more or less the same power. It was shown that the throughput of a slotted A L O H A system can be substantially improved by using directional antennas and multiple receivers. It was found that fewer than five antennas per receiver are required in order to obtain a maximum throughput of at least 90 percent of the maximum achievable throughput. A packet radio slotted A L O H A system with multiple antennas and receivers (MAR) was also studied using a finite population Markovian model. The throughput performance including the effects of three different antenna patterns was evaluated. The notions of expected drift and backlogged packets were used to study the dynamic behaviour of the M A R system. It was found that there is a substantial improvement in the dynamic behaviour when multiple antennas and receivers are used. The throughput performance of a number of antenna selection schemes was analyzed. For the case of an ideal antenna pattern, the optimum scheme was compared to three sub-optimum but easier-to-implement schemes. It was found that the scheme which chooses the antennas with the largest received signal powers is close to optimum. The effects of background noise, Rayleigh fading and a non-ideal antenna pattern were con-sidered. Noise can significantly reduce the throughput at low channel traffic levels. The Rayleigh fading has the effect of slightly increasing the throughput. A non-ideal antenna Chapter 7. Conclusions 129 pattern can severely degrade the performance of an M A R scheme. The throughput is also sensitive to the mobility model assumed for the mobiles, especially for heavy channel traffic. Among the topics which could be further investigated are: • The power group division scheme can be used in the M A R slotted A L O H A scheme. Here the mobile transmitter power is a random variable with a certain distribution function. The M A R slotted A L O H A system with channel model 3 can be consid-ered a special case in which the transmitter power level is chosen according to an exponential distribution. It has been shown that a small improvement in through-put can be achieved in this case. Further throughput improvement may be possible with other power distribution functions. • The use of multiple directional antennas and receivers can be considered for other random access protocols. As an example, the performance improvement for a slot-ted C S M A system could be investigated. Bibliography [I] Bell System Technical Journal, Issue devoted to the Advanced Mobile Radio Phone Service, vol. 58, Jan. 1979. [2] J . Morris, "Creative Resources Management Using Digital Communications," Pro-ceedings of the 33th IEEE Vehicular Technology Conference, Toronto, Ontario, Canada, May 1983. [3] D . C. Cox, "Universal Digital Portable Radio Communications," Proceedings of the IEEE, vol. 75, Apr. 1987. [4] R. E . Kahn, "The Organization of Computer Resources into a Packet Radio Net-work," IEEE Transactions on Communications, vol. COM-25, pp. 169-178, Jan. 1977. [5] R. E . Kahn, S. A . Gronemeyer, J . Burchfiel and R. C. Kunzelman, "Advances in Packet Radio Technology," Proceedings of the IEEE, vol. 66, pp. 1468-1496, Nov. 1978. [6] F . A . Tobagi, R. Binder and B . Leiner, "Packet Radio and Satellite Networks," IEEE Communications Magazine, vol. 22, pp. 24-40, Nov. 1984. [7] B . M . Leiner, D. L . Nielson and F . A . Tobagi, "Issues in Packet Radio Network Design," Proceedings of the IEEE, vol. 75, pp. 6-20, Jan. 1987. [8] D . Bertsekas and R. Gallager, Data Networks. New Jersey: Prentice-Hall, 1987. [9] N . Abramson, "The A L O H A System-Another Alternative for Computer Communi-cations," Proceedings of the AFIPS Fall Joint Computer Conference, Montvale, NJ, U.S.A., vol. 37, pp. 281-285, 1970. [10] L . G . Roberts, " A L O H A Packet System With and Without Slots and Capture," Computer Communications Review, pp. 28-42, Apr. 1975. [II] L . Kleinrock and F . A . Tobagi, "Packet Switching in Radio Channels: Part I-Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics," IEEE Transactions on Communications, vol. COM-23, pp. 1400-1416, Dec. 1975. [12] R. M . Metcalfe and D. R. Boggs, "Ethernet: Distributed Packet Switching for Local Computer Networks," Communications of the ACM, vol. 19, pp. 395-404, July 1976. 130 Bibliography 131 [13] F . A . Tobagi and L . Kleinrock, "Packet Switching in Radio Channels: Part II-The Hidden Terminal Problem in Carrier Sense Multiple-Access and the Busy-Tone Solution," IEEE Transactions on Communications, vol. COM-23, pp. 1417-1433, Dec. 1975. [14] J . I. Capetanakis, "Tree Algorithms for Packet Broadcast Channels," IEEE Trans-actions on Information Theory, vol. IT-25, pp. 505-515, Sept. 1979. [15] M . Scholl and L . Kleinrock, "On a Mixed Mode Multiple Access Schemes for Packet-Switched Radio Channels," IEEE Transactions on Communications, vol. COM-27, pp. 906-911, June 1979. [16] F . A . Tobagi, "Multiaccess Protocols in Packet Communication Systems," IEEE Transactions on Communications, vol. COM-28, pp. 468-488, Apr. 1980. [17] A . Murase and K . Imamura, "Idle-Signal Casting Multiple Access with Collision Detection ( ICMA-CD) for Land Mobile Radio," IEEE Transactions on Vehicular Technology, vol. VT-36, pp. 45-50, May 1987. [18] D . Towsley and P. 0 . Vales, "Announced Arrival Random Access Protocols," IEEE Transactions on Communications, vol. COM-35, pp. 513-521, May 1987. [19] S. J . Chen and O. K . L i , "Reservation C S M A / C D : A Multiple Access Protocol for L A N ' s , " IEEE Journal on Selected Areas in Communications, vol. SAC-7, pp. 202-210, Feb. 1989. [20] F . A . Tobagi, "Modeling and Performance Analysis of Multihop Packet Radio Net-works," Proceedings of the IEEE, vol. 75, pp. 135-155, Jan. 1987. [21] J . J . Metzner, "On Improving Utilization in A L O H A Networks," IEEE Transactions on Communications, vol. COM-24, pp. 447-448, Apr. 1976. [22] N . Abramson, "The Throughput of Packet Broadcasting Channels," IEEE Transac-tions on Communications, vol. COM-25, pp. 117-128, Jan. 1977. [23] I. Cidon and M . Sidi, "The Effect of Capture on Collision-Resolution Algorithms," IEEE Transactions on Communications, vol. COM-33, pp. 317-324, Apr. 1985. [24] D . J . Goodman and A . M . Saleh, "The Near/Far Effect in Local A L O H A Radio Communications," IEEE Transactions on Vehicular Technology, vol. VT-36, pp. 19-27, Feb. 1987. [25] E . Zainal and R. Garcia, "The Effects of Rayleigh Fading on Capture Phenomenon in A L O H A Channels," IEEE Infocom 1987, pp. 888-893, Mar. 1987. Bibliography 132 [26] N . K . Garg and S. Mohan, "Group Testing Protocol with Capture for Random Access Communication," Proceedings of the IEEE International Conference on Communi-cations, pp. 1408-1412, June 1987. [27] K . Mutsuura, H . Okada, K . Ohtsuki and Y . Tezuka, " A New Control Scheme with Capture Effect for Random Access Packet Communications," Proceedings of the IEEE International Conference on Communications, Boston, Massachusetts, U.S.A., June 1989. [28] F . Kuperus and J . Arnbak, "Packet Radio in a Rayleigh Channel," IEE Electronics Letters, vol. 18, pp. 506-507, June 1982. [29] R. Nelson and L . Kleinrock, "The Spatial Capacity of a Slotted A L O H A Mult i -hop Packet Radio Network with Capture," IEEE Transactions on Communications, vol. COM-32, pp. 684-694, June 1984. [30] C. Namislo, "Analysis of Mobile Radio Slotted A L O H A Networks," IEEE Transac-tions on Vehicular Technology, vol. VT-33, pp. 199-204, Aug. 1984. [31] J . C . Arnbak and W. Blitterswijk, "Capacity of Slotted A L O H A in Rayleigh-Fading Channels," IEEE Journal on Selected Areas in Communications, vol. SAC-5, pp. 261-269, Feb. 1987. [32] R. Du, H . Okada, H . Nakanishi, H . Sanada and Y . Tezuka, "Performance Evaluation and Optimization of A L O H A Scheme with Capture Effect," Proceedings of the IEEE Global Conference on Communications, Tokyo, Japan, Nov. 1987. [33] I. Cidon, H . Kodesh and M . Sidi, "Erasure, Capture, and Random Power Level Selection in Multiple-Access Systems," IEEE Transactions on Communications, vol. COM-36, pp. 263-271, Mar. 1988. [34] R. Prasad and J . C. Arnbak, "Enhanced Packet Throughput in Radio Channels with Fading and Shadowing," Canadian Conference on Electrical and Computer Engineering, Vancouver, British Columbia, Canada, pp. 78-80, Nov. 1988. [35] T. T. Ha, "The Effect of Fading in Mobile A L O H A Radio Communications," Pro-ceedings of the 39th IEEE Vehicular Technology Conference, San Francisco, Cali-fornia, U.S.A., pp. 19-21, Apr. 1989. [36] J-P. M . G. Linnartz and R. Prasad, "Near-Far Effect on Slotted A L O H A Channels with Shadowing and Capture," Proceedings of the 39th IEEE Vehicular Technology Conference, San Francisco, California, U.S.A., pp. 809-813, Apr. 1989. Bibliography 133 [37] A . U . H . Sheikh, Y . D . Yao and X . Wu, "The Impact of Fast Fading on A L O H A System in the Mobile Environment," Proceedings of the 39th IEEE Vehicular Tech-nology Conference, San Francisco, California, U.S.A., pp. 804-808, Apr. 1989. [38] D . H . Davis and S. A . Gronemeyer, "Performance of Slotted A L O H A Random Ac-cess with Delay Capture and Randomized Time of Arrival," IEEE Transactions on Communications, vol. COM-28, pp. 703-710, May 1980. [39] I. M . I. Habbab, M . Kavehrad and C-E. W. Sundberg, " A L O H A with Capture Over Slow and Fast Fading Radio Channels with Coding and Diversity," IEEE Journal on Selected Areas in Communications, vol. SAC-7, pp. 79-88, Jan. 1989. [40] Y . Onozato, J . L iu and S. Noguchi, "Stability of a Slotted A L O H A System with Capture Effect," IEEE Transactions on Vehicular Technology, vol. VT-38, pp. 31-35, Feb. 1989. [41] J . E . Wieselthier, A . Ephremides and L . A . Michaels, " A n Exact Analysis and Performance Evaluation of Framed A L O H A with Capture," IEEE Transactions on Communications, vol. COM-37, pp. 125-137, Feb. 1989. [42] D . F . Lyons and P. Papantoni-Kazakos, " A Window Random Access Algorithm for Environments with Capture," IEEE Transactions on Communications, vol. C O M -37, pp. 766-770, July 1989. [43] A . Shwartz and M . Sidi, "Erasure, Capture, and Noise Errors in Controlled Multiple-Access Networks," IEEE Transactions on Communications, vol. COM-37, pp. 1228-1231, Nov. 1989. [44] M . Abramowitz and I. A . Stegun, Handbook of Mathematical Functions. New York: Dover Publications, 1972. [45] K . Bullington, "Radio Propagation for Vehicular Communications," IEEE Transac-tions on Vehicular Technology, vol. VT-26, pp. 295-308, Nov. 1977. [46] W. Lee, "Studies of Base-Station Antenna Height Effects on Mobile Radio," IEEE Transactions on Vehicular Technology, vol. VT-29, pp. 252-260, May 1980. [47] R. H . Clarke, " A Statistical Theory of Mobile-Radio Reception," The Bell System Technical Journal, vol. 47, pp. 957-1000, Jul-Aug 1968. [48] W . C. Jakes, Microwave Mobile Communications. New York: J . Wiley, 1974. [49] W . L . Stutzman and G. A . Thiele, Antenna Theory Design. New York: J . Wiley, 1981. Bibliography 134 50] C. Lau and C. Leung, "Performance of a Power Group Division Scheme for A L O H A Systems in a Finite Capture Environment," IEE Electronics Letters, vol. 24, pp. 915-916, July 1988. 51] C. Lau and C. Leung, "Capture Models for Mobile Packet Radio Networks." Ac-cepted for publication in I E E E Transactions on Communications, Dec. 1989. [52] I. S. Gradshteyn and I. M . Ryzhik, Table of Integrals, Series, and Products. New York: Academic Press, 1980. [53] L . W . Couch II, Digital and Analog Communication Systems, 2nd edition. New York: MacMillan, 1987. [54] J . S. Bird, "Error Performance of Binary N C F S K in the Presence of Multiple Tone Interference and System Noise," IEEE Transactions on Communications, vol. C O M -33, pp. 203-209, Mar. 1985. [55] L . Kleinrock and S. Lam, "Packet Switching in a Multiaccess Broadcast Channel: Performance Evaluation," IEEE Transactions on Communications, vol. COM-23, pp. 410-423, Apr. 1975. [56] C. Lau and C. Leung, "Throughput of Slotted A L O H A Channel with Multiple Antennas and Receivers," IEE Electronics Letters, vol. 24, pp. 1540-1542, Dec. 1988. [57] C. Lau and C. Leung, " A Slotted A L O H A Packet Radio System with Multiple Antennas and Receivers," Proceedings of the 38th IEEE Vehicular Technology Con-ference, Philadelphia, Pennsylvania, U.S.A., pp. 402-407, June 1988. [58] A . B . Carleial and M . E . Hellman, "Bistable Behavior of A L O H A - Type Systems," IEEE Transactions on Communications, vol. COM-23, pp. 401-409, Apr. 1975. [59] M . Schwartz, Information Transmission, Modulation, and Noise. Singapore: Mc-Graw Hi l l International, 1980. [60] C. Lau and C. Leung, "Antenna Selection in a Multi-Sector Packet Radio Network," Proceedings of the IEEE International Conference on Communications, Boston, Massachusetts, U.S.A., June 1989. [61] R. J . Larsen and M . L . Marx, An Introduction to Mathematical Statistics and its Applications. New Jersey: Prentice-Hall, 1981. 62] M . R. Spiegel, Mathematical Handbook of Formulas and Tables. New York: McGraw-Hi l l , 1968. Bibliography 135 [63] J . M . Wozencraft and I. M . Jacobs, Principles of Communication Engineering. New York: John Wiley & Sons, 1967. Appendix A Bounds on Truncation Errors A number of bounds on truncation errors are derived in this appendix. A . l Truncation Error for qit M l i modei 1 The truncation error t\ which results from setting the upper limit of the integral in (3.26) to b is given by Using the fact that erfc(y) is a decreasing function of y, we can upperbound the expres-sion in (A.l) by r f 2 erfc I ~2~a x *— i dx. (A . l ) erfc e *x* dx = i erfc [ ^ a 2 b j j erfc \~^~h (A.2) 136 Appendix A. Bounds on Truncation Errors 137 A.2 Truncation Error for q i t NCFSK The truncation error e2 which results from setting the upper limit of the integral in (3.43) to 6 is given by «2 ir A 1 2~2 (A.3) Lower and upper bounds on e2 can be obtained using 1 - \e~T < 1 - \e~T- < 1, x > 6, and are given by 2t(i - 1) roo ^ ~ l e >2) TT Jb 1 + (i - l)2X dx < e 2 < 2 » ( i - l ) roo 7T A l + (* - 1 ) 3 x 2 " K > i-1) Evaluating the integrals in (A.4), we obtain 2i / , 1 _ » 2 \ L 1 ^ 2i 1 — 1 — -e "5" J arctan——— < e2 < —arctan— —. 7T \ 2 / (t — 1)6 7T U —1)6 (i-l)b (A.5) A.3 Truncation Error for q i t p u n c t u r e d bell, m o d e l I The truncation error e3 which results from setting the upper limit of the integral in (3.57) to b is given by £3 erfc I ~2~a x dx. (A.6) Appendix A. Bounds on Truncation Errors 138 Since erfc {^-ct2x} < erfc ( ^ a 2 & ) for b < x, we have e 3 < i erfC{^P\ erfc I — P erfc I —T— a b rr f *b\V /' er/c I ——a 0 er /c I ——6 (A.7) A.4 Truncation Error for qit punched bell, model 2.1 The truncation error €4 which results from setting the upper limit of the integral in (3.65) to 6 is given by j e * erfc I —-—y/ircxJ dx e 4 (A.8) Since erfc (^ -^rca : ) < erfc ^^^/xcft^ for b < x, we have e4 < erfc (—^—V*cbj J e *x* dx = er/c —y/ncb^ j erfc (A.9) A . 5 Truncation Error for P(SJ7) In this section, it is shown that the magnitude of the error e5 in the numerical evaluation of (6.5) is bounded as in (6.10). Equation (6.5) can be written as Appendix A. Bounds on Truncation Errors 139 £ P ( 0 / H O P ( s|f > 7) P(sh) = (A.10) T.PU) /(7li) £ P ( 0 / ( 7 | i ) P ( S | » I 7 ) + C t=l £ J'(i) /(7li) + * (A.H) where C = J2 P({) /(7l*) P ( S K>7) a n d * = £ P0') /(7lj)- T h e error. e6 which t = u + l j—u+1 results from setting the upper limit of each of the infinite sums in (A.10) to u is given by where X ± J ] P ( i ) / ( 7 | t ) P ( S | t , 7 ) and Y ^  ]T P( j) f(l\j). Since £ > 0 and 6 > 0, we can lower and upperbound C5 by - x s . < <_ Y(Y + 6) ~ 3 " Y Also using the fact that X < Y and £ < 8, we have < e5 < i . (A.13) - p < «s < (A.M) Using (6.6) and (6.3), we can obtain an upper bound on S as follows: Appendix A. Bounds on Truncation Errors 140 Substituting (A.15) in (A.14) yields (6.10). The following shows that the bound in (6.10) is a monotonically increasing function of g and p. Letting v = — r - , the right hand side of (6.10) can be written as e *•» / (») i=o (A.16) Differentiating f(v) in (A.16) with respect to v, we obtain #00 dv i=o oo „ . ' u-1 E ^ r - E f r E J V e «T j=0 J' (A.17) The numerator in (A.17) can be expressed as Appendix A. Bounds on Truncation Errors 141 u - l v3 77 e ^^Z2 2 °° i v*-1 i=o J -e *T («-i)iSiJ' 0 0 tt* t! l=U ° ° 1>* j=0 •» • i=o J-e «i , . u - l ( u - l ) ! + £ 7 j=0 e 4T (A.18) It can be easily seen that (A.18) and hence (A.17) are non-negative. Therefore f(v) in (A.16) is a monotonically increasing function of v. Appendix B Bounds on Capture Probability Upper and lower bounds on ft, j^n, m o d e l 1 and ft, NCFSK are derived in this appendix. B . l Bounds on ft, 6en, m o d e l x The upper and lower bounds on ft, MI, m o d e l 1 as given by (3.26) are derived as follows: Upper bound First, using the fact that e * x 2 < 1 for x > 0, we can upperbound ft by 9i < » / Jo erfc I ——ax i-l dx. (B. l ) Next, we prove that erfc(y) < e v^ v, y > 0. (B.2) Proo/; Consider the range i/ < The error function is given by 142 Appendix B. Bounds on Capture Probability 143 f(y) = -LTe'^dz V 7 T JO 4 r^v i 2 Since u = ^-x < 1, the expression in (B.3) can be lowerbounded by f(y) > - f^Ve-^du TT Jo = l - e - ^ , (B.4) i.e. erfc(y) = 1 - erf(y) < e (B.5) For y > using the upper bound Q(x) < l e ~V [63] where Q(x) = | e r / c ( ^ ) , we obtain erfc(y) = 2 Q(yV2) < e-y2 < e~^v. (B.6) Q.E.D. Appendix B. Bounds on Capture Probability 144 Using (B.2), the expression in (B. l ) can further be upperbounded by if Jo c7 (r^ r) ' qi < i e-^-V* dx lo 1 / i (B.7) Lower bound Using the fact that a 2 > 1, we obtain qi > i e f Jo r ( 2 erfc ——ax 2 dx. (B.8) Letting y = erfc (^-a2xj, we have qi > ^Ty'-'dy cr Jo v 2 - (B.9) B .2 Bounds on NCFSK The upper and lower bounds on qi as given by (3.43) are derived as follows: Appendix B. Bounds on Capture Probability 145 2i(i - 1) r°° 1 / 7T Jl 1 + (t - 1) 2 Z 2 V 1 1 - £ \ L J  i iyx2\1-2e 2 1 The integral in (B.10) is bounded by i J i^ x1- h \-r\x — l ) 2 x 2 ( i — l ) 2 Ji x2 v ' where 1 x —e *"%fe = e k -J^erfcUL (B.12) Appendix C Asymptotic Value of P(S|7,T?) In this appendix, we show that the asymptotic value lim P(S|7,77) of equation (6.25) is unity for p = 0. From equation (6.25), 00 P(i\ n P{&\™) = JigpfhM /(7«I0 dlt- (c.i) Using (6.2), (6.6), (6.8) and (6.9), equation (C. l ) can be written as ^ ( S | 7 , i 7 ) = °° a* r i=2 l- J~ i — 1 3 _ » ( i - l ) 2 \ _ 3 j_ E ^ - ^ 7 - e - ^ T 3=1 J' Z 3 _ « ~ n i - 1 3 r / 7 t \ \dlt 0 0 „i— 1 iLr=—TTT7 J e ^ ft (J - 1)! oo i »T-'t -e-^ + E^r / c + 1 -t[i\Jo 2 a 1 - a (C.2) — -i! 146 Appendix C. Asymptotic Vaiue of P(S|7,TJ) As 7 —• oo, equation (C.2) reduces to — rr i r< Y — 1 + V * — - / a 2 e *<• da 3=1 J' Using (3.362) in [52], the integral in (C.3) can be expressed as f°° _ 3 _ j r £ , 2 / a *e <o da = -. Jo 1 Hence, l im P(S | 7 ,T/) = 1. Appendix D Numerical Evaluation of the t - fo ld Convolution A numerical method for computing the i-fold convolution of a function using is discussed in this appendix. D . l Convolution of a Truncated Function Let f(x) = 0 for x < 0 and denote the t-fold convolution of f(x) by /®*(x). For t = 2, we can write (D.l) Let /r(sc) be a truncated version of f(x) at x — xy, i.e. f(x), 0<x<xT, (D.2) otherwise. The 2-fold convolution of /r(s) is given by 148 Appendix D. Numerical Evaluation of the i-fold Convolution 149 0 < x < xj, xT < x < 2xT, (D.3) x > 2XT-From (D . l ) , (D.2) and (D.3), it can be seen that / f 2 ( x ) = /® 2 (x ) in the range 0 < x < xT. For the same range of x, it can be readily shown that /®*(x) = /®' (x) . D.2 Convolution Using Fast Fourier Transform In this section, we discuss a numerical method for computing the i-fold convolution of a function f(x), 0 < x < XT- The procedure is as follows: Step 1: Perform a Fast Fourier Transform (FFT) on f(x) to obtain F(s). Step 2: Compute [F(*)]\ Step 3: Perform an Inverse F F T on P"(.s) to obtain the i-fold convolution of / (x ) , 0 < x < x j . In Section 6.2.2, a 2 2 0 -point F F T and a step size of 0 .01 were used to compute the values of / ( 7 | i ) , 2 < i < 32, in the interval 0 < 7 < 5242 (this upper limit is determined by the step size and the number of points). We can then obtain the P(S | 7 ) curves in the interval 0 < 7 < 5242 as shown in Figure D . l . The P(S | 7 ) curves obtained by simulation are also depicted in Figure D . l . It can be seen that the probability of success for 7 > 5242 is bounded by / ® 2 ( x ) = / fT(a)fT(x-a)da Jo I Ma) Mx ~ a) da, Jo < / Ma) Mx - a) da> 0 , Appendix D. Numerical Evaluation of the i-fold Convolution 150 g Scheme 1 Scheme 2 Scheme 3 Scheme 4 Lower bound Upper bound Lower bound Upper bound Lower bound Upper bound Lower bound Upper bound 0.5 0.9361 0.9373 0.8995 0.8999 0.9085 0.9085 0.8962 0.8964 1.0 0.9334 0.9381 0.8714 0.8732 0.8838 0.8838 0.8356 0.8359 2.0 0.8921 0.9043 0.8379 0.8451 0.7863 0.7863 0.6997 0.7008 4.0 0.8236 0.8516 0.8074 0.8328 0.4986 0.4986 0.5152 0.5189 8.0 0.7567 0.8397 0.7562 0.8390 0.1413 0.1413 0.3750 0.3887 Table D . l : Lower and upper bounds on the throughput of the four antenna selection schemes with channel model 3. P(S| 7 = 5242) < P(S| 7> 5242) < 1. (D.4) As discussed in Section 6.1.2, the evaluation of the throughput requires the values of / ( 7 | i ) in the range 0 < 7 < oo. However, we can lower and upperbound the throughput using (D.4) in (6.14). Table D . l shows the lower and upper bounds of the throughput with M = 8, Nr = 1 and c = 4. Appendix D. Numerical Evaluation of the i-fold Convolution 151 Figure D . l : Probability of success given the received power, P(S |7) , for p channel model 3. = 0 and Appendix E Experiment on Capture Effect A n experiment set up to measure the bit error rate (BER) for a test signal transmitted in the presence of an interferer is discussed in this appendix. The data is first modu-lated using non-coherent frquency shift keying (NCFSK) . The N C F S K signals are then frequency modulated at a carrier frequency of 144.15 MHz. The experimental set-up is shown in Figure E . I . Transmitter H P 1645A Clock at 1200 bps. Pattern at 2 2 0 - 1. A M 7019 Swl on, sw2 on, sw3 off, sw4 on, sw5 off. H P 8656B Carrier frequency at 144.15 MHz. External F M modulation. Frequency deviation at 6 KHz . Interferer H P 1645A Clock at 1200 bps. Pattern at 2 2 0 - 1. A M 7019 Swl on, sw2 on, sw3 off, sw4 on, sw5 off. 152 Data in Oataout HP 1645A Data out HP 1645A - » T D TC AM 7910 i . Transmitter -^JTD TC AM 7910 Interferer AF in RF out HP8656B 1 ZSC-2-1 s 2 MARCONI AF in RF out 2022 RF in AF out ICOM 2AT RC RD AM 7910 Receiver H P 1645A Data Error Analyzer AM 7910 Bell 202/CCITT V.23 1200bps NCFSK modem HP 8656B RF Signal Generator MARCONI 2022 RF Signal Generator ZSC-2-1 Mini-Ciruit Power Combiner ICOM 2AT 145MHz FM Receiver C O M M U N C I A T I O N S L A B E L E C T R I C A L E N G I N E E R I N G . U B C C A P T U R E R A T I O M E A S U R E M E N T D o c u m e n t N u m b e r Date: Pocombor &. 1 989 ISrioot co Appendix E. Experiment on Capture Effect 154 fPfesio Q U I Z n 1L ^ UJ 1L U. U. >N 0[oP< - l - K C t O o 10 Q g HI 0 Hi ^0—> u. 3* «^=« I ^— i s A AA 2 3 < X J I a << < x° 0 S i 8881 2 |i >>82 o o 0? > II * N < n IL u. -CS—|H- -0—In 4'-Figure E.2: Schematic diagram of a F S K modem. Appendix E. Experiment on Capture Effect 155 Marconi 2022 : Carrier frequency at 144.15 M H z . : External F M modulation. : Frequency deviation at 6 KHz . Receiver I C O M 2 A T : Receive mode. : Carrier frequency at 144.15 MHz . A M 7019 : Swl on, sw2 off, sw3 off, sw4 on, sw5 off. Power combiner ZSC-2-1 : There is a 3 dB attenuation at the output from each of the two inputs. Figure E.3 shows the B E R curves for the test signal of power Tt in the range -122 dBm < r t < -109 dBm (note that there is a 3 dB attenuation at the power combiner, thus, the R F levels at the output of the signal generators are set at 3 dB higher than the desired signal levels). The interfering signal power T i n t is set to (i) zero, (ii) Tt — 6 dB and (iii) Tt — 3 dB. At a B E R of, say, 1 0 - 2 , the test signal with a power of -117 dBm can tolerate an interfering signal power of up to -123 dBm, a capture ratio of 6 dB. A test signal power greater than -117 dBm will result in a lower B E R . However, when T i n t = T t - 3 dB, the B E R is greater than I O - 2 . Appendix E. Experiment on Capture Effect 156 \ ' i 1 1 1 1 1 l i l i . i . i -122 -120 -118 -116 -114 -112 -110 -108 Test signal power, r, (dBm) Figure E .3: Bit error rate as a function of test signal power, r t , with and without interferring signal. Appendix F Simulation Programs Used in Thesis In this appendix, we describe and provide listings for the Monte Carlo simulation pro-grams used in this thesis. F . l A Two Power Group A L O H A Simulation Program A P A S C A L program which simulates the two power group A L O H A system described in Section 3.2.1 is listed in this section. The interarrival time between new packets from either user group is exponentially distributed. Any group i packet that is not success-fully received in a given time slot will be retransmitted j slots later, where j is a number Input traffic Channel traffic Output traffic C P U time group 1 group 2 group 1 group 2 group 1 group 2 0.1 0.10 0.111 ±0.029 0.130 ±0.044 0.099 ±0.026 0.101 ±0.031 33 0.2 0.10 0.263 ±0.050 0.153 ±0.044 0.200 ±0.024 0.101 ±0.027 60 0.3 0.10 0.514 ±0.047 0.211 ±0.061 0.299 ±0.013 0.100 ±0.028 119 0.1 0.15 0.111 ±0.034 0.207 ±0.047 0.099 ±0.030 0.151 ±0.025 44 0.2 0.15 0.258 ±0.035 0.255 ±0.037 0.199 ±0.025 0.150 ±0.019 76 0.3 0.15 0.513 ±0.039 0.374 ±0.069 0.299 ±0.013 0.151 ±0.030 156 Table F . l : C P U time for the two power group A L O H A simulation program. Number of time slots processed = 10 s. 157 Appendix F. Simulation Programs Used in Thesis 158 chosen at random from {1,2,3, • • •, fc; is a constant. The program input parameters are the group 1 and 2 input traffic levels (in erlangs), fci, k2 and the number of tolerable interferers, JVi^. Table F . l lists the C P U time (in seconds) for running this simulation on a S U N 3/50 computer with various input traffic levels, ki = k2 = 80 and JV l i 2 = 2. A Two Power Group A L O H A 1 program simulation_power_group (input,output); 2 {A Power Group Division Scheme) 3 {Two Power Groups ) 4 {Apr 1988 } 5 6 const 7 time_limit = 10000; 8 9 type 10 counter = array[1..2] of integer; 11 l i s t = array[1..2] of real ; 12 l ink = 'element; 13 element = record 14 next : l ink; 15 time : rea l ; 16 group : integer; 17 tx_no : integer; 18 tlme_arr : rea l ; 19 end; 20 21 var 22 queue, s, q : l ink; 23 i , j , g, m, n, k l , k2 : integer,-24 in_traf , ch_traf, success, contend : counter; 25 g l , g2, elk, i_traf , c_traf, o_traf, a_delay, i_mean, i_var : rea l ; 26 c_mean, c_var, c_ci , o_mean, o_var, o_ci, a_mean, a_var, a c i : rea l ; 27 i_eip, c_cip, o_cip, a_cip, eg, s i , s2 : real ; 28 i_sum, i_sum2, c_sum, c_sum2, o_sum, o_sum2, a_sum, a_sum2, delay, ga : l i s t ; 29 sc : array[0..10] of rea l ; 30 31 32 function one_of_k (gp : integer) : rea l ; 33 {returns the number one_of_k chosen uniformly at random from [ l ,k]) 34 var 35 k : integer; 36 x, y : rea l ; 37 begin 38 case gp of 39 1: k := k l ; 40 2: k := k2; Appendix F. Simulation Programs Used in Thesis 159 A Two Power Group ALOHA 41 end; {case} 42 x := random(O) * k; 43 y := 0; 44 repeat 45 y : = y + 1.0; 46 one_of_k := y; 47 u n t i l x < y; 48 end; {one_of_k} 49 50 51 function Interval (gp : Integer) : rea l ; 52 {returns in ter -arr iva l time which has exponential distribution) 53 var 54 x : real ; 55 begin 56 x := - ln( random(O) ); 57 case gp of 58 1: interval := x / g l ; 59 2: interval := x / g2; 60 end; {case} 61 end; {interval} 62 63 64 procedure insertque (e : l ink) ; 65 {insert transmission (new or old) into queue in the order of time} 66 var 67 p, r : l ink; 68 begin 69 p := queue; 70 r := n i l ; 71 while (p <> ni l ) and (pA.time <= eA.time) do begin 72 r := p; 73 p := p A .next; 74 end; {while) 75 i f r <> n i l then begin 76 e*.next := r A .next; 77 r A .next := e; 78 end 79 else begin 80 i f p <> n i l then e A .next := p else eA.next := n i l ; 81 queue := e; 82 end; 83 end; {insertque} 84 85 86 procedure new_arr (gp : integer; t : real) ; 87 (generate new packet and insert into queue) 88 var 89 event : l ink; 90 begin 91 new (event); 92 event*.time :» t + interval (gp); 93 eventA. group gp; 94 eventA.tx_no := 1; 95 event*".time arr : = eventA.time; 96 insertque (event); 97 end; {new_arr} 98 99 100 procedure re xsmn (e : l ink; t : real ) ; Appendix F. Simulation Programs Used in Thesis 160 A Two Power Group ALOHA 101 {retransmit unsuccessful packet at one of the next k slots) 102 var 103 event : l ink; 104 begin 105 new (event); 106 event'.time := t + one_of_k (eA.group); 107 event*.group := eA.group; 108 eventA.tx no : = e' . tx no + 1; 109 event''.time arr := e'.time arr; 110 insertque (event); 111 end; (re_xsmn) 112 113 114 procedure i n i t i a l i s e ; 115 begin 116 elk := 0; 117 new (queue); 118 queue'.next := n i l ; 119 queue'.time := time limit * time l i m i t ; 120 end; { ini t ia l ise) 121 122 123 begin {main program) 124 write ('input traf f ic group 1 : ' ) ; 125 readln (gl); 126 writeln (gl:6:4) ; 127 write ('input traf f ic group 2 : ' ) ; 128 readln (g2); 129 writeln (g2:6:4) ; 130 write ('number of tolerable interferers : ' ) ; 131 readln (n); 132 writeln (n:2); 133 write ('retransmission k l : ' ) ; 134 readln (kl); 135 writeln (kl:4); 136 write ('retransmission k2 : ' ) ; 137 readln (k2); 138 writeln (k2:4); 139 writeln; 140 for i := 1 to 2 do begin 141 i_sum[i] := 0, 142 c sum[i] : = 0, 143 o_sum[i] := 0, 144 a sum[i] := 0, 145 i_sum2[i] := 0; 146 c_sum2[i] := 0; 147 o~sum2[i] := 0; 148 a sum2[i] : = 0; 149 end; 150 151 for m := 1 to 10 do begin 152 153 i n i t i a l i s e ; 154 for i := 1 to 2 do begin 155 in_traf[1] := 0; 156 cbTtraf [1] •= 0; 157 success[i] := 0; 158 delay[i] := 0; 159 new_arr ( i . elk); 160 end; {for) Appendix F. Simulation Programs Used in Thesis 161 A Two Power Group ALOHA 161 162 repeat 163 for 1 := 1 to 2 do contend[1] : = 0; 164 while queue*.time > elk do elk := elk + 1.0; 165 q := queue; 166 while queue*.time <= elk do begin 167 contend[queue*.group] := contend[queue*.group] + 1; 168 i f queue*.tx no = 1 then begin 169 in traf[queue*.group] := in_traf[queue*.group] + 1; 170 new arr (queue*.group, queue*.time); 171 end; "{if} 172 ch_traf[queue*.group] := ch_traf[queue*.group] + 1; 173 queue := queue*.next; 174 end; {while} 175 g := 0; 176 i f (contend[1] = 1) and (contend[2] <= n) then g := 1; 177 i f (contend[1] = 0) and (contend[2] = 1) then g := 2; 178 j := contend[1] + contend[2]; 179 for i := 1 to j do begin 180 i f g = q*.group then begin 181 success[g] := success[g] + 1; 182 delay[g] := delay[g] + elk - q*.time_arr; 183 end 184 else begin 185 re xsmn (q, e lk); 186 end; 187 s := q; 188 q := s*.next; 189 dispose (s); 190 end; (for) 191 u n t i l elk >= time_llmit; 192 193 dispose (queue); 194 writeln ('duration =• ' , c l k : 5 : 0 , ' s lo t s ' ) ; 195 writeln('group input channel output average_delay'); 196 for i := 1 to 2 do begin 197 i t raf := in t ra f [ i ] / elk; 198 e_traf := ch_traf[i] / elk; 199 o_traf := success[i] / elk; 200 a delay := delay[i] / success[i]; 201 i_sum[l] := i_sum[i] + i_ traf ; 202 e_sum[i] :=> o_sum[i] + o_traf; 203 o_aum[l] := o_sum[i] + o_traf; 204 a sum[i] := a sum[i] + a delay; 205 i_sum2[i] := i_sum2[i] + i _ t ra f * i_ traf ; 206 c_sum2[i] := o_sum2[i] + e_traf * o traf ; 207 o_sum2[i] := o_sum2[i] + o_traf * o_traf; 208 a sum2[i] := a sum2[i] + a delay * a delay; 209 wri te ln( i :3 , ' ' , i _ t r a f : 1 4 , ' ' ,o_traf:14, ' ' ,o_traf:14, ' ' ,a_delay:14); 210 end; 211 writeln; 212 end; {for} 213 214 writeln(' s tat i s t ics : ' ) ; 215 writeln; 216 for i := 1 to 2 do begin 217 i_mean := 4_sum[i] / 10; 218 c_mean := e_sum[i] / 10; 219 o mean := o_sum[i] / 10; 220 a_mean := a_sum[i] / 10; Appendix F. Simulation Programs Used in Thesis 162 A Two Power Group ALOHA 221 i_var := (10*i_Bum2 [1] - i_sum[i]*i_sum[i]) / (10 * 9) ; 222 c var := (10*c sum2[i] - c_sum[i]*c sum[l]) / (10 * 9) ; 223 o var := (10*o_sum2[i] - o_aum[i]*o_sum[i]) / (10 * 9) ; 224 a var := (10*a sum2[i] - a sum[i]*a sum[i]) / (10 * 9); 225 i _ c i := 3.25 * sqrt( i_var / 10 ) ; 226 o_cl := 3.25 * sqrt( o_var / 10 ); 227 o_ei := 3.25 * sqrt( o_var / 10 ) ; 228 a_ci := 3.25 * sqrt( a_var / 10 ); 229 l_c lp := l _ o l / l_mean; 230 o_clp := c_el / o_mean; 231 o c ip := o_ol / o_mean; 232 a_eip := a_cl / a_mean; 233 ga[i] c_mean; 234 writeIn('group: ' , 1:1); 235 writeln(' input channel output delay'); 236 writeln('mean: ',i_mean:12,' ',c_mean:12, ' ',o_mean: 12, ' , a mean:12); 237 writeln('variance: ' , i var:12,' ' , c var:12,' ' ,o var:12, var:12); 238 writeln('99% C . I . : ' , l c i : 1 2 , ' ' , o c i : 1 2 , ' ' ,o _ci:12, ' ' , a c i "12) ; 239 writeln TCI/mean: ' , i _c ip :12 , ' ' ,c_cip:12, ' ' ,o_cip:12, cip:12); 240 writeln; 241 end; {for} 242 243 eg := exp (-(ga [1]+ga [2])) ; 244 sc[0] := 1; 245 for j := 1 to n do se[j] := sclj-1] * ga[2] / j ; 246 s i := 0; 247 for j := 0 to n do s i := s i + sc[ j ] ; 248 s i := s i * ga[l] * eg; 249 s2 := ga[2] * eg; 250 write ln( 'analyt ic results (for comparison):'); 251 w r l t e l n C S l : ' , s l : 12 , ' w i t h G l : ',ga[l]:12>; 252 writeln('S2: ' ,s2:12,' withG2: ',ga[2]:12); 253 writeln; 254 255 end. (main) Appendix F. Simulation Programs Used in Thesis 163 F.2 A n Infinite Population M A R Slotted A L O H A (Poisson Input Traffic) Simulation Program In Chapter 6, the infinite population M A R slotted A L O H A system model assumes that the channel traffic is Poisson. A simulation program in which the input traffic is Poisson was used to validate this assumption. The program is written in P A S C A L . The retrans-mission protocol is similar to that described in Section F . l , i.e. the retransmission delay (in terms of time slots) is a number uniformly distributed in {1,2,3, • • •, k}. The running time for this simulation depends mainly on the value of the input traffic. Table F.2 shows the C P U time (SUN 3/50) and the channel and output traffic for the following input pa-rameters: c = 4, 8 = 4, 7? = 0, p = 0, antenna selection Scheme 2, antenna pattern: rect, bell-shaped traffic density and no signal fading. The input traffic is at about 80 percent of the maximum throughput. M Input Channel Output C P U time traffic traffic traffic (seconds) 1 1 0.43 0.686 ±0.028 0.426 ±0.008 722 2 1 0.53 0.865 ±0.030 0.527 ±0.008 977 4 1 0.63 1.090 ±0.032 0.625 ±0.009 1397 8 1 0.69 1.231 ±0.032 0.684 ±0.008 1998 2 2 0.85 1.328 ±0.031 0.843 ±0.009 1499 4 2 1.13 1.665 ±0.029 1.125 ±0.013 2158 8 2 1.30 1.859 ±0.034 1.293 ±0.013 3029 Table F.2: C P U time for the infinite population M A R A L O H A simulation program (Poisson input traffic). Number of time slots processed = 10 s. Appendix F. Simulation Programs Used in Thesis 164 An Infinite Population M A R Slotted ALOHA (Poisson Input Traffic) I program 8 imu la t ion_ lp_MAR_AL0HA (input,output); 2 3 {infinite population m sectors nr receivers slotted ALOHA } 4 {poisson input t r a f f i c } 5 {date: Aug 23, 88 (revised Feb 17, 89 : fixed and rand position) ) 6 {revised Dec 21, 89 : include Rayleigh fading, noise, puncturing } 7 { and non-ideal antennas. ) 8 9 const 10 time_limlt = 10000; II bell_const « 0.893243841; 12 13 type 14 sector = array [1..8] of real ; 15 l ink = 'element; 16 element •= record 17 next : l ink; 18 time : rea l ; 19 time_arr : rea l ; 20 tx_no : integer; 21 rx_pow : sector; 22 end; 23 24 var 25 noi_pow, pun_rad : rea l ; 26 elk, in_traf, ch_traf, success, delay, i_sum, c_sum, o_sum, a_sum, g : rea l ; 27 i_sum2, c_sum2, o_sum2, a_sum2, i_mean, c_mean, o_mean, a_mean, i_var : rea l ; 28 c_var, o_var, a_var, i _ c i , c_ci , o_ci, a_ci, cap_ratio, beta, capture : rea l ; 29 max_pow, tot_pow : sector; 30 queue, s, q : l ink; 31 spatial , posit ion, selection, counter, msector, k_retx, no receiver : integer; 32 i , j , k, m, nptr, column, rayleigh, ant_type : integer; 33 prhol : array [1..12] of real ; 34 prho, rho : array [1..81] of rea l ; 35 s_flag : array [1..8] of boolean; 36 37 38 function drand (seed : integer) : real ; 39 {uniform random number generator) 40 external fortran; 41 42 43 function randn (seed : integer) : rea l ; 44 (normal random number generator) 45 external fortran; 46 47 48 function one_out_of (k : integer) : integer; 49 {returns the number one_out_of chosen uniformly at random from [ l ,k) ) 50 begin 51 one_out_of := trunc(drand(0)*k) + 1; 52 end; {one out_of) 53 ~ 54 55 function ranexp (xmean : real) : rea l ; 56 {exponential random number generator with mean = xmean) 57 var 58 x : real ; 59 begin 60 repeat x := drand(O) u n t i l x <> 0; Appendix F. Simulation Programs Used in Thesis 165 An Infinite Population MAR Slotted ALOHA (Poisson Input Traffic) 61 ranexp := -ln(x) / mean; > 62 end; {ranexp) 63 64 65 function recelved_power : rea l ; 66 {returns the received power of a user, near-far effect) 67 var 68 x, d : rea l ; 69 begin 70 case spat ia l of 71 1 : begin {uniform} 72 repeat x := drand(O) u n t i l x > pun_rad; 73 d : = sqrt (x) ; 74 end; 75 2 : begin (bell-shaped) 76 repeat x := abs( randn(O) ) u n t i l x > pun_rad; 77 d := bell_const * sqrt(x); 78 end; 79 end;{case} 80 received_power :<= exp (-beta * ln(d)); 81 end; {received_power} 82 83 84 function cmod (x : real) : rea l ; 85 begin 86 while x >= 1.0 do x :•= x - 2.0; 87 cmod := x; 88 end;{cmod} 89 90 91 function rect (x : real) : rea l ; 92 {ideal antenna} 93 begin 94 i f (x < -1.0) or (x > 1.0) then rect := 0.0 else rect := 1.0; 95 end; 96 97 98 function scos (x : real) : rea l ; 99 {antenna with sinc-cos function} 100 var 101 y, z : rea l ; 102 begin 103 i f x = 0.0 then scos := 1.0 else begin 104 y := 11.35 * (cos(x/2.0) -_1.0); 105 z := sln(y) / y; 106 scos := z * z; 107 end; 108 end; {scos} 109 110 111 function Bine (x : real) : real ; 112 {antenna with sine function} 113 var 114 y, z : rea l ; 115 begin 116 i f x = 0.0 then sine := 1.0 else begin 117 y := 1.39 * x; 118 z := sin(y) / y; 119 sine := z * z; 120 end; Appendix F. Simulation Programs Used in Thesis 166 A n Infinite Population M A R Slotted A L O H A (Poisson Input Traffic) 121 end;{sine} 122 123 124. function psrho (r : real) : rea l ; 125 {returns probabil i ty of success given the received power r) 126 var 127 i : integer; 128 begin 129 i f r <= 0 then psrho :•= 0 else begin 130 i f (r > rho[l]) and (r < rho[nptr]) then begin 131 i := 2; 132 while rho[i] < r do i := i + 1; .133 psrho := prho[i] - (rho[i]-r) * (prho [1] -prho [1-1]) / (rho[ i ] -rho[ i - l ] ) ; 134 end else 135 i f r <= rho[l] then psrho := prho[l] else psrho := prho[nptr]; 136 end; 137 end; 138 139 140 procedure sector_selection (x:sector); 141 {set s_flag[m] true i f sector m is selected) 142 {selection schemes: 1(optimum), 2(largest), 3(smallest), 4(random)} 143 var 144 y : rea l ; 145 i , j , k : integer; 146 ix : array [1..8] of integer; 147 begin 148 i f selection = 1 then for i := 1 to msector do x[i] : = psrho(x[i]); 149 for i := 1 to msector do ix [ i ] : = i ; 150 for j := msector downto 2 do {x[i] in descending order) 151 for 1 := 2 to j do 152 i f x [ i - l ] < x[i] then begin 153 y := x [ i - l ] ; 154 x [ i - l ] := x [ l ] ; 155 x[i] := y; 156 k := l x [ i - l ] ; 157 l x [ i - l ] :•= i x [ i ] ; 158 ix [ i ] := k; 159 end; 160 3 := 0; 161 i f selection = 4 then begin {scheme 4} 162 while (j < msector) and (x[j+l] > 0) do j := j+l; 163 i f j <= no_receiver then 164 for i := 1 to msector do 165 i f j < i then s f lag[ ix[ l ] ] :=> false else s f lag[ ix[ i ] ] := true 166 else begin 167 k := j + 1; 168 for i := k to msector do s_flag[ix[i]] := false; 169 for i :=• 1 to no_receiver do begin 170 k := one_out_of (3) ; 171 s flag[ix[k]] := true; 172 ix[k] := i x [ j j ; 173 3 := 3 - i ; 174 end; 175 for i := 1 to j do s f lag[ ix[ i ] ] := false; 176 end;{if} 177 end else begin {schemes 1, 2 and 3} 178 for i := 1 to msector do begin 179 case selection of 180 1 , 2 : k := i ; Appendix F. Simulation Programs Used in Thesis 167 A n Infinite Population M A R Slotted A L O H A (Poisson Input Traffic) 181 3 : k := msector - i + 1; 182 end; 183 i f (j < no_rooeivar) and (x[k] > 0.0) then begin 184 J := J + 1; 185 s_flag[ix[k]] := true; 186 end 187 else s_flag[ix[k]] := false; 188 end; 189 end; 190 end; {sector_selection} 191 192 .193 procedure insertque (e : l i n k ) ; 194 {insert transmission (new or old) into queue in the order of time) 195 var 196 p, r : l ink; 197 begin 198 p : •» queue; 199 r := n i l ; 200 while (p <> ni l ) and (pA.time <= eA.time) do begin 201 r := p; 202 p := p A .next; 203 end; {while) 204 i f r <> n i l then begin 205 e A .next := r A .next ; 206 r A .next := e; 207 end 208 else begin 209 i f p <> n i l then e A .next :=» p else eA.next := n i l ; 210 queue : = e; 211 end; 212 end; (insertque) 213 214 215 procedure ant_rx_pow (var x : sector); 216 {received power per user at each antenna, including Rayleigh fading) 217 var 218 power, angle, shi f t , phase, gain, sec_sep : rea l ; 219 i : integer; 220 begin 221 eec_sep := 2.0 / msector; 222 power := received_power; 223 angle := 2.0 * (drand(O) - 0.5); 224 shift := 0.0; 225 for i 1 to msector do begin 226 phase := cmod (angle + sh i f t ) ; 227 case ant_type of 228 1 : gain := rect (phase * msector); 229 2 : gain := scoe (phase * msector); 230 3 : gain : => sine (phase * msector) ; 231 end; (case) 232 case rayleigh of 233 1 : x[i] := gain * power; 234 2 : x[i] :=• ranexp(l.O) * gain * power; 235 end; {case) 236 shift := shift + sec_sep; 237 end; {for} 238 end; {ant_rx_pow) 239 240 Appendix F. Simulation Programs Used in Thesis 168 A n Infinite Population M A R Slotted A L O H A (Poisson Input Traffic) 241 procedure new_arr (t : real ) ; 242 {generate new packet and Insert Into queue) 243 var 244 event : l ink; 245 begin 246 new (event); 247 event'.time := t + ranexp (g); 248 event*.time_arr := event*.time; 249 event*.tx_no := 1; 250 ant_rx_pow (event* .rx_pow); 251 Insertque (event); 252 end; {new_arr) 253 254 255 procedure re_xsmn (e : l ink; t : real ) ; 256 {retransmit unsuccessful packet at one of the next k slots) 257 var 258 i : integer; 259 event : l ink; 260 begin 261 new (event) ; 262 event*.time := t + one_out_of (k_retx) - 0.5; 263 event*.time_arr := e*.time_arr; 264 event*.tx_no := e*.tx_no + 1; 265 case position of 266 1 : for i := 1 to msector do event*.rx_pow[i] := e*.rx_pow[i]; 267 2 : ant_rx_pow (event*.rx_pow); 268 end; {case} 269 insertque (event); 270 end; {re xsmn) 271 272 273 procedure i n i t i a l i s e ; 274 begin 275 elk :•= 0; 276 new (queue); 277 queue*.next :«* n i l ; 278 queue*.time := 2 * time_limit; 279 end; { init ial ise} 280 281 282 begin {main program) 283 writeln; 284 write ('Spatial density distr ibution : ' ) ; 285 readln (spatial); 286 case spatial of 287 1 : writeln ('uniform'); 288 2 : writeln ('bell-shaped'); 289 end; 290 write ('Transmitter position : ' ) ; 291 readln (position); 292 case position of 293 1 : writeln ('fixed'); 294 2 : writeln ('random'); 295 end; 296 write ('Antenna selection : ' ) ; 297 readln (selection); 298 case selection of 299 1 : writeln ('highest prob of success'); 300 2 : writeln ('largest power'); Appendix F. Simulation Programs Used in Thesis 169 A n Infinite Population M A R Slotted A L O H A (Poisson Input Traffic) 301 3 : writeln ('smallest non-zero power'); 302 4 : writeln ('random non-zero power'); 303 end; 304 write ('With Rayleigh fading : ' ) ; 305 readln (rayleigh); 306 case rayleigh of 307 1 : writeln ('No'); 308 2 : writeln ('Yes'); 309 end; 310 write ('Punctured radius ° ' ) ; 311 readln (pun_rad); 312 writeln (pun_rad:4:2); .313 write ('Noise power " ') ; 314 readln (noi_pow); 315 writeln (noi_pow:4:2); 316 write ('Capture ratio = ' ) ; 317 readln (cap_ratio); 318 writeln (oap_ratio:4:0) ; 319 write ('Beta = ' ) ; 320 readln (beta); 321 writeln (beta:4:l); 322 write ('Input t r a f f i c = ' ) ; 323 readln (g) ; 324 writeln (g:8:6); 325 write ('No. of sectors = ' ) ; 326 readln (msector) ; 327 writeln (msector:2); 328 write ('No. of receivers = ' ) ; 329 readln (no_receiver) ; 330 i f msector = 1 then no_receiver := 1; 331 writeln (no_receiver:2) ; 332 write ('Antenna type : ' ) ; 333 readln (ant_type); 334 i f msector = 1 then ant_type := 1; 335 case ant_type of 336 1 : writeln ( 'rect '); 337 2 : writeln ('slnc-cos'); 338 3 : writeln ('sine'); 339 end; 340 write ('Jc = ') ; 341 readln (k_retx); 342 writeln (k_retx:3); 343 writeln; 344 i f selection = 1 then begin (additional data (psrho) i s needed) 345 readln (nptr); 346 readln (column); 347 for i := 1 to nptr do begin 348 read (rho[i]); 349 for j := 1 to 12 do read (prhol[j]); 350 prho[i] := prho1[column]; 351 readln; 352 end; 353 end; 354 355 i_sum := 0; 356 c_sum := 0; 357 o_sum := 0; 358 a_sum := 0; 359 i_sum2 := 0; 360 c sum2 := 0; Appendix F. Simulation Programs Used in Thesis 170 A n Infinite Population M A R Slotted A L O H A (Poisson Input Traffic) 361 o sum2 := 0; 362 a sum2 :*> 0; 363 capture := cap_ratio / (cap_ratio + 1.0); 364 365 for m := 1 to 10 do begin 366 367 i n i t i a l i s e ; 368 in_traf := 0; 369 ch_traf := 0; 370 success : = 0; 371 delay := 0; 372 new_arr (elk); .373 374 repeat 375 counter := 0; 376 q := queue; 377 for i := 1 to msector do begin 378 max_pow(i] := 0; 379 tot_j>ow[i] := 0; 380 end; (for) 381 elk := trune (queue*.time) + 1.0; 382 383 while queue*.time <= elk do begin 384 for i := 1 to msector do begin 385 tot_pow[i] := tot_pow[i] + queue*.rx_pow[i]; 386 i f max_pow[i] < queue*.rx_pow[i] then maxpowfi] := queue*.rx pow[i]; 387 end; (for) 388 i f queue*.tx_no = 1 then begin 389 in_traf := in_traf + 1; 390 new arr (queue*.time); 391 end; ( i f ) 392 counter counter + 1; 393 queue := queue*.next; 394 end; (while) 395 396 ch_traf := ch_traf + counter; 397 sector_selection (tot_pow); 398 for i := 1 to counter do begin 399 for j := 1 to msector do 400 i f (s_flag[j]) and (q*.rx_pow[j] = max_pow(j]) and (q*.tx no > 0) 401 and (q*.rx_pow(j] > (capture * (tot_pow(J] + noi pow))) then 402 begin 403 q*.tx_no := 0; 404 success := success + 1; 405 delay := delay + elk - q*.time arr + 1.0; 406 end; {if} 407 i f (q*.tx_no > 0) then re_xsmn (q, elk + 1.0); 408 s := q; 409 q := s*.next; 410 dispose (s); 411 end; (for) 412 u n t i l elk >= tlme_limit; 413 414 dispose (queue); 415 writeln('duration = ' , c l k : 5 : 0 , ' s lots ' ) ; 416 writeln(' input channel output average_delay'); 417 ln_traf :•= in_traf / elk; 418 ch_traf := eh_traf / elk; 419 delay := delay / success; 420 success := success / elk; Appendix F. Simulation Programs Used in Thesis 171 A n Infinite Population M A R Slotted A L O H A (Poisson Input Traffic) 421 i_sum : = i_sum + in_traf; 422 o_sum := c_sum + ch_traf; 423 o_sum : = o_sum + success; 424 a_sum := a_sum + delay; 425 i~sum2 := l_sum2 + in_traf * in_traf; 426 c_sum2 := o_sum2 + oh_traf * ch_traf; 427 o_Bum2 := o_sum2 + success * success; 428 a sum2 := a_sum2 + delay * delay; 429 writeln(in_traf:14, ' ' ,ch_traf:14, ' ' ,success:14,' ' ,delay:14); 430 writeln; 431 end; {for} 432 .433 writeln'('Statistics:') ; 434 writeln; 435 i_mean := l_sum / 10; 436 c_mean := c_sum / 10; 437 o_mean := o_sum / 10; 438 a_mean := a sum / 10; 439 i_var := (10*i_sum2 - l_sum*l_sum) / (10 * 9); 440 c_var := (10*c_sum2 - c_sum*c_sum) / (10 * 9); 441 o_var := (10*o_sum2 - o_sum*o_sum) / (10 * 9); 442 a_var := (10*a_sum2 - a_sum*a_sum) / (10 * 9); 443 i _ c i := 3.25 * sqrt( i_var / 10 ); 444 c_ci := 3.25 * sqrt( c_var / 10 ); 445 o_ci := 3.25 * sqrt( o_var / 10 ); 446 a_ci := 3.25 * sqrt( a_var / 10 ); 447 writeln(' input channel output delay') ; 448 writeln('mean: ',i_mean:12,' ',c_mean:12,' ',o_mean:12,' ' ,a_mean:12); 449 writeln('variance: ',i_var:12,' ',c_var:12,' ',o_var:12,' ' ,avar:12); 450 writeln('99% C . I . : ',l_ci:12,' ',c_ci:12,' ',o_ci:12,' ' , a_ci7l2); 451 452 end. {main} Appendix F. Simulation Programs Used in Thesis 172 F.3 A n Infinite Population M A R Slotted A L O H A (Poisson Channel Traffic) Simulation Program In this section, we present a program which simulates the infinite population MAR slotted ALOHA system using the assumption that the channel traffic is Poisson. The program language is FORTRAN77. Results which cannot be obtained using the approach in Section 6.1 for systems with uniform spatial traffic density or non-ideal antenna patterns are obtained using this simulation. The running time depends mainly on the value of the average channel traffic. Table F.3 illustrates how the CPU time (on a SUN 3/50 computer) increases with the channel traffic per sector g for the following inputs: M = 8, Nr = 2, c = 4, f3 = 4, n = 0, p — 0, antenna pattern: rect, bell-shaped traffic density and no signal fading. Channel Throughput CPU time traffic (seconds) 0.5 1.6437 ±0.0134 594 1 1.6134 ±0.0222 1121 2 1.5245 ±0.0209 2140 4 1.4686 ±0.0297 4158 8 1.4402 ±0.0197 8173 Table F.3: CPU time for the infinite population MAR slotted ALOHA simulation pro-gram (Poisson channel traffic). Number of time slots processed = 104. Appendix F. Simulation Programs Used in Thesis 173 A n Infinite Population M A R Slotted A L O H A (Poisson Channel Traffic) 1 c Simulation: an in f in i t e population MAR slotted ALOHA system. 2 c msect sectors, nr receivers, poisson channel t r a f f i c 3 c c = capture rat io 4 c nuser = Poisson r . v . 5 e received power proportional to distance ** -beta 6 c antenna type: 1 ideal , 2 sinc-cos, 3 B i n e 7 c constant noise power 8 c with / without Rayleigh fading 9 c user spatial d i s t : uniform or gaussian 10 c punctured radius = punr 11 c Aug 30, 88. (revised Feb 16, 89) 12 .13 impl ic i t real*8 (a-h,o-z) 14 dimension prho (454) , r(454), pr(454,12) 15 common prho, r , nptr 16 17 c reading input data (psrho) as required by Scheme 1 18 open (unit=20, f i le='psrho.dat' , status='old') 19 read (20,*) nptr 20 do 10 i = l ,np tr 21 read (20,*) r ( i ) , (pr ( i , J), 3-1,12) 22 10 continue 23 close (unit=20) 24 25 c input parameters (descriptions in the format of write statement) 26 read (5,*) c, beta, pnoise, actnoi, msect, nr, i d i s t , ifade, itype, 27 punr 28 offnoi = actnoi - pnoise 29 i f (msect .eq. 1) then 30 nr o 1 31 itype " 1 32 endif 33 write (6,'(/ ,"Simulation (with 99% confidence intervals)")') 34 write ( 6 , ' ( i l , " sectors " , i l , " receivers slotted ALOHA")') msect, nr 35 i f (itype .eq. 1) write (6,'("Antenna type : ideal")') 36 i f (itype .eq. 2) write (6,'("Antenna type : sinc-cos")') 37 i f (itype .eq. 3) write (6,'("Antenna type : sine")') 38 write (6,' ("No. of users = Poisson"s r .v .") ' ) 39 i f ( idist .eq. 0) write (6,'("User spatial d l s t r . : Uniform")') 40 i f ( idist .eq. 1) write (6,'("User spatial d i s t r . : Gaussian")') 41 write (6,'("capture rat io = ",e8.2,/,"beta ° ",f4.1)') c, beta 42 write (6,'("known noise power *» ",f4.1)') pnoise 43 write (6,'("actual noise power = ",f4.1)') actnoi 44 write (6,'("punctured radius = ",f4.2)') punr 45 i f (ifade .eq. 0) write (6,'("No signal fading")') 46 i f (ifade .eq. 1) write (6,'("With Rayleigh fading")') 47 write (6,'(/,"G/M",4x,"Optimum",14x,"Largest",14x, "Smallest non-zero", 48 . 4x,"Random non-zero")') 49 50 r2 = dsqrt(2.0d0) 51 do 100 3 = 1,12 52 gm = r2 ** (3-6) 53 g o gm * dfloat(msect) 54 seed = O.OdO 55 suml •= O.OdO 5 6 suml = 0.OdO 57 sumk = 0.OdO 58 sumr = O.OdO 59 sum21 = O.OdO 60 sum2i = O.OdO Appendix F. Simulation Programs Used in Thesis 174 A n Infinite Population M A R Slotted A L O H A (Poisson Channel Traffic) 61 sum2k = 0 . OdO 62 sum2r ** 0 . OdO 63 do 20 i = l .nptr 64 prho(i) = p r ( i , j ) 65 20 continue 66 67 do 40 n t r i a l = 1,10 68 lsucc •» 0 69 isucc = 0 70 ksucc = 0 71 nsucc = 0 72 do 30 nthrow = 1,1000 .73 c irandp is a poisson random number generator with mean = g 74 nuser = irandp (g, seed) 75 i f (nuser .gt. 0) then 76 c a l l throw (lsucc, isucc, ksucc, nsucc, msect, nr, nuser, 77 beta, c, itype, i d i s t , pnoise, ifade, punr, offnoi, actnoi) 78 endif 79 30 continue 80 t l = dfloat(lsucc) / 1000.dO 81 t i = dfloat(isucc) / 1000.dO 82 tk <= dfloat (ksucc) / 1000. dO 83 t r = dfloat(nsucc) / 1000.dO 84 suml = suml + t l 85 sumi = sumi + t i 86 sumk = sumk + tk 87 sumr °> sumr + t r 88 sum21 = sum21 + t l * t l 89 sum2i «» sum2i + t i * t i 90 sum2k = sum2k + tk * tk 91 sum2r «» sum2r + t r * t r 92 40 cont inue 93 s i - suml / 10.OdO 94 s i si sumi / 10.OdO 95 sk = sumk / 10. OdO 96 sr " sumr / 10.OdO 97 sdl «• dsqrt ((sum21 - suml**2 / 10.OdO) / 9.OdO) 98 sdi = dsqrt((sum2i - sumi**2 / 10.OdO) / 9.OdO) 99 sdk = dsqrt((sum2k - sumk**2 / 10.OdO) / 9.OdO) 100 sdr = dsqrt((sum2r - sumr**2 / 10.OdO) / 9.OdO) 101 sl99 = 3.25d0 * sdl / dsqrt(10 OdO) 102 si99 «= 3.25d0 * sdi / dsqrt (10 OdO) 103 sk99 = 3.25d0 * sdk / dsqrt(10 OdO) 104 sr99 = 3.25d0 * sdr / dsqrt(10 OdO) 105 s l l = s i - 8199 106 slu a s i -f sl99 107 s i l = s i - si99 108 slu = s i + si99 109 ski « sk - sk99 110 sku = sk + sk99 111 s r l » or - sr99 112 sru = sr + sr99 113 114 write (6,80) gm, ski ,sk,sku, s i l , s i , s l u , s l l , s i , s lu, s r l , s r , s ru 115 80 format (f6.4,12(lx,f6.4)) 116 100 continue 117 118 stop 119 end 120 Appendix F. Simulation Programs Used in Thesis 175 A n Infinite Population M A R Slotted A L O H A (Poisson Channel Traffic) 121 122 subroutine throw (lsucc, isucc, ksucc, nsucc,msect, nr, miser,beta, c. 123 i type, idist ,pnoise , i fade,punr,offnoi ,actnoi) 124 o th is subroutine does the following: 125 c 1. increment lsucc i f there i s a successful xsmn in each of the nr lowest 126 c non-zero power sector. 127 c 2. increment isucc i f there i s a successful xsmn in each of the nr highest 128 c power sector. 129 c 3. increment Icsucc i f there is a successful xsmn in each of the nr sectors 130 c with highest prob of success. 131 c 4. increment nsucc i f there i s a successful xsmn in each of the nr randomly 132 c picked sector. 133 impl ic i t real*8 (a-h,o-z) 134 dimension rhomax(10), rhotot(10), kl(10), ki(10), kk(10), kr(10). 135 ml (10), mi (10), mk(10), mr(10), imax(10) 136 137 do 10 m = 1, insect 138 rhotot(m) = offnoi 139 rhomax(m) = 0.OdO 140 10 continue 141 do 20 i = l ,nuser 142 rho ° upower ( ld is t , beta, ifade, punr) 143 c a l l newusr (rho, msect, rhomax, rhotot, imax, i , itype) 144 20 continue 145 c a l l select (kl, k i , kk, kr, rhotot, msect, nr, c, pnoise) 146 do 30 m = 1,msect 147 ml (m) = imax (m) 148 mi (m) = imax (m) 149 mk(m) = imax(m) 150 mr (m) = imax (m) 151 30 cont inue 152 do 40 n = l , n r 153 i f (ml(kl(n)) .gt. 0) c a l l ixsmn(lsucc, ml, msect, kl(n) , 154 rhomax(kl(n)), rhotot(kl(n))-offnoi, c, actnoi) 155 i f (mi(ki(n)) .gt. 0) c a l l ixsmn(isucc, mi, msect, kl(n) , 156 rhomax(ki(n)), rhotot(ki(n))-offnoi, c, actnoi) 157 i f (mk(kk(n)) -gt. 0) c a l l ixsmn(ksucc, mk, msect, kk(n). 158 rhomax(kk(n)), rhotot(kk(n))-offnoi, c, actnoi) 159 i f (mr(kr(n)) .gt. 0) c a l l ixsmn (nsucc, mr, msect, kr(n). 160 rhomax(kr(n)), rhotot(kr(n))-offnoi, c, actnoi) 161 40 continue 162 return 163 end 164 165 166 subroutine newusr (rho,msect,rhomax, rhotot, imax, iuser, itype) 167 o Given the received power rho of a new user (with ideal antenna), 168 c this subroutine does the following: 169 c 1. computes i t s orientation angle. 170 c 2. computes the power received by each sector (based on antenna type), 171 c 3. add to the to ta l received power of the corresponding sector. 172 c 4 determines the user which has the largest signal power in each sector. 173 implic i t real*8 (a-h,o-z) 174 dimension rhomax(msect), rhotot(msect), imax(msect) 175 176 angle • 2.OdO * (drand(O) - O.SdO) 177 sector = dfloat(msect) 178 secsep = 2.OdO / sector 179 shift' = O.OdO 180 do 10 m = 1,msect Appendix F. Simulation Programs Used in Thesis 176 A n Infinite Population M A R Slotted A L O H A (Poisson Channel Traffic) 181 phase = cmod (angle + shift) 182 i f (itype .eq. 1) gain = rect(phase * sector) 183 i f (itype .eq. 2) gain = scos(phase * sector) 184 i f (itype .eq. 3) gain = sine(phase * sector) 185 rxpow = rho * gain 186 rhotot(m) = rhotot(m) + rxpow 187 i f (rxpow .gt. rhomax(m)) then 188 rhomax(m) = rxpow 189 imax(m) = iuser 190 endif 191 shift = shift + secsep 192 10 continue 193 return 194 end 195 196 197 function upower ( id is t , beta, ifade, punr) 198 c upower returns the received power of a user using an ideal antenna 199 c id i s t i s the user dis tr ibut ion type (0:uniform, l:gaussian) 200 implic i t real*8 (a-h,o-z) 201 data cont/0.893243841d0/ 202 10 i f ( idist .eq. 0) then 203 d = dsqrt( drand(O) ) 204 else 205 d = cont * dsqrt ( dabs (randn (0)) ) 206 endif 207 i f (d . l e . punr) goto 10 208 power = d ** (-beta) 209 i f (ifade .eq. 0) then 210 upower = power 211 else 212 upower = power * (-dlog(drand(0))) 213 endif 214 return 215 end 216 217 218 subroutine select (kl , k i , kk, kr, rhotot, msect, nr, c, pnoise) 219 c returns the indices of those selected sectors according to the 220 c corresponding selection rule . 221 c kk for Scheme 1 222 c k i for Scheme 2 223 c k l for Scheme 3 224 c kr for Scheme 4 225 impl ic i t real*8 (a-h,o-z) 226 dimension kl (nr) , k i (nr ) , kk(nr), rhotot(msect) , ix(10), iy(10). 227 prob (10), kr(nr) , lz(10) 228 nzero = 0 229 do 10 m = 1,msect 230 prob(m) = psrho(rhotot(m), c, pnoise) 231 ix(m) = m 232 iy(m) = m 233 i f (rhotot(m) .gt. O.OdO) then 234 nzero = nzero + 1 235 iz(nzero) = m 236 endif 237 10 continue 238 do 20 J = msect, 2,-1 239 do 20 i = 2,j 240 i f (rhotot( ix( i- l )) . I t . rhotot(ix(i))) then Appendix F. Simulation Programs Used in Thesis 177 A n Infinite Population M A R Slotted A L O H A (Poisson Channel Traffic) 241 index = i x ( i - l ) 242 i x ( i - l ) = ix( l ) 243 ix( i ) o index 244 endif 245 i f (prob(ly(i- l )) . I t . prob(iy(i))) then 246 index >=> i y ( i - l ) 247 i y ( i - l ) = iy( i ) 248 iy ( i ) = index 249 endif 250 20 continue 251 m = msect 252 30 i f (rhotot(ix(m)) .gt. O.OdO) goto 40 •253 m = m - 1 254 i f (m .gt. 0) goto 30 255 40 continue 256 i = nzero 257 do 50 n = l , n r 258 i f (m . l e . 0) m = msect 259 kl(n) = ix(m) 260 m = m - 1 261 xi(n) = ix(n) 262 kk(n) = ly(n) 263 i f (nzero . l e . nr) then 264 kr(n) = ix(n) 265 else 266 j = i p i c k l ( i ) 267 ltr(n) = iz(j) 268 iz ( j ) = iz ( i ) 269 i = i - 1 270 endif 271 50 continue 272 return 273 end 274 275 276 function i p i c k l (i) 277 c randomly pick one number out of i 278 impl ic i t real*8 (a-h,o-z) 279 x = dfloat( i) * drand(0) 280 i p i c k l = int(x) + 1 281 return 282 end 283 284 285 subroutine ixsmn ( i , m, msect, kn, rhom, rhot, c, pnoi) 286 c given the selected sector, i f there i s a successful transmission, 287 c this subroutine does the following: 288 c 1. increment i 289 c 2. set those m=m(kn) to zero 290 impl ic i t real*8 (a-h,o-z) 291 dimension m(msect) 292 i f (rhom .gt. c*(rhot-rhom+pnoi)) then 293 i = i + 1 294 n = m(kn) ^ 295 do 10 j = 1,msect 296 i f (m(j) .eq. n) m(j) = 0 297 10 continue 298 endif 299 return 300 end Appendix F. Simulation Programs Used in Thesis 178 A n Infinite Population M A R Slotted A L O H A (Poisson Channel Traffic) 301 302 303 function psrho (rho, c, pnoise) 304 c psrho returns the prob of success given rho 305 impl ic i t real*8 (a-h,o-z) 306 dimension prho(454), r(454) 307 common prho, r, nptr 308 i f (rho . l e . c*pnoise) then 309 psrho = 0.OdO 310 else 311 i f (rho .gt. r ( l ) .and. rho .I t . r(nptr)) then 312 do 10 i = 2,nptr 313 i f (rho . I t . r ( i ) ) then 314 delp = prho(i) - prho(i- l ) 315 delr = r( i ) - r ( i - l ) 316 grad = delp / delr 317 psrho = prho(i) - (r(i)-rho) * grad 318 return 319 endif 320 10 continue 321 else 322 i f (rho . l e . r ( l ) ) psrho = prho(l) 323 i f (rho .ge. r(nptr)) psrho = prho(nptr) 324 endif 325 endif 326 return 327 end 328 329 330 function cmod (x) 331 impl ic i t real*8 (a-h,o-z) 332 cmod = x 333 10 i f (cmod . l e . l.OdO) return 334 cmod " cmod - 2. OdO 335 goto 10 336 end 337 338 339 function rect (x) 340 implic i t real*8 (a-h,o-z) 341 i f (x . I t . -l.OdO .or. x .gt. l.OdO) then 342 rect = 0.OdO 343 else 344 rect = l.OdO 345 endif 346 return 347 end 348 349 350 function sine (x) 351 implic i t real*8 (a-h,o-z) 352 i f (x .eq. O.OdO) then 353 sine m l.OdO 354 else 355 y = 1.39d0 * x 356 sine = (dsin(y) / y) ** 2 357 endif 358 return 359 end 360 Appendix F. Simulation Programs Used in Thesis 179 An Infinite Population MAR Slotted ALOHA (Poisson Channel Traffic) 361 362 function scos (x) 363 implicit real*8 <a-h,o-z) 364 i f (x .eq. O.OdO) then 365 scos = l.OdO 366 else 367 y = 11.35d0 * (dcos(0.5d0*x) - l.OdO) 368 scos = (dsln(y) / y) ** 2 369 endif 370 return 371 end Appendix F. Simulation Programs Used in Thesis 180 F.4 A Finite Population M A R Slotted A L O H A Simulation Program The throughput performance of the finite population M A R slotted A L O H A system de-scribed in Chapter 5 can be obtained by Monte Carlo simulation. The simulation program is written in P A S C A L . This program is also used to simulate the finite population M A R slotted A L O H A system with mobility model 2 as discussed in Section 5.3.7. For a given set of system (input) parameters, the running time of this simulation program depends on the probabilities pa and pr. To illustrate how the C P U time varies with p0 (pr = 10po)) the simulation was run on a SUN 3/50 computer for various values of pQ. The results are tabulated in Table F.4 with the following input parameters: N = 100, M = 4, NT = 1, c = 4, 8 = 4, n — 0, p — 0, antenna selection: Scheme 2, antenna pattern: sine, uniform traffic density and no fading. Po Throughput C P U time (seconds) 0.00125 0.1223 ±0.0024 1508 0.00250 0.2444 ±0.0055 1652 0.00500 0.4769 ±0.0092 2013 0.01000 0.7212 ±0.0063 4434 0.02000 0.6141 ±0.0071 13910 0.04000 0.5992 ±0.0067 31139 Table F.4: C P U time for the finite population M A R slotted A L O H A simulation program. Number of time slots processed = 5 x 10 4. Appendix F. Simulation Programs Used in Thesis 181 A Finite Population MAR Slotted ALOHA I program simulation_fp_MAR_ALOHA (input, output); 2 3 ( f in i te population msector sectors nreceiver nuser slotted ALOHA } 4 (uniform spatial t r a f f i c density, nuser mobile users } 5 (O-state users transmit with probabil i ty po } 6 {R-state users transmit with probabil i ty pr } 7 (date: Jan 24, 89 (revised Jun 30, 89) ) 8 (revised Aug 9, 89 (Rayleigh fading and noise) ) 9 (revised Aug 29, 89 (Punctured radius) } 10 II const 12 time_limit = 5000; 13 14 type 15 sector = array [1..8] of real ; 16 isector = array [1..8] of integer; 17 state = (0,T,R) ; 18 antenna_type = (ideal type,sine type,scos type); 19 user_record = record 20 status : state; 21 m_power : sector; 22 power : sector; 23 end; 24 25 var 26 i , J , )c, 1, m, n, rayleigh : integer; 27 scheme, msector, nuser, nreceiver : integer; 28 pr, po, cap_ratio, beta, noise, rho, dummy : rea l ; 29 sector_sep, interference, no_success, no_input : rea l ; 30 g, s, sumg, sums, sumg2, sums2, dg, ds, g99, s99, gm, sm, gp, sp : r e a l ; 31 sector_power, desire_power : sector; 32 selected_sector, desire_user : isector; 33 antenna : antenna_type; 34 user : array [1..100] of user_record; 35 36 37 function drand (dummy:integer) : real ; 38 (This ext function is used instead of the Pascal function random(O)} 39 (because some inaccuracy in the f ina l result was encountered when) 40 {random(0) was used.) 41 external fortran; 42 43 44 function ranexp : rea l ; 45 (returns a exp. d i s t r . r . v . with unit mean) 46 var 47 x : rea l ; 48 begin 49 repeat x := drand(0) u n t i l x <> 0.0; 50 ranexp := - ln(x); 51 end;(ranexp) 52 53 54 function received_power : real; 55 (returns the received power of a user) 56 var 57 x : rea l ; 58 begin 59 repeat x :<= drand(0) u n t i l x > rho; 60 received_power := exp (-beta / 2.0 * ln(x)); Appendix F. Simulation Programs Used in Thesis 182 A Finite Population M A R Slotted A L O H A 61 end;{received_power) 62 63 64 function cmod (x:real) : rea l ; 65 begin 66 while x >= 1.0 do x := x - 2.0; 67 cmod := x; 68 end;{cmod} 69 70 71 function rect (x:real) : real ; 72 {ideal antenna) 73 begin 74 i f (x < -1.0) or (x > 1.0) then rect := 0.0 else rect := 1.0; 75 end;{rect} 76 77 78 function Bine (x:real) : rea l ; 79 {antenna with sine function) 80 var 81 y, I : real; 82 begin 83 i f x = 0.0 then sine : = 1.0 else begin 84 y := 1.39 * x; 85 z := sin(y) / y; 86 sine := z * z; 87 end; 88 end;{sine} 89 90 91 function scos (x:real) : rea l ; 92 {antenna with sine-cos function} 93 var 94 y, z : real ; 95 begin 96 i f x = 0.0 then scos : = 1.0 else begin 97 y := 11.35 * (cos(x/2.0) - 1.0); 98 z := sin(y) / y; 99 scos := z * z; 100 end; 101 end;{scos} 102 103 104 function random select (i,n:integer) : integer; 105 {randomly select one number from [i..n]} 106 var 107 m : integer; 108 begin 109 m := n - i + 1; 110 random_select trune (m * drand(O)) + i ; 111 end;{random_select} 112 113 114 function small_select (i,n:integer) : integer; 115 {choose small select from [ i . .n] such that } 116 {sector_power[selected sector[small_select]] i s the smallest) 117 var 118 j , k, m : integer; 119 begin 120 m := i + 1; Appendix F. Simulation Programs Used in Thesis 183 A Finite Population MAR Slotted ALOHA 121 k := i ; 122 for j := m to n do i f 123 sector_power[selected_sectorIk]] > sector_power[selectod_sector[j]] 124 than k := j ; 125 small_select := k; 126 end;{small_select} 127 128 129 function large_eelect (i ,n:integer) : integer; 130 {choose large_select from [ i . .n] such that } 131 {sector_power[selected_sector[large_select]] i s the largest) 132 var .133 j , k, m : integer; 134 begin 135 m := i + 1; 136 k := i ; 137 for j := m to n do i f 138 sector_power[selected_sector[k]] < sector_power[selected_sector[j]] 139 then k := j ; 140 large_select := k; 141 end;{large_select) 142 143 144 procedure xchange ( i , j : integer) ; 145 {xchange selected_sector[i] with selected_aector[j]) 146 var 147 k : integer; 148 begin 149 k := selected_sector[i]; 150 selected_sector[1] := selected_sector[j]; 151 selected_sector[j] := k; 152 end; 153 154 155 procedure transmit (var x:user_record); 156 (user x is sending, set status to T, determine position and power) 157 var 158 power, angle, sh i f t , phase, gain : rea l ; 159 i : integer; 160 begin 161 x.status := T; 162 power := received_power; 163 angle := 2.0 * (drand(O) - 0.5); 164 shift :» 0.0; 165 for i := 1 to msector do begin 166 phase :°> cmod (angle + sh i f t ) ; 167 case antenna of 168 ideal_type : gain := rect (phase * msector); 169 slnc_type : gain := sine (phase * msector); 170 scos_type : gain := scos (phase * msector); 171 end;{case) 172 x.m_power[i] := gain * power; 173 shift := shif t + sector_sep; 174 end;{for} 175 end;{transmit) 176 177 178 procedure retransmit (var x:user_record) ; 179 (retransmit user x, set status to T, position and power unchange} 180 begin Appendix F. Simulation Programs Used in Thesis 184 A Finite Population MAR Slotted ALOHA 181 x.status := T; 182 end;{retransmit} 183 184 185 procedure antenna_power; 186 {sum up the to ta l received power per sector in sector_power} 187 var 188 i , m : integer; 189 begin 190 for m := 1 to msector do sector_power{m] := 0.0; 191 for i := 1 to nuser do begin 192 i f user[i] .status = T then .193 for m := 1 to msector do 194 sectorjpower[m] := sector_power[m] + user[i].power[m]; 195 end; 196 end;{antenna_power} 197 198 199 procedure antenna_select (scheme:integer); 200 {place the indices of the selected sectors in the) 201 {f irst nreceiver elements of the array selected sector) 202 var 203 i , j , m, n : integer; 204 begin 205 i := msector; 206 n := 0; 207 for m := 1 to msector do 208 i f sector_power[m] > 0.0 then begin 209 n := n + 1; 210 selected sector[n] := m; 211 end 212 else begin 213 selected sector[i] m; 214 i := i - 1; 215 end; 216 {n i s the number of non-zero power sectors) 217 i f n > nreceiver then for j := 1 to nreceiver do begin 218 case scheme of 219 1 : m :» random_select ( j ,n); 220 2 : m := small_select ( j ,n); 221 3 : m := large select (j ,n); 222 end;(case) 223 xchange (j,m) ; 224 end; 225 end;{antenna_select} 226 227 228 procedure desire signal_power; 229 {place the strongest signal power per sector in desire_power} 230 var 231 i , j , m : integer; 232 begin 233 for i := 1 to nreceiver do begin 234 m := selected_sector[1] ; 235 desire_power[m] := 0.0; 236 for j := 1 to nuser do begin 237 i f user[j] .status = T then 238 i f user[j].power[m] > desire_power[m] then begin 239 desire_power[m] := user[j].power[m] ; 240 desire user[m] := j ; Appendix F. Simulation Programs Used in Thesis 185 A Finite Population M A R Slotted A L O H A 241 end;{if} 242 end;{for j) 243 end;{for i} 244 end;{desire_signal_power} 245 246 247 begin {main program) 248 readln (cap_ratio); 249 readln (beta); 250 readln (nuser); 251 readln (msector); 252 readln (nreceiver); 253 readln ( i ); {antenna type: 1 for ideal , 2 for sine, 3 for sinc--cos} 254 i f msector = 1 then i := 1; 255 i f nreceiver > msector then nreceiver : - msector; 256 case i of 257 1 : antenna := ideal_type; 258 2 : antenna := sine type; 259 3 : antenna := scos_type; 260 end;(case) 261 readln (1); {1 for fixed posit ion, 2 for random) 262 readln (scheme); {1 random, 2 smallest, 3 largest selection) 263 readln (rayleigh); {0 no fading, 1 with rayleigh fading} 264 readln (noise); {constant noise power) 265 readln (rho); {punctured radius} 266 267 writeln ( 'Finite population slotted Aloha (simulation with 99% CI) ' ) ; 268 writeln ('Spatial d is tr ibut ion : Uniform'); 269 case antenna of 270 ideal_type : writeln ('Antenna type : idea l ' ) ; 271 sinc_type : writeln ('Antenna type : s ine'); 272 scos_type : writeln ('Antenna type : sine-cos'); 273 end;(case) 274 case 1 of 275 1 : writeln ('R-state user position : f ixed'); 276 2 : writeln ('R-state user position : Random'); 277 end;(case) 278 case scheme of 279 1 : writeln ('Antenna selection : Random non-zero'); 280 2 : writeln ('Antenna selection : Smallest non-zero'); 281 3 : writeln ('Antenna selection : Largest'); 282 end;(case) 283 write ('Constant noise power = ',noise:6:2, ' and ' ) ; 284 case rayleigh of 285 0 : writeln ('no fading'); 286 1 : writeln ('with rayleigh fading'); 287 end;(case) 288 writeln {'Number of users * ' ,nuser:3); 289 writeln ('Number of sectors = ',msector:1); 290 writeln ('Number of receivers «= ' ,nreceiver: 1) ; 291 writeln ('Capture rat io = ' ,cap_ratio:2); 292 writeln ('Punctured radius => ' ,rho:5:3); 293 writeln ('Beta ° ' .beta:4:1); 294 writeln; 295 writeln (' Channel Traf f i c Throughput'); 296 297 sector sep := 2.0 / msector; 298 po := 0.0; 299 g := 0.0; 300 Appendix F. Simulation Programs Used in Thesis 186 A Finite Population M A R Slotted A L O H A 301 repeat {until t r a f f i c g > 8} 302 po := po + 0.001; 303 pr : <* 10.0 * po ; 304 suing : = 0.0; 305 sumg2 := 0.0; 306 sums := 0.0; 307 sums2 := 0.0; 308 for i := 1 to nuser do user[i] .status := 0; 309 310 for j := 1 to 10 do begin 311 no input := 0.0; 312 no success : - 0.0; •313 314 for n := 1 to time l imit do begin 315 for i := 1 to nuser do begin 316 case user[i] .status of 317 0 : i f drand(0) <= po then transmit (user [i] Ji-318 ll : i f drand(0) <•= pr then 319 i f 1 «= 1 then retransmit (user[i]) else transmit (user[i]); 320 T : writeln ('ERROR, user ' ,1 :3 , ' at T-state in the end of a s lo t ' ) ; 321 end;(case) 322 i f user[1].status = T then case rayleigh of 323 0 : for k := 1 to msector do 324 user[i].power[k] := user[i].m_power[k]; 325 1 : for k := 1 to msector do 326 user[i].power[k] := ranexp * user[i].m_power[k]; 327 end;(case) 328 end;{for i} 329 330 antenna_power; 331 antenna_select (scheme); 332 de s ire_s ignal_power; 333 for i := 1 to nuser do 334 i f user[i] .status = T then no_input := no_input + 1.0; 335 336 for i :=> 1 to nreceiver do begin 337 m := selected_sector[i]; 338 i f user[desire_user[m] ].status = T then begin 339 interference :•= sector_power [m] - desire_power [m] + noise; 340 i f desire_power[m] > (cap_ratio * interference) then begin 341 no success := no success + 1.0; 342 user[deslre_user[m]].status := 0; 343 end; 344 end; 345 end;{for i ) 346 347 for i := 1 to nuser do 348 i f user[1].status = T then user[i] .status := R; 349 350 end;{for n} 351 352 g := no_input / time l imit ; 353 s := no_success / time_limit; 354 sumg := sumg + g; 355 sumg2 := sumg2 + g * g; 356 sums := sums + s; 357 sums2 := sums2 + s * s; 358 end;{for j) 359 360 g := sumg / 10.0; Appendix F. Simulation Programs Used in Thesis 187 A Finite Population M A R Slotted A L O H A 361 s : = sums / 10.0; 362 dg := sqrt((sumg2 - sumg * sumg / 10.0) / 9.0); 363 ds := sqrt((sums2 - sums * sums / 10.0) / 9.0); 364 g99 := 3.25 * dg / sqrt(10.0); 365 899 := 3.25 * ds / sqrt(10.0); 366 gm := g - g99; 367 sm := a - s99; 368 gp := g + g99; 369 sp := s + s99; 370 writeln (gm:8:5,' ' ,g:8:5, ' ' ,gp:8:5, ' ' ,sm:8:5,' ' , s :8:5 , ' ' , sp:8:5); 371 u n t i l g >= 8.0; 372 writeln; •373 end.(main) Appendix F. Simulation Programs Used in Thesis 188 F . 5 A Simulation Program for Estimating Following is a program written in FORTRAN77 for estimating the probability, g ,^-, that j out of i contending packets are successfully received (see Section 5.2). It took less than 10 minutes ( C P U time on a SUN 3/50 computer) to obtain the set of probabilities {qj\i}, j = 1,2, • • •, 100, with 99 percent confidence intervals falling within 10 percent of the mean values. Once the set of probabilities {qj\i} is obtained, the Markovian model described in Section 5.1 can be used to analyze the throughput performance as well as the dynamic behaviour of the finite population M A R slotted A L O H A system. Appendix F. Simulation Programs Used in Thesis 189 Probability P^ 1 C This program computes q ( i , j ) by Monte Carlo simulation for the Slotted 2 C ALOHA scheme with NR receivers and NS direct ional antennas. 3 C July 3, 1987 (Revised Aug 4) . 4 C include b e l l spatial d i s tr and 3 capture models 5 C Mar 21, 89 (revised Jul 18, 89) . 6 7 IMPLICIT REAL*8 (A-H.O-Z) 8 DIMENSION Q(200,4), ISUCC(200), p(200,10) 9 10 READ (*,*) N, NTRIAL, NR, NS, M, C, ITYPE, IDIST, rho, MCAP 11 12 C N = No. of users .13 C NR = No. of receivers 14 C NS = No. of sectors or antennas 15 C M = Attenuation factor 16 C C = Capture rat io 17 C ITYPE = Antenna : 1, 2 and 3 for ideal , sinc-cos and sine resp. 18 C IDIST = Punctured spatial d i s tr : 1 and 2 for uniform and b e l l resp. 19 C rho = punctured radius 20 C MCAP = Capture model : 1 largest signal > c * second largest signal 21 C 2 largest signal > c * to ta l interference s ignal 22 23 IF (NR .GT. NS) NR = NS 24 IF (NS .EQ. 1) ITYPE = 1 25 WRITE (*,50) N, NTRIAL, NR, NS, M, C 26 IF (IDIST .EQ. 1) WRITE (*,100) rho 27 IF (IDIST .EQ. 2) WRITE (*,110) rho 28 i f (mcap .eq. 1) write (*,120) 29 i f (mcap .eq. 2) write (*,130) 30 IF (ITYPE .EQ. 1) WRITE (*, 60) 31 IF (ITYPE .EQ. 2) WRITE (*,70) 32 IF (ITYPE .EQ. 3) WRITE (*,80) 33 DEL = 1.0D0 / DFLOAT (NTRIAL) 34 35 DO 10 I = 1,N 36 DO 10 K = 1,NR 37 Q(I,K) = O.0DO 38 10 continue 39 40 DO 20 J = 1,NTRIAL 41 CALL ICOLLN (ISUCC, NS, N, M, C, NR, ITYPE, IDIST, rho, mcap) 42 DO 20 I = 1,11 43 DO 20 K ° 1,NR 44 IF (ISDCC(I) .EQ. K) Q(I,K) = Q(I,K) + DEL 45 20 continue 46 47 DO 30 I = 1,N 48 WRITE (*,90) I, (Q (I, K) , K=l, NR) 49 30 continue 50 51 50 FORMAT ('NO. OF USERS = ' , 1 3 , / , ' N O . OF TRIALS = ' , 14 , / , 52 . 'NO. OF RECEIVERS = ' ,12 , / , 53 'NO. OF SECTORS = ' , 1 2 , / , ' A T T N FACTOR = ' , 1 1 , / , 54 . 'CAPTURE RATIO = ',F6.1) 55 60 FORMAT ('ANTENNA: IDEAL',/ ,2X, ' I ' , 2 X , ' Q ' ) 56 70 FORMAT ('ANTENNA: SINC-COS',/, 2X, ' I ' , 2X, ' Q') 57 80 FORMAT ('ANTENNA: SINC , / , 2X, ' I ' , 2X, ' Q') 58 90 FORMAT (13, 4 (2X,F8 . 6) ) 59 100 FORMAT ('SPATIAL DISTRIBUTION: UNIFORM, punctured R = ' ,f4.2) 60 110 FORMAT ('SPATIAL DISTRIBUTION: BELL, punctured R = ' ,f4.2) Appendix F. Simulation Programs Used in Thesis 190 Probability P^ 61 120 format ('CAPTURE MODEL 1 (SIMPLE)') 62 130 format ('CAPTURE MODEL 2 (TOTAL INTERFERENCE)') 63 64 STOP 65 END 66 67 68 C This subroutine returns ISUCC = no. of successful txmn. 69 SUBROUTINE ICOLLN (ISUCC,NS,N,M,C,NR,ITYPE,IDIST,rho,mcap) 70 IMPLICIT REAL*8 (A-H,0-Z) 71 DIMENSION POW(200, 8) , TPOW(8) , K(8), ISUCC (200) , LOC(8) 72 .73 C I = no. of co l l id ing packets 74 75 SECTOR = DFLOAT (NS) 76 SECSEP = 2.ODO / SECTOR 77 DO 10 IS = 1,NS 78 TPOW(IS) = O.ODO 79 10 continue 80 81 DO 50 I = 1,N 82 POWER = UPOWER (M, IDIST, rho) 83 ANGLE = 2.ODO * (DRAND(0) - 0.5D0) 84 SHIFT = O.ODO 85 DO 20 IS = 1,NS 86 PHASE = CMOD (ANGLE + SHIFT) 87 IF (ITYPE .EQ. 3) GAIN = SIDE (PHASE * SECTOR) 88 IF (ITYPE .EQ. 2) GAIN = ENDF (PHASE * SECTOR) 89 IF (ITYPE .EQ. 1) GAIN = RECT (PHASE * SECTOR) 90 POW(I,IS) = GAIN * POWER 91 SHIFT = SHIFT + SECSEP 92 TPOW(IS) o TPOW(IS) + POW(I,IS) 93 20 continue 94 C selecting NR highest power antennas 95 CALL SELECT (NS, NR, TPOW, K) 96 CALL ICCN (POW(l,K(NS) ) , TPOW(K(NS)), C, I, LOC(NS), ICN, mcap) 97 ISUCC (I) = ICN 98 DO 40 J = 2,NR 99 J J «• NS - J + 1 100 CALL ICCN (POW(l,K(JJ)), TPOW(K(JJ)), C, I, LOC (JJ) , ICN, mcap) 101 DO 30 J2 = 2 ,J 102 IF (LOC(JJ) .EQ. LOC (JJ+J2-1) ) GOTO 40 103 30 continue 104 ISUCC(I) = ISUCC(I) + ICN 105 40 CONTINUE 106 50 CONTINUE 107 108 RETURN 109 END 110 111 112 C This subroutine returns the NR highest power sectors in the last 113 C NR elements of the array K. 114 SUBROUTINE SELECT (NS, NR, TPOW, K) 115 IMPLICIT REAL*8 (A-H,0-Z) 116 DIMENSION K(NS) , TPOW(NS) 117 118 DO 10 I = 1,NS 119 K(I) = I 120 10 continue Appendix F. Simulation Programs Used in Thesis 191 Probability P,|; 121 DO 30 J = 1,NR 122 NSMJ = NS - J 123 DO 20 I = 1,NSMJ 124 IF (TPOW(K(I)) .GT. TPOW(K(I+l) ) ) THEN 125 KSAVE = K(I) 126 K(I) = K(I+1) 127 K(I+1) = KSAVE 128 END IF 129 20 continue 130 30 continue 131 132 RETURN 133 END 134 135 136 C This function returns ICN=1 i f the max power > C*( to ta l power 137 C - max power ), =0 otherwise 138 SUBROUTINE ICCN (P, T, C, I, LARGE, ICN, mcap) 139 IMPLICIT REAL*8 (A-H,0-Z) 140 REAL*8 P(200) 141 142 C search for max power terminal 143 LARGE = 1 144 DO 10 J = 2,1 145 IF (P(J) .GT. P (LARGE) ) LARGE = J 146 10 continue 147 148 i f (mcap .eq. 1) then 149 c search for 2nd largest power terminal (capture model 1) 150 power2 = 0.OdO 151 do 20 j *• 1,1 152 i f (j .eq. large) goto 20 153 i f (p(j) .ge. power2) power2 = p(j) 154 20 continue 155 pnoise = power2 156 else 157 pnoise = t - p(large) 158 endif 159 IF (P(LARGE) .GT. C*pnoise) THEN 160 ICN = 1 161 ELSE 162 ICN = 0 163 c this l ine i s added (Jul 18, 89) to include the p o s s i b i l i t y that this 164 c user "LARGE" may be captured in another selected (non-ideal) antenna 165 large = 0 166 END IF 167 RETURN 168 END 169 170 171 C FUNCTION CMOD 172 FUNCTION CMOD(X) 173 IMPLICIT REAL*8 (A-H,0-Z) 174 CMOD = X 175 10 IF (CMOD . L E . 1.0D0) RETURN 176 CMOD = CMOD - 2.ODO 177 GOTO 10 178 END 179 180 Appendix F. Simulation Programs Used in Thesis 192 Probability P,|,-181 C FUNCTION RECT - IDEAL ANTENNA 182 FUNCTION RECT (X) 183 IMPLICIT REAL*8 (A-H.O-Z) 184 IF (X . L T . -1.0D0 .OR. X .GT. 1.0D0) THEN 185 RECT «• 0.0D0 186 ELSE 187 RECT = 1.0D0 188 END IF 189 RETURN 190 END 191 192 193 C FUNCTION ENDF - SINC-COS ANTENNA 194 FUNCTION ENDF (X) 195 IMPLICIT REAL*8 (A-H,0-Z) 196 Y = X / 2.ODO 197 Z = 11.35D0 * (DCOS(Y) - 1.0D0) 198 ENDF = SINC(Z) ** 2 199 RETURN 200 END 201 202 203 c FUNCTION SIDE - SINC ANTENNA 204 FUNCTION SIDE (X) 205 IMPLICIT REAL*8 (A-H,0-Z) 206 Y = 1.39D0 * X 207 SIDE = SINC(Y) ** 2 208 RETURN 209 END 210 211 212 c FUNCTION SINC 213 FUNCTION SINC (X) 214 IMPLICIT REAL*8 (A-H,0-Z> 215 IF (X .EQ. 0.0D0) THEN 216 SINC = 1.0D0 217 ELSE 218 SINC = (DSIN(X) / X) 219 END IF 220 RETURN 221 END 222 223 224 c FUNCTION USER POWER 225 FUNCTION UPOWER (M, IDIST, rho) 226 c M IS THE ATTN FACTOR 227 c IDIST = 1 FOR UNIFORM, OTHERWISE FOR BELL-SHAPED 228 IMPLICIT REAL*8 (A-H,0-Z) 229 DATA CONST/0.893243841D0/ 230 IF (IDIST .EQ. 1) THEN 231 10 DIST = DSQRT( DRAND(O) ) 232 IF (DIST . L E . rho) GOTO 10 233 else 234 20 DIST = CONST * DSQRT( dabs(RANDN(0)) ) 235 IF (DIST . L E . rho) GOTO 20 236 ENDIF 237 UPOWER = DIST ** (-M) 238 RETURN 239 END 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0065461/manifest

Comment

Related Items