Multiple path reactive routing in a mobile ad hoc network

• US 6,961,310 B2
• Filed: 08/08/2002
• Issued: 11/01/2005
• Est. Priority Date: 08/08/2002
• Status: Expired due to Term

• Current Assignee: Stingray IP Solutions LLC (Acacia Research Corporation)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Cain, Joseph Bibb
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): Hyun, Soon D.
• Application Number:
  US10/214,997
• Publication Number:
  US 20040029553A1
• Time in Patent Office: 1,181 Days
• Field of Search: 370/238, 370/238.1, 370/252, 370/338, 370/349, 370/330, 370/332, 370/340, 370/341, 375/267, 709/239, 709/240, 709/241, 709/242, 455/450, 455/452, 455/455
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/726 Reserving resources in multiple paths to be used simultaneously by balancing the load H04L47/125
• CPC Class Codes: H04L 47/746 Reaction triggered by a failure
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/824 Applicable to portable or mobile terminals
• CPC Class Codes: H04W 28/26 Resource reservation
• 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/246 Connectivity information discovery
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

The method includes routing message data from a source node to a destination node in a mobile ad hoc network. The mobile ad-hoc network includes a plurality of intermediate mobile nodes between the source node and the destination node, and a plurality of wireless communication links connecting the nodes together. The method includes, at the source node, discovering routing to the destination node, ranking discovered routes according to at least one link metric, and distributing the message data to the destination node along a plurality of the discovered routes based upon the ranking. The link metric may include a measurement of link delay, link capacity, link available capacity, and/or link reliability.

Claims

1. A method for routing message data from a source node to a destination node in a mobile ad hoc network comprising a plurality of intermediate mobile nodes between the source node and the destination node, and a plurality of wireless communication links connecting the nodes together, the method comprising:

at the source node, transmitting a route request to discover routing to the destination node;

at each intermediate node, determining whether the intermediate node can support the route request and, if so, forwarding the route request to one of other intermediate nodes and the destination node, and temporarily reserving node resources for supportable route requests;

at the destination node, upon receiving the route request, generating a reply to the source node for each discovered route;

at the source node, ranking the discovered routes according to at least one link metric;

at the source node, selecting a plurality of routes to the destination node based upon the ranking;

at the source node, transmitting route confirmations to intermediate nodes on the plurality of selected routes; and

at the source node, distributing the message data to the destination node along the plurality of discovered routes.

2. A method according to claim 1 wherein distributing the message data comprises distributing duplicate message data along the plurality of discovered routes.

3. A method according to claim 1 wherein distributing the message data comprises distributing different portions of the message data along each of the plurality of discovered routes.

4. A method according to claim 1 wherein ranking the discovered routes comprises storing route entries in a route cache, each route entry corresponding to one of the discovered routes.

5. A method according to claim 4 wherein each route entry includes:

a metric value for the link metric; and

a usage factor indicating how much of the message data should be distributed to the corresponding route.

6. A method according to claim 5 wherein each route entry further includes a timer value for expiring the discovered route.

7. A method according to claim 4 wherein storing route entries comprises repeating route entries in the route cache for different classes of message data.

8. A method according to claim 7 wherein the different classes of message data include delay sensitive message data and large volume message data.

9. A method according to claim 1 wherein the link metric comprises a measurement of at least one of link delay, link capacity, link available capacity, and link reliability.

10. A method according to claim 1 further comprising, at the intermediate nodes and the destination node, detecting whether the node can continue to support the route request and, if not, generating an error notification to the source node for a failed route.

11. A method according to claim 10 further comprising, at the source node, upon receiving the error notification, purging the failed route from the discovered routes.

12. A method according to claim 11, further comprising, at the source node, transmitting a second route request to discover new routing to the destination node when the number of discovered routes falls below a threshold.

13. A method for routing message data from a source node to a destination node in a mobile ad hoc network comprising a plurality of intermediate mobile nodes between the source node and the destination node, and a plurality of wireless communication links connecting the nodes together, the method comprising:

at the source node, discovering routing to the destination node;

at the source node, ranking discovered routes according to at least one link metric; and

at the source node, simultaneously distributing the message data to the destination node along a plurality of the discovered routes based upon the ranking.

14. A method according to claim 13 wherein distributing the message data comprises distributing duplicate message data along the plurality of discovered routes.

15. A method according to claim 13 wherein distributing the message data comprises distributing different portions of the message data along each of the plurality of discovered routes.

16. A method according to claim 13 wherein ranking the discovered routes comprises storing route entries in a route cache, each route entry corresponding to one of the discovered routes.

17. A method according to claim 16 wherein each route entry includes:

a metric value for the link metric; and

a usage factor indicating how much of the message data should be distributed to the corresponding route.

18. A method according to claim 17 wherein each route entry further includes a timer value for expiring the discovered route.

19. A method according to claim 16 wherein storing route entries comprises repeating route entries in the route cache for different classes of message data.

20. A method according to claim 19 wherein the different classes of message data include delay sensitive message data and large volume message data.

21. A method according to claim 13 wherein the link metric comprises a measurement of at least one of link delay, link capacity, link available capacity, and link reliability.

22. A method according to claim 13 further comprising, at the source node, detecting failed routes and purging failed routes from the discovered routes.

23. A method according to claim 22 further comprising, at the source node, distributing the message data to the destination node along remaining discovered routes.

24. A method according to claim 23, further comprising, at the source node, transmitting a second route request to discover new routing to the destination node when the number of discovered routes falls below a threshold.

25. A mobile ad hoc network comprising:

a plurality of mobile nodes; and

a plurality of wireless communication links connecting the plurality of mobile nodes together;

each mobile node comprising

a communications device to wirelessly communicate with other nodes of the plurality of nodes via the wireless communication links, and

a controller to route communications via the communications device, the controller comprising

a route discovery unit to discover routing to a destination node,

a route ranking unit to rank discovered routes according to at least one link metric, and

a message data distribution unit to simultaneously distribute the message data to the destination node along a plurality of the discovered routes based upon the rank.

26. A network according to claim 25 wherein the message data distribution unit distributes duplicate message data along the plurality of discovered routes.

27. A network according to claim 25 wherein the message data distribution unit distributes different portions of the message data along each of the plurality of discovered routes.

28. A network according to claim 25 wherein the route ranking unit comprises a route cache for storing route entries each corresponding to one of the discovered routes.

29. A network according to claim 28 wherein each route entry includes:

a metric value for the link metric; and

a usage factor indicating how much of the message data should be distributed to the corresponding route.

30. A network according to claim 29 wherein each route entry further includes a timer value for expiring the discovered route.

31. A network according to claim 28 wherein the ranking unit repeats route entries in the route cache for different classes of message data.

32. A network according to claim 31 wherein the different classes of message data include delay sensitive message data and large volume message data.

33. A network according to claim 25 wherein the link metric comprises a measurement of at least one of link delay, link capacity, link available capacity, and link reliability.

34. A network according to claim 25 wherein the controller further comprises a route request processing unit to determine whether the node can continue to support the route request and, if not, to generate an error notification for a failed route.

35. A network according to claim 34, wherein the route ranking unit purges failed routes from the discovered routes.

36. A network according to claim 35, wherein the route discovery unit discovers new routing to the destination node when the number of discovered routes falls below a threshold.