[Tinyos-devel] Genealogy of TinyOS protocols
Adam
shiyuan69 at gmail.com
Mon Jun 12 15:54:35 PDT 2006
Matt,
I really like your coding style with detailed comments -- very helpful to
see how a successful project completed. Is your volcano monitoring code
publically available? I want to refer some other implementation like FTSP
time synchronization, digital connection with MicaZ related configurations.
Thanks in advance.
Adam
-----Original Message-----
From: Matt Welsh [mailto:mdw at eecs.harvard.edu]
Sent: Thursday, June 08, 2006 10:33 AM
To: Adam
Cc: tinyos-devel at Millennium.Berkeley.EDU
Subject: RE: [Tinyos-devel] Genealogy of TinyOS protocols
Here is what we have:
http://www.eecs.harvard.edu/~mdw/private/volcano-route.tar.gz
It is basically a modified version of MultiHopLQI from contrib/ucb, but
there are a lot of changes (mostly dealing with buffer management).
See the README for details; no guarantees it will work for you :-)
On Thu, 2006-06-08 at 10:17 -0700, Adam wrote:
> Thanks, Matt.
>
> Please send me a copy. Your guys did great job.
>
> Adam
>
> -----Original Message-----
> From: Matt Welsh [mailto:mdw at eecs.harvard.edu]
> Sent: Thursday, June 08, 2006 9:58 AM
> To: Adam
> Cc: tinyos-devel at Millennium.Berkeley.EDU
> Subject: RE: [Tinyos-devel] Genealogy of TinyOS protocols
>
> 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
> > -d
> > evel
> >
> >
> > _______________________________________________
> > Tinyos-devel mailing list
> > Tinyos-devel at Millennium.Berkeley.EDU
> > https://mail.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos
> > -d
> > evel
> >
>
More information about the Tinyos-devel
mailing list