Method and system for hybrid positioning using partial distance information

• US 8,604,978 B2
• Filed: 12/20/2010
• Issued: 12/10/2013
• Est. Priority Date: 04/19/2006
• Status: Active Grant

• Current Assignee: WiChorus, Inc. (Infinera Corp.)
• Original Assignee: WiChorus, Inc. (Infinera Corp.)
• Inventors: Ergen, Mustafa, Jalil, Rehan
• Primary Examiner(s): LIU, HARRY K
• Application Number:
  US12/972,672
• Publication Number:
  US 20110140969A1
• Time in Patent Office: 1,086 Days
• Field of Search: 342458-464, 342/451, 4554561-4566
• US Class Current: 342/458
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

The present invention provides a method and system for positioning one or more anchor nodes or one or more non-anchor nodes in one or more communication networks. A non-anchor node may be in communication with two or more anchor nodes. The method comprises determining two or more distance measurements, corresponding to raw distances of the non-anchor node from the two or more anchor nodes, at predetermined intervals of time. An estimated distance is then calculated between the two or more anchor nodes based on the two or more distance measurements. Estimated distances between a plurality of anchor nodes in the one or more communication networks is calculated in a similar manner. A partial distance matrix is then populated using the estimated distance between the plurality of anchor nodes. A plurality of geographic coordinates of the plurality of anchor nodes is reconstructed based on the partial distance matrix. The plurality of geographic coordinates is reconstructed based on one or more of a geometric build-up algorithm, a shortest-path algorithm and a multidimensional scaling algorithm.

Claims

1. A method for determining geographic coordinates of nodes in a communications network, the method comprising:

determining geographic coordinates of at least a subset of a plurality of anchor nodes in part based on an estimated distance between at least two anchor nodes in the subset, the estimated distance being based on raw distances determined of the at least two anchor nodes from at least one non-anchor node located in a range of, and in communication with, the at least two anchor nodes; and

locating a geographical position of the at least one non-anchor node in part based on the geographic coordinates determined of the at least two anchor nodes.

2. The method of claim 1 further comprising:

determining the raw distances based on distance measurements determined at the at least two anchor nodes or the at least one non-anchor node located in the range of the at least two anchor nodes;

calculating the estimated distance between the at least two anchor nodes among the plurality of anchor nodes based on the raw distances determined; and

replacing a stored estimated distance with the calculated estimated distance if the calculated estimated distance is less than the stored estimated distance between the at least two anchor nodes and maintaining the stored estimated distance if the calculated estimated distance is greater than or equal to the stored estimated distance.

3. The method of claim 2 further comprising:

representing stored estimated distances between the at least two anchor nodes in the subset in a graphical representation, the graphical representation including the plurality of anchor nodes and at least one connection between the plurality of anchor nodes, the at least one connection corresponding to the calculated estimated distance between the at least two anchor nodes; and

estimating a geographic coordinate of at least one of the anchor nodes using at least one of the following methods;

geometric build-up, shortest-path, and multidimensional scaling.

4. The method of claim 2, wherein calculating the estimated distance between the at least two anchor nodes further includes:

summing the raw distances determined among the at least two anchor nodes and the at least one non-anchor node to obtain the calculated estimated distance between the at least two anchor nodes.

5. The method of claim 2, wherein the at least one non-anchor node communicates with the at least two anchor nodes given the at least one non-anchor node is located in the range of the at least two anchor nodes.

6. The method of claim 2, wherein calculating the estimated distance between the at least two anchor nodes includes adding raw distances determined of the at least two anchor nodes from the at least one non-anchor node.

7. The method of claim 2, wherein the distance measurements are obtained by applying at least one of the following metrics:

a time difference of arrivals, time of arrival, and signal strength difference measurement at the at least one non-anchor node or at the at least two anchor nodes.

8. The method of claim 1, wherein at least one of the at least two anchor nodes is a base station and the at least one non-anchor node is a mobile station.

9. The method of claim 1 wherein determining geographic coordinates includes:

reconstructing the geographic coordinates based on at least one of the following methods;

geometric build-up, shortest-path, and multidimensional scaling.

10. The method of claim 1, wherein a first anchor node of the at least two anchor nodes belongs to at least a first communication network and wherein a second anchor node of the at least two anchor nodes belongs to at least a second communication network, wherein the at least one non-anchor node is compatible with each of the first communication network and the second communication network.

11. The method of claim 3, wherein representing stored estimated distances between the at least two anchor nodes among the plurality of anchor nodes in the graphical representation further includes:

applying a breadth first search on the graphical representation to find a plurality of connected components in the graphical representation, wherein the plurality of connected components include at least one of the plurality of anchor nodes with the at least one connection; and

estimating a geographic coordinate of at least one anchor node and the non-anchor node using a method of geometric build-up.

12. The method of claim 11, wherein the method of geometric build-up includes:

locating at least three anchor nodes that have a connection with at least a first predetermined number of anchor nodes, wherein each of the at least three anchor nodes has a connection with each of the at least three anchor nodes; and

estimating at least three geographic coordinates corresponding to the at least three anchor nodes based on a method of coordinate construction.

13. The method of claim 12, wherein estimating the at least three geographic coordinates further includes:

adding the at least three anchor nodes to a set of fixed anchor nodes, wherein at least one geographic coordinate of each anchor node in the set of fixed anchor nodes is known;

traversing the graphical representation to find at least one unfixed anchor node, wherein the at least one unfixed anchor node is connected to a predetermined number of fixed anchor nodes;

determining at least one geographic coordinate of the at least one unfixed anchor node based on the predetermined number of fixed anchor nodes; and

adding the at least one unfixed anchor node to the set of fixed anchor nodes, if the at least one geographic coordinate is determined for the at least one unfixed anchor node.

14. The method of claim 13, wherein, if the predetermined number of fixed anchor nodes is one, then the method further comprises discontinuing the method geometric build-up.

15. The method of claim 13, wherein, if the predetermined number of fixed anchor nodes is two and the at least one unfixed anchor node is connected to the two fixed anchor nodes, then the method further comprises:

finding at least two possible geographic coordinates for the at least one unfixed anchor node, based on at least two estimated distances among the at least one unfixed anchor node and the two fixed anchor nodes;

assigning the at least one unfixed anchor node with the at least one geographic coordinate, the at least one geographic coordinate belonging to the at least two possible geographic coordinates, wherein the at least one geographic coordinate is farther or farthest amongst the at least two possible geographic coordinates from each fixed anchor node in the set of fixed anchor nodes; and

discontinuing the geometric build-up if the at least two possible geographic coordinates and the at least two estimated distances are inconsistent.

16. The method of claim 13, wherein, if the predetermined number of fixed anchor nodes is three or more and the at least one unfixed anchor node is connected to three or more fixed anchor nodes, then the method further comprises:

selecting at least three fixed anchor nodes, wherein at least three estimated distances of the at least one unfixed anchor node from the at least three fixed anchor nodes is at most a predetermined value;

determining the at least one geographic coordinate of the at least one unfixed anchor node using triangulation with the at least three fixed anchor nodes; and

discontinuing the geometric build-up if the at least one geographic coordinate and the at least three estimated distances are inconsistent.

17. The method of claim 13 further comprising estimating the geographic coordinate of the non-anchor node based on the coordinates of the anchor nodes.

18. The method of claim 17 further comprising using triangulation for estimating the geographic coordinate of the non-anchor node based on the coordinates of the anchor nodes.

19. The method of claim 13, wherein, if at least a second predetermined number of fixed anchor nodes is absent in the set of fixed anchor nodes, then reconstructing at least one geographic coordinate of at least one anchor node using at least one method selected from a group consisting of:

a shortest-path and multidimensional scaling.

31. The method of claim 1, wherein the at least two anchor nodes belong to different communications networks and provide service to the at least one non-anchor node, wherein the at least one non-anchor node is compatible with each of the different communications networks.

20. A system for determining geographic coordinates of nodes in a communications network, the system comprising:

a reconstruction module configured to determine geographic coordinates of at least a subset of a plurality of anchor nodes in part based on an estimated distance between at least two anchor nodes in the subset, the estimated distance being based on raw distances determined of the at least two anchor nodes from at least one non-anchor node located in a range of, and in communication with, the at least two anchor nodes; and

a location module configured to locate a geographical position of the at least one non-anchor node in part based on the geographic coordinates determined of the at least two anchor nodes.

21. The system of claim 20 further comprising:

a determining module configured to determine raw distances among at least two anchor nodes of the plurality of anchor nodes and at least one non-anchor node given the at least one non-anchor node is located in a range of the at least two anchor nodes.

22. The system of claim 20 further comprising:

a determining module configured to determine the raw distances based on distance measurements at the at least two anchor nodes or at the at least one non-anchor node given the at least one non-anchor node is located in the range of the at least two anchor nodes.

23. The system of claim 22 further comprising:

a calculating module configured to calculate the estimated distance between the least two anchor nodes among a plurality of anchor nodes based on the raw distances determined; and

a populating module configured to replace a stored estimated distance between the at least two anchor nodes if the calculated estimated distance is smaller that the stored estimated distance and to maintain the stored estimated distance if the calculated estimated distance is greater than or equal to the stored estimated distance.

24. The system of claim 23 wherein the calculation module is further configured to estimate the distance among the at least two anchor nodes and a plurality of anchor nodes based on the determined raw distances of the at least two anchor nodes from the at least one non-anchor node.

25. The system of claim 24 wherein the reconstruction module includes:

a graphical representation module configured to represent stored estimated distances between the at least two anchor nodes among a plurality of anchor nodes in a graphical representation, the graphical representation including the plurality of anchor nodes and at least one connection between the plurality of anchor nodes, the at least one connection based on the calculated estimated distance between the at least two anchor nodes;

a breadth first search module configured to apply a breadth first search on the graphical representation to find a plurality of connected components in the graphical representation, wherein the plurality of connected components include at least one of the plurality of anchor nodes; and

a positioning module configured to estimate a geographic coordinate of at least one of the anchor nodes by using at least one of the following methods;

geometric build-up, shortest-path, and multidimensional scaling to estimate a geographic coordinate of at least one anchor node.

26. The system of claim 25 wherein the reconstructing module is further configured to reconstruct a plurality of geographic coordinates of the plurality of anchor nodes based on at least one of the following:

a geometric build-up, shortest-path, and multidimensional scaling.

27. The system of claim 26, wherein, if the geometric build-up fails, then the positioning module is further configured to reconstruct at least one geographic coordinate of at least one anchor nodes using a shortest-path method, multidimensional scaling, or combination thereof.

28. The system of claim 26 wherein the position module is further configured to estimate the geographic coordinate of the non-anchor node based on the coordinates of the anchor nodes.

29. The system of claim 26 wherein the position module is further configured to estimate the geographic coordinates of the non-anchor node using triangulation.

30. A non-transitory computer readable medium having instructions stored thereon that, when executed by a computing platform, cause the computing platform to:

determine geographic coordinates of at least a subset of a plurality of anchor nodes in part based on an estimated distance between at least two anchor nodes in the subset, the estimated distance being based on raw distances determined of the at least two anchor nodes from at least one non-anchor node located in a range of, and in communication with, the at least two anchor nodes; and

locate a geographical position of the at least one non-anchor node in part based on the geographic coordinates determined of the at least two anchor nodes.