Short Answer[]
Localization based services, especially navigation systems, have ruled our lives for the past ten years. With the advancement of science, our dependence on such services have increased exponentially. Today, one can easily find one’s way to the nearest Starbucks or navigate one’s way in a strange city. From the initial events about 30 years ago when a Soviet Sukhoi interceptor flying over the Sea of Japan fired off two heat-seeking missiles, the technology evolved fast [1].The exponential advancement has us captured to the point where we no longer look for maps, or compasses (basic essentials for travelling 10 years ago) but just our cell phones.
GPS is a household name these days, people might not know that it means “Global Positioning System” but they know GPS will take them wherever they need to go. This ubiquitous piece of technology was not initially intended to be used by civilians, it was profoundly developed for military purposes. It was supposed to be exclusively for military, until President Ronald Reagan ordered a sudden change in policy in response to the deaths of 269 people aboard an airliner which was shot down by Soviets on 1 September 1983, believing it to be a military aircraft on a spying mission. Hence began a spiral of events which delivered to us the GPS, we rely on so much to day. It is to be pointed out that there are other Global Navigation Satellite Systems like Russia’s GLONASS, India’s GAGAN (which recently sent its 7th and final satellite to complete its full constellation). China is in the process of expanding its regional BeiDou Navigation Satellite System into the global Compass navigation system by 2020 [1]. The European Union's Galileo is a global GNSS in initial deployment phase, scheduled to be fully operational by 2020 at the earliest.[2] India currently has satellite-based augmentation system, GPS Aided GEO Augmented Navigation (GAGAN), which enhances the accuracy of NAVSTAR GPS and GLONASS positions, and is developing the Indian Reginal Navigation Satellite System (IRNSS) to be known as NAVigation with Indian Constellation (NAVIC). GPS is used here as a compilation of various different GNSS systems, which work on similar principles.
Positioning Systems like GPS, work extremely well in outdoor environments. The US Government claims to provide a “worst case” pseudo-range (pseudo-range is distance from satellite to receiver) accuracy of 7.8 meters at a 95% confidence level. The actual accuracy that users get is restricted by several other factors and is hence lower than this value [2]. This accuracy will further decrease as we go into confined areas, like urban canyons, close to walls, buildings, trees and underground environments because signal from the satellites will be too weak to come across most buildings. In the end, the accuracy is so poor in Indoor localization that using GPS indoors becomes unreasonable. Here arises the need to develop a completely different system which can augment localization indoors.
Indoor localization comes with its own set of restraints, like smaller dimensions, higher none line of sight (NLOS), high influence of obstacles like walls, trees, buildings, movement of human beings, and many other such factors [3]. Multipath effects are also problematic in this scenario as signals are reflected and attenuated because of obstacles and this not only causes dispersion of information but also noise interference, which makes localization pretty tough. The electromagnetic waves travelling are scattered, reflected and absorbed by obstacles present in its path, hence hindering proper detection of signal. An effective Indoor position system will minimize the effects of these restrictions and accurately position an indoor topography or object or person, depending upon the need [4].
For an indoor system to be in used for real time applications it should fulfill some performance criteria like accuracy, responsiveness, coverage, adaptiveness, scalability, cost and complexity. A large number of Indoor Positioning techniques have been developed like, infrared based systems, radio frequency identification, Bluetooth, FM, ultrasound based systems, etc. A system that gives accurate results in the least time span and is scalable is the best system. Most of the above mentioned techniques provide accurate results but they require a large additional infrastructure for their deployment. Therefore, these systems cannot be used widely as a significant cost is involved in their installation. Moreover, energy consumption and specific environment range limitations are also a great hindrance [5]. IPS is not just hyper refined version of GPS, but works on completely different concept. Though in a way it does take GPS forward. IPS begins where GPS ends. Due to three major effects namely, influence of obstacles, high non-line of sight, and multipath effect, GPS doesn’t work indoors.
IPS doesn’t use satellite communication like GPS, rather IPS uses nearby anchors (nodes with a known position), which either actively locate tags or provide environmental context for devices to sense. WiFi based positioning systems are widely deployed due to the fact that most of the devices are WiFi enabled. WLAN positioning systems measures the received signal strength from all the access points in the range of receiver. This received signal strength is measure by network interface cards (NICs) that are available in most devices. Thus, these devices are easy to locate without any additional hardware installation. In addition to it, even WLAN infrastructures doesn’t require any additional hardware to implement position algorithms. Therefore, cost is significantly reduced. Moreover, the number of devices being connected to WiFi at a particular location is not limited, which enables a large number of users to use positioning system.
Long Answer[]
To determine user location using WLAN, three kinds of approaches are given below:
1. Strongest Base Station Model
2. Propagation Model
3. WLAN RSS
Strongest Base Station Model[]
In this method, user location is estimated based on the location of base station providing strongest signal strength from the set of known base stations.
Fig.1: Strongest Base Station Model [6]
As shown in the fig.1, the location of client can be determined by calculating the signal strength from each access point. The client’s location is near the access point transmitting maximum signal strength. This method is quite simple but the accuracy is low as it doesn’t determine the exact location of the user rather it gives you an idea that the user is close to the access point from which it is getting maximum signal strength. The complexity of indoor environments affects it accuracy to a great extent.
Propagation Model []
In this technique, signal path loss is used to determine the user location, which is determined by received signal strength information. Received signal strength (RSS) is estimated when the transmitter and receiver have unbarred line-of-sight path (LOS). The transmitted and the received powers are known and the received power strength is decreased with the square of the distance.
Received power strength, Pt = 1/D2, where D is the distance between the transmitter and the receiver.
To find the co-ordinates of the mobile user propagation model uses two different techniques:
1. Triangulation
2. Trilateration
Triangulation[]
To determine the user location, geometric properties of triangles are used.In this method, we require one known side of the triangle on two known angles.
To determine the user’s location in 2D plane at least 2 reference points are required. The location of these reference points and the distance between the is known. By using directional antennas or antenna arrays the angle of the received signal from known reference points to the user’s location can be found. These angles are then used to determine the user’s location [7]. As illustrated in the above fig.2, the angle of arrival (AOA) of two reference points (angle 1 and angle 2) are calculated using antenna array.
AOA is the angle between the transmission route of an incident wave and some reference direction, which is known as orientation. Orientation, a fixed direction against which the AOAs are measured, is represented in degrees in a clockwise direction from the North. As shown if fig.3, the antennas are equidistant separated by distance “s”. The incident signal is arriving on antenna array through propagation paths. AOA is computed using the phase-shift difference of the incident signal.
When the orientation of the user is known as shown in fig.4, angle θ1 from b1 and angle θ2 from b2, the relative AOAs can be measured at unknown position U. Then orientation of U is assumed to be ∆θ, therefore, the absolute AOAs can be measured as (θi +∆θ)(mod 2 π ),i = {1,2}. The estimated position of user U is the juncture of all rays when twoor more non-collinear reference points are present [9].
When the orientation of the user is unknown, at least 3 reference points are required to estimate the user’s location. The absolute AOAs can be calculated using the relative AOAs ∠b1ub2, ∠b1ub3 and ∠b2ub3. Since, a chord subtends equal angles, if three points and the chord joining them is known, the intersection of the arcs will determine the user’s location. As shown in the given fig.5, the angle ∠b1ub3 and the chord b1b3 confine user’s position on the arc passing through b1, u and b3. The location of user u can be determined by the intersection of all the arcs [9].
Trilateration[]
It is also known as range technique, since the user’s location is estimated from distance measurements. In this method received signal strength from sender node to receiver node is measured from at least three reference points. The propagation time, that is directly proportional to the propagation distance of signal, from reference points to user is measured. Time synchronization of all the reference points is mandatory. This technique estimates user’s location using time of arrival (TOA). The arrival time of signal at the receiver is measured based on the accurate synchronization of the reference points from where signal is transmitted. The distance between the user and the known reference points is calculated by the arrival time and the corresponding speed of signal.
Fig.6: Trilateration [7]
In fig.6, three reference points b1, b2 and b3 (co-ordinates are X1Y1, X2Y2 and X3Y3 respectively) are known. The distance of user from the three reference point is computed from propagation time delay of signal. The user’s co-ordinates (X Y) can be calculated by computing the intersection point of the three circles. Consider the equation of circle as r2=x2+y2. For a circle centered at XaYa is r2= (x- Xa)2+(y-Ya)2. Similarly, the equations can be found for each circle.
Circle 1: r12 = (x-- X1)2+(y-Y1)2
Circle 3: r32= (x- X3)2+(y-Y3)2
Circle 2: r22= (x- X2)2+(y-Y2)2
The intersection point of the three circles can be calculated by solving the three equations and finding the point that satisfies all the three equations.
The propagation model is quite simple and easy to deploy. But it is not very efficient when high accuracy and precision is required due to the noise in the wireless signal and the influence of obstacles in indoor environment [5].
WLAN RSS Fingerprinting[]
RSS based positioning systems are being widely deployed as they are simple and easy to install and there is no additional infrastructure required that allows it to fit in low budget. RSS fingerprinting is tolerant to wireless signal noise, therefore, it is most exploited technique now-a-days.
In WLAN RSS fingerprinting the received signal strength is measured at all reference points. The RSS data is used to determine the distance between the transmitter and the receiver. This distance is calculated depending upon the conduct of signal transmission and evidence of the building [10]. Fingerprinting has two phases: offline phase and online phase.
WLAN RSS offline Phase []
In this phase the RSS is calculated at all reference points and the data is stored in a training database. Consider n access points (transmitters), and r reference points. At each reference point the RSS is calculated from each of the n access points and the data is then stored in the training database.
Fig.7: RSS Fingerprinting flowchart representation [5]
In fig.7, the RP are the reference points whose x and y co-ordinates are known and RSS values corresponding to each access point is calculated and then stored in the database. There is one major problem encountered in this phase. The number of fingerprints are sometimes insufficient to accurately estimate the position of the mobile user. To overcome this problem, the concept of extrapolation and interpolation is used [12].
WLAN RSS online phase:[]
After acquiring the training database, actual detection of the mobile user can be carried out. The online determination phase can be easily explained using fig.7. The RSS vector associated with the mobile user at any unknown location is measured by using the reference points present in the building. This RSS vector is then compared to the wireless RSS vector records in the training database. Then by using various positioning algorithms, we can predict the most likely location of the mobile user. There are various positioning algorithms which can be used for WLAN RSS fingerprinting approaches. These include, nearest neighbor method and probabilistic estimation.
After picking up the RSS vector in the training database which matches the observed RSS profile the most, the Euclidean distance determination method is used to find user location [5]. It is one of the simplest methods employed for RSS fingerprinting, where the distance between the online RSS value and the offline RSS training database is calculated. When estimating user location, the Euclidean signal distance from the test location is calculated for each reference point. After that, the reference point which has the minimum Euclidean signal distance is selected as the estimated location.
Di is the distance Euclidean Distance between the mobile user and the RSS vectors present in the database.
n is the number of APs,i is the number of reference points.
Rssin the signal strength received from nth AP at ith reference point, stored in the training database.
Rssn value of signal strength received from nth access point at test location.
To improve the accuracy, calculating the nearest neighbor or K nearest neighbor (KNN) is one of the most basic technique employed. In this scheme, values of RSS differences larger than a certain threshold value are filtered out, the distance measure is no longer increased [14]. The distance measure using this scheme can be written as follows.
The location is detected by averaging the RSS vector of the K nearest neighbor with the minimum Euclidean distance. Hence, this algorithm using a well-defined Euclidean Distance metric declares an actual point in physical space as the current location of the mobile user. However, it should be kept in mind that though this is a relatively simple method which does provide a somewhat accurate answer, it does have some problems associated with it. This algorithm can provide multiple outcomes, and if such is the case then some complicated resolving methodologies need to be used. Also, the accuracy is dependent on the reference database granularity. For more accuracy we need finer grid, which will mean a much larger database, which is quite difficult obtain in some situations [11]. Moreover, the Euclidean distance does not provide adequate performance in cases where distribution of the RSS vectors included in fingerprints are non-convex and multi-modal [13], which is the case in indoor environment because of high Non Line of Sight and presence of people. The value of K, that is, the number of neighbors, influences the resulting accuracy, if value of K is 1, the algorithm will deduce the nearest neighbor. A slight improvement to KNN is distance-weighted K Nearest Neighbor (WKNN), where the basic idea is to assign weights to different neighbors. The closer the neighbor higher is the weight assigned to it.
One more techniques can be used in which a power coefficient (α) that is less than 1 is used, instead of 2 as in Euclidean distance. This will reduce the impact of large RSS differences, and increase the importance of exact match [14]. The formula is given below:
Probabilistic Estimation: KNN provides good performance and accuracy under most conditions [11], but it lacks accuracy when the number of reference points are limited. Also in complex indoor environment, the variation if the measured RSS value at each reference point can be quite large, hence hindering the detection process. There are various probabilistic methods which produce Maximum Likelihood (ML), Maximum A Posteriori (MAP), or Minimum Mean Square Error (MMSE) estimates of position using estimates of likelihood and posterior density functions [13]. Bayes rule determination method is also used for finding the highest probability where the mobile user can be present [5]. The most probable location li can be found out using Bayes Rule, which tries to maximize the conditional probability, p(li / RSS). It can be calculated as follows:
P[Rss/li] is the conditional probability of obtaining the RSS at ith position li given that the mobile user is present at the position li .
p(RSS) does not depend on location li and is often regarded as the normalizing constant.
p(li) is the prior probability calculated if the mobile user is located at position li. The prior probability density function p(li) will represent the surrounding environment as seen by the reference points. If we assume that these reference points are uniformly spread throughout the environment, we could say, [15]
Here (.) is the dirac-delta function. If we use this approach, and by assuming that reference points are uniformly distributed, substituting the estimation of in our main equation, we get, [15]
If we define as weight wi (RSS), then it is easier to deduce the minimum mean square error. The MSME could be easily calculated by estimating the likelihood density There are several methods to estimate the probabilistic weightings. These also include the basic histogram-based one and kernel-based one. Also there are various methods which can be used for online matching of test RSS vector values with the collected fingerprints, besides KNN and probabilistic methods, there are also Kernel, and Support Vector Regression (SVR) methods. But for the sake of simplicity only first two methods are discussed here.
Conclusion[]
In conclusion where the use of GPS ends, use of IPS begins. IPS will eventually supplement the use of Global Navigation System but the technology used in both is completely different. To increase the accuracy of finding one’s location, Wi-Fi fingerprinting with RSS based localisation techniques is an area that has been receiving attention from most researchers. Locating a person or device indoors is only half of the solution. For the location to be meaningful for navigation or other purposes, service providers need accurate indoor maps. Despite the name, most current IPS systems are so coarse that they cannot be used to detect the orientation or direction of an object. Apple, Google and Microsoft are all exploring the use of indoor positioning. At this time the effort is focusing on both indoor positioning technologies and creating the base maps that will make such solutions more valuable. Google has its own Android positioning system based on Wi-Fi. Microsoft uses Wi-Fi for indoor positioning, as well, and has some research going on regarding the use of signal strength for location determination. Apple recently acquired WiFi SLAM to get into the indoor location game.
Aditional References[]
[1]David Schneider, New Indoor Navigation Technologies Work Where GPS Can’t. IEEE Spectrum, 20 Nov 2013.
[2]GPS Accuracy, GPS.gov
[3]J.Yiming, Indoor Location Determination, in Location-Based Services Handbook, CRC Press, 2010.
[4]Recent Advances in Wireless Indoor Localization Techniques and System, Journal of Computer Networks and Communications Volume 2013 (2013), Article ID 185138, 12 pages Zahid Farid, Rosdiadee Nordin, and Mahamod Ismail
[5] Landu Jiang, “A WLAN Fingerprinting Based Indoor Localization Technique”.
[6]James Aweya, Luis Orozco BARBOSA, “Method and system for wireless LAN-based indoor position location”,United States Patent, US 8,165,150 B2, Apr. 24, 2012.
[7]Adalja Disha M,”A Comparative Analysis on indoor positioning Techniques and Systems”, International Journal of Engineering Research and Applications, Vol. 3, Issue 2, March -April
[[ https://en.wikipedia.org/wiki/Wi-Fi_positioning_system.%7C[8] https://en.wikipedia.org/wiki/Wi-Fi_positioning_system.]]
[9]R. P and M. L. Sichitiu, "Angle of Arrival Localization for Wireless Sensor Networks," 2006 3rd Annual IEEE
Communications Society on Sensor and Ad Hoc Communications and Networks,
Reston, VA, 2006, pp. 374-382.
[10]Tareq Alhmiedat, Ghassan Samara, Amer O. Abu Salem,” An Indoor Fingerprinting Localization Approach for ZigBee Wireless Sensor Networks”, European Journal of Scientific Research ISSN 1450-216X / 1450-202X Vol. 105 No 2 July, 2013.
[11] A Comparative Performance Evaluation of RSS-Based Positioning Algorithms Used in WLAN Networks Ahmad Hatami and Kaveh Pahlavan Center for Wireless Information Network Studies Worcester Polytechnic Institute (WPI).
[12] Distance-Based Interpolation and Extrapolation Methods for RSS-Based Localization With Indoor Wireless Signals Jukka Talvitie, Markku
Renfors, Fellow, IEEE, and Elena Simona Lohan, Member, IEEE
[13] Kernel-Based Positioning in Wireless Local Area Networks Azadeh Kushki, Student Member, IEEE, Konstantinos N. Plataniotis, Senior Member, IEEE,
and Anastasios N. Venetsanopoulos, Fellow, IEEE
[14] Lee, Joo-Yub, et al. "Analysis of location estimation algorithms for wifi fingerprint-based indoor localization." Proceedings of the 2nd International Conference on Software Technology. Vol. 19. 2013.
[15] Hao Huang, “Post Hoc Indoor Localization Based on RSS Fingerprint in WLAN”, 2014.