Hybrid Method for Solving Dual-Homing Cell Assignment Problem on Two-Level Wireless ATM Network

Der-Rong DIN  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.7   pp.1664-1671
Publication Date: 2004/07/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Multi-dimensional Mobile Information Networks)
Category: Network Theory
Keyword: 
NP-hard,  wireless ATM,  cell assignment,  dual-homing,  simulated annealing,  heuristic algorithm,  

Full Text: PDF(327KB)>>
Buy this Article




Summary: 
In this paper, the optimal assignment problem which assigns cells in PCS (Personal Communication Service) to switches on ATM (Asynchronous Transfer Mode) network is investigated. The cost considered in this paper has two components: one is the cost of handoff that involves two switches, and the other is the cost of cabling. This problem assumes that each cell in PCS can be assigned to two switches in ATM network. This problem is modelled as dual-homing cell assignment problem, which is a complex integral linear programming (ILP) problem. Since finding an optimal solution of this problem is NP-hard, a hybrid method which combines several heuristics and a stochastic search method (based on a simulated annealing(SA) approach) is proposed to solve this problem. The solution method consists of three phases: Primary Assignment Decision Phase (PADP), Secondary Assignment Decision Phase (SADP) and Refinement Phase (RP). The PADP and SADP are used to find good initial assignment, then domain-dependent heuristics are encoded into perturbations of SA in Refinement Phase to improve the result. Simulation results show that the proposed hybrid method is robust for this problem.