Mobility-aware mesh construction algorithm for low data-overhead multicast ad hoc routing

• US 9,713,061 B2
• Filed: 06/25/2014
• Issued: 07/18/2017
• Est. Priority Date: 11/30/2005
• Status: Active Grant

• Current Assignee: PCMS Holdings Incorporated (InterDigital, Inc.)
• Original Assignee: PCMS Holdings Incorporated (InterDigital, Inc.)
• Inventors: Ruiz, Pedro M., Gomez Skarmeta, Antonio F.
• Primary Examiner(s): Jung, Min
• Application Number:
  US14/314,899
• Publication Number:
  US 20140307614A1
• Time in Patent Office: 1,119 Days
• Field of Search: None
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Data overhead of mesh-based multicast ad hoc routing protocols are controlled by adaptively adding redundancy to the minimal data overhead multicast mesh as required by the network conditions. The computation of the minimal data overhead multicast mesh is NP-complete, and therefore an heuristic approximation algorithm inspired on epidemic algorithms is employed to increase tractability of a solution. A mobility-aware and adaptive mesh construction algorithm based on a probabilistic path selection is provided, which is able to adapt the reliability of the multicast mesh to the mobility of the network. Simulation results show that the proposed approach, when implemented into On-Demand Multicast Routing Protocol (ODMRP), is able to offer similar performance results and a lower average latency, while reducing data overhead between 25 to 50% compared to the original ODMRP.

Claims

1. A mobile node of an ad hoc network, comprising:

a wireless communication interface configured to support ad hoc communications with a plurality of other mobile nodes;

a memory configured to store multicast trees; and

at least one automated processor configured to support at least a multicast communication through the wireless communication interface dependent on the stored multicast trees, and to select a communication path based on a composite function of at least a reliability metric and a communication data-overhead metric, wherein low data-overhead paths are selected with increasing probability with an increasing reliability.

2. The mobile node according to claim 1, the at least one processor is further configured to engage in an epidemic propagation of a number of available forwarding nodes in order to define multicast paths.

3. The mobile node according to claim 1, wherein the processor adaptively constructs a mobility-aware mesh.

4. The mobile node according to claim 3, wherein the adaptive mobility-aware mesh approximates a minimal data overhead forwarding mesh.

5. The mobile node according to claim 1, wherein the reliability metric is a function of at least a link duration associated with the each of the other mobile nodes and a number of available paths under current mobility conditions of the mobile ad hoc network.

6. The mobile node according to claim 5, wherein communication paths having a low data-overhead are more probably selected with an increase in a predicted reliability, and paths having a short path length are less probably selected with an increase in the predicted reliability.

7. The mobile node according to claim 1, wherein the at least one processor employs a mobility-aware mesh construction algorithm which employs a heuristic to approximate minimal data overhead forwarding meshes based on an epidemic propagation of a number of forwarding nodes during creation of multicast communication paths, to provide information for selection between alternate communication paths, each communication path characterized by a path length and a path data-overhead.

8. The mobile node according to claim 1, wherein the at least one processor is configured to select a respective communication path with a probability inversely related at least e raised to the power of the link duration, and inversely related to the square of the number of alternate paths between a source and a destination.

9. The mobile node according to claim 1, wherein the at least one processor is configured to further determine a cost of employing a node, and to select a respective communication path in dependence on at least a cost of the nodes in the communication path.

10. The mobile node according to claim 1, wherein the at least one processor is further configured to determine a number of nodes in available communications paths, and select a first communication path having a smaller number of nodes over a second communication path having a larger number of nodes.

11. A method for controlling an ad hoc network, comprising:

communicating between an ad hoc network node and a plurality of other ad hoc network nodes through a communication interface;

maintaining, at the ad hoc network node, a plurality of multicast trees; and

hosting and routing communications through the ad hoc network, with at least one automated processor, in dependence on the plurality of multicast trees, wherein a communication path is probabilistically selected based on a composite function of at least a communication reliability metric and a communication data-overhead metric, wherein low data-overhead paths are selected with increasing probability with an increasing reliability.

12. The method according to claim 11, further comprising performing epidemic propagation of a number of available forwarding nodes in order to define multicast paths.

13. The method according to claim 11, further comprising constructing an adaptive mobility-aware mesh which approximates a minimal data overhead forwarding mesh.

14. The method according to claim 11, wherein the reliability metric is a function of at least a link duration associated with the each of the plurality of other mobile nodes and a number of available paths under current mobility conditions of nodes of the ad hoc network.

15. The method according to claim 14, further comprising more probably selecting communication paths having a low data-overhead with an increase in a predicted reliability, and less probably selecting communication paths having a short path length with an increase in the predicted reliability.

16. The method according to claim 11, further comprising performing a mobility-aware mesh construction algorithm employing a heuristic to approximate minimal data overhead forwarding meshes based on an epidemic propagation of a number of forwarding nodes during creation of multicast communication paths, to provide information for selection between alternate communication paths, each communication path characterized by a path length and a path data-overhead.

17. The method according to claim 11, further comprising selecting a respective communication path with a probability inversely related at least e^ld, wherein ld is the link duration.

18. The method according to claim 11, further comprising determining a cost of employing a respective ad hoc network node, and selecting a communication path in dependence on at least a cost of the respective mobile ad hoc network nodes in the respective communication path.

19. The method according to claim 11, further comprising determining a number of nodes in available communications paths, and selecting a first communication path having a smaller number of nodes over a second communication path having a larger number of nodes.

20. A method for controlling an ad hoc network, comprising:

automatically maintaining a plurality of multicast trees, hosting communications and routing communications in a mobile ad hoc network through an automated wireless communication interface; and

automatically selecting communications paths for communication through the automated wireless interface from a plurality of possible communication paths, dependent on at least the maintained multicast trees, a reliability metric and a communication data-overhead metric, wherein low data-overhead paths to a communication destination are selected with increasing probability with an increasing reliability of a respective path.