Distributed adaptive sensor networks are reactive computing systems, well-suited for tasks in extreme environments, especially when the environmental model and the task specifications are uncertain and the system has to adapt to it. A collection of active sensor networks can follow the movement of a source to be tracked, for example a moving vehicle, it can guide the movement of an object on the ground, (for example a surveillance robot,) or it can focus attention over a specific area, (for example in the case of a fire we would like the sensor network to localize its source and track its spread.) Our goal is to design, build, analyze, and test reactive sensor networks that employ the principles of self-organization and self-assembly to combine structure with function. To this end, we have built a physical sensor network consisting of 50 Mote nodes and algorithmic routing, planning and control support that will allow its units to dynamically and automatically configure themselves into a variety of network configurations in response to environmental changes and in support of different tasks.
Sensors detect information about the area they cover. They can store this information locally or forward it to a base station for further analysis and use. Sensors can also use communication to integrate their sensed values with the rest of the sensor landscape. Users of the network (robots or people) can use this information as they traverse the network. We illustrate this property of a reactive sensor network in the context of a guiding task, where a moving object is guided across the network along a safe path, away from the type of danger that can be detected by the sensors.
The guiding application can be formulated as a robotics motion planning problem in the presence of obstacles. The interesting areas of the sensor network are those where sensors have triggered. They can be represented as obstacles. Such areas may include excessive heat (from volcanoes, fire, etc), people, etc. We assume that each sensor can sense the presence or absence of such an event. An event configuration protocol run across all the nodes of the network creates the event map. We do not envision that the network will create an accurate geometric map, distributed across all the nodes. Instead, we wish for the nodes in the network to provide some information about how far from the event each node is. If the sensors are uniformly distributed, the smallest number of communication hops to a sensor that triggers ``yes'' to the event is a measure of the distance. The goal is to find a path for the moving object that moves toward the events (or avoids them, depending on the application.) The user may ask the network regularly for where to go next. The nodes within broadcasting range from the user supply the next best step.
Inspired by robotics motion planning, we developed several protocols for the distributed guidance problem across sensor networks and reported the details of these algorithms in a paper that has just been accepteed by Mobicom 2003. The map can be constructed incrementally and adaptively as an artificial potential field using hop-by-hop communication. The ``obstacles'' correspond to events and have repulsing values and the goal has an attracting value. The potential field is computed in the following way. Each node whose sensor triggers ``event'' diffuses the information about the event to its neighbors in a message that includes its source node id, the potential value, and the number of hops from the source of the message to the current node. This message is used to update the potential value at the current node. The node then broadcasts a message with its new potential value and number of hops to its neighbors.
The potential field information stored at each node can be used to guide an object equipped with a sensor that can talk to the network in an on-line fashion. The safest path to the goal can be identified with a distributed protocol using dynamic programming. In our Mobicom 2003 paper we prove that our algorithm does not get stuck in local minima. A user of the sensor network can get continuous feedback from the network on how to traverse the area. The user asks the network for where to go next. The neighboring nodes reply with their current values. The user sensor chooses the best possibility from the returned values.
The navigation guidance application is an example of how simple nodes distributed over a large geographical area can assist with global tasks. This application relies on the ability of the network user to interact with the network as a whole and with specific nodes in the network. This interaction is directed at retrieving data from the network (such as collecting local information from individual nodes and collecting global maps from the network) and injecting data into the network (such as configuring the network with a new task or reprogramming its nodes).
The ability to re-task and reposition sensors in a network by sending state changes or uploading new code greatly enhances the utility of such a network. It allows different parts of the network to be tailored to specific tasks, capabilities to be added or changed, and information to be stored in the nodes in the network. When robots or people interact with the network, the sensors become an extension of the user capabilities, basically extending their sensory systems and ability to act over a much large range.
We have developed and built a hand-held device that allows a user of the network (a human or a robot) to interact with the network as a whole or to talk to individual nodes in the network. This device is called a sensory Flashlight and is based on the optical flashlight metaphor. When pointed in a specific direction, the Flashlight collects information from all the sensors located in that direction and provides its user with sensory feedback. The device can also issue commands to the sensors in that direction.
Applications of the Flashlight device for interacting with the sensor network include: (1) Guiding robots or people along paths that may change over time; (2) Reconfiguring a wireless sensor network in a patterned way; (3) Interacting with a wireless sensor network, both consuming and providing information stored within the network, changing and reacting to its topology, re-tasking the network; (4) Invisible markup of a geographic region with information; (5) Sensor management; and (6) Efficiency improvements in message routing.
We have examined the application of these resulting routing algorithms in the context of a tracking task and presented our results in a paper recently accepted by the 2003 ACM SensSys conference. More specifically, we investigated the computational power of sensor networks in the context of a tracking application by taking a minimalist approach focused on binary sensors. The binary model assumption is that each sensor network node has sensors that can detect one bit of information and broadcast this bit to a base station. We examine the scenario in which the sensor's bit is whether an object is approaching it or moving away from it. We analyzed this minimalist binary sensor network in the context of a tracking application and show that it is possible to derive analytical constraints on the movement of the object and derive a tracking algorithm. We also showed that a binary sensor network in which sensors have only one bit of information (whether the object they sense is approaching or moving away) will give accurate predictions about the direction of motion of the object but do not have enough information content to identify the exact object location. For many applications predicting directional information is enough--for example in tracking a flock of birds, a school of fish, or a vehicle convoy. However, it is possible to pin down the exact location by adding a second binary sensor to each node in the net. If we include a proximity sensor that allows each node to report detecting the object in its immediate neighborhood we can determine the direction and location of the moving target.
This minimalist approach to sensor networks gives us insight into the information content of the tracking application, because it gleans the important resources for solving this task. By studying minimalist sensor networks we learn that the binary sensor network model with one bit gives reliable direction information for tracking, but an additional bit provided by a proximity sensor is necessary to pin down exactly the object location.
Our tracking algorithms have the flavor of particle filtering and make three assumptions. First, the sensors across a region can sense the target approaching or moving away. The range of the sensors defines the size of this region which is where the active computation of the sensor network takes place (although the sensor network may extend over a larger area.) The second assumption is that the bit of information from each sensor is available in a centralized repository for processing. This assumption can be addressed by using a simple broadcast protocol in which the nodes sensing the target send their id and data bit to a base station for processing. Because the data is a single bit (rather than a complex image taken by a camera) sending this information to the base station is feasible. Our proposed approach is most practical for application where the target's velocity is slower than the data flow in the network, so that each bit can actually be used in predictions. However, since the accuracy of our trajectory computation depends on the number of data points, the predictions are not affected by the velocity of the target relative to the speed of communication. The third assumption is that an additional sensor that supplies proximity information as a single bit is available. Such a sensor may be implemented as an IR sensor with thresholding that depends on the desired proximity range, and can also be derived from the same basic sensing element that provides the original direction bit of information.
The tracking application and many other sensor network applications require that the sensors in the network agree on the time. A global clock in a sensor system will help process and analyze the data correctly and predict future system behavior. For example, in the vehicle tracking application, each sensor may know the time when a vehicle is approaching. By matching the sensor location and sensing time, the sensor system may predict the vehicle moving direction and speed. Without a global agreement on time, the data from different sensors cannot be matched up. Other applications that need global clock synchronization include environment monitoring (for example, temperature), navigation guidance, and any other application that requires the coordination of locally sensed data and mobility. Clock synchronization may also help to conserve energy in a sensor network, by allowing a coordinated way to set nodes into sleeping mode. This leads to more complex communication since a node must compute when to wake up to receive a message.
In a paper just submitted to Infocom 2004 we discussed three methods for global synchronization in a sensor network: (1) the all-node-based method, (2) the cluster-based method, and (3) a fully localized diffusion-based method. The all-node-based method assumes the transmission time of a packet across a hop is the same for all nodes. It uses a packet to go around a cycle that is composed of all the nodes in the network and amortizes the packet transmission time on the cycle to each hop. This method does not scale well because it requires the nodes in the whole network to participate in the synchronization process at the same time. To address the scalability issue, we propose a hierarchical method. We use clusters to organize the whole network. The cluster head nodes are synchronized by using the first method and in each cluster the members are synchronized with the cluster head. These two methods are not localized; each synchronization process involves all the nodes in that network partition. To achieve full scalability, we propose a fully localized diffusion-based method with both synchronous and asynchronous implementations, in which each node exchanges and updates information locally with its neighbors. No global operations are required. In the synchronous rate-based algorithm, neighboring nodes exchange clock reading values proportional to their clock difference in a set order. To make our implementation more practical, we propose two asynchronous implementations, in which a node can synchronize with its neighbors at any time in any order. The asynchronous algorithms can also adapt to node failure, adverse communication channel, and node mobility.
Although our algorithms are aiming at solving the synchronization problem in a sensor network, they can be easily extended to the data aggregation problem, e.g., finding the average, highest, and lowest sensor data reading among all the sensors in the whole network. For example, in the all-node-based algorithm, the reading of a sensor can be attached to the message when the message used in the all-node-based synchronization is going along the cycle composed of all nodes. The sum of the readings (thus the average reading), the highest, and lowest reading over the whole network can be computed post hoc or on the fly. The diffusion-based algorithm is straightforward to be extended as well as we will see below.