Method and apparatus for locating a remote unit

• US 20050135319A1
• Filed: 12/02/2004
• Published: 06/23/2005
• Est. Priority Date: 12/19/2003
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Huang, Jian, Shi, Qicai, Correal, Neiyer S.
• Granted Patent: US 6,996,403 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks

Abstract

A method and apparatus for locating a remote unit (or node) is provided herein. During operation, location-finding equipment (106) will determine a gross location of non-located nodes (104) by determining distances of the nodes (104) to reference nodes (105). Additionally an error estimate in the location for each node is determined. A first subset of nodes having relatively lower error estimates are “promoted” to reference nodes, and a second subset of nodes having higher error estimates are again located based on a distance to the newly-promoted reference nodes.

Claims

1. A method for locating a remote unit, the method comprising the steps of:

determining location estimates for a plurality of nodes;

determining errors in the location estimates;

determining a first and a second subset of nodes based on the errors in the location estimates, wherein the first subset of nodes comprises those nodes with lower error values in the location estimates and the second subset of nodes comprises those nodes with higher error values in the location estimates; and

relocating the second subset of nodes by utilizing the first subset of nodes.

2. The method of claim 1 wherein the step of determining location estimates for the plurality of nodes comprises the step of determining location estimates for the plurality of nodes via a geometric location technique.

3. The method of claim 2 wherein the step of determining the location estimates for the plurality of nodes comprises the steps of:

determining distances from the plurality of nodes to reference nodes having known locations; and

utilizing a geometric location technique to locate the plurality of nodes based on their distances to the reference nodes.

4. The method of claim 2 wherein the step of determining the location estimates for the plurality of nodes comprises the steps of:

determining distances from the plurality of nodes to a subset of reference nodes having known locations, wherein the subset of reference nodes are chosen to reduce computational complexity; and

utilizing a geometric location technique to locate the plurality of nodes based on their distances to the subset of reference nodes.

5. The method of claim 1 wherein the step of determining errors in the location estimates comprises the step of determining a Geometric Dilution of Precision (GDOP) for the location estimates.

6. The method of claim 1 wherein the step of relocating the second subset of nodes comprises the steps of:

promoting nodes within the first subset of nodes to reference nodes having known locations;

determining distances from nodes within the second subset of nodes to the reference nodes; and

utilizing the geometric location technique to locate the second subset of nodes based on their distances to the reference nodes.

7. The method of claim 1 wherein the step of relocating the second subset of nodes comprises the steps of:

promoting nodes within the first subset of nodes to reference nodes having known locations;

determining distances from nodes within the second subset of nodes to a subset of reference nodes, wherein the subset of reference nodes are chosen to reduce computational complexity; and

utilizing the geometric location technique to locate the second subset of nodes based on their distances to the subset of reference nodes.

8. A method for locating a remote unit, the method comprising the steps of:

determining location estimates for a plurality of nodes by determining distances to reference nodes with known locations;

determining errors in the location estimates;

determining a first and a second subset of nodes, wherein the first subset of nodes comprises those nodes with lower errors for the location estimates and the second subset of nodes comprises those nodes with higher errors for the location estimates;

promoting the first subset of nodes to reference nodes; and

relocating the second subset of nodes by determining their distances to the reference nodes.

9. The method of claim 8 wherein the step of determining the location estimates for the plurality of nodes comprises the steps of determining location estimates for the plurality of nodes by determining distances to a subset of reference nodes, wherein the subset of reference nodes is chosen to reduce computational complexity.

10. The method of claim 8 wherein the step of determining errors in the location estimates comprises the step of determining a Geometric Dilution of Precision (GDOP) in the location estimates.

11. The method of claim 8 wherein the step of relocating the second subset of nodes comprises the steps of relocating the second subset of nodes by determining their distances to a subset of reference nodes chosen to reduce computational complexity.

12. Location Finding Equipment (LFE) comprising:

logic circuitry determining location estimates for a plurality of nodes, determining error values for the location estimates, determining a first and a second subset of nodes based on the error values, wherein the first subset of nodes comprises those nodes with lower error values for the location estimates and the second subset of nodes comprises those nodes with higher error values for the location estimates, and relocating the second subset of nodes by utilizing the first subset of nodes; and

a database for storing location estimates.

13. The LFE of claim 12 wherein the location estimates for the plurality of nodes are determined via a geometric location technique.

14. The LFE of claim 12 wherein the location estimates for the plurality of nodes are determined via a distance to reference nodes having a known location.

15. The LFE of claim 12 wherein the location estimates for the plurality of nodes are determined via a distance to a subset of reference nodes having a known location, wherein the subset of reference nodes is chosen to reduce computational complexity.

16. The LFE of claim 12 wherein the error values comprise Geometric Dilution of Precision (GDOP) values for the location estimates.

17. The LFE of claim 12 wherein the second subset of nodes is relocated by promoting the first subset of nodes to reference nodes and then determining a distance from the second subset of nodes to the reference nodes.

18. The LFE of claim 12 wherein the second subset of nodes is relocated by promoting the first subset of nodes to reference nodes and then determining a distance from the second subset of nodes to a subset of reference nodes chosen to reduce computational complexity.

19. The LFE of claim 12 wherein the plurality of nodes exist within a multi-hop network.