Location estimation in sensor networks

From Wikipedia, the free encyclopedia

Location estimation in wireless sensor networks is the problem of estimating the location of an object from a set of noisy measurements, when the measurements are acquired in a distributed manner by a set of sensors.

Contents

[edit] Motivation

In many civilian and military applications it is required to monitor a specific area in order to identify objects within its boundaries. For example: monitoring the front entrance of a private house by a single camera. When the physical dimensions of the monitored area are very large relatively to the object of interest, this task often requires a large number of sensors (e.g. infra-red detectors) at several locations. The location estimation is then carried out in a centralized fusion unit based on information gathered from all the sensors. The communication to the fusion center costs power and bandwidth which are scarce resources of the sensor, thus calling for an efficient design of the main tasks of the sensor: sensing, processing and transmission.

The CodeBlue system[1] of Harvard university is an example where a vast number of sensors distributed among hospital facilities allow to locate a patient under distress. In addition, the sensor array enables online recording of medical information while allowing the patient to move around. Military applications (e.g. locating an intruder into a secured area) are also good candidates for setting a wireless sensor network.

[edit] Setting

Let θ denote the position of interest. A set of N sensors acquire measurements xn = θ + wn contaminated by an additive noise wn owing some known or unknown probability density function (PDF). The sensors transmit messages (based on their measurements) to a fusion center. The nth sensor encodes xn by a function mn(xn). The fusion center applies a pre-defined estimation rule \hat{\theta}=f(m_1(x_1),\cdot,m_N(x_N)). The set of message functions m_n,\, 1\leq n\leq N and the fusion rule f(m_1(x_1),\cdot,m_N(x_N)) are designed in order to minimize the estimation error in some sense. For example: minimizing the mean squared error (MSE), \mathbb{E}\|\theta-\hat{\theta}\|^2.

Ideally, the sensors would transmit their measurements xn exactly to the fusion center, that is mn(xn) = xn. In this settings, the maximum likelihood estimator (MLE) \hat{\theta} = \frac{1}{N}\sum_{n=1}^N x_n is an unbiased estimator whose MSE is \mathbb{E}\|\theta-\hat{\theta}\|^2 = \text{var}(\hat{\theta}) = \frac{\sigma^2}{N} assuming a white Gaussian noise w_n\sim\mathcal{N}(0,\sigma^2). The next sections suggest alternative designs when the sensors are bandwidth constrained to 1 bit transmission, that is mn(xn)=0 or 1.

[edit] Known noise PDF

We begin with an example of a Gaussian noise w_n\sim\mathcal{N}(0,\sigma^2), in which a suggestion for a system design is as follows [1]:

m_n(x_n)=I(x_n-\tau)= \begin{cases} 1 & x_n > \tau \\ 0 & x_n\leq \tau \end{cases}
\hat{\theta}=\tau-F^{-1}\left(\frac{1}{N}\sum\limits_{n=1}^{N}m_n(x_n)\right),\quad F(x)=\frac{1}{\sqrt{2\pi}\sigma} \int\limits_{x}^{\infty} e^{-w^2/2\sigma^2} \, dw

Here τ is a parameter leveraging our prior knowledge of the approximate location of θ. In this design, the random value of mn(xn) is distributed Bernoulli~(q = F(τ − θ)). The fusion center averages the received bits to form an estimate \hat{q} of q, which is then used to find an estimate of θ. It can be verified that for the optimal (and infeasible) choice of τ = θ the variance of this estimator is \frac{\pi\sigma^2}{4} which is only π / 2 times the variance of MLE without bandwidth constraint. The variance increases as τ deviates from the real value of θ, but it can be shown that as long as | τ − θ | ˜σ the factor in the MSE remains approximately 2. Choosing a suitable value for τ is a major disadvantage of this method since our model does not assume prior knowledge about the approximated location of θ. A coarse estimation can be used to overcome this limitation. However, it requires additional hardware in each of the sensors.

A system design with arbitrary (but known) noise PDF can be found in [2]. In this setting it is assumed that both θ and the noise wn are confined to some known interval [ − U,U]. The estimator of [2] also reaches an MSE which is a constant factor times \frac{\sigma^2}{N}. In this method, the prior knowledge of U replaces the parameter τ of the previous approach.

[edit] Unknown noise parameters

A noise model may be sometimes available while the exact PDF parameters are unknown (e.g. a Gaussian PDF with unknown σ). The idea proposed in [3] for this setting is to use two thresholds τ1,τ2, such that N / 2 sensors are designed with mA(x) = I(x − τ1), and the other N / 2 sensors use mB(x) = I(x − τ2). The fusion center estimation rule is generated as follows:

\hat{q}_1=\frac{2}{N}\sum\limits_{n=1}^{N/2}m_A(x_n), \quad \hat{q}_2=\frac{2}{N}\sum\limits_{n=1+N/2}^{N}m_B(x_n)
\hat{\theta}=\frac{F^{-1}(\hat{q}_2)\tau_1-F^{-1}(\hat{q}_1)\tau_2}{F^{-1}(\hat{q}_2)-F^{-1}(\hat{q}_1)},\quad F(x)=\frac{1}{\sqrt{2\pi}}\int\limits_{x}^{\infty}e^{-v^2/2}dw

As before, prior knowledge is necessary to set values for τ1,τ2 in order to have an MSE with a reasonable factor of the unconstrained MLE variance.

[edit] Unknown noise PDF

We now describe the system design of [2] for the case that the structure of the noise PDF is unknown. The following model is considered for this scenario:

x_n=\theta+w_n,\quad n=1,\dots,N
\theta\in[-U,U]
w_n\in\mathcal{P}, \text{ that is }: w_n \text{ is bounded to } [-U,U], \mathbb{E}(w_n)=0

In addition, the message functions are limited to have the form

m_n(x_n)= \begin{cases} 1 & x\in S_n \\ 0 & x \notin S_n \end{cases}

where each Sn is a subset of [ − 2U,2U]. The fusion estimator is also restricted to be linear, i.e. \hat{\theta}=\sum\limits_{n=1}^{N}\alpha_n m_n(x_n).

The design should set the decision intervals Sn and the coefficients αn. Intuitively, we would allocate N / 2 sensors to encode the first bit of θ by setting their decision interval to be [0,2U], then N / 4 sensors would encode the second bit by setting their decision interval to [-U,0]\cup[U,2U] and so on. It can be shown that these decision intervals and the corresponding set of coefficients αn produce a universal δ-unbiased estimator, which is an estimator satisfying |\mathbb{E}(\theta-\hat{\theta})|<\delta for every possible value of \theta\in[-U,U] and for every realization of w_n\in\mathcal{P}. In fact, this intuitive design of the decision intervals is also optimal in the following sense. The above design requires N\geq\lceil\log\frac{8U}{\delta}\rceil to satisfy the universal δ-unbiased property while theoretical arguments show that an optimal (and a more complex) design of the decision intervals would require N\geq\lceil\log\frac{2U}{\delta}\rceil, that is: the number of sensors is nearly optimal. It is also argued in [2] that if the targeted MSE \mathbb{E}\|\theta-\hat{\theta}\|\leq\epsilon^2 uses a small enough ε, then this design requires a factor of 4 in the number of sensors to achieve the same variance of the MLE in the unconstrained bandwidth settings.

[edit] Additional information

The design of the sensor array requires optimizing the power allocation as well as minimizing the communication traffic of the entire system. The design suggested in [4] incorporates probabilistic quantization in sensors and a simple optimization program that is solved in the fusion center only once. The fusion center then broadcasts a set of parameters to the sensors that allows them to finalize their design of messaging functions m_n(\cdot) as to meet the energy constraints. Another work employs a similar approach to address distributed detection in wireless sensor arrays [5].

[edit] External links

  • CodeBlue Harvard group working on wireless sensor network technology to a range of medical applications.

[edit] References

  1. ^ Ribeiro, Alejandro; Georgios B. Giannakis (March 2006). "Bandwidth-constrained distributed estimation for wireless sensor Networks-part I: Gaussian case". IEEE Trans. on Sig. Proc.. 
  2. ^ a b c d Luo, Zhi-Quan (June 2005). "Universal decentralized estimation in a bandwidth constrained sensor network". IEEE Trans. on Inf. Th.. 
  3. ^ Ribeiro, Alejandro; Georgios B. Giannakis (July 2006). "Bandwidth-constrained distributed estimation for wireless sensor networks-part II: unknown probability density function". IEEE Trans. on Sig. Proc.. 
  4. ^ Xiao, Jin-Jun; Andrea J. Goldsmith (June 2005). "Joint estimation in sensor networks under energy constraint". IEEE Trans. on Sig. Proc.. 
  5. ^ Xiao, Jin-Jun; Zhi-Quan Luo (August 2005). "Universal decentralized detection in a bandwidth-constrained sensor network". IEEE Trans. on Sig. Proc..