caa a22 4500 606190007 CHVBK 20210128100853.0 cr unu---uuuuu 210128e20150901xx s 000 0 eng 10.1007/s10776-015-0272-1 doi (NATIONALLICENCE)springer-10.1007/s10776-015-0272-1 Minimizing Expected Transmissions Multicast in Wireless Multihop Networks [Elektronische Daten] [Kostas Christodoulopoulos, Christos Papageorgiou, Emmanouel Varvarigos] 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. Springer Science+Business Media New York, 2015 Wireless multihop networks nationallicence Multicasting nationallicence Wireless broadcast advantage nationallicence Wireless unreliable transmission nationallicence Graph transformation nationallicence Christodoulopoulos Kostas Department of Computer Engineering and Informatics, University of Patras, Patras, Greece aut Papageorgiou Christos Department of Computer Engineering and Informatics, University of Patras, Patras, Greece aut Varvarigos Emmanouel Department of Computer Engineering and Informatics, University of Patras, Patras, Greece aut International Journal of Wireless Information Networks Springer US; http://www.springer-ny.com 22/3(2015-09-01), 205-219 1068-9605 22:3<205 2015 22 10776 https://doi.org/10.1007/s10776-015-0272-1 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10776-015-0272-1 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Christodoulopoulos Kostas Department of Computer Engineering and Informatics, University of Patras, Patras, Greece aut NATIONALLICENCE 700 1- Papageorgiou Christos Department of Computer Engineering and Informatics, University of Patras, Patras, Greece aut NATIONALLICENCE 700 1- Varvarigos Emmanouel Department of Computer Engineering and Informatics, University of Patras, Patras, Greece aut NATIONALLICENCE 773 0- International Journal of Wireless Information Networks Springer US; http://www.springer-ny.com 22/3(2015-09-01), 205-219 1068-9605 22:3<205 2015 22 10776