- Location estimation in sensor networks
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 distributedmanner by a set of sensors.Motivation
In many civilian and military applications it is required tomonitor a specific area in order to identify objects within itsboundaries. For example: monitoring the front entrance of aprivate house by a single camera. When the physical dimensions ofthe monitored area are very large relatively to the object ofinterest, this task often requires a large number of sensors (e.g.infra-red detectors) at several locations. The location estimationis then carried out in a centralized fusion unit based oninformation gathered from all the sensors. The communication tothe fusion center costs power and bandwidth which are scarceresources of the sensor, thus calling for an efficient design ofthe main tasks of the sensor: sensing, processing andtransmission.
The "
CodeBlue system " [http://www.eecs.harvard.edu/~mdw/proj/codeblue/] ofHarvard university is an example where avast number of sensors distributed among hospital facilitiesallow to locate a patient under distress. In addition, the sensorarray enables online recording of medical information whileallowing the patient to move around. Military applications (e.g.locating an intruder into a secured area) are also good candidatesfor setting a wireless sensor network.etting
Let heta denote the position of interest. A set of N sensorsacquire measurements x_n = heta + w_n contaminated by anadditive noise w_n owing some known or unknown
probability density function (PDF). The sensors transmit messages (based ontheir measurements) to a fusion center. The nth sensor encodesx_n by a function m_n(x_n). The fusion center applies apre-defined estimation rulehat{ heta}=f(m_1(x_1),cdot,m_N(x_N)). The set of message functionsm_n,, 1leq nleq N and the fusion rule f(m_1(x_1),cdot,m_N(x_N)) aredesigned in order to minimize the estimation error in some sense.For example: minimizing themean squared error (MSE),mathbb{E}| heta-hat{ heta}|^2.Ideally, the sensors would transmit their measurements x_nexactly to the fusion center, that is m_n(x_n)=x_n. In thissettings, the
maximum likelihood estimator (MLE) hat{ heta} =frac{1}{N}sum_{n=1}^N x_n is anunbiased estimator whose MSE ismathbb{E}| heta-hat{ heta}|^2 = ext{var}(hat{ heta}) =frac{sigma^2}{N} assuming a white Gaussian noisew_nsimmathcal{N}(0,sigma^2). The next sections suggestalternative designs when the sensors are bandwidth constrained to1 bit transmission, that is m_n(x_n)=0 or 1.Known noise PDF
We begin with an example of a Gaussian noisew_nsimmathcal{N}(0,sigma^2), in which a suggestion for asystem design is as follows [cite journal
last = Ribeiro
first = Alejandro
coauthors = Georgios B. Giannakis
title = Bandwidth-constrained distributed estimation for wireless sensor Networks-part I: Gaussian case
journal = IEEE Trans. on Sig. Proc.
date = March 2006] :: m_n(x_n)=I(x_n- au)=egin{cases} 1 & x_n > au \ 0 & x_nleq auend{cases}
: hat{ heta}= au-F^{-1}left(frac{1}{N}sumlimits_{n=1}^{N}m_n(x_n) ight),quadF(x)=frac{1}{sqrt{2pi}sigma} intlimits_{x}^{infty}e^{-w^2/2sigma^2} , dw
Here au is a parameter leveraging our prior knowledge of theapproximate location of heta. In this design, the random valueof m_n(x_n) is distributed Bernoulli~q=F( au- heta)). Thefusion center averages the received bits to form an estimatehat{q} of q, which is then used to find an estimate of heta. It can be verified that for the optimal (andinfeasible) choice of au= heta the variance of this estimatoris frac{pisigma^2}{4} which is only pi/2 times thevariance of MLE without bandwidth constraint. The varianceincreases as au deviates from the real value of heta, but it can be shown that as long as au- heta|simsigma the factor in the MSE remains approximately 2. Choosing a suitable value for au is a major disadvantage of this method since our model does not assume prior knowledge about the approximated location of heta. 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 cite journal
last = Luo
first = Zhi-Quan
title = Universal decentralized estimation in a bandwidth constrained sensor network
journal = IEEE Trans. on Inf. Th.
date = June 2005] . In this setting it is assumed that both heta andthe noise w_n are confined to some known interval U,U] . Theestimator of also reaches an MSE which is a constant factortimes frac{sigma^2}{N}. In this method, the prior knowledge of U replacesthe parameter au 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 [cite journal
last = Ribeiro
first = Alejandro
coauthors = Georgios B. Giannakis
title = Bandwidth-constrained distributed estimation for wireless sensor networks-part II: unknown probability density function
journal = IEEE Trans. on Sig. Proc.
date = July 2006] for this setting is to use twothresholds au_1, au_2, such that N/2 sensors are designedwith m_A(x)=I(x- au_1), and the other N/2 sensors usem_B(x)=I(x- au_2). The fusion center estimation rule is generated as follows:: hat{q}_1=frac{2}{N}sumlimits_{n=1}^{N/2}m_A(x_n), quadhat{q}_2=frac{2}{N}sumlimits_{n=1+N/2}^{N}m_B(x_n)
: hat{ heta}=frac{F^{-1}(hat{q}_2) au_1-F^{-1}(hat{q}_1) au_2}{F^{-1}(hat{q}_2)-F^{-1}(hat{q}_1)},quadF(x)=frac{1}{sqrt{2piintlimits_{x}^{infty}e^{-v^2/2}dw
As before, prior knowledge is necessary to set values forau_1, au_2 in order to have an MSE with a reasonable factorof the unconstrained MLE variance.
Unknown noise PDF
We now describe the system design of for the case that the structure of the noisePDF is unknown. The following model is considered for this scenario:
: x_n= heta+w_n,quad n=1,dots,N
: hetain [-U,U]
: w_ninmathcal{P}, ext{ that is }: w_n ext{ 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)=egin{cases} 1 & xin S_n \ 0 & x otin S_nend{cases}
where each S_n is a subset of 2U,2U] . The fusion estimator is also restricted to be linear, i.e.hat{ heta}=sumlimits_{n=1}^{N}alpha_n m_n(x_n).
The design should set the decision intervals S_n and thecoefficients alpha_n. Intuitively, we would allocate N/2 sensors to encode the first bit of heta by setting their decision interval to be 0,2U] , then N/4 sensors would encode the second bit by setting their decision interval toU,0] cup [U,2U] and so on. It can be shown that these decisionintervals and the corresponding set of coefficients alpha_nproduce a universal delta-unbiased estimator, which is anestimator satisfying mathbb{E}( heta-hat{ heta})|
for every possible value of hetain [-U,U] and for every realization of w_ninmathcal{P}. In fact, this intuitivedesign of the decision intervals is also optimal in the followingsense. The above design requiresNgeqlceillogfrac{8U}{delta} ceil to satisfy the universaldelta-unbiased property while theoretical arguments show thatan optimal (and a more complex) design of the decision intervalswould require Ngeqlceillogfrac{2U}{delta} ceil, that is:the number of sensors is nearly optimal. It is also argued in that if the targeted MSEmathbb{E}| heta-hat{ heta}|leqepsilon^2 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 [cite journal
last = Xiao
first = Jin-Jun
coauthors = Shuguang Cui
coauthors = Zhi-Quan Luo
coauthors = Andrea J. Goldsmith
title = Joint estimation in sensor networks under energy constraint
journal = IEEE Trans. on Sig. Proc.
date = June 2005] 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 m_n(cdot) as to meet the energyconstraints. Another work employs a similar approach to addressdistributed detection in wireless sensor arrays [cite journal
last = Xiao
first = Jin-Jun
coauthors = Zhi-Quan Luo
title = Universal decentralized detection in a bandwidth-constrained sensor network
journal = IEEE Trans. on Sig. Proc.
date = August 2005] .External links
* [http://www.eecs.harvard.edu/~mdw/proj/codeblue/ CodeBlue] Harvard group working on wireless sensor network technology to a range of medical applications.
References
Wikimedia Foundation. 2010.