Search: onr:"swepub:oai:DiVA.org:liu-11903" >
Minimum-Energy Broa...
Minimum-Energy Broadcast and Multicast in Wireless Networks: An Integer Programming Approach and Improved Heuristic Algorithms
-
- Yuan, Di (author)
- Linköpings universitet,Tekniska högskolan,Kommunikations- och transportsystem
-
- Bauer, Joanna (author)
- University of Bergen, Bergen, Norway
-
- Haugland, Dag (author)
- University of Bergen, Bergen, Norway
-
(creator_code:org_t)
- Institutionen för teknik och naturvetenskap, 2008
- 2008
- English.
-
In: Ad hoc networks. - : Institutionen för teknik och naturvetenskap. - 1570-8705 .- 1570-8713. ; 6:5, s. 696-717
- Related links:
-
https://liu.diva-por... (primary) (Raw object)
-
show more...
-
http://liu.diva-port...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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.
Keyword
- Algorithm
- Broadcast
- Integer programming
- Lagrangean relaxation
- Minimum-energy
- Multicast
- Performance evaluation
- Wireless networks
- TECHNOLOGY
- TEKNIKVETENSKAP
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database