MNet Architecture

Jung Il Choi, Mayank Jain, Jung Woo Lee, Maria Kazandjieva and Philip Levis

Introduction:

Sensor networks fail to meet their performance goals when deployed. Data yields are low; networks last weeks, rather than months; long downtimes are common. Researchers use "Ph.D.s per deployment" as a half-joking measure of the effort it takes. The weeks spent deploying a network are not spent tuning performance; developers spend them trying to figure out why they do not work. Administrators cannot identify what causes network failures. Sensornets are black boxes, where a user has minimal visibility into what nodes are doing and why.

The lack of visibility is fundamental for two reasons: sensor nodes are energy-limited and they are embedded in uncontrolled environments. Energy is the most valuable resource a wireless sensor has. If users could trace all packet transmissions, receptions and internal memory states, it would be easy to identify why a network behaves differently than expected, but they cannot, due to the associated energy cost. Furthermore, every node has a huge unknown variable: the environment it is embedded in to observe.

This project is grounded in the exploration, development, and evaluation of the Mote Network (MNet) architecture, an open-source protocol suite and toolkit for sensor network application development and deployment. The MNet architecture extends visibility as a principle to network protocol design. The protocol suite will include existing dominant protocols redesigned for improved visibility as well as novel protocols whose design maximizes visibility.

Measuring Visibility:

The visibility principle defines a high-level goal for protocol and systems design. We need to explore what it means to follow the principle by researching visibility metrics. Having visibility metrics will enable protocol developers to quantitatively examine and compare design choices. These comparisons require metrics for other protocol properties which visibility may affect. Some properties, such as performance, are well understood and have well-established metrics such as latency, throughput, and convergence time. Other properties, such as energy, will require simple metrics that can guide design decisions. Given its human-centric goal, visibility will inevitably have subjective components. Visibility metrics are therefore intended to be guidelines and useful tools for judging protocols, rather than final arbiters.

Our research goal is to define quantifiable visibility metrics that allow protocol designers to weigh and consider design decisions. To this end, we present two initial ideas for visibility metrics. The first, abstract visibility is simple and can be applied to a protocol specification. The second, concrete visibility, considers observed failure modes and an actual implementation to provide a more specific measurement.

The MNet architecture:

The key insight behind the MNet architecture is that isolation improves visibility. Just as the isolation between processes in an OS makes it easier to determine what causes a crash, isolating protocols can simplify network troubleshooting. To achieve this goal, the MNet architecture institutes the Fair Waiting Protocol (FWP) between wireless sensor protocols and single-hop packet communication. Reversing the common approach of requesting the channel, FWP allows a protocol to grant its local channel to another node to prevent local collisions. FWP provides a sound basis for building higher-level protocols.

FWP introduces two mechanisms to isolate protocols from one another. The first is grant-to-send, a novel collision avoidance scheme where protocols provide information on future transmissions in each data packet. As the name suggests, rather than request a node’s channel by sending it a control packet, as request-to-send/clear-to-send protocols do, in grant-to-send a node can give its channel to another node by transmitting to it. Grant-to-send introduces a single byte header to each data packet, a much smaller overhead than the two packet handshake of request-to-send/clear-to-send (RTS/CTS) protocols, but our initial experiments suggest it can isolate protocols well and greatly avoid collisions. Furthermore, grant-to-send can be used for broadcast based protocols, while RTS/CTS is unusable because it must request the channel from every destination. Instead, with grant-to-send, a node can request a broadcast by granting its channel.

FWP’s second mechanism is fair queuing. Just as an operating system schedules processes to share the processor, FWP schedules protocols to share the wireless channel, using a classical fair queuing algorithm. Protocol grant times provide a clear measurement of channel occupancy. Fair queuing in a multi-hop wireless network is a challenging problem, as each node has its own individual view of channel usage. There are traffic patterns which cannot be scheduled fairly at all nodes. Furthermore, as not all nodes have the same workload, they must implicitly schedule protocols fairly based on limited information. We are exploring one approach FWP can use to achieve this goal, called protocol penalties.

Applying Visibility to Protocols:

Visibility metrics can be used to guide protocol design. Applying them to existing protocols gives us a better understanding of their visibility/efficiency tradeoffs. Working up the protocol stack from FWP, however, we can also apply these metrics to clean-slate protocol design, asking the question: what might a protocol designed for visibility look like?

As an example of such an exercise, we examine a heavily studied sensornet protocol, tree collection. We consider the possible failures for a tree-based collection protocol and see that many can be eliminated. With this idea, we have designed the Pull Collection Protocol (PCP), a collection tree protocol optimized for visibility.

Besides clean-slate protocol design, we will also examine existing protocols and research how we can modify them to improve visibility without breaking interoperability. One protocol we have begun to look at in this light is Deluge, a protocol for disseminating new binaries into a network. Our initial investigations suggest that misbehaving nodes can trigger Deluge’s packet suppression mechanisms and cause network starvation. Developing algorithms for such protocols that maintain fault tolerance and visibility will broaden the set of networking primitives available to protocol designers.

Publications:


[1] Jung Il Choi, Mayank Jain, Maria Kazandjieva, and Philip Levis, "Granting Silence to Avoid Wireless Collisions." To appear in the Proceedings of the 18th IEEE International Conference on Network Protocols (ICNP 2010).

[2] Jung Il Choi, Maria Kazandjieva, Mayank Jain and Philip Levis, "The Case For A Network Protocol Isolation Layer." In proceedings of the Seventh ACM Conference on Embedded Networked Sensor Systems (SenSys), 2009.

[3] Megan Wachs, Jung Il Choi, Jung Woo Lee, Kannan Srinivasan, Zhe Chen, Mayank Jain and Philip Levis, "Visibility: A New Metric for Protocol Design." In Proceedings of the Fifth ACM Conference on Embedded Networked Sensor Systems (SenSys), 2007. "Slides"

[4] Jung Il Choi and Philip Levis, "Grant to Send: Fairness and Isolation in Low-Power Wireless." Technical Report SING-06-01.

[5] Jung Il Choi, Jung Woo Lee, Megan Wachs and Philip Levis "Opening the Sensornet Black Box." In Proceedings of the International Workshop on Wireless Sensornet Architecture (WWSNA), 2007.