Advanced
Distance Geometry-based Wireless Location Algorithms in Cellular Networks with NLOS Errors
Distance Geometry-based Wireless Location Algorithms in Cellular Networks with NLOS Errors
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jun, 9(6): 2132-2143
Copyright © 2015, Korean Society For Internet Information
  • Received : September 23, 2013
  • Accepted : May 06, 2015
  • Published : June 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Junhui Zhao
Key Lab of Broadband Wireless Communication and Sensor Network Technology (Nanjing University of Posts and Telecommunications), Ministry of Education
Hao Zhang
School of Electronics and Information Engineering, Beijing Jiaotong University Beijing 100044, China
Rong Ran
School of Electrical and Computer Engineering, Ajou University, Suwon, South Korea

Abstract
This paper presents two distance geometry-based algorithms for wireless location in cellular network systems—distance geometry filtering (DGF) and distance geometry constraint (DGC). With time-of-arrival range measurements, the DGF algorithm estimates the mobile station position by selecting a set of measurements with relatively small NLOS (non-line-of-sight) 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.
Keywords
1. Introduction
W ith the rapid development of fourth-generation mobile communication technologies, wireless location-based 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 (time-of-arrival) is a key factor. In an LOS (line-of-sight) environment, TOA measurements are only affected by measurement errors, which usually satisfy the zero-mean 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 non-negligible 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 near-optimum 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 geometry-based 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 Er ; S = { P 1 , P 2 , ⋯ , Pn }, and dij denotes the distance between points Pi and Pj . The matrix formed by dij is defined as the distance matrix of S and is defined as:
PPT Slide
Lager Image
The above matrix is also named a ‘semi-metric 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 non-degenerate.
For a semi-metric matrix D and set of ordered points, S = { P 1 , P 2 , ⋯ , Pn }, we can define a distance function as d ( Pi , Pj ) = dij (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 = { Pi , Pj , ⋯ , Pk }, 1 ≤ i j ≤ ⋯ ≤ k n . Then the m -dimensional, semi-metric matrix D ′ of S ' is defined as:
PPT Slide
Lager Image
Therefore, the square-bordered matrix of D ′ is defined as:
PPT Slide
Lager Image
with ( m + 1) dimensions; the determinant of
PPT Slide
Lager Image
is valued as Δ( i , j ,…, k )
Theorem 1: the Blumenthal embedding theorem [8] : assume that matrix D is an n × n dimensional, semi-metric matrix. The necessary and sufficient condition that it is embedded in E r and non-degenerate is shown in that, if we change the order of the elements in D , the consequential semi-metric matrix D a satisfies the following conditions:
PPT Slide
Lager Image
Condition 2: For two positive integers u 1 and u 2 satisfying r + 1 < u 1 , u 2 n , there exists
PPT Slide
Lager Image
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, semi-metric matrix. The necessary and sufficient condition that it is embedded in E 2 and non-degenerate is shown in that, after adjusting the order of the elements in D , the consequential semi-metric matrix D a satisfies the following conditions:
PPT Slide
Lager Image
Condition 2: For two positive integers u 1 and u 2 satisfying r + 1 < u 1 , u 2 n
PPT Slide
Lager Image
where
PPT Slide
Lager Image
is inevitable; ∆(1,2,3) < 0 means the first three points are not co-linear; ∆(1,2,3, u 1 ) = ∆(1,2,3, u 2 ) = ∆(1,2,3, u 1 , u 2 ) means the rank of the semi-metric, square-bordered matrix
PPT Slide
Lager Image
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
PPT Slide
Lager Image
, respectively.
PPT Slide
Lager Image
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 square-bordered matrix:
PPT Slide
Lager Image
where v refers to a signal velocity.
Similarly, for the case of 3-reference BSs, such as (O, A, B), with the ordered set of points (O, A, B, M), we can obtain the square-bordered matrix as:
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
where ( xi , yi ) 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:
PPT Slide
Lager Image
with a solution as:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
- 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 4-BS location case:
PPT Slide
Lager Image
Since practical measurements include NLOS errors, we cannot perfectly obtain Eq. (14). However, we can choose a set of measurements that minimizes
PPT Slide
Lager Image
and use the selected set of measurements to locate the MS.
In the TOA location model, the measuring equation system is given as follows:
PPT Slide
Lager Image
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
PPT Slide
Lager Image
. Substituting the coordinates of BSs (O, A, B, C) into Eq. (15), the coordinates of the MS are achieved as:
PPT Slide
Lager Image
PPT Slide
Lager Image
Schematic diagram of the TOA model
Similarly, for the 3-BS case, the corresponding filtering equation is given as:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
. Therefore, the corresponding coordinate of the MS’s position is:
PPT Slide
Lager Image
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 pseudo-code procedure is given as follows:
PPT Slide
Lager Image
The algorithm for the 3-BS 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 4-reference BSs, Eq. (14) is already obtained:
PPT Slide
Lager Image
. Because of the positive deviation due to NLOS errors, the obtained measurements can be defined as:
PPT Slide
Lager Image
where ti and εi ≥ 0 denote the actual measurement and deviation, respectively. Therefore, the constraint equation is given as:
PPT Slide
Lager Image
Thus, the measurement optimization problem is formulated as follows:
PPT Slide
Lager Image
After solving the above problem, the optimized TOA measurements are given as:
PPT Slide
Lager Image
Therefore, the optimized distance measurements are
PPT Slide
Lager Image
. By utilizing the LS (least squares) algorithm, the position coordinates can be obtained:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and ( xi , yi ) are the coordinates of the BSs, while di is the optimized distance measurement ( i = 1, 2, 3, 4 ) .
For the 3-BS case, the corresponding nonlinear optimization problem is shown as Eq. (24):
PPT Slide
Lager Image
where
PPT Slide
Lager Image
,
PPT Slide
Lager Image
.
The computing complexity of the DGC algorithm is O(n 3 ) ; however, it only requires a small number of measurements.
The pseudo-code procedure for the 4-BS case is given as follows:
PPT Slide
Lager Image
For the 3-BS 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 4-BS and 3-BS 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:
PPT Slide
Lager Image
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 near-optimal set of measurements is contained.
PPT Slide
Lager Image
Simulation results for the 4-BS location
PPT Slide
Lager Image
Simulation results for the 3-BS 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.
PPT Slide
Lager Image
Results of location error for different NLOS errors
Additionally, the DGC algorithm provides better performance for the 4-BS location than for the 3-BS 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 4-BS or 3-BS 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 square-bordered 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 near-optimum 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.
References
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/S1005-8885(10)60023-4
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 next-generation 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