M.Sc Student | Wermuth Michal |
---|---|

Subject | Broadcasting Methods for Mobile Ad-Hoc Networks |

Department | Department of Electrical Engineering |

Supervisor | Professor Ariel Orda |

A Mobile Ad hoc Network (MANET) is a wireless network consisting of mobile nodes, without any pre-determined infrastructure or central entity. The ability to perform broadcasting is a critical building block useful in various network applications. One of the most efficient broadcasting mechanisms is to restrict the flooding to a small Connected Dominating Set (CDS) of nodes.

We present two distributed deterministic algorithms to construct a small CDS in MANETs, namely HTree (Hierarchical Tree) and PTree (Pseudo Tree). Both algorithms are able to stabilize in presence of topology changes, and their time complexity depends on the size of the output CDS rather than on the total number of nodes in the network. As a result, in most of the cases, both algorithms are much more efficient than Das et al.'s algorithm, which is the best known distributed MCDS approximation for general graphs. The proven approximation bounds on the size of the output CDS (with respect to the size of the MCDS) of HTree and PTree are only slightly higher than the approximation bound of Das et al.'s algorithm, and simulation results confirm that the actual differences are negligible.

As MANETs usually suffer from high packet error rate, it is
desirable that the routes between nodes through the CDS will be as short as
possible. In this context, we define the RRL-MCDS problem. Given a parameter
*k*, the RRL-MCDS_{k} is the minimum CDS through
which the route between any node *
uÎV
*and its 2-hop
neighbor *vÎN ^{2}*(

Next, we propose the MPR_{4} algorithm, which
potentially reduces the size of the broadcast set in Qayyum et al.'s MPR
algorithm. The MPR_{4} algorithm is based on relaxing of the
requirement that the MPR set of every node is a subset of its neighbors.
Instead, we allow the MPR set of every node to consist of nodes up to 3 hops
from it. MPR_{4}
is local, and requires 3-hops
topology information (rather than 2-hops required by the MPR algorithm).
Finally, we propose a Load-Balancing heuristics to mitigate the effect of
bottlenecks in the MPR algorithm.