An enhanced simulated annealing algorithm for solving the cell assignment problem of the two-level wireless ATM network

Der-Rong Din, S. S. Tseng

Research output: Contribution to journalArticle

Abstract

In this paper, we investigate the problem of optimum assignment of cells in PCS (Personal Communication Service) to switches in an ATM (Asynchronous Transfer Mode) network. Given cells and switches in an ATM network (whose locations are fixed and known), the problem is grouping cells into clusters and assigning these clusters in an optimum manner. This problem is termed as cell assignment problem and modeled as a complex integer programming problem, and finding an optimal solution to this problem is NP-complete. Owing to the inability of simulated annealing (SA) to generate solutions that always satisfy all the constraints, the performance of a traditional-SA approach is not so promising. The SA technique is, however, easy to implement, requires little expert knowledge and is not memory intensive. Hence, in this paper, we attempt to develop an enhanced-SA approach for solving the cell assignment problem. The enhanced-SA constructs constraint-satisfying configurations and perturbation mechanism to ensure that the candidate configurations produced are feasible and satisfy all the constraints. The performance of the enhanced-SA algorithm is demonstrated through simulation. The result of the study is also compared with previous reported solution methods.

Original languageEnglish
Pages (from-to)111-125
Number of pages15
JournalEngineering Intelligent Systems
Volume12
Issue number2
Publication statusPublished - 2004 Jun 1

Fingerprint

Asynchronous transfer mode
Simulated annealing
Switches
Personal communication systems
Integer programming
Computational complexity
Data storage equipment

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this

@article{4fec67bb65384e87ae11168355921666,
title = "An enhanced simulated annealing algorithm for solving the cell assignment problem of the two-level wireless ATM network",
abstract = "In this paper, we investigate the problem of optimum assignment of cells in PCS (Personal Communication Service) to switches in an ATM (Asynchronous Transfer Mode) network. Given cells and switches in an ATM network (whose locations are fixed and known), the problem is grouping cells into clusters and assigning these clusters in an optimum manner. This problem is termed as cell assignment problem and modeled as a complex integer programming problem, and finding an optimal solution to this problem is NP-complete. Owing to the inability of simulated annealing (SA) to generate solutions that always satisfy all the constraints, the performance of a traditional-SA approach is not so promising. The SA technique is, however, easy to implement, requires little expert knowledge and is not memory intensive. Hence, in this paper, we attempt to develop an enhanced-SA approach for solving the cell assignment problem. The enhanced-SA constructs constraint-satisfying configurations and perturbation mechanism to ensure that the candidate configurations produced are feasible and satisfy all the constraints. The performance of the enhanced-SA algorithm is demonstrated through simulation. The result of the study is also compared with previous reported solution methods.",
author = "Der-Rong Din and Tseng, {S. S.}",
year = "2004",
month = "6",
day = "1",
language = "English",
volume = "12",
pages = "111--125",
journal = "International Journal of Engineering Intelligent Systems for Electrical Engineering and Communications",
issn = "0969-1170",
publisher = "CRL Publishing",
number = "2",

}

An enhanced simulated annealing algorithm for solving the cell assignment problem of the two-level wireless ATM network. / Din, Der-Rong; Tseng, S. S.

In: Engineering Intelligent Systems, Vol. 12, No. 2, 01.06.2004, p. 111-125.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An enhanced simulated annealing algorithm for solving the cell assignment problem of the two-level wireless ATM network

AU - Din, Der-Rong

AU - Tseng, S. S.

PY - 2004/6/1

Y1 - 2004/6/1

N2 - In this paper, we investigate the problem of optimum assignment of cells in PCS (Personal Communication Service) to switches in an ATM (Asynchronous Transfer Mode) network. Given cells and switches in an ATM network (whose locations are fixed and known), the problem is grouping cells into clusters and assigning these clusters in an optimum manner. This problem is termed as cell assignment problem and modeled as a complex integer programming problem, and finding an optimal solution to this problem is NP-complete. Owing to the inability of simulated annealing (SA) to generate solutions that always satisfy all the constraints, the performance of a traditional-SA approach is not so promising. The SA technique is, however, easy to implement, requires little expert knowledge and is not memory intensive. Hence, in this paper, we attempt to develop an enhanced-SA approach for solving the cell assignment problem. The enhanced-SA constructs constraint-satisfying configurations and perturbation mechanism to ensure that the candidate configurations produced are feasible and satisfy all the constraints. The performance of the enhanced-SA algorithm is demonstrated through simulation. The result of the study is also compared with previous reported solution methods.

AB - In this paper, we investigate the problem of optimum assignment of cells in PCS (Personal Communication Service) to switches in an ATM (Asynchronous Transfer Mode) network. Given cells and switches in an ATM network (whose locations are fixed and known), the problem is grouping cells into clusters and assigning these clusters in an optimum manner. This problem is termed as cell assignment problem and modeled as a complex integer programming problem, and finding an optimal solution to this problem is NP-complete. Owing to the inability of simulated annealing (SA) to generate solutions that always satisfy all the constraints, the performance of a traditional-SA approach is not so promising. The SA technique is, however, easy to implement, requires little expert knowledge and is not memory intensive. Hence, in this paper, we attempt to develop an enhanced-SA approach for solving the cell assignment problem. The enhanced-SA constructs constraint-satisfying configurations and perturbation mechanism to ensure that the candidate configurations produced are feasible and satisfy all the constraints. The performance of the enhanced-SA algorithm is demonstrated through simulation. The result of the study is also compared with previous reported solution methods.

UR - http://www.scopus.com/inward/record.url?scp=4344607739&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4344607739&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:4344607739

VL - 12

SP - 111

EP - 125

JO - International Journal of Engineering Intelligent Systems for Electrical Engineering and Communications

JF - International Journal of Engineering Intelligent Systems for Electrical Engineering and Communications

SN - 0969-1170

IS - 2

ER -