Node localization in communication networks

• US 20050080924A1
• Filed: 10/09/2003
• Published: 04/14/2005
• Est. Priority Date: 10/09/2003
• Status: Active Grant

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Ruml, Wheeler, Shang, Yi
• Granted Patent: US 7,457,860 B2
• Time in Patent Office: Days
• US Class Current: 709/239
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal

Abstract

Disclosed herein is a method for deriving node localization information within communication networks having a plurality of nodes, which are separated by node paths. The method includes estimating the shortest path between multiple pairs of nodes in the network and constructing a matrix encompassing the estimated shortest paths. Multidimensional scaling is then applied to the matrix and the largest eigenvectors of the transformed matrix are identified. From this is constructed a relative map of the location of the pairs of nodes within the network by utilization of the eigenvectors.

Claims

1. A method for deriving node localization information within communication networks having a plurality of nodes, wherein said nodes are separated by paths comprising:

estimating the shortest path between a plurality of pairs of the nodes in the network;

constructing a matrix, wherein said matrix includes said estimated shortest paths;

applying multidimensional scaling to said matrix and identifying the eigenvectors corresponding to the largest eigenvalues; and

constructing a relative map of the location of said plurality of pairs of nodes within the network utilizing said eigenvectors.

2. The method for deriving node localization information according to claim 1, wherein computing said shortest paths comprises:

assigning estimated values to the initial edges in the graph; and

applying an all-pairs shortest path algorithm.

3. The method for deriving node localization information according to claim 2, wherein said edges are assigned a value of 1.

4. The method for deriving node localization information according to claim 2, wherein said estimated values are based on information such as ranging data, received signal strength, or other means.

5. The method for deriving node localization information according to claim 1, wherein said plurality of pairs of the nodes in the network comprises all nodes in the network.

6. The method for deriving node localization information according to claim 1, wherein said relative map comprises a two-dimensional map.

7. The method for deriving node localization information according to claim 1, wherein said relative map comprises a three-dimensional map.

8. The method for deriving node localization information according to claim 1, wherein said relative map includes anchor nodes.

9. The method for deriving node localization information according to claim 8, further comprising transforming said relative map to an absolute map based on the absolute position of said anchor nodes.

10. The method for deriving node localization information according to claim 9, wherein transforming said relative map to an absolute map comprises one or more of translation, reflection, orthogonal rotation, or scaling.

11. The method for deriving node localization information according to claim 8, wherein not fewer than three said anchor nodes are utilized to construct a two-dimensional relative map.

12. The method for deriving node localization information according to claim 8, wherein not less than four said anchor nodes are utilized to construct a three-dimensional relative map.

13. The method for deriving node localization information according to claim 9, further comprising refining said transformed relative map, wherein refining comprises causing distances between nodes within a specified refinement range to better match estimated or measured distances.

14. The method for deriving node localization information according to claim 13, wherein said refinement range is defined based on hops and specifies those nodal distances to be considered.

15. The method for deriving node localization information according to claim 1, wherein the network comprises a distributed network having a plurality of sub-networks, wherein each said sub-network includes a local map having not less than one pair of said plurality of pairs of nodes within the network.

16. The method for deriving node localization information according to claim 15, comprising:

setting not less than one value for a local mapping range;

computing local maps for each sub-network within said distributed network;

merging said local maps for each sub-network to form a relative map for said distributed network; and

transforming said distributed network relative map to an absolute map for said distributed network.

17. The method for deriving node localization information according to claim 16, wherein said local mapping range value varies for the sub-networks within said distributed network.

18. The method for deriving node localization information according to claim 16, wherein said local mapping range value is defined based on hops.

19. The method for deriving node localization information according to claim 16, wherein computing local maps for each sub-network within said distributed network comprises:

computing the shortest distance between all pairs in a sub-network node'"'"'s local mapping range;

constructing a distance matrix for each said sub-network, wherein said distance matrix includes said shortest path distances;

applying multidimensional scaling to each said distance matrix and identifying the largest eigenvectors; and

constructing said local map of the location of said plurality of pairs of nodes within each said sub-network utilizing said eigenvectors.

20. The method for deriving node localization information according to claim 16, wherein said local maps are merged either sequentially or in parallel.

21. The method for deriving node localization information according to claim 16, wherein said local maps are merged randomly.

22. The method for deriving node localization information according to claim 16, wherein said local maps are merged according to specified properties.

23. The method for deriving node localization information according to claim 16, wherein said local maps are merged by patching.

24. The method for deriving node localization information according to claim 23, wherein patching comprises:

randomly selecting a sub-network node, wherein said sub-network node includes an associated local map;

identifying said randomly selected sub-network node local map as the core map; and

merging neighboring sub-network node local maps with said core map.

25. The method for deriving node localization information according to claim 23, wherein patching said sub-network local maps together comprises patching together not fewer than two of said sub-network local maps, wherein patching said not fewer than two of said sub-network local maps comprises:

selecting a first node within a sub-network having a first local map, wherein said first local map includes a plurality of said pairs of nodes;

selecting a second sub-network having a second local map, wherein said second sub-network local map includes a plurality of said pairs of nodes and wherein said first local map and said second local map include a maximum number of common nodes;

merging said first local map and said second local map to form a first patched map;

selecting a next node from said first patched local map;

selecting a different sub-network having a different local map, wherein said different local map includes a plurality of said pairs of nodes and wherein said first patched local map and said different local map include a maximum number of common nodes;

merging said first patched local map and said different local map to form a second patched map; and

repeating selecting a next node, selecting a different sub-network, and merging said patched local map and said different local map until all network nodes are included in a final patched global map.

26. The method for deriving node localization information according to claim 16, wherein transforming said distributed network relative map comprises not less than one of translation, reflection, orthogonal rotation, or scaling.

27. The method for deriving node localization information according to claim 16, further comprising refining said relative map for said distributed network.

28. The method for deriving node localization information according to claim 26, wherein refining said relative map for said distributed network comprises causing the computed distances between neighbor nodes to match measured distances between said neighbor nodes.

29. An article of manufacture comprising a computer usable medium having computer readable program code embodied in said medium which, when said program code is executed by said computer causes said computer to perform method steps for deriving node localization information within communication networks having a plurality of nodes, wherein the nodes are separated by paths comprising:

estimating the shortest path between a plurality of pairs of the nodes in the network;

constructing a matrix, wherein said matrix includes said estimated shortest paths;

applying multidimensional scaling to said matrix and identifying and the largest eigenvectors; and

constructing a relative map of the location of said plurality of pairs of nodes within the network utilizing said eigenvectors.