A realistic evaluation of indoor positioning systems based on Wi-Fi fingerprinting: The 2015 EvAAL–ETRI competition

2.1. Open access datasets

In order to compare different IPSs, we must find a common input. Jain [31] calls the workload selection the most crucial part of a system analysis. Particularly, it must be representative of the real application, it must include the impact of external components, and it must allow for repeatability. Open access datasets are ideal for comparing different IPSs, given that they are collected in a way that would also happen in a real application. Since the datasets are static, they allow different researchers to apply their or others’ systems to the same data without much effort.

Two important open access datasets were contributed by the competition organizers. The first one was used in the competition [61] and is discussed in detail in Section 3.2. The other was published recently [63] and covers a single large room, where magnetometer data was collected, in addition to acceleration and orientation. This dataset features trajectories through the room, so that also tracking algorithms can be tested. Another important source of common data is the EVARILOS project [66]. From here, samples can be obtained from different locations, including offices and an industrial-like environment. Finally, some datasets available at Crawdad,5

The EvAAL–ETRI Indoor Location Competition aimed at establishing benchmarks and evaluation metrics for comparing AAL solutions.6

Tracks 1 and 2 were on-site and they took place at the IPIN conference venue in parallel to the conference. Competitors were allowed to survey the area the day before the day of the competition, but they could not deploy any external element to support positioning. At the competition, an external actor had to follow a pre-defined competition path, which reproduces the way people move within a big indoor environment. This path was disclosed 30 minutes before the competition. For Track 1 “Smartphone based positioning”, the competitors could use any sensor available on their smartphones. For Track 2, “Foot-mounted pedestrian dead reckoning positioning”, the competitors could use Micro-Electro-Mechanical Systems (MEMS) sensors (inertial, compass, and pressure sensors) for positioning, and external electronic devices, such as tablets or notebooks, for control and monitoring.

Track 3 “Wi-Fi fingerprinting in large environments” was off-site, the competitors had access to a large Wi-Fi fingerprint database, the UJIIndoorLoc database [61], to which they had to apply their algorithms off-line. Competitors only had to implement and set up their localization systems with the open access database. For the competition, a private testing data without labels (ground-truth locations) was provided to the competitors. Competitors had 6 weeks to provide their predictions about indoor location private testing fingerprint. This track is detailed in Sections 3.1 and 3.2.

Evaluating AAL Systems Through Competitive Benchmarking (EvAAL) was the first international competition aimed at comparing indoor localization systems, with its first edition organized in 2011. In 2014, two new competitions were born: the IPIN competition and the Microsoft Indoor Localization Competition – ISPN. The current EvAAL–ETRI competition is the continuation of the previous editions of EvAAL and IPIN competitions.

3.1. Competition details

In contrast to earlier EvAAL, IPIN and MS competitions, the 2015 EvAAL–ETRI competition featured an off-site track. Participants in this off-site track applied their IPSs to a large scale database containing Wi-Fi fingerprints (see Section 3.2). This allowed participants to prepare their systems, off-line and off-site, in advance. Moreover, the competitors had the same data to generate, configure and tune their IPSs. The idea was to estimate the locations of a private set of Wi-Fi fingerprints, whose ground truth was unknown for competition participants. The competition main aim was to fairly compare different approaches for multi-building, multi-floor positioning using a common reference database.

Each competing team had to register by submitting a short description of their IPS. This abstract was evaluated by the independent Technical Program Committee to asses its feasibility. The private test set (see Section 3.2) was released to all competitors in August 7th 2015 and the organizers scheduled the submission of the results (estimated positions) to September 20th 2015. All competitors had one month and a half to prepare their IPSs and submit up to five different sets of estimations. These estimations were evaluated by the competition organizers, who selected the best performing approach according to the mean positioning error for each team. We define the positioning error as the Euclidean distance between the real position where the fingerprint was taken and the estimated position provided by the competing IPS. Although this distance is computed in two dimensions, penalties are added for floor error and building error. In particular, we add 4 m for each wrong floor (absolute difference between the real and estimated floors) and 50 m if the building was not correctly estimated. The results were presented at the IPIN 2015 conference.

The four finalist teams that participated in the off-site competition were:

The Technical Program Committee was composed by independent experts: Machaj Juraj (University of Žilina, Slovakia), Christos Laoudias (University of Cyprus, Cyprus), Antoni Perez (Universit Oberta de Catalunya, Spain) and Robert Piché (Tampere University of Technology, Finland). The Organizing Committee was composed by: Joaquín Torres-Sospedra, Raul Montoliu, Sergio Trilles and Oscar Belmonte (Universitat Jaume I, Castellón, Spain).

3.2. The datasets for the off-site competition

The off-site competition’s datasets were collected at the Jaume I University [61]. Researchers of the INIT research group collected fingerprints in three buildings: two buildings with four floors, and one building with five floors. The total covered area is almost 110000 m², with 520 WAPs scattered through the environment. The fingerprints were stored in three datasets, two of which are publicly available for training and validation purposes, while the third dataset was provided as input data for the competitors’ systems. Ground truth and some information about the user was omitted to perform a realistic evaluation of the competing positioning systems.

The first dataset is the training dataset. It contains 19937 fingerprints, collected at 933 distinct locations. Each fingerprint includes its location. On average, 18 access points are visible in any fingerprint. At 71% of the locations there are 20 fingerprints or more, with up to 80 fingerprints at a single location. At only 2.36% of the locations there are less than 9 fingerprints. The average received signal strength for an access point is − 83.24 dBm . For the training dataset, users collected data in 6 days within the period running from May 30th to June 20th of 2013.

The second dataset is the validation dataset. It contains 1111 fingerprints, collected at 1074 distinct locations, where these locations do not exactly correspond to the locations of the training dataset. Each fingerprint includes its location. On average, 16 access points are visible in any fingerprint. At 98% of the locations there is only one fingerprint, with at most 8 fingerprints at a single location. The average received signal strength for an access point is − 77.66 dBm . For the validation dataset, users collected data in nine days within the period running from September 19th to October 8th 2013.

The third dataset is the one that was private to the competition organizers. It contains 5179 fingerprints, and only the organizers have access to the locations of where the fingerprints were collected. On average, 16 access points are visible in a fingerprint. The average received signal strength for an access point is − 72.02 dBm . For the private test dataset, users collected data in four days divided into two periods: 2 days around the end of November 2013, and 2 days at the end of March 2015. A total of 1395 testing fingerprints, more than 25%, were collected 19 months after the data collected for the radio map (training data).

The approach adopted by the RTLS@UM team to address the competition challenge comprises the creation of the radio map and the process used to estimate the positions associated to each one of the samples in the private testing dataset [51].

The following names and conventions are used in the next paragraphs:

Since each team was given access to a training (T) and validation (V) datasets, both datasets including the position (building, floor and latitude/longitude coordinates) associated to each sample, joining both datasets ( T ∪ V ) to build the radio map maximizes the available information about the covered area. Moreover, the samples in V are more recent that the samples in T, include information about 55 new WAPs not observed in T, and map some new locations not mapped in T.

Since both datasets (T and V) are made from samples collected by a multitude of different devices, an approach inspired on the work of Laoudias et al. [39] was used to normalize the RSSI values. The normalization process first computes rssi d as the average RSSI value across all the samples in the radio map, for all WAPs, as measured by device d. This is called the representative RSSI value for device d. The mean of all representative RSSI values, RSSI D , can then be used to compute the deviation of each device d from the mean: Δ rssi d = RSSI D − rssi d . By subtracting this deviation value Δ rssi d from all the RSSI values measured by device d, a normalized radio map is obtained.

The position estimation process is based on a hierarchical approach designed for large-scale multi-building, multi-floor settings where computational effort is to be minimized. Given a fingerprint fp 0 taken at an unknown location, the process starts by estimating the building (b) where it was collected, as follows:

Take WAP 0 1 , the strongest WAP observed in fp 0 .

and requires that each entry in the radio map be appended with the index of its strongest WAPs (strongAP1, strongAP2, …), which is done only once while building the radio map. This query might have to be repeated (step 3 above), by replacing strongAP1 by strongAP2 and so on, if the result set is empty, which is quite unlikely.

Floor (f) estimation is achieved by a combination of filtering, k-NN classification, and majority rule-based selection operations, as described by the following procedure:

Build R ′ , a subset of R, with all the samples from the building b estimated in the previous process (building estimation) (filtering).

After estimating the floor, the geometric coordinates are estimated based on a simple k-NN classification procedure as follows:

Build R ‴ , a subset of R ″ , with all the samples where the floor f is the one estimated in the previous process (floor estimation) (filtering).

3.4. The HFTS team competing system

The HFT Team competed with two algorithms: The “Fingerprint Calibrated Weighted Centroid” (FCWC) method and the “Scalar Product Correlation Fingerprinting” (SPCF) algorithm.

The first approach uses weighted centroid to calculate the rover position. For this approach, the position of the WAPs are needed. Since these WAP positions were not known, they were estimated using the calibration dataset of the competition: from the existing RSSI readings of a certain WAP at different test points, the position of this WAP was calculated using weighted centroid. This “reverse positioning” is performed once to generate an WAP position database.

The second approach uses processed fingerprints to estimate positions via k-NN. The SPCF algorithm performed slightly better in the competition. Therefore all numbers and scores in the paper, which belong to the HTF team, have been obeyed with the SPCF algorithm.

Both algorithms are model based: The Frijs equation [22] with modified propagation exponent n (see for example [29]) is used to translate an RSSI value into an inverse distance estimation: (2) w = 10 S [dBm] / ( 10 · n ) , if S ≥ RSSI min 0 , otherwise , where w is the inverse distance, S is the measured RSSI value, and RSSI min is a lower RSSI threshold. The equation does not contain a constant factor representing the transmission power, as both algorithms would eliminate that constant anyways.

For the FCWC algorithm, the inverse distance is used as weight for the summing of the WAP positions. For the SPCF algorithm, inverse distance vectors are compared using the scalar product as comparison norm: U , V are two vectors of weighted RSSI values U : u q = w ( RSSI U , q ) respectively V : v q = w ( RSSI V , q ) , with q denoting the WAP index. For missing values a weight of zero is assigned to u q respectively v q . The normalized scalar product, Eq. 3, is used as a measure for the equality of two RSSI vectors. (3) nsp ( U , V ) = cos ( α ) = ∑ u q v q | U | | V |

Where nsp values vary between [ − 1..1 ] , with higher values indicating higher correlation or “nearness”.

The position estimate is obtained by using k-NN with that norm: Those three positions R i of the training points with the highest correlation values are averaged with a weight of 2, 1 and 1, in descending correlation order, and the result is the position estimate. The propagation exponent n and RSSI min are determined manually for both algorithms, globally as well as for each building, by minimizing the positioning error for the training dataset. A more detailed description is given in [35].

An important competition task is the building and floor estimation. For both described algorithms, positions are always three dimensional coordinates and comprise ( x , y , z ) , i.e. northing, easting and height. The z component for the calibration measurement positions is generated using the floor ID. The algorithms, i.e. FCWC and SPCF, operate on these three-dimensional coordinates and therefore produce not only a ( x , y ) result but also a z result. No special algorithm for building- and floor-ID determination is applied. Instead, a bounding box is defined for each building, and the building ID for a certain measurement is obtained by matching the calculated x and y coordinates with the boxes. The floor ID is given by the z component of the position estimate.

3.5. The MOSAIC team competing system

The MOSAIC competition system is based on the Wi-Fi positioning system that was included in the Opportunistic Seamless Localization system [67]. This system defines weights for three distinct situations in Wi-Fi fingerprint comparison. The comparison is between a fingerprint collection that describes the radio map, and a fingerprint that is measured for localization. Each access point in the measured fingerprint is compared with the corresponding access point of a fingerprint in the collection that describes the radio map, for each fingerprint in this collection. The fingerprints in the collection are the mean values of all fingerprints measured at that location during the training phase. In the competition, the team used only the training dataset values.

The three situations are: first, the access point in the measured fingerprint was also measured with some received signal strength in the collection’s fingerprint – defined as a hit; second, an access point in the collection’s fingerprint does not occur in the measured fingerprint – defined as a miss; third, an access point in the measured fingerprint does not occur in the collection’s fingerprint – defined as an extra. The MOSAIC team additionally defined the situation where an access point does not occur in both the measured fingerprint and the collection’s fingerprint – we call this a none.

The MOSAIC system calculates the likelihood of the given situation for each access point in the measured fingerprint. To compute the likelihood of the measured fingerprint, the algorithm multiplies the likelihoods of the access points, assuming that they are independent [7]. By normalizing the likelihood of the measured fingerprint over all locations in the training dataset, the algorithm can calculate the posterior probability distribution of the location given the measured fingerprint. It then selects a location by using k-NN, with k = 3 , weighted by the posterior value.

Adapting the MOSAIC system to the competition data representation required little effort. There was a slight difference in location specification: the MOSAIC system uses a relative system without any floors, while the competition data uses an absolute system in different buildings and floors. This only influences the interpretation of the results, it has no influence on the MOSAIC likelihood calculation, which is by design agnostic to the position representation. However, since a k-NN is also implemented, the floors and buildings have to be taken into account. The building and floor identification numbers are weighted by the posterior value, just like the position is, and then rounded to again obtain a building and floor identification number.

3.6. The ensemble approach

Ensembles are commonly used in regression and classification tasks to combine a set of individual estimators (classifiers or regressors) [19,59]. The error may be reduced when the individual estimators have a high degree of diversity [64,65].

Here a simple ensemble approach has been developed as a first attempt to fuse the three competing systems in an advanced IPSs. The main idea was to try to combine the strengths of all the competing systems. Although there were four finalists in the competition, only three of them accepted to include their system in the ensemble and participate in the elaboration of this paper. The ensemble works as follows:

The results – error and building&floor hit detection rate – of the three competing IPSs before the competition on the validation set, included in the short description or implemented by the organization committee, have been used to set the priorities in Steps 3 and 4. In particular, the hit rate is used to establish the priorities in Step 3, whereas the error in positioning is used to establish the priorities in Step 4.

4.1. Baseline results

A baseline based on the k-Nearest Neighbor rule (k-NN) [15] is introduced for comparison purposes. In particular, the k-NN algorithm with k = 1 and the Manhattan distance (or city block) as base distance to calculate the closest(s) neighbors is used for the baseline. The reference dataset is generated from the training and validation subsets of the UJIIndoorLoc database using the Positive values data representation [62] (see Eq. (4)), where the new low values stand for low signal (0 means that the WAP has not been detected) and the higher values indicate that the signal is stronger. Finally, all the WAPs (520 in this work) are considered to calculate the Manhattan distance between two fingerprints in our implementation of the 1-NN algorithm, it even compute those WAPs which are not detected (value 0) in any of the two compared fingerprints. The results of this baseline are shown in Table 2, where the mean error and the percentile values are based on the positioning error with penalties described in Section 3.1. (4) NewRSSI = OldRSSI + 105 if OldRSSI < 0 0 otherwise

According to the results shown in Table 2, the baseline mean error is 8.46 m but the floor hit rare is 85.34%. In all the cases, the building has been correctly estimated.

The results of the competing teams are shown in Table 3. Again, the mean error and the percentile values are based on the positioning error with penalties described in Section 3.1. Moreover, the results of the simple ensemble approach (see Section 3.6) are also included in the table.

According to the results shown in Table 3, the RTLS@UM IPS provided the best competing results according to the mean positioning error (including the floor and building error penalties) and, therefore, this team was the winner of the off-site track in the 2015 EvAAL–ETRI competition. Moreover, this team also reported the lowest error in most of percentile values. Although the competition metric was the mean error, the EvAAL website reports ranks based on the third percentile for all the tracks. In the off-site track, ranks provided by the mean error and third quartile are identical.

Although the HFTS team reported a mean error similar to the baseline, it provided the overall highest floor hit rate (96.25%). The HFTS’s IPS reduces the wrong-floor errors in a 2.5% with respect to the teams with highest hit rate.

The MOSAIC team provides the third best 25th and 50th (median) percentiles and also the second best Floor hit rate among the competing IPSs. In contrast to the other competing IPSs, it reports a Building hit rate of 98.65% which had a negative impact on the mean error.

The ICSL team reports the second lowest mean error. However, it was the competing team reporting the lowest floor hit rate.

The ensemble approach, which combines the three competing IPSs, provides the best overall results. The three competing systems equally contributed on estimating the building and floor (see Table 4). The coordinates were mainly provided by the RTLS@UM system (96.97% of cases) and the rest were provided by HFTS system (3.03% of the cases). Although the ensemble improvements with respect to the best errors and hit rates are marginal, they are not when the ensemble is compared to

For RTLS@UM system, the ensemble and the individual competing systems. similar errors in positioning but the ensemble provides a hit floor detection rate 3% higher. For HFTS system, both provide similar hit detections rates but the ensemble provides a positioning error about 2.4 m lower. The ensemble takes benefit from the three independent competing systems, it provides the highest floor hit rate and the lowest positioning error.

OPEN IN VIEWER

Fig. 1.

Distribution of the errors in positioning with penalties for the baseline, competing IPSs and ensemble.

Figure 1 shows the Cumulative Distribution Function (error in positioning with penalties) for the baseline, the competing IPSs and the ensemble approach. In the figure, it can be seen that there are two differentiated groups of IPSs. The first group reports the lowest error and it is formed by the IPS developed by RTLS@UM IPS and the ensemble, whereas the baseline and the IPSs developed by MOSAIC and HFTS form the second group. On the second group, the IPS developed by ICSL reports the lowest error. Among the other systems, the IPS developed by MOSAIC tends to be the one until the 35th percentile and the IPS developed by HTFS tends to be the best from 60 to 95 percentile. Although the differences between two IPSs are marginal in some cases, the error function does not explicitly include the floor hit rate. As stated in [10] wrong-floor errors may not be acceptable at all because it is much easier to move within the same floor than among floors. Although the results reported by the ICSL team and the baseline are similar to the IPS provided by HFTS and MOSAIC, they should be discarded due their low floor hit rate.

This section introduces the discussion derived from the competing systems, the results shown and the experiences reported by the competitors.