SPREAD-SPECTRUM MULTIPLE ACCESS FOR INTERACTIVE DATA COMMUNICATIONS by VICTOR CHUNG MING LEUNG B.A.Sc , U n i v e r s i t y of B r i t i s h CoIombia s 1977 A THESIS SUBMITTED IN PARTI Al, FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY i n THE FACULTY OF GRADUATE STUDIES Department of E l e c t r i c a l Engineering We accept t h i s t h e s i s as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA December 1981 © V i c t o r Chung Ming Leung„ 1981 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an advanced degree a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e head o f my department o r by h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f E l e c t r i c a l Engineering The U n i v e r s i t y o f B r i t i s h C o l u m b i a 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5 Date J f l i , 3 0 , \C\%Z, ABSTRACT Spread-spectrum multiple access (SSMA) is conceptually attractive for interactive data communications over broadcast channel shared by a large number of potential users. The present thesis Involves a study of asynchronous direct sequence SSMA interactive data communication systems. The study includes a unified analysis and assessment of system delay-throughput performance. Two important message delay components which are affected by the design of the transmitter/receiver pair result from code acquisition and bit-errors. A new code synchronizer design featuring a number of parallel correlators is developed, and an analysis of synchronizer performance as it relates to SSMA applications is provided. It is shown that average acquisition delay decreases in proportion to Increase In the number of correlators when this number is small. Receiver bit-error probability for any given channel occupancy is derived. Three protocols suitable for SSMA transmissions under different oper-ating conditions are proposed. Using one of these protocols, the expected number of transmissions before a message is received error-free is estimated by averaging bit-error probabilities over a postulated channel occupancy proba-bility distribution. This distribution is verified using data obtained from channel simulations. Delay-throughput characteristics of the SSMA system are thus obtained by evaluating the above delays and other exogenous delays at various traffic levels. Results relevant to the given system and traffic models, transmission protocol, and transmitter/receiver structure are obtained assuming that users' i i codes are uncorrelated. Subsequently, i t is shown that the results are easily modified to account for code cross-correlations. Assessment of SSMA delay-throughput performance Is accomplished by com-parisons with pure ALOHA, slotted ALOHA and queueing channels. These compari-sons necessitate extension of existing analysis of slotted ALOHA channels to include the effects of Gaussian channel noise, as well as development of an analysis procedure for noisy pure ALOHA channels. It is shown that in power-limited situations, the capacities of ALOHA and queueing channels can be maxi-mized with respect to the transmission bit rate. Delay-throughput comparisons show that at throughput levels much lower than the capacities of these chan-nels, average delays for SSMA are higher than those of the other channels. However, capacities of SSMA channels are generally higher than those of the other channels, which occupy only a fraction of the available bandwidth at power levels favourable to SSMA. In such cases, the throughput which results for a given delay clearly favours SSMA. Comparisons are also performed with respect to m-parallel ALOHA or queue-ing channels, where ra is the number of channels accommodated by the available bandwidth. In this case the capacities of SSMA channels are generally less than those of m-parallel slotted ALOHA or queueing channels, but approximately equal to those of m-parallel pure ALOHA channels. Therefore, SSMA presents a viable alternative to m-parallel pure ALOHA multiple access for interactive data communications. SSMA is especially favourable for transmissions of long messages In a wide-band broadcast channel with limited power. i i i TABLE OF CONTENTS Page 1. INTRODUCTION 1 1.1 Motivation and Objectives 1 1.2 Spread-Spectrum Multiple Access 2 1.3 Review of Previous Work 5 1.4 Outline of the Thesis 9 2. SYSTEM MODEL 12 2.1 Structure of the Transmitter and Receiver 12 2.2 Multiple Access Channel Model 14 2.3 Bit-Error Probability at the Receiver Output 18 2.3.1 Derivations 18 2.3.2 Numerical Examples 22 3. SPREAD-SPECTRUM CODE SYNCHRONIZATION 26 3.1 Introduction 26 3.2 Structure of the Code Synchronizer 27 3.3 The Synchronization Detector 29 3.3.1 Description 29 3.3.2 Probability Density of Correlator Outputs 30 3.3.3 Probabilities Attributed to Synchronization Detector Decisions 38 3.4 The Search/Lock Strategy 39 3.4.1 The SLS Logic 39 3.4.2 Mean and Mean-Squared Dwell Time 45 3.4.3 Mean and Mean-Squared Time to Lock 50 3.4.4 Probability of Entering Lock Mode with the Correct Cell 51 3.5 Acquisition Time 53 3.5.1 Mean Acquisition Time 53 3.5.2 Acquisition Time Variance 55 3.5.3 Acquisition Time Confidence Estimates 58 3.6 Hold-In Time 59 3.6.1 Mean and Variance of Hold-In Time 59 3.6.2 Approximation of Hold-In Time Probability Distribution 61 3.7 Numerical Examples 63 iv Page 4. SSMA SYSTEM PERFORMANCE 90 4.1 Traffic Model . 90 4.2 Protocols for SSMA Signal Transmission 91 4.3 Delay-Throughput Analysis for Protocol B 97 4.3.1 Effects of PNR and Delay Components on Total Delay . . . 97 4.3.2 Delay as Functions of Average Channel Occupancy . . . . 100 4.3.3 Channel Stability 104 4.3.4 Delay-Throughput Characteristics and Channel Capacity 110 5. COMPARISON WITH OTHER MULTIPLE ACCESS TECHNIQUES 120 5.1 Introduction 120 5.2 Delay-Throughput Characteristics of a Slotted ALOHA Channel with Additive Gaussian Noise 122 5.3 Delay-Throughput Characteristics of a Pure ALOHA Channel with Additive Gaussian Noise 133 5.4 Delay-Throughput Characteristics of a Queueing Channel with Additive Gaussian Noise 155 5.5 Comparison of Delay-Throughput Characteristics Between SSMA, Pure ALOHA, Slotted ALOHA and Oueueing Channels 163 6. CONCLUSION 174 6.1 Summary of Results 174 6.2 Suggestions for Further Work 176 6.2.1 Enhancement of Receiver Performance Through Interference Cancellation 177 6.2.2 Different Power Levels for Acquisition and Message Transmission 177 6.2.3 Effect of Various Modulation Schemes on Direct Sequence SSMA Performance 178 6.2.4 Extension of Results to Other Spread-Spectrum Techniques 178 6.2.5 Extension of Results to Fully Connected Network . . . . 178 6.2.6 Exploration of New Coding Schemes 179 6.2.7 Extension of Results to Non-Gaussian Channels 179 6.2.8 Application of Decision Feedback to Improve Channel Stability 179 v Page REFERENCES 180 Appendix 1. D e r i v a t i o n of Equation (2.3.6) 185 Appendix 2. D e r i v a t i o n of Equation (2.3.11) 188 Appendix 3. GPSS Program f o r Channel Simulation 193 Appendix 4. Goodness-of-Fit Tests . . . 195 v i LIST OF TABLES Table Page 2.3.1 SSMA s i g n a l parameters 22 3.6.1 Percent d e v i a t i o n <5 of a c t u a l and e x p o n e n t i a l l y approximated h o l d - i n time cumulative d i s t r i b u t i o n . . 64 3.7.1 Spread-spectrum code synchronizer parameters' 65 5.2.1 Optimum values of b i t r a t e R and corresponding maximum channel c a p a c i t y C f o r s l o t t e d ALOHA channel w i t h a d d i t i v e Gaussian noise 132 5.3.1 Optimum values of b i t r a t e R and corresponding maximum channel c a p a c i t y C f o r pure ALOHA channel w i t h a d d i t i v e Gaussian noise 155 5.4.1 Optimum values of b i t r a t e R and corresponding maximum channel c a p a c i t y C f o r M/D/l queueing channel w i t h a d d i t i v e Gaussuan noise 162 v i i LIST OF ILLUSTRATIONS Figure Page 2.1.1 Direct sequence spread-spectrum transmitter/receiver pair 13 2.2.1 Model of SSMA channel and i t s sources and sinks . . . 15 2.3.1 B i t - e r r o r p r o b a b i l i t y p vs. number of a c t i v e users M for various PNR values, co-channel i n t e r f e r e r s modelled as Gaussian noise sources 24 2.3.2 ; B i t - e r r o r p r o b a b i l i t y upper bound vs. number of a c t i v e users M for various PNR values, showing the e f f e c t s of c r o s s - c o r r e l a t i o n s between 511-bit Gold's codes . . . 25 3.2.1 Direct sequence spread-spectrum code synchronizer . . 28 3.3.1 One of K envelope c o r r e l a t o r s in code synchronizer . 31 3.4.1 The search/lock strategy l o g i c 41 3.4.2 Markov chain model of SLS given that one of the K c e l l s being tested i s in synchronization (event Y). . 43 3.4.3 Markov chain model of SLS given that none of the K c e l l s being tested are i n synchronization (event Y) . 44 3.7.1 False alarm p r o b a b i l i t y p vs. d e c i s i o n threshold V- i n the search mode 67 3.7.2 False alarm p r o b a b i l i t y p vs. d e c i s i o n threshold V in the l o c k mode 68 3.7.3 Mean a c q u i s i t i o n time vs. number of a c t i v e users M for various V g values with PNR = 50.0 dB-Hz 69 3.7.4 Mean a c q u i s i t i o n time vs. number of a c t i v e users M for various V_ values with PNR = 70.0 dB-Hz 70 v i i i Figure Page 3.7.5 A c q u i s i t i o n time standard d e v i a t i o n v s . number of a c t i v e users M f o r v a r i o u s v g values w i t h PNR = 70.0 dB-Hz 71 3.7.6 Mean a c q u i s i t i o n time v s . number of a c t i v e users M f o r v a r i o u s PNR values 72 3.7.7 A c q u i s i t i o n time standard d e v i a t i o n v s . number of a c t i v e users M f o r v a r i o u s PNR values . . . . . . . . 73 3.7.8 Mean a c q u i s i t i o n time v s . number of a c t i v e users M f o r v a r i o u s K values w i t h PNR =50.0 dB-Hg 75 3.7.9 Mean a c q u i s i t i o n time v s . number of a c t i v e users M f o r v a r i o u s K values w i t h PNR = 70.0 dB-H z 76 3.7.10 A c q u i s i t i o n time standard d e v i a t i o n v s . number of a c t i v e users M f o r v a r i o u s K values w i t h PNR =70.0 dB-Hz 77 3.7.11 Reduction of minimum mean a c q u i s i t i o n time f o r v a r i o u s K values as f r a c t i o n of minimum mean a c q u i s i t i o n time f o r K = 1 78 3.7.12 Upper bound f o r 90% confident a c q u i s i t i o n time v s . number of a c t i v e users M 79 3.7.13 Upper bound f o r 99.9% confident a c q u i s i t i o n time v s . number of a c t i v e users M 80 3.7.14 Upper bound f o r 99.999% confident a c q u i s i t i o n time v s . number of a c t i v e users M 81 3.7.15 Mean h o l d - i n time v s . number of a c t i v e users M f o r v a r i o u s V .values 83 Li " 3.7.16 Mean h o l d - i n time v s . number of a c t i v e users M f o r va r i o u s PNR values w i t h K = 4 84 i x Figure Page 3.7.17 Hold-in time standard deviation vs. number of act i v e , ' ; users M for various PNR values with K.= 4 85 3.7.18 Mean hold-in time vs. number of a c t i v e users M for various PNR values with K = 32 86 3.7.19 Hold-in time standard deviation vs. number of act i v e users M for various PNR values with K = 32 87 3.7.20 Mean hold-in time vs. number of a c t i v e users M for various K values 88 3.7.21 Hold-in time standard deviation vs. number of act i v e users M for various K values 89 4.2.1 Three, protocols f o r SSMA signal transmission 93 4.3.1 Mean channel occupation time T^Q vs. number of act i v e users M for various PNR values 99 4.3.2 Comparison of contributions of and T M/P C to T ^ at d i f f e r e n t l e v e l s of channel oc,cupancy 101 4.3.3 Mean channel-occupation time T vs. average number of ac t i v e users M for various message lengths l 105 4.3.4 E f f e c t of increasing K on mean channel occupation t J m e TC0 . . . . 106 4.3.5 Graphical solutions of L i t t l e ' s formula as applied to the SSMA channel for three d i f f e r e n t cases of X values 108 4.3.6 C r i t i c a l values of a r r i v a l rate X vs. message length I, with PNR = 60.0 dB-Hz . . . .' " I l l 4.3.7 C r i t i c a l values of a r r i v a l rate X vs. message length I, with PNR = 70.0 dB-Hz, . . . . ^ 112 x Figure Page 4.3.8 SSMA delay-vs.-throughput curves f o r v a r i o u s message lengths w i t h PNR = 60.0 dB-Hz and (a) K = 1, (b) K = 4 114 4.3.9 SSMA delay-vs.-throughput curves f o r v a r i o u s message lengths w i t h PNR =70.0 dB-Hz, and (a) K = 1, (b) K = 4 115 /•• 4.3.10 SSMA channel c a p a c i t y C v s . message l e n g t h I, w i t h PNR = 60.0 dB-Hz 117 4.3.11 SSMA channel c a p a c i t y C v s . message l e n g t h I, w i t h PNR =70.0 dB-Hz 118 5.2.1 A t y p i c a l set of s l o t t e d ALOHA delay-vs.-throughput curves showing e f f e c t s of d i f f e r e n t maximum ret r a n s m i s s i o n delays i n K s l o t s 127 5.2.2 E f f e c t s of d i f f e r e n t b i t r a t e s R on s l o t t e d ALOHA delay-vs.-throughput curves optimized over K w i t h PNR = 60.0 dB-Hz; and (a) £ = 1024 b i t s , (b). I = 2048 b i t s , (c) I = 8192 b i t s 129 5.2.3 E f f e c t s of d i f f e r e n t b i t r a t e s R on s l o t t e d ALOHA delay-vs.-throughput curves optimized over K w i t h PNR =70.0 dB-Hz•: and (a) I = 1024 b i t s , (b) I = 2048 b i t s , (c) I = 8192 b i t s 130 5.2.4 S l o t t e d ALOHA delay-vs.-throughput curves f o r d i f f e r e n t message lengths £, optimized over K and R, w i t h (a) PNR = 60.0 dB-Hz, (b) PNR = 70.0 dB-Hz . . . 131 5.3.1 Comparison between the time p e r i o d i n which r e t r a n s m i s s i o n of a packet, p r e v i o u s l y blocked at time t , may begin and the v u l n e r a b l e period of a new tra n s m i s s i o n at time t ^ . The extent of overlapping of the two time periods i s p r o p o r t i o n a l to the p r o b a b i l i t y that the two packets c o l l i d e 136 5.3.2 {-In p ( t ) } / A t v s . t ; p(t) i s the p r o b a b i l i t y that events occuring i n the time i n t e r v a l ( t , t+At) do not cause a r e t r a n s m i s s i o n w i t h i n the vulnerable^ period of a packet t r a n s m i t t e d at time t n 138 x i Figure Page 5.3.3 G r a p h i c a l e v a l u a t i o n of - l n { P r ( E |E )} 142 5.3.4 Graphical e v a l u a t i o n of - l n { P r ( E 3 | E ^ } 143 5.3.5 A t y p i c a l set of pure ALOHA delay-vs.-throughput curves showing e f f e c t s of d i f f e r e n t maximum re t r a n s m i s s i o n delays i n KT sec 150 m 5.3.6 E f f e c t s of d i f f e r e n t b i t r a t e s R on pure ALOHA del a y -vs .-throughput curves optimized over K w i t h PNR = 60.0 dB-Hz and (a) I =1024 b i t s , (b) JI = 2048 b i t s , (c) I = 8192 b i t s 152 5.3.7 E f f e c t s of d i f f e r e n t b i t r a t e s R on pure ALOHA delay-vs.-throughput curves optimized over K w i t h PNR = 70.0 dB-Hz and (a) I = 1024 b i t s , (b) & = 2048 b i t s , (c) H = 8192 b i t s 153 5.3.8 Pure ALOHA delay-vs.-throughput curves f o r d i f f e r e n t message lengths I, optimized over K and R, w i t h (a) PNR = 60.0 dB-Hz",', (b) PNR =70.0 dB-Hz 154 5.4.1 E f f e c t s of d i f f e r e n t b i t r a t e s R on M/D/l queueing delay-vs.-throughput curves w i t h PNR = 60.0 dB-Hz and (a) £ = 1024 b i t s , (b) I = 2048 b i t s , (c) % = 8192 b i t s 159 5.4.2 E f f e c t s of d i f f e r e n t b i t r a t e s R on M/D/l queueing delay-vs.-throughput curves w i t h PNR = 70.0 dB-Hz and (a) I = 1024 b i t s , (b) I = 2048 b i t s , (c) I = 8192 b i t s 160 5.4.3 M/D/l queueing delay-vs.-throughput curves f o r d i f f e r e n t message lengths I, w i t h (a) PNR = 60.0 dB-Hz, (b) PNR = 70.0 dB-Hz 161 5.5.1, Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, s l o t t e d ALOHA and queueing w i t h PNR = 60.0 dB-Hz. and JI = 1024 b i t s 164 5.5.2 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, s l o t t e d ALOHA and queueing w i t h PNR = 60.0 dB-Hz and SL = 2048 b i t s 165 x i i Figure Page 5.5.3 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, s l o t t e d ALOHA and queueing w i t h PNR = 60.0 dB-Hz and £ '= 8192 b i t s 166 5.5.4 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, s l o t t e d ALOHA and queueing w i t h PNR = 70.0 dB-Hz. and £ = 1024 b i t s ........... 167 5.5.5 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, s l o t t e d ALOHA and queueing w i t h PNR =70.0 dB-Hz and £ = 2048 b i t s 168 5.5.6 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, s l o t t e d ALOHA and queueing w i t h PNR = 70.0 dB-Hz and £ = 8192 b i t s 169 x i i i ACKNOWLEDGEMENT I am deeply g r a t e f u l to my research s u p e r v i s o r , Dr. R.W. Donaldson, f o r h i s encouragement and many h e l p f u l suggestions during the course of t h i s t h e s i s . G r a t e f u l acknowledgement i s extended to the N a t u r a l Sciences and Engineering Research Council f o r f i n a n c i a l support r e c e i v e d under the Postgraduate Schol a r s h i p s Program, and to the N a t i o n a l Research Council f o r support under Grant NRC A-3308. S p e c i a l thanks are a l s o extended to Mr. A. Mackenzie f o r h i s t e c h n i c a l a s s i s t a n c e and to Mrs. Kathy Brindamour f o r t y p i n g the manuscript. F i n a l l y , I am t h a n k f u l to my parents and s i s t e r s f o r t h e i r patience and encouragement. x i v 1 1. INTRODUCTION 1.1 Motivation and Objectives Advances in digital technology have led to growing interest in interactive data communications for a variety of applications including data base updating and retrieval, electronic funds transfer, electronic mail, interactive distance education, placing of reservations for travel, accommodation and entertainment, point of sale information processing, and remote monitoring of property and equipment. Communication nodes include homes, business establishments, data storage locations, educational institutions and mobile transceivers. These applications motivate the use of readily available broadcast communication facilities such as satellite links, cable networks and radio networks for wide-band point-to-point and multipoint interactive data communications. Pseudonoise (PN)-coded spread-spectrum multiple access (SSMA) communica-tion systems enable a large number of users to share a common broadcast channel. Although SSMA receiver performance in terms of bit-error probability has been determined by others, system development has been impeded by the lack of comprehensive evaluations of overall system performance. The primary ob-jective of this thesis is performance evaluation for PN-coded direct sequence SSMA interactive data communication systems. An important measure of interactive data communication system performance is the delay-throughput characteristic. System throughput is the amount of information transferred from al l sources to destinations per unit time. It is a function of the total traffic generated, an entity not within control of the system. However, the feasible level of system throughput is constrained by the 2 acceptability of the corresponding message delay. Therefore throughput is treated as an independent variable for the evaluation of message delay, where delay is the elapsed time between the input of a message from its source to the system and the correct reception of the entire message at its destination. For interactive data communications, short message delays are desirable, especially when human interaction is involved. Message delays averaging two to three seconds with standard deviations of one to two seconds are considered acceptable [Ml, Rl]. In SSMA communications, PN-code synchronization is a primary cause of delay. In this thesis a code synchronizer suitable for direct sequence SSMA applications is introduced and its acquisition time and hold-in time statistics are obtained. System and data traffic models as well as appropriate signal transmission protocols are established to facilitate delay-throughput analysis in relation to synchronization delay, bit-error probability and message length. Delay-throughput characteristics for other multiple accessing schemes including pure ALOHA, slotted ALOHA and queueing are obtained, and are used for comparison purposes. The effects of transmission errors caused by random noise as well as "collisions" are included in the analysis. 1.2 Spread-Spectrum Multiple Access Spread-spectrum techniques [D1,D2] are employed in communications, ranging, direction finding and position location. Spreading of the signal spectrum may be achieved by direct multiplication of the signal with a code sequence at a high clock rate (direct sequence technique) or by varying the carrier frequency in a time-coded fashion (frequency hopping technique). 3 Combinations of the two techniques and other techniques may also be used. The received signal is de-spread by application of the spreading technique in reverse so that the desired information is restored to its original bandwidth while uncorrelated noise and interference remain spread to the transmission bandwidth. Thus, a spread-spectrum gain results when filtering extracts the information and rejects most of the noise and interference. Advantages of spread spectrum communications are as follows: 1. Spectrum spreading enhances the signal to noise ratio of the de-spread signal in the presence of noise and co-channel jamming and thereby reduces the transmitter power required. 2. Because spread-spectrum signals have wideband spectra with low spectral densities which are noise-like when PN codes are used, they are less susceptible to eavesdropping. Furthermore, an intercepted signal cannot be decoded without knowledge of the spread-spectrum code, although codes that are not cryptographically safe may be reconstructed using suitable processing techniques. 3. The inherent frequency diversity of spectrum spreading effectively combats passive Interference such as fading, multipath and intersymbol inter-ference . The inherent attractiveness of SSMA as a means of point-to-point communication on broadcast channels is a direct consequence of the above features. Thus the channel is shared by a number of users, each of which is assigned a unique code sequence chosen from a set of codes with low mutual cross-correlations. As a result, the signal transmitted by each user appears 4 as noise to a l l other users, and each user sees himself as the only occupant of a noisy channel. Further to advantages cited above, SSMA possesses the follow-ing advantages: 4. Compared with other multiple accessing schemes, SSMA does not require universal timing as in time division multiple access and a l l slotted con-tention multiple accessing schemes, or frequency guard-bands as in fre-quency division multiple access. Users may transmit at any time using the entire bandwidth available to the system, and collision with other users does not necessitate retransmission as in ALOHA and carrier-sense multiple access. 5. Because of low spectral densities and noise-like spectra of SSMA signals, co-existence of SSMA with other services in the same channel is possible, with only a slight degradation to all received signals. It is therefore feasible to phase in SSMA over a period of time to replace existing services. 6. Hardware for a l l users is standardized and could benefit from large scale integration with sufficient demand. The PN-code generator is easily realized by a shift register with feedback connections determined by the user's code. 7. Priority messages can be accommodated by simply increasing the transmitter power, or by other means. 5 Potential disadvantages of SSMA communications are as follows: 1. Large channel bandwidth, which is often scarce and costly, is needed. However sharing of the channel among a number of users considerably re-duces this potential disadvantage, particularly when the user traffic is bursty. In this case the law of large number applies to average and smooth the demand placed on the channel, with a small subset of the totality of potential users actually occupying the channel at any instant. 2. Spread-spectrum receivers are somewhat more complex than those used in other multiplexing schemes. However, continued decreases in costs of digital electronics largely obviate this problem. 3. Some form of power control may be required in some applications where received power from different users varies in accordance with transmitter-receiver distance separation; for example on a cable network. In such cases an indirect form of- power control would involve limiting the network to a star configuration. The ultimate question is this: "How does the efficiency of SSMA compare with that of other multiplexing schemes for point-to-point communication on broadcast channels?" This thesis deals with this question. 1.3 Review of Previous Work Although the basic principles of spread-spectrum systems have been known for many years, most of the early development was done in the military domain because implementation was costly. In the late 1960's advances in satellite technology attracted much interest in multiple accessing the satellite channel. Schwartz et al. [SI] analysed several modulation techniques, including spread-6 spectrum, for multiple access to satellite repeaters. Aein [Al] derived the optimum bandwidth and the resulting maximum number of simultaneous users for SSMA to a hard-limiting satellite repeater. Anderson and Wintz [A2] analysed a SSMA system with a hard limiter by computing the signal to noise ratio at the output of a correlation detector. The analysis included the effects of cross-correlations of the PN codes. Advances in digital computer technologies since the 1970's has led to growing demand for interactive data communications. Advantages in sharing computer and communication resources [Kl, K2] have spawned schemes for packet transmission over broadcast channels, including ALOHA [K3, LI, CI], carrier sense and busy tone [K4, TI] multiple access, and polling [T2]. Analysis has centered on the delay-throughput characteristics of these schemes. However, delay-throughput analysis for SSMA is lacking. Spread-spectrum transceiver hardware such as megabits-per-second code generators [D5], surface acoustic wave devices [Gl] and digital correlators [El] are becoming available as digital technologies advance. As a result, there is growing interest in spread-spectrum for data communications. Signal to noise ratio and bit-error probability of SSMA receivers were analysed by Pursley [PI] and Yao [Yl]. The effects of code sequence parameters were further considered by Pursley and Sarwate [P2]. While these authors assumed equal power for a l l co-channel users at the receiving site, the effects of geographical distribution of users were considered by Musa and Wasylkiwskyj [M2]. The proper operation of a SSMA communication system depends on the assign-ment of codes with low mutual cross-correlations to the system users. For 7 direct sequence applications, Gold [Gl] presented a method of generating a large number of non-pseudonoise codes with bounded cross-correlations from a pair of PN codes, and Anderson [A3] described a strategy of selecting a subset of PN codes with bounded cross-correlations from the set of a l l PN codes which have identical lengths. For frequency hopping applications, the formulation of optimal frequency hopping sequences for SSMA was investigated by Solomon [S2], and the design of a time-frequency coded signal set with low cross-correlations was presented by Yates and Cooper [Y2], The delay characteristics of a SSMA communication system are related closely to the spread-spectrum code acquisition time if code synchronizers are used. When the received signal frequency and the receiver's environmental temperature are stable, information can be extracted using a matched fi l t e r for the intended code sequence and code acquisition is not necessary. Matched filt e r receivers are usually implemented using surface acoustic wave (SAW) or charge coupled (CCD) devices [Bl,B2,V2,M3]. SAW devices are only applicable for short code lengths (less than 200 chips) because of physical limitations on length of delay line, resolution of taps, and signal attenuation. Performance of SAW filters deteriorates when signal frequency or environmental temperature fluctuates. CCD filters are only useful for code rates of 5 MHz or less, and are also subjected to attenuation problems for long code lengths. SAW and CCD filters are expensive because they are not currently mass-produced. For SSMA applications, other methods of demodulation, usually involving the use of a code synchronizer, are normally more appropriate and less expensive. A code synchronizer generally performs two tasks, acquisition and track-ing. The acquisition process brings the receiver generated code in phase with 8 the received code. The tracking process then keeps the codes in phase. Delay-lock loops [S3] or dithering loops [HI] are usually used for tracking. Various methods of code acquisition have been proposed. Sequential estimation [W1,K5,W2] achieves rapid acquisition by initializing the receiver's code generator with an estimate of the received code. Because this estimate is made without the benefit of spread-spectrum gain, i t is unreliable when a number of coded signals are present. Therefore sequential estimation is unsuitable for SSMA applications. Another method of acquisition uses the sliding correlator [Dl] whereby the phases of the local code and received code slide past each other until a match occurs. Analysis of various forms of sliding correlators was offered by Sage [S4], Holmes and Chen [H2] and Hopkins [H3], These cor-relators are well suited for SSMA applications, although acquisition time is quite long. Hopkins' synchronizer is particularly Interesting because both acquisition and tracking are treated in a unified manner and the eventuality of losing lock is also taken into consideration. It appears that acquisition time and hold-in time performance of code synchronizers in SSMA data communication systems has not been investigated in the literature. The application of SSMA in a cellular mobile radio system has recently been investigated by Cooper, Nettleton and Grybos [C2,C3,N1,N2,N3,G3]. Their suggestion that SSMA is spectrally more efficient than conventional narrow band FM techniques for cellular mobile radio service has been a subject of dispute [H4]. Applications of spread-spectrum techniques to enhance the performance of ALOHA-type contention multiplexing schemes in packet radio networks were des-cribed by Kahn et al. [K6]. The throughput-delay characteristics of a system 9 which employs SSMA to reduce the message-obliterating effect of collisions in slotted ALOHA multiple access were recently analysed by Raychaudhiru [R2]. In this analysis, perfect code-synchronization between transmitter/receiver pairs and perfect block-synchronization among system users were assumed. Use of SSMA for interactive data communications involving a large user population is new, and comprehensive results on performance analysis and optimization of such systems are unavailable. In particular, analysis in synchronizer performance and delay-throughput characteristics for asynchronous SSMA communication systems is lacking. 1.4 Outline of the Thesis In Chapter 2 models for a spread-spectrum transmitter/receiver pair and the multiple access channel are specified. The bit-error probability at the receiver output is derived for the case where co-channel interferers are model-led as Gaussian white noise. An upper bound for the bit-error probability is also obtained by taking into consideration the maximum cross-correlation between the code sequences. A numerical example using a specific set of system parameters is presented. A code synchronizer employing a number of sliding correlators working in parallel is presented in Chapter 3. In addition to having the advantages of Hopkins' synchronizer [H3] cited earlier, the design of this synchronizer reduces the mean and standard deviation of acquisition time in proportion to the number of parallel correlators used. In the special case where the number of parallel correlators equals one, this synchronizer reduces to the one pro-posed by Hopkins. The means and variances of acquisition time and hold-in time 10 are derived. An acquisition time confidence estimate is obtained using Chebyshev's inequality. It is also demonstrated that the hold-in time prob-ability distribution is approximately exponential. Finally, to show the effect of some synchronizer and system parameters on acquisition time and hold-in time, a number of graphs are presented using a set of fixed synchronizer para-meters and the system parameters specified in Chapter 2. The overall SSMA data communication system performance is considered in Chapter 4. Protocols suitable for SSMA signal transmission under different conditions of propagation delay and acknowledgement delay in relation to acquisition time and message duration are described. Average message delays are derived for these protocols. A probability distribution for the number of active users is approximated using simulation techniques. Delay-versus-throughput curves are obtained for different message lengths using results from Chapters 2 and 3. It is shown that the SSMA channel is subjected to insta-bility when it is operating near capacity. This property is common to other forms of contention multiple access. In Chapter 5, delay-throughput characteristics are derived for pure ALOHA and slotted ALOHA channels where retransmissions are caused not only by collisions but also by random errors resulting from channel noise. Considera-tion of the effects of random errors is essential for proper system performance comparisons. It is shown that the capacities of these channels can be maxi-mized at some optimum data rates under conditions of fixed power and unlimited bandwidth. The same analysis is repeated for a M/D/l queueing channel. Comparison between delay-throughput characteristics of SSMA, pure ALOHA, slotted ALOHA and queueing channels shows that SSMA is quite favorable, especially in limited power, wide-bandwidth-available situations. Chapter 6 concludes the thesis with a summary of the results and some suggestions for further research. 12 2. SYSTEM MODEL 2.1 Structure of the Transmitter and Receiver Simplified block diagrams of a direct sequence spread-spectrum trans-mitter/receiver pair are shown in Fig. 2.1.1. The signals indicated are those used for and resulting from the modulation and demodulation of a message sequence generated by a typical (i-th) user of the channel. The transmitted signal s^(t) is formed by biphase-modulating a sinusoidal carrier of angular frequency u c and average power P by a binary sequence which is a product of the message (information) sequence m^(t) and the code sequence c^(t) assigned to the i-th user. That is, s.(t) = /2P m.(t) c,(t) cos (co t + 6.) (2.1.1) i l i c l where 6^ is a random time invariant phase angle, uniformly distributed between 0 and 2TT. Both binary sequences m^(t) and c^(t) consist of unit amplitude, positive and negative rectangular pulses. The pulse duration T^ of m^(t) is assumed to be related to the pulse duration T c and period (length) L of Cj,(t) by T v = L • T (2.1.2) b c The modulation process thus spreads the information bandwidth B^ in the base-band to a much wider transmission bandwidth Bfc in the passband. These band-widths are related to the pulse durations by B = 1/T. (2.1.3) m b = 2/T (2.1.4) t c 13 S : ( t ) \/2Pcos(co ct+ej) CARRIER GENERATOR (a) TRANSMITTER r ( t ) LOW PASS FILTER B.W. = B m dt t = Tu DECISION mj(t ) DEVICE Cj(t*t; ) CODE GENERATOR y 2 c o s ( c o c ( t + T j ) + 9 j ) CARRIER GENERATOR CODE SYNCHRONIZER CARRIER SYNCHRONIZER (b) R E C E I V E R F i g . 2.1.1 D i r e c t sequence spread-spectrum t r a n s m i t t e r / r e c e i v e r p a i r . 14 The receiver correlates the received signal r(t) with a locally generated signal which is a product of a replica of c^(t) and a sinusoid phase-coherent with the carrier of s^(t). This process restores the desired information to its baseband bandwidth B and rejects most of the interference and noise power m which has a baseband bandwidth greater than B^/2. The resulting signal a^(t) is sampled at the information bit rate. A decision device then reconstructs an estimate m^(t) of the message sequence from the samples. Successful demodula-tion of the desired information requires that synchronization with s^(t) be established at the code word, code bit (chip) and carrier levels. 2.2 Multiple Access Channel Model Consider M active users simultaneously accessing a SSMA channel. The SSMA channel and its signal sources and sinks are shown in Fig. 2.2.1. The sources and sinks consist of M matching transmitter/receiver pairs as described in Section 2.1. The output of each transmitter is subjected to an independent random delay x uniformly distributed between 0 and T^ which accounts for the asynchronous nature of the M signals. Assuming that the SSMA channel is a linear Gaussian noise channel with zero attenuation, all receivers therefore receive a composite signal r(t) = s(t) + n(t) (2.2.1) where M s(t) = I s (t-x.) (2.2.2) i=l and n(t) is the channel noise generated by a white Gaussian process with two-m«(t) m 2(t) m M ( t ) . TRANSMITTER Nol S , ( t ) DELAY TRANSMITTER No2 So( t ) DELAY X 2 TRANSMITTER NoM s M ( t ) DELAY X M s(t)gy_(t) n(t) RECEIVER No1 m^t) RECEIVER No 2 m 2(t) RECEIVER No M |mM(t) SOURCES SSMA CHANNEL SINKS Fig. 2.2.1 Model of SSMA channel and i t s sources and sinks. 16 side spectral density NQ/2. In eqn. (2.2.2), s^(t) is given by eqn. (2.1.1). Each of the M signals presents an equal average power P to a l l receivers. A single user power to (single-sided) noise-density ratio (PNR) at the input to the receivers can be defined as PNR = P/NQ (2.2.3) The above channel model is applicable to a centralized network where the user population communicates only with a fixed central node over a common Gaussian noise channel. Located at the central node is one receiver for each potential user. With suitable controls, signal power contributed by each active user can be maintained constant at all receivers. Such a network may b realized through the use of: (i) a satellite transponder not driven to saturation, with a single earth station as the central node; (ii) a satellite which acts as the central node itself, that is, a l l receivers are on board the satellite; ( i i i ) a coaxial cable linking a l l users to the central node; (iv) a radio network, with a l l users as well as central node stationary. With some modifications, the channel model is also applicable to other SSMA channels such as VHF and UHF mobile radio channels. In many multiple access applications, direct user-to-user communication i desirable, and the resulting network configuration is fully connected. Appli-cation of SSMA to this network configuration is hindered by two major problems power control and contention. 17 Geographical dispersion of receiving sites in a connected network results in difficulties in controlling transmitter power to enable a l l users to present equal signal power to a l l other users. If it is only required that received power from all other users be constant at a user's receiving site, but that this power may vary from one receiving site to another, then a central trans-ponder may be used to equalize the path attenuation between any one user and all other remaining users. In this case the power control requirement is the same as that of a centralized network, with the transponder replacing the cen-tral node. The network remains fully connected because the transponder retransmits a l l received signals without demodulating them. However, trans-ponding doubles the transmission bandwidth requirement. The contention problem is caused by the desirability of minimizing the number of receivers at user's site. Contention is not a problem if each userv has as many receivers as there are other users, in which case the total number of receivers required for an n-user population is n(n-l), a very large number if n is large. If each user has only one receiver, then the total number of receivers is reduced to n, a much smaller number. However, in this case con-tention arises when two or more users try to communicate with another user at the same time. Contention generally lowers the performance of the SSMA chan-nel, but analysis is probably very difficult because the time that each user spends in the channel is not constant. An additional problem that accompanies contention is addressing. When there is one receiver per user, the best addressing scheme is to assign to each receiver a unique code which every transmitter incorporates into its transmission to that receiver. Alternative-ly, if each user is assigned a unique code for transmission rather than recep-18 tion, then the originating user must, probably through a separate channel, identify himself and request that the destination receiver tune to the correct code sequence. In this case contention in the request channel is possible, as well as contention in the SSMA channel. In this thesis detailed analysis of SSMA performance will be restricted to centralized networks. This problem is itself very important, and our methods and results would be useful in analyzing SSMA performance in networks where contention is involved. 2.3 Bit-Error Probability at the Receiver Output 2.3.1 Derivations Referring to the receiver block diagram shown in Fig. 2.1.1(b), the signal to noise (power) ratio (SNR) of the sampled integrator output a^(T^) for the i-th receiver is (E[a±(T )])2 S N R = Var[a l (T b ) l ( 2 ' 3 ' 1 ) where E[x] and Var[x] denote expected value (mean) and variance of random vari-able x, respectively. The decision device is a two level quantizer which makes a transition when a.(T.) changes sign. If the noise components of a.(T,) are i b l b Gaussian, the bit-error probability p at the output of the decision device is a P B - 0.5 erfc (• SNR ) (2.3.2) where 19 erfc(x) = — f e~ t 2dt (2.3.3) nr x In SSMA communications, the noise components of a.(T,) contributed by co-chan-i b nel interferers are not truly Gaussian. Therefore p as given by eqn. (2.3.2) represents an approximation to the exact p which is too complicated to obtain. a Fortunately, this approximation is usually quite good because the sum of the noise components aproaches a Gaussian distribution as the channel occupancy increases In accordance with the central limit theorem [P3]. It is convenient to distinguish between the noise and signal components of a. (T,). Thus I D ai (V = ai S (V + ai N (V (2.3.4) s N where a^ (T^) is the signal component and a^ (T^) is the noise component. It N s can be shown that a^ (T^) has zero expected value and a^ (T^) has zero g variance. The squared expected value of a.(T.) or a. (T.) is l b I D (E [ a ±(T b ) ] ) 2 = ( E [ a i S ( T b ) ] ) 2 = -lpT b2 (2.3.5) N To calculate the variance of a.(T,) or a. (T,), consider two different cases. I D I D Case 1: Interference from other users of the channel behaves as independent sources of Gaussian noise, each of which has a uniform spectral density P/2Bt over the transmission bandwidth. In this case 1 1 See Appendix 1 for derivation. 20 Var[ a i(T b)] = Var[a ± N(T b)] = 0.9 N^ /B^ (2.3.6) where NQ is the spectral density of noise plus interference from (M-l) other channel users given by ND - T + ^ W 1 ( 2 ' 3 ' 7 ) The SNR is therefore S N R = N B + (M-I)P(B /Bj (2.3.8) o m m t Define the spread-spectrum processing gain G by s s G = B /(2B ) - L (2.3.9) ss t m Thus 2.22 • PNR • G -S N R = (M-l) • PNR + ( 2 ' 3 - 1 0 ) and p may be calculated using eqn. (2.3.2). B Case 2: The cross-correlations between the code sequences assigned to a l l potential users are upper-bounded by the maximum cross correlation \b . In this case 2 max Var [a. N(Tj 1 < (M-lH 2 P/2 + 0.45 N /B (2.3.11) L l b J rmax o m and the SNR is given by 2 See Appendix 2 for derivation. 21 2.22 • PNR • G ss (2.3.12) SNR > 1.11 • (M-l) • Ui 2 • B • B • PNR + B. Tmax t m t Substituting the r i g h t hand side of eqn. (2.3.12) into eqn. (2.3.2), the p thus calculated gives an upper bound to the actual Case 1 i s applicable when the user propulation (UP) i s s u f f i c i e n t l y small that codes with low cross-correlations may be assigned. Mazo [M4] has shown that for UP « d 2/2, where d = 2B tT^, codes may be assigned so that each receiver's b i t - e r r o r p r o b a b i l i t y i s at least as good as that calculated under case 1. If the set of codes i s r e s t r i c t e d to PN codes with length L for ease of generation and good auto-correlation, then case 1 i s applicable only i f UP « L. Selection of a set of codes with low cross-correlations usually involves extensive searching using a d i g i t a l computer. If a large UP i s desired, procedures e x i s t for construction of a large set of codes with higher but bounded cr o s s - c o r r e l a t i o n s , and r e s u l t s obtained under case 2 may be used to bound p . One such procedure was proposed by Gold [G2]. It provides for construction of 2 n+l code sequences of length 2 n - l from a p a i r of PN codes of the same length. The cross-correlations of these sequences are bounded by (n+l)/2 n odd (2.3.13) 'max U2 (n+2)/2 + l ] T ; c n even 22 2.3.2 Numerical Examples A set of signal parameters typical for moderate-speed spread-spectrum data communications is shown in Table 2.3.1. TABLE 2.3.1 SSMA Signal Parameters Information bit rate Information (baseband) bandwidth 1/Tb = 50 KBits/sec. B = 50 KHz m L = 511 chips 1/T = 25.55 MBits/sec. c B = 51.1 MHz t Spread-spectrum code length Spread-spectrum code rate Transmission bandwidth Assuming case 1 is valid, a family of bit-error probability (p_) vs. number of active user (M) curves at different PNR's is shown in Fig. 2.3.1. These curves show that at low PNR's p is insensitive to changes in M because n channel noise predominates over co-channel interference. At moderate to high PNR's, p D increases with M. If M stays constant, p decreases with increasing B Ji PNR but at a decreasing rate so that beyond a certain PNR (about 80 dB-Hz in this case) increase in PNR does not bring about any improvement in p D. This is is because at high PNR's co-channel interference predominates (i.e. (M-l) PNR >> Bfc). Thus eqn. (2.3.10) becomes SNR « 2.22 Ggs/(M-1) and p g is independent of PNR. Using a set of Gold codes [G2] with signal parameters listed in Table 2.3.1 and applying results derived under case 2, bit-error probability upper bounds are plotted against number of active users at different PNR's as shown 23 in Fig. 2.3.2. Except for a compressed horizontal axis, these curves are similar to the ones in Fig. 2.3.1 and the previous observations regarding Fig. 2.3.1 are a l l applicable to Fig. 2.3.2. For Gold codes of length L = 511, \|> = 33T . Since G = L, eqn. (2.3.12) becomes rmax c ss 2.22 • PNR • G S N R > 4.73 . (M-l) • Vm\ Bfc ( 2 - 3 ' 1 4 ) This lower bound on SNR equals the SNR value in eqn. (2.3.10) i f the number of co-channel interferers in eqn. (2.3.10) is multiplied by 4.73. Thus, with uncorrelated user codes (case 1), the SSMA system can accommodate more than four times the number of active users than when Gold codes are used while achieving the same bit-error probability p^. However, Gold codes can support a much higher user population (UP < 513 in this case) than PN codes which satisfy the uncorrelated codes assumption of case 1. 24 PNR IN DB-HZ 0 40 80 120 160 200 N O . Q F A C T I V E U S E R S . M F i g . 2.3.1 B i t - e r r o r p r o b a b i l i t y p v s . number of a c t i v e users M f o r v a r i o u s PNR v a l u e s , co-channel i n t e r f e r e r s modelled as Gaussian noise sources. PNR IN DB-HZ 0 10 20 30 4 0 - 5 0 N O . O F A C T I V E U S E R S . M F i g . 2.3.2 B i t - e r r o r p r o b a b i l i t y upper bound v s . number of a c t i v e user M f o r v a r i o u s PNR v a l u e s , showing the e f f e c t s of c r o s s - c o r r e l a t i o n s between 511-bit Gold's codes. 26 3. SPREAD-SPECTRUM CODE SYNCHRONIZATION 3.1 Introduction Acquisition and tracking of the spread-spectrum code sequence is essential for successful demodulation of the desired signal using the correlation receiver described in Section 2.1. A code synchronizer is employed for these purposes. Code synchronizers incorporating a sliding correlator for acquisition and a delay lock loop for tracking are well suited for SSMA applications. A typi-cal example is Hopkins' synchronizer [H3] which also includes a search/lock strategy (SLS) to arbitrate the transitions between acquisition and tracking. The SLS can be modelled as a finite Markov chain with absorbing boundaries which facilitates analysis of the acquisition time and hold-in time performance of the code synchronizer. Such analysis is important because acquisition time is a major cause of message delay and a long hold-in time is needed to avoid loss of synchronization before transmission of a message is complete. Sliding correlators acquire a code sequence by searching serially through al l code cells 1 to detect the (correct) cell that synchronizes with the desired signal. Acquisition delay results because on the average the correct cell Is located after testing N/2 cells, where N is the total number of code cells. Acquisition delay may be reduced by parallel/serial searches whereby K cells, each displaced from the next by approximately N/K consecutive cells, are simul-1 Code cells are the phases of the code sequence in discreet and equally spaced steps. 27 taneously tested. In this case the correct cell is located after an average of N/(2K) cell-tests. A code synchronizer incorporating a sliding correlator with parallel/-serial searching, a delay lock loop and a SLS is described and analyzed in this chapter. In the special case of K = 1, this synchronizer reduces to the one proposed by Hopkins. This synchronizer is chosen for ease of implementation and analysis, and because its performance seems acceptable for some applica-tions. The synchronizer may not be optimum, however. 3.2 Structure of the Code Synchronizer A block diagram of the code synchronizer is shown in Fig. 3.2.1. The dashed lines divides the blocks into three functional groups: the synchroniza-tion detector, the SLS and the delay lock loop. The heart of the code synchronizer is the local code generator which supplies K code cells to the synchronization detector for testing. It also supplies the appropriate code phases to the delay lock phase detector via a phase selector controlled by the SLS. The phase and frequency of the code generator is coarse-controlled by the synchronization detector via the SLS during acquisition and fine-controlled by the delay lock loop during tracking. The synchronization detector employs K sliding envelope correlators to perform a parallel/serial search during acquisition. The K cells, each dis-placed from the next by approximately N/K consecutive cells, slide past the received code sequence to search for the cell which is the best match to the phase of the received code sequence. The detector detects the maximum output of the K correlators which also exceeds a given threshold and declares the RECEIVED SIGNAL BANDPASS FILTER SQUARE LAW - l ]T d t T •> o / V, i — i i i i J< v 2 BANDPASS FILTER SQUARE LAW 1 BANDPASS FILTER SQUARE LAW Vj= max THRESHOLD DEVICE (V0) t=T SYNCHRONIZATION DETECTOR WITH K ENVELOPE CORRELATORS DELAY LOCK LOOP PN CODE GENERATOR TIMING VOLTAGE CONTROLLED CLOCK PHASE SELECTOR DELAY LOCK PHASE DETECTOR COARSE CONTROL SEARCH CONTROL FINE CONTROL HIT OR MISS SEARCH LOGIC SEARCH /LOCK STRATEGY LOOP FILTER F i g . 3.2.1 D i r e c t sequence spread-spectrum code synchronizer ho 00 29 corresponding c e l l as c o r r e c t (a h i t ) . The SLS uses the i n f o r m a t i o n s u p p l i e d by the s y n c h r o n i z a t i o n de tec to r to c o n t r o l the t r a n s i t i o n s between a c q u i s i t i o n (search) and t r a c k i n g ( l o c k ) modes by means of a l o g i c a l p rocedure . I t a l s o a l t e r s the c o r r e l a t o r i n t e g r a t i o n t ime and d e c i s i o n t h r e s h o l d when a change of mode o c c u r s . When the phase of l o c a l code c l o s e l y matches that of the r e c e i v e d code, the phase d i f f e r e n c e i s detected by the de lay l o c k loop which generates an e r r o r s i g n a l to f i n e - c o n t r o l the phase of the code g e n e r a t o r . As a r e s u l t , the l o c a l code t r a c k s the r e c e i v e d code . D e t a i l e d d i s c u s s i o n s of de lay l o c k loop des ign and o p e r a t i o n [S5] w i l l not be repeated h e r e . I t i s assumed that w i t h proper cho ice of loop f i l t e r parameters the de lay l o c k loop w i l l operate as d e s i r e d . In t h i s case the l o c a l code w i l l l o c k onto the r e c e i v e d code w i t h i n a s u f f i c i e n t l y short t ime a f t e r the a c q u i s i t i o n procedure b r ings the phase d i f f e r e n c e to l e s s than h a l f a c h i p . 3 .3 The S y n c h r o n i z a t i o n Detector 3 . 3 . 1 D e s c r i p t i o n The s y n c h r o n i z a t i o n de tec to r c o n s i s t s of K envelope c o r r e l a t o r s and a d e c i s i o n d e v i c e . Each envelope c o r r e l a t o r m u l t i p l i e s the l o c a l code c o r r e -sponding to a g iven code c e l l to the r e c e i v e d s i g n a l . The product i s then bandpassed to remove most no ise and i n t e r f e r e n c e , squared and lowpassed to e x t r a c t the enve lope , then i n t e g r a t e d f o r T seconds and sampled at the end of the i n t e g r a t i o n p e r i o d . The K c o r r e l a t o r outputs are fed to the d e c i s i o n dev ice c o n s i s t i n g of a maximum s i g n a l e x t r a c t o r and a t h r e s h o l d d e v i c e . The maximum s i g n a l e x t r a c t o r e x t r a c t s the maximum from the K c o r r e l a t o r outputs and 30 identifies the correlator (i-th correlator) corresponding to i t . If the maxi-mum exceeds a given threshold, the decision that the i-th correlator produces a hit is made. If the maximum is less than the threshold, the decision is that al l correlators have missed. The probability density of each correlator output and some probabilities attributed to the synchronization decisions are derived in the following sections. 3.3.2 Probability Density of Correlator Outputs A block diagram of the envelope correlator is shown in Fig. 3.3.1. Each of the K correlators are identical except for the local code sequence fed to the multiplier. The code sequences for the K correlators satisfy the relation that the code cell <J>^ (i = 1,2, •••,K) to be tested by the i-th correlator dif-fers in phase from the cells tested by the adjacent correlators, ,,. ,„ and F Y(i-l)modK d)>. i . \ !„> by IN/KI consecutive cells, where Txl denotes the smallest integer Y(i+l)modK greater than or equal to x. Let x(t) be the signal at the square-law envelope detector input. Expressed in terms of its envelope a(t), its phase angle a and the carrier frequency u>c, x(t) = a(t) cos fw t + a) (3.3.1) c The output of the square law device is kx 2(t) = V 2 ka 2(t) [l + cos [2^ + 2a)] (3.3.2) The low-pass filter rejects the double frequency term to give u(t) = V 2 ka 2(t) (3.3.3) BANDPASS FILTER B.W. = B f x(t) 1 k( ) 2 LOWPASS ' u(t) 1 f T <* 1 FILTER 1 T Jo t = T — L SQUARE LAW ENVELOPE DETECTOR J F i g . 3.3.1 One of K envelope c o r r e l a t o r s i n code synchronizer 32 at the envelope detector output. The bandpass filter output envelope a(t) has a correlation time of l/B^ where is the bandpass filter bandwidth. If a(t) has a random component i t is reasonable to assume that values of a(t) and thus of u(t) when separated by 1/B^ seconds are independent. Let be random variables representing values of u(t) 1/Bj seconds apart. The integration can therefore be approximated by the summation of n = B^ T independent identically distributed random variables IL/B,., k = 1,2, •••,n. Let V. be a random variable representing the i-th sampled integrator output v^T). If n is large, the central limit theorem [P3] is applicable and the probability density function (pdf) of V^, f^ (v^,), is approximately Gaussian. Thus f (v.) = exp i /Til a [ - 7 t ^2 ] < 3 - 3 - 4 ) where mean u and variance a 2 are given by p = (n/T)E[u/Bf] = E[U] (3.3.5) a 2 = (n/T2)Var [U/Bf ] = Var[U]/(Bf-T) (3.3.6) Given that $ is in synchronization (event S) or not in synchronization (event S) with the received signal, two conditional pdf's, f v| g(v|s) and f I —(v|S) can be obtained from the conditional means and variances of U. The V I o subscript i is dropped because the conditional pdf's are identical for a l l correlator outputs. 33 To derive the conditional means and variances of U, consider two d i f f e r e n t cases. Case 1: Assume co-channel i n t e r f e r e r s behave as independent sources of Gaussian noise with uniform two-sided spectral density of P/(2B t) over the transmission bandwidth. From the channel model i n Section 2.2, the t o t a l noise power contributed by (M-l) co-channel i n t e r f e r e r s and the channel noise i n the bandpass f i l t e r bandwidth i s When ^ i s not synchronized with the received code, a(t) i s the noise envelope [Zl] which has a Rayleigh pdf given by N T = N QB f + (M-l)PB f/B t (3.3.7) a a > 0 f A | S ( a l ^ = (3.3.8) 0 a < 0 v. Applying the transformation U = V 2 kA 2 (3.3.9) to eqn. (3.3.8) y i e l d s u 1 u > 0 f u | s ( u , ~ S ) = \ (3.3.10) 0 u < 0 34 which is an exponential pdf with mean E[U|S] = kN (3.3.11) and variance Var[u|S] = (kN ) 2 (3.3.12) When <j>^ synchronizes with the received code, the bandpass fi l t e r output has an additional signal component ±/2P cos (u^t). The envelope a(t) has a Rician pdf given by [Zl] _ (2P+a2) N„ 2N, f A | 8(a|S) = i N„ 0 T _ r/2P a^ ^ n (3.3.13) , a < 0 where I Q( •) is the modified Bessel function of the first kind and zero order. Define the signal-to-noise power ratio in the filter bandwidth as p = P/N, (3.3.14) Define a random variable Z by the transformation Z = A2/(2NT) (3.3.15) Eqn. (3.3.15) transforms eqn. (3.3.13) to give the pdf of Z, r e ( z + p ) In(2/zp) , z > 0 f z, s(z| S) = (3.3.16) I 0 , z < 0 35 The moment generating function for Z is -j uz C z ( s(-) = / f 7 | s (z|S) z | s 1 el-jco dz (3.3.17) 1-joo Its first and second derivatives are j 3 — = ~ (1 + D - j u ) d U (1-jo,)3 d 2 G z i s ^ > i ^ r 1 = - e J doo2 (3.3.18) p(p + 1-joi) + 3(p + 1-jo)) (1-jo))5 (l-jo))^ (1-jo))3 The mean and variance of Z are therefore given by E[Z|S] = • d C z | s ( Q ) , + -I 1 — : — = 1 + P d u " d 2C„ u(0) E[Z2|S] = ( - j ) 2 _ £ J £ = p2 + 4 p + 2 do)2 (3.3.19) (3.3.20) (3.3.21) and Var[z|S] = E[Z2|S] - (E[Z|S]}2 = 1 + 2p Since the random variable U is related to Z by (3.3.22) U = kNTZ (3.3.23) the mean and variance of U conditioned on S are 36 E[U|S] = kNT(l+p) (3.3.24) Var[u|S] = (kNT)2(l+2p) (3.3.25) To summarize, the conditional pdfs of the sampled integrator outputs are Gaussian with means u|S = kNT(l+p) (3.3.26) u|S = kNT (3.3.27) and variances a2|S = (kNT)2(l+2p)/(BfT) (3.3.28) 02|S = (kNT)2/(BfT) (3.3.29) These results are consistent with those derived by Marcum [M5] using a slightly different approach. Case 2: Assume that cross-correlations between code sequences assigned to al l potential users are bounded by <J>max« Further assume that each co-channel interferer contributes a signal ±(il> /T, ) /2Pcos( co t+6. ) & ymax b c i to the bandpass filter output; 0^ is a random phase angle, uniformly distributed between -T T and ir, which Is unchanged in each correlation interval of duration 1/B^ . The sum of noise components at the bandpass filter output is l-M-1 -| * n(t) " [_l ^max/Tb^ m C O s ( 9 i ) + n c ( t ) J C 0 S ( u 0 ^ 37 " [_J ^max / Tb) ^ s i n ^ + n s ( t ) J s i n U O t ) = x (t) cos ( u n t ) + x (t) s i n (cont) (3.3.30) c u s u The terms n (t) and n (t) are Gaussian with zero means and c s variances of NQB^. The pdf's for C.^ = cos 0^ and = s i n 0^ are, respectively, f r CO = 1 , |c.| < 1 (3.3.31) C i 1 TT/PCT2 and i — , I s J < 1 (3.3.32) S i 1 TT/PST2 with means E f C j = E[S ±] = 0 (3.3.33) and variances var[C ±] = var[S ±] - V 2 (3.3.34) If the number of simultaneous users M i s large, the sine and cosine noise components contributed by (M-l) co-channel interferers are Gaussian with zero means and variances of (M-l)(il> /T,) 2P, by rmax b ' 3 virtue of the central l i m i t theorem [P3], Therefore, the t o t a l cosine and sine noise components, x (t) and x ( t ) , are Gaussian c s with zero means and variance or t o t a l noise power of 38 N T = N0Bf + (M-l)(* m a x/T b)2p (3.3.35) With the total Gaussian noise power thus defined, equations (3.3.8) to (3.3.29) from Case 1 become valid and applicable to Case 2. The total noise power for Case 1 and Case 2 may be compared using signal parameters listed in Table 2.3.1 with = 100 KHz. The total noise power for Case 1 is Using a set of Gold's code with ^ m a x = 33 T c > the total noise power for Case 2 is Therefore, to maintain the same total noise power and hence synchronizer per-formance, when Gold's codes of length L = 511 are used the channel can accommo-date half the number of simultaneous users compared to the case where uncorre-cted codes of the same length are used. 3.3.3 Probabilities Attributed to Synchronization Detector Decisions Assuming that the K sampled integrator outputs v^T), v 2(T) , • • • ,v^(T) are independent, their joint pdf is simply the product of the individual pdf's derived In the last section. Let (i) p_., (ii) p_. and ( i i i ) p_,_ be the probabilities of making the decision that <j>^ is synchronous with the received code (i-th correlator pro-duces a hit) when in fact the following conditions are true, respectively: N T = NQBf + 0.00196 (M-l)P (3.3.36) NT = N 0 B f + ° - 0 0 4 1 7 (M-DP (3.3.37) (i) None of <|> <f>v is synchronous with the received code. 39 (ii) <j>^ is synchronous with the received code, ( i i i ) 4>j , j+i, is synchronous with the received code. This decision is made if v±(T) = max {v^T), v2(T) , vR(T) } and v ±(T) > v Q where v Q is a decision threshold. Therefore, PFA = / ° ° f v | s ( v l § ) [/ V f v | s( u|S)du] K _ 1dv (3.3.38) v0 PD = / f v| sCv|s) f ~ / V f v | - ( U | S ) d U ~ l K _ 1 d V (3.3.39) V Q ' L-oo 1 —I PFD = / " f v | s ( v | § ) f v | s ( u ^ ) d u ] K " 2 / f V | S ( w l S ) d w d V ( 3 - 3 > 4 0 ) Using the conditional pdf's derived before, the probabilities p ? A, p Q and p may be evaluated using numerical integration techniques. FD 3.4 The Search/Lock Strategy 3.4.1 The SLS Logic The SLS is a logical procedure which controls the operation of the code synchronizer. It supervises the transitions between search mode (acquisition) and lock mode (tracking), and adjusts the synchronization detector integration time T and decision threshold v Q when mode transitions occur to achieve a reasonable trade-off between acquisition time and hold-in time. At the end of each integration period, the decision device of the synchronization detector provides the SLS with the information of whether one of the K correlators pro-duces a hit or a l l correlators produce a miss. A correlator identifier (CI) 40 with possible values of 1,2, •••,K identifies the correlator that produces a hit. A flow chart of the SLS logic is shown in Fig. 3.4.1. It is a modified version of the up-down counter strategy described by Hopkins [H3]. Briefly, Hopkins' SLS is analogous to an up-down counter with possible counts of 0, 1, 2 and 3. A new cell is tested at count 1 in the search mode. A hit increases the count by 1 to a maximum of 3 when the lock mode is entered, whereas a hit reduces the count by 1 to a minimum of 0 when the present cell is rejected in favour of a new cell and a transition to search mode is made if lock mode was previously entered. To control a parallel/serial search, Hopkins' SLS is modi-fied so that K cells are simultaneously being tested. At count 2 in the search mode the CI is registered in a correlator identifier register (CIR) for reference. A hit with the same CI advances the count to 3 whereas a hit with a different CI causes the CIR to be updated. In the lock mode, only a hit which CI is the same as the current content of the CIR causes the count to be advanc-ed, whereas a miss or a hit with a different CI causes the count to be retarded. At count 0 the phase of the code generator is changed by one step and a new set of K cells is presented for testing. In the search mode the probability that one of the cells currently being tested is correct is small if K « N. In this case a short integration time T g and a high threshold V serves to decrease p and quicken acquisition. The S r A converse is true in the lock mode. Therefore the integration time is increased to T and the threshold is reduced to VT . An increased p results so that i t would be harder for random disturbances to knock the synchronizer out of lock. REJECT CELLS ADJUST CODE PHASE MISS ± SEARCH 1 T = T S 's v 0 = vc MISS HIT Clr-(CIR)' HIT CI = (CIR), SEARCH 2 T = T 0 . v0=v s CI——(Gl«) ENTER SEARCH MODE, SET SEARCH MODE PARAMETERS IT-LOCK 3 v0 = v L T= T. HIT CI = (CIR) HIT CI = (CIR)| LOCK 2 Vo = V L T = T, LOCK 1 v0 = v L T r T , MISS. OR HIT, CI # (CIR) HIT HIT, Cf=(CIR) ENTER LOCK MODE, SET LOCK MODE PARAMETERS MISS OR HIT, CI f (CIR) MTSS OR HIT, CI #(CIR) Legend: - d e c i s i o n t h r e s h o l d T - syn c h r o n i z a t i o n detector i n t e g r a t i o n time CI - c o r r e l a t o r i d e n t i f i e r ->• - " i s assigned to " (CIR) - c o r r e l a t o r i d e n t i f i e r r e g i s t e r F i g . 3.4.1 The search/lock s t r a t e g y l o g i c , 42 Analysis of the SLS is simplified by representing the SLS by finite Markov chains with absorbing boundaries and applying the theory of finite Markov chains [K7J. A finite Markov chain is characterized by its transition matrix [p.,]. Element p.. is the probability of transition from state i to state j . J J [p^j] can be rearranged and partitioned to reflect the type of state transi-tions as follows. state absorbing transient absorbing transient (3.4.1) where I is an identity matrix for probabilities of transitions among absorbing states, $ is a zero matrix for the zero probabilities of transitions from absorbing states to transient states, R is a matrix of probabilities of transi-tions from transient states to absorbing states and Q is a matrix of probabili-ties of transitions among transient states. Let Y be the event that one of the K cells being currently tested is synchronous with the received code and Y be the complement of Y. The finite Markov chain representations of the SLS under events Y and Y are shown in Figs. 3.4.2 and 3.4.3, respectively. R E J E C T S E A R C H 1 S E A R C H 2 L 0 C K 3 L 0 C K 2 L 0 C K 1 R E J E C T P 1 = S E A R C H M O D E P D V L O C K M O D E P D : (K -1)x ( S E A R C H MOD E P F D > P 6 = L O C K M O D E P F D P 3 ' : ( K - 2 ) x ( S E A R C H M O D E P F D ' % = 1-V • P 2 P 4 = = S E A R C H M O D E P F D Q 5 = 1 " P 5 " 6 = 1 " P 6 Fig."3.4.2 Markov chain model of SLS given that one of the K c e l l s being t e s t e d i n s ynchronization (event Y) REJECT SEARCH1 SEARCH2 LOCK3 LOCK2 LOCK1 RE JECT p. = Pi = Po = Kx ( S E A R C H MODE P-A ) r A ( K - 1 ) x ( S E A R C H MODE P p A ) SEARCH MODE P. FA P 0 = LOCK MODE P FA % = 1 - P o q 3 = 1 - p 3 F i g . 3.4.3 Markov chain model of SLS given t h a t none of the_K c e l l s being tested are i n s y c h r o n i z a t i o n (event Y ) . 45 3.4.2 Mean and Mean-Squared Dwell time Dwell time is the time taken to reject a set of K cells without achieving synchronization with the received code. Let T ^ and S^ ^ be the mean and mean-squared dwell time respectively when event Y is true. Referring to the Markov chain shown in Fig. 3.4.3, the dwell time for event Y is the absorption time from state 1 to any absorbing state. c Let tt be the set of transient states and tt be the complement of tt, the set of absorbing states. Let s^ denotes state k. Let t^ ^ be the absorption time from transient state i to any absorbing state, and be the transition time from state i . The mean absorption time from transient state i is Therefore the mean absorption times for al l transient states satisfy the matrix equation where E[t,] is a vector of mean absorption times with elements E[t. .] such that s^eft. For event Y, matrix I in eqn. (3.4.3) is a 5x5 identity matrix, Q is the matrix of probabilities of transitions among transient states given by (3.4.2) E[t x] = (I - Qj)" 1 T x (3.4.3) 46 State 1 1 2 3 4 5 0 Po 0 0 0 ^0 P i P2 0 0 0 0 P3 ^3 0 0 0 P3 0 ^3 0 0 0 P3 0 (3.4.4) where the non-zero elements are defined in Fig. 3.4.3, and T x is the vector of transition times given by ,t 'l " [ TS' TS' TL' TL» T L ] (3.4.5) where T and T are the search mode and lock mode integration times respec-o JLi tively. Thus the mean dwell time for event Y is TD1 - ( E [ i l ] ) l 'Dl which is the element of vector Eftj] corresponding to state 1. (3.4.6) Similarly the mean-squared absorption time from transient state i is * o i-Ci ts e- O ' s, eft k s. eft k which results in the matrix equation E[t$] = (I - Q ^ - 1 (T^ + 2D n Qj E[tJ} (3.4.8) where the mean-square absorption time vector E[t2] has elements E[t 2 .], vector T£ is formed by element-by-element squaring of T^, and DT^ is a diagonal matrix given by 47 T s 0 0 0 0 0 T s 0 0 0 0 0 T L 0 0 0 0 0 TL 0 0 0 0 0 T (3.4.9) The mean-squared dwell time for event Y is therefore (3.4.10) When event Y is true, the dwell time is the absorption time from state 1 to absorbing states 0 or 11 of the Markov chain shown in Fig. 3.4.2. Let the mean and mean-squared dwell time for event Y be T^ a n d S ^ respectively. Let t be the absorption time from transient state i to absorbing states L , 1 0 or 11. Since transitions from transient states 4, 5 and 6 to absorbing states 0 or 11 are impossible, these three transient states may bea merged into absorbing state 10 with no adverse effects to the following derivations. The mean and mean-squared absorption times from transient state i to absorbing states 0 or 11 are E [ t 2 J = J P l k T i + I P i k E t T i + t 2 J (3.4.11) ' s^eQ -{s 10} skeft ' and s efi ~ { s 1 0 } s. eft k which result in the matrix equations 48 E[t 2] = (I - Q 2) _ 1 D p 2 T 2 (3.4.13) and E[tg] - (I - Q 2) _ 1 {Do + 2 D T 2 Q2 E[t 2]} (3.4.14) In eqns. (3.4.13) and (3.4.14), mean and mean-squared absorption time vectors E[t 2] and E[t|] respectively have elements E[t^ ^ 1 and E[t| ^ ] with s^eft, f 2 is the transition time vector given by T2 = tV V V V V \f ( 3 ' 4 - 1 5 ) and T£ is T 2 squared element-by-element, Q2 is the transition probability matrix given by State 1 2 3 7 8 9 1 0 Pi P 2 0 0 0 2 <io 0 P 2 0 0 0 3 Pi P3 Pif 0 0 7 0 0 0 P 6 0 8 0 0 0 P6 0 <U 9 0 0 0 0 Pe 0 (3.4.16) where the non-zero elements are defined in Fig. 3.4.2, I is a 6x6 identity matrix, D _ is a diagonal matrix given by 49 J¥2 D, T2 0 0 0 1 0 0 0 0 0 0 ( 1 - P i ) 0 0 0 0 0 0 1 0 0 0 (3.4.17) 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 i n F i g . 3.4.2, and i s a diagonal matrix given by s 0 0 0 0 0 T s 0 0 0 0 0 T s 0 0 0 (3.4.18) ) 0 0 T L 0 0 ) 0 0 0 T L 0 ) 0 0 0 0 V 3.4.13) and eqn. (3.4.14), the mean and mean-squared dw e l l times are r e s p e c t i v e l y TD2 - ( E [ l 2 ^ 1 and SD2 = C E l t j D j (3.4.19) (3.4..20) 50 3.4.3 Mean and Mean-Squared time to Lock When event Y Is true, i t is possible for the synchronizer to lock onto the received signal with the correct cell. If the SLS goes into lock mode with the correct cell, the elapsed time since the present group of K cells was first tested is the time to lock, which is the absorption time from state 1 to state 10'. Absorbing states 10' and 11' are formed by merging, respectively, states 4, 5, 6, 10 and states 7, 8, 9, 11 in Fig. 3.4.2. Let the mean and mean-squared times to lock be T and S respectively. L K L K Let t be the absorption time from transient state i to absorbing state j ,1 10'. As before, the vectors of mean and mean-squared absorption times satisfy the matrix equations E[t 3] - (I - Q3)- 1 D p 3 T 3 (3.4.21) and E[t§] - (I - Q 3) _ 1 {Dp3 T§ + 2 T g Q3 E[t 3]} (3.4.22) where vectors E[t 3] and E[t^] have elements Eft^ ^ ] and E[t2 ^ ] respectively, vectors f 3 = [Ts, T s , Tgf (3.4.23) -2 and TQ is TQ squared element-by-element, I is a 3x3 identity matrix, matrices 51 State 1 2 3 0 <*0 P i 0 P i P2 P 2 P3 (3.4.24) and 'P3 (l-q 0) 0 0 0 1 0 0 0 (1-Plt) (3.4.25) where pj, p 2, P 3 , P ^ and q Q are defined in Fig. 3.4.2. Solving the matrix equations results in TLK = ( E [*3Di (3.4.26) and (3.4.27) 3.4.4 Probability of Entering Lock Mode with the Correct Cell Let p be the probability that the SLS enters lock mode with the correct J_i cell locking onto the received code when event Y is true. Let B be the matrix which element is the probability of being absorbed in absorbing state j from an initial transient state i , given by B . . = P., . + J P J , B. . , s.eft , s.eftC (3.4.28) l j i j 8,60 ± k k j 1 2 k 52 Eqn. (3.4.28) satisfies the matrix equation B = (I - Q)-1R (3.4.29) where Q and R are submatrices of the transition matrix in eqn. (3.4.1). Referring to the Markov chain in Fig. 3.4.2, it is obvious that transi-tions to states 4 or 7 guarantee absorption at states 10 or 11. By merging states 4, 5, 6, 10 into state 10' and states 7, 8, 9, 11 into state 11', the matrices Q and R in eqn. (3.4.29) can be simplified as follows. State 1 2 3 1 0 Pi P2 Q - 2 *0 0 P 2 3 0^ Pi P 3 State .' 0 10' 11' 1 0^ 0 0 R = 2 0 Pi 0 3 0 0 p-In eqns. (3.4.30) and (3.4.31), the non-zero elements are defined in Fig. 3.4.2. Solving eqn. (3.4.29) yields 53 3«5 A c q u i s i t i o n Time 3.5.1 Mean A c q u i s i t i o n Time An important performance measure of the code synchronizer i s the proba-b i l i t y d i s t r i b u t i o n of the a c q u i s i t i o n time random va r i a b l e T . A c q u i s i t i o n time i s the time taken by the synchronizer to lock onto the received code a f t e r the desired signal i s present. Let J be a random variable such that a f t e r the desired s i g n a l begins, event Y occurs J times before event Y occurs. The occurrence of event Y then repeats a f t e r every (N/K)-l occurrences of event Y, assuming henceforth that K i s a factor of N. Since the desired s i g n a l may s t a r t at any time, Pr(J=j) = K/N , j=0,l,2, ...,(N/K)-1 (3.5.1) Define a set of random variables Z^, m=l,2, • • • ,N/K, by m 1 , 1 < m < J (3.5.2) 0 , J < m < N/K Therefore the p r o b a b i l i t y d i s t r i b u t i o n of Z i s given by ( N / K ) - l Pr(Z m=l) = I Pr(Z m=l|j=j)Pr(J=i) 3=0 (N/K)-l I K/N j=m = l-(m K/N) (3.5.3) Pr(Z m=0) = l-Pr(Z m=l) = m K/N (3.5.4) If the synchronizer locks onto the received code at the n-th occurrence of Y, the a c q u i s i t i o n time i s 54 (T | lock at n-th Y) n-1 N/K N/K T(i - D(N/K)+i + Zm T(n-l)(N/K)+m + T(n-1)(N/K)+J+1 (3.5.5) where, with reference to the set of K c e l l s being tested when the desired signal begins ( i = l ) , f dwell time of i - t h set of c e l l s , i*(n-l)(N/K)+J+l I time to lock, From Sections 3.4.2 and 3.4.3, i=(n-l)(N/K)+J+l (3.5.6) Etx.j = <( [" T D 1 , i * ( £-l)(N/K)+J+l , £=l,2,..-,n TD2 * ± = ( A _ 1 ) ( N / K ) + J + 1 » 4 - 1 , 2 , n - 1 I TLK ' ^(n-DCN/K)-1-^1 (3.5.7) From the p r o b a b i l i t y d i s t r i b u t i o n of Z m, E[Z ] = Pr(Z =1) = l-(mK/N) m m (3.5.8) and m=l Therefore N/K N/K I E[ZJ = (N/K) - (K/N) I m = [(N/K)-l]/2 m=l E[T I lo c k at n-th Y] A (3.5.9) - H)[|-l)L1Mj+ie.lt l (t 1 ,N (3.5.10) J Dl D2 J 2 <-K ^ D l ' "LK The p r o b a b i l i t y of locking onto the received code at the n-th occurrence of 55 Y i s Pr (lock at n-th Y) = p j l - p ^ 1 1 - 1 (3.5.11) The mean a c q u i s i t i o n time i s therefore E [ V - - 0TD1 + T L K + [ ( | - l ) T m + T D 2 ] p L I ( n - D d - p / " 1 n=l " I " l^krKl + ^ ) T D 2 + TLK < 3- 5' 1 2) L i Li 3.5.2 A c q u i s i t i o n Time Variance Squaring both sides of eqn. (3.5.5) and taking the mean, the mean-squared a c q u i s i t i o n time given that a c q u i s i t i o n i s successful at the n-th occurrence of event Y is n-1 N/K E[ T | | lock at n-th Y] = ^ x ( 1 . 1 ) ( H / K ) 4 j ) 2 N/K + f V Z T l2 + T 2 + \ ^ m T(n-l)(N/K)+m J T(n-1)(N/K)+J+1 n-1 N/K N/K 2 J , J , T ( i -D(N/K)+j \ Zm T(n-l)(N/K)+m + 1= 1 j = 1 m= 1 n-1 N/K N/K 2 T(n-l)(N/K)+J+l ^ T(i-l)(N/K)+j + J : Zm T(n-l)(N/K)+m^ (3.5.13) From Sections 3.4.2 and 3.4.3, 56 K[TJ ] - -( SD1 * ±*(l-l'WK.'+J+1 » 4=1,2,...,n SD2 ' 1 = ( * - 1 ) ( N / K ) + J + 1 > £=1,2, •••,n-l (3.5.14) I S L R , i=(n-l)(N/K)+J+l From the probability distribution of Z , E[Z 2] = Pr(z=l) = 1 - (mK/N) (3.5.15) L mJ v m ' Furthermore, definition of Z in eqn. (3.5.2) implies m (N/K)-l Prfz = 1, Z = 1 £ < m ) = Y Pr(J=j) = 1 - (mK/N) (3.5.16) j=m so that E[Z„Z 1 = 1 - (mK/N) , 1 < £ < m < N/K (3.5.17) L £ mJ Substitutions into each term in the right hand side of eqn. (3.5.13) yield r(i-l)(N/K)+j n-1 N/K i-1 j=l = C«-» [| - 1 )SD1 + SD2 + C| " 0(1 - 2 ^ + 2(| -1)T D 1 T D 2] + (n-l)(n-2)[(|- l ) 2 + 2 (| - 1JT^ + ] (3.5.18) N/K N/K E [ ( \ Zm T(n-l)(N/K)+m^^ = E^ \ Zm T(n-l)(N/K)+m m=1 m=1 (N/K)-l N/K + 2 Li Z£ZmT(n-l)(N/K)+£ T(n-l)(N/K)-hJ £=1 m=£+l - i i - o s i + i £ - o c i - - 3 ) T S 1 ( 3 - 5 - 1 9 > 57 E h 2 n - l ) « K ) + J + l ] * SIK ( 3 - 5 - 2 0 ) n-1 N/K N/K E ^ 2 1I1 T(i-D(N/K)+j J1 Zm T(n-l)(N/K)-hJ = ( n - l ) ( l - i P T 2 i + ( n - l ) ( | - l ) T D 1 T D 2 (3.5.21) n-1 N/K N/K E[ 2 T(n-l)(N/K)+J+l(A ^ T(i-l)(N/K)+j + E Z m T( n-l)(N/K)-hii^ i=l j=l m=l = 2 ( n - 1 ) T L K [ | " O T D 1 + T D 2 ] + (| ~ l ) T m T L K (3.5.22) Multiplying the sum of equations (3.5.18) to (3.5.22) by Pr (lock at n-th Y) in eqn. (3.5.11) and summing the result over n from one to infinity, the mean-squared acquisition time thus obtained is Li Li + 2hr)\ 22 + [3+*&(I- 0 & D 1 T D 2 Li L i L i + I " ^hrKl TLK + 2 ^ T D 2 TLK ( 3 ' 5 ' 2 3 ) Li L J The acquisition time variance is therefore Var[TA] = E[T 2] - (E[Tj ) 2 (3.5.24) 58 where E[T2] amd E[T ] are given by eqn. (3.5.23) and eqn. (3.5.12) respec-A A tively. 3.5.3 Acquisition Time Confidence Estimates The probability that the acquisition time is within a given time limit can be accurately calculated if the acquisition time pdf is available. Derivation of the acquisition time pdf requires the derivation of a l l the moments. The first and second moments have been formulated in the two previous sections. Derivation of higher moments seems practically impossible. However, a confidence estimate of the acquisition time can be obtained using Chebyshev inequality [D5] which states that Pr(|T - E[T J| > e) <Var[T AJ/e 2 (3.5.25) A confidence lower bound of x% is obtained by setting the right hand side of inequality (3.5.25) to 1-0.Olx so that inequality (3.5.25) can be rewritten as Pr(T A < 0) > O.Olx (3.5.26) where, if x is given, the acquisition time upper bound is 0 = E[T ] + •Var[T ]/(l-0.01x) (3.5.27) or, if 3 is given, x = 100[l-Var[TA]/(3-E[TA])2] (3.5.28) Inequality (3.5.26) states that with confidence of at least x%, the acquisition time is upper-bounded by 3« 59 3.6 Hold-In Time 3.6.1 Mean and Variance of Hold-In Time In the lock mode, the synchronization detector continues to make a decision every T seconds causing an appropriate state transition in the SLS. Li In the presence of noise and co-channel interference, the lock mode detection probability p D is close to but less than one. Therefore, after the SLS enters lock mode with acquisition of the correct cell, if the desired signal continues to be present, it is inevitable that the SLS eventually retards its count to zero, the search mode is re-entered and synchronization is lost. The time that the SLS spends in the lock mode when synchronization is maintained is the hold-in time T . H Referring to the Markov chain shown in Fig. 3.4.2, the hold-in time is the absorption time from state 4 to the only possible absorbing state 10. As before, the mean and mean-squared hold-in times are, respectively, elements corresponding to state 4 of the mean and mean-squared absorption time vectors Eft^] and E[t£J which satisfy the matrix equations E[tk] = (I - Q^-l T1+ (3.6.1) E [ t2J = (I - Q^ - 1 {Tg + 2T Qlf E[tlf]} (3.6.2) where is the matrix 60 State 4 5 6 , 4 P 5 q5 0 5 P 5 0 q5 6 0 P5 0 -(3.6.3) with p 5 and q 5 defined in Fig. 3.4.2, is the vector " tTL' TL' \ ? and T£ is squared element by element. Solving eqn. (3.6.1), the mean hold-in time is E[TH] = (— + —)1 (3.6.4) (3.6.5) Substituting Eft^] into eqn. (3.6.2) and solving the equation, the mean-squared hold-in time is E f T 2 1 = f — + — - — + — - — I T 2 £,L-LHJ 6 4 3 2 > L (3.6.6) q5 q5 q5 q5 q5 Therefore the hold-in time variance is Var[TH] = E[T2] - (E[T HJ) 2 <\% <\\ qg q§ q. .)T 2 (3.6.7) 61 3.6.2 Approximation of Hold-In Time Probability Distribution An important performance criterion for the code synchronizer is that the probability that the hold-in time is greater than the message transmission time should be close to one. This ensures that premature loss of synchronization does not occur most of the time. It is therefore of interest to calculate the synchronization loss probability. Define p (i) as the probability that nTT seconds after the SLS enters lock n L mode with acquisition of the correct cell the SLS is in state i . Define vector Pn = t p n ( 4 ) ' P n ( 5 ) ' P n ( 6 ) ' P n ( 1 0 ) ^ (3.6.8) From the Markov chain shown in Fig. 3.4.2, (3.6.9) where P n = [1,0,0,0]' (3.6.10) and state transition matrix G = State 4 5 6 10 4 P 5 5^ 0 0 5 P5 0 q5 0 6 0 Ps 0 10 0 0 0 1 (3.6.11) Iterative calculation of p yields the cumulative distribution for T.,, as n H follows. Pr(T H < nTL) = Pn(10) (3.6.12) 62 The probability of synchronization loss after at least nT seconds is Pr(T„ > nT) = 1 - p (10) (3.6.13) H L n Let p be the probability of detection in the lock mode. In eqn. (3.6.11) , Pc = Pp., and q,. = 1 - pnT . Computations of the cumulative distribu-tion for T reveal that for p. fixed and p (10)«1, p (10) increases approxi-H o n n mately linearly with n, and to maintain a constant p (10), n must increase by n three order of magnitude for each order of magnitude decrease in q 5. Hence, for p close to one, the number of iterations n and the computation time are JJJLi large even for p (10) close to zero. A better method to evaluate eqns. n (3.6.12) and (3.6.13) is therefore needed. Unfortunately, the Chebyshev inequality cannot be applied to lower-bound the probability in eqn. (3.6.13). When p »1 so that q,-«l, the mean and variance of T derived in the last section may be reduced to E[T„] » (l/q^)T T , q q«l (3.6.14) VartTR] » (l/q§)T2 , q 5«l (3.6.15) The fact that the mean and standard deviation of T^ are nearly equal for q 5«l suggests that eqns. (3.6.12) and (3.6.13) may be approximated by an exponential distribution. To test this hypothesis, l-pn(10) from eqn. (3.6.13) is compared with 63 -n/n n > 0 e F(n) = (3.6.16) 0 n < 0 where n - (1 + 2q|)/q| (3.6.17) and the percentage deviation 6 = [1 - pn(10)] " F(n) x 100% (3.6.18) 1 ~ Pn(10) is obtained. Values of 6 are tabulated against different values of 1 - Pn(10), p and n in Table 3.6.1. Table 3.6.1 shows that the exponential distribution is an excellent approximation to the probability distribution of T for a l l values of 1 -Pn(10) and p D L considered. The accuracy of the approximation improves with n, the number of iterations, and a large n is the condition under which the approximation becomes necessary. 3.7 Numerical Examples Given the single user power to noise-density ratio PNR, the transmission bandwidth , the filter bandwidth B^ , the number of simultaneous channel users M, the number of possible code cells N, the number of parallel envelope correlators K, the search mode integration time T and decision threshold V , and the lock mode integration time T and decision threshold V , the perform-ance measures for the code synchronizer as derived in the previous sections may 1-Pn(10) n Precision . of n Deviation <5 (%) 0.9 0.9 0.99 0.9925 0.995 110 105,000 250,000 845,000 ± 0.5 ±5 0 0 ± 500 ±2500 -2.031 x 10~ 2 -2.538 x 10~ 5 -1.085 x 10~ 5 -3.246 x 10~ 6 0.99 0.9 0.99 0.9925 0.995 13 10,100 23,800 80,500 ± 0.5 ± 50 ± 50 ± 250 3.639 x 10" 3 -1.574 x 10 - 6 -7.549 x 10~ 7 -2.538 x 10" 7 0.999 0.9 0.99 0.9925 0.995 0.999 3 1,000 2,370 8,000 1,000,000 ± 0.5 ± 5 ± 5 ± 25 ±5000 -2.011 x 10~ 3 7.091 x 10~ 7 2.012 x 10" 7 2.994 x 10" 8 -1.294 x 10~ 9 TABLE 3.6.1 Percent Deviation <$ of Actual and Exponentially Approximated Hold-in Time Cumulative Distribution 65 be calculated using assumptions given under either case 1 or case 2 in Section 3.3.2. The means and standard deviations (square roots of the variances) of acquisition time and hold-in time are plotted against M using the signal parameters in Table 2.3.1 and a set of fixed synchronizer parameters tabulated in Table 3.7.1. Table 3.7.1 Spread-Spectrum Code Synchronizer Parameters Bandpass filter bandwidth Search mode Integration time Lock mode integration time Search step size Number of code cells 1 Search mode decision threshold b Lock mode decision threshold V Li Number of parallel correlators K B f = 100 KHz T s = 0.2 msec. TL = 1.0 msec. A = 0.5 chips N = 1024 V„ \ see Figs. 3.7.3 to 3.7.21 A series of graphs showing the dependence of these curves on each of the parameters Vg, V^, PNR and K are obtained. Case 1 assumptions are used, but results for Case 2 are obtainable simply by halving the scale of the horizontal axis and will not be duplicated. The following discussions are generally valid for both Case 1 and Case 2. Before the results are presented and discussed, some remarks regarding Vc To facilitate computations, two redundant cells have been appended to the 1022 possible code cells. 66 and V are in order. In eqns. (3.3.26) to (3.3.29), letting kN =1, the con-ditional means and variances for the Gaussian pdf of the detector output become u| S = 1 + p (3.7.1) u|s = 1 (3.7.2) o2|S = (l+2p)/(BfT) (3.7.3) o2|§ = l/(BfT) (3.7.4) The decision thresholds V and V specified with the results correspond to the Gaussian pdf's with means and variances given by eqns. (3.7.1) to (3.7.4). Figure 3.7.1 and Fig. 3.7.2 show the false alarm probability versus the decision threshold for different values of K, in the search mode and in the lock mode respectively. Calculations reveal that when PNR = 50 dB-Hz or higher, the mean and standard deviation of acquisition time are insensitive to changes in V . The opposite is true for V , as illustrated by Figs. 3.7.3 to 3.7.5. Given PNR, K O if and the expected range of M, the mean acquisition time can be optimized with respect to V . For example, Fig. 3,7.3 shows that with PNR = 50 dB-Hz and K=4, optimum values for V are approximately 1.5 for 1 < M < 200, 1.4 for 200 < M < 870 and 1.3 for M > 870. Figures 3.7.4 and 3.7.5 show that V has the same effect on the mean and standard deviation of acquisition time. The relationships between PNR and the mean and standard deviation of acquisition time are shown in Figs. 3.7.6 and 3.7.7. Both graphs display a minimum irreducible mean or standard deviation which occurs at large values of PNR and small values of M as a result of an' "overhead" of searching through an 1.0 1.2 1.4 1.6 1.8 2.0 D E C I S I O N T H R E S H O L D , V S F i g . 3.7.1 False alarm p r o b a b i l i t y p v s . d e c i s i o n threshold r A i n the search mode. 68 1.0 1.1 1.2 1.3 1.4 D E C I S I O N T H R E S H O L D . V L F i g . 3.7.2 False alarm p r o b a b i l i t y p v s . d e c i s i o n t h r e s h o l d r A VT i n the l o c k mode. 0 20 40 60 80 ,100 N O . O F A C T I V E U S E R S . M C X 1 0 1 ) F i g . 3.7.3 Mean a c q u i s i t i o n t ime v s . number of a c t i v e u s e r s M f o r v a r i o u s 7V R v a l u e s . w i t h PNR = 50.0 dB-Hz. 70 I 0 20 40 SO 80 ,100 N O . O F A C T I V E U S E R S . M ( X 1 0 1 ) F i g . 3.7.4 Mean a c q u i s i t i o n time v s . number of a c t i v e users M f o r v a r i o u s V_ values w i t h PNR = 70.0 dB-Hz. 71 0 20 40 60 80 100 N O . O F A C T I V E U S E R S . "M ( X 1 0 1 ) F i g . 3.7.5 A c q u i s i t i o n time standard d e v i a t i o n v s . number of a c t i v e users M f o r v a r i o u s V values w i t h PNR = 70.0 dB-Hz. 72 o o PNR IN DB-HZ 55.0 60-0 PNR^70.0DB-HZL I i I n i i 0 20 40 60 N O . O F R C T I V E U S E R S . 80 100 M ( X 1 0 1 ) F i g . 3.7.6 Mean a c q u i s i t i o n time v s . number of a c t i v e users M f o r v a r i o u s PNR values i r 20 40 60 80 10 O F A C T I V E U S E R S , M ( X 1 0 1 F i g . 3.7.7 A c q u i s i t i o n time standard d e v i a t i o n v s . number of a c t i v e users M f o r v a r i o u s PNR v a l u e s . 74 average of N/(2K) code cells to locate the correct cell for the first time. The relationships between PNR and receiver bit-error probability was discussed in Section 2.3. Therefore the choice of PNR affects the SSMA system perform-ance as a whole. Although a high PNR level is generally desired, it is constrained by such considerations as government regulations, limitation of power supply, and cost, weight and physical size of the transmitter. Furthermore, increase in PNR beyond 80 dB-Hz does not bring about any improvement in acquisition time or bit-error probability as co-channel interference predominates over channel noise. Figures 3.7.8, 3.7.9 and 3.7.10 show that the effect of increasing K is to reduce the mean and standard deviation of acquisition time. The rate of reduc-tion decreases as K is increased. The ratio of reduction RT = T (K)/T (1), A A where T (K) is the minimum irreducible mean acquisition time for a synchronizer A with K parallel correlators, is plotted against log2(K) in Fig. 3.7.11. This graph shows that when K is small, reduction in mean acquisition time is almost proportional to increase in K. Another consequence of increasing K is that the complexity and therefore cost of the synchronizer also increase. Hence there is a trade-off between cost increase and acquisition time reduction. Upper bounds for 90%, 99.9% and 99.999% confident acquisition time as derived in Section 3.5.3 are plotted against M for different values of PNR with V = 1.7, V = 1.0 and K = 1 in Figs. 3.7.12, 3.7.13 and 3.7.14 respectively. O J-j From these graphs, T^ < 0.29 sec. with probability of at least 0.9; T^ < 1.97 sec. with probability of at least 0.999 and T < 18.8 sec. with probability of A at least 0.99999 for large PNR, small M and given values of VQ, VT and K. cr 1 cr " . • • ~ U J -2 1 - PNR = 50.0 DB-HZ ' VS=1.5 VL = 1.0 s H i r ~ n 1 1 1 1 1 1 0 20 40 60 80 100 N O . O F A C T I V E U S E R S . M C X 1 0 1 ) F i g . 3.7.8 Mean a c q u i s i t i o n time v s . number of a c t i v e users M f o r v a r i o u s K values w i t h PNR = 50.0 dB-Hz. P N R =70.0 D B - HZ VS =1.7 VL =1.0 0 20 40 60 80 ,10 N O . O F A C T I V E U S E R S . M C X 1 0 1 3.7.9 Mean a c q u i s i t i o n time v s . number of a c t i v e users M f o r v a r i o u s K values w i t h PNR = 70.0 dB-Hz. F i g . 3.7.10 A c q u i s i t i o n time standard d e v i a t i o n v s . number of a c t i v e users M f o r v a r i o u s K values w i t h PNR = 70.0 dB-Hz. 79 n i i i i i i i i i r 0 20 40 60 80 100 N O . O F A C T I V E U S E R S . M ( X 1 0 1 ) F i g . -3.7.12 Upper bound f o r 90% confident a c q u i s i t i o n time v s . number of a c t i v e users M. 80 i — i — i i i i r i i i r 0 20 40 60 80 100 N O . O F A C T I V E U S E R S . M ( X 1 0 1 ) F i g . 3.7.13 Upper bound f o r 99.9% confident a c q u i s i t i o n time v s . number of a c t i v e users M. 81 i i • i i i » • ' i i 0 20 40 60 80 ,100 N O . O F A C T I V E U S E R S . M ( X 1 0 5 ) F i g . 3.7.14 Upper bound f o r 99.999% confident a c q u i s i t i o n time v s . number of a c t i v e users M. 82 The hold-in time is independent of search mode parameters. Figure 3.7.15 shows that mean hold-in time increases with decreasing V . Since V is con-Li LI strained not to be less than 1.0 in order that false alarms are not favoured in the lock mode, it seems that V = 1.0 is an appropriate choice. Li The mean and standard deviation of hold-in time are plotted against M for different values of PNR with K = 4 in Figs. 3.7.16 and 3.7.17, and with K = 32 in Figs. 3.7.18 and 3.7.19. Except at very low PNR's, these graphs show that the mean and standard deviation of hold-in time are approximately equal for given values of PNR and K. Comparison between the graphs for K = 4 and K = 32 reveals that increase in K results in decreases in the mean and standard devia-tion. This fact is further exemplified by Figs. 3.7.20 and 3.7.21 which also show that reductions in the mean and standard deviation of hold-in time occur at a decreasing rate as K increases. Therefore, when K is increased in order to reduce acquisition time, it is important to check that the mean hold-in time is not also reduced by such an extent that the synchronization loss probability is significantly increased. The hold-in time lower bounds for synchronization loss probabilities of 0.9, 0.999 and 0.99999, as given by the exponential approximation of eqn. (3.6.13), can be obtained by multiplying the scales of the mean hold-in time axis in the suitable graphs by factors of 0.1, 0.001 and 0.00001, respectively. D 20 ,40 60 80 100 NO. OF A C T I V E U S E R S . Ii ( X l U 1 ) F i g . 3.7.15 Mean h o l d - i n time vs. number of a c t i v e users M f o r v a r i o u s VT v a l u e s . ~ l i r~ i i i i i i i r 0 20 40 60 80 100 N O . O F A C T I V E U S E R S . M ( X 1 0 1 ) F i g . 3.7.16 Mean h o l d - i n time v s . number of a c t i v e users M f o r v a r i o u s PNR values w i t h K = 4. 85 0 20 40 60 80 100 N O . O F R C T I V E U S E R S . M (X . 1 0 1 ) F i g . 3.7.17 Ho l d - i n time standard d e v i a t i o n vs. number of a c t i v e users M f o r v a r i o u s PNR values w i t h K = 4. 86 F i g . 3.7.18 Mean h o l d - i n time vs. number of a c t i v e users M f o r v a r i o u s PNR values w i t h K =32. ~T i r i i i i r i — i — r 0 20 40 60 80 100 N O . O F A C T I V E U S E R S . M ( X 1 0 1 •) F i g . 3.7.19 Hold-in time standard d e v i a t i o n v s . number of a c t i v e users M f o r v a r i o u s PNR values w i t h K = 32. 0 20 40 60 80 10 N O . O F A C T I V E U S E R S . M ( X 1 0 1 F i g . 3.7.20 Mean h o l d - i n time v s . number of a c t i v e users M f o r v a r i o u s K va l u e s . F i g . 3.7.21 H o l d - i n time standard d e v i a t i o n v s . number of a c t i v e users M f o r v a r i o u s K values. 90 4. SSMA SYSTEM PERFORMANCE 4.1 Traffic Model In an interactive data communication system, a user normally sends a mes-sage and waits for a response before sending another message. In a SSMA sys-tem, a user with a message to send may immediately become active in the channel until the message is correctly received. The user then remains idle until another message is ready. It is reasonable to assume that users access the channel independently, in which case the arrival of users and hence messages in the SSMA channel constitutes a Poisson random process [D6]. Let X be the mes-sage arrival rate for the entire user population. The probability that m users (or messages) arrive during a time Interval x is Pr(m,x) = k A J j e A T , x>0 , m= 0,1,2,... (4.1.1) and the inter-arrival time is exponentially distributed with mean 1/X. The Poisson assumption is supported by traffic statistics [F1,D7] obtained from operational multiple access systems. Restrictions on the length of messages generated by the users of a SSMA system is not really necessary. However, to facilitate comparison with ALOHA systems which restrict users' messages to a fixed length, messages In the SSMA system are also assumed to have a fixed length of Z bits/message. All messages are assumed to incorporate sufficient error detection channel coding so that bit-errors caused by channel noise or by loss of synchronization may be detect-ed by the receiver with a negligible probability of undetected errors. 91 4.2 Protocols for SSMA Signal Transmission A SSMA channel with M active users simultaneously sending messages to a central node is modelled in Section 2.2. For interactive data communications, the SSMA channel constitutes a forward channel, and transmissions from the node to the users, including acknowledgement messages, are handled by a separate return channel in an adjacent band. For maximum efficiency, messages addressed to different users are usually queued in the return channel, with a higher priority often assigned to acknowledgement messages. Signal transmission protocols are procedures whereby users and nodes exchange information using the forward and return channels to facilitate code synchronization and correct message reception. The following discussions are restricted to protocols governing the transmission of messages from users to a central node. Two important design criteria for SSMA protocols are minimization of aver-age message delay D and maximization of the channel capacity (maximum attain-able average throughput) C, given the message length £, the received power to noise density ratio PNR, the average message service delay T (sum of average round trip propagation delay 2T and average acknowledgement delay T ), the user population UP, and system parameters listed in Tables 2.3.1 and 3.7.1. In some cases the above criteria are not compatible and trade-offs are necessary. T is the time it takes for the central node to acknowledge establishment of K synchronization or error-free reception of a message, and includes processing time at the node, queueing delay and transmission time for the acknowledgement message. 92 For small user populations (e.g. UP < 200 at PNR > 70 dB-Hz), receiver performance does not degrade appreciably when a l l users are active, compared to when a single user is active (see Fig. 2.3.1). Message delays and channel capacity are optimized in such cases if code synchronization between node and users is maintained at all times. Acquisition is necessary only in the infre-quent event that the code synchronizer loses lock. Message delay consists of the propagation delay, a number of message transmissions to achieve error-free reception, and a number of service delays i f each message transmission is acknowledged. The maximum channel capacity C = UP'RJJJ bits/sec, where is the information bit rate, occurs when message interarrival time for each user is zero and message errors are negligible. Further analysis will be restricted to systems with large user populations and large message interarrival times. In this case code acquisition is neces-sary before a new message is transmitted, and acquisition delay has major effects on message delay and channel capacity. Figure 4.2.1 illustrates three possible protocols for SSMA signal trans-mission between an active member of a large user population and a central node. Protocol A: An active user simply transmits the message repeatedly until being acknowledged by the node that the message has been correctly received (positive acknowledgement). Protocol B: An active user first sends a synchronization preamble until being acknowledged that synchronization is established at the node. The user then sends the message as in Protocol A. USER ACTION SIGNAL IN FORWARD CHANNEL SIGNAL IN RETURN CHANNEL NODE ACTION -TIMING AT NODE SEND MESSAGE IN REPETITION //////////////////////////////////////////////////////////////////////// ^T-ACQUISITION DECODE UNTIL MESSAGE ERROR-FREE «-fT—y -<-lst T—y «-2nd T-m m 1 m 1 m ' PROTOCOL A h-rth T—»• 1 m / / / / / / / / / / / / ACKNOWLEDGE < T. K ^T; USER ACTION SIGNAL IN FORWARD CHANNEL SIGNAL IN RETURN CHANNEL NODE ACTION TIMING AT NODE SEND SYNC. PREAMBLE ///////////////////////////////// «-T, ACQUISITION / / / / / / / / / / SYN. ACK. K SEND MESSAGE IN REPETITION '' ///////////////////////////////////////////////////// P DECODE UNTIL MESSAGE ERROR-FREE -KLst T—*h-2nd T—» m / m > • • h-rth T -y 1 m PROTOCOL B / / / / / / / / / / MES. ACK. < TT K USER ACTION SIGNAL IN FORWARD CHANNEL SIGNAL IN RETURN CHANNEL-NODE 'ACTION TIMING AT NODE SEND SYNC. PREAMBLE ///////////////////// SEND MESSAGE ///////////// - v TRY TO. ACQUIRE CODE. AND DECODE • MESSAGE 'WITHIN' '.THIS. TIME. FRAME / / / / / / / / / / / / / / / / / / / / ACKNOWLEDGE ONLY I F MESSAGE ERROR-FREE K W REPEAT SEQUENCE IF ACK. NOT RECEIVED //////////////////• PROTOCOL C ., F i g , 4.2.1 Three p r o t o c o l s f o r SSMA s i g n a l t r a n s m i s s i o n 94 In both Protocols A and B, i f a p o s i t i v e acknowledgement i s not received within a reasonable time T^, channel or equipment f a i l u r e may have occurred and other actions could be i n i t i a t e d by the user. The a c q u i s i t i o n time confidence estimate derived i n Section 3.5.3 i s an important consideration i n the determination of T^. Protocol C; An active user sends a synchronization preamble for a f i x e d duration T E, followed by the message, sent once, with no r e p e t i t i o n s . Successful a c q u i s i t i o n followed by error-free reception of the message i s acknowledged. If this acknowledgement i s not received within a waiting time T w, the preamble and message are sent again. This process repeats u n t i l the p o s i t i v e acknowledgement i s received. In Protocol C T and T are chosen to achieve given p r o b a b i l i t i e s p and E W A p„ that T < T and T_ < T , where T and T are the a c q u i s i t i o n time and S A E S W A o service time random v a r i a b l e s , r e s p e c t i v e l y . Given p^, T^ can be determined from the a c q u i s i t i o n time confidence estimate derived i n Section 3.5.3. This estimate i s rather loose and gives a long delay, which can be reduced using a ti g h t e r estimate. However, knowledge of the a c q u i s i t i o n time p r o b a b i l i t y d i s -t r i b u t i o n i s then necessary. If the p r o b a b i l i t y d i s t r i b u t i o n for.Tg i s also known, minimization of average delay with respect to p and p i s p o s s i b l e . A o Once synchronization has been achieved, transmitted data b i t s are decoded with b i t - e r r o r p r o b a b i l i t y p B derived i n Section 2.3. In an independent-error channel, the p r o b a b i l i t y P £ of error-free reception of an £-bit message i s 95 P c = ( 1 " P B ) £ - 1-*P b , £p B«l (4.2.1) For Protocols A and B, the average number of message repetitions before correct reception i s therefore 00 f = I r P (1-P ) r _ 1 = 1/P (4.2.2) u. c c c r=l S i m i l a r l y , for Protocol C the number of preamble/message transmissions before error-free reception i s r 1 V s p c J (4.2.3) Assuming that the number of active users i s known and constant, l e t T be A the mean acquisition time. The average message delays D for Protocols A, B and C are as follows: * p + *A + $ + -rK ' Protoco1 A c D = <| f„ + T. + T 0 + T /P , Protocol B (4.2.4) P A S m c Fp + TE + Tm + ^ - W CW ^ A V C ) ' P R ° T 0 C 0 1 C where T m = £T^ i s the message duration. Furthermore, the channel capacity C i s a decreasing function of the average channel-occupation time (the average time during which an active user occupies the forward channel) which i s given below for each of Protocols A, B and C. 96 f T Q + T A + + ' Protocol A "S ' ~A ' 2^ ' P ''m c T „ 0 = 2T P + T + T /P , Protocol B (4.2.5) CO S A m c ( X + T ) / f p » P o P ) » Protocol C From eqns. (4.2.4) and (4.2.5), comparisons of average delay and channel capacity between Protocols A, B and C can be made as follows: ( i ) Average delay for Protocol A i s less than that for Protocol B and. channel capacity for Protocol A i s greater than that for Protocol B i f T /2 < T_, and conversely, m b ( i i ) Since T > T and P AP C < 1, average delay for Protocol B i s less than that for Protocol C i f T_ < T - f . . b Ci A ( i i i ) S i m i l a r l y , average delay for Protocol A i s l e s s than that for Protocol C unless Tffl i s very large. ( i v ) Note that T < D for Protocol C but the converse i s true for Proto-cols A and B. Therefore i f 2T i s large compared with T - T (e.g. b E A i n cases where a large number of p a r a l l e l correlators are used i n the synchronizer, or In cases where round t r i p delays to a geosynchronous s a t e l l i t e are involved), Protocol C may y i e l d a greater channel capa-c i t y than Protocols A or B. In t h i s case a trade-off between average delay and channel capacity exists i f f g < T g - T A < 2T g. The above discussions serve only as a rough guideline for protocol s e l e c -t i o n . More accurate delay a n a l y s i s , as given i n the following sections, must consider the number of active users as a random v a r i a b l e . Further analysis 97 necessitates the s p e c i f i c a t i o n s of system parameters from which numerical results are obtained. It i s assumed that T = 0 and T = T = 0.01 s e c , ir o K values t y p i c a l for a t e r r e s t r i a l network, and that I > 1000 b i t s . Under such assumptions the a p p l i c a t i o n of Protocol B i s appropriate. .4.3 Delay-Throughput Analysis f o r Protocol B 4.3.1 E f f e c t s of PNR and Delay Components on Total Delay In Section 4.2, average message delay D and average channel-occupation time T are derived for d i f f e r e n t protocols assuming that channel occupancy M i s f i x e d . In r e a l i t y , M varies i n time as users access the channel at random and occupy the channel for a random duration. Thus vari a t i o n s i n M must be taken into account when averaging message delay and channel-occupation time. It i s desirable to express D and as functions of average channel occupancy M so that the average throughput corresponding to a given average delay may be obtained v i a L i t t l e ' s formula [K7], M .= X T C Q (4.3.1) Unfortunately, no simple r e l a t i o n s h i p e x i s t s between D (or -T ) and M because T (and thus D) and M are inter-dependent. I t i s possible to gain some insight into the re l a t i o n s h i p between T and M by examining the e f f e c t s of in d i v i d u a l delays and the PNR l e v e l on T^ as function of M, again assumed to be fixed i n time. Such examinations and subsequent analysis can only be pur-sued using numerical examples. Results w i l l be obtained using system para-98 meters shown i n Tables 2.3.1 and 3.7.1, with V = 1.7, V T = 1.0 and T„ = 0.01 s e c , and assuming co-channel users to be sources of Gaussian noise. Figure 4.3.1 shows a family of T ^ - v s . - M curves at d i f f e r e n t l e v e l s of PNR with K=l. These curves show that T^,Q increases rapidly at a given M when PNR decreases below 60 dB-Hz. On the other hand, increase i n PNR above 80 dB-Hz does not bring about any improvement (decrease) i n . For PNR > 60 dB-Hz, a channel occupancy M q exists such that T ^ i s minimum and i n s e n s i t i v e to changes i n M whenever M<M . When M>M , T„„ increases rapidly with M. The parts of the o o' CO v curve where M<M , M«M and M » M are c a l l e d the " f l a t " , "knee" and "ascent", o o o ' ' r e s p e c t i v e l y . The f l a t of a T -vs . - M curve i s very important for the operation of a SSMA channel because i n this region small fluctuations i n M do not a f f e c t the averages, T and D, and operation of the channel i s therefore stable. On the other hand, at the ascent of a T ^ - v s . - M curve, increases i n M cause T to increase, which causes further increases i n M and T ^ , and so on. Operation of the channel i s therefore unstable. Thus, stable operation of the SSMA channel with the given parameters i s possible only i f PNR > 60 dB-Hz with PNR = 70 dB-Hz being a good operating point. Given the shape of the T ^ - v s . - M curves, i t i s reasonable to suggest that for PNR > 60 dB-Hz; ( i ) T -vs . - M curves have the same shape as the T p -vs . - M curves; ( i i ) the f l a t s of corresponding T -vs . - M and T o r i-vs . - M curves have the same l e v e l , but the knee of the T r n - v s , - M curve 99 . NO. O F A C T I V E U S E R S . M F i g . 4.3.1 Mean channel occupation time vs. number of a c t i v e users M for various PNR values. 100 i s closer to the o r i g i n , i . e . , i t occurs at M <M ; ( i i i ) the ascent of the T„. tt ' ' o o CO -vs.-M curve does not occur i n r e a l i t y because i t corresponds to an unstable channel where M could increase i n d e f i n i t e l y and M i s thus undefined. However, t h i s part of the curve w i l l be included to f a c i l i t a t e discussions on channel s t a b i l i t y i n a l a t e r section. Assuming that T , T and thus T c are independent of M, then T and D, as p K. o CO given i n eqns. (4.2.4) and (4.2.5), are related to M through the delay compon-ents T. and T /P . Figure 4.3.2 gives a comparison between T., T /P and A m c A m c T C Q as functions of M with PNR = 70 dB-Hz and K=l. It shows that both and T ,P are constant with respect to M for small values of M, and increase with M m/ c for large values of M, with T m/P c increasing at a much fas t e r rate than T^. Therefore, the knee and ascent of the T^-vs.-M curve are influenced mainly by T /P . Figure 3.4.2 also shows that with K=l, the l e v e l of the f l a t i s caused m c mainly by T^ which i s about f i v e times T . However, T^ can be reduced to le s s than T i f K>5. m 4.3.2 Delays as Functions of Average Channel Occupancy Assuming that T and T are independent of M, i t i s shown i n Section 4.3.1 P K that T /P i s the main cause for changes of T,,.. and D r e l a t i v e to M. There-in c fore, fluctuations of M i n time do not s i g n i f i c a n t l y change the contribution of T to T calculated using a fixed M, provided that the envelope co r r e l a t o r s of A each synchronizer incorporates some form of automatic gain control which 101 0 100 200 300 400 N O . O F A C T I V E U S E R S . M F i g . 4.3.2 Comparison of contributions of T, and T /P to _ A m c T at d i f f e r e n t l e v e l s of channel occupancy. 102 responses to changes i n M. On the other hand, re-evaluation of T /P to m c account for changes of M about a given average value M i s necessary. When M changes i n time, P £ as given by eqn. (4.2.1) i s no longer v a l i d . Assuming that M does not change within each b i t transmission period T, ( i . e . b X T b « l ) , and l e t t i n g PgCM^) be the b i t - e r r o r p r o b a b i l i t y for the k-th b i t of a message, expressed as function of the channel occupancy during the k-th b i t period, then p c - * [ I - P b ( V ] k=l £ > 1 - I p ( I t ) (4.3.2) k=l * k Let P^( m) D e t n e p r o b a b i l i t y that M=m for a given value of M. Further assume that values of M for adjacent b i t periods are independent. Then the average p r o b a b i l i t y of co r r e c t l y receiving a message i s bounded by P c > 1 - I p g (4.3.3) where 00 p"B = I P M(m) p B(m) (4.3.4) m=l Thus replacing T /P by T /P i n eqns. (4.2.4) and (4.2.5) would account for r o m c m c the fluctuations i n M and res u l t i n expressions for D and T as functions of M. Assuming equality i n (4.3.3), values of D and T thus obtained are some-what pessimistic and result i n a steeper ascent. 103 The above analysis presumes the a v a i l a b i l i t y of the p r o b a b i l i t y d i s t r i b u -t i o n f o r M. Unfortunately, a n a l y t i c a l derivation of Pj^(ffl) i s very d i f f i c u l t because i t involves the i n t e r a c t i o n of d i f f e r e n t random processes i n a complex manner. If T i s constant, then M has a Poisson d i s t r i b u t i o n because the a r r i v a l process i s Poisson. This leads to the hypothesis H that even i f T o CO i s random, the p r o b a b i l i t y d i s t r i b u t i o n of M i s s t i l l Poisson. This hypothesis i s tested by performing x 2 - t e s t s t 0 examine the goodness of f i t between sets of data on frequency of each M value and corresponding sets of frequencies pre-dicted by the Poisson d i s t r i b u t i o n . Data are obtained from computer simula-tions of a disc r e t e model of the system written i n the GPSS simulation language 1 [G4]. Because the simulation runs are time consuming and expensive, only a representative set of parameters (4=1000 b i t s , PNR=70 dB-Hz, K=l, V =1.7, V =1.0, other parameters as given i n Tables 2.3.1 and 3.7.1) i s used, S Li with a r r i v a l rate X ranging from 10 messages/sec. to 1000 messages/sec. In a l l cases considered, r e s u l t s 2 indicate acceptance of H q with a 0.05 l e v e l of s i g -n i f i c a n c e . Therefore, given average channel occupancy M, the p r o b a b i l i t y d i s -t r i b u t i o n for M i s approximately PM(m) = m=0,l,2,««« (4.3.5) *A program l i s t i n g i s given i n Appendix 3. 2Results of goodness of f i t tests are presented i n Appendix 4. 104 The above results are not applicable to the knee and ascent of the T -cu vs.-M curve because here the channel i s a c t u a l l y unstable. Nevertheless, P^( m) as given by eqn. (4.3.5) w i l l be used for computation of the en t i r e T -vs.-M curve so as to determine the p o s i t i o n of the knee. Although t h i s p o s i t i o n i s now subjected to some ambiguity, i t i s expected that t h i s ambiguity i s small. Two families of T^-vs.-M curves for d i f f e r e n t message lengths with K=l and PNR = 60 dB-Hz and 70 dB-Hz are shown i n F i g . 4.3.3. These curves a l l have the same shape. Increasing £ has the e f f e c t of t r a n s l a t i n g a curve towards the upper-left corner, i . e . an increase i n the l e v e l of the f l a t and a decrease i n i t s length, as a r e s u l t of increase i n T m and increasing rate of reduction of P r e l a t i v e to M. T_ -vs.-M curves for d i f f e r e n t values of K with £ = 1024 c CO b i t s and PNR = 70 dB-Hz are shown i n F i g . 4.3.4. Evidently, when K increases to a value at which T.<T , further increases i n K re s u l t s i n i n s i g n i f i c a n t A m ° reduction i n T and are therefore not worthwhile. Note that s i m i l a r D-vs.-M curves may be obtained by subtracting T^-0.01 sec. from the T r n values. 4.3.3 Channel S t a b i l i t y In the immediately preceding two sections i t i s stated that some parts of the T -vs.-M curves do not represent the actual channel behaviour because the channel i s unstable with the r e s u l t that the M values do not e x i s t . An explan-ation of this phenomenon i s offered i n t h i s section by exploring the r e l a t i o n -ships between T -vs.-M curves and the message a r r i v a l rate X. I ! PNR =60.0 DB - H Z K=1 -tr 10 24 BITS 2048 BITS 4096 BITS 81S2 BITS 16384 BITS o CJ UJ CO o LU o I—I I — o c r -Q_ ZD CJ ' LJ O LU CT IE CJ cr LU 51-1 I I I 1 1 1 1 1 0 50 100 150 200 _ 250 RVERRGE NO. OF A C T I V E USERS. M PNR = 70.0 DB - HZ K = 1 1= 1024 BITS 2048 BITS 4 0 9 6 BITS 8192 BITS 16384 BITS I I I I 1 1 1 - 1 1 0 50 100 150 200 _ 250 RVERRGE NO. OF R C T I V E USERS. M F i g . 4.3.3 Mean channel occupation time T vs. average number of ac t i v e users M for various v_<U message lengths 1,. o 106 a O L U CO o u l\-LU CD a:. CL ZD C_J CJ> O cr CE L U I CD 1 PNR =70.0 DB-HZ XV1024 BITS K=1 K=2 K =4 K=8 0 50 A V E R A G E N O n r I i i i i 100 150 200 250 O F A C T I V E U S E R S . M Fi g . 4.3.4 E f f e c t of increasing K on mean channel occupation time T CO* 107 T r_, M and X are related by L i t t l e ' s formula given by eqn. (4.3.1). Given X and an appropriate T^-vs.-M curve, the values of and M s a t i s f y i n g L i t t l e ' s formula are given by the i n t e r s e c t i o n of the T -vs.-M curve with a straight l i n e through the o r i g i n with slope 1/X (assuming scales for both axis are l i n e a r ) . Such intersections can be interpreted as the steady state operat-ing point of the channel. The existence and number of steady state operating points may be c l a s s i f i e d under three possible cases i l l u s t r a t e d i n F i g . 4.3.5. For any given T^-vs.-M curve, a c r i t i c a l a r r i v a l rate X c r exists such that case 1: ^ ^ c r a n <* t h e r e a r e no operating points; case 2: X=X and there i s a unique operating point (M , T ); CJL* J. (_»UX case 3: ^ A c r a n <* there are two operating points, ( ^ j ^QQ2^ a n <* ( M3 ^C03^* The value l / ^ c r Is given by the slope of the l i n e which goes through the o r i g i n and i s tangent to the given T -vs.-M curve. To analyze the channel s t a b i l i t y for the three d i f f e r e n t cases, consider changes of channel occupancy i n time. It i s affected by the rates of a r r i v a l and departure of channel users. If there are M channel users and each spends T^Q sec. i n the channel, the rate of departure i s M/T^. Taking averages, therefore, y i e l d s dM _ .. M . -rr = * (4.3.6) dt -CO Consider M and T i n eqn. (4.3.6) as short term averages and apply the equa-t i o n to the three cases. 108 Tco M CASE T: A> Acr F i g . 4.3.5 Graphical solutions of L i t t l e ' s formula as applied to the SSMA channel for three d i f f e r e n t cases of X values. 109 case 1: A>M/T for a l l M, therefore dM/dt>0 and the channel occupancy increases without bound. The channel i s unstable. case 2: If M^M1, then *>M/TC0 and dM/dt>0. Therefore i f M<M1, then M d r i f t s toward Mj at which point dM/dt=0. However, i f M>Mj, then M increases without bound. The channel i s unstable because any small disturbance that causes p o s i t i v e deviation of the short term M from the operating point may lead to i n s t a b i l i t y . case 3: By the same arguments, the channel i s unstable at operating point (Rj, T c o^) but stable at operating point ( r l , , TQO2^* A T M 3 ' A S M A L I increase i n M causes i t to d r i f t towards i n f i n i t y , whereas at M2, M always converges back to M 2 a f t e r a disturbance causes M to deviate from M2, provided the distrubance i s not large enough to cause M to reach or exceed Mg. The following conclusions may be drawn from the above discussions: ( i ) The channel i s always unstable i f X>\^. ( i i ) Stable operation of the channel i s possible (at least i n the short term) i f X<X^. However, there i s a non-zero p r o b a b i l i t y that d e t e r i o r a t i o n of receiver sign a l to noise r a t i o over a few message durations, caused by a large number of a r r i v a l s , an increase i n noise, or fading, results i n channel i n s t a b i l i t y . An unstable channel i s said to have f a i l e d when average delays approach i n f i n i t y . Although mean time to channel f a i l u r e has been derived f o r sl o t t e d ALOHA channels [K3], s i m i l a r analysis i s not fe a s i b l e for the SSMA channel. One expects that the mean time to channel f a i l u r e i s a decreasing function of 110 the " s t a b i l i t y margin", defined as the distance between M 2 and H^. Thus the SSMA channel may be expected to sustain stable operation for a long period of time i f A « A c r « A c r I s plotted against message length Z with K=l,4,16 and with the l i m i t i n g case where T A=0, i n F i g . 4.3.6 for PNR = 60 dB-Hz and F i g . 4.3.7 for PNR = 70 dB-Hz. Increasing K has the e f f e c t of increasing at small values of Z, but such e f f e c t i s not appreciable at large values of Z. The l i m i t i n g case gives the maximum X for any given T and I. cr o When channel f a i l u r e occurs, both Protocols A and B described i n Section 4.2 have provisions for recovery which require users to take appropriate action i f no acknowledgement i s received within T sec. of accessing the channel. 4.3.4 Delay-Throughput C h a r a c t e r i s t i c s and Channel Capacity A necessary condition for the stable operation of a SSMA channel i s that the average rate of message a r r i v a l at the channel equals the average rate of message departure. Therefore the average throughput S of a stable SSMA channel i s simply S = X messages/sec. (4.3.7) or S = Xfc b i t s / s e c . (4.3.8) The upper bound on S i s c a l l e d the channel capacity C. Since any ^>^cr r e s u l t s i n i n s t a b i l i t y , whereas stable operation i s possible for A<^ c r> t n e channel capacity i s therefore C = X Z b i t s / s e c . (4.3.9) cr Delay-vs.-throughput curves (D-S curves) are obtained by p l o t t i n g the I l l 10 4 10 ; M E S S A G E L E N G T H / ( B I T S ) F i g . 4.3.6 C r i t i c a l values of a r r i v a l rate X vs. message length I with PNR = 60.0 dB-Hz. C r 112 10: 10" 10 5 10' M E S S R G E L E N G T H I ( B I T S ) F i g . 4.3.7 C r i t i c a l values of a r r i v a l rate vs. message length I, with PNR =70.0 dB-Hz. ° 113 average delay D corresponding to a given average channel occupancy M against average throughput S calculated from eqn. (4.3.8) with X = M/T c o (4.3.10) Families of D-S curves for d i f f e r e n t message lengths are shown i n F i g . 4.3.8 with K=l,4 and PNR = 60 dB-Hz, and i n F i g . 4.3.9 with K=l,4 and PNR = 70 dB-Hz. Each of these curves possesses the following general properties: ( i ) A maximum throughput, corresponding to the channel capacity, e x i s t s . ( i i ) The maximum throughput p a r t i t i o n s the curve into two parts, a f i r s t part where average delay i s r e l a t i v e l y constant, and a second part where average delay increases without bound as throughput drops to zero. ( i i i ) The f i r s t part of the curve corresponds to the delay-throughput char-a c t e r i s t i c of the SSMA channel when I t i s stable i n the steady s t a t e . (i v ) The second part of the curve indicates channel i n s t a b i l i t y . When a r r i v a l rate i s too high, the channel follows t h i s curve upward and to the l e f t i n time so that eventually the channel f a i l s . Comparing the d i f f e r e n t curves, the following observations can be made: (1) Average delay D increases with message length I. D increases at a slower rate than Z when % i s small and the a c q u i s i t i o n time and ser-vice time overhead i s s i g n i f i c a n t . When % i s large, D increases at the same rate as %. (2) When the channel i s stable, the average delay i s i n s e n s i t i v e to changes i n the PNR l e v e l , provided these changes do not cause the channel to become unstable. AVERAGE MESSAGE DELAY D (SEC.) 10-' 10° 101 10* 09 4> UJ 00 CU c/> P CO (a & 1— CD I /->. rt o ^ C o c -l-i < CD CO H i O H < PI H H-O C tn CD CO CO cu TO (D (D P OQ rt P4 CO Z H* rt a fa ON o I tn N AVERAGE MESSAGE DELAY D ( S E C . ) 10-* TO-1 10° ] 0 ] o 7*3 O C I Q "D C Z CO, ro 3 CD COOJ \ -m o • 10' I I 1 I I 11ll I I I 1 1 I I 1 i r i rt i n r — i — r i i n n 1—i—i i i i i n 1 — i — i i i i 11 VII F i g . 4.3.9 SSMA delay-vs with PNR = 70 .-throughput curves for various message lengths .0 dB-Hz and (a) K = 1, (b) K = 4 116 (3) When K i s increased, D decreases, but at a decreasing rate. Decreases i n D caused by increases i n K become i n s i g n i f i c a n t when SL or K are large. (4) Channel capacity C increases when PNR i s increased to 70 dB-Hz from 60 dB-Hz. In f a c t , C increases at a decreasing rate for increases of PNR to l e v e l s below 80 dB-Hz, and reaches a constant plateau for PNR > 80 dB-Hz. (5) C increases with K when JI i s f i x e d . Such an increase becomes less s i g n i f i c a n t at large values of SL. (6) For any given values of PNR and K, C can be maximized with respect to SL. Observations (5) and (6) above are further substantiated by F i g s . 4.3.10 and 4.3.11, which show values of channel capacity versus message lengths for K=l,4,16 and for the l i m i t i n g case, TA=0, with PNR = 60 dB-Hz and PNR = 70 dB-Hz, r e s p e c t i v e l y . The l i m i t i n g case gives an upper bound to the achievable channel capacity for given values of PNR, SL and Tg. These figures show that as K i s increased, the optimum SL which maximizes C decreases and the maximum C i s increased u n t i l i t reaches the upper bound given by T =0, at which point the corresponding optimum SL i s the lowest p o s s i b l e . Further decrease i n the o p t i -mum value of SL and increase i n the upper bound for C can only be achieved by decreasing the average service time Tg. The two figures also show that increasing PNR from 60 dB-Hz to 70 dB-Hz re s u l t s i n increases i n both the maxi-mum C and the corresponding optimum SL, for any given K. 117 CD LO U J CO CD I ' I I I I 111 ' I I I I I 11 I I I I 1 I 11 CO s i , , o CO C_) > - - f \— C E ^ Q_ CE C J . CD UJ CE I E C J CD O TA = 0 K = 16 K=4 K = 1 P N R = 6 0 . 0 D B - H Z i — i — i i 11111 1 1 I M i l l 10 : 1—I—I I I I 111 M E S S A G E L E N G T H I ( B I T S ) 10< F i g . 4.3.10 SSMA channel capacity C vs. message length I, with PNR = 60.0 dB-Hz. 118 C E _J I E O CD O I I I I I I I I I I 1,1 I PNR =70-0 D B - H Z i — i — i i 1111 i — i — i i II 111 i — i — i i 1111 10 3 10 4 10 5 M E S S A G E L E N G T H D I B I T S ) 101 F i g . 4.3.11 SSMA channel capacity C vs. message length I, with PNR = 70.0 dB-Hz. 119 The above re s u l t s were obtained assuming users' codes are uncorrelated. If Gold's codes of length L=511 are used, r e s u l t s from Ch. 2 indicate that the above re s u l t s remain v a l i d i f mean channel occupancy, average throughput and channel capacity are reduced by a factor of f i v e . 120 5. COMPARISON WITH OTHER MULTIPLE ACCESS TECHNIQUES 5.1 Introduction Contention multiple access schemes enable a number of users to access a broadcast channel independently without the complexity of c e n t r a l i z e d schedul-ing of dedicated frequency or time s l o t s . Messages are usually assembled into fixed length packets for transmission. The simplest contention scheme allows a user to transmit a packet whenever one i s ready. When one user starts transmitting before another user has f i n i s h e d , a c o l l i s i o n occurs which o b l i t e r a t e both users' packets and retrans-missions are necessary. To minimize the chance of a c o l l i s i o n between the same packets when retransmitting, retransmissions are randomly delayed according to a given delay d i s t r i b u t i o n . Such a multiple access scheme i s know as "pure ALOHA" and i t s system throughput was analysed by Abramson [A4]. In pure ALOHA systems, packet c o l l i s i o n s reduce system throughput, and the maximum throughput or channel capacity i s R/2e where R i s the transmission data r a t e . The p r o b a b i l i t y of packet c o l l i s i o n s i s reduced by half i f a l l trans-missions s t a r t at the beginning of f i x e d time s l o t s whose lengths equal the packet duration. Such a multiple access scheme i s known as "sl o t t e d ALOHA" and i t doubles the channel capacity of a comparable pure ALOHA system. However, global block synchronization becomes necessary and increases system complexity. Delay-throughput c h a r a c t e r i s t i c s and system s t a b i l i t y for s l o t t e d ALOHA mu l t i -ple access have been extensively studied [Kl,K3,L1,C1]. In a l l the analysis cited above, i t i s assumed that received packets are error-free i f they have not encountered any c o l l i s i o n s . This assumption i s 121 v a l i d when bandwidth and hence data rate i s li m i t e d but power i s unlimited, so that a n e g l i g i b l e receiver b i t - e r r o r rate can be achieved. If packets are transmitted i n a wideband channel with l i m i t e d power the above assumption i s usually unreasonable. Unfortunately, delay-throughput analysis for sl o t t e d and pure ALOHA under wideband, limited power situations i s unavailable. In th i s case increasing the data rate increases both the channel capacity and the b i t -error r ate. In addition to packets destroyed by c o l l i s i o n s , packets di s t o r t e d by channel noise are also retransmitted. When the data rate increases to a l e v e l where di s t o r t e d packets cause a s i g n i f i c a n t f r a c t i o n of a l l retransmis-sion t r a f f i c , channel capacity ceases to increase. Thus a maximum channel capacity exists at an optimum data rate. Detailed analysis i s given i n Sec-tions 5.2 and 5.3 for sl o t t e d ALOHA and pure ALOHA, respectively, assuming additive white Gaussian channel noise. This assumption applies to most time-invariant channels. Analysis for other channels can be obtained by s u b s t i t u t -ing for the appropriate message-error rate. Improved channel capacities are achieved by contention multiple access schemes which employ more sophisticated transmission protocols, for example, c a r r i e r sense multiple access [K4] and busy-tone multiple access [ T I ] , Further improvements i n channel capacities are obtained by combining contention and scheduling, as i n split-channel reservation multiple access [T2], With i n -creasing system complexity, channel capacity ultimately approaches that of a perfect scheduling M/D/l queueing channel. In this case channel capacity i s equal to the data rate i f transmissions are e r r o r - f r e e , and somewhat less i f channel errors necessitate retransmissions. Section 5.4 shows that i n wideband 122 power-limited s i t u a t i o n s , an optimum data rate again maximizes the channel capacity. Since SSMA operates with very simple transmission protocols, i t i s reason-able to compare i t s delay-throughput performance against that of ALOHA, the simplest multiple access scheme, and queueing, the ultimate. In Section 5.5, such comparisons are conducted on an equal-bandwidth, equal-single-user-power basis, using the channel model described i n Section 2.2. Because the available bandwidth i s not f u l l y u t i l i z e d by the ALOHA and queueing channels at data rates optimum with respect to the system parameters considered for SSMA, delay-throughput performance of m pure ALOHA, sl o t t e d ALOHA or queueing channels operating i n p a r a l l e l i s also included i n the comparison, where m i s the number of channels that can be f i t t e d into the available bandwidth at optimum data rate. 5.2 Delay-Throughput C h a r a c t e r i s t i c s of a Slotted ALOHA Channel with Additive Gaussian Noise Assume that packets of fixed length Z b i t s are transmitted under s l o t t e d ALOHA using binary PSK at a b i t rate of R bits/second. The channel i s thus pa r t i t i o n e d into time s l o t s of £/R sec. duration. If exactly one packet i s transmitted i n a given time s l o t , then the p r o b a b i l i t y P c of correct recep-t i o n i s as follows, where PNR and p B denote, respectively, the receiver s i g -nal power to noise density r a t i o and the b i t - e r r o r p r o b a b i l i t y : P c = (1 - P B ) * (5.2.1) 123 P B = \ erf c (/¥) (5.2.2) where 2 <» 2 erfc(x) = - t dt (5.2.3) Now consider the general s i t u a t i o n where one or more packets may be trans-mitted i n a given s l o t . Let S denote the channel throughput, G the channel t r a f f i c , and D the average packet delay i n seconds. Both S and G are steady state average values i n packets/slot. To f a c i l i t a t e a n alysis, assume that the system s a t i s f i e s the following conditions: ( i ) A r r i v a l of new packets constitutes a Poisson random process charac-te r i z e d by channel throughput S. ( i i ) Automatic retransmission request (ARQ) error control i s incorporated receiver detects errors i n one or more packet b i t s , with errors caused either by a packet c o l l i s i o n or by random channel noise. A packet c o l l i s i o n always causes a l l packets involved to be blocked. A blocked packet i s retransmitted a f t e r a random delay uniformly d i s -tributed over K s l o t s . Packets transmitted i n a given s l o t are distinguished either as newly generated, or as blocked i n one of K immediately preceding s l o t s . Following the notations i n the throughput derivation for sl o t t e d ALOHA i n [ K l ] , l e t q n be the p r o b a b i l i t y that a newly generated packet i s received without error, and i n packet transmissions. A packet i s said to be blocked i f the q t be the p r o b a b i l i t y that a previously blocked packet i s received without 124 e r r o r . The average number of retransmission u n t i l a packet i s received without error i s C 1 " q n £ - l = _ _ [ i (5.2.4) S q t so that s = i + q ! - q G ( 5 - 2 - 5 ) M t n Consider the event E Q that one of the K immediately preceding s l o t s does not cause a retransmission i n the given s l o t and l e t i t s p r o b a b i l i t y be q Q . This event occurs i f , i n that previous s l o t , no packets were transmit-ted, one packet was transmitted and received without error, or one or more packets were blocked but retransmissions do not occur i n the given s l o t . Assume that packets i n previous s l o t s are generated by a Poisson random process characterized by channel t r a f f i c G. Thus oo m q o - e" G + P cGe" G + (1 - P c ) ( l - I)Ge- G + z e ^ l - I)» - £ = e K + P § e~ G (5.2.6) C K. A packet newly generated i n the given s l o t i s received without error i f the event E Q occurs for each of the K immediately previous s l o t s , the packet i s the only one generated, and t h i s packet i s not dis t o r t e d by channel noise. Therefore q = q K e" S P (5.2.7) n n no c Now consider a previously blocked packet transmitted i n the given s l o t . 125 This packet was blocked i n one of K immediately previous s l o t s , namely the j - t h s l o t . Let E j be the event that the packet transmitted i n the given s l o t i s received without error, E 2 be the event that the packet was blocked i n the j - t h s l o t because of random b i t errors, and E 3 be the event that the packet was blocked i n the j - t h s l o t because of a packet c o l l i s i o n . Since the events E 2 and E 3 are mutually exclusive, the p r o b a b i l i t y of a previously blocked packet being received without error i s q t = Pr(E 1|E 2.UE 3) Pr(E in-E2) • + -Pr(E in-E3) Pr(E 2) + Pr(E 3) (5.2.8) The i n d i v i d u a l p r o b a b i l i t i e s are evaluated as follows: P r ( E 2) = e " G ( l - P c) (5.2.9) P r ( E 3 ) = 1 - e" G (5.2.10) PrCE.AE,) - e " G ( l - P j q * " 1 e~ S P„ (5.2.11) _ G = (e K - e" G) q K _ 1 e" S P (5.2.12) o c Substituting eqns. (5.2.9) to (5.2.12), i n c l u s i v e into eqn. (5.2.8) y i e l d s 126 | e ' K . e - 0 + e - G ( 1 . . .p. ) ]. q.»Tl. <r?.p. ' e-° (1 - P ) + 1 - e"° c = q q K _ 1 e" S P (5.2.13) where q c i s defined as _ G K -G _ e - e P -£ (5.2.14) c , —G _ 1 - e P c Eqns. (5.2.5), (5.2.7) and (5.2.13) constitue a system of non-linear equa-tions from which throughput S may be solved for any given values of K, P c and G. Furthermore, the packet delay D may be calculated from o 1 • - - q - K D = v T + T + [ ( l + T + T ] (5.2.15) 2 m s q^ _ 2 m s where T m = l/R i s the packet transmission time and T s i s the service time including propagation delay and time for acknowledgement. From these c a l c u l a -t i o n s , a delay-vs.-throughput (D-S) curve may be plotted for s p e c i f i c values of £, R, PNR and K. A t y p i c a l set of D-S curves 1 i s shown i n F i g . 5.2.1, where £, R and PNR are fixed and K varies for each curve. The envelope of such a set of curves describes the optimum throughput-delay c h a r a c t e r i s t i c s of a s l o t t e d ALOHA system where K varies adaptively according to the l e v e l of channel t r a f -lIn a l l cal c u l a t i o n s for D, i t i s assumed that T s = 0.01 sec. 127 0.0 0.1 0 .2 0 .3 0 . 4 THROUGHPUT" S (PACKETS/SLOT) F i g . 5.2.1 A t y p i c a l set of sl o t t e d ALOHA delay-vs.-throughput curves showing e f f e c t s of d i f f e r e n t maximum retransmission delays i n K s l o t s . 128 f i c . The maximum throughput for the optimized D-S curve i s c a l l e d the channel capacity C. For fixed values of I and PNR an optimum b i t rate R should e x i s t to maximize the channel capacity C, assuming no bandwidth r e s t r i c t i o n s . This conclusion i s based on the fact that an increase i n R acts d i r e c t l y to increase the throughput; however, i t also causes P c to decrease which acts i n d i r e c t l y to decrease the throughput. Sets of optimized D-S curves 2 depicting the v a r i a -t i o n of delay-throughput c h a r a c t e r i s t i c s and channel capacity with R, for fixed values of Z and PNR, are shown i n F i g s . 5.2.2 and 5.2.3. From these graphs optimum values of R (accurate to two s i g n i f i c a n t d i g i t s ) and the corresponding maximum channel capacities are obtained and tabulated i n Table 5.2.1. F i g . 5.2.4 shows the relationships between packet length l and D-S curves with chan-nel capacities optimized over K and R, at fixed l e v e l s of PNR. Table 5.2.1 and figures 5.2.2 to 5.2.4 i n c l u s i v e , y i e l d the following observations: ( i ) At fixed PNR and % values, there exists an optimum R at which channel capacity i s maximized. 2To f a c i l i t a t e comparisons, throughput i s converted to b i t s / s e c . v i a the r e l a -t i o n S b i t s / s e c . = (S packets/slot)(I bits/packet)/(£/R s e c . / s l o t ) . •JI • . j ->irH cr SLOTTED ALOliA OWiNEL OPTIHI5E0 OVER K PNR • 60D3-HZ ; i » 1024 BITS I R IN KB'SiC. 50 . 100->jJ~ 1 3 0 -1 4 0 -1 5 0 -1 6 0 -175— 2 0 0 -—T-45 (a) 50 o z o (T> LiJ -200 SLOTTED ALOHA CHANNEL OPTIMISED OYER K PNR - 600B-HZ . J. • 2048 BITS T T 10 15 20 25 , 30. _35 THROUGHPUT IN KILOD T-" 1Q1TS/SEC. — T -45 (b) to cr UJ a. c U J -SLOTTED RLOHR CHANNEL OPTIMISED OVER K PNR 60 OB-HZ 8192 BITS o.a —T— 5.0 —I 1 1 1 1 1 1 I • „ IOC 15.0 10.0 21.0 30.0, 35.0 «.0 45.0 50.0 THROUGHPUT IN KILOBITS/SEC. (c) Fig. 5 2 2 E f f e c t s of d i f f e r e n t b i t rates R on s l o t t e d ALOHA delay-vs.^throughput curves optimized over K with PNR = 60.0 dB-Hz and (a) 1 - 1024 b i t s , (b) I = 2048 b i t s , (c) * = 8192 b i t s . Fig. 5.2.3 Effects-of different bit rates R on slotted ALOHA delay-vs.-throughput curves optimized over K with PNR =70.0 dB-Hz and (a)Jl = 1024 bits, (b) I = 2048 bits, (c)I = 8129 bits. _L_ I L « 1024 BITS-L * 20468ITS-£,.» 8132 BITS-SLOTTED ALOHA CHANNEL OPTIMISED OVER K & R PNR - 60DB-HZ - i r 1 1 1 1 i r 50 15 20 25 30 35 40 45 THROUGHPUT IN KILOBITS/SEC. (a) ' 50 "SLOTTED ALOHA CHANNEL OPTIMISED OVER K & R PNR - 70 DB-HZ . CO o O <-Jo-CO - J m H UJ u r n l. « IC24BITS -JU • 20486IT5-' ti - 8192 BITS-- 1 1 1 1 1 1 1 I I 50 100 150 200 250 300 350 400 450 500 • THROUGHPUT IN KILOBITS/SEC. . ( b ) F i g . 5.2.4 Slotted ALOHA delay-vs.-throughput curves for d i f f e r e n t message lengths I, optimized over K and R, with (a) PNR =60.0 dB-Hz, (b) PNR = 70.0 dB-Hz. 132 Table 5.2.1 Optimum Values of B i t Rate R and Corresponding Maximum Channel Capacity C for Slotted ALOHA Channel with Additive Gaussian Noise PNR (dB-Hz) I ( b i t s ) R ( b i t s / sec.) C (bits/sec.) 60.0 1024 1.5 X 10 5 4.82 x l O 4 60.0 2048 1.4 X 10 5 4.37 x lO1* 60.0 8192 1.1 X 10 5 3.72 x 101* 70.0 1024 1.5 X 10 6 4.77 x 10 5 70.0 2048 1.4 X 10 6 4.38 x 10 5 70.0 8192 1.1 X 10 6 3.72 x 10 5 ( i i ) At fixed PNR and X,, for any given l e v e l of throughput less than the channel capacity, there ex i s t s an optimum R, not necessarily the same as i n ( i ) , at which delay D i s minimized, ( i i i ) Time delay D increases without bound as throughput approaches channel capacity, at which point the channel becomes unstable, ( i v ) At a fixed l e v e l of PNR and throughput S, delay increases with packet length. 133 (v) Channel throughput decreases as packet length increases, i f PNR and D are held constant. 5.3 Delay-Throughput C h a r a c t e r i s t i c s of a Pure ALOHA Channel with Additive Gaussian Noise Let T m = i/R be the packet transmission time under pure ALOHA, where X, i s the packet length and R i s the transmission b i t rate. A given packet i s blocked either by c o l l i s i o n with another packet transmitted within ±T m sec. (the vulnerable period) of the st a r t of transmission of the given packet, or as a r e s u l t of Gaussian channel errors i n the received packet. Assume that a blocked packet i s retransmitted a f t e r a delay of T s + T sec. from the time of transmission of i t s l a s t b i t , where T s i s again the packet service time including propagation delay and acknowledgement time, and x i s a uniformly d i s t r i b u t e d random variable between 0 and T r s e c 1 . Given the received power to noise density r a t i o PNR, b i t rate R and packet length Si, pg and P c are again given by eqns. (5.2.1) and (5.2.2). Assume that new packets are generated by a Poisson random process with parameter Aj. Therefore, average steady state channel throughput S = X, T (5.3.1) 1 m Consider a user who starts transmitting a packet at time t Q . D i s t i n -1 Assume T r > 4 T, 134 gulshing this packet as either newly generated or previously blocked, l e t q n be the p r o b a b i l i t y that a newly generated packet i s received without e r r o r , and q t be the p r o b a b i l i t y that a previously blocked packet i s received without e r r o r . No attempt i s made to further d i s t i n g u i s h previously blocked packets as new packets or retransmissions. They are assumed to be generated by a Poisson process with parameter X 2 such that average channel t r a f f i c G = X„ T (5.3.2) 2 m The average number of retransmission u n t i l a packet i s received without error i s again G 1 " q n § - 1 = n (5.3.3) S q t so that q t G S = 1 + a - q ( 5 ' 3 - 4 ) t M n The p r o b a b i l i t y q n i s derived as follows. The "vulnerable period" i s the time i n t e r v a l (t -T , t +T ) i n which i n i t i a t i o n of any other packet trans-o m o m J t-missions causes a c o l l i s i o n with the packet which begin transmission at t Q . A newly generated packet i s successfully received i f and only i f the following events j o i n t l y occur: E : no other new packets are generated i n the vulnerable period; 3. E, : no retransmissions of previously blocked packets begin i n the b vulnerable period; and E c : channel noise does not cause any b i t e r r o r s . The p r o b a b i l i t i e s f o r E and E are as follows: a c 135 Pr(E ) = e 2 X l T m = e 2 S (5.3.5) a Pr(E ) - P (5.3.6) c c The derivation of Pr(E^) i s more involved. Assume that transmission of a packet started at time t and was blocked. Retransmission of th i s packet may s t a r t within the vulnerable period i f the i n t e r v a l (t+T +T , t+T +T +T ) J m s m s r overlaps with the vulnerable period, as shown i n F i g . 5.3.1. Thus the sole cause of retransmissions started i n the vulnerable period i s blocked transmis-sions generated i n the i n t e r v a l (t -T -T -2T , t -T ). P a r t i t i o n t h i s time ° o s r m o s i n t e r v a l into subintervals of equal length At and l e t At approach zero. Theories of Poisson processes s t i p u l a t e p r o b a b i l i t i e s i n each subinterval as follows: ( i ) A 2At that one new or previously blocked packet was generated; ( i i ) l-X 2At that no packet was generated; and ( i i i ) a n e g l i g i b l e p r o b a b i l i t y that two or more packets were generated. Let p(t) be the p r o b a b i l i t y that a subinterval at ( t , t+At) does not cause a retransmission i n the vulnerable period. Then Pr(E v) = n p(t, ) , t -T -T -2T <t. <t -T b , k o s r m k o s k = exp{£ In [p(t, )]} (5.3.7) k fc where ln(x) denotes the natural logarithm of x. Considering the amount of overlap i n F i g . 5.3.1, PARTIAL 1 ,PARTIAL r * " NO OVERLAP NO OVERLAP «•*—| OVERLAP 1 COMPLETE OVERLAP 1 OVERLAP WITH 1 WITH | WITH . WITH • WITH VULNERABLE PERIOD •VULNERABLE VULNERABLE PERIOD VULNERABLE VULNERABLE PERIOD 1 1 | 1 PERIOD I PERIOD 1 | r"^ m p urn 1 1 in m 1 1 i i 1 t t+T t+T +T t+T +T +T i m m s m s r PACKET TRANSMITTED AND BLOCKED RETRANSMISSION OF BLOCKED •PACKET STARTS WITHIN THIS-TIME INTERVAL F i g . 5.3.1 Comparison between the time period i n which retransmission of a packet, previously blocked at time t , may begin and the vulnerable period of a new transmission at time t ^ . The extent of overlapping of the two time periods i s proportional to the p r o b a b i l i t y that the two packets c o l l i d e . 137 f l - X 0 A t ( l - e P ) ( t -t-T )/T , t -2T -T <t<t -T 1 2 c o s r ' o m s o s p(t) = -J l - X n A t ( l - e ~ 2 G P )2T /T , t - T -T <t<t -2T -T y 1 2 c m r o s r o m s ll-X„At(l-e P )(t+2T +T +T - t )/T , t -2T -T -T <t<t -T -T 2 c m s r o r ' o m s r o s r (5.3.8) Since ln(l+x)sc for x « l and At approaches zero, ln[p(t)]" = —9C - X 9 A t ( l - e P„)(t -t-T )/T , t -2T -T <t<t -T 2 c o s r o m s o s —9C -X„At(l-e P )2T /T , t -T -T <t<t -2T -T 2 c m r ' o s r o m s l-X„At(l-e~ 2 GP )(t+2T +T +T - t )/T , t -2T -T -T <t<t -T -T 2 c m s r o r o m s r o s r (5.3.9) The function - l n [ p ( t ) ] / A t i s shown gra p h i c a l l y i n F i g . 5.3.2. The area under - l n [ p ( t ) ] / A t i n the j - t h subinterval i s simply - l n [ p ( t ^ ) ] . Hence - £ l n [ p ( t ^ ) equals the area under the trapezoid i n F i g . 5.3.2, and — 9 f E ln[p(t, )) = -X,(l-e P„)2T , k 2 c m k —or = -2G(l-e P ) (5.3.10) c Therefore, Pr(E, ) = e D -2G(l-e 2 G P ) c (5.3.11) and the p r o b a b i l i t y of a newly generated packet being received without error i s In p(t) SUBINTERVAL I SUBINTERVAL j • SUBINTERVAL k Fi g . 5.3.2 {-In p(t)}/At vs. t; p(t) i s the p r o b a b i l i t y that events occuring i n the time i n t e r v a l ( t , t+At) do not cause a retransmission within the vulnerable period of a packet transmitted at time t n . 139 q = Pr(E )Pr(E, )Pr(E ) n a b c - 2 G ( l - e _ 2 G P ) = e e C P (5.3.12) c To derive the p r o b a b i l i t y q n, assume that a packet was transmitted at time t ^ and was blocked, and that retransmission occurs at time t Q . The block-age at t j resulted from one of two mutually exclusive events. E^: a c o l l i s i o n occurred, i . e . one or more ad d i t i o n a l packets were transmitted within the time i n t e r v a l (t^T,,, , t j + T ^ ; E 2 : no a d d i t i o n a l packets were transmitted i n the time i n t e r v a l (tj-Tm, t ^Tflj) but one or more b i t - e r r o r s were detected i n the received packet. From the retransmission delay d i s t r i b u t i o n , t 1 i s constrained within the time i n t e r v a l ( t 0 - T s - T r - T m , t 0 - T s - T m ) . Define the event E 3 : no previously blocked packets (except the one transmitted at t^) begin retransmission i n the vulnerable period. Let I, denote the time i n t e r v a l (t -T -T -2T , t -T ) and I„ denote the time 1 o s r m ' o s 2 i n t e r v a l ( t j - T , t 1 + T m ) . Note that I j includes I 2 . Again p a r t i t i o n II into subintervals of equal duration At. If a subinterval (t,t+At) does not f a l l within I 2 , the p r o b a b i l i t y p(t) that this subinterval does not cause a retrans-mission i n the vulnerable period i s given by eqn. (5.3.8). For t e I 2 , t h i s p r o b a b i l i t y i s modified as follows: 140 (p(t)|E 1,t£l 2)= l - [ X 2 / ( l - e - 2 G ) ] A t ( V t - T s ) / T r , t o-T s-2T m<t<t o-T s l - [ X 2 / ( l - e " 2 G ) ] A t 2T m/T r,t o-T s-T r<t<t o-T s-2T m l - [ X 9 / ( l - e - 2 G ) ] A t ( t + 2 V T s + T r - t o ) / T r , t o - T s - T r - 2 T m < t < t o - T s - T r 1 (5.3.13) (p(t)|E t e l j = 1 (5.3.14) Taking natural logarithm and l e t t i n g At approach zero y i e l d s -2GS l n ( p ( t ) | E 1,teI 2) = \ - t X 2 / ( l - e — ) ] A t ( t o - t - T s ) / T r , t o - T s - 2 T m < t < t o - T s - [ X 2 / ( l - e - 2 G ) ] A t 2T m/T r,t o-T s-T r<t<t o-T s-2T m L - U 2 / ( l - e - 2 G ) ] A t ( t + 2 T m + T s + V t o ) / T r , t o - T s - T r - 2 T m < t < t o - T s ^ (5.3.15) ln ( p ( t ) | E ,tel„) - 0 (5.3.16) Conditioned on t . , the p r o b a b i l i t y ( q j t , ) = e " P . Pr(E. E.U E ) t 1 c J 1 I (5.3.17) where P r ( E 3 | E 1 U E 2) = Pr(E i n E 3) + P r ( E 2 O E 3 ) Pr(E 1) + Pr(E 2) (5.3.18) Evaluating each term i n eqn. (5.3.18) y i e l d s P r ( E 1) = l - e ~ 2 G (5.3.19) 141 Pr ( E 2 ) = e 2 G ( 1 - P C ) (5.3.20) Pr(E.nE-) = P (E_|E 1)Pr(E.) (5.3.21) 1 3 r 3 1 • 1 P r ( E 2 H E 3 ) = P r ( E 3 | E 2 ) P r ( E 2 ) (5.3.22) Furthermore Pr(E |E ) = n p(t) n ( p ( t ) | E 1 ) subintervals subintervals e l r l 2 e I 2 exp { Z In p(t) + E In (p( t ) | E 1 ) } (5.3.23) subintervals subintervals e l r l 2 e I 2 P r ( E 3 | E 2 ) = exp { Z In p(t) + Z In (p ( t ) | E ? ) } (5.3.24) subintervals subintervals Fi g . 5.3.3 and F i g . 5.3.4 show how the summations i n eqn. (5.3.23) and eqn. (5.3.24) are evaluated f o r d i f f e r e n t values of t j . For the three range of t p the following r e s u l t s are obtained: Case 1: t -T -T -T <t,<t -T -T +T o s r m l o s r m __ r G e " 2 G [ l + P ^ l - e " 2 G ) ] ( t f t - t . ) 2 - l n P r ( E 3 | E l ) = 26( l - e " 2 G P c ) + {- \ T m T r ( l - e ) ^ V V ^ V V + 4 Tm 2 - I ( T s + V T m ) 2 } ( 5 ' 3 ' 2 5 ) CASE 1 : t_-T -T -T < t n < t n - T -T +T O s r m 0 O s r m 142 Ps(l-e-2GP )2T /T '2 c m ' \ AREA = -In Pr(E /E,) 1-Tm t h fcl+Tm t_-T -T -2T t_-T -T O s r m O s r t_-T -2T t_-T 0 s m 0 s CASE 2 : t n - T -T +T < t. < t n - T -3T O s r m 1 O s m t - T -T -2T t -T -T O s r Q s r t_-T -2T t n - T O s m 0 s CASE 3 : t~-T -3T < t, < t_ -T -T O s m 1 O s m A 02T 2 m (l-e-2V / " —Or X (l-e P )2T /T 2 c m i / / AREA = -In P r ( E 3 / E 1 ) t.-T 1 m t„-T -T -2T t.-T -T O s r m O s r t. f t + T 1 J 1 m t_-T -2T t_-T 0 s m . 0 s F i g . 5.3.3 Graphical evaluation of :.^ln{Pr(E„/E ) } CASE 1 : t _ - T - T - T .< t. < t„- T - T + T 0 s r m 1 0 s r m A„(l-e )2T /T 2 c m r SHADED AREA = -In P r ( E 3 / E 0 ) t -T -T -2T 0 s r m t.-T -T 0 s r t n - T -2T t n - T 0 s m 0 s CASE 2 : t„- T -T +T < t. < t„- T -3T O s r m 1 O s m SHADED AREA = -In Pr(E /E ) A M-e Z ° P )2T /T J 2 c m r •t.-T t. t. 1 m 1 1 t.-T -T -2T t n - T -T 0 s r m 0 s r t_-T -2T O s m 0 s CASE 3 : t„- T - 3T < t. i: t_-T -T 0 s m 1 - 0 s m SHADED AREA = —? r A„(l-e P )2T /T / c m r -ln P r ( E 3 / E 2 ) t -T -T -2T t n - T -T 0 s r m 0 s r t.-T t, t.+T t 1 m 1 1 m t n - T -2T t_-T O s m 0 s F i g . 5.3.4 Graphical evaluation of -ln{Pr(E /E )'•} 144 _ „ r G(l-e 2 G P c ) ( t - - t j ) 2 -lnPr(E |E2) = 2G(l-e Z U P £ ) t 2 m r + (T +T -T ) ( t -t.) + 4T 2 - ^ (T +T -T ) 2} (5.3.26) s r m o l m I s r m J Case 2: t -T -T +T <t,<t -T -3T o s r m l o s m _. r 4Ge 2 G [ l + P - ( l - e 2 G ) ] T m -lnPr(E_|E 1) = 2G( 1-e 2 G P ) + ^ - (5.3.27) 3 1 C T [1-e Z G ] r - l n P r ( E 3 | E 2 ) = 2G(1-e 2 G P c ) - 4G(1-e ^ P J T L / T . (5.3.28) Case 3: t -T -3T <t.<t -T -T o s m 1 o s m -lnPr(E 0|E 1) = 2G(1-e 2 G P ) + (G/T T )[e 2 G / ( l - e 2 G)][1+P (1-e 2 G ) ] 3 1 c m r c {- (t - t , ) 2 / 2 + (T +3T ) ( t -t.) + 4T 2 - ( T +3T ) 2/2} (5.3.29) o l s m o l m s m - l n P r ( E 3 | E 2 ) = 2G(l-e 2 G P c ) - (G/TMT^K 1-e 2 G P c ) {- ( t Q - t 1 ) 2 / 2 + ' V W ' l * + 4 Tm 2 " ( T s + 3 T m ) 2 / 2 > ( 5 - 3 ' 3 0 ) Let -2G(l-e~ 2 GP ) f (G) = e ° (5.3.31) 145 f 2 ( G ) = Ge" 2 G[l+P ( l - e ~ 2 G ) ] c T T ( l - e " 2 G ) m r (5.3.32) G ( l - e " 2 G P ) f 3(G) = T T C m r K = T +T -T 1 s r m K = T +3T 2 s m (5.3.33) (5.3.34) (5.3.35) Then ( f (G)exp(-f (G)[- i-(t - t -KJ 2+4T 2 ] } , t -K.-2T <t.<t -K, J- / o i l m o l m l o l Pr(E |E ) = ^ f (G)exp{-4T 2 f 9 ( G ) } , t -K,<t.<t -K 0 J i i m z o 1 1 o 2 .f 1(G)exp{-f 2(G)[- l ( t o - t r K 2 ) 2 + 4 T m 2 ] } , t ^ t j ^ - y a , , (5.3.36) Pr(E 3|E 2)= <{ f f 1 ( G ) e x p { f 3 ( G ) [ - } ( t 0 - t 1 - K 1 ) 2 + 4 T m 2 ] } , t ^ - l T ^ t ^ f 1 ( G ) e x p { 4 T m 2 f 3 ( G ) } , t ^ K ^ t ^ t ^ | f ( G ) e x p { f , ( G ) [ - Ut -t.-K 9) 2+4T 2 ] } , t -K_<t <t -K +2T (5.3.37) 1 3 2 o 1 2 m o z l o z m and 146 e " 2 S P c [ ( l - e " 2 G ) P r ( E 3 | E 1 ) + e Z U(l-P c>Pr(E 3JE,,)] -20,, l-e" 2 GP (5.3.38) The p r o b a b i l i t y that a previously blocked packet i s received without error i s qt-J (qJV f T / t 1 ) d t 1 -oo 1 (5.3.39) where f T ( t ^ i s the pdf for ^ given by r 1/T , t -T -T -T <t <t -T -T \ r o s r m l o s m f T x ( t l ) = < 0 , elsewhere (5.3.40) The f i n a l r e s u l t i s therefore q t = e- 2 SF(G,P c,T m,T s,T r) (5.3.41) where, with ( t o - * ^ ) = T» -2G„ F(G,P ,T m,T s,T r) = { P / ^ O / f T ^ l - e P c) ] } { ( l - e ~ 2 G ) e x p [ - 4 T m 2 f 2 ( G ) ] [ T r - 4 T m K +2T + / 1 m e x p ( f (G)(x-K ) 2/2)dx K l 147 + / 2 exp(f (G)(x-K ) 2/2)d T] V 2 T m z m + e 2 G ( l - P c ) e x p [ 4 T m 2 f 3 ( G ) ] [ T r - 4 T m K +2T + / 1 m exp(-f (G)(x-K ) 2/2)dx K l K_ 2 + J ' exp(-f (G)(x-K ) /2)dx]} (5.3.42) K 9 ~ 2 T m 2 Letting T1 = T-KJ , x 2 = x-K 2 > and X q = Xj = x 2 i n eqn. (3.5.42) yields 2GT F(G,P c,T m,T s,T r) = { P ^ ^ O / t ^ d - e P £) ] } {(1-e 2 G ) e x p [ - 4 T m 2 f 2 ( G ) ] [ T r - 4 T m 2T + / m exp(f (G)x 2/2)dx ] -2T 2 ° m + e 2 G ( l - P c ) e x p ( 4 T m 2 f 3 ( G ) ] [ T r - 4 T m 148 2T + / m exp(-f (G)x 2 / 2 ) d T o ] } (5.3.43) -2T ° ra Expressing T r as T r=KT m > K>4 and l e t t i n g x = x 0/T m, yi e l d s s i m p l i f i -cations as follows to eqn. (5.3.43): -2G(1-P ce- 2 G) - 4 G e - 2 G [ l + P c ( l - e - 2 G ) ] F(G,P c,T m,T s,K) = P ^ ( i _ p e . 2 G ) { ( l - e " 2 G ) e Ge 2 G[1+P (1-e 2 G ) ] 2 C X 2 ~ =2G~ 2 [ K _ 4 + J e K ( 1 " 6 > dx] + -2 4G(1-P c 2 G ) -G(l-P ce 2 G ) x2 -2G,. _ N K r„ ,, ? _ K 2 e " 2 G ( l - P j e [K-4+ / e * dx] (5.3.44) -2 where function F i n eqn. (5.3.41) i s replaced by F. Since solution to the x t 2 i n t e g r a l j e dt i s not available i n closed form, the integ r a l s i n eqn. o (5.3.44) must be evaluated using numerical methods. It i s i n t e r e s t i n g to note that for K-x», the above results converge to those obtained using the Poisson assumption for channel t r a f f i c , i . e . S = Ge" 2 GP (5.3.45) c From eqns. (5.3.40) and (5.3.43) i t follows that 149 "2G(l-e 2 G P ) l i m q = e " 2 S P e ° = q (5.3.46) K-H» H t c M n and —2G lim S lim -2S W ~ 2 G ( 1 - e P c ) — = rr = q = e P e (5.3.47) By d i r e c t s u b s t i t u t i o n , i t can be confirmed that eqn. (5.3.45) i s a so l u t i o n of eqn. (5.3.47). Given a set of values for G, P , T , T and T (or K ) , the variables S, ' e m ' s r * ' q n and q t may be solved from a system of non-linear equations given by eqns. (5.3.4), (5.3.12) and (5.3.41). The corresponding average packet delay D i s given by ( l - q n ) D = T + T + — (T + T + T /2) (5.3.48) m s q f c m s r Using the r e s u l t s derived above, a delay-vs .-throughput (D-S) curve maybe plotted f or given values of PNR, R, £., T s and K . Assuming Tg=0.01 s e c , a t y p i c a l family of D-S curves for various K with fixed PNR, R and I i s shown i n F i g . 5.3.5. The envelope described by these curves represents the optimum throughput-delay c h a r a c t e r i s t i c s of a pure ALOHA channel where K varies adap-t i v e l y according to the l e v e l of channel t r a f f i c . If the usable b i t rate i s not l i m i t e d by channel bandwidth, the through-put-delay c h a r a c t e r i s t i c s can be further optimized over the b i t rate R by maxi-mizing the channel capacity C (the maximum achievable throughput corresponding to the v e r t i c a l portion of the envelope) or a l t e r n a t i v e l y by minimizing the 150 o C E _J L U Q LU CD oz-jL L U o PNR =70.0 DB - HZ 2 = 1 0 2 4 BITS R =10MBITS/SEC K= 300 -150 T T T 0.0 0.0 0.1 0.3 0.2 THROUGHPUT S (PRCKETS/TM SEC.] F i g . 5.3.5 A t y p i c a l set of pure ALOHA delay-vs.-throughput curves showing e f f e c t s of d i f f e r e n t maximum retransmission delays i n KT sec. J m 151 time delay at a given l e v e l of channel throughput. Thus from each graph i n Figs . 5.3.6 and 5.3.7 the channel capacity i s v i s u a l l y optimized with respect to R and the re s u l t s (accurate to two s i g n i f i c a n t d i g i t s ) are tabulated i n Table 5.3.1. The e f f e c t of d i f f e r e n t message lengths on the throughput-delay c h a r a c t e r i s t i c s (the D-S curves with C maximized are used) i s i l l u s t r a t e d i n F i g . 5.3.8. These graphs show that throughput-delay c h a r a c t e r i s t i c s of pure ALOHA are s i m i l a r to that of s l o t t e d ALOHA. S p e c i f i c a l l y , the observations i n Section 5.2 regarding F i g s . 5.2.2 to 5.2.4 are also applicable to Fig s . 5.3.6 to 5.3.8. Comparing Table 5.3.1 with Table 5.2.1, channel capacities for both pure ALOHA and s l o t t e d ALOHA are maximized at the same b i t rate at given values of PNR and £, and the maximum channel capacity for pure ALOHA i s approximately half that of sl o t t e d ALOHA. 00 U i U> 0> w H- Hi r t i-h (D O in r t CO O II i-h ON P . O H-• Mi o Mi ro H w CD 1 P w r t N cr p p r t H — fu r t ft> CO «•= II o h-' p o J> p H cr H* T t CD l# o -^—* > cr •—' p. CD M n ho is o CO J> • 00 1 r t cr P * H- H r t o CO p v OP p* / - N * P o p r t O P II H < 00 (T) h-' CO <D O -d cr r t H- H-r t 3 CO H-• N (D Cu O < CD K 7i o Co cnui m rvs. T !MF CELRY IN MILLISECONDS 3 10' 5 10" S ' i • • •' l i t I i i i i I 1 >—i—J— 5° o r-CO-t n u i m TIME CELRY IN MILLISECONDS S 10' 5 10' ' . i. . i 1 1 1 I.I I I I I L 10* i 111 IVJ CT) t— o o o Ji X CD O D O XI o Co Si"" HO' toot TIME DELAY IN MILLISECONDS 5 !0' 5 10' ' . . . . i • • i . . . . i L I * -o c m it II 3) Q en r~ o a CO X D x> CD 00 1 o X X Xl C/l 1^ 2: m r* o —* cn a o -:: m F i g . 5.3.7 E f f e c t s of d i f f e r e n t b i t rates R on pure ALOHA delay-vs.-throughput curves optimized over K with PNR = 70,0 dB-Hz and (a) I = 1024 b i t s , (b) £ = 2048 b i t s , (c) I = 8192 b i t s . Ln I 1 I I I I I I I PURE ALOHA CHANNEL OPTIMISED OVER K X, R PNR = 60 DB-HZ 0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 20.0 THROUGHPUT IN KILOBITS/SEC. (a) 22.5 25.0 m-l CO o •z. o OS,. UJ.-1 to >-ex _J L U a „ c LU' i J i i • i ; I i L_ i PURE ALOHA.CHANNEL OPTIMISED OVER K I R PNR = 70 DB-HZ I I I 1024 BITS-2048 BITS-8192 BITS-0.0 25.0 T T 1 I 1 I 50.0 75.0 100.0 125.0 150.0 175.0 200.0 225.0 250.0 THROUGHPUT IN KILOBITS/SEC. F i g . 5.3.8 Pure ALOHA delay-vs.-throughput' curves for d i f f e r e n t message lengths : with (a) PNR = 60.0 dB-Hz, (b) PNR = 70.0 dB-Hz. . (b) '• optimized over K and R, 155 Table 5.3.1 Optimum Values of B i t Rate R and Corresponding Maximum Channel Capacity C for Pure ALOHA Channel with Additive Gaussian Noise PNR(dB-Hz) Jt(bits) R(bits/sec.) C(bits/sec.) 60.0 1024 1.5 x 10 5 2.42 x I0h 60.0 2048 1.4 x 10 5 2.19 x 10^ 60.0 8192 1.1 x 10 5 1.86 x 10 4 70.0 70.0 70.0 1024 2048 8192 1.5 x 10 6 1.4 x 10 6 1.1 x 10 6 2.42 x 10 5 2.20 x 10 5 1.87 x 10 5 5.4 Delay-Throughput C h a r a c t e r i s t i c s of a Queueing Channel with Additive Gaussian Noise Consider a Gaussian noise channel serving a user population on a f i r s t -come-first-served basis and with perfect scheduling of transmission time so that no c o l l i s i o n may occur on the channel. Assume messages have fixed length of SL bits/message and a r r i v a l of new messages constitutes a Poisson process with aggregate a r r i v a l rate X messages/sec. Given the received signal-to-noise 156 density r a t i o PNR and the transmission b i t rate R, message b i t s are received with b i t - e r r o r p r o b a b i l i t y p R given by eqn. (5.2.2) and the p r o b a b i l i t y P c of error-free reception of a message i s given by eqn. (5.2.1). A transmitted message i s retained i n a buffer at the transmitter u n t i l a p o s i t i v e acknowl-edgement of er r o r - f r e e reception i s received. If a negative acknowledgement i s received, the message rejoins the queue with a p r i o r i t y higher than that f o r new messages. The channel therefore constitutes a two p r i o r i t y c l a s s , head-of-the-l i n e M/D/l queue and the analysis i n Section 3.6 of [Kl] i s applicable. Let XJJ and Xj. be the a r r i v a l rate of new and retransmitted messages, respectively, and assume a r r i v a l s of new and retransmitted messages are Poisson and independent. Therefore ^ = X (5.4.1) and GO n=l Define the channel u t i l i z a t i o n f a c t o r p as p = X T (5.4.3) m where T m = S./R i s the message duration. Therefore, the channel u t i l i z a t i o n factors p n and p r for new and retransmitted messages are, respectively, p = XT (5.4.4) n m p = XT (l-P )/P (5.4.5) Define 157 a - P + P = XT /P (5.4.6) n Hn K r m c 0 = p = XT (l-P )/P = f l - P )a (5.4.7) r r cJ c ^ cJ n Then Cobham's r e s u l t i n Section 3.6 of [Kl] gives the following s o l u t i o n to the average waiting time and Wr for new and retransmitted messages, respec-t i v e l y . o W ° (5.4.8) W n = [1-oJU-oJ Wr - (5.4.9) W q i s the average residual transmission time for a message transmission i n progress when another message j o i n s the queue, and Is given by T 2 XT 2 *o " - f " = I T - ( 5 - 4 ' 1 0 ) c The average delay D for error-free reception of a message i s therefore D = W + (T + W + T ]/P - ff + W ) (5.4.11) n ^ s r m-'c v s r 1 where T g i s the average service delay, including round-trip propagation time and acknowledgement delay. Waiting time W r and hence D become unbounded as X approaches P /T and a approaches one. When D i s f i n i t e , the corresponding c m n average throughput S i n b i t s / s e c . f o r a given X i s 158 S = X T R m X < P /T c i m (5.4.12) When D i s i n f i n i t e , S reaches i t s maximum value known as the channel capacity C which i s given by Curves of D-vs.-S are plotted for the queueing channel discussed above f or various R values, with £=1024, 2048 and 8192 bits/message i n Fi g s . 5.4.1 and 5.4.2, where PNR = 60 dB-Hz and 70 dB-Hz, re s p e c t i v e l y . These graphs show that i f R i s not constrained (e.g. by the available bandwidth), then as i n ALOHA channels, channel capacity C i s maximized at an optimum value of R for any given PNR and I. Optimum values of R (accurate to two s i g n i f i c a n t d i g i t s ) and corresponding maximum value of C are tabulated i n Table 5.4.1 for PNR = 60 and 70 dB-Hz and Si = 1024, 2048 and 8192 bits/message. The relationships between D-vs.-S curves with maximized channel capacity and d i f f e r e n t message lengths are shown by two graphs i n F i g . 5.4.3 for PNR = 60 and 70 dB-Hz, res p e c t i v e l y . C = P R (5.4.13) c Ln Ml pd Mi (1) II o rt cn CD O • o O a* O* UJ, i i-n N ro n O rt —* cr 03 H-rt *=> >-{ CO II rt to CO o ro pd •P-o cr rt CO -/—. i—• cr .Q c >= fo c II cc ro 3 O 09 •P-oo (t) cr M H- cu rt cn 1 < CO • o 1 rt *° Pf II ti CP 03 P4 '-D ro rt cr O H-(T i-i CO < • to CO t. rt pr (a) (b) (c) F i g . 5.4.2 Effects of different bit rates R on M/D/l queueing delay-vs.-throughput curves with PNR = 70.0 dB-Hz and (a) JI = 1024 bi t s , (b) I = 2048 b i t s , (c) I = 8192 b i t s . i—» ON o M/D/1 Q U E U E P N R = 7 0 . 0 D B - H Z I = 1 0 2 4 B I T S -£ = 2 0 4 8 B I T S -l =S192BITS -— i 1 1 1 1 1 r 0 .0 0 . 4 0 . 8 1.2 THROUGHPUT S (MB!TS/SECJ (a) 1.6 U o >-5*2" UJ a LU CD UJ > cr M / D / 1 Q U E U E P N R = 6 0 . 0 D B - H Z I = 1 0 2 4 B I T S -l = 2 0 4 8 B I T S -l = 8 1 9 2 B ! T S -T 1 i 1 r 0 . 0 4 0 . 0 8 0 . 0 1 20 . 0 ; THROUGHPUT S (KBITS/SEC.) (b) F i g . 5.4.3 M/D/l queueing'delay-vs.-throughput curves f o r d i f f e r e n t message lengths £, with (a) PNR = 60.0 dB-Hz, (b) PNR = 70.0 dB-Hz. 160 162 Table 5.4.1 Optimum Values of B i t Rate R and Corresponding Maximum Channel Capacity C for M/D/l Queueing Channel with Additive Gaussian Noise PNR (dB-Hz) £ ( b i t s ) R (bits/sec) C (bits/sec) 60.0 60.0 60.0 1024 2048 8192 1.5 x 10 5 1.4 x 10 5 1.1 x 10 5 1.31 x 10 5 1.19 x 10 5 1.01 x 10 5 70.0 70.0 70.0 1024 2048 8192 1.5 x 10 6 1.4 x 10 6 1.1 x 10 6 1.31 x 10 6 1.19 x 10 6 1.01 x 10 6 Comparison with the re s u l t s i n Sections 5.2 and 5.3, shows that the delay-throughput c h a r a c t e r i s t i c s for M/D/l queueing channel are s i m i l a r to those of pure and sl o t t e d ALOHA channels optimized over retransmission delay d i s t r i b u -t i o n . Thus observations ( i ) to (v) stated i n Section 5.2 are applicable to the queueing channel, with the exception that although delay becomes unbounded when throughput approaches channel capacity, the queueing channel does not become unstable as do ALOHA channels. It i s also of in t e r e s t to note that, given PNR and i values, the b i t rates which maximize channel capacities are the same for queueing, s l o t t e d ALOHA and pure ALOHA, and the corresponding maximum channel 163 capacities for these multiple access schemes have the r a t i o of l : l / e : l / 2 e approximately, which i s the same as the capacity r a t i o for these schemes operating i n a noiseless channel. Channel noise a f f e c t s the three multiple access schemes i n a way which leaves t h e i r r e l a t i v e performance unchanged. 5.5 Comparison of Delay-Throughput C h a r a c t e r i s t i c s Between SSMA, Pure ALOHA, Slotted ALOHA and Queueing Channels In this section, delay-throughput c h a r a c t e r i s t i c s of SSMA, pure ALOHA, slotte d ALOHA and queueing channels are compared under the conditions that messages of equal length £ are transmitted i n a l l multiple access channels with equal single user power to noise-density r a t i o PNR and equal a v a i l a b l e trans-mission bandwidth B t. These multiple access channels are assumed to conform to the channel model presented i n Section 2.2, that i s , each channel connects the user population to a central node i n a star configuration. Delay-vs.-throughput curves for the above multiple access channels are shown i n F i g s . 5.5.1 to 5.5.6 i n c l u s i v e for PNR = 60 and 70 dB-Hz, £ = 1024, 2048 and 8192 bits/message and Bfc = 51.1 MHz. Because the actual transmission bandwidths for pure ALOHA, sl o t t e d ALOHA and queueing at b i t rate R which maximizes the channel capacity for the given values of PNR and £ are much less than B t, these multiple access schemes are penalized by having excessive unused bandwidth. To perform more meaningful comparisons, the figures also include delay-vs.-throughput curves for m pure ALOHA, sl o t t e d ALOHA or queueing channels operating i n p a r a l l e l . These curves are obtained assuming that a l l users have the same a r r i v a l rate and each user i s permanently assigned to one of m channels with i d e n t i c a l delay-throughput a CO c n a J — J i PURE ALOHA SLOTTED ALOHA QUEUEING J , i i i i i i J i i i I I i 11 / P U R E ALOHA — m=154( SLOTTED ALOHA (^QUEUEING PNR = 60 D B - HZ = 1024 BITS r ~ ~ i — I T I I I ! | ]0 3 • 1 0 ' J i i i I ' ' i i i 11 ; i i i i i i i 11 1 1—i i i i i 11 1 0 s ' 1 0 5 ] 0 ' THROUGHPUT S (BITS/SEC.) . i I I I I 1 0 ' F i g . 5.5.1 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, s l o t t e d and queueing with PNR = 60.0 dB-Hz and I = 1024 b i t s . ALOHA a -3 CO a - d c n -LU a U J (JD CL > c n i 11111 PURE A L O H A — -SLOTTED ALOHA-Q U E U E I N G -1, 1,1 JQ PNR = 60 DB - HZ X = 2048 BfTS [PURE ALOHA m = 1 6 5 ( SLOTTED ALOHA (^QUEUEING -i i i i i i i 11 J L I I I I, I I J L 2 ~1 1 1 1 I i l l l | I I I I I I M | H I I I I I I 11 1 1—| | | | | 11 1 0 3 1 0 « 1 0 s 1 0 6 1 0 ; THROUGHPUT S (BJTS/SEC. ) I I I I I I 10 5 F i g . 5.5.2 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, slott e d ALOHA and queueing with PNR = 60.0 dB-Hz and % = 2048 b i t s . LU CO a -3 ' *—i LU a LU CD CE LUS > cr PURE ALOHA SLOTTED ALOHA QUEU! PNR = 60.0 DB - HZ Ji* 8192 BITS m = 211/PURE ALOHA—•) (SLOTTED ALOHA [QUEUEING i i i i i i i i ! I I 11 10' 1—1—1 I I 11 a 10 : T T 1 1—I M i l l i i r r 10' THROUGHPUT S (BITS/SEC. ) 10' F i g . 5.5.3 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, slotted ALOHAjand queueing with PNR = 60.0 dB-Hz and I = 8192 b i t s . THROUGHPUT S (BITS/SEC,) F i g . 5.5.4 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, s l o t t e d ALOHA and queueing with PNR = 70.0 dB-Hz and SL = 1024 b i t s . ON F i g . 5.5.5 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, s l o t t e d ALOHA and queueing with PNR = 70.0 dB-Hz and I = 2048 b i t s . THROUGHPUT S (BITS/SEC ALOHA F i g . 5.5.6 Comparison of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, sl o t t e d ALOHA and queueing with PNR = 70.0 dB-Hz and £ = 8192 b i t s . as 170 c h a r a c t e r i s t i c s . It i s further assumed that the central node has m rece i v e r s , one for each of the m channels. Thus the o v e r a l l throughput i s m times the throughput of a single channel, and average delay i s unchanged. Assuming that guard bands occupy at least 10% of channel bandwidth, then m = trunc(B t/2.2R) (5.5.1) where trunc(x) i s the integer part of r e a l number x. This lower-bounds the delay-throughput c h a r a c t e r i s t i c s for f u l l load-sharing among the m channels, the analysis for which i s quite unwieldy. The above r e s u l t s are also a p p l i c -able to a f u l l y meshed network i n which each user receives i n one of m channels and which t r a f f i c matrix i s such that off diagonal elements are a l l equal. The following observations can be made regarding F i g s . 5.5.1 to 5.5.6: ( i ) SSMA possesses a higher channel capacity than the other schemes operating over a single channel, except that queueing y i e l d s a higher capacity then SSMA with K=l when PNR = 70 dB-Hz and H = 1024 b i t s / -message. ( i i ) SSMA possesses a lower channel capacity than other schemes operating over m channels, except that at PNR = 70 dB-Hz capacity for m pure ALOHA channels i s lower than that of SSMA with K > 64 for £ = 1024 b i t s , K > 16 for I = 2048 b i t s and K > 4 for I = 8192 b i t s . ( i i i ) The difference i n channel capacities i n ( i ) changes i n favour of SSMA as I increases, PNR decreases, or K increases. The same i s true f o r the channel capacity differences i n ( i i ) , except that changes i n PNR have the apposite e f f e c t . 171 ( i v ) When throughput l e v e l s of a l l multiple access schemes are much less than the respective channel c a p a c i t i e s , SSMA gives the longest and queueing gives the shortest average delay. The average delays for the ALOHA channels are between the two extremes. The difference between the two extremes decreases as I increases, PNR decreases or K increases. The e f f e c t of increasing K to reduce t h i s delay diff e r e n c e diminishes as I increases. (v) At throughput values greater than the channel capacity of a single pure ALOHA, slott e d ALOHA or queueing channel and less than the chan-nel capacity of SSMA (such values exist for some values of K i n a l l cases considered), average delay for SSMA i s less than that of the other schemes. ( v i ) In a l l cases considered, for some values of K there e x i s t s a range of throughput values at which average delay for SSMA i s less than that of m-parallel pure ALOHA channels. ( v i i ) The average delays for a l l multiple access schemes considered are quite acceptable when operating well below channel capacity. In general, the following remarks are relevant to comparisons between delay-throughput c h a r a c t e r i s t i c s of SSMA, pure ALOHA, slott e d ALOHA and queue-ing channels: (1) SSMA derives i t s multiple access c a p a b i l i t i e s from operating at a data rate lower than what i t takes to accomplish a reasonable message error rate i n other channels (50 Kbits/sec for SSMA vs. 1.5 Mbits/sec for other schemes at PNR = 70 dB-Hz with £ = 1024 b i t s ) . Therefore, at low throughput values SSMA i s i n f e r i o r because of i t s longer message 172 duration. Under such condition SSMA delays may be lowered by increas-ing information b i t rate and thus decreasing processing gain, but th i s could lead to increase i n cr o s s - c o r r e l a t i o n which would tend to counteract any improvement. (2) At moderately high throughput l e v e l s , SSMA i s superior to single chan-nel ALOHA or queueing because of i t s higher channel capacity. How-ever, single channel ALOHA or queueing only uses a f r a c t i o n of the transmission bandwidth of SSMA. (3) If m ALOHA or queueing channels are f i t t e d into the transmission band-width of SSMA, then both slo t t e d ALOHA and queueing give channel capa-c i t i e s and delays superior to those of SSMA. However, performance of m channel pure ALOHA i s quite comparable to that of SSMA. SSMA i s es p e c i a l l y favourable for long messages. (4) Increasing PNR improves the performance of single channel ALOHA or queueing more than that of SSMA. In fact at approximately PNR = 85 dB-Hz optimum single channel ALOHA or queueing would occupy the en t i r e B t with the r e s u l t i n g delay-throughput c h a r a c t e r i s t i c s much better than those of m channels operating at a lower PNR l e v e l . However, the delay-throughput c h a r a c t e r i s t i c s of SSMA would show l i t t l e improvement from that obtained at PNR = 70 dB-Hz. (5) Channel capacity and average delay for SSMA are both affected by the average service time T g and could both benefit from i t s reduction. However, reduction of service time only helps to decrease delay i n 173 ALOHA and queueing channels, and has no e f f e c t on t h e i r channel capa-c i t y . (6) The above comparison i s based on the assumption that messages have fixed length. If message lengths are va r i a b l e , average delays increase from a l i t t l e for SSMA to probably very much f o r s l o t t e d ALOHA. Average delays only depend on mean message duration f o r SSMA, and depend on mean and variance of message duration for queueing. Analysis on ef f e c t s of variable message lengths on ALOHA channels i s unavailable and i s probably very complicated. (7) The above re s u l t s f o r SSMA were obtained assuming that users' codes are uncorrelated. If Gold's codes of the given length were used, a f i v e times reduction i n throughput would r e s u l t , and whatever advan-tages i n channel capacity SSMA presents over other schemes would be severely reduced. Delay-throughput c h a r a c t e r i s t i c s are important factors i n the choice of multiple access schemes for data communication networks. The above comparisons of delay-throughput c h a r a c t e r i s t i c s between SSMA, pure ALOHA, sl o t t e d ALOHA and queueing show that the performance of SSMA i s quite acceptable compared to that of sl o t t e d ALOHA and queueing, and i s very favourable compared to that of pure ALOHA. SSMA i s p a r t i c u l a r l y suitable f o r applications where average message length i s quite long, power i s l i m i t e d , a wide transmission bandwidth i s a v a i l -able and i t s e f f i c i e n t u t i l i z a t i o n i s not, therefore, a primary consideration. 174 6. CONCLUSIONS 6.1 Summary of Results This thesis presents a comprehensive evaluation of the delay-throughput performance of an asynchronous d i r e c t sequence SSMA i n t e r a c t i v e data communica-ti o n system based on a centralized network configuration. Results that con-s t i t u t e o r i g i n a l contributions are summarized below: ( i ) A code synchronizer with K p a r a l l e l correlators was proposed, developed and analyzed. In p a r t i c u l a r , means, standard deviations and confidence estimates for a c q u i s i t i o n time and hold-in time were derived. E f f e c t s of changes i n some synchronizer parameters on the above performance meansures were investigated. I t was shown that reduction i n mean a c q u i s i t i o n time i s proportional to an increase i n K. Application of the above re s u l t s to the spe c i a l case K = 1 (Hopkins' synchronizer) were presented. (These r e s u l t s together with t h e i r implications regarding protocol design are being published [L2].) ( i i ) Three protocols suitable for SSMA communications under various opera-tin g conditions were developed and analyzed, ( i i i ) SSMA delay-throughput c h a r a c t e r i s t i c s were obtained for Protocol B using a given set of system parameters and assuming uncorrelated users' codes. It was shown that average delays stay r e l a t i v e l y con-stant f o r t r a f f i c l e v e l s l e s s than the channel capacity, whereas average delays increase without bound and throughput l e v e l s diminish to zero for t r a f f i c l e v e l s exceeding channel capacity. Relationships 175 between channel capacity, channel s t a b i l i t y , message a r r i v a l rate, message length, PNR l e v e l and the number K of p a r a l l e l c orrelators i n the synchronizer were considered. Results show that channel capacity can be maximized with respect to message length. Increasing K generally reduces t o t a l delay and increases the channel capacity. Using the analysis procedures developed, SSMA delay-throughput c h a r a c t e r i s t i c s f o r other protocols using d i f f e r e n t system parameters could be pursued. ( i v ) Delay-throughput analysis f or s l o t t e d ALOHA channels was extended to include the e f f e c t s of Gaussian channel noise. A novel approach was used to obtain the delay-throughput c h a r a c t e r i s t i c s of pure ALOHA channels under the influence of Gaussian noise. A p r i o r i t y queueing model was established to f a c i l i t a t e delay-throughput analysis of Gaussian channels with p e r f e c t l y scheduled transmission, with re-transmissions at a higher p r i o r i t y for messages degraded by b i t -e r r o r s . At any given PNR l e v e l and given message length, capacities of these channels can be maximized with respect to transmission b i t rate. Results also show that the r e l a t i v e performance of these channels subjected to the corruption of Gaussian noise are unchanged when compared to noise-free channel performance, (v) Delay-throughput comparisons for SSMA, pure and slo t t e d ALOHA, and queueing were presented. Also included i n these comparisons are the delay-throughput c h a r a c t e r i s t i c s of m p a r a l l e l pure ALOHA, s l o t t e d ALOHA or queueing channels which f i t the transmission bandwidth for SSMA. These comparisons show that delays i n the SSMA channel are 176 longer than those i n the other channels when operating at throughput l e v e l s which are much less than the capacities of a l l the channels. The capacity of the SSMA channel i s generally higher than that of a single ALOHA or queueing channel but lower than that of multiple s l o t t e d ALOHA or queueing channels. The capacities of SSMA and multiple pure ALOHA channels are approximately equal. In conclusion, our results show that under the sp e c i f i e d conditions the delay-throughput performance of SSMA i s comparable to other multiple accessing schemes considered. Because SSMA protocols are comparable i n s i m p l i c i t y to the pure ALOHA protocol, and are less complicated than those of s l o t t e d ALOHA and perfect scheduling, SSMA presents a viable a l t e r n a t i v e to other multiple accessing schemes. SSMA i s e s p e c i a l l y favorable for transmission of long messages i n a wideband channel using a l i m i t e d amount of power. For short message lengths, much improvement i n SSMA delay-throughput c h a r a c t e r i s t i c s may be r e a l i z e d by increasing the number of p a r a l l e l c orrelators i n the synchronizer. 6.2 Suggestions f o r Further Work Delay-throughput performance of SSMA was analyzed i n the preceding chapters assuming a p a r t i c u l a r system configuration and receiver structure. Comprehensive studies of spread-spectrum communications i n general and SSMA i n p a r t i c u l a r are scarce, and much opportunity exists for further study. Some would undoubtedly involve a p p l i c a t i o n or modification of our methods and r e s u l t s . L i s t e d below are some areas of i n t e r e s t . 177 6.2.1 Enhancement of Receiver Performance through interference Cancellation In a centra l i z e d network a l l SSMA receivers are located at the ce n t r a l node. Thus interference c a n c e l l a t i o n can be achieved by subtracting the information extracted by one receiver from the received s i g n a l of a l l other r e c e i v e r s . Analysis by Kashihara [K8] shows that t h i s technique v i r t u a l l y eleminates co-channel interference of other users at high PNR l e v e l s . It i s of int e r e s t to examine the delay-throughput performance of a SSMA system incorporating t h i s processing technique. 6.2.2 Dif f e r e n t Power Levels f o r A c q u i s i t i o n and Message Transmission It has been shown that for PNR > 60 dB-Hz, message retransmissions r e s u l t i n g from b i t - e r r o r s r e s u l t i n rapid increases i n SSMA delay when channel occupancy exceeds a c e r t a i n l e v e l , whereas a c q u i s i t i o n delay does not begin to increase rapidly u n t i l channel occupancy has reached a much higher l e v e l . If a lower power l e v e l were used for transmission of the a c q u i s i t i o n preamble and a higher power l e v e l for transmission of the message, then the l e v e l of channel occupancy at which retransmission delay begins to increase r a p i d l y would be increased, and the l e v e l at which a c q u i s i t i o n delay begin to increase r a p i d l y would be reduced. An o v e r a l l increase i n channel capacity would r e s u l t . The extent to which optimal assignment of the two d i f f e r e n t power l e v e l s could increase channel capacity i s of i n t e r e s t . 178 6.2.3 E f f e c t of Various Modulation Schemes on Direct Sequence SSMA Performance Applications of quadriphase and M-ary modulation schemes to d i r e c t sequence spread-spectrum communications have been investigated [P4, S6]. It i s of in t e r e s t to examine how applications of these modulation schemes a f f e c t o v e r a l l system performance, and synchronizer performance i n p a r t i c u l a r . 6.2.4 Extension of Results to Other Spread-Spectrum Techniques Other spread-spectrum techniques such as time and frequency hopping, and hybrids of various techniques are also suitable for SSMA app l i c a t i o n s . Receiver structure and modulation formats for these techniques are quite d i f f e r e n t from those of d i r e c t sequence. With suitable modifications our res u l t s should be applicable to SSMA systems using these other techniques. 6.2.5 Extension of Results to F u l l y Connected Network Two problems related to the ap p l i c a t i o n of SSMA to a f u l l y connected network were c i t e d i n Section 2.2. The power control problem can be overcome by transponding which enables a l l users to impart the same PNR to any one receiving s i t e , but this PNR l e v e l may d i f f e r from one receiving s i t e to another. If the PNR l e v e l s at a l l receiving s i t e s are at least 70 dB-Hz for the system which parameters are given i n our numerical examples, then e s s e n t i a l l y uniform performance i s attained at a l l receiving s i t e s . The contention problem arises i f there i s only one receiver per s i t e , and r e s u l t s i n degradation i n delay-throughput performance. Analysis of the ef f e c t s of contention to SSMA performance i s probably very involved. A s i m i l a r but 179 possibly simpler problem i s the e f f e c t of contention to the performance of a multi-channel ALOHA system i n a f u l l y connected network. 6.2.6 Exploration of New Coding Schemes Coding schemes which produce code sets with large numbers of elements and low c r o s s - c o r r e l a t i o n between elements are e s s e n t i a l to the successful opera-ti o n of a SSMA system, e s p e c i a l l y i f a large user population i s to be served. Continuing e f f o r t i n the development of suitable coding schemes would be u s e f u l . 6.2.7 Extension of Results to Non-Gaussian Channels Derivation of appropriate SNR expressions for SSMA i n non-Gaussian chan-nels such as fading channels and hard - l i m i t i n g channels enables d i r e c t a p p l i c a -t i o n of our re s u l t s for SSMA performance evaluations. It i s anticipated that the inherent frequency d i v e r s i t y w i l l give SSMA addit i o n a l advantages over other multiple access techniques f o r applications i n non-Gaussian channels. 6.2.8 Application of Decision Feedback to Improve Channel S t a b i l i t y In a ce n t r a l i z e d random access network, when the propagation delay i s short, i t i s possible to improve channel s t a b i l i t y by using estimates of chan-nel s t a t i s t i c s at the cent r a l node to generate decision feedback over the return channel, thus l i m i t i n g further access when the channel Is close to saturation. Delay-throughput analysis f o r a decision feedback protocol i s of i n t e r e s t . 180 REFERENCES Al J.M. Aein, "Multiple access to a hard-limiting communication s a t e l l i t e repeater," IEEE Trans. Space E l e c t r o n i c s and Telemetry, v o l . SET-10, pp. 159-167, Dec. 1964. A2 D.R. Anderson and P.A. Wintz, "Analysis of a spread-spectrum m u l t i p l e -access system with a hard l i m i t e r , " IEEE Trans. Comm. Tech., v o l . COM-17, pp. 285-290, A p r i l 1969. A3 D.R. Anderson, "A new class of c y c l i c codes," SIAM J . Appl. Math., v o l . 16, pp. 181-197, Jan. 1968. A4 N. Abramson, "The throughput of packet broadcasting channels," IEEE Trans. Comm., v o l . COM-25, pp. 117-128, Jan. 1977. Bl D.T. B e l l , J r . , J.D. Holmes and R.V. Ridings, "Application of acoustic surface-wave technology to spread spectrum communications," IEEE Trans. Sonics and Ultr a s o n i c s , v o l . SU-20, pp. 181-189, Apr. 1973. B2 D.D. Buss, D.R. C o l l i n s , W.H. Bailey and C.R. Reeves, "Transversal f i l t e r i n g using charge-transfer devices," IEEE J . Solid-State C i r c u i t s , v o l . SC-8, pp. 138-146, Apr. 1973. B3 H.O. Burton and D.D. Su l l i v a n , "Errors and error control," Proc. IEEE, v o l . 60, pp. 1293-1301, No. 1972. CI A.B. C a r l e i a l and M.E. Hellman, "Bistable behaviour of AL0HA-typ§ systems," IEEE Trans. Comm., v o l . COM-23, pp. 401-409, Apr. 1975. C2 G.R. Cooper, "Multi-service aspects of spread-spectrum mobile communication systems," Conference Record of MIDCON/78, Dallas, Texas, Dec. 12-14, 1978, E l e c t r i c a l and Ele c t r o n i c s Exhibitions, Inc. C3 G.R. Cooper and R.W. Nettleton, "A spread-spectrum technique f o r high-capacity mobile communications," IEEE Trans. Vehicular Tech., v o l . BT-27 , pp. 264-275, Nov. 1978. Dl R.C. Dixon, Spread Spectrum Systems. New York: Wiley & sons, 1976. D2 R.C. Dixon, Ed., Spread Spectrum Techniques. New York: IEEE Press, 1976. D3 R.W. Donaldson, Design of Dis t r i b u t e d Computer-Communication Networks, pp. 40-41. Report to the Department of Communications, Ottawa, Canada, July 1977. D4 R.C. Dixon, "100 MHz. pseudonoise code generator," TRW Systems Group, Report IOC7325.2-19, July 1968. 181 D5 W.B. Davenport, J r . , P r o b a b i l i t y and Random Processes, Ch. 7. New York: McGraw H i l l , 1970. D6 W.B. Davenport, J r . , P r o b a b i l i t y and Random Processes, Ch. 13. New York: McGraw H i l l , 1970. D7 A.L. Dudick, E. Fuchs and P.E. Jackson, "Data t r a f f i c measurements f o r inquiry-response computer communications system," Proc. IFIP, pp. 634-641, Ljubljana, Yugoslavia, Aug. 1971. E l J . Eldon, "Correlation - a powerful technique for d i g i t a l s i g n a l processing," TRW LSI Products LSI Public a t i o n TP17A, La J o l l a , C a l i f o r n i a , Dec. 1980. F l E. Fuchs and P.E. Jackson, "Estimates of d i s t r i b u t i o n s of random variables for c e r t a i n computer communication t r a f f i c models," Comm. ACM, v o l . 13, pp. 752-757, Dec. 1970. Gl D.A. Gandolfo, G.D. O'clock, and C L . Grasse, "Acoustic surface wave sequence generators and matched f i l t e r s with adjustable taps," IEEE Int. Microwave Symp. Dig., pp. 60-61, May 1971. G2 R. Gold, "Optimal binary sequences f o r spread spectrum multiplexing, "IEEE Trans. Information Theory, v o l . IT-13, pp. 619-621, Oct. 1967. G3 D.P. Grybos and G.R. Cooper, "A receiver f e a s i b i l i t y study f o r the spread-spectrum high capacity mobile radio system," Conf. Rec. Vehicular Tech. Society, Denver, CO., Mar. 22-24, 1978. G4 G. Gordon, The Application of GPSS V to Discrete System Simulation, Englewood C l i f f s , N.J.: Prentice H a l l , 1975. HI H.P. Hartmann, "Analysis of a dithering loop for PN code tracking," IEEE Trans. Aerospace E l e c t r o n i c Systems, v o l . AES-10, pp. 2-9, Jan. 1974. H2 J.K. Holmes and C C . Chen, "Acquisition time performance of PN spread-spectrum systems," IEEE Trans. Comm., v o l . COM-25, pp. 778-784, Aug. 1977. H3 P.M. Hopkins, "A u n i f i e d analysis of pseudonoise synchronization by envelope c o r r e l a t i o n , " IEEE trans. Comm., v o l . COM-25, pp. 770-778, Aug. 1977. H4 P.S. Henry, "Spectrum e f f i c i e n c y of a frequency-hopped-DPSK spread-spectrum mobile radio system," IEEE trans. Vehicular tech., v o l . VT-28, pp. 327-332, Nov. 1979. 182 Kl L. Kleinrock, Queueing Systems, V o l . 2: Computer Applications. New York: Wiley & Sons, 1976. K2 L. Kleinrock, "On resource sharing i n a d i s t r i b u t e d communication environment," IEEE Comm. Magazine, v o l . 17, pp. 27-33, Jan. 1979. K3 L. Kleinrock and S.S. Lam, "Packet swithcing i n a multiaccess broadcast channel: performance evaluation," IEEE Trans. Comm., v o l . COM-23, pp. 410-423, Apr. 1975. K4 L. Kleinrock and F.A. Tobagi, "Packet switching i n radio channels: part I - c a r r i e r sense multiple-access modes and th e i r throughput-delay c h a r a c t e r i s t i c s , " IEEE Trans. Comm., v o l . COM-23, pp. 1400-1416, Dec. 1975. K5 C.C. Kilgus, "Pseudonoise code acqusition using majority l o g i c decoding," IEEE Trans. Comm., v o l . COM-21, pp. 772-774, June 1973. K6 R.E. Kahn, S.A. Gronemeyer, J . Bu r c h f i e l and R.C. Kunzelman, "Advances i n packet radio technology," Proc. IEEE, v o l . 66, pp. 1468-1496, Nov. 1978. K7 J.G. Kemeny and J.L. S n e l l , F i n i t e Markov Chains. Princeton, N.J.: Van Nostrand Co., 1969. K8 T.K. Kashihara, "Adaptive c a n c e l l a t i o n of mutual interference i n spread spectrum multiple access," Proc. ICC'80, pp. 44.4.1-44.4.5, Seattle, Washington, June 1980. LI S.S. Lam and L. Kleinrock, "Packet switching i n a multiaccess broadcast channel: dynamic control procedures," IEEE trans. Comm. v o l . C0M-23, pp. 891-904, Sept. 1975. L2 V.C.M. Leung and R.W. Donaldson, "Confidence estimates for a c q u i s i t i o n times and hold-in times for PN-SSMA synchronizer employing envelope c o r r e l a t i o n , " IEEE Trans. Comm., v o l . COM-30, Jan. 1982. Ml J . Martin, Design of Man-Computer Dialogues. Eaglewood C l i f f s , N.J.: Prentice H a l l , 1973. M2 S.A. Musa and W. Wasylkiwskyj, "Co-channel interference of spread spectrum systems i n a multiple user environment," IEEE trans. Comm., v o l . C0M-26, pp. 1405-1413, Oct. 1978. M3 M.B. M i l s t e i n and P.K. Das, "Spread spectrum receiver using surface acoustic wave technology," IEEE Trans. Comm., v o l . COM-25, pp. 841-847, Aug. 1977. M4 J.E. Mazo, "Some t h e o r e t i c a l observations on spread-spectrum communications," the B e l l System t e c h n i c a l Journal, v o l . 58, pp. 2013-2023, No. 1979. 183 M5 J . I . Marcum, "A s t a t i s t i c a l theory of target detection by pulsed radar, mathematical appendix," IRE Trans., v o l . IT-6, pp. 269-288, Apr. 1960. Nl R.W. Nettleton and G.R. Cooper, "Error performance of a spread-spectrum mobile communications system i n a rapidly-fading environment," Conf. Rec. NTC'77, Los Angeles, CA, Dec. 5-7, 1977. N2 R.W. Nettleton and G.R. Cooper, "Mutual interference i n c e l l u l a r LMR systems: narrowband and broadband techniques compared," MIDCON 1977 Session Reprint, Session 9, Chicago, IL, Nov. 1977. N3 R.W. Nettleton and G.R. Cooper, "Spectral e f f i c i e n c y i n c e l l u l a r land-mobile communications: a spread-spectrum approach," Technical Report TR-EE 78-44, Purdue University, Oct. 1978. Pi M.B. Pursley, "Performance evaluation f o r phase-coded spread-spectrum multiple-access communication - part I: system analysis," IEEE Trans. Comm.. v o l . COM-25, pp. 795-799, Aug. 1977. P2 M.B. Pursley and D.V. Sarwate, "Performance evaluation for phase-coded spread-spectrum multiple-access communication - part I I : code sequence analysis," IEEE Trans. Comm., v o l . COM-25, pp. 800-803, Aug. 1977. P3 A Papoulis, P r o b a b i l i t y , Random Variables, and Stochastic Processes. New York: McGraw-Hill, 1965. P4 M.B. Pursley, F.D. Garber and J.S. Lehnert, "Analysis of generalized quadriphase spread-spectrum communications," Proc. ICC'80, pp. 15.3.1-15.3.6, Seattle, Washington, June 1980. Rl W.B. Rouse, "Design of man-computer int e r f a c e for on-line i n t e r a c t i v e systems," Proc. IEEE, v o l . 63, pp. 847-857, June 1975. R2 D. Raychaudhuri, "Performance analysis of random-access packet-switched code d i v i s i o n multiple access systems," IEEE trans. Comm., v o l . C0M-29, pp. 895-901, June 1981. 51 J.W. Schwartz, J.M. Aein and J . Kaiser, "Modulation techniques f o r multiple access to a hard-limiting s a t e l l i t e repeater," Proc. IEEE, v o l . 54, pp. 763-777, May 1966. 52 G. Solomon, "Optimal frequency hopping sequences for multiple access", Proc. Symp. Spread Spectrum Comm., Naval Ele c t r o n i c s Lab., Mar. 1973. 53 J . J . Spilker, J r . and D.T. M a g i l l , "The delay-lock discriminator - an optimum tracking device," Proc. IRE, v o l . 49, pp. 1403-1416, Sept. 1961. 54 G.F. Sage, " S e r i a l synchronization of pseudonoise systems," IEEE Trans. Comm. Tech., v o l . C0M-12, pp. 123-127, Dec. 1964. 184 55 J . J . S p i l k e r , J r . , "Delay-lock tracking of binary signals," IEEE Trans. Space E l e c t r o n i c s and telemetry, v o l . SET-9, pp. 1-8, Mar. 1963. 56 D.L. S c h i l l i n g , L.B. M i l s t e i n , R.L. Pickholtz and R.W. Brown, "Optimization of the processing gain of an M-ary di r e c t sequence spread spectrum communication system," IEEE trans. Comm., v o l . COM-28, pp. 1389-1398, Aug. 1980. TI R.A. Tobagi and L. Kleinrock, "Packet switching i n radio channels: part II - the hidden terminal problem i n c a r r i e r sense multiple-access and the busy-tone solution," IEEE Trans. Comm., v o l . COM-23, pp. 1417-1433, Dec. 1975. T2 F.A. Tobagi and L. Lkeinrock, "Packet swithcing i n radio channels: part III - p o l l i n g and (dynamic) split-channel reservation multiple access," IEEE Trans. Comm., v o l . COM-24, pp. 832-844, Aug. 1976. VI R. Van Slyke and H. Frank, "Network r e l i a b i l i t y a n a l ysis: Part 1," Networks, v o l . 1, No. 3, pp. 279-290, 1972. V2 P.A. DeVito, P.H. Carr, W.J. Kearns and J.H. S i l v a , "Encoding and decoding with e l a s t i c surface wvaes at 10 Megabits per second," Proc. IEEE, v o l . 59, pp. 1523-1525, Oct. 1971. Wl R.B. Ward, "Acquisition of Pseudonoise signals by sequential estimation," IEEE Trans. Comm., v o l . COM-13, pp. 475-483, Dec. 1965. W2 R.B. Ward and K.P. Yiu, "Acquisition of pseudonoise signals by recursion-aided sequential estimation," IEEE trans. Comm., v o l . COM-25, pp. 784-794, Aug. 1977. Yl K. Yao, "Error p r o b a b i l i t y of asynchronous spread spectrum multiple access communications systems," IEEE trans. Comm., v o l . COM-25, pp. 803-809, Aug. 1977. Y2 R.D. Yates and G.R. Cooper, "Design of large signa l sets with good aperiodic c o r r e l a t i o n properties," Technical Report TR-EE 66-13, Purdue Un i v e r s i t y , Sept. 1966. Y3 P.S. Yu and S. L i n , "An e f f i c i e n t selective-repeat ARQ scheme f or s a t e l l i t e channels and i t s throughput analysis," IEEE trans. Comm., v o l . COM-29, pp. 353-363, Mar. 1981. Zl R.E. Ziemer and W.H. Tranter, P r i n c i p l e s of Communications, Ch. 7, Boston, Mass.: Houghton M i f f l i n Co., 1976. 185 Appendix 1. Derivation of Equation (2.3.6) Consider the receiver block diagram i n F i g . 2.1.1(b), and l e t x(t) and y(t) be the input and output s i g n a l s , r e s p e c t i v e l y , of the low pass f i l t e r which has the transfer function Cl , | f| < B H(f) = { Q f | f | > B " ( A l . l ) Let u(t) be the l o c a l l y generated signa l which i s synchronized to the i - t h user's tranmission. Let the random phases and delays of a l l transmitted signals, s ^ ( t ) , be measured with reference to s ^ ( t ) . Therefore, 0^=0, 1^=0 and u(t) = JI c^(t) cos(cot) (A1.2) i c Let x N ( t ) and y N ( t ) be the noise components of x(t) and y ( t ) , r e s p e c t i v e l y , contributed by n(t) and s ^ ( t ) , k * i . Modelling a l l PN signals as band-limited, uncorrelated Gaussian white noise, y i e l d s the power spectra for s^(t) and u(t) as follows: fP/2B t , |f±fj < B t/2 S c ( f ) = S k , elsewhere and S (f) = S ( f ) / P (A1.4) u s, k where f = co /2TT. c c The power spectrum for n(t) i s S (f) = N 12 (A1.5) n o 186 Convolution of S u ( f ) with the sum of S n ( f ) and (M-l)S g ( f ) re s u l t s i n the following spectrum for x N ( t ) . N (M-l)P r_£ + 2 2B^ 2 f C1 - n r - ) > l f l < T -s N ( f ) "< X N (M-l)P ° + (1 " 4B. B t 2 If±2f B. N-0. l f ± 2 fol <T-elsewhere (A1.6) Since B « B , low-pass f i l t e r i n g r e s u l t s i n the following spectrum f or y (t) m t N (M-l)P S N ( f ) S S N ( 0 ) = - + - 2 B -y x t S N ( f ) = 0 = N , f < B D m m (A1.7) The corresponding autocorrelation function f o r y (t) i s sin(2irB x) R „( x) = 2B N - _ m N m D 2 irB x y m (A1.8) It follows that E [ ( a N ( T b ) ) 2 ] T b T b E [ / / y N ( t ) y N ( x ) d t dx] o o T T b b = / / R N ( t - x)dt dx o o y N 2 TT 2lT , . x D _ r r sin(x-y) d x 2 lr 2B o o X " y m (A1.9) 187 where the su b s t i t u t i o n T, = 1/B has been made. Evaluating the double i n t e g r a l b m i n eqn. (A1.9) by numerical methods, yi e l d s the res u l t given by eqn. (2.3.6), V a r [ a N ( T b ) ] = 0.9 N D/B m ( A i a Q ) ( 1 8 8 Appendix 2. Derivation of Equation (2.3.11.) In addition to signals defined i n Ch. 2 and Appendix 1, l e t x ^ ( t ) , Y^(t) and a (t) be the components of x ( t ) , y(t) and a ( t ) , respectively, contributed by the k-th active user of the channel. Consider the i - t h r e c i e v e r . For k * i , x f c(t) = s k ( t ) u(t) = /P c.(t)c, (t-x, ) {cos(co x -0, ) + cos[co (2t-T, ) + 0, ]} (A2.1) l k k c k k c k k The low pass f i l t e r removes the double frequency term to give sin(2TrB t) y k ( t ) = /P c i ( t ) c k ( t - T k ) c o s ( c o c x k - 0 k ) * 2B m ^ ™ (A2.2) m where * denotes convolution. Expanding the code sequences c^(t) and c k ( t ) into series of pulse t r a i n y i e l d s c ( t ) = I a p(t-mT ) (A2.3) i L m c m=—00 c, (t) = I b p(t-nT ) (A2.4) k u n c n=-» where {a } and {b } are the sequences of code symbols with values of ±1 and m n period L corresponding to c ^ t ) and c f c ( t ) , and p(t) i s a pulse defined by 1 , 0 < t < T p(t) = (A2.5) 1^0 , elsewhere In eqns. (As.3) to (A2.5) i n c l u s i v e , T £ i s the pulse duration of the spread-spectrum codes. Therefore 189 C l ( t ) c k ( t - x k ) = I a mp(t-mT c) I b n p ( t - n T c - T k ) (A2.6) m=—co n=—oo This product i s zero for a l l values of t except where the pulses overlap. Define r ^ and d^ as follows: r k = trunc ) (A2.7) d k " \ ~ r k T c ( A 2 ' 8 ) where trunc(x) i s the largest integer less than or equal to r e a l number x. Then eqn. (A2.6) becomes oo c.,(t) c, ( t - T . ) = Y [a b .p^t-mT ) + a b p„(t-mT )] , A O n N i k k L m m - r , - l r l c m m-r, 2 c (A2.9) m=-°° k k where p^(t) and p 2 ( t ) are pulses defined by r 1 , o < t < a. p (t) =\ (A2.10) V 0 , elsewhere f l , d,< t < T P 2 ( t ) =j C ( A2.ll ) 10 , elsewhere Because 1/B = T, = LT , T « 1/B and s i n ( 2 t r B t ) / 2 T r B t may be considered as m b c ' c m m m J a constant within any time i n t e r v a l of length T^. Therefore sin(2irB t) d sin[2uB (t-mT ) ] P l ( t - m V * 2 , B t m a 2,B (t-mT ) ° ( A 2 ' 1 2 ) m m c s i n ( 2 n B t) (T -d, )sin [ 2 i r B_(t-mT_) ] P 2<'- Tc> * 2 » B t m ~* 2 „ ( t - J ) ( A 2 ' 1 3 ) m m c 190 Define the function f i k ( m > \ ) hY V = ^ V r / A V r ^ c ^ (A2.14) Since a and b are periodic i n m with period L, so i s f ± k ( m , T f c ); thus m m f i k(m+nL, r f c) = f i k ( m > T k)» a n y integer n (A2.15) Substituting for. c ^ O c ^ t - T ^ ) , eqn. (A2.2) becomes y (t) = ^ 2 B c o s ( B T - V I I {f l k(m +nL, Tfc) n=-» m=l s i n [ 2 irB (t-mT -nLT ) ] i n c c i 2TTB (t-mT -nLT ) ' m c c v¥2Bmcos(a)cV0k) I f i k(m,T k) m=l sin[2irB (t-mT -nT, ) ] r. m c b i 2TTB (t-mT -nT, ) n=-<» m c b L = /P2B mcos(ai T k-6^) I f ± k ( m , x k)g(t-mT c) (A2.16) m=l where the function g i s defined as follows: A * sin[2TrB (t-nT.) ] n=-» m b Note that g(t) i s periodic i n t with period T^ and that value of g(t) may be computed to a s a t i s f a c t o r y degree of accuracy using numerical methods. Integration of Y k ( t ) followed by sampling y i e l d s 191 a k(T f e) = / ^ 2 B m c o s ( I f i k(m, T k)g(t-tnT c)dt o m=l T L b = ^B^osCco^-e^) I f ± k (m, x k) / g(t)dt (A2.18) m=l o In eqn. (A2.18) inte g r a t i o n i s over one period of g ( t ) . Therefore g(t-mT c) may be replaced by g ( t ) . Numerical int e g r a t i o n gives the following r e s u l t : T b / g(t)dt = Tfe/2 = l / 2 B m (A2.19) o Define the maximum cr o s s - c o r r e l a t i o n between the code sequences as T b max * " /T / c.(t)c.(t+T)dt m^ax i , j , T j q i J max L " i . k . T \ f i k ( m ' T ) ( A 2 - 2 0 ) ' ' m=l Making appropriate s u b s t i t u t i o n s , an upper bound for the mean squared value of k a (T, ) i s therefore given by b E [ ( a k ( T b ) ) 2 ] < E [ P ^ J x (l-rcos(2a) cT k-0 k))/2] (A2.22) Since E t c o s U w ^ - O j ) ] = 0 (A2.23) i t follows that E [ ( a k ( T ) ) 2 ] < 2 12 (A2.24) Tmax Applying the res u l t s i n Appendix 1 to the Gaussian channel noise only, 192 N the contribution of channel noise to a (T^) i s a n ( T u ) = 0.45 N /B (A2.25) b o m N Summing a l l contributions, results i n Var[a (T^)].being bounded as follows: Var[a N(T, )] < (M-l)ij, 2 P/2 + 0.45 N /B (A2.26) b ymax o m which i s the r e s u l t given by eqn. (2.3.11). 193 A P P E N D I X 3. G P S S PROGRAM FOR S I M U L A T I O N O F S S M A C H A N N E L R E A L L O C A T E X A C , 3 7 0 0 * * * * * * * * * * * * * * * * * * * * * * * * * * * * S S M A - R T * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * TO S I M U L A T E A SSMA C O M M U N I C A T I O N S Y S T E M W I T H R E T R A N S M I S S I O N * * ON M E S S A G E E R R O R S . A S S U M E : * * ( 1 ) E X P O N E N T I A L L Y D I S T R I B U T E D I N T E R A R R I V A L T I M E ; * ( 2 ) F I X E D M E S S A G E L E N G T H ; * * * ( 3 ) U N I F O R M L Y D I S T R I B U T E D A C Q U I S I T I O N T I M E ; . * * ( 4 ) F I X E D S E R V I C E T I M E OF 0.01 S E C ; * * ( 5 ) F I X E D B I T - E R R O R R A T E F O R T R A N S M I S S I O N O F E A C H B I T ; * * ( 6 ) M E S S A G E T R A N S M I S S I O N R E P E A T E D U N T I L E R R O R - F R E E . * * M E S S A G E D E L A Y S A R E T A B U L A T E D . C H A N N E L O C C U P A N C Y I S S A M P L E D * * A T F I X E D I N T E R V A L S AND T A B U L A T E D . * * * ***************************************************************** S I M U L A T E * * D E F I N E F U N C T I O N S * X P D I S F U N C T I O N R N 1 , C 2 4 I N V E R T E D E X P O N E N T I A L D I S T R I B U T I O N 0 , 0 / . 1 , . 1 0 4 / . 2 , . 2 2 2 / . 3 , . 3 5 5 / . 4 , . 5 0 9 / . 5 , . 6 9 / . 6 , . 9 1 5 / . 7 , 1 . 2 . 7 5 , 1 . 3 8 / . 8 , 1 . 6 / . 8 4 , 1 . 8 3 / . 8 8 , 2 . 1 2 / . 9 , 2 . 3 / . 9 2 , 2 . 5 2 / . 9 4 , 2 . 8 1 . 9 5 , 2. 9 9 / . 9 6 , 3. 2/. 9 7 , 3. 5/. 9 8 , 3. 9/. 9 9 , 4. 6/..995, 5. 3/. 9 9 8 , 6. 2 . 9 9 9 , 7 / . 9 9 9 8 , 8 P B I T F U N C T I O N S $ C H A N L ; C 1 3 E R R O R S / 1 0 0 0 B I T S V S C H N . O C P . A T 7 0 D B - H Z 0 , 0 / 1 2 5 , 0 / 2 0 5 , 1 / 2 5 4 , 2 / 2 8 5 , 3 / 3 0 8 , 4 / 3 4 7 , 6 / 3 8 0 , 8 / 4 0 8 , 1 0 4 6 0 , 1 4 / 5 5 0 , 2 2 / 6 7 2 , 3 4 / 8 2 8 , 5 0 / * . . " • • , * S I M U L A T I O N OF I N D I V I D U A L U S E R S * G E N E R A T E X H $ I A R R T , F N $ X P D I S , , , , 1 P H C R E A T E AN A R R I V A L E N T E R C H A N L I N C R E M E N T C H A N N E L O C C U P A N C Y A D V A N C E X H $ T A C Q , X H $ T A C Q A C Q U I S I T I O N D E L A Y A D V A N C E X H $ T S E R V S E R V I C E D E L A Y T R A N A S S I G N 1 , X H $ M L E N , P H S E T U P B I T C O U N T E R L O G I C R 1 R E S E T B I T - E R R O R S W I T C H N X B I T T E S T L R N 8 , F N $ P B I T , C O R R GO TO CORR I F NO B I T - E R R O R L O G I C S 1 S E T B I T E R R O R S W I T C H CORR A D V A N C E X H $ T B I T T R A N S M I S S I O N T I M E F O R 1 B I T A S S I G N 1 - , 1 , P H D E C R E M E N T B I T C O U N T E R T E S T E P H 1 , 0 , N X B I T A L L B I T S T R A N S M I T T E D ? I F NOT, GOTO N X B I T G A T E L R 1,TRAN R E T R A N S M I T I F B I T - E R R O R S O C C U R E D T A B U L A T E D E L A Y D E L A Y T A B U L A T E D A F T E R M E S S A G E E R R O R - F R E E A D V A N C E X H $ T S E R V S E R V I C E D E L A Y FOR A C K N O W L E D G E M E N T L E A V E C H A N L D E C R E M E N T C H A N N E L O C C U P A N C Y T E R M I N A T E S I M U L A T I O N OF 1 U S E R C O M P L E T E D 194 * COLLECT STATISTICS FOR CHANNEL OCCUPANCY * ' GENERATE XH$SAMPT,,,,,OPH SAMPLE AT REGUALR INTERVAL TABULATE NUSER TABULATE CHANNEL OCCUPANCY TERMINATE 1 * * I N I T I A L I Z E SAVEVALUES * * * * INITIAL INITIAL INITIAL INITIAL INITIAL INITIAL DEFINE TABLES XH$TBIT,2 XH$TSERV,1000 XH$TACQ,10000 XH$IARRT, 1 25 XH$SAMPT,750 XH$MLEN,1000 DELAY TABLE NUSER TABLE * * CONTROL BIT TRANSMISSION TIME 0.02 MSEC, SERVICE TIME 0.01 SEC. MEAN ACQUISITION TIME 0.1 SEC. IARRT 0.00125SEC, 800MES./SEC. SAMPLING INTERVAL 0.0075SEC. MESSAGE LENGTH 1000 BITS M1 ,3000,1000,24 S$CHANL,60,1, 1 00 START 18,NP IN I T I A L I Z E CHANNEL RESET START 500 COLLECT '500 SAMPLES CLEAR XH2-XH5 NUSER TABLE S$CHANL,90,1, 100 INITIAL XH$IARRT,100 IARRT 0.001SEC, 1 000MES . /SEC. INITIAL XH$SAMPT,700 SAMPLING INTERVAL 0.007SEC. START 1 9,NP IN I T I A L I Z E CHANNEL RESET START 500 COLLECT 500 SAMPLES END 195 Appendix 4. Goodness-of-Fit Tests The following i s the summary of a number of goodness-of-fit tests perform-ed between the d i s t r i b u t i o n s of channel occupancy obtained from simulations of a SSMA channel and exponential d i s t r i b u t i o n s whose expected values equal the corresponding channel occupancy averages. Data were obtained for PNR = 70 dB-Hz and I = 1000 bits/message, with X ranging from 10 to 1000 messages/sec. In the simulations i t was assumed that a c q u i s i t i o n delays were uniformly d i s t r i -buted between 0 and twice the mean value for a synchronizer with K = 1, Vg = 1.7, V = 1.0. This assumption i s reasonable for the PNR l e v e l and range of J_i channel occupancies considered because the mean and standard deviation of a c q u i s i t i o n time are minimum and have the r a t i o of standard deviation/mean = 0.6 = l//3~, the corresponding r a t i o for a uniform d i s t r i b u t i o n . To test the hypothesis H : Pr(M=m) = — r e o m! against 500 channel occupancy samples obtained from simulation, where M i s the sample mean, data and r e s u l t s are tabulated below. Case 1: X = 10 messages/sec. M = 1.441 Channel Observed Expected (°r Ei) 2 Occupancy Frequency Frequency M °i E i E i 0 116. 118.35 0.046 1 177. 170.54 0.245 2 119. 122.87 0.122 3 58. 59.02 0.018 4 19. 21.26 0.241 5 to 6 11. 7.60 1.522 (0.-E.)2 I \ 1 = 2.194 Number of degrees of freedom = 5 2 Xo.05 = 11.070 > 2.194 Therefore, we f a i l to reject H q at a 0.05 l e v e l of s i g n i f i c a n c e . Case 2: X = 50 messages/sec. M = 6.775 * Channel Occupancy M Observed Frequency °i Expected Frequency E i E i 0 to 2 21. 17.54 0.681 3 26. 29.59 0.436 4 48. 50.12 0.090 5 62. 67.92 0.516 6 88. 76.69 1.667 7 74. 74.23 0.001 8 63. 62.86 0.000 9 47. 47.32 0.002 10 35. 32.06 0.270 11 9. 19.75 5.848 12 11. 11.15 0.002 13 8. 5.81 0.826 14 to 16 6. 4.62 0.413 I % 1 = 10.752 Number of degrees of freedom = 12 2 ^.05 = 21.016 > 10.752 Therefore, we f a i l to rej e c t H at a 0.05 l e v e l of si g n i f i c a n c e , ' o 198 Case 3: X = 100 message/sec. M = 13.717 Channel Occupancy M Observed Frequency °1 Expected Frequency E i E i 0 to 6 7. 8.45 0.248 7 9. 10.00 0.101 8 19. 17.15 0.199 9 29. 26.14 0.313 10 41. 35.86 0.738 11 44. 44.71 0.011 12 41. 51.11 2.001 13 60. 53.93 0.683 14 44. 52.84 1.479 15 47. 48.32 0.036 16 55. 41.43 4.447 17 27. 33.43 1.235 18 22. 25.47 0.473 19 21. 18.39 0.370 20 12. 12.61 0.030 21 13. 8.24 2.752 22 to 26 9. 11.42 0.512 = 15.630 Number of degrees of freedom = 16. Therefore, we f a i l to rej e c t Ho at a 0.05 l e v e l of s i g n i f i c a n c e . Case 4: X = 200 message/sec. M = 28.271 Channel Occupancy M Observed Frequency °1 Expected Frequency E i t o r t - ) 2 E. l 0 to 17 6. 7.96 0.482 18 6. 5.48 0.049 19 to 20 11. 19.68 3.830 21 14. 15.52 0.149 22 23. 19.94 0.469 23 23. 24.51 0.093 24 24. 28.87 0.823 25 27. 32.65 0.978 26 35. 35.50 0.007 27 51. 37.18 5.141 28 40. 37.54 0.162 29 38. 36.59 0.054 30 37. 34.48 0.184 31 36. 31.45 0.659 32 35. 27.78 1.875 33 27. 23.80 0.430 34 23. 19.79 0.520 35 18. 15.99 0.254 36 11. 12.55 0.192 37 to 38 8. 16.73 4.554 39.to 42 . 7. 13.05 - 2.803 = 23.708 Number of degrees of freedom = 20. Therefore, we f a i l to reject H at a 0.05 l e v e l of s i g n i f i c a n c e . Case 5: A = 400 message/sec. M = 56.605 Channel Observed Expected Occupancy Frequency Frequency M °i E i E i 0 to 39 6. 4.31 0.667 40 to 42 7. 8.83 0.378 43 to 44 10. 11.65 0.235 45 6. 8.25 0.613 46 9. 10.15 0.130 47 12. 12.22 0.004 48 15. 14.42 0.024 49 12. 16.65 1.300 50 25. 18.85 2.004 51 20. 20.93 0.041 52 26. 22.78 0.456 53 25. 24.33 0.019 54 32. 25.50 1.656 55 23. 26.25 0.401 56 23. 26.53 0.469 57 29. 26.35 0.268 58 29. 25.71 0.421 59 22. 24.67 0.289 60 22. 23.27 0.070 61 23. 21.60 0.091 62 25. 19.72 1.416 63 19. 17.71 0.093 64 10. 15.67 2.050 65 13. 13.64 0.030 66 10. 11.70 0.248 67 9. 9.89 0.079 68 10. 8.23 0.381 69 to 70 7. 12.21 2.224 71 to 72 • 7. 7.77 0.077 73 to 74 7. 4.68 1.146 75 to 77 7 3.51 3.466 = 20.745 Number of degrees of freedom = 30. Therefore, we f a i l to reject Ho at a 0.05 l e v e l of s i g n i f i c a n c e . Case 6: X = 500 message/sec. M = 70.553 Channel Occupancy M Observed Frequency °i Expected Frequency E. i E i 0 to 55 7. 16.38 5.374 56 to 57 11. 11.83 0.058 58 10. 7.96 0.523 59 9. 9.52 0.028 60 6. 11.19 2.409 61 10. 12.95 0.670 62 12. 14.73 0.506 63 11. 16.50 1.832 64 20. 18.19 0.181 65 20. 19.74 0.003 66 17. 21.10 0.709 67 26. 22.22 0.643 68 23. 23.06 0.000 69 28. 23.57 0.831 70 29. 23.76 1.155 71 25. 23.61 0.082 72 29. 23.14 1.486 73 30. 22.36 2.610 74 32. 21.32 5.351 75 30. 20.06 4.931 76 25. 18.62 2.188 77 15. 17.06 0.249 78 14. 15.43 0.133 79 16. 13.78 0.357 80 11. 12.15 0.109 81 9. 10.59 0.238 82 9. 9.11 0.001 83 to 84 9. 14.24 1.931 85 to 87 7. 13.42 3.069 = 37.744 Number of degrees of freedom = 28. Therefore, we f a i l to rej e c t H at a 0.05 l e v e l of s i g n i f i c a n c e . Case 7: X = 800 message/sec. M = 112.359 Channel Occupancy M Observed Frequency °i Expected Frequency E. l ( ° i - E i ) 2 E i 0 to 91 5. 10.91 3.198 92 to 93 7. 6.42 0.053 94 to 95 10. 9.16 0.077 96 to 97 11. 12.54 0.188 98 5. 7.71 0.955 99 9. 8.75 0.007 100 9. 9.84 0.071 101 9. 10.94 0.345 102 12. 12.05 0.000 103 7. 13.15 2.876 104 12. 14.21 0.343 105 8. 15.20 3.412 106 20. 16.11 0.937 107 18. 16.92 0.069 108 21. 17.60 0.655 109 19. 18.15 0.040 110 14. 18.54 1.110 111 19. 18.76 0.003 112 22. 18.82 0.536 113 34. 18.72 12.482 114 26. 18.45 3.093 115 16. 18.02 0.227 . . .continued Case 7: X = 800 message/sec. M = 112.359 Channel Occupancy M Observed Frequency °i Expected Frequency E i ( 0 r E r ) 2 E i 116 21. 17.46 0.719 117 20. 16.76 0.624 118 23. 15.96 3.102 119 8. 15.07 3.319 120 13. 14.11 0.088 121 16. 13.10 0.640 122 13. 12.07 0.072 123 15. 11.03 1.433 124 7. 9.99 0.895 125 7. 8.98 0.436 126 5. 8.01 1.130 127 5. 7.08 0.613 128 11. 6.22 3.676 129 to 130 7. 10.10 0.950 131 to 133 7. 10.32 1.068 134 to 143 6. 11.58 2.692 = 52.134 Number of degrees of freedom = 37. Therefore, we f a i l to reject H at a 0.05 l e v e l of s i g n i f i c a n c e . Case 8: X= 1000 message/sec. M= 141.500 Channel Occupancy M Observed Frequency °i Expected Frequency E i ( 0 , - E ^ E i 0 to 116 5. 6.21 0.236 116 to 117 5. 3.53 0.613 118 to 119 5. 5.07 0.001 120 to 121 6. 7.05 0.156 122 to 123 10. 9.47 0.029 124 5. 5.78 0.106 125 6. 6.55 0.046 126 5. 7.35 0.753 127 11. 8.19 0.962 128 10. 9.06 0.098 129 8. 9.93 0.376 130 12. 10.81 0.130 131 9. 11.68 0.615 132 14. 12.52 0.175 133 7. 13.32 2.999 134 9. 14.07 1.824 135 16. 14.74 0.107 136 18. 15.34 0.462 137 15. 15.84 0.045 138 18. 16.24 0.190 139 21. 16.54 1.205 140 15. 16.71 0.176 141 18. 16.77 0.090 142 18. 16.71 0.099 143 21. 16.54 1.203 144 19. 16.25 0.465 145 12. 15.86 0.939 146 17. 15.37 0.173 .continued Case 8: X = 1000 message/sec. M = 141.500 Channel Occupancy M Observed Frequency ° 1 Expected Frequency E i E l 147 11. 14.80 0.974 148 15. 14.15 0.052 149 13. 13.43 0.014 150 9. 12.67 1.064 151 9. 11.88 0.696 152 22. 11.05 10.837 153 7. 10.22 1.017 154 16. 9.39 4.646 155 7. 8.58 0.290 156 7. 7.78 0.078 157 12. 7 .01 3.551 158 to 159 8. 11.87 1.260 160 5. 4.94 0.001 161 12. 4.34 13.500 162 to 165 6. 12.36 3.276 166 to 173 6, 9.73 1.428 = 56.952 Number of degrees of freedom = 4 3 . Therefore, we f a i l to reject H q at a 0.05 l e v e l of s i g n i f i c a n c e .
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Spread-spectrum multiple access for interactive data...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Spread-spectrum multiple access for interactive data communications Leung, Victor Chung Ming 1981
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Spread-spectrum multiple access for interactive data communications |
Creator |
Leung, Victor Chung Ming |
Publisher | University of British Columbia |
Date Issued | 1981 |
Description | Spread-spectrum multiple access (SSMA) is conceptually attractive for interactive data communications over broadcast channel shared by a large number of potential users. The present thesis Involves a study of asynchronous direct sequence SSMA interactive data communication systems. The study includes a unified analysis and assessment of system delay-throughput performance. Two important message delay components which are affected by the design of the transmitter/receiver pair result from code acquisition and bit-errors. A new code synchronizer design featuring a number of parallel correlators is developed, and an analysis of synchronizer performance as it relates to SSMA applications is provided. It is shown that average acquisition delay decreases in proportion to Increase In the number of correlators when this number is small. Receiver bit-error probability for any given channel occupancy is derived. Three protocols suitable for SSMA transmissions under different operating conditions are proposed. Using one of these protocols, the expected number of transmissions before a message is received error-free is estimated by averaging bit-error probabilities over a postulated channel occupancy probability distribution. This distribution is verified using data obtained from channel simulations. Delay-throughput characteristics of the SSMA system are thus obtained by evaluating the above delays and other exogenous delays at various traffic levels. Results relevant to the given system and traffic models, transmission protocol, and transmitter/receiver structure are obtained assuming that users' codes are uncorrelated. Subsequently, it is shown that the results are easily modified to account for code cross-correlations. Assessment of SSMA delay-throughput performance Is accomplished by comparisons with pure ALOHA, slotted ALOHA and queueing channels. These comparisons necessitate extension of existing analysis of slotted ALOHA channels to include the effects of Gaussian channel noise, as well as development of an analysis procedure for noisy pure ALOHA channels. It is shown that in power-limited situations, the capacities of ALOHA and queueing channels can be maximized with respect to the transmission bit rate. Delay-throughput comparisons show that at throughput levels much lower than the capacities of these channels, average delays for SSMA are higher than those of the other channels. However, capacities of SSMA channels are generally higher than those of the other channels, which occupy only a fraction of the available bandwidth at power levels favourable to SSMA. In such cases, the throughput which results for a given delay clearly favours SSMA. Comparisons are also performed with respect to m-parallel ALOHA or queueing channels, where ra is the number of channels accommodated by the available bandwidth. In this case the capacities of SSMA channels are generally less than those of m-parallel slotted ALOHA or queueing channels, but approximately equal to those of m-parallel pure ALOHA channels. Therefore, SSMA presents a viable alternative to m-parallel pure ALOHA multiple access for interactive data communications. SSMA is especially favourable for transmissions of long messages In a wide-band broadcast channel with limited power. |
Subject |
Interactive computer systems |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-04-15 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0095603 |
URI | http://hdl.handle.net/2429/23619 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1982_A1 L48.pdf [ 8.82MB ]
- Metadata
- JSON: 831-1.0095603.json
- JSON-LD: 831-1.0095603-ld.json
- RDF/XML (Pretty): 831-1.0095603-rdf.xml
- RDF/JSON: 831-1.0095603-rdf.json
- Turtle: 831-1.0095603-turtle.txt
- N-Triples: 831-1.0095603-rdf-ntriples.txt
- Original Record: 831-1.0095603-source.json
- Full Text
- 831-1.0095603-fulltext.txt
- Citation
- 831-1.0095603.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
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-0095603/manifest