Identification of the location of nodes distributed in ad hoc networks

• US 20070195759A1
• Filed: 02/17/2006
• Published: 08/23/2007
• Est. Priority Date: 02/17/2006
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Sinha, Koushik, Chowdhury, Atish
• Granted Patent: US 8,040,859 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• 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
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A location of node i in a network having a plurality of nodes is identified by intersecting regions that are guaranteed to contain the node i with respect the other nodes that are neighbors of the node i and iteratively minimizing the size of the intersection region containing the node i.

Claims

1. A method of identifying a location of a node i in a network having a plurality of nodes comprising:

receiving a location of a region that is guaranteed to contain the node i, wherein the determining of a location of a region is based on range information obtained with respect to other nodes in a neighborhood of the node i;

determining a region of residence of the node i based on the region that is guaranteed to contain the node i, wherein the region residence has a size; and

,

iteratively minimizing the size of the region of residence of the node i.

2. The method of claim 1 wherein the iteratively minimizing of the size of the region of residence of the node i terminates when the minimum region of residence of the node i is not improved as a result of an iteration.

3. The method of claim 1 wherein the determining of the region of residence of the node i comprises determining a minimum region of residence of the node i based on a viewed region of residence of the node i and a previously determined minimum region of residence of the node i.

4. The method of claim 3 wherein the iteratively minimizing of the size of the region of residence of the node i terminates when the minimum region of residence of the node i is not improved as a result of an iteration.

5. The method of claim 1 wherein the receiving of a location of a region that is guaranteed to contain the node i comprises receiving a region of a node j that was extended in every direction by a measured range value r_ij, wherein the node j is in the neighborhood of the node i, and wherein r_ij is based on a range between nodes i and j.

6. The method of claim 1 wherein the iteratively minimizing of the size of the region of residence of the node i comprises:

determining a region of residence of a node j in the view of the node i, wherein the node j is within a transmission range of the node i; and

,

transmitting to node j the region of residence of the node j in the view of the node i.

7. The method of claim 6 wherein the iteratively minimizing of the size of the region of residence of the node i terminates when the minimum region of residence of the node i is not improved as a result of an iteration.

8. The method of claim 6 wherein the determining of the region of residence of the node i comprises determining a minimum region of residence of the node i based on a viewed region of residence of the node i and a previously determined minimum region of residence of the node i.

9. The method of claim 8 wherein the iteratively minimizing of the size of the region of residence of the node i terminates when the minimum region of residence of the node i is not improved as a result of an iteration.

10. The method of claim 6 wherein the receiving of a location of a region that is guaranteed to contain the node i comprises receiving a region of a node j that was extended in every direction by a measured range value r_ij, wherein the node j is in the neighborhood of the node i, and wherein r_ij is based on a range between nodes i and j.

11. A computer readable storage medium having program code stored thereon which, when executed, identifies a location of node i in a wireless network having a plurality of nodes by performing the following functions:

a) receiving a location of a first region from a node j, wherein the first region is guaranteed to contain the node i, wherein the first region has a size, wherein the size of the first region is dependent upon a range between the nodes i and j, and wherein the node j is within a transmission range of the node i;

b) receiving a location of a second region from a node k, wherein the second region is guaranteed to contain the node i, wherein the second region has a size, wherein the size of the second region is dependent upon a range between the nodes i and k, and wherein the node k is within a transmission range of the node i;

c) receiving a location of a third region from a node l, wherein the third region is guaranteed to contain the node i, wherein the third region has a size, wherein the size of the third region is dependent upon a range between the nodes i and l, and wherein the node l is within a transmission range the node i;

d) determining a minimum region of residence of the node i from an intersection of the first, second, and third regions; and

,

e) iteratively reducing the size of the minimum region of residence of the node i.

12. The computer readable storage medium of claim 11 wherein the function of iteratively reducing the size of the minimum region of residence of the node i terminates when the minimum region of residence of the node i is not improved as a result of an iteration.

13. The computer readable storage medium of claim 11 wherein the function of determining a minimum region of residence of the node i comprises determining a minimum region of residence of the node i based on a previously determined minimum region of residence of the node i.

14. The computer readable storage medium of claim 13 wherein the function of iteratively reducing the size of the minimum region of residence of the node i terminates when the minimum region of residence of the node i is not improved as a result of an iteration.

15. The computer readable storage medium of claim 11 wherein the function of receiving a location of a first region from a node j comprises receiving a region of the node j that is extended in every direction by a measured range value r_ij between the nodes i and j, wherein the function of receiving a location of a second region from a node k comprises receiving a region of the node k that is extended in every direction by a measured range value r_ik between the nodes i and k, and wherein the function of receiving a location of a third region from a node l comprises receiving a region of the node l that is extended in every direction by a measured range value r_il between the nodes i and l.

16. The computer readable storage medium of claim 11 wherein the function of iteratively reducing the size of the minimum region of residence of the node i comprises:

determining a region of residence of the node j in the view of the node i;

transmitting to node j the region of residence of the node j in the view of the node i;

determining a region of residence of the node k in the view of the node i;

transmitting to node k the region of residence of the node k in the view of the node i;

determining a region of residence of the node l in the view of the node i; and

,

transmitting to node l the region of residence of the node l in the view of the node i.

17. The computer readable storage medium of claim 16 wherein the function of iteratively reducing the size of the minimum region of residence of the node i terminates when the minimum region of residence of the node i is not improved as a result of an iteration.

18. The computer readable storage medium of claim 16 wherein the function of determining a minimum region of residence of the node i comprises determining a minimum region of residence of the node i based on a previously determined minimum region of residence of the node i.

19. The computer readable storage medium of claim 18 wherein the function of iteratively reducing the size of the minimum region of residence of the node i terminates when the minimum region of residence of the node i is not improved as a result of an iteration.

20. The computer readable storage medium of claim 16 wherein the function of receiving a location of a first region from a node j comprises receiving a region of the node j that is extended in every direction by a measured range value r_ij between the nodes i and j, wherein the function of receiving a location of a second region from a node k comprises receiving a region of the node k that is extended in every direction by a measured range value r_ik between the nodes i and k, and wherein the function of receiving a location of a third region from a node l comprises receiving a region of the node l that is extended in every direction by a measured range value r_il between the nodes i and l.