Method and apparatus for shortening multi-hop routes in a wireless ad hoc network

• US 10,063,460 B2
• Filed: 09/30/2015
• Issued: 08/28/2018
• Est. Priority Date: 09/30/2015
• Status: Active Grant

• Current Assignee: Mitre Corporation
• Original Assignee: Mitre Corporation
• Inventors: Wu, Pui W., Barron, Richard J.
• Primary Examiner(s): Phillips, Hassan
• Assistant Examiner(s): Sharma, Gautam
• Application Number:
  US14/871,700
• Publication Number:
  US 20170093687A1
• Time in Patent Office: 1,063 Days
• Field of Search: None
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method for routing data packets in a network comprising, at a first node of the network, establishing communication with a plurality of neighbor nodes in the network, determining a destination node for a data packet, determining a path for routing the data packet from the first node to the destination node, wherein the path comprises one or more relay nodes for relaying the data packet from the first node to the destination node, the one or more relay nodes comprising a first neighbor node of the plurality of neighbor nodes for receiving the data packet from the first node, identifying among the one or more relay nodes and the destination node a second neighbor node of the plurality of neighbor nodes, and in accordance with the identification of the second neighbor node, transmitting the data packet to the second neighbor node.

Claims

1. A method for routing data packets in a network, comprising:

at a first node of the network;

establishing communication with a plurality of neighbor nodes in the network, the plurality of neighbor nodes being within a radio communication range of the first node;

determining a destination node for a data packet;

determining a path for routing the data packet from the first node to the destination node, wherein the path comprises a sequence of one or more relay nodes for relaying the data packet from the first node to the destination node, the one or more relay nodes comprising a first neighbor node of the first node for receiving the data packet from the first node;

comparing the destination node and each node in the sequence of one or more relay nodes in backwards order with the plurality of neighbor nodes until a node from the one or more relay nodes and the destination node is identified as being a second neighbor node of the first node; and

reducing a length of the path by transmitting the data packet to the second neighbor node instead of the first neighbor node in response to identifying the second neighbor node.

2. The method of claim 1, wherein the network is a wireless ad-hoc network that routes data within the network using wireless radio signals.

3. The method of claim 1, wherein establishing communication with a plurality of neighbor nodes comprises communicating directly with each node of the plurality of neighbor nodes.

4. The method of claim 1, wherein establishing communication with a plurality of neighbor nodes comprises:

broadcasting a first message comprising identification of the first node;

receiving a neighbor message from each neighbor node in the plurality of neighbor nodes, wherein for a respective neighbor node, the neighbor message comprises the identification of the first node and identification of the respective neighbor node; and

broadcasting a second message containing identification of the first node and identification of each neighbor node in the plurality of neighbor nodes.

5. The method of claim 1, wherein identifying the second neighbor node comprises:

selecting a first selected node of the one or more relay nodes and the destination node;

determining whether the plurality of neighbor nodes comprises the first selected node;

in accordance with a determination that the plurality of neighbor nodes does not comprise the first selected node, selecting a second selected node of the one or more relay nodes, wherein the second selected node is selected so as to be between the first selected node and the first node on the path; and

determining whether the plurality of neighbor nodes comprises the second selected node.

6. The method of claim 1, wherein the first node receives, from a respective node in the network, information about a subset of neighbor nodes for the respective node and the path is determined based on the information.

7. The method of claim 1, wherein:

prior to determining the destination node for the data packet, the first node receives a message originated by the destination node comprising a list of one or more selected neighbor nodes; and

the path for routing the data packet is determined at least in part based on the list of one or more selected neighbor nodes.

8. The method of claim 1, wherein reducing the length of the path comprises reducing an amount of nodes required to relay the data packet form the first node to the destination node.

9. The method of claim 1, comprising:

maintaining a sparse network topology of the network, wherein the path is determined based on the sparse network topology.

10. A device for routing data packets in a network, comprising:

one or more processors,

memory, and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs comprising instructions for;

establishing communication with a plurality of neighbor nodes in the network, the plurality of neighbor nodes being within a radio communication range of the first node;

determining a destination node for a data packet;

determining a path for routing the data packet from the device to the destination node, wherein the path comprises a sequence of one or more relay nodes for relaying the data packet from the device to the destination node, the one or more relay nodes comprising a first neighbor node of the first node for receiving the data packet from the device;

comparing the destination node and each node in the sequence of one or more relay nodes in backwards order with the plurality of neighbor nodes until a node from the one or more relay nodes and the destination node is identified as being a second neighbor node of the first node; and

reducing a length of the path by transmitting the data packet to the second neighbor node instead of the first neighbor node in response to identifying the second neighbor node.

11. The device of claim 10, wherein the network is a wireless ad-hoc network that routes data within the network using wireless radio signals.

12. The device of claim 10, wherein establishing communication with a plurality of neighbor nodes comprises communicating directly with each node of the plurality of neighbor nodes.

13. The device of claim 10, wherein establishing communication with a plurality of neighbor nodes comprises:

broadcasting a first message comprising identification of the device;

receiving a neighbor message from each neighbor node in the plurality of neighbor nodes, wherein for a respective neighbor node, the neighbor message comprises the identification of the device and identification of the respective neighbor node; and

broadcasting a second message containing identification of the device and identification of each neighbor node in the plurality of neighbor nodes.

14. The device of claim 10, wherein identifying the second neighbor node comprises:

selecting a first selected node of the one or more relay nodes and the destination node;

determining whether the plurality of neighbor nodes comprises the first selected node;

in accordance with a determination that the plurality of neighbor nodes does not comprise the first selected node, selecting a second selected node of the one or more relay nodes, wherein the second selected node is selected so as to be between the first selected node and the device on the path; and

determining whether the plurality of neighbor nodes comprises the second selected node.

15. The device of claim 10, wherein the device receives, from a respective node in the network, information about a subset of neighbor nodes for the respective node and the path is determined based on the information.

16. The device of claim 10, wherein:

prior to determining the destination node for the data packet, the device receives a message originated by the destination node comprising a list of one or more selected neighbor nodes; and

the path is determined at least in part based on the list of one or more selected neighbor nodes.

17. The device of claim 10, wherein reducing the length of the path comprises reducing an amount of nodes required to relay the data packet form the first node to the destination node.

18. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a node of a network, cause the node to:

establish communication with a plurality of neighbor nodes in the network, the plurality of neighbor nodes being within a radio communication range of the first node;

determine a destination node for a data packet;

determine a path for routing the data packet from the node to the destination node, wherein the path comprises a sequence of one or more relay nodes for relaying the data packet from the node to the destination node, the one or more relay nodes comprising a first neighbor node of the first node for receiving the data packet from the node;

compare the destination node and each node in the sequence of one or more relay nodes in backwards order with the plurality of neighbor nodes until a node from the one or more relay nodes and the destination node is identified as being a second neighbor node of the first node; and

reducing a length of the path by transmitting the data packet to the second neighbor node for relay to the destination node instead of the first neighbor node in response to identifying the second neighbor node.

19. A method for routing data packets in a network, comprising:

at a first node of the network;

establishing communication with a plurality of neighbor nodes in the network, the plurality of neighbor nodes being within a radio communication range of the first node;

storing, in a memory of the first node, information identifying the plurality of neighbor nodes;

determining a path for routing data from the first node to a second node in the network, wherein the path comprises a sequence of one or more relay nodes for relaying the data from the first node to the second node, the one or more relay nodes comprising a first neighbor node of the first node for receiving the data from the first node;

comparing the destination node and the one or more nodes in the sequence with the information identifying the plurality of neighbor nodes until a node from the one or more relay nodes and the destination node is identified as being a second neighbor node of the first node;

storing, in the memory of the first node, at least a portion of a shortened path for routing data from the first node to the second node, wherein the at least a portion of the shortened path comprises at least the second neighbor node;

determining that a destination for a data packet comprises the second node; and

reducing a length of the path by transmitting the data packet to the second neighbor node instead of the first neighbor node in accordance with the at least a portion of the shortened path stored in the memory.

20. The method of claim 19, wherein the network is a wireless ad-hoc network that routes data within the network using wireless radio signals.

21. The method of claim 19, wherein establishing communication with a plurality of neighbor nodes comprises communicating directly with each node of the plurality of neighbor nodes.

22. The method of claim 19, wherein establishing communication with a plurality of neighbor nodes comprises:

broadcasting a first message comprising identification of the first node;

receiving a neighbor message from each neighbor node in the plurality of neighbor nodes, wherein for a respective neighbor node, the neighbor message comprises the identification of the first node and identification of the respective neighbor node; and

broadcasting a second message containing identification of the first node and identification of each neighbor node in the plurality of neighbor nodes.

23. The method of claim 19, wherein identifying the second neighbor node comprises:

selecting a first selected node of the one or more relay nodes and the second node;

determining whether the plurality of neighbor nodes comprises the first selected node;

in accordance with a determination that the plurality of neighbor nodes does not comprise the first selected node, selecting a second selected node of the one or more relay nodes, wherein the second selected node is selected so as to be between the first selected node and the first node on the path; and

determining whether the plurality of neighbor nodes comprises the second selected node.

24. The method of claim 19, wherein the first node receives, from a respective node in the network, information about a subset of neighbor nodes for the respective node and the path is determined based on the information.

25. The method of claim 19, wherein:

prior to determining the path for routing data from the first node to the second node, the first node receives a message originated by the second node comprising a list of one or more selected neighbor nodes; and

the path for routing the data is determined at least in part based on the list of one or more selected neighbor nodes.

26. The method of claim 19, wherein the method reduces an amount of nodes required to relay the data packet from the first node to the second node.

27. A device for routing data packets in a network, comprising:

one or more processors,

memory, and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs comprising instructions for;

establishing communication with a plurality of neighbor nodes in the network, the plurality of neighbor nodes being within a radio communication range of the first node;

storing, in a memory of the first node, information identifying the plurality of neighbor nodes;

determining a path for routing data from the device to a second node in the network, wherein the path comprises a sequence of one or more relay nodes for relaying the data from the first node to the second node, the one or more relay nodes comprising a first neighbor node of the first node for receiving the data from the device;

comparing the destination node and the one or more relay nodes in the sequence with the information identifying the plurality of neighbor nodes until a node from the one or more relay nodes and the destination node is identified as being a second neighbor node of the first node;

storing, in a routing table in the memory of the first node, at least a portion of a shortened path for routing data from the first node to the second node, wherein the at least a portion of the shortened path comprises at least the second neighbor node;

determining that a destination for a data packet comprises the second node; and

reducing a length of the path by transmitting the data packet to the second neighbor node instead of the first neighbor node in accordance with the at least a portion of the shortened path stored in the routing table.