Ph.D Thesis

Ph.D StudentAmzallag David
SubjectApproximation Algorithms For Optimization Problems
in Future Cellular Networks
DepartmentDepartment of Computer Science
Supervisors PROF. Joseph Naor
PROF. Dan Raz
Full Thesis textFull thesis text - English Version


The main goal of this research is to develop new approaches specifically addressing several fundamental optimization problems associated with the upcoming future cellular networks. This research rigorously studies algorithmic aspects of these optimization problems, incorporates the anticipated future new technologies into the studied framework, and presents new methods for solving these problems. Our new techniques are based on novel modeling of technology dependent characterizations and using approximation algorithms in order to provide provable good solutions. In addition, methods presented in this work are also applicable to various current network radio technologies.

We start by studying the problem of planning future cellular networks. In general, cell planning includes choosing a network of base stations that can provide the required coverage of the service area with respect to current and future traffic requirements, available capacities, interference, and the desired QoS. We rigorously study both the budget limited cell planning problem and the minimum-cost cell planning problem.

Next we address a challenging problem that arises in the design of a new topology for radio access network (RAN) for future cellular networks. In this problem we study algorithmic aspects of replacing the commonly used star based architecture, in which a Radio Network Controller (RNC) is connected to a set of base stations via direct links, with a more complex tree structure, in which a base station can be connected to an RNC via other base stations.

Finally, motivated by algorithmic characterizations of the new OFDMA multiple access technique standard (as defined by the IEEE 802.16e--2005), we design a new approach for the cell selection mechanism. Cell selection is the process of determining the cells that provide service to each mobile station. Optimizing these processes is an important step towards maximizing the utilization of current and future cellular networks.

In this thesis, we provide the first approximation algorithms for all of the above problems. Our results indicate that a theoretical study together with optimized practical implementations outperform previous commonly used techniques, and achieve a close-to-optimal solutions on real cellular networks.