Unified routing scheme for ad-hoc Internetworking

• US 20020013856A1
• Filed: 09/21/2001
• Published: 01/31/2002
• Est. Priority Date: 12/23/1998
• Status: Abandoned Application

• Current Assignee: David A. Beyer, J. Joaquin Garcia-Luna-Aceves, Thane J. Frivold
• Original Assignee: David A. Beyer, J. Joaquin Garcia-Luna-Aceves, Thane J. Frivold
• Inventors: Beyer, David A., Frivold, Thane J., Garcia-Luna-Aceves, J. Joaquin
• Application Number:
  US09/957,756
• Publication Number:
  US 20020013856A1
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

The Invention provides methods and apparatus for determining various cost metrics for routing in a computer network. The cost metrics may include measures of interference over time to neighbor nodes of a first node of the computer network per data bit transmitted on a communication link used by the first node. Such a metric may be estimated using the RF transmit power used by the first node for the communication link, the link data rate and the RF-path loss on the communication link, which is determined by a neighbor node comparison of the RF transmit power to a received signal strength at the neighbor node. The cost metric may also include measure of node energy consumed per data bit for transmissions over a communication link within the computer network. Node energy may be computed so as to account for all power not used by a node in a non-transmitting state.

Claims

1. A method for determining a cost metric for routing between a plurality of nodes of a computer network, the method comprising:

determining a cost metric comprising interference over time per data bit to each of at least one neighbor node of a first node of the plurality of nodes, for a communication link used by the first node.

2. The method of claim 1, wherein the interference over time per data bit is determined as a normalized number of non-intended receiving nodes multiplied by seconds per bit.

3. The method of claim 2, wherein the normalized number of non-intended receiving nodes is determined by determining a number of nodes that would receive a transmission at an RF power greater than a threshold power level.

4. The method of claim 2, wherein the normalized number of non-intended receiving nodes is determined by summing the received RF power level of transmissions on the communications link at each of the at least one neighbor node.

5. The method of claim 1, wherein the step of determining a cost metric comprises:

transmitting at an RF transmit power level from said first node to each of the at least one neighbor node on the communication link;

determining the RF path loss by comparing the RF transmit power level to a received signal strength level at each of the at least one neighbor node; and

determining a cost metric for the communication link using the RF path loss at each of the at least one neighbor node and a data rate of the communication link.

6. A method for determining a cost metric for routing between a plurality of nodes of a computer network, the method comprising:

determining a cost metric comprising node energy consumed per data bit for transmissions over a communication link used by a first node of the plurality of nodes.

7. The method of claim 6, wherein the step of determining comprises determining a cost metric comprising a node energy including all additional power not consumed by the first node in its quiescent state.

8. The method of claim 6, wherein the step of determining comprises determining a cost metric comprising a node energy including power required to put the first node in an active state.

9. A method for determining a cost metric for routing between a plurality of nodes of a computer network, the method comprising:

determining a cost metric comprising a type of power consumed for transmission by a first node of the plurality of nodes over a communications link used by the first node.

10. The method of claim 9, wherein the type of power consumed includes battery power.

11. The method of claim 9, wherein the type of power consumed includes solar power.

12. A node capable of operation in a computer network comprising a plurality of other nodes, wherein the node determines a cost metric for routing, the cost metric comprising interference over time per data pit to at least one of the plurality of other nodes for a communications link used by the node.

13. The node of claim 12, wherein the interference over time per data bit is determined as a normalized number of non-9ntended receiving nodes of the plurality of other nodes multiplied by seconds per bit.

14. The node of claim 13, wherein the normalized number of non-intended receiving nodes is determined by determining a number of nodes that would receive a transmission at an RF power greater than a threshold power level.

15. The node of claim 13, wherein the normalized number of non-intended receiving nodes is determined by summing the received RF power level of transmissions on the communications link at each of the at least on of the plurality of other nodes.

16. The node of claim 12, wherein the node determines the cost metric by transmitting at an RF power level from the node to each of the plurality of other nodes on the communication link, determining the RF path loss by comparing the strength level at leach of the plurality of other nodes, and determining the cost metric for the communication link using the RF path loss at each of the plurality of other nodes and a data rate of the communication link.

17. 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 node energy consumed per data bit for transmissions over a communications link used by the node.

18. The node of claim 17, wherein the cost metric comprises a node energy including all additional power not consumed by the node in its quiescent state.

19. The node of claim 17, wherein the cost metric comprises a node energy including power required to put the node in an active state.

20. An apparatus for determining a cost metric for routing in a network comprising a plurality of nodes, wherein the cost metric comprises a type of power consumed for transmission by a selected node of the plurality of nodes.

21. The apparatus of claim 20, wherein the type of power consumed includes battery power.

22. The apparatus of claim 20, wherein the type of power consumed includes solar power.

23. The apparatus of claim 20, wherein the type of power consumed includes unrestricted power.