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

• US 20060098608A1
• Filed: 11/08/2004
• Published: 05/11/2006
• 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
• Granted Patent: US 7,408,911 B2
• Time in Patent Office: Days
• 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; 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.

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, further comprising:

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.

4. A method as claimed in claim 3, 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.

5. 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.

7. A method as claimed in claim 5, 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.

30. A method as claimed in claim 7, 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 the metrics in the route request packet are better than the current metrics is 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 the current route.

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

controlling a node that is sourcing data packets to a destination node to perform a route discovery process to discover another route to the destination node, and to repeat the route discovery process at periodic intervals, 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.

28. A method as claimed in claim 6, wherein:

the network is a wireless ad-hoc peer-to-peer network.

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

maintaining 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;

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 threshold value.

9. A method as claimed in claim 8, wherein:

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

the route is between the source and destination nodes in the wireless ad-hoc peer-to-peer network.

10. A method as claimed in claim 8, wherein:

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

11. A method as claimed in claim 8, wherein:

the controlling 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.

12. A method as claimed in claim 11, 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.

13. A method as claimed in claim 8, further comprising:

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

14. A method as claimed in claim 8, further comprising:

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

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

15. A node, adapted for use in a wireless communication network, the node comprising:

a controller, adapted 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.

16. A node as claimed in claim 15, 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.

17. A node as claimed in claim 15, wherein:

the controller is further adapted to control 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.

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

the controller is further adapted to update the respective link reliability values for each of the respective links based on conditions affecting the quality of the respective links.

19. A node, adapted for use in a wireless communication network, the node comprising:

a controller that controls the node that is sourcing data packets to a destination node to perform a route discovery process to discover another route to the destination node, and to repeat the route discovery process at periodic intervals, 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.

20. A node as claimed in claim 19, 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.

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

the network is a wireless ad-hoc peer-to-peer network.

31. A node as claimed in claim 20, 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 the metrics in the route request packet are better than the 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 the current route.

21. A node, adapted for use in a wireless communication network, the node comprising:

a controller, adapted to maintain 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, the controller being further adapted to compare the metric-per-hop value to at least one threshold value and to control 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 threshold value.

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

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

the route is between the node and the destination node in the wireless ad-hoc peer-to-peer network.

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

the controller is further adapted to update the metric-per-hop value based on conditions affecting the quality of the links in the route.

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

the controller is further adapted to control 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.

25. A node as claimed in claim 24, 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.

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

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

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

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