On least expected transmissions multicasting in wireless networks

In this paper we propose an optimal algorithm for the problem of least expected transmissions multicasting in wireless networks. The algorithm starts by transforming the network graph into an expanded graph that captures the wireless broadcast advantage (WBA) while simplifying point-to-multi-point transmissions in the original graph into point-to-point transmissions in the auxiliary expanded graph. Using an appropriate function to calculate the weights of the expanded graph links we also capture the wireless unreliable transmission (WUT) characteristics of the wireless medium. By solving the minimum Steiner tree problem on the expanded graph we obtain the optimal solution of the initial problem. Since the optimal algorithm is of non-polynomial complexity, we proceed to propose a heuristic algorithm. 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.