Unified routing scheme for ad-hoc internetworking

Abstract

The invention provides a method and apparatus for determining cost metrics for routing in a computer network. The cost metrics may include a measure of the quality of a wireless communication link within the computer network. Such a metric may be used in determining which links of the network to utilize. For example, one may examine local routing information maintained by a first node of a computer network to determine whether alternate paths exist to a neighbor node of the first node, using a sequence of one or more links other than a candidate link through the computer network and compute a link quality of the candidate link. Then, if no alternate path exists to the neighbor node, or the link quality of the candidate link exceeds a defined threshold value, the candidate link may be accepted. If one or more alternate paths do exist to the neighbor node, then by comparing link qualities of the links along each of the alternate paths with the link quality of the candidate link one may decide to accept the candidate link if the link quality of the candidate link compares favorably with the link qualities of the links on the alternate paths. The metrics may also include an indication of the type of power available to the node, the power state of the node, or an indication of whether the node is an anchor for the computer network.

What is claimed is:  
     
         1 . A method for determining a cost metric for routing in a computer network comprising a plurality of nodes, the method comprising: 
 determining a cost metric comprising a measure of quality for transmissions over a communication link used by a first node of the plurality of nodes.    
     
     
         2 . The method of  claim 1 , wherein the step of determining comprising determining a cost metric comprising a packet success rate determined over a plurality of packet transmissions on the communications link.  
     
     
         3 . The method of  claim 1 , wherein the step of determining comprises determining a cost metric comprising a combination of a measure of the reliability of the communication link and a measure of interference over time on the communication link per data bit as caused by transmission from a second node of the plurality of nodes.  
     
     
         4 . The method of  claim 1 , wherein the step of determining comprises determining a cost metric comprising a combination of a measure of the reliability of the communications link and a measure of power consumed per data bit by the first node for transmissions on the communications link.  
     
     
         5 . The method of  claim 1 , further comprising the step of determining whether to include a second node of the plurality of nodes in a routing table for said first node, according to a cost metric for transmission from the first node to the second node on the communication link.  
     
     
         6 . The method of  claim 1 , further comprising transmitting the cost metric from said first node to at least a second node of the plurality of nodes in a routing table update message.  
     
     
         7 . The method of  claim 1 , wherein the step of determining comprises determining a cost metric comprising a measure of node energy consumed per data bit on the communications link and a measure of interference experienced over time on the communications link per data bit as caused by transmissions from a second node of the plurality of nodes.  
     
     
         8 . A node capable of operation in a network comprising a plurality of other nodes, wherein the node determines a cost metric for routing, the cost metric comprising a measure of quality for transmissions over a communication link used by the node.  
     
     
         9 . The node of  claim 8 , wherein the cost metric comprises a packet success rate determined over a plurality of packet transmissions on the communications link.  
     
     
         10 . The node of  claim 8 , wherein the cost metric comprises a combination of a measure of the reliability of the communication link and a measure of the interference over time on the communication link per data bit as caused by transmissions from a selected other node of the plurality of other nodes.  
     
     
         11 . The node of  claim 8 , wherein the cost metric comprises a measure of the reliability of the communications link and a measure of power consumed per data bit by the first node for transmissions on the communications link.  
     
     
         12 . The node of  claim 8 , wherein the node further determines whether to include a selected other node of the plurality of other nodes in a routing table for the node, according to a cost metric for transmission from the node to the selected other node on the communications link.  
     
     
         13 . The node of  claim 8 , wherein the node further transmits the cost metric to at least a selected other node of the plurality of other nodes in a routing table update message.  
     
     
         14 . The node of  claim 8 , wherein the cost metric comprise a measure of node energy consumed per data bit on the communication kink and a measure of interference experienced over time on the communications link per data bit as caused by transmissions from a selected other node of the plurality of other nodes.