Assignment 3 (due Nov. 20 1:30pm)

Wireless sensor networks (WSNs) have gained significant visibility in various scientific fields over the past few years, exemplified by sensor data collection applications. In this assignment, you will implement a simple data collection system that transmits real-time temperature and humidity measurements to a base station. These measurements are subsequently displayed on a PC screen.

At a high level, the network consists of a number of sensing nodes and a node acting as the base station plugged into a PC's USB port. Each sensing node samples the onboard temperature and humidity sensors and also relays measurements to the base station. Other than sampling the onboard sensors, the base station forwards all the data it receives from the network to the PC via the serial port. The entire system can be divided into the following logical blocks:

Sense Application:

Sense periodically samples the onboard SHT11 temperature/humidity sensors on Telosb. We set the sampling interval to be T_sampling = 20 seconds. After sampling the sensors, Sense creates an application data unit (ADU), which is the following tuple <Node ID, Node local time stamp, Temperature reading, Humidity reading>. Then, Sense passes the ADU down to the routing layer (via the Send interface) to be forwarded to the base station. If the routing layer is unable to forward the ADU (i.e., Send.send(...) or Send.sendDone(...) returns error codes other than SUCCESS), then Sense temporarily stores the ADU on the 1MB external flash. Later when the routing layer can successfully forward ADU again, Sense will read out all stored ADUs and pass them down to the routing layer one by one.

You may find the TinyOS' Log abstraction helpful for using the external flash. Specifically, the Log abstraction offers a way to sequentially write/read log entries to a circular buffer. You should look at the LogRead and LogWrite interfaces. Note that the external flash is a non-volatile storage unit, and you should erase it before you use it for the first time and whenever you change the log entry format.

Routing Layer:

The routing layer overlays a collection tree on top of the sensing nodes, rooted at the base station. Every node in the tree has a parent that it uses to forward its data.

Maintaining the potential parent list

Nodes continuously maintain a list of potential parents, which are tree nodes that they can later use to connect to the collection tree. Each entry in the potential parent list looks like the following:

 +---------+-----+-----------+----------------+
 | Node ID | LQI | Hop count | Parent node ID |
 +---------+-----+-----------+----------------+

The steps for maintaining the potential parent list are outlined below:

The node overhears data traffic (not the handshake traffic) on the network. For every data packet it overhears, it proceeds to step 2 if one of the following conditions is true. Otherwise the node discards the packet.
1. The hop count in the data packet is smaller or equal to that of the node (see below for definition of hop count).
2. The packet destination is already on the potential parent list (described below).
If the packet source (A) is already on the potential parent list, then the node needs to check if the packet destination (B) is the same as the source's parent in the potential parent list. If not, the node removes A's entry from the potential parent list. Moreover, the node also removes all entries with hop count larger than A's hop count, and it discards the overheard data packet. Otherwise, the node proceeds to step 3.
If the packet RSSI is at least -80 dBm, the node records the packet source node ID in the list (along with the LQI, hop count, and the packet destination). If the packet source is already on the potential parent list, then the node updates the current average LQI.

Joining the collection tree

After booting up,

The node first sets its hop count to be 0xFF (the largest unigned 8-bit value). Then, it idle-listens for 2 × T_sampling seconds and tries to build the potential parent list as outlined above.
Then, the node tries to establish connection with one of the potential parents. Specifically, it picks the node in the potential parent list with the highest LQI. Note that if the list is empty, then the node will try the base station (you can make the assumption that the base station always has a node ID of 1).
The node first sends a JOIN_REQUEST message to the potential parent. Upon receiving this request message, the potential parent checks if the packet RSSI is above -80 dBm. If yes, then it replies with a JOIN_GRANT message. Otherwise, it discards the JOIN_REQUEST message.
Upon receiving the JOIN_GRANT message, the node has successfully joined a collection tree, and it now forwards all its packets (either from itself or its children) to the parent. Since the JOIN_GRANT message includes the parent node's hop count, the node knows its hop count in the network. If the node does not receive the JOIN_GRANT message within 32 msec after sending the JOIN_REQUEST message, it picks the next best node in the potential parent list as the new potential parent, and repeats the process from step 3. If it has tried all nodes in the list, it returns to step 1 above.

A tree node might need to find another parent for various reasons. For example, the parent node has depleted the battery, or the link quality becomes worse. In this assignment, a tree node gives up on the current parent if it cannot deliver 5 consecutive data packets to that parent (i.e. no acknowledgments even with the hop-by-hop retransmissions outlined below). In this case, it immediately removes the failed node from its potential parent list and goes to step 2.

Forwarding the data

The routing layer may receive packets for forwarding from two sources:

Sense injects sensor samples every T_sampling seconds. If the node has not joined any data collection tree, the Send.send(...) should return EOFF. If the routing layer is already trying to forward a packet from Sense, then Send.send(...) should return EBUSY immediately. Otherwise, the routing layer will try to send the packet, and signal Send.sendDone(...) event upon completion.
Packets may be relayed from the node's children. If the node is currently part of a data collection tree, it will queue the packet for forwarding and send back an acknowledgment. Your code is responsible for generating these acknowledgments. Otherwise, it discards the packet. TinyOS offers the QueueC component and the Queue interface for fixed-size queues. You will also need the PoolC component and the Pool interface for keeping track of available message_t objects (the first TinyOS FAQ mail I sent out for assignment 2 should give you hints on why you need to do this).

You should implement hop-by-hop retransmissions (up to 3 times) in case the node doesn't receive any acknowledgment.

The routing layer has the following data packet format:

 +-------------------+-----+
 | Src node hop count| ADU |
 +-------------------+-----+

where ADU's format is the one described above and Src node hop count is 8 bits long.

Base Station Mote:

The base station is a special version of the sensing node where the parent is always set to the PC (i.e., hop count = 0). This means that the base station always forwards the data packets to the serial port.

PC:

The application running on the PC is a python script, and it uses a python library that implements the TinyOS serial stack. The python script continuously listens for incoming serial packets and then displays the sensor measurements on the screen. Note that the network collects raw data (i.e. ADC counts), and your python script will need to convert them to human-readable units (e.g. degrees C) before printing to screen. You can find the conversion formula in section 4.3 of the SHT1x data sheet. For humidity, use the rows for 12-bit output. For temperature, use the rows for 14-bit output and 3V VDD.

Here is a screen shot of the script output from my office desk:

 Src Node: 2, Local time: 300, Humidity: 30.9073288, Temperature: 21.85
 Src Node: 2, Local time: 320, Humidity: 28.7249768, Temperature: 21.87
 Src Node: 2, Local time: 340, Humidity: 28.2358624, Temperature: 21.96
 ...

Skeleton Code:

You can download the skeleton code here.

SenseAppC.nc: The top-level wiring file for the system.
SenseP.nc: The implementation file for Sense application.
RoutingLayerC.nc and RoutingLayerP.nc: The routing layer.
Common.h: Some constants that I think might be useful.
demo.py: A python script that demonstrates how to use the TinyOS python serial stack. Basically, it waits for incoming serial packets, and decode the packet payload with the pre-defined format definition.
volumes-stm25p.xml: Volume definition file (Refer to the TinyOS tutorial for more information).

Programming motes is straight-forward. First, you plug the mote into your PC. The output of motelist should show you the device port of the mote. For example,

 mike@sprite:~/cs450$ motelist
 Reference  Device           Description
 ---------- ---------------- ---------------------------------------------
 M4AN1DBO   /dev/ttyUSB0     Moteiv tmote sky

Then, go to the directory with your application (for example, tinyos-2.x/apps/Blink), and type the following command.

 make telosb install,<node id> bsl,<device port>

You should see something similar to the following:

 mike@sprite:~/local/src/tinyos-2.x/apps/Blink$ make telosb install,0 bsl,/dev/ttyUSB0
 mkdir -p build/telosb
     compiling BlinkAppC to a telosb binary
 ncc -o build/telosb/main.exe  -Os -O -mdisable-hwmul -Wall -Wshadow -Wnesc-all -target=telosb -fnesc-cfile=build/telosb/app.c -board= -DDEFINED_TOS_AM_GROUP=0x22 -DIDENT_APPNAME=\"BlinkAppC\" -DIDENT_USERNAME=\"mike\" -DIDENT_HOSTNAME=\"sprite\" -DIDENT_USERHASH=0xc50d8da4L -DIDENT_TIMESTAMP=0x490a0845L -DIDENT_UIDHASH=0xa8dc4e1fL  BlinkAppC.nc -lm 
     compiled BlinkAppC to build/telosb/main.exe
             2650 bytes in ROM
               55 bytes in RAM
 msp430-objcopy --output-target=ihex build/telosb/main.exe build/telosb/main.ihex
     writing TOS image
 tos-set-symbols --objcopy msp430-objcopy --objdump msp430-objdump --target ihex build/telosb/main.ihex build/telosb/main.ihex.out-0 TOS_NODE_ID=0 ActiveMessageAddressC$addr=0
 Could not find symbol ActiveMessageAddressC$addr in build/telosb/main.exe, ignoring symbol.
 Could not find symbol TOS_NODE_ID in build/telosb/main.exe, ignoring symbol.
     installing telosb binary using bsl
 tos-bsl --telosb -c /dev/ttyUSB0 -r -e -I -p build/telosb/main.ihex.out-0
 MSP430 Bootstrap Loader Version: 1.39-telos-8
 Mass Erase...
 Transmit default password ...
 Invoking BSL...
 Transmit default password ...
 Current bootstrap loader version: 1.61 (Device ID: f16c)
 Changing baudrate to 38400 ...
 Program ...
 2682 bytes programmed.
 Reset device ...
 rm -f build/telosb/main.exe.out-0 build/telosb/main.ihex.out-0

Debugging on the mote can be difficult, especially for the first time. I suggest checking the code behavior frequently to catch bugs early. One common way to debug is to use the three onboard leds (refers to the LedsC component and the Leds interface). The three leds are as follows:

led0: Red
led1: Green
led2: Blue

If you want to use TOSSIM to debug, you should talk to me as there are some limitations that you need to work around.

Deliverables:

All of your code.
A README on tasks that you did not complete, and anything that you want to get my attenton on.
Short-answer questions:
1. What is one benefit of using a three-way handshake?
2. Prove or disprove that the algorithm for maintaining the potential parent list does not create routing loops in the network.