Minimizing expected transmissions multicast in wireless multihop networks

We address the multicast problem in a wireless multihop network in the presence of errors. Finding the multicast schedule that minimizes the expected number of transmissions, while accounting for both the wireless broadcast advantage (WBA) and the wireless unreliable transmission (WUT) characteristics, has not been solved optimally before. We formally define the problem and propose an initial algorithm of non-polynomial complexity to obtain the optimal solution. The algorithm starts by transforming the wireless network topology into an auxiliary expanded graph that captures the WBA property, and assigning appropriate weights to the links so as to capture the WUT property. The proposed transformation is interesting on its own merit, since it permits us to consider only point-to-point transmissions (as in wireline networks) in the expanded graph, instead of the point-to-multipoint transmissions present in the original wireless network, and can also be useful in other optimization problems some of which we briefly describe. By solving the minimum Steiner tree problem on the expanded graph we obtain the optimal multicast solution for the initial graph. Since the optimal algorithm is of non-polynomial complexity, we also propose a number of heuristic algorithms. In particular, we first present a truncated graph transformation and then describe two heuristic algorithms for obtaining the multicast schedule. Simulation results show that the proposed heuristics have performance close to that of the optimal algorithm, at least for the instances for which we were able to track optimal solutions, while outperforming other heuristic multicast algorithms.