Flooding? Trickle and RBP

Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks

(Levis et al.)

RBP: Robust Broadcast Propagation in Wireless Networks

(Stann et al. SenSys’06)

Today we discussed “flooding” protocols and quickly entered a discussion regarding the definition of flooding. The RBP paper defines flooding as a network-level mechanism that sends information to all nodes in a connected network. However, the RBP paper does not actually introduce a flooding protocol, but rather a robust broadcast protocol that can be used in a flooding protocol… very confusing. I agree this is a semantics discussion, but an important one when discussing the minutia of these protocols. Trickle, on the other hand, is a form a flooding, but more specifically a consensus algorithm. We agreed that there was nothing inherent to Trickle that made it suitable for only code propagation. In general, it can be considered a consensus protocol that is used in this case for pre-code propagation.

Many of us missed the oh so important point that Trickle does not actually perform code propagation, despite its title. The authors even mention this in section 5.1: “The actual code propagation mechanism is outside the scope of Trickle…” What Trickle actually does is form consensus throughout the network as to what is the most recent version of code. Using this consensus, nodes may request updates if they are out of date, but the actual propagation of code is not done by Trickle… hmm, sneaky. I don’t understand why the authors chose to market Trickle in this manner. Why couldn’t they introduce Trickle as a consensus forming algorithm for WSN that, by the way, can be used in a code propagation application? A consensus algorithm would be more general and more useful to other people than what Trickle is now.

We talked about Trickle’s usefulness in real world applications. Someone pointed out that Trickle requires nodes to be always on, which severely impacts node lifetimes by wasting energy. We briefly discussed how we could implement Trickle with LPL and quickly realized that this is not such an easy problem as one might think. With LPL you have a duty cycle and a preamble before each packet. For an efficient network with long duty cycles and preambles, the latency of a transmission means that code will take long to propagate through the network. You can dynamically adjust your duty cycles, but both nodes must agree on the check interval… you can’t do this independently. Maybe you can use RBP to flood the network with the check intervals… maybe not. Another issue that came up was that in Trickle you are limited to a 30 byte routine payload. This seems very unrealistic and very much tailored to Maté. A general code propagation algorithm should accept larger code payloads.

Even though this argument might not apply to these papers because they are a couple of years old, here it goes. Almost all papers that we have read so far claim scalability and demonstrate that claim using simulators. However, most use a small number of nodes in their real-world evaluations (20-40). A common explanation is that they did not have enough motes for a larger test. However, given today’s test beds (Harvard’s MoteLab, Ohio State’s Kansei… etc) with over 200 nodes there is no excuse not to perform large scale experiments. Most of these test beds give out accounts to researchers and are created for this purpose. The next time I see a new paper that does a real world experiment with 5 motes on their desk, but claims scalability, I will be very skeptical.

Networking: Dozer and IP is dead

Dozer: Ultra-Low Power Data Gathering in Sensor Networks
(Nicolas Burri, Pascal von Rickenbach, and Roger Wattenhofer, ISPN '07)

IP is Dead, Long Live IP for Wireless Sensor Networks
(Jonathan Hui and David Culler, SenSys '08)


Thursday we started the discussion by contrasting the two papers at a high level. They both address the problem of networking in wireless sensor networks at all levels with very different philosophies: minimalist vs. maximalist. Dozer is perfectly orchestrated, hand tailored to reduce radio duty cycles while maintaining low message loss under a light load (sampling the environment every minute and a half and beacon messages every half minute), while IPv6 focuses on interoperability and standardization.

Particularly clever bits in Dozer were using a random jitter after TDMA to alleviate transmission conflicts between different branches of the routing tree. Another was tracking the time drift instead of resetting the clock, as earlier papers have mentioned how sensitive applications can be to small perturbations in timing. Dozer forgoes CSMA and low power listening, gaining efficiency by allowing child nodes to sleep through their siblings transmission time and using random (but predictable for parents and children via shared seed) backoffs. Nodes follow two TDMA schedules, one dictated by their parent and one they generate for their children.

Looking for failure modes and things we would have designed differently, we discussed the problems with adding new nodes in a TDMA scheme, epoch growth negatively impacting turnaround time, and the problems with selecting parents mainly on hopcount. Sniffing in low-power-listening is used to gain an idea about link quality and contention, which can't be used when specifically powering off the radio during other's turns. Selecting parents based on hopcount will frequently mean choosing a node at the edge of the nodes detection range, which can be a lower quality connection and result in lost packets thus increasing latency. One simple addition would be to factor in RSSI when detecting and choosing parents in the beacon phases. Another would be to track failed packets and switch parents after a certain threshold.

Dozer buffers one message per node to relay upstream, which some thought might mean one per child and others one per descendant (child/grandchild/etc), and it refuses to accept another packet from that child until the current message has been relayed. Thus bursty network behavior will cause congestion for a long time.

We spent a few minutes interpreting the graphs, figuring out what amount of time was represented in each and what the low duty cycle actually was (2% and .2% are an order of magnitude different, and are each stated in different parts of the paper). One graph we would have liked to see was transmission loss over time - did the network converge towards stability or were the losses constant throughout? One participant took issue with their energy evaluation: radio transmission normally dominates the energy costs, but is it still overwhelming at .2% duty cycle?

Wrapping up out discussion on Dozer, we agreed they presented a full working vertical solution instead of attacking a single layer, which is a holy grail of WSN networking. The low transmission rate assumption limits their applicability, but it was openly admitted and discussed.

Moving on to IPv6 on WSN, we examined why we would even want to try such a implementation and came up with interoperability and standardization. Several wanted our sensor nodes to be able to communicate with other devices (an actuator motor locking a door), to reuse existing tools and applications from regular networking contexts, and to make motes more accessible to programmers. One participant was at the conference talk and relayed how differently this paper was presented there. Jonathan started with "Here is an efficient, working system", went into the benchmarks/graphs, and then described the problem domain and what they encountered along the way of building it (which is the inverse of most systems talks).

The underlying idea is to move the narrow waist up from the active message layer to the network layer by adopting a recognized standard. The network processing community is concerned with quality of service and reliability, however WSN's are not just about moving raw data to the base station, local aggregation can also be important (local max or average of sensor values). So, using IPv6 loses the local topology benefits of tweaking our own MAC and networking protocols but gains a lot in accessibility to normal programmers. Chirps allow nodes to power down their radios when they know they won't need to listen to a message, which greatly improves performance. Synchronous acks allow the application to decide whether to retransmit and to whom.

We briefly talked about Zigbee and Bluetooth as heavyweight protocols, over-engineered for their frequent uses. The internet evolved more from tradition instead of standards. Processing was done at endpoints as much as possible, though some companies like Akamai are moving away from that now. It's governed more by a rough consensus in running code than strict adherence to particular standards, which is a very different social model. The IP paper is also coming from that philosophy, complex but flexible and demonstrate a full working example before expecting anyone to listen.

t-kernel: Providing Reliable OS Support to Wireless Sensor Networks
(Lin Gu and John Stankovic, Sensys 2006)

Resource Aware Programming in the Pixie OS
(Konrad Lorincz et al, Sensys 2008 )

Today we took the plunge into OS design space for wireless sensor
networks. The TinyOS system encourages a component based design where
higher level components abstract away lower level or the hardware
components. While designing any application of reasonable complexity
the programming model quickly becomes a web of components and I have
found it difficult to follow the chain of execution without looking
into the app.c file. A lot of people would argue that TinyOS is not an
operating system but rather a collection of drivers, exposing too many
knobs for the end application to manage. At the other end of the
spectrum are systems like Eon which seeks to abstract away most of the
system complexity and exposes perhaps a little too less. As the
application complexity grows, it would become necessary to support
higher level services like protection domains and virtualized
resources, but the question is do we just strip down existing OSs or
do we need to come up with something more clever.

Gu's paper brought out some interesting debates in the class. Firstly,
it seems like the translations would have been easier at compile time.
One member thought that this approach was taken because it was easier
to implement. Another member pointed out that it was easier to move a
smaller binary to the flash. Moreover it was clear that reasoning
about resources was no longer straight forward (assuming that you
wanted to trace/ model resource consumption). What would have been a
simple call to switch on the LED and measure its power draw, can now
be preceded by swaps to and from the flash, making it difficult to
measure the energy consumed by the operation. Thus one form of
simplicity was traded off for reliability guarantees. Many people
complained that the paper did not bring out the reliability aspect of
the system. Some people felt that it would have been more convincing
if could be shown that the system was able to detect bugs in popular
existing "wild" programs or using other fault injection techniques.
Perhaps the only guarantee that the system provides is that a buggy
application would cause a callback to the kernel. A member argues that
this functionality could have been implemented with a hardware timer
that caused the node to reboot if it hung. The participants also felt
that the code bloat was perhaps excessive but did not necessarily
achieve the performance acceleration associated with such bloating.
Finally, one member vehemently defended t-kernel as a convoluted way
to write a micro-kernel whereas another member thought that is a
software fault isolation on the mote platform.

The Pixie paper was presented at this year's Sensys (along with
lance). It was pointed out that a number of operating systems,
specially those for laptops or mobile phones, tend to be resource
aware. However they might not expose those parameters to the end
application, eg DVFS allows the kernel to slow down operations without
the application really noticing. Having coming into this project late
the data-flow model does seem somewhat intuitive. However the fact
that tickets are not enforced implies that the scratchpad versions of
my programs bypass them. Working with Pixie for the class projects
would definitely help uncover shortcomings with the existing system.
For a while we have been planning on writing a profiling tool that
measures the steady state resource consumption of individual stages
and hopefully that will come out soon.

All these papers make me wonder if we are focusing too much on
managing individual nodes. After all the purpose of the entire WSN is
to monitor a phenomenon and I think that the time is right to take a
more holistic approach towards resource management. Perhaps it would
be easier to reason about the system as a whole than in its pieces.

Operating System Design for WSNs and the nesC Programming Language

The nesC Language: A Holistic Approach to Networked Embedded Systems

(Gay et. al., PLDI 2003)

The Emergence of Networking Abstractions and Techniques in TinyOS

(Levis et. al.)

For Thursday’s discussion, we widened our scope a bit focusing on two papers which addressed overarching aspects of OS design for WSNs. We began by discussing various aspects of nesC, a C-based language designed specifically for programming wireless sensor networks. One aspect of nesC which sparked some debate was the ‘static’ nature of the language, meaning that all memory allocation for a program is set at compile time. While some people agreed with the authors that this design offered the programmer security in knowing that a mote left running for months at a time would not run out of memory, a number of people took issue with this approach. One issue with this static approach to memory allocation is that programmers may be forced to make inefficient use of memory when buffering data of an unpredictable size, since they must allocate all the memory they might need up front. Worse, if one wants to take code written nesC for a particular mote platform and port it to one with different memory constraints it may be necessary to manually re-write all the parts of the code which allocate buffers. Some people argued that this problem could be solved by good programming practice, using constants to clearly define your buffer size in your program header.

I particularly liked one suggested solution to this problem: an automatic buffer-sizing program which could run at compile time and configure buffers appropriately. This might be accomplished by adding a range syntax when defining buffers, allowing the compiler to pick a specific buffer allocation at compile time given the memory constraints of other components in the program and the hardware platform. It seems to me that something like this would go a long way toward making the TinyOS vision of reusable components (more of) a reality.

Another key focus of nesC is dealing with concurrency. In nesC, code can be run one of two ways: asynchronously from an interrupt handler, or synchronously  as part of a scheduled 'task'. The creators of nesC are particularly concerned about  'data races' resulting from concurrent attempts to access a single variable. If it is necessary to ensure that particular block of code cannot be interrupted, we can declare a section of code "atomic." On this point, a number of people worried about the way in which nesC implements atomicity: it turns off all interrupts. This struck me as a rather dramatic approach, and several people worried that a long section of atomic code might lead a mote to miss important sensor information, or render it unable to keep up with the stringent timing requirements of some of the MAC protocols we've been discussing. One person offered a potential fix for this problem, suggesting that the compiler could try to model program timing and detect situations in which the program could be liable to miss a timer interrupt or violate other key timing constraints.

One aspect of nesC which everyone seemed to appreciate was the use of interfaces and parameters to ensure a clean program structure. While this structure can be overly verbose in trivial programs, it makes program structure considerably more readable and helps to enforce good programming practices. As we considered the potential future of nesC and TinyOS, asking whether they would still be prevalent 10 years from now, this clean structure was especially important. The clean relatively simple structure of both nesC and TinyOS were votes in their favor in this regard, especially when we considered alternative UNIX-type approaches. 

Personally, I'm looking forward to actually trying out nesC over the next few weeks before I make any final calls as to its strengths and weaknesses. I like the clean structure and syntax of the language, and the almost hardware-like metaphor of wiring components together, but I'm curious to see how these aspects of the language will actually feel when I sit down to write some real code. 

Research projects and collaboration

Mike Mitzenmacher posted an interesting article about doing collaborative research on his own blog, which is intended for students in his graduate course (CS222) this term, but is just as relevant for this class as well. Good reading.

Z-MAC and Component-Based MAC Architecture

Z-MAC: a Hybrid MAC for Wireless Sensor Networks
(Rhee et al., SenSys 2005)

A Component-Based MAC Architecture for Power-Efficient Media Access Control in Wireless Sensor Networks
(Rhee et al., SenSys 2005)

Today we continued our discussion of MAC protocols by discussing Z-MAC, a hybrid CSMA / TDMA protocol. CSMA is ideal for low traffic conditions, but can yield low throughput under high contention. TDMA can efficiently schedule nodes and maintain high channel utilization, but slots are wasted under low traffic conditions, there are other problems, such as distributed slot assignment. Z-MAC is proposed as a hybrid of these two approaches, primarily utilizing CSMA but switching to TDMA mode when under high contention. This should, in theory, improve performance at both ends of the utilization spectrum, while mitigating many of TDMA's drawbacks by gracefully degrading to CSMA.

The class raised several interesting points about Z-MAC (specifically the TDMA element). One main concern was the practical difficulties involved in slot assignment. Z-MAC does initial slot assignment at startup, but simultaneous startup may be impractical in real-world deployments. Even if the practical difficulties of slot assignment are handled smoothly, the links are assumed to be static until the setup phase is run again. This may not be entirely true in a real deployment either, as even the paper states that "sensor networks may undergo frequent topology changes." While distributed slot assignment is certainly possible, many of us felt that this may be more difficult to achieve in practice than implied.

We also discussed the HCL (High Contention Level) and LCL (Low Contention Level) modes employed by the protocol. HCL is triggered by a ECN (Explicit Contention Notification) message, and nodes enter a TDMA-like mode, where slot owners have a smaller contention window (and thus, priority for their assigned slots). One major point that arose during our discussion focuses on why Z-MAC allows nodes in a one-hop neighborhood to contend for a neighbor's slot when that neighbor does not utilize it's own slot in HCL mode? For example, consider a three-node chain in HCL mode: A--B--C, assigned slots 1,2,3 respectively. If Slot=2, and the owner (B) does not transmit, then both A and C could contend for the same slot and transmit, since they are both in the one-hop neighborhood of B. This could cause a hidden terminal problem. Thus, the only way of avoiding hidden terminals is actually to limit slot contention to the slot owner(s). However, upon further discussion, it was suggested that if a slot is not going to be utilized, then deliberately allowing a situation where a hidden terminal could arise is better than just wasting the slot entirely. On the other hand, energy efficiency is important in WSNs -- so some argued against allowing the one-hop neighborhood to contend for a slot, because transmissions might be useless, wasting precious energy.

This brought us to our next topic: energy utilization. Clearly, the overhead of Z-MAC (such as slot assignment / clock synchronization) will utilize more energy than a simple CSMA-only scheme requiring none of this overhead. The big question for us: Do the energy savings of HCL under high contention really justify the energy cost of this overhead? We feel this would be an interesting area for deep exploration, particularly through the lens of practical workloads.

We also discussed practical issues regarding time synchronization. In an application with very low network utilization, synchronizing clocks every 100 packets may result in large amounts of clock drift between nodes. If traffic suddenly surges, and ECN messages are broadcasted, when nodes switch into HCL mode, they may have extremely out-of-sync clocks. It's not entirely apparent that the LCL to HCL switch is necessarily a smooth one under a situation like this.

Ultimately, we wondered how Z-MAC would perform under real-world workloads. We agreed that situations where nodes are transmitting at near-maximum capacity are rare in real-world sensor networks, and want to see more a detailed analysis of all the popular MAC protocols through a variety of workloads. This brought us back to our previous points regarding the need for standardized MAC protocol benchmarks. In general, while we thought that Z-MAC was a strong idea, we had difficulty becoming comfortable with the exact dynamics of the system. For practical system deployment, we were undecided whether it would make sense to pick this hybrid MAC, or a simpler system with less overhead, like B-MAC.

Although we ran out of time before fully discussing the component-based MAC architectures, we did get a chance to hit on a few high-level topics. Before even discussing any details of the MLA (MAC Layer Architecture), we discussed the overall implications of creating a framework for creating MAC protocols. As the authors write, "using these components, developers can quickly construct new MAC protocols that meet the demands of their specific applications." While we felt that reuse and structure is a good thing, is it necessarily good to have a framework for creating more MAC protocols? Do we really need to have a library of hundreds or thousands of MAC protocols that we can choose from when developing sensor network applications? In general, most of us felt that tailoring the MAC protocol for specific applications is a good thing. However, many felt that the alternative of having more complete MAC protocols with many more tuning knobs, or perhaps even a self-tuning MAC protocol, could be a viable alternative to creating a framework for developing entirely new MAC protocols.

The MAC soupbowl

http://www.st.ewi.tudelft.nl/~koen/MACsoup/index.php

In view of our current fascination with MAC layer protocols, I found this wonderful website that talks about each of them briefly.