On accuracy of region based localization algorithms for wireless sensor networks

Shigeng Zhang, Jiannong Cao, Yingpei Zeng, Zhuo Li, Lijun Chen, Daoxu Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)

Abstract

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 Cramér-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 sk23π and the expected localization error square of p in worst case is bounded below by sk12π. 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.
Original languageEnglish
Pages (from-to)1391-1403
Number of pages13
JournalComputer Communications
Volume33
Issue number12
DOIs
Publication statusPublished - 15 Jul 2010

Keywords

  • Localization error
  • Lower bound
  • Region based localization
  • Sensor networks

ASJC Scopus subject areas

  • Computer Networks and Communications

Cite this