Methods and Systems for Location Estimation

• US 20100014443A1
• Filed: 05/28/2009
• Published: 01/21/2010
• Est. Priority Date: 05/28/2008
• Status: Active Grant

• Current Assignee: Nivis LLC
• Original Assignee: Nivis LLC
• Inventors: Ticus, Ion, Assimiti, Robert, Chilom, Marius, Pocol, Ioan, Cristian, Voicu, Ratiu, Ovidiu
• Granted Patent: US 8,254,293 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 64/003 locating network equipment

Abstract

A network operating center for a network comprising known-location and unknown-location nodes can be configured to receive from each unknown-location node estimates of the distances from that node to each of its neighbor nodes. The network controller can then choose an initial location estimate for each unknown-location node and compute distances from the initial location estimates to the corresponding neighbor nodes. The network operating center can then choose subsequent location estimates of the unknown-location nodes by minimizing an error criterion based on a comparison of the received neighbor node distance estimates with the computed neighbor node distances.

Claims

1. A method of estimating the physical location of a first unknown-location node in a network comprising known-location nodes and unknown-location nodes, the method comprising:

maintaining in a database known locations of the known-location nodes and estimates of locations of the unknown-location nodes;

receiving neighbor node distance estimates for the first unknown-location node;

choosing an initial location estimate for the first unknown-location node;

computing neighbor node distances for the first unknown-location node; and

choosing a subsequent location estimate for the first unknown-location node based on a comparison of the neighbor node distance estimates with the computed neighbor node distances.

2. The method of claim 1 wherein choosing a subsequent location estimate based on a comparison of the neighbor node distance estimates with the computed neighbor node distances comprises:

computing a total error from the neighbor node distance estimates and the computed neighbor node distances; and

choosing a subsequent location estimate to reduce the total error.

3. The method of claim 2 wherein computing a total error from the neighbor node distance estimates and the computed neighbor node distances comprises:

computing a magnitude of the difference between each neighbor node estimate and each corresponding computed neighbor node distance;

multiplying the magnitude of the difference by a number larger than or equal to one if the neighbor node associated with the computed neighbor node distance is a known-location node; and

summing the modified magnitudes and unmodified magnitudes to obtain a total error.

4. The method of claim 3 further comprising:

computing a stopping criterion; and

while the stopping criterion does not satisfy a stopping threshold;

choosing a second subsequent location estimate.

5. The method of claim 4 wherein computing a stopping criterion comprises setting the stopping criterion to the total error.

6. The method of claim 4 wherein computing a stopping criterion comprises counting a number of epochs.

7. The method of claim 1 wherein choosing an initial location estimate comprises choosing the initial location estimate randomly.

8. The method of claim 1 wherein choosing an initial location estimate comprises:

identifying two known-location neighbor nodes that have the two shortest neighbor node distance estimates, and

choosing the initial location based on the identified neighbor nodes.

9. The method of claim 1 wherein choosing an initial location estimate comprises:

identifying two unknown-location neighbor nodes that have the two shortest neighbor node distance estimates, and

choosing the initial location based on the identified neighbor nodes.

10. The method of claim 1 wherein choosing a subsequent location estimate that differs from a previous location estimate comprises determining the subsequent location estimate to be at a configurable distance in a configurable direction relative to the previous location estimate.

11. The method of claim 10 further comprising determining the configurable direction so as to minimize the maximum magnitude of tension between the unknown location node and the neighbor nodes.

12. The method of claim 1 further comprising updating in the database the estimate of the location of the unknown-location node with the subsequent location estimate.

13. The method of claim 1 wherein the unknown-location node is a radio node.

14. A method of estimating the physical locations of a plurality of unknown-location nodes in a network comprising known-location nodes and unknown-location nodes, the method comprising:

maintaining in a database known locations of the known-location nodes and estimates of locations of the unknown-location nodes; and

for each unknown-location node;

receiving neighbor node distance estimates;

choosing an initial location estimate;

computing neighbor node distances; and

choosing a subsequent location estimate based on a comparison of the neighbor node distance estimates with the computed neighbor nodes.

15. The method of claim 14 wherein choosing a subsequent location estimate based on a comparison of the neighbor node distance estimates with the computed neighbor nodes comprises:

computing a total error from the neighbor node distance estimates and the computed neighbor node distances; and

choosing a subsequent location estimate to reduce the total error.

16. The method of claim 15 wherein computing a total error from the received neighbor node distance estimates and the computed updated neighbor node distances comprises:

computing a magnitude of the difference between each received neighbor node estimate and each corresponding computed updated neighbor node distance;

multiplying the magnitude of the difference by a number larger than or equal to one if the neighbor node associated with the computed updated neighbor node distance is a known-location node; and

summing the modified magnitudes and unmodified magnitudes to obtain the total error.

17. The method of claim 16 further comprising

computing a stopping criterion;

and

while the stopping criterion does not satisfy a stopping threshold;

for each unknown-location node choosing a second subsequent location estimate.

18. The method of claim 17 wherein computing a stopping criterion comprises determining the largest of the total errors associated with the plurality of unknown-location nodes.

19. The method of claim 17 wherein computing a stopping criterion comprises counting a number of epochs.

20. The method of claim 17 wherein computing a stopping criterion comprises computing the sum of the total errors associated with the plurality of unknown-location nodes.

21. The method of claim 14 wherein choosing an initial location estimate comprises choosing the initial location estimate randomly.

22. The method of claim 14 wherein choosing an initial location estimate comprises:

identifying two known-location neighbor nodes that have the two shortest neighbor node distance estimates, and

choosing the initial location based on the identified neighbor nodes.

23. The method of claim 14 wherein choosing an initial location estimate comprises:

identifying two unknown-location neighbor nodes that have the two shortest neighbor node distance estimates, and

choosing the initial location based on the identified neighbor nodes.

24. The method of claim 14 wherein choosing a subsequent location estimate that differs from a previous location estimate comprises determining the subsequent location estimate to be at a configurable distance in a configurable direction relative to the previous location estimate.

25. The method of claim 24 further comprising determining the configurable direction so as to minimize the maximum magnitude of tension between the unknown location node and the neighbor nodes.

26. The method of claim 14 further comprising updating in the database the estimates of the locations of the plurality of unknown-location node with the subsequent location estimates.

27. The method of claim 14 wherein each of the plurality of unknown-location nodes is a radio node.

28. A method of estimating the physical locations of one or more unknown-location nodes in a network comprising known-location nodes and unknown-location nodes, the method comprising:

maintaining in a database known locations of the known-location nodes and estimates of locations of the unknown-location nodes;

for each unknown-location node;

receiving neighbor node distance estimates;

choosing an initial location estimate;

computing neighbor node distances between the initial location estimate and neighbor node locations of neighbor nodes;

computing a total error from the received neighbor node distance estimates and the computed neighbor node distances;

computing a stopping criterion;

determining if the stopping criterion satisfies a stopping threshold;

while the stopping criterion does not satisfy the stopping threshold;

for each unknown-location node;

choosing a subsequent location estimate that differs from a previous location estimate;

computing updated neighbor node distances between the subsequent location estimate and neighbor node locations of neighbor nodes;

computing an updated total error from the received neighbor node distance estimates and the computed neighbor node distances;

determining if the stopping criterion satisfies a stopping threshold; and

updating in the database the estimate of the locations of the unknown-location nodes if the stopping criterion satisfies the stopping threshold.

29. The method of claim 28 wherein choosing a subsequent location estimate that differs from a previous location estimate comprises determining the subsequent location estimate to be at a configurable distance in a configurable direction relative to the previous location estimate.

30. The method of claim 29 further comprising determining the configurable direction so as to minimize the maximum magnitude of tension between the unknown location node and the neighbor nodes.

31. A position location estimation system for estimating the location of nodes in a network comprising known-location nodes and unknown-location nodes, the position location estimation system comprising a network operating center comprising a processor and a database, wherein:

the database comprises the locations of the known-location nodes and estimates of the locations of the unknown-location nodes;

the network operating center is configured to receive neighbor node distance estimates for each unknown-location radio node;

the processor of the network operating center is configured to;

determine a location estimate for each unknown-location node;

compute neighbor node distances between the location estimate and neighbor node locations for each unknown-location radio node;

determine an updated location estimate for each unknown-location radio node based on the computed neighbor node estimates and the received neighbor node distance estimates; and

the network operating center is further configured to update in the database the estimate of the locations of the unknown-location nodes.