Abstract:
A novel method and apparatus for coping with lost acknowledgements from power-saving stations in local-area networks are disclosed. In particular, the illustrative embodiment modifies the access point&#39;s and power-saving stations&#39; protocols to prevent repeated lost acknowledgements from occurring. An access point, after transmitting the final downlink frame of a sequence to a station and receiving an acknowledgement from the station, transmits a “double acknowledgement” to the station. A power-saving station, after receiving the final downlink frame of a sequence and transmitting an acknowledgement to the access point, stays awake until one of the following occur: (i) the station receives a double acknowledgement, (ii) the station observes a frame transmitted from the access point to another station, or (iii) the station observes that the shared-communications channel of the local-area network is idle for a particular time interval.

Description:
REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of:
         1. U.S. provisional patent application Ser. No. 60/443,581, filed 30 Jan. 2003, entitled “Dealing With Loss Of Acknowledgements From Stations Operating In Power-Saving Mode In Wireless LANs,” which is also incorporated by reference.       

    
    
     FIELD OF THE INVENTION 
     The present invention relates to telecommunications in general, and, more particularly, to wireless local area networks. 
     BACKGROUND OF THE INVENTION 
       FIG. 1  depicts a schematic diagram of an exemplary wireless local-area network (LAN)  100  in the prior art comprising access point  101  and stations  102 - 1  through  102 -N, wherein N is a positive integer, interconnected as shown. Each station  102 - i , wherein i is a member of the set {1, 2, . . . N}, is a device such as a notebook computer, personal digital assistant (PDA), tablet PC, etc. that transmits radio signals to and receives radio signals from other stations in local-area network  100  via access point  101 . 
     Access point  101  and stations  102 - 1  through  102 -N transmit data in units referred to as frames over a shared-communications channel such that if two or more stations (or an access point and a station) transmit frames simultaneously, then one or more of the frames can become corrupted (resulting in a collision). As a result, local-area networks typically employ one or more protocols to ensure that a station or access point can gain exclusive access to the shared-communications channel for an interval of time in order to transmit its frames. Frames transmitted from a station  102 - i  to access point  101  are referred to as uplink frames, and frames transmitted from access point  101  to a station  102 - i  are referred to as downlink frames. In accordance with some protocols (e.g., Institute of Electrical and Electronics Engineers [IEEE] 802.11, etc.), when a station  102 - i  receives a downlink frame from access point  101 , the station transmits an acknowledgement back to access point  101  informing the access point that the downlink frame was successfully received. Similarly, when access point  101  receives an uplink frame from a station  102 - i , the access point acknowledges receipt of the frame. Acknowledgements may be combined with data frames, the receipt of which must be acknowledged, too. 
     A station  102 - i  can prolong its battery life by powering off its radio (or in general, its transceiver) when not transmitting or receiving. When a station powers off its radio, the station is said to enter a reduced-power state (also called the doze state). A station wakes up from the doze state by powering on its radio to enter the alert state. While a station is in the doze state, it cannot transmit or receive signals, and is said to be asleep. While a station is in the alert state, it can transmit or receive signals; the time interval that a station is known to the access point to be in the alert state is said to be the awake period. A station that conserves battery life by alternating between alert and doze states is said to be in power-save mode, and a station that employs power-save mode is said to be a power-saving station. 
     Problems can arise, however, when power-saving stations enter the doze state. Typically, the protocol enables the station to know whether additional frames will be transmitted to the power-saving station in the alert state before it goes back to sleep. There are several ways for a power saving station to know that a frame is the last frame to be sent by the access point before it wakes up again. For example, according to the IEEE 802.11-1999 protocol, a power-saving station, which sends a frame known as the PS-Poll to notify the access point that it is awake, will receive a single downlink frame from the access point. In another example, a power-saving station that follows the IEEE 802.11e proposed power-saving mechanisms will be notified that a downlink frame is the last frame received in its awake period by the access point setting a special bit in the control field of that frame to 1. 
     Once a station has received the last frames destined for it, it may enter the reduced-power state. However, a problem can arise when a power-saving station, after receiving the last downlink frame, transmits an acknowledgement to the access point and subsequently enters the doze state. In particular, in accordance with some protocols, if the acknowledgement is “lost” (i.e., the access point doesn&#39;t receive the acknowledgement [e.g., due to RF interference, etc.]), then the access point re-transmits the frame to the power-saving station and waits again for an acknowledgement. Because the power-saving station is in the doze state, however, the station does not receive the re-transmitted frame, and therefore does not transmit an acknowledgement to the access point, thereby resulting again in a lost acknowledgement, which causes the access point to re-transmit the frame, etc. The retransmissions repeat indefinitely or until a pre-specified limit on retransmissions is exhausted. The occurrence of such “repeated” lost acknowledgements causes, at the very least, a waste of bandwidth, and potentially, depending on the protocol, a significant increase in delay, jitter, etc. for other stations in the local-area network. 
     SUMMARY OF THE INVENTION 
     The present invention addresses the problem of lost acknowledgements in local-area networks with power-saving stations. In particular, the illustrative embodiment modifies the access point&#39;s and power-saving stations&#39; protocols in order to prevent repeated lost acknowledgements from occurring as a consequence of losing the acknowledgement to the final downlink frame of a sequence of one or more downlink frames. 
     In the illustrative embodiment of the present invention, an access point, after transmitting a downlink frame f to a station, does one of two things:
         if frame f was the last frame in the sequence of frames to transmit to the station, the access point transmits a “double acknowledgement” to the station (i.e., a frame that acknowledges that the station&#39;s acknowledgement was received, and does not normally require an acknowledgement),   otherwise, the access point transmits the next frame in the sequence to the station, in normal fashion.       

     A power-saving station, knowing that a received downlink frame is the last downlink frame the access point will send to the station until the station wakes up again, transmits its acknowledgement and waits until one of the following occur before entering the doze state:
         (i) the station receives a double acknowledgement,   (ii) the station, listening to the shared-communications channel, observes a frame transmitted from the access point to another station, or   (iii) the station, listening to the shared-communications channel, observes that the channel has been idle for a particular time interval (e.g., the Point Coordination Function InterFrame Spacing [PIFS] for an IEEE 802.11 network, etc.).
 
Once any of these three situations occur, the power-saving station enters the doze state. Thus, a power-saving station does not enter the doze state until the station knows that the access point presently will not be sending any more frames to the station.
       

     For the purposes of this specification, the statement that a frame f is the “final frame in a sequence of one or more frames” transmitted to a station comprises:
         (i) the case in which the access point has no more frames buffered for the station, and   (ii) the case in which the access point has insufficient time remaining to transmit additional frames to the station (e.g., the access point proceeds to poll another station in its polling list, the access point transmit frames to another station, etc.), and   (iii) the case in which the access point has no further downlink transmissions planned for a specified time interval, and       

     The illustrative embodiment comprises: (a) receiving a final frame of a sequence of one or more frames; (b) transmitting to the sender of said final frame an acknowledgement that acknowledges said first frame; (c) receiving from the sender of said final frame a frame that acknowledges said acknowledgement; and (d) entering, after (c), a reduced-power state. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  depicts a schematic diagram of an exemplary wireless local-area network  100  in the prior art. 
         FIG. 2  depicts a schematic diagram of a portion of local-area network  200  in accordance with the illustrative embodiment of the present invention. 
         FIG. 3  depicts a block diagram of the salient components of access point  201 , as shown in  FIG. 2 , in accordance with the illustrative embodiment of the present invention. 
         FIG. 4  depicts a block diagram of the salient components of station  202 - i , as shown in  FIG. 2 , in accordance with the illustrative embodiment of the present invention. 
         FIG. 5  depicts a flowchart for access point  201 , as shown in  FIG. 2 , for transmitting one or more frames to station  202 - i , as shown in  FIG. 2 , in accordance with the illustrative embodiment of the present invention. 
         FIG. 6  depicts a flowchart for power-saving station  202 - i , as shown in  FIG. 2 , for determining when to enter a reduced-power state, in accordance with the illustrative embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 2  depicts a schematic diagram of local-area network  200  in accordance with the illustrative embodiment of the present invention. Local-area network  200  comprises access point  201 , and stations  202 - 1  through  202 -N, interconnected as shown. At least one station  202 - i  in local-area network  200  is a power-saving station, where i is an integer in set {1, . . . N}. 
     Access point  201  is capable of receiving frames from stations  202 - 1  through  202 -N via a shared-communications channel, and of transmitting frames to stations  202 - 1  through  202 -N via the shared-communications channel as described below and with respect to  FIG. 5 . 
     Power-saving station  202 - i  is capable of (i) generating frames, (ii) transmitting frames over a shared-communications channel to access point  201 , (iii) receiving frames from the shared-communications channel, and (iv) transitioning from an alert state to a doze state as described below and with respect to  FIG. 6 . 
       FIG. 3  depicts a block diagram of the salient components of access point  201  in accordance with the illustrative embodiment of the present invention. Access point  201  comprises receiver  301 , processor  302 , memory  303 , and transmitter  304 , interconnected as shown. Although in the illustrative embodiment receiver  301  and transmitter  304  make up an integrated transceiver (e.g., a two-way radio, etc.), as shown in  FIG. 3 , it will be appreciated by those skilled in the art that in some embodiments receiver  301  and transmitter  304  might be logically integrated, rather than physically integrated. 
     Receiver  301  is a circuit that is capable of receiving frames from shared communications channel  203 , in well-known fashion, and of forwarding them to processor  302 . It will be clear to those skilled in the art how to make and use receiver  301 . 
     Processor  302  is a general-purpose processor that is capable of executing instructions stored in memory  303 , of reading data from and writing data into memory  303 , and of executing the tasks described below and with respect to  FIG. 5 . In some alternative embodiments of the present invention, processor  302  might be a special-purpose processor (e.g., a network processor, etc.). In either case, it will be clear to those skilled in the art, after reading this disclosure, how to make and use processor  302 . 
     Memory  303  is capable of storing programs and data used by processor  302 , as is well-known in the art, and might be any combination of random-access memory (RAM), flash memory, disk drive, etc. It will be clear to those skilled in the art, after reading this specification, how to make and use memory  303 . 
     Transmitter  304  is a circuit that is capable of receiving frames from processor  302 , in well-known fashion, and of transmitting them on shared communications channel  203 . It will be clear to those skilled in the art how to make and use transmitter  304 . 
       FIG. 4  depicts a block diagram of the salient components of station  202 - i , in accordance with the illustrative embodiment of the present invention. Station  202 - i  comprises receiver  401 , processor  402 , memory  403 , and transmitter  404 , interconnected as shown. Although in the illustrative embodiment receiver  401  and transmitter  404  make up an integrated transceiver (e.g., a two-way radio, etc.), as shown in  FIG. 4 , it will be appreciated by those skilled in the art that in some embodiments receiver  401  and transmitter  404  might be logically integrated, rather than physically integrated. 
     Receiver  401  is a circuit that is capable of receiving frames from shared-communications channel  203 , in well-known fashion, and of forwarding them to processor  402 . Receiver  401  is also capable of being powered off for a doze state. It will be clear to those skilled in the art how to make and use receiver  401 . 
     Processor  402  is a general-purpose processor that is capable of executing instructions stored in memory  403 , of reading data from and writing data into memory  403 , of outputting signals to receiver  401  and transmitter  404  to transition between an alert state and a doze state, and of executing the tasks described below and with respect to  FIG. 6 . In some alternative embodiments of the present invention, processor  402  is a special-purpose processor (e.g., a network processor, etc.). In either case, processor  402  contains one or more logic circuits, as is well known in the art, and it will be clear to those skilled in the art after reading this disclosure how to make and use processor  402 . 
     Memory  403  is capable of storing programs and data used by processor  402 , as is well-known in the art, and might be any combination of random-access memory (RAM), flash memory, disk drive, etc. It will be clear to those skilled in the art, after reading this specification, how to make and use memory  403 . 
     Transmitter  404  is a circuit that is capable of receiving frames from processor  402 , in well-known fashion, and of transmitting them on shared communications channel  203 . Transmitter  404  is also capable of being powered off for a doze state. It will be clear to those skilled in the art how to make and use transmitter  404 . 
     In the illustrative embodiment of the present invention, access point  201  and stations  202 - 1  through  202 -N support at least one IEEE 802.11 protocol. In alternative embodiments of the present invention, access point  201  and stations  202 - 1  through  202 -N might support other protocols in lieu of, or in addition to, one or more IEEE 802.11 protocols. Furthermore, in some embodiments of the present invention local-area network  200  might comprise an alternative shared-communications channel (for example, wireline instead of wireless). In all such cases, it will be clear to those skilled in the art after reading this specification how to make and use access point  201  and stations  202 - 1  through  202 -N. 
       FIG. 5  depicts a flowchart for access point  201  for transmitting a sequence of one or more frames to station  202 - i , in accordance with the illustrative embodiment of the present invention. It will be clear to those skilled in the art which tasks depicted in  FIG. 5  can be performed simultaneously or in a different order than that depicted. 
     At task  510 , access point  201  checks whether the next frame to transmit to station  202 - i  is the last frame in the sequence. (As described above, a frame is the last frame in the sequence if either (i) access point  201 &#39;s downlink buffer for station  202 - i  is empty, or (ii) access point  201  has insufficient time to transmit at least one more frame in the buffer.) If the frame is the last frame in the sequence, execution proceeds to task  520 , otherwise execution continues at task  540 . 
     At task  520 , access point  201  transmits the frame to station  202 - i  with an indication that it is the last frame in the sequence (e.g., by setting a ‘More Data’ bit to  0 , by setting the EOSP in an 802.11 frame to 1, etc.) 
     At task  530 , access point  201  receives an acknowledgement from station  202 - i  via the shared-communications channel in well-known fashion. As indicated by dotted line  525  in  FIG. 5 , if station  202 - i  does not receive the acknowledgement (e.g., due to RF interference, etc.), then execution goes back to task  520  in accordance with the protocol of the prior art, in well-known fashion. As will be demonstrated in the description of  FIG. 6  below, the problem of repeated lost acknowledgements due to a power-saving station entering the doze state will not occur in the illustrative embodiment. After task  530 , execution proceeds to task  560 . 
     At task  540 , access point  201  transmits the frame to station  202 - i  via the shared-communications channel in normal fashion. The first time task  540  is executed, the first frame in the sequence is transmitted; the second time task  540  is executed, the second frame in the sequence is transmitted; etc. 
     At task  550 , access point  201  receives an acknowledgement from station  202 - i  via the shared-communications channel in well-known fashion. As indicated by dotted line  545 , if station  202 - i  does not receive the acknowledgement (e.g., due to RF interference, etc.), then execution goes back to task  540  in accordance with the protocol of the prior art, in well-known fashion. After task  550 , execution continues back at task  510 . 
     At task  560 , access point  201  checks whether station  202 - i  is the last polled station during a contention-free period (e.g., an IEEE 802.11 Controlled Access Period [CAP], etc.). If so, execution proceeds to task  570 , otherwise the method of  FIG. 5  terminates. 
     At task  570 , access point  201  transmits a double acknowledgement to station  202 - i  (i.e., a frame that acknowledges that station  202 - i &#39;s acknowledgement was received) via the shared-communications channel in well-known fashion. As will be appreciated by those skilled in the art, in some embodiments the double acknowledgement frame might have the same format as a regular acknowledgement of the particular protocol, while in some other embodiments the double acknowledgement frame might have some other format. 
     After task  570 , the method of  FIG. 5  terminates. 
       FIG. 6  depicts a flowchart for power-saving station  202 - i  for determining when to enter a reduced-power state, in accordance with the illustrative embodiment of the present invention. It will be clear to those skilled in the art which tasks depicted in  FIG. 6  can be performed simultaneously or in a different order than that depicted. 
     At task  610 , station  202 - i  receives the last frame in a sequence from access point  201  via the shared-communications channel. As described above, there are a variety of ways in which to indicate that a frame is the last in a sequence (e.g., by setting a ‘More Data’ bit to 0, by setting the EOSP in an 802.11 frame to 1, etc.). 
     At task  620 , station  202 - i  transmits an acknowledgement to access point  201  via the shared-communications channel in well-known fashion. 
     At task  630 , station  202 - i  stores the current time in variable t. 
     At task  640 , station  202 - i  listens to the shared-communications channel in well-known fashion. 
     At task  650 , station  202 - i  checks whether there is a frame on the shared-communications channel; if not, execution proceeds to task  660 , otherwise execution continues at task  670 . 
     At task  660 , station  202 - i  checks whether the difference between the current time and time t exceeds the Point Coordination Function InterFrame Spacing (PIFS) time interval. If so, which indicates that the shared-communications channel has been idle for more than the PIFS, and therefore that access point  201  has no more frames to transmit to station  202 - i , execution proceeds to task  695 , otherwise execution continues back at task  640 . 
     At task  670 , station  202 - i  checks whether the frame observed at task  650  is directed to a station other than station  202 - i ; if so, execution proceeds to task  695 , otherwise, execution proceeds to task  680 . 
     At task  680 , station  202 - i  checks whether the frame (which was directed to station  202 - i ) is a double acknowledgement (i.e., whether the frame acknowledges an acknowledgement that station  202 - i  transmitted at either task  620  above or task  690  below); if so, execution proceeds to task  695 , otherwise, execution proceeds to task  690 . 
     At task  690 , station  202 - i  transmits an acknowledgement to access point  201  that acknowledges the frame received at task  650  (which is a “regular” downlink frame, not a double acknowledgement). After task  690 , execution continues back at task  640 . 
     At task  695 , station  202 - i  enters a reduced-power state (i.e., processor  402  outputs a signal that causes receiver  401  and transmitter  404  to power off), in well-known fashion. 
     After task  695 , the method of  FIG. 6  terminates. 
     Although the illustrative embodiment of the present invention is disclosed in the context of IEEE 802.11 local-area networks, it will be clear to those skilled in the art after reading this specification how to make and use embodiments of the present invention for other kinds of networks and network protocols. 
     It is to be understood that the above-described embodiments are merely illustrative of the present invention and that many variations of the above-described embodiments can be devised by those skilled in the art without departing from the scope of the invention. It is therefore intended that such variations be included within the scope of the following claims and their equivalents.