Fast hardware-oriented algorithm for 3D positioning in line-of-sight and single bounced non-line-of-sight environments

The ability to find the location of a mobile object and track it in two-dimensional (2D) and three-dimensional (3D) space is an indispensable feature of wireless communication systems. In particular, the increase in demand for using self-navigation technology in unmanned vehicles is attracting additional attention to this area of research. The methods and techniques developed for these systems compete in terms of simplicity, performance, and accuracy. However, the majority of solutions focus on only one of these performance metrics and are not applicable to the projected systems. In this study, a new location estimation solution that satisfies all three performance metrics (simplicity, accuracy, and efficiency) is achieved. The developed algorithms can be executed on a mobile object to allow it to learn its position in space. Furthermore, the simplicity of the mathematical operations used, namely binary shift and add operations, makes our algorithm hardware-friendly. Accelerated coordinate rotation digital computer (CORDIC) algorithms are used for the first time with line-of-sight (LOS) and single-bounced-scattering non-line-of-sight (SBS NLOS) signal arriving approaches for mobile object self-positioning. This study also introduces a newly developed ‘vector-breaking’ method (VBM) to estimate the location of a mobile object using the arriving signals from scatters with unknown locations. Test results using the developed algorithm show that the projected level of accuracy has been achieved. Furthermore, the developed algorithm performs better than the solutions currently available in the field.

PDF

___

[1] Choi H, Geeves M, Alsalam B, Gonzalez F. ”Open source computer-vision based guidance system for UAVs on-board decision making,” 2016 IEEE Aerospace Conference; Big Sky, MT, USA; 2016. pp. 1-5. doi: 10.1109/AERO.2016.7500600
[2] Rullan-Lara JL, Salazar S, Lozano R. UAV real-time location using a wireless sensor network. In: 2011 8th Workshop on Positioning, Navigation and Communication; Dresden, Germany; 2011. pp. 18-23. doi: 10.1109/WPNC.2011.5961008
[3] Tsuji H, Gray D, Suzuki M, Miura R. Radio location estimation experiment using array antennas for high altitude platforms. In: 2007 IEEE 18th International Symposium on Personal, Indoor and Mobile Radio Communications, Athens, Greece; 2007. pp. 1-5. doi: 10.1109/PIMRC.2007.4394608
[4] Abbas R, Michael K. COVID-19 Contact Trace App Deployments: Learnings From Australia and Singapore. IEEE Consumer Electronics Magazine 2020; 9 (5): 65-70. doi: 10.1109/MCE.2020.3002490
[5] Weizman Y, Tan AM, Fuss FK. Use of wearable technology to enhance response to the Coronavirus (COVID-19) pandemic. Public Health 2020; 185: 221-222. DOI: 10.1016/j.puhe.2020.06.048.
[6] Thong STS, Han CT, Rahman TA. Intelligent fleet management system with concurrent GPS & GSM real-time positioning technology. In: 2007 7th International Conference on ITS Telecommunications; Sophia Antipolis, France; 2007. pp. 1-6, doi: 10.1109/ITST.2007.4295849.
[7] Zantout R, Jrab M, Hamandi L, and F. Sibai FN. Fleet management automation using the global positioning system. In: 2009 International Conference on Innovations in Information Technology (IIT); Al Ain, United Arab Emirates; 2009. pp. 30-34. doi: 10.1109/IIT.2009.5413792
[8] Du J, Barth MJ. ”Next-Generation Automated Vehicle Location Systems: Positioning at the Lane Level,” in IEEE Transactions on Intelligent Transportation Systems, vol. 9, no. 1, March 2008.pp. 48-57. doi: 10.1109/TITS.2007.908141
[9] Federal Communications Commission. Fact sheet: FCC wireless 911 requirements. Government Printing Office (accessed 5 May 2001). Website http://www.fcc.gov/e911/
[10] Seeman ED, O’Hara MT, Holloway J, Forst A. The impact of government intervention on technology adoption and diffusion: the example of wireless location technology. Electronic Government, an International Journal, 2007; 4 (1): 1-19.
[11] Mohapatra D, Suma SB. Survey of location based wireless services. IEEE International Conference on Personal Wireless Communications; ICPWC, New Delhi, India; 2005. 358-362.
[12] Dao D, Rizos C, Wang J. Location-based services: technical and business issues. Gps Solutions, 2002; 6 (3): 169-178.
[13] Yunos HM, Gao JZ, Shim S. Wireless advertising’s challenges and opportunities. Computer, 2003; 36 (5): 30-37.
[14] Stilp LA. Carrier and end-user applications for wireless location systems. Wireless Technologies and Services for Cellular and Personal Communication Services (International Society for Optics and Photonics), January 1996; Vol. 2602: 119-126.
[15] Want R, Schilit B. Expanding the horizons of location-aware computing. Computer, 2001; 34 (8): 31-34.
[16] Tsalgatidou A, Veijalainen J, Markkula J, Katasonov A, Hadjiefthymiades S. Mobile e-commerce and locationbased services: Technology and requirements. ScanGIS, June 2003; Vol. 2003: 1-14.
[17] Gezici S. A survey on wireless position estimation. Wireless personal communications, 2008; 44 (3): 263-282.
[18] Sayed AH, Tarighat A, Khajehnouri N. Network-based wireless location: challenges faced in developing techniques for accurate wireless location information. IEEE signal processing magazine, 2005; 22 (4): 24-40.
[19] Caffery JJ. A new approach to the geometry of TOA location. Vehicular Technology Conference Fall 2000. IEEE VTS Fall VTC2000. 52nd Vehicular Technology Conference; Boston, MA, USA; 2000. (Cat. No. 00CH37152); Vol. 4: 1943-1949.
[20] Reed JH, Krizman KJ, Woerner BD, Rappaport TS. An overview of the challenges and progress in meeting the E-911 requirement for location service. IEEE Communications Magazine, 1998; 36 (4): 30-37.
[21] Spirito MA, Mattioli AG. Preliminary experimental results of a GSM mobile phones positioning system based on timing advance. Gateway to 21st Century Communications Village. VTC 1999-Fall. IEEE VTS 50th Vehicular Technology Conference, Amsterdam, Netherlands; September 1999. (Cat. No. 99CH36324); Vol. 4: 2072-2076.
[22] Khajehnouri N, Sayed AH. A non-line-of-sight equalization scheme for wireless cellular location. In 2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, Hong Kong, China; April 2003. Proceedings:(ICASSP’03); Vol. 6: VI-549.
[23] Guvenc I, Chong CC. A survey on TOA based wireless localization and NLOS mitigation techniques. IEEE Communications Surveys & Tutorials, 2009; 11 (3): 107-124.
[24] Al-Jazzar S, Caffery J, You HR. A scattering model based approach to NLOS mitigation in TOA location systems. IEEE 55th Vehicular Technology Conference. VTC, Birmingham, AL, USA; Spring 2002. (Cat. No. 02CH37367); Vol. 2: 861-865.
[25] Wang Z, Zekavat SA. Omnidirectional mobile NLOS identification and localization via multiple cooperative nodes. IEEE Transactions on Mobile Computing, 2011; 11 (12): 2047-2059.
[26] Paton IJ, Crompton EW, Gardiner JG, Noras JM. Terminal self-location in mobile radio systems. Sixth International Conference on Mobile Radio and Personal Communications, Coventry, UK; December 1991: 203-207.
[27] Chan YT, Ho KC. A simple and efficient estimator for hyperbolic location. IEEE Transactions on signal processing, 1994; 42 (8): 1905-1915.
[28] Botteron C, Host-Madsen A, Fattouche M. Cramer-Rao bounds for the estimation of multipath parameters and mobiles’ positions in asynchronous DS-CDMA systems. IEEE Transactions on Signal Processing, 2004; 52 (4): 862-875.
[29] Kangas A, Siomina I, Wigren T. Positioning in LTE. Handbook of Position Location: Theory, Practice, and Advances: John Wiley and Sons, Inc., Publication, 2011: 1081-1127. doi:10.1002
[30] Zhao Y. Standardization of mobile phone positioning for 3G systems. IEEE Communications Magazine, 2002; 40 (7): 108-116.
[31] Cheung KW, So HC, Ma WK, Chan YT. Least squares algorithms for time-of-arrival-based mobile location. IEEE Transactions on Signal Processing, 2004; 52 (4): 1121-1130.
[32] Patwari N, Ash JN, Kyperountas S, Hero AO, Moses RL et al. Locating the nodes: cooperative localization in wireless sensor networks. IEEE Signal processing magazine, 2005; 22 (4): 54-69.
[33] Roos T, Myllymäki P, Tirri H, Misikangas P, Sievänen J. A probabilistic approach to WLAN user location estimation. International Journal of Wireless Information Networks, 2002; 9 (3): 155-164.
[34] Roos T, Myllymaki P, Tirri H. A statistical modeling approach to location estimation. IEEE Transactions on Mobile computing, 2002; 1 (1): 59-69.
[35] Mazenc C, Merrheim X, Muller JM. Computing Functions cos/sup-1/and sin/sup-1/Using CORDIC. IEEE Transactions on Computers, 1993; 42 (1): 118-122.
[36] BingJuang T, FengLin H. CORDIC algorithm for vectoring mode without constant scaling factors. Electronics Letters, 1999; 35 (12): 971-972.
[37] Villalba J, Lang T, Zapata EL. Parallel compensation of scale factor for the CORDIC algorithm. Journal of VLSI signal processing systems for signal, image and video technology, 1998; 19 (3): 227-241.
[38] Fessler JA, Hero AO. Space-alternating generalized expectation-maximization algorithm. IEEE Transactions on signal processing, 1994; 42 (10): 2664-2677.
[39] Sakagami S, Aoyama S, Kuboi K, Shirota S, Akeyama A. Vehicle position estimates by multibeam antennas in multipath environments. IEEE Transactions on Vehicular Technology, 1992; 41 (1): 63-68.
[40] Seow CK, Tan SY. Non-line-of-sight localization in multipath environments. IEEE Transactions on Mobile Computing, 2008; 7 (5): 647-660.
[41] Fang BT. Simple solutions for hyperbolic and related position fixes. IEEE transactions on aerospace and electronic systems, 1990; 26 (5): 748-753.
[42] Salamah M, Doukhnitch E. An efficient algorithm for mobile objects localization. International Journal of Communication Systems, 2008; 21 (3): 301-310.
[43] Doukhnitch E, Salamah M, Sandouka A. Novel hardware-oriented algorithms for TDOA positioning technique in cellular networks. Mathematical Methods in Engineering, Springer, Dordrecht, Netherlands; 2007: 347-357.
[44] Doukhnitch E, Salamah M, Ozen E. An efficient approach for trilateration in 3D positioning. Computer communications, 2008; 31 (17): 4124-4129.
[45] Muller JM. Elementary functions Algorithms and Implementations, Springer Science+Business Media New York, USA; 2016. doi: 10.1007
[46] Shikur BY, Weber T. Tdoa/aod/aoa localization in nlos environments. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Florence, Italy; (2014, May): 6518-6522.
[47] Doukhnitch E, Salamah M. General approach to simple algorithms for 2-D positioning techniques in cellular networks, Computer Communications, Volume 31, Issue 10, 2008, ISSN 0140-3664, Pages 2185-2194.
[48] Jami I, Ali M, Ormondroyd RF. Comparison of Methods of Locating and Tracking Cellular Mobiles, Novel Methods of Location and Tracking of Cellular Mobiles and Their System Applications (Ref. No. 1999/046), IEE Colloquium, London UK, 1/1-1/6.
[49] Xinning W, Palleit N, Weber T. ”AOD/AOA/TOA-based 3D positioning in NLOS multipath environments,” 2011 IEEE 22nd International Symposium on Personal, Indoor and Mobile Radio Communications, Toronto, ON, Canada; 2011.pp. 1289-1293. doi: 10.1109/PIMRC.2011.6139709
[50] Samadi S, Khosravi MR, Alzubi JA, Alzubi OA, Menon VG. ”Optimum range of angle tracking radars: a theoretical computing.” International Journal of Electrical and Computer Engineering (IJECE) Vol 9, No 3, June 2019, doi: 10.11591/ijece.913, pp. 1765-1772
[51] Roxin A, Gaber J, Wack M, Nait-Sidi-Moh . ”Survey of wireless geolocation techniques.” 2007 IEEE Globecom Workshops. IEEE, Washington, DC, USA; 2007.
[52] Federal Communications Commission. Fact sheet: FCC wireless 911 Location Accuracy requirements. Government Printing Office (accessed 16 January 2020). Website https://www.federalregister.gov/documents/2020/01/16/2019-28483/wireless-e911-location-accuracyrequirements.
[53] Li J, Lu I, Lu JS. DOA-based localization algorithms under NLOS conditions. IEEE Long Island Systems, Applications and Technology Conference (LISAT). IEEE, Farmingdale, NY, USA; 2018 May. pp. 1-6.
[54] Liu B, Zhu X, Jiang Y, Huang, Y. Low Complexity Cooperative Positioning in Multipath Environment. In 2018 IEEE/CIC International Conference on Communications in China (ICCC). IEEE, Beijing, China; 2018 August. pp. 298-303.
[55] Liu H, Dai W, Shen Y. Super-resolved Localisation without Identifying LoS/NLoS Paths. arXiv preprint. 2019 November, arXiv:1910.12662.
[56] Xu C, Wang Z, Wang Y, Wang Z, Yu L. Three passive TDOA-AOA receivers-based flying-UAV positioning in extreme environments. IEEE Sensors Journal, 2020; 2 (16): 9589-9595.