Adaptive routing

• US 8,036,207 B2
• Filed: 06/02/2005
• Issued: 10/11/2011
• Est. Priority Date: 06/04/2004
• Status: Active Grant

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Inventors: Sivakumar, Tatikonda Venkata Lakshmi Narasinha, Huang, Leping, Chen, Hongyuan
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US11/628,596
• Publication Number:
  US 20080112325A1
• Time in Patent Office: 2,322 Days
• Field of Search: 370/238, 370/327, 370/338, 370/352, 370/400, 370/401, 455/406, 455/411, 455/426.1, 455/426.2
• US Class Current: 370/351
• 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 communicating in an ad-hoc network, the method comprising:

broadcasting a DUPROUTE packet to one or more neighbor nodes to determine an existence of one or more alternate routes between a first node and a destination node, wherein the DUPROUTE packet comprises a TimeToLive field, and wherein the one or more neighbor nodes are configured to decrement the TimeToLive field and forward the DUPROUTE packet to additional neighbor nodes if the destination node is not an immediate neighbor of the one or more neighbor nodes;

selecting, solely at a first node, a first candidate route between the first node and a second node based on at least one performance criterion, wherein the first candidate route includes a plurality of links corresponding to at least one intermediate node located between the first node and the second node on the first candidate route, and wherein at least one link of the plurality of links is not included in an existing route between the first node and the second node;

discontinuing use of the existing route at the first node; and

commencing use of the selected first candidate route at the first node in place of the existing route, wherein use of the plurality of links of the selected first candidate route is initialized via nodes of the existing route; and

maintaining use of the selected first candidate route until a second candidate route is selected such that data may be transmitted over the maintained first candidate route until the selected second candidate route is commenced.

2. The method as claimed in claim 1, wherein the at least one performance criterion relates to any one or more of:

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

a bit error rate for the first candidate route;

a delay for the first candidate route;

power consumption;

interference.

3. The 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 a plurality of candidate routes.

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

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

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

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

8. The method as claimed in claim 1, wherein selecting the first candidate route between the first node and the second node uses roles of nodes in the candidate route.

9. The 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 first candidate route an initialization message for establishing an inter-node link between the second node and the neighboring node.

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

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

12. The method as claimed in claim 9, wherein the initialization message is a BRREP packet.

13. The method as claimed in claim 1, wherein initializing comprises sending from the second node an initialization message that is sent within the existing network from node to node of the selected first candidate route in sequence and is updated at each node.

14. The method as claimed in claim 13, wherein the initialization message initializes establishment of inter-node links within the selected first candidate route.

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

16. The method as claimed in claim 1, wherein the switching from using the existing route to using the selected first 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 first candidate route.

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

18. The method of claim 1, wherein the one or more neighbor nodes are configured to discontinue processing of the DUPROUTE packet if the DUPROUTE packet is a duplicate of a packet the one or more neighbor nodes have previously received.

19. The method of claim 1, further comprising checking for unused active links, wherein an active link is unused if it is not used for data traffic for a pre-determined time period.

20. The method of claim 1, further comprising receiving a DUPROUTEREPLY message from the one or more neighbor nodes in response to the destination node being the immediate neighbor of the one or more neighbor nodes.

21. The method of claim 20, further comprising, in response to receiving the DUPROUTEREPLY message, terminating the link to the destination node and placing the destination node in a probable neighbor list.

22. A node of an ad-hoc network comprising:

a selection element configured to broadcast a DUPROUTE packet to one or more neighbor nodes to determine an existence of one or more alternate routes between a first node and a destination node, wherein the DUPROUTE packet comprises a TimeToLive field, and wherein the one or more neighbor nodes are configured to decrement the TimeToLive field and forward the DUPROUTE packet to additional neighbor nodes if the destination node is not an immediate neighbor of the one or more neighbor nodes;

a selection element configured to select a first, candidate route between a first node and a second node based on at least one performance criterion, wherein the first candidate route includes a plurality of links corresponding to at least one intermediate node located between the first node and the second node on the first candidate route, and wherein at least one link of the plurality of links is not included in an existing route between the first node and the second node;

a processor configured to discontinue use of the existing route; and

commence use of the selected first candidate route in place of the existing route, wherein use of the plurality of links of the selected first candidate route is initialized via nodes of the existing route; and

wherein use of the first candidate route is maintained until a second candidate route is selected such that data may be transmitted over the maintained first candidate route until the second candidate route is commenced.

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

receiving a message at a device in the 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;

if a direct link from the device to the second node is available, establishing a first 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 and maintaining use of the first candidate route until a second candidate route is selected such that data may be transmitted over the maintained first candidate route until the second candidate route is commenced, else forwarding the message to at least another device, and further establishing the first candidate route for routing packets between the first and second nodes only if the direct link is available and of sufficient quality.

24. The method as claimed in claim 23, further comprising adding a timestamp to the received message at the device.

25. The method as claimed in claim 23, wherein establishing a first candidate route comprises communicating the first candidate route to the second node.

26. The method as claimed in claim 25, wherein the first candidate route is communicated by forwarding the message to the second node.

27. The method as claimed in claim 23, wherein the device is a node of the first ad-hoc network.

28. The method as claimed in claim 23, wherein the at least another device comprises probable neighbors of the device in the ad-hoc network.

29. The method as claimed in claim 23, wherein the at least another device comprises at least another device to which the device in the ad-hoc network can establish a link of sufficient quality.

30. The method as claimed in claim 23, wherein the at least another device comprises a node adjacent the device in the ad-hoc network in the existing route.

31. A device 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 determining element for determining if a direct link from the device to a second node is available;

a candidate route establishing element for establishing a first candidate route for routing packets between a first node and the second node 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, wherein use of the first candidate route is maintained until a second candidate route is selected such that data may be transmitted over the maintained first candidate route until the second candidate route is commenced;

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, and further establishing the first candidate route for routing packets between the first and second nodes only if the direct link is available and of sufficient quality.

32. A device 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 broadcasting a DUPROUTE packet to one or more neighbor nodes to determine an existence of one or more alternate routes between a first node and a destination node, wherein the DUPROUTE packet comprises a TimeToLive field, and wherein the one or more neighbor nodes are configured to decrement the TimeToLive field and forward the DUPROUTE packet to additional neighbor nodes if the destination node is not an immediate neighbor of the one or more neighbor nodes;

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, wherein the candidate route is maintained until a second candidate route is selected such that data may be transmitted over the maintained candidate route until the second selected candidate route is commenced.