# Game Theory-Based Load-Balancing Algorithms for Small Cells Wireless Backhaul Connections +
## 2 Materials and Methods
### Modeling the User Clustering Process as a Game  
The user clustering problem aims to associate each user terminal to one and only one AP in such a way as to maximize the use of the available resources while fulfilling the flows' end-to-end QoS requirement. For this, each user should be connected to the nearest AP (to maximize the user-AP link's quality), and the difference between the load and capacity of the APs should be minimized. To model the clustering problem, let's denote by \(D_{i}(t)\) the demand formulated by the user \(i\), and by \(C_{j}(t)\) the sum of the capacity of the tunnels starting from APs \(j\). Let \(x_{i,j}\) be a binary variable which is \(x_{ij}=1\) if the user \(i\) is connected to APs \(j\) and 0 otherwise, then the load \(L_{j}(t)\) of the \(j\)-th AP is:  
\[L_{j}(t)=\sum_{i}x_{i,j}\cdot D_{i}(t)\ \forall j \tag{27}\]The clustering problem can be formulated as a liner programming problem in the following way:  
\[ \begin{array}{c}\min\limits_{j}\sum\limits_{j}y_{j}\cdot\left(L_{j}(t)-C_{j}(t )\right)\\ \min\limits_{j}\sum\limits_{i}\sum\limits_{j}x_{i,j}\cdot d_{i,j}\\ s.t.\\ \sum\limits_{j}x_{i,j}=0\ \forall i\\ x_{i,j},\ y_{j}\in\{0,1\}\end{array}  \tag{28}\]  
where \(y_{j}\) = 1 if \(L_{j}(t)>C_{j}(t)\) and 0 otherwise and \(d_{i,j}\) is the distance between the \(i\)-th user terminal and the \(j\)-th AP. To solve the user clustering problem a simple non-cooperative and a cooperative game is proposed. In each case, the AP is represented by a \"user broker\" (player) \(ap_{i}\), which allows more users to connect to the AP if the AP's load is less than the instantaneous capacity. In the non-cooperative game, each AP agent chooses the action that minimizes the gap between the load and backhaul capacity of the represented AP. Definition of the game:  
* the \(ap_{i}\), \(i\)\(\in\)\(\{1,\ldots,K\}\) AP agents are the players;
* \(A_{i}\) = \(\{\)P\({}_{1}\), \(\ldots,\) P\({}_{\text{N}}\}\) is the finite set of the actions of player \(i\), i.e., each player should choose a transmit power that influences the user terminals to connect or not to the specific AP. It is defined an action profile \(\mathbf{a}\) = \((a_{1},a_{2},\ldots\ a_{K})\), where each element \(a_{i}\) of the vector represents one action for each player of the game, and each action profile corresponds to an arrangement \(\mathbf{s}\) of APs and users. * the payoff or the utility function \(u_{i}\) of a player in this case is \(u_{i}=C_{i}(t)-L_{i}(t)\), i.e., the expected difference between the load and the capacity of \(\text{AP}_{\text{i}}\). The steps necessary to implement the non cooperative clustering process are described by Algorithm 6. ```
estimate the difference between the demand and capacity for each AP. 1:for\(j\) = 1 to Ndo
2: estimate \(C_{i}(t)-L_{i}(t)\) using the average packet delay or the lengths of the transmit queues. Check if the AP has free capacity. 3:if\(C_{i}(t)-L_{i}(t)>0\) Increase the transmit power of \(\text{AP}_{\text{i}}\) and by this increase the coverage area and the number of users connected to \(\text{AP}_{\text{i}}\). 4:else Reduce the transmit power of \(\text{AP}_{\text{i}}\) and by this reduce the coverage area and the number of users connected to \(\text{AP}_{\text{i}}\). 5:endif
6:endfor
7: Each user checks the strengths of the received signal from each AP and chooses the AP from which the received signal has the highest power. ```  
**Algorithm 6** Non cooperative user clustering mechanism  
In the case of the cooperative game each AP agent, \(ap_{i}\), collaborates with the agents of the neighboring APs to choose the strategy that might minimize the gap between their load and the backhaul capacity.