Method and apparatus for mesh routing

• US 7,881,206 B2
• Filed: 12/31/2007
• Issued: 02/01/2011
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: St. Pierre, Robert P., De, Pradip S., Gupta, Vipul
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): LOPATA, ROBERT J
• Application Number:
  US11/967,416
• Publication Number:
  US 20090168653A1
• Time in Patent Office: 1,128 Days
• Field of Search: 370/238, 370/392, 370/229, 370/235, 709/238, 709/239, 709/240, 709/241
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04W 24/10 Scheduling measurement reports ; Arrangements for measurement reports
• CPC Class Codes: H04W 28/088 among core entities
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00

Abstract

Method and apparatus for optimizing mesh routing for stability and system lifetime maximization in networks, for example in wireless networks. A routing module may be instantiated in nodes on the network. The routing module may implement a link quality and node health aware routing protocol on the network that considers a combination of link quality and node health/residual lifetime metrics in the calculation of the desirability of nodes and links between nodes as parts of an overall route. A route selection metric for each route may be determined from routing cost metrics for the nodes on the route and the number of hops on the route. A node may then select a best route according to the determined route selection metrics for the routes.

Claims

1. A device, comprising:

a processor; and

a memory comprising program instructions executable by the processor to implement a routing module configured to;

determine one or more link quality metrics and one or more health metrics at the device, wherein the one or more link quality metrics indicate communications link quality to one or more other devices that are neighbor nodes to the device on a network, and wherein the one or more health metrics indicate current health status of the device;

determine a routing cost metric for the device from the one or more link quality metrics and the one or more health metrics;

receive a routing message corresponding to a particular route on the network that includes the device from a previous node on the particular route;

in response to receiving the routing message, include the routing cost metric for the device in the routing message; and

send the routing message to a next node on the particular route.

2. The device as recited in claim 1, wherein the routing cost metric included in the outgoing routing message is used in calculating a routing selection metric for the particular route on the network, wherein the routing selection metric for the particular route is compared to the routing selection metric for other routes on the network at a source node of the routing message to select a best route on the network from the source node to a destination node on the network.

3. The device as recited in claim 1, wherein the network is a wireless network, wherein the device further comprises a wireless communications module, and wherein the device configured to communicate with other devices on the wireless network via the wireless communications module.

4. The device as recited in claim 1, wherein the device further comprises a limited power source, and wherein the one or more health metrics include current status of the limited power source.

5. The device as recited in claim 1, wherein the device further comprises a battery as a power source, and wherein the one or more health metrics include a health metric determined by the routing module according to a normalized function of power remaining in the battery.

6. The device as recited in claim 1, wherein the one or more link quality metrics include a link quality metric determined by the routing module as a history depreciated normalized sum of link quality at the device over a time window.

7. A system, comprising:

a plurality of nodes configured to implement a network among the nodes, wherein each node is a computing device that implements a routing module configured to;

determine one or more link quality metrics and one or more health metrics at the node, wherein the one or more link quality metrics indicate communications link quality to one or more other nodes that are neighbor nodes to the node on the network, and wherein the one or more health metrics indicate current health status of the device;

determine a routing cost metric for the node from the one or more link quality metrics and the one or more health metrics;

receive one or more routing messages each corresponding to a particular route on the network that includes the node from a previous node on the particular route;

in response to receiving the one or more routing messages, include the routing cost metric for the node into each of the one or more routing messages; and

send each of the one or more routing message to a next node on the corresponding particular route.

8. The system as recited in claim 7, wherein one of the plurality of nodes is a source node configured to:

initiate a route request message on the network, wherein the route request message requests route information to one of the plurality of nodes as a destination node;

calculate a routing selection metric for each particular route on the network to the destination node according to the routing cost metrics included in route reply messages received at the source node; and

compare the calculated routing selection metrics for the routes on the network to the destination node to select a best route to the destination node.

9. The system as recited in claim 8, wherein, to calculate a routing selection metric for each particular route on the network to the destination node according to the routing cost metrics included in route reply messages received at the source node, the source node is further configured to, for each route reply message, adjust a count of the number of hops on a route indicated in the route reply message according to routing cost metrics for nodes on the route indicated by the route reply message.

10. The system as recited in claim 7, wherein the nodes are wireless devices, wherein the network is a wireless network, and wherein each node is configured to communicate with other nodes on the wireless network via a wireless communications protocol.

11. The system as recited in claim 7, wherein one or more of the devices comprises a limited power source, and wherein the one or more health metrics include current status of the limited power source.

12. A method, comprising:

initiating, at a source node on a network implemented among a plurality of nodes, a route request message that requests route information to a destination node on the network;

propagating the route request message across a plurality of routes through the nodes on the network to the destination node;

initiating, at the destination node, a route reply message for each route request message received at the destination node;

calculating a routing cost metric from one or more link quality metrics and one or more health metrics at each node on each route; and

including, at the each node on each route, the routing cost metric for the node on a particular route in a route reply message corresponding to the particular route on the network that includes the node.

13. The method as recited in claim 12, wherein the one or more link quality metrics indicate communications link quality to one or more other nodes that are neighbor nodes to the node on the network, and wherein the one or more health metrics indicate current health status of the node.

14. The method as recited in claim 13, wherein one or more of the nodes comprises a limited power source, and wherein the one or more health metrics include current status of the limited power source.

15. The method as recited in claim 12, further comprising:

calculating a routing selection metric for each particular route on the network to the destination node according to the routing cost metrics included in the route reply messages; and

comparing, at the source node, the calculated routing selection metrics for the routes on the network to the destination node to select a best route to the destination node.

16. The method as recited in claim 14, wherein said calculating a routing selection metric for each particular route on the network to the destination node according to the routing cost metrics included in the route reply messages comprises, for each route reply message, adjusting a count of the number of hops on a route indicated in the route reply message according to routing cost metrics for nodes on the route indicated by the route reply message.

17. The method as recited in claim 12, wherein the nodes are wireless devices, wherein the network is a wireless network, and wherein each node is configured to communicate with other nodes on the wireless network via a wireless communications protocol.