Lead Investigator:

Gaurav Sukhatme

Overview

We consider the problem of deploying a sensor network that provides a required quality of sensing coverage while minimizing overall communication cost. Our approach is to decouple the sensing and communication problems by first finding the smallest set of node locations that provide adequate sensor coverage, followed by augmentation of the network with a small number of additional radios to decrease overall communication cost. To address the non-idealities caused by environmental factors, sensing and communication models are constructed empirically based on data collected in the field. Results from deployment of a low-power camera network in a complex, outdoor environment show that this decoupled, data-driven strategy works well in practice. While the above deployment and node augmentation algorithms are centralized, our current focus is on extending them to distributed, iterative node repositioning algorithms.

Approach

Sensor network deployments must meet application-specific sensing and communication requirements. Further, it is desirable that these requirements be fulfilled by an efficient use of resources (e.g. using as few nodes as possible). In complex, outdoor environment, sensor network deployment is difficult because ideal models for sensing and communication are inaccurate thus limiting their utility, non-ideal behavior due to environmental factors is difficult to model, and the (few) useful models that are available are rarely simple geometric shapes, making the problem of optimal sensor placement NP-hard. Our approach is as follows. We first consider the sensing coverage problem alone and find the smallest set of node locations that provide sensor coverage. Once an optimal sensor placement is found, we study and model the communication links of the resulting network. Using these models, we find a minimal set of node additions that result in significantly decreasing the communication cost of the overall network. An important feature of our work is that we do not assume ideal models for either sensing or communication. Instead, we build empirical models based on data collected in the field. The empirical model of communication links is a function of the set of node locations; changing the location of a node not only affects its links but also of its set of 1-hop neighbors. It is extremely impractical to explore a large number of combinations of node locations and choose the best one. Our decoupled, two-phase strategy has the advantage that once the link models are formed for the network induced by the optimal sensor placements, the node displacement is minimal. This makes it a very practical approach for real deployments.

Systems/Experiments

We address the following general problem: Given a bounded domain, find a deployment with the minimum number of sensors equipped with radios, such that (a) each point in the domain is covered by at least one camera and (b) the communication  cost for a pre-defined task is less than a given threshold.  The specific application we consider is detection of motion along a path in an outdoor environment. A point on the given path is said to be covered if any motion at that point can be reliably detected by at least one camera. The communication cost is measured in terms of the number of transmissions required to reliably transmit data. We decouple the above problem as follows:

1. Sensor-centric Placements: Given a path of arbitrary complexity, find an arrangement of limited-view cameras that minimizes the number of cameras while ensuring that every point in the path is covered by at least one camera.
2. Communication Augmentation: Given a deployed set of wireless nodes with characterized link data, models, and power model, is there is set of k additional positions for radios such that the number of transmissions in the network is less than a given cost threshold.

The Cyclops camera sensor couples with a Mote and consists of a CMOS imager with CIF image capability and an internal image processor unit for image interpretation and analysis.  The detection range also depends on occlusions in the environment and luminance. It is possible to model occlusions by surveying and mapping the obstacles. However, luminance is very hard to model. To address this, we sample a sufficiently large number of points along the path, characterize the detection algorithm at these point (averaged over various lighting conditions) and given a new point, estimate the detection range based on the closest available sampled point. Table 5 shows the detection range estimates based on data collected at 14 points 5 along the path The problem of finding the minimum number of cameras to cover the path is equivalent to the art-gallery problem which is NP-hard [2]. We consider a simplified version of the problem by assuming that cameras are placed parallel to the path. If the path is simple, i.e. it does not intersect itself, then path coverage is equivalent to 1D set cover which can be solved optimally using Algorithm GreedyCover which finds the optimal set of camera locations S given the path P and location dependent sensing coverage ranges C. If the path intersects itself, the number of excess cameras returned by the algorithm will, in the worst case, be equal to the number of intersections.

The key challenge in the camera deployment problem above is that the sensing range is a function of the cameras location. Such location-dependent sensing models have not be addressed in existing coverage literature. We propose the following generalized framework: Given a bounded convex region, Q, and locations of n sensors p = {p1, p2, ..., pn} such that the sensing performance of each sensor i at point q is given by f(pi, q), maximize the average coverage

Given a sensor network deployed according to the sensing requirements, we collect communication data and construct two link models. The first model characterizes individual links in terms of the average number of transmissions required for a single packet communication. The second model predicts the required number of transmissions for direct communication between the radios at a given distance. The model does not just deduce the most likely communication cost but also provides the probability that a link at a given distance will have a particular communication cost. The major technical problem associated with the task of adding radios for the reduction of communication cost is the identification of regions where the new radio would not just locally reduce communication cost, but also the overall cost. To achieve this, we map the nodes into a new space, named the communication space. In the communication space, the nodes are positioned in such a way that the distances between the nodes corresponds to the required number of transmissions for the shortest path communication between any two nodes.

Accomplishments

Our work makes contributions on three fronts. First, we develop a decoupled, practical method for sensor deployment which has good sensor coverage performance at low communication cost. Second We provide a centralized, optimal algorithm for path coverage based on 1D Set Cover and demonstrate its efficiency for a network of low-power cameras in a complex, outdoor environment (fig. 1). Based on this, we propose a generalized framework for sensor location optimization where the performance of a sensor is a function of its location. Initial results in simulation indicate that for path coverage, near optimal node configurations can be achieved using a local greedy heuristic. Third, we describe algorithms to a. model and predict packet reception rates online, and b. reduce the communication cost of a deployment by adding radios.

Future Directions

We have addressed the problem of effective and parsimonious sensor network deployment. Sensor network deployment is a challenging problem because of the discrepancies between ideal sensing (and communication) models and reality, the difficulty of modeling non-ideal behavior due to environmental factors, and the fact that useful models are rarely simple geometric shapes, making the problem of optimal sensor placement NP-hard. While one can view deployment as a constrained joint optimization problem, it is clear that for several interesting combinations of sensors and radios, joint sensing and communication optimization is overkill. We have proposed a decoupled, sequential approach which first considers the sensing coverage problem independently, and finds the smallest set of node locations that provide sensor coverage. Specifically, we have shown how to do this with cameras, by treating coverage as a target detection problem. Once an optimal sensor placement is found, we exhibit an algorithm to find a minimal set of node additions that result in significantly decreased communication cost of the overall network. We show that in poorly connected networks, additional nodes are necessary and sufficient for acceptable communication at low cost. Experiments in simulation and with a real deployment in a botanical garden validate our approach. In future, we want to extend these algorithms to distributed versions where the sensing and communication models are constructed locally and in real-time so that the nodes can iteratively reposition themselves and converge on an optimal configuration.

People

Faculty:

• Gaurav Sukhatme, Computer Science/Electrical Engineering, UCLA
• Daniela Rus, Computer Science, MIT
• Miodrag Potkonjak, Computer Science, UCLA
• Deborah Estrin, Computer Science, UCLA

Graduate Students:

• Sameera Poduri (USC)
• Ajay Deshpande (MIT)

External Research Partnerships

MIT CSAIL (current)