Multidimensional Scaling
Multidimensional scaling (MDS) [4] is a set of related s-
tatistical techniques often used in information visualization
for exploring similarities or dissimilarities in data. An MD-
S algorithm starts with a matrix of item-item dissimilari-
ties, then assigns a location to each item in d-dimensional
space, where d is specified a priori. For sufficiently small d
(d =2, 3), the resulting locations may be displayed in a 2D
graph or a 3D structure.
Seeing inter-device distances as a metric of dissimilarity,
many approaches of network localization adopt MDS as a
tool for calculating the locations of wireless devices [28, 8].
For example, in wireless sensor networks, sensor nodes are
capable of measuring the distances to neighboring nodes by
RSS, ToA, TDoA, etc. MDS is used to assign a coordinate
to each node such that the measured inter-node distances
are as much preserved as possible. Some researchers pro-
pose MDS to figure out WiFi AP locations [14]. In their
approach, AP-AP distances are determined by a radio at-
tenuation model. Although being similar to our solution in
terms of the usage of MDS, it is neither for user localization
nor fingerprinting-based.
3. OVERVIEW
3.1 Data Collection
User participation is essential in the initial period at the
online stage. Untrained users walk in a building following
daily activities. Mobile phones, carried by users, collect
WiFi RSS characteristics (a.k.a. RSS fingerprints or signa-
tures) at various locations along user movement paths, and
the walking distances are also recorded. Walking distances
are measured as footsteps from the readings of integrated
accelerometers in mobile phones. Similarly, accelerometers
also infer the starting and finishing moments of user paths.
LiFS harnesses the walking distance between two endpoints
(denoted by corresponding fingerprints) along a user path to
establish the geographical relationship among fingerprints.
During data collection, users can be even unaware of the
collection task in which they are actually involved.
3.2 System Architecture
In this subsection, we present the system architecture
of LiFS, as shown in Figure 1. The working process of
LiFS consists of two phases: training and operating. The
major output of training phase is a fingerprint database in
which an RSS fingerprint and its corresponding location are
associated. The fingerprint database is further used in op-
erating phase to process location requests. We describe the
training and operating phases in detail next.
Training Phase. The core task of training phase is to
build the fingerprint database. We divide this task into 3
steps: (1) transforming floor plan to stress-free floor plan;
(2) creating fingerprint space; (3) mapping fingerprints to
real locations.
A floor plan shows a view of a building structure from
above, including the relationships between rooms, spaces,
and other physical features. The geographical distance be-
tween two locations in a floor plan is not necessary to be
the walking distance between them due to the block of wall-
s and other obstacles. Hence, we propose stress-free floor
Floor Plan
Stress-free
Floor Plan
Raw RSS
Data
Fingerprint
Space
Fingerprint
Database
MDS MDS
Mapping
Location
Query
Location
Estimation
ra
in
Figure 1: System architecture.
70m
23m
Stairs
Corridors
Inaccessible areas
AP Locations
Figure 2: Floor plan of the experiment field.
plan, which puts real locations in a floor plan into a high
dimension space by MDS [4], such that the geometrical dis-
tances between the points in the high dimension space reflect
their real walking distances. Through stress-free floor plan,
the walking distances collected by users can be accurately
and carefully utilized.
Fingerprint space is a unique component in LiFS, differ-
ent from traditional approaches. According to the inter-
fingerprint distances, MDS is used to create a high dimen-
sion space, in which fingerprints are represented by points,
and their mutual distances are preserved. In traditional ap-
proaches, fingerprints are geographically unrelated, losing
the possibility of building fingerprint space.
In fingerprint database, fingerprints are associated with
their collecting locations (i.e., fingerprints are labeled with
locations). Such associations are achieved by mapping fin-
gerprint space (fingerprints) to stress-free floor plan (loca-
tions) . As shown in Figure 1, fingerprint database, as the
core component, connects training and operating phase.
Operating Phase. When a location query comes, usu-
ally an RSS fingerprint sent by a user, LiFS takes it as a
keyword and searches the fingerprint database. The best
matched item is viewed as the location estimation and sent
back to users. To find the best matches, many searching
algorithms can be used. In this design, we adopt a simple
one, the nearest neighbor algorithm. More specifically, we
assume that a fingerprint f is collected at the same location
as f
,iff
is the most similar to f in the fingerprint database.
4. STRESS-FREE FLOOR PLAN
In architecture and building engineering, a floor plan is a
diagram, showing a view from above of the relationships be-
tween rooms, spaces, and other physical features at one level