CODA: Congestion Detection and Avoidance in Sensor Networks

Paper Synopsis

Presented By: David Sprague

February 9, 2004

Open Office Version (more likely to work correctly)

Sensor networks, although extremely varied in their functionality and designs, have greater energy conservation requirements than traditional networks. In such networks, data transmission congestion should not be handled in a traditional manner. Data packets need to be transmitted over the network, but retransmission due to congestion incurs a substantial energy cost on each sensor that should be avoided. Wan, Eisenman and Campbell further stressed the importance of energy conservation through congestion avoidance in small, infrequently transmitting, energy limited sensor networks that occasionally demonstrate “bursty” transmission rates.

CODA, the proposed congestion handling technique, uses an energy efficient heuristic for monitoring the localized network and avoids congestion though open-loop hop-by-hop backpressure and closed-loop regulation with upstream nodes. The initial receiver based congestion detection used by CODA is simple message queue monitoring. If the queue is empty or overflowing, congestion at the node is obvious. If there are messages in a sensor’s queue, however, channel loading is used to give accurate information about the surrounding networks activity rate. Whenever a node starts sensing the channel (there is something in is queue) the node listens for 1 epoch time to measure the channel, periodically sampling the network’s performance rather than continuously monitoring the channel. In this way, the network can be accurately monitored with a minimal amount of energy expensive channel loading. The second technique used in CODA is open-loop hop-by-hop backpressure regulation. This means that a sink detecting congestion or potential congestion, broadcasts a suppression message to all neighbors. Each node then handles this suppression message and the message may, depending on the network’s policy, propagate up to source nodes. Data packets may also be dropped due to this message, network policy permitting. The third aspect of the CODA system is closed-loop multi-source regulation. When a threshold level of network activity is detected, a sink S informs all neighboring source nodes that they must receive ACKs from S at a certain frequency or else they need to substantially reduce their sending rates. This enables sink oriented selective regulation of data transmissions. Due to the extra messaging incurred, closed-loop regulation is more energy intensive than open-loop regulation. However, this paper’s experimental results have demonstrated the necessity of this technique.

Wan et al. wished to demonstrate that CODA not only severely reduced energy consumption on their target network type, but also resulted in little to no data fidelity penalty. Two experimental metrics were examined: the average energy tax and the average fidelity penalty. The average energy tax was calculated as the total number of packets dropped in the network divided by the number of packets received at the sink. Average fidelity penalty was calculated as the difference between CODA and an ideal congestion scheme in the number of packets received by the sink. A series of network simulations with six sources and three sinks randomly distributed across a sensor field of 30 to 120 nodes was used to test CODA. Wan et al. examined three different test conditions: a densely deployed sensor field with impulse data events (test A), a sparsely deployed sensor network with transient hotspots (test B), and a high data rate sparsely deployed sensor field with both transient and persistent hotspots (test C). Test A showed that with a small (3± 11%) decrease in data fidelity, packet drop rates were reduced by an order of magnitude (88±2%). Test B demonstrated the effectiveness of closed-loop regulation in controlling congestion (with up to 500% energy savings) with a minimal energy overhead while open-loop regulation alone was not able to guarantee control over persistent congestion. The signaling overhead of CODA was less than 1% with respect to the number of packets delivered to the sink. Finally, test C showed that CODA’s open and closed loop regulations can obtain up to 1500% energy savings with a fidelity penalty under 40%. These experimental results suggest that CODA can provide potentially high-energy savings for sensor networks by alleviating and avoiding congestion with only a modest reduction in data fidelity.

Discussion Summary

How do the authors define optimal? If the optimal (control group) congestion scheme can be worse than CODA in some cases, how is it optimal?

The control group can not be the optimal congestion scheme since the control condition’s fidelity penalty values are between 1 and 0
It was assumed that the optimal scheme is one that had no energy or retransmission constraints, and negligible packet loss due to transmission.
It was not clearly stated whether the optimal scheme was based on a theory or the currently optimal scheme for any network.

By exclusively using simulation data, is CODA’s measured effectiveness valid? Shouldn’t it be tested on a real sensor network?

Buck: It is standard practice for researches to present their initial technique with only a modest experimental evaluation. Subsequent evaluations with real networks would then be used to generate further publications.

Lower layer protocols handle data retransmission and packet loss. What does CODA provide in terms of congestion control?

Since CODA is abstracted away from the loss packet detection and retransmission found in the standard TCP protocol, CODA does not provide as novel or all encompassing an approach as suggested in the paper
CODA’s congestion avoidance and data flow moderations should severely reduce or eliminate the actual data retransmission performed by TCP by reducing the possibility of a node’s message buffer overflowing.
“Real world” testing is required to evaluate the true effectiveness of CODA

By reducing data transmission rates, CODA may increase packet loss and congestion by preventing source nodes from emptying their queues. How does CODA actually alleviate congestion if this is the case?

CODA is not appropriate for all sensor networks and should not be used on constant high congestion networks.
One of the primary motivations for CODA’s development was small, energy limited sensor networks that infrequently transmit but potentially show “bursty” data transmissions.
CODA will just delay the inevitable (unless packet dropping is permitted) if the network constantly transmits at high data rates.

With such small sensor nodes, message queue space is limited but the paper ignores this fact. What about the energy cost of maintaining the message queue? Doesn’t it run out of space?

The paper assumes that the message queue will be relatively large provided that CODA is used. If not, congestion is detected much earlier in the network and data flow will be severely reduced (perhaps constantly)
The energy costs for data transmission are suggested/implied to be far greater than the energy cost of maintaining the message queue. This claim may not be valid (is one wasted packet transmission worth 4 extra items in a queue for 1 second? Five seconds?), but since only 1% of the network energy cost is caused by the CODA overhead, this claim may have some basis in reality.

References

The Armstrong Project (the people who developed CODA and directed diffusion)

http://comet.ctr.columbia.edu/armstrong/

Bandwidth Management in Wireless Sensor Networks (CODA in context. Poster Abstract):

http://www.cens.ucla.edu/sensys03/proceedings/ p306-hull.pdf

Colorado State University Lecture Notes (Where some of the slides came from)

http://www-net.cs.umass.edu/cs791_sensornets/Transport_protocol_slides_part2.ppt

MICS 2003 Scientific Conference (General Sensor Network Information)

http://www.terminodes.org/micsLinks.php