KNN Algorithm for Indoor Navigation System Using LoRa
D Chandana1, Dr. Savitha C2, Dr. M Z Kurian3
1 PG- Electronics and Communication Engineering,
Sri Siddhartha Institute of Technology, Tumkur, Karnataka.
2 Assistant Professor, Electronics and Communication Engineering,
Sri Siddhartha Institute of Technology, Tumkur, Karnataka.
3 Head of Department, Electronics and Communication Engineering,
Sri Siddhartha Institute of Technology, Tumkur, Karnataka.
Abstract
Over the past few years, with the development of more advanced mobile technologies and broader application demands, a number of new technologies have been used for indoor navigation system. Navigation systems help users access unfamiliar environments. Current technological advancements enable users to encapsulate these systems in handheld devices, which effectively increases the popularity of navigation systems and the number of users. In indoor environments, the lack of global positioning system (GPS) signals and line of sight makes navigation more challenging compared to outdoor environments. Indoor localization can provide a number of various services like advertising according to location, indoor navigation and automation of different applications. There are many different techniques that provide Location Based Services (LBS) such as time-difference-of-arrival, angle-of-arrival, time-of-flight and received signal strength indicator (RSSI). RSSI is one of the most widely used method as it is cost-effective and easily implemented. Nevertheless, RSSI performance is limited by indoor noise. K-nearest neighbor (KNN) filtering algorithm is an accurate filter algorithm that can enhance RSSI performance localization indoors. KNN is one of the most popularly used algorithms for indoor positioning systems.
Keywords: Indoor Localization, Location Based Services (LBS), RSSI, KNN.
With the rapid growth of modern technology in information and communication technologies, Location Based Services (LBS) has been widely used to make lives intelligent and convenient. The indoor positioning technology plays an important role for LBS in providing service applications. Localization is the process of determining a person’s location. Different techniques were established in ancient times for localization and navigation. In today’s world, tracking an object can be considered as the same thing. The availability of GPS on the mobile phones now allows person to localize the current location of the person. Self-localization and aided localization are two types of localization. Self-localization refers to a person’s natural ability to locate their current location using natural abilities such as sight, sense, hearing, etc., whereas aided localization refers to the use of technological instruments to accomplish localization for a person. Outdoor and indoor aided localization are the two types of aided localization. There has been a lot of progress in the field of localization over the last decade. The development of modern communication technologies enabled positioning services to take place.
In outdoor environments, appropriate services have been provided through GPS to position and locate. GPS operates effectively with line of sight and does not suitable for indoor localization because the signals do not pass-through hard surfaces. Attenuation and dispersion are mainly caused by roofs, walls and many other objects. As a result, researchers have proposed and built various indoor localization systems, each with its own set of advantages and disadvantages. Some research results on indoor positioning have been produced in order to fill in the places that satellite navigation and positioning technology cannot cover, such as the indoor environment in parking lots, buildings, airport terminals, stations, and so on. Indoor positioning the majority of indoor location is based on the Received Signal Strength Indicator (RSSI). At the moment, most RSS-based indoor positioning algorithms use position fingerprint technologies, fingerprint positioning based on signal time of arrival (TOA) and angle of arrival fingerprint positioning does not require any additional hardware to generate perfect time synchronization or angular measurements.
There are two phases of location fingerprinting algorithms: offline phase and online phase. It is important to select a number of reference points and collect RSS at each reference point position corresponding00 to various Access Points (AP) during the offline phase, as well as to create a database collecting each reference point location and fingerprint corresponding to RSS. In the online phase, it is important to compare RSS from the terminal real-time measurement with RSS from fingerprint data in order to estimate the terminal’s position. The K-nearest neighbor algorithm (KNN) is one successful technique for estimating users’ locations by determining the centroid of the K closest neighbors. To minimize signal instability, the signal from the localization method is positioned by KNN algorithm.
Horus system models the probability statistic in radio map and stores the RSS Gaussian distribution in 2002. At the same time, the block cluster concept is offered for the first time. In comparison to competing systems, the approach reduces computational complexity and enhances positioning accuracy [1].
In addition to employing Wi-Fi, the authors developed a novel technique that combined noisy positional information estimated by the dead-reckoning method with location data gathered by RSS fingerprinting using algorithms such as ANN, KNN, NBC, and SVM with uncertainty. To achieve the integration, the sigma-point Kalman particle filtering (SKPF) algorithm is used [2].
Support Vector Machine (SVM) is a supervised learning technique for data categorization and regression that is powerful and commonly used for the indoor navigation system. SVMs have been widely used in practical applications such as text categorization, bioinformatics, and image recognition. The authors of this paper discussed Support Vector Regression (SVR) to create a model for determining the relationship between RSS information and its geographical location [3].
Using smartphones, the authors employed two approaches to estimate the user’s location. Sensor fusion technology is used in one of them to integrate the original data from the accelerometer and magnetometer inertial sensors to accurately determine the user’s position [4].
The authors proposed a target positioning method based on NN and KNN that enhances positioning accuracy while reducing the algorithm’s calculation time when compared to the neural network algorithm [5].
RSSI Wi-Fi-based ensemble technique for indoor localization is provided. The authors calculated the weights of four separate classifiers in the ensemble decision using the Dempster-Shafer theory of belief functions. To improve the accuracy of the classifiers, mean and standard deviation were added as features, along with RSSI Wi-Fi. The approach yields around 98 percent localization accuracy with a 2-meter localization error, according to the experiments. Although the addition of mean and standard deviation enhanced localization, the model did not account for the temporal autocorrelation inherent in the RSSI Wi-Fi signal [6].
The RSSI Wi-Fi signal was modelled using a Gaussian pdf. The user took several samples, which were then fitted to a Gaussian pdf. Finally, the parameters of the user’s fitted Gaussian pdf were utilized to estimate the user’s position using Machine Learning methods. Despite the fact that the authors utilized a Gaussian kernel to describe the signal, the temporal autocorrelation inherent in the signal was not used in the offline phase or online phase [7].
LoRa is low power wide area network (LPWAN) technology from Semtech (Camarillo, CA, USA) which is the physical layer of LoRa communication technology, long-range wide area network is the Media Access Control (MAC) layer in LoRa. It determines the protocol and system architectural communication for LoRa. LoRaWAN sets the battery life, communication range and service quality. LoRa allows long-range star architecture instead of the most commonly used mesh network architecture. In the star topology, individual nodes do not need to transmit data from nodes, which preserves energy efficiency and longer battery life. The battery of the LoRa module could have been in operation for over 10 years.
LoRa is a long-range, low-power wireless technology platform that utilizes the license-free radio frequency spectrum in the industry, scientific and medical. Thus, it is a physical layer used for long-range communication. To reach low power, many wireless technologies utilize FSK (Frequency Shift Key) modulation. FSK modulation makes it easy to demodulate with the possibility of a low error rate. However, LoRa uses Chirp Spread Spectrum (CSS) modulation to maintain low power features to the benefit of the growing scope of communication. It is the first implementation towards the commercialization of low-cost infrastructure through CSS. The basic principle is that the information is encoded with the help of a chirp. Prior to sending a message, the LoRa transmitter sends out a chirp signal to verify that the band is free to send the message. Once the LoRa receiver has taken the transmitter preamble chirp, the end of the preamble is signalled by the reverse chirp, which indicates to the LoRa transmitter that it is clear to commence transmission. The strong penetration of the LoRa signal enables it to ensure sufficient coverage in an indoor environment that is difficult to access localization. Compared with Wi-Fi or Bluetooth which are IoT-based solution that has a short range of data communication while maintaining a low developmental cost. All these features make LoRa become an attractive candidate for today’s market and make it capable of competing with other IoT technologies like Wi-Fi, Bluetooth, and so on.
Figure 1: LoRa Applications
Figure 1 shows the LoRa application areas. However, the LoRa technology is well suited for a wide range of industrial automation, medical and residential control and monitoring application.
The Received Signal Strength Indicator (RSSI) is one of the most widely used features for indoor localization. The measurement method’s primary premise is that it calculates the power contained in a signal conveyed from that of an access point to a client device or the other way around. The relationship between the strengths of the transmitted and received signals can be used to estimate the distance since RF waves attenuate according to the inverse square law. Presumably, as the number of devices increases, more data can be collected. Therefore, if accurate RSSI readings are acquired, the accuracy may be increased. The system is negatively affected by this. Increasing the number of devices would increase the amount of interference between different signals. Errors should be taken into consideration when estimating the distance between the two devices. Indeed, in wireless localization systems, the major challenge is that range measurements are often associated with errors. Even though RSSI is the least costly and easiest method to use, it does not offer the best accuracy. Filtering is necessary to eliminate noise and improve system accuracy using RSSI-based localization.
One of the most used algorithms for indoor positioning systems is K-nearest neighbour. The KNN algorithm can be used in supervised machine learning to solve classification and regression-related issues. The separation between patterns and reference patterns found in the database is used to identify the location. Calculating distances can be done using a variety of formulas, such as the Manhattan distance or the Euclidean distance. It chooses the best matching fingerprints based on their reciprocal distance and averages the locations of the same k patterns. Prior to that, the estimated position is determined using the reference points associated with these k fingerprints. Thus, the vectors serve as the primary element in pattern matching algorithms to determine the difference between the RSSI vector being evaluated and one of the fingerprints. KNN algorithm based on Euclidean Distance to find the nearest point is given by equation 1.
Consider the fingerprinting data base {RSSvi, RPxi}, where RP is the reference point. The RPxi displays, the location of the ith RP, an d the RP’s RSSvi is a vector of RSSIs, consisting of the elements {RSSI1, RSSI2, RSSI3,…,RSSIn}. The fingerprint that is closest to the current measurement in the signal space is simply chosen using this process. By determining the distance of each RP in the database vector from the tag based on their RSSs while taking Euclidian distance into account, the K nearest neighbors is really determined. The signal strength vector can be one of the following values- RSSI1, RSSI2, RSSI3,…RSSIj,…, RSSIn, where RSSIj stands for the RSS of AP (access point) jth and can be NULL if that AP is not detected. The Euclidian distance between the RSSIs of the ith RP and the user’s is then determined by:
|
|
The method was tested using a range of K values, and the outcomes were compared. In order to distinguish the nearest neighbour and prevent ties, the odd prime integers are typically used as the k value. To avoid situations when K neighbors include an equal amount of reference signals from various classes, K should ideally be a prime number [8]. There is more variance if K is less in value. Alternatively, if K has a bigger number, there will be more bias, so the data must be considered while selecting the correct K.
Figure 2: KNN Algorithm
Figure 2 shows the K nearest neighbour algorithm. According to the shown figure, class B will be chosen as a classification of the estimated position for K=3.
ADVANTAGES
KNN is most popular and efficient filtering algorithm. KNN find the distances between a access point and reference point by collecting the RSSI values, the chooses the closest value. This paper discusses about the LoRa, which is one of the wireless protocols designed specifically for long-range and low power communications. the position of the user in the indoor localization is estimated by measuring the RSSI values. It is one of the widely used feature for indoor localization. In order to remove the noise and increase the accuracy of the system the KNN algorithm is used.
REFERENCES