Overview

The data collection performance of a sensor network is fundamental to all applications that use the sensor network. It is thus of immediate interest to improve the quality of this data. We are exploring one possible method towards this objective, using controlled mobility in the network. We consider the problem of controlling motion in a distributed manner for a mobile sensor network for a specific form of motion capability. Mobility itself may have a high resource overhead, hence we exploit a constrained form of mobility which has very low overheads but provides significant reconfiguration potential. We have defined a quantitative metric for sensing performance which is concretely tied to real sensor and medium characteristics, rather than assuming an abstract range based model. The problem of determining the desirable network configuration is expressed as an optimization of this metric. We have also developed an optimization algorithm which computes a desirable network configuration, and adapts it to environmental changes. A key property of our algorithm is that convergence to a desirable configuration can be proved even though no global coordination is involved. A network protocol to implement this algorithm has been developed. We have tested our methods both through simulations and experiments on a laboratory test-bed.

Approach

It is important to understand the various tasks required to reconfigure the network in response to medium and phenomenon demands. We divide these tasks into: understanding the medium propagation characteristics, understanding the phenomenon distribution and the motion coordination algorithm. The first two tasks were discussed in previous years report and we focus on the third here.

Systems/Experiments

Several simulations and experiments have been carried out in order to establish the viability of our approach and to test out its various component algorithms. Two example applications were developed to demonstrate the use of our distributed motion control methods and are described below.

The first application focuses on ubiquitous computing domains where several important objects in a user's environment are tagged with visual tags which may be identified from the tag pattern. The recognition algorithms require a high-resolution image of the tag and our actuation algorithms provide that hi resolution image after detecting the presence of a tag using color.

The second application uses motion for the detection phase. We use autoregressive methods to learn the background scene and adapt to changes in the scene. Each image captured is subtracted from the leant background to detect the presence of moving objects.

Figure 1. Motion detection for guiding the actuation.

Figure 1 shows (a) the captured image, (b) the difference image (after subtracting the background) and (c), the filtered difference image to detect the objects of interest, which are marked by blue rectangles. The motion detection methods are affected by the environmental factors such as changes in light levels and presence of noise motion in the scene and we are working on techniques to alleviate these effects.

Both these applications demonstrate ideas that may be generalized to several other applications. For instance a science application may use motion to detect the presence of interesting animal species; a security application may use color to detect faces in a scene and so on.

Accomplishments

The motion control algorithms were implemented on the experimental test-bed to illustrate that the designs work with very realistic system constraints. A computationally tractable algorithm has been designed for optimizing the configuration of the network with respect to a realistic performance metric for the quality of sensing. Unlike most metrics found in prior work that only focus on the extent of coverage, our metric also accounts for the actuation delay as part of the sensing performance since this delay is required to actuate before high resolution coverage can be provided for any event detected within the coverage area. The algorithm is named Incremental Line Search (ILS) based on its characteristic incremental one dimensional search in the design space.

A distributed network protocol has also been developed to realize the coordination required among nodes to implement the distributed optimization algorithm that is used for configuring the network.

The algorithm design was evaluated along three criteria:

1. Convergence: It was shown that the motion control algorithm will always cause the network configuration to converge to a stable state. The convergence property holds under a realistic optimization metric design, with no abstract assumptions on smoothness and differentiability. Further, the distributed operation optimizes a global metric.
2. Goodness of stable state: Simulations were carried out to study if the stable state found by the distributed algorithm is a good one. even though the optimization problem being solved was proved to be NP hard, which makes the determination of a global optimal computationally intractable, our simulations indicate two desirable properties about the stable state discovered by the distributed algorithm:
1. The algorithm performs significantly better than a local algorithm that does not exploit coordination as does our method.
2. Multiple random runs of our algorithm all converge to stable states that have a utility metric within 10% of each other. This indicates that the stable state found by our algorithm is close to global optima. These runs and also the baseline performance for an algorithm without coordination are shown in Figure 1.

1. Speed of Convergence: The time to converge for our distributed motion control algorithm was also studied through simulation and it was found that with the network communication and motion delay characteristics of the hardware used in our prototype, the converge takes the order of a few minutes.

Figure 2. Convergence performance. The dashed line shows the baseline performance of optimization without coordination

Future Directions

The project provides several avenues for future research. The current motion control algorithm is designed to optimize the network configuration such that the detection quality is maximized while at the same time the actuation delay required, when an interesting phenomenon is detected, is minimized. It is of further interest to develop the reactive methods used for actuation after an event of interest is detected and multiple sensors may be actuated to provide high-resolution coverage of that event.

People

Graduate students: Aman Kansal

Faculty Mentors: Mani Srivastava, Gregory J Pottie, William J Kaiser, Gaurav S Sukhatme