Resource Allocation in Cellular Networks with Coexisting Femtocells and Macrocells

Over the last decade, cellular networks have grown rapidly from circuit-switch-based voice-only networks to IP-based data-dominant networks, embracing not only traditional mobile phones, but also smartphones and mobile computers. The ever-increasing demands for reliable and high-speed data services have challenged the capacity and coverage of cellular networks. Research and development on femtocells seeks to provide a solution to fill coverage holes and to increase the network capacity to accommodate more mobile terminals and applications that requires higher bandwidth.

Among the challenges associated with introducing femtocells in existing cellular networks, interference management and resource allocation are critical. In this dissertation, we address fundamental aspects of resource allocation for cellular networks with coexisting femtocells and macrocells on the downlink side, addressing questions such as: How many additional resource blocks are required to add femtocells into the current cellular system? What is the best way to reuse resources between femtocells and macrocells? How can we efficiently assign limited resources to network users?

In this dissertation, we develop an analytical model of resource allocation based on random graphs. In this model, arbitrarily chosen communication links interfere with each other with a certain probability. Using this model, we establish asymptotic bounds on the minimum number of resource blocks required to make interference-free resource assignments for all the users in the network. We assess these bounds using a simple greedy resource allocation algorithm to demonstrate that the bounds are reasonable in finite networks of plausible size. By applying the bounds, we establish the expected impact of femtocell networks on macrocell resource allocation under a variety of interference scenarios.

We proceed to compare two reuse schemes, termed shared reuse and split reuse, using three social welfare functions, denoted utilitarian fitness, egalitarian fitness, and proportionally fair fitness. The optimal resource split points, which separate resource access by femtocells and macrocells, are derived with respect to the above fitness functions. A set of simple greedy resource allocation algorithms are developed to verify our analysis and compare fitness values of the two reuse schemes under various network scenarios. We use the obtained results to assess the efficiency loss associated with split reuse, as an aid to determining whether resource allocators should use the simpler split reuse scheme or attempt to tackle the complexity and overhead associated with shared reuse.

Due to the complexity of the proportionally fair fitness function, optimal resource allocation for cellular networks with femtocells and macrocells is difficult to obtain. We develop a genetic algorithm-based centralized resource allocation algorithm to yield suboptimal solutions for such a problem. The results from the genetic algorithm are used to further assess the performance loss of split reuse and provide a baseline suboptimal resource allocation. Two distributed algorithms are then proposed to give a practical solution to the resource allocation problem. One algorithm is designed for a case with no communications between base stations and another is designed to exploit the sharing of information between base stations. The numerical results from these distributed algorithms are then compared against to the ones obtained by the genetic algorithm and the performance is found to be satisfactory, typically falling within 8% of the optimum social welfare found via the genetic algorithm. The capability of the distributed algorithms in adapting to network changes is also assessed and the results are promising.

All of the work described thus far is carried out under a protocol model in which interference between two links is a binary condition. Though this model makes the problem more analytically tractable, it lacks the ability to reflect additive interference as in the SINR model. Thus, in the final part of our work, we apply conflict-free resource allocations from our distributed algorithms to simulated networks and examine the allocations under the SINR model to evaluate feasibility. This evaluation study confirms that the protocol-model-based algorithms, with a small adjustment, offer reasonable performance even under the more realistic SINR model.

This work was supported by the National Institute of Justice, Office of Justice Programs, U.S. Department of Justice under Award No. 2005-IJ-CX-K017 and the National Science Foundation under Grant No. 0448131. Any opinions, findings, and conclusions or recommendations expressed in this dissertation are those of the author and do not necessarily reflect the views of the National Institute of Justice or the National Science Foundation. The NSF/TEKES Wireless Research Exchange Program also contributed to this work by funding a summer study.