TITLE OF THE INVENTION: A BANDWIDTH EFFICIENT HARQ SCHEME IN RELAY NETWORK

BACKGROUND OF THE INVENTION: Field of the Invention:

[0001] The present invention relates to wireless communications and, more specifically, to wireless relay networks. Description of the Related Art:

[0002] A wireless relay network is a multi-hop system in which end nodes, such as mobile stations (MS) and subscription stations (SS) are connected to the base station (BS) or access point (AP) via a relay station (RS). The traffic between the MS/SS and the BS/AP passes through and is processed by the relay station (RS). [0003] The 802.16 Mobile Multi-Hop Relay (MMR), a study item established in the IEEE 802.16 working group, provides examples of relay networking. The MMR working group focuses on defining a network system that utilizes relays stations (RS) to extend the network coverage and/or enhance the system throughput. Figure 1 illustrates an exemplary relay network which comprises, in part, a relay station (RS), mobile station (MS), subscriber station (SS) and base station (BS).

[0004] Hybrid automatic repeat request (H-ARQ) is a scheme which combines ARQ protocols with forward-error-correcting (FEC) schemes that are generally considered to be the best error-control techniques for wireless links. Different wireless technology may have different H-ARQ schemes. [0005] In IEEE 802.16, the H-ARQ scheme is implemented as a part of the media access controller (MAC) and can be enabled on a per-terminal basis. Two main variants of H-ARQ are supported: chase combining and incremental redundancy (IR). For IR, the PHY layer encodes the H-ARQ generating four versions for the encoded H-ARQ attempts. Each H-ARQ attempt is uniquely identified using a H-ARQ attempt identifier (SPID). For chase combining, the PHY layer encodes the H-ARQ packet generating only one version of the encoded packet. As a

result, no SPID is required for chase combining.

[0006] For downlink operation, the BS sends a version of the encoded H-ARQ packet to the MS/SS. The MS/SS attempts to decode the encoded packet on this first H-ARQ attempt. If the decoding is successful, the MS/SS sends an acknowledgement (ACK) to the BS. If the decoding is not successful, the MS/SS sends a non-acknowledgement (NAK) to the BS. In response, the BS will send another H-ARQ attempt to the MS/SS. The BS may continue to send H-ARQ attempts until the MS/SS successfully decodes the packet and sends an ACK. [0007] The H-ARQ scheme works well in a system without a relay station (RS) where the H-ARQ scheme is applied directly between the BS and MS/SS. However, when a RS is introduced into the system, although H-ARQ is still implemented between the MS/SS and BS, the RS needs to forward all the H- ARQ attempts and ACK/NAKs between the MS/SS and BS. [0008] Therefore, according to prior art solutions, if the first H-ARQ attempt is not sent successfully due to error or loss, another H-ARQ attempt needs to be sent unitl the MS/SS or BS successfully decodes it. Consequently, the subsequent H-ARQ attempt(s) must be transmitted over all the different hops (links) between the BS and MS/SS. Bandwidth is re-allocated between BS and MS/SS for transmitting the subsequent H-ARQ attempt(s), even though some of the links may have already transferred the frame successfully. This results in bandwidth wastage and throughput loss. Thus, there is a need for an enhanced H-ARQ scheme with an improved utilization of network resources. [0009] In view of the above, embodiments of the present invention provide an improved H-ARQ scheme which provides better bandwidth utilization. The invention can be applied to relay in various wireless technologies, such as WiMax MMR.

SUMMARY OF THE INVENTION:

[0010] The present invention provides, in one embodiment, a method of

communication in a wireless relay network. The method includes sending an H- ARQ attempt from a base station to a relay station, from a mobile station to a relay station, or between relay stations. The attempt may include a packet and the relay station makes an effort to decode the packet. The method further includes forwarding the attempt to a mobile station or base station and decoding the packet at the mobile station or base station. An acknowledgement is sent from the mobile station to the base station, or from the base station to the relay station, when the packet is decoded successfully. Otherwise, a non-acknowledgement is sent indicating that the packet could not be successfully decoded. The method also includes identifying, at the base station, a first relay station (RS _n ) which did not successfully receive and decode the packet. The base station then instincts a previous relay station (RS _n-1 ) to generate the H-ARQ attempt which was not successfully decoded by RS _n and forwarding it to RS _n .

[0011] The present invention also provides, according to one embodiment, a wireless communication system. The wireless communication system includes a plurality of relay stations, a base station, and at least one mobile station. An H- ARQ attempt is forwarded from the base station or the at least one mobile station, through the relay stations, to the at least one mobile station or the base station. The base station is configured to identify a first relay station which did not successfully receive and decode the packet based on feedback information. [0012] In addition, the invention provides, in one embodiment, a base station. The base station includes a transmitter configured to transmit an attempt to at least one relay station. The at least one relay station is configured to decode the attempt and forward the attempt to a mobile station. The base station further includes an identifying unit configured to identify, when the attempt was not successfully decoded, a first relay station that did not successfully receive and decode the attempt. The base station also includes an instructing unit configured to instruct a previous relay station to generate the attempt which was not successfully decoded and to forward the attempt to the first relay station that did not successfully receive and decode the attempt.

[0013] The present invention further provides, according to one embodiment, a wireless communication system. The wireless communication system includes means for sending an H-ARQ attempt from a base station, or a mobile station, to a relay station. The method further includes means for forwarding the attempt to a mobile station or base station and decoding the packet at the mobile station or base station. The method also includes means for identifying, at the base station, a first relay station (RS _n ) which did not successfully receive and decode the packet, and means for instructing a previous relay station (RS _n- i) to generate the H-ARQ attempt which was not successfully decoded by RS _n and forwarding it to RS _n .

[0014] The invention also provides, in one embodiment, a mobile station. The mobile station includes a transmitter configured to transmit an attempt to at least one relay station. The at least one relay station is configured to decode the attempt and forward the attempt to a base station. When the attempt was not successfully decoded, a first relay station that did not successfully receive and decode the attempt is identified. A previous relay station is then instructed to generate the attempt which was not successfully decoded and to forward the attempt to the first relay station that did not successfully receive and decode the attempt.

BRIEF DESCRIPTION OF THE DRAWINGS:

[0015] For proper understanding of the invention, reference should be made to the accompanying drawings, wherein:

Fig. 1 illustrates an example of a wireless communications network according to an embodiment of the invention;

Fig. 2 illustrates an example of a relay network with one or multiple relay stations according to an embodiment of the invention;

Fig. 3 illustrates an example of a relay network with enhanced H-ARQ according to an embodiment of the invention;

Fig. 4 illustrates another example of a relay network with enhanced H-

ARQ according to an embodiment of the invention;

Fig. 5 illustrates an example of a relay network with enhanced H-ARQ according to an embodiment of the invention;

Fig. 6 illustrates an example of a relay network with enhanced H-ARQ according to an embodiment of the invention;

Fig. 7 illustrates an example of a relay network with enhanced H-ARQ according to an embodiment of the invention;

Fig. 8 illustrates a method of communication in a wireless network according to one embodiment of the invention;

Fig. 9 illustrates a block diagram according to an embodiment of the invention;

Fig. 10 illustrates a method of communication in a wireless network according to one embodiment of the invention;

Fig. 11 illustrates a block diagram according to an embodiment of the invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT(S): [0016] The present invention provides an enhanced H-ARQ scheme that optimizes bandwidth utilization and spectrum efficiency. As discussed above, H- ARQ is a scheme that combines ARQ protocols with FEC schemes which are considered to be the best error-control techniques for wireless links. [0017] Previously, when an H-ARQ attempt was not successfully received at the MS/SS- due to error or loss, subsequent attempts would be sent until the MS/SS successfully decodes the packet and sends an acknowledgement. These subsequent H-ARQ attempts need to be transmitted over all the different links between the MS/SS and BS, thereby resulting in the re-allocation of bandwidth between the MS and BS despite the fact that some of the links may have already transferred the frame successfully.

[0018] According to embodiments of the present invention, on the other hand, when an H-ARQ attempt is unsuccessful due to loss or error over a hop between the BS and MS/SS, then only the first node in the hop chain that fails to decode the packet transmits another H-ARQ attempt. The BS determines the first node that fails on decoding based on the feedback information sent from the nodes on the path. The node previous to the failed node is then instructed to retransmit by the BS. Specific embodiments of the invention are discussed below. [0019] Fig. 1 illustrates an example of a wireless communication system according to one embodiment of the invention. The wireless communication system includes a base station BS in communication with at least one mobile station MS and at least one relay station RS. The mobile station MS may then move such that it is in communication with the relay station RS. The relay station RS, in turn, may be in communication with at least one subscriber station SS. [0020] Figs. 8 and 10 illustrate examples of methods of communication in a wireless relay network, such as the one illustrated in Fig. 1. The methods include sending an H-ARQ attempt from a base station to a relay station, from a mobile station to a relay station, or between relay stations. The attempt may include a packet and the relay station makes an effort to decode the packet. The method further includes forwarding the attempt to a mobile station or base station and decoding the packet at the mobile station or base station. An acknowledgement is sent from the mobile station to the base station, or from the base station to the mobile station, when the packet is decoded successfully. Otherwise, a non- acknowledgement is sent indicating that the packet could not be successfully decoded. The method also includes identifying, at the base station, a first relay station (RS _n ) which did not successfully receive and decode the packet based on feedback information sent from the relay stations. The base station then instructs a previous relay station (RS _n-1 in the downlink direction, or-RS _n+ i in the uplink direction) to generate the H-ARQ attempt which was not successfully decoded by RS _n and forwarding it to RS _n . [0021] Fig. 9 illustrates a block diagram of a system according to one example of

the invention. The system includes a base station, a plurality of relay stations, and a mobile station. As mentioned above, according to an embodiment of the invention, the base station forwards an H-ARQ attempt to the first relay station. The H-ARQ attempt is then forwarded through the plurality of relay stations until reaching the mobile station. The mobile station sends an acknowledgement (ACK) when the packet is decoded successfully. When the packet is not successfully decoded, the mobile station sends a non-acknowledgement (NAK) to the base station.

[0022] Alternatively, as illustrated in Fig. 11, the H-ARQ attempt may be forwarded in the uplink direction. In other words, according to an embodiment of the invention, the mobile station forwards an H-ARQ attempt to the first relay station. The H-ARQ attempt is then forwarded through the plurality of relay stations until reaching the base station. The base station sends an acknowledgement (ACK) when the packet is decoded successfully. When the packet is not successfully decoded, the base station sends a non- acknowledgement (NAK) to the mobile station.

[0023] Fig. 2 illustrates a relay network with one or multiple relay stations according to an embodiment of the invention. Fig. 2 assumes that there are n relay stations over the link between BS and MS. For the downlink traffic, H- ARQ attempt(s) are sent from RSj to RS _i+1 . After receiving a H-ARQ attempt, RSj ₊₁ decodes the encoder packet based on previously received H-ARQ attempt(s) if the currently received H-ARQ attempt is not H-ARQ attempt 00. Otherwise, RSi ₊₁ decodes the H-ARQ attempt 00. If the packet is successfully decoded, an ACK is sent back to BS or RSi and the successfully decoded packet is restored by RSj ₊₁ . Otherwise, a NAK is sent instead and RSi ₊₁ keeps a copy of the previously received H-ARQ attempt(s). The H-ARQ attempt, whether it is correctly decoded or not by RSj, is forwarded by RS ₁ to RS _i+1 until it reaches the MS/SS, which will send an ACK or NAK depending on the decoding result.

[0024] Alternatively, the H-ARQ may not be forwarded to the next hop, if it is

not correctly decoded. Instead a null frame or some other indication is forwarded, if the bandwidth cannot be allocated for any other purpose. [0025] Upon receiving the packet in the pre-assigned bandwidth, the MS/SS decodes the packet. If the MS/SS is not able to decode the packet correctly, it sends a NAK to the BS. Upon receiving a NAK from the MS/SS, based on the ACKs/NAKs received from the RSs, the BS is able to identify the first RS on the downlink path (assuming RS _k ), which has not successfully received and decoded the packet. The manner in which the BS identifies such an RS will be discussed in greater detail below. The BS then instructs RS _k -i to generate the H-ARQ attempts based on the PHY specification and sends the specified H- ARQ attempt to the MS/SS. Therefore, the BS does not need to resend the H- ARQ attempt from BS to RS _k-1 , but only schedules the resources for sending specified H-ARQ attempt from RS _k- i to the MS/SS. The same procedure described above is applied until the MS/SS successfully receives the packet. Once the MS/SS decodes the packet successfully, MS sends ACK back to the BS, and BS considers this packet as transmitted successfully. [0026] As mentioned above, there may be two approaches for the BS to identify the first RS over the downlink path, which has not received or successfully decoded the encoder packet. A first approach is illustrated in Fig. 3. As shown therein, whenever RSj receives a H-ARQ attempt, it sends ACK/NAK directly back to BS (i.e., the ACK/NAK is not processed by the RSs in between). The first RS on the downlink path from the BS to MS/SS, which sends a NAK or from which no feedback is received, is the first RS that has not received or successfully decoded the encoder packet. In order for the RSs to transmit the ACK/NAK, the BS needs to schedule uplink resources to carry such feedback information from all the RS _f (i >k) whenever BS sends a H-ARQ attempt or instructs RS _k to send a H-ARQ attempt as described above. [0027] A second approach for the BS to identify the first RS which has not received or successfully decoded the encoder packet is illustrated in Fig. 4. As shown in Fig. 4, a H-ARQ attempt is generated from the BS or RS _k and sent

toward the MS/SS over the downlink path. The feedback (ACK/NAK) is generated from RSj ₊₁ (note: RS _n+I = MS/SS) and sent to RSj on the reverse path. If RSj was not able to decode the encoder packet, then RSj updates the feedback information from RSj ₊₁ indicating that the feedback is a NAK and RSi is the first node that did not successfully decode the encoder packet. The feedback information is propagated and updated over the reverse path from the MS/SS to RS _k . RS _k then sends the feedback information directly to the BS. Based on such feedback information, the BS is then able to identify the first RS on the downlink path, which has not received or successfully decoded the encoder packet. This approach requires the BS to schedule the resource to carry the feedback information from MS/SS to RS _k via all the RSs in between and directly from RS _k to the BS.

[0028] For the uplink traffic, H-ARQ attempt® are sent from RS _i+1 to RSj. After receiving a H-ARQ attempt, RSi decodes the encoder packet based on previously received H-ARQ attempt(s) if the currently received H-ARQ attempt is not H-ARQ attempt 00. Otherwise, RS ₁ decode the H-ARQ attempt 00. If the packet is successfully decoded, an ACK is sent back to BS Otherwise, a NAK is sent instead and RSj keeps a copy of the previously received H-ARQ attempt(s). The H-ARQ attempt, whether it is successfully decoded or not by RSi, is forwarded by RSi to RS _1-1 until it reaches the BS, which will send an ACK or NAK depending on the decoding result. Alternatively, the H-ARQ attempt may not be forwarded to the next hop if it is not correctly decoded, and instead a null frame or some other indication is forwarded, if the bandwidth cannot be allocated for any other purpose.

[0029] Upon receiving the packet in the pre-assigned bandwidth, the BS decodes the packet. If the BS is not able to decode the packet correctly, it sends a NAK to the MS. At the same time, based on the ACKs/NAKs received from the RSs, the BS is able to identify the first RS on the uplink path (assuming RS _k ), which has not successfully received and decoded the packet. The manner in which the BS may identify such a RS is discussed in further detail below.

The BS then instructs RS _k+ i to generate the H-ARQ attempts based on the PHY specification and sends the specified H-ARQ attempt to the BS. Therefore, the BS does not need to instruct MS/SS to send the H-ARQ attempt, but only schedules the resources for sending specified H-ARQ attempt from RS _k+1 to the BS. The same procedure described above is applied until the BS successfully receives the packet. The BS may send ACK back to the MS/SS after decoding the packet successfully or knowing RS _k+1 (if RS _k+1 != MS/SS) decodes the packet successfully.

[0030] As mentioned above, there may be two approaches for the BS to identify the first RS over the uplink path, which has not received or successfully decoded the encoder packet. Fig. 5 illustrates a first approach. As shown in Fig. 5, whenever RSi receives a H-ARQ attempt over uplink and is not able to decode it successfully, it sends an ACK/NAK directly back to BS (i.e., the ACKTNAK is not processed by the RSs in between). The first RS on the uplink path from the MS/SS to the BS, which sends a NAK or from which no feedback is sent, is the first RS that has not received or successfully decoded the encoder packet. In order for the RSs to transmit the ACK/NAK, the BS needs to schedule uplink resource to carry such feedback information from all the RSi (i <k) whenever the BS sends a H-ARQ attempt or instructs RS _k to send a H-ARQ attempt as described above.

[0031] Fig. 6 illustrates a second approach for the BS to identify the first RS over the uplink path that has not received or successfully decoded the encoder packet. As shown in Fig. 6, a H-ARQ attempt is generated from MS/SS or RS _k and sent toward the BS over the uplink path through the RSs. Two options may be available for transmitting the feedback information.

[0032] According to one embodiment of the invention, as illustrated in Fig. 6, upon receiving a H-ARQ attempt, RSj ₊₁ decodes the encoded packet and a feedback (ACK/NAK) is generated and sent to RSj on the uplink path. If RSj ₊₁ decodes the packet successfully, it may send a ACK to RSj ₊₂ , which triggers RSi ₊₂ to clear the buffer of the stored packet. Assuming RS _k is the first RS over

the uplink path, which is not able to successfully decode the encoded packet. Then after finding out the failure of decoding and receiving the ACK from RS _k+I , RS _k then updates the feedback information from RS _k+1 indicating that the feedback is a NAK and it is RS _k that is not able to decode the packet. RS _k then sends the NAK to RS _k-1 . When RS _k-1 receives the NAK, it just forwards it to RS _k - ₂ until the NAK reaches the BS. This requires the BS to schedule the resources to carry the ACK/NAK between every two adjacent RSs on the uplink path starting from RS _k-i .

[0033] According to another embodiment of the present invention, as illustrated in Fig. 7, only the NAK is transmitted over the regular data traffic channel. Upon receiving a H-ARQ attempt, RSj ₊₁ decodes the encoded packet. If successful, RSi ₊₁ only sends the encoded packet to RSj without sending an ACK. Assuming RS _k is the first RS over the uplink path, which is not able to successfully decode the encoded packet. Then after finding out the failure of decoding, RS _k generates a NAK with indication that it is the first node that fails to decode the packet and sends it to RS _k-1 . Since RS _k-1 will not forward the non-decoded packet to the next hop, it uses the traffic channel that was originally assigned to carry the H-ARQ attempt to carry the NAK and sends it to RS _k-2 . Such a process continues until the NAK reaches the BS. [0034] Regardless of which option is implemented, if the BS receives a NAK, then based on such feedback information, the BS is able to identify the first RS on the uplink path that has not received or successfully decoded the encoder packet.

[0035] Furthermore, certain embodiments of the present invention provide a method of carrying feedback information from the relay stations (RS) to the base station (BS) in 802.16 technology. The present invention provides several ways for carrying the feedback information in a downlink direction. According to one embodiment, the UL MAP allocates resources to carry the feedback (i.e., NAK) in the HARQ ACK Region delivered through the HARQ ACK Region Allocation IE or the Comρact_UL_MAP_IE from each RS ₁ (i >k) and MS.

[0036] One option for carrying feedback information in a downlink direction is for the UL MAP to allocate resources for every RS to either generate or propagate the feedback information to the previous RS. The feedback information contains ACK/NAK which is carried in the HARQ ACK Region delivered through the HARQ ACK Region Allocation IE ₅ or the CompactJUL- MAPJE and the RS IDs of the RSs that send the NAK and traffic direction for each frame acknowledged in the HARQ ACK Region.

[0037] Since the feedback from RSs for both uplink and downlink traffic is transmitted in the uplink direction, the RSs needs to know if the feedback is allocated for uplink traffic or the downlink traffic. If it is uplink, the feedback is associated with the uplink traffic carried in the same frame. If it is downlink, the feedback is associated with the downlink traffic transmitted before a fixed period defined by H-ARQ DL ACK delay offset. A Direction field may be included to indicate such information.

[0038] Note that for each of the frames, there will be one RS which is the first RS that is not able to decode the packet successfully. Therefore, the feedback information contains a block map. Each block contains one RS ID, which corresponds to the frame at the same location of the ACK bitmap in the ACK Channel Region. Possible approaches for indicating the location of the set of RS ids (i.e., a block map) in the UL MAP are listed below: Approach 1:

Use Compact UL-MAP IE for extension for compact UL MAP case.

Approach 2:

Use Extended-2 UIUC in UL-MAP extended-2 IE for normal UL MAP case.

The new HARQ RSID_Indication_IE is defined in the following table.

[0039] With respect to carrying feedback information in an uplink direction, the same approaches can be used as for the downlink direction but with the Direction field set to 0. Additionally, according to an embodiment of the invention, the RS ID in the feedback information can be carried using the traffic channel allocated for the HARQ data which is not sent due to unsuccessful decoding. In order to indicate whether the payload is regular traffic or RS ID information, the extended subheader can be used as shown below.

The format of HARQ RSID Indication extended subheader can be defined as shown below.

[004O]As a result of the various embodiments and examples described above, the present invention provides novel systems and methods for an improved H- ARQ scheme which provides better bandwidth utilization. [0041] One having ordinary skill in the art will readily understand that the invention as discussed above may be practiced with steps in a different order, and/or with hardware elements in configurations which are different than those which are disclosed. Therefore, although the invention has been described based upon these preferred embodiments, it would be apparent to those of skill in the art that certain modifications, variations, and alternative constructions would be apparent, while remaining within the spirit and scope of the invention.