Advanced
Improved TOA-Based Localization Method with BS Selection Scheme for Wireless Sensor Networks
Improved TOA-Based Localization Method with BS Selection Scheme for Wireless Sensor Networks
ETRI Journal. 2015. Aug, 37(4): 707-716
Copyright © 2015, Electronics and Telecommunications Research Institute (ETRI)
  • Received : October 27, 2014
  • Accepted : March 19, 2015
  • Published : August 01, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Seungryeol Go
Jong-Wha Chong

Abstract
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.
Keywords
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 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.
II. System Model in Wireless Localization
- 1. TOA-Based Ranging System
The TOA-based ranging system utilizes the propagation delay of the transmitted signal, 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 .
PPT Slide
Lager Image
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
t p,TWR = 1 2 ( T round,A T 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
1 2 ( T round,A T reply,B )   and    1 2 ( T round,B T reply,A ).
Consequently, the average propagation delay is given by
t p,SDS-TWR = 1 4 {( T round,A T reply,B )+( T round,B T 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.
- 2. TOA-Based Location Estimation
To describe the TOA-based localization scenario [5] , we consider a two-dimensional (2-D) network that consists of N fixed BSs with known locations, expressed as x i = [ xi , yi ] 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,
d ^ i
, from the 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]
d ^ i = c t p      =  d i + b i + n i ,
where di is the true distance using the TOA method between the MS and the i th BS, bi is the NLOS bias error, and ni ~𝒩(0,
σ i 2
)is the AWGN with variance
σ i 2
. The NLOS error bias bi 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
b i ={ 0 if ith BS is LOS, e i if ith BS is NLOS.
PPT Slide
Lager Image
TOA-based localization in NLOS environments.
In (9), we assume that bi = ei if the signal propagation between the i th BS and the MS is in an NLOS environment.
The noiseless true distance di is calculated by equation trilateration as follows:
d i =   x  x i   = ( x x i ) 2 + ( y y i ) 2 ,
where ∥·∥ represents the Euclidean norm operation on a vector of the distance between the MS and the i th BS.
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
d i 2 = (x x i ) 2 + (y y i ) 2 ,    i=1, ... ,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
d ^ i 2 = (x x i ) 2 + (y y i ) 2 ,     i = 1, ... , N,
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] :
= 1 2 P
with
A=[ x 1       y 1       0.5 x 2       y 2       0.5                  x N       y N       0.5 ],θ=[  x   y  x 2 + y 2 ], P=[ x 1 2 y 1 2 d 1 2 x 2 2 y 2 2 d 2 2            x N 2 y N 2 d N 2 ].
As a result, obtaining θ with the MS’s location value x , we can calculate the matrix interpretation (9), which is computed as
θ ^ = 1 2 ( A T A ) 1 A T P,
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.
PPT Slide
Lager Image
Transformation process of TOA-based localization from LOS environments to NLOS environments: (a) LOS environments and (b) NLOS environments.
- 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
x ^ NLS =arg  min x { i=1 N ( d ^ i x x i ) 2 } = min x { i=1 N ( e i ) 2 },
where
d ^ i
is the measured distance, x is the coordinate value of the MS’s location, x i is the coordinate value of the i th BS’s location, and ei = bi + ni 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
x ^ WLS =arg  min x { i=1 N β i ( d ^ i x x i ) 2 } = arg  min x { i=1 N β i ( e i ) 2 }.
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/
σ i 2
, where
σ i 2
is denoted by
σ i 2  = E{ ( d ^ i x x i ) 2 },
where E{ · } is the expected value operator.
- 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
Diagram of intersections in TOA-based localization.
- 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 di , which is given by
x ^ LMS = arg  min x { me d i ( d ^ i x x i ) 2 },
where med i ( θ ( i )) is the median of the function θ ( i ) over all possible values of i .
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
Relationship between length of chord and NLOS error.
In Section II-2, we expressed the i th BS’s location as x i = [ xi , yi ] T and the measured distance as
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 ˜ 1 = | A x 1 +B y 1 +X+YR | A 2 + B 2  or   d ˜ 2 = | A x 2 +B y 2 +X+YR | A 2 + B 2 ,
where
A=2( x 1 x 2 ),  B=2( y 1 y 2 ), X= x 1 2 + x 2 2 ,  Y= y 1 2 + y 2 2 , and  R= d ^ 1 2 + d ^ 2 2 .
To calculate the length of the chord between two TOA circles, the Pythagorean theorem is utilized using the distance
d ˜
and the measured distance
d ^
, and is expressed as follows:
l = 2 d ^ 1 2 d ˜ 1 2   or  l = 2 d ^ 2 2 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.
PPT Slide
Lager Image
Length of chord in TOA-based localization: (a) computation of length of chord and (b) expression of chords.
- 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 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
arg  min j  L(j).
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 .
PPT Slide
Lager Image
Flow chart of localization process using BS selection.
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. 1: Set i = 1 2: for each fixed ith BS (i = 1 to N)        calculate measured distance di between the ith BS and the MS 3: end do bind jth set which is combined by three BSs 4: for each jth combination (j = 1 to NC3) // C is combination operator        compute the length of chords between TOA-circles L(j) 5: end do find set combined by three BSs of the jth combination        minimizing the length of chords 6: do estimate the MS’s location at the jth set composed of three BSs        using conventional localization methods
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] 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,
x ^
, using the localization techniques in Section IV, and it is expressed by
Estimation error =| x x ^ |.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
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.
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 [15] 7.7550 m 9.5970 m 6.9895 m
Prop 3.3148 m 4.0264 m 3.3469 m
WLS [16] 4.3419 m 4.9746 m 3.8681 m
Prop 1.3498 m 2.3314 m 0.8422 m
Centroid [19] 6.2087 m 6.8934 m 4.5639 m
Prop 3.7009 m 4.6961 m 4.1665 m
LMS [21] 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] 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.
PPT Slide
Lager Image
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 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 [15] 6.1167 m 6.3203 m 6.5906 m
Prop 3.1436 m 3.2472 m 3.3947 m
WLS [16] 4.0583 m 5.4701 m 4.0472 m
Prop 2.5877 m 2.8870 m 2.9375 m
Centroid [19] 4.5410 m 4.7639 m 4.4939 m
Prop 2.5038 m 3.0313 m 2.1483 m
LMS [21] 5.6071 m 7.6874 m 5.5236 m
Prop 2.7037 m 2.6040 m 2.7142 m
PPT Slide
Lager Image
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.
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 r 1 and r 2 and having centers ( x 1 , y 1 ) and ( x 2 , y 2 ) are expressed, respectively, as
{ (x x 1 ) 2 + (y y 1 ) 2 = r 1 2 , (x x 2 ) 2 + (y y 2 ) 2 = r 2 2 ,
or        { 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.
To solve the straight line through the intersection of two circles, the difference between the two circles in (22) is described by
2( x 1 x 2 )x2( y 1 y 2 )+X+YR=0,
where X , Y , and R are constant values with
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 = ( 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
n= Ai+Bj 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
d=∥ EQ ¯ ∥
is the length of the projection of
v= RE →
(the vector from R to E) onto n , and is expressed as
d=| vn |=| [( x 1 x 0 )i+( y 1 y 0 )j]n |                = A( x 1 x 0 )+B( y 1 y 0 ) A 2 + B 2 .
PPT Slide
Lager Image
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
d= | A x 1 +B y 1 +C | 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).
BIO
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.
References
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