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

• US 20090129316A1
• Filed: 08/18/2008
• Published: 05/21/2009
• 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: BBN Technologies (Rtx Corporation)
• Inventors: Krishnan, Rajesh, Basu, Prithwish, Hansen, Richard Earl, Ramanathan, Subramanian, Hain, Regina Rosales, Jones, Christine Elaine
• Granted Patent: US 8,149,716 B2
• Time in Patent Office: Days
• US Class Current: 370/328
• 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 the routing cost associated with delivering the data bundle from the router to the destination node, ii) comparing the routing cost with a threshold value, and iii) if the routing cost is greater than or equal to the threshold value, then further processing the data bundle based on a first routing mechanism or, if the routing cost is less than the threshold value, then further processing the data bundle based on a second routing mechanism.

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 including 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 mechanism includes prioritized epidemic routing.

7. The router of claim 6, wherein the second routing mechanism 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 routing 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 routing parameter.

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

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

14. The method of claim 8, wherein selecting a protocol comprises determining whether the packet is likely to be transmitted with sufficient reliability using a first transmission protocol.

15. The method of claim 14, 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.

16. The method of claim 14, 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.

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

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

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

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

21. The method of claim 14, wherein determining whether the packet is likely to be transmitted with sufficient reliability comprises comparing the routing parameter to a threshold.

22. The method of claim 21, wherein the threshold is determined based on the contents of the packet.

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

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

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

26. An epidemic routing process for a communication network, comprising

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

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

determining a first prioritized list for transmitting the packets based on the routing parameter,

determining a second prioritized list for dropping the packets based on the routing parameter,

transmitting the packets from the first node to at least a second and a third node of the plurality of nodes in the communication network using a transmission protocol, wherein the transmission protocol is an epidemic routing process.

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

28. The method of claim 27, 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.

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

30. The method of claim 26, 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.

31. The method of claim 30, wherein the availability measure is an average availability.

32. The method of claim 26, wherein the transmission protocol further comprises identifying a packet using network topology information.