This chapter introduces a methodological approach to the evaluation of localization algorithms. The chapter contains a discussion of evaluation criteria and performance metrics followed by statistical/ empirical simulation models and parameters that affect the performance of the algorithms and hence their assessment. Two contrasting localization studies are presented and compared with reference to the evaluation criteria discussed throughout the chapter. The chapter concludes with a localization algorithm development cycle overview: from simulation to real deployment. The authors argue that algorithms should be simulated, emulated (on test beds or with empirical data sets) and subsequently implemented in hardware, in a realistic Wireless Sensor Network (WSN) deployment environment, as a complete test of their performance. It is hypothesised that establishing a common development and evaluation cycle for localization algorithms among researchers will lead to more realistic results and viable comparisons.
TopIntroduction
Evaluating the relative performance of localization algorithms is important for researchers, either when validating a new algorithm against the previous state of the art, or when choosing existing algorithms which best fit the requirements of a given WSN application. However, there is a lack of unification in the WSN field in terms of localization algorithm evaluation and comparison. In addition, no standard methodology exists to take an algorithm through modelling, simulation and emulation stages, and into real deployment. As a result it can be hard to quantify exactly how and under what circumstances one algorithm is better than another. Moreover, deciding what performance criteria localization algorithms are to be compared or evaluated against is important for the success of the resulting implementation given that different applications will have differing needs.
Since localization algorithms are expected to be used in real applications, it is not conclusive to verify their performance in simulation only. The authors here argue that algorithms should be emulated (on test beds or with empirical data sets) and subsequently implemented in hardware, in a realistic WSN deployment environment, as a complete test of their performance.
In this chapter, performance evaluation metrics are discussed alongside three criteria – localization accuracy, cost, and coverage. Given that WSNs are typically constrained in terms of node/network lifetime and per-node computational resources, addressing these constraints leads to trade-offs in the performance of localization algorithms. For example, if maximising localization accuracy is the foremost priority, specific hardware may have to be added to each sensor node, increasing node size, cost and weight. Conversely, if the hardware available is already determined, then the application expectations with respect to performance criteria (such as accuracy) must be adjusted accordingly.
The chapter is structured as follows: a discussion of the various performance criteria and evaluation metrics that are readily used in the analysis of localization algorithms is first presented. Next, representative topologies that affect performance criteria are given, followed by simulation models and parameters that affect the performance of localization algorithms. A case study is presented, outlining an acoustic monitoring sensor network with high accuracy constraints enforced by application requirements. This case study is contrasted with an example where scalability and longer network lifetime are required at the expense of complexity and localization accuracy. Finally, the chapter closes with a brief discussion on the development cycle of a localization algorithm, from simulation to real deployment.
It should be noted that although this chapter makes particular emphasis on simulation and comparison of range-based localization algorithms, many of the metrics and techniques described are applicable to other approaches, such as Angle of Arrival (AoA) based algorithms, for example.
Evaluation Criteria
Whilst the intuitive measure of the performance of a localization algorithm may be to show how well it can estimate positions of nodes compared to the known ground truth (to the degree of accuracy required by the WSN application, as discussed further below), localization algorithms are also subject to the general constraints of wireless networked sensing. It follows that a broader set of evaluation criteria for localization algorithms are needed (and are useful to both developers and users of localization algorithms), examples of which are accuracy, cost, coverage, robustness and scalability. These criteria reflect the constraints already mentioned - computational limitations, power constraints, unit cost and network scalability.
Some evaluation criteria are binary in nature: algorithms either have a specific property or they do not (for example, they are self-configuring or not; they are anchor free or not). Classifications and binary criteria can be used by researchers to narrow the set of existing algorithms to evaluate against, or to choose from. For example, one may only consider distributed, anchor-free, range based localization algorithms, immediately limiting the number of algorithms to compare to. Some evaluation criteria and trade-offs however, need quantification and qualification. These are described below in more detail, and questions are posed that might be useful to the algorithm or WSN application designer in establishing a given algorithm’s performance.