Improved TOA-Based Localization Method with BS Selection Scheme for Wireless Sensor Networks

ETRI Journal.
2015.
Aug,
37(4):
707-716

- Received : October 27, 2014
- Accepted : March 19, 2015
- Published : August 01, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

The purpose of a localization system is to estimate the coordinates of the geographic location of a mobile device. The accuracy of wireless localization is influenced by non-line-of-sight (NLOS) errors in wireless sensor networks. In this paper, we present an improved time of arrival (TOA)–based localization method for wireless sensor networks. TOA-based localization estimates the geographic location of a mobile device using the distances between a mobile station (MS) and three or more base stations (BSs). However, each of the NLOS errors along a distance measured from an MS (device) to a BS (device) is different because of dissimilar obstacles in the direct signal path between the two devices. To accurately estimate the geographic location of a mobile device in TOA-based localization, we propose an optimized localization method with a BS selection scheme that selects three measured distances that contain a relatively small number of NLOS errors, in this paper. Performance evaluations are presented, and the experimental results are validated through comparisons of various localization methods with the proposed method.
the
mobile station (MS)). The distance data between each BS and the MS can be measured by multiplying the signal propagation delay time by the speed of light. In TOA-based location estimation, the unique point of the intersection of the TOA circles is in fact the location of the MS itself. However, in WSNs, because of a variety of errors such as non-line-of-sight (NLOS) conditions
[2]
, clock offset
[3]
, and unequal reply time of ranging
[4]
, the TOA circles do not accurately calculate the unique point of intersection in the TOA-based location estimation method, as shown in
[5]
. Among several such distance errors, NLOS errors seriously affect the performance of a localization system. Furthermore, in indoor environments, due to the existence of obstructions, signal interference, channel fading, and multipath
[6]
between nodes are influenced by a combination of line of sight (LOS), NLOS, and a weakened signal. Therefore, in WSNs, localization techniques have been recently investigated by a variety of methods for reducing NLOS errors
[7]
–
[8]
. In
[8]
, a TOA-based localization for the NLOS error migration method is presented in indoor environments. The technique (that is, NLOS error mitigation method) estimates the geographic location of an MS using compensated distances.
In this paper, for NLOS environments, we propose an improved TOA-based localization method with a BS selection scheme for WSNs. The object of this paper is to enhance the performance of the localization system using three or more BSs in WSNs. We present an optimized localization method with a BS selection scheme that selects a combination of three BSs with fewer NLOS errors. In
[8]
, the compensated distances, which are converted into measured distance by using the NLOS error mitigation method, are directly utilized in TOA-based localization. However, this paper focuses on a selection scheme that selects a combination of three BSs with fewer NLOS errors in a wireless localization system. The key concept of this paper is to calculate the location of an MS by using the measured distances between the MS and three surrounding BSs through a BS selection scheme; the measured distances mentioned here are to contain relatively few NLOS errors. To verify localization performance, we conduct localization experiments in real indoor environments, and the simulation results are shown to establish the improved localization performance due to the proposed BS selection scheme in WSNs.
t
_{p}
, to estimate the distance between two nodes. It can be classified as one of three techniques, including one-way ranging (OWR)
[9]
, two-way ranging (TWR)
[10]
, or symmetrical double-sided two-way ranging (SDS-TWR)
[4]
,
[8]
, based on the transmitted packets for calculating the distance. The three techniques for TOA-based ranging briefly diagram the system in a scenario between two nodes.
A. OWR
The OWR protocol
[9]
requires accurately synchronized local clocks between two nodes for ranging. However, in WSNs, this method is not attractive due to very accurate clocks, which increase the complexity and cost of the nodes for ranging. As described in
Fig. 1
, the TOA of the signal at the
i
th node is calculated by
t
_{p}
.
TOA-based ranging protocols.
B. TWR
This protocol
[10]
requires the nodes to exchange two packets for distance estimation and reduces the clock synchronization requirement replying with the transmitted packet between BSs and the MS. In the TWR protocol of
Fig. 1
, the TOA of the signal
t
_{p,TWR}
is described as
(1) $${t}_{\text{p,TWR}}=\frac{1}{2}({T}_{\text{round},A}-{T}_{\text{reply},B}),$$
where
T
_{round, A}
denotes the round-trip time at node A and
T
_{reply, B}
denotes the reply time at node B.
C. SDS-TWR
The SDS-TWR protocol is presented to eliminate the offset, which induces the ranging error, of the TWR protocol associated with
T
_{reply, B}
, as discussed in
[4]
,
[8]
, and
[11]
. To properly utilize SDS-TWR, a minimum of four packets is required with an assumption that
T
_{reply, A}
=
T
_{reply, B}
, as shown in
Fig. 1
. As illustrated in
Fig. 1
, SDS-TWR has two round-trip times, denoted by
T
_{round,A}
and
T
_{round,B}
, which are measured between two nodes and are calculated using
(2) $$\frac{1}{2}({T}_{\text{round},A}-{T}_{\text{reply},B})\text{and}\frac{1}{2}({T}_{\text{round},B}-{T}_{\text{reply},A}).$$
Consequently, the average propagation delay is given by
(3) $${t}_{\text{p,SDS-TWR}}=\frac{1}{4}\{({T}_{\text{round},A}-{T}_{\text{reply},B})+({T}_{\text{round},B}-{T}_{\text{reply},A})\}.$$
In WSNs, the ranging estimation accuracy is dependent on the distance measurement accuracy, which can be affected by additive white Gaussian noise (AWGN), multipath environments, direct path excess delay, NLOS error, multiple access interference, clock offset, and unequal reply times.
N
fixed BSs with known locations, expressed as
x
_{i}
= [
x_{i}
,
y_{i}
]
^{T}
for
i
= 1, ... ,
N
. The location of the MS with an unknown location is expressed as
x
= [
x
,
y
]
^{T}
. For example, in NLOS environments,
Fig. 2
illustrates TOA-based localization among three BSs and an MS. The TOA-based measured distance,
i
th BS to the MS can be computed by multiplying the TOA of the signal
t
_{p}
in Section II-1 by the speed of light
c
, and it is modeled as
[5]
,
[12]
(4) $$\begin{array}{l}{\widehat{d}}_{i}=\text{}c\cdot {t}_{\text{p}}\\ \text{=}{d}_{i}+{b}_{i}+{n}_{i},\end{array}$$
where
d_{i}
is the true distance using the TOA method between the MS and the
i
th BS,
b_{i}
is the NLOS bias error, and
n_{i}
~𝒩(0,
b_{i}
is a positive-distance bias that is due to the obstacles of the signal direct path between the
i
th BS and the MS, and it is expressed by
(5) $${b}_{i}=\{\begin{array}{lll}0\hfill & \text{if}\hfill & i\text{thBSisLOS,}\hfill \\ {e}_{i}\hfill & \text{if}\hfill & i\text{thBSisNLOS.}\hfill \end{array}$$
TOA-based localization in NLOS environments.
In (9), we assume that
b_{i}
=
e_{i}
if the signal propagation between the
i
th BS and the MS is in an NLOS environment.
The noiseless true distance
d_{i}
is calculated by equation trilateration as follows:
(6) $$\begin{array}{ll}{d}_{i}\hfill & =\Vert \text{}\text{x}-{\text{x}}_{i}\Vert \text{}\hfill \\ \hfill & =\sqrt{{\left(x-{x}_{i}\right)}^{2}+{\left(y-{y}_{i}\right)}^{2}},\hfill \end{array}$$
where ∥·∥ represents the Euclidean norm operation on a vector of the distance between the MS and the
i
th BS.
(7) $${d}_{i}^{2}={(x-{x}_{i})}^{2}+{(y-{y}_{i})}^{2},\text{}i=1,\text{}\mathrm{...}\text{},N.$$
Then, we can calculate the location of the MS using the unique point of intersection of all of the TOA circles. However, in real environments, considering the TOA measurements with noise and the NLOS errors at fixed BSs, a TOA circle is modeled as
(8) $${\widehat{d}}_{i}^{2}={(x-{x}_{i})}^{2}+{(y-{y}_{i})}^{2},\text{}i\text{=1,}\mathrm{...}\text{,}N\text{,}$$
using (4) in Section II-2. In
Fig. 2
, we cannot calculate the location of the MS using the unique point of intersection of the TOA circles with the measured distance. Hence, to solve the MS’s location using a nonlinear model in TOA measurements, we have to convert a nonlinear expression into a linear expression using the difference of the TOA measurements. As a result, utilizing some matrix linearization and representation, we have the following linear model of the TOA measurements as in
[13]
–
[14]
:
(9) $$\text{A\theta}=\frac{1}{2}\text{P}$$
with
(10) $$\text{A}=\left[\begin{array}{c}{x}_{1\text{}}{y}_{1\text{}}-0.5\\ {x}_{2\text{}}{y}_{2\text{}}-0.5\\ \vdots \text{}\vdots \text{}\vdots \\ {x}_{N\text{}}{y}_{N\text{}}-0.5\end{array}\right],\text{\theta}=\left[\begin{array}{c}\text{}x\\ \text{}y\text{}\\ {x}^{2}+{y}^{2}\end{array}\right],\text{P}=\left[\begin{array}{l}{x}_{1}^{2}\text{+}{y}_{1}^{2}-{d}_{1}^{2}\\ {x}_{2}^{2}\text{+}{y}_{2}^{2}-{d}_{2}^{2}\\ \text{}\vdots \\ {x}_{N}^{2}\text{+}{y}_{N}^{2}-{d}_{N}^{2}\end{array}\right].$$
As a result, obtaining
θ
with the MS’s location value
x
, we can calculate the matrix interpretation (9), which is computed as
(11) $$\widehat{\text{\theta}}=\frac{1}{2}{\left({A}^{\text{T}}A\right)}^{-1}{A}^{\text{T}}P\text{\hspace{0.17em}},$$
where T is the transpose operator. Also, this process of solving the matrix expression of the TOA measurements (that is, equations (9), (10), and (11)) is called the linear least squares method, as in
[12]
. However, in NLOS environments, the unique point of intersection of all TOA circles with the measured distance between the BSs and MS does not exist, as shown in
Fig. 3
.
We clearly describe the transformation process of TOA-based localization from LOS environments to NLOS environments in
Fig. 3
. Due to the presence of NLOS errors, the intersection for the MS’s estimated location will be transferred from the true MS location. Consequently, it is difficult to accurately find the estimated location of the MS in NLOS environments.
Transformation process of TOA-based localization from LOS environments to NLOS environments: (a) LOS environments and (b) NLOS environments.
(12) $$\begin{array}{ll}{\widehat{\text{x}}}_{\text{NLS}}\hfill & =\text{arg\hspace{0.17em}}\underset{\text{x}}{\text{min}}\left\{{\displaystyle \sum _{i=1}^{N}{\left({\widehat{d}}_{i}-\Vert \text{x}-{\text{x}}_{i}\Vert \right)}^{2}}\right\}\hfill \\ \hfill & =\underset{\text{x}}{\text{min}}\left\{{\displaystyle \sum _{i=1}^{N}{\left({e}_{i}\right)}^{2}}\right\},\hfill \end{array}$$
where
x
is the coordinate value of the MS’s location,
x
_{i}
is the coordinate value of the
i
th BS’s location, and
e_{i}
=
b_{i}
+
n_{i}
is the error value between the MS and the
i
th BS, as described in Section II-2.
To enhance the performance of the NLS technique, the weighted least squares (WLS) method has been presented in
[16]
, and is denoted as
(13) $$\begin{array}{ll}{\widehat{\text{x}}}_{\text{WLS}}\hfill & =\text{arg\hspace{0.17em}}\underset{\text{x}}{\text{min}}\left\{{\displaystyle \sum _{i=1}^{N}{\beta}_{i}{\left({\widehat{d}}_{i}-\Vert \text{x}-{\text{x}}_{i}\Vert \right)}^{2}}\right\}\hfill \\ \hfill & =\text{arg\hspace{0.17em}}\underset{\text{x}}{\text{min}}\left\{{\displaystyle \sum _{i=1}^{N}{\beta}_{i}{\left({e}_{i}\right)}^{2}}\right\}.\hfill \end{array}$$
Some weights,
β_{i}
, can be utilized to feature the dependability of each measured distance between the MS and the
i
th BS in WSNs. We denote the weight factor
β_{i}
, which is defined as the variance of the TOA error in
[15]
,
[17]
and is expressed as
β_{i}
= 1/
(14) $${\sigma}_{i}^{2}\text{=E}\left\{{\left({\widehat{d}}_{i}-\Vert \text{x}-{\text{x}}_{i}\Vert \right)}^{2}\right\},$$
where E{ · } is the expected value operator.
Diagram of intersections in TOA-based localization.
d_{i}
, which is given by
(15) $${\widehat{\text{x}}}_{\text{LMS}}=\text{\hspace{0.17em}arg\hspace{0.17em}}\underset{\text{x}}{\text{min}}\left\{\text{me}{\text{d}}_{i}{\left({\widehat{d}}_{i}-\text{\hspace{0.17em}}\text{\Vert}\text{x}-{\text{x}}_{i}\text{\Vert}\right)}^{2}\right\},$$
where med
_{i}
(
θ
(
i
)) is the median of the function
θ
(
i
) over all possible values of
i
.
Relationship between length of chord and NLOS error.
In Section II-2, we expressed the
i
th BS’s location as
x
_{i}
= [
x_{i}
,
y_{i}
]
^{T}
and the measured distance as
(16) $${\tilde{d}}_{1}=\frac{|A{x}_{1}+B{y}_{1}+X+Y-R|}{\sqrt{{A}^{2}+{B}^{2}}}\text{or}{\tilde{d}}_{2}=\frac{|A{x}_{2}+B{y}_{2}+X+Y-R|}{\sqrt{{A}^{2}+{B}^{2}}},$$
where
(17) $$\begin{array}{l}A=-2({x}_{1}-{x}_{2}),\text{}B=-2({y}_{1}-{y}_{2}),\\ X={x}_{1}^{2}+{x}_{2}^{2},\text{}Y={y}_{1}^{2}+{y}_{2}^{2},\text{and}R={\widehat{d}}_{1}^{2}+{\widehat{d}}_{2}^{2}.\end{array}$$
To calculate the length of the chord between two TOA circles, the Pythagorean theorem is utilized using the distance
(18) $$l\text{=2}\sqrt{{\widehat{d}}_{1}^{2}-{\tilde{d}}_{1}^{2}}\text{or}l\text{=2}\sqrt{{\widehat{d}}_{2}^{2}-{\tilde{d}}_{2}^{2}},$$
where
l
is the length of the chord. Similarly, other lengths of chords, such as between BS2 and BS3 and between BS3 and BS1, can be easily computed. By computing the distance from a point to a line as described in Appendix 2, we can estimate the length of a chord that consists of the intersections of TOA circles. For example, as shown in
Fig. 6(a)
, using the Pythagorean theorem between the circles of two BSs, the length of chord can be calculated. Also similarly, as shown in
Fig. 6(b)
, the length of chords in three BSs is drawn in 2-D localization system.
Length of chord in TOA-based localization: (a) computation of length of chord and (b) expression of chords.
L
(
j
), where
j
is the number of combinations of three BSs from the total BSs. Finally, we can estimate the MS’s location, which is estimated using the localization method as described in Section III, by using the minimizing step, which is expressed as
(19) $$\mathrm{arg}\text{}\underset{j}{\text{min}}\text{}\text{L}\text{(}j\text{)}.$$
Equation (19) can minimize the estimation error of the MS’s location using a process that finds the combination of three BSs with the fewest NLOS errors in WSNs. The procedure of finding the value of
j
that minimizes the sum of the lengths of the chords is the BS selection, and
Fig. 7
shows a flow chart of the localization process with the BS selection. Then, we present the algorithm using the proposed BS selection scheme in
Table 1
.
Flow chart of localization process using BS selection.

^{T}
, [1.5, 20.5]
^{T}
, [34.7, 20.5]
^{T}
, [34.7, 1.1]
^{T}
, [19.1, 1.1]
^{T}
, and [19.1, 20.5]
^{T}
at a height of 1.7 m. The MS’s location for the experimental test was placed in several locations with coordinate values of [7.9, 6]
^{T}
, [19.1, 10.5]
^{T}
, and [27.8, 15]
^{T}
at a height of 1 m. The estimation error is the difference between the coordinates of the true MS location,
x
, and the coordinates of the estimated MS location,
(20) $$\text{Estimationerror=}\left|\text{x}-\widehat{\text{x}}\right|.$$
Experimental environment (gymnasium).
In
Fig. 9
, to verify the effectiveness of the localization system, the number of 200 shot patterns for the localization is shown in overlap. Comparing the shot patterns for NLS
[15]
, WLS
[16]
, centroid
[19]
, and LMS
[21]
with the BS selection method, we can confirm that the shot pattern of the MS in the localization system with BS selection is distributed more accurately than the others.
Table 2
shows the experimental results of the localization system by comparing various conventional methods with the proposed localization scheme. For instance,
Fig. 9
indicates the shot patterns of the experimental results of four different location estimation techniques at a location (19.1, 10.5) in a gymnasium. As shown in
Figs. 9(a)
and
9(b)
, comparing the localization without BS selection and with BS selection, the distributions of the shot patterns for estimating the MS’s location using localization with BS selection are more accurate than the localization without BS selection.
Table 2
illustrates estimation errors, excerpts from the shot pattern data from the experimental results, recorded at three different locations.
Comparison of distributions of shot pattern at location (19.1, 10.5) in gymnasium: (a) using general localization without BS selection and (b) using proposed localization with BS selection.

^{T}
, [10.52, 34.6]
^{T}
, [90.04, 34.6]
^{T}
, [90.04, 11.5]
^{T}
, [56.98, 11.5]
^{T}
, and [56.98, 34.6]
^{T}
at a height of 1.7 m. We installed the MS in locations with coordinate values [30.2, 19.7]
^{T}
, [56.2, 19.7]
^{T}
, and [72.8, 19.7]
^{T}
at a height of 1 m.
Experimental environment (parking lot).
The experimental results of the localization system are shown in
Table 3
. The simulation analysis in the parking lot proves that the proposed method has better localization performance than the other localization methods. In
Fig. 11
, the shot patterns of the results of the localization experiment are indicated at location (30.2, 19.7) in the underground parking lot. To compare the accuracy in estimating the MS’s location, the number of 100 shot patterns is drawn in overlap using various localization methods. To evaluate the performance of the localization methods,
Figs. 11(a)
and
11(b)
represent the localization without BS selection and with BS selection, respectively.
Table 3
shows estimation errors, excerpts from the shot pattern data from the experimental results, for localization methods with and without BS selection.

Comparison of distributions of shot pattern at location (30.2, 19.7) in underground parking lot: (a) in general localization without BS selection and (b) in proposed localization with BS selection.
r
_{1}
and
r
_{2}
and having centers (
x
_{1}
,
y
_{1}
) and (
x
_{2}
,
y
_{2}
) are expressed, respectively, as
(21) $$\{\begin{array}{l}{(x-{x}_{1})}^{2}+{(y-{y}_{1})}^{2}={r}_{1}^{2},\\ {(x-{x}_{2})}^{2}+{(y-{y}_{2})}^{2}={r}_{2}^{2},\end{array}$$
(22) $$\text{or}\{\begin{array}{l}{x}^{2}+{y}^{2}-2x{x}_{1}-2y{y}_{1}+{x}_{1}^{2}+{y}_{1}^{2}-{r}_{1}^{2}=0,\\ {x}^{2}+{y}^{2}-2x{x}_{2}-2y{y}_{2}+{x}_{2}^{2}+{y}_{2}^{2}-{r}_{2}^{2}=0.\end{array}$$
To solve the straight line through the intersection of two circles, the difference between the two circles in (22) is described by
(23) $$-2({x}_{1}-{x}_{2})x-2({y}_{1}-{y}_{2})+X+Y-R=0,$$
where
X
,
Y
, and
R
are constant values with
x
_{1}
,
y
_{1}
) to the straight line determined by the equation
A
(
x
−
x
_{0}
) +
B
(
y
−
y
_{0}
) =
Ax
+
By
+
C
= 0 is determined as in
[28]
. To do so, consider the unit normal vector
(24) $$\text{n}=\frac{A\text{i}+B\text{j}}{\sqrt{{A}^{2}+{B}^{2}}},$$
which is a unit vector normal to the straight line. As illustrated in
Fig. 12
, a perpendicular is dropped from E to the straight line to construct the triangle REQ. The distance
n
, and is expressed as
(25) $$\begin{array}{l}d=\left|\text{v}\cdot \text{n}\right|=\left|[({x}_{1}-{x}_{0})\text{i}+({y}_{1}-{y}_{0})\text{j}\text{]}\cdot \text{n}\right|\\ \text{=}\frac{A({x}_{1}-{x}_{0})+B({y}_{1}-{y}_{0})}{\sqrt{{A}^{2}+{B}^{2}}}.\end{array}$$
Geometry for determining distance from point E to straight line RQ .
The distance
d
from a point (
x
_{1}
,
y
_{1}
) to the plane
Ax
+
By
+
C
= 0 is
(26) $$d=\frac{\left|A{x}_{1}+B{y}_{1}+C\right|}{\sqrt{{A}^{2}+{B}^{2}}}.$$
This work was supported by the National Research Foundation of Rep. of Korea (NRF) grant funded by the Korean government (MOE) (NRF-2013R1A1A2011259).
milkyface@hanyang.ac.kr
Seungryeol Go received his BS degree in electronics and computer engineering from the School of Electrical Engineering, Hanyang University, Seoul, Rep. of Korea, in 2011 and his MS and PhD degrees in electronics and computer engineering from Hanyang University, in 2015. His main research interests are indoor wireless communication SoC design for ranging and positioning; location estimation algorithms; two-way ranging protocols; and timing and frequency synchronization of chirp signals.
Corresponding Author jchong@hanyang.ac.kr
Jong-Wha Chong received his BS and MS degrees in electronics engineering from Hanyang University, Seoul, Rep. of Korea, in 1975 and 1979, respectively, and his PhD degree in electronics and communication engineering from Waseda University, Tokyo, Japan, in 1981. Since 1981, he has been with the Department of Electronic Engineering, Hanyang University, where he is now a professor. His main research interests are SoC design methodology; memory-centric design and physical design automation of 3D-ICs; indoor wireless communication SoC design for ranging and location; and video systems and power IT systems.

Location estimation
;
time of arrival
;
TOA
;
wireless localization
;
non-line-of-sight
;
NLOS
;
BS selection
;
wireless sensor networks

I. Introduction

In recent years, the location awareness systems of wireless devices have received a great deal of interest in many wireless systems such as cellular networks, wireless local area systems, ad hoc networks, and wireless sensor networks (WSNs). For example, location information–based services, which are widely utilized for location-based social networking systems, emergency 911 (E-911), shopping malls, and welfare facilities, have improved the quality of life for the foreseeable future. However, in indoor environments, a global positioning system signal, which is widely used for real-time locating systems (RTLS), is not available. Recently, in WSNs, many localization systems have utilized the received signal strength indicator, time of arrival (TOA), time difference of arrival (TDOA), and angle of arrival methods in
[1]
.
In TOA-based localization techniques, a base station (BS) measures the delay time of the signal propagation from a mobile device (from hereon in, we refer to this as
II. System Model in Wireless Localization

- 1. TOA-Based Ranging System

The TOA-based ranging system utilizes the propagation delay of the transmitted signal,
PPT Slide

Lager Image

- 2. TOA-Based Location Estimation

To describe the TOA-based localization scenario
[5]
, we consider a two-dimensional (2-D) network that consists of
d ^ i

, from the
σ i 2

)is the AWGN with variance
σ i 2

. The NLOS error bias
PPT Slide

Lager Image

III. Wireless Localization Techniques

- 1. Matrix Representation in TOA Measurements

To determine the location of an MS in TOA-based localization, we model the nonlinear equations of the TOA circles using
PPT Slide

Lager Image

- 2. Nonlinear Least Squares (NLS) Technique

In WSNs, the NLS technique
[15]
is a well-known localization method for estimating the MS’s location. The object of NLS is to seek the coordinate value of the MS’s location, which estimates the minimized value of the difference between the measured distance and the true distance (that is, distance error), and can be expressed as
d ^ i

is the measured distance,
σ i 2

, where
σ i 2

is denoted by
- 3. Centroid Method Using Center of Gravity Technique

The centroid method for wireless localization is a location estimation technique that uses the center of gravity of the intersection coordinates of the TOA circles, and is concretely explained in
[18]
–
[19]
. As illustrated in
Fig. 4
, we simply describe the centroid method in TOA-based 2-D localization.
In
Fig. 4
, the measured distances between the MS and the three BSs are briefly drawn, and then the intersection-coordinates are marked using TOA circles. In wireless localization, if the TOA measurements are LOS or noiseless environments, then the TOA circles will intersect at a unique point, as illustrated in
Fig. 3(a)
. However, in NLOS or indoor environments, the MS is located within the intersection region of all of the TOA circles (that is, the region within points A, B, and C, as shown in
Fig. 4
). To accurately estimate the MS’s location within the intersection region, the centroid method uses the center of gravity of the intersection of the TOA circles in
[18]
–
[19]
. As described in
[20]
, the MS’s location is estimated so that the geometric dilution of precision (GDOP) value is minimized at the center of gravity of the intersection region.
PPT Slide

Lager Image

- 4. Least Median Squares (LMS) Technique

In wireless localization for NLOS environments, an LMS technique, which is one of the most widely used fitting algorithms, is presented for NLOS mitigation. In
[21]
, the LMS presents a less complex implementation that chooses the solution of the smallest median between the measured distance
d ^ i

and the true distance
IV. BS Selection Scheme in WSNs

- 1. Computation of Length of Chords between TOA Circles

As shown in
Figs. 2
and
3
, in the 2-D space, three TOA measurements are drawn depicting the measured distances from the BSs to the MS. According to a geometric principle, two circles, for which the sum of the radii of the two circles is larger than the distance between the centers of the two circles (that is, the locations of two BSs) will meet at two intersection points. The intersection points among circles can be calculated using the data of the measured distances and the location of one of the BSs. In this section, the goal is to describe the relationship between the NLOS errors and the chords within the TOA circles, and to obtain the solution process for finding the length of a chord using the mathematical calculations written in the Appendices. As described in
Fig. 5
, we briefly depict the transformation process associated with NLOS errors. Because of the presence of NLOS errors, the intersection for the MS’s estimated location is relocated from the true MS location. As a result, the length between the intersections of two circles becomes transformed, as shown in
Fig. 5
. The difference in the length of the line between the intersections of the two circles, which is called a chord, has occurred in response to the location estimation error.
PPT Slide

Lager Image

d ^ i

for TOA-based location estimation. For example, as described in the Appendices, using a BS’s location and a straight line through the intersection between the circles BS1 and BS2, the distance from a BS’s location to a straight line can be calculated as
d ˜

and the measured distance
d ^

, and is expressed as follows:
PPT Slide

Lager Image

- 2. BS Selection Scheme Using Length of Chords

The TOA-based localization system is fundamentally utilized by three BSs. In WSNs, three or more BSs are installed to improve the localization performance and to estimate the location of the MS in an extensive area. However, to precisely estimate the MS’s location in NLOS environments, it is necessary to propose an optimal localization method that uses the BS selection scheme in
[22]
. In WSNs, generally speaking, the localization accuracy is not necessarily better when more BSs are used, because it is difficult to judge the NLOS or LOS environments between the fixed BSs and the MS. Therefore, it is necessary to utilize location estimation with three selected BSs, which reduces the effect of NLOS errors in wireless localization. Then, we can minimize the estimation error of the MS with the localization system by using three BSs with fewer NLOS errors. In Section IV-1, the core idea is to find the lengths of the chords, because they are related to the MS’s location with NLOS errors. That is, if the sum of the lengths of the chords is computed to have a minimum value, then the NLOS error of the TOA-based location estimation would become minimized, which moves toward the MS’s true location. By utilizing both the lengths of the chords and the measured distance, we present an efficient localization method that has more than three BSs in WSNs.
First, to utilize improved localization with BS selection, the measured distance is calculated by TOA measurements among the BSs and the MS. Then, the length values of the chords are computed by a combination of three BSs. Using the combination that includes the three BSs, the sum of the lengths of the chords made by the TOA measurements is computed, and is denoted by
PPT Slide

Lager Image

Efficient localization scheme algorithm.

Algorithm | Location estimation method with BS selection |
---|---|

To utilize the proposed localization method, TOA measurements among the BSs and the MS are performed in WSNs, and then the BS selection scheme is conducted. _{i}_{N}C_{3}) // C is combination operator |

V. Experimental Results

In this section, to verify the performance of the proposed method, we used the chirp spread spectrum (CSS)–based WSN system developed in
[23]
–
[24]
. We conducted an experiment with six fixed BSs in an underground parking lot and a gymnasium with interference and multipath environments. Then, we conducted location estimation experiments from several MS locations in experimental conditions. The distance between the BS and the MS is calculated using SDS-TWR
[4]
,
[11]
. The results of the TOA measurements were sent to a server computer, which calculated the location of the MS using the localization techniques.
- 1. Gymnasium with Interference and Multipath

The verification of the location estimation was performed in a 36 m × 22 m gymnasium with the presence of interference and multipath, as shown in
Fig. 8
. For the simulation test of the localization system, we placed six BSs at locations with coordinate values [1.5, 1.1]
x ^

, using the localization techniques in Section IV, and it is expressed by
PPT Slide

Lager Image

PPT Slide

Lager Image

Comparison of estimation error between localization methods and proposed method in gymnasium.

Localization | Method | Coordinates of MS’s location | ||
---|---|---|---|---|

(7.9, 6) | (19.1, 10.5) | (27.8, 15) | ||

NLS | 7.7550 m | 9.5970 m | 6.9895 m | |

Prop | 3.3148 m | 4.0264 m | 3.3469 m | |

WLS | 4.3419 m | 4.9746 m | 3.8681 m | |

Prop | 1.3498 m | 2.3314 m | 0.8422 m | |

Centroid | 6.2087 m | 6.8934 m | 4.5639 m | |

Prop | 3.7009 m | 4.6961 m | 4.1665 m | |

LMS | 4.1254 m | 6.0652 m | 4.3708 m | |

Prop | 2.0482 m | 1.7698 m | 1.3113 m |

- 2. Underground Parking Lot with NLOS Errors, Interference, and Multipath

The experimental tests were conducted in a 110 m × 40 m parking lot with NLOS errors, interference, and multipath, as shown in
Fig. 10
. Since a steel frame, car, and wall are present, the parking lot is a more realistic environment than the gymnasium. The base stations, which used 2.4 GHz for telecommunications, were already installed in the underground parking lot for mobile phone communication. Our wireless devices
[25]
, based on CSS
[23]
–
[24]
, could be influenced by interference from the 2.4 GHz devices
[26]
. To compare the location estimation methods, we installed our BSs at locations with coordinate values [10.52, 11.5]
PPT Slide

Lager Image

Comparison of estimation error between localization methods and proposed method for parking lot.

Localization | Method | Coordinates of MS’s location | ||
---|---|---|---|---|

(30.2, 19.7) | (56.2, 19.7) | (72.8, 19.7) | ||

NLS | 6.1167 m | 6.3203 m | 6.5906 m | |

Prop | 3.1436 m | 3.2472 m | 3.3947 m | |

WLS | 4.0583 m | 5.4701 m | 4.0472 m | |

Prop | 2.5877 m | 2.8870 m | 2.9375 m | |

Centroid | 4.5410 m | 4.7639 m | 4.4939 m | |

Prop | 2.5038 m | 3.0313 m | 2.1483 m | |

LMS | 5.6071 m | 7.6874 m | 5.5236 m | |

Prop | 2.7037 m | 2.6040 m | 2.7142 m |

PPT Slide

Lager Image

VI. Conclusion

Accurate estimation of an MS location using wireless localization is difficult due to the presence of NLOS errors. Because of this, several localization methods have been studied for WSNs. In this paper, we present an effective TOA-based localization method using BS selection in wireless localization. We focus on a TOA-based localization method that has an added selection scheme — one that uses three BSs with fewer NLOS errors — to improve the localization performance. In WSNs, three or more BSs are installed to accurately estimate the MS for wireless localization. We select three optimal BSs with fewer NLOS errors between the BSs and the MS to improve the performance of the localization system. This localization method with the BS selection scheme has been implemented to optimize localization for WSNs. To validate the proposed method, we performed localization experiments using a CSS-based WSN system for wireless localization. As a result, the performance analysis shows that the localization estimation error is reduced.
Appendix

- 1. Straight Line through Intersection of Two Circles

The set of points whose distance to the center is a radius is a circle in
[27]
. Two circles of radii
X= x 1 2 + x 2 2

,
Y= y 1 2 + y 2 2

, and
R= r 1 2 + r 2 2

.
- 2. Distance: Point to Plane (Line) in Two Dimensions

In vector space, the distance from a point E = (
d=∥ EQ ¯ ∥

is the length of the projection of
v= RE →

(the vector from R to E) onto
PPT Slide

Lager Image

BIO

Kupper A.
2005
“Location-Based Services: Fundamentals and Operation,”
Wiley
New York, NY, USA
121 -
154

Chan Y.-T.
2006
“Time-of-Arrival Based Localization under NLOS Conditions,”
IEEE Trans. Veh. Technol.
55
(1)
17 -
24
** DOI : 10.1109/TVT.2005.861207**

Jiang Y.
,
Leung V.C.M.
“An Asymmetric Double Sided Two-Way Ranging for Crystal Offset,”
Int. Symp. Signals, Syst. Electron.
Montreal, Germany
July 30–Aug. 2, 2007
525 -
528

Xing L.J.
,
Zhiwei L.
,
Shin F.C.P.
“Symmetric Double Side Two Way Ranging with Unequal Reply Time,”
IEEE Veh. Technol. Conf.
Baltimore, MD, USA
Sept. 30–Oct. 3, 2007
1980 -
1983

Guvenc I.
,
Chong C.-C.
2009
“A Survey on TOA Based Wireless Localization and NLOS Mitigation Techniques,”
IEEE Commun. Surveys Tutorials
11
(3)
107 -
124
** DOI : 10.1109/SURV.2009.090308**

Sayed A.H.
,
Tarighat A.
,
Khajehnouri N.
2005
“Network-Based Wireless Location: Challenges Faced in Developing Techniques for Accurate Wireless Location Information,”
IEEE Signal Process. Mag.
22
(4)
24 -
40
** DOI : 10.1109/MSP.2005.1458275**

Gezici S.
2005
“Localization via Ultra-wideband Radios: A Look at Positioning Aspects for Future Sensor Networks,”
IEEE Signal Process. Mag.
22
(c22)
70 -
84

Go S.
,
Kim S.
,
Chong J.
2014
“An Efficient Non-line-of-Sight Error Mitigation Method for TOA Measurement in Indoor Environments,”
Proc. Int. Conf. Ubiquitous Inform. Manag. Commun.
(72)

Ahn H.-S.
,
Hur H.
,
Choi W.-S.
“One-Way Ranging Technique for CSS-Based Indoor Localization,”
IEEE Int. Conf. Ind. Informat.
Daejeon, Rep. of Korea
July 13–16, 2008
1513 -
1518

Kim H.
2009
“Double-Sided Two-Way Ranging Algorithm to Reduce Ranging Time,”
IEEE Commun. Lett.
13
(7)
486 -
488
** DOI : 10.1109/LCOMM.2009.090093**

Go S.
,
Chong J.-W.
“An Efficient Ranging Protocol Using Multiple Packets for Asynchronous Real-Time Locating Systems,”
Int. Conf. Comput. Collective Intell. Technol. Appl.
Ho Chi Minh, Vietnam
Nov. 28–30, 2012
457
127 -
134

Guvenc I.
,
Chong C.-C.
,
Watanabe F.
“Analysis of a Linear Least-Squares Localization Technique in LOS and NLOS Environments,”
IEEE Veh. Technol. Conf.
Dublin, Ireland
Apr. 22–25, 2007
1886 -
1890

Cheung K.W.
2004
“Least Squares Algorithms for Time-of-Arrival-BasedMobile Location,”
IEEE Trans. Signal Process.
52
(4)
1121 -
1130
** DOI : 10.1109/TSP.2004.823465**

Chan Y.-T.
,
Hang H.Y.C.
,
Ching P.-C.
2006
“Exact and Approximate Maximum Likelihood Localization Algorithms,”
IEEE Trans. Veh. Technol.
55
(1)
10 -
16
** DOI : 10.1109/TVT.2005.861162**

Caffery J.J.
,
Stuber G.L.
1998
“Overview of Radiolocation in CDMA Cellular Systems,”
IEEE Commun. Mag.
36
(4)
38 -
45

Sieskul B.T.
,
Zheng F.
,
Kaiser T.
“Time-of-Arrival Estimation in Path Attenuation,”
IEEE Workshop Signal Process. Adv. Wireless Commun.
Perugia, Italy
June 21–24, 2009
573 -
577

Gezici S.
,
Sahinoglu Z.
2004
“UWB Geolocation Techniques for IEEE 802.15.4a Personal Area Networks,” MERL Tech. Rep.
Cambridge, MA, USA

Feng K.-T.
,
Chen C.-L.
,
Chen C.-H.
2008
“GALE: An Enhanced Geometry-Assisted Location Estimation Algorithm for NLOS Environments,”
IEEE Trans. Mobile Comput.
7
(2)
199 -
213
** DOI : 10.1109/TMC.2007.70721**

Chen C.-H.
2009
“Wireless Location Estimation with Assistance of Virtual Base Stations,”
IEEE Trans. Veh. Technol.
58
(1)
93 -
106
** DOI : 10.1109/TVT.2008.924984**

Levanon N.
2000
“Lowest GDOP in 2D Scenarios,”
IEE Proc. Radar, Sonar, Navigation
147
(3)
149 -
155
** DOI : 10.1049/ip-rsn:20000322**

Li Z.
2005
“Robust Statistical Methods for Securing Wireless Localization in Sensor Networks,”
Int. Symp. Inf. Process. Sensor Netw.
Los Angeles, CA, USA
Apr. 25–27, 2005
91 -
98

Ji Y.
“Optimal Sniffers Deployment on Wireless Indoor Localization,”
Proc. Int. Conf. Comput. Commun. Netw.
Honolulu, HI, USA
Aug. 13–16, 2007
251 -
256

2007
IEEE Std. 802.15.4a-2007, Amendment to 802.15.4-2006: Wireless Medium Access Contr. (MC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Pers. Area Networks (LR-WPANs)
Piscataway, NJ, USA

2010
ISO/IEC Std. 24730-5, Inf. Technology-Real-Time Locating Systems (RTLS)-Part 5: Chirp Spread Spectr. (CSS) at 2.4 GHz Air Interface
Geneva, Switzerland

Oh D.
,
Kwak M.
,
Chong J.-W.
2012
“A Subspace-Based Two-WayRanging System Using a Chirp Spread Spectrum Modem, Robust to Frequency Offset,”
IEEE Trans. Wireless Commun.
11
(4)
1478 -
1487
** DOI : 10.1109/TWC.2012.030512.111044**

Hur H.
,
Ahn H.-S.
2010
“A Circuit Design for Ranging Measurement Using Chirp Spread Spectrum Waveform,”
IEEE Sensors J.
10
(11)
1774 -
1778
** DOI : 10.1109/JSEN.2010.2049488**

Zwillinger D.
1996
“CRC Standard Mathematical Tables and Formulae,”
CRC Press
New York

Marsden J.E.
,
Tromba A.J.
1996
“Vector Calculus,”
Freeman & Co.
New York, USA

Citing 'Improved TOA-Based Localization Method with BS Selection Scheme for Wireless Sensor Networks
'

@article{ HJTODO_2015_v37n4_707}
,title={Improved TOA-Based Localization Method with BS Selection Scheme for Wireless Sensor Networks}
,volume={4}
, url={http://dx.doi.org/10.4218/etrij.15.0114.1251}, DOI={10.4218/etrij.15.0114.1251}
, number= {4}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Go, Seungryeol
and
Chong, Jong-Wha}
, year={2015}
, month={Aug}