Methods and systems for location estimation

• US 8,254,293 B2
• Filed: 05/28/2009
• Issued: 08/28/2012
• Est. Priority Date: 05/28/2008
• Status: Expired due to Fees

• Current Assignee: Nivis LLC
• Original Assignee: Nivis LLC
• Inventors: Cristian, Voicu, Chilom, Marius, Assimiti, Robert, Ratiu, Ovidiu, Ticus, Ion, Pocol, Ioan
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Mansoury, Nourali
• Application Number:
  US12/473,600
• Publication Number:
  US 20100014443A1
• Time in Patent Office: 1,188 Days
• Field of Search: 370/255, 370/328, 455/456.1, 455/456.2, 455/456.3, 455/456.6
• 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 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.

2. 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.

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

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

5. The method of claim 1 wherein computing the stopping criterion comprises counting a number of epochs.

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

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

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

choosing the initial location based on the identified known-location neighbor nodes.

8. The method of claim 1 wherein choosing the 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 unknown-location neighbor nodes.

9. A system comprising:

a non-transitory computer-readable medium; and

one or more processors in communication with the non-transitory computer-readable medium, the one or more processors configured to;

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

for each unknown-location node;

receive neighbor node distance estimates;

choose an initial location estimate;

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

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

compute a stopping criterion;

determine if the stopping criterion satisfies a stopping threshold;

while the stopping criterion does not satisfy the stopping threshold;

for each unknown-location node;

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

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

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

determine if the stopping criterion satisfies a stopping threshold; and

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

10. The system of claim 9 wherein the one or more processors are further configured to choose a subsequent location estimate that differs from a previous location estimate by determining the subsequent location estimate to be at a configurable distance in a configurable direction relative to the previous location estimate.

11. The system of claim 10 wherein the one or more processors are further configured to determine the configurable direction so as to minimize the maximum magnitude of tension between an unknown location node and the neighbor nodes.

12. The system of claim 9 further comprising the database, the one or more processors in communication with the database.

13. The system of claim 9 wherein the one or more processors is configured to compute the stopping criterion by setting the stopping criterion to the total error.

14. The system of claim 9 wherein the one or more processors is configured to compute the stopping criterion by counting a number of epochs.

15. The system of claim 9 wherein the one or more processors is configured to choose the initial location estimate by choosing the initial location estimate randomly.

16. The system of claim 9 wherein the one or more processors is configured to choose the initial location estimate by:

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

choosing the initial location based on the identified known-location neighbor nodes.

17. The system of claim 9 wherein the one or more processors is configured to choose the initial location estimate by:

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

choosing the initial location based on the identified unknown-location neighbor nodes.

18. A non-transitory computer-readable medium comprising program code, the program code configured to cause a processor to execute a method, the program code comprising:

program code for maintaining in a database known locations of known-location nodes and estimates of locations of unknown-location nodes;

for each unknown-location node;

program code for receiving neighbor node distance estimates;

program code for choosing an initial location estimate;

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

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

program code for computing a stopping criterion;

program code for determining if the stopping criterion satisfies a stopping threshold;

while the stopping criterion does not satisfy the stopping threshold;

for each unknown-location node;

program code for choosing a subsequent location estimate that differs from a previous location estimate;

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

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

program code for determining if the stopping criterion satisfies a stopping threshold; and

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

19. The non-transitory computer-readable medium of claim 18 wherein the program code for choosing a subsequent location estimate that differs from a previous location estimate comprises program code for determining the subsequent location estimate to be at a configurable distance in a configurable direction relative to the previous location estimate.

20. The non-transitory computer-readable medium of claim 19 further comprising program code for determining the configurable direction so as to minimize the maximum magnitude of tension between an unknown location node and the neighbor nodes.

21. The non-transitory computer-readable medium of claim 18 wherein the program code for computing the stopping criterion comprises program code for setting the stopping criterion to the total error.

22. The non-transitory computer-readable medium of claim 18 wherein the program code for computing the stopping criterion Comprises program code for counting a number of epochs.

23. The non-transitory computer-readable medium of claim 18 wherein the program code for choosing the initial location estimate comprises program code for choosing the initial location estimate randomly.

24. The non-transitory computer-readable medium of claim 18 wherein the program code for choosing the initial location estimate comprises:

program code for identifying two known-location neighbor nodes that have two shortest neighbor node distance estimates, and

program code for choosing the initial location based on the identified known-location neighbor nodes.

25. The non-transitory computer-readable medium of claim 18 wherein the program code for choosing the initial location estimate comprises:

program code for identifying two unknown-location neighbor nodes that have two shortest neighbor node distance estimates, and

program code for choosing the initial location based on the identified unknown-location neighbor nodes.