CS G250: Wireless Networks

Spring 2005

Sensor Network Project

In this project, you will develop code to set up a spanning tree in a sensor network rooted at the base station, and then use the spanning tree to count the number of sensor nodes in the network reachable from the base station. The code will be developed over the TinyOS environment and can be run on a 8-node MICAz mote network (developed by Crossbow Technologies) that we have recently acquired. The assignment can be entirely developed and simulated on your home machine using the simulator TOSSIM, that is available with the TinyOS distribution.

Installation: There are two options.

CrossBow's installation package.
- Go to Crossbow's manuals page and download the "Getting Started Guide" under the "Wireless" category;
- Follow the instructions in Chapter 2 - "Installation of TinyOS". Make sure you have the Crossbow setup CD, or a zipped copy of the CD (uncompressed size < 200MB), which will be made available.
UC Berkeley's TinyOS installation. Go to the TinyOS download webpage, follow the downloading and installation instructions. Make sure you download version 1.1.7 or later.

Getting Started: Read through CrossBow's manual "Getting Started Guide", where basic sensor networing products and programming models are presented.

Mote programming:

Go to the TinyOS tutorial, study Lesson 1 through 8. Pay attention to the sample programs and programming model of NesC.
All the examples in the tutorial can be tried out on TOSSIM - the sensor network simulator. The command to compile a PC version of the program is "Make pc", and the program is stored under the build/pc directory in your program directory.
There are two sets of sample applications - the Crossbow version and the UCB TinyOS version, located under cygwin's "/opt/tinyos-1.x/contrib/xbow/apps/" and "/opt/tinyos-1.x/apps/" respectively. Either would work fine. However in your program directory, the "Makefile" you choose should be consistent with your choice of TinyOS installation, since Crossbow has an added set of libraries. If you choose Crossbow's samples, make sure you also copy the "MakeXbowlocal" file.
Read the TOSSIM tutorial for issues in controlling the simulation.
Optional: Read the nesC Language Reference Manual. (Lessons 1 through 8 of the TinyOS tutorial should suffice for the assignment.)
You might experience problems while using some the Java tools. Simple hacking sometimes works.
While debugging your program, make sure you use DBG_USR1 (and/or DBG_USR2, DBG_USR3. In your shell window, use "export DBG=usr1" (and/or usr2, usr3) to filter out unnecessary screen output.

Spanning tree and node count

The goal of this assignment is to set up a spanning tree over the nodes reachable from the base station, and compute a count of the number of reachable nodes, using the tree. There are multiple approaches to this problem, one of which is outlined below. More hints and details will be added as we go along.

Single-hop network: Broadcast a DISCOVERY packet. Node that receives a DISCOVERY packet replies to base station with a REPLY packet. The base station counts one for every node that replies. This count represents the number of nodes directly reachable from the base station. Using a topology file that simulates a network of nodes in 1 cell, check what that the program returns.
Retransmissions: If the number of reachable nodes is high, which you can set by setting the topology file appropriately, you may observe that not all the replies from the neighbors of the base station are received by the base station. This is because there may be collisions, and the MAC protocol does not explicitly avoid these. You can implement a simple retransmission protocol in which the node retransmits up to a MAX_TRANSMISSIONS (say, 5) number of times, after waiting a random period of time between retransmissions. You can set up random waiting times using a timer.
Multi-hop network: Now we will generalize the above protocol to apply to a multi-hop network. A node that receives a DISCOVERY packet for the first time stores information indicating that the source node of the DISCOVERY packet is its parent and sends two messages: (i) a unicast REPLY message to the sender of the DISCOVERY packet; and (ii) a broadcast DISCOVERY packet that forwards the packet to the neighbors.
Processing REPLY messages: A node that is not the base station node receives a REPLY packet simply forwards the packet up to its parent. The base station node that receives a REPLY node adds 1 to the count for every unique originator of the REPLY message.
Optimization: Rather than forwarding the REPLY messages, the intermediate nodes can maintain information about their children and compute the count of the number of nodes in their subtree. This is the count that the node can forward to its parent. This will imply only a linear number of messages in the number of nodes in the network.