Topology controlled discovery for next hop determination
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.
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.