İç mekan konum belirleme sistemlerinde konum kestirim doğruluğunun yükseltilmesi
Improvement of the location estimation accuracy in indoor localization systems
Yazar: EMRE DORUK
Danışman: DOÇ. DR. OSMAN KAAN EROL ; DOÇ. DR. TANER ARSAN
İstanbul Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı / Kontrol ve Otomasyon Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2021
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering

Özet:
Çağımızda  artan teknoloji kullanımı ile nesnelerin veya canlıların konum bilgisinin önemi artmaktadır. Konum bilgisinin doğruluk seviyesinin önemi iç ve dış mekanlar için farklılık göstermektedir. Dış mekanlardaki konum hassasiyeti 3 m – 15 m seviyelerinde hassas kabul edilebilir olur iken iç mekanlarda bu seviyeler istenilen hassasiyetten oldukça uzak kalmaktadır. Bu hassasiyet beklentisi farklılığı iç mekân konumlandırmada radyo frekansı ile tanıma (Radio-frequency Identification – RFID), ultra geniş bant (Ultra Wide Band-UWB) sistemleri, Bluetooth gibi farklı teknolojiler ortaya çıkarmıştır. Ultra geniş bant teknolojisi ise  iç mekan konum belirleme teknolojileri arasında en güvenilir ve en  yüksek doğruluklu sistemler olarak öne çıkmaktadır.
Bu tez çalışması ile iç mekân konum kestirimindeki hataların belirlenmesi ve bu hataları azaltma yöntemleri tanımlanarak konum kestirim doğruluğunun yükseltilmesi amaçlanmaktadır. Literatürde mevcut olan yöntemler temel araçlar olarak kullanılmıştır. Bu araçların sağladığı faydalardan yararlanılabilmesi için hibrit algoritmalar önerilmiştir. Önerilen algoritmaların başarımları saha verileri ile test edilmiştir. Saha verilerini toplarken MDEK DWM1001 UWB sensör seti kullanılmıştır. Test ortamı olarak ise Kadir Has Üniversitesi Steelcase Active Learning Center sınıfı seçilmiştir. Seçilen sınıfın 5.4 m x 5 m alanı veri toplama bölgesi olarak belirlenmiştir. Belirlenen bu alanda 132 nokta işaretlenmiş ve bu 132 noktadan yaklaşık 65000 konum verisi toplanmıştr. Toplanan saha verilerinin dağılımları ve hata karakteristikleri incelenmiştir. Ardından önerilen algoritmalar saha verileri kullanılarak test edilmiştir. Ham verilerin ve işlenmiş verilerin ortalama hata değerleri kıyaslamıştır.
Toplanan verilerin hata değeri UWB sensörlerinin beklenen değeri olan 10 cm-20 cm aralığında, 11.46 cm olarak tespit edilmiştir. Ham verilere önerilen algoritma adımları uygulanmıştır. Algoritmaların konum kestirim doğruluklarına etkisi incelenmştir. Kullanılan algoritmalar ile en az Kalman Filtresi ile % 25.5 iyileşme sağlanmıştır. En yüksek ise Kalman Filtresi-Büyük Patlama Büyük Çöküş Optimizasyonu (BP-BÇ) ve K-En Yakın Komşu Atama (K-EYK) algoritmalarının kombinasyonundan oluşan metot ile % 68 iyileşme sağlandığı gözlemlenmiştir. 11.47 cm olan ortalama hata değeri en yüksek başarımı veren algoritma ile 3.67 cm seviyesine çekilmiştir.

Abstract:
The importance of localization estimation accuracy in indoor positioning is increasing with the increasing use of technology in our age. The importance of the accuracy level of localization systems differs for indoor and outdoor environments. 3 m -15 m accuracy can be considered sufficient enough for outdoor positioning systems. However, these accuracy levels are far from the desired sensitivity for indoor environments. This difference in sensitivity expectation has revealed different technologies such as radio frequency identification, ultra wide band systems, Bluetooth in indoor positioning. Ultra-wideband technology steps forward as the most reliable and most accurate systems for indoor localization technologies.
With this thesis, it is aimed to modeling the errors in indoor localization systems and to increase the accuracy of localization estimation by proposing the methods to reduce these errors.  Because of the reliability and high accuracy of UWB sensors MDEK DWM1001 UWB sensor set selected to collect localization data. That sensor system provides indoor localization accuracy in the 10 cm- 20 cm range. Kadir Has University Steelcase Active Learning Center was selected for collecting data. This classroom measures 7.35 m x 5.41 m. Middle 5.4 m x 5 m region used to test area. This test area is divided into 0.5 m x 0.5 m grids. 4 anchors placed in the corners of the classroom with 2.80 m height. 1 tag placed to each grid point with about 1.50 m height. To prevent signal reflection from humans a tripod used to stabilize the tag. At each grid point about 500 location data collected. At the end of data collection, approximately 6500 location data were collected. 
All of the collected data were examined by using MATLAB. Firstly, data distribution was examined for each grid point. After that square error values of each grid point measurements were calculated. In this examination, it was observed that the lowest error between the points was 2.17 cm and the highest error was 31.92 cm. The total mean square error of the data was calculated by taking the mean of these grid points.  This value was calculated as 11.4 cm. The  mean square error value is consistent with the expected average value for UWB sensors.
Another step of this work is developing an algorithm for decreasing measurement error. For this purpose three main method were used; Big Bang Big Crunch (BB-BC) optimization, Kalman Filter and K-Nearest Neighbors (K-NN) algorithm. BB-BC is an evolutionary optimization method. The most important feature of the BP-BC optimization algorithm is the low computation time as well as the high convergence speed. This algorithm is very easy to implement. BB-BC optimization method is chosen for eliminating biased errors. Second method is Kalman Filter. Kalman Filter is a prediction algorithm introduced by Rudolf Emil Kalman. Kalman Filter is useful, efficient, fast and powerful for real-time systems. This method it has found many applications and has become standardized for many systems. Kalman Filter is chosen for eliminating Gaussian noise. Third method is K-Nearest Neighbors algorithm. This is a sample-based learning algorithm. It is a type of machine learning that classifies certain features of unidentified data that are new to the system by comparing them with the most similar K data from the previously collected and recorded data in the same system. This method is used to assign correct correction values quickly.
Basic methods have been used with various variations to eliminate measurement errors. Three algorithm developed for this work. First algorithm involves two of those methods. In this algorithm, data filtered by Kalman Filter. Then BB-BC used for calculating offset values for each grid point. After that, a function which dependent on the measurement values is defined. This function used for selecting correct offset values which were calculated by BB-BC. Second and algorithm involves all three algorithms. First step of the second algorithm is eliminating biased errors with BB-BC. BB-BC calculates offset values of each grid point. After this step, the K-NN algorithm is used for give the correct offset values to the correct measurement. Final step of this algorithm is filtering processed data with Kalman Filter. Third algorithm is a version of the second algorithm. The order of the algorithm steps of the second one has been changed for this algorithm. First step of this algorithm is filtering data with Kalman Filter. After that, eliminating biased errors with BB-BC optimization. Final step of this algorithm is using K-NN for proper offset values. 
The algorithms described above have been tested with real data. Raw data divided into three parts. First two parts of raw data used for training BB-BC, Kalman Filter and K-NN.  Third part of data used as a test set. In order to establish a standard, only the Kalman Filter has also been tested with real data. The mean square error value of the raw data was determined as 11.46 cm. Kalman Filter decreased this value to 8.53 cm. Kalman Filter the BB-BC then function defining algorithm decreased to 7.08 cm. Second algorithm, BB-BC then K-NN then Kalman Filter approach reduced error value into 4.16 cm. Kalman Filter then BB-BC then K-NN algorithm decreased error value even more. The MSE value of this algorithm is 3.67 cm. 
In order to increase the accuracy of location estimation indoors; Improvement methods which using optimization method (BP-BC), estimation algorithm (Kalman Filter), machine learning algorithm (K-NN) methods have been proposed. By combining these methods, it is aimed to benefit from their strengths. The BB-BC algorithm calculated optimal values for each measurement point, which reduced the error to very low levels. In addition to this, filtering raw data with Kalman Filter before BB-BC reduced error even more for each grid. However, it was not possible to reduce the calculated 132 offset value pairs to a single value due to the error characteristic. In real life, it will not be possible for the target to correctly select which correction value. Further methods are designed to correctly select these values. For this reason, only the grid performance value of the BB-BC algorithm is excluded from the evaluation. When Kalman Filter was applied to raw data alone, it decreased the error value from 11.46 cm to 8.53 cm. This method gives system 25.5 % accuracy increase. The gain brought by the Kalman Filter is used for the next algorithms.
In the next three algorithms, the focus is on correctly distributing the 132 offset value pairs obtained by the previous steps over the entire measurement area. Kalman Filter the BB-BC then function defining algorithm focused on reducing the set of correction values to two surface functions for the x plane and the y plane. After many functions (Rastrigin, Ackley, Fourier, etc.) tested during the studies, this function was defined as a 10th degree polynomial. The parameters of the polynomial were also estimated by the BB-BC method. This algorithm provided % 38.2  accuracy increase. Different methods have been designed since this increase is not enough for targeted correction levels.
Due to the difficulty of fitting the offset values into a continuous function, the K-NN algorithm is included in the system in order to distribute it appropriately. In order to evaluate the place of the K-NN algorithm in the algorithm flow, 2 different methods were created. With the 2nd algorithm, firstly, correction values were calculated with BB-BC to eliminate biased errors, and K-NN method was used to distribute these calculated correction values correctly. This algorithm provided % 63.7  accuracy increase. In order to further increase the high level of success achieved with second algorithm third algorithm was performed. The purpose of the third algorithm, changing flow order for clearing Gaussian noise in the measurement data first, then leaves only biased noises to the BP-BC method. Thus, the BB-BC method calculated more accurate offset values and these values could be distributed appropriately with the K-NN. Final algorithm provides a % 68 accuracy increase.