Efficient trilateration algorithm using time differences of arrival

Article history: Received 20 July 2012 Received in revised form 5 December 2012 Accepted 6 December 2012 Available online 24 January 2013 Keywords: Local positioning systems Cayley–Menger bideterminants Trilateration TDOA
∗ Corresponding author. Tel.: +34 918856544; fax: +34 918856591. ˜ E-mail addresses: urena@depeca.uah.es, jesus.urena@uah.es (J. Urena). 0924-4247/$ – see front matter © 2012 Elsevier B.V. All rights reserved. /10.1016/j.sna.2012.12.021
Both TOA and TDOA require solving a non-linear system of equations to obtain the position of the mobile tag. The iterative minimization of the non-linear system of positioning equations by the Gauss–Newton algorithm is usually chosen for the positioning algorithm (Positioning using the Gauss–Newton Algorithm – PGNA) due to its good properties [11]. This work proposes a new method that offers a similar performance, measured from the estimation of the Position Dilution of Precision (PDOP) in a set of points, than the PGNA, but with a significant reduction of the computational load. It uses the properties of Cayley–Menger bideterminants [12] to solve the positioning equations (Positioning using Cayley–Menger based Algorithm – PCMA). Three different resolution methods are presented: the first one considers some geometrical constraints (the beacons are in the same Z-constant plane); the second method solve a general case by using a rotation of the coordinate system; and finally the third method, also for a general case, is based on the minimization of a non-linear function to calculate only one variable by means of an iterative procedure. An ultrasonic LPS based on these proposals is presented and the positioning results are compared with those of the PGNA. Apart from ultrasounds [13,14] other technologies, commonly used in LPS, such as infrared [15] or RF [16], can take advantage from the algorithm proposed in this paper. The rest of the document is structured as follow: Section 2 introduces some properties of the Cayley–Menger bideterminants and how they have been used in spherical trilateration positioning. Section 3 deals with the adaptation of the Cayley–Menger based equations for the hyperbolic trilateration case. In Section 4 three different algorithms to find out the position of the mobile tags are addressed. Section 5 presents a comparison between the proposed algorithm (PCMA) and the traditional PGNA by using simulated data, including an evaluation of the efficiency
1. Introduction The research in Local Position Systems (LPS) has acquired a great importance during the last years due to the variety of applications that these kinds of systems can offer in the interior of buildings. Examples of these applications are the guidance of people [1,2], the study of people’s behavior in a specific context [3], the development of healthcare and entertaining applications [4,5], and indoor robot applications [6–8]. LPS can operate on a similar principle than GPS, that is, with a set of transmitting elements (beacons) placed at known positions of the environment and a mobile receiver (tag) whose position is the one to be computed. The tag location can be determined by spherical trilateration from the Times of Arrival (TOAs) of the emitted signals [9]. However, the tag needs to know when the beacons start transmitting their corresponging signals. Thus, it is necessary a synchronism trigger signal between the tag and the beacons what involves the use of additional hardware, i.e. RF transceivers in an ultrasonic LPS. Additionally, the errors in the synchronization process increase the errors in the calculation of the tag position. To avoid the problem of the emitter-receiver synchronization, it is possible to use a hyperbolic positioning algorithm [10]. This algorithm requires measuring the Time Differences of Arrival (TDOA) among a reference beacon and the others. Hyperbolic trilateration allows asynchronous detection at the expense of using one more beacon that acts as a reference.
Efficient trilateration algorithm using time differences of arrival
˜ ∗ , Juan C. García, Carmen Pérez, José M. Villadangos, Enrique García Daniel Ruiz, Jesús Urena
Sensors and Actuators A 193 (2013) 220–232
Contents lists available at SciVerse ScienceDirect
Sensors and Actuators A: Physical
journal homepage: /locate/sna
Electronics Department, University of Alcala, Campus Universitario s/n, 28805 Alcalá de Henares, Madrid, Spain