10-10-2012, 02:18 PM
Wireless Indoor Tracking System (WITS)
wits.pdf (Size: 1,003.98 KB / Downloads: 107)
Abstract
A wireless indoor tracking system is described in this paper, which can be
used to track and locate both moving and static WLAN-enabled devices
inside a building. The system is purely software based, which means an
advantage for the existing WLAN. No additional hardware and costs are
required. Using complex mathematic algorithms, the system determines
the locations of the mobile devices according to the received signal
strength from visible access points. Taking into account the historical
signal strength, the interior structure of the building and available Bluetooth
access points, the positioning and tracking accuracy achieved is very
optimistic. Experimental results are reported at the end of the paper.
Introduction
People’s location is a crucial ingredient in many ubiquitous computing applications.
It makes possible reasoning about what the person is doing or what he/she
is interested in, therefore determining what information to present and in what
way, even triggering automatic events that benefit the person. Development of
wireless communication technology and widely deployment of wireless networks
have made location-aware applications possible and necessary. Tourist guiding
system in the city, visitor guiding system in the conference center, multimedia
navigation and information system in the gardens or zoos, and etc, will benefit us
greatly. To realize such promising applications, we must have an accurate
positioning and tracking system as prerequisite.
Related work
Since WLAN-based tracking has gained much attention in recent years, several
teams have been working in this field. RADAR, developed by Bahl and Padmanabhan,
is regarded as the first one. Using the nearest neighbor algorithm, RADAR
gave a median spatial error distance of 2.94 meters [Bah00a]. Using a Viterbi-like
algorithm in the enhanced-RADAR, the median spatial error distance was reduced
to 2.37 meters [Bah00b]. LOCADIO developed by Krumm and Horvitz used
Hidden Markov Model to infer the location of a client with a median error of
1.5 meter and whether or not the client is in motion with a classification accuracy
of 87%. For motion, they measure the variance of the signal strength of the strongest
access point as input to a simple two-state Hidden Markov Model for smoothing
transitions between the inferred states of »still« and »moving«. For location,
they used another Hidden Markov Model on a graph of locations nodes [Kru04].
The location system described by Ladd et al. used Bayesian reasoning and a Hidden
Markov Model (HMM). Taking into account signal strength from multiple
access points, the probability of seeing the access points at a location and the orientation, the system achieved a median spatial error distance of around 1 meter in
hallways [Lad02]. A WLAN location determination technique, the Joint Clustering
technique, presented by Youssef et al. used 1) signals strength probability distributions
to address the noisy wireless channels, and 2) clustering of locations to
reduce the computational cost of searching the radio map. The technique gave
user location to within 7 feet with over 90% accuracy [You03]. Ekahau is the
commercial real-time location system using site calibration and statistical modeling
of signal strengths in the market, which announces up to 1 meter average
accuracy [Eka]. While most other teams used manual calibration, UCSD’s ActiveCampus
used a formula that approximates the distance between wireless sensor
and access point as a function of signal strength. Using hill-climbing algorithm,
the system achieved the accuracy of 10 meters [Gri02].
System description
The approaches to determine the locations of the mobile devices based on WLAN
can be categorized into two classes: switch-based and client-based. To realize
switch-based location determination, the wireless switch system must include a
positioning component, which measures the signal strength of the mobile devices
within its range and estimates their locations using specific mathematical algorithms.
All the work is done at the switch side. Differently, for client-based location
determination, it is the mobile device that retrieves the signal strength from
its wireless adapter and reports it to the location determination server, which
then estimates the location of the mobile device using proper mathematical algorithm.
Client-based location determination does not require the positioning component
to be included in the wireless switch system, therefore, can work with
normal 802.11 access points. The Wireless Indoor Tracking System (WITS) discussed
in this paper is client-based.
A calibration process must be conducted before the client-based tracking, in
which signal strength footprints at various locations inside the building are collected
and stored in a so called RSS (Received Signal Strength) radio map. In the
tracking phase, the client, i.e. the mobile device, retrieves the current received signal
strength from visible access points, passes them to the location determination
server, which matches them with the RSS radio map and estimates the current
location of the client using the positioning and tracking algorithm. The estimated
locations can be used by upper-layer location-aware applications. Figure 1 illustrates
the process and the components.
Nearest neighbor algorithm
The nearest neighbor algorithm provides the basic idea of deterministic WLANbased
positioning. During calibration, the system collects multiple samples of signal
strength footprints at the calibrated locations and stores the signal strength
mean value of every calibrated location in the RSS radio map. In tracking phase,
the current received signal strength is compared with the mean values in the RSS
radio map. The record that matches the current received signal strength best is
picked up. The idea is to calculate the Euclidean distance between the current
received signal strength and the records in the RSS radio map and choose the one
minimizing the Euclidean distance [Bah00a].
Layout of building
In indoor scenario, logical errors, such as being indistinguishable of different
floors, different rooms, or different sides of a wall, are regarded as big errors.
Even though their spatial distance may be small, the path between them might be
quite long. To reduce such logical errors, the layout of the building is applied to
the tracking algorithm, which proves quite effective.
The layout of the building is expressed by a connected graph, in which the
directly connected vertexes are adjacent locations. The shortest distance between
any two locations can be calculated by Dijkstra’s shortest path algorithm, which
is then used as the physical distance in the history-based algorithms illustrated in
Figure 4. Since the layout of the building does not change often, the shortest distance
between calibrated locations are calculated by Dijkstra’s shortest path algorithm
and stored in the database, from which the history-based algorithm get the
distance directly without complex calculation. The left figure in Figure 5 is the
snapshot of the table which contains the information of the directly connected
calibrated locations. The right figure contains the shortest distance between any
two calibrated locations. [Kru04]