|
|
||||
|
|
|
|||
| Localization |
Our work in localization has several components:
|
|||
| 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 |