Weitere Kapitel dieses Buchs durch Wischen aufrufen
This chapter describes recent results addressing resource allocation problems in the context of current and future cellular technologies. We present models that capture several fundamental aspects of planning and operating these networks, and develop new approximation algorithms providing provable good solutions for the corresponding optimization problems. We mainly focus on two families of problems: cell planning and cell selection. Cell planning deals with choosing a network of base stations that can provide the required coverage of the service area with respect to the traffic requirements, available capacities, interference, and the desired QoS. Cell selection is the process of determining the cell(s) that provide service to each mobile station. Optimizing these processes is an important step towards maximizing the utilization of current and future cellular networks.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
A. Ageev and M. Sviridenko. Approximation algorithms for maximum coverage and max cut with given sizes of parts. In Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 1610 of Lecture Notes in Computer Science, pages 17–30. Springer-Verlag, 1999.
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows (Theory, Algorithms, and Applications). Prentice Hall, 1993.
D. Amzallag, R. Bar-Yehuda, D. Raz, and G. Scalosub. Cell Selection in 4G Cellular Networks. In Proceedings of the Annual IEEE 27th INFOCOM, pages 700–708, 2008.
D. Amzallag, R. Engelberg, J. Naor, and D. Raz. Cell planning of 4G cellular networks. Technical Report CS-2008-04, Computer Science Department, Technion - Israel Institute of Technology, 2008.
D. Amzallag, M. Livschitz, J. Naor, and D. Raz. Cell planning of 4G cellular networks: Algorithmic techniques, and results. In Proceedings of the 6th IEE International Conference on 3G & Beyond (3G’2005), pages 501–506, 2005.
D. Amzallag, J. Naor, and D. Raz. Coping with interference: From maximum coverage to planning cellular networks. In Proceedings of the 4th Workshop on Approximation and Online Algorithms (WAOA), volume 4368 of Lecture Notes in Computer Science. Springer-Verlag, 2006.
D. Amzallag, J. Naor, and D. Raz. Algorithmic aspects of radio access network design in B3G/4G cellular networks. In Proceedings of the Annual IEEE 26th INFOCOM, pages 991–999, 2007.
David Amzallag. Approximation Algorithms for Optimization Problems in Future Cellular Networks. PhD thesis, Department of Computer Science, Technion - Israel Institute of Technology, 2008.
M. Andrews and L. Zhang. Hardness of the undirected edge-disjoint path problem. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 276–283, 2005.
A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, and B. Schieber. A unified approach to approximating resource allocation and scheduling. In Proceedings of the 32th ACM Symposium on Theory of Computing (STOC), pages 735–744, 2000.
M. F. Cátedra and J. Pérez-Arriaga, editors. Cell Planning for Wireless Communications. Mobile Communications Series. Atrech House Publishers, Norwood, MA, 1999.
C. Chekuri, S. Khanna, and F. B. Shepherd. The all-or-nothing multicommodity flow problem. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pages 156–165, 2004.
C. Chekuri, S. Khanna, and F. B. Shepherd. Multicommodity flow, well-linked terminals, and routing problems. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 183–192, 2005.
J. Chuzhoy and J. Naor. Covering problems with hard capacities. In Proceedings of the 43th Annual IEEE Symposium on Foundations on Computer Science (FOCS), pages 481–489, 2002.
E. D. Demaine, U. Feige, M. Hajiaghayi, and M. R. Salavatipour. Combination can be hard: Approximability of the unique coverage problem. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 162–171, 2006.
U. Feige. Coping with NP-hardness of the graph bandwidth problem. In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT), pages 10–19, 2000.
L. Fleischer, M.X. Goemans, V.S. Mirrokni, and M. Sviridenko. Tight approximation algorithms for maximum general assignment problems. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 611–620, 2006.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., San Francisco, 1979. MATH
S. V. Hanly. An algorithm for combined cell-site selection and power control to maximize cellular spread spectrum capacity. IEEE Journal on Selected Areas in Communications, 13(7):1332–1340, 1995. CrossRef
S. Y. Hui and K. H. Yeung. Challenges in the migration to 4G mobile systems. IEEE Communications Magazine, 41:54–59, December 2003. CrossRef
N. Johnston and H. Aghvami. Comparing WiMAX and HSPA: A guide to the technology. BT Technology Journal (BTTJ), 25(2):191–199, 2007. CrossRef
Y. K. Kim and R. Prasad. 4G Roadmap and Emerging Communication Technologies. Artech House Publishers, Boston, MA, 2006.
M. J. Nawrocki, M. Dohler, and A. Hamid Aghvami, editors. Understanding UMTS Radio Network: Modelling, Planning and Automated Optimisation. John Wiley & Sons, Ltd., 2006.
B. Patt-Shamir, D. Rawitz, and G. Scalosub. Distributed approximation of cellular coverage. In Proceedings of the 12th International Conference on Principles of Distributed Systems (OPODIS), pp. 331–345, 2008.
A. Sang, X. Wang, M. Madihian, and R. D. Gitlin. A Load-aware handoff and cell-site selection scheme in multi-cell packet data systems. In Proceedings of the IEEE 47th Global Telecommunications Conference (GLOBECOM), volume 6, pages 3931–3936, 2004.
A. Sang, X. Wang, M. Madihian, and R. D. Gitlin. Coordinated load balancing, handoff/ cell-site selection, and scheduling in multi-cell packet data systems. In Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 302–314, 2004.
K. Tutschku. Demand-based radio network planning of cellular mobile communication systems. In Proceedings of the IEEE 17th INFOCOM, pages 1054–1061, 1998.
N. Umeda, T. Otsu, and T. Masamura. Overview of the fourth-generation mobile communication system. NTT DoCoMo Technical Review, 2(9):12–31, 2004. Available at http://www.ntt.co.jp/tr/0409/special.html.
J. Vygen. Approximation algorithms for facility location problems. Technical report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, 2005. Available at http://www.or.uni-bonn.de/~vygen/fl.pdf.
D. Wisely. Cellular mobile–the generation game. BT Technology Journal (BTTJ), 25(2):27–41, 2007. CrossRef
- Resource Allocation Algorithms for the Next Generation Cellular Networks
- Springer London
- Chapter 6
Neuer Inhalt/© ITandMEDIA, Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung/© astrosystem | stock.adobe.com