On accuracy of region based localization algorithms for wireless sensor networks

Although many localization algorithms have been proposed, few efforts have been devoted to theoretical analysis on accuracy of these algorithms. For range-based localization problems, the Cramer-Rao lower Bound (CRB) provides an algorithm-independent method to analytically compute a tight lower bound on the square of sensors' localization errors. However, for range-free localization algorithms there are little similar work. In this paper, based on geometric 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. Assume a sensor node p can lie at any point with equal probability in a deployment region R whose size is s. If in a RBL algorithm R is partitioned into k arbitrary subregions, then the expected localization error of p in worst case is bounded below by root s/k 2/3 root pi and the expected localization error square of p in worst case is bounded below by s/k 1/2 pi. The bounds are not theoretically tight: however our simulation results show that the gaps between these bounds and corresponding achievable values are small. The obtained results can be used to bound localization accuracy of RBL algorithms in a wireless sensor network. (The localization accuracy is defined as the average localization error of all nodes in the network.) Our simulation results show that the derived bound can effectively reflect the best localization accuracy RBL algorithms can achieve in randomly deployed sensor networks with enough large number of sensors. We also investigate the key factors that impact localization accuracy in RBL algorithms. With these results, we show by examples with simulation results how to set up guidelines in the design of RBL algorithms in order to achieve high localization accuracy. (C) 2010 Elsevier B.V. All rights reserved.