NEST: Network of Embedded Systems
The main contribution of this project is the a real-time network coordination and control middleware that abstracts, controls, and ultimately guarantees the desired behavior of large unreliable networks such as those composed of sensors and actuators. Our networks of sensors and actuators differ from the traditional networked systems in that, in aggregate, they must be highly adaptive, must cope with high rates of component failure, mobility, and reconfiguration, and must export a highly configurable set of parameterized services that may involve coordinating a rich set of sensors and actuators in the network core. This functionality will be supported by composable microprotocols that allow behavior specification, perform large-scale component coordination, and export the perception of customized QoS guarantees.
Project Collaborators
The NEST project is funded by DARPA ITO. The members of the real-time computing laboratory at the University of Virginia collaborate closely with the following partners on the NEST project:
- University of Illinois, Urbana-Champaign: Lui Sha, P.R. Kumar.
- Carnegie-Mellon University: Bruce Krogh.
- Lockheed Martin: Denny Adams
Technical Overview
It will soon be possible to develop, economically, large numbers of small smart components that combine computing power, wireless communication capabilities, and specialized sensors and actuators. These components or nodes may be deployed in thousands to achieve a common mission. They may be used to monitor poorly accessible or dangerous environments such as the ocean floor, neighborhoods of volcanic activities, hostile territories (e.g., behind enemy lines), disaster areas, and nuclearly active fields. They may also be deployed to accomplish interactive tasks such as finding and detonating enemy mines, looking for survivors of natural disasters, or containing and isolating oil spills to protect a nearby coastline. The new technology creates a different set of challenges arising from the fact that:
- Nodes are embedded into a geographic landscape and interact tightly with the physical environment.
- Nodes are smaller and less reliable than traditional network routers.
- Nodes generate (and possibly store) data from sensors unlike traditional routers.
- Nodes may be mobile.
What is needed is a new set of software tools and protocols to enable effective programming and usage of such networked embedded computing systems.
Programming Paradigm
Many of the functions performed by the net will require replication. For example, measuring temperature gradients in a certain neighborhood, monitoring the progression of a moving object, storing a variable amount of information about a monitored activity, etc. In some sense, the coverage or the quality with which the function is performed may depend on the degree of geographic replication of this function. This is somewhat analogous to the way locally-acting microorganisms cooperate to achieve tangible effects on a larger scale.
Our main abstraction exported by the OS to the application programmer is that of Microcells. Microcells are the equivalent of tasks in traditional operating systems. Microcells begin their life-cycle as inactive software components with a specific application-dependent function (implemented by microcell code). They may initially reside on randomly selected host nodes until activated. Microcells are activated by stimuli in the environment, as well as by events in the computing system (such as specific changes in resource utilization). Once a microcell is activated, the stimulus of interest can cause it to perform self-replication, migration, or grouping. The mechanisms for microcell replication, migration, and coordination are supplied by the underlying software infrastructure. The description of activating stimulae are a part of microcell specification. Control-theoretical techniques will be used to control microcell replication (i.e., growth). For example, growth may be controlled to reach the required computing capacity or geographic coverage for different functions performed in the vicinity of an event of interest. The right code and data repositories will thus populate the right geographic neighborhoods to minimize internode communication and maximize the utility of the network (e.g., maximize its capacity to collect and process information from the physical environment).
The programmer needs only to supply the microcell and a description of its stimulae. The rest (including which microcells to execute, when to execute them, where, and on how many nodes) is undertaken by the operating system in response to environmental state. The system implements its own microcells which are called system services. Such services implement fundamental activities in the infrastructure, such as information storage (caching).
Node Architecture
- Feedback Control Resource Management: The main departure of resource management mechanisms in the proposed OS lies in their adaptivity. Resource allocation is not static, but rather guided by control-theory-based correction algorithms that employ feedback to achieve the desired state. The module uses feedback to dynamically resolve optimization problems involving power consumption, CPU allocation, communication, and physical location.
- Aggregate QoS Management: An interesting challenge is to produce the desired behavior from the sum of independent operations of locally interacting components. This module is responsible for setting the aggregate QoS goals and translating them into parameters that control local node interaction.
- Local Routing: Traditional routing algorithms rely on unique names (such as IP addresses) to find the addressed destination. In a large number of small redundant computing devices, management of unique names can become highly inefficient. Instead, local names will be used that are unique with high probability in a given local neighborhood. New routing techniques will be developed for approximate neighborhood specification, and for node location within a neighborhood.
- Event/Landmark Addressable Communication: In everyday life we often communicate location implicitly by using landmarks or events as points of reference rather than GPS coordinates. For example, "I'll see you at the presentation", or "meet me on the hill". Since our network is embedded in a physical environment, we believe that the more natural way to locate neighborhoods is by sensor-detected landmarks or events. For example, "measure radiation in the vicinity of Object A". Here "Object A" (which may be mobile) implicitly defines a location. The communication is intended to that dynamic neighborhood and not to any particular node address. Our communication subsystem will support this type of communication as one of its main abstractions.
- Team Formation: In some sense, team formation addresses the reciprocal problem to consensus. Consensus refers to having all those who are members of a group agree on a given state. Team formation refers to letting all those who agree on a given state be members of the same team. The team may be dynamic. For example, its members may be all those nodes who are within 300 yards from some moving target, X.
- Microcell Management: This component controls the behavior of microcells such as activation, replication, and migration. Microcells are the main abstraction supported by our operating system. It replaces the traditional abstraction of a task.
Local Services
One of the main thrusts of the project is the development of middleware services for coordination in deeply embedded device networks to bridge the gap between sensors and actuation.
- Information caching: This service implements distributed storage that keeps track of important state in the network. The service is implemented as a special-purpose microcell that is activated by the changes in sensor measurements, as well as by increases in communication traffic. Hence, fast-acting events as well as network congestion will increase the caching activity in the neighborhood of those events which is consistent with our desire to store the produced information and reduce communication.
- Clock Synchronization: Many fundamental issues may need to be revisited in developing clock synchronization an unreliable wireless ad hoc environment.
- Group Membership: We shall develop membership algorithms for highly dynamic groups. Those groups may be formed in response to events in the environment such as the presence of intruders. They will be dynamic (e.g., to track the intruder), and defined not only by the communication substrate, but also by the I/O status. In other words, sensed conditions in the physical environment may define who is in the group. We shall also develop protocols for partial membership. A node can be a member of a group to a fractional degree. The fraction specifies the degree of "loyalty" of the node to the group which permits creating, representing, and controlling gradient relations (e.g., the closer the node to the target the more time it should devote to the task of monitoring).
- Distributed Control: Actuators may exert distributed control on the environment. The control signals are coupled in that the effect of one actuator may interfere with the effects of another in the same vicinity. Distributed middleware will be written to coordinate actuator activity.
- Location Services: In some applications, nodes should be location aware. Since it is very costly to add GPS to each node, in general nodes would have to infer their location from the known locations of a handful of base-stations. Triangulation techniques will be developed to propagate location awareness among all nodes.
- Testing Tools: Debugging software for deeply embedded networks is not an easy tasks. One of the directions of this project is on developing distributed testing and debugging tools.
- Monitoring Services: Convenient visualization of the state of the monitored and controlled environment is an important part of the interface between deeply embedded networks and human agents. A suite of monitoring, visualization and control services will be developed to interface the human to the network.
Software Release: VigilNet
A robust, self-organizing, wireless sensor network system for long-term, persistent surveillance, involving detection, tracking, classification, and identification of vehicle and personnel targets over various types of terrain (Consists of 40,000 lines of code running on XSM, MICA2 devices and fully integrated with other sophisticated sensors and backend systems).
More Information
More information about the sensor network project can be obtained from our publications and slide presentations.