Adaptive Routing

• US 20080112325A1
• Filed: 06/02/2005
• Published: 05/15/2008
• Est. Priority Date: 06/04/2004
• Status: Active Grant

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Spyder Navigations LLC (Intellectual Ventures LLC)
• Inventors: Sivakumar, Tatikonda Venkata Lakshmi.Narasinha, Huang, Leping, Chen, Hongyuan
• Granted Patent: US 8,036,207 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/22 Alternate routing
• 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/16 based on interference
• 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
• CPC Class Codes: H04W 40/34 Modification of an existing route
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Methods and devices are shown for improving an existing route between a first node and a second node in a first ad-hoc network that includes a plurality of nodes, the method and devices selecting based on a predetermined performance criterion or criteria one of a plurality of candidate routes between the first node and the second node, wherein each candidate route includes at least one inter-node link that is not included within the first ad-hoc network and at least one candidate route including multiple inter-node links; initializing, via the existing route, the use of the inter-node links of the selected candidate route; and switching from using the existing route to using the candidate route.

Claims

1. A method of improving an existing route between a first node and a second node in a first ad-hoc network that comprises a plurality of nodes, the method comprising:

selecting based on a predetermined performance criterion or criteria one of a plurality of candidate routes between the first node and the second node, wherein each candidate route comprises at least one inter-node link that is not comprised within the first ad-hoc network and at least one candidate route comprises multiple inter-node links,

initializing, via the existing route, use of the inter-node links of the selected candidate route, and

switching from using the existing route to using the candidate route.

2. A method as claimed in claim 1, wherein the performance criterion or criteria relate to any one or more of:

the number of inter-node links within the candidate route;

the bit error rate for the candidate route;

the delay for the candidate route;

power consumption;

interference.

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

receiving a plurality of messages routed from the first node to the second node each of which comprises a distinct one of the plurality of candidate routes.

4. A method as claimed in claim 3, wherein the selecting, initializing, switching and receiving occur at the second node.

5. A method as claimed in claim 3, wherein each of the messages received is a BRREQ packet comprising a candidate route defined by a field PartialRouteMeasurement.

6. A method as claimed in claim 3, wherein the selecting uses timestamp information from each of the received messages.

7. A method as claimed in claim 1, wherein the step of selecting uses roles of nodes in the candidate route.

8. A method as claimed in claim 1, wherein the initializing comprises:

sending from the second node via the existing route to a neighboring node that neighbors the second node in the selected candidate route, an initialization message for establishing an inter-node link between the second node and the neighboring node.

9. A method as claimed in claim 8, wherein the initialization message comprises timing information for coordinating the neighboring node and second node in establishing an inter-node link.

10. A method as claimed in claim 9, wherein the timing information substantially synchronizes a page scan state and a page state in the second node and neighboring node.

11. A method as claimed in claim 8, wherein the initialization message is a BRREP packet.

12. A method as claimed in claim 1, wherein the step of initializing comprises:

sending from the second node an initialization message that is sent within the existing network from node to node of the selected candidate route in sequence and is updated at each node.

13. A method as claimed in claim 12, wherein the initialization message initializes establishment of inter-node links within the selected candidate route where necessary.

14. A method as claimed in claim 12, wherein when the initialization message is received at the first node in the selected candidate route that node switches from using the existing route to using the selected candidate route.

15. A method as claimed in claim 1, wherein the switching from using the existing route to using the selected candidate route, occurs at the second node, when it receives a switch message from the first node indicating that the first node has switched from using the existing route to using the selected candidate route.

16. A method as claimed in claim 15, wherein the switch message is a BRREF packet.

17. A method as claimed in claim 3, wherein the plurality of messages originate when the first node is unable to establish a link of sufficient quality to the second node to transfer data.

18. A device operable as a first node in a first ad-hoc network comprising a plurality of nodes, including the first node and a second node, and an existing route between the first node and the second node that comprises a plurality of inter-node links, the device comprising:

a selecting element for selecting based on a predetermined performance criterion or criteria one of a plurality of candidate routes between the first node and the second node, wherein each candidate route comprises at least one inter-node link that is not comprised within the first ad-hoc network and at least one candidate route comprises multiple inter-node links;

an initializing element for initializing, via the existing route, use of the inter-node links of the selected candidate route; and

a switching element for switching from using the existing route to using the candidate route.

19. A method of improving an existing route between a first node and a second node in a first ad-hoc network that comprises a plurality of nodes, the method comprising:

receiving a message at a device operable as a node of an ad-hoc network;

maintaining a cumulative history of a route the message has taken from the first node to the device;

maintaining a performance cost of the route the message has taken from the first node to the device;

then if a direct link from the device to the second node is available, establishing a candidate route for routing packets between the first and second nodes that comprises the route the message has taken from the first node to the device and the link between the device and the second node, else forwarding the message to at least another device.

20. A method as claimed in claim 19, comprising:

establishing a candidate route for routing packets between the first and second nodes only if the direct link is available and of sufficient quality.

21. A method as claimed in claim 19, further comprising adding a timestamp to the received message at the device.

22. A method as claimed in claim 19, wherein establishing a candidate route comprises communicating the candidate route to the second node.

23. A method as claimed in claim 22, wherein the candidate route is communicated by forwarding the message to the second node.

24. A method as claimed in claim 19, wherein the device is a node of the first ad-hoc network

25. A method as claimed in claim 19, wherein the at least another device comprises probable neighbors of the device operable as a node of an ad-hoc network.

26. A method as claimed in claim 19, wherein the at least another device comprises at least another device to which the device operable as a node of an ad-hoc network can establish a link of sufficient quality.

27. A method as claimed in claim 19, wherein the at least another device comprises a node adjacent the device operable as a node of an ad-hoc network in the existing route.

28. A device operable as a node in an ad-hoc network that comprises a plurality of nodes, the device comprising:

a receiver for receiving a message;

a route history maintenance element for maintaining a cumulative history of a route the message has taken to the device;

a performance cost maintenance element for maintaining a performance cost of the route the message has taken to the device;

a determining element for determining if a direct link from the device to the second node is available;

a candidate route establishing element for establishing a candidate route for routing packets between the first and second nodes that comprises the route the message has taken from the first node to the device and the direct link between the device and the second node if said direct link from the device to the second node is available; and

a forwarding element for forwarding the message to at least another device if said direct link from the device to the second node is not available.

29. A device operable as a node in a first ad-hoc network comprising a plurality of nodes that are interconnected by a plurality of inter-node links, comprising:

a neighbor list maintaining element for maintaining a list of neighboring devices, wherein each neighboring device is operable as a node in an ad-hoc network and operable to have a direct link to the device operable as a node in said first ad-hoc network and wherein the list comprises a plurality of entries each of which is associated with a neighboring device and each of which comprises an identifier of the associated neighboring device and a parameter indicating the quality of a direct link between the associated neighboring device and the device operable as a node in said first ad-hoc network.

30. A device, operable as a node in an ad-hoc network that comprises a first link between the device and a first node, comprising:

an identifying element for identifying when the first link is unused;

a determining element for determining whether there is a route via the ad-hoc network other than the first link between the device and the first node; and

a terminating element for terminating the first link if there is a route.

31. (canceled)

32. A device operable as a first node in a first ad-hoc network comprising a plurality of nodes, including the first node and a second node, and an existing route between the first node and the second node that comprises a plurality of inter-node links, the device comprising:

means for selecting based on a predetermined performance criterion or criteria one of a plurality of candidate routes between the first node and the second node, wherein each candidate route comprises at least one inter-node link that is not comprised within the first ad-hoc network and at least one candidate route comprises multiple inter-node links;

means for initializing, via the existing route, use of the inter-node links of the selected candidate route; and

means for switching from using the existing route to using the candidate route.