Minimum-Energy Broadcast and Multicast in Wireless Networks: An Integer Programming Approach and Improved Heuristic Algorithms
2008 (English)In: Ad hoc networks, ISSN 1570-8705, Vol. 6, no 5, 696-717 p.Article in journal (Refereed) Published
Both integer programming models and heuristic algorithms have been proposed for finding minimum-energy broadcast and multicast trees in wireless ad hoc networks. Among heuristic algorithms, the broadcast/multicast incremental power (BIP/MIP) algorithm is most known. The theoretical performance of BIP/MIP has been quantified in several studies. To assess the empirical performance of BIP/MIP and other heuristic algorithms, it is necessary to compute an optimal tree or a very good lower bound of the optimum. In this paper, we present an integer programming approach as well as improved heuristic algorithms. Our integer programming approach comprises a novel integer model and a relaxation scheme. Unlike previously proposed models, the continuous relaxation of our model leads to a very sharp lower bound of the optimum. Our relaxation scheme allows for performance evaluation of heuristics without having to compute optimal trees. Our contributions to heuristic algorithms consist of the power-improving algorithm successive power adjustment (SPA), and improved time complexity of some previously suggested algorithms. We report extensive numerical experiments. Algorithm SPA finds better solutions in comparison to a host of other algorithms. Moreover, the integer programming approach shows that trees found by algorithm SPA are optimal or near-optimal.
Place, publisher, year, edition, pages
Institutionen för teknik och naturvetenskap , 2008. Vol. 6, no 5, 696-717 p.
Algorithm, Broadcast, Integer programming, Lagrangean relaxation, Minimum-energy, Multicast, Performance evaluation, Wireless networks
National CategoryEngineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-11903DOI: 10.1016/j.adhoc.2007.06.006OAI: oai:DiVA.org:liu-11903DiVA: diva2:18295
Original publication: Di Yuan, Joanna Bauer and Dag Haugland, Minimum-Energy Broadcast and Multicast in Wireless Networks: An Integer Programming Approach and Improved Heuristic Algorithms, 2008, Ad Hoc Networks, (6), 5, 696-717. http://dx.doi.org/10.1016/j.adhoc.2007.06.006. Copyright: Elsevier B.V., http://www.elsevier.com/2008-05-232008-05-232012-06-25