Fourth generation (4G) cellular systems, including those based on the popular Long Term Evolution Advanced (LTE-A) standard, are based on Orthogonal Frequency Division Multiple Access (OFDMA) technology, and are often deployed with universal frequency reuse, wherein the entire available spectrum is reused in every cell. We study the inter-cell interference coordination (ICIC) problem in such a cellular network. In each cell, only a subset of the available subchannels are allocated to mobile stations (MSs) in a given time slot so as to limit the interference to neighboring cells; also, each base station (BS) uses a fixed transmit power on every allocated subchannel. The objective is to allocate the available subchannels in each cell to the MSs in the cell for downlink transmissions taking into account the channel qualities from BSs to MSs as well as traffic requirements of the MSs so as to maximize the weighted sum of throughputs of all the MSs. First, we show that this problem is NP Complete. Next, we show that when the potential interference levels to each MS on every subchannel are above a threshold (which is a function of the transmit power and the channel gain to the MS from the BS it is associated with), the problem can be optimally solved in polynomial-time via a reduction to the matching problem in bipartite graphs. We also formulate the ICIC problem as a noncooperative game, with each BS being a player, and prove that although it is an ordinal potential game in two special cases, it is not an ordinal potential game in general. Now, in general, there exists a trade-off between the total throughput (sum of throughputs of all the MSs) and fairness under the allocations found by resource allocation schemes. We introduce the concept of tau-alpha-fairness by modifying the concept of alpha-fairness, which was earlier proposed in the context of designing fair end-to-end window-based congestion control protocols for packet-switched networks. The concept of tau-alpha-fairness allows us to achieve arbitrary trade-offs between the total throughput and degree of fairness by selecting an appropriate value of alpha in [0,infinity). We show that for every alpha in [0,infinity) and every tau > 0, the problem of finding a tau-alpha-fair allocation is NP-Complete. Also, we propose a simple, distributed subchannel allocation algorithm for the ICIC problem, which is flexible, requires a small amount of time to operate, and requires information exchange among only neighboring BSs.
Gaurav S. Kasbekar received B.Tech. in Electrical Engg. from Indian Institute of Technology (IIT), Bombay in 2004, M.Tech. in Electronics Design and Technology (EDT) from Indian Institute of Science (IISc), Bangalore in 2006 and Ph.D from University of Pennsylvania, USA in 2011. He is currently an Assistant Professor with the Department of Electrical Engineering, IIT Bombay. His research interests are in the modeling, design and analysis of wireless networks. He received the CEDT Design Medal for being adjudged the best Masters student in EDT at IISc.