System and method to decrease the route convergence time and find optimal routes in a wireless communication network

• US 7,408,911 B2
• Filed: 11/08/2004
• Issued: 08/05/2008
• Est. Priority Date: 11/08/2004
• Status: Active Grant

• Current Assignee: Strong Force IoT Portfolio 2016, LLC (Strong Force Intellectual Capital, LLC)
• Original Assignee: MeshNetworks, Inc. (Motorola Solutions, Inc.)
• Inventors: Joshi, Avinash
• Primary Examiner(s): Nguyen, Brian D
• Application Number:
  US10/982,837
• Publication Number:
  US 20060098608A1
• Time in Patent Office: 1,366 Days
• Field of Search: 370/338, 370/252, 370/225
• US Class Current: 370/338
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

A system and method for decreasing the route convergence time in a wireless communication network, such as a wireless ad-hoc peer-to-peer network, by finding an alternate route if the nodes anticipate weakening or breakage of a route currently in use. The system and method which enables reactive routing protocols to find optimal routes between nodes in these types of networks when those routes cannot otherwise be found in certain conditions. The system and method thus decrease the route convergence time, provide an effective and efficient way to find optimal routes, and improve overall performance of the network with regard to throughput, delay, packet completion rate and other factors.

Claims

1. A method for determining a route between nodes in a wireless communication network, the method comprising:

maintaining a respective link reliability value for each of a plurality of respective links between one of the nodes in the network and other nodes in the network;

comparing the respective link reliability values to a threshold value;

controlling the node to issue a route warning message identifying any of the links whose respective link reliability value fails to meet the threshold value before the link has failed;

controlling a node that receives the route warning message and that is sourcing data packets to a destination node whose link is identified by the route warning message to perform a route discovery process to discover another route to the destination node;

repeating the route discovery process at periodic intervals, wherein when the node performs the route discovery process at each periodic interval, the node includes a periodic identifier in a route request packet that the node sends during the route discovery process to differentiate the route request packet being sent during a periodic performance of the route discovery process from a normal route request packet.

2. A method as claimed in claim 1, wherein:

the network is a wireless ad-hoc peer-to-peer network; and

each of the respective link reliability values represents a respective quality of a respective link between two of the nodes in the wireless ad-hoc peer-to-peer network.

3. A method as claimed in claim 1, wherein:

the route discovery process uses a time to live (TTL) value as a current hop count in a current route between the node performing the route discovery process to the destination plus a factor that is a function of at least one of the following;

a number of hops in the current route, routing metrics of the current route, number of neighbors and a constant value.

4. A method as claimed in claim 1, wherein:

the maintaining step comprises updating the respective link reliability values for each of the respective links based on conditions affecting the quality of the respective links.

5. A method as claimed in claim 1, wherein the periodic intervals are determined based on at least one of the following:

a number of nodes neighboring the node, mobility of the node and a metrics-per-hop value representing a ratio of cumulative route metrics for links in a route between the node and a destination node to which a packet that the node is attempting to send is addressed and a number of hops between the node and the destination node.

6. A method as claimed in claim 1, further comprising:

when a node receives the route request packet sent during a periodic performance of the route discovery process, the node accepts the route request packet if metrics in the route request packet are better than current metrics it has stored, and discards the route request packet if the metrics in the route request packet are worse than the current stored metrics even if the route request packet carries a higher sequence number than that of a current route.

7. A node operating within a wireless communication network, the node comprising:

a controller, operating to maintain a respective link reliability value for each of a plurality of respective links between the node and other nodes in the network, to compare the respective link reliability values to a threshold value, and to control the node to issue a route warning message identifying any of the links whose respective link reliability value fails to meet the threshold value before the link has failed;

wherein the controller controls the node to perform a route discovery process to discover another link to replace the link whose respective link reliability value fails to meet the threshold value,

wherein the controller repeats the route discovery process at periodic intervals,

wherein when the node performs the route discovery process at each periodic interval, the node includes a periodic identifier in a route request packet that the node sends during the route discovery process to differentiate the route request packet being sent during a periodic performance of the route discovery process from a normal route request packet.

8. A node as claimed in claim 7, wherein:

the network is a wireless ad-hoc peer-to-peer network; and

each of the respective link reliability values represents a respective quality of a respective link between the node and the other nodes in the wireless ad-hoc peer-to-peer network.

9. A node as claimed in claim 7, wherein:

the controller updates the respective link reliability values for each of the respective links based on conditions affecting the quality of the respective links.

10. A node, as claimed in claim 7 wherein the periodic intervals are determined based on at least one of the following:

a number of nodes neighboring the node, mobility of the node and a metrics-per-hop value representing a ratio of cumulative route metrics for links in a route between the node and a destination node to which a packet that the node is attempting to send is addressed and a number of hops between the node and the destination node.

11. A node as claimed in claim 7, wherein:

when a node receives the route request packet sent during a periodic performance of the route discovery process, the node accepts the route request packet if metrics in the route request packet are better than current metrics it has stored, and discards the route request packet if the metrics in the route request packet are worse than the current stored metrics even if the route request packet carries a higher sequence number than that of a current route.

12. A method for determining a route between nodes in a wireless communication network, the method comprising:

maintaining a respective link reliability value for each of a plurality of respective links between one of the nodes in the network and other nodes in the network;

comparing the respective link reliability values to a threshold value; and

controlling the node to issue a route warning message identifying any of the links whose respective link reliability value fails to meet the threshold value before the link has failed,

wherein the link reliability value comprises a metric-per-hop value representing a ratio of cumulative route metrics for a route between a source node attempting to send a packet and a destination node to which that packet is addressed and a number of hops between the source and destination nodes;

the method further comprising;

comparing the metric-per-hop value to at least one threshold value; and

controlling the source node to perform a route discovery process to discover another link to replace a link in the route whose metric-per-hop value fails to meet the at least one threshold value.

13. A method as claimed in claim 12, wherein:

the maintaining step comprises updating the metric-per-hop value based on conditions affecting the quality of the links in the route.

14. A method as claimed in claim 12, wherein:

the controlling the source node step controls the source node to perform the route discovery process using a time-to-live value equal to the number of hops in the route plus a factor.

15. A method as claimed in claim 14, wherein:

the factor is a function of at least one of a number of hops in the route, routing metrics of the route, and a constant.

16. A method as claimed in claim 12, further comprising:

controlling the source node to send the route metrics along with each data packet flowing between the source node and the destination node.

17. A method as claimed in claim 12, further comprising:

storing the route metrics in a header of a data packet being sent from the source node to the destination node; and

updating the route metrics as the data packet traverses through different nodes while traveling between the source node and the destination node.

18. A node operating within a wireless communication network, the node comprising:

a controller, operating to maintain a respective link reliability value for each of a plurality of respective links between the node and other nodes in the network, to compare the respective link reliability values to a threshold value, and to control the node to issue a route warning message identifying any of the links whose respective link reliability value fails to meet the threshold value before the link has failed,

wherein the link reliability value comprises a metric-per-hop value representing a ratio of cumulative route metrics for a route between the node and a destination node to which a packet being sent from the node is addressed and a number of hops between the node and the destination node,

wherein the controller compares the metric-per-hop value to at least one threshold value and controls the node to perform a route discovery process to discover another link to replace a link in the route whose metric-per-hop value fails to meet the at least one threshold value.

19. A node as claimed in claim 18, wherein:

the controller updates the metric-per-hop value based on conditions affecting the quality of the links in the route.

20. A node as claimed in claim 18, wherein:

the controller controls the node to perform the route discovery process using a time-to-live value equal to the number of hops in the route plus a factor.

21. A node as claimed in claim 20, wherein:

the factor is a function of at least one of a number of hops in the route, routing metrics of the route, and a constant.

22. A node as claimed in claim 18, wherein:

the controller controls the node to send the route metrics alone with each data packet flowing between the node and the destination node.

23. A node as claimed in claim 18, wherein:

the controller store the route metrics in a header of a data packet being sent from the node to the destination node, such that the route metrics can be updated as the data packet traverses through different nodes while traveling between the node and the destination node.