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

• US 8,797,878 B1
• Filed: 12/04/2012
• Issued: 08/05/2014
• Est. Priority Date: 11/30/2005
• Status: Expired due to Fees

• Current Assignee: PCMS Holdings Incorporated (InterDigital, Inc.)
• Original Assignee: PCMS Holdings Incorporated (InterDigital, Inc.)
• Inventors: Ruiz, Pedro M., Gomez, Antonio Fernando Skarmeta
• Primary Examiner(s): Jung, Min
• Application Number:
  US13/693,368
• Time in Patent Office: 609 Days
• US Class Current: 370/238
• 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 method for operating a mobile node of an ad hoc network, comprising:

communicating through a wireless communication interface with a plurality of other mobile nodes;

building a plurality of multicast trees comprising identifications of alternate communication paths; and

routing and hosting communications through a mobile node of an multi-hop ad hoc network along a communication path, using at least a multicast communication through the wireless communication interface dependent on the multicast trees, and probabilistically selecting a respective communication path based on a composite function of at least a reliability metric and a communication data-overhead metric of the respective communication path, so that low data-overhead communication paths are selected with increasing probability with an increasing reliability of the respective communication path.

2. The method according to claim 1, further comprising engaging in an epidemic propagation of a number of available forwarding nodes in order to define communication paths.

3. The method according to claim 1, further comprising constructing a mobility-aware mesh.

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

5. The method 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 alternate communication paths under current mobility conditions of the mobile ad hoc network.

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

7. The method according to claim 1, further comprising employing 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 method according to claim 1, further comprising selecting 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 communication paths between a source and a destination.

9. The method according to claim 1, further comprising 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 method according to claim 1, further comprising determining a number of nodes in available communication paths, and preferentially select a communication path having a smaller number of nodes over a communication path having a larger number of nodes.

11. A mobile ad hoc network method, comprising:

automatically communicating wirelessly between a mobile ad hoc network node and a plurality of other mobile ad hoc network nodes through a wireless communication interface;

automatically maintaining, at the mobile ad hoc network node, a plurality of multicast trees defining alternate communication paths; and

automatically hosting and routing communications through the mobile ad hoc network, 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 communication paths are selected with increasing probability with an increasing reliability.

12. The mobile ad hoc network method according to claim 11, further comprising performing epidemic propagation of a number of available forwarding nodes in order to define the alternate communication paths.

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

14. The mobile ad hoc network 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 alternate communication paths under current mobility conditions of the mobile ad hoc network.

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

16. The mobile ad hoc network 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 mobile ad hoc network method according to claim 11, further comprising selecting 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 communication paths between a source and a destination.

18. The mobile ad hoc network method according to claim 11, further comprising determining a cost of employing a respective mobile 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 mobile ad hoc network method according to claim 11, further comprising determining a number of nodes in available communications paths, and preferentially selecting a communication path having a smaller number of nodes over a communication path having a larger number of nodes.

20. A method for communicating through a mobile ad hoc network, comprising:

providing a mobile ad hoc network node having an automated wireless communication interface configured to support at least communications with a plurality of other mobile nodes;

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

automatically selecting communications paths for communication through the mobile ad hoc network from the plurality of alternate communication paths, dependent on at least the multicast trees, a reliability metric and a communication data-overhead metric, wherein low data-overhead communication paths to a communication destination are selected with increasing probability with an increasing reliability of a respective communication path.