Name
Title | ||
|---|---|---|
Dual Decomposition for Computational Optimization of Minimum-Power Shared Broadcast Tree in Wireless Networks |
Abstract | ||
|---|---|---|
We consider the problem of constructing a shared broadcast tree (SBT) in wireless networks, such that the total power required for supporting broadcast initiated by all source nodes is minimal. In the well-studied minimum-energy broadcast (MEB) problem, the optimal tree varies by source. In contrast, SBT is source-independent, thus substantially reducing the overhead for information storage and processing. The SBT problem also differs from the range assignment problem (RAP), because the power for message forwarding in SBT, although being source-independent, depends on from which tree neighbor the message is received. We approach SBT from a computational optimization standpoint, and present a dual decomposition method applied to an optimization model that embeds multiple directed trees into a shared tree. For the dual decomposition method, some of the constraints in the model are preferably formulated implicitly. The dual decomposition scheme is coupled with a fast local search algorithm. We report computational results demonstrating the effectiveness of the proposed approach. In average, the performance gap to global optimality is less than three percent. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/TMC.2011.231 | IEEE Trans. Mob. Comput. |
Keywords | Field | DocType |
optimisation,information storage,range assignment problem,message forwarding power,discrete optimization,rap,tree neighbor,minimum-power shared broadcast tree,shared tree,shared broadcast tree,dual decomposition,optimal tree,sbt problem,dual decomposition scheme,well-studied minimum-energy broadcast,wireless networks,radio networks,meb problem,broadcast communication,dual decomposition method,information processing,multiple directed trees,computational optimization standpoint,local search algorithm,minimum-energy broadcast problem,computational optimization,optimization,broadcasting,computational modeling,mathematical model,mathematical programming | Wireless network,Broadcasting,Computer science,Discrete optimization,Computational optimization,Computer network,Decomposition method (constraint satisfaction),Assignment problem,Local search (optimization),Broadcast communication network,Distributed computing | Journal |
Volume | Issue | ISSN |
11 | 12 | 1536-1233 |
Citations | PageRank | References |
2 | 0.40 | 30 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Di Yuan | 1 | 41 | 6.94 |
| Dag Haugland | 2 | 151 | 15.18 |