Transcript WILL: Wireless Indoor Localization Without Site Survey

WILL: Wireless Indoor Localization
Without Site Survey
Chenshu Wu1, Zheng Yang1,3, Yunhao Liu1,3, Wei Xi2,3
1MOE Key Lab for Information System Security, School of Software,
Tsinghua National Lab for Information Science and Technology,
Tsinghua University
2Xi’an Jiao Tong University
3Department of Computer Science and Engineering, HKUST
1
Outline
•
•
•
•
•
Introduction
WILL Architecture
Experiment
Performance
Conclusion
2
Introduction
• A majority of previous localization approaches
employ Received Signal Strength (RSS) as a
metric for location determination
• localization is usually divided into : training
and serving
3
Introduction
• Training
– involve the site survey process in which engineers
record the RSS fingerprints at every position of an
interesting area and build a fingerprint database
• Serving
– user sends a location query with its current RSS
fingerprint, localization algorithms return the
matched locations
4
Introduction
• What’s the problem?
Site Survey
– time-consuming
– labor-intensive
– easily affected by environmental dynamics
• But construct fingerprint database is
inevitable
by exploiting user motions
from mobile phones
• Achieve competitive room level accuracy
5
Introduction
• wall-penetrating effect
– signals may encounter a considerable abrupt
change while passing through a wall
– RSS of a same AP can vary significantly in two
rooms
• Tri-axial accelerometers
– obtain user movements and utilizes moving traces
to assist localization
– explore reachability between different areas
6
Introduction
7
WILL Architecture
8
Fingerprint Collection
• users do not need to deliberately collect data
– The information of WiFi signals and sensor
readings is collected automatically by their smart
phones
• Continuous vs. discontinuous records
– If the records are measured during user’s
movements or not
9
Fingerprint Processing
• Due to signal instability, it is inadequate to utilize
absolute RSS values directly for location
estimation
• RSS stacking difference
– cumulative difference between one AP and all other
APs
– Calculate the
dissimilarity of
F and F’
– I is an indicative
function
10
Virtual Room Generation
• Formally, if ϕ(F1, F2) < ξ, F1 and F2 are treated
to be in the same virtual room, where ξ is a
dissimilarity threshold of the room
• Can be clustered by data mining approach
• Each fingerprint is tagged with a virtual room
label
• Each room R is marked with a representative
fingerprint F[R]
11
Logical Floor Plan Construction
• Just use the continuous records (trace)
• formalized as an undirected graph P = (V, E)
• Edge (u, v)ϵ E
– a user can walk from room u to v seamlessly
without passing any other room
• If a user walks from room A to room B through
a corridor segment C
– C is reachable from both A and B
– A is not directly connected to B
12
Logical Floor Plan Construction
• consider a single user trace <F, A> where
F=[F1, F2, …, Fm], A=[A1, A2, …, Am] indicate the
a sequence of m fingerprints and acceleration
records
– Each Fi belongs to a Ri
• if Ri ≠ Ri+1, edge (Ri, Ri+1) is added to the logical
floor plan P if (Ri, Ri+1) is not in E
13
Logical Floor Plan Construction
14
Floor Plan Mapping
• physical floor plan is also modeled with an
undirected graph P′ = (V’, E′)
– the corridors can be divided into several segments
– Essentially, corridors are connected to most rooms
– Find a mapping function p:V→V’
• Subsection Mapping Method (SSMM)
– Skeleton Mapping
– Branch-Knot Mapping
– Correction
15
Floor Plan Mapping
• Skeleton Mapping
– Betweenness centrality
– σst is the number of shortest paths from s to t
– Vertices that occur on many shortest paths
between other vertices have higher betweenness
– A certain number of vertices which have higher
betweenness are mapped to the corridor
segments
16
Floor Plan Mapping
• Branch-knot mapping
– the rest vertices are mapped using Kuhn-MunKras
Algorithm [23]
– Using
as weight, solve
the weighted minimum bipartite matching
– Minimize
• [23] J. Munkres, “Algorithms for the assignment and
transportation problems,” Journal of the Society for
Industrial and Applied Mathematics
17
Floor Plan Mapping
• Correction Algorithm
18
Floor Plan Mapping
19
Floor Plan Mapping
20
Floor Plan Mapping
21
Localization
• each virtual room R are marked with a
fingerprint F[R]
• Given a finger print F
– localization engine first determines the virtual
room
– consults the floor plan database to obtain the
physical room
22
Database Update
• Minor update
– Use user query to update virtual room features
– representative fingerprints, dissimilarity
thresholds
• Major update
– if huge data are collected through a long-term
running, especially when enough continuous data
are included
– floor plan is corrected
23
Experiment
• Use Android smart phones collect Wifi signal
• Deployment
– 1600 m2
– 16 offices (5 large, 7 small, 4 inaccessible)
– 26 APs
– steel keels wrapped in two wooden clapboard
– Wifi signal: per 0.5 second
– Accelerometer: 50 ms/ 1 sec
24
Experiment
25
Performance
26
Performance
27
Performance
28
Performance
29
Performance
30
Performance
31
Conclusion
• WILL is an indoor logical localization approach
without labor-intensive site survey or
knowledge of AP locations and power settings
• It achieves an average room-level accuracy of
86%, which is competitive to existing designs
32