A combinatorial approximation algorithm for CDMA downlink rate allocation

Richardus J. Boucherie, A.F. Bumb, A.I. Endrayanto, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

61 Downloads (Pure)

Abstract

This paper presents a combinatorial algorithm for downlink rate allocation in Code Division Multiple Access (CDMA) mobile networks. By discretizing the coverage area into small segments, the transmit power requirements are characterized via a matrix representation that separates user and system characteristics. We obtain a closed-form analytical expression for the so-called Perron-Frobenius eigenvalue of that matrix, which provides a quick assessment of the feasibility of the power assignment for a given downlink rate allocation. Based on the Perron-Frobenius eigenvalue, we reduce the downlink rate allocation problem to a set of multiple-choice knapsack problems. The solution of these problems provides an approximation of the optimal downlink rate allocation and cell borders for which the system throughput, expressed in terms of utility functions of the users, is maximized.
Original languageEnglish
Title of host publicationTelecommunications Planning: Innovations in pricing, network design and management
EditorsS. Raghavan, G. Anandalingam
Place of PublicationBerlin
PublisherSpringer
Pages275-293
Number of pages19
ISBN (Print)978-0-387-29222-9
DOIs
Publication statusPublished - 2006

Publication series

NameOperations Research/Computer Science Interfaces
PublisherSpringer
Volume33
ISSN (Print)1387-666X

Fingerprint

Approximation algorithms
Code division multiple access
Wireless networks
Throughput

Keywords

  • CDMA
  • IR-69807
  • Knapsack
  • EWI-16538
  • Multiple-choice
  • Downlink rate allocation
  • Approximation scheme
  • Feasibility transmit power

Cite this

Boucherie, R. J., Bumb, A. F., Endrayanto, A. I., & Woeginger, G. (2006). A combinatorial approximation algorithm for CDMA downlink rate allocation. In S. Raghavan, & G. Anandalingam (Eds.), Telecommunications Planning: Innovations in pricing, network design and management (pp. 275-293). (Operations Research/Computer Science Interfaces; Vol. 33). Berlin: Springer. https://doi.org/10.1007/0-387-29234-9_14
Boucherie, Richardus J. ; Bumb, A.F. ; Endrayanto, A.I. ; Woeginger, Gerhard. / A combinatorial approximation algorithm for CDMA downlink rate allocation. Telecommunications Planning: Innovations in pricing, network design and management. editor / S. Raghavan ; G. Anandalingam. Berlin : Springer, 2006. pp. 275-293 (Operations Research/Computer Science Interfaces).
@inbook{fe4458f202dd4bed8706ad1ed88f4041,
title = "A combinatorial approximation algorithm for CDMA downlink rate allocation",
abstract = "This paper presents a combinatorial algorithm for downlink rate allocation in Code Division Multiple Access (CDMA) mobile networks. By discretizing the coverage area into small segments, the transmit power requirements are characterized via a matrix representation that separates user and system characteristics. We obtain a closed-form analytical expression for the so-called Perron-Frobenius eigenvalue of that matrix, which provides a quick assessment of the feasibility of the power assignment for a given downlink rate allocation. Based on the Perron-Frobenius eigenvalue, we reduce the downlink rate allocation problem to a set of multiple-choice knapsack problems. The solution of these problems provides an approximation of the optimal downlink rate allocation and cell borders for which the system throughput, expressed in terms of utility functions of the users, is maximized.",
keywords = "CDMA, IR-69807, Knapsack, EWI-16538, Multiple-choice, Downlink rate allocation, Approximation scheme, Feasibility transmit power",
author = "Boucherie, {Richardus J.} and A.F. Bumb and A.I. Endrayanto and Gerhard Woeginger",
year = "2006",
doi = "10.1007/0-387-29234-9_14",
language = "English",
isbn = "978-0-387-29222-9",
series = "Operations Research/Computer Science Interfaces",
publisher = "Springer",
pages = "275--293",
editor = "S. Raghavan and G. Anandalingam",
booktitle = "Telecommunications Planning: Innovations in pricing, network design and management",

}

Boucherie, RJ, Bumb, AF, Endrayanto, AI & Woeginger, G 2006, A combinatorial approximation algorithm for CDMA downlink rate allocation. in S Raghavan & G Anandalingam (eds), Telecommunications Planning: Innovations in pricing, network design and management. Operations Research/Computer Science Interfaces, vol. 33, Springer, Berlin, pp. 275-293. https://doi.org/10.1007/0-387-29234-9_14

A combinatorial approximation algorithm for CDMA downlink rate allocation. / Boucherie, Richardus J.; Bumb, A.F.; Endrayanto, A.I.; Woeginger, Gerhard.

Telecommunications Planning: Innovations in pricing, network design and management. ed. / S. Raghavan; G. Anandalingam. Berlin : Springer, 2006. p. 275-293 (Operations Research/Computer Science Interfaces; Vol. 33).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - A combinatorial approximation algorithm for CDMA downlink rate allocation

AU - Boucherie, Richardus J.

AU - Bumb, A.F.

AU - Endrayanto, A.I.

AU - Woeginger, Gerhard

PY - 2006

Y1 - 2006

N2 - This paper presents a combinatorial algorithm for downlink rate allocation in Code Division Multiple Access (CDMA) mobile networks. By discretizing the coverage area into small segments, the transmit power requirements are characterized via a matrix representation that separates user and system characteristics. We obtain a closed-form analytical expression for the so-called Perron-Frobenius eigenvalue of that matrix, which provides a quick assessment of the feasibility of the power assignment for a given downlink rate allocation. Based on the Perron-Frobenius eigenvalue, we reduce the downlink rate allocation problem to a set of multiple-choice knapsack problems. The solution of these problems provides an approximation of the optimal downlink rate allocation and cell borders for which the system throughput, expressed in terms of utility functions of the users, is maximized.

AB - This paper presents a combinatorial algorithm for downlink rate allocation in Code Division Multiple Access (CDMA) mobile networks. By discretizing the coverage area into small segments, the transmit power requirements are characterized via a matrix representation that separates user and system characteristics. We obtain a closed-form analytical expression for the so-called Perron-Frobenius eigenvalue of that matrix, which provides a quick assessment of the feasibility of the power assignment for a given downlink rate allocation. Based on the Perron-Frobenius eigenvalue, we reduce the downlink rate allocation problem to a set of multiple-choice knapsack problems. The solution of these problems provides an approximation of the optimal downlink rate allocation and cell borders for which the system throughput, expressed in terms of utility functions of the users, is maximized.

KW - CDMA

KW - IR-69807

KW - Knapsack

KW - EWI-16538

KW - Multiple-choice

KW - Downlink rate allocation

KW - Approximation scheme

KW - Feasibility transmit power

U2 - 10.1007/0-387-29234-9_14

DO - 10.1007/0-387-29234-9_14

M3 - Chapter

SN - 978-0-387-29222-9

T3 - Operations Research/Computer Science Interfaces

SP - 275

EP - 293

BT - Telecommunications Planning: Innovations in pricing, network design and management

A2 - Raghavan, S.

A2 - Anandalingam, G.

PB - Springer

CY - Berlin

ER -

Boucherie RJ, Bumb AF, Endrayanto AI, Woeginger G. A combinatorial approximation algorithm for CDMA downlink rate allocation. In Raghavan S, Anandalingam G, editors, Telecommunications Planning: Innovations in pricing, network design and management. Berlin: Springer. 2006. p. 275-293. (Operations Research/Computer Science Interfaces). https://doi.org/10.1007/0-387-29234-9_14