Node localization in communication networks

• US 7,457,860 B2
• Filed: 10/09/2003
• Issued: 11/25/2008
• Est. Priority Date: 10/09/2003
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Kang; Paul H
• Application Number:
  US10/682,754
• Publication Number:
  US 20050080924A1
• Time in Patent Office: 1,874 Days
• Field of Search: 709/224, 709/226, 709/238, 709/239, 709/242, 709/223, 702/150, 702/186, 4554561- 6, 715/734
• US Class Current: 709/223
• 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 a distributed communication network, the distributed communication network comprising a plurality of sub-networks, each sub-network having a plurality of nodes, wherein said nodes are separated by paths, the method comprising:

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

computing local maps for each sub-network within the distributed communication network by;

estimating the shortest path between a plurality of pairs of the nodes in the sub-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 local map of the location of said plurality of pairs of nodes within the sub-network utilizing said eigenvectors;

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

transforming the distributed communication network relative map to an absolute map for the distributed communication network,

wherein each of the sub-networks includes a local map having not less than one pair of the plurality of pairs of nodes within the distributed communication network.

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 edges are assigned a value of 1.

4. The method for deriving node localization information according to claim 2, wherein said shortest paths are estimated 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 each sub-network comprises all nodes in the sub-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 said local mapping range value varies for the sub-networks within said distributed network.

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

17. The method for deriving node localization information according to claim 1, wherein computing local maps for each sub-network within said distributed communication 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.

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

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

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

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

22. The method for deriving node localization information according to claim 21, 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.

23. The method for deriving node localization information according to claim 21, 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.

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

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

26. The method for deriving node localization information according to claim 24, 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.

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

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

computing local maps for each sub-network within the distributed communication network by;

estimating the shortest path between a plurality of pairs of the nodes in the sub-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 local map of the location of the plurality of pairs of nodes within the sub-network utilizing said eigenvectors;

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

transforming the distributed communication network relative map to an absolute map for the distributed communication network,

wherein each of the sub-networks includes a local map having not less than one pair of the plurality of pairs of nodes within the distributed communication network.