A Robust Indoor Positioning and Auto-Localisation Algorithm

Rainer Mautz, Washington Y. Ochieng

Centre for Transport Studies, Department of Civil and Environmental Engineering, Imperial College London, London, United Kingdom, SW7 2AZ.
Institute of Geodesy and Photogrammetry,Swiss Federal Institute of Technology, ETH Zurich.

DOI:                 

Abstract

Sensor networks that use wireless technology (IEEE standards) to measure distances between network nodes allow 3D positioning and real-time tracking of devices in environments where Global Navigation Satellite Systems (GNSS) have no coverage. Such a system requires three key capabilities: extraction of ranges between sensor nodes, appropriate supporting network communications and positioning. Recent research has shown that the first two of these capabilities are feasible. This paper builds on this and develops an automatic and robust 3D positioning capability. A strategy is presented that enables high integrity positioning even in the presence of large mean errors in the range measurements. This is achieved by an algorithm that generates a tight, high-confidence upper bound on the error in a position estimate, given the noisy range measurements from the radio devices in view. As a core feature, we present a novel network auto-localisation algorithm that fully automatically determines the positions of all nearby fixed nodes. Results from a real network using the Cricket Indoor Location System show how all sensor nodes can be determined based on only one dynamic node. Simulations of static networks with 100 nodes demonstrate the importance of solving folding ambiguities. Studies from networks with imprecise range measurements have shown that it is possible to theoretically achieve a position deviation that is of the size of the ranging error.

Keywords

auto-localisation, positioning algorithm, wireless sensor positioning, multilateration

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Coope I (2000), Reliable computation of the points of intersection of n spheres in n-space, ANZIAM Journal, Vol. 42(E), pp. C461-477, 2000.
[2]	Darnell, C and Wilczoch, C (2002), Real Time Positioning; Construction and implementation of a GPSCommunicator. Master’s thesis in Control andCommunication, Report no. LITH-ISY-EX-3246-2002, Link?ping University, Sweden.
[3]	Eren, T; Goldenberg, D; Whiteley, W; Yang, Y; Morse, A; Anderson, B and Belhumeur, P (2004), Rigidity, computation and randomization of network localization. In: Proceedings of IEEE Infocom ’04, Hong Kong, China, April 2004.
[4]	Goldenberg D; Krishnamurthy, A; Maness, W; Yang, Y; Young, A; Morse, A; Savvides, A and Anderson B (2005), Network Localization in Partially Localizable Networks. In Proceedings of IEEE INFOCOM 2005, Miami, FL, March 13-17, 2005.
[5]	Grafarend, E and Sanso, F (Editors) (1985), Optimization and Design of Geodetic Networks. Springer-Verlag.
[6]	Grafarend, E and Schaffrin, B (1993), Ausgleichung in linearen Modellen, Wissenschaftsverlag, Mannheim, Leipzig, Wien Zürich
[7]	Haggag, H and Mehraei, G (2006), Robot Interaction Using Cricket, an Indoor Positioning System, Technical Report of the Maryland Engineering Research Internship Teams (MERIT), University of Maryland and Virginia Commonwealth University.
[8]	Horn, B (1987), Closed-from solution of absolute orientation using unit quaternions. Journal of Opt. Soc. Amer., vol. A-4, pp. 629–642, 1987.
[9]	Manolakis, D (1996), Efficient Solution and Performance Analysis of 3-D Position Estimation by Trilateration, IEEE Aerospace and electronic systems, Vol 32, No. 4, Oct. 1996.
[10]	Mautz, R., Ochieng, W.Y., Brodin, G., Kemp, A. (2007), 3D Wireless Network Localization from Inconsistent Distance Observations, Ad Hoc & Sensor Wireless Networks, Vol. 3, No. 2–3, pp. 141–170.
[11]	Mautz, R. (2002), Solving Nonlinear Adjustment Problems by Global Optimization, Bollettino di Geodesia e Scienze Affini, Vol. 61, No.2, pp. 123 – 134.
[12]	Moore, D; Leonard, J; Rus, D and Teller, S (2004), Robust distributed network localization with noisy range measurements, Proceedings of the ACM Symposium on Networked Embedded Systems, 2004.
[13]	Niculescu, D and Nath, B (2001), Ad-hoc positioning system, in: IEEE GlobeCom, 2001.
[14]	Priyantha N. B. (2005), The Cricket Indoor Location System, PhD Thesis, Massachusetts Institute of Technology, June 2005, 199p.
[15]	Savarese, C; Langendoen, K and Rabaey, J (2002), Robust positioning algorithms for distributed ad-hoc wireless sensor networks, in: USENIX Technical Annual Conference, Monterey, CA, 2002, pp. 317–328.
[16]	Savvides, A; Han, C and Strivastava, M (2001), Dynamic Fine-Grained Localization in Ad-hoc Networks of Sensors, Proceedings of ACM SIGMOBILE 2001, Rome, Italy, July 2001
[17]	Savvides, A; Park, H and Srivastava, M (2003), The n-Hop Multilateration Primitive for Node Localization Problems. MONET 8(4): 443-451.
[18]	Savvides, A; Garber, W; Adlakha, S; Moses, R and Srivastava, M (2003a), On the Error Characteristics of Multihop Node Localization in Ad-Hoc Sensor Networks, Proceedings of the Second International Workshop on Information Processing in Sensor Networks (IPSN'03), Palo Alto, California, 317-332.
[19]	Shang, Y; Ruml, W; Zhang, Y and Fromherz, M (2004), Localization from Connectivity in Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 11, pp. 961–974, Nov. 2004.
[20]	Smith, A; Balakrishnan, H; Goraczko, M and Priyantha N (2004), Tracking Moving Devices with the Cricket Location System, Proc. 2nd USENIX/ACM MOBISYS Conf., Boston, MA, June 2004.
[21]	Taylor, C., Rahimi, A., Bachrach, J., Shrobe, H., and Grue, A. (2006), Simultaneous localization, calibration, and tracking in an ad hoc sensor network. In: Proceedings of the 5. international Conference on information Processing in Sensor Networks (Nashville, Tennessee, USA, April 19 - 21, 2006). IPSN '06. ACM Press, New York, NY, 27-33. DOI= http://doi.acm.org/10.1145/1127777.1127785
[22]	Taylor, C J; (2005), Simultaneous Localization and Tracking in Wireless Ad-hoc Sensor Networks, Master Thesis of Engineering, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology.
[23]	Thomas, F and Ros, L (2005), Revisiting Trilateration for Robot Localization, IEEE Transactions on Robotics, Vol. 21, No. 1, pp. 93-101, February 2005.
[24]	Wang, K J (2004), An Ultrasonic Compass for Context-Aware Mobile Applications, Master Thesis of Engineering, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology.