Locating engine

Articleissues
refimprove=May 2008
essay=May 2008

A locating engine performs the computing of coordinates of locations of objects and of persons based on methods of multilateration or triangulation. This applies mainly with real-time locating systems (RTLS) and navigation support systems.

Some suppliers describe the approach as a positioning engine, however no position is affected, but just a location determined.

Traditional approaches

Locating has a long tradition in geodesy since C.F. Gauss' work in 1821-1825.The concepts of triangulation and multilateration have been well elaborated since then. More modern approaches take the matrix calculus into account. The basic concept of Gauss applied the concept of over-determination for systems of quadratic equations, thus leading to the generalized approach of least squares.

Advanced approaches

Especially Torgerson proposed the concept of multidimensional scaling (first published in 1928 and finally renewed in 1958) for overdetermined numerical problems with unknown dimensionality and heavy stochasticity or also biased variations. This approach may be applied to 3-dimensional locating in R3 under deterministic but noisy conditions as well. Detailed tutorial may be found in [http://www.pavis.org/essay/multidimensional_scaling.html Proximity Visualization of Abstract Data from Wojciech Basalaj (2001)] . Extension to the locating problem is found in several instances of patent literature, as e.g. in [http://www.freepatentsonline.com/6318375.html] .

= Features of a generic locating engine =

In terms of informatics, the process of locating based on distinct results from distance metering is performed in a "locating engine". The prerequisite is the metering. Both processes may be implemented independently and thus tailored independently to various requirements of application.

Such locating engine combines algorithms of geometry or topography with algorithms of filtering. The key issue of qualifying such locating engines is with the problem of sets of metered distances never matching in one coordinate, but in areas encircled by circles (TOA) or hyperbolas (TDOA). The task for the locating engine is to calculate promptly ("in real time") for any real location a best estimate for the coordinates of the real location.

The method of locating with an RTLS in any systems layout is always a special method out of the family of methods for dead reckoning. The location of any bearer of an RTLS node may be located with a typical accuracy. This varies with the RTLS deployed and with degradation in the actual operational situation. To make clear, that Real Time Locating with an RTLS is an operational means to achieve some information about a momentary location with only short-term validity, the term "guess" is used. RTLS is always a best guess to support an operation. At no extent it may be used to interrogate map information with topographic or geodesic accuracy.

The tendency to apply for patent rights on applied mathematics where time is a parameter leads to closing the books on algorithms. The quantity of granted patents on special breeds of locating engines will rise. Currently few offers are on the market for either open source, closed source or closed applications including locating engines. The composition of such engine from scratch is not necessary. Mathematical libraries offer a large variety of building blocks. However, the quality of any solution is ruled by experience with the error models of metering and the cohesion control with networking.

The interested party must test the offerings to find the best fit for supporting operations. There is no general approach to success.

Simplification

For didactic purposes, the simplifying of a model used to set up a properly computing locating engine may be reduced to R2, the simple Pythagorean plane (applying Pythagoean theorem to distances on any Euclidean plane in R2). However, this approach does not deliver proper solutions even in a physically plane environment, as the errors do not stick to this simplification. Suitable approaches will be achieved with a correct model referring to the R3 Euclidean space.

Topology and topography

Location information is never obtained in a single step. A location may be described through relative positional data, absolute positional data or any intermediate information for obtaining such data. Eventual descriptions are topographical, mostly referring to a terrain map or a building plan. Locating requires more than topological descriptions, which for instance only include neighbourhoods and hop counts, as is the case of communications networks. The topological description is however a prerequisite for operating some types of locating engines in order to obtain a topographical determination afterwards.

Unambiguousness

To obtain an appropriate result with locating, not only precision is required, but primarily the unambiguousness of data for processing is required.

That is quite simple to comprehend:

* On a trajectory, it is sufficient to know two way points to determine a third location. Any leg defined with two known way points gives a unique set of coordinates for any third way point on the very same trajectory, disregarding the orientation of the trajectory on a surface or in a space. However, the trajectory must be well defined. In the case of a straight line, the two way points with coordinates and a Euclidean norm for the trajectory fulfil this condition.
* On a surface, it is sufficient to know three way points to determine a fourth location. Any triangle defined with three known way points gives a unique set of coordinates for any fourth way point on the very same surface, spanned with the triangle and disregarding the orientation of the triangle in a space and the planarity of the surface. However, the surface must be well defined. In the case of a plane, the three way points with coordinates and a Euclidean norm for the plane fulfil this condition.
* In a space, it is sufficient to know four waypoints to determine a fifth location. Any tetrahedron defined with four known waypoints gives a unique set of coordinates for any fifth waypoint in the very same space, spanned with the tetrahedron and disregarding the orientation of the tetrahedron in space and the orthogonality of the space. However, the space must be well defined. In the case of a plane, the four waypoints with coordinates and a Euclidean norm for the space fulfil this condition.To obtain an appropriate result with locating, not only precision is required, but primarily the of sufficient complete data for processing unambiguous results is required.

In any 3D Euclidean system of coordinates, the Euclidean distance is the metrics to determine the position of objects in an interrelation. In a simplified 2D system of coordinates, the Euclidean distance simplifies to the Pythagorean distance. The inversion of the distance calculus (quadratic equation with three resp. two variables) delivers the coordinates of a current location. This requires proper distances for at least 4 known locations (in 3D) or at least 3 known locations (in 2D). Any lesser reference point count delivers ambiguous solutions.

Then, fulfilling the condition for unambiguousness, metering shall be performed from or towards various reference points to calculate the unknown location as the unknown position inside a plane circle triangle (3 reference points in a 2D space with three distance circles) or inside a spherical tetrahedron (4 reference points in a 3D space with four spherical shell surfaces).

Even with a sufficient count of reference points ambiguousness resides. The first reason is the time consumption for measurements and the motion of the target to be located. The other insisting reasons are pertaining even motionless scenarios. The reasons are the key problem of metering:
* Accuracy,
* Reproduceability and
* Resolution
* NoiseThus the demand for "highest precision" reprehends the requester: An increase in precision does generally not solve the problem. Finally noise will be kept as the residing challenge. Generally mathematics and physics provide the escape at reasonable cost, but not with increase in accuracy only. That may be observed with the geometric solutions in locating engines. The "center of gravity" approach in 2D and 3D concepts leads to poor results.

= Data bases and hosts =

Generally locating engines work on data obtained from databases or from measurements and export results to spatial databases and spatio-temporal databases.

Data sets

Location data ages with motion. Thus data sets for locations must include coordinates and a time of capture. This applies as well in asynchronous metering concepts. To perform locating properly, most systems apply sequences of computed locations as a track. To align these data sets, date and time comply with the needs.

To serve communication between nodes, time accompanies location data. To ease this communication, data is conveyed in containers and wrappers. Respective standardization is common for the communicating of maritime coordinates as well as satellite data. However, communication for other terrestrial usage is normally defined with proprietary methods. Hence, RTLS comply with standardization of ranging, but not with any standardization of computed data.

Data representation with motion

For locating engines the most common feature of variation is motion. Motion drives aging of spatial dfata on moving objects. However, spatial data on reference objects under operational conditions of a locating engine is not subject of motion.

The crossbreed of spatial databases with data sets containing instances affected by motion and ceteris paribus is subject of spatio-temporal databases.

Complex applications demand for data representation in structures of the type of spatio-temporal databases, which include both location and time as parameters for multiplicitly represented instances ceteris paribus.

Standardization of spatial data sets

Current work for standardization of spatial data sets is bound to conventional spatial data bases and does yet not include parameters of motion. Hence, modeling the data for locating engines may refer to standardization for unambiguous data, but then will not refer to notions of motion, i.e. location and time.

Hosting of data and engine

The locating engine must be materialized in a component capable to compute location and to manage data sets on localities. Such implementing

* may be established as a central server function. Such is current habit in indoors oriented RTLS designs. This approach has all features of centralization with advantages in power source and computing power, but is encompassed with disadvantages of mandatory networking requirements, latency increase and bottlenecks in communications.

* will be easily established as a local client function. Such is current habit in vehicle oriented RTLS designs. This approach has all features of decentralization with common conditions in vehicle power sources and sufficient computing power at reasonable cost, but is encompassed with disadvantages of access rates of lesser rapid memory entities, mandatory networking requirements to report similar data to all moving and locating entities.

* could be established as a local DSP function. Such is yet not current available in portable RTLS designs, but will appear in the market soon as comparable to PDA or handy implementations of GPS functionality. This approach has all features of autonomy, but when measurement for locating may be an active wireless approach as for communications, encompassed with harsh conditions for power efficiency. However, sufficient computing power is available at reasonable cost, but may have some limitations or restrictions in tracking functions due to lesser availability of data from networking with other units.

Anyhow, centralized functions in a single locating engine server facility are definitively not the ultima ratio in modern systems design.

= Mathematical modeling for locating =

Applying RTLS or other locating hardware requires equivalent methodology to make appropriate use of obtained measures. This shall be comprised in an RTLS locating machine that keeps the user and applicator free of considerations about how to obtain best estimates for mobile positions.Such locating machine e.g. for planar motion in buildings and on plane surfaces comprises at least of the following:
* Measurement computation to cope with the stochastic errors of metered distance values, thus reducing noise.
* Modeling the mesh of nodes and distances as a stable network of controlled topology and as a virtual surface.
* Conformal modeling matching the real operational surfaces, to serve location data for physically purposeful positions e.g. outside obstacles and driving or settled on a plane.
* Providing stable tracks according to inherited motion capabilities, i.e. not jumping aside nor forth and aback and keeping steady speed and acceleration.This list may be extended upon sound modeling concepts. Interested parties may believe, electrotechnically sound solutions alone do not cover this modeling requirement even by most skillful measuring methodology.

Abstract mathematical models

The collection of measurements with locating systems may lead to data that is heavily biased, noise loaded and over-determined. In result, it is not possible to form a distinct model from this data. The first step therefore applies an abstract procedure, as e.g. multidimensional scaling. With a setting to three dimensions in R3, the transition to a model is prepared, that bridges to imagination of motion in a 3D space.

Geometric models

Basing concept of the geometric approaches is determining the area of the own location with plane circles or spherical surfaces as confining lines respectively areas. These 2D-circles or 3D-spherical surfaces around the transmitter position describe the range with the measured distance from any metering node. Hence several distance circles (at least 3) or spherical surfaces (at least 4) around the corresponding transmitters define a planar polygon or a multihedron and the own real location is assumed lying in the center of gravity of this polygon or multihedron.

To encircle any area in R2 or volume in R3 greater zero, tolerances are added to the measured distances for computing the location. Many of the RTLS systems in market use such a simple 2D- or 3D- geometric approach for modeling the location of metering nodes. The concept postulates that the circles describe planes or surfaces that would include area or volume greater zero or just tangle in one position. However, the easiest understanding with such didactically skilled models coincides with a very bad performance considering stochastic and systematic errors.

Success with such geometric model is in fact hampered by multiple path errors, statistical errors and diverse metering inaccuracies. Such approaches fail in highly dynamic environments and may show severe jitter even with nodes at zero speed. Beyond this, the involving of more than the least required number of reference nodes (>3 for 3D and >4 four 4D) increases the complication. The interested user should not assume that such simple approaches would allow for the good performance or high precision with systems as e.g. with GPS in open air. Some higher level of sophistication is required to obtain sound results.

Analytical models

The need to define encircled volumes with geometric models leads to various strategies of biasing the obtained measurements.Basing concept of approaches with autonomous agents as a higher abstraction is a matrix of distance metrics of all pairs of nodes that performed cooperative distance metering. Some of the elements of this matrix may remain empty or distances are not metered simultaneously. The approach serves complex error models and will deliver appropriate estimates for real location. In case the inverted matrix exists, the model makes use of a priori knowledge about known distances to and coordinates of anchor nodes and the time series of error converges to sufficient low values.

The most generic approach for spatial locating is that of iterative MDS, multi-dimensional scaling in R3 Euclidean spaces.

Differential models

The other model based approach to motion detection with RTLS is the computing of differentials of the position information.

Instantiated models

The easy approach however in modeling is just recording and plotting constant field characteristics with the operational equipment for locating in the operational ambience. Such mapping of propagation characteristics requires the following for confinements as rooms or rack alleys:

* uptaking mapping instances per confinement
* precise maps valid for the existing equipping in the confinement
* no change to the local furnishing in the confinement
* few interference of moving objects other but those to locate

Then the model to support locating exists in an instance for each confinement. Such approach does not work in open air, however, there normally is not much to plot. Additionally, with such vast preparatory infrastructural work, what remains to earn the attribute "real time"?Hence this concept works in a well known environment and somewhat low grade equipped buildings. When equipment is not highly electrified, motion of any objects remains at low speed, population is sparse and whatever challenge is absent, then such approach might suffice. Whenever changes in the vicinity generates changes to the plot, there must be either an adaptation of the plot or some adaptivity in the system. Some products are rather successful based on this concept.

= A priori knowledge =

Locating is not recommended for spontaneous start from scratch. The availability of a maximum of knowledge about the ambience and the past is deemed mandatory.

Tracking

All past information about location may be included to tracks. Self tracking is as valuable as tracking of other objects. The stability of tracking may be improved by knowledge about motion. Then new locations may be estimated more easily from earlier computed data and from latest acquisition.

Mapping

Mapping is well known to traditional navigation and has been re-introduced to plotting propagation diagrams for confinements. Such mapping basis may improve the guessing of received wireless power levels (RSSI) and converting it to distance metrics.

The more reasonable approach is the notion of obstacles which will interfere motion, i.e. where objects can physically not pass through. Disclosing terrain or floor surfaces and solid structures in maps is information well qualified to improve tracking and thus contribute to locating.

= Approaches to numerical computing =

The basic concern in locating is the mathematical approach. First concepts neglecting error lead to simple proposals. However, the facts of maesurement accuracy damand for further improving.

The Euclidean distance between two pints is a basic measure for computing locations. However, measurement errors prevent from quick success. The real challenge from noise and other errors require higher sophisticated approaches.

Traditional surveying

Numerical methods for surveying are well established since the days of C.F. Gauss. Respective solutions dominate the market.

Multidimensional scaling

Multidimensional scaling (MDS) is a crossbred from psychology mathematics. However, uncertainty about the model to represent correct dimensionality of the data sample is not the problem in terrestrial locating. The methods developed for MDS application serve well for easy implementation of locating functions. Hence applying MDS is a strong approach to perform the locality computing [www.cs.cmu.edu/~ftorre/papers/mswim09r-Cabero.pdf] . Currently reported approaches do not consider moving nodes with TOA distance metrics and special motion models, but anyhow the method is rather docile to prevent from faulty results.

The processing of available data does not compensate for the error sources without the traditional concepts:
* extinguishing the corsest single measurements first
* sampling and computing statistics for sufficient measurements
* predicting and correcting for motion tracks
* matching with context information
* taking into account the basing statistical model conditionsObeying these exercises may lead to sufficiently useful location data

= References to various approaches =

Open concept / hybrid solutions

* [http://www.aeroscout.com/content/difference AeroScout hybrid options]

Plain WiFi & RFID solutions

RSSI solutions

* [http://www.aeroscout.com/content/technology AeroScout WiFi approach]
* [http://www.ekahau.com/?id=20061 Ekahau approach]
* [http://www.meritechsolutions.com/iPointRTLS.aspx WiFi Mesh Network]
* [http://parcowireless.com/content.php?content=Press_Releases&Action=Show&ID=74 Ekahau / Parco Merged Media approach]
* [http://www.rft.com/products/pinpointrtls/ WiFi Sniffer Solution]

Plain RFID solutions

* [http://www.iaito.co.in/ RFID UHF solutions details not disclosed]

RFID beacon solutions

* [http://www.radarfind.com/solution/index.htm Radarfind beacon solution details not disclosed]
* [http://www.rfcode.com/index.php?option=com_content&view=article&id=293&Itemid=104 RF Code 433 MHz beacon solution]

TOA / TDOA solutions

Proprietary wireless solutions

* [http://www.ubisense.net Ubisense approach]
* [http://www.wherenet.com Zebra WhereNet approach]
* [http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/4494447/4510344/04510378.pdf?isnumber=4510344&prod=CNF&arnumber=4510378&arSt=219&ared=227&arAuthor=Fuentes+Michel%2C+J.+C.%3B+Millner%2C+H.%3B+Vossiek%2C+M. Symeo Approach]

UWB solutions

Special applications using the proposals with communications according to IEEE 802.15.4aUWB are still under development. None of the proposed approaches serves a systems requirement with moving nodes (2008-04).

* [http://www.timedomain.com/about/Newsroomcontent/TDCDualModePressRelease020408.pdf Time Domain / Aero Scout approach]

= See also =

* RTLS
* Real-time locating standards
* Navigation
* Unilateration

Bibliography

* Bronstein, A. M, Bronstein, M.M, and Kimmel, R. (2006), "Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching", Proc. National Academy of Sciences (PNAS), Vol. 103/5, pp. 1168-1172.
* Cox, M.F., Cox, M.A.A., (2001), "Multidimensional Scaling", Chapman and Hall.
* Coxon, Anthony P.M. (1982): "The User's Guide to Multidimensional Scaling. With special reference to the MDS(X) library of Computer Programs." London: Heinemann Educational Books.
* Green, P. (1975) Marketing applications of MDS: Assessment and outlook, "Journal of Marketing", vol 39, January 1975, pp 24-31.
* Kruskal, J. B., and Wish, M. (1978), "Multidimensional Scaling", Sage University Paper series on Quantitative Application in the Social Sciences, 07-011. Beverly Hills and London: Sage Publications.
* Torgerson, W. S. (1958). "Theory & Methods of Scaling". New York: Wiley.

Literature

* IEEE Std 802.15.4 (publication available through [http://www.ieee.org] )
* IEEE Std 802.15.4a Annex D1 (serving a good comparison of R2/2D models)
* [http://www.pavis.org/essay/multidimensional_scaling.html Multi-Dimensional scaling]
* [http://www.ucs.louisiana.edu/~rbh8900/PermapManual.pdf Implemented MDS software package manual]
* [http://www.mathpsyc.uni-bonn.de/doc/delbeke/delbeke.htm Learning website on MDS methodology]
* [http://www.granular.com/MDS/ Communicative website on MDS methodology]