Granted Patent B2

US 8,165,143 · App. 12/724,635 · Granted Apr 24, 2012

Abstract

Claims (47)

1. An apparatus, comprising:

a reception module in an intermediate node to receive, from a source node, a route request message associated with a destination node; and

a processing module in the intermediate node to determine that when the intermediate node has a route to the destination node in its route cache and energy associated with the intermediate node is above a threshold, a counter associated with the intermediate node is to be adjusted and a message is to be sent to additional nodes along the route to cache the route, to adjust corresponding node counters, and to ignore later route requests; and to determine that when the intermediate node does not have the route in the route cache and the energy associated with the intermediate node is above the threshold, the counter associated with the intermediate node is to be adjusted, a counter check message is to be broadcast to neighboring nodes, and entries in route caches associated with the neighboring nodes that reveal themselves to be selfish nodes in response to the counter check message are to be invalidated; and to determine that when none of the neighboring nodes reveal themselves to be selfish nodes in response to the counter check message, the route request message comprising indications of values of the counter and the energy associated with the intermediate node is to be broadcast, and the later route requests are to be ignored.

2. The apparatus of claim 1 , further comprising:

an energy monitor to determine an amount of the energy associated with the intermediate node.

3. The apparatus of claim 1 , further comprising:

a battery, wherein the energy associated with the intermediate node substantially corresponds to a level of remaining power of the battery.

4. A system, comprising:

a source node to transmit a route request message associated with a destination node; and

an intermediate node coupled to the source node via a mobile ad-hoc network, the intermediate node comprising a reception module to receive the route request message from the source node, and a processing module to determine that when the intermediate node has a route to the destination node in its route cache and energy associated with the intermediate node is above a threshold, a counter associated with the intermediate node is to be adjusted and a message is to be sent to additional nodes along the route to cache the route, to adjust corresponding node counters, and to ignore later route requests; and to determine that when the intermediate node does not have the route in the route cache and the energy associated with the intermediate node is above the threshold, the counter associated with the intermediate node is to be adjusted, a counter check message is to be broadcast to neighboring nodes, and entries in route caches associated with the neighboring nodes that reveal themselves to be selfish nodes in response to the counter check message are to be invalidated; and to determine that when none of the neighboring nodes reveal themselves to be selfish nodes in response to the counter check message, the route request message comprising indications of values of the counter and the energy associated with the intermediate node is to be broadcast, and the later route requests are to be ignored.

5. The system of claim 4 , wherein the counter associated with the intermediate node is to be stored in the route cache associated with the intermediate node.

6. A processor-implemented method to execute on one or more processors that perform the method, comprising:

receiving, from a source node, a route request message associated with a destination node at an intermediate node;

when the intermediate node has a route to the destination node in its route cache and energy associated with the intermediate node is above a threshold, adjusting a counter associated with the intermediate node and sending a message to additional nodes along the route to cache the route, to adjust corresponding node counters, and to ignore later route requests;

when the intermediate node does not have the route in the route cache and the energy associated with the intermediate node is above the threshold, adjusting the counter associated with the intermediate node, broadcasting a counter check message to neighboring nodes, and invalidating entries in route caches associated with the neighboring nodes that reveal themselves to be selfish nodes in response to the counter check message; and

when none of the neighboring nodes reveal themselves to be selfish nodes in response to the counter check message, broadcasting the route request message comprising traversed node identifications, indications of values of the counter and the energy associated with the intermediate node, and ignoring the later route requests.

7. The method of claim 6 , wherein the selfish nodes are revealed when the node counters corresponding to the selfish nodes have a value that is below or above the designated value associated with selfish behavior, depending on the direction of the adjusting.

8. The method of claim 6 , further comprising:

decrementing the threshold associated with the intermediate node by a predetermined amount to provide a revised threshold when the energy associated with the intermediate node is not above the threshold so that future comparisons of the energy associated with the threshold and the route request message will make use of the revised threshold.

9. The method of claim 6 , further comprising:

sending a drop node message to a source node associated with the route request when at least one of the neighboring nodes reveals itself to be one of the selfish nodes.

10. The method of claim 6 , further comprising:

refraining from sending a drop node message to a source node associated with the route request when an alternative path is found in the route cache of the intermediate node.

11. The method of claim 6 , further comprising:

receiving identification of at least one of the neighboring nodes revealing itself to be one of the selfish nodes by way of a selfish message broadcast from the one of the selfish nodes to neighbors of the one of the selfish nodes, the neighbors comprising all nodes within a designated network distance.

12. The method of claim 11 , wherein the designated distance is defined in terms of a number of network hops.

13. The method of claim 6 , wherein the energy associated with the intermediate node substantially corresponds to a level of remaining battery power available to the intermediate node.

14. The method of claim 6 , further comprising:

receiving a drop node message at a node along the route that is not the intermediate node; and

searching the route cache associated with the node along the route to find an alternate route to the destination node.

15. The method of claim 14 , further comprising:

updating entries in the route cache associated with each node along the route to the source node that is not the intermediate node to incorporate the alternate route.

16. The method of claim 6 , further comprising:

receiving a first arriving route reply message in response to the route request message at the source node; and

selecting the route included in the route reply message to route the message from the source node to the destination node; and

ignoring subsequent route reply messages.

17. A processor-implemented method to execute on one or more processors that perform the method, comprising:

traversing intermediate nodes as traversed nodes in a network during network routing operations to determine an original routing path for a source message from a source node in the network to a destination node in the network by using proactive routing between clusters of nodes in the network, and both proactive and reactive routing within the clusters;

selecting the original routing path according to a greedy energy strategy that operates to define the original routing path as a path having a greater energy value associated with the intermediate nodes than other paths;

upon discovery of selfish nodes by one of the intermediate nodes, the selfish nodes being neighbors to at least one of the intermediate nodes, directing removal of the selfish nodes from route caches associated with the traversed nodes; and

determining an alternate routing path for the source message in the network, the alternate routing path different from the original routing path, by sequentially searching upstream route caches in the traversed nodes in the network to discover the alternate path.

18. The method of claim 17 , wherein the discovery of the selfish nodes further comprises:

adjusting counters in the traversed nodes in a first direction when the traversed nodes forward the source message;

adjusting counters in nodes neighboring the intermediate nodes in a second direction different from the first direction when another message to be routed in the network is originated by the nodes neighboring the intermediate nodes; and

discovering the selfish nodes by checking values of the counters in nodes neighboring the intermediate nodes.

19. The method of claim 17 , wherein the determining the alternate routing path further comprises:

searching route caches in the traversed nodes to locate divergent routes to the destination.

Assignments (16)