TOPOLOGY CONTROLLED DISCOVERY FOR NEXT HOP DETERMINATION

• US 20090046601A1
• Filed: 03/12/2008
• Published: 02/19/2009
• Est. Priority Date: 08/15/2007
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Nordmark, Erik, Chakrabarti, Samita
• Granted Patent: US 8,180,352 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In a particular embodiment of the present invention, a particular node in an ad hoc network is configured with a desirable number of neighbor nodes and equipped with a transmission power level hierarchy. The particular node may adjust a transmission power level to a different level in the transmission power level hierarchy, based on a number of responses received from neighbor nodes after the particular node broadcasts a request at current transmission power level. This adjustment process is repeated until the particular node acquires a desirable number of neighbor nodes.

Claims

1. A method implemented by a particular node in an ad hoc network, comprising:

(a) broadcasting a request for response at a particular transmission power level;

(b) receiving an N number of responses, thereby indicating that an N number of neighbor nodes received and responded to the request;

(c) determining whether N is within a desired range;

(d) in response to a determination that N is within the desired range, concluding that the particular transmission power level is an appropriate power level to use for future transmissions;

(e) in response to a determination that N is not within the desired range, determining whether to adjust the particular transmission power level; and

(f) repeating (a) through (e) until N is within the desired range.

2. The method of claim 1, wherein determining whether to adjust the particular transmission power level comprises:

determining whether N is below the desired range; and

in response to a determination that N is below the desired range, increasing the particular transmission power level.

3. The method of claim 2, wherein determining whether to adjust the particular transmission power level further comprises:

in response to a determination that N is above the desired range, decreasing the particular transmission power level.

4. The method of claim 1, wherein the N number of neighbor nodes represents a set of potential next-hop nodes to which the particular node may forward packets, and wherein the method further comprises:

receiving a packet that is to be forwarded to a destination node;

determining one or more possible paths to the destination node; and

selecting, from the one or more possible paths, a desired path which has one of the N neighbor nodes as a next hop.

5. The method of claim 1, wherein the N number of neighbor nodes represents a set of potential next-hop nodes to which the particular node may forward packets, and wherein the method further comprises:

identifying, based on the N number of responses received, an M number of nodes reachable from the particular node;

determining whether the M number of nodes includes a destination node;

in response to a determination that the M number of nodes does not include the destination node, determining new values for the desired range; and

repeating (a) through (e) until N is within the desired range with the new values determined.

6. The method of claim 1, wherein determining whether to adjust the particular transmission power level comprises:

determining whether N is below the desired range;

determining whether the particular transmission power level is the highest of available transmission power levels; and

in response to a determination that N is below the desired range and that the particular transmission power level is the highest of available transmission level, leaving the particular transmission power level unchanged.

7. The method of claim 1, wherein determining whether to adjust the particular transmission power level comprises:

determining whether N is above the desired range;

determining whether the particular transmission power level is the lowest of available transmission power levels; and

in response to a determination that N is above the desired range and that the particular transmission power level is the lowest of available transmission level, leaving the particular transmission power level unchanged.

8. The method of claim 1, wherein determining whether N is within a desired range comprises:

receiving user input indicating a range of neighbor nodes; and

setting the desired range to the range of neighbor nodes indicated by the user input.

9. The method of claim 1, wherein determining whether N is within a desired range comprises programmatically setting the desired range.

10. A machine readable medium, comprising instructions for:

(a) broadcasting a request for response at a particular transmission power level;

(b) receiving an N number of responses, thereby indicating that an N number of neighbor nodes received and responded to the request;

(c) determining whether N is within a desired range;

(d) in response to a determination that N is within the desired range, concluding that the particular transmission power level is an appropriate power level to use for future transmissions;

(e) in response to a determination that N is not within the desired range, determining whether to adjust the particular transmission power level; and

(f) repeating (a) through (e) until N is within the desired range.

11. The machine readable medium of claim 10, wherein the instructions for determining whether to adjust the particular transmission power level comprise:

instructions for determining whether N is below the desired range; and

instructions for increasing the particular transmission power level in response to a determination that N is below the desired range.

12. The machine readable medium of claim 10, wherein the instructions for determining whether to adjust the particular transmission power level further comprise:

instructions for decreasing the particular transmission power level in response to a determination that N is above the desired range.

13. The machine readable medium of claim 10, wherein the N number of neighbor nodes represents a set of potential next-hop nodes to which the particular node may forward packets, and wherein the instructions further comprise:

instructions for receiving a packet that is to be forwarded to a destination node;

instructions for determining one or more possible paths to the destination node; and

instructions for selecting, from the one or more possible paths, a desired path which has one of the N neighbor nodes as a next hop.

14. The machine readable medium of claim 10, wherein the N number of neighbor nodes represents a set of potential next-hop nodes to which the particular node may forward packets, and wherein the instructions further comprise instructions for:

identifying, based on the N number of responses received, an M number of nodes reachable from the particular node;

determining whether the M number of nodes includes a destination node;

determining new values for the desired range in response to a determination that the M number of nodes does not include the destination node; and

repeating (a) through (e) until N is within the desired range with the new values determined.

15. The machine readable medium of claim 10, wherein the instructions for determining whether to adjust the particular transmission power level comprise:

instructions for determining whether N is below the desired range;

instructions for determining whether the particular transmission power level is the highest of available transmission power levels; and

instructions for leaving the particular transmission power level unchanged in response to a determination that N is below the desired range and that the particular transmission power level is the highest of available transmission level.

16. The machine readable medium of claim 10, wherein the instructions for determining whether to adjust the particular transmission power level comprise:

instructions for determining whether N is above the desired range;

instructions for determining whether the particular transmission power level is the lowest of available transmission power levels; and

instructions for leaving the particular transmission power level unchanged in response to a determination that N is above the desired range and that the particular transmission power level is the lowest of available transmission level.

17. The machine readable medium of claim 10, wherein the instructions for determining whether N is within a desired range comprise:

instructions for receiving user input indicating a range of neighbor nodes; and

instructions for setting the desired range to the range of neighbor nodes indicated by the user input.

18. The machine readable medium of claim 10, wherein the instructions for determining whether N is within a desired range comprises instructions for programmatically setting the desired range.