Method and system for hybrid positioning using partial distance information

• US 7,880,676 B2
• Filed: 04/18/2007
• Issued: 02/01/2011
• Est. Priority Date: 04/19/2006
• Status: Expired due to Fees

• Current Assignee: WiChorus, Inc. (Infinera Corp.)
• Original Assignee: WiChorus, Inc. (Infinera Corp.)
• Inventors: Jalil, Rehan, Ergen, Mustafa
• Primary Examiner(s): Tarcza; Thomas H
• Assistant Examiner(s): Nguyen; Nga X
• Application Number:
  US11/736,597
• Publication Number:
  US 20080125161A1
• Time in Patent Office: 1,385 Days
• Field of Search: 342458-465
• 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 positioning a plurality of anchor nodes in one or more communication networks, the method comprising:

determining raw distances of at least two anchor nodes of the plurality of anchor nodes from at least one non-anchor node at predetermined intervals of time, wherein the at least one non-anchor node is located in a range of the at least two anchor nodes;

calculating an estimated distance between the at least two anchor nodes at the predetermined intervals of time based on the determined raw distances of the at least two anchor nodes from the at least one non-anchor node;

populating a partial distance matrix with the estimated distance between the at least two anchor nodes at the predetermined intervals of time based on a predetermined condition, wherein the predetermined condition is a condition to update stored estimated distance between the at least two anchor nodes with the estimated distance; and

reconstructing a plurality of geographic coordinates of the plurality of anchor nodes based on the populated partial distance matrix, wherein the plurality of geographic coordinates are reconstructed based on at least one of a geometric build-up algorithm, a shortest-path algorithm, and a multidimensional scaling algorithm.

2. The method of claim 1, wherein an anchor node is a base station and a non-anchor node is a mobile station.

3. 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 a second anchor node of the at least two anchor nodes belongs to at least a second communication network, the first communication network and the second communication network belonging to the one or more communication networks, wherein the non-anchor node is compatible with each of the first communication network and the second communication network.

4. The method of claim 1, wherein the raw distance of the at least two anchor nodes from the non anchor node is obtained by applying at least one of a time-difference of arrivals algorithm, a time of arrival algorithm, and a signal strength difference measurement algorithm at the at least one non-anchor node.

5. The method of claim 1, wherein if the estimated distance is smaller than a stored estimated distance, then the stored estimated distance is updated with the estimated distance;

and

if not, then the stored estimated distance is maintained.

6. The method of claim 1, wherein the reconstructing the plurality of geographic coordinates of the plurality of anchor nodes comprises:

representing the partial distance matrix in a graphical representation, wherein the graphical representation comprises the plurality of anchor nodes and one or more connections between the plurality of anchor nodes, wherein the one or more connections are based on the estimated distance between the at least two anchor nodes in the populated partial distance matrix;

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 comprise one or more of the plurality of anchor nodes with the one or more connections; and

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

7. The method of claim 6, wherein the geometric build-up algorithm comprises:

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;

estimating at least three geographic coordinates corresponding to the at least three anchor nodes based on a coordinate construction algorithm;

adding the at least three anchor nodes to a set of fixed anchor nodes, wherein one or more geographic coordinates of each anchor node in the set of fixed anchor nodes are 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 second predetermined number of fixed anchor nodes;

determining at least one geographic coordinate of the at least one unfixed anchor node based on the second 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.

8. The method of claim 7, wherein if the second predetermined number of fixed anchor nodes is one, then discontinuing the geometric build-up algorithm.

9. The method of claim 7, wherein if the second predetermined number of fixed anchor nodes is two, the at least one unfixed anchor node being connected to two fixed anchor nodes, then performing:

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

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 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 algorithm, if the at least two possible geographic coordinates and the at least two estimated distances are inconsistent.

10. The method of claim 7, wherein if the second predetermined number of fixed anchor nodes is three or more, the at least one unfixed anchor node being connected to three or more fixed anchor nodes, then performing:

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 a triangulation algorithm with the at least three fixed anchor nodes; and

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

11. The method of claim 7 further comprises estimating the geographic coordinate of the non-anchor node based on the set of fixed anchor nodes.

12. The method of claim 7, wherein if at least a third predetermined number of fixed anchor nodes is absent in the set of fixed anchor nodes, then one or more geographic coordinates of one or more anchor nodes are reconstructed using at least one of a shortest-path algorithm and a multidimensional scaling algorithm.

17. The method of claim 1, wherein the at least one non-anchor node communicates with the at least two anchor nodes when the at least one non-anchor node is located in the range of the at least two anchor nodes.

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

20. The method of claim 5, wherein the stored estimated distance comprises a distance between the at least two anchor nodes.

13. A system for positioning a plurality of anchor nodes in one or more communication networks, the system comprising:

a determining module, wherein the determining module is configured for determining raw distances of at least two anchor nodes of the plurality of anchor nodes from at least one non-anchor node at predetermined intervals of time, wherein the at least one non-anchor node is located in a range of the at least two anchor nodes;

a calculating module, wherein the calculating module is configured for calculating an estimated distance between the at least two anchor nodes at the predetermined intervals of time based on determined raw distances of the at least two anchor nodes from the at least one non-anchor node;

a populating module, wherein the populating module is configured for populating a partial distance matrix with the estimated distance between the at least two anchor nodes at the predetermined intervals of time based on a predetermined condition, wherein the predetermined condition is a condition to update stored estimated distance between the at least two anchor nodes with the estimated distance; and

a reconstructing module, wherein the reconstructing module is configured for reconstructing a plurality of geographic coordinates of the plurality of anchor nodes based on the populated partial distance matrix, wherein the plurality of geographic coordinates are reconstructed based on at least one of a geometric build-up algorithm, a shortest-path algorithm, and a multidimensional scaling algorithm.

14. The system of claim 13, wherein the reconstructing module comprises:

a graphical representation module, wherein the graphical representation module is configured for representing the partial distance matrix in a graphical representation, wherein the graphical representation comprises the plurality of anchor nodes and one or more connections between the plurality of anchor nodes, wherein the one or more connections are based on the estimated distance between the at least two anchor nodes in the populated partial distance matrix;

a breadth first search module, wherein the breadth first search module is configured for 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 comprise one or more of the plurality of anchor nodes; and

a positioning module, wherein the positioning module is configured for using at least one of a geometric build-up algorithm, a shortest-path algorithm and a multidimensional scaling algorithm to estimate a geographic coordinate of the at least one of the anchor node and the non-anchor node.

15. The system of claim 13, wherein if the geometric build-up algorithm fails, then the positioning module reconstructs one or more geographic coordinates of one or more anchor nodes using at least one of the shortest-path algorithm and the multidimensional scaling algorithm.

18. The system of claim 13, wherein the at least one non-anchor node communicates with the at least two anchor nodes when the at least one non-anchor node is located in the range of the at least two anchor nodes.

16. A non-transitory computer readable medium having instructions, that when executed by a computing platform, result in execution of a method for positioning a plurality of anchor nodes in one or more communication networks, the method comprising:

determining raw distances of at least two anchor nodes of the plurality of anchor nodes from at least one non-anchor node at predetermined intervals of time, wherein the at least one non-anchor node is located in a range of the at least two anchor nodes;

calculating an estimated distance between the at least two anchor nodes at the predetermined intervals of time based on the determined raw distances of the at least two anchor nodes from the at least one non-anchor node;

populating a partial distance matrix with the estimated distance between the at least two anchor nodes at the predetermined intervals of time based on a predetermined condition, wherein the predetermined condition is a condition to update stored estimated distance between the at least two anchor nodes with the estimated distance; and

reconstructing a plurality of geographic coordinates of the plurality of anchor nodes based on the populated partial distance matrix, wherein the plurality of geographic coordinates are reconstructed based on at least one of a geometric build-up algorithm, a shortest-path algorithm, and a multidimensional scaling algorithm.