# Online Distributed User Association for Heterogeneous Radio Access Network
## 4 Algorithm Description
### Hierarchical \(d\)-Choices Scheme
```
1:\(\lambda_{i}:=\{\text{set consisting loads of tiers for $i$th UE }|\eta_{i,j,k}\geq\tau\}\)
2:for all \(\text{UEs},i\)do
3: Independently choose a set \(K_{i}^{d}\) of \(d1\) tiers at random from \(\lambda_{i}\)
4:\(\lambda_{i,k}:=\{\text{loads of tiers belong to }K_{i}^{d}\}\), without loss of generality \(\lambda_{i,k}:=\{\ \lambda_{i,1},\lambda_{i,2},...,\lambda_{i,d1}\}\)
5: find \(K_{\psi}:=opt\) ( \(\lambda_{i,1},\lambda_{i,2},...,\lambda_{i,d1}\) )
6:\(B_{i}:=\{\text{ set of BSs}\in k_{\psi}\ |\ \eta_{i,j,k}\geq\tau\}\)
7: Independently choose a set \(B_{i}^{d}\) of \(d2\) BSs at random from \(B_{i}\)
8:\(\lambda_{j,k}:=\{\text{loads of BSs belong to }B_{j}^{d}\}\), without loss of generality \(\lambda_{j,k}:=\{\ \lambda_{j,1},\lambda_{j,2},...,\lambda_{j,d2}\}\)
9: find \(B_{\psi}:=opt\) ( \(\lambda_{j,1},\lambda_{j,2},...,\lambda_{j,d2}\) )
10: Associate UE \(i\) with \(B_{\psi}\) BS
11:endfor
12:\(K_{\psi}^{load1}=min\{\lambda_{i,1}^{load1},\lambda_{i,2}^{load1},...,\lambda _{i,d1}^{load1}\}\)
13:\(K_{\psi}^{load2}=max\{\lambda_{i,1}^{load1},\lambda_{i,2}^{load1},...,\lambda _{i,d1}^{load2}\}\)
14:\(B_{\psi}^{load1}=min\{\lambda_{j,1}^{load1},\lambda_{j,2}^{load1},...,\lambda _{j,d2}^{load1}\}\)
15:\(B_{\psi}^{load2}=max\{\lambda_{j,1}^{load1},\lambda_{j,2}^{load1},...,\lambda _{j,d2}^{load2}\}\)
```  
**Algorithm 3** Two-level _d_-choices scheme. Algorithm 3 executes the \(d\)-choices schemes in two levels. The UE begins its user association procedure by accumulating the BSs which satisfy the \(\eta_{i,j,k}\geq\tau\) in a tier-wise manner (Step 1). Subsequently, in Steps 3-5 the UE selects a tier from the \(K_{j}\) set using the \(d\)-choices scheme. The same procedure is applied to choose a BS from the chosen tier in Steps 6-9. Then in Step 10, the UE associates with the chosen BS. As the two load parameters, \(\lambda_{i,k}^{load1}\) and \(\lambda_{i,k}^{load2}\), have different properties, the \(opt\) function in Steps 5 and 9 returns different values, as mentioned in Steps 12-15. In the next subsection, we discuss the effect of different values for \(d1\) and \(d2\). Effects of Different \(d\)-Choices and Different User Association Methods  
To evaluate the effect of different \(d\)-choices, we consider a hypothetical scenario where there are four tiers and each tier has 10 servers. 1000 UEs arrive at the system one by one to attach with a server. First, the UE randomly picks \(d1\) tiers, and chooses the tier with the smallest load (total number of UEs). After the selection of an appropriate tier, the UE then randomly picks \(d2\) servers from a selected tier and picks the server with the minimum load. We chose Jain's fairness index for the fairness evaluation. The different \(d\)-choices, average Jain's fairness index, and the total probes made by a UE are given in Table 3. The Jain's fairness index with only four probes is about 0.9985, and this fairness does not increase significantly with an increase in the number of probes. The author in Ref. [53] showed that the power consumption of a UE increases with an increase in the number of probes. Apart from selecting the tier with a minimum load, a new scheme could be considered for the evaluation. If we select the most unbalanced tier from the \(d\) chosen tiers and allocate the UE to the minimum loaded BS, then the scenario will be totally different. This strategy may not ensure a load-balancing scenario. Think of a situation where all the servers of a tier have an equal number of  
Figure 3: Two-level load transmission. In Level One, all the small-cell BSs, pico and femto, send their respective load value to macro BS. In Level Two, all the base stations (BSs) broadcast their load values. UEs, but the total UE number is less than another unbalanced tier. The balanced tier will never be selected, even though the total number of UEs are less than other tiers. The final outcome will be an unbalanced allocation; hence, this method is not desirable.