## 3 User Clustering and Power Allocation Co-Design
### Lagrangian Multiplier Based Dynamic Programming Model for Power Allocation  
After user clustering, the target problem is now reduced to determine how much energy should be allocated to each cluster, i.e., calculate \(P=\{P_{1},P_{2},\cdots,P_{n}\}\). We observe that this problem has an optimal substructure property. Thus, it can be solved by dynamic programming techniques. We choose dynamic programming to solve this problem due to the following reasons. Firstly, dynamic programming can solve a problem optimally by breaking it into sub-problems and recursively finding the optimal solution. Therefore, using a dynamic programming algorithm can examine each cluster's power allocation and combine their results to give the best solution. Secondly, in the present cellular system, the service association between BS and users can remain unchanged for more than hundreds of microseconds. This frequency is enough for BS to perform rescheduling of power allocation, where the user clustering result is relatively static. Therefore, the power allocation can be done offline, and the timing overhead incurred by a dynamic programming algorithm will not cause the latency for communication services between BS and users. Let \(f(j,p)\) be the maximum throughput of the \(j\)-th cluster with power budget \(p\). Define the maximum throughput of the previous \(j\) clusters with energy budget \(p\) as \(T(j,p)\), and the corresponding optimal power allocation for the \(j\)-th cluster is defined as \(A(j,p)\). In  
Figure 2: An example result of allocating 19 users into three clusters. our dynamic programming model, we consider decreasing the continuous power budget with the minimum assignable unit \(\xi\) and allocating an integral multiple of \(\xi\) power to each cluster. We can look back at the optimal way to allocate the previous \(j-1\) clusters' power and determine how much energy should be allocated to the \(j\)-th cluster. Based on this observation, the recursive solution of the optimal subproblem is listed as  
\[T(j,p)=\left\{ \begin{array}{c}0,if\ j=0,\\ \max\biggl{\{}T(j-1,p-k\xi)+f(j,k\xi)|k=0,1,\ldots,\biggl{\lfloor}\frac{\min \left(p,\omega_{j}p_{k}\right)}{\xi}\biggr{\rfloor}\biggr{\}},if\ j=1,2,\ldots,c.\end{array} \right. \tag{13}\]  
Algorithm 1 shows the inter-cluster dynamic programming for energy efficiency maximization. The recurrence of the solution compares up to \(\left\lfloor\frac{\omega_{j}p_{k}}{\xi}\right\rfloor+1\) values to obtain each \(T(j,p)\), which denotes the cases in which \(k\xi\) power budget is assigned to the \(j\)-th cluster, and the remaining \(p-k\xi\) power budget is assigned to the previous \(j-1\) clusters. The optimal power allocation result, which is denoted as \(\left\{\bar{P}_{1},\bar{P}_{2},\ldots,\bar{P}_{c}\right\}\) can be obtained by backtracking the values of \(A(j,p)\), as showed in steps 25 to 29 in Algorithm 1. Based on the above processes, now the only problem to be solved is calculating the relationship between the maximum throughput and the pow budget in each cluster, i.e., the function \(f(j,p)\), which is an input of the inter-cluster dynamic programming algorithm.