# Online Distributed User Association for Heterogeneous Radio Access Network
## 2 Related Works
### Offline and Online User Association  
In the offline user association scheme, a static network environment is provided where the complete setup is assumed to be known previously. In general, a throughput optimization problem is formulated for the user association problem. Authors in Refs. [17; 31; 32; 33; 34; 35; 37; 38; 39; 40; 41; 42; 43] considered a static environment, where the channel condition does not change. A q-learning-based BS selection game was applied in Ref. [30]. In this, the UE tries to maximize a utility function by associating it with the best possible candidate for BS. The system converges to Nash equilibrium after several numbers of steps. By considering numerous sensors and mobile devices with a dense deployment and formulating the problem as a non-cooperative game mode, authors in Ref. [38] investigate the cell selection problem. They theoretically found the circular boundaries between the devices selecting the macrocell and those selecting the picocells. However, in the game-theory-based schemes, the players (BSs or UEs) cannot act rationally all the time due to the fact that different players (e.g., BSs) always have different optimization objectives [44]. Although the user association problem for a static/offline environment has been thoroughly investigated, less attention has been given to the online user association. The motivation behind the online user association problem is the practical nature of the problem. This is due to the fact that, in the presence of new UEs arriving over time, the problem is solved from scratch, where there is a high probability of UE re-association. This is not desirable from a UE's perspective, where frequent re-association occurs. The online schemes, on the other hand, do not need the complete setup in prior. The association decision is taken in an online fashion--that is, each UE associates with a BS upon arrival to the network. There is less related work present for the online user association problem. Authors in Ref. [19] highlighted the problem in static environments, and proposed user-centric and cell-centric online algorithms. A game-theory-based BS selection strategy was investigated in Ref. [39]. The problem was formulated as a non-cooperative game, where the strategy converges to Nash-equilibrium in a small number of steps. These schemes are straightforward as the maximum of a utility is considered for the user association. In this scheme, UEs arrive to the system one after another and select the BS which either maximizes the utility of the BS or the UE. Authors in Ref. [45] study the user association problem by considering both energy and spectrum efficiency maximization of the 5G HetNet. Taking the quality of service into account, the authors develop a low-complexity algorithm to solve the formulated optimization problem in an approximate manner. The approximation algorithm can also be employed in an online fashion. In Table 1, we have compared various user association schemes, while considering fairness and the environment type. The low complexity and dynamic nature of the distributed algorithm is well-suited for the cell selection problem. In this paper, we proposed two types of online distributed algorithms for load-balancing in a heterogeneous cellular network, such as _probabilistic_ and _d-choices_-based user association schemes. _D-choices_-based distributed load-balancing algorithms have been successfully applied to various server selection and channel allocation problems [46], where a client chooses \(d\) number of servers uniformly at random and associates with that server, which has a minimum load. A solution to balls into non-uniform bins was investigated in Ref. [47], where a heterogeneous environment was considered and the balls are assigned to the bins. After the allocation, the maximum load (number of balls) was found to be \(\frac{lnln(n)}{ln(d)}\), where \(n\) is the number of bins and \(d\) is the number of choices for a ball. A more realistic environment was considered in Ref.