Minimizing expected transmissions multicast in wireless multihop networks

Kostas Christodoulopoulos, Christos Papageorgiou, Emmanouel Varvarigos

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)205-219
Number of pages15
JournalInternational Journal of Wireless Information Networks
Volume22
Issue number3
DOIs
Publication statusPublished - Sep 2015
Externally publishedYes

Keywords

  • Graph transformation
  • Multicasting
  • Wireless broadcast advantage
  • Wireless multihop networks
  • Wireless unreliable transmission

Cite this