### Method of Indoor Position

```Techniques of Indoor
Positioning

Outline
Introduction
 Basic Techniques
 Commercial Products
 Using the Indoor Map Information
 Indoor Positioning Using Femtocell
 4G LTE-A Localization System
 In-Location Alliance
 Conclusions

Introduction

Location-aware real-time services
◦ Elderly nursing
◦ Child monitoring
◦ Object positioning
Global Positioning System (GPS) is the
most well-known positioning service
 The restrictions of GPS

◦ Requiring a line of sight (LOS) with satellite
systems
Introduction (cont.)
◦ GPS signal is easily affected by buildings
◦ Errors up to 10m

Need other techniques for indoor
positioning
Basic Techniques

Employ some information between
beacon nodes and the unknown node
Trilateration
Trilateration (cont.)
Node A’s coordinate is (xa, ya)
 Node B’s coordinate is (xb, yb)
 Node C’s coordinate is (xc, yc)
 The unknown node D’s coordinate is (x,
y)
 The distance between A (or B or C) and
D is d1 (or d2 or d3)

Trilateration (cont.)
Triangulation (cont.)
Triangulation (cont.)
The unknown node D’s coordinate is (x,
y)
 Node A’s coordinate is (xa, ya) and the
angle to the D is ∠ADB
 Node B’s coordinate is (xb, yb) and the
angle to the D is ∠ADC
 Node C’s coordinate is (xc, yc) and the
angle to the D is ∠BDC

Triangulation (cont.)

Circle
center coordinate is
α = ㄥ1 = 2π − 2ㄥ
to calculate
and r1
 Similarly, calculate
and
center
 Use trilateration to calculate D’s position
,
Measuring Distance
Three basic properties to measure the
distance between a beacon node and a
unknown node
2. Time of flight (TOF)
3. Angle of arrival (AOA)

Two kinds of methods for RSSI location
1. Database

(cont.)

Database
◦ Measure the relation between distances and
◦ Set up a database

According the database, we can calculate
the distance between two nodes
(cont.)

◦ In the RADAR system, the Wall Attenuation
Factor (WAF) model is:
where n indicates the rate at which path loss
decreases with distance, P(d0) signal power at
some reference d0, and d is the transmitterreceiver distance.
(cont.)
Moreover, C is the maximum number of
obstructions (walls), nW the number of
obstructions between the transmitter and
receiver, and WAF is the wall attenuation factor.
Time of flight

Calculate the distance between a
transmitter and a receiver by the time of
flight
◦ Time of arrival (TOA)
◦ Time difference of arrival (TDOA)
Time of flight (cont.)

TOA
◦ The transmitter and receiver must
synchronize their time
◦ The transmitter sends a signal to the receiver
◦ Upon receiving the signal, based on the
propagation time, the receiver can calculate
the distance between the transmitter and it
Time of flight (cont.)
Time of flight (cont.)

TDOA
◦ Based on the difference of time between
different signals from the transmitter arriving
◦ The transmitter sends two different signals
with propagation speeds α1 , α2, respectively
different times, say T1 and T2, respectively
◦ The distance is
Time of flight (cont.)
Angle of arrival

By the propagation direction of radiofrequency waves incident on an antenna
array
Comparisons

◦ Disadvantage: unstable, easily impacted by the
environment

TOA
complex hardware
Comparisons (cont.)

TDOA
◦ Advantage: no time synchronization, good
accuracy

AOA
required
Maximum likelihood estimation
Maximum likelihood estimation
(cont.)

n reference nodes with coordinates
The unknown node in (x, y)
 The distances between reference nodes
and the unknown node are
,

Maximum likelihood estimation
(cont.)

Subtract the last equation from each
equation
Maximum likelihood estimation
(cont.)

Use the matrix representation AX=b

The coordinate of the unknown node :
Self-Calibrating Indoor Positioning
System Based On ZigBee Devices
This paper presents a positioning system
based on the round-trip time-of-flight
(RTT) measurement
 RTT can be modeled as:

System Architecture

The developed system is composed of
three types of transponders:
◦ Mobile node
◦ Calibration node
◦ Fixed node
System Architecture (cont.)

Mobile node
◦ Chipcon CC2431 : Zigbee chip
◦ TMS320C6713(DSP) : Timing and control
functions
◦ TDC-GP2 : Time interval measurement
function, timing and control functions
System Architecture (cont.)

Calibration node
◦ Chipcon CC2431 : Zigbee chip
◦ TDC-GP2 : Time interval measurement function,
timing and control functions

Fixed node
◦ Chipcon CC2431 : Zigbee chip
Measuring procedure

Measuring procedure
1.
2.
3.
4.

Initiated by a mobile node
It transmits a packet to a fixed node
Fixed node retransmits a packet
The master node receives the packet and its
TDC determines the RTT
Calibrating procedure
1. Initiated by a mobile node
2. It transmits a packet to a calibration node
3. The calibration node initializes its TDC
Measuring procedure (cont.)
4. The calibration node transmits a packet to a
selected fixed node
5. The selected fixed node received and
retransmits the packet
6. The calibration node receives the packet
and its TDC determines the RTT
7. The calibration node repeats the foregoing
procedure to a set of fixed nodes
8. The results of RTT are sent to the mobile
node for calibration
Measuring procedure (cont.)

By using the calibration data, the mobile
node DSP can determine the unknown
position more accurately
Tested Result

Three fixed node, one calibration node
NTU Indoor Localization

◦ Training
 Collect RSSI values at every specific position
 Use all collected RSSI values to build a database
◦ Tracking
 Upon receiving RSSI values, an end-device can
compare them with those in the database
 Then calculate the position by KNN (K-NearestNeighbor)
NTU Indoor Localization (cont.)
Fingerprint location
(B1,B2,B3,B4…) (x1,y1,z1)
Beacon 1
Beacon 2
…..
…..
…..
…...
Beacon 3
Look up the table
NTU Indoor Localization (cont.)
NTU Indoor Localization (cont.)

Example of KNN
AP2
30m
AP1
9
10
11
12
5
6
7
8
1
2
3
4
50m
AP3
NTU Indoor Localization (cont.)

STEP1
normalizes them

STEP2
◦ The normalized RSSI values are compared with
those in the database, and find the minimum L
differences Dn
◦
◦ Sn is store at the database

STEP3
◦ For L nearest neighbors, the location estimate is
◦
NTU Indoor Localization (cont.)

STEP1
◦ PT = (-94dbm -96dbm -95dbm)
◦ PT = (0dbm -2dbm -1dbm)

RL
1
x,
y
2
3
Normalize
4
5
6
7
8
9
10
11
12
10, 20, 30,
10 10 10
40,
10
10,
20
20,
20
30,
20
40,
20
10,
30
20,
30
30,
30
40,
30
AP1
-73 -82 -89
-94
-82
-86
-91
-95
-89
-91
-94
-97
AP2
-82 -86 -91
-95
-73
-82
-89
-94
-66
-80
-87
-93
AP3
-94 -89 -82
-73
-93
-87
-80
-66
-94
-89
-82
-73
AP1
0
0
0
0
0
0
0
0
0
0
0
0
AP2
-9
-4
-2
-1
9
4
2
1
23
11
7
4
AP3
-21 -7
7
-21
-11
-1
11
29
-5
2
12
24
NTU Indoor Localization (cont.)

STEP2
RL 1
D

2
3
4
5
6
7
8
9
10 11 12
21 8
8
22
15
6
13
30
25
13
STEP3
◦
◦
16
26
AeroScout
AeroScout Tag
Tag using RFID 2.4Ghz WiFi transmission, MAX read
range 200M, LF125k precise positioning 1~2M，
positioning in outdoor or harsh
environments
 They execute sophisticated radio signal
measuring and calculating methods
 Then the results are sent to the
AeroScout Engine for accurately
positioning

AeroScout TDOA

Use TDOA for positioning
AeroScout System Architecture
AeroScout Engine
vendor's wireless Access Points nearby
 Allow accurate and reliable positioning
for assets equipped with AeroScout's WiFi-based Active RFID Tags

AeroScout MobileView

Customers use MobileView to TRACK,
MANAGE and INTEGRATE their assets
from a single platform
Ekahau
Ekahau System Architecture
Ekahau RTLS works on top of any standard 802.11
compliant networks, even with multi-vendor
networks
 Key components of the system include:

◦ Wi-Fi tags
 Various physical formats, battery options and features
◦ Ekahau RTLS Controller (ERC)
 Sends messages and remotely configure the tags
◦ Server software
 Calculates the location using Wi-Fi signal strength readings
Ekahau System Architecture (cont.)
◦ Ekahau Site Survey (ESS)
 An easy-to-use utility for network verification and
creating positioning models during system set-up
◦ Ekahau Vision
 A web-based rules, work-flow and alerting engine
 Allows users to configure a variety of applications
location calculated by ERC
 Configures various status, event and tag rules
Ekahau System Architecture
Ekahau Tags
Using 2.4G WiFi (RSS)& IR transmission,
MAX read range 100M, precise positioning 1M
Ekahau RTLS (ERC)

probabilistic approach for interpreting the
RF signals
◦ Called Multi-Hypotheses tracking
◦ The algorithm is constantly calculating multiple
possible locations for a tracked object and gives
each possible location a score
 Based on all known factors outside: environment
characteristics, differences between mobile devices,
signal history and the movement models
 Chooses the location with the highest score
Ekahau Site Survey

A easy-to-use professional Wi-Fi
Network planning, site survey, and
management software tool
Ekahau Site Survey (cont.)

ESS enables users to quickly and easily
create, improve and troubleshoot a Wi-Fi
positioning system
Ekahau Vision
• Help users find important assets and people
Ekahau API
Tag location, presence and status
information
 Tag commissioning and management
 Two-way text messaging and commands
 Floor plan images and zones
 Open architecture and XML-based web
services

Identec
Identec System Architecture
Identec Tags
i-CARD CF 350
i-PORT M350 RTLS
i-MARK 2
i-Q350 RTLS
i-SAT 300 RTLS
Active RFID UHF & LF UHF label
Identec SensorSMART Platform
Identec Software (i-SHARE, Watcher,
CTAS)
i-SHARE
Identec Software (i-SHARE, Watcher,
CTAS)
CTAS
Identec Software (i-SHARE, Watcher,
CTAS)
Watcher
Comparisons

AeoScout
Ekahau
Identec

Zigbee
& LF
RFID
2.4G WiFi &
LF
2.4G
IR
RFID
UHF & LF
Tag 頻率

2.4GHz
0.5~6M
1~5年
2.4GHz
20cm~6M
4年
2.4GHz
NA
3~5年
920Mhz
0~3.5M
4年

1年
20sec/發射
3.75年
5min/發射
3年
15min/發射
4年
2sec/發射

80M
3M
200M
1~2M
100M
1M
500M
1M
Gsensor振動功

OK
N/A

LCD顯示功能

N/A
N/A

N/A

N/A

1200
~6000
3000
~6000
N/A
N/A
Tag大約價格
(NTD)
Comparisons (cont.)

Wi-Fi

ITRI, Ekahau, 室內：1～5m 室內外皆可使用，

Skyhook,

40m
Intel

Research

Wi-Fi
AeroScout, 1～5m
(TDOA) Hitachi
AirLocation



Background

Wireless sensor
network’s(WSN)
requirements
National Chung Hsing University System and Network Laboratory
71
Background (cont.)
Low communication speed
 Low power consumption
 Low cost

IEEE規格
802.15.4
802.15.1
802.11b

ZigBee
Bluetooth
Wi-Fi

868MHz/915MHz
/2.4GHz
2.4GHz
2.4GHz

O-QPSK,BPSK
GFSK
CCK,PBCC

30m~100m
10m
100m

20Kbps、40Kbps、
250Kbps
1Mbps
11Mbps

65536節點
7節點
32節點

Years
Days
Hours

72
Knowledge of Map Matching

Using digital map and road network to
enhance the positioning accuracy
National Chung Hsing University System and Network Laboratory
73
Knowledge of Map Matching
(cont.)
1.
2.
Vertex-based Map Matching
Segment-based Map Matching
National Chung Hsing University System and Network Laboratory
74
Knowledge of Map Matching
(cont.)
1.
2.
Vertex-based Map Matching
Segment-based Map Matching
National Chung Hsing University System and Network Laboratory
75
Knowledge of Map Matching
(cont.)

Map Matching Technique
◦ Distance of point-to-point
◦ Distance of curve-to-curve
◦ Angle of curve-to-curve
National Chung Hsing University System and Network Laboratory
76
Knowledge of Map Matching
(cont.)

Distance of point-to-point
National Chung Hsing University System and Network Laboratory
77
Knowledge of Map Matching
(cont.)

Distance of curve-to-curve

If 1 + 2 < 1 + 2 , 2 will
National Chung Hsing University System and Network Laboratory
78
Knowledge of Map Matching
(cont.)

Angle of curve-to-curve

If  >  , we chose road 1
National Chung Hsing University System and Network Laboratory
79
System Implementation
User (End Device)
 Router
 Coordinator
 Server (laptop)

National Chung Hsing University System and Network Laboratory
80
System Implementation (cont.)

Hardware: CC2530ZDK
National Chung Hsing University System and Network Laboratory
81
System Implementation (cont.)

Software:
◦ IAR Embedded Workbench IDE
 For ZigBee network
◦ Visual C#2010
 For positioning algorithm
National Chung Hsing University System and Network Laboratory
82
System Implementation(cont.)
83
System Implementation (cont.)

235
230
225
220

215

210
205
200
195
0
100
200
300
400
500
600
700
84
System Implementation (cont.)

Positioning Algorithm
◦ Two-intersected-circles algorithm
◦ Indoor-map-matching algorithm
National Chung Hsing University System and Network Laboratory
85
System Implementation (cont.)

Two-intersected-circles algorithm
National Chung Hsing University System and Network Laboratory
86
System Implementation (cont.)
National Chung Hsing University System and Network Laboratory
87
System Implementation (cont.)
National Chung Hsing University System and Network Laboratory
88
Flow Chart
Start

89
System Implementation (cont.)

Indoor-map-matching algorithm
◦ Path database
◦ Matching algorithm
National Chung Hsing University System and Network Laboratory
90
Path Database

Use vertices and segments to denote
paths
National Chung Hsing University System and Network Laboratory
91
Path Database (cont.)
Vertex
Segment

X座標

Y座標

National Chung Hsing University System and Network Laboratory
a
b
c
92
Matching Algorithm
1.
2.
If there is no reference node, use
distance of point-to-point
If there is a reference node, use
distance of curve-to-curve
1
1
2
2
1 + 2 ＜(1 + 2 )
National Chung Hsing University System and Network Laboratory
93
Matching Algorithm (cont.)
1.
2.
3.
4.
Planning paths and set up the database in
the server
If no reference node, find the closest
vertex to the unknown node
Find all the segments that are connected
to the closest vertex, and determine the
closest segment
If there is a reference node, find the
closest segment like step1~3
National Chung Hsing University System and Network Laboratory
94
Matching Algorithm(cont.)
5.
6.
7.
If the segment is connected with
previous segment, this segment is the
right segment
If it is not connected, calculate the
distances between the two nodes and
the two segments
Compare the sum of distances. The
smaller one is the right segment
National Chung Hsing University System and Network Laboratory
95
Start
Flow Chart

vertex

segment

segment之距離

96
Experiment and Result
97
Experiment and Result (cont.)

Database 1
National Chung Hsing University System and Network Laboratory
98
Experiment and Result (cont.)
0
2
4
6
8
10
12
0
1
2

3

4
5
6
National Chung Hsing University System and Network Laboratory
99
Experiment and Result (cont.)

0
1
2
3
4
5
6
7
8
9
10
0
0.5
1
1.5
2

2.5
3
3.5
4
National Chung Hsing University System and Network Laboratory
100
Experiment and Result (cont.)

Database 2
National Chung Hsing University System and Network Laboratory
101
Experiment and Result (cont.)
0
2
4
6
8
10
12
0
0.5
1
1.5
2

2.5
3
3.5
4
4.5
National Chung Hsing University System and Network Laboratory
102
Experiment and Result (cont.)

0
1
2
3
4
5
6
7
8
9
10
0
0.5
1
1.5
2

2.5
3
3.5
4
National Chung Hsing University System and Network Laboratory
103
Experiment and Result (cont.)

Database 3
National Chung Hsing University System and Network Laboratory
104
Experiment and Result (cont.)
0
1
2
3
4
5
6
7
0
0.5
1
1.5
2

2.5

3
3.5
4
4.5
5
National Chung Hsing University System and Network Laboratory
105
Experiment and Result (cont.)

0
1
2
3
4
5
6
7
0
0.5
1

1.5
2
2.5
National Chung Hsing University System and Network Laboratory
106
Indoor Positioning Using Femtocell
Publication Year: 2011
IEEE CONFERENCE PUBLICATIONS
Femtocell Overview

Femtocell coverage is smaller
◦ Mainly used to compensate for the region the
other base stations can not cover
◦ Enhances the data transfer rate
◦ Typically used for residential or small business
environment.
Femtocell Based Positioning
Methods

To locate a mobile device in a network of
femtocells, we need to determine its
position relative to at least three
femtocells to achieve successful
triangulation
◦ Femtocells’ locations are known
Femtocell Based Positioning
Methods (cont.)

The distance between the mobile and a
femtocell is estimated by:
◦ Calculating the signal propagation loss
(pathloss) between them
◦ Or the time taken by the signal to propagate
from one point to the other.
Femtocell Based Positioning
Methods (cont.)

Signal Strength Triangulation based
methods:
• Generate a database of pathloss at all
locations via ray-tracing simulation of detailed
building interiors
• Using WinProp software tool
• Being matched against the database to
estimate the position
Femtocell Based Positioning
Methods (cont.)

Time based methods :
◦ The signal propagation delay between
femtocells and mobile
◦ Though useful in calculating distance, this is
ineffective for indoor positioning
Strength

The position of a mobile can be estimated
by measuring the strength of the received
downlink signals at the mobile from a
group of femtocells
◦ The pathloss to each visible femtocell can
then be calculated using the femtocell
transmit powers
Strength (cont.)

The serving femtocell requests the mobile
to send a Measurement Report Message
(MRM)
◦ Containing Ecp/Io and Ecp information
 Ecp is the received signal strength of the serving
femtocell pilot
 Io is the total received energy on the serving
femtocell frequency (as measured by the mobile)
Strength (cont.)

The fingerprint is matched against the
database
◦ Containing pathloss values from all points in
the network’s coverage region to all
femtocells

The methods used to create time
orthogonalization of signals

To avoid persistent interferences
Strength (cont.)

Inter-frequency Beacon Transmission
◦ Each femtocell may transmit its beacon pilot
on different frequency channels
 In a time division multiplexed manner (TDMA)
◦ As measurements are made by the mobiles on
the channels at multiple instances, the mobile
will now be able to detect signals from
different femtocells as all other interferers
are removed
Strength (cont.)

Co-ordinated Silence Techniques
◦ Techniques also help create time
orthogonalization of signals to avoid the
problem of strong interference from the
serving femtocell
 Such as HDP and OTDOA-IPDL

Femtocells need to also support
alternative solutions for mobiles that are
not equipped with these features
Strength

The position of a mobile can also be
estimated by measuring the strength of
◦ Received at a group of femtocells
 Since the transmit power of the mobile is unknown
and dynamic, the pathloss cannot be estimated from
this measurement
 The difference of the measured strength at two
femtocells is equal to the pathloss difference from
the mobile’s location to these femtocells
Strength (cont.)

The difference in the pathloss values can
be used as a fingerprint.
◦ Those femtocells that can sense the mobile
send the measured Ecp/Nt and Nt values to
the positioning server
◦ The server calculates the pathloss difference
to a number of pairs of femtocells and
matches this against the database to predict
the mobile’s position
Simulation Model
Simulation Model (cont.)
Beamforming basics

Beamforming uses multiple antennas
◦ Control the direction of a wavefront by
appropriately weighting the magnitude and
phase of ndividual antenna signals (transmit
beamforming).
◦ This makes it possible to provide better
coverage to specific areas

Because every single antenna in the array makes a
contribution to the steered signal, an array gain
(also called beamforming gain) is achieved
Beamforming basics (cont.)

Beamforming makes it possible to
determine the direction that the
wavefront will arrive
◦ Direction of Arrival, or DoA

technique of continually applying
◦ This requires rapid signal processing and
powerful algorithms.
Beamforming basics (cont.)
• Antenna array with a distance d between the
individual antennas.
• The additional path that a wavefront must
traverse between two antennas is d * sin Ѳ.
Beamforming basics (cont.)

The antenna diagram is affected by the distance
d between the antennas.
OTDOA

OTDOA：Observed Time Difference of
Arrival
4G LTE-A Localization
UE 利用陣列天線估測DOA

Femtocell BS

UE
Femtocell BS1
Marcocell
BS
 M , M

Steering 方式增強接收訊號
 2 ,2
Femtocell BS2
 1 ,1
 3 , 3
Femtocell BS3
UE

TX beamforming 技術將訊號

Femtocell BS
UE
OTDOA+DOA方式取得位置
127



◦ DOA estimation in UE
◦ Beamforming technique

 當使用者位於室內或GPS無LOS訊號時，

 改善Positioning system QoS

128
UE之DOA估測技術

signals/pilots are arranged across time and
frequency domain (OFDMA modulation)

Collect those pilots to form a virtual array
◦ 解決實體陣列維度不足問題
◦ 可同時估測多BS方向
129
In-Location Alliance

Founded by 22 companies across
industries
◦ Nokia, Samsung Electronics, Sony Mobile
CSR, etc.
◦ To drive innovation and market adoption of
high accuracy indoor positioning and related
◦ The primary solutions will be based on
enhanced Bluetooth® 4.0 low-energy
technology and Wi-Fi (802.11.ac) standards
IEEE 802.11ac spec.
802.11ac
802.11n
Band
5GHz Band
2.4GHz/5GHz(opt)
Channel Bandwidth
20,40,80,160 MHz
20,40MHz
Max Data rate
6933Mbps
~600Mbps
Spatial Streams
Up to 8 spatial streams 4 spatial streams
Modulation
256-QAM
64-QAM
MIMO
Multi-User MIMO
Single-User MIMO
Backward
compatibility
802.11n(on 5GHz)
802.11a
802.11 b/g
Band
Operating on 5GHz band
Less interference than on 2.4GHz
• More non-overlapping channel
avaliable. (25 to 3 on 2.4GHz) 7
• Mandatory support 20/40/80MHz,
160MHz optional.
•
•
Bandwidth
Table of Data rate:
Higher Order Modulation
• Increase 33% PHY rate relied on 256-QAM
• QAM is Quadrature Amplitude Modulation.
• 6 bits coded information to 8bits coded
information.
Improved MIMO
• Up to 8 spatial streams
• 4 spatial streams with 11n
• Multi-Users MIMO
• Single-Users MIMO
• Beneficial for handset or tablet
• Multiple antennas are not necessary
Dynamic Bandwidth Management
• Improved handshake mechanism.
• RTS/CTS
• Interference detection threshold
improved
• -62dBm down to -72dBm
Single Closed Loop-Method Transmit
Beamforming
• Beamforming focuses the APs transmit
energy of spatial stream toward
Clients
Special Sounding Signal
AP
STAs
Report their Beamformaing matrices
• Limitation of TxBeamforming on 5GHz
band
Backward Compatibility
• Required to be fully compatible with
802.11n(Operating on 5GHz)and
802.11a
• 802.11b/g not support
NOKIA – Bluetooth 4.0

The High Accuracy Indoor Positioning
(HAIP) technology
◦ Nokia is looking to employ it based on
Bluetooth 4.0
◦ Even in its current form it will have accuracy
of one meter
 That’s certainly good enough for general positioning
inside
 It gets much more interesting when it can get down
to 20cm with modification
 Industry application for stock control
NOKIA – Bluetooth 4.0 (cont.)

Using a single antenna
and fixed mobile height,
mobile can resolve its
2D location
NOKIA – Bluetooth 4.0 (cont.)

Using multiple
positioning beacons,
mobile can resolve its
3D location or
increasing the position
reliability and accuracy
Conclusions


◦ 無直射路徑問題(NLOS propagation)
 手機有GSM900、WCDMA、HSDPA等等的不同

◦ 多重路徑干擾(Multipath Interference)
◦ 多使用者環境的影響
◦ 手機電源消耗問題(power issue)
142