[Tinyos-devel] Genealogy of TinyOS protocols

[Matt Welsh]

For what it's worth, we have used MultiHopLQI extensively in our volcano
monitoring system and it worked very well. Of course, we ended up making
a number of changes and cleanups to correct problems with the buffer
management. If someone wants me to send them the code I'm happy to do
so.

Matt

On Thu, 2006-06-08 at 09:54 -0700, Adam wrote:
> 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
> 
> 
> _______________________________________________
> Tinyos-devel mailing list
> Tinyos-devel at Millennium.Berkeley.EDU
> https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel
>