A heuristic algorithm for solving the network expanded problem on wireless ATM environment

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, the network expanded problem (NEP) which optimally assigns new adding and splitting cells in PCS (Personal Communication Service) network to switches in an ATM (Asynchronous Transfer Mode) network is studied. In NEP, the locations of all cells (or Base Station, BS) in PCS network are fixed and known, but new switches should be installed to ATM network and the topology of the backbone network may be changed. Given some potential sites of new switches, the problem is to determine how many switches should be added to the backbone network, the locations of new switches, the topology of the new backbone network, and the assignments of new adding and splitting cells in the PCS to switches on the new ATM backbone network in an optimum manner. The goal is to do the expansion in as attempt to minimize the total communication cost under budget and capacity constraints. The NEP is modeled as a complex integer programming problem and finding an optimal solution to this problem is NP-hard. A heuristic algorithm is proposed to solve this problem. The proposed heuristic algorithm consists of four phases: Remaining Capacities Pre-assigning Phase (RCPP), Cell Clustering Phase (CCP), Switch Selection Phase (SSP), and Backbone Design Phase (BDP). Experimental results indicate that the proposed algorithm can find good solution.

Original languageEnglish
Title of host publicationComputational Science and Its Applications - ICCSA 2007 - International Conference, Proceedings
Pages846-859
Number of pages14
EditionPART 1
Publication statusPublished - 2007 Dec 1
EventInternational Conference on Computational Science and its Applications, ICCSA 2007 - Kuala Lumpur, Malaysia
Duration: 2007 Aug 262007 Aug 29

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume4705 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherInternational Conference on Computational Science and its Applications, ICCSA 2007
CountryMalaysia
CityKuala Lumpur
Period07-08-2607-08-29

Fingerprint

Asynchronous transfer mode
Heuristic algorithms
Heuristic algorithm
Communication
Switches
Switch
Personal communication systems
Backbone
Budgets
Cluster Analysis
Topology
Cell
Costs and Cost Analysis
Integer programming
Heuristics
Transfer (Psychology)
Base stations
Computational complexity
Budget Constraint
Capacity Constraints

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Din, D. R. (2007). A heuristic algorithm for solving the network expanded problem on wireless ATM environment. In Computational Science and Its Applications - ICCSA 2007 - International Conference, Proceedings (PART 1 ed., pp. 846-859). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4705 LNCS, No. PART 1).
Din, Der Rong. / A heuristic algorithm for solving the network expanded problem on wireless ATM environment. Computational Science and Its Applications - ICCSA 2007 - International Conference, Proceedings. PART 1. ed. 2007. pp. 846-859 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).
@inproceedings{e40929935c02430ba695d64f7a468503,
title = "A heuristic algorithm for solving the network expanded problem on wireless ATM environment",
abstract = "In this paper, the network expanded problem (NEP) which optimally assigns new adding and splitting cells in PCS (Personal Communication Service) network to switches in an ATM (Asynchronous Transfer Mode) network is studied. In NEP, the locations of all cells (or Base Station, BS) in PCS network are fixed and known, but new switches should be installed to ATM network and the topology of the backbone network may be changed. Given some potential sites of new switches, the problem is to determine how many switches should be added to the backbone network, the locations of new switches, the topology of the new backbone network, and the assignments of new adding and splitting cells in the PCS to switches on the new ATM backbone network in an optimum manner. The goal is to do the expansion in as attempt to minimize the total communication cost under budget and capacity constraints. The NEP is modeled as a complex integer programming problem and finding an optimal solution to this problem is NP-hard. A heuristic algorithm is proposed to solve this problem. The proposed heuristic algorithm consists of four phases: Remaining Capacities Pre-assigning Phase (RCPP), Cell Clustering Phase (CCP), Switch Selection Phase (SSP), and Backbone Design Phase (BDP). Experimental results indicate that the proposed algorithm can find good solution.",
author = "Din, {Der Rong}",
year = "2007",
month = "12",
day = "1",
language = "English",
isbn = "9783540744689",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
number = "PART 1",
pages = "846--859",
booktitle = "Computational Science and Its Applications - ICCSA 2007 - International Conference, Proceedings",
edition = "PART 1",

}

Din, DR 2007, A heuristic algorithm for solving the network expanded problem on wireless ATM environment. in Computational Science and Its Applications - ICCSA 2007 - International Conference, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 4705 LNCS, pp. 846-859, International Conference on Computational Science and its Applications, ICCSA 2007, Kuala Lumpur, Malaysia, 07-08-26.

A heuristic algorithm for solving the network expanded problem on wireless ATM environment. / Din, Der Rong.

Computational Science and Its Applications - ICCSA 2007 - International Conference, Proceedings. PART 1. ed. 2007. p. 846-859 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4705 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - A heuristic algorithm for solving the network expanded problem on wireless ATM environment

AU - Din, Der Rong

PY - 2007/12/1

Y1 - 2007/12/1

N2 - In this paper, the network expanded problem (NEP) which optimally assigns new adding and splitting cells in PCS (Personal Communication Service) network to switches in an ATM (Asynchronous Transfer Mode) network is studied. In NEP, the locations of all cells (or Base Station, BS) in PCS network are fixed and known, but new switches should be installed to ATM network and the topology of the backbone network may be changed. Given some potential sites of new switches, the problem is to determine how many switches should be added to the backbone network, the locations of new switches, the topology of the new backbone network, and the assignments of new adding and splitting cells in the PCS to switches on the new ATM backbone network in an optimum manner. The goal is to do the expansion in as attempt to minimize the total communication cost under budget and capacity constraints. The NEP is modeled as a complex integer programming problem and finding an optimal solution to this problem is NP-hard. A heuristic algorithm is proposed to solve this problem. The proposed heuristic algorithm consists of four phases: Remaining Capacities Pre-assigning Phase (RCPP), Cell Clustering Phase (CCP), Switch Selection Phase (SSP), and Backbone Design Phase (BDP). Experimental results indicate that the proposed algorithm can find good solution.

AB - In this paper, the network expanded problem (NEP) which optimally assigns new adding and splitting cells in PCS (Personal Communication Service) network to switches in an ATM (Asynchronous Transfer Mode) network is studied. In NEP, the locations of all cells (or Base Station, BS) in PCS network are fixed and known, but new switches should be installed to ATM network and the topology of the backbone network may be changed. Given some potential sites of new switches, the problem is to determine how many switches should be added to the backbone network, the locations of new switches, the topology of the new backbone network, and the assignments of new adding and splitting cells in the PCS to switches on the new ATM backbone network in an optimum manner. The goal is to do the expansion in as attempt to minimize the total communication cost under budget and capacity constraints. The NEP is modeled as a complex integer programming problem and finding an optimal solution to this problem is NP-hard. A heuristic algorithm is proposed to solve this problem. The proposed heuristic algorithm consists of four phases: Remaining Capacities Pre-assigning Phase (RCPP), Cell Clustering Phase (CCP), Switch Selection Phase (SSP), and Backbone Design Phase (BDP). Experimental results indicate that the proposed algorithm can find good solution.

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

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

M3 - Conference contribution

AN - SCOPUS:38049079230

SN - 9783540744689

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 846

EP - 859

BT - Computational Science and Its Applications - ICCSA 2007 - International Conference, Proceedings

ER -

Din DR. A heuristic algorithm for solving the network expanded problem on wireless ATM environment. In Computational Science and Its Applications - ICCSA 2007 - International Conference, Proceedings. PART 1 ed. 2007. p. 846-859. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).