LoRaWAN fingerprinting with K-Means: the relevance of clusters visual inspection

LoRaWAN Fingerprinting with K-Means: the Relevance of Clusters Visual Inspection Joaquín Torres-Sospedra1, Michiel Aernouts2, Adriano Moreira1and Rafael Berkvens2 1ALGORITMI Research Centre, University of Minho, 4800-058 Guimarães, Portugal 2IDLab – Faculty of Applied Engineering, University of Antwerp – imec, Antwerp, Belgium Abstract LoRaWAN-based positioning is emerging as an alternative positioning solution for battery-constrained IoT devices or GNSS-denied areas in urban environments. The data collected at the LoRaWAN Base Stations, such as the RSSI of received messages, can be merged to generate an RF fingerprint. Unsupervised crowdsourcing can be leveraged to build a large radio map covering a urban area at the expense of introducing noise of around tens of meters when labelling the reference data. As fingerprinting may have a low efficiency in a such a dense radio map, we propose to use 𝐾 -Means clustering to make the position estimation faster. During our study, we found that clustering can also be used to detect large outliers in the radio map that can be subject to be removed. The rationale is to identify those samples within the cluster that are far from the geometric centroid of the cluster. This paper introduces the analysis of introducing 𝐾 -Means clustering with outlier detection and the benefits it might bring. Although removing outliers have not had an outstanding increase in the positioning accuracy, the performed analysis has enabled a new metric that is moderately correlated with the positioning error. This correlation may be useful to detect unreliable position estimates and discard them. The results presented in this work, based on two LoRaWAN datasets, show that the average and median positioning error can be improved by 5 % to 10 % by discarding 4 % to 6 % of operational samples. Keywords Fingerprinting, Clustering, Scalability, LoRaWAN 1. Introduction The Internet of Things ( IoT ) aims to interconnect a wide variety of objects, ranging from temperature sensors on mobile cooling containers to garbage bins in a city. In order to correctly interpret the measurements of such sensors, it is important to correlate them with location information. In many cases, IoT devices include a GNSS receiver for this purpose. However, this receiver only provides the device itself with location data, an Low Power Wide Area Network ( LPWAN ) such as LoRaWAN is often used to get sensor measurements and GNSS data to the user. This workflow is illustrated in Fig.1. ICL-GNSS’22: International Conference on Localization and GNSS, June 07–09, 2022, Tampere, Finland [email protected] ( Joaquín Torres-Sospedra); Michiel.A[email protected] ( Michiel Aernouts); [email protected].pt ( Adriano Moreira); [email protected] ( Rafael Berkvens)  0000-0003-4338-4334 ( Joaquín Torres-Sospedra); 0000-0002-0527-3871 ( Michiel Aernouts); 0000-0002-8967-118X ( Adriano Moreira); 0000-0003-0064-5020 ( Rafael Berkvens) ©2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) Figure 1: LPWANS are used to get sensor and location data to the user. Additionally, the user can access network metadata from the LPWAN. An important constraint on IoT communication and localization technologies is that they must be as energy-efficient as possible, because IoT devices generally operate for multiple years using small batteries. This, and the fact that GNSS can normally only be used in outdoor environments, has motivated researchers to omit power-hungry GNSS receivers and instead leverage the existing LPWAN link and sensor data for localization purposes. For example, metadata such as the Received Signal Strength Indicator ( RSSI ), phase or timing information from multiple LPWAN receivers can be translated to distance estimations between each receiver and a transmitting IoT device. However, these methods strongly depend on the LPWAN network deployment and generally lead to high location estimation errors. A previous analysis on the choice between GNSS and LPWAN localization shows that the latter should only be favored over GNSS when a large location error is justifiable and when the energy budget of an IoT device is extremely limited [ 1 ]. In practice, this means that implementing GNSS receivers on low-power IoT devices is often feasible. That being said, LPWAN localization can certainly still prove its use, because not all applications require location data with GNSS -like accuracy. For example, a construction company might only want to know at which of its building sites its assets are located, which implies that an error of hundreds of meters can be accepted. LPWAN localization can also play an important role in multimodal localization, for example as a fallback solution when a tracking device is moving into GNSS -denied areas such as tunnels or indoor environments [2]. Moreover, it may act as a verification mechanism to detect GNSS spoofing. In 2019, Aernouts et al. published an extended version of the LoRaWAN dataset described in [ 3 ]. Over a course of three months, 20 postal services cars carried LoRaWAN devices that periodically transmitted their latest GNSS location. As a result, the collected dataset contains 130430 entries with a ground truth location, the LoRa Spreading Factor ( SF ) used by the transmitter, timing data and Received Signal Strength ( RSS ) data for each receiving LoRaWAN gateway. It should be noted that the ground truth information was collected from GNSS receivers and, therefore, with potential errors of tens of meters. First, urban canyoning can decrease the GNSS accuracy, since the dataset is collected in a dense urban area. Second, the received GNSS coordinates of the transmitting device could differ from the actual device coordinates at receiving time because the total transmission time of a LoRa signal can take up to a few seconds, depending on the payload size and the SF . This effect becomes even more prominent when the transmitter travels at higher speeds. RSS data enables positioning with trilateration and fingerprinting. While the former requires knowing the location of the LoRaWAN Base Stations ( BS s), the propagation model and the environment obstructions; the latter only requires a set of reference data at known positions, also known as the radio map. In this paper, we focus on passive fingerprinting, where a fingerprint is the set of RSSI measurements of a particular LoRaWAN message transmitted by a device and measured in the available LoRaWAN BSs in the operational area. This technique requires two phases: the offline phase focuses on geo-referenced RSSI data collection (see radio map collection in [ 3 ]), whereas the online phase estimates the position of new fingerprints at unknown positions with, for instance, a 𝑘 -Nearest Neighbour ( 𝑘-NN )-based algorithm and the radio map. However, fingerprinting is computationally demanding if the dataset contains thousands of samples, e.g. LoRaWAN datasets in [ 3 ]. In those datasets, every single operational fingerprint has to be compared with all the reference samples in the radio map, even if they significantly differ, to obtain the most similar ones and compute the final position estimate. Thus, clustering techniques have been applied to split the radio map into several smaller versions [ 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 ]. In the operational stage, the identification of the most relevant cluster is done first (coarse search). Then, the position is estimated using the corresponding reduced radio map (fine-grained search). This two-step procedure is significantly faster that regular fingerprinting, specially in large datasets [15]. In this paper we propose a version of 𝐾 -Means clustering with outlier detection where noisy fingerprints are removed. We hypothetise that the clusters generated with 𝐾 -Means over the feature RSSI space can be de-noised by removing the reference samples which are significantly far for the cluster geometric centroid. It is worth noting that the proposed algorithmic solution is performed after generating the clusters with 𝐾 -Means. 𝐾 -Means clustering is an unsupervised model that groups similar data without, in this case, the location information (i.e., the labels). Thus, we consider that 𝐾 -MEANS basic principles cannot be significantly re-formulated to make it more robust. The main contributions of this work include: • Modification of 𝐾 -Means to remove outliers from clusters according to the geometric information; • Comprehensive comparison between applying 𝐾 -Means without and with ourlier detection; •A new metric which is correlated with the positioning error under some cases; •A procedure to discard unreliable position estimations. The remainder of this work is organised as follows. Section 2introduces the related work on LoRaWAN, fingerprinting and clustering. Section 3describes the materials and methods used in this work. Section 4details the experimental setup and shows the empirical results. Section 5 provides the final discussion and conclusions about this work. 2. Related work 2.1. LoRaWAN and fingerprinting LoRaWAN’s relatively wide bandwidth of 125 kHz to 250 kHz makes it a suitable candidate for both RSS -based and time-based localization. Thanks to the widespread availability of LoRaWAN networks and datasets, many researchers have evaluated the performance of various localization methods. For instance, Pospisil et al. evaluated the performance of five Time Difference of Arrival ( TDoA ) algorithms through simulation and validated two of them with field measurements. They achieved a mean location error of 543 m in a test area of 4.58 km2 [ 16 ]. The aforementioned LoRaWAN dataset by Aernouts et al. enabled many researchers to evaluate fingerprinting and machine learning approaches for localization. Pandangan et al. generated a hybrid dataset containing RSS and TDoA information based on the LoRaWAN dataset. Their hybrid dataset was then used to evaluate 𝑘-NN and Random Forest algorithms which resulted in a median error of 333 m and 194 m respectively [ 17 ]. This is a slight improvement compared to related research on Neural Network localization with the LoRaWAN dataset [ 18 , 19 ]. Purohit et al. also used this dataset for their research on Neural Network localization. In their investigation of three different learning models, the Long Short-Term Memory (LSTM) model with 64 neurons came out on top with a mean error of 191 m [ 20 ]. Janssen et al. compared the location accuracy, 𝑅2 score and evaluation time of ten Machine Learning algorithms using the LoRaWAN dataset. Their experiments show that the weighted 𝑘-NN and Random Forest algorithms result in the best accuracy and 𝑅2 score, but Random Forest has a significantly faster computation time [ 21 ]. In a subsequent study, the authors extended their comparison with range-based localization using eight different path loss models and six weight functions. Their best path loss model - weight function combination yielded an estimation error of 700 m , which is significantly higher than the 340 m obtained with fingerprinting. Furthermore, this work provides a comprehensive overview of the trade-offs that must be made between range-based and fingerprinting-based localization, including accuracy, complexity, cost, etc. [22]. 2.2. Clustering in fingerprinting Clustering has been widely applied in Wi-Fi and BLE fingerprinting to reduce the computational cost and keep similar accuracy, being 𝐾 -Means [ 4 , 5 ], including 𝐾 -Medoids [ 6 , 7 ] and Fuzzy 𝑐-Means (FCM) [8,9,10] variants, the most popular. Other approaches, such as Affinity Propagation Clustering ( APC ) [ 11 , 12 ] or Density-based spatial clustering of applications with noise ( DBSCAN ) [ 13 , 14 ], have also been explored but their feasibility may depend on the dataset according to some preliminary experiments we performed. Therefore, this work is focusing in 𝐾 -Means clustering, trying to take benefit from the position information of the reference data to remove those reference samples that may poison the radio map. To enhance the performance of 𝐾 -Means, we have used the Manhattan distance for distances computations in the feature ( RSSI ) space and the centroid initialization proposed in [23]. 3. Materials and Methods 3.1. 𝐾-Means in fingerprinting The core of the passive fingerprinting technique requires two phases: the off-line and on-line phases as explained before. In the off-line phase, reference fingerprints ( 𝑠𝑡 ) are generated from a set of received LoRaWAN messages (that include their position from GPS) by the available LoRaWAN BS , generating thus a radio map ( 𝒯 ). In the on-line phase, the operational fingerprints (from unknown positions) are compared to the fingerprints stored in the radio map. Their position is estimated using the locations of the most similar fingerprints in the radio map, usually computing their centroid. After generating the radio map 𝒯 , similar fingerprints in the feature RSSI space are grouped by 𝐾 -Means clustering algorithm. It is expected that fingerprints within a cluster would be also close in the geometrical space. The output of 𝐾 -Means provides the 𝐾 cluster centroids, 𝒞𝑖,∀𝑖∈[1, . . . , 𝐾] , and the reduced radio map for every cluster 𝒯𝑖,∀𝑖∈[1, . . . , 𝐾] . The centroids and reference fingerprints are both vectors representing the feature RSSI space, thus having as many values as LoRaWAN BSs. As an illustrative example, a few clusters over the LoRaWAN 2017/18 dataset are shown in Fig. 2. The gray dots represent the reference fingerprints in the radio map, whereas the coloured ones represent the samples in the cluster. The number of reference fingerprints and their dispersion in the geometric space depends on the cluster. 500 1000 1500 2000 2500 3000 200 400 600 800 1000 1200 1400 1600 1800 2000 200 400 600 800 1000 1200 1400 1600 1000 1500 2000 2500 3000 3500 4000 4500 500 1000 1500 2000 2500 3000 3500 4000 Figure 2: Example of six illustrative clusters generated by 𝐾 -Means in LoRaWAN 2017/18 dataset. Color indicates distance [m] to geometric centroid. In the operational phase, the search of most similar reference fingerprints is done in a two-step process. First, the operational fingerprint is compared to all the cluster centroids ( RSSI space) to retrieve the one reporting the lowest Euclidean distance. Second, the search of most similar reference fingerprints is done over the corresponding reduced radio map, 𝒯𝑖. 3.2. Analysis of clustering with 𝐾-Means Previous results in the literature show that 𝐾 -Means in fingerprinting reduces the computational cost at the expense of a slightly higher positioning error. This reduction on time is specially relevant in large datasets [24]. In this paper, the same clustering model has been applied to both LoRaWAN datasets, being 𝐾the squared root of the samples in the radio map as suggested in [24]. These results, which are shown in Section 4.2, were in phase with the results reported in the literature. However, to avoid the adoption of a black box approach while using 𝑘 -Means, an additional overall analysis on the clusters was performed. In particular, the location (longitude and latitude in WGS84 format) of the reference samples in the reduced radio map was visually inspected for each cluster, showing a relevant output in many clusters. Fig. 2shows six illustrative examples of the clusters generated with 𝐾 -Means. Despite their size and dispersion depend on the cluster, most of them report cases where the fingerprints are very far (reddish points in the figure) from the current geometric centroid and close to others geometric centroids. Those outliers share similar RSSI values with respect other reference fingerprints in the cluster, but thet geographically far from them. Among other factors, this effect may be caused by the positioning errors introduced by the GNSS receivers. 3.3. Removing noisy samples from clusters The idea to remove noisy samples from the radio map is simple. Given the samples (fingerprints) of a cluster, their geometric centroid (in the WGS84 space) is calculated. All samples whose distance to the geometric centroid is higher than twice the median value are removed. This is only applied to those clusters where the maximum distance is higher than 5 times the median value. i.e., it is only applied to those clusters having significant outliers. The proposed model is described in Algorithm 1, which has 3 stages: clusters generation (line 2), clusters cleaning (ln. 3–12) and position estimation (ln.15–22). First and second stage can be performed once per dataset, so their timing can be neglected when providing the computational costs of providing a position estimate in the online phase. 𝒯 is the radio map, 𝒱 is the set with the test/evaluation samples, 𝑘 is the number of nearest neighbors for 𝑘-NN . A sample (fingerprint) is represented with s and has 𝑁𝑏𝑠 elements (one for each LoRaWAN BS ), whereas its position is represented and its position (longitude and latitude in WGS84) with pos . For 𝐾 -Means, 𝐾 is the number of clusters ( 𝐾=√︀|𝒯 | as suggested in [ 15 ]), 𝒞 represents the clusters RSSI centroids and 𝒢 represents the clusters geometric lat/lon centroids. ˙ 𝒯𝑐stands for the clean reduced radio map for cluster 𝑐. The other parameters for the outlier detection were set based on the researchers experience. e.g., the threshold used to remove the noisy samples, 2 times the median distance, has been selected as the distances to the geometric centroid usually increase gradually. Algorithm 1 𝑘-NN for positioning with 𝐾-Means and outlier detection 1: input 𝒯,𝒱,𝑘,𝐾 2: 𝒞𝑖,𝒯𝑖←Apply 𝐾-Means to 𝒯 3: for 𝑖= 1 to 𝐾do 4: 𝒢𝑖←Compute geometric centroid of samples in 𝒯𝑖 5: 𝐺←{︀𝑔𝑒𝑜𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 (︀pos𝑗,𝒢𝑖)︀,∀𝑗∈ 𝒯𝑖}︀ 6: if 𝑚𝑎𝑥 (𝐺)>(5 ·𝑚𝑒𝑑𝑖𝑎𝑛 (𝐺)) then 7: // Remove samples far from geometric centroid 8: ˙ 𝒯𝑖←{︁s𝒯𝑖 𝑗∈ 𝒯𝑖:𝐺𝑗≤(2 ·𝑚𝑒𝑑𝑖𝑎𝑛 (𝐺))}︁ 9: else 10: ˙ 𝒯𝑖← 𝒯𝑗// No cleaning for cluster 𝑖 11: end if 12: end for 13: for 𝑖= 1 to |𝒱| do 14: Identify most relevant cluster, 𝑐 15: Set the reduced radio map ˙ 𝒯𝑐 16: for 𝑗= 1 to |˙ 𝒯𝑐|do 17: Compute distance between s𝒱 𝑖and s ˙ 𝒯𝑐 𝑗 18: end for 19: Sort distances in RSS space 20: Select the 𝑘closest candidates 21: Estimate position lat/lon 22: end for 23: Return: Estimated positions for all samples in 𝒱 4. Experiments and Results 4.1. Experimental Setup In order to assess the proposed clustering model with outlier detection, we have compared the results between the plain 𝑘-NN , the optimization rule proposed by Moreira [ 25 ], 𝐾 -Means without outlier detection and 𝐾 -Means with outlier detection. To estimate the final position, we have used the simple 1 -NN algorithm using the Euclidean distance. The models have been run 10 times to minimise the random initialization of 𝐾-Means. For the experiments, two datasets collected in the city of Antwerp between end of 2017 and beginning of 2019 [ 3 , 26 ] have been used, namely LoRaWAN 2017/18 and LoRaWAN 2018/19. Both datasets were collected to evaluate fingerprint localization algorithms in large outdoor environments and, according to the database authors, the RSSI of the LoRaWAN messages could hold an additional GPS error. This feature makes them appropriate for assessing the proposed algorithm to remove noise from clusters. For both datasets, the samples have been sorted by timestamp and then split for training and testing, the first ≈80% of samples have been used for training and the last ≈20% of samples have been used for evaluation. This division has been performed to avoid having data from the same device and day on both subsets, 𝒯and 𝒱. The evaluation metrics include the Averaged Positioning Error ( APE ), ¯𝜖 ; the Median Positioning Error ( MPE ), ˜𝜖 ; and the Averaged Operational Time ( AOT ), ¯𝜏𝑓𝑝 , and consider all the 10 execution runs. The APE and MPE are included in the ISO18305 standard, whereas the AOT refers to the average time required to process an operational fingerprint and provide the position estimate. In contrast to the plain 𝑘 -NN algorithm, where all fingerprints hold similar operational time, the operational time may significantly vary depending on the cluster. i.e., 𝐾 -Means clustering does not guarantee that all clusters are equally distributed, so the time required to perform the fine-grained search will depend on the selected cluster. Therefore, the standard deviation is also reported for the operational time. 4.2. Results This subsection is devoted to show the empirical results. First, a comparison with traditional fingerprint models is introduced. Then, a comprehensive analysis about the consequences of removing noise from the radio map is performed. Finally, the possible benefits of the proposed model are described. 4.2.1. Comparative analysis Table 1introduces the main results for the comparative analysis. It includes the plain 𝑘 -NN algorithm ( 𝑘= 1 ), the optimization rule based on common strongest anchor proposed in Moreira et al. [ 25 ], and 𝐾 -Means clustering without and with the outlier detection (OD). Fig. 3 introduces the Empirical Cumulative Distribution Function ( ECDF ) plots of the positioning error and operational time of the four methods for both datasets. Table 1 Main results: APE, MPE and AOT Lorawan 2017/18 Lorawan 2018/19 Method ¯𝜖[m] ˜𝜖[m] ¯𝜏[ms] ¯𝜖[m] ˜𝜖[m] ¯𝜏[ms] plain 𝑘-NN 558.3 374.1 2464.0 (13.7 )375.6 169.3 2518.2 (11.0 ) Moreira [25] 563.4 377.0 202.9 (149.7 )375.5 167.7 306.4 (223.9 ) 𝐾-Means 566.1 379.2 17.1 (7.3 )379.7 174.7 28.2 (16.0 ) 𝐾-Means OD 559.3 369.6 16.4 (6.8 )378.8 168.0 26.8 (15.5 ) In general, the four models provide similar results in terms of positioning error being the main difference their computational cost. The two solutions based on 𝐾 -Means report the lowest computational cost with an averaged execution time below 20 ms and 30 ms respectively. Removing the outliers not only made 𝐾 -Means slightly more accurate but also slightly more efficient in the operational stage as the proposed approach removed 8.6% and 9.5% of reference fingerprints on each dataset respectively. However, the improvements may be marginal. LoRaWAN 2017 LoRaWAN 2019 Figure 3: ECDF of positioning error and execution time for both datasets 4.2.2. A comprehensive analysis of removing noise Despite 𝐾 -Means without and with outliers detection having similar performance according to the previous results, positioning can be based on two sources, namely a noisy radio map and a clean radio map. This enables to exploit some additional information at the operational stage as there are samples where both approaches based on 𝐾 -Means (without and with outliers detection) do not agree in estimating the position. This happens in 12% and 32% of samples on each dataset, respectively. Thus, the evaluation set can be split into two subsets, one where both estimators agree and provide the same position estimation (“same” in table and figure), and the other where they disagree (“diff ”). Table 2and Fig. 4show the corresponding results and ECDFs. According to Table 2and the ECDF s plots from Fig. 4, the subset “same” is generally better than the subset “diff ” in both metrics, positioning error and execution time, specially in the first dataset (LoRaWAN 2017/18). i.e. when the two estimators –without and with outlier detection– agree, the positioning results are better that when they disagree. If both estimators disagree, the positioning error provided with 𝐾-Means with outlier detection is better.