Multi-metric routing calculations

Abstract

In a Mobile Ad Hoc Network (MANET), multi-metric information is gathered and applied to a cost-based route calculation. In particular, each node gathers resource metrics from neighboring of nodes, along with data rate and reliability information for data links to and from the node. This information is applied to a costing algorithm such as Dykstra' Open Shortest Path First algorithm to obtain routes through the network. This approach may be adapted with suitable modifications to use with unicast traffic or with a multicast forwarding group.

What is claimed is: 
     
         1 . An ad hoc network node comprising:
 a radio that provide an air interface to an ad hoc network including a link to each one of a plurality of neighbors;   a first router within the ad hoc network node that routes data according to a Scoped Link State Routing (“SLSR”) protocol that employs multi-level scoping to reduce overhead;   a second router within the ad hoc network node that routes data according to a protocol selected from the group consisting of Open Shortest Path First, Border Gateway Protocol, and Routing Information Protocol; and   a signal processor configure to perform the steps of:
 receiving a resource metric from each one of the plurality of neighbors, the resource metric indicative of network resources needed by the corresponding one of the plurality of neighbors, wherein the resource metric includes a node weight representing a ratio of bandwidth required for data in to bandwidth required for data out for a corresponding one of the plurality of neighbors, thereby providing a data link layer resource metric for a route calculation; 
 determining a data rate for the link to each one of the plurality of neighbors using physical layer data that characterizes a rate of data selected according to the physical performance of a wireless communication channel of the radio, thereby providing a data rate metric for the route calculation; 
 determining a reliability for the link to each one of the plurality of neighbors using physical layer data that characterizes a physical reliability of the wireless communication channel, thereby providing a reliability metric for the route calculation; 
 applying the reliability metric, the data rate metric, and the data link layer bandwidth metric to the route calculation to calculate a plurality of routes within the SLSR protocol, the plurality of routes including a route for each one of a plurality of service levels; and 
 sharing network reachability information between the first router and the second router. 
   
     
     
         2 . The device of  claim 1  wherein the signal processor is further configured to perform the steps of:
 receiving a data packet at the node, the data packet having a service level indicator; and 
 routing the data packet according to the route for the service level. 
 
     
     
         3 . The device of  claim 1  wherein each one of the plurality of service levels imposes different requirements on the route calculation, whereby two or more of the service levels achieve different routing trees through the ad hoc network. 
     
     
         4 . The device of  claim 1  wherein the route calculation includes a Dykstra Shortest Path First algorithm. 
     
     
         5 . The device of  claim 1  wherein the signal processor is further configured to perform the step of load balancing network traffic by providing a tie breaking mechanism to distribute traffic among a number of substantially equal cost ones of the routes. 
     
     
         6 . The device of  claim 5  wherein the tie breaking mechanism is based upon destination Internet Protocol addresses. 
     
     
         7 . The device of  claim 1  wherein the route calculation is a unicast route calculation. 
     
     
         8 . The device of  claim 1  wherein the route calculation is a multicast route calculation. 
     
     
         9 . The device of  claim 8  wherein the multicast route calculation employs a forwarding group of nodes responsible for forwarding multicast traffic. 
     
     
         10 . The device of  claim 8  wherein the signal processor is further configured to perform the step of periodically flooding a member advertisement packet from the node to request membership in a multicast forwarding group. 
     
     
         11 . The device of  claim 8  wherein the signal processor is further configured to perform the step of receiving a join request from one of the plurality of neighbors and conditionally relaying the join request when a hop count for the join request does not exceed a predetermined threshold.