286 J.Comput.Sci.Technol.,Mar.2010,Vol.25,No.2 the statistical model of the random observations.i.e.. f(X),where X is the random observation,and 0 is the parameter to be estimated.Any unbiased estimator 0 must satisfy Cov(0)>{-E[Vo(VoInf(X10))T]}-1 (1) where Cov(0)is the error covariance of the estimator, E]indicates expected value,and Ve is the gradient operator with respect to 0. Fig.14.Trilateration under noisy ranging measurements. The CRLB is limited to unbiased estimators that there does not exist any position satisfying all distance provide estimates equal to the ground truth if averaged over enough realizations.In some cases.however,bi- constraints. ased estimators can achieve both a variance and a mean Non-Consistency.In many cases,a single node squared error that are below the CRLB. has many reference neighbors.Any subgroup of them (no less than three)can locate this node by multilat- (b)CRLB for Multihop Localization eration.The computed result,however,is varying if In network localization,the parameter vector of different groups of references are chosen,resulting in interest consists of the coordinates of nodes to be local- non-consistency.Thus,when alternative references are ized,given by [1,41,72,y2,...,L,UL]T,where L available,it is a difficult task to determine which com is the number of nodes to be localized.The observation bination of references provides the best results. vector X is formed by stacking the distance measure- Error Propagation.The results of a multihop lo- ments dij.Let M denote the size of X.We assume the calization process are based on a series of single hop distance measurement are Gaussian52.621,so the pdf of multilaterations in an iterative manner(251.In such a X is vector Gaussian.According to (1),we find that process,errors,coming from each step of multilatera- CRLB ={[G'(0)]T[G(@)]}-1,where o2 is the vari- tion,propagate and accumulatel50-511. ance of each distance measurement error,and G()is the M x 2L matrix whose mn-th element is 2.3.2 Error Characteristics of Localization xi-工1 Localization error is a function of a wide range of dii 、if0n=x: network configuration parameters,including the num- 工j-Ei bers of beacons,the density of node deployment,net- if On xj, d work topology,etc.,which constitute a complicated sys- tem.Understanding the error characteristics of loca- G'(0)mn= 一5 if On =Vi, (2) lization is one essential step towards controlling errors. dii The Cramer Rao Lower Bound(CRLB)161]provides 一班 a means for computing a lower bound on the covari- d if On=Yj ance of any unbiased location estimate that uses dis- 0, otherwise. tance measurements.In addition,CRLB can serve as a benchmark for localization algorithms:if the bound is The above result on CRLB is with the assumption closely achieved,there is little gain to continue working that the location information of beacons is exact.When on improving the algorithm accuracy.Furthermore,the the beacon nodes have location uncertainty,we can dependence of CRLB on network parameters helps to also characterize localization accuracy using a covari- understand the error characteristics of network local- ance bound that is similar to CRLB.Both the two ization. bounds are tight in the sense that localization algo- (a)What is CRLB rithms achieve these bounds in case of highly accurate The Cramer Rao Lower Bound (CRLB)is a clas- ranging measurements.In addition,according to(2), sic result from statistics that gives a lower bound the CRLB can be computed analytically and efficiently, on the error covariance for an unbiased estimate of avoiding the need for expensive Monte-Carlo simula- parameter611.This bound provides a useful guideline tions.The computational efficiency facilitates to study to evaluate various estimators.One important and localization performance of large-scale networks. surprising advantage of CRLB is that we can calcu- (c)CRLB for One-Hop Localization late the lower bound without ever considering any par- One-hop multilateration is the source of the location ticular estimation method.The only thing needed is error that could be amplified by the iterative fashion of286 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 Fig.14. Trilateration under noisy ranging measurements. there does not exist any position satisfying all distance constraints. • Non-Consistency. In many cases, a single node has many reference neighbors. Any subgroup of them (no less than three) can locate this node by multilat￾eration. The computed result, however, is varying if different groups of references are chosen, resulting in non-consistency. Thus, when alternative references are available, it is a difficult task to determine which com￾bination of references provides the best results. • Error Propagation. The results of a multihop lo￾calization process are based on a series of single hop multilaterations in an iterative manner[25]. In such a process, errors, coming from each step of multilatera￾tion, propagate and accumulate[50-51] . 2.3.2 Error Characteristics of Localization Localization error is a function of a wide range of network configuration parameters, including the num￾bers of beacons, the density of node deployment, net￾work topology, etc., which constitute a complicated sys￾tem. Understanding the error characteristics of loca￾lization is one essential step towards controlling errors. The Cramer Rao Lower Bound (CRLB)[61] provides a means for computing a lower bound on the covari￾ance of any unbiased location estimate that uses dis￾tance measurements. In addition, CRLB can serve as a benchmark for localization algorithms: if the bound is closely achieved, there is little gain to continue working on improving the algorithm accuracy. Furthermore, the dependence of CRLB on network parameters helps to understand the error characteristics of network local￾ization. (a) What is CRLB The Cramer Rao Lower Bound (CRLB) is a clas￾sic result from statistics that gives a lower bound on the error covariance for an unbiased estimate of parameter[61]. This bound provides a useful guideline to evaluate various estimators. One important and surprising advantage of CRLB is that we can calcu￾late the lower bound without ever considering any par￾ticular estimation method. The only thing needed is the statistical model of the random observations, i.e., f(X|θ), where X is the random observation, and θ is the parameter to be estimated. Any unbiased estimator ˆθ must satisfy Cov( ˆθ) > {−E[∇θ(∇θ ln f(X|θ))T]} −1 (1) where Cov( ˆθ) is the error covariance of the estimator, E[·] indicates expected value, and ∇θ is the gradient operator with respect to θ. The CRLB is limited to unbiased estimators that provide estimates equal to the ground truth if averaged over enough realizations. In some cases, however, bi￾ased estimators can achieve both a variance and a mean squared error that are below the CRLB. (b) CRLB for Multihop Localization In network localization, the parameter vector θ of interest consists of the coordinates of nodes to be local￾ized, given by θ = [x1, y1, x2, y2, . . . , xL, yL] T, where L is the number of nodes to be localized. The observation vector X is formed by stacking the distance measure￾ments ˆdij . Let M denote the size of X. We assume the distance measurement are Gaussian[52,62], so the pdf of X is vector Gaussian. According to (1), we find that CRLB = { 1 σ2 [G0 (θ)]T[G0 (θ)]} −1 , where σ 2 is the vari￾ance of each distance measurement error, and G0 (θ) is the M × 2L matrix whose mn-th element is G 0 (θ)mn =    xi − xj dij , if θn = xi , xj − xi dij , if θn = xj , yi − yj dij , if θn = yi , yj − yi dij , if θn = yj , 0, otherwise. (2) The above result on CRLB is with the assumption that the location information of beacons is exact. When the beacon nodes have location uncertainty, we can also characterize localization accuracy using a covari￾ance bound that is similar to CRLB. Both the two bounds are tight in the sense that localization algo￾rithms achieve these bounds in case of highly accurate ranging measurements. In addition, according to (2), the CRLB can be computed analytically and efficiently, avoiding the need for expensive Monte-Carlo simula￾tions. The computational efficiency facilitates to study localization performance of large-scale networks. (c) CRLB for One-Hop Localization One-hop multilateration is the source of the location error that could be amplified by the iterative fashion of