HK1076951B - Method and apparatus for fast closed-loop rate adaptation in a high rate packet data transmission - Google Patents

Description

Method and apparatus for fast closed loop rate adaptation in high rate packet data transmission

Background

Field of the invention

The present invention relates to data communication. More particularly, the present invention relates to a novel and improved method and apparatus for fast closed-loop rate adaptation in high rate packet data transmissions.

Second, description of related Art

Mobile computing and data access is becoming available to an ever increasing number of users. The development and introduction of new data services and technologies that will provide continuous data connectivity and full access to information is emerging. Users are now able to use a variety of electronic devices to retrieve voice or data information stored on other electronic devices or data networks. Some of these electronic devices can be connected to the data source by wires, while some can be connected to the data source by wireless solutions. As used herein, an access terminal is a device that provides data connectivity to a user. An access terminal may be coupled to a computing device such as a desktop computer, laptop computer, or Personal Digital Assistant (PDA), or it may be physically incorporated into any such device. An access point is a device that provides a data connection between a packet-switched data network and an access terminal.

One example of an access terminal that may be used to provide a wireless connection is a mobile telephone that is part of a communication system capable of supporting a variety of applications. One such communication system IS a Code Division Multiple Access (CDMA) system that conforms to the "TIA/EIA/IS-95 Mobile Station-Base Station compatibility Standard for Dual-Mode Wireless Spread Spectrum cellular System" hereinafter referred to as the IS-95 Standard. CDMA systems allow for voice and data communications between users over terrestrial links. The use of CDMA technology in a MULTIPLE access communication SYSTEM is disclosed in U.S. Pat. No. 4,901,307, entitled "SPREAD SPECTRUM MULTIPLE ACCESS COMMUNICATION SYSTEM USING SATELLITE OR TERRESTRIAL REPEATERS," and U.S. Pat. No. 5,103,459, entitled "SYSTEM AND METHOD FOR GENERATING WAVEFORMS INTRACTOCELLULAR TELEPHONE SYSTEM," assigned to the assignee of the present invention and incorporated herein by reference. It should be understood that the present invention is equally applicable to other types of communication systems. Systems utilizing other well-known transmission modulation schemes, such as TDMA and FDMA, as well as other spread spectrum systems, may employ the present invention.

Due to the growing demand for wireless data applications, the need for very efficient wireless data communication systems has become increasingly significant. The IS-95 standard IS capable of communicating traffic data and voice data on the forward and reverse links. One METHOD OF transmitting traffic DATA in fixed-size code channel frames is described in U.S. patent No. 5,504,773, entitled "METHOD AND apparatus FOR THE FORMATTING OF DATA FOR TRANSMISSION," assigned to THE assignee OF THE present invention AND incorporated herein by reference. According to the IS-95 standard, traffic data or voice data IS divided into 20 millisecond wide coded channel frames having data rates up to 14.4 Kbps.

One significant difference between voice services and data services is the fact that the former makes use of strict and fixed delay requirements. Typically, the total one-way delay of a speech frame must be less than 100 milliseconds. Instead, the data delay can be a variable parameter used to optimize the efficiency of the data communication system. In particular, more efficient error correction coding techniques may be utilized that require much greater delays than those that can be tolerated by voice services. An exemplary efficient data encoding scheme is disclosed in U.S. patent application serial No. 08/743,688 entitled "SOFT DECISION OUTPUT FOR DECODING DECISION making available encoded data word" filed 11/6 1996, assigned to the assignee of the present invention and incorporated herein by reference.

Another significant difference between voice services and data services is that the former requires a fixed and common grade of service (GOS) for all users. Typically, for digital systems providing voice services, this translates into a fixed and equal transmission rate for all users, and a maximum allowable value for the error rate of the speech frames. In contrast, for data services, the GOS can be different from user to user and can be a parameter optimized to increase the overall efficiency of the data communication system. The GOS of a data communication system is typically defined as the total delay incurred in the transmission of a predetermined amount of data (hereinafter referred to as data packets).

Yet another significant difference between voice services and data services is that the former requires a reliable communication link, which is provided by soft handoff in the exemplary CDMA communication system. Soft handoff results in redundant transmissions from two or more base stations to improve reliability. However, for data transmission, this additional reliability is not required, since erroneously received data packets may be retransmitted. For data services, the transmit power used to support soft handoff may be more efficiently used to transmit additional data.

The transmission delay required to transmit a data packet and the average throughput rate of the communication system are parameters that measure the quality and effectiveness of the data communication system. In data communications, the transmission delay does not have its same effect on voice communications, but it is an important metric for measuring the quality of the data communication system. The average throughput rate is a measure of the efficiency of the data transfer capability of the communication system.

It is well known that in cellular communication systems, the signal to interference and noise ratio (SINR) of any given user is a function of the location of the user within the coverage area. In order to maintain a given level of service, Time Division Multiple Access (TDMA) and Frequency Division Multiple Access (FDMA) employ frequency reuse techniques, i.e., not all frequency channels and/or time slots are used in each base station. In a CDMA system, the same frequency assignment is reused in each cell of the system, thereby improving overall efficiency. The SINR measured at any given user's mobile station determines the information rate that can be supported for that particular link from the base station to the user's mobile station. Given the particular modulation and error correction method used for transmission, a given level of performance may be achieved at a corresponding SINR level. For an idealized cellular network system with a hexagonal cell layout and utilizing a common frequency in each cell, the distribution of SINR achieved in the idealized cells can be calculated.

In systems capable of transmitting data at high rates, which will be referred to as High Data Rate (HDR) systems, an open loop rate adaptation algorithm is used to adjust the data rate of the forward link. An exemplary HDR system is described in U.S. patent application No. 08/963,386 entitled "METHOD AND APPARATUS FOR HIGH RATEPACKET DATA TRANSMISSION," assigned to the assignee of the present invention AND incorporated herein by reference. Open loop rate adaptation algorithms adjust the data rate based on changing channel conditions typically found in a wireless environment. Generally, the access terminal measures the received SINR during the period of pilot signal transmission on the forward link. The access terminal uses the measured SINR information to predict a future average SINR over the duration of the next data packet. An exemplary prediction METHOD is discussed in co-pending U.S. patent application No. 09/394,980 entitled "SYSTEM AND METHOD FOR calculating a prediction METHOD PREDICTING SIGNAL TO an interactive simulation SYSTEM parameter prediction," assigned TO the assignee of the present invention and incorporated herein by reference. The predicted SINR determines the maximum data rate that can be supported on the forward link with a given probability of success. Thus, the open loop rate adaptation algorithm is a mechanism whereby the access terminal requests the access point to send the next packet at a data rate determined by the predicted SINR. Open loop rate adaptation methods have proven to be very effective in providing high throughput packet data systems even in adverse wireless channel conditions, such as mobile environments.

However, the use of open-loop rate adaptation methods is compromised by the implicit feedback delay associated with the feedback of the transmission of rate requests to the access point. This implicit delay problem is exacerbated when channel conditions change rapidly, requiring the access terminal to update its requested data rate several times per second. In a typical HDR system, the access terminal may make approximately 600 updates per second.

There are other reasons for not implementing a pure open loop rate adaptation method. For example, the open-loop rate adaptation method is very dependent on the accuracy of the SINR estimate. Therefore, imperfect SINR measurements will prevent the access terminal from making accurate characterizations of the underlying channel statistics. One factor that will lead to inaccurate channel statistics is the feedback delay discussed above. Due to the feedback delay, the access terminal must use past and current noisy SINR estimates to predict the supportable data rate in the near future. Another factor that will lead to inaccurate channel statistics is the unpredictable, bursty nature of the received data packets. In packet data cellular network systems, such bursts cause sudden changes in the interference level seen at the access terminal. The unpredictability of the interference level cannot be effectively addressed by a pure open-loop rate adaptation scheme.

Another reason for not implementing a pure open loop rate adaptation method is that the effect of errors cannot be minimized. For example, when the prediction error for the estimated SINR is large, as in some mobile environments, the access terminal will transmit a conservative data rate request in order to ensure a low packet error probability. A low packet error probability will provide a low overall delay in transmission. However, it is possible that the access terminal can successfully receive the higher data rate packet. There is no mechanism in the open loop rate adaptation method to update the data rate request based on the estimated channel statistics with a data rate based on the actual channel statistics during transmission of the data packet. Therefore, the open-loop rate adaptation method does not provide the maximized throughput rate when the prediction error for the estimated SINR is large.

Another example of the inability of the open loop rate adaptation method to minimize the effect of errors is the case where the access terminal erroneously decoded the received packet. When an access terminal decodes a packet in error, the Radio Link Protocol (RLP) requires a retransmission request, but the retransmission request is generated only after a gap is detected in the received sequence number interval. Thus, the RLP protocol requires processing of packets subsequently received after the erroneously decoded packet. This process increases the overall transfer delay. Some mechanism is needed to achieve fast retransmission of some or all of the code symbols contained in a data packet that will enable an access terminal to correctly decode the packet without suffering excessive delay.

Therefore, there is currently a need to modify the open loop rate adaptation method to minimize transmission delay and maximize throughput as discussed above.

SUMMARY

The present invention is directed to a novel and improved method and apparatus for modifying an open-loop rate adaptation algorithm to produce a hybrid open-loop/closed-loop rate adaptation scheme. The access point advantageously generates a time interlace structure for slots in the data packet, enabling the access terminal to transmit an indication message to the access point during a period associated with a gap inserted in the interlace structure.

In one aspect of the invention, the period associated with the staggered slots is of sufficient duration to enable the access terminal to decode the data carried in the slots and to send an indication message in accordance with the decoded data. In an alternative aspect of the invention, the indication message is based on an estimated signal to interference and noise ratio level.

In another aspect of the invention, the indication message is 1 bit long, which is interpreted by the access point according to the timing of its arrival.

Brief Description of Drawings

The features, objects, and advantages of the present invention will be apparent from the following detailed description taken in conjunction with the accompanying drawings, in which like reference characters identify corresponding parts throughout.

FIG. 1 is a diagram of an exemplary slot gap interlace structure for multi-slot packets;

FIG. 2 is a diagram of an exemplary uniform N-slot gap interlace structure for multi-slot packets;

FIG. 3 is a diagram of an exemplary non-uniform N-slot gap interlace structure for multi-slot packets;

FIG. 4 is a diagram of an exemplary "stop" control indication for a multi-slot packet;

FIG. 5 is a diagram of an exemplary "extended" control indication for a multi-slot packet;

fig. 6 is a block diagram of an exemplary embodiment of the present invention.

Detailed description of the preferred embodiments

In an exemplary embodiment of a data communication system, forward link data transfer occurs from an access point to one or more access terminals at a data rate requested by the access terminal. Reverse link data communication occurs from one access terminal to one or more access points. Data is divided into data packets, with each data packet being transmitted over one or more time slots. At each time slot, the access point can direct the data transmission to any access terminal in communication with the access point.

Initially, the access terminal establishes communication with the access point using a predetermined access procedure. In the connected state, the access terminal can receive a data message and a control message from the access point and can transmit the data message and the control message to the access point. The access terminal then monitors the forward link for transmissions from the access point in the access terminal's active set. The active set includes a list of access points in communication with the access terminal. In particular, the access terminal measures the signal-to-interference-and-noise ratio (SINR) of the forward link pilot received at the access terminal from the access point in the active set. If the received pilot signal is above a predetermined increase threshold, or below a predetermined decrease threshold, the access terminal reports this to the access point. Subsequent messages from the access point direct the access terminal to add or delete access points from its active set, respectively.

If there is no data to send, the access terminal returns to the idle state and discontinues the transmission of data rate information to the access point. The access terminal periodically monitors control channels from one or more access points in the active set to monitor for paging messages while the access terminal is in an idle state.

If there is data to be transmitted to the access terminal, the central processor sends the data to all the access points in the active set and stores the data in the queues at the access points. The paging message is then sent by one or more access points to the access terminal on respective control channels. The access point may transmit all such paging messages simultaneously across several access points to ensure reception even when the access terminal is handed off in the access point. The access terminal demodulates and decodes signals on one or more control channels to receive the paging message.

Upon decoding the paging message, the access terminal measures the SINR of the forward link signal received at the access terminal from the access points in the active set for each slot until the data transfer is completed. The SINR of the forward link signal may be obtained by measuring the respective pilot signals. The access terminal then selects the best access point based on a set of parameters. The set of parameters may include current and previous SINR measurements and bit error rate or packet error rate. The best access point is selected, for example, based on the maximum SINR measurement. The access terminal then identifies the best access point and transmits a data rate control message (hereinafter DRC message) on a data rate control channel (hereinafter DRC channel) to the selected access point. The DRC message may contain the requested data rate or may alternatively include the quality of the forward link channel (e.g., its SINR measurement, bit error rate, or packet error rate). In this exemplary embodiment, the access terminal can direct the transmission of the DRC message to a particular access point by using a Walsh code that uniquely identifies the access point. The DRC message symbol is exclusive-or (XOR) with the unique Walsh code. Since each access point in the access terminal's active set is identified by a unique Walsh code, only selected access points that perform an XOR operation with the correct Walsh code equivalent to that performed by the access terminal can correctly decode the DRC message. The access point uses the rate control information from each access terminal to transmit forward link data at the highest possible rate.

At each time slot, the access point may select any of the paged access terminals for data transmission. The access point then determines a data rate at which to transmit data to the selected access terminal based on the most current value of the DRC message received from the access terminal. In addition, the access point uniquely identifies the transmission to a particular access terminal by appending an identification preamble to the data packet addressed to the access terminal. In this exemplary embodiment, the preamble is spread using a Walsh code that uniquely identifies the access terminal.

In the exemplary embodiment, the forward link capacity of the data transmission system is determined by the data rate request of the access terminal. Additional gain may be achieved by using directional antennas and/or adaptive spatial filters. An exemplary METHOD AND APPARATUS FOR PROVIDING directed delivery is disclosed in pending U.S. patent application Ser. No. 08/575,049 entitled "METHOD AND APPARATUS FOR DETERMINING THETRANSMISON DATA RATE IN A MULTI-USER COMMUNICATION SYSTEM" filed on 12/20.1995, AND U.S. patent application Ser. No. 08/925,521 entitled "METHOD AND APPARATUS FOR PROVIDING ORTHOGONAL SPOT BEAMS, SECTORS, PICOCELLS" filed on 9/8.1997, both of which are assigned to the assignee of the present invention AND are incorporated herein by reference.

Fast Closed Loop (FCL) rate control adaptation

In an HDR system, an open-loop rate adaptation scheme uses a fast feedback channel to allow transmission of DRC messages from an access terminal to an access point while the access point is simultaneously transmitting data packets to the access terminal on a forward data link. Thus, the access terminal can command the access point to either terminate or extend the current transmission depending on the actual SINR conditions at the receiving access terminal. In an exemplary embodiment, the fast feedback channel is used to carry additional information, as described below.

The forward link data rate in an HDR system varies from 38.4kbps to 2.456 Mbps. The duration of each packet transmission is described in table 1 in terms of the number of slots and other modulation parameters. In this embodiment, a slot corresponds to a period of 1.666ms, or equivalently, a chip rate of 1.2288Mcps2048 chips are transmitted.

Data rate number	Data Rate (kbps)	Number of time slots	Number of bits per packet	Code rate	Modulation
						1	38.4	16	1024	1/4	QPSK
2	76.8	8	1024	1/4	QPSK
						3	102.4	6	1024	1/4	QPSK
4	153.6	4	1024	1/4	QPSK
						5	204.8	3	1024	1/4	QPSK
6	307.2	2	1024	1/4	QPSK
						7	614.4	1	1024	1/4	QPSK
8	921.6	2	3072	3/8	QPSK

9	1228.8	1	2048	1/2	QPSK
						10	1843.2	1	3072	1/2	8PSK
11	2457.6	1	4096	1/2	16QAM

TABLE 1 Forward Link modulation parameters

In an exemplary embodiment, the structure of a multi-slot packet is modified to carry data in predetermined data slots but not in predetermined gap slots. When constructing a multi-slot packet according to the exemplary embodiments, an access terminal receiving the multi-slot packet can utilize the duration of the predetermined interval slots for other purposes. For example, the access terminal can use the time between data slots to determine whether the packet can be correctly decoded with accumulated soft-coded symbols to date. The access terminal can determine whether the data slot has been decoded correctly using various methods including, but not limited to, checking CRC bits associated with the data or estimating a predicted SINR from the SINR of the received pilot and communication symbols.

Fig. 1 is a diagram of an exemplary slot gap interleaving structure for multi-slot packets, in which predetermined data slots and predetermined gap slots are interleaved in an alternating manner. This embodiment will be referred to as a slotted mode hereinafter. A multi-slot packet 100 with data contained in alternating time slots is transmitted from the access point to the access terminal. For example, if the access terminal transmits according to data rate 2 of table 1, there are 8 data slots in a multi-slot packet and the data will be transmitted in slots 1,3, 5, 7, 9, 11, 13, and 15. Slots 2, 4, 6, 8, 10, 12, and 16 are not used to transmit portions of the multi-slot packet. The DRC message from the access terminal may be transmitted to the access point during the time associated with the empty slot. In the above example, it should be clear that the access point may transmit another data packet to the same or a different access terminal during the gap time slot associated with the transmission example of the 8-slot packet.

In addition to DRC messages, this embodiment allows the transmission of indication messages from the access terminal to the access point indicating the reception status of the access terminal, such indication messages including but not limited to "stop" indication messages or "extend" indication messages. It should be noted that the use of the indication message described herein for the present invention is applicable to the other embodiments below.

In an HDR system, the code symbols transmitted at data rates of 307.2kbps and less are repetitions of code symbols transmitted in a packet at 614.4 kbps. In general, most of the code symbols transmitted in a given slot are shifted repetitions of the code symbols transmitted in slot 1 of the packet. A lower data rate requires a lower SINR for a given low packet error probability. Thus, if the access terminal determines that the channel conditions are unfavorable, the access terminal will transmit a DRC message requesting a data rate of less than 614.4 kbps. The access point will then transmit the multi-slot packet according to the structure described in fig. 1. However, if the actual channel conditions improve such that the access terminal requires fewer repetition coded symbols than originally specified by the open loop rate adaptation algorithm, the structure depicted in fig. 1 will allow the access terminal to transmit an indication message, such as a "stop" indication message, on the reverse link feedback channel.

Fig. 2 is a diagram illustrating the use of a stop indication message. The access point transmits data packet 200 according to the interleaving structure of fig. 1. Time slots n, n +2, and n +4 are time slots that carry data. The DRC message 210 is received during slot time period n-1 so that the data in slots n, n +2, n +4, and n +6 is scheduled for transmission according to the requested data rate. The stop indication message 220 is sent by the access terminal because the access terminal has received enough repetitions of the code symbols in time slots n, n +2, and n +4 to determine the complete data without receiving any more repetitions carried by n + 6. Thus, the access terminal is ready to receive new data. The stop indication message 220 is received by the access point during time slot n + 5. Upon receiving the stop indication message 220, the access point will terminate the transmission repetition in the remaining allocated data slot n +6 and begin transmitting the new data packet in slot n + 6. The unused assigned time slot may be reassigned to another packet transmission directed to the access terminal. As such, when the actual channel conditions are allowed to be higher than the data rate specified in the original DRC message based on the estimated channel conditions, closed-loop rate adaptation may be performed to optimize resources. In the above example, by sending a "stop" indication, an effective data rate 4/3 times higher than the originally requested data rate is achieved.

In another aspect of the present embodiment, an indication message may be sent from the access terminal to the access point to allow for more repetition of the coded symbols as long as the actual channel conditions are worse than the estimated channel conditions. This indication message may be referred to as an "extension" indication message. Another use of the "extend" indication message occurs when the access terminal erroneously decodes a slot packet. In this case, the access terminal may transmit an "extension" indication message requesting retransmission of the data carried in the specified time slot. The structure of fig. 1 allows an access point to retransmit data at the very next slot, referred to herein as an extended data slot, after decoding of the "extension" indication message. Fig. 3 is an illustration of such use of an "extension" indication message. The data packet 300 is constructed according to the structure of fig. 1 such that alternating slots are designated interval slots. The DRC message 310 is received by the access point and provides a better rate for the data transmitted in data slot n. Data is also transmitted in time slot n +2 at the requested data rate. However, an "extension" indication message 320 is received by the access point, which instructs data repetition at data slot n +4 due to errors in decoding the data carried in slot n + 2.

In another aspect of this embodiment, a single-slot packet may be requested when the estimated SINR indicates a reduced packet success probability, e.g., 80-90% packet success probability. Based on the received single-slot packet, if the 1 st single-slot packet is not decoded correctly, the access terminal can transmit an "extension" indication to the access point requesting retransmission of the packet. This aspect of the present embodiment has the advantage of increased data throughput rates, which is achieved by the raw transmission of high data rates. According to this embodiment, the high data rate transmission may be adjusted according to the actual channel conditions. Fig. 3 also illustrates this aspect of the invention. If DRC message 310 carries a data request of 307.2kbps, then data is transmitted in slots n and n +2 at the requested rate. However, if the access terminal detects an improvement in channel conditions, the access terminal can send a DRC message carrying a data request of 1.2 Mbps. The access point will then transmit a single slot packet at 1.2Mbps in slot n + 5. During the time associated with the gap slot n +6, the access terminal detects a deterioration in the channel conditions, which necessitates a retransmission of the data in slot n + 5. An "extend" message 340 is transmitted and the access point retransmits the data for slot n +5 in slot n + 7.

In one embodiment, the access terminal may be allowed to transmit up to N per frame_EXT(i) An "extension" indicates a message where i 1, 2, 11 corresponds to one of the data rates illustrated in table 1.

The above procedure for closed loop rate adaptation is an example in transmission, where a data packet comprises one or two time slots. It should be noted that the extended data slot carries code symbols that are repetitions of previously transmitted code symbols, and thus the code symbols in the extended data slot can advantageously be soft combined with previously received code symbols prior to the decoding step to improve reliability. The identification of which code symbols to transmit in an extended data slot is implementation details and does not affect the scope of the invention.

The above-described fast closed-loop rate adaptation method may be implemented to rely on the same fast feedback channel used by the open-loop rate adaptation scheme, but it should be noted that the closed-loop rate adaptation method may also be implemented using another separate channel without changing the scope of the present invention.

Another aspect of the implementation is to indicate a formulation of the message. In an embodiment where only two indication messages are specified in the system, a "stop" indication message and an "extend" indication message, the system only needs 1 bit to carry the indication message. The DRC message carries multiple bits for rate selection and access point identification, but if the system distinguishes the context of the bits based on usage, only 1 bit is needed to indicate either a "stop" indication message or an "extend" indication message. For example, the indication bit may be designated as the FCL bit. If the access point detects the presence of the FCL bit from the access terminal in time slot n, then the access point will interpret the FCL bit as a "stop" indication message if the data slot of the multi-slot packet for that access terminal is scheduled for transmission in time slot n + 1. However, if the packet scheduled to the access terminal and at the requested data rate happens to terminate in time slot n-1, the access point will interpret the FCL bit as an "extension" indication message. On the other hand, if the previous "extension" indication message caused a retransmission of a slot of the packet specified in exactly slot N-1, and the packet had been processed less than N_EXTAn indication message, the access point may also interpret the FCL bit as an "extension" indication message. If neither of these conditions apply, the bit may be removed as a false alarm.

In another embodiment, the indication message may be transmitted on the same feedback channel reserved for open loop DRC messages using one of the reserved DRC codewords. However, in this embodiment, the access terminal cannot transmit the DRC message and the indication message such as the "stop" message at the same time because only one message can be transmitted at a time. Thus, the access terminal will be prevented from serving another packet during the 1 st slot released after sending the stop indication message. However, other access terminals may be served in this 1 st slot release. If the access point serves many access terminals, the efficiency of this embodiment is maximized due to the reduced probability that packets for a given access terminal will be scheduled consecutively.

In another embodiment, the indication message may be transmitted on a separately assigned channel that may be established using additional Walsh functions on the reverse link. This approach has the additional advantage of allowing the access terminal to control the reliability of the FCL channel to a desired level. In the above embodiments, it should be observed that only one access terminal should be transmitting at any given time. Thus, it is feasible to increase the power allocated to transmit the indication message without affecting the capacity of the reverse link.

As noted previously, the access point may maximize efficiency by transmitting data to other access terminals during the gap time slots.

Fig. 4 is a diagram of an exemplary interleaving structure for multi-slot packets, in which predetermined data slots and predetermined interval slots are interleaved in a uniform N-slot pattern. This embodiment will be referred to as uniform N slot mode hereinafter. A multi-slot packet 400 is transmitted from the access point to the access terminal, where every nth slot contains data. The N-1 slots are gap slots in which the access terminal may use the delay associated with the gap slot to attempt to decode data received in the previous data slot. As is well known in the art, blocks of data bits may be transmitted using encoding to enable the reception of data to determine the presence of any errors in the transmission of the data. One example of such a coding technique is the generation of Cyclic Redundancy Check (CRC) symbols. In an aspect of the present embodiment, the delay caused by the uniform insertion of the interval enables the access terminal to decode the CRC bits and to determine whether the data slot was successfully decoded. The access terminal may send the indication message based on the actual success or failure of the decoded data slots instead of sending the indication message based on the SINR estimate. It should be noted that the time required to decode the data is generally proportional to the number of information bits contained in the packet. Thus, as seen in table 1, higher data rate packets require more decoding time. When determining the optimum value of N, the worst-case delay must be taken into account when selecting the staggering period.

In another aspect of this embodiment, the delay caused by the uniform insertion of the gap enables the access terminal to determine the estimated SINR during reception of the data slot and advantageously transmit the DRC message.

In addition, delayed additional slots may be inserted into the multi-slot packet to enable the access terminal to transmit additional messages to the access point.

In a manner similar to the transmission of indication messages for the one slot interval mode embodiment, a "stop" indication message and an "extend" indication message may be used in the uniform N slot interval mode. Furthermore, if the system distinguishes the context of a bit based on usage, the formulation of the indication message may be implemented using only one bit. For example, the indication bit may be designated as the FCL bit. If the access point detects the presence of the FCL bit from the access terminal in time slot n, then the access point will interpret the FCL bit as a "stop" indication message if the data slot of the multi-slot packet for that access terminal is scheduled for transmission in time slot n + 1. However, if the packet scheduled to the access terminal at the requested data rate happens to end in time slot n-p +1, the access point will interpret the FCL bit as an "extension" indication message, where p is the period of the data slot allocated to the access terminal. On the other hand, if the previous "extension" indication message caused a retransmission of a slot of the packet specified exactly in slot N-p +1, and the packet had been processed less than N_EXTAn "extension" indication message, the access point may also interpret the FCL bit as an "extension" indication message. If neither of these conditions apply, the bit may be removed as a false alarm.

Fig. 5 is a diagram of another exemplary interleaving structure for multi-slot packets, in which predetermined data slots and predetermined gap slots are interleaved in a non-uniform slot pattern. This embodiment of the invention will be referred to hereinafter as a non-uniform N-slot spacing pattern. The multi-slot packet 500 is constructed such that the delay of interleaving between data slots is a function of the data rate. The number of spaced slots required between data slots of a packet at rate i, i.e., n (i), is fixed and known by all access terminals and access points. Although this embodiment allows the latency of each data rate packet to be minimized, the access point must satisfy some number of constraints when scheduling packets for transmission. One such constraint is the prevention of overlapping data slots.

As an example of a non-uniform slot pattern, the DRC message of fig. 5 may be used to transmit data in an interleaved pattern. In this embodiment, DRC message 510 requests that the data transmitted in slots n-2, n +2, and n +6 be transmitted at 204.8 kbps. DRC message 520 requests that data be transmitted in slots n +1 and n +3 at 921.6 kbps. DRC message 530 requests that data be transmitted in slot n +8 at 1.2 Mbps. Although individual DRC messages are used for periodic transmissions, combining the periodic transmissions establishes a non-uniform pattern that is non-periodic. It should be noted that there are constraints on the data pattern initiated by DRC message 520. A 2-slot data packet may have been scheduled with a slot interval between pairs of data slots, beginning transmission at either slot n +1 or n-1, but not at slot n. If the pattern had started at n, then the current slot n +3 data may have been transmitted at slot n +2, which would overlap the data slot pattern scheduled by the DRC message 510.

The "stop" indication message and the "extend" indication message may be used in a non-uniform N-slot interval pattern in a similar manner to the transmission of the indication message of a slot interval pattern embodiment. Furthermore, if the system distinguishes the context of a bit based on usage, the formulation of the indication message may be implemented using only one bit. For example, the indication bit may be designated as the FCL bit. If the access point detects the presence of an FCL bit from an access terminal in time slot n, then the access point schedules a data slot of a multi-slot packet for the access terminal for transmission in time slot n +1The FCL bit will be interpreted as a stop indication message. However, if the packet scheduled to the access terminal at the requested data rate happens to terminate in time slots n-n (i), where n (i) is the number of interval slots required between data slots and i indicates the data rate index number, the access point will interpret the FCL bit as an "extension" indication message. On the other hand, if the previous "extension" indication message caused a retransmission of a slot of the designated packet at exactly slot N-N (i), and the packet had been processed less than N_EXTAn "extension" indication message, the access point may also interpret the FCL bit as an "extension" indication message. If neither of these conditions apply, the bit may be removed as a false alarm.

Various advantages over non-uniform slot spacing patterns may be obtained when using uniform slot spacing patterns, and vice versa. Systems using a uniform slot spacing pattern can achieve maximum slot efficiency by staggering the periodic pattern across all slots. For example, in a uniform mode, where time slots n, n +4, n +8,. are allocated to one access terminal, time slots n +1, n +5, n +9,. may be allocated to the 2 nd access terminal, time slots n +2, n +6, n +10,. may be allocated to the 3 rd access terminal, and time slots n +3, n +7, n +11,. may be allocated to the 4 th access terminal. In this way, all time slots are fully utilized to increase the efficiency of the network. However, in some cases, it may be more desirable to implement a non-uniform slot spacing pattern. For example, in high speed data transmission, only one data slot is transmitted with a large number of code symbols. In such a case, the access terminal would require a relatively long duration to decode the received encoded symbols. Thus, implementation of a uniform slot pattern would require a correspondingly large period with a large number of spaced slots, which would not be efficient. In these cases, a non-uniformly spaced slot pattern may be preferred.

Fig. 6 is a block diagram of an apparatus for performing FCL rate control in an HDR system. The access terminal 701 performs SINR estimation and prediction at SINR estimation element 722 based on the strength of the received forward link signal from access point 700. The results from the SINR estimation element 722 are sent to an open loop rate control element 723, which implements an open loop rate control algorithm to select a data rate based on the results from the SINR estimation element 722. Open loop rate control element 723 generates a DRC message to be sent on the reverse link to access point 700. The DRC message is decoded at DRC decoder 713 and the result is sent to scheduler 712 so that access point 700 can schedule data transmission at the specified requested rate in the slot following decoding of the DRC message. It should be noted that the elements described thus far are executing the open loop rate control algorithm described above. The FCL rate control processing is implemented by scheduler 712 using interleaved packet generation and closed-loop rate control element 725 as described above, the closed-loop rate control element 725 operatively enabling FCL rate adaptation for the access terminal 701.

In fig. 6, a 1-slot interval mode is implemented by scheduler 712 to serve two access terminals simultaneously. Thus, the access point 700 maintains two separate buffers, transmit buffer a 710 and transmit buffer B711, to maintain the generation of new slot repeat or slot extension required code symbols. It should be noted that more transmit buffers may be utilized in accordance with the embodiments described herein.

The access point 700 transmits a data packet to the access terminal 701. Upon receiving the data packet, the access terminal 701 may feed back the result from the SINR estimation element to the closed-loop rate control element 725, or alternatively, the access terminal 701 may feed back the result from the decoder 720 to the closed-loop rate control element 725. The buffer 721 may be inserted to provide assistance to the in-order delivery of decoded information from the decoder 720 to upper layer protocols, which will not be described herein. The closed loop rate control element 725 can use the results from the decoder 720 or the SINR estimation element 722 to determine whether to generate an indication message. The indication message is transmitted on the reverse link to the access point 700 where the FCL indication message decoder 714 decodes the indication message and feeds the decoded indication message to the scheduler 712. Scheduler 712, DRC decoder 713, and FCL implementing decoder 714 at access point 700 may be implemented with separate elements or may use a single processor or memory. Likewise, decoder 720, buffer 721, SINR estimation element 722, open-loop rate control element 723, and closed-loop rate control element 725 at access terminal 701 may be implemented with separate elements or combined with memory on a single processor.

Outer loop rate control element 724 may be inserted to calculate long term error statistics. The results of such statistical calculations may be used to determine a set of parameters that may be used to adjust open-loop rate control element 723 and closed-loop rate control element 725.

As discussed herein, the FCL rate adaptation method may determine to send an indication message, such as a "stop" indication message or an "extend" indication message, to the access point. The method provides a fast correction mechanism to compensate for inaccuracies in the open loop rate control scheme. The multi-slot transmission may be stopped when there is sufficient information to decode the packet. On the other hand, when successful decoding cannot be guaranteed, one slot of the ongoing multi-slot packet transmission may be repeated.

Since the FCL rate adaptation method allows the transmission of an extended data slot if the high-rate packet cannot be successfully decoded, the FCL rate adaptation method also improves throughput by allowing the open-loop rate control scheme to actively request 1-slot packets at a higher rate. Throughput is also improved when the FCL rate adaptation method stops multi-slot packets earlier than expected by the open loop rate control algorithm.

For example, the open-loop rate control scheme may be designed such that the open-loop rate control selects a high rate after the end of the 1 st slot using a 1-slot packet having a Packet Error Rate (PER) of about 15% after the end of the 1 st slot and a PER of at most 1% at the end of the extended slot. The extended time slot will increase the average SINR by at least 3dB, except for any time diversity gain and shrinkage loss reduction. For multi-slot packets, the open-loop rate control algorithm can target a PER of 1% at the normal end of the packet. Thus, there may be a large likelihood of packet success at a reduced number of slots, which corresponds to a higher rate than expected. Furthermore, the extended time slot will provide additional margin as needed for successful decoding, thereby reducing the requirement for delayed retransmissions. It should be noted that the SINR value for optimal efficiency will vary according to the various modulation techniques implemented in the network, such that the possible implementation of various SINR values as thresholds does not limit the scope of the embodiments described herein.

Furthermore, depending on the SINR calculation, it should not be very proactive to generate a "stop", "prolong", or FCL-free indication, otherwise the closed-loop rate control algorithm would erroneously assume that the probability of successfully decodable packets would dominate the probability of packet errors.

The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (23)

1. A method of increasing data throughput rate of a communication network, comprising the steps of:

generating a plurality of data slots and a plurality of gap slots at an access point, wherein the plurality of data slots are interleaved with the plurality of gap slots to form a plurality of packets, wherein data is carried in the data slots but not in the gap slots;

transmitting the plurality of packets to the access terminal at a data rate;

detecting the plurality of packets at the access terminal, wherein the access terminal transmits at least one indication message to the access point during a time period associated with at least one intervening slot to indicate a receive status, wherein the number of intervening slots is determined by the data rate; and

modifying the transmission of subsequent data packets to the access terminal in accordance with the indication message received by the access point.

2. The method of claim 1, wherein said plurality of data slots are interleaved with said plurality of gap slots in an alternating pattern.

3. The method of claim 1, wherein the plurality of data slots are interleaved with the plurality of intervening slots such that every nth slot is an intervening slot.

4. The method of claim 1, wherein said plurality of data slots are interleaved with said plurality of gap slots in a non-periodic structure.

5. A method of increasing the data throughput rate of a transmission from an access point to an access terminal, comprising the steps of:

generating, at the access point, a plurality of data packets for transmission to the access terminal, wherein each of the plurality of data packets includes at least one slot, and the access point designates each slot in each of the plurality of data packets as either a data slot or an interval slot, wherein data is carried in the data slot but not in the interval slot;

transmitting the plurality of data packets to the access terminal at an original data rate;

determining a set of estimated channel parameters at the access terminal;

transmitting a data request message to the access point in accordance with the set of estimated channel parameters, wherein the step of transmitting the plurality of data packets to the access terminal is performed in accordance with the data request message;

determining a set of actual channel parameters at the access terminal;

transmitting an indication message to said access point to indicate a reception status if the set of actual channel parameters exceeds a predetermined quality, wherein said step of transmitting an indication message is performed during a time period associated with at least one intervening time slot, the number of intervening time slots in the time period being determined by said data rate, and

modifying transmission of subsequent data packets to the access terminal in accordance with the indication message received at the access point.

6. The method of claim 5, wherein the indication message is a stop indication message if the set of actual channel parameters indicates a noise level lower than a noise level associated with the set of estimated channel parameters.

7. The method of claim 5, wherein the indication message is an extension indication message if the set of actual channel parameters indicates a noise level higher than a noise level associated with the set of estimated channel parameters.

8. The method of claim 5, wherein the indication message comprises 1 bit received during slot n and the access point specifies each of the plurality of data packets in an alternating pattern, wherein the modifying transmission of subsequent data packets to the access terminal comprises:

determining that the bit is a request for termination of transmission if a retransmission of one of the plurality of data packets has been scheduled for slot n + 1;

determining that the bit is a request for retransmission if the transmitted packet ends transmission in slot n-1;

determining that the bit is a request for retransmission if the previous indicator bit caused a retransmission of the transmitted packet in slot n-1 and less than a predetermined number of retransmissions have been processed for the plurality of data packets; and

if any of the above conditions are not met, the bit is determined to be a false alarm.

9. The method of claim 5, wherein the indication message comprises 1 bit received during a time slot n and the access point specifies each time slot of the plurality of data packets by a period p, wherein the modifying transmission of subsequent data packets to the access terminal comprises the steps of:

determining that the bit is a request for termination of transmission if a retransmission of one of the plurality of data packets has been scheduled for time slot n + 1;

determining that the bit is a request for retransmission if the transmitted packet ends transmission in slot n-p + 1;

determining that the bit is a request for retransmission if the previous indicator bit caused a retransmission of the transmitted packet in slot n-p +1 and less than a predetermined number of retransmissions have been processed for the plurality of data packets; and

if any of the above conditions are not met, the bit is determined to be a false alarm.

10. The method of claim 5, wherein the indication message includes 1 bit received during a time slot n, wherein the modifying the transmission of subsequent data packets to the access terminal comprises the steps of:

determining that the bit is a request for termination of transmission if a retransmission of one of the plurality of data packets has been scheduled for time slot n + 1;

determining that the bit is a request for retransmission if the transmitted packet ends transmission in time slots n-n (i), where n (i) is the number of intervening time slots between data slots, and i is a data rate index number;

determining that the bit is a request for retransmission if the previous indication bit caused retransmission of the transmitted packet in time slot n-n (i) and less than a predetermined number of retransmissions have been processed for the plurality of data packets; and

if any of the above conditions are not met, the bit is determined to be a false alarm.

11. The method of claim 5 wherein said set of actual channel parameters includes a signal to interference and noise ratio.

12. The method of claim 5, wherein the step of determining the set of actual channel parameters comprises the step of decoding the plurality of data packets at the access terminal to determine a packet error event, wherein the packet error event indicates a good data packet reception or a bad data packet reception.

13. The method of claim 12, wherein said step of decoding said plurality of data packets at said access terminal comprises the steps of:

decoding the plurality of cyclic redundancy check bits; and

comparing the decoded plurality of cyclic redundancy check bits to an estimated quality metric, wherein the estimated quality metric is calculated from the set of estimated channel parameters.

14. The method of claim 5, wherein said step of transmitting said indication message to said access point comprises the steps of:

processing the encoded symbols to determine a probability value of a transmission error; and

transmitting an extension indication message if the probability value of the transmission error is greater than a predetermined amount.

15. The method of claim 12, wherein the indication message comprises 1 bit received during slot n and the access point specifies each of the plurality of data packets in an alternating pattern, wherein the modifying transmission of subsequent data packets to the access terminal comprises:

determining that the bit is a request for termination of transmission if a retransmission of one of the plurality of data packets has been scheduled for slot n + 1;

determining that the bit is a request for retransmission if the transmitted packet ends transmission in slot n-1;

determining that the bit is a request for retransmission if the previous indicator bit caused a retransmission of the transmitted packet in slot n-1 and less than a predetermined number of retransmissions have been processed for the plurality of data packets; and

if any of the above conditions are not met, the bit is determined to be a false alarm.

16. The method of claim 12, wherein the indication message comprises 1 bit received during a time slot n and the access point specifies each time slot of the plurality of data packets by a period p, wherein the modifying transmission of subsequent data packets to the access terminal comprises the steps of:

determining that the bit is a request for termination of transmission if a retransmission of one of the plurality of data packets has been scheduled for time slot n + 1;

determining that the bit is a request for retransmission if the transmitted packet ends transmission in slot n-p + 1;

determining that the bit is a request for retransmission if the previous indicator bit caused a retransmission of the transmitted packet in slot n-p +1 and less than a predetermined number of retransmissions have been processed for the plurality of data packets; and

if any of the above conditions are not met, the bit is determined to be a false alarm.

17. The method of claim 12, wherein the indication message includes 1 bit received during a time slot n, wherein the modifying the transmission of subsequent data packets to the access terminal comprises the steps of:

determining that the bit is a request for termination of transmission if a retransmission of one of the plurality of data packets has been scheduled for time slot n + 1;

determining that the bit is a request for retransmission if the transmitted packet ends transmission in time slots n-n (i), where n (i) is the number of intervening time slots between data slots, and i is a data rate index number;

determining that the bit is a request for retransmission if the previous indication bit caused retransmission of the transmitted packet in time slot n-n (i) and less than a predetermined number of retransmissions have been processed for the plurality of data packets; and

if any of the above conditions are not met, the bit is determined to be a false alarm.

18. A system for increasing data throughput rate of transmissions from an access point to an access terminal, comprising a processor at the access point configured to selectably generate a plurality of interleaved data slots and gap slots, forming a plurality of data packets for transmission to the access terminal, wherein data is carried in the data slots but not in the gap slots; the number of spaced time slots is related to a data throughput rate, and the processor is further configured to modify subsequent data packets for transmission to the access terminal based on an indication message received by the access point, wherein the indication message is transmitted by the access terminal for a time period associated with at least one spaced time slot.

19. The system of claim 18, further comprising a processor at the access terminal configured to decode the plurality of interleaved data and gap slots, determine a quality value associated with transmission from the access point to the access terminal, generate a data rate request message for transmission based on the quality value, and generate an indication message based on the quality value, wherein the indication message is generated and transmitted to the access point during a time period associated with at least one gap slot.

20. The system of claim 19, wherein the quality value is determined by a channel noise and interference value.

21. The system of claim 19, wherein the quality value is determined from a packet error value based on a number of data slots decoded.

22. An apparatus for adjusting an open loop rate control process, comprising:

a scheduler at the access point for selectably scheduling a plurality of interleaved data slots and gap slots for transmission to an access terminal at a particular data rate, wherein the number of gap slots is determined by the data rate, wherein the scheduler is coupled to at least one buffer for storing data to be transmitted on the forward link channel; wherein the plurality of interleaved data slots and the spacing slots form a plurality of data packets and carry data in the data slots but not in the spacing slots;

a data rate request message decoder coupled to the scheduler for decoding a plurality of data request messages received on a reverse link channel and for inputting data rate request information to the scheduler; and

an indication message decoder coupled to the scheduler for decoding a plurality of indication messages received on the reverse link channel and for inputting decoded indication messages to the scheduler; and

subsequent data packets are transmitted to the access terminal in accordance with the indication message received at the access point, wherein the indication message is transmitted during a time period associated with at least one intervening time slot.

23. An apparatus for adjusting an open loop rate control process, comprising:

an estimating element at the access terminal for determining a quality value associated with the forward link channel;

an open-loop rate control element coupled to the estimation element for generating a plurality of data rate request messages, wherein the open-loop rate control element uses the quality values received from the estimation element to determine the content of the plurality of data rate request messages;

a closed-loop rate control element coupled to the estimation element and a decoder configured to decode a plurality of interleaved data slots and gap slots received at a particular data rate in a selectable manner on the forward link channel, for generating a plurality of indication messages based on quality values from the estimation element or error values from the decoder; wherein the plurality of interleaved data slots and the spacing slots form a plurality of data packets and carry data in the data slots but not in the spacing slots; wherein the number of spaced time slots is determined by the data rate;

a controller coupled to the decoder and the estimation element for enabling the closed-loop rate control element according to a set of thresholds; and

and the subsequent data packet is transmitted to the access terminal according to the indication message received at the access point.