10/7/07

Counting in Tossim


Just a silly application I wrote. A very naive approach to counting in a small sensor network. Programmed in NesC under TinyOS 1.0 and tested under tinyviz.




Since my students might read my blog, and this is an assignment for them, no source code but a simple description.


The network builds a small spanning tree in which a node continuously broadcasts the total of the branch of which it is the root.


All nodes run the same application, node 0 starts as the root of the tree. All nodes remain silent until they receive a broadcast message, node 0 initiates the algorithm.


A node alternatingly broadcasts an AskTotal() to everybody or an AnswerTotal(id,total) message to it's parent. The parent of a node is the first node from which it received an AskTotal().
Nodes store (id,total) pairs in a set. The total send by a node is the sum of the totals in this set plus one. (I guess I should restrict the protocol to just one message.)


The result is a pretty robust algorithm for static networks of a fixed maximal size and fixed maximal degree on the nodes. The algorithm gives the correct total in twice the depth of the tree time. For the shown network of 30 nodes, it calculates a correct answer in about 20 seconds.


Of course, you should never do it this way...