Keywords

1 Introduction

In indoor environments, where GPS based localisation cannot be used, alternative techniques must be considered. One of such techniques is Fingerprinting, which is the most used method for indoor localisation [3].

Fingerprinting comprises two distinct phases [2, 7, 10]: the off-line phase where information about wireless signals are acquired and stored in a database; the on-line phase where the location is estimated, by comparing data stored in the database and data collected on that moment. During the on-line phase it is used a Fingerprint Map (FM), generated using data collected during the off-line phase. The Location Estimation Algorithm (LEA) uses the FM information to map spatial and signal domains to estimate the mobile node coordinates.

As long as it is possible to have access to the incoming wireless signal properties, such as the Received Signal Strength (RSS) value, any wireless technology can be used for Fingerprinting-based localisation. However, if the objective is to develop Location Based Services (LBS) for use with smartphones, a wireless technology supported by such devices must be used. It also must be taken into account that better accuracy values are obtained for shorter range communications [9].

Because WiFi (IEEE802.11) is an ubiquitous technology, available on most smartphones, it is a good choice when creating localisation systems based on consumer electronics products. According to [3] Wireless Local Area Network (WLAN) based localisation systems are dominant indoors. Also such systems have the advantage of not requiring new or proprietary hardware.

Even though good results can be obtained using Fingerprinting localisation based on WLAN, this is not an error free technique. Wireless signals are absorbed by obstacles, including the human body, so users may influence the RSS values. When holding a smartphone, the user will cause the fading of wireless signals irradiated by the Access Points (AP) that are located behind him/her.

As a consequence of this radiation absorption by the user, if an FM is built using data collected only in one direction, it will not be very useful in a real-life application, because during the on-line phase the user might be facing the opposite direction.

A simple (and commonly used) solution to cope with this problem is to acquire data (during the off-line phase) facing different directions (the user rotates 360° while acquires the FM data). The resulting FM can be calculated by averaging all the acquired values.

Another, and more efficient solution, would be to use the most suitable information collected during the off-line phase. Instead of creating a single FM, multiple maps can be generated (one per direction, e.g. North, South, East and West) and at the on-line phase the most suitable map (or set of maps) can be used by the Location Estimation Algorithm. Most of the recent smartphones have a magnetic sensor that can be used to estimate the user’s direction.

Collecting data to build an FM is a time consuming task, if more maps are added (which will be the case), then more time is needed to collect data. This can be overcome by building the FM using propagation models, as presented in [8]. Using this solution it is only needed to add the user as an obstacle and generate the FM.

In this paper it is presented an approach to location estimation using multiple FM as presented by the authors in [5], and the performance of this approach is assessed both using Fingerprint Maps generated with real data acquired in the testing scenario and generated using propagation models. In the presented tests four maps are generated (North, South, East and West) and the assessment of the method feasibility is made using three of the classic LEA: Nearest Neighbour; k-Nearest Neighbour; Weighted k-Nearest Neighbour. To select the best map(s) to be used by the LEA, information provided by the magnetic sensor of an Android smartphone is used.

2 Directional Fingerprint Maps

In this section it will be presented the rational behind the use of multiple FM, the implemented algorithms to choose the correct map and how the maps can be generated without the need to collect RSS values.

2.1 User Interference

During the off-line phase, data must be collected at each spatial point that will be used in the FM. These data include the value of the power that the mobile node receives from the fixed references. When WiFi is used, these references are the network Access Points. The power received by the mobile node, from each AP, is given by Eq. 1:

$$ P_{r} = P_{t} + G_{t} + G_{r} - PL_{tot} $$
(1)

where \( P_{r} \) is the received power (in dBm), \( G_{t} \) and \( G_{r} \) the gains of the transmitting and the receiving antennas (in dB or dBi) and \( PL_{tot} \) is the summation of all losses that electromagnetic waves suffer while travelling between the transmitter and the receiver (in dB).

In Eq. 1, the total path loss (\( PL_{tot} \)) is the result of the free-space path loss and losses due to the presence of obstacles between the transmitter and the receiver. Free-space path loss can be expressed as a function of the distance between the two wireless nodes [1] (Eq. 2):

$$ PL(d) = PL(d_{0} ) + 10N{ \log }\left( {\frac{d}{{d_{0} }}} \right) + X_{\sigma } $$
(2)

where N represents the path loss exponent (which may vary according to the structure of the building [4]), \( d_{0} \) is an arbitrary distance, \( X_{\sigma } \) denotes a Gaussian variable with zero mean and standard deviation \( \sigma \).

Losses due to the presence of obstacles are caused by obstacles found in buildings. Propagation models like COST and Motley-Keenan consider the attenuation due to walls and furniture [8]. However there are other obstacles inside a building that can attenuate wireless signals. The user that is holding the smartphone will also absorb electromagnetic waves. In the literature it can be found that the absorption by a single human body may cause an attenuation as much as 3.5–5.0 dB [2, 11].

Let us consider that for indoor \( N = 3 \) [4] and \( d_{0} = 1\;{\text{m}} \) [8], using Eq. 2, an excess attenuation 5.0 dB is the equivalent to the user moving 1.78 m. This will obviously have a negative impact of the LEA performance and decrease the location estimation precision.

2.2 Multiple Fingerprint Maps

Because it is not feasible to force the user to face the direction at which the FM data was acquired, the proposed solution is to build multiple maps, and during the on-line phase, select the best map(s) to be used by the LEA. For this solution to be possible it is needed to know the user’s direction, both during the on-line and off-line phases of Fingerprinting-based localisation.

Nowadays, using a smartphone, it is relatively easy to know which direction the user (or the smartphone) is facing, e.g. using the magnetic sensor as a compass. If the azimuth value is also stored in the database when FM data is collected, then it will be possible to build multiple maps.

It is not feasible to collect data in every direction because too much data would have to be collected, at each spatial point, to build multiple Fingerprint Maps. Also the azimuth value reported by the sensor has slight changes, even when the smartphone is not moving. The trigonometric circle can be divided into n slices (n is a small value). If \( n = 1 \) then we have the “traditional” FM based on the average of data collected in all directions. In Fig. 1 it is presented an example with \( n = 4 \).

Fig. 1
figure 1

Example using 4 slices

Full size image

As an example in Fig. 1 the four directions are North, South, East and West. It is not mandatory to use these directions. Any direction can be used, as long as the following conditions are met:

  • Directions are fixed, and the same for all spatial points, otherwise it will not be possible to build a reliable set of maps;

  • The trigonometric circle is divided evenly in n slices. Each slice has an amplitude (in °) given Eq. 3.

$$ \alpha = \frac{{360^{ \circ } }}{n}. $$
(3)

To choose the best map(s) to use with the LEA, two approaches have been considered:

  • Direct Map—Only one map is chosen, based on the azimuth value;

  • Weighted Maps—The contribution of each map to the final location estimation is calculated as a function of the azimuth value.

One of the objectives of the authors is to maintain compatibility with previously implemented location methods, i.e., the multi Fingerprint Maps can be used with any LEA, without the need to modify it.

2.2.1 Direct Maps

With Direct Maps, from the set of n maps that are built, only one FM is selected. This selection is based on the azimuth values reported by the magnetic sensor. The selected FM is fed to the LEA that estimates the user’s location (Fig. 2). From the LEA point of view, there is only one FM.

Fig. 2
figure 2

Working principle of the “Direct Maps” method

Full size image

Let us consider that data was collected facing n directions (\( d_{1} ,d_{2} , \ldots ,d_{n} \), with \( 0^{\circ } \le d_{i} \le 360^{\circ } \)), map \( i \) is selected if the current azimuth value (\( \beta \)) meets the condition:

$$ d_{i} - \frac{\alpha }{2} < \beta \le d_{i} + \frac{\alpha }{2} $$
(4)

This is a simple solution, that requires the same computational power as the original LEA. There is only one additional step, which requires low computing power: select the most suitable FM based on the azimuth value.

2.2.2 Weighted Maps

Because the azimuth value might not be stable, in the above method if its value is too close to the boundary values (\( d_{i} - \frac{\alpha }{2} \) or \( d_{i} + \frac{\alpha }{2} \)) the algorithm could be constantly alternating between two maps.

In these conditions, the best choice could be using information of FM i and FM i−1 or FM i and FM i+1. This is the working principle of Weighted Maps. Based on the current azimuth it is calculated the contribution that each map will have in the final estimation of the user’s location (Fig. 3). Then an weighted average of all coordinates estimated by the LEA (one per map) is calculated, to estimate the user’s coordinates.

Fig. 3
figure 3

Working principle of the “Weighted Maps” method

Full size image

In this work a linear weight function, Eq. 5, based on the angular distance of the azimuth value to the reference value is used.

$$ w_{i} = {\begin{array}{*{20}l} {1 - \frac{{|d_{i} - \beta |}}{\theta }, \, } & { 0 \le |d_{i} - \beta | \le \theta \, } \\ {0, \, } & {|d_{i} - \beta | > \theta \, } \\ \end{array} } $$
(5)

where \( w_{i} \) is the weight of map i, β and \( d_{i} \) are as above and θ is a value chosen by the developer. The value used for θ, together with n, define the maximum number of maps that are considered in the location estimation. For example if \( n = 4 \) and \( \theta = 45^{ \circ } \), then 2 maps are used.

For each map (i) that meets the condition \( w_{i} > 0 \), the user’s location is estimated (without considering the weight). The final user’s coordinates is then calculated as in Eq. 6:

$$ P(x,y) = \sum\limits_{i = 0}^{j - 1} {\frac{{w_{i} }}{w}} \times P(x,y)_{i} $$
(6)

where \( P(x,y) \) is the estimated user’s location, j is the number of maps that meets the condition \( w_{i} > 0 \) and \( P(x,y)_{i} \) is the user’s location estimated using map i and w the summation of all weights.

Because the location is estimated for each map, it is possible to use multiple maps with Location Estimation Algorithms that were not developed to use it. Each execution of the LEA is independent.

Compared with the previous solution, the computational time is increased (j times). However a possible alternative would be to generate a new FM, e.g. by doing an weighted average of the maps, for each execution of the LEA. If the maps have many points, the computational requirements would also be increased (for each point an FM had to be created) and the memory requirements would also increase (to store \( n + 1 \) maps).

2.3 Generating the FM Using Propagation Models

Because collecting data to generate multiple FM is a very time consuming task, the Fingerprint Maps can be obtained by simulation, i.e., using propagation models to predict the RSS values at each point of the FM. To build such maps we have to consider the effect of the free-space attenuation, the attenuation due to obstacles (e.g. walls) and the user interference.

Because of the results obtained in [8], to model the FM it was used the a modified Motley-Keenan model, which is based on Motley-Keenan model, Eq. 7:

$$ PL(d) = PL(d_{0} ) + 10N{ \log }\left( {\frac{d}{{d_{0} }}} \right) + \sum\limits_{i = 1}^{N} {k_{i} L\omega_{i} } $$
(7)

where:

  • \( {k}_{{i}} \): the number of walls of type i;

  • \( {L\omega }_{{i}} \): attenuation factor for walls of type i.

The above model does not consider wall thickness, so the adjusted model of Eq. 8 was considered:

$$ PL(d) = PL(d_{0} ) + 10N{ \log }\left( {\frac{d}{{d_{0} }}} \right) + \sum\limits_{i = 1}^{N} {k_{i} L_{0i} 2^{{{ \log }_{3} (\frac{{\varepsilon_{i} }}{{\varepsilon_{0i} }})}} } $$
(8)

where:

  • \( {L}_{{0{i}}} \): is the attenuation of a reference wall with thickness \( \varepsilon_{0} \);

  • \( {k}_{{i}} \): is the number of type i walls that have thinness \( \varepsilon_{i} \).

To the above model we have also to add the attenuation due to the presence of the user. It was considered that the user is always facing the mobile terminal, so the user acts as an obstacle, with constant attenuation, between the mobile terminal and the Access Points behind him/her.

Also a random value (\( X_{\sigma } \)) must be added to the final RSS values, as in Eq. 2. These values add some randomness to the FM, making it more similar to the real values typically found in Fingerprint Maps acquired using a mobile terminal.

3 Testing Scenario and Conditions

To assess the feasibility of the proposed methods, data was collected in a building at the Campus of the University of Trás-os-Montes and Alto Douro. These data were used to generate the Fingerprint Maps and to off-line test the “Direct Map” and “Weighed Maps” methods.

In Fig. 4 it is depicted the map of the area where data was collected. In the map are marked the spatial points where RSS samples were acquired and the location of the reference Access Points. At each spatial point of the map, data was collected facing four directions: North, South, East and West. At each direction 20 samples of the received power of all AP, the azimuth and the magnetic field values were recorded.

Fig. 4
figure 4

Map of the testing scenario

Full size image

To collect data it was used an Android smartphone running an application developed by the authors for these tests. Because all the tests must be made using the same data, no data processing was made in real-time with this application. All data was stored in XML (eXtensible Markup Language) files and processed off-line.

To compare the performance of the proposed methods with other methods to generate the FM, in the present work the following classic LEA were used:

  • Nearest Neighbour (NN)—it is assumed that the current coordinates of the mobile node (in the spatial domain) are the coordinates of the nearest point (in the signals domain);

  • k-Nearest Neighbour (kNN)—the k nearest neighbours (in the signals domain) are selected, and then it is assumed that the mobile node coordinates (in the spatial domain) is the average of the spatial coordinates of those k points;

  • Weighted k-Nearest Neighbour (WkNN)—similar to kNN, however an weighted average is used to estimate the user’s coordinates.

Results presented in Sect. 4 were obtained considering \( k = 3 \) for kNN and WkNN, and, as in [9] the used weights (from the nearest to the furthest point) were 0.7, 0.2 and 0.1.

4 Numerical Results

In this section are presented the results obtained by the proposed methods, using data collected at the testing scenario. First are presented reference values, obtained in tests made for performance comparison. These reference tests also allow to demonstrate how the presence of the user can influence the location estimation accuracy. After, are presented the results that were obtained using the methods proposed in this paper.

Results obtained with the “Direct Map” and “Weighted Maps” (both for FM built using acquired data and FM built using propagation models) are divided into two subsections. First are presented the results that were obtained using four maps (N, S, E and W) and the user facing the same directions. After, are presented the results of two other tests where the same four maps were used, but the with user facing one of eight possible directions (N, NE, E, SE, S, SW, W and NW).

For all tests are shown the normalized values for the Precision, Standard Deviation, Maximum Error and Minimum Error, obtained using the three LEA.

4.1 Reference Values

Because one alternative to the use of multiple maps is to build a single FM, based on data collected in all directions, the first test was made with such an FM. The FM used in the test, which results are presented in Table 1, was built by averaging RSS data collected in the four directions.

Table 1 Results using the FM based on all directions
Full size table

These values are presented here as reference values, and will be used for performance comparison.

The next test consisted in generating an FM per direction and do the location estimation of an user facing the same direction as the FM, during the on-line phase. Results of this test are presented in Table 2. This is not a feasible solution for a real-life location system, however it can be used as the best case scenario. These are the best values that can be achieved using multiple maps.

Table 2 Results obtained using one FM per direction
Full size table

Comparing data on Table 2 with data on Table 1 it can be concluded that considering a global FM with data collected in all directions, the results are worse than when the correct directional FM is used. These results validate that the solutions presented in this paper can improve the user’s location estimation.

Results of another test, made to demonstrate the user influence in the precision of the location system, are presented on Table 3. In this test four FM are used, one per direction, and the user is rotating. Analysing data it can be concluded that the user presence has a negative impact in the system precision, but not in the accuracy.

Table 3 Results using an FM per direction and user facing four directions
Full size table

As it was expected the results obtained using an FM based on the average values of all directions (Table 1) are better than those obtained with single direction FM (Table 3).

4.2 Multiple Maps Using Four Directions and FM Built Using Acquired Data

The first set of tests using the proposed methods are presented in Table 4. For all these tests the FM was generated the real data acquired in the testing scenario. In this table are shown the results of a test using Direct Maps (a single map is chosen). In these tests four FM were generated (one per direction), the user’s location was estimated with the user facing all the four directions (N, S, E and W), and the FM was automatically selected by the method.

Table 4 Results using directional FM (Direct Map) with four directions and FM built using acquired data
Full size table

Comparing the obtained data with Table 1, better results are achieved with directional maps, as it was expected. However, even though the user was not moving while acquiring data, the obtained results are worse than those where the FM was chosen manually (Table 2). This is because the azimuth value reported by the magnetic sensor is not stable.

Using weighted maps (Table 5), there is a slight improvement of the precision (comparing to Table 4) and an improvement of the accuracy in comparison to the FM generated with all data (Table 1).

Table 5 Results using weighted FM with four directions and FM built using acquired data
Full size table

4.3 Multiple Maps Using Eight Directions and FM Built Using Acquired Data

In this set of tests it is considered that the user might not be facing any of the directions used to build the FM. The Fingerprint Maps are the same as above (N, S, E and W) but for the user’s location four new directions are added (NE, SE, SW and NW). As for the previous tests the used FM were obtained using real data acquired in the testing scenario.

These are limit conditions, because four slices are considered (\( \alpha = \theta = 90^{ \circ } \)). The newly added direction fall directly at the boundary between the Fingerprinting Maps. So this can be considered as a worse case scenario where the first method will constantly switch between maps. So for both methods it is expected a worse performance in comparison to results presented in Tables 4 and 5, and a better performance than using a single FM with all data (Table 1). In fact, analyzing Table 6 it can be concluded that those assumptions are true, except for the precision values with Nearest Neighbour Algorithm.

Table 6 Results using directional FM (Direct Map) with eight directions and FM built using acquired data
Full size table

Results obtained using weighted maps are shown in Table 7. As it was expected these results are better than the above. There is an improvement of the location precision and accuracy. There is a slight increase of both the maximum error value though.

Table 7 Results using weighted FM with eight directions and FM built using acquired data
Full size table

4.4 Multiple Maps Using Four Directions and FM Built Using Propagation Models

To assess the feasibility of FM generated using propagation models, are presented in this section two sets of tests. The first set, which results are presented in Table 8, corresponds to tests made using Direct Maps, and the second corresponds to tests made using weighted maps (Table 9). In these tests the FM was generated using propagation models and data acquired in the testing scenario was used to estimate the location.

Table 8 Results using directional FM (Direct Map) with four directions and FM built using propagation models
Full size table
Table 9 Results using weighted FM with four directions and FM built using propagation models
Full size table

Both methods had a similar performance, and for simulated FM there is no apparent advantage in using weighted maps instead of directional maps.

Comparing data from these tests with data of the previous testes (with all real data), including the reference tests, results are worse. Nevertheless these are not disappointing results taking into consideration that there is the advantage of not having to manually collect data from the scenario. Also, in the worse case we have a difference of 19 cm (for NN) when comparing to data of Table 1, which for most indoor location applications is suitable.

4.5 Multiple Maps Using Eight Directions and FM Built Using Propagation Models

The last two sets of tests (Tables 10 and 11) were made considering eight directions, the same as in Sect 4.3. However in these two tests the FM was generated using propagation models.

Table 10 Results using directional FM (Direct Map) with eight directions and FM built using propagation models
Full size table
Table 11 Results using weighted FM with eight directions and FM built using propagation models
Full size table

In a first analysis to the data it can be concluded that the results are better than those obtained with only four directions and simulated FM.

Weighted maps (Table 11) had worse performance than the version using real data (Table 7), and direct maps (Table 10) had a better performance in comparison to the tests made using real data (Table 6).

Both tests had better results than those made with real data, presented as reference values (Table 1).

5 Conclusion and Future Work

If the user’s direction is known, as well as the direction at which data to build the FM was collected, it is possible to decrease the location error. Two methods based on the direction information, compatible to existing LEA that were developed without having the user direction information, were presented and their performance was assessed.

Comparing the results obtained using a single FM (average) and the multi map approach, it was obtained an improvement of 10.3 % for Nearest Neighbour, 8.7 % for k-Nearest Neighbour and 9.30 % for Weighted k-Nearest Neighbour.

Obviously that the user, in a real life application, will not be facing exactly the same direction at which the FM was collected. Even in these conditions, there is an improvement on the LEA performance (except for Nearest Neighbour in this particular testing scenario).

If instead a comparison is made with results obtained using an FM which includes only data collected in one direction, the precision improves by 22.08 % for Nearest Neighbour, 14.07 % for k-Nearest Neighbour and 18.44 % for Weighted k-Nearest Neighbour.

By using multiple maps it was possible to improve the performance of the LEA, however there is a drawback, related to the amount of data that must be collected. To build more maps, it must exist in the database more data. Because collecting data to build an FM is a time consuming task, tests were also made using propagation models, considering the user direction and the user influence in the signal propagation.

Comparing results obtained using real data and simulated FM, it can be concluded the use of Fingerprint Maps with direction information obtained using real data are obviously better. However the FM generated using propagation models (containing user direction information) have a better performance than real data FM without user direction information. The precision values are improved by 4.46 % for Nearest Neighbour, 8.66 % for k-Nearest Neighbour and 8.52 % for Weighted k-Nearest Neighbour. Taking into consideration the advantages of using Fingerprint Maps generated using propagation models, these can be considered good results.

Further improvements of the the maps generated by propagation models, or even to maps collected using other mobile devices, can be made using Direct Search Methods as presented in [6].