Fast Hardware-Oriented Algorithms for 3D Positioning in LOS and Single Bounced NLOS Environments

Abstract

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. These studies have been supported by governments and businesses since the beginning. In particular, the increase in demand for using self navigation technology in unmanned vehicles is attracting additional attention to this area of research. The self-location estimation process is an indefeasible capability that an unmanned vehicle should have. This process requires high accuracy that is hard to be achieved by mobile devices, usually having limited power and computing capabilities. 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, two new location estimation solutions that satisfy all three performance metrics (simplicity, accuracy, and efficiency) are developed. Accordingly, two accelerated variations of 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 in the self-positioning process. The simplicity of the mathematical operations used, namely binary shift and add operations, makes our solutions hardware friendly. The second novelty of the study is the newly developed “Vector Breaking Method” (VBM) used for estimating the location of mobile objects using the arriving signals Bbounced from scatters with unknown locations. Test results using the developed algorithms show that the projected level of accuracy has been achieved. Furthermore, our solutions have presented better performance than the solutions currently available in the field. Keywords: 3D positioning, location estimation, LOS, line of sight, NLOS, non-line of sight, CORDIC, fast rotation algorithm, AOA, AOD, TOA, TDOA, EOTDO, CID, eCID, RSS, cellular wireless communication systems, One-bounced-scattering, hardware-oriented, antenna arrays, mobile object, base station, scatter, ACE algorithm, fixed angle rotation method, FARM, dynamic angle rotation method, DARM, vector breaking method, VBM, vector lengthening method, VLM, level of accuracy, computational cost, accuracy level.

ÖZ: Kablosuz iletişim sistemleri vasıtasıyla, iki boyutlu ve üç boyutlu uzayda hareket halindeki cihazların yerlerinin saptanabilmesi, takiplerinin yapılabilmesi son yıllarda en çok dikkat çeken teknolojilerdendirler. Bunların geliştirilmesine yönelik yapılan araştırmalar da devletler ve iş dünyası tarafından daha ilk günlerden beri desteklenmektedirler. Özellikle, insansız hava araçlarının kullanımının oldukça yaygınlaştığı günümüzde, hareket halindeyken bu araçlara kendi konumunu tespit edebilme yeteneğini kazandırmaya yönelik araştırmalar oldukça ilgi görmektedirler. Bugün, kendi konumunu bilerek seyir görevini yapabilmek, yeni nesil tüm insansız araçların vazgeçilemez bir yeteneği olmuştur. Sınırlı enerji ve işemci gücüne sahip bu tür hareketli araçlar, yüksek hassasiyet gerektiren bu tür işlemleri yerine getirmekte oldukça zorlanmaktadırlar. Bu amaçla geliştirilmiş bir çok çözüm yöntemi işlem basitliği, performans ve hassasiyet kıstaslarına göre birbirleriyle yarışmaktadırlar. Bu yöntemlerin büyük çoğunluğu aynı anda bu üç kıstası da sağlayamadıklarından, arzu edilen performansı gösteremiyorlar. Bu tez çalışmamızda üç boyutlu uzayda hareket eden cihazların konum tespiti ve takibinde, aynı anda basitlik, hassasiyet ve verimlilik kıstaslarının üçünü de sağlayabilecek; sınırlı güç ve işlemci kapasitesiyle de kullanılabilecek çözümler üretmeyi hedefledik. Çözümümüz, yer tayini hesaplarının baz istasyonları üzerinde değil de hareketli cisim üzerinde yapılacağı şekilde tasarlandı. Bu amaçla, sadece direk olarak baz istasyonlarından gönderilen sinyallerle (LOS) değil, yeri belli olmayan engenlere vurup yansıyarak hareketli cihazımıza ulaşan (NLOS) sinyallerin de kullanılacağı bir grafiksel çözüm yöntemi geliştirildi. Ardından, hesaplarımızda kullanılması gereken çok fazla işlemci gücü ve enerjisi gerektiren trigonometric fonksiyonları hızlandırılmış CORDIC algoritmaları ile değiştirerek, çözümlerimizi normalden daha hızlı ve az işlemci gücü ile de çalışabilmesi sağlandı. Çalışmamız, CORDIC algoritmalarının ilk kez NLOS sinyalleri ile kullanılmasından dolayı eşsiz bir çalışma olarak değerlendirilebilir. Çalışmamızdaki ikinci özgünlük ise, ilk kez çalışmamızda geliştirilmiş ve kullanılmış olan “Vektör Kırma” Metodumuzdur (VBM). Bu metot yardımıyla, yerleri belli olmayan engellerden yansıyarak hareketli cismimize ulaşan baz istasyonu sinyallerini kullanılarak hareketli cismin yeri tahmin edilmektedir. Çalışmamızda geliştirdiğimiz yer tayin yöntemleri simulasyonlarla test edildi ve hedeflenen doğrulukta sonuç verdikleri görüldü. Ayrıca, her iki yöntemimiz de, işlem ve enerji verimliliği konusunda, alanda kabul görmüş rakiplerinden daha iyi performanslar gösterdiler. Anahtar Kelimeler: 3B konumlandırma, konum tahmini, direk görüş hattı, , indirek görüş hattı, CORDIC, hızlı açı döndürme algoritması, sinyal geliş açısı, sinyal gönderim açısı, sinyal geliş zamanı, sinyal geliş zaman farkı, yayın hücresi kimliği, hücresel kablosuz iletişim sistemleri, tek sekmeli yansıma, donanım uyumlu, anten dizisi, hareketli obje, baz ‘stasyonu, engel, ACE algoritması, sabit açılı döndürme metodu, , değişken açılı döndürme metodu, vektör kırma metodu, vektör uzatma metodu, doğruluk seviyesi, işlemsel maliyet.