CS 213: Advanced Topics in

Distributed Embedded Systems

Assignment 2: Getting Started with TinyOS

Due Date: January 26th, 11:59pm PST

The purpose of this assignments is to get you familiarized with programming in TinyOS, the operating system for the Mote platform developed at U.C.Berkeley. Many of the steps involved in this assignment will be familiar to you from last weeks Em* assignment. However, the assignment that you are given here and the questions that are posed will differ slightly to give you a more diverse programming experience. As with the previous assignment, this one will require some setup, some implementation, and some testing to complete it.

TinyOS can be installed on both Windows(under cygwin) and Linux platforms and the assignment can be done on your home machine if you prefer. Detailed installation instructions are available at the TinyOS webpage. However, since our laboratory at UCLA is primarily Linux-oriented, you are unlikely to get assistance if you have problems with the Windows installation. You will be required to use only the simulator, Tossim/Nido, therefore, you need not install tools such as 'uisp' for the class assignments.

As with the first assignment, you can also work on the simulation machines (tobiko and dragon) that you used for the Em* assignment.

NOTE: If you are using the class machines for simulations, be warned that there may be contention for their use as the deadine approaches. So START EARLY!!

Part I: Setup

Step 1:

Log in to tobiko or dragon, and download the source code via anonymous CVS from the Sourceforge TinyOS Project page (see this page for a detailed explanation).

cvs -d:pserver:anonymous@cvs.sourceforge.net:/cvsroot/tinyos login
When prompted for a password for anonymous, simply press the Enter key.
cvs -z3 -d:pserver:anonymous@cvs.sourceforge.net:/cvsroot/tinyos co tinyos-1.x

Then, download the additional files to the tinyos-1.x/ directory, and untar them:

wget http://www.cens.ucla.edu/213/213-ps2.tgz
tar -xzvf 213-ps2.tgz

This should create two directories, 'apps/cs213-W04-Sample/' and 'apps/cs213-W04/' and install a bunch of files in each.

Once you have the files downloaded, build the system. Set the TOSDIR environment variable to the tos directory within tinyos-1.x as shown below. This "export" line is required each time you log in before building (you can add it to your .bashrc file if you prefer).

export TOSDIR=/home/your_username/tinyos-1.x/tos

At this point, you can test a small program to see if your installation has been succesfull.

cd apps/Blink
make pc

The 'make pc' should complete with no errors. All executables, object files, and libraries are stored in an architecture-specific directory: build/pc within the Blink directory.

./build/pc/main.exe --help

should give you a list of options while running the program in the simulator.
First, try running something.

./build/pc/main.exe 1

You should see a whole bunch of output about nodes being started, CLOCK components being initialized, etc.
If that works, try running the sample code in the cs213-W04-Sample directory. This is the example that was presented to you in class and shows the simple case of a Sink flooding a packet to a network, and all nodes receiving the flooded packet. Now, execute the below set of instructions.

cd apps/cs213-W04-Sample
make pc
export DBG=usr2
./build/pc/main.exe 5

You should see the following

3: Node 3 initialized
3: Node 3 started
0: Sink initialized
0: Node 0 started
2: Node 2 initialized
2: Node 2 started
1: Node 1 initialized
1: Node 1 started
4: Node 4 initialized
4: Node 4 started
0: Sink timer fired
1: Source received flood msg: cmd=PKT_TYPE_NODE_COUNT_REQ seqno=0
2: Source received flood msg: cmd=PKT_TYPE_NODE_COUNT_REQ seqno=0
4: Source received flood msg: cmd=PKT_TYPE_NODE_COUNT_REQ seqno=0
3: Source received flood msg: cmd=PKT_TYPE_NODE_COUNT_REQ seqno=0
0: Sink sent flood: status=1

Step 2:
The next step is to look at the documentation on Tossim (TinyOS simulator - also called Nido) and to read through the tutorial. It is especially important that you go through the tutorial Lesson 5 on Tossim. Also, carefully read through the Nido system description (you have a local copy of it too at /tinyos-1.x/doc/nido.pdf). Pay special attention to the section on Radio models (Section 3) Once you are done with this, you can start on your assignment.

Part II: Implementation

For this assignment, you will need to implement an application in TinyOS that counts the number of nodes in the system. To help you get started, the tar file we provided you contains a skeleton program with a few missing pieces, in 'apps/cs213-W04/'.

In class, we covered the Flooding component (lib/FloodM.nc) and its configuration file (lib/Flood.nc). The flooding module exposes the FloodData interface (lib/FloodData.nc). You will NOT need to modify any of the code in the above flooding components for this assignment. However, it will be useful for you to go through it to see how it is written.

The algorithm we use in this assignment makes use of the above flooding component. Node 0 is designated as the sink on startup, waits for a certain period of time and floods out a request messag to reach all other nodes in the system. Each node, upon receiving the request message, will flood a reply message. The sink receives the count of unique senders and can print out this number using a dbg() command.

Three lossy topology files are provided. '5x5-5.nss' is a 5 by 5 grid of nodes with grid separation 5 ft. Similarly, '5x5-20.nss' is a 5 by 5 grid with separation 20 ft and so on. Since the effective radio range of the Mote radio is approximately 50ft, each topology represents different lossy characteristics.

To run the code with one of these files, you will have to specify the filename in the command-line as follows:

./build/pc/main.exe -rf=5x5-10.nss 25

The lines written in red indicate questions to answer in your solution.

Step 1:

Familiarize yourself with the code provided:

Node.h: Implementation header file, contains message formats and internal data structures.
Node.nc: Configuration file. You will not be required to change this file.
NodeM.c: Main application file. This is the only file which you will have to modify

There are three places in the code (marked with 'CODE TO BE FILLED IN') where you will need to add code to complete the program.

Complete the missing code segments:

FloodData.recvFlood(): Two code snippets need to be filled in. (a) If the packet is a count request packet, then nodes that are not sinks should check if the packet is either from a new sink or is from the previous sink with a sequence number fresher than the one seen before. This procedure is to prevent the node from responding multiple times to the same request. If the request is a new one, the node starts the CountResponseTimer to fire after pre-defined period RESPONSE_PERIOD. (b) If the packet is a response packet, then only the sink is interested in this. The sink checks to see if the node id is different from those that it has heard from, in which case, it stores it and increments its counter.
CountResponseTimer.fired(): The flooded reply is sent within this function. For this step, do not bother about 'status' reply (which could be SUCCESS/FAIL) that you get from the sendFlood interface. We will fix take care of this case in the next step.

In order to speed the process, we have made sure that the existing framework runs, so you incrementally build the assignment.

To test and debug your program, run the program with a few nodes. As described by the Tossim/Nido manual, which you should have read by now, the easiest way to start is to use a simplistic single-hop radio model (ie all nodes are within earshot of each other and packetloss is zero). This case is achieved when no command-line parameters are given. eg: './build/pc/main.exe 5' simulates 5 nodes in one broadcast domain.

In this step, look at the count that is obtained at the sink, i.e. how many different flooded replies does the sink receive. It is alright if the number does not correspond to the actual number of nodes in the network. In fact, if you are not seeing losses, there is something wrong. This is something we will fix in the later steps.

Helpful Tips:

Debug using the simple radio model with few nodes (eg: 5)
Use the dbg() function to emit log messages at various loglevels. Note that the FloodM module uses DBG_USR1. For your code, use debug levels DBG_USR2 and DBG_USR3. You can turn on a particular set of debug levels by 'export DBG_USR=usr2'
See the TinyOS Documentation Pages here for more information.
If you are an emacs user, you might want to use the 'nesc.el' file provided here to give you nesC syntax highlighting. For vi users, a Vim syntax file can be obtained here

Submit your final source code (including the changes that you make in steps 2, 3 and extra credit) as part of your solution.

Plot or otherwise make a table of Number Of Nodes (y-axis) VS Network Count Received At Sink (x-axis) for the lossless radio model, in which you use 5,10,20 and 40 nodes.

Similarly, plot or provide the table of LossyModelName (y-axis) vs Network Count received At Sink (x-axis) for the lossy models, where you use the three given files.

There are two issues that result in counting errors in Step 1.

The first is the possibility that the FloodM module is busy when a packet was attempted to be sent, i.e. if the Flood.sendFlood command returns a FAIL status. Since TinyOS uses non-blocking interfaces and no queuing is done within the Flood module, it is very likely that a status FAIL response is received.

The second problem is the possibility that nodes are responding in a synchronized manner, with the result that their packets are colliding with each other.This happens because of the choices that we made in our algorithm in Step 1. The sink broadcast would have been simultaneously received at all nodes in the network. Each node would have set a timer for the same amount of time (RESPONSE_PERIOD), at the end of which it would have attempted to flood. Thus, it is likely that many nodes try to simultaneously access the channel, with the result that some of them collide.

We will address these two issues in Steps 2 and 3.

Step 2:

We will now see what happens when the Flood interface returns status flag FAIL in CountResponseTimer.fired(). Clearly, when the status is fail, a backoff policy is needed i.e. the flood should be re-attempted after a time period. This procedure is similar to a MAC-layer backoff policy when the channel is sensed to be busy, except, at the application level. Clearly, tight-looping till the Flood module becomes available is not the best way to do this since this will waste system resources. Instead, you will re-start the timer with a different time-period, BACKOFF_PERIOD (defined in Node.h). Do this a maximum of MAX_RETRANSMISSIONS (defined in Node.h) times before giving up on the flood module. Such a policy makes your module robust to failures in the Flood module.

Also, vary the MAX_RETRANSMISSIONS parameter (set to two by default) defined in Node.h till you seem to achieve better results.

How does this improve the count seen by the sink? Provide the same table as for Step 1 as result.

Step 3:

The second problem that we identified was synchronized channel access, in other words, the lack of randomization in transmission times. In Step 2, you were asked to start CountResponseTimer after a fixed time, RESPONSE_PERIOD. Since the broadcast from the sink would have reached all nodes at the same time, and each node would have set a timer for exactly the same time period, the likelihood of many nodes trying to simultaneously access the channel is high. This dramatically increases the likelihood of collisions, and hence packet-loss.

You will now add application-level randomization to the code to add jitter i.e. use a random number instead of RESPONSE_PERIOD. You are already provided hooks to the Random_LFSR (Random Linear Feedback Shift Register) component, which can be used to provide random numbers. Note that it has already been initialized in StdControl.init(). You can call Random.rand() function to get a new 16 bit random number. This random number can be suitably shortened to suit your needs by using only some of its digits (eg: Random.rand() & 0xff). Note that this is not as good of a pseudo-random number generator that you are likely to get on a PC but a very crude one for the Mote platform. So, you might see some synchronization even after randomization.

Your task in this step is to add randomization and try to improve the count that the sink obtains by following the procedure in Step 1.

How much randomization is required for the sink to obtain the total network count within 10% error?

As with Assignment 1, give an estimate of the latency, i.e. the amount of time that the sink will have to wait before it gets the responses from all nodes. Provide this number only for the '5x5-10.nss' topology.

Extra credit:

Make the sink timer periodic i.e. instead of sending out a single count request, the sink now sends out periodic requests. This change can be easily accomplished by modifying the first field of a Timer.start(..) command to TIMER_REPEAT instead of TIMER_ONE_SHOT, which results in the sink sends a new Count request packet every FLOOD_PERIOD seconds. In this case, the sink will have an estimate of the network count at the end of each FLOOD_PERIOD.

First, determine a choice of randomization and MAX_RETRANSMISSIONS that lets the sink get results within 10% of the actual network count for every period.

Give a list of at least 3 parameters that influence the choice of the above parameters and how they do so. Hint: think about network scaling, MAC-level channel access etc.