User Association in Heterogeneous Networks

01 Jan 2014

In dense heterogeneous cellular networks, mobile devices such as smart phones can potentially associate with several different base stations.  Which one should they choose? WNCG Profs. Andrews and Caramanis, in collaboration with lead researcher Qiaoyang Ye and Principal Engineer Mazin Al-Shalash from WNCG affiliate Huawei  have been working towards characterizing optimal user associations, and simple techniques to approach these optimal associations, which can be extremely complex to determine.   Their work has drawn attention from several major players in the 3GPP standards in addition to Huawei, including Qualcomm, Nokia Siemens Networks, Alcatel-Lucent, and NTT Docomo, who have each built on their ground-breaking results. 

First some background.  To meet crushing data traffic demands, cellular networks are evolving into ever-denser and irregular heterogeneous networks, especially through proliferation of small cells (e.g., picocells and femtocells). Due to the disparate transmit powers of different base stations, “natural” user association metrics like SINR or RSSI can lead to a major load imbalances and under-utilized small cells, with the macrocell remaining a major bottleneck. A critical missing piece in the conventional association metrics is the load, which provides a view of resource allocation and thus affects the long-term rates. In general, finding an optimal load-aware user association is a combinatorial optimization problem with exponential complexity. Meanwhile, any practically useful solution must be lightweight and efficient, and ideally solvable in a distributed way.

In two recent papers, Prof. Jeff Andrews, Prof. Constantine Caramanis, Qiaoyang Ye, and Mazin Al-Shalash, along with Beiyu Rong and Yudong Chen have used tools from convex optimization to address the association problem, devising easily computable upper bounds to optimal network performance, and then devising extremely efficient distributed algorithms that are provably near-optimal. In addition, they compared the extremely simple approach advocated by 3GPP known as “biasing”, or cell range expansion, whereby small cell received powers are artificially biased by a certain amount, for example 10 dB, compared to the macrocells to result in more mobile users associating with them.

The first paper provides a low-complexity distributed algorithm that converges to a near-optimal solution. We found that the gap between the rate-optimized association and the range expansion approach can actually be very small, if the bias is chosen carefully.   This is somewhat surprising, and was the first result in the literature to show that simple optimized biasing (where all BSs in the network of a certain class use the same exact value) is in fact pretty close to a globally optimal association policy.

Since users offloaded to small cells suffer strong interference from macro base stations, muting the macrocells for a certain fraction of resources reduces this interference, at the cost of turning off the most congested base stations.  Is this a good tradeoff? In the second paper, we considered this question, and found that the answer is generally “yes”.  In particular, under a typical small cell deployment of say 6 picocells per macrocell, the macrocell should mute itself roughly half of the time.  This increases the edge rate substantially, in part by allowing more aggressive biasing since the interference is reduced.



This work was also partially supported by the National Science Foundation, and the Defense Threat Reduction Agency (DTRA).