Wi-Fi Indoor Postioning System (2010)

The two basic methods of finding the position of the user given the signals strength of Wi-Fi are trilateration (Bahl and Padmanabhan, 2000; Wang et al., 2003) and location signature / fingerprinting (Bahl and Padmanabhan, 2000). The trilateration method can compute the user location on the fly from the signal strength data and known positions of the Wi-Fi signal transmitters also called Access Points (APs). The distance of the user from any Wi-Fi transmitter is inversely proportional to the signal strength obtained from that transmitter. One can find the user’s location if at least 3 Wi-Fi transmitters are visible. But this method of trilateration does not work well in the indoor environment. This is because of the signals undergo various interference and multipath problems due to the features like walls, equipments within the building and so the trilateration will not result in correct positioning of the user (Li et al. 2006).

The other method of positioning namely location signature / fingerprinting method solves this by involving two phases. In the first training phase, the location signature (i.e. the signal strength data from various access points (APs) at that point) of discrete points were recorded and stored in the database along with the location details of that point with in building. Since the actual signals at various points are collected, this signal information will include the interference and multipath patterns of the Wi-Fi signal data in the indoor environment which will even help to differentiate between two spatially close points but separated by walls. In the second positioning or testing phase, the obtained signals at user’s location are matched back to the training data. The location corresponding to the best match using a location estimation algorithm is the estimated position of the user.

This experiment studies about the Wi-Fi Location signature / fingerprinting method and does a preliminary comparison of the two location estimation algorithms namely the nearest neighborhood (Bahl and Padmanabhan, 2000) and Naïve Bayes (Pang et al., 2007) in terms of location estimation accuracy.

2. Experiment Setup:

The experiment was done in a real indoor environment without any special modifications. Totally 21 access points (APs) within and around the building were used in this experiment. 29 discrete points were selected in a section of the building which served as training points at which the Wi-Fi signal training data was collected. This section of the building constitutes test bed for the experiment.

2.1 Collection of Wi-Fi signal data (Training phase):

At the 29 points of the test area, the Wi-Fi signals strength was observed using the Wi-Fi sensors and recorded from each of the 21 access points. At each of the training points, the Wi-Fi signal strength is observed in 4 directions with 2 readings per direction separated by an interval of 5 seconds. This training data is stored in the database.

2.2 Location estimation methods (Testing phase):

The position of the user can be computed by location fingerprint matching algorithms when the Wi-Fi signal strength received from various access points is known. During testing the user stands at a well known position and record the Wi-Fi signal. Then using the location estimation algorithms the location of the user is estimated, from which the error between the actual and the estimated location can be computed. Two of such algorithms used are nearest neighborhood and Naïve Bayes method. The results of these algorithms in estimating the location of the user is discussed later.

2.2.1 Nearest neighborhood algorithm:

This algorithms searches the given test signals pattern with all the other signals in the database and match with the point which corresponds to the nearest neighbor in the signal hyperspace. This can be computed by calculating the least square of the test signals pattern and the other points signal pattern recorded during the training phase and selecting the point with the least distance.

2.2.2 Naïve Bayes method:

In Naïve Bayes method, the given set of signals at the user’s location is processed and the probability of the each and every point in the database being the user location is calculated using the probability density function. Then the point with the highest probability of being the user location is picked and declared as the user’s location.

2.3 Results and Discussion

The Figure 1 shows the test area for this project and the software tool used in this experiment. The base image shows the layout of the building floor. The blue dots represent the points at which the training data is collected. Figure 2 shows the errors (in meters) for all the test points. The X-axis represents the various test points and the Y-axis shows the corresponding error in location estimation in meters using the two algorithms namely the nearest neighborhood and Naïve Bayes. From the graph one could see that the Naïve Bayes algorithm is performing better in terms of location estimation and the average error in location estimation is around 2 meters, where as the average error in nearest neighborhood is around 4.5 meters.

2.4 Future Work:

The variation in the Wi-Fi signals with respect to the time, day and seasonal variation are major factors affecting the location estimation procedures. Also the Wi-Fi signals vary due to interference from other electromagnetic waves in the same wavelength which operate in the buildings like microwave ovens. These constitute the noise of the system. This noise negation models can be incorporated into the location estimation procedures.

Figure 2: Graph showing the location estimation errors of Nearest neighborhood and Naïve Bayes algorithms for various test points

References:

1. Bahl, P, Padmanabhan, VN (2000) RADAR: An in-building RF-based user location and tracking system, IEEE Infocom 2000, Tel Aviv, Israel, 26-30 March, vol. 2, pp. 775-784.

2. Hightower, J., & Borriello, G., “Location systems for ubiquitous computing”, IEEE Computer, August 2001, 34, (8), pp. 57-66

3. Wang, Y., Jia, X., Lee, H.K., and Li, G.Y., “An indoor wireless positioning system based on WLAN infrastructure”, 6th Int. Symp. on Satellite Navigation Technology Including Mobile Positioning & Location Services, Melbourne, Australia, 22-25 July 2003, CD-ROM proc., paper 54.

4. Li, B, Salter, J, Dempster AG, Rizos, C (2006) Indoor Positioning Techniques Based on Wireless LAN, First IEEE International Conference on Wireless Broadband and Ultra Wideband Communications, Sydney, Australia, 13-16 March, paper 113.

5. P. Prasithsangaree, P. Krishnamurthy, and P. K. Chrysanthis, “On Indoor Position Location with Wireless LANs,” in Proc. IEEE International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC’02), Lisbon, Portugal, Sept. 2002.

6. Pang, J., Greenstein, B., Gummadi, R., Seshan, S., and Wetherall, D. 802.11 user fingerprinting. In MobiCom (Sept. 2007).

7. Li, B., Wang, Y., Lee, H.K., Dempster, A.G. & Rizos, C. “Method for Yielding a Database of Location Fingerprints in WLAN”, Communications, IEE Proceedings, Vol. 152, Issue 5, October 2005, pp. 580-586.

8. B Fu, G Bernath, B Steichen, S Weber “Wireless Background Noise in the Wi-Fi Spectrum” Mobile Computing, 2008. WiCOM'08