Topology controlled discovery for next hop determination

• US 8,180,352 B2
• Filed: 03/12/2008
• Issued: 05/15/2012
• 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
• Primary Examiner(s): Nguyen, Duc
• Assistant Examiner(s): CHOW, CHARLES CHIANG
• Application Number:
  US12/047,097
• Publication Number:
  US 20090046601A1
• Time in Patent Office: 1,525 Days
• Field of Search: 455/424, 455/425, 455/456.5, 455/456.6, 455/561, 455/550.1, 455/575.1, 455/522, 455/455, 455/69, 455/70, 455/63.1, 455/127.1, 455/513, 455/456.1, 370/318, 370/312, 370/313, 370/315, 370/310, 370/503, 370/338, 370/349, 370/400, 370/401, 370/390, 370/432
• US Class Current: 455/445
• 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, wherein N represents a set of potential next-hop nodes to which the particular node may forward packets;

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

(d) in response to a determination that N is not within the desired range, adjusting the particular transmission power level and repeating (a) through (c);

(e) 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;

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

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

(h) in response to a determination that the M number of nodes does not include a destination node, generating new values for the desired range and repeating (a) through (c); and

(i) in response to a determination that the M number of nodes includes the destination node, transmitting a packet addressed to the destination node to a next-hop node using the particular power transmission level.

2. The method of claim 1, wherein adjusting 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 adjusting 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 transmitting the packet addressed to the destination node to the next-hop node further comprises:

receiving the packet addressed to the 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 uses the next-hop node.

5. The method of claim 1, wherein adjusting the particular transmission power level comprises:

determining whether N is below the desired range;

determining whether the particular transmission power level is 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.

6. The method of claim 1, wherein adjusting the particular transmission power level comprises:

determining whether N is above the desired range;

determining whether the particular transmission power level is 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.

7. The method claim 1, wherein determining whether N is within the desired range comprises:

receiving user input indicating a range of neighbor nodes; and

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

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

9. A non-transitory machine readable medium, comprising instructions for:

(a) broadcasting, by a node comprising a computer system, 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, wherein N represents a set of potential next-hop nodes to which the particular node may forward packets;

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

(d) in response to a determination that N is not within the desired range, adjusting the particular transmission power level and repeating (a) through (c);

(e) 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;

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

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

(h) in response to determination that the M number of nodes does not include a destination node, generating new values for the desired range and repeating (a) through (c); and

(i) in response to a determination that the M number of nodes includes the destination node, transmitting a packet addressed to the destination node to a next-hop node using the particular power transmission level.

10. The non-transitory machine readable medium of claim 9, wherein adjusting the particular transmission power level comprises:

determining whether N is below the desired range; and

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

11. The non-transitory machine readable medium of claim 9, wherein adjusting the particular transmission power level further comprises:

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

12. The non-transitory machine readable medium of claim 9, wherein transmitting the packet addressed to the destination node to the next-hop node further comprises:

receiving the packet addressed to the 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 uses the next-hop node.

13. The non-transitory machine readable medium of claim 9, wherein adjusting the particular transmission power level comprises:

determining whether N is below the desired range;

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

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.

14. The non-transitory machine readable medium of claim 9, wherein adjusting the particular transmission power level comprises:

determining whether N is above the desired range;

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

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 highest of available transmission level.

15. The non-transitory machine readable medium of claim 9, wherein determining whether N is within the 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.

16. The non-transitory machine readable medium of claim 9, wherein determining whether N is within the desired range comprises programmatically setting the desired range.