Ramana Rao Kompella and Alex C. Snoeren ,
" Practical Lazy Scheduling in Sensor Networks",
First ACM Conference on Embedded Networked Sensor Systems (Sensys)
November 2003.

Presentation: PowerPoint, PDF

Summary:

This paper presents L-CSMA/CA, a scheduling mechanism that aims to minimize radio power consumption in wireless communication. It is proposed as an extension to CSMA/CA. In particular this is targeted at sensor networks, where energy is a precious resource. The method takes advantage of Shannon's law, which states that the energy required for transmission of a fixed amount of information is convex with respect to the transmission rate. Commodity radios generally only support a small set of discrete transmission rates. The authors modify an optimal offline scheduling algorithm by Uysal-Biyikoglu et al. (1994) to support discrete transmission rates, make the algorithm online and allow for multiple senders. These features are added incrementally.

The discrete algorithm rounds the optimal transmission rate to one that is supported by the radio. Rounding the transmission rate up consumes more power, whereas rounding down gives significant additional delays. A tradeoff is made between power consumption and delay.

The online version of the algorithm uses delay look-ahead. The algorithm works in two phases, a look-ahead phase, where incoming packets are buffered, and a scheduling phase, which transmits the buffered packets at an optimal rate to minimize power consumption. The two phases are pipelined, so during the scheduling phase, new packets that arrive are being buffered. A time-horizon parameter D is introduced, which is the duration of the look-ahead phase. Larger D gives power consumption closer to the optimal offline algorithm, but introduces larger delays.

For the distributed algorithm, several assumptions are made:

• all nodes are not malicious
• shared broadcast medium
• nodes are synchronizable up to millisecond precision
• nodes can determine sender and duration of any transmitted packet

Class discussion:

• Kevin pointed out that sending ACKs (in CSMA/CA) will lead to extra traffic and most protocols designed for sensor networks avoid them. Thus, implementing the algorithm on top of CSMA/CA may not be optimal and other methods that do not require ACKs would possibly be better.
• Buck noted that there is often a tradeoff involving delay, e.g. in his work (streaming media) as well as in this algorithm. Here the tradeoff is between delay and power consumption.

Relevant Links