Method and apparatus to compute the geolocation of a communication device using orthogonal projections

• US 6,750,818 B2
• Filed: 06/25/2002
• Issued: 06/15/2004
• Est. Priority Date: 12/04/2000
• Status: Active Grant

• Current Assignee: III Holdings 1, LLC
• Original Assignee: TensorComm, Inc. (Rambus Inc.)
• Inventors: Thomas, John K., Narayan, Anand P.
• Primary Examiner(s): Blum, Theodore M.
• Application Number:
  US10/178,541
• Publication Number:
  US 20040017311A1
• Time in Patent Office: 721 Days
• Field of Search: 342/450, 342/451, 342/457
• US Class Current: 342/450
• CPC Class Codes: G01S 19/21 Interference related issues ; Issues related to cross-correlation, spoofing or other methods of denial of service
• CPC Class Codes: G01S 19/46 the supplementary measurement being of a radio-wave signal type
• CPC Class Codes: G01S 5/0215 Interference
• CPC Class Codes: G01S 5/10 Position of receiver fixed by co-ordinating a plurality of position lines defined by path-difference measurements , e.g. omega or decca systemsG01S5/12 takes precedence ; beacons and receivers cooperating therewith G01S1/306, G01S1/308
• CPC Class Codes: H04B 1/7075 with code phase acquisition
• CPC Class Codes: H04B 1/7103 the interference being multiple access interference
• CPC Class Codes: H04B 1/7105 Joint detection techniques, e.g. linear detectors
• CPC Class Codes: H04B 1/7117 Selection, re-selection, allocation or re-allocation of paths to fingers, e.g. timing offset control of allocated fingers
• CPC Class Codes: H04B 2001/70706 using a code tracking loop, e.g. a delay locked loop
• CPC Class Codes: H04B 2201/70701 featuring pilot assisted reception
• CPC Class Codes: H04B 2201/70715 with application-specific features

Abstract

A novel method and apparatus for determining geolocation of a mobile transmitter is provided. The apparatus and the method utilize an orthogonal projection of a source signal to canceling interference from the source signal in the geolocation process.

Claims

1. A method for determining geolocation of a mobile transmitter, the method comprising the steps of:

generating a location request;

detecting a first source signal (y1);

generating an orthogonal projection of said first source signal;

canceling interference from said first source signal by utilizing said orthogonal projection;

detecting at least one more source signal (y2 . . . yn); and

utilizing said source signals to determine a location of said mobile.

2. The method recited in claim 1 wherein said first source signal is a pilot signal.

3. The method recited in claim 1 wherein said at least one more source signal is a pilot signal.

4. The method recited in claim 1 wherein at least one of said first or said at least one more source signals are also used to generate a respective orthogonal projection and respective canceling interference step.

5. The method recited in claim 1 wherein at least three source signals are detected.

6. The method recited in claim 1 wherein an advanced forward triangulation is utilized for determining said location of said mobile.

7. The method recited in claim 1 wherein a received signal comprises H, the first source signal of interest;

S, the signals of all other sources and multi-path versions of the source of interest and composed of vectors s₁,s₂,s₃ . . . , s_p; and

noise (n);

the method comprising the steps of;

determining a basis matrix U composed of basis vectors u₁,u₂, . . . u_p;

storing elements of said basis matrix U; and

determining y_perp where;

8. The method recited in claim 7, wherein said step of determining basis vectors comprises the steps of:

A. assigning s₁ as a first basis matrix U;

B. decomposing s₂ into a component which is in said basis matrix U and a component that is not (u₂); and

C. redefining the basis matrix U to incorporate basis vector u₂.

9. The method recited in claim 8, wherein said step of determining basis vectors further comprises the steps of:

repeating steps B and C for each element of S.

10. The method recited in claim 8, wherein said step of determining basis vectors further comprises the steps of:

comparing u_i to a predetermined threshold and if u_i is greater than said threshold, adding u_i to the basis and repeating steps B and C for each element of S, else ignoring the u_i and continuing to repeat steps B and C.

11. The method recited in claim 8, wherein said step of determining basis vectors further comprises the steps of:

computing 1/σ

_i, where u_i^Tu_i=σ

_i; and

storing u_i and 1/σ

_i.

12. The method recited in claim 8, wherein said step of computing basis vectors further comprises the steps of:

$\mathrm{computing}<br><br>\text{\hspace{1em}<br><br>}<br><br>u_i=s_i-u_1<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_1}<br><br>u_1^T<br><br>s_i-u_2<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_2}<br><br>u_2^T<br><br>s_i-\mathrm{\dots <br><br>}-u_{i-1}<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_{i-1}}<br><br>u_{i-1}^T<br><br>s_i;<br><br>$$\mathrm{storing}<br><br>\text{\hspace{1em}<br><br>}<br><br>u_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>1/{\mathrm{\sigma <br><br>}}_i;<br><br>\mathrm{and}$

storing u_i and 1/σ

_i; and

repeating said determining and storing steps if u_i is above a predetermined threshold, else ignoring this particular u_i.

13. The method recited in claim 7, wherein said step of determining y_perp comprises the step of calculating y_perp with the following formula:

$y_{\mathrm{perp}}=y-U<br><br>\left[\begin{array}{ccccc}\frac{1}{{\mathrm{\sigma <br><br>}}_1}& 0& ·<br><br>& ·<br><br>& 0\\ 0& \frac{1}{{\mathrm{\sigma <br><br>}}_2}& ·<br><br>& ·<br><br>& 0\\ ·<br><br>& ·<br><br>& ·<br><br>& ·<br><br>& ·<br><br>\\ ·<br><br>& ·<br><br>& ·<br><br>& ·<br><br>& ·<br><br>\\ 0& 0& ·<br><br>& ·<br><br>& \frac{1}{{\mathrm{\sigma <br><br>}}_p}\end{array}\right]<br><br>U^T<br><br>y.$

14. The method recited in claim 7, wherein said step of determining y_perp comprises the step of calculating y_perp with the following formula:

$y_{\mathrm{perp}}=y-u_1<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_1}<br><br>u_1^T<br><br>y-u_2<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_2}<br><br>u_2^T<br><br>y-\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>u_{p-1}<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_{p-1}}<br><br>u_{p-1}^T<br><br>y-u_p<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_p}<br><br>u_p^T<br><br>y.$

15. The method recited in claim 7, further comprising a step of determining y_s where:

16. The method recited in claim 1 wherein a received signal comprises H, a spread signal matrix of the source of interest;

S, the spread signal matrix of all other sources of interest and composed of vectors s₁,s₂,s₃ . . . ,s_p; and

noise (n);

the method comprising the steps of;

A. assigning s₁ as a first basis vector u₁;

B. determining σ

_i, where u_i^Tu_i=σ

_i;

C. storing u_i;

D. computing of inner products of the s_i+1 and the u₁ through u_i vectors;

E. multiplying said inner product with a respective scalar 1/σ

_i and thereby creating a first intermediate product;

F. scaling each respective basis vector u_i by multiplying each respective first intermediate product with each respective basis vector u_i;

G. obtaining a vector sum from step F;

H. subtracting said vector sum from s_i+1 to obtain the next basis vector u_i+1;

I. comparing u_i+1 to a predetermined value and if equal to or less than said value, discarding the u_i+1 and going to step N;

J. storing u_i+1;

K. determining an inner product of u^T_i+1u_i+1;

L. determining the reciprocal of step K which is 1/σ

_i+1;

M. storing 1/σ

_i+1;

N. incrementing i;

O. conducting steps D through N until i=p, where p is the total number of said sources of interest; and

P. determining y_perp where;

17. The method recited in claim 16, wherein said computing step (D) is conducted in series.

18. The method recited in claim 16, wherein said computing step (D) is conducted in parallel.

19. The method recited in claim 16, wherein said multiplying step (E) is conducted in series.

20. The method recited in claim 16, wherein said multiplying step (E) is conducted in parallel.

21. The method recited in claim 16, wherein said scaling step (F) is conducted in series.

22. The method recited in claim 16, wherein said scaling step (F) is conducted in parallel.

23. The method recited in claim 16, wherein said storing step (C) also stores σ

_i.

24. The method recited in claim 16, wherein said storing step (C) also stores 1/σ

_i.

25. The method recited in claim 16, wherein said inner product step (K) is conducted in series.

26. The method recited in claim 16, wherein said inner product step (K) is conducted in parallel.

27. The method recited in claim 1 wherein a received signal comprises H, a spread signal matrix of the source of interest;

S, the spread signal matrix of all other sources of interest and composed of vectors s₁,s₂,s₃, . . . ,s_p; and

noise (n);

the method comprising the steps of;

A. assigning s₁ as a first basis vector u₁;

B. determining σ

_i, where u_i^Tu_i=σ

_i;

C. storing u_i;

D. computing of inner products of the s_i+1 and the u₁ through u_i vectors;

E. multiplying said inner product with a respective scalar 1/σ

_i and thereby creating a first intermediate product;

F. scaling each respective basis vector u_i by multiplying each respective first intermediate product with each respective basis vector u_i;

G. serially subtracting said intermediate product from s_i+1;

H. utilizing the result from step G and subtracting the next incoming value of $u_i<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_i}<br><br>u_i^T<br><br>s_{i+1}$

 

until all the values are processed;

I. obtaining the next basis vector u_i+1 from step H;

J. comparing u_i+1 to a predetermined value and if equal to or less than said value, discarding u_i+1 and going to step O;

K. storing u_i+1;

L. determining an inner product of u^T_i+1u_i+1;

M. determining the reciprocal of step K which is 1/σ

_i+1;

N. storing 1/σ

_i+1;

O. incrementing i;

P. conducting steps D through O until i=p, where p is the total number of said sources of interest; and

Q. determining y_perp where;

28. The method recited in claim 27, wherein said computing step (D) is conducted in series.

29. The method recited in claim 27, wherein said computing step (D) is conducted in parallel.

30. The method recited in claim 27, wherein said multiplying step (E) is conducted in series.

31. The method recited in claim 27, wherein said multiplying step (E) is conducted in parallel.

32. The method recited in claim 27, wherein said scaling step (F) is conducted in series.

33. The method recited in claim 27, wherein said scaling step (F) is conducted in parallel.

34. The method recited in claim 27, wherein said storing step (C) also stores σ

_i.

35. The method recited in claim 27, wherein said storing step (C) also stores 1/σ

_i.

36. The method recited in claim 27, wherein said inner product step (L) is conducted in series.

37. The method recited in claim 27, wherein said inner product step (L) is conducted in parallel.

38. An apparatus for determining geolocation of a mobile transmitter, the apparatus comprising:

means for generating a location request;

means for detecting a first source signal (y1);

means for generating an orthogonal projection of said first source signal;

means for canceling interference from said first source signal by utilizing said orthogonal projection;

means for detecting at least one more source signal (y2 . . . yn); and

means for utilizing said first and said at least one more source signals to determine the geolocation of said mobile transmitter.

39. The apparatus recited in claim 38 wherein said first source signal is a pilot signal.

40. The apparatus recited in claim 38 wherein said at least one more source signal is a pilot signal.

41. The apparatus recited in claim 38 wherein at least one of said first and said at least one more source signals are also used in generate a respective orthogonal projection and respective canceling interference step.

42. The apparatus recited in claim 38 wherein at least three source signals are detected.

43. The apparatus recited in claim 38 wherein an advanced forward triangulation is utilized for determining said geolocation of said mobile transmitter.

44. The apparatus recited in claim 38, wherein said first signal comprising H, a signal of the source of interest;

S, the signals of all other sources and composed of vectors s₁,s₂,s₃ . . . ,s_p; and

noise (n);

the apparatus further comprising;

means for determining a basis vector U;

means for storing elements of said basis vector U; and

means determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

45. The apparatus recited in claim 38, wherein said first signal comprising H, a spread signal matrix of the source of interest;

S, the spread signal matrix of all other sources of interest and composed of vectors s₁,s₂,s₃ . . . ,s_p; and

noise (n);

the apparatus further comprising;

A. means for assigning s₁ as a first basis vector u₁;

B. means for determining σ

_i, where u_i^Tu_i=σ

_i;

C. means for storing u_i;

D. means for computing of inner products of the s_i+1 and the u₁ through u_i vectors;

E. means for multiplying said inner product with a respective scalar 1/σ

_i and thereby creating a first intermediate product;

F. means for scaling each respective basis vector u_i by multiplying each respective first intermediate product with each respective basis vector u_i;

G. means for obtaining a vector sum from step F;

H. means for subtracting said vector sum from s_i+1 to obtain the next basis vector u_i+1;

I. means for comparing u_i+1 to a predetermined value and if equal to or less than said value, discarding this u_i+1 and going to step N;

J. means for storing u_i+1;

K. means for determining an inner product of u^T_i+1u_i+1;

L. means for determining the reciprocal of step K which is 1/σ

_i+1;

M. means for storing 1/σ

_i+1;

N. means for incrementing i;

O. means for conducting steps D through N until i=p, where p is the total number of said sources of interest; and

P. means for determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

46. The apparatus recited in claim 38, wherein said first signal comprising H, a spread signal matrix of the source of interest;

S, the spread signal matrix of all other sources of interest and composed of vectors s₁,s₂,s₃ . . . ,s_p; and

noise (n);

the apparatus further comprising;

A. means for assigning s₁ as a first basis vector u₁;

B. means for determining σ

_i, where u_i^Tu_i=σ

_i;

C. means for storing u_i;

D. means for computing of inner products of the s_i+1 and the u₁ through u_i vectors;

E. means for multiplying said inner product with a respective scalar 1/σ

_i and thereby creating a first intermediate product;

F. means for scaling each respective basis vector u_i by multiplying each respective first intermediate product with each respective basis vector u_i;

G. means for serially subtracting said intermediate product from s_i+1;

H. means for utilizing the result from step G and subtracting the next incoming value of $u_i<br><br>\frac{1}{{\mathrm{\sigma <br><br>}}_i}<br><br>u_i^T<br><br>s_{i+1}$

 

until all the values are processed;

I. means for obtaining the next basis vector u_i+1 from step H;

J. means for comparing u_i+1 to a predetermined value and if equal to or less than said value, going to step O;

K. means for storing u_i+1;

L. means for determining an inner product of u^T_i+1u_i+1;

M. means for determining the reciprocal of step K which is 1/σ

_i+1;

N. means for storing 1/σ

_i+1;

O. means for incrementing i;

P. means for conducting steps D through O until i=p, where p is the total number of said sources of interest; and

Q. means for determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty.

47. An apparatus for determining geolocation of a mobile, the apparatus comprising:

means for generating a location request;

means for detecting a first source signal (y1);

means for generating an orthogonal projection of said first source signal;

means for canceling interference from said first source signal by utilizing said orthogonal projection;

means for detecting at least one more source signal (y2 . . . yn); and

means for utilizing said first and said at least one more source signals to determine the location of said mobile.

48. The apparatus recited in claim 47 wherein said first source signal is a pilot signal.

49. The apparatus recited in claim 47 wherein said at least one more source signal is a pilot signal.

50. The apparatus recited in claim 47 wherein at least one of said first and said at least one more source signals are also used to generate a respective orthogonal projection and respective canceling interference step.

51. The apparatus recited in claim 47 wherein at least three source signals are detected.

52. The apparatus recited in claim 47 wherein an advanced forward triangulation is utilized for determining said location of said mobile.

53. The apparatus recited in claim 47 wherein said first source signal comprises H, a signal of the source of interest;

S, the signals of all other sources and multi-path versions of the source of interest and composed of vectors s₁,s₂,s₃ . . . ,s_p; and

noise (n);

the apparatus comprising;

means for determining a basis matrix U composed of basis vectors u₁,u₂, . . . u_p;

means for storing elements of said basis matrix U;

means for determining y_perp where;

54. The apparatus recited in claim 16, further comprising means for determining y_s where:

55. The apparatus recited in claim 27, further comprising means for determining y_s where:

56. An apparatus for determining geolocation of a mobile, the apparatus comprising:

means for generating a location request from a base station;

means for detecting a first source signal (y1) from said mobile;

means for generating an orthogonal projection of said first source signal;

means for canceling interference from said first source signal by utilizing said orthogonal projection;

means for detecting at least one more source signal (y2 . . . yn); and

means for utilizing said source signals to determine the location of said mobile.

57. The apparatus recited in claim 56 wherein said first source signal is a pilot signal.

58. The apparatus recited in claim 56 wherein said at least one more source signal is a pilot signal.

59. The apparatus recited in claim 56 wherein at least one of said one or more source signals are also used in generate a respective orthogonal projection and respective canceling interference step.

60. The apparatus recited in claim 56 wherein at least three source signals are detected.

61. The apparatus recited in claim 56 wherein an advanced forward triangulation is utilized for determining said location of said mobile transmitter.

62. The apparatus recited in claim 56 wherein said first source signal comprising H, a signal of the source of interest;

S, the signals of all other sources and composed of vectors s₁,s₂,s₃ . . . ,s_p; and

noise (n);

the apparatus comprising;

means for determining a basis vector U;

means for storing elements of said basis vector U;

means for determining y_perp where;

y_perp=y−

U(U^TU)<sup>−

1</sup>U^Ty;

means for determining y_s where;

63. A method for determining geolocation of a mobile transmitter, the method comprising the steps of:

A. generating a location request;

B. detecting a first source signal (y1);

C. assigning a first pre-determined correlation length to a variable N;

D. increasing said correlation length N by an amount Y;

E. determining signal to noise ratio of said first source signal (y1);

F. comparing said signal to noise ratio to a predetermined threshold to determine if said signal to noise ratio is equal to or above said threshold, if below said threshold, then initiating step G otherwise, initiating step H;

G. comparing said correlation length to a predetermined maximum correlation length and if below said maximum correlation length, returning to step D, otherwise going to step H;

H. generating an orthogonal projection of said first source signal;

I. canceling interference from said first source signal by utilizing said orthogonal projection;

J. detecting at least one more source signal (y2 . . . yn); and

K. utilizing said source signals to determine the geolocation of said mobile transmitter.

64. The method recited in claim 63 wherein said amount Y is a fixed amount.

65. The method recited in claim 63 wherein said amount Y is a variable amount.

66. A method for determining geolocation of a mobile transmitter, the method comprising the steps of:

A. generating a location request;

B. detecting a first source signal (y1) at a first base station;

C. generating an orthogonal projection of said first source signal;

D. canceling interference from said first source signal by utilizing said orthogonal projection;

E. detecting said first signal source (y1) at least one more base station; and

F. utilizing timing information of said source signal to determine the geolocation of said mobile transmitter.

67. An apparatus for determining geolocation of a mobile transmitter, the apparatus comprising:

means for generating a location request;

means for detecting a first source signal (y1) at a first base station;

means for generating an orthogonal projection of said first source signal;

means for canceling interference from said first source signal by utilizing said orthogonal projection;

means for detecting said first signal source (y1) at least one more base station; and

means for utilizing timing information of said source signal to determine the geolocation of said mobile transmitter.