Abstract:
A communication device includes a processing unit and a transmitter. The processing unit specifies a number of data blocks in an ARQ receive window and divides the receive window into a number of sectors, each sector having a portion of the number of data blocks in the receive window. The processing unit further receives data blocks within the receive window transmitted from a transmitting communication device and constructs an acknowledgement bitmap for each sector in the receive window. The acknowledgement bitmap includes a sector acknowledgement bit. The transmitter transmits the acknowledgement bitmap for each sector to the transmitting communication device.

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates generally to automatic-repeat-request (ARQ) transmission protocols in communications systems and, more particularly, to systems and methods for implementing hierarchical acknowledgement bitmaps in ARQ transmission protocols. 
     In communication systems employing conventional ARQ protocols, such as, for example, sliding window ARQ, a transmitting device can transmit up to N blocks of data (where N equals the send window size) before receiving any acknowledgement (ACK) messages from a receiving device. As is known in the art, a large sliding window advantageously increases channel utilization and data throughput. The receiving device may acknowledge data blocks received from the transmitting device using a conventional flat bitmap. In such a flat bitmap, one bit, called an acknowledge/negative acknowledge (ACK/NACK) bit, is used to acknowledge or negative acknowledge each individual data block in the receive window. The ACK/NACK bit is set to “1” if a corresponding block has been received. Otherwise, the ACK/NACK bit is set to “0”. 
     Conventionally, the receiving device includes the flat bitmap in a separate ACK/NACK message and sends the message to the transmitting device on a return channel to acknowledge receipt of the data blocks sent by the transmitting device. The receiving device may also piggyback the bitmap in a header of any data block it sends to the transmitting device. The efficient transmission of acknowledgement bitmaps by the receiving device is an important issue if a large window size is used because the conventional flat bitmap may not fit into a single ACK/NACK message. 
     The receiving device can divide a long flat bitmap into several partial bitmaps and then send the partial bitmaps using several transmissions. If a partial bitmap is corrupted, however, the transmitting device must wait longer until it can advance its send window since the send window cannot be advanced until the partial bitmap is received. This delay causes the send window to stall and, thus, the transmitting device cannot transmit any new data blocks. Protocol stalling can be a performance limiting factor in an ARQ protocol (e.g., RLC protocol in Enhanced General Packet Radio Service (EGPRS)) with a large window size and having a long round-trip delay. 
     To overcome the inefficiency of the flat bitmap, the EGPRS protocol, for example, uses a one-dimensional run length coding (based on ITU-T T.4) to compress the bitmap. The T.4 procedure for encoding run lengths, however, can achieve bitmap compression only if, on average, the run lengths are longer than corresponding code words. In many cases, the flat bitmap cannot be compressed, or even worse, the compressed bitmap requires more bits than the flat bitmap. 
     BRIEF SUMMARY OF THE INVENTION 
     In accordance with the purpose of the invention as embodied and broadly described herein, a method for communicating data between a transmitting communication device and a receiving communication device includes specifying a number of data blocks in an ARQ receive window; dividing the receive window into a number of sectors, each sector comprising a portion of the number of data blocks in the receive window; receiving, at the receiving communication device, data blocks within the receive window transmitted from the transmitting communication device; constructing an acknowledgement bitmap for each sector in the receive window, the acknowledgement bitmap comprising a sector acknowledgement bit; and transmitting the hierarchical acknowledgement bitmap for each sector to the transmitting communication device. 
     In another implementation consistent with the present invention, a method for constructing an acknowledgment message in a communication device includes dividing an ARQ receive window into a number of sectors, each sector comprising a portion of a number of data blocks in the receive window; receiving data blocks within the ARQ receive window; and constructing an acknowledgement bitmap for each sector in the receive window, the acknowledgement bitmap comprising a sector acknowledgement bit. 
     In a further implementation consistent with the present invention, a data structure encoded on a computer readable medium includes acknowledgement data for acknowledging data blocks received in each sector of an ARQ receive window, each sector comprising a portion of a number of data blocks in the receive window, the acknowledgement data comprising a sector acknowledgement bit. 
     In an additional implementation consistent with the present invention, a method of compressing an acknowledgement bitmap used in an ARQ protocol includes selecting a size for each sector in an ARQ receive window, each sector comprising a portion of a number of data blocks in the receive window; constructing a hierarchical acknowledgement bitmap for each sector in the receive window, the hierarchical acknowledgement bitmap comprising a sector acknowledgement bit; determining a bit compression of a total acknowledgement bitmap comprising the hierarchical bitmaps for each sector in the receive window; and if the bit compression of the total acknowledgement bitmap is not sufficient, re-selecting the size for each sector of the receive window. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an embodiment of the invention and, together with the description, explain the invention. In the drawings, 
     FIG. 1 illustrates an exemplary system in which a system and method, consistent with the present invention, may be implemented; 
     FIG. 2 illustrates an exemplary communication device consistent with the present invention; 
     FIG. 3 illustrates an exemplary hierarchical acknowledgement bitmap consistent with the present invention; 
     FIGS. 4-5 are flowcharts that illustrate exemplary ARQ processing consistent with the present invention; and 
     FIG. 6 is a flowchart that illustrates an exemplary receive window sector size selection process consistent with the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The following detailed description of the invention refers to the accompanying drawings. The same reference numbers in different drawings identify the same or similar elements. Also, the following detailed description does not limit the invention. Instead, the scope of the if invention is defined by the appended claims. 
     Systems and methods consistent with the present invention provide mechanisms that can achieve acknowledgement bitmap compression under most channel conditions. Bitmap compression can be achieved in the present invention by collectively acknowledging/negative acknowledging consecutive blocks having the same receive status in an ARQ window. 
     FIG. 1 illustrates an exemplary system  100  consistent with the present invention. System  100  may include communication device  105  connected with communication devices  110   a  through  110   n  via network  115 , using wired ( 140 ), wireless ( 135 ) or optical connection links (not shown). Network  115  may include one or more networks utilizing any type of multi-access media, including a local area network (LAN), a metropolitan area network (MAN), a satellite network, a bidirectional cable TV network, or a cellular telephone network. 
     Communication devices  105  and  110   a - 110   n  may be similarly constructed and may include telephones, cellular radiotelephones (with or without a multi-line display), Personal Communications System (PCS) terminals, or the like. PCS terminals may combine a cellular radiotelephone with data processing, facsimile and data communications capabilities. Communication devices  105  and  110   a - 110   n  may further include personal digital assistants (PDAs), conventional laptop and/or palmtop receiver, or other appliances that include radiotelephone transceivers, or the like. PDAs may include radiotelephones, pagers, Internet/intranet access, web browsers, organizers, calendars and/or global positioning system (GPS) receivers. Communication devices  105  and  110   a - 110   n  may further be referred to as “pervasive computing” devices. 
     FIG. 2 illustrates an exemplary communication device  105  consistent with the present invention. Communication device  105  may include a communication interface  205 , an optional antenna  210 , an optional equalizer  215 , an optional encoder/decoder  220 , a processing unit  225 , a memory  230 , output device(s)  235 , input device(s)  240 , and a bus  245 . 
     Communication interface  205  may connect communication device  105  to another device or network, such as network  115 . For example, communication interface  205  may include transceiver circuitry well known to one skilled in the art for transmitting and/or receiving data bursts in a network, such as network  115 , via antenna  210 . 
     Equalizer  215  may store and implement conventional Viterbi trellises for estimating received symbol sequences using, for example, a conventional maximum likelihood sequence estimation technique. Equalizer  215  may additionally include conventional mechanisms for performing channel estimation. 
     Encoder/decoder  220  may include conventional circuitry for decoding and/or encoding received or transmitted symbol sequences. 
     Processing unit  225  may perform all data processing functions for inputting, outputting, and processing of data including data buffering and device control functions, such as call processing control, user interface control or the like. 
     Memory  230  provides permanent, semi-permanent, or temporary working storage of data and instructions for use by processing unit  225  in performing processing functions. Memory  230  may include large-capacity storage devices, such as a magnetic and/or optical recording medium and its corresponding drive. 
     Output device(s)  235  may include conventional mechanisms for outputting data in video, audio, and/or hard copy format. Input device(s)  240  permit entry of data into communication device and may include a user interface and a microphone (not shown). The microphone can include conventional mechanisms for converting auditory input into electrical signals. 
     Bus  245  interconnects the various components of communication device  105  to permit the components to communicate with one another. 
     The configuration of components of communication device  105  illustrated in FIG. 2 is for illustrative purposes only. One skilled in the art will recognize that other configurations may be implemented. 
     FIG. 3 illustrates an exemplary hierarchical bitmap  300 , consistent with the present invention, for implementation in a sliding window Automatic-Repeat-Request (ARQ) protocol. The exemplary hierarchical bitmap  300  may be used to reduce the size of the bitmap transmitted from a receiving device to a transmitting device when a receive window is large. As shown in FIG. 3, a receive window  305  of the sliding window ARQ may comprise n sectors of receive window data blocks  310 , where sector  1   315 , sector  2   320 , and sector  3   325  are shown for illustrative purposes. Each sector may further include a fixed number C of blocks of data (C=4 shown for purposes of illustration). 
     Hierarchical bitmap  300  includes sector bitmaps, one sector bitmap for each sector in receive window  305  (three sector bitmaps shown in FIG. 3 for illustrative purposes). Each sector bitmap may include a level  1  sector ACK bit  340 , a level  2  sector NACK bit  335  and/or a level  3  individual bitmap  330 . An individual bitmap  330  can be associated with each sector and includes C bits, one bit for each block of the sector. If a particular block in a sector has been received (R), then the associated bit in the individual bitmap  330  can be set to “1”. If a particular block in a sector has not been received (N), then the associated bit can be set to “0”. As an example of sector bitmaps in a receive window, FIG. 3 illustrates sector  1  bitmap  345  as including a sector ACK bit; sector  2  bitmap  350  as including a sector ACK bit and a sector NACK bit; and sector  3  bitmap  355  as including a sector ACK bit, sector NACK bit, and an individual bitmap for each data block of the sector. 
     A sector ACK bit  340  specifies whether the data blocks of an entire sector can be collectively acknowledged. That is, if all data blocks of a sector have been received, then the sector ACK bit  340  for that sector can be set to “1”. Furthermore, the sector negative acknowledgement bit (NACK)  335  may not be needed if all data blocks of a sector have been received. Also, the individual bitmap  330  for a sector may not be needed if all data blocks of the sector have been received. For example, all blocks of sector  1   315  have been received, as indicated by “R” in FIG. 3, and the corresponding sector ACK  340  can be set to “1”. Neither the sector NACK bit  335  or the individual bitmap  330  for sector  1   315  would be used in the hierarchical bitmap  300 . 
     If all of the blocks of a sector have not been received, then the sector ACK bit  340  for that sector can be set to “0”. Furthermore, if none of the data blocks in a particular sector have been received, then the sector NACK bit  335  associated with the particular sector can be set to “1”. In this instance, the individual bitmap  330  for the particular sector may not be needed. For example, none of the data blocks of sector  2   320  have been received, as indicated by “N” in FIG. 3, and the sector ACK bit  340  of sector  2  is set to “0” and the sector NACK bit  335  of sector  2  is set to “1”. The individual bitmap  330  for sector  2   320  would not be used in the hierarchical bitmap  300 . 
     If some of the data blocks of a sector have been received, but there is at least one block that has not been received in that sector, then both the sector ACK bit  340  and the sector NACK bit  335  for that sector can be set to “0”. Additionally, the individual bitmap for that sector can be constructed for the sector and included in the hierarchical bitmap  300 . For example, the first and fourth data blocks of sector  3   325  have been received while the second and third data blocks of sector  3   325  have not been received, as indicated by “R” and “N” in FIG.  3 . Therefore, the sector ACK bit  340 , sector NACK bit  335 , and the individual bitmap of sector  3   325  are included in the hierarchical bitmap  300 . 
     FIGS. 4-5 illustrate exemplary processing, consistent with the present invention, for implementing an ARQ protocol at communication device  105  using hierarchical acknowledgement bitmaps. As one skilled in the art will appreciate, the process exemplified by FIGS. 4-5 may be implemented as a sequence of instructions and stored in memory  230  of communication device  105  for execution by processing unit  225 . Alternatively, the process may be implemented in hardware or in any combination of hardware and software. The exemplary processing illustrated in FIGS. 4-5 describes the reception of data blocks at communication device  105  transmitted from, for example, communication device  110   a.    
     Prior to the start of building a hierarchical bitmap, processing unit  225  of communication device  105  initiates an empty hierarchical bitmap in memory  230  and sets a sector index m to 1 [step  405 ]. Processing unit  225  then can divide the data blocks in the current receive window into n sectors, with each sector consisting of C data blocks [step  410 ]. Processing unit  225  can then build a hierarchical bitmap by processing one sector at a time in accordance with the following processing steps. 
     Processing unit  225  determines if all data blocks in sector m have been received from, for example, communication device  110   a  [step  415 ]. If so, processing unit  225  sets a sector ACK bit  340  to “1” [step  420 ] and specifies the bit(s) of a sector bitmap for sector m as comprising the sector ACK bit [step  425 ]. At step  505  (FIG.  5 ), processing unit  225  can append the sector bitmap of sector m to the hierarchical bitmap and store the hierarchical bitmap in memory  230  of communication device  105 . If processing unit  225  determines in step  415  that not all of the data blocks of sector m have been received, then it can set the sector ACK bit  340  to “0” [step  430 ]. 
     Subsequent to step  430 , processing unit  225  may determine if none of the data blocks of sector m have been received [step  435 ]. If no data blocks have been received, processing unit  225  may set the sector NACK bit  335  to “1” [step  440 ] and specify the sector bitmap of sector m as comprising the sector ACK bit  340  and the sector NACK bit  335  [step  445 ]. At step  515  (FIG.  5 ), processing unit  225  can append the sector bitmap of sector m to the hierarchical bitmap and store the hierarchical bitmap in memory  230  of communication device  105 . 
     If processing unit  225  determines in step  435  that some of the data blocks of sector m have been received, but at least one data block of sector m has not been received, then processing unit  225  can set the sector NACK bit to “0” [step  450 ]. Processing unit  225  then can construct an individual bitmap  330  for all data blocks of sector m starting from the first data block of sector m [step  455 ]. To construct an individual bit amp  330  for sector m, an individual ACK bit can be set to “1” for each data block of sector m that has been received. Furthermore, an individual ACK bit can be set to “0” for each data block of sector m that has not been received. After an individual bitmap has been constructed for sector m, processing unit  225  can specify the sector bitmap of sector m as comprising the sector ACK bit, the sector NACK bit and the constructed individual bitmap [step  460 ]. At step  510  (FIG.  5 ), processing unit  225  can append the sector bitmap of sector m to the hierarchical bitmap and store the hierarchical bitmap in memory  230  of communication device  105 . 
     After processing unit  225  finishes the sector designated by the current sector index m, processing unit  225  proceeds to a next sector by incrementing sector index m by 1 [step  520 ]. Processing unit  225  can then determine if sector index m is equal to the number of sectors n in the receive window [step  525 ]. If not, processing returns to step  415 . If m=n, then processing unit  225  passes the bits of the hierarchical bitmap, together with other possible information, to communication interface  205  for transmission to, for example, communication device  110   a  [step  530 ]. 
     FIG. 6 illustrates an exemplary process, consistent with the invention, for selecting a sector size C for each sector of receive window  305 . The sector size C, in combination with the number of sectors n of the receive window and the transmission block error rate (BLER), determines a bitmap compression ratio as compared to a conventional ARQ flat acknowledgement bitmap. The following exemplary process, thus, enables the determination of a desired bitmap compression ratio given a sector size C, a maximum receive window size (RWS MAX ) and a BLER. 
     To begin the sector size selection process, a BLER and a RWS MAX  are first selected [step  605 ]. For example, a BLER of 10% (i.e., 0.10) and a RWS MAX  of 1024 may be selected. A desired sector size C for each sector in the receive window is further selected [step  610 ]. For example, a C of 4 data blocks may be selected, as depicted in FIG.  3 . The number n of sectors, corresponding to the maximum receive window size RWS MAX  and the selected sector size C, can be determined by the following relation [step  615 ]:              n   =       RWS   MAX     C             Eqn   .     (   1   )                                  
     Given the example values of RWS MAX , BLER and C above, the number of sectors n would equal 1024/4, equaling 256. The average number n 1  of sectors that can be acknowledged with a single sector ACK bit can be determined by the following relation [step  620 ]: 
     
       
           n   1   =n (1−BLER) C   Eqn. (2) 
       
     
     Using the example values, n 1  would equal 256*(1−0.1) 4 , equaling 167.9616. The average number n 2  of sectors that can be negative acknowledged with two bits (one sector ACK bit and one sector NACK bit) can be determined by the following relation [step  625 ]: 
     
       
           n   2   =n BLER C   Eqn. (3) 
       
     
     Using the example values n 2  would equal 256*(0.1) 4 , equaling 0.0256. The average number n 3  of sectors that can be individually ACKed/NACKed can be determined by the following relation [step  630 ]: 
       n   3   =n−n   1   −n   2   Eqn. (4) 
     Therefore, using the example values, n 3  would equal 256−167.9616−0.0256, equaling 88.0128. The total number of bits B 1  of the hierarchical bitmap may then be determined using the following relation [step  635 ]: 
     
       
           B   1   =n   1 +2 n   2 +(2 +C ) n   3   Eqn. (5) 
       
     
     Using the example values, B 1  would equal 167.9616+2*0.0256+(2+4)*88.0128, equaling 696.0896. As a comparison, the total number B 2  of bits of a conventional flat bitmap can be determined using the following relation [step  640 ]: 
     
       
           B   2   =Cn   Eqn. (6) 
       
     
     Using the example values, B 2  would equal 4*256, equaling 1024. The bitmap compression ratio (COMPRESSION) of the hierarchical bitmap of the present invention may then be determined using the following relation [step  645 ]:              COMPRESSION   =         B   2     -     B   1         B   2               Eqn   .     (   7   )                                  
     Using the example values, the bitmap compression equals (1024−696.0896) divided by 1024, equaling 0.32 (or 32%). 
     If the determined bitmap compression is insufficient for a particular application, then the desired sector size C can be reselected [step  610 ]. The process depicted in steps  610  through  650  can then be repeated until sufficient bitmap compression is achieved for a particular application. 
     Using the sector size selection process described above, it can be seen that if the BLER is not very high (e.g., &lt;30%), the bitmap size may be reduced even more if only the sector ACK bit, and not the sector NACK bit, is used in the acknowledgement bitmap. This occurs because, with a BLER smaller than 30%, the number of sector that can be NACKed with only two bits is so small that the additional sector NACK bits are wasted. On the other hand, if the BLER is high (e.g., 50% or higher) and/or block errors occur in bursts, then it can be seen that it is advantageous to keep the sector NACK. 
     Systems and methods consistent with the present invention, therefore, provide mechanisms for achieving acknowledgement bitmap compression under most channel conditions as compared to conventional flat acknowledgement bitmaps. Bitmap compression can be achieved in the present invention through the collective acknowledgement/negative acknowledgement of consecutive blocks having the same receive status in an ARQ window. 
     The foregoing description of embodiments of the present invention provides illustration and description, but it is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. For example, the described implementation includes software and hardware, but elements of the present invention may be implemented as a combination of hardware and software, in software alone, or in hardware alone. Also, while series of steps have been described with regard to FIGS. 4-6, the order of the steps may be varied in other implementations consistent with the present invention. No element, step, or instruction used in the description of the present application should be construed as critical or essential to the invention unless explicitly described as such. 
     The present invention may be embodied as cellular communication systems, methods, and/or computer program products. Accordingly, the present invention may be embodied in hardware and/or in software (including firmware, resident software, micro-code, etc.). Furthermore, the present invention may take the form of a computer program product on a computer-usable or computer-readable storage medium having computer-usable or computer-readable program code embodied in the medium for use by or in connection with an instruction execution system. In the context of this document, a computer-usable or computer-readable medium may include any medium that can contain, store, communicate, propagate, or transport the program for use by, or in connection with, an instruction execution system, apparatus, or device. The computer-usable or computer-readable medium may include, for example but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium. 
     More specific examples (a non-exhaustive list) of a computer-readable medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a random access memory (RAM), a read-only memory (ROM), a erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, and a portable compact disc read-only memory (CD-ROM). Note that the computer-usable or computer-readable medium could even be paper or another suitable medium upon which the program is printed, as the program can be electronically captured, via, for instance, optical scanning of the paper or other medium, then compiled, interpreted, or otherwise processed in a suitable manner, if necessary, and then stored in a computer memory. 
     One skilled in the art will recognize that the principles of the present invention may be applied to any wired or wireless system utilizing any type of multi-access scheme, such as TDMA, CDMA or FDMA. It should be further understood that the principles of the present invention may be utilized in hybrid systems that are combinations of two or more of the above multi-access schemes. In addition, a communication device, in accordance with the present invention, may be designed to communicate with, for example, a wireless base station transceiver using any standard based on GSM, TDMA, CDMA, FDMA, a hybrid of such standards or any other standard. 
     The scope of the invention is defined by the claims and their equivalents.