Lab 3: Routing in sensor networks

Background

Wireless sensor networks consists of a large number of small computers, sensor nodes, like the one below that can sense its environment, compute, store information and communicate wirelessly. You can find more background and what we are doing with such a sensor network here.

In this lab we are going to simulate a small network of MicaZ sensor nodes.You can get data about them from the manufacturers homepage, but it's not needed for the lab.

Routing

In general, at the deployment of a sensor network it is not known where individual sensors are going to end up. Therefore the sensors needs to form the network ad hoc and set up all needed services in the setting they ended up in. Routing of messages is one important service and that is the topic of this lab.

Sensor node limitations

These sensor nodes run on batteries. To ensure a long life of the network it is therefore important to conserve battery power. Of all mechanisms of a sensor node, sending messages is clearly the one that uses the power. Therefore battery usage is a very important variable in getting a good routing algorithm

Practical details

Accounts

The lab is done on the computer csmisc19.cs.chalmers.se. To get a username and password, do an empty submission to Account Request in Fire (i.e. press the submit button for the "lab" in Fire named Account Request, without uploading a file or if you get problems with some empty file).

Files

TinyOS with all sources for libraries and everything is installed at /opt/tinyos-2.1.0. There you find Rout.tar.gz. Unpack that into your home directory (at the server) and do the assignment from there.

Assignment background

You will be given a program that performs very basic routing and you are going to improve it so that battery power is conserved better to get as long life of the network as possible (measured as the number of collected messages by the sink during the simulation).

Write a report describing your improvements and presenting the algorithm and results from your simulations. See details about the report further down.

The setting

Nodes are places in a grid and have already performed some localization algorithm so they know where nodes of different ID:s are. In this lab the location is based on the ID in fact, but in a realistic setting to calculate relative location is a more complicated matter.

A simple radio model is used where all messages comes through even when to a node that is transmitting at the same time. This is highly unrealistic, but makes it much easier to compare the different algorithms.

The battery model

The very simple battery model only takes sending of messages into account. The cost of sending a message is the quadratic distance between the sender and the receiver (where the distance of two neighboring nodes in the same row or column is 1). The cost of broadcasting is set to MAXDISTANCE (the maximum quadratic distance a message can reach).

Basic procedure

Unpack Rout.tar.gz in your home directory on the server.
Do changes to the program.
Compile the program by executing: make micaz sim
Run the simulation by executing: ./simulation.py <topology file>
Repeat as needed.

Some tips and pointers

The code is in the language NesC that is a C dialect with facilities to connect different modules. In this lab you will only need to do changes in very C-like code.
TinyOS is event driven. Everything that happens in the program begins by an outside call to a function beginning with event.
All function calls outside RoutC begins with call.
Go through the code and get a feel what is happening.
Set USEBATTERY temporarily to 0 to see the number of collected messages if no battery limits were in place.
Messages are sent by filling in the fields of message and call routMessage().
The information that is printed during the simulation is controlled by the file channels.txt

Resources

You can probably figure out how to do the assignment without having to look in any documentation. However, to understand what is going on the Tutorials are the easiest way to get a basic understanding on how things works.

TinyOS 2.0 Documentation
- Tutorials
- Documentation for the system libraries

Topologies

The nodes are always placed in a rectangular grid. The number of columns need to match the constant COLUMNS in Rout.h The nodes are numbered 0 to COLUMNS-1 on the first row, COLUMNS to 2*COLUMNS-1 on the second and so on. Nodes can be removed from a topology using the removenodes.py script to create more interesting topologies. The removed nodes will still be run but have no one to communicate with. You can build topologies on your own using buildtopo.py to get a grid and then remove some nodes to get some interesting formation.

The Files

The files that you most likely want to do changes to are emphasized.

The application

Makefile	Makefile
Rout.h	Headerfile for the application
RoutAppC.nc	Defines how the application module is connected with other TinyOS modules
RoutC.nc	The application.
TossimPacketModelC.nc	Simplified radio model
CpmModelC.nc	Simplified radio model
RandomMlcgP.nc	Improved randomizer for simulation

Simulation

simulation.py	General simulation driver.
simulationrun.py	Specific simulation settings
channels.txt	Controls the output from the simulation
comb.topo	Topology with arms. Use showtopo.py to view it.
grid.topo	Grid topology. Use showtopo.py to view it.
holes.topo	Topology with holes. Use showtopo.py to view it.

Scripts

buildtopo.py	Builds new topologies
showtopo.py	Shows a topology
removenodes.py	Removes nodes from a topology and outputs a new one
collected.sh	Pipe the output of the simulation through this script to get a good view on collected messages.

The Assignment

Part 1 – improve the basic routing

Implement something better than the basic routing algorithm. The battery level is something that is known to a node, so feel free to use that in your algorithm. If you need to send more information in your announcement messages you can add field to the message struct in Rout.h.

You should write a report where you:

Discuss the idea behind your algorithm.
Present results from comparing your algorithm to the original algorithm.
Discuss failed improvements.

make sure that you keep a copy of part 1 before you do the changes of part 2 (see below at the submission section).

Part 2 – Clustered data aggregation

In the current setting each sensor node sends their information in a message that is routed to the sink. It is very expensive to rout all individual messages. Instead information is often collected and processed and aggregated within an area in the network. This summarized information can then be sent and routed over the network.

In the current algorithm the content messages have a value that is always set to one. To aggregate many messages these values could be summed up and sent in one message. Of course it would be easy for every node along the way to sum up messages that arrives to it, but in a more realistic situation the information sent is something more meaningful that cannot be summarized far from the nodes that sent the information. In this setting we want many nodes in an area to send their information to the same node, a cluster head, that do the summarization and then sends a message that is to be routed towards the sink. That message should be routed normally.

Which node is the cluster head? A simple algorithm is for every node with a certain probability announces itself to be a cluster head. Then the nodes that did not announce themselves as cluster nodes pick the best, in some respect, cluster head and sends their message to it. The cluster head adds up the content information and sends a message with the aggregated data.

Implement an algorithm to do this. Feel free to base the decision on if you are a cluster head and which cluster head to pick on any parameters you like, battery level of the node, battery level of neighbors, anything you find useful. If you want to use random numbers in any way, use random() in RoutC.nc. Feel free to add more message types if you need that. It is not allowed for a cluster head to store content for more than one round though. We assume that the sink needs regular updates.

You should add to the report:

Discuss the idea behind your algorithm.
Present results from comparing your algorithm to your algorithm in part one.
Discuss failed improvements.

On your results

There are no fixed limits for what you need to achieve. Try out some different ideas until you feel you have reached a good result. The experimentation is the most important part, not the exact results.

Submission and presentation

Your results should be presented at the lecture slot at Monday, March 7, 2011. The presentation should take no more than 3 minutes where you present how your routing algorithm works and what results you got. You are supposed to do this in groups of two.

Files on your account

When you submit your code you should, in your home directory on the lab machine, place:

The code of part one in a directory named part1
The code of part two in a directory named part2
Your report named report.xxx, where xxx is the extension of your chosen file format

Make sure that for each of the directories you can go in there and compile and run the code for that part. We will run your code logged in at your account, so you don't need to think about permissions or anything like that.

Note that you should submit your code and report to Fire as usual as well.

Deadline: March 4, 2011

The labs will be reported using the Fire system as usual but also arranged on your account in the way described above. Fire can be found at: https://fire.cs.chalmers.se:8039/cgi/Fire-ds2. Make sure that both members of the group are added before submitting.

A tar.gz file with the following is what is supposed to be submitted:

A working program that satisfies the aforementioned requirements, with source code.
- The source code must be clear and well structured.
- The source code is also placed in directories on your account as described above.
A report containing the things specified for the two parts.