A method and apparatus for link adaptation for packet transmission

Technical Field

0001The invention relates to a method and apparatus for link adaptation for packet transmission. In particular, it relates to a method and apparatus for link adaptation for packet transmission for varying and high traffic loads.

Background

0002In the wireless local area network (WLAN) market, the dominant medium access control (MAC) technique is CSMA/CA (carrier sense multiple access with collision avoidance); a random access protocol implemented in current IEEE 802.11 a/b/g products.

0003In the context of 802.11, CSMA/CA access is referred to as the distributed coordination function (DCF). An enhanced version of DCF (called Enhanced Distributed Channel Access or EDCA) is described in IEEE 802.11e that improves the MAC by introducing access priorities. However this enhanced version still relies on CSMA/CA, and it is anticipated that CSMA/CA will remain the dominant MAC protocol for a number of years.

0004In addition to medium access control, 802.11 WLAN systems typically also implement link adaptation techniques, which aim to select the highest possible bit rate given the current link quality.

0005Link adaptation methods for packet transmission enable a transmitter to select the physical bit rate that will maximise the link throughput under some quality of service (QoS) constraints. In order to take this decision, the link adaptation must therefore estimate the transmitter to receiver link quality. This link quality can be monitored either through some explicit feedback sent by the receiver (e.g. acknowledgement (ACKs) of successfully received packets), or by some implicit feedback; for example, an access point (AP) can infer the downlink quality from measurements performed on the uplink data packets it receives from a mobile terminal (MT), without requiring some explicit signalling.

0006Most link adaptation strategies proposed in the literature (for example, Simoens, S. and Bartolome, D.; "Optimum performance of link adaptation in HIPERLAN/2 networks", IEEE 53rd Vehicular Technology Conference, 6-9 May 2001 Volume 2, pp 1129 -1133,) ultimately rely on a prediction of the packet error rate (PER) of the link, which is then used to maximize the throughput under some QoS constraints. A few others take into account additional parameters such as the transmit power.

0007The PER can be estimated either directly, by counting the packet errors (unacknowledged packets), or indirectly by measuring channel metrics (e.g. signal to noise plus interference ratio (SNIP), channel delay spread, etc.,) and then assuming that the PER is a function of these metrics (e.g. by using PER vs. SNR curves).

0008It would be useful if one could base link adaptation on channel dependent metrics such as SNIR or delay spread, because they are available instantly (it is not necessary to count several packet errors to get an estimate of the PER) and they are not altered by traffic load. However, it is not always possible to provide for explicit signalling of SNIP or Channel delay spread by the transmitter. For example, the IEEE802.11 standards do not provide for this.

0009As noted previously, one solution would be to use some implicit feedback, but such a solution is limited by the fact that the uplink and downlink are not symmetrical: the MT and AP transmit powers are different, the radio frequency parts involved are not the same, and the interference at the AP and at the MT can differ significantly.

0010It would appear that in fact the simplest solution in 802.11 is to perform a link adaptation based on acknowledgements (ACKs). In 802.11, an ACK is sent after each successfully decoded packet, and so the PER can theoretically be estimated from the ratio of unacknowledged packets to the total number of sent packets.

0011Several methods exploiting ACKs have been proposed. Some methods consist of comparing the estimated PER to a threshold. If the PER is above the threshold then a lower bit rate (more robust) mode is selected for the next transmission. If the PER is below a given threshold, then a higher bit rate (less robust) is selected. In A.J. van der Vegt, "Auto Rate Fallback Algorithm for the IEEE 802.11a Standard", available at http://www.phys.uu.nl/∼vdvegt/docs/gron/, the authors use a variant of ACK-based link adaptation by counting the number of successive ACKs, and the number of successive missed ACKs.

0012However, a problem with ACK based link adaptation is that poor link quality is not the only possible cause of missed ACKs, resulting in a biased estimate of the link quality that overestimates the contribution of link quality to missed ACKs, and consequently a reduction in the effectiveness of the link adaptation. The purpose of the present invention is to address the above problem.

Summary of the Invention

0013The present invention provides a method of reducing packet error rate estimation bias in link adaptation for packet transmission, characterised by the step of estimating a probability of packet collision.

0014In a first aspect, the present invention provides a method of link adaptation, as claimed in claim 1.

0015In a second aspect, the present invention provides an apparatus for link adaptation, as claimed in claim 9.

0016Further features of the present invention are as defined in the dependent claims.

0017Embodiments of the present invention will now be described by way of example with reference to the accompanying drawings, in which:

Brief description of the drawings

0018<ul id="ul0001" list-style="none"><li>FIG. 1 is a graph showing data throughput on the y-axis versus traffic load on the x-axis for several link adaptation methods in the prior art.</li><li>FIG. 2 is a block diagram illustrating the operation of a distributed coordination function.</li><li>FIG. 3 is a graph showing data throughput on the y-axis versus traffic load on the x-axis for several link adaptation methods in the prior art and an embodiment of the present invention.</li></ul>

Detailed description

0019A method of link adaptation is disclosed. In the following description, a number of specific details are presented in order to provide a thorough understanding of the present invention. It will be obvious, however, to a person skilled in the art that these specific details need not be employed to practice the present invention. In other instances, well known methods, procedures and components have not been described in detail in order to avoid unnecessarily obscuring the present invention.

0020In fact, when implementing link adaptation methods, a major problem with carrier sense multiple access with collision avoidance (CSMA/CA) is that packet collisions frequently occur as cell load increases. These collisions can affect a link adaptation method, leading to a significant decrease in throughput.

0021This phenomenon appears particularly in the case of link adaptation methods in a mixed traffic environment (voice over internet protocol (VoIP) and file transfers). The problem thus identified is to find a means to make the link adaptation method substantially compensate for packet collisions due to traffic load, and so maintain a level of performance.

0022This problem manifests itself in contention-based methods such as the ACK based methods discussed previously, since in random access networks a missed ACK can come from either thermal noise (e.g. link quality) or packet collision. Therefore, when the traffic load (cell load) increases and packet collisions become frequent, the measured PER also increases and ACK-based link adaptation methods typically fall back to a lower bit rate.

0023This is clearly an undesirable response. Falling back to a lower bit rate increases the medium occupancy, which makes the transmission more robust to noise whilst in fact the packet collisions are the real problem. However, the result of increase medium occupancy is typically to increase packet collisions, so exacerbating the original problem. The overall result is a drop in throughput due to a rapid reduction in bit rate, as seen in FIG. 1:

0024In the graph of FIG. 1, the number of large file transfers occurring simultaneously in an IEEE802.11a cell is increased along the x-axis from 1 to 7. With an SNR based link adaptation ('+' curve), the average cell throughput on the y-axis decreases slowly from 24 Mbit/s to 16 Mbit/s as the load increases. But with a basic ACK-based algorithm exhibiting the problems discussed above ('•' curve, based on average PER estimation and threshold comparison), the throughput drops very quickly.

0025Packet collisions occur due to the nature of the 802.11 CSMA/CA access, referred to as the distributed coordination function (DCF).

Referring to FIG. 2, DCF operates as follows:

0026A station B 130 waiting to transmit must first contend to get access to the medium. This consists of generating a random number between 0 and its contention window (CW). This number is called the back-off counter 150. Then station B 130 senses the channel. If the channel is free for a longer time than the distributed inter frame space (DIPS) 140, it starts decreasing the back-off counter 150 every time slot. The decrease of the back-off counter 150 can be interrupted by a transmission by another station A 110, which can be followed by a short inter frame space (SIFS) 170 and an acknowledgement 180 if the packet 160 was successfully decoded (for clarity features 160, 170 and 180 are shown magnified in FIG. 2). The SIFS 170 is shorter than the DIFS 140, so that the other stations will let the acknowledgement 180 be transmitted without contention. After the acknowledgement 180, if the channel remains free longer than a DIFS 140, the station B resumes the decrease of the back-off counter 150. Finally, when the latter reaches zero, station B 130 transmits. If the back-off counter 150 of two stations reach zero at the same time, however, the resulting collision can corrupt both packets.

0027In an embodiment of the present invention, in operation a station waiting to transmit will implement a method to estimate the probability that another device starts transmitting in the same time slot, i.e. a probability of packet collision.

0028By estimating a probability of packet collision, a substantially unbiased estimate of PER can be produced by factoring for that proportion of failed packets that are due to packet collision rather than other aspects of link quality.

0029The probability of packet collision can be estimated by calculating substantially the following equation part;<maths id="math0001" num="Eq. 1"><math display="block"><mrow><msub><mrow><mover accent="true"><mrow><mtext mathvariant="italic">P</mtext></mrow><mo>ˆ</mo></mover></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">Busy</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">Total</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP1513281A1_D0001.tif" /></maths> where N_Busy is the number of transmission slots in an observation period that are occupied, and N_Total is the total number of slots in the observation period.

0030The observation period varies depending upon the application and channel load. Typical durations observed in simulations are one second for data transmissions, and 5 seconds for VoIP. The method envisages that over this observation period an ongoing refinement of <i>P̂</i>_<i>C</i> may take place. Subsequent additional observations are also envisaged, in particular if traffic loads vary considerably.

0031In an embodiment of the present invention, observation is substantially continuous. In such a case the observation period used in Eq. 1 will be a recent period.

0032Transmission slots are defined in Bianchi, G., "Performance analysis of the IEEE 802.11 distributed coordination function", IEEE Journal on Selected Areas in Communications, Volume 18 No. 3, March 2000 pp 535-547, as any one of the following; <ul id="ul0002" list-style="none" compact="compact"><li>i. an empty slot;</li><li>ii. a successful transmission (i.e. a packet, followed by a short inter-frame space (IFS), an acknowledgement (ACK) and a distributed IFS; and</li><li>iii. a failed transmission (i.e. a packet followed by a point coordination function IFS).</li></ul>

0033In an alternative embodiment of the present invention, an estimation of packet collision probability comprises calculating the average number of empty slots between the end of a distributed inter-frame space and the start of a transmission, during an observation period. The probability is then substantially the inverse of that average.

0034In a first alternative embodiment of the present invention, the average is calculated using the existing back-off counter 150. However, this assumes that the back-off counter is in use often enough to produce a sufficiently accurate average within the observation period.

0035In a second alternative embodiment of the present invention, the average is calculated using a dedicated counter.

0036In calculating the packet error rate, current ACK-based link adaptation methods assume that the observed probability of packet failure corresponds to the packet error rate (PER) due to line quality, that is:<maths id="math0002" num="Eq. 2"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">fail</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">PER</mtext></mrow></math><img file="EP1513281A1_D0002.tif" /></maths> whereas in actuality the relationship is<maths id="math0003" num="Eq. 3"><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">fail</mtext></mrow></msub><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></msub><mtext> + (1 - </mtext><msub><mrow><mtext mathvariant="italic">P</mtext></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></msub><mtext>)</mtext><mtext mathvariant="italic">PER</mtext></mrow></math><img file="EP1513281A1_D0003.tif" /></maths> Comparing Eq. 2 and Eq. 3 shows that when packet collisions occur, Eq. 2 overestimates the PER. As noted previously, this estimation bias reduces the effectiveness of current ACK based methods due to unnecessary reductions in bit rate.

0037In an embodiment of the present invention, a substantially unbiased PER is estimated by calculating substantially the following equation part;<maths id="math0004" num="Eq. 4"><math display="block"><mrow><mtext mathvariant="italic">PÊR</mtext><mtext> = </mtext><mfrac><mrow><msub><mrow><mover accent="true"><mrow><mtext mathvariant="italic">P</mtext></mrow><mo>ˆ</mo></mover></mrow><mrow><mtext mathvariant="italic">fail</mtext></mrow></msub><mtext> - </mtext><msub><mrow><mover accent="true"><mrow><mtext mathvariant="italic">P</mtext></mrow><mo>ˆ</mo></mover></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></msub></mrow><mrow><mtext>1 - </mtext><msub><mrow><mover accent="true"><mrow><mtext mathvariant="italic">P</mtext></mrow><mo>ˆ</mo></mover></mrow><mrow><mtext mathvariant="italic">C</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP1513281A1_D0004.tif" /></maths> where <i>P̂</i>_<i>fail</i> is the packet failure rate in an observation period, <i>P̂</i>_<i>C</i> is the estimate of packet collision probability and <i>PÊR</i> is the resulting estimate.

0038In an embodiment of the present invention, a simple method of using the <i>PÊR</i> in a link adaptation method is as an input to the regulation of the bit transmission rate, by <ul id="ul0003" list-style="none" compact="compact"><li>i. including a factor to the link adaptation calculation intended to lower the bit transmission rate if <i>PÊR > X</i>; and</li><li>ii. including a factor to the link adaptation calculation intended to raise the bit transmission rate if <i>PÊR</i> < <i>Y</i>,</li></ul> where X and Y are threshold values.

0039It will be clear to a person skilled in the art that <i>PÊR</i> can be used as an input to the regulation of the bit transmission rate in conjunction with other factors, such as any alternative link quality estimate, or quality of service constraints, in the regulation of a link adaptation method.

0040It will also be clear to a person skilled in the art that embodiments of the present invention can also be applied to other link adaptation methods that combine <i>P̂</i>_<i>C</i> with other metrics than <i>P̂</i>_<i>fail</i>. For example, the number of successive failures can be used instead of the failure probability in generating <i>PÊR</i>.

0041The performance improvement brought by an embodiment of the present invention is illustrated by the '*' curve of FIG. 3. Here, with the unbiased PER estimator <i>PÊR</i> of Eq. 4 used in the simulation, now up to 4 users can simultaneously download large files without the cell throughput collapsing.

0042Apparatus operable to perform link adaptation is also provided, comprising estimation means for estimating a probability of packet collision as described herein.

0043In an embodiment of the present invention, a mobile terminal comprises the apparatus.

0044In another embodiment of the present invention, a WLAN access point comprises the apparatus.