programming and solved through linear relaxation or brute- force searching. Unlike above global optimization approaches,game theory based algorithms utilize user preference to select the best BS in a distributed way.It is shown in [3]that the BS selection game converges to Nash equilibria when there is only one class of radio access technology.However,only carefully designed game strategies can converge in case there are multiple classes of BSs in the network.When both the preference of the user and the small cells are considered, 600 a college admission algorithm can be used to find a stable matching between users and femtocells [4].Unfortunately, (a)Local preference based association these distributed algorithms do not provide any performance guarantee for randomly deployed networks. III.MOTIVATION AND SYSTEM MODEL A.Motivation As a motivating example,Fig.I gives a snapshot of user association plan for randomly distributed users and BSs in a 70x70 meters area.To simplify the illustration,we only draw a single tier of femtocells,where each femtocell can serve up 0 to 6 users.Fig.1(a)shows the result when users select serving meters BS based on local preference,e.g.,they try to associate with (b)Globally optimized association the BS which provides the highest throughput as in [3].[4].In the lower-right region of Fig.1(a),there is a cluster of users Fig.1.User association for randomly deployed femtocells (femtocells:blue stars,users:red dots.association relationship:red or green lines). not associated with any femtocells,since all nearby femtocells do not have any vacancy.Although there are abundant lightly B.System Model loaded femtocells in the upper-right region,they cannot serve Hinted by the observations in the previous section,we these "orphan"users due to the limited communication range This imbalanced traffic load for femtocells leads to higher formulate the user association problem as a global optimization traffic burdens on the next tier of BSs,i.e.,these "orphan' problem.Consider a HetNet which consists of N BSs in the BS users have to turn to the microcell tier or the marcocell tier set B and M users in the user set l.Base Stations can be either for help. macrocells,picocells,femtocells or WiFi APs.Different types of BSs are characterized by their Radio Access Technologies Fig.1(b)shows a more balanced association plan con- (RATs),transmission powers and backhaul bandwidths.We structed through global optimization algorithm.In this case, assume that users can switch between multiple BSs,but they lightly loaded femtocell can take over users associated with can only associate with one BS at the same time,due to heavily loaded femtocells in a cascading way so that more the capability limitations of mobile devices.If a user has users can be served by femtocells,as illustrated in the red multiple interfaces that can operate independently,we treat rectangle of Fig.1(b).Some of these femtocells serve users each interface as a separate user. outside their Voronoi cells.This means the global optimization We assume that the achievable throughput for a given user solution forces users to accept a less preferred choice by is determined by two factors,the transmission bit rate and re- associating them to a femtocell which is not the nearest one to sources allocated to the user.Firstly,the wireless transmission them.Existing association algorithms,such as SINR Biasing bit rate for a given user is determined by the received SINR [7]or Game Theory based algorithm [3],cannot sacrifice the of the serving BS.As instantaneous SINR perceived by the welfare of some users to achieve global optimality. user is time-varying due to slow/fast fading and transmission The difference between the user association plans in of nearby BSs/users,we use the long-term average rate to Fig.1(a)and 1(b)leads to drastic difference in the load of characterize the achievable rate.In the following discussions, macrocells.For example,femtocells serve about 80%users in we assume the average rate that user i can receive from BS j is Fig.1(a).In a three tier HetNet which consists of femtocells, rij.Secondly,the throughput for user i is also determined by the amount of wireless resources that BS j allocates for user i microcells and macrocells,the marcocell tier needs to serve (1-80%)x(1-80%)=4%users,assuming the microcell tier By wireless resources,we mean time slots in TDMA systems, subcarriers in OFDM systems or Resource Blocks (RBs)in can also offload 80%users.If the offloading ratio is improved to 95%as in Fig.1(b),the macrocell only needs to serve LTE.We use cij to denote the proportion of resources that BS j allocates to user i.Combining these two factors,the 0.25%of all users,which is an order of magnitude less than the previous case.In consequence,fewer costly macrocells need to throughput of user i under BS j can be written as cijrij. be deployed or upgraded.Therefore,achieving an offloading The goal of the user association problem for HetNet is ratio close to 100%is crucial for reducing the network cost. to find an optimal association scheme for each user i alongprogramming and solved through linear relaxation or brute￾force searching. Unlike above global optimization approaches, game theory based algorithms utilize user preference to select the best BS in a distributed way. It is shown in [3] that the BS selection game converges to Nash equilibria when there is only one class of radio access technology. However, only carefully designed game strategies can converge in case there are multiple classes of BSs in the network. When both the preference of the user and the small cells are considered, a college admission algorithm can be used to find a stable matching between users and femtocells [4]. Unfortunately, these distributed algorithms do not provide any performance guarantee for randomly deployed networks. III. MOTIVATION AND SYSTEM MODEL A. Motivation As a motivating example, Fig. 1 gives a snapshot of user association plan for randomly distributed users and BSs in a 70×70 meters area. To simplify the illustration, we only draw a single tier of femtocells, where each femtocell can serve up to 6 users. Fig. 1(a) shows the result when users select serving BS based on local preference, e.g., they try to associate with the BS which provides the highest throughput as in [3], [4]. In the lower-right region of Fig. 1(a), there is a cluster of users not associated with any femtocells, since all nearby femtocells do not have any vacancy. Although there are abundant lightly loaded femtocells in the upper-right region, they cannot serve these “orphan” users due to the limited communication range. This imbalanced traffic load for femtocells leads to higher traffic burdens on the next tier of BSs, i.e., these “orphan” users have to turn to the microcell tier or the marcocell tier for help. Fig. 1(b) shows a more balanced association plan con￾structed through global optimization algorithm. In this case, lightly loaded femtocell can take over users associated with heavily loaded femtocells in a cascading way so that more users can be served by femtocells, as illustrated in the red rectangle of Fig. 1(b). Some of these femtocells serve users outside their Voronoi cells. This means the global optimization solution forces users to accept a less preferred choice by associating them to a femtocell which is not the nearest one to them. Existing association algorithms, such as SINR Biasing [7] or Game Theory based algorithm [3], cannot sacrifice the welfare of some users to achieve global optimality. The difference between the user association plans in Fig. 1(a) and 1(b) leads to drastic difference in the load of macrocells. For example, femtocells serve about 80% users in Fig. 1(a). In a three tier HetNet which consists of femtocells, microcells and macrocells, the marcocell tier needs to serve (1−80%)×(1−80%) = 4% users, assuming the microcell tier can also offload 80% users. If the offloading ratio is improved to 95% as in Fig. 1(b), the macrocell only needs to serve 0.25% of all users, which is an order of magnitude less than the previous case. In consequence, fewer costly macrocells need to be deployed or upgraded. Therefore, achieving an offloading ratio close to 100% is crucial for reducing the network cost. 0 100 200 300 400 500 600 700 0 100 200 300 400 500 600 700 meters meters (a) Local preference based association 0 10 20 30 40 40 60 70 0 10 20 30 40 50 60 70 meters meters (b) Globally optimized association Fig. 1. User association for randomly deployed femtocells (femtocells: blue stars, users: red dots, association relationship: red or green lines). B. System Model Hinted by the observations in the previous section, we formulate the user association problem as a global optimization problem. Consider a HetNet which consists of N BSs in the BS set B and M users in the user set U. Base Stations can be either macrocells, picocells, femtocells or WiFi APs. Different types of BSs are characterized by their Radio Access Technologies (RATs), transmission powers and backhaul bandwidths. We assume that users can switch between multiple BSs, but they can only associate with one BS at the same time, due to the capability limitations of mobile devices. If a user has multiple interfaces that can operate independently, we treat each interface as a separate user. We assume that the achievable throughput for a given user is determined by two factors, the transmission bit rate and re￾sources allocated to the user. Firstly, the wireless transmission bit rate for a given user is determined by the received SINR of the serving BS. As instantaneous SINR perceived by the user is time-varying due to slow/fast fading and transmission of nearby BSs/users, we use the long-term average rate to characterize the achievable rate. In the following discussions, we assume the average rate that user i can receive from BS j is rij . Secondly, the throughput for user i is also determined by the amount of wireless resources that BS j allocates for user i. By wireless resources, we mean time slots in TDMA systems, subcarriers in OFDM systems or Resource Blocks (RBs) in LTE. We use cij to denote the proportion of resources that BS j allocates to user i. Combining these two factors, the throughput of user i under BS j can be written as cij rij . The goal of the user association problem for HetNet is to find an optimal association scheme for each user i along