A near-optimum MAC protocol based on the distributed queueing random access protocol (DQRAP) for a CDMA mobile communication system

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATONS, VOL. 18, NO. 9, SEPTEMBER 2000 1701 A Near-Optimum MAC Protocol Based on the Distributed Queueing Random Access Protocol (DQRAP) for a CDMA Mobile Communication System Luis Alonso, Member, IEEE, Ramón Agustí, Member, IEEE, and Oriol Sallent, Member, IEEE Abstract—This paper presents and analyzes a new near-optimum medium access control (MAC) protocol. The proposed access scheme is suitable for a CDMA mobile communication environment, and keeps under control and upper bounded the number of simultaneous transmissions. It has a delay performance approaching that of an ideal optimum M/M/ system, where is the number of spreading codes being used (maximum number of simultaneous transmissions). The protocol is a free random access protocol when the traffic load is light, and switches smoothly and automatically to a reservation protocol when traffic load becomes heavier. It is based on distributed queues and a collision resolution algorithm. Moreover, a physical receiver structure is proposed and analyzed in order to preserve the robustness of the protocol in a wireless link. The results obtained show that the protocol outperforms other well known medium access protocols in terms of stability and delay, even when taking into account the loss caused by channel propagation conditions. Index Terms—Code division multiaccess, mobile communications, multiaccess communication, protocols. I. INTRODUCTION IN THE LAST few years, manyresearch efforts have focused on the design of medium access control (MAC) protocols. In the future third-generation communication systems, mixed services and different traffic patterns will have to share the same channel structure and resources. MAC techniques must provide flexibility and efficiency to allow the existence of these types of systems with reasonable complexity and reliability. ALOHA and slotted-ALOHA techniques have been widely used in the past as random access protocols. However, their low throughput (0.18 and 0.36 maximum) and potential instability at heavy traffic load have led to the appearance of collision resolution algorithms (CRA), also called tree algorithms [1], which have a higher performance (up to 0.568 based on ternary channel feedback [2]). Some protocols achieve higher throughput by using control minislots for reservation purposes. Of all these, the announced arrival random access protocols Manuscript received July 1, 1999; revised February 25, 2000. This work was supported by CYCIT Project TIC 98-684. Part of this work was presented at PIMRC’99, Osaka, Sept. 1999; and at VTC’99 Fall, Amsterdam, Sept. 1999. The authors are with the Department of Signal Theory and Communications, Universitat Politècnica de Catalunya (UPC), Barcelona 08034, Spain (e-mail: [email protected]; [email protected]; [email protected]). Publisher Item Identifier S 0733-8716(00)07135-3. (AARA) [3] achieve the best delay and throughput performance (0.853 with only three control minislots). However, to reach throughputs approaching unity, the AARA protocols need a theoretically infinite number of minislots, and this is obviously impractical and inefficient because of the overhead introduced by each minislot. One widely studied medium access protocol based on control minislots is DQRUMA (distributed queue request update multiple access) [15]. This protocol uses a certain number of access minislots for reservation purposes. Terminals with data to transmit send an access request in one of these minislots applying a slotted-ALOHA strategy. This request contains the identification number of the terminal and the type and quality of the demanded service. The main advantage of using this centralized strategy is that it allows the designer to totally control the behavior of the system. It is possible to give priority to terminals with strict quality requirements, such as tight delay bounds, instead of simply maximizing the overall throughput. However, high complexity algorithms, a great amount of signaling and feedback information, and accurate admission control policies are required forthe system to workcorrectly. Moreover, slotted-ALOHA strategy is used for accessing purposes, and thus the potential instability problem is still present when traffic load is high. In general, merely using control minislots makes the system more complex as it is necessary to have time slots with different time sizes. Nevertheless, we observe that all existing tree protocols that do not have minislots use data slots to resolve collisions, and thus lose the channel capacity of all the empty slots or collided packets. The suggested improvements to tree protocols seek to reduce the number of collisions and empty slots, but they do not eliminate this type of efficiency loss. Keeping all these ideas in mind, Xu and Campbell proposed the distributed queueing random access protocol (DQRAP) [4], [5], [19], which seems to be one of the best-performing MAC protocols proposed to date. This protocol uses three control minislots and is based on a tree-type collision resolution algorithm. It wasinitiallydesignedforaTDMAenvironment,particularlyfor the distribution of CATV (cable TV) signal. Inspired by DQDB (distributed queueing dual bus, now the IEEE 802.6 standard for metropolitan area networks), its performance approaches that of an ideal M/D/1 queue, reaching maximum stable throughputs close to one, and maintaining its stability for traffic loads up to 0733–8716/00$10.00 © 2000 IEEE 1702 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATONS, VOL. 18, NO. 9, SEPTEMBER 2000 channel capacity. These near-optimum characteristics add to the appeal of using the rationale of this protocol in other transmission environments such as packet radio systems. On the other hand, direct-sequence code division multiple access (DS-CDMA) is going to be adopted for third-generation mobile telecommunication systems. Schemes based on wide-band CDMA (WCDMA) [6] have been chosen as radio interfaces by the standardization body in Japan (ARIB), and also in Europe by the ETSI for the UMTS Terrestrial Radio Access (UTRA) [7]. This access scheme is also being considered in the International Mobile Telecommunication 2000 (IMT-2000) [8] by the ITU. In this paper, we propose a random near-optimum medium access protocol that modifies and extends DQRAP techniques for use in a CDMA environment such as those mentioned above. The operation mode of the protocol may allow the use of random access channels (RACH) or other packet transmission systems, in uplinks (reverse links), not only for accessing purposes but also to efficiently transmit data. For this purpose, the idea of using a DQRAP engine for each oneofthe spreadingcodesisintroduced. Then,astheprotocol is based on two logical distributed queues (the collision resolution queue and the transmission queue), the queues corresponding to each spreading code are joined in only one queue for each group (resolution and transmission). We will show in this paper that the DQRAP/CDMA protocol can be modeled as two concatenated M/M/ systems, where is the number of available spreading codes. Moreover, DQRAP/CDMA is provided with a mechanism that reduces to a minimum the jitter in the delay of the packets corresponding to one message, and also becomes a new advantage for managing messages of more than one slot length. The protocol is a free random access protocol when the traffic load is light, thus reducing the transmission delay, and switches smoothly and automatically to a reservation protocol when traffic load becomes heavier, blocking the transmission of newly arrived packets by putting them into a data transmission queue. Then, given certain CDMA channel characteristics (i.e., spreading factor, bits per slot, fading and interference model, diversity, coding, ARQ strategy, etc.), DQRAP/CDMA allows an optimum number of simultaneous transmissions to be kept in the system, avoiding collisions to a great extent (they only could appear for light traffic conditions) and preventing the use of more receiver resources than strictly needed. This behavior is the key to its good delay and throughput performance. In order to assess the DQRAP/CDMA scheme under realistic conditions, a receiver scheme for the control minislot detection was proposedand analyzed. Expressions for the minislot statemisdetectionprobabilitieswerederived,andvarious mechanisms were introduced to keep the robustness of the protocol in a Rayleigh fading channel situation. Finally, a comparison was made to other MAC schemes extensively studied in the open literature such as slotted-ALOHA/CDMA [9] and ISMA/CDMA [14].Theresultsobtainedshowasignificantimprovementinthe system delay and throughput performance. The paper is organized as follows. The protocol description is detailed in Section II. In Section III, the analytical model is presentedandstudied. Expressionsforthetotalsystemdelayare alsoderived inthissection. SectionIV explainsand analyzesthe proposed scheme for the control minislot state detection. In this section, protocol algorithm modifications are also introduced to recover from errors in the minislot detection. Section V shows computersimulationresultsandcomparisons toother protocols. Finally, Appendix I and Appendix II are devoted to the conclusion. II. PROTOCOL DESCRIPTION Let us consider data terminals which share a CDMA channel with available spreading codes to communicate with a base station. The time axis is divided into slots, and each slot has two fields. The first field is the access field, which is further divided into control minislots. The second field is the data part, where terminals will transmit their packets. We assume that every station has perfect slot and minislot synchronization. The spreading codes are put in order, and we will denote for the th code. We consider that the terminals are able to change the spreading code for data and request transmission on a slot-by-slot basis. The messages generated by one terminal are split into slot-duration packets and put into a buffer. Each packet will be sent with the same spreading code, but not all the packets pertaining to one message will necessarily be sent with the same spreading code. The protocol uses two concatenated distributed queues: the collision resolution queue and the data transmission queue. When a message arrives at the system, the corresponding terminal, following a certain set of rules described below, selects a spreading code and sends a request in one of the control minislots pertaining to this code. If it fails (i.e., the request collides with one or more requests from other messages), it enters the collision resolution queue. Collisions are then resolved in the order fixed by the queue discipline. In addition, the data transmission queue contains the messages that have succeeded in their request and are waiting to be transmitted to the base station also following the order fixed by the corresponding queue discipline. Collision resolution and data transmission processes work in parallel. All the terminals must have four integer counters, which representthetwologicaldistributedqueues.Wewilldenotethemas TQ, RQ, pTQ, and pRQ. TQ is the number of messages waiting for transmission in the distributed transmission queue. RQ is the numberofcollisionswaitingforresolutioninthedistributedcollision resolution queue. pTQ is the position of a given terminal in the data transmission queue, and pRQ is the position of that terminal in the collision resolution queue. These values range from 0, meaning that the terminal does not have any position in the corresponding queue, to TQ or RQ (respectively), 1 being the first position of the queue. TQ and RQ have the same value foralltheterminalsinthesystem(i.e.,theyrepresent distributed queues), while pTQ and pRQ have a specific value for each terminal. We assume both queues to be FIFO. All four values are initially set to zero and must be kept updated using the feedback information sent by the base station, each slot, using a broadcast channel, and following a set of rules described below. It consists of ternary state data for each control minislot of every spreading code, and also has to include a final-message-bit for each code. ALONSO et al.: NEAR-OPTIMUM MAC PROTOCOL BASED ON DQRAP 1703 The three different states that the base station must be able to distinguish are: empty, success, and collision. A collision will occur when more than one station transmits in the same minislot of the same spreading code. The final-message-bit is the mark that all the data terminals must send when they are transmitting the last packet from one message. This flag bit must be ON in the last packet of each message, and must be OFF in all the other packets. This mechanism allows all packets from a message to be transmitted with a single request and minimizes the delay jitter between these packets. Nevertheless, if propagation delay in the system prevents the terminals from receiving thefeedback informationaboutthis final-message-bit beforethe nextdata slot begins, anempty slot loss is produced at the endof each message. If messages are known to be short (for example, ATM cells), it should be possible and convenient to switch off this mechanism and consider all messages formed by a single packet. Theprotocolalgorithmconsistsofthreesetsofrules thateach data terminal has to follow at the end of each slot. They are, in orderofexecution,thequeueingdisciplinerules(QDR),thedata transmission rules (DTR), and the request transmission rules (RTR). A. Algorithm Rules We will now describe the algorithm rules that each data terminal has to execute at the end of each slot, assuming that, at this time, the feedback information from the base station about the state of the control minislots of the previous slot has already been received by the terminal. They must be executed in the order presented below. Some rules have initial conditions that must be true to execute the corresponding actions. If the assertion is not verified, then the algorithm simply jumps to the next rule. When all the rules have been checked, the slot finishes and a new one starts. 1) QDR (Queueing Discipline Rules): a) Each station increments the value of TQ by one unit for each control minislot in the success state, taking into account the feedback information from all the control minislots from any of the spreading codes. b) Each station reduces the value of TQ by one unit for each packet correctly received by the base station with the final-message-bit set to ON from any of the spreading codes. c) If RQ , each station reduces the value of RQ by RQ units. d) Each station increments the value of RQ by one unit for each control minislot in the collision state, taking into account all the control minislots from any of the spreading codes. e) Dependingonitsstate,and theresults ofthecontrolminislots, each station calculates the values for pTQ and pRQ. That is, if it has sent a request and this request has succeeded, it calculates its position among allthe succeeding minislots and sets pTQ to the corresponding value at the end of TQ. For this purpose, all the successes are sorted using the order of the spreading code to which they belong, and within the same spreading code, using a time arrival criterion. On the other hand, if the request has collided, the terminal calculates its position among all the present collisions and sets pRQ to the corresponding value at the end of RQ. If it has not sent any request, then pTQ and pRQ follow the same update rules as TQ and RQ, respectively, but only if the initial values are other than zero. 2) DTR (Data Transmission Rules): a) If TQ , each station that has pTQ , pRQ and data packets ready to be sent transmits the first packet of its buffer using the spreading code . This rule is also called the free access rule, as it allows newly arrived packets to be transmitted immediately when traffic load is light. However, using this rule may cause a collision in the data part of a slot. b) If a station has pTQ and pTQ , the station transmits the first packet of its buffer using the spreading code . If this packet is the last one of the current message, the station sets the final-message-bit to ON. 3) RTR (Request Transmission Rules): a) If RQ , each station that has pRQ and pTQ and data packets ready to be sent randomly selects one of the control minislots of the spreading code and transmits a request in it. b) If a station has pRQ and pRQ , the station randomlyselectsoneofthecontrolminislotsofthespreading code and transmits a request in it. B. Example The example shown in Fig. 1 illustrates the operation of the protocol with , , and starting from an idle system (all values are initially zero). All the messages generated by the terminals are assumed to be of length one, so each data slot has the final-message-bit set to ON. In slot , three messages arrive at the system. In , they try to send a request and also to transmit the data in the first spreading code (using rules RTR-1 and DTR-1). Only the request from succeeds and enables to enter the transmission queue. As the requests of and collide, they enter the collision resolution queue. All packets use the free access rule (DTR-1), and then the data part also collides. In this slot, a message from arrives at the system. In , is the only packet in the transmission queue and it is thus transmitted using the first spreading code (DTR-2). Packets and resolve their collision (RTR-2) and enter the transmission queue ( in the first position, as its request used a prior control minislot) (QDR-5). However, transmits its request and data using the second spreading code (RTR-1 and DTR-1). As is the only new packet arriving at the system, its data transmission succeeds, and therefore it does not need to enter any queue. Two more packets arrive at this slot. In , and are transmitted using the first and second spreading codes (DTR-2). The new packets and send their requests and collide. They enter the collision resolution queue. In , requests from and collide and the packets again enter the collision resolution queue. The requests from and 1704 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATONS, VOL. 18, NO. 9, SEPTEMBER 2000 Fig. 1. Example of DQRAP/CDMA protocol operation. also collide and enter this latter queue in the next position, as they have used a higher-in-order spreading code. In , all the packets attempt to resolve their collisions and succeed, entering the transmission queue. This process continues endlessly. C. Practical Considerations At this point, we are going to outline some practical considerations for real implementation purposes. First of all, we are considering that the feedback information about the states of the control minislots is broadcasted to the terminals and arrives before the next time slot begins. This is a feasible feature as the system has the data slot duration for performing this transmission. Moreover, it is assumed that the base station also broadcasts the values of TQ and RQ periodically in the control downlink, in order to allow new users to join the system and recover from possiblelossesofthecounters.Thisinformationconsistsofonly two integer values that occupy a fewbits. Another practical possibility is to transmit this number to the mobile terminals only when needed to join the system or recover from errors. III. PROTOCOL MODEL AND ANALYSIS The DQRAP/CDMA protocol can be modeled as shown in Fig. 2. We have two queue subsystems: the collision resolution subsystem and the transmission subsystem. The enable transmission interval (ETI) service time represents the time each message has to wait from when it arrives at the system until the next time slot starts. Normalizing the time axis in slot units, this Fig. 2. Model of DQRAP/CDMA protocol. service time will thus be a uniformly distributed random variable in the interval (0, 1). Both subsystems have as many servers as available spreading codes (i.e., ). The elements in the system are the messages generated by the users, although they only use the control minislots for accessing purposes in the collision resolution subsystem. The feedback line in this subsystem represents that the messages that collide in their requests must enter the queue again until they succeed. A. Delay Analysis The total delay for a message can be broken down into four terms: the service time of the ETI , the total delay of the collision resolution subsystem , the total delay of the data transmission subsystem , and the delay caused by the collision of a data packet in a data slot . This latter term appears when more than one terminal transmits its packet using ALONSO et al.: NEAR-OPTIMUM MAC PROTOCOL BASED ON DQRAP 1705 rule 1 of the DTR (the free access rule) in the same slot. Thus, the expected value of the total delay of the system is EE E E E (1) We will now describe the expression of the terms in (1). First of all, E equals 0.5 because the arrival of messages is independent of the slot timing and, as noted above, is a uniformly distributed random variable in the interval (0, 1). 1) Total Delay of the Collision Resolution Subsystem: Let be the probability that a message will find a free control minislot to access when it arrives at the system, where is the total message input rate to the system (with Poisson distribution). We may note that, according to RTR, all newly arrived messages use the same spreading code to send their request. In addition, the arrival process is memoryless, and the protocol uses a tree algorithm for collision resolution, that is, all packets that have collided in a certain minislot use an exclusive code to resolve their contention. Then, if we have control minislots per code, it results in (2) where is the probability of randomly choosing an empty minislot when packets have arrived at the system in a given slot, and is the probability that packets arrive at the system in that slot. Therefore, it can be written that (3) All the messages in the collision resolution subsystem (including both the messages waiting in the queue and the newly arrived ones) have a probability of succeeding in their request. Thus, the service time for the collision resolution subsystem will be a geometrically distributed discrete random variable (where denotes the integer part), with probability distribution function (PDF): (4) At this point, if we use the exact discrete service time distribution, the system is an M/G/ and, as pointed out in [10], this type of system is analytically unmanageable and only loose bound expressions exist for them. However, in our case, we can approximate the geometrical distribution by the corresponding exponential distribution for a continuous service time as, in fact, the geometrical distribution values are only the sampling of the exponential one. Computer simulation results, as will be shown in Section IV, will confirm that this approximation is feasible, as they fit this model very well. Then, with this assumption, we can write its probability density function as (5) We can thus see that the service time of the collision resolution subsystem is a Poisson-distributed random variable with mean (6) We can therefore model the system as an M/M/ . Following the analysis in [10], adding the waiting time in the queue plus the service time, we can write the total delay for the collision resolution subsystem (7) where (8) and (9) This last expression is the Erlang C formula for the delay probability. 2) Total Delay of the Data Transmission Subsystem: As both arrival and service time processes are Poisson-distributed, the collision resolution subsystem output traffic pattern will also be Poisson-distributed and, as shown in [11], with the same rate as the input traffic . This output traffic is directly the input traffic of the data transmission subsystem. All the terminals generate messages of exponentially distributed length with mean . Then, assuming that the system uses a Stop & Wait ARQ strategy to retransmit each packet containing one or more error bits, the service time of the data transmission subsystem will also be exponentially distributed. The mean value of this service time will be the mean length of the messages, , multiplied by the mean transmission time for each packet of the message, . Calling the probability that a packet has at least one error bit, we can write the value for as (10) If we discard and retransmit any packet having at least one erroneous bit, is the block error ratio, BLER, so we can finally 1706 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATONS, VOL. 18, NO. 9, SEPTEMBER 2000 write the mean service time for the data transmission subsystem as BLER (11) Again, both the input traffic and the service time of the data transmission subsystem are exponentially distributed, and we can thus model this subsystem as an M/M/ queue system. Its total delay expression thus has the same terms as the one for the collision resolution subsystem but changing the service time rate by the new value , that is, BLER BLER (12) where the expression for is also the same as for but substituting the value of with the new value . That is, (13) Note that is the Erlang C formula with servers and with this new value . 3) Data Collision Delay: According to the algorithm rules of the protocol, the only possible situation where a data collision can occur is when the system has fewer than messages waiting in the data transmission subsystem, and more than one packet arrives at the system in the same slot. The mean delay caused by this event will be its probability, since if a data collision occurs, the message will enter any of the two subsystems of the model (depending on whether its request has succeeded or collided) and will no longer collide. We can evaluate this probability as (14) where is the probability that the system has units, taking into account the ones in the queue and the ones being served. 4) Total System Delay: The average total delay for a message will be BLER BLER To evaluate this expression, we need to know the value of the BLER. If we assume a perfect power control for a steady state andneglectthe effect ofthermal noise,we mayusetheGaussian hypothesis for the interferences. Then, as we discard and retransmit all the packets containing one or more errors, we can write [12] BLER erfc (15) where spreading factor; number of simultaneous data transmissions; number of bits contained in the packets sent during a time slot. Note that is not constant with time. For analytical evaluation purposes, we will use , as this is the worst case value. However, this perfect power control is not available in the initial transient state when minislots are used to access the media. Therefore, a Rayleigh fading model can approach the communication channel better, as is shown in the following. B. Detection of Access Requests in Control Minislots One of the main problems for the practical implementation of protocols using minislots for accessing purposes is the complexity they entail in the physical layer. In normal conditions, the only difference between these control minislots and the data slots is their length, measured in bits or in time units. Unfortunately, regardless of the actual length of a slot, special symbols such as bit training patterns must be transmitted at the beginning of each slot for channel synchronization, equalization, and power control. The number of these symbols required depends on the characteristics of the radio link. The performance improvement of the minislots is thus impaired when taking into accountthisphysicallayer overhead.Moreover,mixedslotsizes complicate the hardware design of the radio interface. However, DQRAP/CDMA has a critical advantage for tackling this problem. Control minislots are simply a burst of chips that a terminal has to send inside a certain window of time for the base station to detect its access demand. The only requirement is that it must be possible for the base station to distinguish between three different states: 1) empty, that is, no energy is received; 2) success, that is, a single burst from any terminal has been detected; and 3) collision, when two or more bursts have been detected. The receiver structure for this access scheme could be as follows: each station has two different assigned access sequences, and no other terminal will have the same pair of sequences. Whena terminalhas totransmitanaccessburstin acontrolminislot, it will send both sequences simultaneously. The detection ALONSO et al.: NEAR-OPTIMUM MAC PROTOCOL BASED ON DQRAP 1707 Fig. 3. Structure of the minislot receiver at the base station. of more than two access sequences will allow the base station to detect collisions without any need to have one matched filter for each user. Fig. 3 shows the structure of the receiver at the base station. This receiver consists of a bank of matched filters, one for each different sequence. A matched filter will output a peak whenever it detects that any terminal has transmitted the corresponding sequence. Then, the decision block only needs to count the number of correlation peaks at the output of the bank of filters. Ideally, if two peaks are detected, it means that only one terminal has sent its request. A greater number of peaks will denote the presence of a collision. The absence of peaks simply revealstheabsenceof accessrequests.Notethatifweuseabank of filters, we can address different users. In order to assess the performance of the proposed receiver scheme in terms of the probability of minislot state misdetection, we first must calculate the detection and false alarm probabilitiesat theoutput ofeach detectionfilter, thatis, thematched filter with the square power and threshold decision blocks. C. Analysis of the Minislot State Detection Scheme Using an optimal receiver scheme, with antenna and postdetection diversity of order (see Appendix II), the false alarm probability and the detection probability for each detection filter are given by (16) (17) where is the decision threshold, and (18) and (19) is the number of chips, is the total interference level, is the energy per chip, and is the number of simultaneous access request transmissions. Note that and depend on the number of simultaneous user transmissions that cause interference in the system, that is, on the value of . In our practical case, the transmitted sequences are used for access request detection (and possible collisions) in the control minislots. This number of simultaneous transmissions thus matches the number of access request sequences sent in the same considered minislot, using any of the available spreading codes. Moreover, this value will depend on the traffic load offered to the system, measured in terms of the number of messages trying to access the channel per time unit (doubled). We must choose a value for (the number of simultaneous access requests), which we will call design , or simply , and select the false alarm probability we wish for this specific value. Indeed, if we neglect the effect of the thermal noise (interference limited system), and denoting as the design false alarm probability, the value for the decision threshold can be explicitly written for (no diversity) (20) Therefore, the detection probability is (21) Fig. 4 shows the values for the false alarm and detection probabilities as a function of the parameter for a sequence of length . However, the real false alarm and detection probabilities in the system will not be as presented in this figure. Indeed, once the threshold for the decisor has been chosen, these probabilities still depend on the number of simultaneous access requests transmitted in each minislot, that is, the total interference level, which will not always be the design one . In general, we will actually have a certain value for different from . 1708 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATONS, VOL. 18, NO. 9, SEPTEMBER 2000 Fig. 4. Detection and false alarm probabilities in a Rayleigh fading environment without diversity. Given the threshold value defined in (20), the expressions for the probabilities in the system will be (22) (23) where is the actual number of access requests. As an example, Figs. 5 and 6 show the false alarm and detection probabilities as a function of for a and with . We can observe that the variation of the detection probability is very small with . Furthermore, the false alarm probability also increases smoothly for and decreases abruptly when . These properties match our practical application well: when traffic load is higher than the design rate, the probabilities are only slightly worse than decided; and when traffic load becomes lighter, the false alarm probability decreases dramatically, improving the system performance. Using antenna diversity , it is not possible to write the explicit expression of the threshold as a function of the false alarmprobability. Letus use forthe relationthatfulfills (24) where, again, design false alarm probability; number of simultaneous access requests used for design; number of actual simultaneous access requests. The false alarm and detection probabilities are thus (25) (26) Note that all the expressions presented assume a perfect minislot synchronization, that is, all the access requests arrive at the base station simultaneously. In fact, this situation is a worst case scenario, as all the access requests suffer the maximum possible interference level. However, this situation keeps the size of the minislots to a minimum and, as they represent an access overhead that is not useful for data transmission, maximizes the data throughput efficiency. It would be possible to fulfill this condition using mobile location techniques [13]. If they are not available, the minislot size is lower bounded by the maximum propagation delay in the system. In a macrocell environment, this value may be significantly greater than the access request size, and the detection probability will be enforced, as not all the received requests will be simultaneous in time. For this case, the expression presented in (26) will represent a lower bound for the detection probability. Note also that the values presented in Fig. 6 for the detection probability of the receiver filter seem to be low, but they represent a worst-case situation. We are sending a chip sequence in a Rayleigh fading channel using no diversity and only average open loop power control. For example, using antenna diversity of order , and for and we have . It is proved in [4], [5], and [19] that with only three control minislots, the average number of slots in which packets ALONSO et al.: NEAR-OPTIMUM MAC PROTOCOL BASED ON DQRAP 1709 Fig. 5. False alarm probability as a function of the number of access requests. Fig. 6. Detection probability as a function of the number of access requests. resolve their contention is lower than , and thus the system throughput is only limited by the data transmission channel rate. Therefore, using only three control minislots, the protocol achieves its best performance, keeping the access overhead loss very small. Henceforth we will always use for all analytical and simulation purposes. Even more, if messages are long (they consist in more than one transmission packet), it can be seen that with only minislots, it could be enough to reach the maximum throughput performance [18]. We will also show this feature in Section IV. D. Probability of Minislot State Misdetection According to the false alarm and detection probabilities described above, there will be a certain probability of the base station failing to detect the state of each control minislot. We will now describe the expressions of this probability, for all six different error situations possible. We will use to represent the postdetection empty state, for the postdetection success state, and forthepostdetectioncollisionstate. Fig.7showsallthese error situations. First of all, the probability of detecting one or two correlation peaks (the base station detects a successful access), when infact no user has transmitted its access sequence, is (27) Fig. 7. Possible misdetection situations. where is the false alarm probability of each detection filter and is the total number of detection filters. This expression implicitly assumes that the system decides that there has been a single access request transmission when only one correlation peak is detected. This assumption is made supposing that the false alarm probability is much lower than the no-detection probability, which is a reasonable assumption as the false alarm probability is a design parameter. 1716 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATONS, VOL. 18, NO. 9, SEPTEMBER 2000 Fig. 17. IP message delay with mixed IP-voice traffic sources. Finally, we may note that even the conceptual complexity of DQRAP/CDMA seems to be rather considerable, the protocol algorithm is quite simple to implement, and the computational load added is minimum (only integer simple operations are required). Moreover, it would simplify, to some extent, the base station complexity, as it reduces the number of total receivers needed to manage a certain number of mobile terminals. V. CONCLUSION A proposal for a near-optimum random access protocol for a CDMA environment suitable for the future third generation mobile communication systems has been presented. An analytical model has been introduced, and the results obtained match the ones obtained by computer simulations well. It has been shown that the protocol has good delay and stability characteristics, maintaining the standard deviation of the message’s delay bounded by its mean value and achieving a nearly optimum maximum stable throughput, for given channel characteristics. It is therefore a suitable proposal for improving the use of the capacities of random access channels in a reverse link. A receiver scheme for the detection of access requests has been proposed and analyzed, and the misdetection state probabilities have been derived. The protocol’s sensitivity to errors in the detection of the state of the control minislots has been studied.Protocol modifications havebeenintroducedto manage the possible error scenarios, showing great robustness and little efficiency loss in realistic channel conditions. It has been shown that the protocol outperforms other widely used multiple access schemes in terms of the maximum stable throughput and the delay characteristics. APPENDIX I We are to find the expression of the number of combinations of users that are able to generate a peaks if they are assigned a unique pair of sequences between different available ones. We must make an abstraction of the problem as follows. Let be the first integer numbers. That is, we number the received peaks from 1 to . Let be the different possible pairs we can create. Each pair represents one user. Let this be all the possible groups of pairs of numbers, that is, all the possible groups of users having 1 to users per group. We must evaluate, for any from 1 to , which of these groups contain at least once all the numbers from 1 to , being able to repeat the numbers as many times as desired, and how many users there are in each group. Calling this number , we will suppose that we know the value of for any value , and with these values we will evaluate the function for (the target value). We calculate all the different groups of users we can make from the total possible users, and then we subtract thosethatdonothaveall thenumbersfrom1to . Whichgroups do not fulfill this condition? First of all, those that leave one number unselected, which will be the number of pairs that generate peaks multiplied by the a positions where we can locate the blank. Then, we must subtract the pairs that leave two unselected numbers multiplied by the number of combinations leaving two blanks of a number, and so on. The result is thus We have explicitly eliminated the terms for and becausetheyarezero. Weonly needtheinitial values toevaluate the recursive expression. These are ALONSO et al.: NEAR-OPTIMUM MAC PROTOCOL BASED ON DQRAP 1717 Fig. 18. Receiver structure for each receiver filter. APPENDIX II It is shown in [16] that the optimum receiver scheme for a sequence detection filter is the one shown in Fig. 18. Each branch of the receiver presented in Fig. 3 has this structure. As shown in the figure, for a given user , the input signal follows the expression, where represents the energy per chip, is the impulse response of the channel, and is the informationthatmodulates thecodesequence .Wechose for all , that is, we send a single bit, without modulating . With these assumptions, the expected value of the correlation between the input signal and the local copy of the sequence,forthe in-phaseandquadraturesequences , hasthe following expression [16]: (39) where (40) and isthenumberofchipsinthesequence(iftheycorrespond to one bit, this value will be equal to the spreading factor). The matched filter output peak corresponds to , which implies that for any input filter . As both signals are squared and added, the phase term becomes irrelevant, always supposing that this value remains constant during the -chip transmission time. On the other hand, the variance of both components is [16] Var Var (41) where (42) represents the thermal noise , plus the total interference caused by the rest of users. For a time-limited filter, the value of the integral in (42) is 2/3. Thus, assuming a power control that maintains the same for all users, the variance of both in-phase and quadrature components is Var (43) with being the number of simultaneous access request transmitted. To find the detection and false alarm probabilities of the receiver scheme, we must take into account the propagation channelconditions. Wewill consideraRayleigh fadingenvironment. Note that the decision variable is .It can be proved that the diagram shown in Fig. 18 is optimal for signals with unknown phase, according to either the Bayes or the Newman–Pearson optimality criteria [17]. Using the latter, the system design consists in fixing the decision threshold value to obtain a certain allowable false alarm probability. The criterion guarantees that the chosen value is that which maximizes the detection probability for that false alarm probability value. These probabilities are obtained from integrating two likelihood functions of , depending on the initial possible hypothesis: under the assumption that no signal has been transmitted, and under the assumption that the target sequence has been transmitted. Using antenna and postdetection diversity of order , that is (similarly to the time postdetection integration used in [16]), adding the contributions of independent signals coming from the same number of different antennas and receivers, these functions are given by (44) (45) where is twice the variance of each component , and is the mean square, which is obtained as the sum of the squares of the in-phase and quadrature component means. Defining , the likelihood functions are finally (46) The false alarm and detection probabilities are obtained by evaluating the integral of the corresponding function from the threshold value to infinity, thus giving (47) (48) REFERENCES [1] D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall International, 1992. [2] B. S. Tsybakov and N. B. Likhanov, “Upper bound on the capacity of a random multiple access system,” Problems Inform. Transmission, vol. 23, no. 3, pp. 224–236, 1987. [3] T. Towsley and P. O. Vales, “Announced arrival random access protocols,” IEEE Trans. Commun., vol. COM-35, pp. 513–521, May 1987. 1718 IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATONS, VOL. 18, NO. 9, SEPTEMBER 2000 [4] W. Xu and G. Campbell, “A near perfect stable random access protocol for a broadcast channel,” in IEEE Proc. ICC’92, vol. 1, pp. 370–374. [5] , “DQRAP—A distributed queueing random access protocol for a broadcast channel,” presented at the SIGCOMM’93, San Francisco, Sept. 14, 1993. [6] E. Dahlman, P. Beming, J. Knutsson, F. Ovesjö, M. Persson, and C. Roobol, “WCDMA—The radio interface for future mobile multimedia communications,” IEEE Trans. Veh. Technol., vol. 47, Nov. 1998. [7] “UMTS terrestrial radio access: Concept evaluation (UMTS 30.06),” ETSI Tech. Rep. 101 146, version 3.0.0, Dec. 1997. [8] “Requirements for the radio interface(s) for future public land mobile telecommunication systems (FPLMTS),” Recommendation ITU-R M.1034, 1994. [9] A. Chockalingam, W. Xu, and L. Milstein, “Performance of a multichannel packet CDMA protocol in a fading environment,” in Conf. Rec., IEEE Veh. Technol. Conf., VTC’97, 1997. [10] L. Kleinrock, Queueing Systems. New York: Wiley, 1976. [11] X. Zhang and G. Campbell. (1993, Aug.) Performance analysis of distributedqueueingrandomaccessprotocol—DQRAP. DQRAPResearch Group Rep. 93-1, Computer Sci. Dep., Illinois Inst. Technol.. [Online]. Available: http://www.iit.edu/~dqrap/html/papers2.html [12] M. B. Pursley, “Performance evaluation for phase-coded spread-spectrum multiple-access communication—Part I: System analysis,” IEEE Trans. Commun., vol. COM-25, pp. 795–799, Aug. 1977. [13] T. S. Rappaport, J. H. Reed, and B. D.Woerner, “Position location using wireless communications on highways of the future,” IEEE Commun. Mag., pp. 31–44, Oct. 1996. [14] J. Pérez, R. Agustí, and O. Sallent, “Performance analysis of an ISMA CDMA packet data network,” in Proc. IEEE Veh. Technol. Conf., VTC’99 Fall, Amsterdam, Sept. 1999. [15] M. J. Karol, Z. Liu,and K. Y. Eng, “Distributed-queueingrequest update multiple access (DQRUMA) for wireless packet (ATM) networks,” in Proc. ICC’95, Seattle, WA, pp. 1224–1231. [16] A. J. Viterbi, CDMA Principles of Spread Spectrum Communication. Reading, MA: Addison-Wesley , 1995. [17] J. Neyman and E. S. Pearson, “On the problem of the most efficient tests of statistical hypotheses,” , 1933. [18] C.-T. Wu and G. Campbell, “Extended DQRAP (XDQRAP), a cable TV protocol functioning as a distributed switch,” DQRAP Research Group Rep. 94-2. [19] W. Xu and G. Campbell, “DQRAP—A distributed queueing random accessprotocolforabroadcastchannel,”Computer Commun.Rev.,vol.23, no. 4, pp. 270–278, Oct. 1993. Luis Alonso (M’99) received the Engineer degree in telecommunications from the Universitat Politècnica de Catalunya (UPC), Spain, in 1997. He joined the Escola Tècnica Superior d’Enginyeria de Telecomunicació de Barcelona, Spain, as Visitant Professor in 1998. In 1999, he joined the Escola Universitária Politécnica del Baix Llobregat, Spain, where he became Assistant Professor.He is currently doing hisPh.D.thesisaboutmediumaccess protocols, scheduling algorithms, packet radio techniques, and spread-spectrum systems for mobile communications. Ramon Agustí (M’78) was born in Riba-roja d’Ebre, Spain, on August 15, 1951. He received the Engineer of Telecommunications degree from the Universidad Politécnica de Madrid, Spain, in 1973, and the Ph.D. degree from the Universitat Politècnica de Catalunya, Spain, 1978. In 1973, he joined the Escola Técnica Superior d’Enginyers de TelecomunicaciódeBarcelona, Spain,wherehebecame FullProfessorin 1987.Hehasbeen working in the field of digital communications with particular emphasis on digital radio, both fixed radio relay, and mobile communications. He has also been concernedwiththeperformanceanalysisand development offrequency-hopped spread-spectrum systems. He participated in the COST 231, RACE, and ACTS European research programs, and currently is participating in the IST program. His research interests are in the area of mobile communications with special emphasis on CDMA systems and packet radio networks. Oriol Sallent (M’98) received the Engineer and Doctor Engineer degrees in telecommunication from the Universitat Politècnica de Catalunya (UPC), Spain, in 1994 and 1997 respectively. He received the Doctorate Award from the Telecommunication Engineer Association of Spain in 1997 for his Ph.D. dissertation on multiple access protocols for CDMA-based systems. He joined the Escola Tècnica Superior d’Enginyeria de Telecomunicació de Barcelona, where he became Assistant Professor in 1994 and Associate Professor in 1998. His research interests are in the field of mobile communication systems, especially packet radio techniques and spread-spectrum systems.