Browsing by Author "Din, DR"

Now showing 1 - 7 of 7

A genetic algorithm for solving dual-homing cell assignment problem of the two-level wireless ATM network
(2002-11-01)
Din, DR
;
Tseng, SS
;
資訊工程學系
;
Department of Computer Science
In this paper, we investigate the optimal assignment problem, which assigns cells in Personal Communication Service to switches on Asynchronous Transfer Mode network in an optimum manner. The cost has two components: one is the cost of handoffs that involve two switches, and the other is the cost of cabling. This problem is model as dual-homing cell assignment problem, which is a complex integer programming problem. Since finding an optimal solution of this problem is NP-hard, a stochastic search method, based on a genetic approach, is proposed to solve this problem. In this paper, domain-dependent heuristics are encoded into crossover operations, mutations of genetic algorithm (GA) to solve this problem. Simulation results show that GA is robust for this problem. (C) 2002 Elsevier Science B.V. All rights reserved.
A simulated annealing algorithm for extended cell assignment problem in a wireless ATM network
(2001)
Din, DR
;
Tseng, SS
;
資訊工程學系
;
Department of Computer Science
In this paper, we investigate the extended cell assignment problem which optimally assigns new adding and splitting cells in PCS (Personal Communication Service) to switches in a wireless ATM (Asynchronous Transfer Mode) network. Given cells in a PCS and switches on an ATM network (whose locations are fixed and known), we would like to do the assignment in an attempt to minimize a cost criterion. The cost has two components: one is the cost of handoffs that involve two switches, and the other is the cost of cabling. This problem is modeled as a complex integer programming problem, and finding an optimal solution to this problem is NP-hard. A simulated annealing algorithm are proposed to solve this problem. The simulated annealing algorithm, ESA (enhanced simulated annealing), generates constraint-satisfy configurations, and uses three configuration perturbation schemes to change current configuration to a new one. Experimental results indicate that ESA algorithm has good performances.
A solution model of integrating cells of PCS to switches in wireless ATM network
(2002-08-01)
Din, DR
;
Tseng, SS
;
資訊工程學系
;
Department of Computer Science
In this paper, we investigate the optimal assignment problem of cells in PCS (Personal Communication Service) to switches on a ATM (Asynchronous Transfer Mode) network. Given cells and switches on an ATM network (whose locations are fixed and known), the problem is to group cells into clusters and assign these clusters to switches in an optimum manner. This problem is modeled as a complex integer programming problem. Since finding an optimal solution of this problem is NP-hard, a heuristic solution model consists of three phases (Cell Pre-Partitioning Phase, Cell Exchanging Phase, and Cell Migrating Phase) is proposed. Experimental results show that Cell Exchanging and Cell Migrating Phases can really reduce total cost near 44% on average.
An enhanced simulated annealing algorithm for solving the cell assignment problem of the twolevel wireless ATM network
(2004-06-01)
Din, DR
;
Tseng, SS
;
資訊工程學系
;
Department of Computer Science
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.
Genetic algorithm for extended cell assignment problem in wireless ATM network
(2000)
Din, DR
;
Tseng, SS
;
Jiang, MF
;
資訊工程學系
;
Department of Computer Science
In this paper, we investigate the extended cell assignment problem which optimally assigns new and split cells in PCS (Personal Communication Service) to switches in a wireless ATM network. Given cells and switches in an ATM network (whose locations are fixed and known), the problem is assigning cells to switches in an optimum manner. We would like to do the assignment in as attempt to minimize a cost criterion. The cost has two components: one is the cost of handoffs that involve two switches, and the other is the cost of cabling. This problem is modeled as a complex integer programming problem and finding an optimal solution to this problem is NP-complete. A stochastic search method, based on a genetic approach is proposed to solve this problem. Simulation results show that genetic algorithm is robust for this problem.
Heuristic algorithm for optimal design of the two-level wireless ATM network
(2001-07-01)
Din, DR
;
Tseng, SS
;
資訊工程學系
;
Department of Computer Science
In this paper, we investigate the optimal assignment problem of cells in PCS (Personal Communication Service) to switches in a wireless ATM network. Given cells and switches on an ATM network (whose locations are fixed and known), the problem is grouping cells into clusters and assigning these clusters to the switches in an optimum manner. This problem is modeled as a complex integer programming problem and finding an optimal solution of this problem is NP-complete. A three-phase heuristic algorithm MCMLCF (Maximum cell and minimum local communication first) consisting of Cell Pre-Partitioning Phase, Cell Exchanging Phase, and Cell Migrating Phase, is proposed. First, in the Cell Pre-Partitioning Phase, a three-step procedure (Clustering Step, Packing Step, and Assigning Step) is proposed to group cells into clusters. Second, Cell Exchanging Phase, is proposed to greatly improve the result by repeatedly exchanging two cells in different switches. Finally, Cell Migrating Phase is proposed to reduce cost by repeatedly migrating all cells in a used switch to an empty switch. Experimental results indicate that the proposed algorithm runs efficiently. Comparing the results of the algorithm to a naive heuristic called NSF, we have shown that the computation time is reduced by 30.1%. Experimental results show that Cell Exchanging and Cell Migrating phases can reduce the total cost by 34.1% on average. By comparing the results of the proposed algorithm to the genetic algorithm, the heuristic method came close to optimum - on average within 5%.
Heuristic and simulated annealing algorithms for solving extended cell assignment problem in wireless ATM networks
(2002-02-01)
Din, DR
;
Tseng, SS
;
資訊工程學系
;
Department of Computer Science
In this paper, we investigate the extended cell assignment problem which optimally assigns new adding and splitting cells in Personal Communication Service (PCS) to switches in a wireless Asynchronous Transfer Mode (ATM) network. Given cells in a PCS network and switches on an ATM network (whose locations are fixed and known), we would like to do the assignment in an attempt to minimize a cost criterion. The cost has two components: one is the cost of handoffs that involve two switches, and the other is the cost of cabling. This problem is modeled as a complex integer programming problem, and finding an optimal solution to this problem is NP-hard. A heuristic algorithm and a simulated annealing algorithm are proposed to solve this problem. The heuristic algorithm, Extended Assignment Algorithm (EEA), consists of two phases, initial assigning phase and cell exchanging phase. First, in the initial assigning phase, the initial assignments of cells to switches are found. Then, these assignments are improved by performing cell exchanging phase in which two cells are repeatedly exchanged in different switches with great reduction of the total cost. The simulated annealing algorithm, ESA (enhanced simulated annealing), generates constraint-satisfied configurations, and uses three configuration perturbation schemes to change current configuration to a new one. Experimental results indicate that EAA and ESA algorithms have good performances. Copyright (C) 2002 John Wiley Sons, Ltd.