This paper presents two distance geometrybased algorithms for wireless location in cellular network systems—distance geometry filtering (DGF) and distance geometry constraint (DGC). With timeofarrival range measurements, the DGF algorithm estimates the mobile station position by selecting a set of measurements with relatively small NLOS (nonlineofsight) errors, and the DGC algorithm optimizes the measurements first and then estimates the position using those optimized measurements. Simulation results show that the proposed algorithms can mitigate the impact of NLOS errors and effectively improve the accuracy of wireless location.
1. Introduction
W
ith the rapid development of fourthgeneration mobile communication technologies, wireless locationbased sevice is becoming more and more critical in cellular network systems. In order to meet the FCC’s E911 specification, wireless location technologies have attracted lots of attention and achieved many valuable results
[1

2]
. For wireless location algorithms, TOA (timeofarrival) is a key factor. In an LOS (lineofsight) environment, TOA measurements are only affected by measurement errors, which usually satisfy the zeromean Gaussian distribution. Chan and Ho proposed a TOA algorithm, named the Chan algorithm, which can improve positioning accuracy in LOS environments
[3]
. However, in NLOS environments, TOA measurments usually cause a nonnegligible deviation compared to the actual position, due to reflections and refractions from outdoor obstacles such as buildings, pedestrains, cars, etc. This deviation is referred to as NLOS errors and mainly influences the precision of the TOA location. Therefore, reducing the effect of NLOS errors is the main problem to overcome in improving the accuracy of TOA algorithms.
Zongjie and Yiquan first applied the distance geometry filtering (DGF) algorithm to ultrasonic positioning
[4]
. Junhui and Wei extended the algorithm to wireless location and achieved good performance in finding the UWB (ultra wideband) wireless location
[5]
. Zheng and colleagues used the geometric location algorithm with the randomly distributed sensor network
[6]
. However, these algorithms usually estimate NLOS errors via TOA measurements
[7]
, which means that a large number of measurements is required in order to gain a priori information regarding NLOS errors; this significantly increases computational complexity and results in the algorithm’s being impractical. Besides, achieved a priori information is not adaptive for varying environments, which also affect the accurancy of wireless location. Thus, more feasible algorithms that take NLOS errors into account are desired.
In this paper, based on the Blumenthal embedding theorem of distance geometry
[8]
, we propose two algorithms with TOA measurements for wireless location: the distance geometry filtering (DGF) algorithm and the distance geometry constraint (DGC) algorithm. Neither algorithm needs to acquire a priori information. If the number of measurements is large enough, the DGF can mitigate the effect of NLOS errors and achieve nearoptimum performance. The DGC algorithm releases the requirement regarding the quantity of measurements, which results in a slight degradation of location accuracy compared to the DGF algorithm; however, DGC still outperforms the conventional least squares (LS) algorithm for wireless location.
The remainder of this paper is divided into three sections. Section 2 introduces the theory of distance geometry; Section 3 presents distance geometrybased location algorithms in NLOS environments for cellular network systems; and Section 4 provides simulation results. Conclusions are given in Section 5.
2. Theory of Distance Geometry
Set
S
as an ordered set of points in the
r
dimensional Euclidean space
E_{r}
;
S
= {
P
_{1}
,
P
_{2}
, ⋯ ,
P_{n}
}, and
d_{ij}
denotes the distance between points
P_{i}
and
P_{j}
. The matrix formed by
d_{ij}
is defined as the distance matrix of
S
and is defined as:
The above matrix is also named a ‘semimetric matrix’. If distance matrix
A
represents the distance relation for a set of ordered points in Euclidean space E
_{r}
, we say matrix
A
is embedded in E
_{r}
. When it is embedded in E
_{r}
but not embedded in E
_{r–1}
, we say it is nondegenerate.
For a semimetric matrix
D
and set of ordered points,
S
= {
P
_{1}
,
P
_{2}
, ⋯ ,
P_{n}
}, we can define a distance function as
d
(
P_{i}
,
P_{j}
) =
d_{ij}
(1 ≤
i
,
j
≤
n
). We define another set of ordered points,
S^{′}
⊆
S
, where the total number of points in
S^{′}
is
m
(<=
n
), and the points of
S^{′}
follow the same order as that of
S
, i.e.
S^{′}
= {
P_{i}
,
P_{j}
, ⋯ ,
P_{k}
}, 1 ≤
i
≤
j
≤ ⋯ ≤
k
≤
n
. Then the
m
dimensional, semimetric matrix
D
′ of
S
' is defined as:
Therefore, the squarebordered matrix of
D
′ is defined as:
with (
m
+ 1) dimensions; the determinant of
is valued as Δ(
i
,
j
,…,
k
)
Theorem 1:
the Blumenthal embedding theorem
[8]
: assume that matrix
D
is an
n
×
n
dimensional, semimetric matrix. The necessary and sufficient condition that it is embedded in E
_{r}
and nondegenerate is shown in that, if we change the order of the elements in
D
, the consequential semimetric matrix
D
_{a}
satisfies the following conditions:
Condition 2: For two positive integers
u
_{1}
and
u
_{2}
satisfying
r
+ 1 <
u
_{1}
,
u
_{2}
≤
n
, there exists
For the special case of E
_{2}
, we have the following theorem:
Theorem 2:
the Blumenthal embedding theorem: assume that matrix
D
is an
n
×
n
dimensional, semimetric matrix. The necessary and sufficient condition that it is embedded in E
_{2}
and nondegenerate is shown in that, after adjusting the order of the elements in
D
, the consequential semimetric matrix
D
_{a}
satisfies the following conditions:
Condition 2: For two positive integers
u
_{1}
and
u
_{2}
satisfying
r
+ 1 <
u
_{1}
,
u
_{2}
≤
n
where
is inevitable; ∆(1,2,3) < 0 means the first three points are not colinear; ∆(1,2,3,
u
_{1}
) = ∆(1,2,3,
u
_{2}
) = ∆(1,2,3,
u
_{1}
,
u
_{2}
) means the rank of the semimetric, squarebordered matrix
is 4.
3. Distance Geometry Location Model for Cellular Networks
Consider a cellular network system with four adjoining BSs (illustrated as
Fig. 1
), and assume that the distance between two adjacent BSs is 2a. Hence, the coordinates of four BSs (O, A, B, C) are given as
, respectively.
Schematic diagram of cellular location
Define
t
_{1}
,
t
_{2}
,
t
_{3}
and
t
_{4}
asthe time measurements from (O, A, B, C) to the MS M. According to Eq. (3), with the ordered set of points (O, A, B, M, C), we obtain the following squarebordered matrix:
where
v
refers to a signal velocity.
Similarly, for the case of 3reference BSs, such as (O, A, B), with the ordered set of points (O, A, B, M), we can obtain the squarebordered matrix as:
It is easy to verify that the above two cases both satisfy the Blumenthal embedding theorem. Consequently, matrices (8) and (9) have the same determinants when using Theorem 2.
 3.1 The Least Squares Algorithm of the TOA Model
According to the TOA estimation principle, the measurement equation is described as:
where (
x_{i}
,
y_{i}
) are the coordinates of the reference BSs, (
x
_{0}
,
y
_{0}
) are the coordinates of the MS, and
n
is the number of the BS. Ideally, the MS is located on the
k
circles, with the BS positioned in the centre and the distance as the radius. However, due to NLOS errors,
k
circles cannot intersect at one point. After letting each of the two equations subtract, we can obtain the following equation:
with a solution as:
where
 3.2 Distance Geometry Filtering Algorithm
If multiple sets of measurements are available, there must be one set with the least error compared to the actual value in LOS environments. The DGF algorithm is applied to achieve the best set of measurements for locating the MS.
According to condition 2 of the Blumenthal embedding theorem, we can obtain Eq. (14) for the 4BS location case:
Since practical measurements include NLOS errors, we cannot perfectly obtain Eq. (14). However, we can choose a set of measurements that minimizes
and use the selected set of measurements to locate the MS.
In the TOA location model, the measuring equation system is given as follows:
Choose any three circles and subtract for two equations of the three. Three lines can then be obtained that intersect at one point (as shown in
Fig. 2
). We can obtain four points for four location circles, (
x
_{M1}
,
y
_{M1}
), (
x
_{M2}
,
y
_{M2}
), (
x
_{M3}
,
y
_{M3}
), (
x
_{M4}
,
y
_{M4}
); according to the centroid localization algorithm, the position of the MS is then
. Substituting the coordinates of BSs (O, A, B, C) into Eq. (15), the coordinates of the MS are achieved as:
Schematic diagram of the TOA model
Similarly, for the 3BS case, the corresponding filtering equation is given as:
where
. Therefore, the corresponding coordinate of the MS’s position is:
The computing complexity of the DGF algorithm is formulated as O(n) . However, a large number of measurements is required to guarantee that the best measurements are contained.
The pseudocode procedure is given as follows:
The algorithm for the 3BS case can be obtained by applying (17) and (18) to Step 2 and Step 10, respectively.
 3.3 Distance Geometry Constraint Algorithm
Considering that measurements with NLOS errors may cause a positive deviation compared to those representing the actual position of an MS, the distance geometry constraint algorithm is proposed to correct the deviation using the constraint relation.
For the case of 4reference BSs, Eq. (14) is already obtained:
. Because of the positive deviation due to NLOS errors, the obtained measurements can be defined as:
where
t_{i}
and
ε_{i}
≥ 0 denote the actual measurement and deviation, respectively. Therefore, the constraint equation is given as:
Thus, the measurement optimization problem is formulated as follows:
After solving the above problem, the optimized TOA measurements are given as:
Therefore, the optimized distance measurements are
. By utilizing the LS (least squares) algorithm, the position coordinates can be obtained:
where
and (
x_{i}
,
y_{i}
) are the coordinates of the BSs, while
d_{i}
is the optimized distance measurement (
i
= 1, 2, 3, 4 ) .
For the 3BS case, the corresponding nonlinear optimization problem is shown as Eq. (24):
where
,
.
The computing complexity of the DGC algorithm is O(n
^{3}
) ; however, it only requires a small number of measurements.
The pseudocode procedure for the 4BS case is given as follows:
For the 3BS case, the algorithm is obtained by substituting Eq. (24) for Eq. (21) in Step 2.
4. Simulation Results
We assume that the BSs are located as shown in
Fig. 1
in a cellular network system. Therefore, a rhombus shape and triangle shape are used to illustrate the 4BS and 3BS locations, respectively. In the simulation experiment, we assume that the distance between two adjoining BSs is 1000 m and that the average NLOS error is 250 m. The LS algorithm is also simulated as a baseline for comparison, and the mean square error of position locating through the algorithms is calculated using the following equation:
where (
x
_{0}
,
y
_{0}
) represent the coordinates of the MS’s position, and (
x
,
y
) represent the estimated coordinates.
From
Figs. 3
and
4
, we observe that, compared to the LS algorithm, both DGF and DGC algorithms can mitigate the effect of NLOS errors and provide more precise results. We also notice that the DGF algorithm outperforms the DGC because the DGC cannot provide a perfect estimation of the deviation due to a nonlinear optimization process; thus, a relatively large deviation still remains. Therefore, the effect of NLOS errors cannot be significantly mitigated using the DGC algorithm. However, that algorithm only requires a small number of measurements and can thus be applied when the number of both the NLOS errors and BSs are small. On the other hand, the DGF algorithm performs well but needs a large number of measurements to guarantee that the nearoptimal set of measurements is contained.
Simulation results for the 4BS location
Simulation results for the 3BS location
Fig. 5
compares RMSE in terms of NLOS errors for DGF, DGC and LS. We notice that the performance of the DGC decreases as the NLOS increases, which is similar to other existing algorithms (such as the Taylor and Chan algorithms), whereas the performance of the DGF is little impacted by the number of NLOS errors. The number NLOS errors has little impact on DGF because no matter how large the error is, the DGF always tries to find the measurement set that best approaches the actual one (which is why the number of measurement sets must be as large as possible). Consequently, DGF’s performance degradation due to increasing NLOS errors is negligeable.
Results of location error for different NLOS errors
Additionally, the DGC algorithm provides better performance for the 4BS location than for the 3BS location because more measurements are available for a larger number of reference BSs. Meanwhile, since a set of measurements with small NLOS errors is almost sure for either the 4BS or 3BS case, the DGF is barely sensitive to the number of BSs.
5. Conclusion
This paper proposes the distance geometry filtering (DGF) algorithm and the distance geometry constraint (DGC) algorithm for wireless location. According to the Blumenthal embedding theorem, the wireless location is described as two different optimization problems. The DGF algorithm is applied to solve an optimization problem that minimizes the determinant of the squarebordered matrix representing the geometry distance relation of a cellular system. The DGF algorithm is equivalent to selecting one set of measurements with a small number of NLOS errors and using that selected set to estimate the MS position; it thus provides nearoptimum performance provided the number of available measurements is large enough. When a limited number of measurements is available, the DGC first optimizes the measurement set such that it better approaches the actual set, and then estimates the MS position via the adjusted measurements. Since the DGC algorithm is applied to solve a nonlinear optimization problem, the optimal solution is usually not achievable, which leads to the degradation of wireless location accuracy compared to that achieved by the DGF. However, both algorithms outperform the LS algorithm.
BIO
Junhui Zhao received his M.E. and Ph.D. in Electrical Engineering from Southeast University, China, in 1998 and 2004, respectively. He was a visiting scholar in Yonsei University and Nanyang Technological University in 2004 and 2013 separately. From 2004 to 2008, he was an associate professor at Macau University of Science and Technology, Macau, China. He is currently a professor at the school of Electronics & Information, Beijing Jiaotong University, China. His research interests include cognitive radio and wireless localization.
Hao Zhang was born in 1988. He is a graduate student of Beijing Jiaotong University. His research area is wireless indoor location theory and wireless communication system.
Ran Rong received her M.E. and Ph.D. degrees from Chonbuk National University and Yonsei University, South Korea, in 2004 and 2009, respectively. From 2009 to 2010, she was a senior researcher at the Electronics & Telecommunication Research Institute (ETRI), South Korea, working on IEEE 802.16m standardization. She was a research associate in HKUST from 2010 to 2011, and is currently an assistant professor at the School of Electrical and Computer Engineering, Ajou University. Her research interests include massive MIMO, compressive sensing, and cognitive radio.
Chen P.C.
1999
“Mobile position location estimation in cellular systems,”
Martin H.
,
Rudolf M.
,
Markus S.
1997
“Estimating position and velocity of mobiles in a cellular radio network,”
IEEE Transactions on Vehicular Technology
2
(1)
65 
71
Chan Y.T.
,
Ho K.C.
1994
“A simple and efficient estimator for hyperbolic location,”
IEEE Transactions on Signal Processing
42
(8)
1905 
1915
DOI : 10.1109/78.301830
Zongjie L.
,
Yiquan Y.
1996
“Geometric constraints and data processing in acoustic location technique,”
Chinese Journal of Sensors and Actuators
1
19 
26
Junhui Z.
,
Wei Y.
2011
“Distance geometric constraint filtering algorithm and its application in UWB location,”
The Journal of China Universities of Posts and Telecommunications
18
(1)
23 
27
DOI : 10.1016/S10058885(10)600234
Zheng J.
,
Chengdong W.
,
Chu H.
,
Ji P.
“Localization Algorithm Based on RSSI and Distance Geometry Constrain for Wireless Sensor Network,”
in Proc. of 2010 International Conference on Electrical and Control Engineering (ICECE)
2010
2836 
2839
Mazuelas S.
,
Lago F.A.
,
Blas J.
,
Bahillo A.
,
Fernandez P.
,
Lorenzo R.M.
,
Abril E.J.
2009
“Prior NLOS Measurement Correction for Positioning in Cellular Wireless Networks,”
IEEE Transactions on Vehicular Technology
58
(5)
2585 
2591
DOI : 10.1109/TVT.2008.2009305
Havel T.F.
,
Kuntz I.D.
,
Crippen G.M.
1983
“The theory and practice of distance geometry,”
Bulletin of Mathematical Biology
45
(5)
665 
720
DOI : 10.1007/BF02460044
Ziming H.
,
Abdullah A.
,
Yi M.
,
Rahim T.
2013
“A Cooperative Positioning Algorithm in Cellular Networks with Hearability Problem,”
Wireless Communications Letters
2
(1)
66 
69
DOI : 10.1109/WCL.2012.102512.120663
Kay S.
,
Vankayalapati N.
2013
“Improvement of TDOA Position Fixing Using the Likelihood Curvature’
IEEE Transactions on Signal Processing
61
(8)
1910 
1914
DOI : 10.1109/TSP.2013.2246154
Yi Heng Z.
,
Hao Z.
,
Jie Z.
2011
“Wireless cooperative localization in the nextgeneration mobile communication system,”
Journal of Beijing University of Posts and Telecommunications
34
(1)
126 
129
Yi M. Y.
,
Yuan L. M.
,
Jun Z. B.
2009
“A TOA/AOA Location Algorithm in NLOS Environment,”
Journal of Electronics & Information Technology
31
(1)
37 
40