On accuracy of region-based localization algorithms for wireless sensor networks

Localization is an essential problem in Wireless Sensor Networks (WSNs). Many localization algorithms have been proposed, but few efforts have been paid on theoretical analysis on the accuracy of these algorithms. Because it is naturally to formalize range-based localization problems as deterministic parameter estimation problems, for range-based localization algorithms Cramer-Rae Lower Bound (CRLB) has been used to lower bound the variance on the estimation of sensor's positions. However, few similar works have been done for range-free localization algorithms. In this paper, based on geometry properties, we theoretically analyze bounds on accuracy for Region-Based Localization (RBL) algorithms which can be classified as one type of range-free localization algorithms. We prove that if in a RBL algorithm, the deployment region R with the area size 8 is partitioned into k regions (they can be with any shape and any area size), the localization accuracy is bounded below by -√s/k 2/3√π, no matter how the algorithm partitions R. Although the lower bound is not theoretically tight, our simulation results show that the gap between this bound and achievable accuracy is very small. We conjecture a tighter lower bound 1.003-√s/k 2/3√π when k is large enough. We also observe that in order to achieve high localization accuracy, partitioned regions should have nearly the same size. We give three examples with simulation results to show how the results can be used to set the values of the parameters, like k and the corresponding anchor/event number, in a RBL algorithm in order to achieve desired localization accuracy.