Mathematical Modeling in Industry - A Workshop for Graduate Student, May 26-June 3, 2002

Mobility Management in Cellular Telephony

David Shallcross
Telcordia Technology

We will look at a problem arising in the operation of cellular telephone systems. A mobile station (i.e. cell phone) communicates directly with the Base Transceiver Station (BTS) for the cell it occupies. Several BTSs are associated with a single Base Station Controller (BSC). In turn, several BSCs are associated with a single Mobile Switching Center (MSC). If a mobile station moves from one cell to another, work must be done by the BTSs, BSCs, and possibly the MSCs, for the old and new cells. This amount of work will vary depending on whether the two cells use the same BSC, or even the same MSC. Given an estimate of this handover traffic, we would like to avoid overloading the BSCs and MSCs. To this end we may reassign BTSs among the BSCs at the same MSC.

This problem may be formulated as a variant of the Quadratic Assignment Problem (QAP), a well-known NP-hard problem. We will investigate applying modifications of methods for the QAP to this cell phone problem. I intend for the students to implement and test one such method of their choosing. I hope to provide something like realistic data for this.

Students should have some experience with optimization, and implementing optimization algorithms.

References:

For the technology: Understanding Cellular Radio, William Webb, Artech House, 1998

A general introduction: Combinatorial Optimization, Cook, Cunningham, Schrijver, + Pulleyblank, John Wiley and Sons, 1998

One possible class of methods:
Tabu Search, F. Glover + M. Laguna, Kluwer Academic Publishers, 1997

One model:
Quadratic Assignment and Related Problems, Pardalos + Wolkowicz, eds., DIMACS vol 16, American Methematical Society, 1994

Also see the QAPLIB home page: http://www.opt.math.tu-graz.ac.at/qaplib/.

 

Industrial Programs