Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Design for Optimizability: Traffic Management of a Future Internet Read chapter Read first chapter

2010 | OriginalPaper | Chapter

6. Resource Allocation Algorithms for the Next Generation Cellular Networks

Authors : David Amzallag, Danny Raz

Published in: Algorithms for Next Generation Networks

Publisher: Springer London

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Cross-Layer Capacity Estimation and Throughput Maximization in Wireless Networks
next chapter Ethernet-Based Services for Next Generation Networks
Footnotes
1
We assume that the reader is familiar with the most well-known notions in cellular networks. An excellent introduction can be found in [36]
 
2
Notice that when planning cellular networks, the notion of “clients” sometimes means mobile stations and sometimes it represents the total traffic demand created by a cluster of mobile stations at a given location. In this chapter we support both forms of representations.
 
3
For simplicity, we do not consider here interference of higher order. These can be further derived and extended from our model.
 
4
The class ZPP is equal to the intersection of the computational complexity classes RP and Co-RP
 
Literature
1.
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.
2.
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows (Theory, Algorithms, and Applications). Prentice Hall, 1993.
3.
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.
4.
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.
5.
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.
6.
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.
7.
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.
8.
David Amzallag. Approximation Algorithms for Optimization Problems in Future Cellular Networks. PhD thesis, Department of Computer Science, Technion - Israel Institute of Technology, 2008.
9.
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.
10.
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.
11.
R. Bar-Yehuda. One for the price of two: A unified approach for approximating covering problems. Algorithmica, 27(2):131–144, 2000.MathSciNetMATHCrossRef
12.
M. F. Cátedra and J. Pérez-Arriaga, editors. Cell Planning for Wireless Communications. Mobile Communications Series. Atrech House Publishers, Norwood, MA, 1999.
13.
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.
14.
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.
15.
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.
16.
M. Dawande, J. Kalagnanam, P. Keskinocak, F.S. Salman, and R. Ravi. Approximation algorithms for the multiple knapsack problem with assignment restrictions. Journal of Combinatorial Optimization, 4(2):171–186, 2000.MathSciNetMATHCrossRef
17.
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.
18.
19.
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.
20.
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.
21.
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
22.
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
23.
S. Y. Hui and K. H. Yeung. Challenges in the migration to 4G mobile systems. IEEE Communications Magazine, 41:54–59, December 2003.CrossRef
24.
N. Johnston and H. Aghvami. Comparing WiMAX and HSPA: A guide to the technology. BT Technology Journal (BTTJ), 25(2):191–199, 2007.CrossRef
25.
26.
Y. K. Kim and R. Prasad. 4G Roadmap and Emerging Communication Technologies. Artech House Publishers, Boston, MA, 2006.
27.
R. Mathar and M. Schmeink. Optimal base station positioning and channel assignment for 3G mobile networks by integer programming. Annals of Operations Research, 107:225–236, 2002.MathSciNetCrossRef
28.
M. J. Nawrocki, M. Dohler, and A. Hamid Aghvami, editors. Understanding UMTS Radio Network: Modelling, Planning and Automated Optimisation. John Wiley & Sons, Ltd., 2006.
29.
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.
30.
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.
31.
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.
32.
M. Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint. Operations Research Letters, 32:41–43, 2004.MathSciNetMATHCrossRef
33.
K. Tutschku. Demand-based radio network planning of cellular mobile communication systems. In Proceedings of the IEEE 17th INFOCOM, pages 1054–1061, 1998.
34.
35.
36.
D. Wisely. Cellular mobile–the generation game. BT Technology Journal (BTTJ), 25(2):27–41, 2007.CrossRef
Metadata
Title
Resource Allocation Algorithms for the Next Generation Cellular Networks
Authors
David Amzallag
Danny Raz
Copyright Year
2010
Publisher
Springer London
Book
Algorithms for Next Generation Networks

Print ISBN: 978-1-84882-764-6

Electronic ISBN: 978-1-84882-765-3

Copyright Year: 2010

DOI
https://doi.org/10.1007/978-1-84882-765-3_6

Premium Partner

    Image Credits