Dynamic Resource Allocation in Wireless Heterogeneous Networks

Deployment of low power basestations within cellular networks can potentially increase both capacity and coverage. However, such deployments require efficient resource allocation schemes for managing interference from the low power and macro basestations that are located within each other’s transmission range. In this dissertation, we propose novel and efficient dynamic resource allocation algorithms in the frequency, time and space domains. We show that the proposed algorithms perform better than the current state-of-art resource management algorithms. In the first part of the dissertation, we propose an interference management solution in the frequency domain. We introduce a distributed frequency allocation scheme that shares frequencies between macro and low power pico basestations, and guarantees a minimum average throughput to users. The scheme seeks to minimize the total number of frequencies needed to honor the minimum throughput requirements. We evaluate our scheme using detailed simulations and show that it performs on par with the centralized optimum allocation. Moreover, our proposed scheme outperforms a static frequency reuse scheme and the centralized optimal partitioning between the macro and picos. In the second part of the dissertation, we propose a time domain solution to the interference problem. We consider the problem of maximizing the alpha-fairness utility over heterogeneous wireless networks (HetNets) by jointly optimizing user association, wherein each user is associated to any one transmission point (TP) in the network, and activation fractions of all TPs. Activation fraction of a TP is the fraction of the frame duration for which it is active, and together these fractions influence the interference seen in the network. To address this joint optimization problem which we show is NP-hard, we propose an alternating optimization based approach wherein the activation fractions and the user association are optimized in an alternating manner. The subproblem of determining the optimal activation fractions is solved using a provably convergent auxiliary function method. On the other hand, the subproblem of determining the user association is solved via a simple combinatorial algorithm. Meaningful performance guarantees are derived in either case. Simulation results over a practical HetNet topology reveal the superior performance of the proposed algorithms and underscore the significant benefits of the joint optimization. In the final part of the dissertation, we propose a space domain solution to the interference problem. We consider the problem of maximizing system utility by optimizing over the set of user and TP pairs in each subframe, where each user can be served by multiple TPs. To address this optimization problem which is NP-hard, we propose a solution scheme based on difference of submodular function optimization approach. We evaluate our scheme using detailed simulations and show that it performs on par with a much more computationally demanding difference of convex function optimization scheme. Moreover, the proposed scheme performs within a reasonable percentage of the optimal solution. We further demonstrate the advantage of the proposed scheme by studying its performance with variation in different network topology parameters.

Essays in Market Design

In this dissertation, I study three problems in market design: the allocation of resources to schools using deferred acceptance algorithms, the demand reduction of employees on centralized labor markets, and the alleviation of traffic congestion. I show how institutional and behavioral considerations specific to each problem can alleviate several practical limitations faced by current solutions. For the case of traffic congestion, I show experimentally that the proposed solution is effective. In Chapter 1, I investigate how school districts could assign resources to schools when it is desirable to provide stable assignments. An assignment is stable if there is no student currently assigned to a school that would prefer to be assigned to a different school that would admit him if it had the resources. Current assignment algorithms assume resources are fixed. I show how simple modifications to these algorithms produce stable allocations of resources and students to schools. In Chapter 2, I show how the negotiation of salaries within centralized labor markets using deferred acceptance algorithms eliminates the incentives of the hiring firms to strategically reduce their demand. It is well-known that it is impossible to eliminate these incentives for the hiring firms in markets without negotiation of salaries. Chapter 3 investigates how to achieve an efficient distribution of traffic congestion on a road network. Traffic congestion is the product of an externality: drivers do not consider the cost they impose on other drivers by entering a road. In theory, Pigouvian prices would solve the problem. In practice, however, these prices face two important limitations: i) the information required to calculate these prices is unavailable to policy makers and ii) these prices would effectively be new taxes that would transfer resources from the public to the government. I show how to construct congestion prices that retrieve the required information from the drivers and do not transfer resources to the government. I circumvent the limitations of Pigouvian prices by assuming that individuals make some mistakes when selecting routes and have a tendency towards truth-telling. Both assumptions are very robust observations in experimental economics.