Lead Investigator

Greg Pottie

Overview

Many applications in sensor networks deal with spatial environmental phenomena. These phenomena are very complicated and not well understood yet. Their modeling is still incorporating much uncertainty. Often the goal of the sensor network is to estimate a spatial field. The common way to achieve it is by a model-based (or parametric) approach where we assume a parametric model and we estimate its parameters from the data. But this approach is problematic since it is based on trusting the model, which might not be close to the true field. Non-parametric estimation is a common approach as well. But it is problematic since it is computationally expensive. For both approaches, placing the sensors in informative locations is essential. We would like to deploy as few sensors as possible. Good techniques for placing the sensors are available and they fall into what is called experiment design.

We are interested in an approach that lies between these two. We would like to place the sensors under uncertainty in the model assumed for the data. We have two opposing goals when choosing locations for sensor placement. First, we want to place sensors such that error in the estimation of the model parameters is small. At the same time, we want to remain robust to uncertainty in our model structure. Three different approaches have been tested for polynomial models of the field of interest

Approach

Experiment design given a model

 Consider the problem of estimating the parameters “a_i” of a polynomial regression model from measurements

   (1)

where e_i is measurement noise. We can rewrite (1) in vector form:

where and . We assume that e_i are independent Gaussian random variables with zero mean and unit variance, and that x₁,…,x_m span Rⁿ⁺¹. In this Gaussian setup the maximum likelihood estimate of a is the minimum variance estimate and is given by the least-squares solution

where X is the matrix whose columns are x_i’s. X is called the design matrix. The resulting estimation error is a Gaussian vector with mean zero and covariance matrix

We can see that the variance depends only on the design matrix X. The covariance matrix C reflects the accuracy of the estimation--the smaller (in some sense) the matrix is, the better the accuracy will be. Now suppose that we can choose the locations “x_i” from a set of plausible locations Z= {z₁,…, z_p}. The experiment design consists of choosing from the set Z the locations “x_i” that are maximally informative. One approach would be to minimize (in some sense) the matrix C. Define m_j to be the number of times we chose the location z_j. Note that we might choose a single location multiple times if it is an especially informative location. Since we are restricted to choosing m locations we get the following equation:

The error covariance matrix can be written now as

Now we can write the experiment design as an optimization problem as follows

This problem formulation results in an NP problem because of the integer constraint on “m_j”. We can relax this integer constraint and get an approximate design. The problem becomes

   (2)

The minimization (2) above is vague since it is a minimization of a matrix. We will introduce a convex scalarization for the problem. The most common scalarization is the D-optimal design where we minimize the log-determinant of the error covariance matrix C. The problem now becomes:

    (3)

which is a convex problem.

There are many other scalarizations (E-optimal, A-optimal, etc...) that minimize different convex functions of the error covariance matrix C, but we will focus on the D-optimal design. The normalized solution of (3) {m_i/m} can be interpreted as the relative frequency of choosing the location z_i. Finally the solution of (3) can be also rounded to get integer values for “m_i”. We notice that this whole formulation does not use the data to find the approximate optimal locations for the sensors. In fact it is assuming that the model we choose to fit in (1) is the true model!

In sensor networks, we face two difficulties regarding the basic formulation presented above:

1. The true model of the data is unknown. 
2. Sometimes different modalities are present on the same sensor and the corresponding processes follow different models; so we would like to find “good” designs (placement of the sensors) for the different models.

Both of these difficulties can be treated by a robust design to modeling errors that will (hopefully) perform well under different model assumptions. We focus on linear (polynomial) models for the ease of the math. We would like to understand how the solution of the optimization problem (3) behaves for different orders of the model. More specifically we focus on designs for two models, a first order polynomial and a second order polynomial in (1). We investigate the relation between the designs for both models. We can easily see that the difference between the two scenarios is the vectors z_i: for the first order model and for the second order model .

First approach:

Under the first order model assumption:

Under the second order model assumption:

where u= and v=[ , ]^T .

Therefore det C₂= det(C₁).det((u-v^T.C₁.v)^-1) which implies           

                 log det C₂=  log det(C₁) - log ((u-v^T.C₁.v))                                              (4)

Equation (4) shows some relationship between the utility functions of the first and second order models, but it is not clear yet if there is any relationship between the designs {m_i} picked by each model.

Second Approach:

The second approach we took is based on the dual problem of (3) which is given by

    (5)

where the domain of E is (the set of positive definite matrices). This dual problem (5) is a Semi-Definite Program (SDP), which is convex in E. It has a nice interpretation: it finds the minimum volume ellipsoid, centered at the origin, that contains the locations z₁,…,z_p. The ellipsoid is given by where is the optimal solution of (5). By complementary slackness we get

    (6)

Equation (6) is a good characterization of the solution: for the optimal m_j^o different from zero chosen by (3), the corresponding locations z_j should satisfy

which means that the locations chosen by the experiment design should lie on the minimal volume ellipsoid that contains the set Z. Now the relationship between the solutions under different model assumptions can be posed from a new perspective derived from equation (6): Given a set of locations Z, how is the second order minimum volume ellipsoid (corresponding to the first order model) containing the set Z related to the third order minimum volume ellipsoid (corresponding to the second order model) containing Z?

The two approaches presented above try to find some sort of a tradeoff between the complexity needed in the model and the accuracy in the estimation. Formulations such as these are interesting since they will help in knowing how much effort we need to refine the model. This effort could be detailed scientific analysis to know how the different variables are related.

Third Approach

The third approach we took deals with the same general idea but from a different perspective. We are trying to find designs, which are “good” for multiple model assumptions. This situation arises, for example, when we are trying to deploy nodes that have multiple sensor modalities (e.g. temperature, light, humidity, etc).  In this situation, we are dealing with different modalities that each has a different model. So the goal of the experiment design is to find locations that result in high accuracy for estimating multiple fields together. We focused as above on polynomial models. We took a Bayesian approach for this problem. We sought good designs by simply minimizing the average of the utility functions corresponding to the different models. We will illustrate the approach in the following example.

Assume that we have nodes that have two sensing modalities situation arises, a temperature sensor and a light sensor. Assume further that the temperature field is a first order polynomial model and the light field is a second order polynomial model. Using a Bayesian approach we can modify the convex program (3) and get

     (7)

which is a convex program. The solution of (7) provides good estimation of both the temperature and light fields. It performs better than the optimal solution, assuming the temperature field model in estimating the light field; and it performs better than the optimal solution, assuming the light field model in estimating the temperature field.

Future Directions

After finding the relationship between the optimal sensor locations and the order of the model, we would like to have hierarchical or sequential procedures for placing sensors over space and time. We believe that such understanding will help in answering interesting questions about the relationship between the complexity of the models and the accuracy of the application needed e.g. how much do I need to know about the phenomenon (modeling complexity) in order to achieve a certain goal with a fidelity requirement? 

People

Faculty:

• Greg Pottie, Electrical Engineering Dept., UCLA

Graduate Students:

• Nabil Hajjchehade, EE Dept., UCLA