US 6,353,744 B1Grant

Method for positioning with low geometrical dilution of position (GDOP)

Issue Date:2002-03-05

•8 Claims

•2 Drawing Sheets

Abstract

The invention is directed to positioning with low geometrical dilution of position (GDOP). Generally, the invention is a method for positioning including the steps of transmitting a asynchronous signal from a mobile to at least one base station; receiving the asynchronous signal at each base station; for each base station, determining a spherical line of position for the mobile using the received non-synchronous signal; and positioning the mobile using the spherical lines of position. The invention is a position location system which has the merits of both spherical and hyperbolic positioning systems while avoiding their drawbacks. The invention is less sensitive to GDOP and the mathematical model is easier to handle than the known hyperbolic system. The mathematical model embodied in the invention is equivalent to a convex quadratic probing subject to an ice-cream cone constraint. The invention also embodies an efficient algorithm for this optimization model. The invention is primarily directed to position location for E911, it can also applied to any other fields where position location is used, such as, but not limited to, radar positioning, satellite positioning and navigation systems.

Metadata

Assignee

Nortel Networks Limited

Inventors

Shiquan Wu
Song Zhang
Xixian Chen

Application Information

Application Number:US 09/374,103

Filing Date:1999-08-16

Priority Date:1999-08-16

Art Unit:7

Classifications

IPC:

H04Q 720

Field of Search:

4554564554574554224555753423570134235702342357043423570634235709342450342457342458342462342463342452

Patent Drawings (2 sheets)

Description

Field of the Invention

[0002] The present invention relates generally to positioning and more particularly to a method and system for positioning with low geometrical dilution of position.

Background of the Invention

[0003] Emergency 911 service is rapidly becoming essential in today's society. One of the compelling reasons for using the existing landline emergency 911 system is the ability to trace the caller's location. Using databases in the telephone network switches, the caller's location is determined and made available to the emergency services. In the event the caller is unable to inform the operator of their location, the ability to trace the call is invaluable.

[0004] The explosive growth of mobile phones, however, causes complications for emergency 911 services. While mobile users may call the 911 operator just as they would using a landline phone, there is no ability to trace the exact location of the mobile caller. The emergency 911 operator currently can only trace the mobile call to the base station closest to the mobile caller is using.

[0005] Mobile systems with the ability to locate mobile callers are known as enhanced 911 or E911 systems. One known approach to determine a mobile caller's location involves using an improved handset. The improved handset may incorporate a global positioning systems (GPS) receiver to determine the mobile caller's location and then transmit the location to the emergency 911 operator. Another improved handset may use signals from multiple base stations to determine the mobile caller's location. These handset improvements, however, involve improved handset circuitry that increases the cost of the handsets. Further, the extra circuitry requires extra battery power. Moreover, deployment of the improvement takes time since it depends on the users upgrading their handsets.

[0006] Another approach would not modify the handsets, thereby avoiding the problems started above. The so-called network approach involves modifying the base stations.

[0007] The network approach may use two known positioning systems: spherical and hyperbolic. The spherical system measures the time of arrival (TOA) from the mobile signal at base stations, which are at known locations. The hyperbolic system measures the time difference of arrival (TDOA) of the mobile signal between base stations.

[0008] Positioning By TOA (Spherical System)

[0009] If each receiver knows the transmission time of the mobile and the receivers are synchronized with each other, then they can measure the travel time (or TOA) of the mobile signal, and therefore the distance from the mobile to the receiver. For example, suppose there are more than 3 receivers and the measurement by each receiver has no error. Thus, around each receiver there is a circle with each receiver as the centre and the distance between the receiver and the mobile as radius. All the circles intersect at a unique point that is the position of the mobile. The circles are known as lines of position.

[0010] Assuming the spherical system receivers are synchronized, the TOA can be estimated accurately with moderate high signal to noise ratio. The solution of the spherical equations is no very sensitive to the TOA estimation errors. Spherical systems are widely used in positioning, but they cannot be used directly to position a mobile since the mobile is not synchronized with the base stations.

[0011] Positioning by TDOA (Hyperbolic system)

[0012] TDOA can be used to position the mobile. Suppose the signal sequence arrives at base stations at (x₁,y₁), (x₂,y₂), (x₃,y₃) and TDOAs are measured are τ₂₁, τ₃₁, . . . , and ν is the speed of light, then by the wave propagation property it follows that

[0013] {square root over ((x₃+L −x)²+L +(y₃+L −y)²+L )}−{square root over ((x₁+L −x)²+L +(y₁+L −y)²+L )}=ντ₃₁ Eqn. 1

[0014] {square root over ((x₂+L −x)²+L +(y₂+L −y)²+L )}−{square root over ((x₁+L −x)²+L +(y₁+L −y)²+L )}=ντ₂₁ Eqn. 2

[0015] Therefore, Eqns. 1 and 2 define hyperbolic lines of position around the base stations if more than 3 base stations are involved in this positioning process. If there is no error for each TDOA measurement, all these hyperbolic curves will have a unique intersection, which is the position of the mobile.

[0016] Unlike the spherical system that measures TOA, the hyperbolic system measures TDOA and hence the mobile does not have to be synchronized with the base stations. Hyperbolic systems, however, are sensitive to Geometrical Dilution of Position (GDOP).

[0017] Geometrical Dilution of Position (GDOP)

[0018] There will always by the measurement errors in practice. Thus, the hyperbolas will deviate from the true curve to some extent depending on the measurement error distribution. The possible intersection of the hyperbolas might be anywhere in an area around the true location. This area is usually referred to GDOP. Thus, GDOP contributes to the overall location error. It can be shown that the GDOP is larger as the mobile location is far away from the central part of the triangular formed by base stations.

[0019] Therefore, clearly there is a need to reduce the GDOP in positioning systems.

Summary of the Invention

[0020] The present invention is directed to positioning with low GDOP.

[0021] According to one aspect of the present invention, there is provided a method for positioning including the steps of: transmitting a asynchronous signal from a mobile to at least one base station; receiving the asynchronous signal at each base station; for each base station, determining a spherical line of position for the mobile using the received non-synchronous signal; and positioning the mobile using the spherical lines of position.

[0022] An advantage of the invention is less sensitivity to GDOP with a more convenient mathematical model.

[0023] Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.

Brief Description of the Drawings

[0024] The embodiments of the invention will now be described with reference to the accompanying drawings, in which:

[0025] FIG. 1 is a flow chart of the Prone Algorithm used in an embodiment of the invention; and

[0026] FIG. 2 is a flow chart of aspects of the Prone Algorithm used in an embodiment of the invention.

[0027] Similar references are used in different figures to denote similar components.

Detailed Description of the Invention

[0028] The detailed description of the invention includes

[0029] a general overview of the invention, and

[0030] a description of the embodiments of the invention, including the presently preferred embodiment.

[0031] By way of overview, this invention is a position location system which has the merits of both spherical and hyperbolic positioning systems while avoiding their drawbacks. The invention is less sensitive to GDOP and the mathematical model is easier to handle than the known hyperbolic system. The mathematical model embodied in the invention is equivalent to a convex quadratic programming subject to an ice-cream cone constraint. The invention also embodies an efficient algorithm for this optimization model. The invention is primarily directed to position location for E911, it can also applied to any other fields where position location is used, such as, but not limited to, radar positioning, satellite positioning and navigation systems.

[0032] Therefore, generally speaking, the invention uses a reformulated hyperbolic system that is more like a spherical system. A least squares solution minimizes the sum of the error in the reformulated system.

[0033] Also, each base station is weighted based on the SNR of the received signal. Thus, the reformulated system can account for other practical issues in the system.

[0034] The reformulated system uses equations, that when plotted, define a cone. The cone is a function of variable r, thus for each r the equations define a circle. The variable r is the distance from mobile to serving base station. Although any base station van be picked, in practice the one being used by the mobile, that is highest SNR for min error is used.

[0035] The invention may also include a fast algorithm to solve the reformulated equations. The solution is on the surface of cone.

[0036] The algorithm, for a given r, solves a nonlinear minimization problem for x,y, then varies r and repeats. The minimum of all the solution sets is the result of the algorithm.

[0037] For a given r, the algorithm an almost results in an explicit answer. This results in a savings in computation power. As will be seen later, because Q bar is positive, then there are only two solutions from which to pick minimum, almost a closed form solution.

[0038] Thus, a method for positioning includes the steps of:

[0039] transmitting a asynchronous signal from a mobile to at least one base station.

[0040] receiving the asynchronous signal at each base station.

[0041] for each base station, determining a spherical line of position for the mobile using the received non-synchronous signal. Preferably, a time difference of arrival at each base station is used to determine the spherical lines of position.

[0042] positioning the mobile using the spherical lines of position.

[0043] Also preferably, the time difference of arrival at each base station is substantially equal to the difference between the asynchronous signal time of arrival at each base station and the asynchronous signal time of arrival at a serving base station.

[0044] A description of the presently preferred embodiment follows.

[0045] Positioning Model

[0046] Hyperbolic systems are more sensitive to GDOP than spherical systems. Hyperbolic systems were proposed originally for the acoustic sensors system under the sea and the purpose was to avoid the synchronization between receiver and those sensors. Thus, only those sensors needed to be synchronized so that they transmitted beacons at the same time. For the preferred E911 systems, the situation is just opposite. The base stations are passive receivers while mobile is the transmitter. An embodiment of the invention use circles rather than hyperbolae, but avoids synchronization between mobile and base stations.

[0047] As an example only, assume there are three base stations, A, B and C, and one mobile. Suppose the base stations have been synchronized and the mobile signal has arrived at base stations A, B and C at the time τ(A), τ(B) and τ(C) respectively and C is the serving base station. According to the wave propagation properly, the unknown mobile location (x,y) will satisfy the following equations:

[0048] (x−x_c)²+(y−y_c)²=r²

[0049] (x−x_a)²+(y−y_a)²=(r+Δa)²

[0050] (x−x_b)²+(y−y_b)²=(r+Δb)² Eqn. 3

[0051] where r is the distance from the mobile to the serving base station, Δa=ν(τ(a)−τ(c)), Δb=ν(τ(b)−τ(c)) and ν is the velocity of the light. When the TOA estimation has error, the last two equations might become inequalities, it is “>” when TOA is underestimated and “<” when TOA is overestimated. But the first one is always equality since there is no error there. Note that now r is a variable rather than a constant, r needs to be optimized in order to estimate the mobile location.

[0052] Eqn. 3 can be solved and has a unique solution when TOA estimation has no error. Unfortunately, the real situation is that there is always estimation error and there are often more than 3 base stations being involved for the locating. In general, we will have an equation system looks like the following:

[0053] (x−x₁)²+(y−y₁)²=r²

[0054] (x−x₂)²+(y−y₂)²=(r+Δ₁)²

[0055] (x−x_N)²+(y−y_N)²=(r+Δ_N)² Eqn. 4

[0056] Here it is assumed that there are N base stations involved in location activity and (x_N, y_N)'s are the corresponding co-ordinates of these base stations. Note that the right hand sides of these equations are variables rather than fixed numbers. This enables an embodiment of the invention to use a spherical system without the need to know the transmission time of the mobile. Moreover, these equations are much easier than to solve hyperbolic equations. In summary, the invention has the advantages of both spherical positioning systems and hyperbolic positioning systems while reducing their disadvantages.

[0057] There are N equations (inequalities) and N variables. But only the first equation holds the exactly equality. Since all the equations are formed by circles, the error strip is only dependent on the TOA estimation error and is not sensitive to the geometric location of the mobile. So GDOP restriction is relaxed for this embodiment of the invention. Further, the TOA error distribution and the different contribution of each individual base station according to its hear-ability (SNR, C/I etc.) may be considered. These considerations are reflected by giving them different weights, say w(n) for the nth base station. Then, the positioning model to be optimized becomes

\begin{matrix} \min f (x, y, r) = \sum_{n = 2}^{N} w (n) {| {(x - x_{n})}^{2} + {(y - y_{n})}^{2} - {(r + Δ_{N})}^{2} |}^{2} subject to {(x - x_{1})}^{2} + {(y - y_{1})}^{2} = r^{2}, r \geq 0 & Eqn . 5 \end{matrix}

[0058] Typically, w(n) can be set to any positive constant but it is preferably to equal to 1. Eqn. 5 is a convex quadratic and the constraint is an ice cream cone. Therefore, there exists highly efficient algorithm to solve this problem.

[0059] Algorithm for Optimizing the Positioning Model

[0060] The following is an algorithm called the Prone algorithm and is specially designed for the model defined by Eqn. 4. It is a kind of approximate algorithm and its precision and computation load can be pre-defined.

[0061] The Prone Algorithm

[0062] Input parameters to the algorithm are:

[0063] r₁, the radius of the serving base station coverage;

[0064] (x₁,y₁), the co-ordinate of the serving base station;

[0065] N, the number of base stations involved;

[0066] (x_n,y_n), n=2,3, . . . , N, the co-ordinates corresponding to the other base stations, the order of numbering is based on their hear-ability conditions such as C/I, SNR etc.;

[0067] w(n), n=2,3, . . . ,N, the assigned weights to each base station according to their C/I and SNR.

[0068] Let

(x_{a}, y_{a}) = \frac{(x_{1}, y_{1}) + \sum_{n = 2}^{N} (x_{n}, y_{n})}{N}, r_{a} = \sqrt{{(x_{a} - x_{1})}^{2} + {(y_{a} - y_{1})}^{2}}

[0069] and solve

\begin{matrix} \begin{matrix} \min f (x, y, r_{a}) = \sum_{n = 2}^{N} w (n) | {(x - x_{n})}^{2} + \\ {{(y - y_{n})}^{2} - {(r_{a} + Δ_{t})}^{2} |}^{2} \end{matrix} subject to {(x - x_{1})}^{2} + {(y - y_{1})}^{2} = r_{a}^{2} & Eqn . 6 \end{matrix}

[0070] Suppose (x*,y); be the solution and let l*=f(x*,y*,r²). Clearly l* is less than f(x₂,y₂,r₂).

[0071] for r=0:Δr:r₁;

[0072] solve sub-optimization problem

[0073] min(f(x,y,r)|(x−x_x)²+y−y_y)²=r²;

[0074] Let (x′,y′) be its solution;

[0075] if l*>f(x′,y′,r);

[0076] set l*=f(x′,y′r); (x*,y*)=(x′,y′);

[0077] else l*=l*, (x*,y*)=(x*,y*);

[0078] end;

[0079] end

[0080] Note that the final (x*,y*) is the solution of the model with a resolution Δr. The key idea is the efficient subproblem solver, which is another aspect of the invention.

[0081] The Solution of Sub-optimization Problem

[0082] Without loss of generality, assume (x₁,y₁)=(0,0), that is assume (x₁,y₁) to be the co-ordinate system origin. Then the minimization problem becomes

\begin{matrix} \min f (x, y, r) = \sum_{n = 2}^{N} w (n) {| {(x - x_{n})}^{2} + {(y - y_{n})}^{2} - {(r + Δ_{N})}^{2} |}^{2} subject to x^{2} + y^{2} = r^{2}, r \geq 0 & Eqn . 7 \end{matrix}

[0083] which can be simplified as

\begin{matrix} \min f (x, y, r) = \frac{1}{2} \begin{matrix} [x & y & r] Q [\begin{matrix} x \\ \begin{matrix} y \\ r \end{matrix} \end{matrix}] + C^{T} \end{matrix} [\begin{matrix} x \\ \begin{matrix} y \\ r \end{matrix} \end{matrix}] + \\ \sum_{n = 2}^{N} w (n) {(x^{2} + y^{2} - Δ_{N}^{2})}^{2} \end{matrix}

subject to x^{2} + y^{2} = r^{2}, r \geq 0

[0084] where

\begin{matrix} Q = [\begin{matrix} q_{11} & q_{12} & q_{13} \\ q_{12} & q_{22} & q_{23} \\ q_{13} & q_{23} & q_{33} \end{matrix}] = \sum_{n = 2}^{N} {w (n) [\begin{matrix} x_{n} \\ \begin{matrix} y_{n} \\ Δ_{n} \end{matrix} \end{matrix}]}^{T} \begin{matrix} [x_{n} & y_{n} & Δ_{n}] \end{matrix} & Eqn . 8 \end{matrix}

\begin{matrix} C = [\begin{matrix} C_{1} \\ C_{2} \\ C_{3} \end{matrix}] = \frac{1}{2} \sum_{n = 2}^{N} (x^{2} + y^{2} - Δ_{N}^{2}) w (n) [\begin{matrix} x_{n} \\ \begin{matrix} y_{n} \\ Δ_{n} \end{matrix} \end{matrix}] & Eqn . 9 \end{matrix}

[0085] Thus, the optimization problem is actually a 3 dimensional convex minimization problem constrained on an ice-cream cone. There are many efficient algorithms existed for this type of problem. Interesting enough, for a fixed r, the above problem actually has an explicate solution which can be used in the Prone Algorithm. In fact, when r is fixed, the dimensional of the above minimization problem can be reduced to 2 as

\begin{matrix} \begin{matrix} \begin{matrix} \min f (x, y, r) = \frac{1}{2} \begin{matrix} [x & y] \overline{Q} [\begin{matrix} x \\ y \end{matrix}] + {\overline{C}}^{'} [\begin{matrix} x \\ y \end{matrix}] + \frac{1}{2} q_{33} r^{2} + C_{3} r + \end{matrix} \\ \sum_{n = 2}^{N} w (n) {(x^{2} + y^{2} - Δ_{N}^{2})}^{2} \end{matrix} \\ subject to x^{2} + y^{2} = r^{2}, r \geq 0 \\ where \end{matrix} \\ \overline{Q} = [\begin{matrix} q_{11} & q_{12} \\ q_{12} & q_{22} \end{matrix}] & Eqn . 10 \\ \overline{C} = [\begin{matrix} C_{1} \\ C_{2} \end{matrix}] + 2 r [\begin{matrix} q_{13} \\ q_{23} \end{matrix}] & Eqn . 11 \end{matrix}

[0086] Since Q is related to the locations of base stations only and w(n) is positive, it is a positive definite matrix if at least 3 involved base stations are not co-linear. Suppose it has eigenvalue decomposition as

[0087] {overscore (Q)}=λ₁ν₁ν₁^T+λ₂ν₂ν₂^T Eqn. 12

[0088] where 0<λ₁≦λ₂and ν₁and ν₂are the corresponding eigenvectors. Then there is two situations.

[0089] The first solution:

\begin{matrix} \frac{{({\overline{υ}}_{1}^{T} \overline{C})}^{2}}{λ_{1}^{2}} + \frac{{({\overline{υ}}_{2}^{T} \overline{C})}^{2}}{λ_{2}^{2}} \leq r^{2}, find μ 0 such that \\ \frac{{({\overline{υ}}_{1}^{T} \overline{C})}^{2}}{{(λ_{1} - μ)}^{2}} + \frac{{({\overline{υ}}_{2}^{T} \overline{C})}^{2}}{{(λ_{2} - μ)}^{2}} = r^{2} then & Eqn . 13 \\ [\begin{matrix} x \\ y \end{matrix}] = \frac{({\overline{υ}}_{1}^{T} \overline{C}) {\overline{υ}}_{1}}{λ_{1} - μ} + \frac{({\overline{υ}}_{2}^{T} \overline{C}) {\overline{υ}}_{2}}{λ_{2} - μ} & Eqn . 14 \end{matrix}

[0090] is the solution of the sub-minimization.

[0091] The second solution:

\begin{matrix} \frac{{({\overline{υ}}_{1}^{T} \overline{C})}^{2}}{λ_{1}^{2}} + \frac{{({\overline{υ}}_{2}^{T} \overline{C})}^{2}}{λ_{2}^{2}} > r^{2}, find μ 0 such that \\ \frac{{({\overline{υ}}_{1}^{T} \overline{C})}^{2}}{{(λ_{1} + μ)}^{2}} + \frac{{({\overline{υ}}_{2}^{T} \overline{C})}^{2}}{{(λ_{2} + μ)}^{2}} = r^{2} then & Eqn . 15 \\ [\begin{matrix} x \\ y \end{matrix}] = \frac{({\overline{υ}}_{1}^{T} \overline{C}) {\overline{υ}}_{1}}{λ_{1} + μ} - \frac{({\overline{υ}}_{2}^{T} \overline{C}) {\overline{υ}}_{2}}{λ_{2} + μ} & Eqn . 16 \end{matrix}

[0092] is the solution. To find μ, any line search algorithm, such as bi-section method, can be used.

[0093] While the present invention has been described in connection with what is presently considered to be the most practical and preferred embodiments, it is to be understood that the invention is not limited to the disclosed embodiments. To the contrary, the present invention is intended to cover various modifications, variations, adaptations and equivalent arrangements included within the spirit and the scope of the appended claims. The scope of the claims is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structures and functions.

Claims

What is claimed is:

1. A method for positioning comprising the steps of:

a. transmitting a asynchronous signal from a mobile to at least one base station;

b. receiving the asynchronous signal at each base station;

c. for each base station, determining a spherical line of position for the mobile using the received non-synchronous signal; and

d. positioning the mobile using the spherical lines of position.

2. The method recited in claim 1 wherein step (c) uses a time difference of arrival at each base station to determine the spherical lines of position.

3. The method recited in claim 2 wherein the time difference of arrival at each base station is substantially equal to the difference between the asynchronous signal time of arrival at each base station and the asynchronous signal time of arrival at a serving base station.

4. The method recited in claim 3 wherein the spherical lines of position determined according to

\begin{matrix} {\begin{matrix} {(x - x_{1})}^{2} + {(y - y_{1})}^{2} = r^{2} for the serving base station \\ {(x - x_{n})}^{2} + {(y - y_{n})}^{2} = {(r + Δ_{n})}^{2} for n = 2, \dots, N non-serving  base  stations \end{matrix} \end{matrix}

where (x,y) is the mobile position, (x₁,y₁) is the location of the serving base station, (x_n,y_n) are the locations of the non-serving base stations, N is the number of base stations, r is the distance of the mobile to the serving base station, and Δ_nis a distance based on the time difference of arrival.

5. The method according to claim 4 wherein the positioning the mobile step positions the mobile by minimizing the spherical lines of position.

6. The method recited in claim 3 wherein the spherical lines of position determined by minimizing

\min f (x, y, r) = \sum_{n = 2}^{N} w (n) {| {(x - x_{n})}^{2} + {(y - y_{n})}^{2} - {(r + Δ_{N})}^{2} |}^{2}

subject to {(x - x_{1})}^{2} + {(y - y_{1})}^{2} = r^{2}, r \geq 0

where (x,y) is the mobile position, (x₁,y₁) is the location of the serving base station, (x_n,y_n) are the locations of the non-serving base stations, N is the number of base stations, r is the distance of the mobile to the serving base station, w(n) is a predetermined for the nth base station and Δ_nis a distance based on the time difference of arrival.

7. The method according to claim 6 wherein the positioning the mobile step positions the mobile by minimizing the spherical lines of position.

8. The method recited in claim 7 wherein minimizing the spherical lines of position uses a Prone Algorithm.

Patent Citations (5)

Patent	Date	Inventor	Cited By
US5652592(A)	1997-07-01	Sanderford et al.	Examiner
US6006097(A)	1999-12-01	Hornfeldt et al.	Examiner
US6009091(A)	1999-12-01	Stewart et al.	Examiner
US6122512(A)	2000-09-01	Bodin	Examiner
US6256505(B1)	2001-07-01	Kingdon et al.	Examiner

Abstract