Skip to main content
SpringerLink
Log in

A Constant-Competitive Algorithm for Online OVSF Code Assignment

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Orthogonal Variable Spreading Factor (OVSF) code assignment is a fundamental problem in Wideband Code-Division Multiple-Access (W-CDMA) systems, which plays an important role in third generation mobile communications. In the OVSF problem, codes must be assigned to incoming call requests with different data rate requirements, in such a way that they are mutually orthogonal with respect to an OVSF code tree. An OVSF code tree is a complete binary tree in which each node represents a code associated with the combined bandwidths of its two children. To be mutually orthogonal, each leaf-to-root path must contain at most one assigned code. In this paper, we focus on the online version of the OVSF code assignment problem and give a 10-competitive algorithm (where the cost is measured by the total number of assignments and reassignments used). Our algorithm improves the previous O(h)-competitive result, where h is the height of the code tree, and also another recent constant-competitive result, where the competitive ratio is only constant under amortized analysis and the constant is not determined. We also improve the lower bound of the problem from 3/2 to 5/3.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Chan, W.T., Chin, F.Y.L., Ye, D., Zhang, Y., Zhu, H.: Frequency allocation problem for linear cellular networks. In: Proceedings of the 17th Annual International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 4288, pp. 61–70. Springer, Berlin (2006)

    Google Scholar 

  2. Chan, W.T., Chin, F.Y.L., Ye, D., Zhang, Y., Zhu, H.: Greedy online frequency allocation in cellular networks. Inf. Process. Lett. 102(2–3), 55–61 (2007)

    Article  MathSciNet  Google Scholar 

  3. Chan, W.T., Chin, F.Y.L., Ye, D., Zhang, Y., Zhu, H.: Online frequency allocation in cellular networks. In: Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 241–249 (2007)

  4. Chin, F.Y.L., Zhang, Y., Zhu, H.: Online OVSF code assignment in cellular networks. In: Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science, vol. 4508, pp. 191–200. Springer, Berlin (2007)

    Chapter  Google Scholar 

  5. Caragiannis, I., Kaklamanis, C., Papaioannou, E.: Efficient on-line frequency allocation and call control in cellular networks. Theory Comput. Syst. 35(5), 521–543 (2002). A preliminary version of the paper appeared in SPAA 2000

    Article  MATH  MathSciNet  Google Scholar 

  6. Erlebach, T., Jacob, R., Mihalak, M., Nunkesser, M., Szabo, G., Widmayer, P.: An algorithmic view on OVSF code assignment. Algorithmica 47, 269–298 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  7. Forišek, M., Katreniak, B., Katreniaková, J., Královič, R., Královič, R., Koutný, V., Pardubská, D., Plachetka, T., Rovan, B.: Online bandwidth allocation. In: Proceedings of the 16th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 4698, pp. 546–557. Springer, Berlin (2007)

    Google Scholar 

  8. Li, X.Y., Wan, P.J.: Theoretically good distributed CDMA/OVSF code assignment for wireless ad hoc networks. In: Proceedings of the 11th Annual International Conference of Computing and Combinatorics, pp. 126–135 (2005)

  9. McDiarmid, C., Reed, B.A.: Channel assignment and weighted coloring. Networks 36(2), 114–117 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  10. Minn, T., Siu, K.Y.: Dynamic assignment of orthogonal variable-spreading factor codes in W-CDMA. IEEE J. Sel. Areas Commun. 18(8), 1429–1440 (2000)

    Article  Google Scholar 

  11. Rouskas, A.N., Skoutas, D.N.: OVSF codes assignment and reassignment at the forward link W-CDMA 3G systems. In: Proceedings of the 13th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications

  12. Tomamichel, M.: Algorithmische Aspekte von OVSF Code Assignment mit Schwerpunkt auf Offline Code Assignment. Student thesis at ETH Zürich (2004)

  13. Wan, P.J., Li, X.Y., Frieder, O.: OVSF-CDMA code assignment in wireless ad hoc networks. In: Proceedings of DIAL M-POMC 2004 Joint Workshop on Foundations of Mobile Computing, pp. 92–101 (2004)

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, The University of Hong Kong, Pokfulam road, Hong Kong, Hong Kong

    F. Y. L. Chin, H. F. Ting & Y. Zhang

Authors
  1. F. Y. L. Chin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. H. F. Ting
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Y. Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to H. F. Ting.

Additional information

The research of F.Y.L. Chin was supported by HK RGC grant HKU-7113/07E.

The research of H.F. Ting was supported by HK RGC grant HKU-7045/02E.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chin, F.Y.L., Ting, H.F. & Zhang, Y. A Constant-Competitive Algorithm for Online OVSF Code Assignment. Algorithmica 56, 89–104 (2010). https://doi.org/10.1007/s00453-008-9241-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-008-9241-8

Keywords

Search

Navigation