METHOD AND SYSTEM FOR HYBRID POSITIONING USING PARTIAL DISTANCE INFORMATION

• US 20080125161A1
• Filed: 04/18/2007
• Published: 05/29/2008
• Est. Priority Date: 04/19/2006
• Status: Active Grant

• Current Assignee: WiChorus, Inc. (Infinera Corp.)
• Original Assignee: WiChorus, Inc. (Infinera Corp.)
• Inventors: Jalil, Rehan, Ergen, Mustafa
• Granted Patent: US 7,880,676 B2
• Time in Patent Office: Days
• US Class Current: 455/524
• 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 at least one of an anchor node and a non-anchor node, the method comprising:

determining at least two distance measurements at predetermined intervals of time, each distance measurement of the at least two distance measurement corresponding to a raw distance of at least one non-anchor node from at least two anchor nodes, wherein the at least one non-anchor node is located in a range of the at least two anchor nodes, the at least two anchor nodes belonging to a plurality of anchor nodes and the at least one non-anchor node belonging to a plurality of non-anchor nodes, the plurality of anchor nodes and the plurality of non-anchor nodes located in one or more communication networks;

calculating at least one estimated distance between the at least two anchor nodes belonging to the plurality of anchor nodes based on the at least two distance measurements;

populating a partial distance matrix corresponding to the plurality of anchor nodes based on a predetermined condition, wherein the partial distance matrix comprises at least one distance entry; and

reconstructing a plurality of geographic coordinates of the plurality of anchor nodes based on the 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 at least two distance measurements are 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 for the at least two anchor nodes.

5. The method of claim 1, wherein the calculating step comprises calculating the at least one estimated distance by adding the at least two distance measurements.

6. The method of claim 1, wherein the predetermined condition comprises the at least one distance entry being the at least one estimated distance, if the at least one estimated distance is smaller than a stored at least one estimated distance, wherein the stored at least one estimated distance corresponds to the at least one estimated distance.

7. The method of claim 6, wherein the predetermined condition comprises the at least one distance entry being the stored at least one estimated distance, if the stored at least one estimated distance is smaller than the at least one estimated distance.

8. The method of claim 1, wherein the reconstructing step 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 comprise at least one connection between the at least two anchor nodes, if the estimated distance is calculated for the at least two or more anchor nodes;

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.

9. The method of claim 8, 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.

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

11. The method of claim 9, 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.

12. The method of claim 9, 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.

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

14. The method of claim 9, 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.

15. A system for positioning at least one of an anchor node and a non-anchor node, the system comprising:

a determining module, wherein the determining module is configured for determining at least two distance measurements at predetermined intervals of time, each distance measurement of the at least two distance measurement corresponding to a raw distance of at least one non-anchor node from each of at least two anchor nodes, wherein the at least one non-anchor node is in located a range of the at least two anchor nodes, the at least two anchor nodes belonging to a plurality of anchor nodes and the at least one non-anchor node belonging to a plurality of non-anchor nodes, the plurality of anchor nodes and the plurality of non-anchor nodes located in one or more communication networks;

a calculating module, wherein the calculating module is configured for calculating at least one estimated distance between the at least two anchor nodes belonging to the plurality of anchor nodes based on the at least two distance measurements;

a populating module, wherein the populating module is configured for populating a partial distance matrix corresponding to the plurality of anchor nodes based on a predetermined condition, wherein the partial distance matrix comprises at least one distance entry; 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 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.

16. The system of claim 15, wherein the calculating module is configured for calculating the at least one estimated distance by adding the at least two distance measurements.

17. The system of claim 15, 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 comprise at least one connection between the at least two anchor nodes if the estimated distance is calculated for the at least two or more anchor n7odes;

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.

18. The system of claim 15, 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.