Advanced
Hybrid Linear Closed-Form Solution in Wireless Localization
Hybrid Linear Closed-Form Solution in Wireless Localization
ETRI Journal. 2015. Jun, 37(3): 533-540
Copyright © 2015, Electronics and Telecommunications Research Institute (ETRI)
  • Received : March 28, 2014
  • Accepted : March 19, 2015
  • Published : June 01, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Seong Yun Cho

Abstract
In wireless localization, several linear closed-form solution (LCS) methods have been investigated as a direct result of the drawbacks that plague the existing iterative methods, such as the local minimum problem and heavy computational burden. Among the known LCS methods, both the direct solution method and the difference of squared range measurements method are considered in this paper. These LCS methods do not have any of the aforementioned problems that occur in the existing iterative methods. However, each LCS method does have its own individual error property. In this paper, a hybrid LCS method is presented to reduce these errors. The hybrid LCS method integrates the two aforementioned LCS methods by using two check points that give important information on the probability of occurrence of each LCS’s individual error. The results of several Monte Carlo simulations show that the proposed method has a good performance. The solutions provided by the proposed method are accurate and reliable. The solutions do not have serious errors such as those that occur in the conventional standalone LCS and iterative methods.
Keywords
I. Introduction
Ranging measurements–based localization methods have been widely used for global positioning systems/global navigation satellite systems and wireless localization systems [1] [4] . In general, model-free localization algorithms can be divided into the following two categories: iterative methods and linear closed-form solution (LCS) methods [4] [16] .
Iterative methods yield an approximated solution using a linearized range error equation obtained by a first-order Taylor series–based linearization of a nonlinear range equation. In such methods, a local minimum problem may occur due to the large error of the first nominal point for linearizing a nonlinear range equation [4] , [15] . To overcome the local minimum problem, a proper additional algorithm has to be used in conjunction with an iterative method [4] . However, such an iterative method will then have a large computational burden due to both the iterative process and the aforementioned required proper additional algorithm [15] .
LCS methods are free from the problems that occur in the iterative methods. This is why it is preferable to use an LCS method as opposed to an iterative method even though the iterative method can provide a more accurate solution in general. Several LCS methods have been investigated. The three most representative examples of these are the direct solution (DS) method [8] [9] , the range-difference method [10] [14] , and the difference of squared range measurements (DSRM) method [15] .
In [15] , it was shown that the DSRM method is equivalent to the range-difference method. Therefore, the DS and DSRM methods are considered in this paper. The two methods use squared range measurements to remove a square root from a range equation. In this process, the DS method neglects measurement noise [9] , whereas the DSRM method does not [15] .
The DS method calculates two candidate solutions and selects the better one based on the measurement residual comparison [9] . If the number of reference nodes whose locations are known is larger than or equal to three, then a candidate selection is reasonable. However, the DS method has an ill-conditioning problem; namely, the red sea zone problem [15] . The problem occurs in a special zone where the result of taking a square root in a quadratic formula is a value near zero or a complex number. In this zone, both candidate solutions spread out on both sides of a true solution. That is, the solutions of the DS method have comparatively large errors. The DSRM method uses difference values of squared range measurements to remove quadratic terms from the squared range measurement equation. If the reference nodes are located well around the mobile node to be localized, then the estimated solution may be accurate. If the mobile node is far from a cluster of reference nodes, however, then the localization error may be large. Taken together, each LCS method has an individual problem and each problem has its own unique error property. To avoid the problems of the two LCS methods considered in this paper and to provide accurate/reliable solutions, a hybrid LCS method is presented. In this method, two check points predicting the problem occurrence are analyzed first. Then, the solutions of the two standalone LCS methods are integrated based on the check points. To evaluate the performance of the presented method, several Monte Carlo simulations are carried out. The simulation results show that the hybrid solution method has better performance than the conventional standalone methods irrespective of the relative locations of the mobile node and reference nodes.
This paper is structured as follows. In Section II, two conventional LCS methods and problems are described. In Section III, a hybrid LCS solution method is presented, and simulation results are analyzed to validate the performance of the proposed method in Section IV. Conclusions will be given in the last section.
II. Two Conventional LCS Methods and Problem Description
Using the Euclidean distance measurement, the following basic 2D range equation is formulated:
d ˜ i,m = d i,m + w i,m = ( x j x m ) 2 + ( y i y m ) 2 + w i,m ,
where di, m is the true range between reference node i and mobile node m ,
( ⋅ ˜ )
is the measurement of (·), ( xi , yi ) and ( xm , ym ) are location data of the reference node i and mobile node m , respectively, and wi,m is the measurement noise, which is assumed as a zero-mean stationary Gaussian random process.
Actually, the measured range data contains non-Gaussian errors caused by multipath and non-line-of-sight signals. However, such errors are ignored in this paper, because it is assumed that they are compensated for in the signal processing step. If the range is measured using the IEEE 802.15.4a standard–based impulse radio ultra-wideband (IR-UWB), then the multipath and non-line-of-sight errors can be eliminated [17] [18] . To estimate the location of the mobile node in this equation, two conventional LCS methods are described and problems of the solutions are defined.
- 1. DS Method
The DS method is one of many widely used LCS methods [7] [8] . The DS method can be summarized as follows [15] :
[ x ̂ m (k) y ̂ m (k) ] DS =L( R a + R b b+ (1) k b 2 4ac 2a ),
where k ∈ {1, 2},
L= ( H T H) 1 H T ,
H=[ 2 x 1 2 y 1 2 x n 2 y n ],
R a =[ d ˜ 1,m 2 ( x 1 2 + y 1 2 ) d ˜ n,m 2 ( x n 2 + y n 2 ) ],
R b = [ 1 1 n ]T ,
a= (L R b ) T (L R b ),
b=2 (L R a ) T (L R b )1,
and
c  =    (L R a ) T (L R a ).
In the above equations, n is the number of reference nodes that are connected to the mobile node; n ≥ 3.
One of two candidate solutions in (2) is the exact solution, whose residual will be smaller than that of the other candidate solution. The residuals are calculated, using the candidate solutions, as follows:
res(k)= 1 n i=1 n ( d ˜ i,m ( x i x ̂ m (k) ) 2 + ( y i y ̂ m (k) ) 2 ) 2 .
However, there may be an abnormal case; for example, where two candidate solutions exist on both sides of the true location. In this case, both candidate solutions have relatively large errors. The abnormal case occurs in a special zone; namely, the red sea zone, in the application area [15] . In the special zone, a square root in the quadratic formula is near zero or a complex number.
- 2. DSRM Method
The solution of the DSRM method can be summarized as follows [15] :
[ x ̂ m y ̂ m ] DSRM = ( G T Q 1 G) 1 G T Q 1 Z,
where
G=[ x c x 1 y c y 1 x c x n1 y c y n1 ],
Z= [ ρ 1,c ρ n1,c ] T ,
and
Q=E{ V V T } = σ w 2 [ d ˜ 1,m 2 + d ˜ c,m 2 d ˜ c,m 2 d ˜ c,m 2 d ˜ c,m 2 d ˜ 2,m 2 + d ˜ c,m 2 d ˜ c,m 2 d ˜ c,m 2 d ˜ c,m 2 d ˜ n1,m 2 + d ˜ c,m 2 ].
In the equations above, ( xc , yc ) is the location of the common reference node (selected from reference nodes) and
ρ i,c = d ˜ i,m 2 d ˜ c,m 2 ( x i 2 + y i 2 )+( x c 2 + y c 2 ) 2 ,
V=[ ( d 1,m w 1,m d c,m w c,m )+( w 1,m 2 w c,m 2 )/2 ( d n1,m w n1,m d c,m w c,m )+( w n1,m 2 w c,m 2 )/2 ],
where σw is the standard deviation of the range measurement errors and
d ˜
is used instead of d .
In the DSRM method, the red sea zone does not exist. However, if the mobile node is far from a cluster of reference nodes, then the localization error may increase because the measurement noise is multiplied by the distance between the reference node and mobile node, as shown in (16).
III. Hybrid LCS
Each of the two standalone LCS methods has its own individual problem, as mentioned above. In this work, a hybrid LCS method is presented to avoid these problems. To design the hybrid LCS method, the conditions causing the problems are analyzed first.
In the DS method, the calculation of the square root in (2) may cause the red sea zone problem. Let’s consider Fig. 1 . First, it is assumed that there are only two reference nodes, node 1 and node 2. In this case, the following phenomenon occurs in (2):
{ b 2 4ac=0 b 2 4ac<0        when  δ=0,    when  δ<0,
where
δ= i=1 n d ˜ i,m i=1 n d i,m .
PPT Slide
Lager Image
Two examples of localization with DS method.
The first condition can provide an exact solution. However, this condition may not occur in real environments. The second condition causes two imaginary candidate solutions, because the two circles do not meet. That is, the red sea zone problem occurs.
Second, it is assumed that there are four reference nodes. In this case, if δ ≤ 0, then the red sea zone problem occurs. Moreover, the red sea zone problem may occur in the case of δ ≈ 0. In the case of Fig. 1 , δ = 0.20873, and the value of b 2 – 4 ac becomes 4.04710E-4. When the mobile node is at this location, the DS method cannot provide an exact solution. Consequently, we can judge whether the red sea zone problem occurs based on the value of b 2 – 4 ac .
Remark 1 . The smaller the value of ( b 2 – 4 ac ) DS is, the more likely the red sea zone problem is to occur.
In the DSRM method, there is an index for analyzing the location error. That is, a dilution of precision (DOP) value. DOP is calculated as follows:
DOP DSRM = trace( ( G T Q 1 G) 1 ) .
Remark 2 . The larger the DOP value is, the larger the location error is.
From these remarks, it is possible to predict the possibility of the occurrence of the red sea zone problem in the DS method and the location error caused in the DSRM method. Based on this information, the following hybrid method can be designed:
[ x ̂ m y ̂ m ] H = w DS w DS + w DSRM [ x ̂ m y ̂ m ] DS                           + w DSRM w DS + w DSRM [ x ̂ m y ̂ m ] DSRM ,
where
w DS = w 1 ( b 2 4ac) DS ,
w DSRM = w 2 1 DOP DSRM ,
where w 1 and w 2 are scaling parameters.
The scaling parameters are related to the shape of the red sea zone and the distribution of DOP. So, the scaling parameters are decided in consideration of these facts and the geometric distribution of the reference nodes. The scaling parameters are adjusted in such a way as to ensure that a complementary relation between w DS and w DSRM exists. That is, the red sea zone in the DS method must be covered with a zone where the DOP values in the DSRM method are good for accurate localization. To achieve this, two check points, ( b 2 – 4 ac ) DS and 1/DOP DSRM , are analyzed in the application area. Then, the scaling parameters are decided using a trial-and-error method.
IV. Simulation Results and Analysis
This section presents several Monte Carlo simulation results comparing the statistical performance of the proposed hybrid solution with those of the two conventional standalone solutions in the presence of noise. The measurement noise is set as white Gaussian noise because it is assumed that IR-UWB is used for measuring the ranges. Simulation is performed in Matlab. For a quantitative analysis, three scenarios that have different geometry distributions of reference nodes are used. The different geometry distributions of reference nodes change the red sea zone in the DS method and DOP in the DSRM method. In these scenarios, the same application area is set as (0.0 m, 0.0 m, 100.0 m, 100.0 m); it is assumed that a mobile node is located in this area. The standard deviation of the range measurement noise is set equal to 0.33 m in response to the specification of the IR-UWB signal. For the Monte Carlo simulations, 44,100 (441 points × 100 times) ensembles of localization solutions are generated. The following remarks are presented to address analytic views from the simulation results.
Remark for scenario 1 . In this scenario, it is assumed that three reference nodes are located at (1.0 m, 1.0 m), (1.0 m, 70.0 m), and (100.0 m, 100.0 m), respectively. Figures 2 and 3 show the localization results for scenario 1. In Fig. 2 , upper-left, lower-left, and upper-right plots denote locations estimated by the DS method, DSRM method, and hybrid method, respectively. In Fig. 3 , the left three plots denote location errors of the three localization methods, and the right three plots denote check point 1, check point 2, and weighting, respectively. As shown in Figs. 2 and 3 , the DS method has a red sea zone on the diagonal area connecting reference node 2 and reference node 3. In this zone, two candidate solutions are located on both sides of a true location [15] . Therefore, accurate solutions cannot be estimated in this zone using the DS method. In the results of the DSRM method, it can be seen that there is no critical area causing large estimation errors, such as the red sea zone in the DS method. On the right side of the application area, however, the estimation errors increase from the left side because the mobile node is far from a cluster of reference nodes.
To fuse the results of the DS and DSRM methods, two scaling parameters are set through simulations first. In Fig. 3 , it can be understood that the smaller a check point is, the larger the estimation error is. Based on the two aforementioned check points, the scaling parameters, w 1 and w 2 , are set equal to 10.0 and 1.0, respectively. Then, it can be confirmed by the weighting figure that the good area of the DSRM method can cover the bad area of the DS method. Based on the weighting from (20)–(22), the hybrid method is processed. It can be seen from the results in Fig. 2 that the location errors caused in the DSRM method in the lower-right area are compensated. However, it can be seen that the location errors in the upper-right area are similar to the DSRM method. The reason is that both standalone methods each yield large location errors. The lower-right plot in Fig. 2 denotes the error probabilities of the three methods, and Table 1 denotes the localization errors. Consequently, it can be stated that the proposed hybrid method has a good performance, which is a result of combining the advantages of the two standalone methods it employs.
PPT Slide
Lager Image
Localization results of scenario 1.
PPT Slide
Lager Image
Location error and check points of scenario 1.
Remark for scenario 2 . In this scenario, it is assumed that four reference nodes are located at (1.0 m, 1.0 m), (1.0 m, 100.0 m), (70.0 m, 1.0 m), and (30.0 m, 100.0 m), respectively. Figures 4 and 5 show the localization results of scenario 2. As shown in the results of the DS method, a red sea zone exists on a straight line and its environs. This causes large localization errors, as can be seen in the upper-left plot of Fig. 5 . From the results of the DSRM method, it can be known that the further mobile nodes are away from a cluster of reference nodes, the larger location errors are. To analyze the cause of this, two check points are calculated (see Fig. 5 ). The analysis results are similar to that of scenario 1. Therefore, two scaling parameters in the hybrid solution method are set equal to the same values that were used for scenario 1. It can be confirmed that the bad area of the DS method is covered by the good area of the DSRM method in the lower-right plot of Fig. 5 . Consequently, the results of the hybrid method show that there is no area that has large location errors caused by the relations among the reference nodes and mobile node. The performance of the localization methods can be compared using the lower-right plot of Fig. 4 and Table 1 .
Localization errors (3σ, 99.73%).
Scenario Methods
DS method DSRM method Hybrid method
1 4.8316 m 1.9844 m 1.5907 m
2 5.0451 m 1.4230 m 0.9903 m
3 4.3983 m 2.4135 m 1.6176 m
PPT Slide
Lager Image
Localization results of scenario 2.
PPT Slide
Lager Image
Location error and check points of scenario 2.
Remark for scenario 3 . In this scenario, it is assumed that three reference nodes are located at (40.0 m, 80.0 m), (1.0 m, 40.0 m), and (100.0 m, 60.0 m), respectively. Figures 6 and 7 show the localization results of scenario 3. As shown in the results of the DS method, a red sea zone exists on a horizontal area including the reference nodes, where the values of the check point 1 are close to 0. In this area, large localization errors occur (see the upper-left plot of Fig. 7 ). On the other hand, the results of the DSRM method have a different property compared with the results of the DS method. To analyze this phenomenon, check point 2 is calculated as denoted in Fig. 7 . In the area where the location error of the DSRM method increases, the value of check point 2 decreases. In this application, two scaling parameters in the hybrid solution method are set equal to the same values that were used for scenario 1. The results show that the good area of the DSRM method in the application area covers the bad area of the DS method. Therefore, the performance of the hybrid solution method can be enhanced based on the proposed hybrid algorithm [(20)–(22)].
PPT Slide
Lager Image
Localization results of scenario 3.
PPT Slide
Lager Image
Location error and check points of scenario 3.
It can be concluded that the hybrid solution method has better performance than the conventional standalone methods irrespective of the relative locations among the mobile node and reference nodes in the application area. For the hybrid solution, a double computation needs to be performed in comparison with the DS and DSRM methods. To analyze the computational burden, the process time in each of the locations in Figs. 2 , 4 , and 6 , denoted in the above simulations, is calculated using the “tic/toc” command in Matlab and is denoted in Fig. 8 . The mean values for the DS method, DSRM method, and hybrid solution are calculated as 9.8876E-5 s, 8.4126E-5 s, and 1.9149E-4 s, respectively. That is, the computational burden of the hybrid solution is increased. However, the problem of computational complexity is not that serious. Therefore, it can be stated that the hybrid solution can be used effectively in consideration of the performance advancement.
PPT Slide
Lager Image
Processing time.
V. Conclusion
The merits of LCS methods for wireless localization include non-approximated solutions and low computational burden when compared with iterative methods. However, each LCS method has its own pitfall. For example, the DS method has the red sea zone problem, and the DSRM method has errors increasing with distance between the mobile node and a cluster of reference nodes. Fortunately, the error occurrence probabilities are independent of each other and the areas where the errors occur can be guessed using check points. Motivated by the independent error properties of the conventional LCS methods, a hybrid LCS method was presented for avoiding the problems and estimating locations accurately, in this paper. The performance has been verified by several Monte Carlo simulation results. The simulation results show that the localization accuracy of the proposed hybrid solution is better than the conventional standalone solutions.
BIO
sycho@kiu.kr
Seong Yun Cho received his BS, MS, and PhD degrees in control and instrumentation engineering from Kwangwoon University, Seoul, Rep. of Korea, in 1998, 2000, and 2004, respectively. In 2003, he was a research assistant of the Automation and System Research Institute, Seoul National University, Rep. of Korea. In 2004, he was with the School of Mechanical and Aerospace Engineering, Seoul National University, Rep. of Korea, where he was a postdoctoral fellow, BK21. From 2008 to 2013, he worked for the Electronics and Telecommunications Research Institute, Daejeon, Rep. of Korea. From 2008 to 2013, he was an adjunct assistant/associate professor of the Mobile Communication & Digital Broadcasting Engineering Department, University of Science & Technology, Daejeon, Rep. of Korea. Since 2013, he has been with the Department of Applied Robotics, Kyungil University, Gyeongsan, Rep. of Korea, where he is now an assistant professor. His major research interests include positioning and navigation systems, filtering theory for linear/nonlinear systems, and telematics/LBS application systems.
References
Kolodziej K.W. , Hjelm J. 2006 Local Positioning Systems: LBS Applications and Services Taylor & Francis Group Boca Raton, FL, USA
Kaplan E.D. 1996 Understanding GPS: Principles and Applications Artech House Norwood, MA, USA
Yan J. 2013 “Review of Range-Based Positioning Algorithms,” IEEE Aerosp. Electron. Syst. Mag. 28 (8) 2 - 27    DOI : 10.1109/MAES.2013.6516141
Cho S.Y. , Choi Y.W. 2010 “Access Point-less Wireless Location Method Based on Peer-to-Peer Ranging of Impulse Radio Ultra-wideband,” IET-Radar, Sonar Navigation 4 (5) 733 - 743    DOI : 10.1049/iet-rsn.2009.0157
Mendel J.M. 1995 Lessons in Estimation Theory for Signal Processing, Communications, and Control Prentice-Hall International NJ, USA
Gezici S. , Guvenc I. , Sahinoglu Z. “On the Performance of Linear Least-Squares Estimation in Wireless Positioning System,” IEEE Int. Conf. Commun. Beijing, China May 19–23, 2008 4203 - 4208
Cho S.Y. 2010 “Localization of the Arbitrary Deployed APs for Indoor Wireless Location-Based Applications,” IEEE Trans. Consum. Electron. 56 (2) 532 - 539    DOI : 10.1109/TCE.2010.5505966
Bancroft S. 1985 “An Algebraic Solution of the GPS Equation,” IEEE Trans. Aerosp. Electron. Syst. 21 (7) 56 - 59
Biton I. , Koifman M. , Bar-Itzhack I.Y. 1998 “Improved Direct Solution of the Global Positioning System Equation,” J. Guidance, Contr., Dynamics 21 (1) 45 - 49    DOI : 10.2514/2.4195
Schmidt R.O. 1972 “A New Approach to Geometry of Range Difference Location,” IEEE Trans. Aerosp. Electron. Syst. 8 (6) 821 - 835
Friedlander B. 1987 “A Passive Localization Algorithm and its Accuracy Analysis,” IEEE J. Ocean. Eng. 12 (1) 234 - 245    DOI : 10.1109/JOE.1987.1145216
Smith J.O. , Abel J.S. 1987 “Closed-Form Least-Squares Source Location Estimation from Range-Difference Measurement,” IEEE Trans. Acoust., Speech, Signal Process. 35 (12) 1661 - 1669    DOI : 10.1109/TASSP.1987.1165089
Schau H. , Robinson A. 1987 “Passive Source Localization Employing Intersecting Spherical Surfaces from Time-of-Arrival Differences,” IEEE Trans. Acoust., Speech Signal Process. 35 (8) 1223 - 1225
Chan Y.T. , Ho K.C. 1994 “A Simple and Efficient Estimator for Hyperbolic Location,” IEEE Trans. Signal Process. 42 (8) 1905 - 1915    DOI : 10.1109/78.301830
Cho S.Y. , Kim B.D. 2013 “Linear Closed-Form Solution for Wireless Localization with Ultra-wideband/Chirp Spread Spectrum Based on Difference of Squared Range Measurements,” IET Wireless Sensor Syst. 3 (4) 255 - 265    DOI : 10.1049/iet-wss.2012.0159
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
Lee J.-Y. , Scholtz R.A. 2002 “Ranging in a Dense Multipath Environment Using an UWB Radio Link,” IEEE J. Sel. Areas Commun. 20 (9) 1677 - 1683    DOI : 10.1109/JSAC.2002.805060
Djeddou M. 2013 “TOA Estimation Technique for IR-UWB Based on Homogeneity Test,” ETRI J. 35 (5) 757 - 766    DOI : 10.4218/etrij.13.0112.0889