HK1067833B - System and method for frame re-transmission in a broadcast communication system - Google Patents

Description

System and method for frame retransmission in a broadcast communication system

Technical Field

The present invention relates to broadcast communications, also known as point-to-multipoint or group communications, in wired or wireless communication systems. More particularly, the present invention relates to a system and method for providing frame retransmission in such a broadcast communication system.

Background

The field of wireless communications includes many applications including cordless telephones, paging, wireless local loops, and satellite communication systems. One particularly important application is the cellular telephone system of mobile subscribers. (the term "cellular" system, as used herein, includes both cellular and PCS frequencies.) various air interfaces have been developed for such cellular telephone systems, including Frequency Division Multiple Access (FDMA), Time Division Multiple Access (TDMA), and Code Division Multiple Access (CDMA). In connection therewith, various national and international standards have been established, including Advanced Mobile Phone Service (AMPS), global system for mobile communications (GSM), and interim standard 95 (IS-95). In particular, the Telecommunication Industry Association (TIA) and other well-known standards bodies have promulgated IS-95 and its derivatives, such as IS-95A, IS-95B (commonly referred to as IS-95), ANSIJ-STD-008, IS-99, IS-2000, IS-657, IS-707, and the like. Generally, information transmitted within such systems is formatted into discrete packets, also referred to as data packets or data frames, simply frames. To increase the likelihood of successfully transmitting frames during transmission, various retransmission schemes have been developed. For example, Radio Link Protocol (RLP) has been developed to perform frame retransmission when one or more frames are not successfully received. The RLP protocol controls how and when frames are retransmitted from a transmission system to a receiver.

To determine which frames were not successfully received using RLP, an octet sequence number is included as a frame header in each frame transmitted. The sequence number is incremented from 0 to 256 for each frame and then reset back to 0. Unsuccessfully received frames are detected when frames with out-of-order sequence numbers are received, or errors are detected using CRC checksum information or other error detection methods. Upon detecting an unsuccessfully received frame, the receiver sends a negative acknowledgement message (NAK) to the transmitting system that includes the sequence number of the incorrectly received frame. The transmission system then retransmits the frame including the sequence number originally transmitted. If the retransmitted frame has not been successfully received, a second retransmission request is sent to the transmission system, requesting that the frame be transmitted twice. If the frame has not been successfully received, a third retransmission request is sent to the transmitting system, requesting that the frame be sent three times. If the frame has not been successfully received after the third retransmission request, no further retransmission is requested and the frame is ignored for reconstruction of the original data at the receiver.

The frame retransmission scheme just described is an example of the scheme used for point-to-point communication between a transmission system and a receiver. Such retransmission systems are impractical in broadcast communication systems because there may be an almost unlimited number of retransmission requests from the various receivers. In particular, for any given frame, the probability of a frame being received in error (or not received at all) in a broadcast transmission system is much higher than in a point-to-point broadcast system. As the number of receivers increases, the probability of the required retransmissions also increases significantly. Also, as the number of retransmissions increases, the delay (i.e., latency) for transmitting new information increases to a point where the application using the information at the receiver is significantly impacted. For example, delays in speech greater than a few hundred milliseconds can result in unacceptable speech quality at the receiver. Furthermore, this retransmission scheme also depends on the presence of a feedback channel. That is, for this scheme to work well, two-way communication between the transmitter and the receiver is required. In some systems, such a bi-directional link may not be available.

There is a need for a method and apparatus for frame retransmission in a broadcast communication system that avoids latency problems.

Disclosure of Invention

Methods and apparatus for providing high speed broadcast communications are described. In one embodiment, the present invention describes an apparatus comprising a receiver configured to receive a message indicating a frame received in error by a wireless communication device, the message including an identification of the frame. The memory is used to store a predetermined number for determining when to retransmit frames. The processor is configured to determine an accumulated number of frames received in error and to command a frame retransmission if the accumulated number is greater than a predetermined number.

In another embodiment, the present invention is directed to a method comprising the steps of: receiving a message indicating a frame received in error by the wireless communication device, the message including a data frame identification; determining a cumulative number of times the data frame has been received in error; and retransmitting the data frame if the accumulated number of times is greater than a predetermined number.

Drawings

The features, nature, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like elements have like numerals wherein:

fig. 1 is an illustration of a wireless communication system in which a wireless communication device communicates with a base station;

fig. 2 illustrates a portion of the base station of fig. 1 including the logic elements required for data transmission and retransmission request processing;

fig. 3 is a flow diagram illustrating one embodiment of a method for providing frame retransmission in a broadcast communication system; and

fig. 4 is a flow diagram illustrating one embodiment for determining whether to retransmit a requested frame when a negative acknowledgement message (NAK) is received.

Detailed Description

A method and apparatus for providing frame retransmission in a broadcast communication system is described. Although the embodiments have been described with reference to a terrestrial-based wireless communication system, it will be appreciated that the invention may also be used in other wired and wireless communication systems, such as in a satellite communication system. It should also be understood that the embodiments described herein may also be used in many alternative wireless communication systems, such as in a Code Division Multiple Access (CDMA) system, global system for mobile communications (GSM), or other well-known wireless communication systems.

Fig. 1 is an illustration of a wireless communication system 100 in which Wireless Communication Devices (WCDs) 102, 104 communicate with a base station 108. The base station 108, in turn, communicates with a Mobile Switching Center (MSC) 110. MSC110 interfaces with a public switched telephone network 112 and the internet 114 to provide bidirectional voice and data communications to WCDs 102, 104, and 106. Each WCD is capable of receiving broadcast messages directed to multiple recipients on a forward broadcast control channel (F-BCCH), i.e., a logical communication channel from the base station 108 to the WCD. The message broadcast on the F-BCCH is typically a low speed data message, typically comprising a text message. There are many methods known in the art for a WCD to receive broadcast messages on the F-BCCH. These methods generally include: the WCD monitors a predefined frequency, time slot, and/or code (e.g., a Walsh code of a CDMA system) to receive a paging message indicating the availability of broadcast messages directed to the WCD. Instructions for receiving broadcast messages may be transmitted to WCDs over a forward common control channel (F-CCCH), which is a communication channel received by each WCD in communication system 100.

The communication system 100 may provide some form of point-to-point high speed communication. For example, in a cdma2000A communication system, a forward supplemental channel (F-SCH) is defined that allows data rates of up to 307kbs from the base station 108 to a single WCD. The low-speed data is made available via the F-SCH, a forward fundamental channel (F-FCH), or a forward dedicated control channel (F-DCCH) assigned to a particular WCD.

Communication system 100 incorporates a forward high-speed broadcast channel, i.e., F-HSBCH, for transmitting high-speed data (64 kbs or higher in one embodiment), such as Internet Protocol (IP) datagrams. The F-HSBCH allows users to receive streaming audio and video information. In addition, the F-HSBCH may be used to transport large computer files over the air. Finally, such systems would allow push-to-talk communications for either data or voice applications.

In one embodiment, F-HSBCH is used to transmit high speed data from one or more base stations to multiple WCDs. Each WCD may also monitor one or more paging or control channels to receive signaling and instructions from the base station, e.g., to receive point-to-point voice calls, to receive high speed data on different frequencies/time slots/codes, to receive SMS or other low speed group messages, etc. For example, the WCD may monitor a forward paging channel (F-PCH). In one embodiment, each WCD monitors the F-BCCH and F-CCCH channels for such information. In another embodiment, the information is received by monitoring the F-DCCH, which is a signaling channel used to transmit information to the WCD on a one-by-one basis.

The F-HSBCH may use a retransmission scheme to ensure reception of information to the WCD. In a point-to-point wireless communication system, retransmission is achieved by providing feedback from the WCD to the base station. For example, the well-known Radio Link Protocol (RLP) used in CDMA communication systems uses negative acknowledgement messages (NAKs) to indicate that one or more data frames have not been received. However, this scheme cannot be used in a broadcast communication system because of the possibility of endless retransmission requests from various WCDs receiving the information. That is, as the number of WCDs increases, the probability of any frame requiring transmission also increases greatly. The present invention describes a retransmission scheme for use in a broadcast communication system.

In one embodiment, retransmission of a data frame may occur only when a predetermined number or percentage of WCDs request retransmission using NAK, ACK (acknowledgement message), or any other signaling method known in the art. The predetermined number of retransmission requests may comprise a fixed number or it may be dynamic based on one or more operating conditions of the communication system. For example, in one embodiment, as the delay in transmitting a new frame from the base station increases due to an increase in frame retransmissions, the predetermined number of retransmission requests required to trigger frame retransmissions decreases, and vice versa. The delay in sending a new frame may be measured by measuring the number of new frames waiting to be sent in the electronic memory or buffer.

In another embodiment, frame retransmissions occur according to the number of WCDs receiving a given broadcast. For example, if only 2 WCDs are receiving the streaming audio feed and a single NAK is received from one WCD, the base station will retransmit the necessary frame. However, if there are 100 WCDs receiving a data file, the predetermined number of retransmission requests required to trigger frame retransmission would be high, e.g., 10 NAKs would need to be received before retransmission occurs. The number of WCDs that are receiving a particular broadcast may be determined by: a Home Location Register (HLR) or Visitor Location Register (VLR) associated with a particular base station or base station sector is visited and the number of WCDs registered to receive such broadcasts is counted. This information may be used alone or in combination with indications from the WCD that come through a reverse signaling link requesting participation in a particular broadcast.

Generally, when a frame is received by the WCD in error (or if the frame is not received at all), the WCD transmits a NAK to the base station indicating which frame(s) need to be retransmitted. The NAK may be transmitted on any number of reverse communication channels. For example, in a CDMA2000A compliant communication system, a NAK must be transmitted on a reverse access channel (R-ACH), an extended reverse access channel (R-EACH), a reverse dedicated control channel (R-DCCH), or a reverse common control channel (R-CCCH).

Fig. 2 illustrates a portion of the base station 108 including the logical elements required for data transmission and retransmission request processing. Typically, the preformatted data is fed into buffer 200 for temporary storage before being modulated by processor 210. Buffer 200 comprises a rewritable electronic memory, such as a Random Access Memory (RAM). The data stored in buffer 200 is then provided to modulator 202 where it is modulated in accordance with the selected communication system type. Modulator 202 may comprise discrete electronic components, a VLSI microchip, a custom ASIC, a processor executing a series of executable computer instructions, or a combination thereof, for modulating data from buffer 200. Modulator 202 modulates the data in accordance with a selected communication system type, such as: CDMA, TDMA or GSM. The modulator 202 is well known in the art.

The modulator 202 generally modulates the data frames from the buffer 200 at a constant rate and provides the modulated data frames to the transmitter 204, where the modulated data frames are upconverted and wirelessly transmitted to one or more WCDs within the coverage area of the base station 108.

If one or more data frames are not received correctly by the WCD (or not received at all), the WCD may generate a request for the base station 108 to retransmit the "lost" frame. This request, commonly referred to as a retransmission request, is in one embodiment a negative acknowledgement message, i.e., NAK. The NAK generally identifies which frames are lost to enable the base station 108 to retransmit the necessary frames.

When the WCD transmits a NAK, the receiver 206 receives the NAK at the base station 108. The receiver 206 down-converts the NAK and provides it to the demodulator 208. The demodulator 208 demodulates the NAK according to the type of communication system used, e.g., CDMA, TDMA, GSM, etc. The NAK is then provided to processor 210. The processor 210 comprises a microcomputer that executes a set of executable computer instructions stored in a non-volatile electronic memory such as Read Only Memory (ROM) 212. The ROM212 may alternatively include any number of known electronic memories, including electrically erasable programmable read-only memory (EEPROM), erasable programmable read-only memory (EPROM), or flash memory.

When processor 210 receives a NAK, processor 210 evaluates which frames were requested for retransmission. These frames may be identified by any technique known in the art, for example, by numbering when data frames are transmitted. After processing the NAK, processor 210 stores the pertinent details of the NAK in erasable memory 214. The erasable memory 214 generally comprises Random Access Memory (RAM) or other electronic memory device for volatile electronic data storage. Processor 210 may store information related to the received NAK, such as an identification of the requested data frame to be retransmitted and/or the time of receipt of the NAK. It is also possible to store the identity of the WCD that sent the NAK. This identification typically occurs simultaneously with each NAK, as is well known in the art.

Processor 210 then determines whether one or more of the data frames requested within the NAK are to be retransmitted. Retransmissions may occur under certain conditions, which are detailed below. If processor 210 determines that frame retransmission is necessary, it instructs modulator 202 to select the desired data frame from buffer 200. Modulator 202 then modulates the identified frames and provides the modulated frames to transmitter 204 for transmission to one or more WCDs.

Fig. 3 is a flow diagram illustrating one embodiment of a method for providing frame retransmission in a broadcast communication system. In step 300, one or more data frames are transmitted from the base station 108 to one or more WCDs. In step 302, a first NAK is received from the WCD identifying one or more data frames that were not successfully received. In step 304, processor 210 determines whether to retransmit the requested data frame based on a previously received NAK. If processor 210 determines that retransmission is required, processor 210 instructs modulator 202 to retransmit the identified number of data frames, step 306. If the processor 210 determines that retransmission is not required, the processor 210 takes no action related to frame retransmission, which is shown in step 308.

Figure 4 is a flow diagram of one embodiment for determining whether to retransmit a requested frame upon receipt of a NAK. In step 400, a NAK is received from the WCD. In step 402, processor 210 examines the NAK to determine which data frames to retransmit the request, and determines the WCD identification. In step 404, processor 210 checks memory 214 to determine whether one or more of the requested data frames have been requested by another WCD, depending on the WCD identification stored in memory 214. If another WCD has requested at least one of the frames requested by the NAK just received, processor 210 increments a count of the number of times one or more data frames have been requested for retransmission, as shown at step 406. The count is then stored in memory 214 in conjunction with the requested data frame, as shown in step 408.

In another embodiment, processor 210 assigns a count to each data frame identified by a NAK and stores the identification of each frame and its associated count in memory 214. Upon receiving a NAK, processor 210 compares each data frame identified by the NAK to the number of times each data frame has been requested for retransmission indicated in memory 214. If the number of retransmission requests associated with a particular data frame is equal to a predetermined number, the data frame is retransmitted. In another embodiment, the count is not incremented unless the relevant frame of the count is requested by a new WCD, i.e., a WCD that has not previously requested the particular frame. In this embodiment, a WCD identification is stored as each NAK is received so that subsequent retransmission requests can be checked to ensure uniqueness.

If another WCD has not previously requested retransmission of the data frame identified by the NAK just received, processor 210 stores information associated with the NAK just received in memory 214, as shown in step 410. Such information includes at least an identification of the data frame requested for retransmission. The information may also include a count associated with the number of times the data frame has been identified for the retransmission request.

In step 412, processor 210 compares the count associated with the NAK just received to a predetermined number to determine whether to retransmit the expected data frame. If the count is greater than or equal to the predetermined number, processor 210 instructs modulator 202 to retransmit the frame identified in the NAK just received, as shown at step 414. If the count is less than the predetermined number, processor 210 does not command a retransmission and processor 210 waits to receive another NAK, as shown at step 416.

The predetermined number may be a fixed number or a variable number. If it is a fixed number, it is selected to avoid excessive retransmissions, as this interrupts the transmission of new information to the WCD. For example, the predetermined number may comprise a number of 10, such that no retransmission occurs until at least 10 WCDs request retransmission of the same frame.

If the predetermined number is a variable number, it may vary according to one or more factors determined by an external signal provided by processor 210 or by another processor (not shown). Typically, the predetermined number will vary depending on the delay (i.e., latency) of the data frame waiting to be transmitted. In one embodiment, the latency may be measured by the buffer 200 being checked. As the number of data frames waiting to be transmitted in buffer 200 increases, the latency associated with those data frames also increases. Thus, processor 210 may measure the current latency by determining the number of data frames stored within buffer 200. If the number of data frames stored in buffer 200 exceeds one or more predetermined thresholds, the predetermined number required for retransmission is correspondingly increased, and vice versa.

In another embodiment, the predetermined number may vary depending on the number of WCDs receiving the group transmission. In this embodiment, the more WCDs receiving a transmission, the more the predetermined number increases and vice versa. For example, if only two are receiving a broadcast transmission by a WCD and one of the two WCDs sends a NAK, processor 210 may retransmit the identified data frame upon receipt of a single retransmission request. In this case, the predetermined number is equal to 0. If there are one hundred WCDs receiving the broadcast transmission, processor 210 may not command a retransmission until more NAKs, such as 20 such NAKs, are received identifying the same data frame.

Of course, other embodiments will use a combination of the fixed or variable techniques just discussed. For example, basing the predetermined number on the number of WCDs receiving the broadcast transmission and the transmission latency. In this example, retransmissions may be based on a variable predetermined number, but limited by a predefined upper limit, which is an upper limit on the amount of latency tolerated by the receiving WCD. Other combinations are of course possible.

In yet another embodiment, the predetermined number is based on the type of medium being broadcast to the WCD. In this embodiment, if the medium is not time sensitive, the predetermined number is set to a relatively low number, possibly even 1. Non-time sensitive media may include data files like e-mail and software programs, and are generally identified by small or nonexistent effects from the perspective of the WCD user. Time sensitive media may include voice or audio information and are generally classified by relatively small latency delays that can have a significant negative impact on the application of the WCD user. For example, small latency delays typically have a significant negative impact on the communication quality of a user during a voice call.

In any case, the various media types available in communication system 100 are predefined such that processor 210 may adjust the predetermined number according to each media type. During call setup, an indication of the type of medium is passed to processor 210, typically by issuing a message from the originating WCD indicating the type of communication service desired for the group communication. When the processor 210 receives the indication, it adjusts the predetermined number according to the media type identified by the indication. Of course, the predetermined number may also be adjusted in conjunction with any of the other fixed or variable techniques discussed above.

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 (18)

1. An apparatus for providing frame retransmission in a broadcast communication system, comprising:

a receiver for receiving a message indicating a frame received in error by a wireless communication device, the message including an identification of the frame;

a memory for storing a predetermined number for determining when to retransmit the frame; and

a processor for determining a cumulative number of times the frame was received in error and commanding retransmission of the frame if the cumulative number of times is greater than the predetermined number.

2. The apparatus of claim 1, wherein:

the message further includes a wireless communication device identification;

the memory is further configured to store the wireless communication device identification;

the processor is further configured to determine an accumulated number of times the frame was received in error, the accumulated number of times increasing each time the frame is identified by a subsequent message from the other wireless communication device.

3. The apparatus of claim 2, wherein the message comprises a negative acknowledgement message (NAK).

4. The apparatus of claim 2, wherein the message comprises a frame number.

5. The apparatus of claim 2 wherein said predetermined number comprises a fixed number.

6. The apparatus of claim 2 wherein said predetermined number comprises a variable number.

7. The apparatus of claim 6, wherein the predetermined number varies according to a latency associated with transmitting a new data frame to the wireless communication device.

8. The apparatus of claim 7, further comprising a transmit buffer, wherein the latency is determined by counting a number of data frames waiting to be transmitted within the transmit buffer.

9. The apparatus of claim 6, wherein the predetermined number varies according to a number of wireless communication devices currently receiving a broadcast transmission.

10. A method of providing frame retransmission in a broadcast communication system, comprising the steps of:

receiving a message indicating a data frame received by the wireless communication device in error, the message including a data frame identification;

determining an accumulated number of times the data frame has been received in error; and

retransmitting the data frame if the accumulated number of times is greater than a predetermined number.

11. The method of claim 10, wherein the step of determining a cumulative number of times the data frame has been received in error comprises the steps of:

determining whether the wireless communication device has previously requested retransmission of the data frame; and

incrementing the cumulative number of times if the wireless communication device has not previously requested retransmission of the data frame.

12. The method of claim 11, wherein the step of determining whether the wireless communication device has previously requested retransmission of the data frame comprises the steps of:

receiving a wireless communication device identification associated with the data frame;

determining whether the wireless communication device identification is stored in electronic memory;

determining whether the data frame identification is stored in the electronic memory with the wireless communication device identification;

if the wireless communication device identification is stored in the electronic memory and if the data frame identification is stored in the electronic memory with the wireless communication device identification, then it is determined that the wireless communication device has previously requested retransmission of the data frame.

13. The method of claim 10, wherein the message comprises a negative acknowledgement message (NAK).

14. The method of claim 10, further comprising the steps of:

determining a latency associated with the broadcast transmission; and

adjusting said predetermined number in accordance with said wait time.

15. The method of claim 14, wherein the determining step comprises the steps of: the number of data frames waiting to be transmitted within the transmit buffer is determined.

16. The method of claim 14, wherein the step of adjusting said predetermined number comprises the steps of:

increasing the predetermined number as the wait time decreases; and

decreasing the predetermined number as the wait time increases.

17. The method of claim 10, further comprising the steps of:

determining a number of wireless communication devices currently receiving a broadcast transmission;

adjusting the predetermined number according to the number of wireless communication devices currently receiving the broadcast transmission.

18. The method of claim 17, wherein the step of adjusting said predetermined number comprises the steps of:

increasing the predetermined number as the number of the plurality of wireless communication devices currently receiving the broadcast transmission increases; and

decreasing the predetermined number as the number of the plurality of wireless communication devices currently receiving the broadcast transmission decreases.