Identification of the location of nodes distributed in ad hoc networks

• US 8,040,859 B2
• Filed: 02/17/2006
• Issued: 10/18/2011
• Est. Priority Date: 02/17/2006
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Chowdhury, Atish Datta, Sinha, Koushik
• Primary Examiner(s): Karikari; Kwasi
• Application Number:
  US11/357,839
• Publication Number:
  US 20070195759A1
• Time in Patent Office: 2,069 Days
• Field of Search: 4554561-4566, 455/457, 455/422, 455/440, 370/338, 340988-996, 342/450
• US Class Current: 370/338
• 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 non-transitory computer readable storage medium having program code stored thereon which, when executed, identifies a location of a first 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 second node, wherein the first region is guaranteed to contain the first node, wherein the first region has a size, wherein the size of the first region is dependent upon a range between the first and second nodes, and wherein the second node is within a transmission range of the first node;

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

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

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

,

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

2. The non-transitory computer readable storage medium of claim 1 wherein the function of iteratively reducing the size of the minimum region of residence of the first node terminates when the minimum region of residence of the first node is not improved as a result of an iteration.

3. The non-transitory computer readable storage medium of claim 1 wherein the function of determining a minimum region of residence of the first node comprises determining a minimum region of residence of the first node based on a previously determined minimum region of residence of the first node.

4. The non-transitory computer readable storage medium of claim 3 wherein the function of iteratively reducing the size of the minimum region of residence of the first node terminates when the minimum region of residence of the node is not improved as a result of an iteration.

5. The non-transitory computer readable storage medium of claim 1 wherein the function of receiving a location of a first region from a second node comprises receiving a region of the second node that is extended in every direction by a first measured range value between the first and second nodes, wherein the function of receiving a location of a second region from a third node comprises receiving a region of the third node that is extended in every direction by a second measured range value between the first and third nodes, and wherein the function of receiving a location of a third region from a fourth node comprises receiving a region of the fourth node that is extended in every direction by a third measured range value between the first and fourth nodes.

6. The non-transitory computer readable storage medium of claim 1 wherein the function of iteratively reducing the size of the minimum region of residence of the first node comprises:

determining a region of residence of the second node in the view of the first node;

transmitting to the second node the region of residence of the second node in the view of the first node;

determining a region of residence of the third node in the view of the first node;

transmitting to the third node the region of residence of the third node in the view of the first node;

determining a region of residence of the fourth node in the view of the first node; and

,

transmitting to the fourth node the region of residence of the fourth node in the view of the first node.

7. The non-transitory computer readable storage medium of claim 6 wherein the function of iteratively reducing the size of the minimum region of residence of the first node terminates when the minimum region of residence of the first node is not improved as a result of an iteration.

8. The non-transitory computer readable storage medium of claim 6 wherein the function of determining a minimum region of residence of the first node comprises determining a minimum region of residence of the first node based on a previously determined minimum region of residence of the first node.

9. The non-transitory computer readable storage medium of claim 8 wherein the function of iteratively reducing the size of the minimum region of residence of the first node terminates when the minimum region of residence of the first node is not improved as a result of an iteration.

10. The non-transitory computer readable storage medium of claim 6 wherein the function of receiving a location of a first region from a second node comprises receiving a region of the second node that is extended in every direction by a first measured range value between the first and second nodes, wherein the function of receiving a location of a second region from a third node comprises receiving a region of the third node that is extended in every direction by a second measured range value between the first and third nodes, and wherein the function of receiving a location of a third region from a fourth node comprises receiving a region of the fourth node that is extended in every direction by a third measured range value between the first and fourth nodes.