Course Project:
There will be two projects in this course: a warm-up project (5%) and the main course project (50%).
Warm-up project:
The purpose of this project is to gain some experience with TinyOS, the TOSSIM simulator, and programming the iMote2's. Most of the code will be provided for you as well as detailed instructions for installation and the loading of the code onto the motes. Please remember however, that the iMote2 (and to a lesser extent TinyOS in general) is an experimental platform and problems and bugs can occur, so do not wait until the last minute to try things out.Main Project:
This project is based on the Desync paper, published at this year's IPSN. The first step is to read the paper. The project will involve implementing the algorithm on the iMote2's and exploring possible extensions. The project will consist of two main parts. Each group will get several motes to code on and experiment with. We will also make a larger number of motes (up to 8) available for shorter periods of time. At the end of the quarter there will be a test day where your implementations and algorithms will be tested on a larger scale (an 8 node multi-hop network).
Overview
The algorithm described in the paper is straightforward and well explained in the paper. There are several reasons for wanting to desynchronize the nodes. The first is explained in the paper and is for TDMA. Alternatively one can think of it as a sampling method. Spreading the sampling out over time is one possible strategy to try to get a uniform sampling in time and space.
The project will be in two parts. For the first part of the project you may make the following assumptions:
The key in this project will be ensuring stability and scalability. Most of the components that you'll use here were introduced in the warm-up project (Timer, GenericComm, Main). However, you will need to be familiar with SysTimeC compenent and SysTime64 interface which allow you to record system time and to precisely schedule Desync message transmissions. The testing procedure we will use is described in the next section.
The second part of the project is more open and requires an extension to where all the motes do not hear each other. Your task will be to come up and implement an algorithm which maximizes a metric of performance described in the Extension section below.
Implementing and Testing the Algorithm
The challenge in the first part is implementing the algorithm under the assumption of single hop deployment and ensuring a certain level of robustness against missed packets, interference and time stamping errors. Note that the larger the period is compared to the number of motes, the more tolerant your system will be to some of these errors (it is your job to figure out which ones).
Your algorithm should work for varying numbers of motes and under different T 's with various failure modes. We will come up with several scenarios which test your algorithm, but a big part of the research in sensor networks (and this assignment) is thinking about what could go wrong. A few examples of possibilities are dropped packets, different values of T, and motes entering and exiting the network.
When we will test your algorithm, we will load a number of motes with your code. Your motes will be physically placed in a single hop radius from each other and from our base station. Base station will broadcast a single value T to all your motes. The motes must receive this and appropriately desynchronize afterwards. The base station will also transmit other packets which you won't have to handle:
The polling packets will test your desynchronization by reading off the next time when your Alarm will fire. You have to use SysTime64.setAlarm() command to schedule your Desync events (testing details).
Specifically you will need to keep track of the local state of the machine. The simplest way to do this is with a state machine which updates when events are triggered. The communications aspect will be given as a component you will connect to. This is a wrapper for the communications module you used in the warmup. It provides simple filtering so that various topologies can be simulated. (implementation hints)
Setting the Period
Your application however does need to be able to receive periodMsg_t radio messages with AM handler 5. This message (see mainapp.h) contains a single 2 byte variable which specifies the Desync period in 10ms units. After receiving this message, your application needs to start Desync algorithm with this period. You may assume that at least one mote will receive this message and will know the correct period. It is your job to ensure that all the motes which come into communication range know about the period.
Extension
The extension is more open-ended, allowing you to come up with your own algorithm. The "best" solution is not known and so this is original research you will be doing. Don't worry about getting the best performance but try to come up something reasonable and think about how to justify your decsisions.
The setting is the same as above except we give you an allowed topology. That is, you will have to use RadioWrapperC to simulate a spread out network. We will define certain metrics as a measure of performance. You have multiple options for which metrics you optimize:
Below are some examples of approaches you could take, although your own ideas are highly encouraged. The first approach is simpler but the second is closer to what we actually want and so is valued higher. The metrics are described in detail in Metrics.
Simulate a complete graph
Enable a multihop version of the above algorithm by simulating that all the motes can hear each other. This will involve adding information to the beacons each mote sends out. This will involve ensuring that your global ordering is consistent with existing links. The most important thing is that if two motes follow each other but cannot hear each other, then the timing information is forwarded.
Building maximal cliques
If we discover the maximal cliques of motes and ignore the links which are not part of the the maximal cliques. However, here care must be taken to ensure that motes do not repeatedly collide. In other words, the offsets must be such that they "fit" together.
Randomized algorithm
We can choose our firing time randomly and cross our fingers :). If we detect another mote firing too close to our timeslot, we can generate a new random firing slot and stick to it. The question is, how do you determine your slot size which depends on the metrics which you choose to optimize. Also, how do you make sure that the slots between you and your neighbors are aligned?
Requirements
The requirements of this project are that the one-hop algorithm should work. You should also implement one extension, and try to get it work as well as possible.
The code for the main project can be downloaded (here)
For project questions please contact Primoz Skraba (CA) or Brano Kusy.
Submitted reports: project01 , project02, project03, project04. Please, refer to this work if you plan to use it.
Resources:
tinyos project webpage (worth exploring, almost everything links to somewhere on this site)