Throughput Optimization in Mobile Backbone Networks
Authors:
Open Access
- 14 October 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Mobile Computing
- Vol. 10 (4) , 560-572
Abstract
This paper describes new algorithms for throughput optimization in a mobile backbone network. This hierarchical communication framework combines mobile backbone nodes, which have superior mobility and communication capability, with regular nodes, which are constrained in mobility and communication capability. An important quantity of interest in mobile backbone networks is the number of regular nodes that can be successfully assigned to mobile backbone nodes at a given throughput level. This paper develops a novel technique for maximizing this quantity in networks of fixed regular nodes using mixed-integer linear programming (MILP). The MILP-based algorithm provides a significant reduction in computation time compared to existing methods and is computationally tractable for problems of moderate size. An approximation algorithm is also developed that is appropriate for large-scale problems. This paper presents a theoretical performance guarantee for the approximation algorithm and also demonstrates its empirical performance. Finally, the mobile backbone network problem is extended to include mobile regular nodes, and exact and approximate solution algorithms are presented for this extension.Keywords
This publication has 24 references indexed in Scilit:
- Valid inequalities for mixed integer linear programsMathematical Programming, 2007
- Radio planning and coverage optimization of 3G cellular networksWireless Networks, 2007
- The complexity of base station positioning in cellular networksDiscrete Applied Mathematics, 2005
- Sequencing-by-hybridization revisited: the analog-spectrum proposalIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004
- Landmark routing in ad hoc networks with mobile backbonesJournal of Parallel and Distributed Computing, 2003
- Efficient algorithms for geometric optimizationACM Computing Surveys, 1998
- Integrated power control and base station assignmentIEEE Transactions on Vehicular Technology, 1995
- An algorithm for combined cell-site selection and power control to maximize cellular spread spectrum capacityIEEE Journal on Selected Areas in Communications, 1995
- A simple distributed autonomous power control algorithm and its convergenceIEEE Transactions on Vehicular Technology, 1993
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms1981