Abstract
We address the call control problem in wireless cellular networks that utilize Frequency Division Multiplexing (FDM) technology. In such networks, many users within the same geographical region (cell) can communicate simultaneously with other users of the network using distinct frequencies. The available frequency spectrum is limited; hence, its management should be done efficiently. The objective of the call control problem is, given a spectrum of available frequencies and users that wish to communicate in a cellular network, to maximize the number of users that communicate without signal interference. We study the online version of the problem in cellular networks using competitive analysis and present new upper and lower bounds.
This work was partially funded by the European Union under the IST FET Project CRESCCO.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Awerbuch, B., Azar, Y., Fiat, A., Leonardi, S., Rosen, A.: Competitive On–line Competitive Algorithms for Call Admission in Optical Networks. Algorithmica 31(1), 29–43 (2001)
Awerbuch, B., Bartal, Y., Fiat, A., Rosen, A.: Competitive Non–Preemptive Call Control. In: Proc. of the 5th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 1994), pp. 312–320 (1994)
Bartal, Y., Fiat, A., Leonardi, S.: Lower Bounds for On–line Graph Problems with Applications to On–line Circuit and Optical Routing. In: Proc. of the 28th Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 531–540 (1996)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
Caragiannis, I., Kaklamanis, C., Papaioannou, E.: Efficient On–Line Frequency Allocation and Call Control in Cellular Networks. In: Theory of Computing Systems, vol. 35, pp. 521–543 (2002); Preliminary versions in SPAA 2000 and IPDPS 2001
Caragiannis, I., Kaklamanis, C., Papaioannou, E.: Simple On-line Algorithms for Call Control in Cellular Networks. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 67–80. Springer, Heidelberg (2004)
Erlebach, T., Jansen, K.: The Maximum Edge-Disjoint Paths Problem in Bidirected Trees. SIAM Journal on Discrete Mathematics 14(3), 326–355 (2001)
Hale, W.K.: Frequency Assignment: Theory and Applications. Proc. of the IEEE 68(12), 1497–1514 (1980)
Janssen, J., Krizanc, D., Narayanan, L., Shende, S.: Distributed On–Line Frequency Assignment in Cellular Networks. Journal of Algorithms 36(2), 119–151 (2000)
Leonardi, S., Marchetti–Spaccamela, A., Prescuitti, A., Rosen, A.: On–line Randomized Call–Control Revisited. SIAM Journal on Computing 31(1), 86–112 (2001)
Motwani, R., Raghavan, B.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Pantziou, G., Pentaris, G., Spirakis, P.: Competitive Call Control in Mobile Networks. Theory of Computing Systems 35(6), 625–639 (2002)
Wan, P.-J., Liu, L.: Maximal Throughput in Wavelength-Routed Optical Networks. In: Multichannel Optical Networks: Theory and Practice. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 46, pp. 15–26. AMS, Providence (1998)
Yao, A.C.: Probabilistic Computations: Towards a Unified Measure of Complexity. In: Proc. of the 17th Annual Symposium on Foundations of Computer Science (FOCS 1977), pp. 222–227 (1977)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Caragiannis, I., Kaklamanis, C., Papaioannou, E. (2005). New Bounds on the Competitiveness of Randomized Online Call Control in Cellular Networks. In: Cunha, J.C., Medeiros, P.D. (eds) Euro-Par 2005 Parallel Processing. Euro-Par 2005. Lecture Notes in Computer Science, vol 3648. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11549468_119
Download citation
DOI: https://doi.org/10.1007/11549468_119
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28700-1
Online ISBN: 978-3-540-31925-2
eBook Packages: Computer ScienceComputer Science (R0)