# A Three-Dimensional Wireless Indoor Localization System

Authors: Ping Yi; Minjie Yu; Ziqiao Zhou; Wei Xu; Qingquan Zhang; Ting Zhu
Journal: Journal of Electrical and Computer Engineering
 (2014)

---

## Abstract

Indoor localization, an emerging technology in location based service (LBS), is now playing a more and more important role both in commercial and in civilian industry. Global position system (GPS) is the most popular solution in outdoor localization field, and the accuracy is around 10 meter error in positioning. However, with complex obstacles in buildings, problems rise in the “last mile” of localization field, which encourage a momentum of indoor localization. The traditional indoor localization system is either range-based or fingerprinting-based, which requires a lot of time and efforts to do the predeployment. In this paper, we present a 3-dimensional on-demand indoor localization system (3D-ODIL), which can be fingerprint-free and deployed rapidly in a multistorey building. The 3D-ODIL consists of two phases, vertical localization and horizontal localization. On vertical direction, we propose multistorey differential (MSD) algorithm and implement it to fulfill the vertical localization, which can greatly reduce the number of anchors deployed. We use enhanced field division (EFD) algorithm to conduct the horizontal localization. EFD algorithm is a range-free algorithm, the main idea of which is to dynamically divide the field within different signature area and position the target. The accuracy and performance have been validated through our extensive analysis and systematic experiments.


---

## Body

## 1. Introduction

The next evolutionary in smart environments develops fast in building, utilities, industrial, home, shipboard, and transportation system automation. One of the crucial technologies and scientific researches of smart environments is based on location-aware systems. Location-aware systems have improved the quality of life and provide people with convenience in working, outing, shopping, dining, and many other activities.In recent years, with the open-sourced Android operating system and the continuous cost-reduction in hardware, smart phone is getting more and more popular. Android/IOS based smart phones can be seen everywhere, and we can easily get the location of our friends with the widely used location-aware systems, like global position system (GPS). GPS is the most popular solution in outdoor localization field, and the accuracy is around 10 meter error in positioning. It provides good user-experience in outdoor scenarios. However, when we try to use GPS in indoor environment, like in an office or at home, we can barely receive the signals of satellites, and the error of accuracy will be out of tolerance. The root cause is that with complex obstacles in buildings the satellite signals cannot transmit the walls and floors.Thus, we need an indoor localization system to do the “last mile” localization. The “last mile” or “last kilometer” is a phrase used by the telecommunications, cable television, and Internet industries to refer to the final leg of the telecommunications networks delivering communications connectivity to retail customers. In localization field, we also have the “last mile” problems, and we need the indoor localization systems that can make up the weakness of GPS system.Over the past decade, indoor-localization-based technology and algorithms are flourishing, and almost all indoor localization systems are based on signal analysis of wireless sensor networks (WSNs). Generally speaking, indoor location mechanisms can be separated into two parts: range-based method and range-free method. Range-based methods are the mainstream ways to do indoor location in the early years, such as TOA [1], TDOA [2], AOA [3], and RSSI [4]. Since the range-based method requires expensive hardware and precise statistics, the range-free algorithms develop fast in recent years, such as RSD, EZ, BT, and UnLoc. However, some limitations restrain these algorithms from generalized indoor location, for fingerprinting technology needs lots of precollection of data.Thus, we propose the idea of 3-dimensional on-demand indoor localization system (3D-ODIL), which can be fingerprint-free and deployed effectively in a multistorey building. The contributions are as follows.In this paper, we propose the idea of 3-dimensional on-demand indoor localization system (3D-ODIL), which can be fingerprint-free and deployed rapidly in a multistorey building. The 3D-DDIL consists of two parts, horizontal localization and vertical localization.On horizontal direction, we use enhanced field division (EFD) algorithm to conduct the horizontal localization. EFD algorithm is a range-free algorithm, which implements the idea that the whole map is dynamically divided into fields that with signature sequences mark and locate the target device. The key idea of EFD provides a new developing direction for indoor localization. Traditional ways focus on the actual value of the received signal strength (RSS), but the value of which is fluctuant and greatly impacted due to the complex environments with obstacles. The EFD algorithm lays emphasis on the possible position on the map and utilizes the high-low relationship between the RSSs from each anchor to decide which areas the receiver should lies in. This allows for the minimization of the RF fading effect. What is more, taking advantage of field division with optimal anchor placements, we avoid the issues of intensive fingerprint sampling. Fingerprinting technology is a highly precise way to do indoor localization, but the weakness is also obvious: it need more time to find optimal anchor placements.On vertical direction, we implement multistorey differential (MSD) algorithm to fulfill the vertical localization, which can greatly reduce the number of anchors deployed. Vertical localization, or called multistorey positioning, is an underestimated aspect to be discussed in indoor localization field. With anchors predeployed in the building in typical system, we can equip anchors with the same allocation plan on each floor, and it is simple to determine the floor: the floor of the anchor which has the strongest signal. However, in on-demand situation, we need to do rapid deployment, as few anchors as possible. We need to divide more floors with limited anchors. The MSD algorithm provides an efficient way to do vertical localization with few anchors.Finally, we build a localization system platform, as shown in Figure7, from off-the-shelf commercialized products. The system includes three major components: the mobile anchor platform, a mobile localization unit, and a back-end server. The mobile anchor platform can be a portable LTE/GSM mini-radio station or a traditional Wi-Fi router, which act as a radio signal generator. The mobile localization unit is an Android-based smart phone, which is a commercial device and we can use it to receive signals and communicate with the server. The back-end server plays the role of data storage and computing unit.The rest of the paper is organized as follows. Multistorey differential algorithm is presented in Section2. Enhanced field division (EFD) algorithm is discussed in Section 3. Analysis data of MSD algorithm is illustrated in Section 4. The performance of the prototype system in practical environments is evaluated in Section 5. Section 6 briefly discusses related work, and Section 7 concludes the paper.


## 2. Multistorey Differential Algorithm

Three-dimensional localization system should provide both horizontal and vertical localization functions as a comprehensive system. In contrast to horizontal location, vertical localization has quite different model. The insertion loss of the reinforced wall (about 20–40 dB) is larger comparing to the brick wall (about 10 dB to 20 dB) [5]. Since the separation of reinforced concrete walls between all floors, it is inaccurate to use typical trilateral RSSI localization system to do vertical localization. Wireless indoor localization without site survey (WILL) [6] provides a fingerprinting system to do 3-dimensional localization. Unfortunately, there is no mature and general vertical localization which can be rapidly deployed on-demand. Thus, we designed multistorey differential (MSD) algorithm.


### 2.1. Fundamental Theory of Vertical Localization

Figure1 shows the basic building model we use. Assume that the height of the building is H
(
m
), and the height of each floor is h
(
m
). We set up two anchors on the first floor (S
1) and top floor (S
2), which are at the same horizontal position. Since we focus on the vertical localization, we can simplify the 3-dimensional system of coordinate to 2-dimensional system of coordinate, of which axis Z is the vector from S
1 to S
2 and axis X is the distance between our test point and axis Z. The position of the test point (P
1) is (
x
,
z
).Figure 1
Basic model of MSD.Definition 1 (FSPL).
FSPL is the abbreviation of free-space path loss, which is the difference between transmitter power and received signal power, and also takes the gain of two antennas into consideration:(1)
FSPL
=
P
T
+
G
T
+
G
R
-
P
R
,
where P
R is the received signal power, P
T is the base station (BS) transmitter power, G
T is the transmitting antenna gain, and G
R is the receiving antenna gain.Definition 2 (MSPL).
MSPL is the abbreviation of multistorey path loss, which is the extension of FSPL with the insertion loss of reinforced concrete wall:(2)
MSPL
=
FSPL
+
N
*
L
I
,
where N is the number of walls inserted in the path and L
I is the insertion loss of reinforced concrete wall (about 20–40 dm) [5].Theorem 3.
Consider(3)
M
S
P
L
=
20
log
⁡
d
+
20
log
⁡
f
+
20
log
⁡
[
4
π
c
]
+
N
*
L
I
.Proof of Theorem3.
Corresponding values of path losses were computed from the measured received signal power using the expression [7]
(4)
L
p
=
(
EIRP
-
G
R
)
-
P
R
,
where EIRP is the effective isotropic power of the BS transmitting antenna. For the free-space model, the expression for the received signal power, with directional base station antenna, is [8, 9]
(5)
P
R
=
P
T
*
G
T
*
G
R
*
(
λ
4
π
d
)
2
,
where λ is the wavelength and d is the distance between the BS antenna and mobile station (MS) receiver antenna. If P
R and P
T are expressed in dBm and the gains are in dB, (2) becomes [10]
(6)
P
R
=
P
T
+
G
T
+
G
R
+
20
log
⁡
[
λ
4
π
d
]
.
Consider the FSPL, which is defined in (1). When substituting λ
=
c
/
f, (3) and (4) become
(7)
FSPL
=
20
log
⁡
[
4
π
d
λ
]
=
20
log
⁡
d
+
20
log
⁡
f
+
20
log
⁡
[
4
π
c
]
.
Also, we can get the MSPL equation(8)
MSPL
=
20
log
⁡
d
+
20
log
⁡
f
+
20
log
⁡
[
4
π
c
]
+
N
*
L
I
.For typical radio applications, it is common to findf measured in units of MHz and d in meter. Assuming that we use Wi-Fi routers as the anchors (f
=
2400 MHz), the MSPL equation becomes
(9)
MSPL
=
20
log
⁡
[
4
π
d
λ
]
+
N
*
L
I
=
20
log
⁡
d
+
N
*
L
I
+
k
MSPL
,
where k
MSPL is a constant value, and we can calculate the exact value as 40.05 in our assumption.As we can see,N equals the floor integer of z
/
h, which is [
z
/
h
]. At test point, we can receive the signals from both S
1 and S
2. The MSPL for S
1 is
(10)
MSP
L
S
1
=
20
log
⁡
x
2
+
z
2
+
k
MSPL
+
[
z
h
]
*
L
I
.And theMSPL for S
2 is
(11)
MSP
L
S
2
=
20
log
⁡
x
2
+
(
H
-
z
)
2
+
k
MSPL
+
[
(
H
-
z
)
h
]
*
L
I
.Considering the variant ofMSP
L
S
1 and MSP
L
S
1,
(12)
Δ
MSPL
=
MSP
L
S
2
-
MSP
L
S
1
=
20
log
⁡
x
2
+
(
H
-
z
)
2
x
2
+
z
2
+
[
(
H
-
2
z
)
h
]
*
L
I
.In our scenario, our target is to conduct localization in multistorey building, and we should combine our math equation with the given conditions. Thus, we focus on the exact floor rather than the precise height.Theorem 4.
When we are on different floors of a multistorey building, we can distinguish theΔ
M
S
P
L value regardless of the horizontal point we stay at.Proof of Theorem4.
Since we are aiming to distinguish the floor, we assume that the vertical coordinates are evenly spaced, and the absolute height is(
N
floor
-
1
)
*
h, where N
floor is the floor number. To prove our theorem, we receive the Δ
MSPL at two different points, which are noted as P
1
(
x
1
,
z
1
) and P
2
(
x
2
,
z
2
):
(13)
Δ
MSP
L
P
1
-
Δ
MSP
L
P
2
=
20
log
⁡
x
1
2
+
(
H
-
z
1
)
2
x
1
2
+
z
1
2
+
[
(
H
-
2
z
1
)
h
]
*
L
I
-
20
log
⁡
x
2
2
+
(
H
-
z
2
)
2
x
2
2
+
z
2
2
-
[
(
H
-
2
z
2
)
h
]
*
L
I
.
Consider the relationship betweenz
1 and z
2. Obviously, if we can distinguish different points of the floor n and floor n
+
1, we can easily distinguish each floor of the building. Thus, we need to make research on the extreme condition that z
2
=
z
1
+
h, and we generalize z
1 as y. Thus, (13) becomes
(14)
Δ
MSP
L
P
1
-
Δ
MSP
L
P
2
=
20
log
⁡
x
1
2
+
(
H
-
z
1
)
2
x
1
2
+
z
1
2
+
[
(
H
-
2
z
1
)
h
]
*
L
I
-
20
log
⁡
x
2
2
+
(
H
-
z
2
)
2
x
2
2
+
z
2
2
-
[
(
H
-
2
z
2
)
h
]
*
L
I
=
20
log
⁡
x
1
2
+
(
H
-
z
1
)
2
x
1
2
+
z
1
2
*
x
2
2
+
z
2
2
x
2
2
+
(
H
-
z
2
)
2
-
2
*
L
I
=
10
log
⁡
x
1
2
+
(
H
-
z
1
)
2
x
1
2
+
z
1
2
*
x
2
2
+
z
2
2
x
2
2
+
(
H
-
z
2
)
2
-
2
*
L
I
.
If we want to use this theorem to localize the floor, we need to decrease the impact of x. We separate it into two parts:
(
1
)  x
1
=
x
2.
We nameΔ
DMSPL from Δ
MSP
L
P
1
-
Δ
MSP
L
P
2. Equation (14) becomes
(15)
Δ
DMSPL
=
Δ
MSP
L
P
1
-
Δ
MSP
L
P
2
=
10
log
⁡
x
2
+
(
H
-
z
1
)
2
x
2
+
z
1
2
*
x
2
+
z
2
2
x
2
+
(
H
-
z
2
)
2
-
2
*
L
I
.
Takex as variable; we can get the derivative of the function:
(16)
d
Δ
DMSPL
d
x
=
20
x
ln
⁡
⁡
10
*
[
(
1
x
2
+
(
H
-
z
1
)
2
-
1
x
2
+
(
H
-
z
2
)
2
)
iiiiiiiiiiiiiiiiiii
(
1
x
2
+
(
H
-
z
1
)
2
-
1
x
2
+
(
H
-
z
2
)
2
)
+
(
1
x
2
+
z
2
2
-
1
x
2
+
z
1
2
)
]
.
Whenx
>
0, the derivative d
Δ
DMSPL
/
d
x
<
0, which means that Δ
DMSPL is a monotonic decreasing function with variable x when x
>
0. When x
→
0, (15) becomes
(17)
Δ
DMSPL
=
20
log
⁡
[
H
*
h
(
H
-
z
-
h
)
*
z
+
1
]
-
2
*
L
I
.
Whenx
→
∞, (15) becomes
(18)
Δ
DMSPL
=
-
2
*
L
I
.
(
2
)  x
1
≠
x
2.
We assume thatx
1
<
x
2. If we need to evaluate the impact of variables x
1,  x
2, we can analyze the extreme condition: x
1
→
0, x
2
→
∞. Equation (14) becomes
(19)
Δ
DMSPL
=
10
log
⁡
(
H
-
z
1
)
2
z
1
2
*
1
-
2
*
L
I
=
20
log
⁡
(
H
z
-
1
)
-
2
*
L
I
.
Equations (17), (18), and (19) demonstrate the different condition of Δ
DMSPL, the first item of them has minor impact (about 0–10 dB), and the second item has a major impact (about 40–50 dB).
With the deduction above, we can useΔ
DMSPL as the reference value to distinguish different floors.


### 2.2. Modeling with Multiple Anchors on Each Floor

We can separately do the vertical localization with the value ofΔ
MSPL theoretically, but, in real conditions, with the complex indoor environment and the fluctuation feature of wireless signal, we need to design a stable and multianchor model to enhance the accuracy of vertical localization.The fundamental theory of vertical localization analyzes the condition of 1-pair-anchor deployment, and we want to generalize it to multianchor model.Consider the actual deployment scenario. We need to deploy wireless anchors in the whole building. For floori, we put m
i anchors on it.As we name our system on-demand, we should minimize the number of anchors deployed with less impact on the accuracy of the whole system. With the fundamental theory of vertical localization, we can distribute the anchors on some specific floors, which have an interval ofn floors:
(20)
m
i
=
{

m
i
,
if
i
%
n
=
1
,
0
,
otherwise
.
The m
i of each floor is decided by the anchors needed for horizontal localization system.If a building has more storeys thann
+
1, we can degrade this building to several subbuildings with n
+
1 storeys and filter the receiving wireless signal only from floor t (the first floor of subbuilding) and floor (
t
+
n
).Now we have a(
n
+
1
) storey subbuilding model, and we need to decide the interval n and figure out the m-anchor algorithm.The intervaln is decided by the value that how many anchors on (
n
+
1
)th floor can be detected on the ith floor. We note the value as r
i. Obviously, r
i must be a nonnegative number, and r
1 is the minimum of r
i. We name R the threshold of the subbuilding model, which equals r
1.To do the vertical localization, we need to guarantee thatR
≥
1. Referring to (3) and (8) and substituting N
=
n
-
1:
(21)
P
R
=
P
T
+
G
T
+
G
R
-
20
log
⁡
d
-
k
MSPL
-
(
n
-
1
)
*
L
I
.
Consider the normal usage conditions: P
T
=
20 dBm, G
T
=
17 dBm, and G
R
=
2 dBm. The smart phone can detect the wireless signals that P
R is more than −99 dBm. Thus,
(22)
(
n
-
1
)
*
L
I
<
97.95
-
20
log
⁡
d
.
If d
max
⁡
=
30 m and L
I
=
20 dB, we can get the n
max
⁡
=
4.When we receiver
i wireless signals on the ith floor, we need to take advantage of all received signals to enhance the accuracy and the success rate of vertical localization.We assume that the value ofΔ
MSPL on each floor is in a narrow interval, for we can separate the value from different floors. Let us define the weight assigned to different anchors as W
=
{
w
1
,
w
2
,
…
w
i
,
…
,
w
k
}; is the weight for anchor {
i
}. As such, the Δ
MSPL value of multianchor mode will be determined as
(23)
Δ
MSP
L
WAVG
=
∑
i
‍
w
i
*
Δ
MSP
L
i
.Now we should consider the determination ofW:
(24)
U
(
ρ
^
,
σ
ρ
^
2
)
=
ρ
^
-
γ
σ
ρ
^
2
,
where ρ
^ is defined as the average of the signal, σ
ρ
^
2 is the standard deviation of ρ
^, and γ defines a relative interference coefficient that describes the loss in signal strength due to environmental interference. The r will be higher for a signal unfriendly environment such as a concrete wall building than for an outdoor environment known for less interface. Therefore, to improve the accuracy, a signature must be selected. Let us define the weight assigned to different anchors as W
=
{
w
1
,
w
2
,
…
,
w
n
}; w
i is the weight for ancho
r
i. As such, the optimization problem will be to determine W so that the total utility is maximized; that is,
(25)
max
⁡
W
∑
i
‍
U
(
ρ
^
i
,
σ
ρ
^
i
2
)
,
s
.
t
.
W
′
i
=
1
,
w
i
>
0
.Lemma 5.
The optimal solution ofW will be
(26)
w
=
1
γ
Q
-
1
(
ρ
+
λ
1
)
.Proof of (26).
Under our definition, the total utility can be written as(27)
∑
i
=
1
n
‍
w
i
U
(
ρ
^
1
,
σ
ρ
^
i
2
)
=
∑
i
=
1
n
‍
w
i
ρ
^
i
-
r
(
∑
i
=
1
n
‍
w
i
2
σ
ρ
^
i
2
+
2
∑
i
=
1
n
‍
∑
j
≠
i
n
‍
w
i
w
j
Cov
(
σ
ρ
^
i
,
σ
ρ
^
j
)
)
=
W
ρ
-
r
W
′
Q
W
,
in which,
(28)
Q
=
(
σ
ρ
^
1
2
σ
ρ
^
1
,
ρ
^
2
⋯
σ
ρ
^
1
,
ρ
^
n
σ
ρ
^
2
,
ρ
^
1
σ
ρ
^
2
2
⋯
σ
ρ
^
1
,
ρ
^
n
⋮
⋮
⋱
⋮
σ
ρ
^
n
,
ρ
^
1
σ
ρ
^
n
,
ρ
^
2
⋯
σ
ρ
^
n
2
)
,
σ
ρ
^
i
,
ρ
^
j is the degradation correlation between anchors i and j, and n is the number of anchors. The numerical solution of W can be solved by Lagrangian derivation. Let us form
(29)
C
=
W
′
ρ
-
γ
W
′
Q
W
-
λ
1
(
W
′
1
-
1
)
,
where λ
1 is a Lagrange multiplier. Then, taking derivatives of the Lagrangian with respect to vector W
′, we get
(30)
δ
L
δ
W
′
:
ρ
-
γ
Q
W
-
λ
1
=
0
.
As a result, this proves (26).The optimalW
=
{
w
1
,
w
2
,
…
,
w
n
} can then be applied to our measurement of RS
S
t as WRS
S
t to derive the optimal field signature s
*
(
t
).


## 2.1. Fundamental Theory of Vertical Localization

Figure1 shows the basic building model we use. Assume that the height of the building is H
(
m
), and the height of each floor is h
(
m
). We set up two anchors on the first floor (S
1) and top floor (S
2), which are at the same horizontal position. Since we focus on the vertical localization, we can simplify the 3-dimensional system of coordinate to 2-dimensional system of coordinate, of which axis Z is the vector from S
1 to S
2 and axis X is the distance between our test point and axis Z. The position of the test point (P
1) is (
x
,
z
).Figure 1
Basic model of MSD.Definition 1 (FSPL).
FSPL is the abbreviation of free-space path loss, which is the difference between transmitter power and received signal power, and also takes the gain of two antennas into consideration:(1)
FSPL
=
P
T
+
G
T
+
G
R
-
P
R
,
where P
R is the received signal power, P
T is the base station (BS) transmitter power, G
T is the transmitting antenna gain, and G
R is the receiving antenna gain.Definition 2 (MSPL).
MSPL is the abbreviation of multistorey path loss, which is the extension of FSPL with the insertion loss of reinforced concrete wall:(2)
MSPL
=
FSPL
+
N
*
L
I
,
where N is the number of walls inserted in the path and L
I is the insertion loss of reinforced concrete wall (about 20–40 dm) [5].Theorem 3.
Consider(3)
M
S
P
L
=
20
log
⁡
d
+
20
log
⁡
f
+
20
log
⁡
[
4
π
c
]
+
N
*
L
I
.Proof of Theorem3.
Corresponding values of path losses were computed from the measured received signal power using the expression [7]
(4)
L
p
=
(
EIRP
-
G
R
)
-
P
R
,
where EIRP is the effective isotropic power of the BS transmitting antenna. For the free-space model, the expression for the received signal power, with directional base station antenna, is [8, 9]
(5)
P
R
=
P
T
*
G
T
*
G
R
*
(
λ
4
π
d
)
2
,
where λ is the wavelength and d is the distance between the BS antenna and mobile station (MS) receiver antenna. If P
R and P
T are expressed in dBm and the gains are in dB, (2) becomes [10]
(6)
P
R
=
P
T
+
G
T
+
G
R
+
20
log
⁡
[
λ
4
π
d
]
.
Consider the FSPL, which is defined in (1). When substituting λ
=
c
/
f, (3) and (4) become
(7)
FSPL
=
20
log
⁡
[
4
π
d
λ
]
=
20
log
⁡
d
+
20
log
⁡
f
+
20
log
⁡
[
4
π
c
]
.
Also, we can get the MSPL equation(8)
MSPL
=
20
log
⁡
d
+
20
log
⁡
f
+
20
log
⁡
[
4
π
c
]
+
N
*
L
I
.For typical radio applications, it is common to findf measured in units of MHz and d in meter. Assuming that we use Wi-Fi routers as the anchors (f
=
2400 MHz), the MSPL equation becomes
(9)
MSPL
=
20
log
⁡
[
4
π
d
λ
]
+
N
*
L
I
=
20
log
⁡
d
+
N
*
L
I
+
k
MSPL
,
where k
MSPL is a constant value, and we can calculate the exact value as 40.05 in our assumption.As we can see,N equals the floor integer of z
/
h, which is [
z
/
h
]. At test point, we can receive the signals from both S
1 and S
2. The MSPL for S
1 is
(10)
MSP
L
S
1
=
20
log
⁡
x
2
+
z
2
+
k
MSPL
+
[
z
h
]
*
L
I
.And theMSPL for S
2 is
(11)
MSP
L
S
2
=
20
log
⁡
x
2
+
(
H
-
z
)
2
+
k
MSPL
+
[
(
H
-
z
)
h
]
*
L
I
.Considering the variant ofMSP
L
S
1 and MSP
L
S
1,
(12)
Δ
MSPL
=
MSP
L
S
2
-
MSP
L
S
1
=
20
log
⁡
x
2
+
(
H
-
z
)
2
x
2
+
z
2
+
[
(
H
-
2
z
)
h
]
*
L
I
.In our scenario, our target is to conduct localization in multistorey building, and we should combine our math equation with the given conditions. Thus, we focus on the exact floor rather than the precise height.Theorem 4.
When we are on different floors of a multistorey building, we can distinguish theΔ
M
S
P
L value regardless of the horizontal point we stay at.Proof of Theorem4.
Since we are aiming to distinguish the floor, we assume that the vertical coordinates are evenly spaced, and the absolute height is(
N
floor
-
1
)
*
h, where N
floor is the floor number. To prove our theorem, we receive the Δ
MSPL at two different points, which are noted as P
1
(
x
1
,
z
1
) and P
2
(
x
2
,
z
2
):
(13)
Δ
MSP
L
P
1
-
Δ
MSP
L
P
2
=
20
log
⁡
x
1
2
+
(
H
-
z
1
)
2
x
1
2
+
z
1
2
+
[
(
H
-
2
z
1
)
h
]
*
L
I
-
20
log
⁡
x
2
2
+
(
H
-
z
2
)
2
x
2
2
+
z
2
2
-
[
(
H
-
2
z
2
)
h
]
*
L
I
.
Consider the relationship betweenz
1 and z
2. Obviously, if we can distinguish different points of the floor n and floor n
+
1, we can easily distinguish each floor of the building. Thus, we need to make research on the extreme condition that z
2
=
z
1
+
h, and we generalize z
1 as y. Thus, (13) becomes
(14)
Δ
MSP
L
P
1
-
Δ
MSP
L
P
2
=
20
log
⁡
x
1
2
+
(
H
-
z
1
)
2
x
1
2
+
z
1
2
+
[
(
H
-
2
z
1
)
h
]
*
L
I
-
20
log
⁡
x
2
2
+
(
H
-
z
2
)
2
x
2
2
+
z
2
2
-
[
(
H
-
2
z
2
)
h
]
*
L
I
=
20
log
⁡
x
1
2
+
(
H
-
z
1
)
2
x
1
2
+
z
1
2
*
x
2
2
+
z
2
2
x
2
2
+
(
H
-
z
2
)
2
-
2
*
L
I
=
10
log
⁡
x
1
2
+
(
H
-
z
1
)
2
x
1
2
+
z
1
2
*
x
2
2
+
z
2
2
x
2
2
+
(
H
-
z
2
)
2
-
2
*
L
I
.
If we want to use this theorem to localize the floor, we need to decrease the impact of x. We separate it into two parts:
(
1
)  x
1
=
x
2.
We nameΔ
DMSPL from Δ
MSP
L
P
1
-
Δ
MSP
L
P
2. Equation (14) becomes
(15)
Δ
DMSPL
=
Δ
MSP
L
P
1
-
Δ
MSP
L
P
2
=
10
log
⁡
x
2
+
(
H
-
z
1
)
2
x
2
+
z
1
2
*
x
2
+
z
2
2
x
2
+
(
H
-
z
2
)
2
-
2
*
L
I
.
Takex as variable; we can get the derivative of the function:
(16)
d
Δ
DMSPL
d
x
=
20
x
ln
⁡
⁡
10
*
[
(
1
x
2
+
(
H
-
z
1
)
2
-
1
x
2
+
(
H
-
z
2
)
2
)
iiiiiiiiiiiiiiiiiii
(
1
x
2
+
(
H
-
z
1
)
2
-
1
x
2
+
(
H
-
z
2
)
2
)
+
(
1
x
2
+
z
2
2
-
1
x
2
+
z
1
2
)
]
.
Whenx
>
0, the derivative d
Δ
DMSPL
/
d
x
<
0, which means that Δ
DMSPL is a monotonic decreasing function with variable x when x
>
0. When x
→
0, (15) becomes
(17)
Δ
DMSPL
=
20
log
⁡
[
H
*
h
(
H
-
z
-
h
)
*
z
+
1
]
-
2
*
L
I
.
Whenx
→
∞, (15) becomes
(18)
Δ
DMSPL
=
-
2
*
L
I
.
(
2
)  x
1
≠
x
2.
We assume thatx
1
<
x
2. If we need to evaluate the impact of variables x
1,  x
2, we can analyze the extreme condition: x
1
→
0, x
2
→
∞. Equation (14) becomes
(19)
Δ
DMSPL
=
10
log
⁡
(
H
-
z
1
)
2
z
1
2
*
1
-
2
*
L
I
=
20
log
⁡
(
H
z
-
1
)
-
2
*
L
I
.
Equations (17), (18), and (19) demonstrate the different condition of Δ
DMSPL, the first item of them has minor impact (about 0–10 dB), and the second item has a major impact (about 40–50 dB).
With the deduction above, we can useΔ
DMSPL as the reference value to distinguish different floors.


## 2.2. Modeling with Multiple Anchors on Each Floor

We can separately do the vertical localization with the value ofΔ
MSPL theoretically, but, in real conditions, with the complex indoor environment and the fluctuation feature of wireless signal, we need to design a stable and multianchor model to enhance the accuracy of vertical localization.The fundamental theory of vertical localization analyzes the condition of 1-pair-anchor deployment, and we want to generalize it to multianchor model.Consider the actual deployment scenario. We need to deploy wireless anchors in the whole building. For floori, we put m
i anchors on it.As we name our system on-demand, we should minimize the number of anchors deployed with less impact on the accuracy of the whole system. With the fundamental theory of vertical localization, we can distribute the anchors on some specific floors, which have an interval ofn floors:
(20)
m
i
=
{

m
i
,
if
i
%
n
=
1
,
0
,
otherwise
.
The m
i of each floor is decided by the anchors needed for horizontal localization system.If a building has more storeys thann
+
1, we can degrade this building to several subbuildings with n
+
1 storeys and filter the receiving wireless signal only from floor t (the first floor of subbuilding) and floor (
t
+
n
).Now we have a(
n
+
1
) storey subbuilding model, and we need to decide the interval n and figure out the m-anchor algorithm.The intervaln is decided by the value that how many anchors on (
n
+
1
)th floor can be detected on the ith floor. We note the value as r
i. Obviously, r
i must be a nonnegative number, and r
1 is the minimum of r
i. We name R the threshold of the subbuilding model, which equals r
1.To do the vertical localization, we need to guarantee thatR
≥
1. Referring to (3) and (8) and substituting N
=
n
-
1:
(21)
P
R
=
P
T
+
G
T
+
G
R
-
20
log
⁡
d
-
k
MSPL
-
(
n
-
1
)
*
L
I
.
Consider the normal usage conditions: P
T
=
20 dBm, G
T
=
17 dBm, and G
R
=
2 dBm. The smart phone can detect the wireless signals that P
R is more than −99 dBm. Thus,
(22)
(
n
-
1
)
*
L
I
<
97.95
-
20
log
⁡
d
.
If d
max
⁡
=
30 m and L
I
=
20 dB, we can get the n
max
⁡
=
4.When we receiver
i wireless signals on the ith floor, we need to take advantage of all received signals to enhance the accuracy and the success rate of vertical localization.We assume that the value ofΔ
MSPL on each floor is in a narrow interval, for we can separate the value from different floors. Let us define the weight assigned to different anchors as W
=
{
w
1
,
w
2
,
…
w
i
,
…
,
w
k
}; is the weight for anchor {
i
}. As such, the Δ
MSPL value of multianchor mode will be determined as
(23)
Δ
MSP
L
WAVG
=
∑
i
‍
w
i
*
Δ
MSP
L
i
.Now we should consider the determination ofW:
(24)
U
(
ρ
^
,
σ
ρ
^
2
)
=
ρ
^
-
γ
σ
ρ
^
2
,
where ρ
^ is defined as the average of the signal, σ
ρ
^
2 is the standard deviation of ρ
^, and γ defines a relative interference coefficient that describes the loss in signal strength due to environmental interference. The r will be higher for a signal unfriendly environment such as a concrete wall building than for an outdoor environment known for less interface. Therefore, to improve the accuracy, a signature must be selected. Let us define the weight assigned to different anchors as W
=
{
w
1
,
w
2
,
…
,
w
n
}; w
i is the weight for ancho
r
i. As such, the optimization problem will be to determine W so that the total utility is maximized; that is,
(25)
max
⁡
W
∑
i
‍
U
(
ρ
^
i
,
σ
ρ
^
i
2
)
,
s
.
t
.
W
′
i
=
1
,
w
i
>
0
.Lemma 5.
The optimal solution ofW will be
(26)
w
=
1
γ
Q
-
1
(
ρ
+
λ
1
)
.Proof of (26).
Under our definition, the total utility can be written as(27)
∑
i
=
1
n
‍
w
i
U
(
ρ
^
1
,
σ
ρ
^
i
2
)
=
∑
i
=
1
n
‍
w
i
ρ
^
i
-
r
(
∑
i
=
1
n
‍
w
i
2
σ
ρ
^
i
2
+
2
∑
i
=
1
n
‍
∑
j
≠
i
n
‍
w
i
w
j
Cov
(
σ
ρ
^
i
,
σ
ρ
^
j
)
)
=
W
ρ
-
r
W
′
Q
W
,
in which,
(28)
Q
=
(
σ
ρ
^
1
2
σ
ρ
^
1
,
ρ
^
2
⋯
σ
ρ
^
1
,
ρ
^
n
σ
ρ
^
2
,
ρ
^
1
σ
ρ
^
2
2
⋯
σ
ρ
^
1
,
ρ
^
n
⋮
⋮
⋱
⋮
σ
ρ
^
n
,
ρ
^
1
σ
ρ
^
n
,
ρ
^
2
⋯
σ
ρ
^
n
2
)
,
σ
ρ
^
i
,
ρ
^
j is the degradation correlation between anchors i and j, and n is the number of anchors. The numerical solution of W can be solved by Lagrangian derivation. Let us form
(29)
C
=
W
′
ρ
-
γ
W
′
Q
W
-
λ
1
(
W
′
1
-
1
)
,
where λ
1 is a Lagrange multiplier. Then, taking derivatives of the Lagrangian with respect to vector W
′, we get
(30)
δ
L
δ
W
′
:
ρ
-
γ
Q
W
-
λ
1
=
0
.
As a result, this proves (26).The optimalW
=
{
w
1
,
w
2
,
…
,
w
n
} can then be applied to our measurement of RS
S
t as WRS
S
t to derive the optimal field signature s
*
(
t
).


## 3. The Algorithm of Enhanced Field Division

### 3.1. Field Division

During our previous research, we find that the relative signal strength rather than the absolute one can be employed to mark different unique regions in an environment. We then introduce the concept of field division with each divided subarea owning a unique signature (which will be described later). Without loss of generality, we start the discussion within a two-dimensional paradigm although our algorithm can be applied into a three-dimensional paradigm. We focus on how to use relative signal strength to determine subarea. For convenience, we first take a look at one region without interference. (Note that the practical factors will be considered in detail later on.) Ignoring the environmental noise, the received signal strength (RSS) will demonstrate a monotonic effect on the geographic distance. Though using the relative signal strength, we consider that a RSS model can facilitate our discussion. A well-studied RSS distribution model in db (decibel) as in (31) [11] meets the purpose:
(31)
RSS
(
n
i
)
=
p
0
n
i
+
10
n
log
⁡
(
r
0
n
i
r
i
)
,
in which, n, r
0
n
i, and p
0
n
i are the constants parameters for anchor n
i and r
i is the distance between the current location and anchor n
i. Letting k be the number of anchor nodes in a map, we define a high-dimensional location signature function F as follows:
(32)
s
=
F
(
rss
(
n
1
)
,
rss
(
n
2
)
,
…
,
rss
(
n
k
)
)
,
where s is signature of the target location and rss
(
n
i
), 1
≤
i
≤
k, is the target’s RSSs relative to the anchor node n
i. The function F is modeled by a descending sorting function. Therefore, we have rss
(
n
i
)
>
rss
(
n
j
) for all i
<
j for every signature s. Given the modified RSS transmission model, we denote the subarea in Definition 6 for field division.Definition 6 (subarea).
Subarea is the point set whose members own the same signature in the field segmentation.And the boundary is defined as a curve that is separating two adjacent subareas. Given any paired anchors,A
n
i, A
n
j, the dedicated part of the boundary attributed to them consists of positions, where rss
(
n
i
)
=
rss
(
n
j
). Taking a region with two anchors, A and B, as an example, the positions on the boundary can be derived as
(33)
p
0
A
+
10
n
log
⁡
r
0
A
r
1
=
p
0
B
+
10
n
log
⁡
r
0
B
r
2
,
where r
1 and r
2 represent the relative distance to anchors A and B. Solving this equation, we can get a relationship of r
1 and r
2 as (
r
2
/
r
1
)
=
k, where k
=
2
(
p
0
b
-
p
0
A
)
/
10
n.


### 3.2. Model Adjustment

Note that it is not the absolute accuracy of the RSSs, but rather the relative strength that EFD algorithm relies on in localization. Based on our measurements, we discovered the RSS degradation due to the impact of interference toward different anchors to be highly correlated. To accommodate RF fading and the multipath effects in environments, we can make an adjustment to the RSS model in (31) for the sake of convenience. Therefore, we model the effects by a factor λ to p
0 so that λ
i
p
0 absorbs the environmental interference pattern. The ideal RSS model will be adjusted as
(34)
RSS
(
i
)
=
λ
i
p
0
+
10
n
log
⁡
(
r
0
r
i
)
+
ϵ
,
where λ
i is the interference factor of anchors and ϵ is the adjustment error. Because factors λ
i
,
i
=
1,2
,
…
,
N, are highly correlated, the huge interference does not actually make that much difference in the division signatures after adjusting the model. As a result, the problem turns into estimating λ
i to minimize the estimation σ
(
ϵ
). If we denote p
′
=
λ
i
p
0 and assume that the p
′ follows a normal distribution, p
′
~
N
(
μ
0
,
σ
0
2
), and there are prior beliefs about the E
(
p
′
)
=
μ
0 and σ
(
p
′
)
=
σ
0, μ
0 and σ
0 represent the best guess for p
′ and the uncertainty of the guess, which comes from prior experiments or specification from service providers; we can modify the inputs to (34) based on thein situ estimation of p
^
′ and σ
^
(
p
′
) [12]. A standard estimator of expectations is the sample mean σ
(
ϵ
):
(35)
μ
^
=
1
l
∑
‍
t
=
1
l
X
T
~
N
(
μ
1
,
σ
1
2
l
)
,
where l is the number of available sampling series. However, the sample mean is a highly inefficient estimator as the sampling estimation varies widely when different sampling series are fed into the estimation process [12]. One way to cope with this issue is to use a more efficientbalance estimator:
(36)
μ
(
b
)
≡
(
1
-
b
)
μ
^
+
b
π
0
,
where π
0 is our best guess, π
0
~
N
(
μ
0
,
σ
0
2
), and 0
≤
b
≤
1 is the balance factor. The purpose is then to minimize balance σ
b under any given μ
(
b
). We can formalize our model as
(37)
Minimize
σ
b
2
=
b
′
V
b
Subject
to
E
(
μ
0
)
=
b
′
U
=
μ
-
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
∑
i
=
1
n
b
i
=
1
,
where V is covariance matrix between μ
^ and π
0 and U is the vector [
μ
0
,
μ
1
].The first solution to that formalization is(38)
V
b
=
λ
U
,
⟶
b
=
V
-
1
U
.Thus, the optimal balance factors given by the answer are used to derive theu
(
b
), as the optimal representation of p
′ in (34).


### 3.3. Grid Tracking Strategy

As mentioned previously, one of the biggest challenges that the EFD system faces is the status quo issue. In this section, we will discuss another key technique used in EFD, the grid tracking strategy, in which ordinal gridding based onin situ information such as the magnetic field is used to assist localization within a subarea. Denote V
-
t by the estimated velocity of the target at time t and D
→
t as the moving direction of the target. These two properties, importantly describing the motion characteristics, can be estimated precisely by approaches such as the geomagnetic field analysis by the EFD location platform.


#### 3.3.1. Magnetic Theory

Geomagnetic field is relatively stable and easy to use in giving a direction, so we estimate the directions via the geomagnetic field. To preprocess the magnetic field data, we adapt a recursive method to track the dynamic measurement by assuming that it is approximately stationary. Denotes
(
t
) by the measured signal at time slot t, which corresponds to x-, y-, or z-component of the magnetic field data and may suffer from the measurement noise or other uncertainties. The recursive method intends to track the noise-free data by updating
(39)
s
^
(
t
)
=
α
*
s
^
(
t
)
+
(
1
-
α
)
s
(
t
)
,
where s
^
(
t
) denotes the estimated signal at time slot t and α is a weight factor that balances between earlier data prior to time t and the current measurement s
(
t
). Clearly, the larger α is, the more dependent s
^
(
t
) is on earlier measurements. By this way, it is possible to remove the noise effects by relying on the historical data. However, there is a clear trade-off on the value of α, since a larger α would introduce difficulties in capturing sudden changes in s
(
t
). To this end, the smoothed magnetic fields with various choices of α are plotted in Figure 2 to illustrate the trade-off in selecting an appropriate value for α. Lastly, by initializing s
^
(
1
)
=
s
(
1
), the recursive update in (39) is extremely simple to implement since it involves only linear updates. Interestingly, this preprocessing step can effectively smooth out the perturbation present in the magnetic field data, as shown in Figure 2 with α
=
0.75.Magnetic data processed with differentα.
(a)
(b)
(c)
(d)


#### 3.3.2. Details of the Grid Tracking

While the target is moving, fictitious edges for four two-dimensional directions, S, N, W, and E, are dynamically created to gauge the motion range of a target at each cyclet. By default, the edges matrix L is set to the boundary (B
n) of the subarea A
n:
(40)
L
(
0
)
=
B
n
=
(
min
⁡
(
x
)
max
⁡
(
x
)
min
⁡
(
y
)
max
⁡
(
y
)
)
,
(
x
,
y
)
∈
A
n
,
where (
x
,
y
) is the coordinates of the subarea A
i when the target enters initially. Then, the L at time t is updated by
(41)
L
(
t
)
=
L
(
t
-
1
)
+
V
-
·
D
→
,
where L is a 2
×
2 matrix; for example, L
1,1
←
min
⁡
(
x
)and L
2,2
← limit to the north.If the edgeL exceeds the boundary of subarea A
i, this L will be replaced with the boundary. Note that the process continues until a detection of a signature change, which indicates that the target is crossing the boundary of the subarea. To move the L, we define a velocity matrix L
v as
(42)
L
v
=
[
V
-
·
cos
⁡
θ
V
-
·
cos
⁡
θ
V
-
·
sin
θ
V
-
·
sin
θ
]
.If a target moves within one subarea,L
(
t
)
=
L
(
t
-
1
)
+
L
v. However, once it crosses the boundary, the limit L will make a specific change.


### 3.4. Correction with Boundary Passing

As the target crosses the boundary separating two subareasS
i and S
j, the corresponding signatures from EFD’s mobile localization platform will change. This actually offers a great opportunity for EFD to calibrate the location estimation. Denote D
v by the direction indicator as
(43)
D
v
=
(
w
e
s
n
)
,
in which w
e
=
(
(
1
/
2
)
·
π
<
θ
<
(
3
/
2
)
·
π
)
?
1
:
2
,
s
n
=
(
π
<
θ
<
2
·
π
)
?
1
:
2, and θ
=
∠
D
→. As the signatures change, the correction algorithm will be carried out immediately as described in Algorithm 1.Algorithm 1:Correction at boundary crossing.
Output: L
→ the limit for estimated position
(1)  Input area sequence numbern
(2)  GetB
n as defined in (40)
(3)  Get the estimated angle for current moving (θ) to calculate the Dir and L
v as is defined in (43) and (42)
(4)temp
=
L
+
L
v
(5)for  i
=
1
;
i
≤
2  do
(6)
if  temp
i
,
j, j
=
3
-
Dir
1
,
i  inside subarea  then
(7)L
i
j
=
temp
i
,
j
(8)
else
(9)U
s
e
d
B
o
r
d
e
r
←
B
n
(
i
,
3
-
Dir
1
,
i
)
(10)
L
i
,
j
=
U
s
e
d
B
o
r
d
e
r
(11)
L
i
,
Dir
1
,
i
=
L
i
,
3
-
Dir
1
,
i  +  2
L
v
i
,
Dir
1
,
i;
(12)e
s
t
P
o
s
←
∑
(
x
k
,
y
k
)
/
n
u
m
b
e
r
o
f
(
x
k
,
y
k
) where (
x
k
,
y
k
)
∈
s
u
b
a
r
e
a
(
n
)
&
&
(
x
k
,
y
k
)
∈
L
i
m
i
t
(
t
)


## 3.1. Field Division

During our previous research, we find that the relative signal strength rather than the absolute one can be employed to mark different unique regions in an environment. We then introduce the concept of field division with each divided subarea owning a unique signature (which will be described later). Without loss of generality, we start the discussion within a two-dimensional paradigm although our algorithm can be applied into a three-dimensional paradigm. We focus on how to use relative signal strength to determine subarea. For convenience, we first take a look at one region without interference. (Note that the practical factors will be considered in detail later on.) Ignoring the environmental noise, the received signal strength (RSS) will demonstrate a monotonic effect on the geographic distance. Though using the relative signal strength, we consider that a RSS model can facilitate our discussion. A well-studied RSS distribution model in db (decibel) as in (31) [11] meets the purpose:
(31)
RSS
(
n
i
)
=
p
0
n
i
+
10
n
log
⁡
(
r
0
n
i
r
i
)
,
in which, n, r
0
n
i, and p
0
n
i are the constants parameters for anchor n
i and r
i is the distance between the current location and anchor n
i. Letting k be the number of anchor nodes in a map, we define a high-dimensional location signature function F as follows:
(32)
s
=
F
(
rss
(
n
1
)
,
rss
(
n
2
)
,
…
,
rss
(
n
k
)
)
,
where s is signature of the target location and rss
(
n
i
), 1
≤
i
≤
k, is the target’s RSSs relative to the anchor node n
i. The function F is modeled by a descending sorting function. Therefore, we have rss
(
n
i
)
>
rss
(
n
j
) for all i
<
j for every signature s. Given the modified RSS transmission model, we denote the subarea in Definition 6 for field division.Definition 6 (subarea).
Subarea is the point set whose members own the same signature in the field segmentation.And the boundary is defined as a curve that is separating two adjacent subareas. Given any paired anchors,A
n
i, A
n
j, the dedicated part of the boundary attributed to them consists of positions, where rss
(
n
i
)
=
rss
(
n
j
). Taking a region with two anchors, A and B, as an example, the positions on the boundary can be derived as
(33)
p
0
A
+
10
n
log
⁡
r
0
A
r
1
=
p
0
B
+
10
n
log
⁡
r
0
B
r
2
,
where r
1 and r
2 represent the relative distance to anchors A and B. Solving this equation, we can get a relationship of r
1 and r
2 as (
r
2
/
r
1
)
=
k, where k
=
2
(
p
0
b
-
p
0
A
)
/
10
n.


## 3.2. Model Adjustment

Note that it is not the absolute accuracy of the RSSs, but rather the relative strength that EFD algorithm relies on in localization. Based on our measurements, we discovered the RSS degradation due to the impact of interference toward different anchors to be highly correlated. To accommodate RF fading and the multipath effects in environments, we can make an adjustment to the RSS model in (31) for the sake of convenience. Therefore, we model the effects by a factor λ to p
0 so that λ
i
p
0 absorbs the environmental interference pattern. The ideal RSS model will be adjusted as
(34)
RSS
(
i
)
=
λ
i
p
0
+
10
n
log
⁡
(
r
0
r
i
)
+
ϵ
,
where λ
i is the interference factor of anchors and ϵ is the adjustment error. Because factors λ
i
,
i
=
1,2
,
…
,
N, are highly correlated, the huge interference does not actually make that much difference in the division signatures after adjusting the model. As a result, the problem turns into estimating λ
i to minimize the estimation σ
(
ϵ
). If we denote p
′
=
λ
i
p
0 and assume that the p
′ follows a normal distribution, p
′
~
N
(
μ
0
,
σ
0
2
), and there are prior beliefs about the E
(
p
′
)
=
μ
0 and σ
(
p
′
)
=
σ
0, μ
0 and σ
0 represent the best guess for p
′ and the uncertainty of the guess, which comes from prior experiments or specification from service providers; we can modify the inputs to (34) based on thein situ estimation of p
^
′ and σ
^
(
p
′
) [12]. A standard estimator of expectations is the sample mean σ
(
ϵ
):
(35)
μ
^
=
1
l
∑
‍
t
=
1
l
X
T
~
N
(
μ
1
,
σ
1
2
l
)
,
where l is the number of available sampling series. However, the sample mean is a highly inefficient estimator as the sampling estimation varies widely when different sampling series are fed into the estimation process [12]. One way to cope with this issue is to use a more efficientbalance estimator:
(36)
μ
(
b
)
≡
(
1
-
b
)
μ
^
+
b
π
0
,
where π
0 is our best guess, π
0
~
N
(
μ
0
,
σ
0
2
), and 0
≤
b
≤
1 is the balance factor. The purpose is then to minimize balance σ
b under any given μ
(
b
). We can formalize our model as
(37)
Minimize
σ
b
2
=
b
′
V
b
Subject
to
E
(
μ
0
)
=
b
′
U
=
μ
-
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
∑
i
=
1
n
b
i
=
1
,
where V is covariance matrix between μ
^ and π
0 and U is the vector [
μ
0
,
μ
1
].The first solution to that formalization is(38)
V
b
=
λ
U
,
⟶
b
=
V
-
1
U
.Thus, the optimal balance factors given by the answer are used to derive theu
(
b
), as the optimal representation of p
′ in (34).


## 3.3. Grid Tracking Strategy

As mentioned previously, one of the biggest challenges that the EFD system faces is the status quo issue. In this section, we will discuss another key technique used in EFD, the grid tracking strategy, in which ordinal gridding based onin situ information such as the magnetic field is used to assist localization within a subarea. Denote V
-
t by the estimated velocity of the target at time t and D
→
t as the moving direction of the target. These two properties, importantly describing the motion characteristics, can be estimated precisely by approaches such as the geomagnetic field analysis by the EFD location platform.


### 3.3.1. Magnetic Theory

Geomagnetic field is relatively stable and easy to use in giving a direction, so we estimate the directions via the geomagnetic field. To preprocess the magnetic field data, we adapt a recursive method to track the dynamic measurement by assuming that it is approximately stationary. Denotes
(
t
) by the measured signal at time slot t, which corresponds to x-, y-, or z-component of the magnetic field data and may suffer from the measurement noise or other uncertainties. The recursive method intends to track the noise-free data by updating
(39)
s
^
(
t
)
=
α
*
s
^
(
t
)
+
(
1
-
α
)
s
(
t
)
,
where s
^
(
t
) denotes the estimated signal at time slot t and α is a weight factor that balances between earlier data prior to time t and the current measurement s
(
t
). Clearly, the larger α is, the more dependent s
^
(
t
) is on earlier measurements. By this way, it is possible to remove the noise effects by relying on the historical data. However, there is a clear trade-off on the value of α, since a larger α would introduce difficulties in capturing sudden changes in s
(
t
). To this end, the smoothed magnetic fields with various choices of α are plotted in Figure 2 to illustrate the trade-off in selecting an appropriate value for α. Lastly, by initializing s
^
(
1
)
=
s
(
1
), the recursive update in (39) is extremely simple to implement since it involves only linear updates. Interestingly, this preprocessing step can effectively smooth out the perturbation present in the magnetic field data, as shown in Figure 2 with α
=
0.75.Magnetic data processed with differentα.
(a)
(b)
(c)
(d)


### 3.3.2. Details of the Grid Tracking

While the target is moving, fictitious edges for four two-dimensional directions, S, N, W, and E, are dynamically created to gauge the motion range of a target at each cyclet. By default, the edges matrix L is set to the boundary (B
n) of the subarea A
n:
(40)
L
(
0
)
=
B
n
=
(
min
⁡
(
x
)
max
⁡
(
x
)
min
⁡
(
y
)
max
⁡
(
y
)
)
,
(
x
,
y
)
∈
A
n
,
where (
x
,
y
) is the coordinates of the subarea A
i when the target enters initially. Then, the L at time t is updated by
(41)
L
(
t
)
=
L
(
t
-
1
)
+
V
-
·
D
→
,
where L is a 2
×
2 matrix; for example, L
1,1
←
min
⁡
(
x
)and L
2,2
← limit to the north.If the edgeL exceeds the boundary of subarea A
i, this L will be replaced with the boundary. Note that the process continues until a detection of a signature change, which indicates that the target is crossing the boundary of the subarea. To move the L, we define a velocity matrix L
v as
(42)
L
v
=
[
V
-
·
cos
⁡
θ
V
-
·
cos
⁡
θ
V
-
·
sin
θ
V
-
·
sin
θ
]
.If a target moves within one subarea,L
(
t
)
=
L
(
t
-
1
)
+
L
v. However, once it crosses the boundary, the limit L will make a specific change.


## 3.3.1. Magnetic Theory

Geomagnetic field is relatively stable and easy to use in giving a direction, so we estimate the directions via the geomagnetic field. To preprocess the magnetic field data, we adapt a recursive method to track the dynamic measurement by assuming that it is approximately stationary. Denotes
(
t
) by the measured signal at time slot t, which corresponds to x-, y-, or z-component of the magnetic field data and may suffer from the measurement noise or other uncertainties. The recursive method intends to track the noise-free data by updating
(39)
s
^
(
t
)
=
α
*
s
^
(
t
)
+
(
1
-
α
)
s
(
t
)
,
where s
^
(
t
) denotes the estimated signal at time slot t and α is a weight factor that balances between earlier data prior to time t and the current measurement s
(
t
). Clearly, the larger α is, the more dependent s
^
(
t
) is on earlier measurements. By this way, it is possible to remove the noise effects by relying on the historical data. However, there is a clear trade-off on the value of α, since a larger α would introduce difficulties in capturing sudden changes in s
(
t
). To this end, the smoothed magnetic fields with various choices of α are plotted in Figure 2 to illustrate the trade-off in selecting an appropriate value for α. Lastly, by initializing s
^
(
1
)
=
s
(
1
), the recursive update in (39) is extremely simple to implement since it involves only linear updates. Interestingly, this preprocessing step can effectively smooth out the perturbation present in the magnetic field data, as shown in Figure 2 with α
=
0.75.Magnetic data processed with differentα.
(a)
(b)
(c)
(d)


## 3.3.2. Details of the Grid Tracking

While the target is moving, fictitious edges for four two-dimensional directions, S, N, W, and E, are dynamically created to gauge the motion range of a target at each cyclet. By default, the edges matrix L is set to the boundary (B
n) of the subarea A
n:
(40)
L
(
0
)
=
B
n
=
(
min
⁡
(
x
)
max
⁡
(
x
)
min
⁡
(
y
)
max
⁡
(
y
)
)
,
(
x
,
y
)
∈
A
n
,
where (
x
,
y
) is the coordinates of the subarea A
i when the target enters initially. Then, the L at time t is updated by
(41)
L
(
t
)
=
L
(
t
-
1
)
+
V
-
·
D
→
,
where L is a 2
×
2 matrix; for example, L
1,1
←
min
⁡
(
x
)and L
2,2
← limit to the north.If the edgeL exceeds the boundary of subarea A
i, this L will be replaced with the boundary. Note that the process continues until a detection of a signature change, which indicates that the target is crossing the boundary of the subarea. To move the L, we define a velocity matrix L
v as
(42)
L
v
=
[
V
-
·
cos
⁡
θ
V
-
·
cos
⁡
θ
V
-
·
sin
θ
V
-
·
sin
θ
]
.If a target moves within one subarea,L
(
t
)
=
L
(
t
-
1
)
+
L
v. However, once it crosses the boundary, the limit L will make a specific change.


## 3.4. Correction with Boundary Passing

As the target crosses the boundary separating two subareasS
i and S
j, the corresponding signatures from EFD’s mobile localization platform will change. This actually offers a great opportunity for EFD to calibrate the location estimation. Denote D
v by the direction indicator as
(43)
D
v
=
(
w
e
s
n
)
,
in which w
e
=
(
(
1
/
2
)
·
π
<
θ
<
(
3
/
2
)
·
π
)
?
1
:
2
,
s
n
=
(
π
<
θ
<
2
·
π
)
?
1
:
2, and θ
=
∠
D
→. As the signatures change, the correction algorithm will be carried out immediately as described in Algorithm 1.Algorithm 1:Correction at boundary crossing.
Output: L
→ the limit for estimated position
(1)  Input area sequence numbern
(2)  GetB
n as defined in (40)
(3)  Get the estimated angle for current moving (θ) to calculate the Dir and L
v as is defined in (43) and (42)
(4)temp
=
L
+
L
v
(5)for  i
=
1
;
i
≤
2  do
(6)
if  temp
i
,
j, j
=
3
-
Dir
1
,
i  inside subarea  then
(7)L
i
j
=
temp
i
,
j
(8)
else
(9)U
s
e
d
B
o
r
d
e
r
←
B
n
(
i
,
3
-
Dir
1
,
i
)
(10)
L
i
,
j
=
U
s
e
d
B
o
r
d
e
r
(11)
L
i
,
Dir
1
,
i
=
L
i
,
3
-
Dir
1
,
i  +  2
L
v
i
,
Dir
1
,
i;
(12)e
s
t
P
o
s
←
∑
(
x
k
,
y
k
)
/
n
u
m
b
e
r
o
f
(
x
k
,
y
k
) where (
x
k
,
y
k
)
∈
s
u
b
a
r
e
a
(
n
)
&
&
(
x
k
,
y
k
)
∈
L
i
m
i
t
(
t
)


## 4. System Analysis

To illustrate the performance of the MSD system, we executed extensive computer analysis and conducted localization tests based on our software-hardware 3D-ODDIL system platform. In this section, the analysis results are demonstrated.


### 4.1. MSD with One Anchor Pair

First, we design the analytical environment: we plot 1 pair of anchors on the 1st and(
n
+
1
)th floor and calculate the Δ
MSPL values under this circumstance. The anchor pair is at the same point vertically, and we evaluate the Δ
MSPL value when the horizontal distance x varies from 0 to 20 meter. We repeat the computing with different N values to see whether our algorithm is universal. And the results are shown in Figure 3. We define the floor height h
=
3.5 meters and the insertion loss of reinforced concrete wall L
I
=
25 dB. The max distance from test point to the anchors horizontally is 20 meter.DifferentΔ
MSPL when interval varies.
(a)
Intervaln
=
3
(b)
Intervaln
=
4
(c)
Intervaln
=
5
(d)
Intervaln
=
10


### 4.2. MSD with Multipair Anchors

In this section, we analyze the condition that there are multianchors in MSD algorithm. The test environment is an expanded condition of MSD with 1 pair of anchors. Figure4 illustrates different conditions with 3 anchor pairs. Figure 5 illustrates different conditions with 5 anchor pairs. We define d
i as the horizontal distance for anchor pair i. We set interval n
=
4. The figures illustrate the value curve when multipair anchors are detected.Δ
MSPL with 3 anchor pairs.
(a)
d1 = 0, d2 = 10, and d3 = 20
(b)
d1 = 5, d2 = 10, and d3 = 20
(c)
d1 = 10, d2 = 15, and d3 = 20
(d)
d1 = 12, d2 = 15, and d3 = 18Δ
MSPL with 5 anchor pairs.
(a)
d1 = 0, d2 = 5, d3 = 10, d4 = 15, and d5 = 20
(b)
d1 = 6, d2 = 8, d3 = 16, d4 = 18, and d5 = 18


### 4.3. Effects of Multipair Anchors

As we can see in the results, the analytical points on each floor fluctuate in narrow space, and theΔ
MSPL line of each floor is almost parallel to each other. When more anchors are detected, the result curve is smoother and improves to distinguish the floors. We can conclude that, under ideal circumstance, the MSD algorithm can fulfill the task of floor localization.


## 4.1. MSD with One Anchor Pair

First, we design the analytical environment: we plot 1 pair of anchors on the 1st and(
n
+
1
)th floor and calculate the Δ
MSPL values under this circumstance. The anchor pair is at the same point vertically, and we evaluate the Δ
MSPL value when the horizontal distance x varies from 0 to 20 meter. We repeat the computing with different N values to see whether our algorithm is universal. And the results are shown in Figure 3. We define the floor height h
=
3.5 meters and the insertion loss of reinforced concrete wall L
I
=
25 dB. The max distance from test point to the anchors horizontally is 20 meter.DifferentΔ
MSPL when interval varies.
(a)
Intervaln
=
3
(b)
Intervaln
=
4
(c)
Intervaln
=
5
(d)
Intervaln
=
10


## 4.2. MSD with Multipair Anchors

In this section, we analyze the condition that there are multianchors in MSD algorithm. The test environment is an expanded condition of MSD with 1 pair of anchors. Figure4 illustrates different conditions with 3 anchor pairs. Figure 5 illustrates different conditions with 5 anchor pairs. We define d
i as the horizontal distance for anchor pair i. We set interval n
=
4. The figures illustrate the value curve when multipair anchors are detected.Δ
MSPL with 3 anchor pairs.
(a)
d1 = 0, d2 = 10, and d3 = 20
(b)
d1 = 5, d2 = 10, and d3 = 20
(c)
d1 = 10, d2 = 15, and d3 = 20
(d)
d1 = 12, d2 = 15, and d3 = 18Δ
MSPL with 5 anchor pairs.
(a)
d1 = 0, d2 = 5, d3 = 10, d4 = 15, and d5 = 20
(b)
d1 = 6, d2 = 8, d3 = 16, d4 = 18, and d5 = 18


## 4.3. Effects of Multipair Anchors

As we can see in the results, the analytical points on each floor fluctuate in narrow space, and theΔ
MSPL line of each floor is almost parallel to each other. When more anchors are detected, the result curve is smoother and improves to distinguish the floors. We can conclude that, under ideal circumstance, the MSD algorithm can fulfill the task of floor localization.


## 5. Experiment and Analysis

To quantify the performance of the proposed MSD algorithm, we carried out extensive vertical location tests by using our developed localization system platform. In this section, we categorize the experiments we have done into two sets in different environments with increasing complexity.


### 5.1. Localization System Platform

As a generic localization system, the 3D-ODDL systems can be suitable to any types of anchors with different radio signal frequencies. For the convenience deployment of experiments, we build our platform with Wi-Fi routers as the anchors and Android-based smart phones/tablets as the signal receivers. We choose Tenda W3000R routers as our anchors and use Google Nexus 7 as the signal receiver. The whole platform is shown in Figure6.Figure 6
3D-ODDL platform.Dormitory building overview.
(a)
(b)


### 5.2. Experiments in a Dormitory Building

#### 5.2.1. Received Signals in the Building

Figure8 is the signal received map when we jog on the first floor. We set one anchor on each floor from floor 1 to floor 3. All the anchors are on the same horizontal position. We can see that the signals of each anchor fluctuate as time flies.MSD experiment data with 2 anchor pairs.
(a)
(b)
(c)
(d)
(e)
(f)


#### 5.2.2. MSD Experiments with Two Anchor Pairs

In this part, we set two anchor pairs on floor 1 and floor 3 of the building and receive signals on floors 1, 2, and 3. The distance between each anchor pair on the same floor is 10 meters. The sampling points on horizontal direction are 2 m, 4 m, 6 m, 8 m, and 10 m. We record 20 times for all sampling points with every 5 seconds. Figure8 shows the test data, with the coordinates: axis x sampling time in sec, axis y distance on horizontal direction in meter, and axis z received signals in dB.Then, we use our weighting model to calculate the weighted-average of received signals on each floor:(44)
Δ
MSP
L
WAVG
=
∑
i
‍
(
1
/
δ
i
(
∑
i
(
1
/
δ
i
)
)
*
Δ
MSP
L
i
)
.
Finally, we use the MSD algorithm to calculate the values of Δ
MSPL. We can see the key feature in Table 1.Table 1
Average and standard deviation.
Index
Floor 1
Floor 2
Floor 3
Average
37.96
−4.58
−44.25
Standard deviation
7.19
5.21
6.6
Δ
DMSPL
42.54
39.67
/


## 5.1. Localization System Platform

As a generic localization system, the 3D-ODDL systems can be suitable to any types of anchors with different radio signal frequencies. For the convenience deployment of experiments, we build our platform with Wi-Fi routers as the anchors and Android-based smart phones/tablets as the signal receivers. We choose Tenda W3000R routers as our anchors and use Google Nexus 7 as the signal receiver. The whole platform is shown in Figure6.Figure 6
3D-ODDL platform.Dormitory building overview.
(a)
(b)


## 5.2. Experiments in a Dormitory Building

### 5.2.1. Received Signals in the Building

Figure8 is the signal received map when we jog on the first floor. We set one anchor on each floor from floor 1 to floor 3. All the anchors are on the same horizontal position. We can see that the signals of each anchor fluctuate as time flies.MSD experiment data with 2 anchor pairs.
(a)
(b)
(c)
(d)
(e)
(f)


### 5.2.2. MSD Experiments with Two Anchor Pairs

In this part, we set two anchor pairs on floor 1 and floor 3 of the building and receive signals on floors 1, 2, and 3. The distance between each anchor pair on the same floor is 10 meters. The sampling points on horizontal direction are 2 m, 4 m, 6 m, 8 m, and 10 m. We record 20 times for all sampling points with every 5 seconds. Figure8 shows the test data, with the coordinates: axis x sampling time in sec, axis y distance on horizontal direction in meter, and axis z received signals in dB.Then, we use our weighting model to calculate the weighted-average of received signals on each floor:(44)
Δ
MSP
L
WAVG
=
∑
i
‍
(
1
/
δ
i
(
∑
i
(
1
/
δ
i
)
)
*
Δ
MSP
L
i
)
.
Finally, we use the MSD algorithm to calculate the values of Δ
MSPL. We can see the key feature in Table 1.Table 1
Average and standard deviation.
Index
Floor 1
Floor 2
Floor 3
Average
37.96
−4.58
−44.25
Standard deviation
7.19
5.21
6.6
Δ
DMSPL
42.54
39.67
/


## 5.2.1. Received Signals in the Building

Figure8 is the signal received map when we jog on the first floor. We set one anchor on each floor from floor 1 to floor 3. All the anchors are on the same horizontal position. We can see that the signals of each anchor fluctuate as time flies.MSD experiment data with 2 anchor pairs.
(a)
(b)
(c)
(d)
(e)
(f)


## 5.2.2. MSD Experiments with Two Anchor Pairs

In this part, we set two anchor pairs on floor 1 and floor 3 of the building and receive signals on floors 1, 2, and 3. The distance between each anchor pair on the same floor is 10 meters. The sampling points on horizontal direction are 2 m, 4 m, 6 m, 8 m, and 10 m. We record 20 times for all sampling points with every 5 seconds. Figure8 shows the test data, with the coordinates: axis x sampling time in sec, axis y distance on horizontal direction in meter, and axis z received signals in dB.Then, we use our weighting model to calculate the weighted-average of received signals on each floor:(44)
Δ
MSP
L
WAVG
=
∑
i
‍
(
1
/
δ
i
(
∑
i
(
1
/
δ
i
)
)
*
Δ
MSP
L
i
)
.
Finally, we use the MSD algorithm to calculate the values of Δ
MSPL. We can see the key feature in Table 1.Table 1
Average and standard deviation.
Index
Floor 1
Floor 2
Floor 3
Average
37.96
−4.58
−44.25
Standard deviation
7.19
5.21
6.6
Δ
DMSPL
42.54
39.67
/


## 6. Related Work

Localization in WSN has become an active research topic again recently, and a continuum of algorithms has been proposed [13–25]. Sensors and beacons are utilized to detect the movements for range-based localization in [14, 16, 22, 23]. To undermine the effect from physical channel, range-free algorithms based on a relative distance using trilateration and grid-based methods based on landmarks in school and office contexts emerged in RSD [26], RND [27], UnLoc [28], and EZ [29]. Both range-free and grid-based methods make great improvement in roubustness and reliability, and each of them owns unique merits in indoor localization. However, they understate the complexity of implementing 3-dimensional localization, albeit they depict reliable methods for 2-dimensional localization. In this paper, we focus on the 3-dimensional localization, analyze the characteristics of indoor vertical distribution, and propose a distinctive vertical localization and a horizontal localization in a hybrid idea of range-free and grid-based methods.


## 7. Conclusion

This paper introduces a new mechanism of localization called 3-dimensional on-demand indoor localization system (3D-ODIL), which can increase the accuracy and stability of localization of multistorey buildings. On horizontal direction, we use enhanced field division (EFD) algorithm to conduct the horizontal localization. On vertical direction, we implement multistorey differential (MSD) algorithm to fulfill the vertical localization, which can greatly reduce the number of anchors deployed. To test the mechanism of the MSD, we conduct a series of experiments. And we also build a localization system platform to conduct real-environmental experiments. The result proves that the MSD is more reliable than other approaches for vertical localization. More importantly, the low-cost design and on-demand deployment allow the 3D-ODIL for large-scale applications and wide utilization.



---

*Source: 149016-2014-07-20.xml*