[Tinyos-devel] Genealogy of TinyOS protocols

[Philip Levis]

On Jun 6, 2006, at 9:52 AM, Steve Jones wrote:

> Hi,
>
> I'm trying to fathom some sort of genealogy for the many examples of
> protocols that exist in the TinyOS source tree.
>
> Can any honourable and long standing members of the TinyOS  
> community give
> some rough guidance as to:
>
> What came first?
>
> What's loosly derived from what?
>
> What's dead on the vine?
>
> What the perceived current winners/ best of breed are?

I don't know all of the protocols out there; my apologies if I miss  
one, and if I have, it would be great if someone could chime in. My  
perspective is very Berkeley-centric.

The paper "The Emergence of Networking Abstractions and Techniques in  
TinyOS"[5] gives a brief genealogy until about 2004, which was when  
CC2420-based platforms (MicaZ/Telos) were just emerging. Therefore it  
doesn't cover how 802.15.4 has changed the space. I won't revisit the  
ground the paper covers, but if you have questions I can do my best  
to answer. The end of the message has a tree of sorts.

The CC2420 radio changed the protocol space in two ways. First, while  
it supports hardware-generated synchronous acknowledgments, the way  
the chip works you can only use them if you also have address  
decoding. That is, the chip won't generate acks for you *and* let you  
snoop on packets to other nodes (broadcast works fine). Several pre- 
CC2420 protocols depended on this functionality (e.g., MintRoute).  
The second change came from a indicator that the CC2420 provides, the  
"chip correlation indicator," which is often called LQI (Link Quality  
Indicator, from the 802.15.4 spec). If you want to be *really*  
precise about it, the CC2420 does not provide LQI, as you are  
supposed to compute LQI from the value the radio gives you, but  
usually it's pretty clear what people mean so it's no big deal.

In terms of tree collection in 1.x, the genealogy looks something  
like this:

Berkeley:
MHOP -> BLESS -> lib/Route -> lib/MintRoute -> lib/MultiHopLQI -> lib/ 
Drain

Crossbow:
lib/MintRoute -> contrib/xbow/tos/lib/ReliableRoute ->  contrib/xbow/ 
tos/lib/ReliableRoute_*

The big shift from MintRoute[1] to MultiHopLQI was to use the LQI  
reading from the CC2420 to estimate link quality rather than  
calculate PRR from received packets. The change between MultiHopLQI  
and Drain[2] was that Drain produces a static tree, which can be  
regenerated from the tree root, while MultiHopLQI, following the  
MintRoute approach, has a continuously updated tree.

I have never tested Crossbow's protocols, and I've never read a  
comparative evaluation of them, so I can't comment on how well they  
work. It's my understanding that Jason Hill wrote a good deal of the  
code, and if so, that often means they're worth looking at.

Moteiv's boomerang distribution has a modified version of MultiHopLQI  
which takes advantage of a very different link-layer abstraction.

There is one reported issue with MintRoute, which is that under heavy  
load the tree falls apart. Someone from USC (I can't remember who,  
unfortunately) told me that this is because data packets fill the  
send queue, causing control packets to be dropped (there is no fair  
queueing/priority queueing).

It's my understanding that most people using CC2420 platforms use  
MultiHopLQI or something home-grown. There is a lot of recent  
activity in the TinyOS 2.0 net2 Working Group to put together a  
collection routing implementation that learns from all of these  
previous efforts and provides better reliability and more robust  
operation. It will be in the beta2 release later this month. It  
doesn't have a name yet.

There are also some protocols/approaches whose genealogy I'm not sure  
of, but are worth mentioning. They might be completely separate in  
terms of code, etc. The major one I'd consider here is Fusion[6],  
from MIT, a collection protocol with several mechanisms for  
congestion control.

Since NSDI 2004, there's been a good deal of work in dissemination  
protocols, which reliably deliver data to every node in a network.  
The two major examples of this are Deluge[3], for large (hundreds- 
thousands of packets) program binaries, and Drip, for smaller (single  
packet) values. The Maté virtual machine in lib/VM has protocol for  
medium-sized (1-10 packet) values[4], but it was never fully optimized.

There are also protocols for any-to-any routing on logical coordinate  
systems (Beacon Vector Routing) and geographhical coordinates (GPSR),  
but I'm not nearly as up to date on the genealogy here.

Phil

[1] Alec Woo et al. "Taming the Underlying Challenges..." SenSys 2003
[2] Gilman Tolle et al. "Design of an Application-Cooperative  
Management System..." EWSN 2005
[3] Jonathan Hui et al. "The Dynamic Behavior of a Data Dissemination  
Protocol..." SenSys 2004
[4] Philip Levis et al. "Active Sensor Networks," NSDI 2005.
[5] Philip Levis et al. "The Emergence of Networking Abstractions..."  
NSDI 2004.
[6] Bret Hull et al. "Mitigating Congestion in Wireless Sensor  
Networks." SenSys 2004.