Kamin Whitehouse :: Projects

Research Publications Misc
Localization Our work in localization has several components:
  • hardware and software for acoustic and ultrasonic ranging on the mica and mica2 motes
  • large collections of acoustic, ultrasound, and RF ranging data from multiple different environments
  • a simulator called "silhouette" that simulates a localization deployment given an empirical ranging profile
  • comparison of empirical ranging data with theoretical models
  • analysis of dozens of localization deployments (under submission)
  • sensitivity analysis of several localization algorithms to ranging irregularities in various empirical profiles (in progress)
The schematics, data, code, paper and presentation for this project are freely available.
Semantic Streams One of the largest remaining obstacles to the widespread use of sensor networks is the interpretation of the sensor data; users must be able to query for high-level facts about the world, not just raw ADC readings. We designed a framework called Semantic Streams which allows users to pose declarative queries for semantic values, such as "the speeds of vehicles near the entrance of the parking garage." The system combines logical inference with AI planning techniques to compose a sequence of inference units, which are stream operators that perform a minimal amount of sensor fusion or interpretation on incoming event streams and incorporate newly inferred semantic values into outgoing event streams. Both the sensor network and the inference units are logically described in Prolog and the system can reason about which sensors in space to use and whether the inference units are being used in an appropriate world context. Typically, multiple combinations of sensors and inference units can answer the same query, so users can also declare QoS constraints in CLP(R) notation to choose between logically equivalent inference graphs, for example: "the confidence of the speed estimates should be greater than 90%." or ``I want to minimize the total number of radio messages.'' This work is patent pending. The paper, poster, and presentation are freely available.
Hood: a Distributed Programming Abstraction Traditional distributed programming abstractions such as shared memory are difficult to apply to sensor networks because of the unreliable, low-bandwidth, geographically-constrained communication model. Instead, many distributed sensor network algorithms are based on the concept of a neighborhood in which each node selects a set of important neighbors and maintains state about them. However, programmers must still implement neighborhoods in terms of their component parts: messaging, data caching, and membership. We developed an abstraction called Hood that unifies these fundamental concepts as a distributed programming primitive for sensor networks. Using Hood, a neighborhood can be defined by a set of criteria for choosing neighbors and a set of variables to be shared, such as a one-hop neighborhood over which light readings are shared and a two-hop neighborhood over which both locations and temperature are shared. Once the neighborhoods are defined, Hood provides an interface to read the names and shared values of each neighbor. Beneath this interface, Hood is hiding the complexity of discovery and data sharing. We have shown that this abstraction captures the common usage of neighborhoods in many publicly available sensor network applications, and it has been used to implement some of TinyOS's largest applications. The code, documentation, paper and presentation for this work are freely available.
Marionette: Embedded Wireless Debugging A main challenge to developing applications for wireless embedded systems is the lack of run-time visibility and control. We developed a tool suite called Marionette which provides an interpreter through which the network operator can remotely call the node's functions, read and write its variables, and access its enumerations and data structures. This interactive and scriptable environment allows the developer to seamlessly trade off between between writing application logic on the PC for simplicity and debugging or writing it on the nodes for increased efficiency. This greatly eases the development process and we have shown that this tool suite can reduce code size in several existing applications by up to 75%. Marionette is actively being used for development on several testbeds of up to several hundred nodes. Marionette builds upon my earlier work on the Matlab/TinyOS development environment, which has been in the main TinyOS distribution for years. The code, screenshots, documentation and presentation for this project are freely available.
Calibration Instead of using a single, highly-engineered sensor, sensor networks monitor the world through hundreds of cheap, assembly-line components. Many such devices have poor factory calibration and drift over time during use. Because sensor networks can contain thousands of such sensors and can be influenced by the environment, they should be self-calibrated after deployment. Unfortunately, pairing each sensor with an actuator to provide a known stimulus does not solve this problem because the actuators must also be calibrated. We developed a technique in which, instead, each node calibrates its sensor using the actuators of all of its neighbors. This creates an over-constrained system from which calibration coefficients can be inferred even in the face of some noise from both the sensors and actuators. We demonstrated the calibration technique on a 36 node testbed with microphones and acoustic actuators. The code, paper and presentation for this project are freely available.
Mutation Routing One of the biggest challenges in a distributed tracking application such as the Pursuer-Evader Game (PEG) is mobile-mobile routing: routing from a source node to a destination while both are changing location in the network topology. Mutation Routing is an algorithm that finds a route once and then mutates it when nodes move. The algorithm can be proven never to mutate to an inconsistent state and, because mutation eliminates the need for control message and new route discovery overhead, it increases the overall bandwidth on the route. One disadvantage to this algorithm, however, is that routes can mutate to sub-optimal, snake-like patterns. Mutation routing therefore trades energy-efficiency and latency for higher bandwidth and lightweight route maintenance. Current work is investigating hybrid routing algorithms that can choose the ideal operating point in this tradeoff. The poster and presentation are freely available.
Collision Detection and Recovery Besides complex techniques like CDMA, most wireless MAC protocols today lose packets during collisions and cannot differentiate between packet collisions and channel noise. Therefore, they unnecessarily avoid simultaneous transmission even though many radios exhibit the Capture Effect, which is the ability to correctly receive a strong signal from one transmitter despite significant interference from other transmitters. We developed a technique to exploit this effect to cheaply detect and recover from packet collisions using only simple, low-power radios that are commonly used in sensor networks. This technique differentiates between collisions and channel noise, recovers one of the packets entirely, and can often identify both transmitters that were involved in the collision. This allows MAC protocols to be more aggressive by transmitting while neighbors are also transmitting; if a collision occurs, one of the packets will actually get through and feedback can be used to request the lost packets and/or to prevent such collisions in the future. We demonstrated the collision detection and recovery technique on a 28 node testbed and current experiments with new MAC protocols are showing up to 30% gains in bandwidth and latency. The code, paper and presentation for this project are freely available.

Kamin Whitehouse
Computer Science Department
The University of Virginia
217 Olsson Hall
Charlottesville, Virginia 94720