UIUC RTSL: RT-Chain

Home

RT-Chain Home

Sections:

-NS-2

Equipment

Multimedia

Download

Real Time Ad-Hoc Wireless Communication Based on RT-Chains

In this work, we investigated how to provide real-time support for Wireless Multimedia Sensor Networks (WMSNs) and more in general for wireless ad-hoc networks whose messages are time sensitive. In particular, we assumed a deployment where the network structure is not regular, and nodes do not keep synchronized clocks. Network communication includes both best-effort traffic and soft real-time flows that can be opened on demand. Each real-time flow is characterized by a priority, which is determined by its urgency, and real-time packets as a group are given precedence over best effort traffic. Our goal is to develop a multi-hop prioritized MAC protocol that can provide soft bandwidth guarantees for all flows while at the same time allowing high throughput throughout the network. Our design of Real-Time Chains achieves this goal solving two main problems: 1) packet collisions on wireless channel; 2) priority inversions when accessing wireless medium.

Prioritized Packet Transmission

In Real-Time Chains, packets belonging to flows with different priorities are prioritezed based on the Black Burst (BB) scheme [Sobr99]. In the figure below, assume that both nodes N1, N2 must send a packet at the same time, but they are within interference range of each other. Using the BB approach, the senders synchronize on transition from busy to idle channel. Each sender then transmits a jamming signal (the Black Burst) with length proportional to its packet priority. The sender with the longest BB wins the contention and transmits the packet; afterwards all other senders contend again with a BB transmission until each of them eventually wins and transmits its packet. It can be shown that transmissions using different priorities are collision-free in the absence of hidden nodes; extensive experimental evaluations on MICAz hardware revealed that by setting appropriate transmission parameters it is possible to avoid the hidden node problem in most cases.

RT-Chains operation

RT-Chains uses a set of channels reserved for real-time traffic: [1,..,C] (in our implementation, C=5). All best effort traffic shares channel 0; hence, best effort traffic cannot interfere with real-time traffic. Initially, all nodes listen on channel 0 and serve best effort traffic. Whenever a new real-time flow must be opened, a chain opening request is transmitted on channel 0 using the BB scheme: it has higher priority over best effort traffic (CSMA/CA of 802.15.4) and it uses geographic forwarding as routing protocol. Nodes reached by the chain opening request switch to the reserved channels and start serving the chain exclusively until it is closed. Nodes belonging to a chain are organized in cells operating on different channels; this allows good spatial reuse of the wireless medium since interference among nodes is minimized. To communicate between cells, nodes perform channel hopping. The figure below shows the packet transmission schedule for two consecutive cells.

Each node holds a one-packet buffer. Whenever the buffer is empty, the node listens on its reception channel and immediately acknowledges any packet sent to it. If the id of the received packet is greater than the counter, its value is updated and the packet is copied in the buffer. Upon copying a packet in the buffer, the node switches to its transmission channel and uses the BB contention scheme to transmit the packet. While the buffer is full, the node does not acknowledge any packet sent to it. If the node receives an ACK after winning a BB contention and sending the packet, it removes it from the buffer and switches back to listening. Otherwise, it contends again on the transmission channel until it correctly receives an ACK.

Soft Real-Time Guarantees

If the priority and route of each existing flow is known, it is possible to compute soft real-time guarantees on throughput for each flow by building a set of linear constraints where the variables are the expected throughputs, and solve the system maximizing each flow throughput starting from the highest priority one. In detail:

- For each active flow (where r is the required bandwidth for the flow):

- For each set of flows belonging to an interference point I (where two or more flows cross):

Experimental Results

We fully implemented RT-Chains using MICAz motes. These motes employ a CC2420 transceiver with a maximum raw bandwidth of 250kbps. The transceiver supports the IEEE 802.15.4 standard (ZigBee) which is used to transmit best-effort traffic on channel 0. We deployed a network of 20 motes on a grass field and recorded throughput for both a single and double chain configuration. In the experiment, CSMA represents the performance obtained using 802.15.4 instead of Black Burst in the single chain. As shown by the graph, the obtained experimental results match closely with the expected theoretical guarantees. In particular, note that under heavy load the high priority flow obtains 2/3 of the bandwidth, while the low priority flow obtains the remaining bandwidth. RT-Chains has been used in the ALEIS project to carry both audio and critical healthcare information.

Bandwidth for a single chain

Bandwidth for two crossing chains

References

[Bui07]
B. D. Bui and R. Pellizzoni and M. Caccamo and C. F. Cheah and A. Tzakis. Soft Real-Time Chains for Multi-Hop Wireless Ad-Hoc Networks. Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), 2007.

[Sobr99]
J. L. Sobrinho and A. S. Krishna kumar. Quality-of-Service in ad hoc carrier sense multiple access networks. IEEE Journal on Selected Areas in Communications, 17(8):1353–1368, August 1999.

People

   Principal Investigator:
     Marco Caccamo (website, email)
   Students:
     Bach D. Bui
     Rodolfo Pellizzoni
     Chin F. Cheah
     Andrew Tzakis

Funding

This research was supported by the National Science Foundation through grants CCF-0325716, CNS-0509268, CNS-0613665 and CCR-0237884.