Assignment 2 (due Oct. 23 1:30pm)

Like computer networks in general, sensor networks divide radio communication into several layers, such as the Medium Access Control (MAC) layer. Unlike the network layer, the MAC layer tries to ensure that a node can efficiently transmit a packet to its one-hop neighbors. It also tries to minimize the interferences among different transmissions. However, because of the energy constraint in most sensor networks, many MAC layer also incorporates duty cycles and turn off the radio as much as possible.

In this assignment, we will look at two duty-cycle MAC protocols: X-MAC and Ri-MAC. You will implement both in TOSSIM and compare the performance under different metrics.

Protocols Description

We assume that all nodes maintain their own duty cycle schedule. Although both X-MAC and Ri-MAC are asynchronous MAC protocols, they differ in the way senders and receivers reach the rendezvous point before the data transfer. X-MAC is sender-initiated while Ri-MAC is receiver-initiated. The following sub-sections walk through the two protocols.

X-MAC

We use a simplified version of X-MAC for the assignment. When node S has a packets to send to node R, it repeatedly sends the packet (with a small 250 ms gap between attempts, for a maximum of one duty-cycle period). When R wakes up and turns ON the radio, it will receive the data packet from S and sends back an acknowledgement packet. Upon receiving the acknowledgement, S knows that its data packet has successfully reached R, and then it goes back to sleep if it has nothing else to send. R goes back to sleep if it does not hear any data packets destined to itself for the duration equal to the wake-up period.

If there is no sender, R will not hear any data packet destined to itself when it wakes up, and R will just goes back to sleep until the next polling interval.

Note that if the sender cannot delivery the packet within one duty-cycle period, it stops and signals FAIL to the user application.

Receiver-Initiated MAC (Ri-MAC)

When node R wakes up, it broadcasts a base beacon notifying neighbors that it is ready to receive data packets. The base beacon carries the maximum back-off value t_max. When node S receives the base beacon, it first picks a random back-off time, t, between 0 and t_max ms, and then it waits. After t ms has passed, S sends R the pending data packet. Upon receiving the data packet, R broadcasts an acknowledgment beacon with the data packet sequence number (in addition to the t_max). The included sequence number informs S the successful delivery, and S goes to sleep if it has no more pending data packets. Like the base beacon, the acknowledgment beacon carries new t_max to initiate new data transfer. We will talk about how to calculate t_max later. If R does not receive any incoming data packets before t_max expires, it goes back to sleep.

Collisions can happen in the case of multiple senders. For example, both S1 and S2 want to send packets to R, but they pick close back-off times. If R detects packet collision on the channel, it broadcasts a new beacon with a larger t_max after the previous t_max expires. By having a larger t_max for the next period, Ri-MAC intends to separate the packet transmission time from multiple senders.

Note that if the sender cannot delivery the packet within one duty-cycle period, it stops and signals FAIL to the user application.

We will use Binary Exponential Back-off (BEB) strategy to calculate t_max at the receiver. Specifically, (2^ i ) - 1 where i starts from 1 and increments by 1 every time the node detects a collision. Note that i is reset to 1 when the node goes back to sleep.

Skeleton code

You can download the skeleton code here. The skeleton code inserts a new component, called MacC, between Active Message (AM) layer and user application. Packets from the user application first reach MacC. Following the protocol description above, MacC uses different approaches to transmit the packet to the receiver. To simplify the implementation, we assume MacC can serve one packet at a time. MacC should return EBUSY if it is busy. MacC should also periodically (according to the duty cycle) turn ON the radio and see if there is any packets destined to the node.

Ri-Mac requires the node to detect if a collision has occurred on the radio channel. TOSSIM has been changed to notify RiMacP.nc when a such condition has occurred (refer to CollisionNotify interface in RiMacP.nc).

Deliverables

  1. All the nesC code and simulation scripts that you have written. If your implementation is not complete, you should also include a README that points out the missing parts.
  2. Create a linear 3-node topology, where nodes can only hear their immediate neighbors. The two end nodes are senders and the middle node is the receiver. Assume the duty-cycle period is 10 second with 10% duty cycle. Simulate each protocol for 10 minutes with the following packet-injection rates from the user application: 500 ms, 1 second, and 2 seconds. Graph the total number of packets sent in the network, the total number of packets received by the receiver, and the average packet latency.
  3. Create a 5-node full-mesh topology, where 4 nodes are senders and 1 node is the receiver. Repeat the tasks as mentioned in the previous deliverable.
  4. Create a linear 4-node topology, where nodes can only hear their immediate neighbors. One of the two end nodes is the sender while the other is the receiver. Have the sender randomly generate 20 packets over the course of 10 minutes. Then, show the data latency for each packet that successfully reaches to the receiver.
    Note that MAC layer is responsible for only one-hop communication. For the purpose of the assignment, you can have the following simple routing algorithm. Sequentially assign node ID to all four nodes with the sender being node 1. Whenever a node receives a packet, it forwards to node with an ID that is 1 larger than itself.

Reference

M. Buettner, G. Yee, E. Anderson, R. Han, "X-MAC: A Short Preamble MAC Protocol for Duty-Cycled Wireless Sensor Networks." Sensys 2006

Y. Sun, O. Gurewitz, and D. B. Johnson, "Ri-mac: A receiver initiated asynchronous duty cycle mac protocol for dynamic traffic load." Sensys 2008