# Asynchronous Hierarchical Federated Learning Based on Bandwidth Allocation and Client Scheduling
## 3 System Model
### Load Balance  
Generally, it is hard to predict the movement of each client. This work assumes that the state transition probability of each client is available. Specifically, different edge servers have different coverage areas. The probability that a client staying in the coverage area of edge server \(ES_{j}\) moves to the coverage area of edge server \(ES_{j^{\prime}}\) is known a priori. Thus, we model the movement of clients as a Markov process and an example of the state transition probability matrix is given in (8) with \(J=3\), where the elements in row \(j\) and column \(j^{\prime}\) represent the probability that a client moves from the coverage area of edge server \(j\) to the coverage area of edge server \(j^{\prime}\) during the training process.  
\[\mathbf{M}=\begin{bmatrix}e_{11}&e_{12}&e_{13}\\ e_{21}&e_{22}&e_{23}\\ e_{31}&e_{32}&e_{33}\end{bmatrix}. \tag{8}\]  
Each client participating in the training process has a specific initial bandwidth allocation ratio \(\beta_{0}\). First, we define a vector \(\mathbf{n}=[n_{1},n_{2},n_{3},\ldots,n_{J}]^{T}\) where the \(j\)-th element represents the number of clients that are associated with edge server \(j\) in the next round. In addition, we also define a vector \(\mathbf{x}=[x_{1},x_{2},x_{3},\ldots,x_{J}]^{T}\) where the \(j\)-th element denotes the number of clients initially allocated by the cloud server to the \(j\)-th edge server. Then, we formulate the following optimization problems, which determine the number of clients that are associated with each edge server, i.e.,  
\[\min_{\mathbf{x}}\sum_{i=1}^{J}(y_{j}-n_{j})^{2},\] (9) s.t. \[\sum_{j=1}^{J}x_{j}-\sum_{j=1}^{J}n_{j}=0,\] \[x_{j}\geq 0,j\in\mathcal{J},\] \[x_{j}^{\text{remain}}-x_{j}\geq 0,j\in\mathcal{J},\]  
where \(y_{j}\) is the \(j\)-th element of \(\mathbf{y}=\mathbf{x}^{T}\mathbf{M}\). We rewrite the first constraint as \(c_{1}(x)=0\), the following \(J\) constraints as \(c_{j}=x_{j}\geq 0,j=2,3,\ldots,J+1\), and the last \(J\) constraint as \(c_{j}=x_{j}^{\text{remain}}-x_{j}\geq 0,j=J+2,J+3,\ldots,2J+1\), respectively.  
The constraint problem (9) can be solved with the projected hypergradient descent method [15], for which the main steps are given as follows:  
Step 1: We first initialize the penalty factor \(\theta_{1}\), error control factor \(\varepsilon>0\), constant \(\theta\in(0,1)\), and \(k=1\).  
Step 2: For the initial point \(\mathbf{X}_{k-1}\), we solve the following unconstrained problem:  
\[M(x,\lambda,\sigma)=f(x)+\frac{1}{2\sigma}\sum_{i=2}^{2J+1}\left\{\left[\max( 0,\lambda_{i}-\sigma c_{i}(x))\right]^{2}-\lambda_{i}^{2}\right\}\]  
\[-\lambda_{1}c_{1}(x)+\frac{\sigma}{2}c_{1}(x), \tag{10}\]  
then we obtain the optimal solution \(\mathbf{X}_{k}\).  
Step 3: If \(\varphi_{k}=\left\{c_{1}^{2}(x)+\sum_{i=2}^{2J+1}\left[\min\left(c_{i}(x_{k}), \frac{(\lambda_{i})}{\sigma}\right)\right]\right\}^{\frac{1}{2}}<\varepsilon\), then \(\mathbf{X}_{k}\) is the optimal solution; stop. Otherwise, go to step 3.  
Step 4: If \(\varphi_{k}/\varphi_{k-1}\leq\theta\), go to step 4. Otherwise, let \(\sigma_{k+1}=c\sigma_{k}\), and go to step 4.  
Step 5: Update the multiplier vector according to  
\[\left(\lambda_{k+1}\right)_{1}=\left(\lambda_{k}\right)_{1}-\sigma c_{1}(x_{k }), \tag{11}\]  
and  
\[\left(\lambda_{k+1}\right)_{i}=\max[0,\left(\lambda_{k}\right)_{i}-\sigma c_{ i}(x_{k})],i=2,3,\ldots,2J+1. \tag{12}\]  
Let \(k=k+1\), then go to step 2.  
Here, the first constraint is an equality constraint and the other constraints are inequality constraints. The output \(\mathbf{X}\) may not an integer and the rounding method can be adopted. Then, the obtained integer solution is the number of clients that are associated with each edge server. The proposed client selection method reduces the insufficient bandwidth allocation, especially when the number clients is large but the available bandwidth is scarce.