Copyright 1999 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
This article was published in the February 1999 issue of
IEEE Personal Communications.

ABSTRACT

 

In this article we address the problem of link adaptation in a wireless data system. Link adaptation is necessary in order to match the data rate to time-varying channel and interference conditions. We present a robust radio link protocol based on the concept of incremental redundancy (IR). Here, redundant data, for the purpose of error correction, is transmitted only when previously transmitted packets of information are received and acknowledged to be in error. The redundant packet is combined with the previously received (errored) information packets in order to facilitate error correction decoding. If there is a decoding failure, more redundancy is transmitted. It is shown here that an RLP built using the IR concept is more robust and has better throughput than link adaptation schemes using explicit channel measurements such as instantaneous or average signal-to-noise or signal-to-interference ratio. We study the performance of an implementation of a IR-based RLP for EDGE data for and demonstrate its superior throughput and robustness properties. The penalty paid for increased robustness and higher throughput is additional receiver memory and higher delay. IR based RLP has already been standardized for IS-136+ packet data and is being actively considered for EDGE standardization.

 

 

An Adaptive Radio Link Protocol with Enhanced Data Rates for GSM Evolution

 

Robert van Nobelen and Nambi Seshadri, AT&T Labs–Research
Jim Whitehead and Shailender Timiri, AT&T Wireless Services

 

The goal of universal communications is ubiquitous access to and communication of information. Ubiquitous implies any medium, wireless or wired, any media -- from voice to video and their combinations -- and devices from an ordinary phone with very limited visual capability (voice- and communications-centric) to personal computers with large displays (visual- and computing-centric). In this context, an ideal wireless data service should be able to seamlessly support major applications that run on the Internet today, from e-mail to Web access to collaborative computing and multicast. In addition, a wireless network is in a unique position to complement wired data service with mobility-driven applications such as navigation, location-based services, and ubiquitous communications in airports, conference centers, hotels, and so forth.
Unfortunately, today's wireless data networks are afflicted with many problems that prevent this ideal vision from happening, such as: Realizing these limitations, various national as well as international organizations are in the process of defining new wireless data standards [1] that will support higher data rates, larger footprints by means of hierarchical cells (pico-, micro-, or macrocellular systems), multimode terminal rates, and terminal-scalable applications, thus encouraging the development of more wireless data applications.

Current Standards

Wireless data systems can be classified into two classes based on whether they are wide area networks or local area networks [2]. Wide-area services include standards such as Cellular Digital Packet Data (CDPD), ARDIS, Metricom's Ricochet packet data service, as well as data services based on cellular standards (IS-136 GSM, IS-95, PDC). While CDPD and ARDIS are macrocellular networks, Ricochet is a microcellular network. They also differ in their data rates, with CDPD providing peak data rates of 19.2 kb/s and Ricochet providing up to 100 kb/s packet- and circuit-switched data.
All the digital cellular and personal communications services (PCS) standards support circuit- and packet-switched data. Perhaps the farthest along in data standard is Global System for Mobile Communications (GSM), the time-division multiple access (TDMA)-based European cellular standard, which supports circuit-switched data from 2.4–14.4 kb/s. Several high-bit-rate services will be available in the near future, including a packet data service called the General Packet Radio Service (GPRS) [3, 4] with data rates of up to 100 kb/s when an entire 200 kHz carrier and all eight time slots are allocated.
IS-136, the North American TDMA standard, will support a packet mode with data rates between 40–64 kb/s by aggregating time slots and introducing higher-level modulation such as eight-level modulation (instead of the four-level modulation used now) [5]. Personal Digital Cellular (PDC), the Japanese narrowband cellular service, is similar to IS-136 and will soon offer packet data services as well.
IS-95, the North American direct sequence code-division multiple access (DS-CDMA) standard, also supports circuit-switched data up to 14.4 kb/s. A new standard for a 64 kb/s integrated services digital network (ISDN) B channel along with a D channel for signaling has been approved which will facilitate ISDN as well as high-speed circuit-switched data [6].
In contrast to the wide-area wireless standards, wireless LANs provide a limited transmission range and are limited in their frequency reuse capability (noncellular). But because of their limited transmission range and wider bandwidths than cellular, they can provide data rates of 2–8 Mb/s. New wireless LAN standards such as High-Performance LAN (HIPERLAN) promise to deliver data rates of up to 20 Mb/s [7].
An interesting question is whether it is possible to engineer wide-area cellular networks that rival the data rates of today's wireless LANs (1–10 Mb/s) using a system bandwidth of 1–5 mHz. If so, what will be data rates for next-generation wireless LANs? In this, regard, work such as advanced cellular Internet service (ACIS) [8] is a promising step.

Future Wireless Data Standards

Significant activity is occurring worldwide today to develop third-generation cellular standards such as International Mobile Telecommunications by the year 2000 (IMT-2000). These systems aim to provide a wide range of services from high-quality voice and data rates of 144 kb/s in wide-area vehicular environments and up to 2 Mb/s in indoor and picocellular environments. The main activity is defining spectrally efficient air interfaces that range from evolution of GSM (200 kHz channelization) by changing the modulation to support higher data rates, to defining wideband air interfaces based on CDMA. However such changes necessarily come with the penalty of not being able to offer the peak rate throughout the cell because of lower noise and interference immunity at higher data rates, thus requiring rate adaptation techniques such as changing the coding and modulation format for GSM and changing the spreading factor for CDMA. This naturally raises some interesting questions at the system level such as designing adaptive radio link protocols, medium access control, QoS provisioning, and so on. We believe these issues are equally important as the design of the wireless pipe. Throughout the rest of this article, the focus will be on one of these issues, that is, the design of an adaptive radio link protocol that is robust to signal and interference variations but provides high throughput efficiency.
The rest of the article is organized as follows. The next section addresses key issues regarding the changing nature of the wireless channel and the need for link adaptation. The article goes on to describe the Incremental Redundancy (IR) protocol for a TDMA system based on Enhanced Data Services for GSM Evolution (EDGE). We present performance results of the IR transmission scheme compared to conventional adaptive coding and modulation schemes in the context of EDGE. The last section has conclusions.

Wireless Channels and Link Adaptation

Wireless data channels are subject to significant interference and fading as well as propagation variations, resulting in widely varying received signal quality [9]. Signal variation is due to three main causes:
  • Variation of received signal strength with distance from the transmitter
  • Shadow fading (large timescale) caused by large obstructions
  • Rayleigh fading caused by local scatterers around the receiver
Furthermore, in packet data systems the bursty nature of data traffic [10] also causes rapid changes in interference characteristics. In order to handle such rapid variations in signal conditions, techniques that adapt the bit rate to channel conditions are being proposed for next- (third-)generation wireless systems. Link adaptation techniques are usually used in voiceband modems during the start of a dialup session. In a wireless channel, link adaptation should occur more frequently because of the rapid changes in signal and interference environment. Link adaptation (also called mode switching or adaptive coding and modulation) requires feedback information from the receiver to the transmitter about the link conditions. Normally, such information consists of parameters such as mean carrier-to-interference ratio (C/I) or signal-to-noise ratio (SNR), standard deviation of SNR channel impulse response characterization, bit error statistics (mean and standard deviation), and packet error rate. In this article we study conventional link adaptation techniques that use such feedback information as well as a technique that performs link adaptation in an implicit manner by purely relying on acknowledgement (ACK/NACK) information from the radio link layer. We present a specific implementation of our implicit link adaptation technique for next-generation GSM, called Enhanced Data for GSM Evolution [11,12].
EDGE is an enhancement to GSM that aims to increase data rates to over 384 kb/s. This rate increase is achieved by introducing a higher-level modulation format, namely 8-phase shift keying (PSK) which transmits 3 b/symbol, instead of the current GSM modulation, which uses a technique called Gaussian minimum shift keying (GMSK) that transmits 1 b/symbol [13]. The penalty incurred by a higher modulation format is an increase in the frame error rate (FER) at the physical layer, especially at low SNR or C/I. We will use SNR and C/I interchangeably. The FER may be reduced to acceptable levels by employing a forward error correction (FEC) code. The residual frame errors are corrected at the link layer by using a selective automatic repeat request (ARQ) scheme; that is, whenever a frame is received in error, the receiver requests that it be retransmitted until decoding is successful [14]. The combination of an FEC code and the ARQ scheme will operate efficiently when designed for a specific SNR operating point. However, deviation from this SNR operating point quickly reduces the efficiency of the scheme; at lower SNR the FER rapidly increases, eventually reducing the throughput to zero, while at higher SNR the FEC coding rate is lower than necessary, and therefore does not yield maximum throughput.
Due to limited available spectrum, in the United States EDGE is expected to be deployed in a reuse 1/3 cellular pattern, meaning that all cells reuse the same set of frequencies on a three-sector basis. With such a tight reuse pattern, interference seen from users in other cells is high, and the value of the SNR as a mobile travels within a cell is anywhere between 0 and 35 dB. With such a wide dynamic range, there is clearly no fixed operating point for a particular FEC design. The solution in the preliminary EDGE proposal is to define six different coding and modulation schemes, as described in Table 1 (PCS1–PCS-6, PCS-6 the least robust and PCS-1 the most), each designed to operate efficiently on part of the expected SNR range. The idea, then, is to select the most appropriate coding scheme for transmission at the currently experienced SNR level, thus realizing link adaptation.
Although in principle this is a reasonable solution, there are a number of unclear practical issues:
  • The SNR needs to be measured at the receiver: It is difficult to obtain an accurate estimate of the instantaneous SNR over a short time interval.
  • There is a delay in feeding back the SNR information: By the time the transmitter selects a new coding and modulation format, the channel conditions may have changed. This would be less of an issue if the channel noise and interference varied slowly and smoothly; however, co-channel interferers turn on and off in an unpredictable manner, resulting in discontinuous jumps of many decibels in SNR level.
  • For the initial transmission of any packet, the present channel conditions may be unknown at the transmitter. If this is the case, it is likely that the majority of the short packets will be transmitted using a nonideal coding and modulation format.
  • Whenever a block fails to be decoded, it is unclear whether the block should be retransmitted using the same coding and modulation format. This could result in unwanted behavior if, for example, the initial transmission used PCS-6 (uncoded modulation) at 30 dB SNR, and the SNR dropped to 10 dB due to a nearby interferer turning on. There would be a close to zero probability of retransmission success until the SNR increased again, therefore stalling the data flow. A timeout mechanism would introduce unnecessary delays and cause frame discards at the higher layers. If a different coding and modulation scheme is used at the physical layer, resegmentation of the previously block transmitted block is necessary.
  • The optimal switching points between different codes are a function of the speed of the mobile, interference characteristics, and other factors.
We present a solution to the above problems by replacing mode switching with a radio link protocol (RLP) that dynamically adjusts the code rate to match the average SNR of the system and realization of the random processes affecting the transmitted signal. The protocol operates by incrementally transmitting additional redundant information whenever decoding of a block fails. The additional redundant information can be combined with the previously transmitted information, resulting in enhanced decoding. Incremental redundancy transmission is well known to the practitioners of error control coding. What is new here is the design of an RLP that can take advantage of this physical-layer feature to improve performance. Incremental Redundancy (IR) transmission is already a part of the next-generation TDMA standard for packet data [15]. It is also being actively considered for EDGE. The purpose of this article is to illustrate the main idea of IR and how it can be incorporated into an RLP. The protocol presented should not be construed as the final design for either the TDMA or EDGE standard. We compare the proposed scheme to a link adaptation scheme that has knowledge of the correct signal quality. However, to be realistic, we assume that such a measure is available and is communicated to the transmitter with a delay of 200 ms.

The Incremental Redundancy Radio Link Protocol

This section describes the IR protocol in a general context.

Position in the Protocol Stack

The purpose of the RLP is to asynchronously transport data between unspecified layer 3 entities. It is positioned between the physical layer (layer 1) and the network layer (layer 3), as shown in Fig. 1. The description presented here is concerned only with the data transport aspects of the protocol, not link establishment, link supervision, link termination, or flow control.
The EDGE Physical Layer -- Figure 2 shows the TDMA slot structure of the EDGE physical layer. Each TDMA frame is of approximately 0.461 ms duration and divided into eight slots. Each slot contains 169 symbols, of which 114 are available for data transmission. The current proposal for the physical-layer frame or radio block is to encode data over 4 slots (i.e., 456 symbols) using one of six coding and modulation schemes, PCS-1–PCS-6. The actual coding scheme to be used for transmission is selected depending on channel conditions measured at the receiver.
The payload of each radio block depends on the coding and modulation scheme, as shown in Table 1. The fourth column of Table 1 lists the raw payload of each coding scheme, that is, the number of data bits carried by the physical layer alone. The payload as seen by the logical link control (LLC) layer is shown in the fifth column. This number is the raw physical payload less 48 overhead bits comprising the MAC header, the block check sequence, and the RLC block sequence number for the purposes of the selective repeat ARQ protocol. The last column shows the maximum LLC data rate per slot per second (this does not take into account the LLC framing and segmentation overhead).

The Incremental RLP Structure

Figure 3 shows a block diagram of the data transport component of the IR RLP. The purpose of the protocol is to transport service data units (SDUs) received from layer 3 over the physical layer. The SDUs are octets and are to be delivered in sequence to layer 3 on the receiving side. The following sections describe the components of Fig. 3 in detail.
The Data Blocker -- The data blocker accepts SDUs from the transmitting layer 3 and constructs a blocked SDU by concatenating LData data bits and a frame check sequence (FCS). The FCS is a cyclic redundancy check (CRC) of length LDCRC computed over the corresponding data bits. Figure 4 shows the format of block Bi. The lengths LData and LDCRC are design parameters to be optimized. The blocks Bi of length LBlock = LData + LDCRC are passed to the encoder, described next.
The Encoder -- The channel encoder is a rate R = 1/2 convolutional code, that is, for every information bit, 1 bit of redundancy is added. From the blocked SDU Bi, the encoders output 2D subblocks of length LSubblock = Lblock/D. For the purpose of illustration, these subblocks are divided into two categories, namely data and parity subblocks, denoted Dij and Pij(j = 1...D), respectively. Data subblocks Di1–DiD contain no redundancy and represent a one-to-one mapping to the blocked SDU Bi. Parity subblocks Pi1–PiD contain parity information derived from Bi and are used by the protocol for FEC upon decoding failure at the receiving side. The subblocks are derived from Bi by a rate 1/2 binary convolutional encoder, as shown in Fig. 5. The encoded subblocks are passed to the sending RLP for transmission.
The Sending RLP -- The RLP is required to transport the blocked SDUs Bi to the receiving side, and to deliver them in sequence to layer 3. The RLP does this by initially sending just the data subblocks Di1, ..., DiD, followed by sending additional parity subblocks Pij whenever the receiver fails to decode block Bi correctly. The transmitter cannot discard the data parity subblocks corresponding to block Bi until it has received a positive acknowledgment from the receiver for Bi; hence, the protocol operates by maintaining in a table the subblocks that have been transmitted but not yet acknowledged. An example transmit table is shown in Fig. 6. In this example the protocol operates with D = 4. The table contains the following fields:
  • NS is the sequence number assigned by the sending RLP to each block Bi. The sequence number is i mod WS, where WS is the window size.
  • B is a flag denoting whether or not the corresponding block Bi has been successfully decoded by the receiver. A 0 indicates that the entry is undecoded.
  • R indicates whether the sending RLP needs to transmit more information about block Bi to the receiving RLP.
  • MC indicates whether the protocol has sent nonconsecutive multiple subblocks of block Bi. A 1 indicates yes, 0 no.
  • BD1–BDD indicate whether subblocks D1–DD have been received, respectively. A 0 indicates unreceived.
  • BP1–BPD indicate whether subblocks P1–PD have been received, respectively. A 0 indicates unreceived.
  • Data contains the data and parity {Di1, ..., DiD, Pi1, ..., PiD} subblocks corresponding to block Bi.
The sending RLP uses the following procedure:
  1. Read the feedback packet.
  2. Update the flags B, BD1, ..., BDD , and BP1, ..., BPD . Set the index variable KR to the point at the entry farthest down in the table for which one of the B flags was updated (i.e., changed from 0 to 1) and for which MC = 0.
  3. For each transmit table entry from the first to the entry KR (determined at step 2), set R to 1 and MC to 0.
  4. Delete all entries in the table with B set to 1.
  5. If the last entry in the table has R set to 1, go to step 9.
  6. Find the first entry with R set to 1, move it to the bottom of the table, and go to step 9. If there is no entry with R set to 1, go to 7.
  7. If the window is not full and there are data subblocks at the encoder output corresponding to a data block Bi, retrieve subblocks Di1–DiD and Pi1–PiD from the encoder, assign the next NS, set B and MC to 0, R to 1, place the entry at the bottom of the table, and go to step 9; otherwise, go to step 8.
  8. If the table is empty, stop; otherwise, move the first table entry to the bottom of the table, set MC and R to 1, and go to step 9.
  9. If all data subblocks have been transmitted, send the next parity subblock and set R = 0; otherwise, send the next data subblock.
Note that for transmission, the subblocks are combined with a header, as described in the next section.
Transmitting the PDU Format -- The transmitting RLP sends the data subblocks encapsulated in the physical-layer frame format. Each physical-layer frame consists of a header, and a combination of any ND data and/or parity subblocks as decided by step 9 of the sending protocol procedure. Figure 7 shows the case for ND = 2 for the purpose of illustration, but the format generalizes to larger or smaller values of ND.
The header is rate RHEADER encoded to ensure a sufficient decoding reliability and contains the following fields:
  • NS1...NSND are the block sequence numbers corresponding to the subblocks contained in the frame. Each of these fields is of length LNS bits.
  • NB1–NBND are the subblock sequence numbers corresponding to the subblocks contained in the frame. Each of these fields is of length LNB. The number NB represents which subblock of block Bi is being transmitted. The length LNB is related to D by LNB = log2(2D)
  • A CRC of length LHRC is an FCS over the header bits only. This FCS is used to ensure the integrity of the header information.
The total RLP PDU length is LPDU, which is the layer 1 transmission packet length and is a design parameter to be optimized. It is a function of the number of slots over which a transmission occurs and the modulation format.
The Receiving RLP -- The receiving RLP is the peer of the sending RLP and is responsible for combining the received subblocks and jointly decoding them to recover data blocks Bi. The receive table is complementary to the transmit table, and stores the received subblocks and decoded blocks until they can be delivered in sequence to layer 3. It is well known in the error correction community that decoder performance is considerably enhanced when the received information contains reliability information about each received bit. The reliability information (also called soft decision) results in more memory. The table has the form shown in Fig. 8 and contains the following fields:
  • NS is the block sequence number.
  • BF indicates whether the corresponding block has been decoded successfully. A 1 indicates success.
  • BD1–BDD indicate whether data subblocks Di1–DiD have been received, respectively.
  • BP1–BPD indicate whether parity subblocks Pi1–PiD have been received, respectively.
  • Data contains the soft decision data and parity {Di1, ..., DiD, Pi1, ..., PiD} subblocks corresponding to block Bi.
The receiving RLP follows the following procedure:
  • If available, retrieve a received soft-decision PDUU´t from layer 1, decode the header, and check its RC. If it fails, discard the PDU and go to step 6; otherwise, go to step 3.
  • If BF corresponding to the received NS is set to 1, discard the received PDU and go to step 6; otherwise, go to 3.
  • Set the flag BDj or PDj as specified by NB to 1. Use the quantizer to quantize the soft decision bits of U´t and store the subblock information at the location corresponding to NS and NB in the receive table. If this subblock was already received earlier, add the soft decision metrics.
  • Pass the quantized soft information subblocks corresponding to NS already stored in the table to the decoder and the full soft information of the most recently received subblock. Decode this set of subblocks and compute the FCS. If the FCS passes, store the decoded block in place of the soft decision data and set the flag BF to 1.
  • If the first receive table entry has BF set to 1, deliver the decoded blocks from the first entry up to, but not including, the first entry with BF = 0. Delete the delivered receive table entries.
  • Set NR to the value of NS of the first entry in the table.
  • If a PDU was received or the receiver table is not empty, send the feedback packet created from the receiver table; otherwise, send nothing.
The decoding operation of step 4 is implemented by the decoder described in the following section.
The Decoder -- The decoder corresponds to the transmit encoder of an earlier section. It is passed the subset of received soft-decision subblocks {D´1, ..., D´D, P´1, ..., P´D} and attempts to decode using the soft decision Viterbi algorithm. Any missing soft bits are treated as erasures by the decoding algorithm. The decoder output B´i corresponding to the sending B´i is checked for correct decoding by the FCS decoder.
The FCS Decoder -- The decoder output B´i is passed to the FCS decoder, which computes the FCS of B´i and indicates to the receiving RLP whether the received block passed the frame check.
The Incremental Redundancy Deblocker -- The deblocker performs the inverse operation to the blocker of an earlier section and delivers the deblocked SDUs to layer 3.

Performance Results

Due to space limitations, we will not discuss overheads specific to incorporating IR into EDGE. It is assumed that the MAC protocol is the same as defined in GPRS [3]. This overhead consists of the general MAC header information, temporary flow indicator, block check sequence for the RLC payload, and block sequence number ARQ for the overhead within each PDU block size of 1392 bits is 100 bits for D = 2 and 92 bits for D = 4. It is important to pick an appropriate value of D; larger D results in throughput improvement, but increases delay. We believe that D = 2 is a good compromise, as shown by our simulation results. In this section we present the IR protocol performance compared to pure adaptive coding and modulation formats. We compare the two schemes for the cases of a noise-limited system and an interference-limited system. The following assumptions were made in all the simulations regarding the physical layer:
  • Coherent detection
  • Ideal channel state information (CSI) (The effect of nonideal channel state information through practical estimation methods is assumed to affect each protocol equally; hence, their relative performance remains the same.)
  • Zero intersymbol interference, perfect symbol timing
  • No frequency hopping

A Noise-Limited System

First, we present results that compare the performance of the IR transmission scheme and the mode switching scheme in a purely noise-limited system. Depending on the transmitted power, distance of the receiver from the transmitter, propagation characteristics, and internal receiver noise, the received signal will be subject to a certain average SNR. There will be variations around this average SNR due to local scattering resulting in Rayleigh fading. The Rayleigh faded signal varies depending on the speed of the receiver relative to the transmitter and the carrier frequency (which is assumed to be 900 MHz). Each scheme transmits data continuously over a purely flat fading Rayleigh channel using a 900 MHz carrier. The throughput and delay results are plotted as a function of the average SNR.

Simulation Details

Incremental Redundancy Transmission -- The IR scheme was simulated for the two values of D = 2 (see Appendix) and D = 4 (i.e., 2 subblocks/SDU and 4 subblocks/SDU). The ARQ feedback round-trip time was assumed to be 10 coding blocks, or approximately 200 ms with no feedback errors or losses. This is a reasonable assumption since feedback packets are error protected more heavily than normal traffic packets.
The rate 1/2 IR convolutional encoder is a nonsystematic 64-state code with generators G0 = 1011011 and G1 = 1111001. In the case of D = 2, the data subblocks Dk1and Dk2 are formed from the even and odd bits, respectively, generated by G0, while the parity subblocks Pk1 and Pk2 are formed from the even and odd bits generated by G1. Similarly, for D = 4, each data/parity subblock is formed from every fourth bit of their respective generators.
Each 1392-bit SDU is interleaved over four slots for transmission as follows:
  • Denote the nth bit of the 1392-bit SDU s[n], n = 0...1391.
  • Form four 348-bit blocks B0 to B3, where Bk[m] = s[4m + k], m = 0...347, k = 0...3.
  • Interleave each Bk using a 29-column x 12-row block interleaver to form the slot data Sk. The interleaver is filled column by column and read row by row.
  • Transmit each slot Sk by mapping onto a naturally labeled (i.e., 0–7 counter-clockwise) 8-PSK constellation.
Mode Switching -- The throughput curves for each of the six encoding schemes described in Table 1 were obtained by simulating each encoding scheme at each average SNR level. It is assumed, unless stated otherwise, that the average SNR is measured correctly, but there is a feedback delay of about 200 ms (which is consistent with implementations), and that an ideal mode switching algorithm (i.e., the code that maximizes the throughput) is used. We further assume that the code can be adapted every four slots.
Blocks received in error were retransmitted until successfully received using a selective repeat ARQ scheme operating in a manner similar to that described in [16]. The window size used was 127 (i.e., 8 b/BSN). The overhead in each block was 48 bits, consistent with GPRS implementation. The ARQ feedback round-trip time was assumed to be 10 coding blocks, or approximately 200 ms with no feedback errors or losses.
Throughput -- Figure 9 shows the throughput results of the proposed protocol compared to the EDGE coding and modulation schemes, PCS-1–PCS-6, for a slow mobile speed of 3 km/hr. The x-axis plots the average SNR, the y-axis throughput in kilobits per second per slot. The two cases of the IR transmission system (D = 2 and D = 4) are also plotted.
The throughput of the IR protocol for D = 4 outperforms the case for D = 2 because the redundancy increments are smaller relative to the SDU block size. For example, for D = 4 the first additional increment changes the code rate from rate 1 to rate 4/5, while for D = 2 it jumps immediately to rate 2/3. However, as shown in the section on delay results, D = 4 suffers from increased delays due to a higher number of incremental subblocks required per successful transmission.
IR transmission significantly outperforms ideal mode switching in the range of 5–25 dB. At very high SNR, the greater overhead of IR transmission leads to a slightly lower maximum throughput relative to a mode-switched system.
Figure 10 again shows the throughput of the IR systems against PCS-1–PCS-6, but now for a mobile moving at 100 km/hr. The results are similar to those of Fig. 9, but with a loss in throughput due to a higher probability of experiencing a deep fade within a block as a result of traveling at a higher speed. Figures 9 and 10 highlight a problem with mode switching in that the optimal switching points are a function of the speed of the mobile; for example, the switching point from PCS-5 to PCS-6 at 3 km/hr occurs at around 21 dB, while at 100 km/hr it occurs at 27.5 dB.
Delay -- In general, the average delay of an IR transmission system is higher than that of a mode-switching scheme at lower SNR levels due to the code rate convergence time. This effect may be mitigated if a coarse channel quality estimate is available at the transmitter, in which case more subblocks can be transmitted during the first transmission of a block. Figure 11 plots the delay profiles of mode switching and IR transmission as a function of the SNR level, assuming a feedback round-trip time of 200 ms (i.e., 10 coding blocks).
The mode switching delay has been measured as the time from when a code block enters the sending protocol to when it is delivered in sequence (i.e., block n cannot be delivered before block n – 1) by the receiving protocol to layer 3. Similarly, the IR protocol delay is measured as the time between when an SDU enters the sending protocol to when it is delivered in sequence to the next layer.
Figure 12 shows the delay profiles for both systems at 100 km/hr. Clearly, data transfer stalls below 5 dB, and switching to a more robust modulation such as native GMSK is required.

An Interference-Limited System

The previous section presented throughput results when operating in a static noise environment. A practical system, however, experiences rapidly varying C/I due to shadow fading, interferers turning on and off, as well as Rayleigh fading. In the following section we describe a simple model for such variations, and present the results of mode switching and IR transmission operating in such an environment.
The System Model -- Our system model consists of a cellular system with 1/3 reuse. (1) signals that the full spectrum is used in every cell. (3) corresponds to the fact that each cell is divided into three sectors, and a third of the total spectrum is used in each sector.
We model the interference seen from each base station i by the mobile under consideration as an additive white Gaussian noise (AWGN) on/off process where:
  • The power level is proportional to 1/d4 plus random log-normal shadow fading with standard deviation of 6 dB; d is the distance from base station i to the mobile.
  • The amplitude is modulated by Rayleigh fading, independent from interferer to interferer.
  • The on/off process is generated by a two-state Markov chain, modeling packet transmissions.
The Markov chain shown in Fig. 13 generates a random on/off sequence modeling random packet transmissions. The chain parameters P01 and P10 are computed to give the desired system load and average packet size. The system load is ratio of on time to total time.
Assuming unsynchronized base stations, each interferer's slot structure timing is offset uniformly random relative to the downlink under consideration, as shown in Fig. 14. Unsynchronized operation leads to each downlink slot seeing two partially overlapping interfering slots.
In summary, the channel interference is computed as follows:
  1. Compute the power level of each interferer as 1/d4 + S, where S is log-normal shadow fading with standard deviation of 6 dB.
  2. If the interferer is in the on state, generate an AWGN process at the power level determined at step 1, Rayleigh fade the result, and add them to the downlink signal using the slot offset structure of Figure 14.
  3. Repeat 2 for every slot, and reselect S, every second.
Results -- We compare the throughput performance of the IR protocol with the mode switching system operating in the interference-limited model as a function of the system load. The simulation parameters were as follows:
  • A round-trip delay of 200 ms
  • Shadow fading of 6 dB, with new values selected every second
  • An average interferer packet size of 1000 bytes
  • Ideal CSI
The IR transmission protocol was simulated as presented in the previous sections with a parameter value of D = 2. The mode switching scheme was simulated for two cases:
  • Ideal mode switching with no ARQ retransmission scheme. The transmitter receives an ideal channel quality measurement from the receiver every 200 ms delayed by 20 ms. This value is simply the most recently measured channel state. The transmitter decides on the coding scheme based on the throughput curves of Fig. 9. The throughput is computed simply by using 1 – FER for each block multiplied by its payload.
  • Ideal mode switching with an IS-130 derived selective retransmission protocol. Since this protocol is based on block retransmissions, it is necessary when retransmitting data to use the same coding and modulation scheme as used in the original transmission even if at that point in time it is not the most efficient coding scheme for the channel quality experienced. The protocol has been modified such that out of the list of blocks requiring retransmission, the block that most closely matches the current channel conditions is transmitted in preference over the others (as opposed to the oldest block as in the current IS-130 specifications).
Cell Median -- These results are for a mobile located at the cell median distance; that is, on average 50 percent of users are closer to the base station than this, and 50 percent further away from it. Three throughput curves are plotted in Fig. 13, namely for incremental redundancy transmission, ideal mode switching, and mode switching with the selective repeat protocol. At an expected system loading of between 0.4 (40 percent) and 0.5 (50 percent), IR transmission increases throughput by about 10 kb/s per slot over mode switching with a selective repeat protocol.
Figure 16 plots the average delay corresponding to the throughput curves of Fig. 15 for the IR RLP and the modified mode-switched RLP-1 protocol. The mode-switched protocol suffers a greater delay because of the requirement to retransmit a block using the same coding scheme as its initial transmission.
Cell Edge -- These results are for the worst-case scenario of the user being located at the edge of the cell, where the average interference is the greatest. As Fig. 17 shows, at a load of 40–50 percent the increase in throughput is approximately 9 kb/s per slot.
Figure 18 plots the average delay for the two protocols corresponding to the throughput curves of Fig. 17. Again, the mode-switching RLP-1 protocol suffers greater delays due to trying to retransmit using the same coding scheme as the initial transmission.

Conclusions

We present an overview of link adaptation techniques in cellular systems. Link adaptation is crucial for the operation of wireless data systems since the channel quality varies substantially. The channel quality is a function of the distance of user from base station, local and average fading conditions, interference, interference variations, and other factors. We present the design of a radio link protocol based on incremental redundancy transmission. In this scheme, the code rate is dynamically adjusted until decoding is successful, which means that explicit knowledge of SNR is not necessary. We have shown how such a protocol can be incorporated into an EDGE/GPRS-based system within the currently proposed physical channel and RLC structures. The scheme offers two advantages: it reduces reliance on mode switching, and increases average system throughput. The cost is increased complexity and greater memory requirements at the receiver. Given such wide variations in throughput and delay performance, it is an interesting question whether any quality of service provisioning is possible. The incremental redundancy concept is part of the IS-136 packet data standard and is being actively considered for EDGE.

References
 [1] R. Prasad, J. S. DaSilva, and B. Arroyo-Fernandez, (Guest Editors), "ACTS Mobile Program in Europe, " IEEE Pers. Commun., vol. 36, no. 2, Feb. 1998, pp. 80–136.
[2] D. C. Cox, "Wireless Personal Communications: What Is It?" IEEE Pers. Commun., vol. 2, no. 2, Apr. 1995, pp. 20–35.
[3] G. Brasche and B. Walker, " Concepts, Services, and Protocols of the New GSM Phase 2+ General Packet Radio Services," IEEE Commun. Mag., vol. 35, no. 8, Aug.1997, pp. 94–101.
[4] J. Cain and D. J. Goodman, "General Packet Radio Service in GSM," IEEE Commun. Mag., Oct. 1997, pp. 122–31.
[5] N. R. Sollenberger, N. Seshadri, and R. V. Cox, "The Evolution of IS-136 TDMA for Third Generation Wireless Services," to appear, IEEE Pers. Commun. Mag..
[6] D. N. Kinsley et al., "Evolution of Wireless Data services: IS-95 to CDMA 2000, IEEE Commun. Mag., vol. 36, no. 10, Oct. 1998, pp. 140–49.
[7] ETSI TC_RES 06 921, "High Performance Radio local Area Network (HIPERLAN): Functional Specification," draft for ETS 300 652, Sophia Antipolis, France, July 1995.
[8] L. J. Cimini., Jr., J. C-I Chuang, and N. R. Sollenberger, "Advanced Cellular Internet Service (ACIS)," IEEE Commun. Mag., vol. 36, no. 10, Oct. 1998, pp. 150–59.
[9] W. C. Jakes Jr., Microwave Mobile Communication, Wiley, 1974.
[10] W. Willinger, M. S. Taqqu, and A Eramilli, "A Bibliographical Guide to Self-Similar Traffic and Performance Modeling for Modern High Speed Networks," Stohastic Networks: Theory and Applications, Royal Statistical Lecture Note Series, vol. 4, F. P. Kelly, S Zacharu, and I. Zeidins, Eds. Oxford, U.K.: Clarendon Press, 1996, pp. 339–66.
[11] P. Schram et al., Radio Interface Performance of EDGE, a proposal for Enhanced Data Rates in Existing Cellular Systems, IEEE VTC, May 1998.
[12] A. Furuskär et al., "System Performance of EDGE, a Proposal for Enhanced Data Rates in existing Cellular Systems," IEEE VTC, May 1998.
[13] D. J. Goodman, Wireless Personal Communications Systems, Addison-Wesley, 1997.
[14] S. Lin, D. J. Costello Jr., and M. J. Miller," Automatic-Repeat-Request Error Control Schemes," IEEE Commun. Mag., vol. 22, Dec. 1984, pp. 5–17.
[15] R. van Nobelen, "Toward Higher Data Rates in IS-136," Proc. IEEE VTC, May 1998, pp. 2403–7.
[16] S. Nanda, B. T. Doshi, and R. P. Ejzak. " A retransmission scheme for circuit mode data on wireless kinks," IEEE JSAC, vol. JSAC-12, Oct. 1994, pp. 1338–52.

Biographies
 Robert van Nobelen received B.E. (hons), M.E., and Ph.D. degrees in electrical and electronic engineering from the University of Canterbury, Christchurch, New Zealand, in 1991, 1993, and 1996, respectively. From 1997 to 1998 he wa a senior technical staff member in the Communications Research Department of AT&T Labs–Research, Florham Park, New Jersey. His research interests are convolutional, trellis, and turbo coding for fading channels, channel modeling techniques, and radio-link and MAC protocols.
Nambi Seshadri received a Bachelor's degree in electronics and communications engineering from University of Madras, India, in 1982, and M.S. and Ph.D. degrees in electrical and computer engineering from Rensselaer Polytechnic Institute, Troy, New York, in 1984 and 1986, respectively. He is head of the Communications Research Department at AT&T Laboratories, Florham Park, New Jersey. Prior to this he was a Distinguished Member of Technical Staff at AT&T Bell Laboratories, Murray Hill, New Jersey. Research activities in his department coves a broad range of signal processing and communications concepts. These include signal analysis for compression and transmission, error-resilient signal compression techniques, new transmission techniques for wireless such as space-time coding, radio link adaptation algorithms and protocol design, and software tools for wireless engineering. He was the Associate Editor of Coding Techniques for IEEE Transactions on Information Theory from 1996 to 1998.
Jim Whitehead has worked at Bell Laboratories and AT&T Research since 1977, and there he has designed and evaluated wireless system control algorithms, radio resource management methods, radio network design tools, MAC and ARQ protocols, and such. Currently he works at AT&T Wireless, Redmond, Washington, planning high-speed data services and managing related standards activities.
Shailender Timiri is a senior member of the technical team at AT&T Wireless Services, Redmond, Washington. He received his B.Tech degree in electrical engineering from the Indian Institute of Technology, Bombay, in 1982 and his M.S.E.E. in 1985 from the University of Toledo. He has been with AT&T since 1985. His background includes work in adaptive control, circuit design, VBSI, programmable logic device modeling and simulation, RF instrumentation, and RF system design. Currently he is involved in air interface standards development for IS-136+ and 3G systems.