[Tinyos-devel] Genealogy of TinyOS protocols

[Adam]

I am a Boomerang user. To be honest, I begin to doubt their credibility
after I detect several nasty bugs. For instance, in their MultihopLQI
implementation:

(1) they do not check duplicate packets, in the situation that the ack is
lost and sender resends packets.

(2) if (parents[i].cost + parents[i].estimate < newparent) {
    	  newparent = i;
	  parentestimate = parents[i].cost + parents[i].estimate;
	}
// Obvious, 'newparent' should be 'parentestimate'. I can not believe they
have seriously tested their program before release. This bug is
fundamentally related whether a child chooses a correct parent - how could
this pass test.

Boomerang seems also redesign some MAC protocols in their core part: link
layer abstraction -- SP. I can not find a good document even talking about
what MAC protocol they are using. 

Harvard's codeblue project gives a very good exmaple on documentation. They
have very good readme files - easy to follow. 

I do not have any relation with these two groups, as a user, just want to
sincerely suggest Moteiv to be more professional with software release.


-----Original Message-----
From: tinyos-devel-bounces at Millennium.Berkeley.EDU
[mailto:tinyos-devel-bounces at Millennium.Berkeley.EDU] On Behalf Of Philip
Levis
Sent: Thursday, June 08, 2006 9:17 AM
To: Steve Jones
Cc: tinyos-devel at Millennium.Berkeley.EDU
Subject: Re: [Tinyos-devel] Genealogy of TinyOS protocols

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.


_______________________________________________
Tinyos-devel mailing list
Tinyos-devel at Millennium.Berkeley.EDU
https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel