Frequency Allocation Problems for Linear Cellular Networks

Joseph Wun Tat Chan; Francis Y.L. Chin; Deshi Ye; Yong Zhang; Hong Zhu

doi:10.1007/11940128_8

Frequency Allocation Problems for Linear Cellular Networks

Joseph Wun Tat Chan
, Francis Y.L. Chin
, Deshi Ye
, Yong Zhang
, Hong Zhu

School of Continuing Education

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

21 Citations (Scopus)

Abstract

We study the online frequency allocation problem for wireless linear (highway) cellular networks, where the geographical coverage area is divided into cells aligned in a line. Calls arrive over time and are served by assigning frequencies to them, and no two calls emanating from the same cell or neighboring cells are assigned the same frequency. The objective is to minimize the span of frequencies used.

In this paper we consider the problem with or without the assumption that calls have infinite duration. If there is the assumption, we propose an algorithm with absolute competitive ratio of 3/2 and asymptotic competitive ratio of 1.382. The lower bounds are also given: the absolute one is 3/2 and the asymptotic one is 4/3. Thus, our algorithm with absolute ratio of 3/2 is best possible. We also prove that the Greedy algorithm is 3/2-competitive in both the absolute and asymptotic cases. For the problem without the assumption, i.e. calls may terminate at arbitrary time, we give the lower bounds for the competitive ratios: the absolute one is 5/3 and the asymptotic one is 14/9. We propose an optimal online algorithm with both competitive ratio of 5/3, which is better than the Greedy algorithm, with both competitive ratios 2.

Original language	English
Title of host publication	Algorithms and Computation
Subtitle of host publication	17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings
Editors	Tetsuo Asano
Place of Publication	Heidelberg
Publisher	Springer Berlin Heidelberg
Pages	61-70
Number of pages	10
Edition	1st
ISBN (Electronic)	9783540496960
ISBN (Print)	3540496947, 9783540496946
DOIs	https://doi.org/10.1007/11940128_8
Publication status	Published - 30 Nov 2006
Event	17th International Symposium on Algorithms and Computation, ISAAC 2006 - Kolkata, India Duration: 18 Dec 2006 → 20 Dec 2006

Publication series

Name	Lecture Notes in Computer Science
Volume	4288
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	Theoretical Computer Science and General Issues
ISSN (Print)	2512-2010
ISSN (Electronic)	2512-2029

Name	ISAAC: International Symposium on Algorithms and Computation

Conference

Conference	17th International Symposium on Algorithms and Computation, ISAAC 2006
Country/Territory	India
City	Kolkata
Period	18/12/06 → 20/12/06

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

User-Defined Keywords

Neighboring Cell
Greedy Algorithm
Competitive Ratio
Online Algorithm
Greedy Approach

Access to Document

10.1007/11940128_8

Cite this

Chan, J. W. T., Chin, F. Y. L., Ye, D., Zhang, Y., & Zhu, H. (2006). Frequency Allocation Problems for Linear Cellular Networks. In T. Asano (Ed.), Algorithms and Computation: 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings (1st ed., pp. 61-70). (Lecture Notes in Computer Science; Vol. 4288), (Theoretical Computer Science and General Issues), (ISAAC: International Symposium on Algorithms and Computation). Springer Berlin Heidelberg. https://doi.org/10.1007/11940128_8

Chan, Joseph Wun Tat ; Chin, Francis Y.L. ; Ye, Deshi et al. / Frequency Allocation Problems for Linear Cellular Networks. Algorithms and Computation: 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings. editor / Tetsuo Asano. 1st. ed. Heidelberg : Springer Berlin Heidelberg, 2006. pp. 61-70 (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues). (ISAAC: International Symposium on Algorithms and Computation).

@inproceedings{bca8059578ec4961baf3cc608addfa0f,

title = "Frequency Allocation Problems for Linear Cellular Networks",

abstract = "We study the online frequency allocation problem for wireless linear (highway) cellular networks, where the geographical coverage area is divided into cells aligned in a line. Calls arrive over time and are served by assigning frequencies to them, and no two calls emanating from the same cell or neighboring cells are assigned the same frequency. The objective is to minimize the span of frequencies used.In this paper we consider the problem with or without the assumption that calls have infinite duration. If there is the assumption, we propose an algorithm with absolute competitive ratio of 3/2 and asymptotic competitive ratio of 1.382. The lower bounds are also given: the absolute one is 3/2 and the asymptotic one is 4/3. Thus, our algorithm with absolute ratio of 3/2 is best possible. We also prove that the Greedy algorithm is 3/2-competitive in both the absolute and asymptotic cases. For the problem without the assumption, i.e. calls may terminate at arbitrary time, we give the lower bounds for the competitive ratios: the absolute one is 5/3 and the asymptotic one is 14/9. We propose an optimal online algorithm with both competitive ratio of 5/3, which is better than the Greedy algorithm, with both competitive ratios 2.",

keywords = "Neighboring Cell, Greedy Algorithm, Competitive Ratio, Online Algorithm, Greedy Approach",

author = "Chan, \{Joseph Wun Tat\} and Chin, \{Francis Y.L.\} and Deshi Ye and Yong Zhang and Hong Zhu",

note = "This research is supported by an Hong Kong RGC Grant. Publisher copyright: {\textcopyright} 2006 Springer-Verlag Berlin Heidelberg; 17th International Symposium on Algorithms and Computation, ISAAC 2006 ; Conference date: 18-12-2006 Through 20-12-2006",

year = "2006",

month = nov,

day = "30",

doi = "10.1007/11940128\_8",

language = "English",

isbn = "3540496947",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "61--70",

editor = "Tetsuo Asano",

booktitle = "Algorithms and Computation",

edition = "1st",

}

Chan, JWT, Chin, FYL, Ye, D, Zhang, Y & Zhu, H 2006, Frequency Allocation Problems for Linear Cellular Networks. in T Asano (ed.), Algorithms and Computation: 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings. 1st edn, Lecture Notes in Computer Science, vol. 4288, Theoretical Computer Science and General Issues, ISAAC: International Symposium on Algorithms and Computation, Springer Berlin Heidelberg, Heidelberg, pp. 61-70, 17th International Symposium on Algorithms and Computation, ISAAC 2006, Kolkata, India, 18/12/06. https://doi.org/10.1007/11940128_8

Frequency Allocation Problems for Linear Cellular Networks. / Chan, Joseph Wun Tat; Chin, Francis Y.L.; Ye, Deshi et al.
Algorithms and Computation: 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings. ed. / Tetsuo Asano. 1st. ed. Heidelberg: Springer Berlin Heidelberg, 2006. p. 61-70 (Lecture Notes in Computer Science; Vol. 4288), (Theoretical Computer Science and General Issues), (ISAAC: International Symposium on Algorithms and Computation).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Frequency Allocation Problems for Linear Cellular Networks

AU - Chan, Joseph Wun Tat

AU - Chin, Francis Y.L.

AU - Ye, Deshi

AU - Zhang, Yong

AU - Zhu, Hong

PY - 2006/11/30

Y1 - 2006/11/30

N2 - We study the online frequency allocation problem for wireless linear (highway) cellular networks, where the geographical coverage area is divided into cells aligned in a line. Calls arrive over time and are served by assigning frequencies to them, and no two calls emanating from the same cell or neighboring cells are assigned the same frequency. The objective is to minimize the span of frequencies used.In this paper we consider the problem with or without the assumption that calls have infinite duration. If there is the assumption, we propose an algorithm with absolute competitive ratio of 3/2 and asymptotic competitive ratio of 1.382. The lower bounds are also given: the absolute one is 3/2 and the asymptotic one is 4/3. Thus, our algorithm with absolute ratio of 3/2 is best possible. We also prove that the Greedy algorithm is 3/2-competitive in both the absolute and asymptotic cases. For the problem without the assumption, i.e. calls may terminate at arbitrary time, we give the lower bounds for the competitive ratios: the absolute one is 5/3 and the asymptotic one is 14/9. We propose an optimal online algorithm with both competitive ratio of 5/3, which is better than the Greedy algorithm, with both competitive ratios 2.

AB - We study the online frequency allocation problem for wireless linear (highway) cellular networks, where the geographical coverage area is divided into cells aligned in a line. Calls arrive over time and are served by assigning frequencies to them, and no two calls emanating from the same cell or neighboring cells are assigned the same frequency. The objective is to minimize the span of frequencies used.In this paper we consider the problem with or without the assumption that calls have infinite duration. If there is the assumption, we propose an algorithm with absolute competitive ratio of 3/2 and asymptotic competitive ratio of 1.382. The lower bounds are also given: the absolute one is 3/2 and the asymptotic one is 4/3. Thus, our algorithm with absolute ratio of 3/2 is best possible. We also prove that the Greedy algorithm is 3/2-competitive in both the absolute and asymptotic cases. For the problem without the assumption, i.e. calls may terminate at arbitrary time, we give the lower bounds for the competitive ratios: the absolute one is 5/3 and the asymptotic one is 14/9. We propose an optimal online algorithm with both competitive ratio of 5/3, which is better than the Greedy algorithm, with both competitive ratios 2.

KW - Neighboring Cell

KW - Greedy Algorithm

KW - Competitive Ratio

KW - Online Algorithm

KW - Greedy Approach

UR - https://www.scopus.com/pages/publications/77249095123

U2 - 10.1007/11940128_8

DO - 10.1007/11940128_8

M3 - Conference proceeding

AN - SCOPUS:77249095123

SN - 3540496947

SN - 9783540496946

T3 - Lecture Notes in Computer Science

SP - 61

EP - 70

BT - Algorithms and Computation

A2 - Asano, Tetsuo

PB - Springer Berlin Heidelberg

CY - Heidelberg

T2 - 17th International Symposium on Algorithms and Computation, ISAAC 2006

Y2 - 18 December 2006 through 20 December 2006

ER -

Chan JWT, Chin FYL, Ye D, Zhang Y, Zhu H. Frequency Allocation Problems for Linear Cellular Networks. In Asano T, editor, Algorithms and Computation: 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings. 1st ed. Heidelberg: Springer Berlin Heidelberg. 2006. p. 61-70. (Lecture Notes in Computer Science). (Theoretical Computer Science and General Issues). (ISAAC: International Symposium on Algorithms and Computation). doi: 10.1007/11940128_8

Frequency Allocation Problems for Linear Cellular Networks

Abstract

Publication series

Conference

UN SDGs

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this