Location estimation in sensor networks

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{{cite web|url=http://www.eecs.harvard.edu/~mdw/proj/codeblue/ |title=Archived copy |accessdate=2008-04-30 |url-status=dead |archiveurl=https://web.archive.org/web/20080430133030/http://www.eecs.harvard.edu/~mdw/proj/codeblue/ |archivedate=2008-04-30 }} 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.

Image:LocationEstimation WSN.JPG

Let $\backslash theta$ denote the position of interest. A set of $N$ sensors

acquire measurements $x\_n\; =\; \backslash 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 $n$th sensor encodes

$x\_n$ by a function $m\_n(x\_n)$. The application processing the data applies a pre-defined estimation rule

$\backslash hat\{\backslash theta\}=f(m\_1(x\_1),\backslash cdot,m\_N(x\_N))$. The set of message functions

$m\_n,\backslash ,\; 1\backslash leq\; n\backslash leq\; N$ and the fusion rule $f(m\_1(x\_1),\backslash cdot,m\_N(x\_N))$ are

designed to minimize estimation error.

For example: minimizing the mean squared error (MSE),

$\backslash mathbb\{E\}\backslash |\backslash theta-\backslash hat\{\backslash theta\}\backslash |^2$.

Ideally, sensors transmit their measurements $x\_n$

right to the processing center, that is $m\_n(x\_n)=x\_n$. In this

settings, the maximum likelihood estimator (MLE) $\backslash hat\{\backslash theta\}\; =$

\frac{1}{N}\sum_{n=1}^N x_n is an unbiased estimator whose MSE is

$\backslash mathbb\{E\}\backslash |\backslash theta-\backslash hat\{\backslash theta\}\backslash |^2\; =\; \backslash text\{var\}(\backslash hat\{\backslash theta\})\; =$

\frac{\sigma^2}{N} assuming a white Gaussian noise

$w\_n\backslash sim\backslash mathcal\{N\}(0,\backslash 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.

A Gaussian noise

$w\_n\backslash sim\backslash mathcal\{N\}(0,\backslash sigma^2)$ system can be designed as follows:

:{{cite journal

| last = Ribeiro

| first = Alejandro

|author2=Georgios B. Giannakis

| title = Bandwidth-constrained distributed estimation for wireless sensor Networks-part I: Gaussian case

| journal = IEEE Transactions on Signal Processing

| date = March 2006| volume = 54

| issue = 3

| page = 1131

| doi = 10.1109/TSP.2005.863009

| bibcode = 2006ITSP...54.1131R

| s2cid = 16223482

}}

: $$

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 $\backslash tau$ is a parameter leveraging our prior knowledge of the

approximate location of $\backslash theta$. In this design, the random value

of $m\_n(x\_n)$ is distributed Bernoulli~$(q=F(\backslash tau-\backslash theta))$. The

processing center averages the received bits to form an estimate

$\backslash hat\{q\}$ of $q$, which is then used to find an estimate of $\backslash theta$. It can be verified that for the optimal (and

infeasible) choice of $\backslash tau=\backslash theta$ the variance of this estimator

is $\backslash frac\{\backslash pi\backslash sigma^2\}\{4\}$ which is only $\backslash pi/2$ times the

variance of MLE without bandwidth constraint. The variance

increases as $\backslash tau$ deviates from the real value of $\backslash theta$, but it can be shown that as long as $|\backslash tau-\backslash theta|\backslash sim\backslash sigma$ the factor in the MSE remains approximately 2. Choosing a suitable value for $\backslash tau$ is a major disadvantage of this method since our model does not assume prior knowledge about the approximated location of $\backslash 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.{{cite journal

| last = Luo

| first = Zhi-Quan

| title = Universal decentralized estimation in a bandwidth constrained sensor network

| journal = IEEE Transactions on Information Theory

| date = June 2005| volume = 51

| issue = 6

| pages = 2210–2219

| doi = 10.1109/TIT.2005.847692

| s2cid = 11574873

}}

In this setting it is assumed that both $\backslash theta$ and

the noise $w\_n$ are confined to some known interval $[-U,U]$. The

estimator of also reaches an MSE which is a constant factor

times $\backslash frac\{\backslash sigma^2\}\{N\}$. In this method, the prior knowledge of $U$ replaces

the parameter $\backslash tau$ of the previous approach.

A noise model may be sometimes available while the exact PDF parameters are unknown (e.g. a Gaussian PDF with unknown $\backslash sigma$). The idea proposed in {{cite journal

| last = Ribeiro

| first = Alejandro

|author2=Georgios B. Giannakis

| title = Bandwidth-constrained distributed estimation for wireless sensor networks-part II: unknown probability density function

| journal = IEEE Transactions on Signal Processing

| date = July 2006| volume = 54

| issue = 7

| page = 2784

| doi = 10.1109/TSP.2006.874366

| bibcode = 2006ITSP...54.2784R

| s2cid = 11410878

}}

for this setting is to use two

thresholds $\backslash tau\_1,\backslash tau\_2$, such that $N/2$ sensors are designed

with $m\_A(x)=I(x-\backslash tau\_1)$, and the other $N/2$ sensors use

$m\_B(x)=I(x-\backslash 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

$\backslash tau\_1,\backslash tau\_2$ to have an MSE with a reasonable factor

of the unconstrained MLE variance.

The system design of 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.

$\backslash hat\{\backslash theta\}=\backslash sum\backslash limits\_\{n=1\}^\{N\}\backslash alpha\_n\; m\_n(x\_n)$.

The design should set the decision intervals $S\_n$ and the

coefficients $\backslash alpha\_n$. Intuitively, one would allocate $N/2$ sensors to encode the first bit of $\backslash 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]\backslash cup[U,2U]$ and so on. It can be shown that these decision

intervals and the corresponding set of coefficients $\backslash alpha\_n$

produce a universal $\backslash delta$-unbiased estimator, which is an

estimator satisfying

for every possible value of $\backslash theta\backslash in[-U,U]$ and for every realization of $w\_n\backslash in\backslash mathcal\{P\}$. In fact, this intuitive

design of the decision intervals is also optimal in the following

sense. The above design requires

$N\backslash geq\backslash lceil\backslash log\backslash frac\{8U\}\{\backslash delta\}\backslash rceil$ to satisfy the universal

$\backslash delta$-unbiased property while theoretical arguments show that

an optimal (and a more complex) design of the decision intervals

would require $N\backslash geq\backslash lceil\backslash log\backslash frac\{2U\}\{\backslash delta\}\backslash rceil$, that is:

the number of sensors is nearly optimal. It is also argued in

that if the targeted MSE

$\backslash mathbb\{E\}\backslash |\backslash theta-\backslash hat\{\backslash theta\}\backslash |\backslash leq\backslash epsilon^2$ uses a small

enough $\backslash 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.

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 {{cite journal

| last = Xiao

| first = Jin-Jun

|author2=Andrea J. Goldsmith

| title = Joint estimation in sensor networks under energy constraint

| journal = IEEE Transactions on Signal Processing

| date = June 2005}}

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(\backslash cdot)$ as to meet the energy

constraints. Another work employs a similar approach to address

distributed detection in wireless sensor arrays.{{cite journal

| last = Xiao

| first = Jin-Jun

|author2=Zhi-Quan Luo

| title = Universal decentralized detection in a bandwidth-constrained sensor network

| journal = IEEE Transactions on Signal Processing

| date = August 2005| volume = 53

| issue = 8

| page = 2617

| doi = 10.1109/TSP.2005.850334

| bibcode = 2005ITSP...53.2617X

| s2cid = 8072065

}}

• [https://web.archive.org/web/20080430133030/http://www.eecs.harvard.edu/~mdw/proj/codeblue/ CodeBlue] Harvard group working on wireless sensor network technology to a range of medical applications.

{{reflist}}

{{Wireless Sensor Network}}

Category:Estimation theory

Category:Detection theory

Category:Wireless sensor network