The Future of Sensor Networks

I am occasionally asked by new faculty and grad students (at other schools) whether they should get involved with sensor networks. The concern is that the field has "peaked" and there are risks associated with jumping into an area that may have past its prime. I'm not sure I agree with this assessment. It is true that much of the low-hanging fruit has been picked: after all, the field has been active for about a decade. Rather, I see this as an opportunity to ask where should the field be going in the next ten years. We had a panel on this topic at SenSys 2009, for example. A few thoughts.

First, I think it's important for anyone (new faculty member or grad student) to avoid being too narrow in their research scope. I have always considered myself a "distributed systems person" with a recent fetish for sensor networks, not a "sensor networks person" per se. The set of questions I am interested in find manifestations in sensor networks, but also in clusters, mobile systems, Internet-scale systems, and other domains. That said, it never hurts to ride a wave of burgeoning interest in a research area, as a way of establishing yourself in a community and having impact. To that end the question is whether sensor networking currently offers the right mix of hard problems and trendiness to build a career.

The popularity issue is hard to gauge, but I am convinced that there are some very hard problems in this space that few groups have yet looked at. Most folks probably agree that MAC protocols, routing, localization, and other foundational system services are well trodden problems by now. I'll throw out a few problems that I consider wide open, and by no means is this an exhaustive list.

Managing networks of billions of sensors: Let's say that sensor nets do become massively widespread (some would argue this is well underway). I'm not sure we know how to effectively manage or evolve billions of wireless sensors distributed throughout our environment. Anyone who has deployed a non-trivial sensor network has had to undertake a great deal of manual effort to program the nodes, track their health and behavior over time, and keep tabs on simply where they are. In most computer systems, the ratio of humans to computers is fairly high, so it is reasonable to expect some level of manual effort. Currently, we largely treat sensor nets the same way, but this simply does not scale. We need much better tools and mechanisms for deploying and managing vast networks. Further, as new sensor nodes are introduced into an environment, with new capabilities and software, how do we integrate them with older sensors and allow the entire ecosystem to evolve?

Coupling sensor networks with actuation: This is a hot topic right now and generally falls under the rubric of "cyber-physical systems." I believe we have a very poor understanding of how to synthesize data from a large number of embedded sensors that may be poorly calibrated, not functioning properly (or at all), and exhibit high degrees of spatial diversity. Adding on actuation -- either control of an external system, or direct actuation by the sensor/actuator nodes themselves -- opens up a whole slew of hard problems. We'll need to reason about stability, robustness, and latency. Existing approaches to distributed control will need to take the nodes' resource limitations and failures into account.

Programming and reasoning about complex network-wide behavior: Finally, I am still convinced that our approach to programming large networks is fairly ad hoc. How many times have you read a paper about a protocol or distributed algorithm that involves a tremendous amount of complexity, and for which it's unclear how it will operate in different settings or in conjunction with other code? There are many smart people (I am not one of them) who know how to design complex distributed algorithms, but the devil is in the implementation details, and it's easy to get those wrong. Reasoning about the dynamics of a large sensor network subject to variable loads and resource conditions is extremely difficult, and currently we resort to tuning our code by hand. It's possible that a combination of language, compiler, and runtime support could help automate much of this painstaking design process, but this will require good models and analytical techniques to understand network dynamics at scale.

I think there is plenty of fruit still on the tree, but we need to climb higher up to see it. An "entry level" project for someone wanting to get involved in sensor nets should probably not be to design a new MAC layer or try to solve the localization problem. It's great that systems like TinyOS have matured to the point that lowers the barriers to entry for new researchers; as David Culler likes to say, the hope is that a new researcher in the field can stand on the shoulders of giants, rather than on their toes.

SenSys 2009, Day Three

Today's the last day of SenSys 2009. Some pictures from the poster and demo session are up on the CITRIS website.

The morning session on time synchronization features one of the award papers -- Low-power clock synchronization using electromagnetic energy radiating from AC power lines. This is a very well-executed paper that leverages specialized hardware to pick up the magnetic field radiating from AC power lines to establish a common 60 Hz clock source for a set of sensor nodes. Nodes measure a common frequency but experience local phase offsets, which are corrected for using message exchanges. The hardware only consumes 58uW so this is a very practical approach. If this hardware were widely available, this could be the last word on time synchronization, at least in settings where nodes are deployed in the vicinity of (not necessarily plugged into!) AC power - including buried and overhead power lines.

Shuo Guo from University of Minnesota gave a talk on FIND: Faulty Node Detection for Wireless Sensor Networks. The idea is to look at differences in the ranking between nodes' sensor data and the estimated physical distance from a target to detect sensor faults. This assumes that there is a monotonic relationship between distance to a target and a node's sensor reading. The paper seems to consider a fairly narrow definition of a "fault" and I'm not sure how well this maps onto the kinds of faults seen in real world deployments, nor how this would relate to Byzantine faults caused by buggy or malicious code.

Jung Il Choi from Stanford gave a talk about a network protocol isolation layer, to enable multiple protocols (e.g., CTP and Drip) to coexist without stomping on each other. The isolation layer allows multiple protocols to share a radio link fairly, and observe the same LDR when other protocols are active. This is accomplished using a grant-to-send mechanism that bounds the times when protocols can transmit (to avoid self-interference) and fair queueing. This strikes me as being quite similar to Balakrishnan's Congestion Manager, though without explicit feedback to applications.

Overall the conference was great this year, and the venue worked very well to keep the audience engaged. At the same time it is a huge relief to have it all wrapped up. Looking forward to SenSys 2010 in Zurich!

SenSys 2009, Day Two

Report from Day Two here at SenSys.

Last night at the organizing committee dinner I had the pleasure of chatting with Kris Pister, founder of Dust Networks and the originator of the term "smart dust". I got to pick his brains on the state of sensor networks in industry and the gap between academic work in the area and real-world demands. Kris had a couple of interesting comments. Dust Networks has made major inroads into wireless sensing for industrial automation and is behind the Wireless HART standard. He noted that academics are generally allergic to leveraging fine-grained time sync to enable TDMA and coordinated channel hopping, which can greatly improve reliability. It's true that most academic work favors a CSMA approach. I think there are two reasons for this: first, we don't happen to have a good TDMA implementation for, say, TinyOS that is easy to integrate with existing code. Second, once you go down the TDMA route it taints many aspects of your system design as it tends to violate layering between application logic and the communication substrate.

Kris also noted that a lot of the academic work in this area (including papers in this years' conference) are reporting results that are worse (or at least no better) than what the industrial solutions manage today. I can't prove or disprove this claim but it is true that the academic community is largely unaware of what the industry state-of-the-art is capable of. Kris has been trying to publish papers on their Wireless HART protocol but these kinds of papers are generally not well received by program committees. I do think it would help to have a strong evaluation-driven paper published about this protocol.

A few highlights from today's talks.

Kevin Klues from Berkeley gave a talk on TOSThreads, a threading mechanism for TinyOS. One of the main complaints about programming in TinyOS is that the event-driven programming model requires fairly straightforward programs to be broken up across a set of event handlers. Threading support would make it easier to write simple applications, although it's not clear how much benefit this will have for more complex applications with a high degree of concurrency. Mostly I'm concerned about how one reasons about interactions between threads and the ability to couple activities across them to increase energy efficiency. TOSThreads is a somewhat minimal approach to introducing threads into TinyOS, making it easy to couple threaded and event-driven code, but introduces the distinction between low-priority application threads and a high-priority "kernel" (not a distinction that we have seen in TinyOS before). I think the jury is out on whether this is the right direction but it can make writing simple programs much easier.

My former Ph.D. student, Konrad Lorincz, gave a talk on our Mercury system, which manages energy and radio bandwidth for a network of wearable sensors being used in neuromotor disease rehabilitation studies. Naturally this was the best talk of the conference.

Nithya Ramanathan from UCLA gave a talk on Suelo, which is a system for monitoring contaminants in soil and groundwater. The key challenge is detecting and dealing with faults in the sensors, especially as they are deployed for long periods of time in challenging environments. Suelo adopts a hybrid of autonomous and participatory sensing, by automatically dispatching people to check or replace sensors when data outliers are detected. The system also incorporates feedback from humans to tune the fault detection algorithm. This is a curious paper - it is not a conventional "technology centric" solution. The paper is backed up by data from three deployments (Bangladesh, San Joaquin River, and James Reserve). This is a very important problem for real, long-term sensor network deployments and needs techniques that sometimes are outside of the conventional CS literature. I'm glad this paper is at SenSys.

Rajesh Gupta moderated a panel on "Sensor Networks - The Next Ten Years", looking at the future directions for the field now that we are about a decade in. Mani Srivastava argued that we've moved away from sensing as a key aspect of WSNs, and even further from the potential to do actuation. He admonished the community to focus more on mobile personal sensing. Of course, this involves human factors, such as incentives, user interface design, and privacy. Jack Stankovic thinks the focus will morph into "cyber-physical systems", involving greater interaction with the physical world. To make this work, he argued that we need guaranteed real-time wireless communication as well as formal validation for safety. Joe Paradiso talked about sensor nets as an extension to the nervous system and asked how people will interface with them. His claim is that ubiquitous computing will arise from existing, commodity devices originally intended for other purposes. Finally, Pedro José Marrón talked about the European Cooperating Objects initiative which brings together pervasive computing, sensor nets, and embedded systems.

One thread across these position statements is that the set of open problems is very diverse - and often the solutions are not easily quantified. Perhaps one reason these problems have been less the focus of SenSys is that it is hard to get a quantitative handle on them: it's more difficult to publish papers when you can't show graphs that go up and to the right. By the same token it's hard to get a grad student to go work on a problem dealing with, say, human factors -- at least in the systems and networking community. Joe pointed out that this is more common in other communities, although the methodology (e.g., user studies) can be fairly limiting as well. As a community I think we tend to gravitate towards problems that leverage the techniques and methodologies we feel comfortable with, which in turn constrains the set of problems we tackle.

The poster and demo session followed the presentations. The demos are a real highlight of SenSys and give researchers a way to showcase real systems.

At the banquet we announced the two best paper awards. They are VTrack: Accurate, Energy-Aware Traffic Delay Estimation Using Mobile Phones from MIT and UIC, and Low-power clock synchronization using electromagnetic energy radiating from AC power lines from CMU. Congratulations to both sets of authors!

SenSys 2009, Day One

I'm here in Berkeley for SenSys 2009, the premier venue on sensor network systems. There are 21 papers in the conference this year (out of about 120 submissions) and the quality of the papers is very high. The proceedings have been posted online here. I happen to be the program co-chair along with Jie Liu from MSR, so I feel compelled to blog about the conference.

This morning, Bill Weihl from Google gave the keynote presentation on "The Power of Energy Information." He talked about Google's PowerMeter system which allows consumers to track and visualize the power consumption in their homes -- potentially allowing people to learn about their patterns of electricity use and identify anomalies (like a broken air conditioner). Bill also talked about preliminary work at Google to shift power generation load through smart charging of plug-in electric vehicles, dynamically turning charging on and off across fleets of vehicles based on the grid's fluctuating capacity. It was a great talk and emphasized the potential for large-scale information on energy consumption.

A few highlights from some of my favorite talks today.

Om Gnawali from Stanford gave a talk on the Collection Tree Protocol, which is now the default routing protocol in TinyOS. CTP is the result of a substantial effort to increase robustness and reduce route maintenance overheads for large-scale spanning tree networks. Perhaps the best part of the paper is that they ran extensive measurements on about a dozen sensor network testbeds (including our own MoteLab testbed) to validate the protocol's performance. It is interesting to see the variation in performance across different settings.

Mike Liang from JHU gave a talk on RACNet, a sensor network designed to collect temperature and other data in large datacenters. Unlike "conventional" sensor networks, RACNet uses powered nodes (plugged into the USB port on a server rack) so the need to use, say, low-power MAC protocols is not a concern. RACNet focuses on a token-based data collection protocol to achieve high reliability across a range of node deployment densities, for networks with hundreds of nodes. This is an unusual setting for wireless sensor networks since one might imagine that it is trivial to have the servers themselves collect this data, but it's actually better to have a separate monitoring network that does not directly impact the servers.

Arvind Thiagarajan from MIT gave a talk on VTrack, which uses sparse localization data from mobile phones -- using a combination of GPS and WiFi localization -- to estimate travel time delays for individual road segments. This system provides high-resolution estimates of drive times through "crowdsourcing" mobile phone location data. This involves correcting noisy location estimates using an HMM to map trajectories to road segments. They evaluate the system on more than 800 hours of drive data from a fleet of taxicabs in Boston. I'm glad this paper made it into SenSys since it is not a paper about motes and TinyOS, and points the way towards future directions for the field.

SOSP 2009, Day Three

Final day here at SOSP 2009. Unfortunately my shuttle back to the airport leaves in the middle of the first session, so I am only able to go to the first couple of talks.

Last night at the SIGOPS business meeting, Doug Terry gave an overview of SIGOPS' finances; apparently they are making money hand over fist, and are actually looking for ways to spend down some of the savings. My suggestion: host SOSP 2011 in the ideal location for the conference and don't worry about breaking even.

Speaking of SOSP 2011, Peter Druschel was announced as the Program Chair. There were a few proposals for sites to host the conference. The one that received the most applause was Madeira Island, which is some 500 miles off the coast of Portugal. The site looks fantastic, though I'm not sure about travel connections. Lisbon was the other Portuguese option, which looks great. There were proposals for Dresden, China, Brazil, New Hampshire, and Puerto Rico as well.

The rest of the business meeting included discussions of ACM's copyright policy (and whether SIGOPS should put pressure on them to change it to permit more open distribution of papers); a rehashing of the old single-blind-vs-double-blind controversy (thankfully short); and some discussion of whether the SIGOPS Hall of Fame award should be opened up to non-peer-reviewed publications (there was widespread support for this).

The only talk I have time to write up today is...

Distributed Aggregation for Data-Parallel Computing: Interfaces and Implementations

This paper deals with data-parallel computation in clusters, popularized by systems such as MapReduce and Hadoop. Microsoft's DryadLINQ system automatically generates distributed queries on clusters from application code (e.g., in C#). In this paper, the authors explore programming interfaces to enable distributed aggregation within the cluster: rather than the conventional two-phase "map-reduce" paradigm, allowing intermediate aggregation at source nodes and within intermediate nodes. Doing so can greatly reduce disk and network I/O. The talk emphasized that the programming interface for defining iterator functions can have a substantial impact on performance, and the authors have experimented with a range of aggregation and pipelining strategies.

I have to run to the airport, so I don't have time to write up the Quincy presentation in detail, but kudos to the authors for the Zero Punctuation-themed talk. I'm bummed that I have to miss the UpRight talk as well as the entire last session.

SOSP 2009, Day Two

It's Day Two here in Big Sky and we have a few fresh inches of snow on the ground. Apparently Mike Freedman hit an elk while driving here from Salt Lake City on Sunday (he is OK, the elk is likely not).

Last night at the banquet and awards ceremony, Eric Brewer won the Mark Weiser Award -- well deserved! Eric represents exactly the kind of person this award was designed for, and just before they made the announcement, I was thinking, "Why hasn't Eric won this yet?" Three papers won the SIGOPS Hall of Fame Award, given to the paper that is at least 10 years old that has had substantial influence on the community. I don't recall the papers (they are not posted on the above page yet) but David Cheriton, Butler Lampson, and Hank Levy were all coauthors of the awarded papers.

A few general comments on the SOSP program, and some trends. The hot topics this year continue to be in the realm of debugging and preventing or managing faults. Roughly half of the papers fall into this broad category. There are essentially no papers on distributed systems, at least not in the large scale. (The Microsoft paper on WER is more about debugging than the distributed systems aspect.) Peer to peer, DHTs, etc. are so 2003. Finally, I am quite surprised that there are no papers on virtual machines or cloud computing. This is one area that seems to be getting a lot of attention lately but it's not represented at SOSP this year. Finally, only one BFT paper (gasp!).

Some highlights from Day Two.

Better I/O Through Byte-Addressable, Persistent Memory

This paper from MSR is about rethinking the design of filesystems around the concept of a (hypothetical) byte-addressible, persistent memory, which the authors call BPRAM. Phase Change Memory is now in large-scale production and could provide this capability with reasonable cost within the next few years. BPRAM is expected to be much more durable than flash and much faster (with access times on the order of nanoseconds). The paper proposes BPFS, a new filesystem design that takes advantage of these properties. The key contribution is an atomicity and durability technique called short-circuit shadow paging, which is similar to shadow paging but has a number of optimizations since BPRAM allows one to partially update blocks in place (e.g., one can update just one pointer in an indirect block without rewriting the whole block). The paper also proposes hardware support for atomicity and durability: a new kind of barrier for caches, and adding capacitors to the DIMM so that pending writes complete even if power is lost. What I liked about this paper is that it was looking out beyond existing commercially-available hardware and considering how BPRAM would impact storage system design.

Work-in-Progress Talks

The WIPs are always a lot of fun. Some highlights:

John Ousterhout from Stanford gave an overview on a new project, called RAMCloud, which proposes to reduce the latency for storage in a datacenter by orders of magnitude by developing storage servers with fast RPC (5-10 usec) and that hold all of the data in RAM, rather than on disk.

My own student Geoffrey Challen gave a talk on Integrated Distributed Energy Awareness in sensor networks. The idea is to provide a distributed service allowing sensor nodes to learn of resource availability on other nodes and make informed, coordinated resource allocation decisions. This is the first step towards a distributed OS for sensor nets, something my group is currently working on.

Benjamin Reed from Yahoo! Research gave a talk on "BFT for the skeptics." He made the case that industry is very good at handling crash failures, and some non-crash failures using simple techniques, like checksums. Essentially, it's not clear that BFT solves a real problem that industry has today and argued that unless BFT solutions are easy to configure and solve a real problem, industry would be slow to roll them out.

Eran Tromer from MIT talked about the problem of architectural side-channels allowing information to leak between VMs running on the same physical machine in a cloud. He proposed a tool, called DynamoREA, that rewrites x86 binaries to eliminate these side-channel attacks; for example, by adding noise or delays.

seL4: Formal Verification of an OS Kernel

This paper won one of the best paper awards. The team from NICTA and UNSW formally verified the L4 microkernel, around 8,700 lines of C code, using a 200kloc handwritten specification and machine-checked proof. This is a tremendous amount of work and is the largest verification effort on a complex piece of systems code that I am aware of. They formally proved that there are ZERO bugs in the L4 microkernel: no null pointer dereferences, no memory leaks, no buffer overflows, no infinite loops, and so forth. To make the problem tractable they had to make a number of assumptions - for example, that the compiler and hardware are correct. This seems reasonable to me although we all know that in reality there are bugs in these components as well. Of course, going through this process also uncovered bugs in the specification itself. Very nice work.

Surviving Sensor Network Software Faults

Phil Levis from Stanford gave this talk on Neutron, a new version of TinyOS that adds support for recovery units within the OS, which can be independently rebooted and reinitialized following a memory fault. The idea is to statically determine self-contained groupings of TinyOS components that can be rebooted without impacting each other. The TinyOS kernel itself comprises its own unit which can be rebooted, allowing application code to resume when the reboot is complete. Recovery units can also mark data as "precious" allowing its state to persist across reboots. The authors show that this can be accomplished with low overhead and it reduces the impact of node reboots on overall network availability.

I actually have my doubts about this approach; I think it will make it harder, not easier, for developers to reason about the effect of memory bugs on their code. The advantage of a hard reboot is that it returns the entire node to a known-good state. Having deployed sensor nets with strange bugs impacting data quality, I don't know whether this technique would actually make my life any easier. Damn cool idea though.

Tomorrow I'll blog about the business meeting (tonight) and whatever talks I make it to tomorrow; I have to skip out on the last session to catch my flight home.

SOSP 2009, Day One

I'm in Big Sky, Montana for SOSP 2009 -- widely considered the premier conference on systems. The location is stunning although it's bitterly cold here; I was not ready for this kind of weather for a couple more months. This seems to be the biggest SOSP ever with more than 500 people registered; the last SOSP had a mere 471 attendees. I am not sure what this means. The number of paper submissions has not been going up dramatically, so it's hard to tell if this represents an increasing interest in systems as a field. This year there are a number of co-located workshops, and perhaps with the weak economy people are concentrating their conference travel to focus on fewer high-impact events.

Best paper awards went to three papers: FAWN, RouteBricks, and seL4. These papers all represented a substantial amount of work and have a remarkable number of authors; they are not the kind of papers that were dashed off in two weeks by one or two grad students!

Below are some of the highlights from Day One.

Barbara Liskov - ACM Turing Award Lecture, "The Power of Abstraction"

Barbara used her Turing Lecture as an opportunity to survey the development of Abstract Data Types, CLU, and type hierarchy. It is remarkable how much impact these ideas have had on modern programming languages and practice; Java, C#, Python, and many other languages are the direct descendants of this work. She spend a considerable amount of time talking about the context of programming practice before ADTs were developed, and the issues that computer scientists were concerned about (program structure, control flow, and global state). She surveyed a lot of classic papers -- Dijstra, Wirth, Parnas, and others -- that led to the development of ADTs.

After talking about the mechanisms in CLU, Barbara spent some time reflecting on the current state of programming practice. According to her, modern languages (like Java and C#), but the state of programming is "lousy" -- many untrained programmers developing Internet and browser-based systems rife with things like global state. She wrapped up the lecture by pointing the way to some future opportunities in large multicore systems and reasoning about the semantics of programs running across the Internet.

FAWN - A Fast Array of Wimpy Nodes

The premise of this paper is that it is possible to reduce the power consumption of data centers by an order of magnitude by leveraging much more power-efficient hardware. The idea is to focus on queries per joule as the metric, rather than simply peak performance. They propose a cluster of inexpensive, power-efficient nodes (based on the AMD Geode platform with a small amount of memory and Compact Flash rather than hard disks) and develop a key-value store application. The system has to address the limited memory on the nodes, the need to minimize random writes to the flash (using a log-structured data store), and the need to add or remove nodes from the cluster (using consistent hashing for lookups and migrating data in background tasks). Among other things, the paper shows that the FAWN prototype can sustain around 350 queries per second per Watt, compared to around 50 queries/sec/W for conventional hardware. They also do a nice analysis of total cost of ownership and talk about the regime (in terms of load and data set size) where FAWN makes the most sense.

The Multikernel: A New OS Architecture for Scalable Multicore Systems

This paper is about revamping the design of OS kernels to account for massively multicore systems with heterogeneous hardware (CPUs, GPUs, programmable NICs, and FPGAs). The key idea is to shift away from a single kernel with shared memory and locks on shared data structures over to running a separate kernel on each core, using message passing as the only coordination primitive between cores. This approach allows one to design interprocessor communication protocols that leverage the topology of the underlying interconnect, which can vary substantially between platforms. In the MultiKernel design, all shared state is treated as replicated across cores and mechanisms for explicit replica management (which are typical in distributed systems) become necessary. The authors have implemented a prototype of this design, called BarrelFish, and demonstrated its scalability as the number of cores is increased. This is a really nice piece of systems work and is a classic example of "from scratch" OS design to leverage new hardware trends.

Both the MultiKernel and FAWN papers were presented in an earlier form at HotOS 2009, which I have blogged about earlier.

Debugging in the (Very) Large: Ten Years of Implementation and Experience

This paper from Microsoft deals with Windows Error Reporting, which is the largest client-server system in the world by number of installs. WER receives 100 million error reports a day, across 17 million different programs, across a billion or so installed clients. It's been in operation for 10 years and has led to thousands of bugs being fixed, and has fundamentally changed how Microsoft approaches software development. Galen Hunt from MSR gave a great talk on this system.

The system automatically collects "minidumps" from clients when errors occur, which are then classified into buckets by the back-end servers using a variety of statistical analyses. The bucketing strategy takes into account the program name, version, and symbol in which the program crashed. Doing statistical analysis on so many error reports allows them to narrow in on the bugs that affect the most users and therefore concentrate bug fixing efforts. Galen talked about some of the successes of this system over the years, including identifying 5-year-old heisenbugs in the Windows kernel; detection of widespread malware attacks; and even finding bugs in hardware (such as a broken USB controller that did not implement DMA correctly). This is a great paper on a large, real-world system.

I'll blog about the BOFs, banquet, and award ceremony tomorrow.