Harvard CS263

The Best of CS263

2009-04-24T10:24:00.000-04:00

Well, we're done discussing papers in CS263 this term. We read and talked about 41 papers over the course of the semester, and by and large they were really great.

We decided to run the course in a mock "program committee" style, in which our goal was to pick the top 10 or so papers over the course of the semester. This is great practice for students but also provided a focal point for the discussion: Does a given paper belong in our "program"?

After much deliberation, we have selected the following eight papers as The Best Papers from CS263. This could be seen as a kind of "best sensor network systems papers" award. (Of course, there are many papers we did not read at all, so caveat emptor!)

System Architecture Directions for Networked Sensors, J. Hill et al., ASPLOS'00

This is the classic paper on TinyOS, which lays out many of the challenges in the sensor network domain and focuses on the new OS and communication model requirements.

Radio Interferometric Localization, M. Maroti et al., Sensys'05

There's a lot to like about this paper, which applies RF interferometry to low-power wireless sensor nodes; a lot of technical depth.

The Design of an Acquisitional Query Processor for Sensor Networks, S. Madden et al., SIGMOD'03

TinyDB has been hugely influential in terms of new approaches for querying and aggregating data in sensor nets.

Sensor Network-Based Countersniper System, G. Simon et al., Sensys'04 (BEST PAPER AWARD!)

This system uses acoustic sensors to localize the source of gunshots in an urban setting. It brings together event detection, time synchronization, localization, and a nice sensor fusion algorithm to develop a complete system, which is deployed and evaluated in a real field setting. This paper was universally voted as the students' favorite so we've given it our "best paper award."

Distributed Image Search in Sensor Networks, T. Yan et al., Sensys'08

This paper proposed to use a network of wireless cameras to store and index images which can later be queried by similarity. The authors do a very good job at motivating their design and diving into the details of image processing, flash storage, and so forth.

Dozer: Ultra-Low Power Data Gathering in Sensor Networks, N. Burri et al., IPSN 2007

This paper does a great job at a complete cross-layer design spanning the MAC, link, routing, and application layers to achieve very low power and high reliability for data collection. In some sense this is the first paper I'd give someone working on communication in sensor nets, since it nails down how to do it right.

An Analysis of a Large Scale Habitat Monitoring Application, R. Szewczyk et al., Sensys'04

This is another "classic" paper on the sensor net deployment at Great Duck Island. It's a great case study of the challenges faced by a sensor network in the real world.

Synopsis Diffusion for Robust Aggregation in Sensor Networks, S. Nath et. al, Sensys'04

This was one of the only "algorithms" papers we read, and it does a great job at developing an aggregation technique that is robust to duplicate and lost packets. A superb example of plucking a somewhat obscure concept from the literature and demonstrating its value in a real system.

It's been a great term and I gained a lot by having these heated discussions with the students, who were approaching many of these papers for the first time.

Next week we're doing in-class presentations of the final student projects -- I'll be blogging summaries of those as well!

Underwater sensor networks

2009-04-24T04:25:00.004-04:00

T-Lohi: A New Class of MAC Protocols for Underwater Acoustic Sensor Networks
A. Syed, W. Ye, J. Heidemann

Data Collection, Storage, and Retrieval with an Underwater Sensor Network
I. Vasilescu, K. Kotay, D. Rus
M. Dunbabin, P. Corke

We wrapped up the semester with two papers on underwater sensor networks. As you would imagine, being underwater poses a number of new challenges in the operation of the network. Radio signals don't propagate very far, so optical or acoustic systems instead must be used for communication.

We started with a discussion the data collection paper. This paper presents an underwater sensor network with fixed sensor nodes resting on the bottom of a body of water, while rechargeable mobile "data mules" periodically come by, collecting data from each node. To collect the data, the nodes communicate via line of sight using timed pulses from an LED on one end, and a photo diode on the other end. This requires the mobile node to get fairly close to the stationary node and stay relatively stationary, which could be very difficult with strong currents. Despite some micro-benchmarks performed in the Charles river, the class had its doubts that the system would not work robustly under murky ocean conditions. We talked about how this system could be made to be more robust. Maybe by slowing down the pulses of light, the system would have more time to detect a weak signal, but this comes at the cost of burning more energy on the fixed nodes. Some of the class was disappointed that the authors didn't do more with trying to encode the signals more robustly.

The other way the nodes can communicate with the data mule is acoustically. The nodes were equipped inexpensive audio transducers. But aside from one simple benchmark, it wasn't really used in their system. That was one of the frustrating thing about this paper. The introduction has this vision of many many nodes scattered across the ocean bottom. What they did was far more modest. They were able to collect data in a large swimming pool. We were also left wanting more of an evaluation. For example, how long did it take to collect data from the nodes? Throughput? Latency? In general there is a fine line between explaining your vision of the system vs. the risk of overselling your work and loosing the trust of the reader.

Someone commented that the paper read more like a technical report then a research paper. Lots of mundane details about the system. We liked that they were able to build the system out as much as they did, and the paper does a good job of motivating why this approach makes the most sense in terms of energy, but some of the class felt the cost of moving the mobile node should have been mentioned. Overall, it was pretty impressive that they got things working as well as they did.

The T-Lohi paper focuses on MAC protocols for UWSNs. They use acoustic modems, which have 5 orders of magnitude greater latencies than radio and cost 100 times more to transmit than to receive. T-Lohi uses a short reservation tones and a contention round (CR) before transmitting. The tones are short enough that nodes can often hear other reservation tones. This can give the nodes a count of how many other nodes are wishing to transmit and the backoff timer can be set accordingly for the next CR. When there is only contender in the CR, that node begins transmitting.

They compare 3 variants of T-Lohi: First, synchronized T-Lohi (ST-Lohi) were all nodes are time synced and time is divided up into slots and nodes only transmit at the start of a slot of a CR. Next was cUT-Lohi which is unsynchronized. Every node transmits when it wants, but must listen for twice the propagation delay plus twice the tone length. No collisions are possible. Teh last protocol was aUT-Lohi. Same as above, but only wait the propagation time plus the tone time, but with a chance of collision.

We talked about the problem they were trying to solve, routing packets back to the base station. They were only sending 8 packets per second, in the worst case. That's a pretty low data rate. Is it worth all this extra overhead of the contention rounds? The point of the CR is to reduce collisions. But collisions aren't the end of the world. It's probably the case that since transmitting costs so much, collisions really do hurt you and should be avoided at all costs, but they could have spelled this out more clearly. It would have been great to compare to a strawman of where there was no protocol.

Their use of "optimal" in the graphs was confusing some of us. It seems like a practical upper bounds. It's T-Lohi optimal. Then the discussion turned to whether CSMA schemes are the right way to go with these networks. TDMA would make more sense, but the time synchronization overhead might not make it worthwhile. What about more of a z-mac hybrid approach? Would that be better?

Object Tracking and Image Search

2009-04-18T20:11:00.002-04:00

Object Tracking in the Presence of Occlusions via a Camera Network
Ercan, et al.

Distributed Image Search in Sensor Networks
Yan, et al.

The first paper that we discussed this past Thursday addressed the problem of tracking a static object with multiple occluders (objects blocking the camera’s view of the desired object). The occluders could be moving or static. Compared to the other papers we have discussed so far, this one was heavy on the mathematics, mainly because the paper was focused on explaining the model used to simulate the situation. Also, the only idea that was specific to sensor networks was the idea of reducing the entire image from a camera to one single scan line to minimize the amount of information transferred on the network. It was concluded that this paper comprised in part the “Information Processing” realm of sensor networks.

The authors state the many assumptions that were made, and it was unclear to some of us what the system would or would not detect in special situations. However, we came to the consensus that the assumptions were valid given the constraints on the mathematical tools that the authors used. Something that was not brought up in the paper but addressed in the discussion was the situation of partial occlusions. The process of reducing the entire frame down to one scan line could be problematic in dealing with such situations and some members of the discussion felt that this reduction simplified the assumptions too much.

One person brought up an interesting point questioning whether it is necessary to even track a single object with many occluders. Is it not enough to know whether or not the object is in the room? This was under the presumption that this object tracking system would be deployed for security in such areas as malls, airports, etc. This binary output would be much simpler to implement since each camera just has to report whether or not the desired object is present in its line of vision. It was also hypothesized by some that this work was just a preliminary step towards placing cameras on mobile platforms and the system would then be used to track objects from such things as vehicles, plane, etc.

The second paper we discussed dealt with the problem of distributed image search where each sensor captures images. The user can send ad-hoc or continuous queries to a proxy that would obtain the best search results from the entire network. First we established the assumption that the SIFT algorithm will do a good enough job of translating image information and that the main problem then becomes capturing and querying images on a sensor network. Although it was stated in the paper, it was worthwhile to remind everyone that this system only works when all the objects being monitored similar. For example, one cannot search for a book cover among images of bird species. In this case, the best result visterms would most likely be irrelevant to the search.

After going through the process in which each mote stores images and visterms in an inverted index table, we went on to discuss the evaluation section. One person brought up the fact that there is no end-to-end experiment to measure the amount of time it takes actually pull images from the remote sensor nodes. It would have been nice to see such an experiment since images can be quite large (on the order of 1.6kB) and transferring each image would likely take on the order of 4 packets. There was some skepticism about the power usage value for the CC2420 radio shown in Table 1. One person made the case that the value 214.0 mW was too high and the actual value should be significantly smaller.

Overall, the paper was received very well and we agreed that every issue pertaining to distributed image search was addressed, from storing images on a constrained platform to searching for them. However, the image capture rate of one image every 30 seconds was viewed as unrealistic. A better value would have been on the order of 10Hz. Also, after doing some quick calculations, we found that if the motes had been battery-powered, their lifetime would be on the order of 1.5 hours, which is unacceptable in a widespread deployment. This led to the conclusion that the authors conducted the experiments with motes plugged into an AC power source, rather than batteries. This brought up the larger question: Are motes a sustainable platform on which to implement distributed image search? We agreed that the authors did a nice job of heavily optimizing their solution to work on motes, but, if this still results in a 1.5 hr battery lifetime, then maybe the technology is just not there yet to handle such problems. It was brought up that maybe the gap between what the motes allow and what they are being used for is too wide for the application of distributed image search.

Acoustics

2009-04-18T11:52:00.002-04:00

Sensor Network-Based Countersniper System
Simon et al.

VoxNet: An Interactive, Rapidly-Deployable Acoustic Monitoring Platform
Allen et al.

Acoustic sensing was the topic for Tuesday’s class. The first paper used acoustics to locate a sniper (after taking a shot) and the second presented a generic acoustic sensing framework (to find marmots, among other things).

We clarified a few elements of the countersniper paper first. In particular, the consistency function was unclear to a few people. The function is used to make sense of the multiple shooter predictions coming from nodes. Some nodes may be victim to sound reflection and others may be hearing other sounds. The base station uses the consistency function to combine all of these potentially erroneous readings to make a confident final prediction of the shooter’s location. The function just breaks up a 3D location (X,Y,Z) and time (T) into a four dimensional grid. Each node’s prediction falls into one of the grid’s unit hypercubes (the 4D volume is determined by sensor accuracy characteristics) and the unit hypercube with the most predictions is considered the true shooter location. We had a calculator jam session and found that there are roughly 880 billion potential hypercubes in the shooting range, so an exhaustive search would be slow. Instead, the consistency function just starts with a bisected 4D space, chooses the hypercube and bisects it. This process repeats until a final unit hypercube is chosen.

Signal detection was another important problem the paper had to deal with. To predict a shooter’s location, each node must first know there was a shot. The paper’s approach used zero-crossing points in the acoustic signal, which would give you information on the frequency of the loudest sound. The paper also uses other statistics (max amplitude, etc.) to create a sound signature and can compare this with the expected gunshot signature. At least a few people in class though it was cool that the paper used custom logic (or an FPGA at least) to perform this work more efficiently than a mote.

There seem to be a few ways the system could be fooled. For example, if more motes heard echos than heard a direct event, the consistency function would not work properly. Alternatively, someone could maliciously blast gunshot noises from other locations to distract or jam the countersniper system. Finally, the system wouldn’t do too well if there were multiple rapid-fire shots.

The consensus on this paper was that it brought a lot of techniques together and motivated the use of sensor networks well. This felt like the paper wanted to solve a real problem rather than making up a contrived one.

We moved on to VoxNet, a more generic platform for monitoring acoustics over some area. The system is a bit beefier than our typical sensor networks because it is handling multiple sources with high data rates (4 channels of 44.1KHz audio each). This raised a hearty debate about what a “sensor network” was, exactly. These nodes are using StrongARMs, 802.11, have a large battery, and only have a lifetime of eight hours. These nodes are a far cry from the MSP430 powered motes that might last for months in most of the other papers we read. But, the system forms a network and uses sensors, so it’s technically a sensor network, no?

The paper made accessibility to domain scientists a priority using WaveScope, their dataflow language. The language is pretty simple and can be retargeted for other platforms (such as desktop computers). It also makes use of hand-tuned functions for computationally intensive operations, such as FFTs. This allows WaveScope to get good performance/energy results despite the higher-level language. However, this also lead us to question the performance/energy claims of WaveScope – if most of the processor cycles are spent in these hand-tuned (non-WaveScope) functions, the power/performance evaluation isn’t really measuring WaveScope. Rather, it’s showing that WaveScope doesn’t glue these functions together really poorly. It would be interesting to see how WaveScope performs by itself without these hand-tuned functions.

Finally, we really liked the idea of letting multiple applications coexist. The introduction had us sold on testing code revisions while letting the old programs run, but sadly the paper never came back to it. We would really have loved to see how that functionality fit into the system.

ICEM and Triage: Two approaches to energy management in sensor nets

2009-04-14T13:05:00.003-04:00

Integrating Concurrency Control and Energy Management in Device Drivers by Klues et. al.

Triage: Balancing Energy and Quality of Service in a

Microserver, By Banerjee et. al.

Last Tuesday, we discussed two papers focused on novel approaches to increasing power efficiency in wireless sensor networks. One paper, Integrating Concurrency Control and Energy Management in Device Drivers by Klues et al. focused on building a wireless sensor net OS model which integrates power management at the driver level, automatically turning off peripherals which are not needed. The other paper, Triage: Balancing Energy and Quality of Service in a Microserver, focuses on a specific subset of applications for sensor nets in which resource-constrained nodes are interspersed with more powerful micro-servers. To save power, Triage presents a novel architecture for these microservers in which a low-power node recieves and schedules tasks to be run on a more powerful stargate-class mote, allowing the more power hungry stargate to be turned off much of the time.

We began by focusing on the ICEM paper by Klues et. al. A fundamental underlying argument in ICEM is that much of the inefficiency of existing sensor network systems results from the inefficient handling of concurrency among different parts of an application. To remedy this, ICEM offers a driver system based on the concept of “Power Locks.” To support different types of hardware peripherals, ICEM offers three types of drivers: virtualized, dedicated, and shared. Virtualized drivers encapsulate all the buffering and per-client state maintenance, exposing only a simple functional data path to the application. Dedicated drivers, on the other hand, allow only a single user at a time, which is essential when dealing with low-level hardware control such as turning on or off an LED using a pin on the microcontroller. The third type, shared drivers, permit multiple users but require them to handle concurrency explicitly by trying to acquire a lock on the driver. In a nutshell, ICEM uses the low-level information gained from these driver interfaces to make simple inferences about the future expected concurrency for a given peripheral, and then tries to efficiently put it to sleep at times when it is not needed.

While some thought that the emphasis on deeply integrating power management into the OS was a step in the right direction, there was a good deal of discussion as to whether this approach would truly offer as many gains as they suggest in terms of application performance. A key issue here is the problems created by out-of-phase recurring tasks. For example, if two components of an application sample the ADC every 10 seconds, it would be most efficient to have them synchronized such that each samples one after the other, meaning the ADC would only turn on every 10 seconds for a few cycles. If, however, the components were out of phase such that component one sampled at say time t=n*10, and component two sampled at t=n*10+5, then the ADC is effectively turned on every five seconds which is considerably less efficient. Additionally, several people felt that ICEM had limited utility for applications in which the main power consumption came from a source other than the hardware peripherals, such as PDA class devices.

With regard to the Triage application, there was some discussion as to the applicability of the design to real-world appliacations. A number of people initially felt that the dual hardware approach in a less powerful and more energy efficient node controlled the scheduling of the more power-hungry an more powerful CPU was an innovative approach, but the discussion brought out several of points which raised doubt about its utility. It quickly became apparent that the motivation for the Triage design was based heavily on several assumptions, namely that:

The Microserver can be shutdown much of the time
Messages have to be small (since a lower-power, less powerful node recieves and processes them)
The Microserver will recieve tasks from other nodes in the network via radio (as opposed to from the internet, or a central hub)

The last assumption, in particular, seems to me to limit the potential utility of the Triage design: it necessitates an application in which the resource-constrained nodes do not simply relay data to the microserver, but actually send queries which require use of the heavy processing on the stargate-class device. I can imagine situations in which this might be useful, such as using microservers to offer services to mobile nodes in a ubiquitous computing context, but this type of application is never mentioned by the authors.

Mobile Sensing: CarTel and Nericell

2009-04-13T01:01:00.003-04:00

CarTel: A Distributed Mobile Sensor Computing System
Hull et al.

Nericell: Rich Monitoring of Road and Traffic Conditions using Mobile Smartphones
Mohan et al.

Today, we covered two papers on mobile wireless sensor networks. The
main idea behind mobile sensor networks is to be able to either
dynamically deploy sensors to a particular geographic region of
interest or to cover large geographic areas, where static sensor
installation costs would be prohibitive. The general thrust of this
avenue of research is supported by the increasing penetration of
commodity sensing devices on mobile platforms such as smartphones and
even x86 class hand-held computers (in contrast, most WSN papers that
talk about mote-class devices).

The first of the papers presented CarTel, a distributed, mobile sensor
network and telematics system with an integrated query engine. We
felt that the major contribution of this work was the implementation
of an actual working mobile sensor system, even though it was on a
small scale. However, the system did raise a few interesting issues.
The legality and morality of "borrowing" open wireless access points
by mobile CarTel nodes is questionable, even as the number of open
access points has declined in the last few years. ISPs servicing
last-mile Internet connections to consumers are now providing wireless
APs that are locked out-of-the-box, a strong indication that they will
continue to pursue enforcement of their terms-of-use prohibitions
against public connection sharing. This trend undermines the CarTel
premise (in 2006) that open access points would reach a density that
would allow CarTel to be deployed on a massive scale.

Since 2006, deployment of cellular 3G networks has become commonplace
and most current-generation smartphones and even some hand-held
computers now come with 3G capabilities. This wide-spread
availability of 3G obviates much of the motivation behind CarTel.
True, the data muling aspect of CarTel could be useful for places
where this kind of cellular infrastructure is unavailable. However,
it is getting more difficult to find such places. (One might --
incorrectly -- assume that such scenarios would arise in third-world
countries. However, it is in these countries that cell phone
penetration is even higher than computer penetration.)

We had a sense of slight unease about the way that CarTel incorporated
delay tolerance. Because data-muling and opportunistic open AP usage
are not predictable, data arriving at the base station ("portal" in
CarTel parlance) can be subject to large delays. So how "tolerant"
are we to delays? If delays become huge, one might as well just
purposefully drive a sensor-laden car to a particular region of
interest and drive back! The authors don't give an models of
mobility, node density, range, etc. and so can't provide and feel for
the bounds on delay.

We next turned our attention to several of CarTel's query language
constructs. First, the PRIORITY/DELIVERY ORDER and the
SUMMARIZE AS constructs caught our attention. Prioritization via the
end-point bisection method they propose implies a couple things (1)
that users are generally interested in a "big-picture" view of the
query results, and (2) that FIFO is bad because you can get a huge
delay in results. These are interesting points, but the
implementation of data priority implies in an idiosyncratic way that
real-time querying is the goal of CarTel, which is at odds with the
stated goal of delay tolerance. Second, we discussed the relative
merits of using the "trace" as the base unit of data. It was not
clear to us how GROUP BY a location would be implemented, for example.

We then switched focus to Nericell, a system for annotating road and
traffic conditions using sensor data from smartphones. The crux of
this paper is an interesting way to virtually re-orient sensors in 3D
to a canonical set of axes. Given this capability, simple heuristics
were used to detect potholes and traffic congestion (via accelerometer
and audio samples). We thought that the simple heuristics was a
weakness in this paper. More sophisticated statistical learning
methods exist for this kind of classification/discrimination.
Moreover, such methods may be orientation invariant, obviating the
need for the virtual orientation correction method on which Nericell
is based. On the other hand, the choice of smartphones is an astute
one, since cell phone penetration in India is quite high. Overall, we
felt that the major contribution of this paper is the real-world
implementation on unreliable/uncalibrated sensors, in an extreme
environment (Bangalore roads).

Regiment and Macrolab

2009-04-09T02:17:00.002-04:00

The Regiment Macroprogramming System
Ryan Newton et al.
MacroLab: A Vector-based Macroprogramming Framework for Cyber-Physical Systems
Timothy Hnat et al.

Last Thursday in class we discussed Regiment and Macrolab, continuing our tour through programming models for wireless sensor networks. First we looked at Regiment's evaluation, generally agreeing that number of messages sent was a reasonable rough estimate. However, the number of retries and low-power-listening evesdropping would exponentially increase with network density and affect the energy efficiency. Then we looked at node failure, which would drop the entire subtree until the next tree formation round (epoch). There didn't seem to be a good measure of reliability built in, how many nodes contributed to the value at a given time. Overall we preferred the region metaphor in Regiment to the "vectors" in Macrolab, though most of us are not Matlab or database folks.

We discussed where it fell in the programming language spectrum, deciding eventually that it was between tiered and declarative as it had controls to manage granularity. The big differences between the different languages and programming environments we've read about is in the mental models. Earlier systems addressed problems in great detail just above the hardware level while the more recent papers present intermediate and high level modes of thinking about the problem. The ability to define nested regions is the real difference between Regiment and TinyDB, along with time being a primitive. We returned once again to the problem of time synchronization, what values were really reported at the base station and how accurately they reflected the current state of the sensor space. TinyDB merges old data with new as packets get relayed slowly from the outer reaches of the network.

Someone suggested we might be able to fix this by adding a local timestamp as part of the gathered data and buffering the last bunch of values, returning the one that best matches the requested time when queried. But we still need to map between local and global time to adjust for clock drift. Distributed algorithms in general need a lot more information in order to obtain precise measurements - network depth can have a huge impact on the time required to know everything that happened at a specific instant even discounting the overhead of time synchronization.

We ended up deciding the main contributions were defining functions over regions, allowing programmers to deal with mid-level abstractions with more flexibility than TinyDB but still taking care of all the details of compiling global network definitions to individual node code.

We then moved on to Macrolab, which defined programs in terms of the data needed. Several expressed concerns about trusting their decomposer to generate reasonable code, which others likened to the relational database revolution. Others worried about the cost model, though all thought the idea of where to store the data under what network and workload conditions was a real concern worth study. The paper fell just short of demonstrating run-time adaptivity that would be extremely useful. Even with run-time adaptivity, poorly balanced workloads could cause thrashing between modes and poor overall behavior.

Programming Models -- Tenet and Declarative sensor network

2009-04-07T04:18:00.004-04:00

This class continued the theme of working towards picking the best 10 or so papers of the semester for a wireless sensor network "Hall of Fame". Over spring break we were asked to pick 5 favorites of the 27 the papers we've read so far. We started off the discussion by going over peoples picks and kicking off a new format for the class. The two top papers were TinyOS (ASPLOS'00) and the Radio interferometric localization. There were 4 papers that were in the running for the three remaining slots. Great Duck Island, NesC, Dozer, and Pixie. We decided to keep them in the running for now.

The topic for this class was programming models. As sensor networks mature, it's natural to think about interacting with them at a higher level. Our first paper for discussion was Tenet. Tenet argues for tiered sensor net deployments with simple leaf nodes interacting with more powerful master nodes. Programming the network is done through tasks, which are a linear combination of tasklets. Master nodes disseminate the tasks to the motes which perform the requested operation and send their results to an available master.

Some of the class liked the idea of specialized motes, as one size does not fit all, but wondered how easy is it to decide where to place these master nodes. Then discussion turned to would it be possible to build a mote that could switch from a low power mote to a high power master node, perhaps by using something like dynamic frequency scaling?

There was some concern that this model does not fit the idea of a scattered node deployment (think of nodes being tossed out of a plane), but this is a myth. Very often in real deployments, nodes are placed with some care, but Tenet does have an extra level of planning than some of the other systems we have looked at.

One of the advantages of Tenet is that global coordination is easer than other systems as tasks only come from the masters. Their main claim is the easy of management and usability, but they could do a better job of selling this. It seems like this could extend the lifetime, but no real energy evaluation was provided.

One disadvantage is that you have to code for two different platforms, the motes and the master nodes. They didn't make a convincing argument that it's easier to do this in the master. The usability of the system could be a big win, but the paper didn't convince some of us that it is easier. It seems like they are just pushing the complexity around in the system rather than reducing it.

There is a tension in systems between simplicity/reliability and capability. Tenet comes down on the side of simplicity but did they take advantage of this? They could have talked about all the complexity of the mote-peg as a straw man, and beat up on that a little. That would have been more more convincing. The class voted on the paper for the CS263 hall of fame: 3 weak accepts, 7 weak rejects and two strong rejects, so it didn't make it.

Our second paper was Declarative sensor network. They attempt to come up with a general-purpose, easy to use, efficient programming model for sensor networks. They created Snlog, a dialiect of Datalog to program the network. The application gets translated into a intermediary dataflow representation that uses chains of database operators that is then compiled as an executable for the nodes. They implemented several systems in datalog, such as multi-hop collection, tricke, a tracking app, and many others that they didn't have the room to describe.

The apps seem concise and all could fit on a power point slide, but that lead to our first point of discussion. Could a domain scientist get her application working and get up to speed quickly in such a system? Someone commented it's like writing your application in Haiku. This got a chuckle out of the class and led Matt to his own blog entry on the topic. The point is that maybe several pages of code that you can understand and reason about is better than a half page of code that you have little wiggle room to get wrong. Debugging sensor networks is hard, and these DSN models are tough for some people to wrap their heads around. Despite what the authors want you to believe, sensor networks are not databases.

What does using a DSN buy you? It gives the complier and runtime some flexibility in how to implement it. It's like having an automatic transmission in your car. But you still have to think about programming at the node level. You're basically writing a state machine for the node. The node specifiers are critical to programming the system. You need to pin down on the node the statement is running on, however you are only allowed to name one hop neighbors. There is implicit communication going on and commands are inducing communication in the network. It may be hard to get a handle on energy usage in this systems. As for nominations to the hall of fame there were 4 weak accepts 5 weak reject 3 strong rejects, so we were 0 for 2 with this class.

Dealing With Sensor Data

2009-03-29T19:30:00.002-04:00

A Macroscope in the Redwoods

Tolle et al.

Fidelity and Yield in a Volcano Monitoring Sensor Network

Werner-Allen et al.

Today we discussed two papers which involved environmental monitoring. Although we've seen papers which did this sort of monitoring before (Great Duck Island), both of these papers brought something new to the discussion, in that they tackled using WSN as scientific instruments, with a focus on the collected data.

The first paper we discussed was "Macroscope." Opinion was split over the contributions of this work. Some argued that the real deployment in the redwoods gives a good overview of the capabilities of current WSN for data collection, grounding the field. WSN are here! Data valuable to biologists, that had previously been unattained, was now available. "Macroscope" provided a look into what useful data could be the result of such a deployment, where the problems for future consideration were, and calibration issues.

On the other hand, some argued that there was nothing altogether too impressive here. Previous works had preformed environmental monitoring, and other fields had data sets far, far larger than what was considered in this paper. It was proposed that perhaps particle physicists, astronomers, and some others may get a good laugh out of the relatively tiny data sets from environmental monitoring.

In "Macroscope," the data yield from the network was far less than ideal, and far less than the data loggers. Someone wondered if it wouldn't be better for a static deployment to just run cables, given the unreliability of wireless communication, and given the need for scientists to miss as few sensor readings as possible. We discussed a few problems with wired connections, including deployment issues, and the weight of the cables being cumbersome for the tiny motes. Someone suggested that WSN could hopefully be deployed by a non technical person, just by switching the nodes on, and letting the network form itself, rather than have to worry about physically connecting things properly.

One point of discussion was in regards to the need for the radio network at all. "Macroscope" points out that they used data both from the on board flash data loggers, and from the network. However, had the logs been reset at deployment time, there would have not been any need for the network, so why bother? Could environmental monitoring be an application where long existing data loggers are more appropriate? Someone made the point that the network allows us to do time synchronization for sensor reading timestamps, without power hungry GPS. Additionally, the data from some applications, such as seismological event monitoring, may have real time value.

This motivated a more general discussion about the potential misuse of motes, where other platforms were more appropriate (not saying that this was the case with "Macroscope"). One impassioned individual argued that there may be a temptation to solve an interesting technical problem for motes, for an application where motes aren't the most practical solution. It may indeed be out of balance to stick a mote on an expensive, power hungry sensor.

As the discussion segued to "Volcano," someone suggested that the success or failure of a particular WSN should be data oriented. Indeed, "Volcano" focused on how well a WSN could replace previously used systems for data collection, using data fidelity and yield as its metrics.

In one sense, this work was less successful than "Macroscope." Between software problems and power outages, the network was down for a significant portion of its deployment, making conclusions about performance potentially troublesome. Additionally, a bug in the time sync protocol made data analysis very difficult. Luckily, a sensor nearby to the deployment was used for "ground truth" to successfully recover as much data as possible. The paper stressed the many problems could occur in deployment which were not apparent in lab testing (such as high velocity rocks destroying an antenna).

One person said that this paper presented itself as "We deployed a broken system, and this is how we extracted useful lessons," rather than "Here's our volcano monitoring system, and here was the performance," as the latter presentation may not have been accepted into a top conference, due to the various problems encountered during deployment.

Someone, perhaps somewhat cynically, suggested that if the system had been used to monitor a forest, rather than a volcano, it would not have been accepted.

Throughout the discussion, we considered which of the papers today, if either, we might include in a cs263 hall of fame. Nobody seemed ready to make a strong commitment to either paper, nor did anybody suggest any of the other papers we read this semester. It seemed hard to directly compare the quality of the contributions of one paper with those of another, and even more so to say that one paper is better, by whatever metric, than most of the rest.

Target Tracking

2009-03-17T18:10:00.002-04:00

A Line in the Sand: A Wireless Sensor Network for Target Detection, Classification, and Tracking
Arora et al.

Tracking Multiple Targets Using Binary Proximity Sensors
Singh et al.

We took on object tracking in today’s class. Despite similar goals, the two papers we read took on noticeably different approaches. “Line” clearly made an effort to generalize approaches and algorithms while “Tracking” focused on a narrower 1D subset.

We started our discussion with “Line,” and the brief evaluation was the first issue. Perhaps details of the result were obtained but withheld due to the paper’s military connection? Still, the scalability results they release are not ideal. Further, details of their experiments is vague. Alas, it’s hard to know when you don’t know what you don’t know.

The energy issue came up early too. Many of us would have liked to see some evaluation of the energy consumption of the system. How much energy is consumed by the four consumers identified in the paper (sensing, computing, storing, and communicating)? In the interest of maintaining generalizability, we understand that you wouldn’t want to constrain the system to a certain lifetime or power allocation, but it would be nice to understand the magnitude of power consumption.

We identified some contributions in “Line”. The most obvious was support for tracking in two dimensions, using binary sensors. The paper also introduces the concept of an influence field (the area in which a sensor could detect a target). In addition, the paper attempts to count and categorize tracked objects (ordinary person, soldier, military vehicle). The paper also identifies several potential mote sensors and makes a case for the two they use: a magnetometer and radar. There was a little discussion about whether this list was compiled before or after sensor selection, but this might be some grad students projecting their experiences onto the paper...

The radar sensor was interesting, as most (if not all) of us had never used one. The radar seems to have a good range at 60’, although the specific measurement was not intuitive at first. The sensor is not measuring the velocity of the tracked object, but rather the magnitude of the vector component pointed toward the sensor.

The magnetometer’s characteristics were clearer, but seemed to introduce many of the flaws in this paper. The biggest problem is the range, which seems to be roughly 10’ and we suspect leads the need to have sensors spread out at ranges of 5’ from each other. Not only is this kind of sensor density difficult to deploy, but it causes radio density problems as well. The paper makes several references to contention leading to problems. For example, increasing retransmissions results in worse performance, tuning radio power produces large performance improvements, and scalability becoming a problem due to radio density.

We also identified some weaknesses and questionable assumptions. First, the paper assumes targets are moving. This limits the system to detecting intruders and could not be used to do reconnaissance (how many tanks are hiding in a base, etc.). Second, the paper assumes that two targets are at least 10m from each other. This might be true with vehicles, but is not always clearly the case when dealing with people (soldiers or otherwise). In addition to miscounting, violations of the 10m assumption might lead the system to misclassify a group of soldiers as an armored vehicle. Finally, the paper assumes that noise will only effect a minority of motes. The wind is the example given in the paper, but wouldn’t wind affect a majority of nodes? Wind isn’t terribly discriminating.

We moved on to the “Tracking” paper. The paper also uses binary nodes (this time generalized as outputting a 1 if at least one target is detected, 0 otherwise). The system takes a series of snapshots over time and sends them to a centralized processor. The processor then tries to determine a lower bound on the number of monitored targets.

There were a few terms that needed clarification:

Particle: refers to the trajectory of a target
Cluster: a set of targets with a common trajectory
Particle Filtering: looking at trajectories (particles) over time to determine which nodes are in a cluster. To improve particle filtering accuracy, the algorithm is weighted against changes in velocity.

Although this paper limited itself to one dimension and we all agreed this was not terribly useful, many in class believed the approach could be extended to 2D and beyond. Perhaps the 1D limitation was a product of the need for a simple explanation, although many wanted to know why some results were not given for 2D. After all, if 2D+ is as simple as the paper claims, why not implement it?

Also, the particle filtering algorithm avoids changes in velocity. Although this may be reasonable for tracking certain moving objects, it seemed more likely that objects would change their velocity (people, traffic, birds, etc.).

Finally, we had some questions about how two targets in the same cluster would be counted. Would deviating from a shared trajectory at the same time have a different result than deviating at the same time?

Storage: Capsule and FlashDB

2009-03-16T02:22:00.002-04:00

Capsule: An Energy-Optimized Object Storage System for Memory-Constrained Sensor Devices
Mathur et al.

FlashDB: Dynamic Self-Tuning Database for NAND Flash
Nath and Kansal

The topic of today's discussion was flash storage in wireless sensor networks. The class started by discussing some higher-level issues about storage on motes and about flash storage in general before digging into the specifics of the assigned papers. First, one person questioned the assumption that mote applications are write-intensive. His argument was that motes tend to have low duty cycles, so there is not too much data written after all. In response, one student suggested that the write-intensive classification is based on the read-write ratio instead of basing it on the frequency of writes.

Then, one person questioned the need for advanced storage primitives, such as queues or files, since in practice, most applications use only simple append-only logs. However, some motes store their configuration as files on flash, and filesystem provides a familiar storage abstraction for programmers. If motes supported a filesystem recognized by PC's, such as FAT, we would be able to just pull out an SD card and plug it to a laptop in order to access the data. However, implementing FAT on a mote can be quite challenging, so the network could have few more capable, FAT-enabled motes, which would gather data from other simpler motes.

We were also wondering why we would need a lot of storage on a mote. For example, if the application sampled two sensors every 20 minutes, producing 4 bytes each time, a 2 GB disk would be filled in approximately 20,000 years. Even in the case of data-intensive applications, it would take at least several months in order to fill the disk. Another concern that we discussed was pulling out data once it was collected, since it is effectively impossible to stream several gigabytes of data using the radio. Instead, the users should be able to send queries to motes and retrieve only the data they actually need, which justifies the need for indexes and structured storage in general.

Then, the topic of discussion changed to flash storage and its properties. Someone pointed out that a mote is inherently incapable of efficiently performing updates in place. In order to do so, it must read the entire block to memory before erasing it, which requires more memory than it is found on typical motes. The alternative is to copy the entire block elsewhere in the flash, erase the original block, and then copy it back while performing the requested changes on fly.

In flash, it is possible to turn 0's into 1's without having to erase the entire block. One person suggested that this could be leveraged to change already stored pointers to null pointers if we represent them as FFFF instead of 0000. Another student suggested that the application can leave some of the written data as 0‘s and update it in place later. However, we realized that this would not work, because the flash controllers do not expose the interface for performing such operations.

Finally, our attention turned to Capsule, the first paper assigned for today. The system uses log-structured storage, which seems to be the only reasonable storage model for motes. This approach works well for write-intensive applications at the cost of slow reads. For example, accessing the head of a queue requires the application to traverse it all the way from back to the front. On personal computers, this performance issue is addressed by using large buffers, but on motes, we do not have the luxury to do so.

Most of the remaining discussion of the paper revolved around log cleaning and compaction. Because of the log-based approach, the flash storage can quickly fill up with irrelevant (deleted) data. But in order to use reclaim the space, the log must be compacted due to the must-erase-before-write nature of flash. Compaction, however, takes a lot of energy and time. One of our concerns was that Capsule might start this process even if the client application could be in the middle of a high-rate data capture. Another concern was that when there is nothing to be compacted, the storage component would attempt to do so anyway and just waste energy. Finally, someone pointed out that this scheme effectively allows only 1 GB of storage on a 2 GB device, since it has to leave enough space for compaction.

Towards the end of the class period, we shifted our attention to FlashDB. One of the first observations was that using the B+ tree nodes in the disk modes requires in-place updates, which would not work on typical motes. We highlighted FlashDB's ability to switch the mode of operation online - instead of just determining the appropriate mode before deployment.

We were wondering why we would need the online self-tuning capability until one student suggested an example, in which a mote samples data during the day and streams it to the base station during the night. Ideally, the B+ tree would be in the write-intensive (log) mode during the day and in the read-intensive (disk) mode during the night. However, we were not convinced that FlashDB would make this switch early enough, especially since this dynamics was not evaluated in the paper. Perhaps it would be beneficial if the client application could disable self-tuning and perform it manually.

Data Aggregation: TinyDB, Beyond Average, and Synopsis Diffusion

2009-03-12T10:48:00.003-04:00

TinyDB

(Madden, et al.)

Beyond Average

(Hellerstein, et al.)

Synopsis Diffusion

(Nath, et al.)

Today, we addressed the topic of data aggregation. We began by
exploring the contents of the ACQP and Beyond Average papers. Starting
with ACQP, we were quite pleased to see that the issue of power/energy
consumption was finally being brought to the forefront of a paper
related to sensor networks again (in the previous week, there was a
shared longing for papers that addressed the topic of energy more
directly). Moreover, the ACQP paper presented what one student
suggested was a new "programming model for sensor networks," but, in
particular, was a paradigm of viewing sensor networks as instruments
for scientific studies.

As began to philosophize about this idea, we began discussing the
questions that undergird the distinctions between the systems and
database communities. To a first approximation, we understand that the
systems community tends to approach problems from the bottom-up while
the database community goes from the top-down. A DB example we
discussed regarded the use of query optimizers and other DB internals
to take the declarative statements of a language like SQL and hide the
details of returning the correct answer as quickly and efficiently as
possible. The systems folks in the room tended to agree that we like
to approach problems a (relatively) low-level base.

Ultimately, we were trying to get at the question: Should the system
optimize queries for you? For DB folks, this seemed like a
no-brainer. We even tended to think about the benefits an analogous
(although, not a perfect analogy) of compiler optimization.

But this is where we began to wonder whether the optimizations
presented (e.g., priotization schemes) in this paper seemed
appropriate for sensor networks. While in the compiler analogy,
compilers rearrange instructions but the execution of, say, a
statically-bounded for-loop won't suddenly decided to stop at 10
iterations rather than 20, we questioned the example prioritization
schemes as winavg and delta seemed to defy the correctness that some
sensor network users would desire for their applications. However, we
acknowledged that perhaps specific applications may find those schemes
useful or reasonable, but a skepticism continued to linger on this
point.

Moreover, we felt that the Beyond Average paper might in fact be
breaking the abstraction barrier that it set out to establish
(high-level declarative language - SQL - hiding the underlying details
of sensor network operation). The one example from which this
sentiment emerged was in the Query-Handoff Implementation for tracking
(i.e., Fig 8). The use of SIGNAL EVENT to trigger an ON EVENT
statement appeared a lot like an imperative programming language
method or function call. We weren't certain anymore if the high-level
approach to sensor network application writing was appropriate or
possible after realizing this was what the authors were demonstrating.

In general, we appreciated the abstractions that the DB folks aimed
for but we felt uneasy that this approach to programming sensor
networks would be feasible in the future.

Of course, we also spent some time also examining the Synopsis
Diffusion paper. Mostly, we sought to understand the COUNT algorithm
(which seeks to know how many nodes are present in the network) to
better understand Synopsis Generation, Fusion, and Evaluation. We felt
that there was a little blackbox magic going on for COUNT, especially
in the SE() phase, but we didn't get too hung up on this process.

We seemed to unanimously appreciate the presentation of necessary and
sufficinet properties for ODI-correctness; however, we wished that the
authors would have spent more time discussing how to create
ODI-correct Generations and Fusions.

We had a lot of papers to get through on Tuesday, but each of them
seemed to generate a fair amount of dialogue and interest from the
class, allowing us to explore the range of DB and systems research
philosophy to details of proofs and ODI-correctness.

Time sync and localization: FTSP and Radio Interferometric Localization

2009-03-05T00:06:00.005-05:00

The Flooding Time Synchronization Protocol
Maroti et al.

Radio Interferometric Geolocation
Maroti et al.

Today's discussion was a little different from previous classes
because the two papers weren't on the same topic. So discussion was
largely split into two parts.

Part I: FTSP.

We started off by throwing out some thoughts about our likes and
dislikes. Under the "likes" column, people seemed to agree that FTSP
was a generally useful protocol in that it solved a pratical problem
well (especially, since it produces error on the order of tens of
microseconds). Also, we particularly appreciated the author's
extensive breakdown of the many (ten!) sources of synchronization
error, the magnitudes of each, and their characteristics. The
exposition made it much easier to understand the problem space and
what problem FTSP was trying to solve.

Under the "dislikes" column, people seemed to have some reservations
about the evaluation section since there was no direct evaluation
alongside other synchronization protocols, just comparisons to their
published performance numbers. Along these lines, there were also a
few questions raised about the metrics used to measure FTSP's
performance (we'll get to that a little later).

Root election came up as a discussion topic. It caught our attention
mainly because the root election process was reported to take so long
to converge (17 mins). There was some confusion about what happened
during convergence, when multiple nodes might be considered as root.
The election algorithm maintains time consistency when a root
relinquishes its status to another node with a lower ID, but only if
the algorithm had previously been stable and the nodes were more or
less in sync. However, when the system is boostrapping, clusters in
disjoint parts of the routing tree may have inconsistent times. It
would have been nice if the authors had included some analysis about
how the system behaves during bootstrapping.

The talk about root election brought up a more fundamental question
about whether a root was needed at all. Would it instead be possible
for nodes, in a distributed way, arrive at a global concensus time?
Recent work by the SYRAH group on DESYNC, a distributed concensus protocol modeled on pulse-coupled oscillators,
might serve as a primitive for doing just this.

As we delved deeper into the paper, one major issue that came up was
the authors' evaluation metric of average pairwise error. Since the
whole point of this protocol was to institute a global clock amongst
all the nodes, it would seem more prudent to use a metric that
measured each node's deviation from the global clock. Additionally,
the calculation of the average error per hop seemed strange since it
took the all pairs average error and divided it by the network
diameter.

One alternative to FTSP we considered was a protocol that used time
deltas. The idea would be that each node would measure its time
difference with its parent and that the root could figure out the
clock offset of a node by simply summing the deltas along the path to
that node. The drawback to this is that only the root has a concept
of the global time and that this would make it hard to coordinate
nodes (e.g., "at 10:24:56.000 execute command X"). One could conceivably
send a command from the root like "in 00:10:00.000 execute command X"
and each node would adjust the time according to its own clock
offset. However, this would only work if the time for the message to
propagate to the deepest node was less than the clock skew of any node
along the path. Since we're talking about microseconds, the delta
method may not be feasible.

Part II: Radio Interferometric Geolocation

We started off the discussion of the second paper by again throwing
out our "likes" and "dislikes" about the paper, although there weren't
many "dislikes" to speak of. In particular, people seemed to like the
novelty of the idea and were pleasantly surprised that it was actually
possible to implement. Everyone also seemed to enjoy the fact that
the paper started off with some theoretical underpinnings and then
steadily progressed into a very "engineering" kind of paper
(e.g., dealing with inaccuracy of the radio). It was striking that
nothing about this paper was naive -- there are very important
considerations made for some real world problems that are not
immediately obvious.

One of the highlights of this paper was the method used to defend
against inaccurate radio crystals. The problem they were trying to
solve was that each radio behaved somewhat differently -- when you set
it to emit at a particular frequency, the emitted signal was up to
2kHz from nominal. So the authors built in an automatic calibration
step that involved three nodes: nodes A and B transmitted at close
frequencies f1 and f2. Node B was held fixed at f2 and f1 was varied
until the difference between the frequencies at a third node C was
observed to be minimized. This was pretty clever!

Another clever thing done in this paper was in the measurement of the
frequency and phase offset. Note that what they are sampling is NOT
the carrier frequency. If this were the case, then with a carrier
frequency of approximately 400MHz, the sampling rate would have to be
800MHz -- clearly impossible with an ADC that samples at 9kHz max. So
it was neat that the authors sampled the beat frequency instead --
especially since the two carrier frequencies were close, the beat
frequency was low and easily sampled at 9kHz.

There were some practical considerations that hampered this method.
In particular, the 80 mins it took to localize the nodes seemed a
little onerous, and impossible if nodes were at all mobile. Also, the
experiments were performed in a flat outdoor field, presumably with no
signal interference from other sources. Since this method directly
relies on the radio signal, lack of interference is necessary. This
assumption, however, is not all that realistic. Still, we marvel at
the sheer novelty of the method.

Flush and RCRT: Transporting your data reliably

2009-02-27T17:40:00.002-05:00

Flush: A Reliable Bulk Transport Protocol for Multihop Wireless Networks
(Kim, et al.)

RCRT: Rate-Controlled Reliable Transport for Wireless Sensor Networks
(Paek, et al.)

Today we discussed two protocols that solve the problem of reliable and rate limited transport in wireless sensor networks. First, we discussed the similarities between the two designs and came to the conclusion that both papers use end-to-end NACKS, link-layer ARQ, and provide some sort of mechanism to communicate control information from the nodes. One thing that was not explicitly stated in either of the papers was the different applications for which Flush and RCRT were designed. This addressed some of the skepticism I had about the feasibility of these implementations for general sensor network deployments, since each paper makes assumptions that are not be universally applicable.

I thought the Flush paper somewhat oversimplified the problem of source to sink data transport by accounting for only 1 data flow at any instant. This means that the sink has to directly request data from each source node. While the design works great from a single flow, it also means that all the congestion and rate control information only goes one way: from the source to the sink. There is no mention of the Flush design working in the other direction, and packets from the sink are transported reliably by each node transmitting to the next node in the routing path with ACK confirmation at each step. Flush could probably be modified to handle both directions with some additional overhead.

In the intro, the authors mention that Flush can adapt to varying network conditions. When I first read this, I assumed that Flush would adapt to nodes leaving the network and re-entering or scenarios where the routing path changes. In the evaluation section, I was disappointed to see that the test for adaptability was just having the nodes drop packets at a probability of 0.5 for an interval of 10 seconds. Therefore, the adaptability claim wasn’t properly addressed in terms of node failures, and all other experiments were conducted by freezing the routing tree for every run.

The main discussion point concerning RCRT was the “totalitarian” nature of the relationship between the sink and the network. In other words, when a node’s RTT for repairing a loss exceeds 4, the sink limits the rate of EVERY node by using a multiplicative rule. To bring the network’s rate back up again, every node has to fall below the threshold. We inferred that the authors did this maybe because modifying the rates of each node on an individual basis is too difficult. The network becomes too complex, and it becomes exceedingly difficult for the sink to understand exactly how the nodes affect and interact with each other.

One of the more general philosophical points dealt with the inevitable choice between avoiding congestion and detecting congestion and taking subsequent action. In the RCRT paper, we saw that the network “heals” itself as congestion increases. However, IFRC takes the opposite approach and does what is necessary to prevent the network from being congested. We came to the conclusion that the latter approach will most always lead to better energy utilization because there is never any wasted “effort”. In other words, packet loss leads to the wasted energy since the amount utilized cannot be regained.

Flooding? Trickle and RBP

2009-02-24T21:03:00.006-05:00

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

2009-02-22T12:47:00.002-05:00

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.

2009-02-19T11:31:00.002-05:00

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

2009-02-17T13:38:00.003-05:00

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

2009-02-16T18:08:00.002-05:00

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

2009-02-10T23:59:00.002-05:00

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

2009-02-09T19:11:00.002-05:00

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.

MDW unplugged

2009-02-08T14:28:00.002-05:00

I've decided to start a personal blog where I get a chance to rant and rave about topics dear to my heart, mostly dealing with sensornets, but not necessarily related to this course. For my first post I talk a bit about the relative difficulties of sensor nets research versus other areas of systems. Feel free to check it out and comment.

B-MAC and Taming the underlying challenges

2009-02-06T02:57:00.005-05:00

Versatile Low Power Media Access for Wireless Sensor Networks
(Polastre et al., Sensys 2004)

Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks
(Woo et al., Sensys 2003)

Today we had another round of interesting discussions on another two low level issues in sensor networks: radio channel characteristics and low power MAC design.

We started by talking about what clear channel assessment (CCA) means when used to detect transmissions. CCA tells you when the channel is 'clear' instead of when someone is actually transmitting a packet. The B-MAC showed that using a simple threshold is a poor approach but applying EWMA filter to the CCA result performs reasonably well. Then we discussed hidden terminal problem and benefit/overhead of RTS-CTS scheme as we talked about the comparison of B-MAC and S-MAC. Many of us thought the main difference is configurability. B-MAC exposes more knobs to the application, such as LPL preamble length, check interval and Acks, while S-MAC parameters are not controllable by other layers of the system. The result is higher performance from B-MAC because with application-specific knowledge one can turn on and off these low level features to minimize the overhead of the MAC protocol. On the flip side, this also means that the application programmer needs to know how to turns these knobs that are related to each other. It might seem that each node can tune these parameters dynamically and optimize based on the local conditions. However, it is often not so easy because neighboring nodes need to agree on many of the parameters. For example, you would almost always want the preamble length to be longer than check intervals in order to guarantee waking up of the receiver. Turning on and off Acks could be very confusing too. So, one might ask whether B-MAC is providing too much flexibility and forcing the application to be more complicated.

Another interesting question that was brought up today was: why not use power control, a knob that's there provided by the radio chip? Cell phones do it all the time to save power. Motes should do it too. Lowering transmission power can reduce the size of your neighborhood and therefore possibly increase overall throughput. I think this is an interesting option that hasn't been fully exploited by existing sensor network systems. Or, perhaps it makes higher layers, such as routing protocol, too difficult so people discarded the idea?

In the B-MAC paper, S-MAC was beaten up in almost every metric considered in the paper. With such observation, students asked about how the WSN community usually evaluates MAC protocols. The answer seems to be that every MAC paper chooses different application domains and metrics to show the protocol proposed in the paper performs better than other alternatives but there really hasn't been a complete study to compare them in a standard set of representative environments objectively. Given that so many MAC protocols have been proposed, perhaps it is a good time to do such a study.

One more interesting point that was brought up in class today was: what makes sensor networks a different research area than mobile ad hoc networks (MANET) that has been around for a long time. This is similar to the question we asked on Tuesday on why motes are so different than other computers that it needs new OSes. The papers we read so far mention very little about MANET work while WSN shares some of the challenges with MANET, such as multi-hop routing in wireless networks. I think the distinction still comes from the focus on resource constraints of sensor nodes. MANET community has mostly assumed that the nodes in the network are at least PDA or laptop class of devices. Many of them are even constantly powered (e.g. in military vehicles) so the processing power and energy available to the nodes are plenty. So, MANET research tends to focus on infrastructureless network architecture (no cell tower, no base station), node mobility and dealing with rapid topology changes of the network instead of efficiently managing system resources on the moble nodes. Another distinction is research approach. For example, a lot of MANET research results were derived from simulation based on simple unit-disc model. WSN research community, instead, puts more effort into real experiments to evaluate protocols running on top of real radio.

TinyOS and Great Duck Island

2009-02-03T20:55:00.000-05:00

System Architecture Directions for Networked Sensors
(Hill et al., ASPLOS 2000)

An Analysis of a Large Scale Habitat Monitoring Application
(Szewczyk et al., Sensys '04)

Today was our first proper class and we had a fantastic discussion! Everyone came prepared to talk about the papers, and I think it helped to do a little icebreaking before we got into the discussion itself. I'm really looking forward to the rest of the semester.

I wanted to kick off the class with these two "classic" papers on sensor networks, to help lay the groundwork for the rest of the term. These are great papers, and though I've read them a few times, it is interesting to revisit them now. TinyOS is almost 10 years old, and it's nice to return to the vintage work with some new perspective.

On reading both papers again, I was struck at how low level they both are. The ASPLOS paper really goes bottom-up from the hardware platform and does not indulge in laying out a broader perspective for the field of sensor networks as a whole. Neither paper portends the fetish for complex in-network processing or fancy decentralized algorithms that has taken over much of the community. (I'm one of those fetishists myself, but it's interesting how straight these papers play it.)

We started out talking about what is fundamentally different about sensor networks than conventional computing systems. Most folks seemed to have drunk the TinyOS Kool-Aid and agreed it was all about high concurrency, limited memory, and limited energy. I wanted to press on the point of high concurrency a bit. Aren't ALL computer systems fundamentally concurrent and event-driven? All operating systems are driven by interrupts (keyboard and mouse events, packets coming in, timers going off); are sensor networks really more concurrent than conventional systems? OK, well maybe it has something to do with the lack of buffering, and energy limitations. Now we are getting somewhere - what is fundamental about this? Finally we hit on what I think is essential here: that the limited resources conflate with the concurrency demands to force the programmer to be really "intimate" with their events. You can't hide behind threads or processes anymore: events are part and parcel of what you deal with as a programmer in this domain, so the OS structure had better expose them in a lean and flexible way.

I also wanted to challenge the assumption that motes need to be so small and memory-constrained. Where did this idea come from? The ASPLOS paper more or less assumes it; but if you look carefully at a lot of the potential applications it's not so obvious that you can't get away with, say, a PDA-class device. Strikingly, some of the early design decisions on the mote hardware had some pretty significant impact on the design of TinyOS. My favorite example is that RFM radio, which requires that you bit-bang it to transmit or receive; requiring a context switch every 50 usec (once per bit)! I wonder what would have happened had Jason Hill chosen a better radio or more powerful MCU when he designed the WeC mote. We could be in a very different place today.

But, why the asceticism? TinyOS forces you to tie both hands behind your back and peck at the keyboard with your nose to program... no threads, no sockets, heck, not even malloc or printf. Was this some kind of self-flagellation, doing penance for years of building bigger and faster computers (NOW)?

To understand this lineage one has to go back to the origin of the Berkeley TinyOS effort, which originated with Kris Pister's "Smart Dust" project. That group was developing mm^3 devices integrating extremely simple computation, communication, and sensing. David Culler had the bright idea to build a version of this using off-the-shelf components, to approximate that "plausible future" and study the possibilities enabled by this space. So from the get-go you're talking very resource constrained, and (this is critical) SMALL devices. That fundamental tenet of the sensor network design space was established early on and largely continues to this day; I still see sensor networks based around 16-bit MCUs and the CC2420 when they could just as well use a proper processor and 802.11 radio (for example, if the sensors are powered).

I wouldn't call this merely an academic exercise; but I think we learned a great deal about the fundamentals of this new design space by forcing ourselves to abandon some of our long-held attachments to such luxuries as virtual memory and protection domains. Had we tried to shoehorn PDAs running Linux and make them look kinda, sorta like "sensor networks" I think we would have missed an important opportunity to dig deeper and reveal some essential truths.

Intro slides posted

2009-02-03T11:39:00.001-05:00

For anyone who missed class last Thursday, I've posted the introductory slides for CS263, which summarizes what the class is about (and perhaps more importantly, how you will be graded!).

Welcome to CS263

2009-01-20T14:45:00.001-05:00

This is the official blog for Harvard CS263, Wireless Sensor Networks, a graduate seminar being held in Spring 2009. Click here for the official website for the course. We'll be using this blog as the place to post notes and musings on the papers discussed in the class, as well as for students (and anyone else) to post comments on those discussions.

What is this course all about? Well, we're going to take a tour through some of the best and most influential papers in sensor networking, spanning the last 8 years or so (well, it's a young field). Mostly I want to emphasize how WSNs raise some fundamentally new research challenges in terms of networking, OS design, distributed algorithms, and programming models. We'll also talk extensively about real world applications of sensor nets, from sniper localization to monitoring redwoods, and try to nail down the practical value of some of the more lofty systems research ideas.

The key to this course is going to be discussion on the papers -- this year I am not going to lecture, or even stand at the whiteboard, since that sets the wrong tone. I want everyone to get engaged, which means I'll be limiting enrollment and disallowing laptops in class (imagine!). And this blog is going to be used as a place to capture our discussions, giving them some persistence, and proving a forum for everyone to comment.

(So, let me apologize in advance if you are a coauthor of one of the papers on our syllabus and don't like something that's said about your paper. Just keep in mind that you're on the reading list because I think the paper is really good and worth discussing!)

Really looking forward to the class starting on Jan 29th. If you're so inclined, come join us at 2:30pm in Maxwell Dworkin 221.