The search functionality is under construction.

The search functionality is under construction.

For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (*CAP*). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (*channel span*) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (*QCAP*). To solve hard CAP instances in reasonable time, QCAP evolutes *quasi-solution states* where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.977-987

- Publication Date
- 2002/05/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Nobuo FUNABIKI, Toru NAKANISHI, Tokumi YOKOHIRA, Shigeto TAJIMA, Teruo HIGASHINO, "A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 977-987, May 2002, doi: .

Abstract: For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (*CAP*). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (*channel span*) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (*QCAP*). To solve hard CAP instances in reasonable time, QCAP evolutes *quasi-solution states* where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_977/_p

Copy

@ARTICLE{e85-a_5_977,

author={Nobuo FUNABIKI, Toru NAKANISHI, Tokumi YOKOHIRA, Shigeto TAJIMA, Teruo HIGASHINO, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks},

year={2002},

volume={E85-A},

number={5},

pages={977-987},

abstract={For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (*CAP*). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (*channel span*) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (*QCAP*). To solve hard CAP instances in reasonable time, QCAP evolutes *quasi-solution states* where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.},

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

TI - A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 977

EP - 987

AU - Nobuo FUNABIKI

AU - Toru NAKANISHI

AU - Tokumi YOKOHIRA

AU - Shigeto TAJIMA

AU - Teruo HIGASHINO

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E85-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 2002

AB - For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (*CAP*). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (*channel span*) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (*QCAP*). To solve hard CAP instances in reasonable time, QCAP evolutes *quasi-solution states* where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.

ER -