Location estimation in sensor networks explained

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

Use

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

Let

\theta

denote the position of interest. A set of

N

sensorsacquire measurements

xn=\theta+wn

contaminated by anadditive noise

wn

owing some known or unknown probability density function (PDF). The sensors transmit measurements to a central processor. The

n

th sensor encodes

xn

by a function

mn(xn)

. The application processing the data applies a pre-defined estimation rule

\hat{\theta}=f(m1(x1),,mN(xN))

. The set of message functions

mn,1\leqn\leqN

and the fusion rule

f(m1(x1),,mN(xN))

aredesigned to minimize estimation error.For example: minimizing the mean squared error (MSE),

E\|\theta-\hat{\theta}\|2

.

Ideally, sensors transmit their measurements

xn

right to the processing center, that is

mn(xn)=xn

. In thissettings, the maximum likelihood estimator (MLE)

\hat{\theta}=

1
N
N
\sum
n=1

xn

is an unbiased estimator whose MSE is

E\|\theta-\hat{\theta}\|2=var(\hat{\theta})=

\sigma2
N
assuming a white Gaussian noise
2)
w
n\siml{N}(0,\sigma
. The next sections suggestalternative designs when the sensors are bandwidth constrained to1 bit transmission, that is

mn(xn)

=0 or 1.

Known noise PDF

A Gaussian noise

2)
w
n\siml{N}(0,\sigma
system can be designed as follows:

[2]

mn(xn)=I(xn-\tau)= \begin{cases} 1&xn>\tau\\ 0&xn\leq\tau \end{cases}

\hat{\theta}=\tau-F-1\left(

1
N
N
\sum\limits
n=1

mn(x

n)\right), F(x)=1
\sqrt{2\pi

\sigma}

infty
\int\limits
x
-w2/2\sigma2
e

dw

Here

\tau

is a parameter leveraging our prior knowledge of theapproximate location of

\theta

. In this design, the random valueof

mn(xn)

is distributed Bernoulli~

(q=F(\tau-\theta))

. Theprocessing 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 (andinfeasible) choice of

\tau=\theta

the variance of this estimatoris
\pi\sigma2
4
which is only

\pi/2

times thevariance of MLE without bandwidth constraint. The varianceincreases 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 ofthe sensors.

A system design with arbitrary (but known) noise PDF can be found in.[3] In this setting it is assumed that both

\theta

andthe noise

wn

are confined to some known interval

[-U,U]

. Theestimator of [3] also reaches an MSE which is a constant factortimes
\sigma2
N
. In this method, the prior knowledge of

U

replacesthe parameter

\tau

of the previous approach.

Unknown noise parameters

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 [4] for this setting is to use twothresholds

\tau1,\tau2

, such that

N/2

sensors are designedwith

mA(x)=I(x-\tau1)

, and the other

N/2

sensors use

mB(x)=I(x-\tau2)

. The processing center estimation rule is generated as follows:
\hat{q}
1=2
N
N/2
\sum\limits
n=1

mA(xn),

\hat{q}
2=2
N
N
\sum\limits
n=1+N/2

mB(xn)

\hat{\theta}=F-1(\hat{q
2)\tau
-1
1-F

(\hat{q}1)\tau

-1
2}{F
-1
(\hat{q}
2)-F
(\hat{q}
1)}, F(x)=1
\sqrt{2\pi
}\int\limits_^e^dw

As before, prior knowledge is necessary to set values for

\tau1,\tau2

to have an MSE with a reasonable factorof the unconstrained MLE variance.

Unknown noise PDF

The system design of [3] for the case that the structure of the noisePDF is unknown. The following model is considered for this scenario:

xn=\theta+wn,n=1,...,N

\theta\in[-U,U]

wn\inl{P},thatis:wnisboundedto [-U,U],E(wn)=0

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

mn(xn)= \begin{cases} 1&x\inSn\\ 0&x\notinSn \end{cases}

where each

Sn

is a subset of

[-2U,2U]

. The fusion estimator is also restricted to be linear, i.e.
N
\hat{\theta}=\sum\limits
n=1

\alphanmn(xn)

.

The design should set the decision intervals

Sn

and thecoefficients

\alphan

. Intuitively, one 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 decisionintervals and the corresponding set of coefficients

\alphan

produce a universal

\delta

-unbiased estimator, which is anestimator satisfying

|E(\theta-\hat{\theta})|<\delta

for every possible value of

\theta\in[-U,U]

and for every realization of

wn\inl{P}

. In fact, this intuitivedesign of the decision intervals is also optimal in the followingsense. The above design requires
N\geq\lceillog8U
\delta

\rceil

to satisfy the universal

\delta

-unbiased property while theoretical arguments show thatan optimal (and a more complex) design of the decision intervalswould require
N\geq\lceillog2U
\delta

\rceil

, that is:the number of sensors is nearly optimal. It is also argued in [3] that if the targeted MSE

E\|\theta-\hat{\theta}\|\leq\epsilon2

uses a smallenough

\epsilon

, then this design requires a factor of 4 in thenumber of sensors to achieve the same variance of the MLE inthe unconstrained bandwidth settings.

Additional information

The design of the sensor array requires optimizing the powerallocation as well as minimizing the communication traffic of theentire system. The design suggested in [5] incorporates probabilistic quantization insensors and a simple optimization program that is solved in thefusion center only once. The fusion center then broadcasts a setof parameters to the sensors that allows them to finalize theirdesign of messaging functions

mn()

as to meet the energyconstraints. Another work employs a similar approach to addressdistributed detection in wireless sensor arrays.[6]

External links

Notes and References

  1. Web site: Archived copy . 2008-04-30 . dead . https://web.archive.org/web/20080430133030/http://www.eecs.harvard.edu/~mdw/proj/codeblue/ . 2008-04-30 .
  2. Ribeiro . Alejandro . . Bandwidth-constrained distributed estimation for wireless sensor Networks-part I: Gaussian case . IEEE Transactions on Signal Processing . March 2006. 54 . 3 . 1131 . 10.1109/TSP.2005.863009 . 2006ITSP...54.1131R . 16223482 .
  3. Luo . Zhi-Quan . Universal decentralized estimation in a bandwidth constrained sensor network . IEEE Transactions on Information Theory . June 2005. 51 . 6 . 2210–2219 . 10.1109/TIT.2005.847692 . 11574873 .
  4. Ribeiro . Alejandro . . Bandwidth-constrained distributed estimation for wireless sensor networks-part II: unknown probability density function . IEEE Transactions on Signal Processing . July 2006. 54 . 7 . 2784 . 10.1109/TSP.2006.874366 . 2006ITSP...54.2784R . 11410878 .
  5. Xiao . Jin-Jun . Andrea J. Goldsmith . Joint estimation in sensor networks under energy constraint . IEEE Transactions on Signal Processing . June 2005.
  6. Xiao . Jin-Jun . Zhi-Quan Luo . Universal decentralized detection in a bandwidth-constrained sensor network . IEEE Transactions on Signal Processing . August 2005. 53 . 8 . 2617 . 10.1109/TSP.2005.850334 . 2005ITSP...53.2617X . 8072065 .