CIS 763: Lab #1

(Due Wednesday, May 26)

Use 'script' to record a simulator session. For each problem submit the example used and the 'typescript' file. Below is a sample session of how to use the 'script' command.

[cone] [11> script

Script started, file is typescript

[cone] [2>  cd ~/anish/sim/simulator/bin

[cone] [3> simulator

Welcome to simulator Version 0.1

Type "help" to get help

(sim) …

(sim) …

(sim) …

Stopped at breakpoint 0: <*, *>

(sim) …

Stopped at breakpoint 0: <*, *>

(sim) stop

Excecution halted.

All breakpoints have fired.

(sim) exit

[cone] [5> logout

exit

Script done, file is typescript

Submit your files all at once, otherwise only the last submission persists, erasing all others. Use the following command:
submit c763aa lab2 file1 file2 ...

Your task is to implement any one of the following problems in NesC and to simulate your program in TOSSIM.

Problem #1 Diffusing Computations

The problem of diffusing computations is as follows: Given is a network of nodes, one of which is distinguished as the `initiator', and an infinite sequence of `items' at the initiator. Required is that the initiator flood the items, one by one and in accordance with the sequence order, to all nodes.

Assume that the channels are bidirectional and the network is connected (but not fully connected!). Thus each node can communicate directly with all its neighbors and indirectly with all other nodes. No faults occur.

a) Write a program for diffusing computations.

b) Identify its invariant.

Problem #2 Shortest Path Spanning Tree Construction

The problem of shortest-path spanning tree construction is as follows: Given is a network of nodes, one of which is distinguished as the `leader'. Each node has a parent variable whose type is `node id' and whose initial value is the id of that node itself. Required is that each node set its parent variable such that the graph of the parent relation forms a shortest-path spanning tree rooted at the leader.

Again, assume that the channels are bidirectional and the network is connected (but not fully connected!). Let the length of each channel be 1 for purposes of calculating the length of the path from a node to the leader.

a) Write a program for shortest-path spanning tree construction.

b) Characterize an invariant predicate for your program.

Problem #3 Termination Detection

Let us refine the model of Dijkstra-Safra to say that a node terminates if it receives no message for T time, for some constant T>0.

a) Write a program for termination detection. Choose any underlying NesC program that satisifies this “reactivity” rule.

b) Characterize an invariant predicate for your program.

Problem #4 Snapshots

Assume that the channels are bidirectional and the network is connected (but not fully connected!).

a) Write a program for snapshot collection. Note that the channel state is empty for a WSN. Choose any underlying NesC program, whose state is to be collected..

b) Characterize an invariant predicate for your program.

Note: In tinyos-2, TOSSIM has allows you to simulate specific platforms, including platform specific modules, i.e., by using

% make telosb sim

For this approach to work for every platform, however, you have to implement some 'simulation' modules that are specific to that platform. The current version of tinyos supports simulation only for the 'micaz' platform. The implementation for the telosb platform is incomplete.

But for the purpose of simulation it does not matter if you use 'telosb' platform or the 'micaz' platform. Since both of them use the same radio chip, the code you write for 'telosb' should directly compile for the 'micaz' platform. You can use simulation on micaz platform to test the basic correctness of your code, but any results regarding the per formance are likely to vary significantly from those on an actual implementation on a 'telosb' platform.

In other words, if you want to simulate your code on laptop using tinyos-2, use

% make micaz sim

If you want to test your code on actual telosb mote use

% make telosb