Location estimation in sensor networks

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Motivation[edit]

Many civilian and military applications require monitoring that can identify objects in a specific area, such as monitoring the front entrance of a private house by a single camera. Monitored areas that are large relative to objects of interest often require multiple sensors (e.g., infra-red detectors) at multiple locations. A centralized observer or computer application monitors the sensors. The communication to Power and bandwidth requirements call for efficient design of the sensor, transmission, and processing.

The CodeBlue system[1] of Harvard university is an example where a vast number of sensors distributed among hospital facilities allow staff to locate a patient in 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.

Setting[edit]

LocationEstimation WSN.JPG

Let \theta denote the position of interest. A set of N sensors acquire measurements x_n = \theta + w_n contaminated by an additive noise w_n owing some known or unknown probability density function (PDF). The sensors transmit measurements to a central processor. The nth sensor encodes x_n by a function m_n(x_n). The application processing the data 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 to minimize estimation error. For example: minimizing the mean squared error (MSE), \mathbb{E}\|\theta-\hat{\theta}\|^2.

Ideally, sensors transmit their measurements x_n exactly to the processing center, that is m_n(x_n)=x_n. 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 m_n(x_n)=0 or 1.

Known noise PDF[edit]

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 \tau is a parameter leveraging our prior knowledge of the approximate location of \theta. In this design, the random value of m_n(x_n) is distributed Bernoulli~(q=F(\tau-\theta)). The processing center averages the received bits to form an estimate \hat{q} of q, which is then used to find an estimate of \theta. It can be verified that for the optimal (and infeasible) choice of \tau=\theta the variance of this estimator is \frac{\pi\sigma^2}{4} which is only \pi/2 times the variance of MLE without bandwidth constraint. The variance increases as \tau deviates from the real value of \theta, but it can be shown that as long as |\tau-\theta|\sim\sigma the factor in the MSE remains approximately 2. Choosing a suitable value for \tau is a major disadvantage of this method since our model does not assume prior knowledge about the approximated location of \theta. 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 \theta and the noise w_n 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 \tau of the previous approach.

Unknown noise parameters[edit]

A noise model may be sometimes available while the exact PDF parameters are unknown (e.g. a Gaussian PDF with unknown \sigma). The idea proposed in [3] for this setting is to use two thresholds \tau_1,\tau_2, such that N/2 sensors are designed with m_A(x)=I(x-\tau_1), and the other N/2 sensors use m_B(x)=I(x-\tau_2). The processing 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 \tau_1,\tau_2 to have an MSE with a reasonable factor of the unconstrained MLE variance.

Unknown noise PDF[edit]

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 S_n 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 S_n and the coefficients \alpha_n. Intuitively, we would allocate N/2 sensors to encode the first bit of \theta 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 \alpha_n produce a universal \delta-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 \delta-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 \epsilon, 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.

Additional information[edit]

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]

External links[edit]

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

References[edit]

  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.