Assignment 1 (due 9/18 1:30pm)

This assignment is intended to introduce you to TinyOS programming. You will implement a sensor network synchronicity protocol and test in the TOSSIM simulator.

Time synchronicity is a useful abstraction in sensor networks because it enables coordinated communications and scheduling. Synchronicity is not necessarily the same as time synchronization. The latter implies that there is some global clock in the network. On the other hand, synchronicity is defined as organizing simultaneous collective actions. An example is for nodes to fire their periodic timers at approximately the same time. The Reachback Firefly Algorithm (RFA) is a decentralized algorithm based on how fireflies and neurons spontaneously synchronize. The basic idea is for each mote to shift its period phase by shortening the length of the next period (or jumping in time). The jump's length is derived by observing neighbors' beacons broadcasted when their timer fires.

The assignment is divided into several steps.

Step 1: Install TinyOS2

You need to install TinyOS2 on a machine that you have access to. The course TinyOS page should help you getting TinyOS2 up and running.

Step 2: Read the official TinyOS2 tutorial

The official TinyOS2 tutorial is available here. You should at least read through lesson 1.1, 1.2, 1.3, and 1.11. These lessons introduce basic TinyOS concepts, radio communication, and the TOSSIM simulator.

Step 3: Get the mote to fire timers periodically

The first thing you need to do is to implement a timer. We provide the Makefile and a sample simulation script, which you can download here. Note that the Makefile looks for RadioSyncAppC component as the top-level wiring configuration file. The timer should be one-shot and fire once every TIME_PERIOD_INTERVAL seconds. In this assignment, we define TIME_PERIOD_INTERVAL to be 1 second, or 1024 milli-seconds. When the timer fires, the current mote local time is printed on the screen. You can use TOSSIM's dbg function call (with RadioSync as the output channel) to print to the screen, and get the current mote local time from Timer's getNow() command.

Note: The Blink application under TinyOS (apps/Blink) provides a very good starting point.

Step 4: Send and receive radio messages

Add code and update the timer event handler to broadcast a beacon message every time the timer fires. The beacon message carries an uint16_t field that records the sender's mote ID. You can obtain the mote ID with the defined TinyOS variable, TOS_NODE_ID.

Next, add a radio receive event handler so that you can process the neighbors' beacon messages. For debugging, you can print the mote ID included in the beacon message to the screen.

Step 5: Add logic to implement RFA

The RFA algorithm for calculating the jump, t_jump, is as follows. At the start of each time period, t_jump is initialized to 0. Upon receiving a neighbor's beacon message, the mote calculates the elapsed time since the beginning of the current period. Then, t' is calculated as the sum of this elapsed time and the accumulated jump time so far. Next, t_jump is incremented by t' / 100. Up to now, the timer is always scheduled to fire every PERIOD_INTERVAL seconds. With RFA, the mote should schedule the next timer to fire in PERIOD_INTERVAL - t_jump seconds.

You can test the implementation in a two-node topology and boot each node at different times. Unlike in step 3, you need to print the current simulation time to screen every time the timer fires. This is how you verify whether the network reaches synchronicity. The current simulation timestamp can be obtained with the following code: 

 (double) sim_time() / sim_ticks_per_sec()

An example simulation output that shows network synchronicity: 

 DEBUG (0): 1.000
 DEBUG (1): 1.300
 DEBUG (0): 2.000
 DEBUG (1): 2.293
 DEBUG (0): 2.997
 DEBUG (1): 3.286
 ...
 DEBUG (0): 99.921
 DEBUG (1): 99.922

Step 6: Deliverables

  1. The nesC code that you wrote, and the python scripts you used to obtain the following graphs.
  2. Two graphs that show the convergence time as the number of nodes, N, within the same radio range varies between 2, 3, 4, and 5. For the first graph, set the nodes' start time to be 0.2 seconds from each other. For the second graph, randomly pick a start time for each node. We define convergence time as the time that elapses after the last node starts until all nodes' timers fire in synchronicity. For the purpose of the assignment, the network reaches synchronicity if nodes timers fire within 0.1 seconds of each other.
  3. A graph that shows the convergence time as a function of the packet loss rate. TOSSIM infers packet loss rate from the signal attenuation factor of each link and the strength of node's background noise. The link attenuation factor is specified when you add links between nodes. For example, r.add(0, 1, link_attenuation_factor). The node background noise is specified when you try to add noise trace. For example, node1.addNoiseTraceReading(background_noise). The table below shows what combination of the link attenuation factor and background noise we want to use. What you will need to do is to first estimate the average loss rate for each of these cases. Then you should run the experiment multiple times to find the average convergence time for each of these loss rates.
Link attenuation factorNode background noise
-10-100
-50-80
-65-75
-69-75
-71-75

References