IPTEK The Journal of Technology and Science, 34.
, 2023 .
/pISSN:2088-2033, 0853-4.
DOI: 10.
12962/j20882033.
Received 26 March, 2024.
Revised 26 March, 2024.
Accepted 31 December, 2024
ORIGINAL RESEARCH
A New Indoor Positioning Approach based on Weighted K-Nearest Algorithm Akanni1 | A.
Isa2 | A.
Abdulrahman*3 | A.
Alao4 | O.
Ogun biyi5 1 Departement of Electrical and Electronics Engineering.
University of Ilorin.
Ilorin.
Nigeria.
Email: jimaka2005@gmail.
2 Federal Institute of Industrial Research.
South West Zonal Office.
Akure.
Ondo State.
Nigeria.
Email:
Abdurrhaman49@gmail.
3 Departement of Electrical and Electronics Engineering.
University.
University of Ilorin.
Nigeria.
Email:
abdulrahmanyusuf35@gmail.
4 Departement of Electrical and Electronics Engineering.
University.
University of Ilorin.
Nigeria.
Email:
ra@unilorin.
Abstract Many contemporary technological services rely heavily on precise location data within smartphone applications, making accuracy a crucial aspect of indoor positioning systems.
However, the variability in received signal strength (RSS) poses a challenge for achieving exact locations in Wi-Fi indoor positioning algorithms.
Traditional weighted k-nearest neighbor (WkNN) techniques typically utilize RSS spatial distance for selecting reference points (RP.
to estimate locations.
To enhance position accuracy, this study introduces a novel indoor positioning method based on WkNN.
By incorporating three geometrical distances of RSS .
hysical, spatial, and Canberr.
, this approach selects RPs and conducts position estimation using a fusion weighted strategy based on these distances.
Experimental findings indicate that the 5 Departement of Electrical and Computer newly proposed method outperforms the nearest neighbor (NN) technique.
More- Engineering.
University.
Kwara State University.
Malete.
Kwara State.
Nigeria.
Email: biyikan@gmail.
over, comparative investigations demonstrate its superiority over k-nearest neighbor .
NN) and weighted k-nearest neighbor (WkNN) algorithms.
Compared to NN, kNN, and WkNN algorithms, this novel technique improves positioning accuracy by Correspondence 9%, 32%, and 25%, respectively.
*Email: abdurrhaman49@gmail.
KEYWORDS:
Present Address Wi-Fi.
Access points.
Nearest neighbor.
Indoor positioning.
RSS.
Federal Institute of Industrial Research.
South West Zonal Office.
Akure.
Ondo State.
Nigeria
INTRODUCTION
Indoor localization is a valuable solution in scenarios where the global positioning system (GPS) is inadequate.
Unlike outdoor localization, which is well-established, indoor localization faces challenges in non-line-of-sight (NLOS) situations.
However, the broad installation of wireless equipment and the explosion of portable electronic devices have made precise indoor locating Arkani ET AL.
One attractive approach to this is positioning based on received signal strength (RSS) .
Various common wireless signals, such as Bluetooth .
Wi-Fi .
, ultra-wideband (UWB) .
, and radio frequency identification (RFID) .
, are frequently used for indoor positioning.
The determination of position also depends on existing algorithms for calculations, including direct positioning, geometric computations, and fingerprint localization.
Typical measurement techniques include time of arrival (TOA), angle of arrival (AOA), time difference of arrival (TDOA), and received signal strength (RSS) .
Among these techniques.
WiFi-based indoor positioning has become widely popular due to advantages such as not requiring additional hardware beyond access points (AP.
, adaptability to a variety of indoor settings, as well as the simplicity with which RSS data may be acquired.
The primary aspect of indoor positioning based on RSS fingerprint is the establishment of an RSS fingerprint database, which is subsequently compared with unknown positions (UP.
Each location within the positioning area receives distinct RSS values from each access point (AP), and these variations create unique confirmation data.
The positioning process typically consists of both offline and online phases.
During the offline phase, the main objective is to construct a fingerprint dataset by recording the RSS measurements at various predetermined reference points (RP.
based on the APAos positions, the desired positioning accuracy, and the entire covered area.
This stage is time-consuming and requires a significant amount of labor.
In the online phase, the system determines the position coordinates by matching the recently collected fingerprint of an UP with multiple known fingerprints from the well-structured database.
The fundamental idea for estimating UP is to calculate the similarity between the datasetAos fingerprint and the UPAos fingerprint.
The accuracy of positioning is influenced to different extents by the quality of the estimation algorithm and the reliability of the fingerprint dataset.
Among the numerous algorithms for indoor position estimation, machine learning-based methods are extensively researched.
The K-nearest neighbors .
NN) algorithm, a well-established machine learning technique, was initially introduced in the positioning field, and subsequent algorithms such as WkNN.
M-WkNN, and GK have been developed based on it .
Other machine learning techniques employed for indoor positioning include support vector machine (SVM) .
, k-means clustering .
, and deep neural networks .
The subsequent sections of the document will discuss related work and systematic literature studies concisely in Section 2.
The approach used will be detailed in Section 3, followed by the presentation and analysis of results in Section 4.
The studyAos conclusions will be summarized in Section 5.
RELATED WORKS
Wi-Fi indoor positioning utilizes Wi-Fi signals to determine a userAos location within indoor environments.
Traditional WiFi indoor locating algorithms fall into three categories: proximity, triangulation, and scene analysis .
These algorithms employ various methods to predict a cuserAos location based on Wi-Fi signals .
Proximity Algorithm The proximity algorithm identifies the Wi-Fi access point closest to the userAos device based on the highest received signal strength intensity .
This method relies on signal strength measurements for proximity determination but tends to provide less accurate results .
The accuracy of this algorithm is influenced by the spatial distribution and signal coverage area of Wi-Fi access points.
Triangulation Algorithm In contrast, the triangulation algorithm utilizes signal strength measurements from multiple Wi-Fi access points to calculate the userAos position using triangulation principles .
By analyzing the signal intensity of Wi-Fi transmissions from several access points and employing geometric calculations, this technique offers more precise location information compared to the proximity algorithm .
Arkani ET AL.
Scene Analysis Algorithm The scene analysis algorithm gathers scene attributes .
and estimates an objectAos unknown position by comparing online data with stored location fingerprints .
This technique often utilizes RSS-based location fingerprinting, incorporating fingerprints, magnetic fields, and even GPS signal intensity indoors .
The positioning process based on fingerprinting involves two steps: offline .
and online .
During the offline step, data is collected at each reference point, typically where a reference tag is deployed.
This data includes reference tag positions.
RSSI, and phase information, which are then stored to create a fingerprint database.
This database can subsequently be processed and trained using a machine learning approach to establish a model for the current environment.
Once the database or model is established, the online step involves estimating the position of the target tag by comparing the received signal to the database or trained model .
This algorithm analyzes Wi-Fi signals to determine the userAos position based on factors such as signal strength, quality, and environmental features .
Due to its accuracy and independence from Wi-Fi AP locations, the scene analysis algorithm is increasingly important in indoor positioning, offering precision and playing a significant role in this field .
Previous Researches Karakusak et al.
propose a computational approach based on fingerprint technology with two main phases: training and estimation.
Environmental conditions such as signal attenuation, interference, and multipath propagation can impact the algorithmAos Meng et al.
present an algorithm based on the Adaptive Neuro-Fuzzy Inference System (ANFIS) to enhance positioning accuracy, especially in non-line-of-sight scenarios.
Truong-Quang and Ho-Sy .
introduce the maximum convergence algorithm, achieving accurate positioning with mean accuracy less than 1.
02 meters in a laboratory setting.
Aboodi and Wan .
propose the WBI algorithm, combining RSS technology, trilateration.
Kalman filtering, and Least Square Estimation (LSE) to achieve an average accuracy of 2.
6 meters.
Jian and Hao .
propose a new Wi-Fi indoor location optimization technique based on the position fingerprint algorithm.
Rusli et al.
develop an improved Wi-Fi trilateration-based technique, solving the problem of received signal blocking caused by obstacles indoors.
Li et al.
propose a Wireless Indoor Positioning Algorithm using Principal Component Analysis (PCA) to select ideal samples and improve accuracy.
Keser et al.
offer an F-score-weighted indoor location method incorporating Wi-Fi-RSS and magnetic fingerprint (MF), strengthening system performance and obtaining precise indoor location.
Zhang et .
propose a novel position estimation strategy using radius-based domain clustering (RDC) to avoid AP selection issues and enhance accuracy and reliability.
Wang et al.
devise a sample point clustering approach to improve computational efficiency and mitigate noise and interference on Wi-Fi signals, enhancing indoor location accuracy.
This review finds a lack of extensive work on indoor locating algorithms, indicating the need for advanced approaches.
This article presents an improved WkNN algorithm utilizing physical, spatial, and Canberra distances for enhanced accuracy.
METHOD
The Proposed Algorithm This section introduces the enhanced indoor positioning weighted k-nearest algorithm based on physical, spatial, and Canberra distances of Wi-Fi RSS.
Figure 1 illustrates the framework of the proposed algorithm.
Physical, spatial, and Canberra distances of all reference points (RP.
are evaluated.
Three groups of k-nearest RPs are selected using these distances, and their weights are assigned inversely proportional to the respective distances.
Subsequently, similar RPs among the k-nearest RPs of the three distances are chosen to calculate the unknown locationAos coordinates, and their weights are reevaluated.
Finally, the estimated coordinates of the unknown location are calculated.
The physical distance is calculated using Equation 1 Ocyco ycE yaycn = yc=1 ycE yaycnyc Ocyco | yc ycc Oe yccycnyc | yc=1 || ycn = 1, 2, 3.
A , ycA Arkani ET AL.
FIGURE 1 The Proposed AlgorithmAos Framework ycc ya = yccycu 10 yccycnyc = yccycu 10 ycIycIycI.
ccycu )OeycIycIycI ya 10ycu ycIycIycI.
ccycu )OeycIycIycI ycn PD_i = Physical Distance of the i-th RP, l = number of APs, djC = distance of unknown location, d_ijC = distance of RP from AP.
RSS.
= RSS value measured at d_o from APs.
RSSJC = RSS value measured at unknown locations.
RSS_ijC = RSS value measured at RPs.
The RPs with the lowest PD values are chosen, and their weights based on PD, denoted by W_PD_i, are calculated by Equation 4:
ycE yaycn ycOycE yaycn = Ocya ycn=1 ycE yaycn K= numbers of RPs with smallest PD value The spatial distance is computed using the Euclidean distance given by Equation 5, and the weights of the spatial distance are calculated by Equation 6:
Oo SDycn = Ocyco yc=1 .
cIycIycI ya Oe ycIycIycIycnyc )2 yco ycn = 1, 2, 3.
A , ycA ycIyaycn ycOycIyaycn = Ocya ycn=1 ycIyaycn Furthermore, the Canberra distance and their weights will be computed by equation 7 and 8:
Arkani ET AL.
Ocyco yayaycn = .
cIycIycI ya OeycIycIycIycnyc | yc=1 .
cIycIycI ya | .
cIycIycI yc | ycn ycOyayaycn = Ocya ycn=1 yayaycn RP selection and weight recalculation are done using two methods: weight addition and weight multiplication, as expressed by Equations 9 and 10:
ycOycE yaycn ycOycIyaycn ycOyayaycn ycycn = Ocya .
cOycE yaycn ycOycIyaycn ycOyayaycn ) ycn=1 .
ycOycE yaycn ycOycIyaycn ycOyayaycn ycycn = Ocya .
cOycE yaycn ycOycIyaycn ycOyayaycn ) ycn=1 .
yaE = numbers of RPs common to PD.
SD, and CD.
Lastly, equation 11 yields the approximated coordinate of the unknown site:
C y.
C = ya Oc ycycn .
cuycn , ycycn ) .
ycn=1 .
C y.
C = coordinate of unknown location, .
cuycn , ycycn ) = coordinate of RPs.
The Experimental Setup The detailed map of the research location was created by measuring its full circumference, resulting in dimensions of 42 meters by 25 meters.
Each interior space within this area has a position that can be accessed and identified, forming the basis for dividing the surroundings into square grids.
Following the recommendation from .
, a grid size of 1 meter was chosen to provide finergrained positioning and enhance accuracy.
Care was taken to ensure that all grids were of similar size and aligned with the architectural elements of the space.
The experimental measurements were conducted on the second floor of the NLNG Building in the Faculty of Engineering and Technology at the University of Ilorin.
Figure 2 illustrates the perimeter of the experimental environment at the research location, while Figure 3 displays a selected interior region with square grids marked on the floor.
The optimal access point approach described in .
was utilized.
Due to the variability in device designs, different signals were received from each access point.
To mitigate this variability, only the Tecno Camon 18P smartphone model was employed in the measurement process.
The sample rate was set to two seconds, and to minimize potential orientation bias, the smartphone was randomly positioned and stabilized on a tripod.
RESULT AND DISCUSSION
This section explores the influence of weight recalculation on the selected RPs, thereby affecting positioning quality.
We delve into the three weight recalculation methods mentioned earlier.
Figure 4 illustrates the location error boxplots comparing the WKNN method to the proposed approach, which integrates both addition and multiplication weight computation.
The box plot includes the 90th, 75th, mean error, 25th, and 10th percentile Arkani ET AL.
FIGURE 2 Floor Plan for the Test Environment FIGURE 3 Selected Section of the Test Environment Notably, the mean position is 2.
10 meters and 2.
35 meters for the adopted addition and multiplication weight approach, respectively, surpassing the 2.
80 meters of the WKNN algorithm.
The weight multiplication approach outperforms the addition approach by spreading its weights across high-quality RPs, thus enhancing position accuracy.
FIGURE 4 Positioning Performance Comparison Furthermore, this study explores the impact of the pathloss exponent .
on positioning accuracy.
The results, shown in Figure 5 , reveal a decrease in positioning error with increasing n, followed by a subsequent increase.
For optimal accuracy, a value 4 and 3.
45 is recommended.
However, for this experiment, a slightly different value of 3.
32 is chosen due to the utilization of specific Access Points (AP.
with known positions.
Arkani ET AL.
FIGURE 5 Positioning Error with Varying Value of n CONCLUSION Additionally, the performance of the proposed approach is compared to three different algorithms: nearest neighbor (NN), knearest neighbor (KNN), and weighted k-nearest neighbor (WKNN).
Table 1 summarizes the statistics for each algorithm, demonstrating the superior performance of the proposed algorithm across all metrics.
TABLE 1 Positioning Statistics Comparison of the Four Algorithms Algorithm
KNN
WKNN
Proposed ME .
RMSE .
STD .
Table 2 provides a comprehensive overview of the positioning error, maximum error, and positioning time for NN.
KNN.
WKNN, and the proposed algorithm.
Compared to these algorithms, the proposed algorithm exhibits a significant reduction in positioning time, making it suitable for real-time applications.
A detailed comparison between the WKNN algorithm and the proposed algorithm is depicted in Figure 6 , highlighting the slower increase in positioning time for the proposed method as the number of test points increases.
This suggests that the proposed technique is well-suited for real-time locating applications requiring efficient computation.
TABLE 2 Positioning Statistics Comparison of the Four Algorithms Algorithm
KNN
WKNN
Proposed ME .
RMSE .
STD .
Arkani ET AL.
FIGURE 6 The Positioning Time of WKNN and Proposed Algorithm
CONCLUSION
This study introduces a novel and enhanced positioning technique based on three distinct geometrical distances.
The main aim is to select Reference Points (RP.
accurately for position determination.
To assess its effectiveness, an experiment was conducted in a real indoor scenario.
Results show that the proposed technique outperforms existing algorithms like Nearest Neighbor (NN), k-Nearest Neighbor .
NN), and Weighted k-Nearest Neighbor (WkNN) in positioning accuracy.
Notably, the Mean Error (ME) achieved by the new method is 2.
10 meters, significantly better than the ME values of NN, kNN, and WkNN algorithms.
Specifically, the proposed technique improves upon the ME of NN by 2.
09 meters, kNN by 0.
99 meters, and WkNN by 0.
meters, highlighting its superiority.
Moreover, the proposed algorithm significantly reduces positioning time compared to NN, kNN, and WkNN algorithms, by 3%, 46.
9%, and 55.
6%, respectively.
This reduction underscores not only the enhanced positioning accuracy but also the reduced computation time required.
Overall, the novel approach yields substantial gains in positioning accuracy compared to NN, kNN, and WkNN algorithms, improving positioning accuracy by approximately 49.
9%, 32%, and 25%, respectively.
Moving forward, future research should prioritize investigating improved Access Point (AP) selection techniques to minimize computation time and reduce positioning errors further.
By exploring and implementing advanced AP selection methods, researchers can continue enhancing the overall performance of indoor positioning algorithms.
Therefore, future studies should focus on addressing this critical aspect to contribute to the ongoing advancement of positioning techniques.
ACKNOWLEDGMENT
CREDIT
References