Systems and methods for adaptive routing in mobile ad-hoc networks and disruption tolerant networks

• US 8,149,716 B2
• Filed: 08/18/2008
• Issued: 04/03/2012
• Est. Priority Date: 08/20/2007
• Status: Active Grant

• Current Assignee: US Department of The Army (Government of the United States of America)
• Original Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Inventors: Ramanathan, Subramanian, Basu, Prithwish, Hansen, Richard Earl, Jones, Christine Elaine, Krishnan, Rajesh, Hain, Regina Rosales
• Primary Examiner(s): Nguyen, Hanh
• Application Number:
  US12/229,039
• Publication Number:
  US 20090129316A1
• Time in Patent Office: 1,324 Days
• Field of Search: 370/465, 370/466, 370/351, 370/236, 370/238, 370/238.1, 370/241.1, 370/252, 370/254, 370/392, 370/338, 370/328, 370/329, 370/395.42, 370/400
• US Class Current: 370/238
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/52 Multiprotocol routers
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

The systems and methods described herein include adaptive routing processes for packet-based wireless communication networks. This routing approach works both in MANETs (when a contemporaneous end-to-end path is available) and in DTNs (when a contemporaneous end to end path is not available, but one of formed over space and time). In particular, the methods include adaptively selecting a routing process for transmitting a packet through a node in the network based on available information on the network topology and/or the contents of the packet.

Claims

1. An adaptive router in a communications network comprising:

a receiver for receiving a data bundle, the data bundle originating from a source node and having a designated destination node, and

a processor for i) determining a routing cost associated with delivering the data bundle from the router to the destination node, ii) comparing the routing cost with a threshold value, iii) in response to the routing cost being greater than or equal to the threshold value, further processing the data bundle based on a first routing protocol and, in response to the routing cost being less than the threshold value, further processing the data bundle based on a second routing protocol, and iv) forwarding the data bundle using the selected first or second routing protocol.

2. The router of claim 1, wherein the receiver receives topology awareness information from one or more other nodes in the communications network.

3. The router of claim 2, wherein the topology awareness information includes link availability information associated with one or more communications links between a plurality of nodes of the communications network.

4. The router of claim 3, wherein the routing cost is based, at least in part, on the availability information.

5. The router of claim 4, wherein the threshold is at least one of predetermined or dynamically set.

6. The router of claim 1, wherein the first routing protocol includes prioritized epidemic routing.

7. The router of claim 6, wherein the second routing protocol includes a shortest cost path mode.

8. A method for routing packets in a communication network, comprising

receiving a packet at a first node in a communication network having a plurality of nodes;

determining a route quality parameter of a communication channel between at least two of the plurality of nodes in the communication network; and

selecting a protocol for transmitting the packet from the first node to at least a second node of the plurality of nodes in the communication network based on the route quality parameter, wherein selecting a protocol comprises determining whether the packet is likely to be transmitted with sufficient reliability using a first transmission protocol by comparing the route quality parameter to a threshold.

9. The method of claim 8, wherein the communication network includes at least one of mobile and wireless nodes.

10. The method of claim 8, wherein a first portion of the communication network exhibits characteristics of a disruption tolerant network and a second portion of the communication network exhibits characteristics of a connected mobile ad hoc network.

11. The method of claim 10, wherein the first and second portions of the communication network change over time.

12. The method of claim 10, wherein the route quality parameter includes at least one of a delay, a bandwidth, and an availability measure of at least one of the plurality of nodes in the communication network.

13. The method of claim 12, wherein the availability measure is an average availability.

14. The method of claim 8, wherein if it is determined that the packet will not be transmitted with sufficient reliability using the first transmission protocol, selecting a second transmission protocol to transmit the packet.

15. The method of claim 14, wherein at least one of the first and second transmission protocols is a shortest-path routing process.

16. The method of claim 14, wherein at least one of the first and second transmission protocols is an epidemic routing process.

17. The method of claim 16, further comprising determining a prioritized list for transmitting the packets.

18. The method of claim 16, further comprising determining a prioritized list for dropping the packets.

19. The method of claim 8, wherein if it is determined that the packet will be transmitted with sufficient reliability using the first transmission protocol, selecting the first transmission protocol to transmit the packet.

20. The method of claim 8, wherein the threshold is determined based on the contents of the packet.

21. The method of claim 8, wherein the threshold is determined based on a reliability requirement for transmitting the packet from the first node to a destination node.

22. The method of claim 8, further comprising transmitting the packets using the protocol.

23. The method of claim 8, wherein selecting a protocol comprises identifying a packet including network topology information, and in response, selecting a flooding protocol to transmit the packet.

24. A routing process for a communication network, comprising

receiving packets at a first node in a communication network having a plurality of nodes, the first node having a buffer and a first threshold for buffer occupancy of the buffer;

determining a routing parameter of a communication channel between at least two of the plurality of nodes in the communication network;

determining a prioritized list for dropping the packets based on the routing parameter; and

dropping, based on the prioritized list, at least one of the packets from the first node in response to the buffer occupancy of the buffer being greater than or equal to the first threshold.

25. The method of claim 24, wherein the communication network includes at least one of mobile and wireless nodes.

26. The method of claim 25, wherein a first portion of the communication network exhibits characteristics of a disruption tolerant network and a second portion of the communication network exhibits characteristics of a connected mobile ad hoc network.

27. The method of claim 26, wherein the first and second portions of the communication network change over time.

28. The method of claim 24, wherein the routing parameter includes at least one of a delay, a bandwidth, and an availability measure of at least one of the plurality of nodes in the communication network.

29. The method of claim 28, wherein the availability measure is an average availability.

30. The method of claim 24, further comprising transmitting at least one of the packets from a first node to at least a second and third node of the plurality of nodes in the communication network using a transmission protocol, wherein the transmission protocol further comprises identifying a packet using network topology information.

31. The method of claim 24, wherein

the first node further includes a second threshold for buffer occupancy of the buffer, the second threshold being less than the first threshold;

and

wherein dropping the at least one packet comprises dropping at least one packet based on the prioritized list until a number of packets in the buffer equals the second threshold.