DIVISION OF ENGINEERING AND APPLIED SCIENCES
HARVARD UNIVERSITY

CS 263. Modern Distributed Systems:
Wireless Communications and Sensor Networks

Prof. Matt Welsh
Fall 2005

Assignment #1 - Multihop Data-collection Protocol for Sensor Networks

Due Date: November 8, 2005, 11:59pm EDT

This assignment is intended to introduce you to programming sensor networks using the TinyOS operating system. In this assignment, you will develop a multihop data collection protocol. One node in the network will act as a base station, collecting sensor readings from all other nodes. Each sensor node will periodically sample its sensor and transmit the data to a chosen parent node, which will relay the data to the base station. You will develop your protocol using a "kit" of four Telos motes. You will then deploy and evaluate your protocol on MoteLab, a 30-node sensor network in Maxwell Dworkin hall.

Data collection is a standard operation used in a wide range of sensor network applications. When collecting data from sensor nodes at a single base station, we do not assume that all nodes can communicate with the base station in a single radio hop. That is, nodes in the network may need to relay messages for each other in order for the data to eventually reach the base. The simplest routing topology in this case is a spanning tree, in which the base station is the root and all other nodes are at a depth proportional to the number of radio hops they are from the base. At any moment in time, a given node has a single parent node which is responsible for relaying its messages to the base. Because radio link quality tends to vary over time, and nodes may crash or otherwise fail, nodes may need to select a new parent from time to time. In addition, new nodes may be added to the network over a given deployment. For these reasons, it is not appropriate to "hard code" the routing topology into the application: rather, nodes should dynamically discover potential parent node candidates and adjust the routing topology as needed.

Note that a spanning tree is a very specific type of routing. Unlike any-to-any routing mechanisms, in which nodes must potentially communicate with any other node in the network, a spanning tree requires each node to only keep track of its parent. That is, "routing tables" are unnecessary. However, nodes must still track the existence of other nodes in the network that might serve as their parent.

This assignment has five phases, and you will work in pairs. The first two phases involve installation and testing of the TinyOS environment on your Telos mote kits. The third phase involves writing a simple test program that will help you learn the ropes of TinyOS for simple sensing and communication tasks. The fourth phase involves designing and testing the multihop communication protocol on your mote kit. The fifth and final phase requires deploying the protocol on MoteLab and measuring its performance.

Important: Do not email the course staff with questions about this assignment; you must post to the bulletin board system instead! See below.

Step 0: Form a group and get a mote kit.

We have a limited number of mote kits so working in pairs is necessary. Find a partner to work on the assignment with you. Auditors and visitors should not ask for mote kits (and are not expected to do this assignment).

Once you have a group, obtain a mote kit from Bor-rong Chen, MD238. Each mote kit consists of four Telos sensor nodes and four pairs of AA batteries. You will need a Windows or Linux-based PC with USB in order to program the motes. (If you do not have such a machine, please let us know.) Please note that this equipment is expensive and you are responsible for returning the entire kit in working condition at the end of the semester. Also, be careful of static discharge and other things that can "fry" a mote. We do not have any replacements, so use caution.

Although a fresh pair of AA batteries will last for several days if you leave the mote running, keep in mind that you will be doing a lot of reprogramming and testing. You may need to buy more batteries (at your own expense) to complete the assignment. Note that the Telos motes do not have a power switch, so if you leave the batteries in the mote it is probably drawing power (even if the LEDs are not on). We suggest popping out one of the batteries when the mote is not in use. You do not need to put the batteries into the mote to program it: the mote receives power from the USB port when plugged in.

If a mote behaves fine at first, and later acts erratically (e.g., won't reprogram, radio messages not getting through, etc.) try a fresh pair of batteries.

Step 1: Install the TinyOS software.

The TinyOS distribution includes a range of tools. The TinyOS software itself, a compiler for the NesC programming language used to write TinyOS applications, and other tools, such as a gcc cross-compiler that can generate binaries for the Telos motes. The PC-side tools work with Windows and later versions of Linux (e.g., Red Hat 9 and up). Other operating systems (e.g., OS X) are not supported.

To install TinyOS and have it work with Telos motes, follow the instructions on this web page.

If you have any trouble, we have set up a bulletin board system where you can post questions on the assignment, using the motes, or TinyOS in general. Please read (and respond to!) postings on the bulletin board -- do not email us with questions about the assignment (such email will not be answered).

You should also search the TinyOS mailing list archives if you think your problem has come up before. Try to avoid spamming the lists unless you have tried to ask for help on the class bulletin board first.

Test your installation by programming one of your Telos motes with the "Blink" application. To do this:

  1. cd $TOS_BASE/apps/Blink (where $TOS_BASE is the directory where you installed the TinyOS software)

  2. make telos -- this compiles the Blink application. You should see something like:
    mkdir -p build/telos
        compiling Blink to a telos binary
    ncc -o build/telos/main.exe -Os -fnesc-target=msp430 -gcc=msp430-gcc -mmcu=msp430x149 -Wall -Wshadow -DDEF_TOS_AM_GROUP=0x7d -Wnesc-all -target=telos -fnesc-cfile=build/telos/app.c -board= -DIDENT_PROGRAM_NAME="Blink" -DIDENT_PROGRAM_NAME_BYTES="66,108,105,110,107,0" -DIDENT_USER_HASH=0xcd8f8e91L -DIDENT_UNIX_TIME=0x4158b324L -I/home/lair/mdw/src/tinyos/tinyos-1.x/tos/lib/CC2420Radio Blink.nc -lm 
        compiled Blink to build/telos/main.exe
                2338 bytes in ROM
                  45 bytes in RAM
    msp430-objcopy --output-target=ihex build/telos/main.exe build/telos/main.ihex
    
    If you see any errors, then there is a problem with your TinyOS setup.

  3. Plug a Telos mote into a USB port. (For a Telos mote that has not been programmed before, the LEDs will strobe in a mesmerizing pattern. If this does not happen, the mote is not receiving power from the USB port, so there might be a problem with the USB interface on your machine.)

    Type:

    Windows:    make telos install.1 bsl,2  
    Linux:      make telos install.1 bsl,/dev/ttyUSB0
    
    In the Windows command above, the last "2" on the line refers to COM3. Use the appropriate number for the COM port that your machine uses for the USB interface.

    The red and green LEDs on each corner of the mote should blink, indicating that the node is being reprogrammed. After programming has completed, just the red LED should blink on and off once a second.

    Congratulations -- you have successfully programmed a mote!

Step 2: Go through the TinyOS tutorial.

You will not be able to complete this assignment unless you follow the TinyOS tutorial, which is included in the release as doc/tutorial/index.html. This assignment assumes you have done the tutorial so you understand how to program the motes and get data in and out of a PC; don't dive into the rest of the assignment unless you have done this. You don't need to do every part of the tutorial, such as using TOSSIM, but you do need to understand how to program motes, send and receive radio messages, use SerialForwarder, and so forth.

Step 3: Write a simple program to display the value of the light sensor on each mote.

To learn the ropes of TinyOS program development, your first task is to write a simple program in which the status of each node's light sensor is shown on the LEDs of the other two motes. Take three of your motes. One of them will be "red", the other "green", and the last "blue". The appropriate color LED should be lit on the mote, as well as the other two motes, when the light sensor reads above some threshold value. When the light sensor is below the threshold, the LED should be off on all three motes. This is a pretty silly program but requires you to deal with sensors, timing, and radio communication.

First, you will need to add the following line to the file tinyos-1.x/tos/platform/telos/HamamatsuC.nc:

    /* ... */
    StdControl = ADCC;  /* Add this line here */
    StdControl = HamamatsuM;
    /* ... */
(This fixes a bug in the TinyOS v1.1.7 version of this file that prevents the analog-to-digital converter from being properly initialized.)

To access the light sensor on the Telos mote, use the following component, which you should save as TelosPhoto.nc in your application source directory:

/* Provides an interface to the Telos light sensor */

configuration TelosPhoto {
  provides interface StdControl;
  provides interface ADC;
} implementation {
  components HamamatsuC;

  StdControl = HamamatsuC;
  ADC = HamamatsuC.TSR;
}
You need to wire your application to both the StdControl and ADC interfaces of this component. Accessing the TelosPhoto.ADC component using the ADC.getData() call will return a sample for the Telos' light sensor. There are two light sensors on the Telos mote: A "total solar radiation" (TSR) sensor, and a "photosynthetically active radiation" (PAR) sensor. The component above wires to the TSR sensor.

This sensor is fairly sensitive, so you will need to use a fairly low threshold (between 30 and 50) to distinguish between "light" and "dark" in your application.

To get started with your program, we suggest you take the code from a simple program (e.g., Blink) and modify it. You must use the same Makefile format as other TinyOS applications. That is, don't try to write a new Makefile "by hand" -- the file must include the lines

COMPONENT=YourAppName
include $(MAKERULES)
where YourAppName is the name of the main component in your application, and MAKERULES has been set previously as part of your Telos installation. You are welcome to develop your program outside of the tinyos-1.x/apps directory, but be sure you include the Makerules file appropriately (and keep in mind that you need to set the MAKERULES environment variable as explained here). The TinyOS make system is pretty sophisticated and we strongly suggest you simply use it this way rather than trying to hack together your own Makefiles.

In order to avoid packet collisions with other groups, select an Active Message GroupID in the range 0x10 through 0x50. The GroupID is used to differentiate between radio messages transmitted among "groups" of nodes. To set the GroupID, set the following line at the top of your Makefile, before it includes the Makerules file: DEFAULT_LOCAL_GROUP = 0x40 # For example!!!! Please post your choice of a group ID to the class BB to prevent other groups from picking the same ID. If you see bogus packets arriving, it is likely that you have chosen a GroupID used by another group; just select another GroupID. The GroupID must be the same on all motes that you are programming in order for them to see each other's packets.

This program is fairly straightforward. Nodes should periodically sample their light sensor. If the sensor value is above the threshold, it should turn on its appropriate LED color. Likewise, if the value is below the threshold, it should turn off its LED. In both cases, the node should broadcast a radio message indicating its state to other nodes. Upon reception of such a message, a node should turn the appropriate LED on or off.

A node can identify itself using the macro TOS_LOCAL_ADDRESS which is set when you type

make telos install.1 bsl,2
In this case, the mote is being programmed with TOS_LOCAL_ADDRESS set to 1. You can substitute '1' with any other numeric value to give the node a different ID. Use this address to select the color of the node (e.g., red=1, green=2, etc.)

Step 4: Develop your multihop data collection protocol.

Now that you've learned your way around TinyOS, it's time to develop your multihop data collection protocol. As described above, we suggest you use a simple spanning tree approach to routing: each node in the network has a single parent in the spanning tree, which it sends its data to. The parent, in turn, is responsible for forwarding data from its childen to its own parent. The root of the spanning tree is the base station. When the base station receives a radio message, it simply forwards it to its serial port, allowing the host PC to receive the data.

To send a message to the serial port, use the SendMsg interface just as you would for radio messages, but with a destination address of TOS_UART_ADDR. For example,

  result = call SendMsg.send(TOS_UART_ADDR, sizeof(MultihopMsg), send_msg_ptr);

Before nodes can transmit data, they must have a parent to send it to. How does a node learn about a parent? A simple approach is for nodes to periodically send a "tree formation" message. The base station would transmit such a message indicating its tree depth as 0 (the root of the tree). When another node hears such a message, it realizes it can transmit data to the base, so it chooses the base as its parent. This node would also rebroadcast the tree formation message, advertising its tree depth as 1.

This is a simple technique that does not take several factors into account. For example, a node may have multiple potential parents that it can choose from, perhaps with different tree depths. One approach is to always choose the parent with the smallest depth. However, such a node may be further away in the network, and therefore the radio link may be less reliable. In addition, network links may be asymmetric --- the fact that node A can hear node B does not imply that node B can hear node A. For this assignment, you are not expected to deal with all of these issues, although it is at least a good idea to consider how ignoring them may affect the performance of your design.

You have a great deal of leeway in terms of how you design your system. In general your design should be fairly simple, and if you find that your design is overly complex then you are probably going about things the wrong way.

Some basic requirements for your protocol:

In addition to the TinyOS software itself, you should write a program to display the current state of the network. This program should be written in Java and receive data from the base station node using the TinyOS net.tinyos.message library (documented in the TinyOS tutorial).

You will need to use the mig tool to generate a Java classfile for the message type in Multihop.h:

  mig java -java-classname=MultihopMsg Multihop.h MultihopMsg > MultihopMsg.java

To receive and parse the messages, write Java code that looks something like the following:

  import net.tinyos.message.*;

  // This connects to the SerialForwarder running on the local node.
  MoteIF mote = new MoteIF((net.tinyos.util.Messenger)null);
  // Listen for messages of type MultihopMsg (generated by the 'mig'
  // step above).
  mote.registerListener(new MultihopMsg(), this);

  public void messageReceived(int dstaddr, Message msg) {
    if (msg instanceof MultihopMsg) {
      // Cast to MultihopMsg and do something with it...
    }
  }

Your Java program should periodically display a table of the current network state, with one row for each node in the network. The table should have the following columns:

You can simply output this table in text format to stdout. If you are so inclined you could write a GUI that displays the status of the network in graphical form. (No extra credit, though.)

To test your Java program, first run SerialForwarder to forward data from the serial port to a TCP socket:

  java net.tinyos.sf.SerialForwarder -comm serial@COM6:telos
(Replace COM6 with the name of the serial port used to access the Telos mote. Recall that on Linux machines, you need to make a symlink from /dev/ttyUSB0 to /dev/ttyS4 or similiar, which will show up as COM5 in the above command line.) The GUI will come up and will show a counter of the number of packets received by the SerialForwarder program. If no packets are getting through, you can run the Listen program to look at the data coming over the serial port (killing SerialForwarder first):
  MOTECOM=serial@COM6:telos java net.tinyos.tools.Listen
If you are still not seeing anything, it's possible that you are not sending packets from your program to the serial port correctly. To look at the raw data coming in over the serial port, on a UNIX machine you can do something like:
  stty 19200 raw < /dev/ttyUSB0
  od -x < /dev/ttyUSB0
Note that the od program buffers output one line at a time so you may need to wait before it prints anything.

Once you are getting data into the SerialForwarder, fire up your Java program, which connects to the serial forwarder and receives the messages.

You should test your multihop protocol using your mote kit. The easiest setup is to assign the base station node 0, plugged into your PC, and distribute the other nodes far enough away that at least 1 or 2 of the nodes have to route data through multiple hops to each the base station. (The typical indoor range of the Telos motes is quite good -- 50 to 100 meters. You may need to place nodes in other rooms in order to induce multihop paths.) On your PC, you should run the Java program that you developed above to monitor the network state.

Step 5: Test your multihop routing protocol on MoteLab.

Now you are ready to run your multihop routing application on MoteLab. First, login to moteLab. (Your username and password will be emailed to you when the accounts are ready.) MoteLab uses a slightly different type of mote -- the MicaZ -- which uses a different processor than the Telos. Before uploading your executable to MoteLab, you need to compile your program for the MicaZ:

  make micaz
Update: The MicaZ's on motelab do not have the same light sensors as the Telos, so you will also need to change your program to wire the sensor to DemoSensorC.

The resulting executable will be left in build/micaz/main.exe. Create a job for your application and upload this executable as the file that runs on all motes. Also, upload the MultihopMsg.class file that you generated using mig. This will allow MoteLab to log the messages sent to the serial port of the base station node. Once your job is finished running, this log is available to download as a ZIP file, allowing you to post-process the output to generate statistics.

Schedule your multihop routing application to run for a 30-minute period. Use Mote 5 (located in Matt's office, MD233) as the base station node. (The easiest way to do this is to hardcode this node ID into your program and have this node initiate the tree discovery.) Only the base station should forward any MultihopMsgs it receives to its serial port. However, you are welcome to have other nodes send messages to their serial ports for debugging purposes. As long as you upload a corresponding mig-generated classfile, MoteLab will log the messages to its database and include them in the ZIP file.

Once the program has finished running, generate a table (in a text file) consisting of one row for each node (you should have 30 nodes in all), and the following columns:

The totals and averages should be over the entire 30-minute run. You can easily generate this table by writing a Perl script that parses the logged messages included in the ZIP file from MoteLab.

Step 6: Submit the source code and results from your evaluation.

The final step is to send us the results of your evaluation. Please create a gzipped tar file (or ZIP file) with the following directory structure:

   group-usernames/      (e.g., 'brchen-shnayder/')
     README              Include your names, emails, brief description
     sensor/             Sensor and LED test program from Step 3
     multihop/           Multihop application
       evaluation.txt    PLAIN TEXT FILE of the results described above
       tinyos/           TinyOS code
       java/             Java code for receiver program

Email this as a .tar.gz or ZIP attachment to brchen@eecs by 11:59pm on November 8, 2005. No extensions to this deadline will be granted.