TY - GEN
T1 - Energy-efficient network routing with discrete cost functions
AU - Wang, Lin
AU - Fernández Anta, Antonio
AU - Zhang, Fa
AU - Hou, Chenying
AU - Liu, Zhiyong
PY - 2012
Y1 - 2012
N2 - Energy consumption is an important issue in the design and use of networks. In this paper, we explore energy savings in networks via a rate adaptation model. This model can be represented by a cost-minimization network routing problem with discrete cost functions. We formulate this problem as an integer program, which is proved to be NP-hard. Then a constant approximation algorithm is developed. In our proposed method, we first transform the program into a continuous-cost network routing problem, and then we approximate the optimal solution by a two-step rounding process. We show by analysis that, for uniform demands, our method provides a constant approximation for the uniform network routing problem with discrete costs. A bicriteria network routing problem is also developed so that a trade-off can be made between energy consumption and network delay. Analytical results for this latter model are also presented.
AB - Energy consumption is an important issue in the design and use of networks. In this paper, we explore energy savings in networks via a rate adaptation model. This model can be represented by a cost-minimization network routing problem with discrete cost functions. We formulate this problem as an integer program, which is proved to be NP-hard. Then a constant approximation algorithm is developed. In our proposed method, we first transform the program into a continuous-cost network routing problem, and then we approximate the optimal solution by a two-step rounding process. We show by analysis that, for uniform demands, our method provides a constant approximation for the uniform network routing problem with discrete costs. A bicriteria network routing problem is also developed so that a trade-off can be made between energy consumption and network delay. Analytical results for this latter model are also presented.
KW - approximation
KW - network optimization
KW - network routing
UR - http://www.scopus.com/inward/record.url?scp=84860993904&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-29952-0_32
DO - 10.1007/978-3-642-29952-0_32
M3 - Conference contribution
AN - SCOPUS:84860993904
SN - 9783642299513
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 307
EP - 318
BT - Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Proceedings
T2 - 9th Annual Conference on Theory and Applications of Models of Computation, TAMC 2012
Y2 - 16 May 2012 through 21 May 2012
ER -
