Method and apparatus incorporating adaptive datalink framing for message communication

[0001] The present invention relates generally to communication systems and more particularly to data framing for message communication.

[0002] Digital communications conducted over wireless communication channels are generally subjected to environmental factors that can adversely impact throughput, required energy, or effective range. Bit error rate is often used to characterize channel conditions. Under poor channel conditions, there is usually a high bit error rate for data communications, while under good channel conditions, the bit error rate for such communications is lower. Consequently, there are many techniques that utilize bit error rate determinations for monitoring throughput and related channel parameters when operating communication systems.

[0003] The Open Systems Interconnection (OSI) reference model defines various layers of abstraction for structuring communications. These layers include, among others, the Media Access Control (MAC) layer. In a typical protocol for implementing the MAC layer, data is segmented into packets and the packets transmitted in frames having a particular length. The performance of a MAC layer protocol under given channel conditions can be characterized by transmission delay, defined as the average time spent by a packet while awaiting transmission, and throughput, defined as the fraction of the channel capacity used for data transmissions. Recently, there has been some attention given to the development of techniques to adapt frame length to reflect channel conditions, in an effort to improve performance at the MAC layer. One approach is discussed in a paper entitled ADAPTIVE FRAME LENGTH CONTROL FOR IMPROVING WIRELSS LINK THROUGHPUT, RANGE, AND ENERGY EFFICIENCY, published by Lettieri et al., in the 1998 Institute of Electrical and Electronics Engineers (IEEE) proceedings. Here, the author concluded that performance in wireless networks could improve by manipulating the frame size used to transmit data packets at the MAC layer. In this approach, an approximation of bit error rate on a communication channel is obtained by examining packet error rate, and this approximation is used to select one of “three or four distinct levels of fragmentation over orders of magnitude of bit error rate.” However, this reference uses an empirical approach to determine preferred frame size that is not adequately for many applications.

[0004] While it is recognized that adaptive frame sizing could lead to improvements in network performance, particularly for problems related to congestion due to heavy traffic or densely-deployed network, there exists a need for a practical approach for realizing these benefits.

[0013] Generally, the present invention provides for adaptive datalink frame sizing according to channel conditions in order to optimize data throughput and/or energy consumption. A communication device, according to the invention, operates in a training mode to develop parameters based on estimates related to at least two different instances of channel conditions, such as indicated by bit error rates for channel transmissions. The parameters are used to define a function that characterizes the optimize throughput or energy consumption per bit through varying channel conditions. The function is preferably of the form a0+a1*Log(1+Lp), where a0 and a1 are the fitted parameters, and Lp the frame size. In regular operation, the device responds to changes in channel conditions by transmitting messages on the communication channel using a frame size adapted for channel conditions based on the particular function and the developed parameters.

[0014] FIG. 1 shows a portion of a representative communication network 100, in accordance with the present invention. The communication network 100 of the preferred embodiment is an ad-hoc network having nodes 110–119 distributed over a geographically dispersed area. The nodes preferably implement a sensor network or other data collection network but are not limited to such function. As shown, the nodes of the network have self-organized, and exhibit network redundancy in their communication links. The nodes communicate with one another through single hop or multi-hop communication links using a protocol stack that includes support for at least a portion of the Open Systems Interconnection (OSI) reference model; namely, the media access control (MAC) layer and the physical (PHY) layer. Each node 110–119 has memory, computing, and radio frequency (RF) processing capabilities to establish and operate the communication links in a network efficient and energy efficient manner. Accordingly, each node supports the adaptive frame length methodology of the present invention.

[0015] FIG. 2 shows an example of block communications between two of the devices 111, 112. Messages are processed using upper layers 212 of the protocol stack, segmented for transmission using the adaptive frame length MAC layer, and transmitted as a data packet 206 on a communication channel 205 using the PHY layer 216. Similarly messages are retrieved from the communication channel via the PHY layer 226, de-fragmented at the MAC layer 224 and sent to upper layers 222 for further processing.

[0016] FIG. 3 shows a block diagram of a communication device 300 operable as a node in the network of FIG. 1. In the device, a processor 325 governs the overall device function such as data receipt, transmission, and processing. A receiver 315 coupled to the processor 325 receives incoming messages from a communication channel via an antenna 305 and provides these messages to the processor 325. A transmitter 320, coupled to the processor 325, provides the capability of transmitting on the communication channel data pertaining to device function or other communication requirements as needed. A bit error rate (BER) estimator 370 provides an estimate of the average rate of bit-error for digital communication on the communication channel. In one embodiment, the BER estimator 370 compares equal length frames of two separate bit streams received over a particular time interval and compares raw data with uncorrected data. The BER estimator 370 calculates the number of bit errors by counting the number of bits that differ between the received channel bits and the error corrected estimate of the transmitted channel bits. Error estimates can also be derived from test sequences, from measuring signal parameters, and from techniques using violation detection. The device also includes a throughput payload estimator 380 for estimating the actual throughput for transmissions on the communication channel. Actual throughput can be estimated from current traffic based on the Aloha or other types of random access channel model as is known in the art. The BER and throughput payload estimators 370, 380 can be implemented as part of the decoder design.

[0017] A memory module 350 stores operating instructions and data for the device. Specifically, the memory 350 includes operating instructions 351, 352 for extracting throughput and energy consumption parameters pertaining to the communication, and instructions 353, 354 for selecting frame size for optimum throughput and/or energy consumption for message transmission. The procedures and steps implemented by the various operating instructions 351, 352, 353, 354 of the node in order to optimize packet size/frame length are described below.

[0018] The present invention exploits a relationship existing between throughput and datalink frame size for given bit error rate. In conjunction with the OSI model, the general form of data throughput T_p normalized to the raw bit rate of the channel for data link layer can be expressed as a function of bit error rate:

[0019] $\begin{array}{cc}{T}_p=\frac{L_p}{L_p+L_{\mathrm{mac}}+L_{\mathrm{phy}}}{\left(1-\mathrm{BER}\right)}^{\left(L_p+L_{\mathrm{mac}}\right)},& \left[1\right]\end{array}$
where L_p is the length of the data link payload in bytes, L_mac the length of the MAC header, L_phy the total overhead of the PHY layer including any preamble, post-amble, and inter-frame spacing specified by the attendant protocol. For example, for the commonly used IEEE 802.11 protocol specification, the values for L_mac and L_phy are 52.5 bytes and 40 bytes respectively. FIG. 4 shows a graph 400 of plots of throughput T_p versus payload packet size L_p for a variety of bit error rates for a given communication channel, in accordance with the present invention. Plots 410 are shown for various bit error rates including bit error rates ranging from 10⁻² through 10⁻⁶. According to the present invention, the graph includes a plot 425 of a non-linear function that is used to approximate the maximum throughput T_max for the various bit error rates that span the operating boundary conditions of the communication channel. Preferably, the function has the form:
T_max=a0+a1●Log(1+L_p)  [2]

[0020] where a0 and a1 are parameters derived using the throughput Tp at boundary conditions corresponding to the maximum and minimum expected bit error rate when operating on the channel. Ordinarily, the maximum bit error rate occurs when the channel conditions are at their worst, and the minimum bit error rate corresponds to the best channel conditions.

[0021] The present invention also contemplates the selection of data link frame size to optimize energy consumption, i.e., minimizing the energy per bit used to successfully convey a message through the communication channel. The energy per bit E_b can be expressed for various modulation techniques using well-known relationships. For example, with respect to Quadrature Phase Shift Keying (QPSK), the relationship between bit error rate (BER) and E_b can be expressed as:

[0022] $\begin{array}{cc}\mathrm{BER}=\frac{1}{4}\mathrm{erfc}\left(\sqrt{\frac{E_b}{N_0}}\right),& \left[3\right]\end{array}$

[0023] where erfc is the Error function, and N₀ the spectral noise density. By combining this BER equation with the throughput Tp equation previously discussed, a family of curves can be plotted that represent the normalized transmission energy per bit versus the length of the data link payload in bytes for a variety of values of data throughput. FIG. 5 is a graph showing plots 510 of the normalized energy per bit versus payload packet size L_p for various normalized throughput values. According to the present invention, the graph includes a plot 525 of a non-linear function that is used to approximate the minimum energy per bit E_min for various throughput values that span the operating boundary conditions of the communication channel. Preferably, the function has the form:
E_min=b0+b1●Log(1+L_p)  [4]
where b0 and b1 are parameters derived using the normalized energy per bit at boundary conditions corresponding to the maximum and minimum expected bit error rate when operating on the channel.

[0024] Significantly, functions have been shown that provide for the optimum throughput in high BER conditions, and that provide for minimal energy consumption in low throughput conditions. These functions have a common form of expression with a single adjustable variable/adaptive data link frame length.

[0025] FIG. 6 shows a flowchart of procedures 600 for transmitting a message on a communication channel while using an adaptive frame length to optimize throughput, in accordance with the present invention. A communication device determines boundary conditions for the communication channel by obtaining estimates related to at least two different bit error rates for transmissions on the communication channel, step 610. As indicated earlier, the optimum throughput T_max for a given channel environment is related to the data link length L_p according to the function [2] described above. Accordingly, after two rounds of BER estimations, both parameters a0 and a1 are determined, step 620. In order to better characterize the channel, the BER estimates are preferably obtained at the boundary conditions for the communication channel, i.e., conditions corresponding to the maximum bit error rate and minimum bit error rate. In this manner, the parameters a0 and a1 will lead to a function more representative of the range of likely or expected channel conditions. With knowledge of the BER estimates, the data frame length L_p and frame head parameters such as L_mac and L_phy, two different throughputs T_p can be calculated using equation [1], and two instances of equation [2] can be solved simultaneously to obtain the unknown parameters. Preferably, the communication device determines a first throughput, T1, under maximum bit error rate conditions, and a second throughput, T2, under minimum bit error rate conditions. The unknown parameters a0 and a1 can then be determined by solving the equations:
T1=a0+a1*Log(1+L_p);
T2=a0+a1*Log(1+L_p).

[0026] The parameters so obtained provide for a function that approximates maximum throughput for a variety of bit error rates that span the boundary conditions of the communication channel.

[0027] The communication obtains a message for transmission, step 630, and upon so doing, determines current channel conditions as characterized by a bit error rate estimate for the channel conditions, step 640. The bit error rate estimate is used to determine current throughput T_c for the channel, and equation [2] used to determine the appropriate frame size. In one embodiment, the frame size is determined through an iterative process. A frame size is chosen and a portion of the message transmitted using the selected frame size, steps 650, 655. The actual throughput for the portion of the message is obtained, step 660, and compared with the optimum throughput for that frame size as determined by equation [2] using parameters a0, a1, step 670. When the actual throughput is inconsistent with the optimum throughput, the frame size is adjusted and the process repeated until the optimum throughput is obtained, step 680.

[0028] FIG. 7 is a flowchart of procedures used by a communication device for transmitting a message on a communication channel while using an adaptive frame length to optimize energy consumption per bit, in accordance with the present invention. The communication device characterizes the communication channel by obtaining estimates related to at least two different bit error rates for transmissions on the communication channel, step 710. The two different bit error rates preferably correspond to the boundary conditions for the communication channel, i.e., corresponding to the maximum and minimum error rates. As indicated earlier, the optimized energy consumption per bit E_min for a given channel environment is related to the data link length L_p according to the function [4] described above. Accordingly, after two rounds of BER estimations, both parameters b0 and b1 are determined, step 720. With knowledge of the BER estimates, two different values for the energy per bit can be calculated using equation [3], and two instances of equation [2] can be solved simultaneously to obtain the unknown parameters. Preferably, the communication device determines a first energy per bit value, E1, under maximum bit error rate conditions, and a second energy per bit value, E2, under minimum bit error rate conditions. The unknown parameters b0 and b1 can then be determined by solving the equations:
E1=b0+b1*Log(1+L_p),
E2=b0+b1*Log(1+L_p),

[0029] The parameters so obtained provide for a function that approximates minimum transmission energy per bit for a variety of throughputs that span the boundary conditions of the communication channel.

[0030] The communication obtains a message for transmission, step 730, and upon so doing, determines current channel conditions as characterized by a throughput estimate for the channel conditions, step 740. The throughput estimate, which is related to the bit error rate, is used to determine energy per bit for transmissions on channel, and equation [4] used to determine the appropriate frame size. In one embodiment, the frame size is determined through an iterative process. A frame size is chosen and a portion of the message transmitted using the selected frame size, steps 750, 755. The actual energy per bit for the transmitted portion of the message is obtained, step 760, and compared with the optimum energy per bit for that frame size as determined by equation [4] using parameters b0, b1, step 770. When the actual energy per bit is inconsistent with the optimum energy per bit, the frame size is adjusted and the process repeated until the optimum energy per bit is obtained, step 780.

[0031] The present invention provides for significant benefits over the prior art. By developing a function that characterizes a communication channel, a device can use information on bit error rate estimates to increase throughput or reduce energy consumption in response to channel conditions. This approach is particularly useful for handling channel problems caused by low level or bursty interference, by fading, or by congestion due to densely-deployed nodes. Since bit error rate estimation/detection is generally available in digital communication systems for error correction purposes, these underlying components can form the basis for implementing the adaptive data link framing techniques described herein.

[0032] While the above description is of the preferred embodiment of the present invention, it should be appreciated that the invention may be modified, altered, or varied without deviating from the scope and fair meaning of the following claims.