טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMichal Wermuth
SubjectBroadcasting Methods for Mobile Ad-Hoc Networks
DepartmentDepartment of Electrical Engineering
Supervisor Full Professor Orda Ariel


Abstract

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-MCDSk is the minimum CDS through which the route between any node uÎV and its 2-hop neighbor vÎN2(u) is of length at most k. We prove that the RRL-MCDS problem is NP-complete even for k=2 and that the routes through RRL-CDSk are of length at most k times the original routes. We also provide some centralized polynomial approximations for RRL-MCDSk. The approximations can be computed by any of the CDS nodes once the CDS is constructed.

Next, we propose the MPR4 algorithm, which potentially reduces the size of the broadcast set in Qayyum et al.'s MPR algorithm. The MPR4 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. MPR4 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.