Survey on the WIFI Positioning Technology

A quick survey on the WIFI positioning technology

Abstract

Wireless location estimation technology is applied largely into many fields such as in the military communication, Internet of things and social networks. Meanwhile, with the growing need of WIFI technology, access points of WIFI networks have been deployed in large-scale department stores, cafes, schools and general hospitals. WIFI location positioning can not only offset the drawbacks of GPS especially in built-up area or indoors environment but also enlarge the location estimation services in the relevant industrials. Specifically, more accurate result is the main contribution of the WIFI positioning. Based on WIFI location estimation technology, this survey will present different kinds of approaches applied in WIFI positioning, give a comparison among them and discuss certain algorithms in fingerprint technology.

Key words: WIFI technology, WIFI localization, location positioning algorithms

1 Introduction

With the high development of Wireless Communication and the urgent need of Personal Communication Service, different kinds of wireless networks has emerged such as GSM, WCDMA, TDSCDMA based on Cellular Technology, Wi-Fi based on AP coverage, etc. Diverse wireless network has different features and can also bring about a wide variety of data services which can satisfy the user for their own communication need. Largely, it can offer us high quality of communication experience and alter our way of life.

In the same time, the rapid growth of the wireless communication make the social networks popular among the young generations. Location estimation technology will also make a great contribution to it. In advertising services, as long as the detailed location coordinate of the mobile users is once determined, it will bring about enormous economic benefits to the surrounding business. Business owners could send advertisements to consumers nearby to make more profit. The positioning technology could make public security services more completed. For example, it can aid us to find lost articles, stolen bicycles and missing children or pets. Furthermore, for large manufactures, Location estimation technology could offer the detailed position information of each product components. As for tourists, it can provide travelling information, too. Even in museums, campus and large amusement parks, users could also take the advantage of this location services.

With the WIFI technology being applied into many fields, access points of WIFI networks are covered in large commercial buildings, cafes, schools, grand hospitals, bus stops and metro. WIFI positioning technology could make up the limits in indoors environment of GPS. It can not only improve the accuracy of location estimation but also cut down the cost of coverage, which is significant to the society,

2. Different approaches applied in WIFI positioning

In terms of positioning technology, the most popular one is GPS. However, the environment should be flat and open. As for indoors regions, GPS technology has a relative poor accuracy in location estimation due to the fact that influenced by the building walls and other subjects, the intensity of signal is attenuated largely. Therefore, WIFI position technology could be an optimized choice for indoors environment.

2.1 The definition of the WIFI positioning

Localization is the process of estimating absolute or relative position of mobile objects, referring to the data of predefined spots’ position in restricted area. ^[1] In indoors environment, WLAN is the ideal option to localize the terminals. The access point just like the bases in wireless communication play a significant role in WIFI positioning. Therefore, WIFI could provide the larger coverage as well as make the localization more convenient.

2.2 The classification of the approaches in WIFI Localization

Currently, the majority of WLAN is using the Radio Frequency to communicate with each other due to the fact that most Radio Waves could penetrate walls or obstacles in indoors environment. To be more specific, RSSI is the common localization technology to be applied in wireless environment. ^[2]The following gives a simple description of RSSI.

RSSI (received signal strength indication): Research and experimental measurements show that wireless signal in propagation presents some rules as followed: Once the transmission power of AP is fixed, there is an inverse relationship between the receiver’s received signal strength and distance between sender and receiver.^[3] Specifically, if the distance between them is closer, the stronger received signal strength we will get. By using the known radio propagation model, RSSI method could measure different RSSI of APs from mobile terminals. In most cases, we could get the positioning result through three different APs.

Therefore, positioning approaches based on RSSI could be classified into two fields: one is trilateration positioning and the other is fingerprinting positioning.

2.2.1 Trilateration positioning technology

Trilateration positioning technology means setting the 3 APs to be the center and the distance between AP and to be localized subject to be radius. Therefore, we get the 3 different circles and the focus among them. By using the above data, we could attain the equations to work out the distance of the solution.

In WIFI networks, the distance between AP and user could be attained by two approaches.

1. TOA (time of arrival): TOA is measuring the one-way propagation time between the AP and mobile terminals or the round-trip propagation time. ^[4]The former needs to record the precise signal transmission time of the AP or mobile terminals.Fig.3-1 shows the basic idea of TOA positioning approach. Moreover, the receiver is highly depend on the clock, too; the latter don’t worry about the synchronization. However, there are still high demands on the clock.

Fig.2-1 The schematic diagram of TOA approach

Yet, TOA is highly depend on accurate time clock. During the localization, 1ms of the measuring error could result in the 300m positioning mistake. Therefore, for the AP and mobile terminal there are high demand on precise clock, which increased the localization hard ware costs.

2. TDOA (time difference of arrival): Different from TOA, TDOA is to detect the arrival time difference between the two APs other than the absolute arrival time for the target terminal localization^[5]. Fig.3-2 describe the basic schematic diagram of TDOA approach. Obviously, via this approach, we can minimize the high demand of the synchronization between the sender and receiver. By using the three different AP, it is easy to measure two TDOA values. The mobile terminal is located on two hyperbolic intersection determined by the two TDOA.

Fig.2-2 The schematic diagram of TDOA approach

2.2.2 Fingerprinting positioning technology

Similar to the traditional fingerprint technology, fingerprint technology relies on characterizing the feature of the database to identify the target.Fig.3-3 gives a detailed description of the working principle in finger printing technology. ^[6]There are two stages in the localization: training stage and positioning stage.

• Training Stage: The target in this stage is to build a fingerprint database. First, we should adopt a reasonable reference point distribution for ensuring to provide enough information in the positioning stage. Then, It is important to measure the value of RSS in different reference points. ^[11]The location information of reference points and the corresponding MAC address are recorded in the database. Due to the environment factor, wireless signal strength is not stable. In order to overcome this disadvantage, generally, we take the average of multiple measurements at each reference point. Table2-1 below indicates the establishment of the fingerprint database.

Table2-1 An example of the fingerprint database

• Positioning Stage: Once the database is settle down, according to the certain matching algorithms, the RSS value of the target point is compared with known information in the database. The common matching algorithm is Nearest Neighbor algorithm (NN) , k-Nearest Neighbor algorithm and so on. These approaches will be discussed thoroughly in the next part. At last, we could attain estimated user location.

Fig.2-3 The schematic location positioning technology in fingerprint

The above is some basic approaches in WLAN based indoor location estimation technology. The table 2-2 blow presents a brief comparison among them.

Table 2-2 the comparison among the different approaches in WLAN based indoor environment

3. Location Algorithms in fingerprint technology

In this section, we will introduce two classical positioning algorithms based on fingerprint technology: Nearest Neighbor (NN) algorithm and Naïve Bayesian algorithm.

3.1 The Nearest Neighbor algorithm (NN)

NN could be regarded as a special case of KNN algorithm namely k=1. KNN approach is first introduced in early 1950s. Within the large amount of training set, it is computationally intensive. From then on, it is applied rapidly in the field of pattern recognition.^[8]

NN is based on analogical learning. To be more specific, we could attain the result by comparing the given test examples and resembled training samples. In the field of wireless location estimation, the test samples are fingerprint and the class label is the physical location corresponding to the fingerprint. ^[9]Supposed that if the number of fingerprint is l (denoted as ) in the localization area, there is a mapping relationship between each fingerprint and the corresponding physical location information}.In the real-time positioning stage, one RSS fingerprint example is denoted as S. It contains average RSS value from N different APs, namely .In the fingerprint database, each fingerprint is expressed as. is the fingerprint of No.i, which contains the average value of RSS in No.n AP. Therefore, the similarity between the fingerprint S of the real-time signal and the training samples in the database could be measured by the distance between them, for instance, the Euclidean distance. Just like the formula 3-1 below:

Finally, for the fingerprint S of the real-time signal, the estimated result is the physical location corresponding to the fingerprint which is the nearest one from it. Shown as formula (3-2).

3.2The Naive Bayesian Algorithm

The naïve Bayesian algorithm is based on the probability method deriving from classification in statistics.^[10] Bayesian classification could predict the likelihood of the class members, for instance the given sample belongs to a particular class. The main idea of Bayesian classification is that in many applications, the relationship between the samples and class labels is not determined. In other words, though the test samples are very similar to some training samples, we couldn’t predict the class label clearly. The noise leads to this situation or other confounders which affected the classification didn’t be contained in analysis. Different from KNN, Bayesian classification gives the probability of test samples belonging to the certain class other than the exact class label of test samples.

Based on Bayes Theorem, Bayesian classification is a statistic principle which combines the prior knowledge and new evidence gathered from the new data set. Naive Bayes is the impletion of the Bayesian classification. The localization based on naive Bayesian is as followed: First, supposed that there are l fingerprints in the localization area, denoted as , there is a mapping relationship between the each fingerprint and the corresponding group of location information. In the real-time positing stage, a RSS fingerprint sample is denoted as S and it contains average RSSI value from n different APs,Then, naïve Bayesian algorithm is to attain the posteriori probability of real-time RSS fingerprint samples S in the positioning area, it could be described as below:

In the formula (3-1),with the known location,is the conditional probability of real-time RSS fingerprint sample S.is the prior probability of Li in the localization area. Generally, users could appear on any position of the location area. So we consider is subject to the uniform distribution. The key assumption of Naive Bayesian is that the impact of each attribute value for a given class is independent of the other property values. In other words, in certain location, the RSSI value from different APs is independent and unrelated. Therefore, the calculation of is simplified as We could use Gaussian probability distribution to approximate the RSSI in certain location, the formula is as below.

Eventually, by using the MAP, we estimate the use’s location, described as formula(3-3).

4. Conclusion and Future prospects

Based on WIFI positioning technology, this survey analyze the needs of wireless localization, classify and compare the different approaches implemented in indoor environment and present two classical algorithms in fingerprint technology.

With the high development of WLAN, the technology based on RSSI, especially fingerprint attracts more and more attention. On the basis of the more accurate estimated result, the future research goal is to improve the ease of use in the positioning system and make the location-based services more convenient and more practical. Here are some tips towards the future research fields:

• The fingerprint technology algorithm its self has the drawbacks of enormous complicated preparation works. By using the propagation model, we could reduce the large amount of working preparations.
• Most people study or work in indoors environment. So, how to use other people’s information to improve the user’s own localization accuracy is an interesting issue and many researcher has put emphasis on it.
• Recently, most algorithms are just in theoretical research or basic test scene lacking of practical application consideration. Therefore, how to implement these algorithms into public paces is another urgent issue, too.

References

1. N0HA S, LEE W J, YOUNG J. Comparison of the mechanisms of the Zigbee’s indoor localization algorithm[C], Ninth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel Distributed Computing. Phuket, [S.l.]: [s.n.], 2008: 13-18.
2. ZHUMinghui,ZHANG Huiqing. Research on model of indoor distance measurement based on receiving signal strength[C].2010 International Conference on Computer Design and Appliations. Qinhuangdao, [s.l.]:[s.n.], 2010: 54-58.
3. K.C.Ho,Y.T.Chan.Geolocation of a known altitude object from TDOA and FDOA measurements[J]. IEEE Transactions on Aerospace and Electronic Systems, 2007’ 33(3): 770-783.
4. Binghao Li, Yufei Wang, Hyung Keun Lee,ect.”A New Method of Yielding a Database of Location Fingerprints in WLAN,”IEEE Proceedings Communications. 2005. pp.580-586.
5. Bahl P, Padmanabhan VN. Enhancements of the RADAR User Location and Tracking System. Technical Report MSR-TR-2000-12, 2000.
6. Yongliang Sun;,Yubin Xu, Lin Ma, Zhian Deng, “KNN-FCM hybrid algorithm for indoor location in WLAN ,” Power Electronics and Intelligent Transportation System (PEITS), 2009.pp.251-254dd.
7. Roos T, Myllymaki P, Tirri H, et al. A Probabilistic Approach to WLAN User Location Estimation. International Journal of Wireless Information Networks, 2002, 9, 155-16.