Analysis of a type II hybrid ARQ strategy in a DS-CDMA packet transmission environment

IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 51, NO. 8, AUGUST 2003 1249 Analysis of a Type II Hybrid ARQ Strategy in a DS-CDMA Packet Transmission Environment Jordi Pérez-Romero, Associate Member, IEEE, Ramón Agustí, Member, IEEE, and Oriol Sallent, Member, IEEE Abstract—In this letter, a type II hybrid automatic repeat request scheme is considered as a retransmission strategy in a direct-sequence code-division multiple-access packet mobile radio network. An analysis based on the Equilibrium Point Analysis is presented to model the behavior of the system in a message-based traffic generation model. A simulation approach is introduced to validate the proposed analytical model obtaining results that closely match those derived theoretically. Index Terms—Automatic repeat request (ARQ), channel coding, code-division multiple access (CDMA), Markov processes, packet radio. I. INTRODUCTION GUARANTEEING transmission reliability at the logical link control (LLC) sublayer in a packet radio link is the main task of the automatic repeat request (ARQ) strategies through the retransmission of those packets that have not been successfully received. The so-called hybrid ARQ strategies are located in an intermediate position between ARQ and forward error correction (FEC) strategies, by combining the best of these two techniques. Basically, there are two hybrid ARQ strategies: the type I hybrid ARQ, which makes use of channel coding to protect the information in a similar way as the FEC strategy, but which also carries out retransmissions whenever the code is unable to correct all the errors in the received packet, and the type II hybrid ARQ (from now on referred to as ARQ-II) where an information packet with only error detecting capability is initially sent and, whenever a retransmission is required, redundancy is transmitted instead of repeating the same packet. As a result, the receiver will make use of this redundancy together with the previous data packet to perform error correction ([1], [2]). Not much effort has been devoted so far in the open literature to assess hybrid ARQ strategies when combined with the multiple access technique scheme direct-sequence code-division multiple access (DS-CDMA) that is emerging as the predominant multiple-access scheme in third-generation mobile communications systems. In [3] a type I hybrid ARQ is considered in a slotted DS-CDMA network in the presence of jamming, while in [4] and [5] a comprehensive analytical model is introduced to evaluate the packet transmission performance in the framework of the combined DS-CDMA ARQ-II technique. However, this model is unable to cope in a manageable Paper approved by B. Jabbari, the Editor for Wireless Multiple Access of the IEEE Communications Society. Manuscript received May 15, 1999; revised July 15, 2001; May 15, 2002; and February 15, 2003. This work was supported by CICYT under Project TIC 2001-2222. The authors are with the Department of Signal Theory and Communications, Universitat Politècnica de Catalunya (UPC), Barcelona 08034, Spain (email: [email protected]; [email protected]; [email protected]). Digital Object Identifier 10.1109/TCOMM.2003.815081 way with the presence of even moderate buffer sizes, which are required by ARQ-II in the transmitter site. In this letter we introduce a novel analytical model, which overcomes the above difficulties by allowing us to consider any buffer size dimensioning together with a more realistic message-based instead of packet-based analysis. In this context, a message is considered to be composed of a variable number of fixed length packets. The present letter is organized as follows: in Section II the ARQ-II scheme in the uplink of a DS-CDMA environment is described, while in Section III a Markov model is presented in order to analyze the system under perfect feedback conditions. Finally, in Section IV the proposed model is compared with simulation results and the conclusions are summarized in Section V. II. DESCRIPTION OF ARQ-II IN A DS-CDMA ENVIRONMENT In order to analyze the performance of ARQ-II in a slotted DS-CDMApacketradionetwork,anumberofuserstransmitting -bit packets in the different time slots in the uplink is considered.Eachuserhasapreviouslyassignedspreadingcode.Perfect power control is assumed to counteract the channel fading. Under these circumstances, the simplified improved Gaussian approximation(SIGA)canbeusedtomodelinterference[6]and obtaintheexpressionforthebit-errorprobability asafunction of the spreading factor and the number of simultaneous users transmitting a packet in a given slot . Users generate messages that are divided into -bit packets which are stored in a buffer. An error detecting code is applied to each packet thus obtaining -bit packets that will be transmitted in the different time slots. A half rate invertible code with error correcting capability is also applied toeach -bitpacketandasaresultan -bitredundancypacketis obtained. Such codes can be obtained from cyclic codes simply by removing some of the bits ([1], [7]). Whenever the feedback information in the downlink indicates that the first bits contain errors, the second bits are transmitted in the next slot and then the receiver can make use of these two packets to decode the information based on . When there are more than errors within these two packets, retransmission of the first bits is required, and then correction is performed again based on the last received set of bits. If it is still necessary, the redundancy will be sent again and alternatively original -bit packet and redundancy will be retransmitted until the information can be decodedsuccessfully.Itshouldbenotedthatwhenitisnotpossible to correct the packet even with the redundancy, retransmissions will be made with probability in the successive slots, which allows the reduction of the number of simultaneous users in the system and therefore of the interference level. Finally, after the 0090-6778/03$17.00 © 2003 IEEE 1250 IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 51, NO. 8, AUGUST 2003 Fig. 1. ARQ-II DS-CDMA system model. packet has been correctly received, normal transmission continues with the rest of the packets in the buffer. Fig. 1 represents the process explained above. The Stop & Wait technique is considered, and the ideal situation in which the feedback information in the downlink is received error free and instantaneously is assumed, so that each user will know whether a new packet or a redundancy must be transmitted in the next slot. Similarly, it will be assumed that the code is able to detect all the residual errors in the packet after the correction procedure ([5]). III. MARKOV MODELING OF ARQ-II DS-CDMA A. Traffic Generation Model Several traffic models have been proposed in the literature in order to approximate the data traffic in a realistic way. A common one is an ON/OFF model where the activity (ON) and inactivity (OFF) periods are exponentially distributed. In this case the ON/OFF dynamics can be modeled by a Markov chain, where the transition probability from the ON to the OFF state is , the probability of remainingin the ON state is , the transition probability from the OFF to the ON state is and the probability of remaining in the OFF state is . During the ON periods, each user generates messages according to a Bernouilli process with the probability of a new message arriving in the next slot (i.e., an arrival rate of messages/slot). Notice that the generation process assimilates a Poisson arrival process by a Bernouilli process, assuming that . Message length is geometrically distributed with a mean ( ) bits and, for simplicity, we assume the parity corresponding to code to be included in this length. Messages are divided into -bit packets and if necessary zeros are added in order to have a -bit multiple. Then, the probability of a new message arriving containing packets in the next slot during the ON period as a function of (i.e., we assimilate an exponential law by a geometrical law by assuming )is (1) B. Markov State Definition Let us consider the DS-CDMA system described in Section II, with a total number of admitted users in the system, each of them containing a buffer with room for packets. System dynamics can be modeled by a Markov process where each user can be in a certain state a the beginning of each time slot. A state is denoted by , where S represents the status of the source (i.e., ), i represents the number of packets waiting for transmission in the buffer and X denotes the type of transmission to be carried out in the next slot (i.e., if the first packet of the buffer will be transmitted for the first time, if the redundancy corresponding to the first packet will be sent for the first time, or when the packet has not been corrected by the initial redundancy, and therefore, information and redundancy are alternatively retransmitted with probability ). The states where the buffer is empty are denoted as and . Therefore, this approach requires states, which represents an important difference from other proposed models in the literature [4], [5], which require each state to consider also the number of errors in the previously transmitted packet and consequently, they need a number of statesproportional to ,which becomesunmanageablewhen increases. C. Successful Transmission Probability and Successful Packet Decoding Probability Considering that errors will be equally distributed within the bits of the packet, the probability of receiving an error-free packet as a function of the bit error probability (that in turn depends on the spreading factor and the number of users transmitting simultaneously according to the expressions given in [6]) is (2) The calculation of the probability of successfully decoding a packet after redundancy transmission is the key point that allows the number of states to be independent from the code correcting capability . Strictly speaking, since the number of simultaneous users may vary from slot to slot, this probability needs to consider the number of simultaneous users and the number of errors in the previous transmission (therefore, the states should take into account this number of errors and the number of states would increase with ). However, as the model intends only to derive the system equilibrium points in the steady-state, the approximation to compute relays on considering as the number of simultaneous users the value in the steady state. The validity of this approximation can be checked afterwards by comparing the predicted results with the obtained through simulations. Accordingly, can be calculated as the probability of there existing fewer than errors in a set of bits (i.e., a set of original packet and redundancy) or there existing no errors in the redundancy packet, given that there is at least one error in the first bits, as shown in (3) at the bottom of the next page. D. State Transition Probabilities and Steady-State Distribution System performance in the steady-state can be evaluated by means of the equilibrium point analysis (EPA) technique, consisting in finding the system equilibrium points IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 51, NO. 8, AUGUST 2003 1251 characterized by the number of users in each state when the system reaches the steady-state distribution. These numbers are given in vectors and . In the steady state, the expected inflow and outflow must be the same for all the possible states. As a result, the following set of equations are defined: (4) Matrix is related to the state transition probabilities (i.e., the probabilities of going from state to state in a given slot) for initial states in the ON period, while matrix is related to state transition probabilities for initial states in the OFF period. For initial states in the ON period the state transition probabilitiesareprovidedinTableIwhenthefinalstateisalsoin the ON period. In the case that the final state is in the OFF period, the state transition probabilities would be the same as in Table I simply by substituting by . In this table, is the probability of a message arriving with more packets than the maximum number allowed by the buffer capacity when the buffer contains packets (i.e., arriving packets or more). When such a situation occurs, the whole message is lost. Regarding , it is obtained when substituting in the values , , and , for , meaning that no new messages are generated in the OFF state. In (4) there are linearly dependent equations and hence, the first row can be suppressed, which leads to another set of equations given by (5) beingasquarematrix , acolumnvector with rows, and vector is obtained by removing the first component of vector . The different state transition probabilities depend on the number of simultaneous users in the system. Its value in the steady state can be related with the rest of variables by means of (6) where (7) TABLE I STATE TRANSITION PROBABILITIES FOR STATES IN THE ON PERIOD Similarly, by considering the total number of admitted users in the system and a single column vector formed by “1”s (8) By combining the lastthree equations the following relationship can be obtained where the only unknown parameter is : (9) Afternumericallysolving thisequationintermsof thevalues of and can be derived, and then parameters that deter- (3) 1252 IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 51, NO. 8, AUGUST 2003 mine system performance can be calculated. For instance, the throughput or number of correctly transmitted packets in each slot will be given by (10) The message loss probability, which is the probability of a message arriving containing more packets than the maximum number allowed by the buffer size, is (11) Denoting the service time of a packet (i.e., the time between its first transmission and the instant when the packet can be decoded correctly), when a -packet message arrives in the buffer and it is accepted (i.e., the buffer has enough room for all of its packets), its total delay will have to include the service time for all of its packets, the service time for the packets that are in the buffer and whose service time has not begun yet , and the residual service time for the packet that is currently being transmitted ([8]). As a result, the average message delay is given by (12) where (13) (14) (15) The mean number of packets in a message that is accepted in the buffer, , is the quotient between the mean number of packets and messages that arrive in a given slot, as shown in (16) at the bottom of the page. IV. MODEL VALIDATION The proposed model has been validated through computer simulations. They consider a number of users distributed in a single cell that generate messages according to the specified traffic model. Interference is modeled with the SIGA method (a) (b) Fig. 2. Comparison of (a) simulated and theoretical message delay and (b) throughput. [6], neglecting thermal noise. Perfect power control is assumed to model the link layer and propagation and compute those packets that are successfully received. The described type II hybrid ARQ strategy is applied to perform retransmissions until the packets are successfully recovered. Fig. 2(a) relates the mean message delay with the total number of users in the system for a given arrival rate. Three predominant regionsare observed. First of all, when the number of users is small, total system interference is low, so the packets are correctly received after the first transmission and thus the mean message delay equals the average number of packets per message. As the number of users increases, interference grows, and it becomes necessary to send the redundancy for each packet, thus requiring two slots for a successful transmission. (16) IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 51, NO. 8, AUGUST 2003 1253 This corresponds to the second region, where the delay is approximately twice that for a low number of users. Finally, when the number of users is large, the redundancy may not be enough to correct all the errors, and therefore, the delay increases due to an increase in the number of required retransmissions. A good agreement between model and simulations can be observed, with only minor discrepancies in the transitions between the three regions described above, due to the considered approximation to suppress the dependence between the number of states and the correcting capability. The same good agreement has been observed with respect to other measurements from the model such as the throughput in Fig. 2(b) or in results with different parameters, not shown for the sake of brevity. Another one of the benefits of the proposed modeling relays on detecting those situations in which, depending on system parameters, the system may exhibit multiple equilibrium points. This situation occurs whenever (9) has more than a single solution: this means that the system can stay around one point for a random length of time and then move and stay around another point. Nevertheless, whenever such a situation occurs, only one of the stable equilibrium points corresponds to a good throughput value, while the others correspond to low throughput. As there is no way of controlling when the system will be in the vicinity of each point, this situation with multiple equilibrium points is undesirable. Whether the system exhibits bistable behavior or not depends on the specific values of all the system parameters ( , offered load, ) and the simplest way to find these regions is by analyzing the behavior of (9) with different parameter values. For example, in Fig. 3 we present the region of bistability depending on and the offered load (offered packets/user/slot) for the case with a buffer length and for traffic sources that remain always in the ON state. It can be observed that this region occurs for small values of the offered load and high values of . V. CONCLUSION An ARQ-II strategy has been studied in a slotted DS-CDMA packet transmission environment. A Markov modeling strategy based on the EPA technique has been presented that can predict the behavior of such a system and quite an accurate match between model and simulations has been shown. This model Fig. 3. Region of bistability for the case U=50 , M=50 as a function of the offered load and probability p . allows the consideration of message oriented statistics with an ON/OFF traffic modeling with Poisson arrivals during the ON periods. Similarly, it allows the determination of those combinations of parameters that can lead the system to an undesirable situation with multiple equilibrium points. REFERENCES [1] S. Lin and P. S. Yu, “A hybrid ARQ scheme with parity retransmission for error control of satellite channels,” IEEE Trans. Commun., vol. COM-30, pp. 1701–1719, July 1982. [2] Y. M. Wang and S. Lin, “A modified selective-repeat type-II hybrid ARQ system and its performance analysis,” IEEE Trans. Commun., vol. COM-31, pp. 593–607, May 1983. [3] J. M. Hanratty and G. L. Stüber, “Performance analysis of hybrid ARQ protocols in a slotted direct sequence code-division multiple-access network: jamming analysis,” IEEE J. Select. Areas Commun., vol. 8, pp. 562–579, May 1990. [4] Q. Zhang, T. F. Wong, and J. S. Lehnert, “Stability of a type-II hybrid ARQ protocol for slotted DS-SSMA packet radio systems,” in Proc. IEEE INFOCOM’98, vol. 3, San Francisco, CA, Apr. 1998, pp. 1301–1308. [5] , “Performance of a type-II hybrid ARQ protocol in slotted DS-SSMA packet radio systems,” IEEE Trans. Commun., vol. 47, pp. 281–290, Feb. 1999. [6] R. K. Morrow, Jr., “Accurate CDMA BER calculations with low computational complexity,” IEEE Trans. Commun., vol. 46, pp. 1413–1417, Nov. 1998. [7] S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice-Hall, 1983. [8] L. Kleinrock, Queueing Systems. Volume I: Theory. New York: Wiley, 1975.