Previous 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


Journal of Information Science and Engineering, Vol. 24 No. 2, pp. 483-501 (March 2008)

Heuristic and Simulated Annealing Algorithms for Wireless ATM Backbone Network Design Problem*

Der-Rong Din
Department of Computer Science and Information Engineering
National Changhua University of Education
Changhua City, 500 Taiwan

Personal Communication Network (PCN) is an emerging wireless network that promises many new services for the telecommunication industry. The high speed backbone network (asynchronous transfer mode, ATM or wavelength division multiplexing, WDM) is one possible approach to provide broadband wireless transmission with PCNs using the ATM switches for interconnection of PCN cells. The wireless ATM backbone network design (WABND) problem is to allocate backbone links among ATM switches such that the effects of terminal mobility on the performance of ATM-based PCNs can be reduced. In this paper, the WABND problem is formulated and studied. The goal of the WABND is to minimize the location update cost under constraints. Since WABND is an NP-hard problem, two heuristic algorithms and a simulated annealing algorithm were proposed and used to find the close-to-optimal solutions. The simulated annealing algorithm was able to achieve good performance as indicated from the simulated results.

Keywords: wireless ATM, heuristic algorithm, simulated annealing, NP-hard, backbone network design

Full Text () Retrieve PDF document (200803_11.pdf)

Received February 14, 2006; revised September 14, 2006; accepted January 3, 2007.
Communicated by Yu-Chee Tseng.
*This work was supported in part by the National Science Council of Taiwan, R.O.C. under grants No. NSC 95-2221-E-018-012 and NSC 96-2221- E-018-007.