Paractical network node coordinate estimation

Abstract

Substantially accurate estimation of coordinates of a subject network node in a coordinate space is accomplished by considering designated coordinates of other positioned nodes within the network. The designation of coordinates in the coordinate space to such nodes allows the computation of predicted coordinate distances between two network nodes based on the coordinates. By optimizing the network distance errors between measured distances and predicted coordinate distances, the predicted coordinates of a subject node joining the network can be iteratively refined. With these estimated coordinates, the coordinate distance between two points in the space may be computed as a prediction of the network distance between the two corresponding nodes. Furthermore, coordinate-based coordinate estimation lends itself to security precautions to protect against malicious reference nodes or external interference.

1 . A computer-readable media embodying computer-executable instructions for performing a method comprising: 
 computing distances between coordinates of a subject node in a network and coordinates of each of a plurality of reference nodes in the network; and    adjusting the coordinates of the subject node based on the computed distances.    
   
   
       2 . A computer-readable media as recited in  claim 1 , wherein one of the reference nodes is selected randomly from a group of nodes in the network.  
   
   
       3 . A computer-readable media as recited in  claim 1 , wherein all of the reference nodes are selected randomly from a group of nodes in the network.  
   
   
       4 . A computer-readable media as recited in  claim 1 , wherein the method further comprises: 
 measuring distances between the subject node and each of a plurality of reference nodes.    
   
   
       5 . A computer-readable media as recited in  claim 1 , wherein adjusting the coordinates of the subject node based on the determined distances comprises: 
 measuring distances between the subject node and each of the plurality of reference nodes;    comparing the computed distances and the measured distances; and    adjusting the coordinates of the subject node based on the comparison.    
   
   
       6 . A computer-readable media as recited in  claim 1 , wherein adjusting the coordinates of the subject node based on the determined distances comprises: 
 measuring distances between the subject node and each of the plurality of reference nodes;    determining errors between the computed distances and the measured distances; and    adjusting the coordinates of the subject node based on the determined errors.    
   
   
       7 . A computer-readable media as recited in  claim 1 , wherein the coordinates of the subject node and the plurality of reference nodes are relative to a coordinate space having greater than three dimensions.  
   
   
       8 . A computer-readable media as recited in  claim 1 , wherein the coordinates of the subject node and the plurality of reference nodes are relative to a d-dimensional coordinate space and wherein the number of selected nodes is greater than or equal to (d+1).  
   
   
       9 . A computer-readable media as recited in  claim 1 , wherein the coordinates of at least one of the reference nodes is received from the at least one reference node.  
   
   
       10 . A computer-readable media as recited in  claim 1 , wherein the coordinates for at least one of the reference nodes is received from a reference node other than the at least one reference node.  
   
   
       11 . A computer-readable media as recited in  claim 6 , wherein measuring distances between the subject node and each of a plurality of reference nodes includes determining round-trip delay times between the subject node and each of the reference nodes.  
   
   
       12 . A computer-readable media as recited in  claim 1 , wherein the method further comprises: 
 measuring distances between the subject node and each of the plurality of reference nodes; and    computing an attacker detection metric based on the measured distances.    
   
   
       13 . The method of  claim 1 , wherein the method further comprises: 
 measuring distances between the subject node and each of the plurality of reference nodes;    computing an attacker detection metric based on the measured distances;    replacing a reference node with a new reference node selected from the network to define a new plurality of reference nodes, the replaced reference node exhibiting a greater attacker detection metric than any other reference node in the plurality of reference nodes;    measuring a distance between the subject node and the new reference node; and computing new coordinates for the subject node based on the measured distances distance between the subject node and the new plurality of reference nodes and coordinates for each reference node of the new plurality of reference nodes.    
   
   
       14 . A system comprising: 
 a network distance module computing distances between coordinates of a subject node in a network and coordinates of each of a plurality of reference nodes in the network; and    a coordinate estimation module adjusting coordinates for the subject node based on the computed distances and the coordinates for each of the reference nodes.    
   
   
       15 . The system of  claim 14 , further comprising: 
 a network distance estimation module estimating a network distance between the subject node and a positioned node by computing a coordinate distance between the coordinates of the subject node and coordinates of the positioned node.