# Online Distributed User Association for Heterogeneous Radio Access Network
## 4 Algorithm Description
### Hierarchical \(d\)-Choices Scheme  
The user association problem can be thought of as the \"balls and bins\" problem, shown in Ref. [48]. We can consider UEs to be balls and BSs to be bins. Each UE has a certain BS to associate with, and each BS has a specific capacity--for example, macro BS has more capacity than that of pico BS. Like in the traditional \"balls and bins\" experiment, each ball can choose \(d\) number of bins to associate with, and the expected maximum load is given by Equation (13), where \(n\) is the number of balls in the system. Here, \(O(1)\) represents a constant. No matter how large the size of \(n\) be, the maximum load is bounded by \(\frac{\ln\ln n}{\ln 2}\). \[\mathbb{E}[\text{maximum load}]=\frac{\ln\ln n}{\ln 2}+O(1). \tag{13}\]  
The same principle can be applied to the association scheme in a cellular network. Each user can choose \(d\) number of BSs and select a BS that has the lightest load among the chosen BSs. This above method is well-suited for homogeneous cases, where each BS has the same capacity and same probability of association, but in the case of HetNet, the capacity varies from one tier to another. Hence, load-balancing in this HetNet should be carefully considered. Authors in Ref. [47] proposed a \"balls into non-uniform bins\" method. Accordingly, we first reduced our BS selection problem to the \"balls into non-uniform\" problem, and then applied the algorithm prescribed therein. Each UE will associate with a BS so that the final load will be bounded by some factor. The _d-choices_ scheme has been successfully applied to many load-balancing applications. The main strategy is that when a UE arrives to the system, it chooses \(d\) servers in the system uniformly at random. Then, the UE checks the load of each of the \(d\) servers, and associates with the server with the least load. We tried to apply a similar scheme to this cellular network. Our scheme consists of two levels: (1) load-balancing in different tiers, and (2) load-balancing in each BS in a particular tier. The network traffic for different RATs must flow through the corresponding service gateway, so care must also be taken to balance the load in the service gateway level. We assumed that all BSs broadcasted their load information periodically. The macro BS, having the highest coverage area, has a special task, in that it accumulates all the load parameters of BSs of different tiers, adds them up tier-wise, and then broadcasts the load value. The broadcast signal by macro BS will have the load value of all tiers in the network. The UE performs the load-balancing task in two levels. Figure 3 shows the procedure of load transmission in two levels. After receiving the load information from macro BS, it selects \(d\) tiers uniformly at random, and then chooses a tier from the \(d\) number of tiers which has a minimum load. The next step is to choose a BS from the already chosen tier. The UE repeats the above procedure for selecting a BS from the chosen tier. The UE chooses \(d\) number of BSs uniformly at random, and selects a BS from the \(d\) number of BSs which has a minimum load. This procedure ensures load balancing at two levels: (1) tier-level load-balancing, and (2) BS-level load-balancing. Note that tier-level load-balancing is required to shift the load from a heavily loaded tier to a lightly loaded tier. Algorithm 3, _d-choices_, depicts the above distributed _d_-choices scheme by considering \(\lambda_{j,k}\).