IP Library › Granted Patent US 8,688,139

Granted Patent B2

US 8,688,139 · App. 12/876,970 · Granted Apr 1, 2014

Concurrent wireless transmitter mapping and mobile station positioning

Inventors: Lionel J. Garin (Palo Alto, CA); Ju-Yong Do (Palo Alto, CA); Gengsheng Zhang (Cupertino, CA)

Assignee: QUALCOMM Incorporated

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 8,688,139
App. No.: 12/876,970
Granted: Apr 1, 2014
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

The subject matter disclosed herein relates to concurrently estimating locations for one or more mobile stations and one or more wireless transmitters.

Claims (155)

1. A method comprising:

receiving at a computing platform a plurality of range measurements from one or more mobile stations with unknown positions, the plurality of range measurements comprising one or more range measurements to one or more wireless transmitters with unknown positions and one or more range measurements to one or more wireless transmitters with known positions; and

estimating locations for the one or more mobile stations with unknown positions and locations for the one or more wireless transmitters with unknown positions, by at least inverting a matrix;

wherein the matrix is based at least in part on geometric relationships of locations of the one or more mobile stations and the one or more wireless transmitters with unknown and known positions.

2. The method of claim 1 wherein said estimating comprises:

utilizing a least squares operation.

3. The method of claim 1 further comprising:

calculating a plurality of range estimates based at least in part on a plurality of updated seed locations; and

calculating differences between the plurality of range estimates and the plurality of range measurements.

4. The method of claim 1 further comprising:

detecting mirror effect by trying multiple seed locations and by comparing position fixes based on tried seed locations.

5. The method of claim 4 further comprising:

storing information associated with one or more mirrored position fixes in a database at least in part in response to a detection of one or more mirror effects; and

revisiting one or more of the one or more mirrored position fixes at least in part in response to an availability of additional range measurement information.

6. The method of claim 1 wherein the one or more wireless transmitters with known positions comprises one or more of a wireless access point or a femtocell, and wherein the one or more wireless transmitters with unknown positions also comprises one or more of a wireless access point or a femtocell.

7. The method of claim 1 wherein said receiving the plurality of range measurements from the one or more mobile stations with unknown positions comprises receiving the plurality of range measurements from a plurality of mobile stations with unknown positions.

8. The method of claim 1 wherein said receiving the plurality of range measurements from the one or more mobile stations with unknown positions comprises receiving the plurality of range measurements at a respective plurality of points in time from one mobile station with an unknown position.

9. The method of claim 1 wherein said receiving the plurality of range measurements comprises receiving one or more of a time of arrival, a time difference of arrival, a round trip time, or a received signal strength indicator.

10. The method of claim 1 wherein said receiving the plurality of range measurements from the one or more mobile stations with unknown positions comprises aggregating said plurality of range measurements from the one or more mobile stations with unknown positions over a period of time.

11. The method of claim 10 wherein said concurrently estimating locations for the one or more mobile stations with unknown positions and for the one or more wireless transmitters with unknown positions comprises refining previous estimations of locations for the one or more wireless transmitters based, at least in part, on aggregated range measurements obtained by the aggregating.

12. A method comprising:

estimating locations for the one or more mobile stations with unknown positions and locations for the one or more wireless transmitters with unknown positions, based at least in part on inverting a matrix;

wherein said estimating is performed using an iterative technique, the iterative technique comprising:

calculating a plurality of range estimates ρ based on a plurality of seed locations x; and

calculating differences dρ between the plurality of range measurements received at the computing platform and the plurality of range estimates ρ.

13. A method comprising:

estimating locations for the one or more mobile stations with unknown positions and locations for the one or more wireless transmitters with unknown positions by at least:

calculating a plurality of range estimates ρ based on a plurality of seed locations x;

calculating differences dρ between the plurality of range measurements received at the computing platform and the plurality of range estimates ρ;

calculating updates dx for the plurality of seed locations x based on the differences dρ; and

updating the plurality of seed locations, as x=x+dx.

14. A method comprising:

estimating locations for the one or more mobile stations with unknown positions and locations for the one or more wireless transmitters with unknown positions;

calculating a plurality of range estimates based at least in part on a plurality of estimated locations obtained by the estimating;

calculating differences between the plurality of range estimates and the plurality of range measurements;

determining whether the differences between the plurality of range estimates and the plurality of range measurements are less than a specified error threshold; and

utilizing said estimated locations of the one or more mobile stations with unknown positions and of the one or more wireless transmitters with unknown positions as a plurality of updated seed locations at least in part in response to a determination that the differences between the plurality of range estimates and the plurality of range measurements are less than the specified error threshold.

15. An article comprising a non-transitory storage medium having stored thereon instructions executable by a processor of a computing platform to at least:

estimate locations for one or more mobile stations with unknown positions and locations for one or more wireless transmitters with unknown positions, based at least in part on a plurality of range measurements received from the one or more mobile stations with unknown positions, the plurality of range measurements comprising one or more first range measurements to the one or more wireless transmitters with unknown positions and one or more second range measurements to one or more wireless transmitters with known positions, and by at least inverting a matrix;

wherein the matrix is based at least in part on geometric relationships of locations of the one or more mobile stations and the one or more wireless transmitters with unknown and known positions.

16. The article of claim 15 wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to:

utilize a least squares operation.

17. The article of claim 15 wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to at least:

calculate the plurality of range estimates based at least in part on the plurality of updated seed locations; and

calculate differences between the plurality of range estimates and the plurality of range measurements.

18. The article of claim 15 wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to detect mirror effect by trying multiple seed locations and by comparing position fixes based on tried seed locations.

19. The article of claim 18 wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to:

store information associated with one or more mirrored position fixes in a database at least in part in response to a detection of one or more mirror effects; and

revisit one or more of the one or more mirrored position fixes at least in part in response to an availability of additional range measurement information.

20. The article of claim 15 wherein the one or more wireless transmitters with known positions comprises one or more of a wireless access point or a femtocell, and wherein the one or more wireless transmitters with unknown positions also comprises one or more of a wireless access point or a femtocell.

21. The article of claim 15 wherein said plurality of range measurements received from said one or more mobile stations with unknown positions comprises a plurality of range measurements received from a plurality of mobile stations with unknown positions.

22. The article of claim 15 wherein said plurality of range measurements received from the one or more mobile stations with unknown positions comprises a plurality of range measurements taken at a respective plurality of points in time received from a single mobile station with an unknown position.

23. The article of claim 15 wherein said plurality of range measurements comprises one or more of a time of arrival, a time difference of arrival, a round trip time, or a received signal strength indicator.

24. The article of claim 15 wherein said plurality of range measurements from the one or more mobile stations with unknown positions comprises an aggregate of said plurality of range measurements taken from the one or more mobile stations with unknown positions over a period of time.

25. The article of claim 24 wherein the non-transitory storage medium has stored thereon further instructions executable by the processor to concurrently estimate locations of the one or more mobile stations with unknown positions and of the one or more wireless transmitters with unknown positions at least in part by refining previous estimations of locations for the one or more wireless transmitters with unknown positions based, at least in part, on aggregate of range measurements obtained by execution of the instructions to aggregate.

26. An article comprising a non-transitory storage medium having stored thereon instructions executable by a processor of a computing platform to at least:

wherein the instructions stored on the non-transitory storage media comprise instructions to use an iterative technique, the instructions to use the iterative technique comprising instructions to:

calculate a plurality of range estimates ρ based on a plurality of seed locations x; and

calculate differences dρ between the plurality of range measurements received at the computing platform and the plurality of range estimates ρ.

27. An article comprising a non-transitory storage medium having stored thereon instructions executable by a processor of a computing platform, the instructions comprising:

instructions to estimate locations for one or more mobile stations with unknown positions and locations for one or more wireless transmitters with unknown positions, based at least in part on a plurality of range measurements received from the one or more mobile stations with unknown positions, the plurality of range measurements comprising one or more first range measurements to the one or more wireless transmitters with unknown positions and one or more second range measurements to one or more wireless transmitters with known positions;

wherein the instructions to estimate comprise:

instructions to calculate a plurality of range estimates ρ based on a plurality of seed locations x;

instructions to calculate differences dρ between the plurality of range measurements received at the computing platform and the plurality of range estimates ρ;

instructions to calculate updates dx for the plurality of seed locations x based on the differences dρ; and

instructions to update the plurality of seed locations, as x=x+dx.

28. An article comprising a non-transitory storage medium having stored thereon instructions executable by a processor of a computing platform, the instructions comprising:

instructions to calculate a plurality of range estimates based at least in part on a plurality of estimated locations obtained by execution of the instructions to estimate;

instructions to calculate differences between the plurality of range estimates and the plurality of range measurements;

instructions to determine whether the differences between the plurality of range estimates and the plurality of range measurements are less than a specified error threshold; and

instructions to utilize said estimated locations of the one or more mobile stations with unknown positions and of the one or more wireless transmitters with unknown positions as a plurality of updated seed locations at least in part in response to a determination that the differences between the plurality of range estimates and the plurality of range measurements are less than the specified error threshold.

29. A computing platform comprising:

a communication interface configured to receive a plurality of range measurements from one or more mobile stations with unknown positions, the plurality of range measurements comprising one or more first range measurements to one or more wireless transmitters with unknown positions and one or more second range measurements to one or more wireless transmitters with known positions; and

at least one processor configured to estimate locations of the one or more mobile stations with unknown positions and locations of the one or more wireless transmitters with unknown positions, by at least inverting a matrix;

wherein the matrix is based at least in part on geometric relationships of locations of the one or more mobile stations and the one or more wireless transmitters with unknown and known positions.

30. The computing platform of claim 29 wherein the at least one processor is further configured to:

utilize a least squares operation.

31. The computing platform of claim 29 wherein the at least one processor is further configured to:

calculate the plurality of range estimates based at least in part on the plurality of updated seed locations; and

calculate differences between the plurality of range estimates and the plurality of range measurements.

32. The computing platform of claim 29 wherein the processor is configured to detect mirror effect by trying multiple seed locations and by comparing position fixes based on tried seed locations.

33. The computing platform of claim 32 further comprising:

a memory;

wherein the processor is configured to store in the memory information associated with one or more mirrored position fixes at least in part in response to a detection of one or more mirror effects, and wherein the processor is configured to revisit one or more of the one or more mirrored position fixes at least in part in response to an availability of additional range measurement information.

34. The computing platform of claim 29 wherein the one or more wireless transmitters with known positions comprises one or more of a wireless access point or a femtocell, and wherein the one or more wireless transmitters with unknown positions also comprises one or more of a wireless access point or a femtocell.

35. The computing platform of claim 29 wherein the communication interface is configured to receive the plurality of range measurements from the one or more mobile stations with unknown positions by receiving the plurality of range measurements from a plurality of mobile stations with unknown positions.

36. The computing platform of claim 29 wherein the communication interface is configured to receive the plurality of range measurements from the one or more mobile stations with unknown positions by receiving the plurality of range measurements at a respective plurality of points in time from one mobile station with an unknown position.

37. The computing platform of claim 29 wherein the communication interface is configured to receive the plurality of range measurements at least in part by receiving one or more of a time of arrival, a time difference of arrival, a round trip time, or a received signal strength indicator.

38. The computing platform of claim 29 wherein the communication interface is configured to receive the plurality of range measurements from the one or more mobile stations with unknown positions at least in part by aggregating said plurality of range measurements from the one or more mobile stations with unknown positions over a period of time.

39. The computing platform of claim 38 wherein the processor is configured to concurrently estimate locations for the one or more mobile stations with unknown positions and for the one or more wireless transmitters with unknown positions at least in part by refining previous estimations of locations for the one or more wireless transmitters with unknown positions based, at least in part, on said aggregated range measurements.

40. The apparatus of claim 39 wherein the one or more wireless transmitters with known positions comprises one or more of a wireless access point or a femtocell and wherein the one or more wireless transmitters with unknown positions also comprises one or more of a wireless access point or a femtocell.

41. The apparatus of claim 39 wherein said means for receiving the plurality of range measurements from the one or more mobile stations with unknown positions comprises means for receiving the plurality of range measurements from a plurality of mobile stations with unknown positions.

42. The apparatus of claim 39 wherein said means for receiving the plurality of range measurements from the one or more mobile stations with unknown positions comprises means for receiving the plurality of range measurements at a respective plurality of points in time from one mobile station with a known position.

43. The apparatus of claim 39 wherein said means for receiving the plurality of range measurements comprises means for receiving one or more of a time of arrival, a time difference of arrival, a round trip time, or a received signal strength indicator.

44. The apparatus of claim 39 wherein said means for receiving the plurality of range measurements from the one or more mobile stations with unknown positions comprises means for aggregating said plurality of range measurements from the one or more mobile stations with unknown positions over a period of time.

45. The apparatus of claim 44 wherein said means for concurrently estimating locations for the one or more mobile stations with unknown positions and for the one or more wireless transmitters with unknown positions comprises means for refining previous estimations of locations for the one or more wireless transmitters based, at least in part, on aggregated range measurements obtained by the means for aggregating.

46. A computing platform comprising:

a communication interface to receive a plurality of range measurements from one or more mobile stations with unknown positions, the plurality of range measurements comprising one or more first range measurements to one or more wireless transmitters with unknown positions and one or more second range measurements to one or more wireless transmitters with known positions; and

at least one processor to estimate locations of the one or more mobile stations with unknown positions and locations of the one or more wireless transmitters with unknown positions, based at least in part on inverting a matrix;

wherein the processor is configured to estimate said locations using an iterative technique to at least:

calculate a plurality of range estimates ρ based on a plurality of seed locations x; and

calculate differences dρ between the plurality of range measurements received at the computing platform and the plurality of range estimates ρ.

47. A computing platform comprising:

a communication interface to receive a plurality of range measurements from one or more mobile stations with unknown positions, the plurality of range measurements comprising one or more range measurements to one or more wireless transmitters with unknown positions and one or more range measurements to one or more wireless transmitters with known positions; and

calculate a plurality of range estimates ρ based on a plurality of seed locations x;

calculate differences dρ between the plurality of range measurements received at the computing platform and the plurality of range estimates ρ;

calculate updates dx for the plurality of seed locations x based on the differences dρ; and

update the plurality of seed locations, as x=x+dx.

48. A computing platform comprising:

a communication interface to receive a plurality of range measurements from one or more mobile stations with unknown positions, the plurality of range measurements comprising one or more range measurements to one or more wireless transmitters with unknown positions and one or more range measurements to one or more wireless transmitters with known positions; and

calculate a plurality of range estimates based at least in part on a plurality of estimated locations obtained by the estimating;

calculate differences between the plurality of range estimates and the plurality of range measurements;

determine whether the differences between the plurality of range estimates and the plurality of range measurements are less than a specified error threshold; and

utilize said estimated locations of the one or more mobile stations with unknown positions and of the one or more wireless transmitters with unknown positions as a plurality of updated seed locations at least in part in response to a determination that the differences between the plurality of range estimates and the plurality of range measurements are less than the specified error threshold.

49. An apparatus comprising:

means for receiving a plurality of range measurements from one or more mobile stations with unknown positions, the plurality of range measurements comprising one or more first range measurements to one or more wireless transmitters with unknown positions and one or more second range measurements to one or more wireless transmitters with known positions; and

means for estimating locations of the one or more mobile stations with unknown positions and locations for the one or more wireless transmitters with unknown positions utilizing, at least in part, a processor of a computing platform, and by at least inverting a matrix;

wherein the matrix is based at least in part on geometric relationships of locations of the one or more mobile stations and the one or more wireless transmitters with unknown and known positions.

50. The apparatus of claim 49 further comprising:

means for utilizing a least squares operation.

51. The apparatus of claim 49 further comprising:

means for calculating the plurality of range estimates based at least in part on the plurality of updated seed locations; and

means for calculating differences between the plurality of range estimates and the plurality of range measurements.

52. The apparatus of claim 49 further comprising:

means for detecting mirror effect by trying multiple seed locations and by comparing position fixes based on tried seed locations.

53. The apparatus of claim 52 further comprising:

means for storing information associated with one or more mirrored position fixes at least in part in response to a detection of one or more mirror effects; and

means for revisiting one or more of the one or more mirrored position fixes at least in part in response to an availability of additional range measurement information.

54. An apparatus comprising:

means for receiving a plurality of range measurements from one or more mobile stations with unknown positions, the plurality of range measurements comprising one or more range measurements to one or more wireless transmitters with unknown positions and one or more range measurements to one or more wireless transmitters with known positions; and

wherein the means for estimating comprise means for using an iterative technique, and the means for using the iterative technique comprising:

means for calculating a plurality of range estimates ρ based on a plurality of seed locations x; and

means for calculating differences dρ between the plurality of range measurements received at the computing platform and the plurality of range estimates ρ.

55. An apparatus comprising:

means for calculating a plurality of range estimates ρ based on a plurality of seed locations x;

means for calculating differences dρ between the plurality of range measurements received at the computing platform and the plurality of range estimates ρ;

means for calculating updates dx for the plurality of seed locations x based on the differences dρ; and

means for updating the plurality of seed locations, as x=x+dx.

56. An apparatus comprising:

means for estimating locations for the one or more mobile stations with unknown positions and locations for the one or more wireless transmitters with unknown positions;

means for calculating a plurality of range estimates based at least in part on a plurality of estimated locations obtained by the means for estimating;

means for calculating differences between the plurality of range estimates and the plurality of range measurements;

means for determining whether the difference between the plurality of range estimates and the plurality of range measurements are less than a specified error threshold; and

means for utilizing said estimated locations of the one or more mobile stations with unknown positions and of the one or more wireless transmitters with unknown positions as a plurality of updated seed locations, at least in part in response a determination that the differences between the plurality of range estimates and the plurality of range measurements are less than the specified error threshold.

Assignments (1)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 9, 2010

From: GARIN, LIONEL J; DO, JU-YONG; ZHANG, GENGSHENG

To: QUALCOMM INCORPORATED

Reel/Frame 024961/0302 →

Continuity (2)

Provisional Application 61241353 · Sep 10, 2009

Related Publication 20110059752A1 · Mar 10, 2011