Establishing a coordinate system and coordinates for nodes in a network

• US 20060050651A1
• Filed: 08/19/2004
• Published: 03/09/2006
• Est. Priority Date: 08/19/2004
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Brignone, Cyril, Pradhan, Salil, Connors, Tim
• Application Number:
  US10/922,627
• Publication Number:
  US 20060050651A1
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks

Abstract

A method of determining coordinates for nodes in a network. In response to a node being selected, the node broadcasts a request to other nodes for respective coordinate information of the other nodes. Based on the response to the request, the node takes one of the following steps. The node establishes itself as an origin of the coordinate system if no nodes respond to the request with coordinates. The node establishes a first axis of the coordinate system if one node responds to the request with coordinates. The node establishes a second axis of the coordinate system if two nodes respond to the request with coordinates. And, the node determines coordinates for the node based on distance measurements to selected nodes having established coordinates if three nodes respond to the request with coordinates.

Claims

1. A method of establishing a coordinate system for a network of nodes, comprising:

establishing an origin of said coordinate system by;

receiving an indication that a first node is selected; and

automatically determining that said first node is said origin of said coordinate system in response to said indication that said first node is selected; and

establishing a first axis for said coordinate system by;

receiving an indication that a second node is selected;

automatically determining said first axis based on a line between said first node and said second node in response to said indication that said second node is selected.

2. The method of claim 1, further comprising:

establishing a second axis for said coordinate system by;

receiving an indication that a third node is selected; and

automatically determining said second axis based on position of said third node with respect to said first and second nodes in response to said indication that said third node is selected.

3. The method of claim 2, further comprising:

establishing a third axis for said coordinate system by;

receiving an indication that a fourth node is selected; and

automatically determining said third axis based on said relative positions of said first, second, third, and fourth nodes in response to said indication that said fourth node is selected.

4. The method of claim 1, further comprising, in response to said indications that said first, second, and third nodes are selected, said first, second, and third nodes broadcasting requests for other nodes to respond with their respective coordinates.

5. The method of claim 4, further comprising determining that said origin, said first axis, and said second axis are to be determined based on responses, if any, from said requests.

6. The method of claim 1, wherein said automatically determining that said first node is said origin of said coordinate system further comprises:

said first node broadcasting a first request for other nodes to respond with respective coordinates for said other nodes; and

said first node establishing itself as said origin of said coordinate system in response to said first node determining that no other node in said network responds to said first request.

7. The method of claim 6, wherein said automatically determining said first axis based on the line between said first node and said second node comprises

said second node broadcasting a second request for other nodes to respond with respective coordinates for said other nodes;

and

said second node determining that only said first node responds to said second request, wherein said second node determines that said second node is to establish said first axis.

8. A method of propagating an established coordinate system, comprising:

determining a first pair of possible coordinates for a new node, based on first distance measurements between said new node and first nodes having first respective node coordinates;

determining a second pair of possible coordinates for said new node, based on second distance measurements between said new node and second nodes having second respective node coordinates, wherein said second distance measurements comprise at least one measurement to a node not in said first nodes; and

determining defined coordinates for said new node by determining one set of coordinates from each of said first and said second pair of possible coordinates as valid coordinates and basing said defined coordinates on said determined valid coordinates.

9. The method of claim 8, further comprising determining that nodes to use for distance measurements are said first nodes and said second nodes.

10. The method of claim 8, further comprising:

determining a third pair of possible coordinates for said new node, based on third distance measurements between said new node and third nodes having third respective node coordinates, and wherein;

said determining defined coordinates for said new node by determining one set of coordinates from each of said first and said second pair of possible coordinates as valid coordinates comprises determining one set of coordinates from each of said first, said second, and said third pair of possible coordinates.

11. The method of claim 8, wherein said basing said defined coordinates on said valid coordinates comprises determining a center of gravity of said valid coordinates.

12. The method of claim 8, wherein said established coordinate system has two-dimensions and said determining the first pair of possible coordinates for the new node comprises determining said first pair of possible coordinates based on distance measurements to two nodes in said first nodes.

13. The method of claim 8, wherein said established coordinate system has three-dimensions and said determining the first pair of possible coordinates for the new node comprises determining said first pair of possible coordinates based on distance measurements to three nodes in said first nodes.

14. The method of claim 8, further comprising selecting said first nodes and second nodes from a group of nodes having established coordinates based on how accurate said established coordinates are expected to be.

15. The method of claim 14, wherein said selecting said first nodes and second nodes is further based on a distance between nodes in said first nodes.

16. The method of claim 14, wherein said new node selecting said first nodes and second nodes is further based on alignment of nodes in said first nodes and second nodes.

17. A method of establishing coordinates for nodes in a network, comprising:

in response to a first node being selected, said first node broadcasting a request to other nodes for respective coordinate information of said other nodes; and

said first node establishing itself as an origin of said coordinate system if none of said other nodes respond to said request with coordinates for said other nodes;

said first node establishing a first axis of said coordinate system if one node of said other nodes responds to said request with coordinates for said one node;

said first node establishing a second axis of said coordinate system if two nodes of said other nodes respond to said request with respective coordinates for said two nodes; and

said first node determining coordinates for said first node based on distance measurements to selected nodes of said other nodes having established coordinates if three nodes of said other nodes respond to said request with respective coordinates for said three nodes.

18. The method of claim 17, wherein said first node determining coordinates for said first node comprises:

determining pairs of potential coordinates based on distances between said first node and said nodes having established coordinates;

selecting one set of coordinates from each of said pairs of potential coordinates to form valid coordinates; and

basing coordinates of said first node on said valid coordinates.

19. The method of claim 17, wherein said first node determines said selected nodes having established coordinates from a group of nodes having established coordinates based on how accurately said established coordinates of said group of nodes are expected to be.

20. The method of claim 19, wherein first new node determining said selected nodes is further based on a distance between nodes identified as candidate nodes in said group of nodes.

21. The method of claim 20, further comprising rejecting one of said candidate nodes if said distance is less than a pre-determined value.

22. The method of claim 20, further comprising rejecting one of said candidate nodes if said distance is less than a value learned by said network.

23. The method of claim 20, wherein first new node determining said selected nodes is further based on an angle formed between said candidate nodes.

24. The method of claim 23, further comprising rejecting one of said candidate nodes if said angle is greater than a value learned by said network.

25. A method of propagating an established coordinate system, comprising:

a new node determining a first pair of possible locations for said new node, based on a first at least one distance measurement to at least one node in a first group of nodes having respective node locations;

said new node determining a second pair of possible locations for said new node, based on a second at least one distance measurement to at least one node in a second group of nodes having respective node locations, wherein said second distance measurements comprise at least one measurement to a node not in said first group of nodes; and

said new node determining a defined location for said new node by determining a location from each of said first and second pair as a valid location and basing said defined location on said determined valid locations.

26. The method of claim 25, wherein said coordinate system has one-dimension and said determining a first pair of possible locations for said new node comprises said new node determining said first pair of possible locations for said new node, based on distance measurements to one node in said first group of nodes.

27. The method of claim 25, wherein said coordinate system has two-dimensions and said determining a first pair of possible locations for said new node comprises determining said first pair of possible locations based on distance measurements to two nodes in said first group of nodes.

28. The method of claim 25, wherein said coordinate system has three-dimensions and said determining a first pair of possible locations for said new node comprises determining said first pair of possible locations based on distance measurements to three nodes in said first group of nodes.

29. A location aware device, comprising:

a selection unit configured to receive an indication that the device is selected;

a communication unit configured to communicate with other devices; and

a processing unit coupled to said communication unit and said selection unit, said processing unit configured to;

in response to said indication that the device is selected, control the communication unit to determine how many other devices have already been selected;

establish said device as an origin of said coordinate system if no other devices respond with an indication that the other devices have been selected;

establish a first axis of said coordinate system if one other device indicates that the one other device has been selected; and

establish a second axis of said coordinate system if two other devices indicate that said two other devices have been selected.

30. The device of claim 29, wherein said processing unit is further configured to determine coordinates for said device based on distance measurements to other devices having established coordinates if three other devices indicate that said three other devices have been selected.

31. The device of claim 29, wherein said processing unit is further configured to:

determine a first pair of possible coordinates for said device, based on first distance measurements between said device and first nodes having first respective node coordinates;

determine a second pair of possible coordinates for said device, based on second distance measurements between said device and second nodes having second respective node coordinates, wherein said second distance measurements comprise at least one measurement to a node not in said first nodes; and

determine defined coordinates for said device by determining one set of coordinates from each of said first and said second pair of possible coordinates as valid coordinates and basing said defined coordinates on said determined valid coordinates.

32. The device of claim 31, wherein said processing unit is further configured to determine said first nodes and second nodes from a group of nodes having established coordinates based on how accurate said established coordinates are expected to be.

33. The device of claim 32, wherein said processing unit is further configured to determine said first nodes and second nodes based on a distance between nodes in said first nodes.

34. The device of claim 33, wherein said processing unit is further configured to determine said first nodes and second nodes based on alignment of nodes in said first nodes and second nodes.

35. The device of claim 29, wherein said selection unit comprises a power on switch for the device.

36. The device of claim 29, wherein said selection unit comprises a switch that has a dedicated purpose of selecting the device.

37. The device of claim 29, wherein said communication unit comprises a radio frequency transceiver and an ultrasound transceiver.