Accuracy Bounds for Wireless Localization Methods

Introduction

To provide context for data collected by wireless sensor networks, it is necessary for the sensor network to supply accurate location information for its component sensor nodes (Sheu et al. 2006). To this end, several algorithms and sensor types have been developed for sensor node localization in these networks (Patwari et al. 2003; Ray et al. 2006). These proposed localization systems have been shown to provide excellent localization accuracy for the sensor nodes and mobile terminals in these networks. The remainder of this book describes the design and use of several of these algorithms. However, an important issue for a network designer is to determine what sensors and network topologies are required to achieve the necessary level of localization accuracy for their application. To make these design decisions, tools are required for analytically evaluating the performance of different localization systems with different sensor positions.

The purpose of this chapter is to describe tools for the accuracy analysis of localization systems for wireless sensor networks. The chapter will focus on localization systems based on base stations at known positions making measurements of the radio signals from the sensor nodes. It should be noted that while this chapter describes only radio-based measurements for localization within sensor networks, the mathematical tools are easily applied to other measurements such as acoustic-based distance measurements.

Evaluation methods for localization systems serve two purposes. First, they allow a network designer, prior to the creation of the senor network, to obtain a quantitative bound on how well the localization of sensor nodes can be performed with given types of localization measurements and with different geometric arrangements of the measuring base stations. A network designer can then determine which of a set of possible network designs will achieve the required localization accuracy for their application. Second, these tools can be used to evaluate the performance of an existing localization system to see if the potential location accuracy is being achieved or if further improvements are possible. The tools help to quantify the cost and accuracy tradeoffs of different component choices in a localization system’s design.

In the radiolocation literature, there have been several figures of merit proposed for localization accuracy such as the Circular Error Probable (CEP) and the Geometric Dilution of Precision (GDOP) (Torrieri 1984; Tekinay et al. 1998). These figures of merit provide useful information for the analysis of the performance of location systems, but these values are difficult to calculate for localization systems coping with multipath or non-line-of-sight (NLoS) radio propagation. In Line-of-Sight (LoS) radio propagation, radio signals travel directly on the shortest straight line path from the node to be located to the measuring base stations, whereas during NLoS radio propagation this path is obstructed and the signal is reflected and diffracted during propagation from the target node to the measuring base stations. NLoS propagation complicates the localization problem since the signal characteristics are not only a function of the node and base station locations but also a function of the location of obstructions in the propagation environment.

To provide accuracy information for localization in the presence of multipath and NLoS propagation, figures of merit have been derived in the localization literature such as the Cramér-Rao lower bound on the mean square error of the location estimates. The local Cramér-Rao lower bound has been derived for localization in the presence of multipath and random NLoS radio propagation and used to evaluate the performance of many localization systems (Qi et al. 2002; Botteron et al. 2004). This bound provides an excellent method of evaluating the effects of the locations of the base stations and measurement noise levels on localization accuracy. A difficulty with the use of the Cramér-Rao lower bound as a general evaluation tool for localization accuracy is that it considers the current radio signal measurements as the only source of information on node location. In other words, the Cramér-Rao lower bound assumes that the node location is a deterministic value and the localization system has no other information about the node location prior to the measurements. Other sources of information, such as the sensor selection procedure or the measurements taken in the past, are not considered, so the Cramér-Rao lower bound is no longer a valid lower bound for localization systems where this information is available.