Wireless Positioning System

Seminar II
On
Wi-Fi based Indoor positioning

Submitted By
Vaibhav Gaikwad
Exam seat no.

Seminar Guide
Mrs. Trupti Wagh
Department of Electronics and Telecommunication

PG Communication Network
D. Y. Patil College of Engineering
Akurdi, Pune - 411044
2014-2015
D. Y. PATIL COLLEGE OF ENGINEERING

AKURDI, PUNE - 411044
DEPARTMENT OF ELECTRONICS & TELECOMMUNICATION

ENGINEERING
CERTIFICATE
This is to certify that Vaibhav Gaikwad - Roll No.11
of M.E. Communication Network has successfully completed the
Seminar II titled
towards the partial fulfillment for the requirements of the Masters
Degree of Engineering course under the University of Pune during the
academic year 2014-2015.
Mrs. Trupti Wagh
Mrs.Padma Lohiya
Prof.(Dr.)Mrs.P.Malathi
Seminar Guide
PG Coordinator
HOD (E. & T.C.)
Acknowledgement
I express my sincere gratitude towards the faculty members who makes this
seminar a successful.
I would like to express my thanks to my guide Mrs. Trupti Wagh and Head
of Department Prof.(Dr).Mrs.P. Malathi for her whole hearted co-operation and
valuable suggestions, technical guidance throughout the seminar work. And special
thanks for her kind official support given and encouragement.
I am also thankful to my PG coordinator Mrs. Padma Lohiya for her
valuable guidance.
Finally, I would like to thank to all our staff members of Electronic and
Telecommunication Department who helped me directly or indirectly to complete this
work successfully.
ii
Contents
Certificate
Acknowledgement
ii
1 Introduction
2 Literature Survey
3 Theory
3.1
3.2
3.3
3.4
Fuzzy nature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1
Fuzzy Membership Function . . . . . . . . . . . . . . . . . . . .
3.1.2
Fuzzy Signal Distribution . . . . . . . . . . . . . . . . . . . . .
POSITIONING METHODOLOGIES . . . . . . . . . . . . . . . . . . .
10
3.2.1
Testing the Stability of the Signal . . . . . . . . . . . . . . . . .
12
3.2.2
Estimation Testing Within the Trust-Region . . . . . . . . . . .
12
3.2.3
K-Mean Location Fingerprinting Algorithm . . . . . . . . . . .
13
System Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.3.1
Analyzing accelerometer and compass data . . . . . . . . . . . .
15
3.3.2
Particle filter . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.3.3
Map constraints . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.3.4
Room-level localization . . . . . . . . . . . . . . . . . . . . . . .
17
3.3.5
Updating the database through crowd-sourcing . . . . . . . . .
18
Implemented project by Google . . . . . . . . . . . . . . . . . . . . . .
19
4 Application
21
5 Conclusion
23
6 References
24
iii
List of Figures
1
LF WPS Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . .
Fuzzy Membership function . . . . . . . . . . . . . . . . . . . . . . . .
Flowchart of positioning approach . . . . . . . . . . . . . . . . . . . . .
11
System design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
Collision is detected . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
iv
List of Abbreviations
WPS
Wi-Fi Positioning System
GPS
Global Positioning System
LF
Location Fingerprinting (LF)
RSS
received signal strength
AOA
angle-of arrival
TOA
time-of arrival
MS
Mobile station
TR
Newton Trust Region
AP
Access points
SINR
Signal-to-Interference-plus-Noise-Ratio
PDF
probability density function
MAC
Medium access controller
AP
Access Point
Introduction
In an era where smartphones are becoming an essential part of our life, location
based services like GPS and GLONASS are being extensively used. These services
detect the user equipment (Mobile/GPS device) with the help three or more satellites
As most of the current UE (Mobile,GPS devices) depend on GPS but the quality of
GPS indoor positioning is still poor because GPS and GLONASS cant work without
a direct visibility of sky. The two major problems of current indoor positioning technologies are accuracy and cost. The new method which is becoming popular in indoor
positioning that is Wi-Fi Positioning System (WPS), it is used where GPS is inadequate due to various causes including multipath and signal blockage indoors. Wi-Fi
positioning takes advantage of the rapid growth in the early 21st century of wireless access points in urban areas. It is now widely acknowledged, although Google, Apple, and
various phone makers and carriers have compiled their own very extensive databases
of Wi-Fi access point locations by correlating Wi-Fi access points with GPS locations
of cell phone, smartphone, and in some cases, tablet computer users. Anonymously
determining users location. WPS may be combined with cell phone tower triangulation and GPS to provide reliable and accurate position data under a wide range of
conditions. The data needed to be collected for location based service and is collected
by cell towers and WiFi access points in variety of ways, including UE information.
These data are aggregated and store in public domain. This requires installation of
access points which supply their location information, which is also costly. On the
other hand, cellular networks have a wide coverage on the scale of kilometers and can
serve a whole building. However, measurement accuracy based on cellular signals is
not high enough to locate which shop or restaurant a person is in, and does not meet
the requirements of most indoor applications[10].
There are two typical indoor positioning approaches, Propagation-based and Location Fingerprinting (LF) based. Propagation-based approaches estimate the position
by measuring the received signal strength (RSS) with path loss. The drawbacks of
these approaches lie in the requirement to have a strong Wi-Fi coverage in order to
DYPCOE, Dept.of E&TC, PG (Communication Network) Seminar II
compute every condition that the signal can blend. The LF-based approaches such as
locate a device by comparing its coordinates with the received signal strengths (RSSs)
in a pre-recorded database. The drawbacks of these approaches are highly affected by
internal building infrastructure changes, presence of humans, and interference among
other devices. All these lead to unstable Wi-Fi coverage and inaccurate localization[9].
Figure 1: LF WPS Architecture
As shown in figure:1, the location is computed by WiFi RSS and calibrated by WPS
database for positioning in LF method. The fingerprinting technique is relatively simple
to deploy compared to the other techniques such as angle of arrival (AOA) and time of
arrival (TOA). There is no specialized hardware required at the mobile station (MS).
Any existing wireless LAN infrastructure can be reused for this positioning system.
The deployment of fingerprinting based positioning systems can be divided into two
phases. First, in the offline phase, the location fingerprints are collected by performing
a site-survey of the received signal strength (RSS) from multiple access points (APs).
The entire area is covered by a rectangular grid of points. The RSS is measured with
enough statistics to create a database or a table of predetermined RSS values on the
points of the grid. The vector of RSS values at a point on the grid is called the
location fingerprint of that point. Second, in the on-line phase, a MS will report a
sample measured vector of RSSs from different APs to a central server (or a group of
APs will collect the RSS measurements from a MS and send it to the server). The server
uses an algorithm to estimate the location of the MS and reports the estimate back to
the MS (or the application requesting the position information). The most common
algorithm is to estimate the location computes the Euclidean distance between the
measured RSS vector and each fingerprint in the database. The coordinates associated
with the fingerprint that provides the smallest Euclidean distance is returned as the
estimate of the position. The orientation filter and the Newton Trust Region (TR)
algorithm to enhance the traditional LF by filtering the noisy signal. Although the
average distance error is 1.82 m, this was not completely effective because they still
suffer from the poor Wi-Fi coverage region [9].
Literature Survey
There are several indoor positioning technologies used in smartphones.Research is

going on in Infra based,network terminal based, GPS cast based as well as Wi-Fi based
positioning system. And the most popular is WiFi positioning technology.
[1] Binghao Li1, James Salter, Andrew G. Dempster1 and Chris Rizos1,
Indoor Positioning Techniques Based on Wireless LAN, IEEE Conference, .
In this paper author has proposed approach for location fingerprinting method one
is deterministic and probabilistic. In deterministic the structure of the fingerprint
database is relatively simple and the feature of the RP is only determined by the average RSSs of each APs. Each fingerprint summarizes the data as the average signal
strength to visible access points, based on a sequence of signal strength values recorded
at that location.
[2] J. Kwon, B. Dundar, and P. Varaiya, Hybrid algorithm for indoor
positioning using wireless LAN, IEEE 60th Vehicular Technology Conference, VTC, vol. 7, 2004
In this paper the development of a hybrid method that combines the strength of two
methods which are progation and LF. First authors formulated the RF propagation
loss in a nonlinear, censored regression model and adjusts the regression function to the
observed signal strength in the fingerprint dataset. It balances flexibility and accuracy
of the two traditional methods, makes intelligent use of missing values, produces error
bounds, and can be made dynamic.
[3] K. Kaemarungsi and P. Krishnamurthy, Modeling of indoor positioning systems based on location fingerprinting, INFOCOM. Twenty-third
Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, 2004.
In this paper analytical models for analyzing positioning systems was developed. The
framework for analyzing a simple positioning system that employed the Euclidean distance between a sample signal vector and the location fingerprints of an area stored
in a database. And then analyzed the effect of the number of access points that are
visible and radio propagation parameters.
[4] N. Swangmuang and P. Krishnamurthy, Location Fingerprint Analyses Toward Efficient Indoor Positioning, Sixth Annual IEEE International
Conference on Pervasive Computing and Communications, pp. 101109,
2008.
The authors proposed a new analytical model that employed proximity graphs for
predicting performance of indoor positioning systems based on location fingerprinting.
This model allows computation of an approximate probability distribution of error distance given a location fingerprint database based on received signal strength and its
associated statistics.
[5] S. Fang, T. Lin, and P. Lin, Location Fingerprinting In A Decorrelated Space, Knowledge and Data Engineering, IEEE Transactions on,
vol. 20, no. 5, pp. 685691, 2008.
The authors proposed by projecting the measured signals into a decorrelated signal
space, the positioning accuracy can be improved. This approach achieves a more
efficient information compaction and provides a better scheme to reduce the online
computational complexity. The whole APs information can be utilized. And an additional advantage of technique is that fewer training samples are required to build the
localization system.
[6] Tatsuya Iwase and Ryosuke Shibasaki, Infra-free Indoor Positioning
Using only Smartphone Sensors, International Conference on Indoor Positioning and Indoor Navigation, 28th-31th October 2013.
A solution to reduce the accumulative error of pedestrian dead reckoning carried out
with only the low cost sensors and WiFi in smartphones by realizing cooperative positioning among multiple pedestrians. Authors proposed a method to introduces linkage
structures to simplify trajectories of pedestrians. The structures work as a constraint

to reduce the number of variables to be estimated. Since this constraint makes positioning problems solvable with a small number of observations, this proposed method
screened WiFi data by the signal strength and selected only strong signals for use in
positioning an indoor positioning technique which uses sensors on smartphones without
using any infrastructure.
[7] Yang Liu1, Marzieh Dashti, Mohd Amiruddin Abd Rahman and Jie
Zhang, Indoor Localization using Smartphone Inertial Sensors, IEEE2014.
In this paper, an economic and easy-to-deploy indoor localization model suitable for
ubiquitous smartphone platforms have been established. The method processes embedded inertial sensors readings through a inertial localization system. A particle filter
is developed to integrate the building map constraints and inertial localization results
to estimate users location. To increase the algorithm convergence rate, the users
initial/on-line room-level localization is achieved using WiFi signals. To achieve roomlevel accuracy, only very few training WiFi data, i.e. one per room or per segment of
a corridor, are required.
[8] Igor Bisio, Fabio Lavagetto, Mario Marches and Andrea Sciarrone,
Energy Efficient WiFi-based Fingerprinting for Indoor Positioning with
Smartphones, Globecom 2013-Wireless Networking Symposium
The paper presents an energy efficient WiFi-based indoor positioning algorithm, based
on the probabilistic fingerprinting method, suited to be used over smartphone platforms. The work proposed here a simple algebraic approach aimed at reducing the
computational and energy loads of the probabilistic fingerprinting, which is employed
to carry out the position of a smartphone on the basis of the captured WiFi Access
Points signal strengths in an indoor area. The presented solution does not apply any
kind of approximation with respect to the traditional approach, so avoiding accuracy
detriment. The idea is to factoring out the parts of the probabilistic fingerprint formulae that can be computed a-priori, so reducing the computational burden of the
positioning process.
[9]Eddie C. L. Chan and George Baciu, S.C. Mak, Using Fuzzy Color
Maps to Increase the Positioning Accuracy in Poor Wi-Fi Coverage Regions, IEEE 7th International Conference on Wireless and Mobile Computing, Networking and Communications
Many Researchers used the orientation filter and the Newton Trust Region (TR) algorithm to enhance the traditional LF by filtering the noisy signal. This paper, proposed
approach is divided into four phases. In the first phase that detect the IEEE 802.11b
Wi-Fi signal strength and collect the LFs into a training database. In the second phase
to create a fuzzy color map to visualize the distribution of Wi-Fi signal. To imposed
the Wi-Fi signal distribution color-coded as follows: red represents strong signals and
blue represents weak signals. The semantic expressivity of Fuzzy Logic makes easier
the best fingerprints extraction. Then, this fuzzy color map is used to improve the Kmean positioning algorithm by selecting location fingerprints from those access points
in the red region. Finally, to apply the orientation filter and the Trust-Region method
to estimate the position.
Theory
Wi-Fi based positioning system can be divide into three first one is Fuzzy Signal Color
Mapping, Secondly the positioning methodologies and and third system design
3.1
Fuzzy nature
Due to inherent uncertainty or fuzziness involved in defining Received signal strength,

the RSS can be treated as fuzzy variable. Thus Fuzzy Logic can be used to model the
wireless received signal strength. The fuzzy set theory provides a mechanism for representing linguistic constructs such as many, low, medium ,often, few. The
fuzzy logic provides an inference structure that enable appropriate human reasoning
capabilities. The theory of fuzzy logic is based upon the notion of relative graded
membership. The utility of fuzzy set lies in their ability to model uncertain or ambiguous data. The WLAN signal distribution color-coded as follows: red represents
strong signals and blue represents weak signals. The produced fuzzy signal graph could
give a very concrete visualization and useful pre-positioning information that helps to
estimate the location.
3.1.1
Fuzzy Membership Function
By using Fuzzy Logic mapping of RSS from a 0 to 1 fuzzy membership function can
be achieved. This approach does not use a numeric value. It uses fuzzy logic to broadly
categorize the RSS as strong, normal, or weak.
P (x) =
1 e
2
2
2 2
99K (1)
where P(x) is the probability function, x is the normalized RSS, is the standard
deviation of normalized signal normalized strength in a region, is the mean of signal
strength in a region. The membership function of term set, (RSS Density) is equal
to the set of Red,Green,Blue. Red means the signal strength density is strong; green
means the signal strength is normal; and blue means the signal strength density is
weak. The fuzzy set interval of blue is [0, 0.5], [0, 1] is green and [0.5, 1] is red.
For the blue region, = 0.5, = 0.

Blue (0 < x < 0.5) =
2
2 e2x
2
99K (2)
For the green region substitute, = 0.5, = 0.5.

Green (0 < x < 1) =
1
2 e2(x 2 )2
2
99K (3)
For the Red region substitute, = 0.5, = 1.

Red (0.5 < x < 1) =
2
2 e2(x1)
2
99K (4)
Figure 2: Fuzzy Membership function
Figure 2 shows the fuzzy membership function. X-axis represents the normalized
signal strength from 0 to 1 (from -93dBm to -15dBm). The width of membership function depends on the standard deviation of the RSS. The overlap area can be indicated
by mixed colors.
3.1.2
Fuzzy Signal Distribution
Using different colored regions to represent the WLAN RSS distribution. Conceptually a spatio-temporal region is defined as follows: Assume that B is a finite set
of RSS vectors belonging to a particular color region, where B = b1 , ....bn |bi Rn i.e
bi S, S R, and S [l, u] where l is the lower bound of fuzzy interval and u is
a upper bound of fuzzy interval. To analyze the distribution surfaces S, there always
exists a spatio-temporal mapping, q : B S
R
q(x) = s h(x)b(S)dS 99K (5)
h(x) =
1, if x S
0, x
/S
99K (6)
where h(x) is the characteristic function of S, i.e., b(S) is a weight function that
specifies a prior on the distribution of surfaces Explicitly define b(S) by the signal
propagation loss algorithm which calculates the received signal strength (RSS) with
path loss as follows: R = r0 10 log10 (d) wallLoss 99K (7)
where r0 is initial RSS, d is a distance from access points (APs) to a location, is
the path loss exponent (clutter density factor) and wallLoss is the sum of the losses
introduced by each wall on the line segment drawn at Euclidean distance d. Initially,
r0 is the initial RSS at the reference distance of d0 is 1 meter.
3.2
POSITIONING METHODOLOGIES
Orientation filter, Location Fingerprinting and the Newton Trust- Region methods
are used to estimate the position when the signal is stable. But when a person enters
in a poor Wi-Fi coverage region, the positioning accuracy drops dramatically. To solve
the inaccurate estimation due to the unstable signal, By selecting good candidates of
AP from the red region of the map that to estimate the position. Figure 3 shows the
flowchart which illustrated the process of each step of the the proposed positioning
approach. As shown in the flowchart,first testing of stability of signal by the Signal-toInterference-plus-Noise-Ratio (SINR) is done. The estimated position is too far away
from the Trust-Region. If either the signal is unstable or the estimation point is too far
away from the Trust-Region, instead of picking K-nearest fingerprints, the fingerprints
from the AP in the red region is chosen. Testing the Stability of the Signal In following
subsection, by using the Signal-to-Interference plus- Noise-Ratio (SINR) to determine
whether the signal is stable. SINR is commonly used in wireless communication as a
way to measure the quality of wireless connections.The energy of a signal fades with
distance, which is referred to as a path loss in wireless networks. The definition of
10
Figure 3: Flowchart of positioning approach
SINR is usually defined for a particular receiver (or user). In particular, for a receiver
located at some point x in space (usually, on the plane), then its corresponding SINR
given by as
SIN R(x) =
P
I+N
where P is the power of the incoming signal of interest, I is the interference power
11
of the other (interfering) signals in the network, and N is some noise term, which may
be a constant or random. Like other ratios in electronic engineering and related fields,
the SINR is often expressed in decibels or dB.
3.2.1
Testing the Stability of the Signal
In following subsection, by using the Signal-to-Interference plus- Noise-Ratio (SINR)

to determine whether the signal is stable. SINR is a very common indicator to measure
interference and defined as follows:
SIN R =
RP
b
(c ) R+n
99K (8)
where Rb is the highest RSS after path loss calculation. R is the remaining set of
RSS after path loss calculation. n is the noise signal strength. Rb , R, n are in dBm
unit. Usually, n should have the value of -100dbm. The interference-level function is
defined as follows.
(C ) = max(0, 1 kC ) 99K (9)
where C is the absolute channel difference and k is the non-overlapping ratio of
two channels. and C are in Db unit. For example, if SIN R 0.3, the signal suffers
from a large interference which make it unstable.
3.2.2
Estimation Testing Within the Trust-Region
To test whether the estimated point is too far away from the Trust-Region (TR).
k+1
2 k , if Pk 2
= k ,
if Pk [2 , 1 ]
1 k , if Pk 1
99K (10)
where Pk represents the TR fidelity, k represents the TR radius.2 and 1 ] represent
the lower and upper bound of TR fidelity. 1 and 2 represent the changing ratio of
the TR radius. If Pk > 32 holds, it implies the estimated point is three times away
from the region.
12
3.2.3
K-Mean Location Fingerprinting Algorithm
The K-Mean Location Fingerprinting algorithm requires the online RSS to search for
K closest matches of known locations in signal space from the previously-built database
according to root mean square errors principle. By averaging these K location candidates with or without adopting the distances in signal space as weights, an estimated
location is obtained via weighted K-NN or unweighted K-NN. K-NN classifies a new
data point based on the majority of its K-nearest neighbors. In the simplest case
(K=1), the algorithm finds the single closest match and use that fingerprints location as prediction. There are two sets of data for the Location-Fingerprint approach.
The first set of data is the offline samples of RSS from N APs in the area. Each element in a vector is an independent RSS (in dBm) collected from APs in the location.
W = 1 ...n |i Re is a set of online sampling LF vectors in database. Instead of
using entire set of offline LF vectors, one can use the LFs from APs in the red region
where W B S,S [0.5, 1], B is now a finite set of RSS in the red color region
and defined. The second set of data contains online RSSs,R = R1 ...Rn |Ri Re from
n APs at a particular location. The K-NN algorithm requires the collection of data
(i , dq ), i, q N , for n locations in the site, where dq is the known location of the q t h
measurement and the vector w i is the fingerprint of the location di . When a
receiver in unknown location A becomes aware of a new fingerprint r, it searches for
the fingerprint wi that is closest to r and then estimates the location. The unknown
location for r is decided by a majority vote from the K shortest distance fingerprints.
Estimation the location dq by clustering the distance between online received LF vector r and offline sampling LF vector i as. vector r and offline sampling LF vector i
P
1/q
as dq (r, w) = ( ni=1 |r i |q ) 99K (11) dq is called Manhattan distance if q=1 and
Euclidean distance if q=2 the accuracy does not necessarily higher as q increases. Let
wij be jth sample RSS in the it h access points. m is the number of access points. n is
the number of sample data. The distance between w i and wij is defined as
pPm
dj =
i=1 ij i j=1,2....n
Electing K samples since the smallest value and calculate average coordinates as
P
outputs in following equation: (x, y) = k1 ki=1 (xi , yi ) where (xi , yi is coordinates cor-
13
responding to ith sample.
3.3
System Design
The overall vision of proposed positioning system is shown in Fig.4. The working
Figure 4: system design
process consists of four main phases:

1) localization with room-level accuracy using Wi-Fi signals.
2) step detection using accelerometer sensor.
3) turning angle calculation using digital compass sensor.
4) considering building floor plan constraints to avoid collision to the walls.
Finally the particle filter fuses this information to provide a robust tracking system.
Particle filter employs particles to estimate users position and motion trends. The
key idea is that the particles should not occupy impossible positions given the map
constraints and users motion model. since the user cannot pass through walls, the
particles that cross a wall are weighted down. When a new step is detected, users
motion model is updated by compass readings. Finally, the users position is estimated
to be the average of particles positions.
14
3.3.1
Analyzing accelerometer and compass data
Due to repetitive nature of walks, when a user walks continually, similar pattern
for every step is found on accelerometer reading, a step detection algorithm based
on computing the cross-correlation of the previous sequence of accelerometer readings
samples with current sequence of accelerometer readings samples on the direction of
walks is presented. In this system, similar approach is utilized. Every time a new
step is detected, particle filter estimates the new position status by combining building
floor map constraints information and compass measurements. The compass reading
samples are stored in buffer and processed at the right time, i.e., the moments that
ever step is detected.
3.3.2
Particle filter
Particle filter is a practical implementation of recursive Bayesian filter with the sequential Monte Carlo methods. Bayesian filter estimates a system state vector by constructing the posterior probability density function (pdf) of that state. The posterior
pdf should reflect all the up-to-date knowledge about the system state vector. When
new information is received by recursive Bayesian filter, propagating and updating of
the previous posterior pdf will be implemented. Particle filter approaches probability
density function by distributing different weights to large amount of randomly generated samples. All the randomly generated samples are propagated and updated with
the motion model and measurement model, respectively. Unlike Kalman filter, particle
filter does not requires a prior knowledge of the exact position of user. Also, the model
of the inherent noise embedded in newly entered information and measurement used by
particle filter is not limited to Gaussian distribution. The particle filter implemented in
this system and the assumption used are similar to . The difference is the mechanism
of filtering particles. Convergence rate of particle filter in this system is faster and
reliable as well. The contribution is from implementing on-line room-level localization
technique.
15
3.3.3
Map constraints
Building floor map constraints are considered to calculate possible intersections of

particles trajectory with walls. A collision between moving particle and wall represents
that a possible user moving path intersects walls. As a result, the particle should be
filtered. An easy-to-implement collision detection algorithm is introduced. Given the
floor plan of the building, the coordinates of every walls and partitions are recorded in
the cloud server. To determine if the users trajectory collides a specific wall or not,
a novel approach is applied as following: Given both the coordinates of users current
location, (x1 , y1 ), and possible next location,(x2 , y2 ) as motion endpoints coordinates,
a linear equation representing the users trajectory can be written out , in the form
of y = kx + b. Similarly, linear equations for wall vectors could be built like that as
well. Then, by substituting two motion endpoints 2-D coordinates for x and y in wall
linear function, two values of M1 andM2 are obtained. Similarly, by substituting two
wall end points coordinates for x and y in linear motion function, two values of W1
and W2 are obtained. Three different scenarios may happen:
Figure 5: Collision is detected
M1 andM2 have the same polarities (they are both negative or both positive values) AND the polarities of W1 andW2 are the same as well: in this scenario users
trajectory does not collide the wall. The black dashed line shown in Fig. 4.
M1 andM2 have different polarities (one of them is a negative value and the other
16
is positive) AND W1 andW2 have different polarities as well: in this scenario users
trajectory collide the wall. See blue dashed line shown in Fig. 5.
either M1 andM2 have different polarities AND W1 andW2 have same polarities
OR M1 and M2 have same polarities AND W1 and W2 have different polarities
: in this scenario users trajectory does not collide the wall. See red line shown
in Fig. 5. . . .
3.3.4
Room-level localization
1) Initial room: In the offline phase, few Wi-Fi training data (RSS fingerprints)
are collected only at the center of the rooms, and center of each segments of long
corridors. These few training data limits the initial range of particles. Consequently
the filter convergence to the exact users location more quickly. The basic idea is that
the users online Wi-Fi scans are compared to all few training data to find the nearest
training data in signal space. In this system, using the algorithm presented in to get
the comparison results. Figure 5, A collision is detected in the second scenario. That
gives an initial room level accuracy of the users position. Then, particles are uniformly
distributed in and only in the users estimated initial room.
2) On-line room-level localization: As it is described, particle filter fuses inertial
data and map constraints and accordingly updates the particles continuously. At every
step, the users location is calculated as the average of survived particles positions.
Often when users go out from a room, experience a turn at corridor and then go along
the corridor, survived particles will be distributed in several different room or corridor
segments, so called multi-clustered particles. Clustered particles far from ground true
position of user, as shown in Fig. 5, have serious negative impact on location estimate.
To address this problem, on-line room-level localization algorithm is applied. This
algorithm only runs when a dramatic change in users status is observed, e.g., when
compass readings at two consecutive steps vary significantly. The algorithm aims at
limiting the particles in one room or one segment of a corridor. This task is also
finished by comparing on-line Wi-Fi scans with training fingerprints. The room or
corridor segment holding the smallest difference in signal space will be selected to be
17
on-line room localization result. The particles beyond determined room or corridor
segment range are filtered out. These useless particles are always filtered when their
future movements intersects with walls even if on-line room-level localization technique
is not used i.e., the application of on-line room-level localization technique accelerates
the process of dismissing these particles, which saves the computational load involved
in propagation of and collision detection of useless particles as well. Moreover, on-line
user location estimation error is further reduced by filtering these particles by on-line
room-level localization technique.
3.3.5
Updating the database through crowd-sourcing
Wi-Fi infrastructures may be added/removed/ or moved to new places according to

wireless coverage requirements. The un-updated RSS database causes inaccurate roomlevel positioning. Also, Collecting signal fingerprints deliberately to build a training
database covering all points on the interested indoor area is a time-consuming effort.
For tackling this problem, a simple crowd-sourcing approach, so-called back tracking
is developed to keep the database updated. To implement the back-tracking approach,
all particles are labelled uniquely at the start point of the trajectory. The number
of survived particles reduces by time due to filtering mechanism from on-line roomlevel localization and collision detection. Hence at the end point of the trajectory, the
final survived particles are more exactly converge to the exact users position. The
algorithm track the survived (and labelled) particles backward from the end of the
trajectory to the start point. Trough back propagation of final survived particles,
the position information of these tagged particles throughout the whole trajectory are
obtained. Average of particles position at every step is calculated as users location.
The back-tracking algorithm is applied in the off-line analysis phase after users arrive
at the desired locations. In this way, the Wi-Fi fingerprints database covering whole
interested indoor space could be built after several hours trial and updated as well.
Then, on-line localization accuracy could be benefited from comparing on-line Wi-Fi
scans with the fingerprints data in the database.
18
3.4
Implemented project by Google
Google has successfully implemented Wi-Fi based positioning system by using omnidirectional radio antenna. This antennae receives publicly broadcast wifi radio signals
within range of the vehicle. The vehicle travels at normal road speeds, and so spends
only a very short amount of time within the range of any given wifi access point.
The signals are initially processed onboard in the car, using software including the
standard Kismet open source application. The data is then further processed when
transferred to servers within a Google Data Centre, and used to compile the Google
location based services database. The equipment within the vehicle operates passively,
receiving signals broadcast to it but not The information visible to the equipment is
that which is publicly broadcast over the radio network, using the 802.11 standard.
This includes the 802.11b/g/n protocols. The equipment is able to receive data from
all broadcast frames. This includes, from the header data, SSID and MAC addresses.
All data payload from data frames are discarded, so Google never collects the content
of any communications. In addition, the operator of the access point can choose to
restrict the SSID from broadcast, and in many cases this will mean that the SSID is
not received (although this may vary depending on the way the access point broadcasts
data). The equipment also separately records the signal strength and channel of the
broadcast at the point at which it was received by equipment, and is able to establish
the protocol used (i.e. 802.11b/g/n). It is possible to identify from the data received
if an access point is encrypted - this may be included in the data sent in the frame
header but in any event will be self-evident from the presence of encryption within the
frames generally.
The data which is collected used to provide location based services within Google
products and to users of the Geolocation API. For example, users of Google Maps for
Mobile can turn on My Location to identify their approximate location based on
cell towers and wifi access points which are visible to their device. Similarly, users of
sites like Twitter can use location based services to add a geolocation to give greater
context to their messages. Google currently uses 2 pieces of the data collected during
19
the driving operation to build its database and provide location based services - the
MAC address of the access point and the GPS co-ordinates of the vehicle at the point
at which the access point was visible. This data is stored in aggregate form, and is
used to provide the location based service. Google location based services using wifi
access point data work as follows:
The users device sends a request to the Google location server with a list of
MAC addresses which are currently visible to the device;
The location server compares the MAC addresses seen by the users device with
its list of known MAC addresses, and identifies associated geocoded locations
(i.e. latitude /longitude);
The location server then uses the geocoded locations associated with visible MAC
address to triangulate the approximate location of the user;
This approximate location is geocoded and sent back to the users device. . . .
The only data which Google discloses is a triangulated geocode which is an approximate
location of the users device. At no point does Google publicly disclose MAC addresses
from its database (in contrast with some other providers in Germany and elsewhere).
There has been speculation that Google will make available a map or list of wifi access
points, including identifying the SSID of each access point and/or identifying those
which are open.
20
Application
WPS is a fast-growing, technologically sophisticated field, with potential applications

in many different industries. The most common civilian applications to date have been
land, air and marine navigation, and surveying. More recent applications include agriculture, aircraft precision approach, robotics, intelligent traffic systems, construction,
resource extraction, and geographic information systems (GIS). Developments in hybrid GPS and WPS mean increased reliability and accuracy, and even more widespread
possibilities for tomorrow.
Automobile Navigation : An automotive navigation system incorporates GP S +
W P S and route guidance technology to give accurate real-time route direction
and guidance. Major automobile manufactures now offer optional navigation systems, including General Motors, which first offered, GuideStar from Oldsmobile
and later OnStar from Cadillac.
BMW is offering a navigation system with a liquid-crystal monitor includes

controls for the navigation system, cellular phone, audio system, on-board computer, security system and automatic ventilation system. BMW owners will have
an emergency function that automatically calculates the vehicles exact location
and displays it on the monitor.
Fleet Tracking: Automatic Vehicle Location (AVL) is the combination of GP S +
W P S and computer technology for use with plans, automobiles, trucks and ships.
Vehicles equipped with fleet tracking can be tracked in real time or trips can be
replayed later. You can determine the exact track of each journey and identify
the exact position and time of specific events such as deliveries, extended stops,
etc. Citycab, one of Singapores primary taxi companies, has deployed innovative
satellite technology to provide a solution to the citys transportation dilemma.
The Hilton Hotel chain has applied this idea to its 27 airport hotels in the US.
In addition to tracking each vans exact location, improving driver efficiency and
21
providing advance guest registration, the system is also being used to rapidly
locate a guests automobile upon checkout for immediate front-door delivery.
Mapping & Surveying : W P S + GP S Surveying is the ideal way to survey
positions in a short period of time. Each point surveyed is independent of the
other, which eliminates time consuming traverse. With GPS, an unlimited area
can be covered using satellite transmissions. One person is capable of conducting
a field survey on foot or in a vehicle. Integrated with GIS systems, maps can be
computer generated directly from the field survey data and WPS added more for
indoor.
Mining: Using the WPS gear linked to a computer-designed mine plan, this helps
the company achieve crucial new levels of efficiency. . . .
22
Conclusion
An economic and reliable indoor positioning apporach suitable for smartphone platforms which provides a more accurate and robust mechanism to solve the traditional
poor indoor GPS problem by Wi-Fi based positioning system.In Propagation-based
approache estimated the position by measuring the received signal strength (RSS) so
for poor RSS the system performed poor.The LF method is highly affected by internal
building infrastructure changes, presence of humans, and interference among other devices. So in Wi-Fi based positioning system in fuzzy signal color map helps to improve
the K-mean positioning algorithm by sampling location fingerprints from access points
in the red regions.
23
References
[1] Binghao Li1, James Salter2, Andrew G. Dempster1 and Chris Rizos1, Indoor
Positioning Techniques Based on Wireless LAN, IEEE Conference, .
[2] J. Kwon, B. Dundar, and P. Varaiya, Hybrid algorithm for indoor positioning
using wireless LAN, IEEE 60th Vehicular Technology Conference, VTC, vol. 7, 2004
[3] K. Kaemarungsi and P. Krishnamurthy, Modeling of indoor positioning systems
based on location fingerprinting, INFOCOM. Twenty-third Annual Joint Conference
of the IEEE Computer and Communications Societies, vol. 2, 2004.
[4] N. Swangmuang and P. Krishnamurthy, Location Fingerprint Analyses Toward Efficient Indoor Positioning, Sixth Annual IEEE International Conference on
Pervasive Computing and Communications, pp. 101109, 2008.
[5] S. Fang, T. Lin, and P. Lin, Location Fingerprinting In A Decorrelated Space,
Knowledge and Data Engineering, IEEE Transactions on, vol. 20, no. 5, pp. 685691,
2008.
[6] Tatsuya Iwase and Ryosuke Shibasaki, Infra-free Indoor Positioning Using only
Smartphone Sensors, International Conference on Indoor Positioning and Indoor Navigation, 28th-31th October 2013.
[7] Yang Liu1, Marzieh Dashti, Mohd Amiruddin Abd Rahman and Jie Zhang,
Indoor Localization using Smartphone Inertial Sensors, IEEE2014.
[8] Igor Bisio, Fabio Lavagetto, Mario Marches and Andrea Sciarrone, Energy Efficient WiFi-based Fingerprinting for Indoor Positioning with Smartphones, Globecom
2013-Wireless Networking Symposium
[9]Eddie C. L. Chan and George Baciu, S.C. Mak, Using Fuzzy Color Maps to
Increase the Positioning Accuracy in Poor Wi-Fi Coverage Regions, IEEE 7th International Conference on Wireless and Mobile Computing, Networking and Communications.
[10] Google Help - Location-based services-How do I opt out? Obtained 2012-05-30.
[11] website: http : //gps.about.com/od/glossary/g/wif ip osition.htm
24

Wireless Positioning System

Uploaded by

Copyright:

Available Formats

Wireless Positioning System

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Wireless Positioning System

Uploaded by

Copyright:

Available Formats

Seminar II

Wi-Fi based Indoor positioning

Exam seat no.

Mrs. Trupti Wagh

Department of Electronics and Telecommunication

D. Y. PATIL COLLEGE OF ENGINEERING

DEPARTMENT OF ELECTRONICS & TELECOMMUNICATION

Mrs. Trupti Wagh

HOD (E. & T.C.)

Fuzzy Membership Function . . . . . . . . . . . . . . . . . . . .

Fuzzy Signal Distribution . . . . . . . . . . . . . . . . . . . . .

Testing the Stability of the Signal . . . . . . . . . . . . . . . . .

Estimation Testing Within the Trust-Region . . . . . . . . . . .

K-Mean Location Fingerprinting Algorithm . . . . . . . . . . .

Analyzing accelerometer and compass data . . . . . . . . . . . .

Updating the database through crowd-sourcing . . . . . . . . .

Implemented project by Google . . . . . . . . . . . . . . . . . . . . . .

Fuzzy Membership function . . . . . . . . . . . . . . . . . . . . . . . .

Flowchart of positioning approach . . . . . . . . . . . . . . . . . . . . .

Wi-Fi Positioning System

Global Positioning System

Location Fingerprinting (LF)

received signal strength

Newton Trust Region

probability density function

Medium access controller

Wi-Fi based Indoor positioning

Wi-Fi based Indoor positioning

Figure 1: LF WPS Architecture

Wi-Fi based Indoor positioning

DYPCOE, Dept.of E&TC, PG (Communication Network) Seminar II

Wi-Fi based Indoor positioning

There are several indoor positioning technologies used in smartphones.Research is

DYPCOE, Dept.of E&TC, PG (Communication Network) Seminar II

Wi-Fi based Indoor positioning

DYPCOE, Dept.of E&TC, PG (Communication Network) Seminar II

Wi-Fi based Indoor positioning

structures to simplify trajectories of pedestrians. The structures work as a constraint

DYPCOE, Dept.of E&TC, PG (Communication Network) Seminar II

Wi-Fi based Indoor positioning

DYPCOE, Dept.of E&TC, PG (Communication Network) Seminar II

Wi-Fi based Indoor positioning

Due to inherent uncertainty or fuzziness involved in defining Received signal strength,

Fuzzy Membership Function

DYPCOE, Dept.of E&TC, PG (Communication Network) Seminar II

Wi-Fi based Indoor positioning

For the blue region, = 0.5, = 0.

For the green region substitute, = 0.5, = 0.5.

For the Red region substitute, = 0.5, = 1.

Figure 2: Fuzzy Membership function

Fuzzy Signal Distribution

Wi-Fi based Indoor positioning

DYPCOE, Dept.of E&TC, PG (Communication Network) Seminar II

Wi-Fi based Indoor positioning

Figure 3: Flowchart of positioning approach

DYPCOE, Dept.of E&TC, PG (Communication Network) Seminar II

Wi-Fi based Indoor positioning

Testing the Stability of the Signal

In following subsection, by using the Signal-to-Interference plus- Noise-Ratio (SINR)