MINIMIZING OVERLAP IN TREE-BASED MULTIPOINT COMMUNICATION
Multicasting is applied on many kinds of networks, such as the Internet, mobile ad hoc networks, sensor networks, and so forth. In this thesis we consider the problem of computing multicast trees for multiple multicast groups that minimizes interference/overlap between different multicast groups. We model this problem using graph theory as follows: represent the network topology with a graph G = (V, E), the ith group with the set of vertices Ri V, the source/center node of the multicast with the vertex si Î Ri. In addition we restrict the vertex set of the multicast tree for the ith group to the set Wi Ê Ri. The minimum overlap multicast tree problem is to find a set of multicast trees rooted at , respectively, such that Ri Í V(Ti) Í Wi, that minimizes the total overlap, . We show the latter problem is NP-hard, even for unicasting, i.e., |Ri| = 2,i = 1,…,k. However, we solve the problem in the special case when Ri = Wi, i = 1,…,k, and present an efficient heuristic algorithm for solving the general problem. This heuristic algorithm involves first computing a shortest-path dag Di for each multicast group i, from which an initial set of trees are computed using either a random or greedy method, then pruning the trees and applying a local optimization routine to these pruned trees, and finally pruning the trees generated by the local optimization routine. Further, we design a simulator – Multicast Tree Analyzer (MTA) to simulate this heuristic algorithm for random and ad hoc graphs. The experiments involved computing total overlap for many difference graphs and comparing the greedy choice of initial trees to the random choice. We observed that before applying the local optimization routine the greedy choice of initial trees outperformed (in terms of minimizing with respect to the overlap measure) the random choice of initial trees. However, after performing the local optimization routine they performed about the same. In addition to total overlap we also look at minimizing the maximum overlap and the 2-nom value of load vector.
School:University of Cincinnati
School Location:USA - Ohio
Source Type:Master's Thesis
Keywords:multicast tree overlap interference
Date of Publication:01/01/2005