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

Patent metadata

Field	Value
Publication number	US-10063460-B2
Application number	US-201514871700-A
Country	US
Kind code	B2
Filing date	Sep 30, 2015
Priority date	Sep 30, 2015
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

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.

First claim

What is claimed as new and desired to be protected by Letters Patent of the United States is:

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

Assignees

• Mitre Corp

Inventors

• Wu Pui W
• Barron Richard J

Classifications

• H04L45/122 Primary

  by minimising distances, e.g. by selecting a route with minimum of number of hops · CPC title

• H04W40/22 Primary

  using selective relaying for reaching a BTS [Base Transceiver Station] or an access point · CPC title

• H04L45/12

  Shortest path evaluation · CPC title

• H04L45/123

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• H04W40/246

  Connectivity information discovery · CPC title