Configuration aware packet routing in an ad-hoc network

• US 8,451,807 B2
• Filed: 12/20/2006
• Issued: 05/28/2013
• Est. Priority Date: 12/20/2006
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Yi, Yunjung, Thomas, Vicraj T., Wright, George L.
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US11/613,730
• Publication Number:
  US 20080151841A1
• Time in Patent Office: 2,351 Days
• Field of Search: 370/310, 370/328, 370/338, 370/232, 370/243, 370/352, 370/389, 370/400, 370/401, 370/392, 455/428, 455/445, 455/446, 455/449
• US Class Current: 370/338
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

A method of routing a packet in an ad-hoc network is provided. The method provides a packet at a first node, the first node being one of a plurality of nodes. A destination node is determined for the packet, the destination node being one of the plurality of nodes. Configuration information is also provided, the configuration information representing the location of each of the plurality of nodes. Finally, at least one forward node in a direction towards the destination node is selected based on the configuration information, and packets are sent to the at least one forward node.

Claims

1. A method of routing a packet in an ad-hoc network comprising:

providing a packet at a first node, the first node being one of a plurality of nodes;

determining a destination node for the packet, the destination node being one of the plurality of nodes;

providing configuration information representing the relative location of each of the plurality of nodes to the first node, wherein the relative location of each node is provided to the first node during a set-up of the first node on the network;

using a first routing protocol to discover a first route between the first node and the destination node;

when at least one route discovered by the first routing protocol is valid between the first node and the destination node, routing the packet through the at least one route discovered by the first routing protocol, wherein a route is valid when it has no breakages; and

when no routes discovered by the first routing protocol are valid between the first node and the destination node, routing the packet from the first node using a configuration aware routing protocol using the configuration information stored at the first node by;

selecting at least one forward node based on the configuration information, wherein the forward node is in a direction towards the destination node; and

sending the packet to the at least one forward node.

2. The method of claim 1, wherein the configuration of the plurality of nodes is substantially linear and selecting the forward node further comprises:

selecting a node adjacent to the first node.

3. The method of claim 1, wherein the configuration of the plurality of nodes is non-linear and selecting a forward node further comprises:

identifying a subgroup of the plurality of nodes, the subgroup being in direct communication with the first node, and

comparing the configuration information to the subgroup.

4. The method of claim 1, further comprising:

detecting that the route is invalid prior to sending the packet to the at least one forward node.

5. The method of claim 1, further comprising:

updating the configuration information.

6. The method of claim 1, wherein selecting the at least one forward node further comprises:

calculating a direction to the destination node based on GPS coordinates; and

selecting the node closest to the direction of the destination node.

18. The method of claim 1, wherein when a distance to the destination node from the first node is greater than two hops, sending at least one redundant packet to at least one forward node, wherein a number of the at least one redundant packet being sent is adjusted based on the distance from the first node to the destination node.

7. A method of routing a packet in a semi-static, substantially linear ad-hoc network, the method comprising:

providing a packet at a first node in the semi-static, linearly-configured ad-hoc network;

determining a destination node for the packet, wherein the destination node is in the semi-static, substantially linear ad-hoc network;

discovering a first route between the first node and the destination node using a first routing protocol;

determining at least one forward node that is in a direction towards the destination node relative to the first node;

when at least one route discovered by the first routing protocol is valid between the first node and the destination node, routing the packet through the at least one route;

where no routes discovered by the first routing protocol are valid between the first node and the destination node, routing the packet from the first node using a configuration aware routing protocol based on configuration information regarding a relationship between the locations of a first node and at least one other node in the semi-static, substantially linear ad-hoc network by sending the packet to the at least one forward node in a direction towards the destination node.

8. The method of claim 7, wherein determining the at least one forward node further comprises:

selecting a node adjacent to the first node.

9. The method of claim 7, further comprising:

detecting an invalid route prior to determining the at least one forward node.

10. The method of claim 7, further comprising:

discovering a new route after detecting a break in the first route; and

sending all packets determined to be going to the destination node to the at least one forward node until discovering the new route is completed.

11. The method of claim 10, further comprising:

sending all packets determined to be going to the destination node through the new route after discovering the new route is completed.

12. The method of claim 7, wherein determining the at least one forward node further comprises:

determining based on information that states the order of a substantially linear plurality of nodes.

19. The method of claim 7, wherein when a distance to the destination node from the first node is greater than two hops, sending at least one redundant packet to at least one forward node, wherein a number of the at least one redundant packet being sent is adjusted based on the distance from the first node to the destination node.

13. A node for an ad-hoc network comprising:

a transmitter;

a receiver;

a data storage mechanism containing configuration information representing the location of the node relative to at least one other node, wherein location information for a plurality of other nodes in the ad-hoc network are provided to the node during a set-up of the node on the ad-hoc network; and

a processor coupled to the transmitter, receiver, and data storage mechanism, the processor configured to;

when at least one route discovered by a first routing protocol is valid between the node and a destination node, select a first route to route packets from the first node to the destination node; and

when no routes discovered by the first routing protocol are valid, temporarily routing using a configuration aware routing protocol by choosing a forwarding node for a packet by selecting an adjacent node in the direction of the destination node, the adjacent node determined from the configuration information.

14. The node of claim 13, wherein the configuration information includes information that relates the nodes as one in front of the other.

15. The node of claim 14, wherein the configuration information includes information on the relative locations of all the nodes in the network.

16. The node of claim 14, wherein the nodes within the network form a configuration that is substantially linear.

17. The node of claim 13, wherein the node is wireless and mobile.

20. The node of claim 13, wherein the processor is further configured to choose a forwarding node for at least one redundant packet if a distance to the destination node from the first node is greater than two hops, wherein the processor is further configured to adjust a number of the at least one redundant packet to be sent based on the distance to the destination node.