Route updating in ad-hoc networks

• US 6,535,498 B1
• Filed: 12/06/1999
• Issued: 03/18/2003
• Est. Priority Date: 12/06/1999
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Larsson, Tony, Johansson, Per, Sörensen, Johan
• Primary Examiner(s): Maung, Nay
• Assistant Examiner(s): GELIN, JEAN ALLAND
• Application Number:
  US09/455,168
• Time in Patent Office: 1,198 Days
• Field of Search: 370/218, 370/229, 370/230, 370/231, 370/235, 370/237, 370/241.1, 370/242, 370/252, 370/254, 370/285, 370/338, 370/355, 370/356, 370/351
• US Class Current: 370/338
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

In conventional ad-hoc networks using reactive routing protocols the route between the source node and the destination node is not updated until the route is actually broken. In response to predetermined events a request for updated route message can be sent to the destination node to determine if another route exists between the source node and the destination node. A reply to the request for updated route can be provided by either the destination node or by a node which has a cached route between the source node and the destination node. This updated route request scheme can be implemented in networks which use source routing and networks which use distance vector routing.

Claims

1. In an ad-hoc network, a method for updating a route between a source node and a destination node, the method comprising the steps of:

exchanging information between the source node and the destination node over a first route;

determining, in the source node, whether a predetermined event has occurred;

broadcasting a request for updated route message if the predetermined event has occurred;

receiving the request for updated route message at a neighbor node;

determining whether the neighbor node is the destination node; and

generating and sending a reply message from the neighbor node if the neighbor node is the destination node,

wherein the network uses a reactive routing protocol and wherein the source node and destination node continue to use the first route to exchange information until another route is established.

2. The method of claim 1, wherein the network operates in accordance with source routing, and the step of generating and sending a reply message further comprises the step of:

inserting the entire route between the source node and the destination node in the reply message.

3. The method of claim 2, further comprising the steps of:

forwarding the reply message through intermediate nodes to the source node; and

inserting information about network condition into the reply message at the intermediate nodes.

4. The method of claim 3, wherein the source node determines whether to use the first route or the route in the reply message based on the network condition information.

5. The method of claim 1, wherein the network operates in accordance with distance vector routing, the method further comprising the step of:

storing temporary route information from the neighbor node to the source node.

6. The method of claim 5, further comprising the steps of:

receiving the reply message at a node;

determining whether the node is the source node;

replacing the first route between the source node and the destination node with the temporary route; and

sending messages over the temporary route if the node is the source node.

7. The method of claim 1, further comprising the step of:

determining whether the neighbor node has a cached route to the destination node; and

generating and sending a reply message from the neighbor node if the neighbor node has a cached route to the destination node which meets predetermined criteria.

8. The method of claim 7, further comprising the step of:

storing a time value when a route is created or updated, wherein the predetermined criteria is met if the cached route has been created or updated less than a predetermined time prior to reception of the request for updated route message.

9. The method of claim 7, further comprising the step of:

storing a time value when a route was last used to carry packets, wherein the predetermined criteria is met if the cached route was last used to carry packets less than a predetermined time prior to reception of the request for updated route message.

10. The method of claim 1, wherein the ad-hoc network is a Bluetooth scatternet.

11. The method of claim 1, wherein the predetermined event is the expiration of a predetermined time period.

12. The method of claim 11, wherein the predetermined time period is set to a time period longer than the sum of the time it takes for the request for updated route message to reach the destination node and the time it take the reply message to reach the source node.

13. The method of claim 11, wherein the predetermined time period is set to a first value which is incrementally shortened based on how often routes to the destination node are broken.

14. The method of claim 1, wherein the predetermined event is selected from the group of predetermined events consisting of:

traffic load along the first route between the source node and the destination node,

amount of delay along the first route between the source node and the destination node,

hop count along the first route between the source node and destination node, and

hot spots along the first route between the source node and destination node.

15. In an ad-hoc network, an arrangement for updating a route between a source node and a destination node, the arrangement comprising:

a source node comprising;

means for exchanging information between the source node and the destination node over a first route;

means for determining whether a predetermined event has occurred; and

means for broadcasting a request for updated route message if the predetermined event has occurred;

a neighbor node comprising;

means for receiving the request for updated route message;

means for determining whether the neighbor node is the destination node; and

means for generating and sending a reply message from the neighbor node if the neighbor node is the destination node,

wherein the network uses a reactive routing protocol and wherein the source node and destination node continue to use the first route to exchange information until another route is established.

16. The arrangement of claim 15, wherein the network operates in accordance with source routing, and the means for generating and sending a reply message further comprises:

means inserting the entire route between the source node and the destination node in the reply message.

17. The arrangement of claim 16, further comprising:

intermediate nodes comprising;

means for forwarding the reply message to the source node; and

means for inserting information about network condition into the reply message.

18. The arrangement of claim 17, wherein the source node further comprises:

means for determining whether to use the first route or the route in the reply message based on the network condition information.

19. The arrangement of claim 15, wherein the network operates in accordance with distance vector routing, wherein the neighbor node further comprises:

means for storing a temporary route from the neighbor node to the source node.

20. The arrangement of claim 19, further comprising:

means for receiving the reply message at a node;

means for determining whether the node is the source node;

means for replacing the first route between the source node and the destination node with the temporary route; and

means for sending messages over the temporary route if the node is the source node.

21. The arrangement of claim 15, wherein the neighbor node further comprises:

means for determining whether the neighbor node has a cached route to the destination node; and

means for generating and sending a reply message from the neighbor node if the neighbor node has a cached route to the destination node which meets predetermined criteria.

22. The arrangement of claim 21, wherein the neighbor node further comprises:

means for storing a time value when a route is created or updated, wherein the predetermined criteria is met if the cached route has been created or updated less than a predetermined time prior to reception of the request for updated route message.

23. The arrangement of claim 21, wherein the neighbor node further comprises:

means for storing a time value when a route was last used to carry packets, wherein the predetermined criteria is met if the cached route was last used to carry packets less than a predetermined time prior to reception of the request for updated route message.

24. The arrangement of claim 15, wherein the ad-hoc network is a Bluetooth scatternet.

25. The arrangement of claim 15, wherein the predetermined event is the expiration of a predetermined time period.

26. The arrangement of claim 25, wherein the predetermined time period is set to a time period longer than the sum of the time it takes for the request for updated route message to reach the destination node and the time it take the reply message to reach the source node.

27. The arrangement of claim 25, wherein the predetermined time period is set to a first value which is incrementally shortened based on how often routes to the destination node are broken.

28. The arrangement of claim 15, wherein the predetermined event is selected from the group of predetermined events consisting of:

traffic load along the first route between the source node and the destination node,

amount of delay along the first route between the source node and the destination node,

hop count along the first route between the source node and destination node, and

hot spots along the first route between the source node and destination node.