Distance adaptive routing protocol

• US 8,059,544 B2
• Filed: 12/20/2006
• Issued: 11/15/2011
• Est. Priority Date: 12/20/2006
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Wright, George L., Yi, Yunjung, Thomas, Vicraj T.
• Primary Examiner(s): Ferris; Derrick
• Assistant Examiner(s): GHOWRWAL, OMAR J
• Application Number:
  US11/613,700
• Publication Number:
  US 20080151889A1
• Time in Patent Office: 1,791 Days
• Field of Search: 370/238, 370/390, 370/229, 370/235, 370/236, 370/237, 370/241, 370/252, 370/254, 370/255, 370/310, 370/351, 370/389, 370/392, 370/400, 370/412, 370/413, 370/428, 370/429
• US Class Current: 370/236
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 47/2416 Real-time traffic

Abstract

A method of routing packets in an ad-hoc network is provided. The method determines a hop count for a route. Then, a redundancy value is calculated based on the hop count. A plurality of packets containing identical payload information is then sent down a number of routes equal to the redundancy value.

Claims

1. A method of routing packets in a wireless mobile ad-hoc network comprising:

determining a hop count for a primary route from a first node of the wireless mobile ad-hoc network to a second node of the wireless mobile ad-hoc network;

calculating a redundancy value based on the hop count for the primary route;

sending from the first node of the wireless mobile ad-hoc network a first plurality of packets containing identical payload information down a number of routes equal to the redundancy value; and

at the second node of the wireless mobile ad-hoc network, forwarding a first packet of the first plurality of packets before a second packet of the first plurality of packets, wherein the first packet has traveled through more nodes of the wireless mobile ad-hoc network than the second packet.

2. The method of claim 1, wherein sending the packets further comprises:

concurrently sending all the packets.

3. The method of claim 1, further comprising:

discovering a plurality of routes to a destination;

selecting the primary route from the plurality of routes thereby designating all other routes of the plurality of routes as backup routes, wherein determining the hop count determines the hop count for the primary route; and

selecting at least one redundant route from the backup routes, wherein the number of routes includes the primary route and the at least one redundant route.

4. The method of claim 3, wherein selecting the at least one redundant route further comprises:

choosing a maximum disjointed path from the primary route.

5. The method of claim 1, further comprising:

forwarding packets with longer routes quicker than packets with shorter routes.

6. A method of routing packets in a wireless mobile ad-hoc network comprising:

determining a distance to a destination from a first node of the wireless mobile ad-hoc network along a primary route;

calculating a redundancy value based on the distance to the destination along the primary route;

sending from the first node of the wireless mobile ad-hoc network a number of packets equal to the redundancy value toward the destination, wherein each packet has the same payload information; and

forwarding, from the destination, a first packet of the number of packets before a second packet of the number of packets, wherein the first packet has traveled a greater distance through the mobile ad-hoc network than the second packet.

7. The method of claim 6, wherein sending the number of packets further comprises:

using configuration aware routing to send at least one of the packets.

8. The method of claim 6, wherein determining the distance further comprises:

counting a number of hops on a route to the destination.

10. The method of claim 6, further comprising:

discovering a plurality of routes to the destination;

selecting the primary route from the plurality of routes, thereby designating as backup routes all routes not selected as the primary route from the plurality of routes;

selecting at least one redundant route from the backup routes; and

wherein sending the number of packets comprises sending at least one packet down the primary route and at least one packet down the at least one redundant route.

11. The method of claim 10, wherein selecting the at least one redundant route further comprises:

selecting a number of routes equal to the redundancy value minus one; and

wherein sending the number of packets further comprises sending one packet down the primary route and one packet down each redundant route.

12. The method of claim 10, wherein selecting the at least one redundant route further comprises:

selecting a maximum disjointed path from the primary route.

13. The method of claim 6, further comprising:

receiving one of the number of packets at the destination;

incrementing an aging value for the received packet; and

prioritizing a plurality of packets including the received packet, based on the aging value of each packet.

14. The method of claim 13, wherein prioritizing the plurality of packets further comprises:

providing a plurality of priority queues; and

placing packets of similar priority in a same queue.

15. The method of claim 6, wherein calculating the redundancy value further comprises:

calculating an error probability based on the distance to the destination; and

wherein calculating the redundancy value is further based on the error probability and a desired error rate.

16. The method of claim 6, wherein sending the number of packets is sending a first round of packets, the method further comprising:

sending at least a second round of packets;

receiving at the destination at least one of the second round of packets prior to the first round of packets; and

re-ordering the received packets.

17. The method of claim 6, wherein determining the distance further comprises:

determining a physical distance to the destination.

9. The method of clam 6, wherein sending the number of packets further comprises:

sending all the packets down a single route.

18. A method of processing packets at a first node of a wireless mobile ad-hoc network, the method comprising:

receiving a first packet of a plurality of packets sent from a node at the first node of the wireless mobile ad-hoc network, wherein each of the plurality of packets has a corresponding aging value representing how many times each of the plurality of packets has been forwarded from any node of the wireless mobile ad-hoc network to any other node of the wireless mobile ad-hoc network;

incrementing the aging value corresponding to the first packet when the first packet is received at the first node of the wireless mobile ad-hoc network;

prioritizing the plurality of packets including the first packet and a second packet of the plurality of packets, based on the aging values associated with each of the plurality of packets; and

forwarding the packets from the first node of the wireless mobile ad-hoc network to another node of the wireless mobile ad-hoc network based on the priority of the packets, wherein the first packet is forwarded before the second packet when the first packet has a higher aging value than the second packet.

19. The method of claim 18, further comprising:

providing a plurality of priority queues; and

placing packets of similar priority in a same queue; and

wherein forwarding the packets takes packets from the plurality of priority queues.

20. The method of claim 18, wherein the prioritizing further comprises:

adding the aging value corresponding to the first packet to an existing priority value of the first packet; and

wherein prioritizing the plurality of packets prioritizes based on the priority value including the aging value.