# Effective 5G Wireless Downlink Scheduling and Resource Allocation in Cyber-Physical Systems +
## 4 Dynamic Scheduling and Resource Allocation  
In general, a greedy algorithm makes a choice deemed best according to a certain criterion regardless of the choices it made before or will make in the future. Although it may find an effective solution in a reasonable time, it also results in a suboptimal solution when a series of local decisions fails to lead to a global optimum. The basic idea for dynamic programming is to solve subproblems optimally only once and store the results and look up the stored optimal solutions to the subproblems instead of recomputing them to compute the optimal solution for a given problem efficiently [79; 80].  
In this paper, we design a new SKA algorithm by adapting the dynamic programming method for the 0/1 knapsack problem to optimize the utility of SKA for allocating RBs to active users with non-empty queues. It is challenging to design a cost-effective algorithm for RB allocation, since the 0/1 knapsack problem is NP-complete. In this section, we design a dynamic programming algorithm to maximize the utility defined in Section 3 in polynomial time and analyze the time complexity.  
To this end, we first design the recursive structure of utility function \(V\) to allocate free RBs, \(N_{B}^{free}\), optimally to an arbitrary user \(u\) where \(Q_{u}>0\) as follows:  
\[V[u,k]=\begin{cases}max\left(V[u-1,k],V[u-1,k\ -m[u]]+w[u]\times r_{u,l}(m[u]) \right)&\text{if }m[u]\leq k;\\ V[u-1,k]&\text{otherwise}.\end{cases}\]  
Here, \(k\) is the number of the available RBs, \(m[u]\) is the number of RBs required by the MS \(u\) and \(r_{u,l}(m[u])\) is the transmission capacity provided to MS \(u\) by \(m[u]\) RBs. If \(m[u]\leq k\), MS \(u\) can be assigned the required number of RBs. In this case, our dynamic programming method for SKA optimizes the total utility by assigning \(m[u]\) RBs to MS \(u\), if \(V[u-1,k\ -m[u]]+w[u]\times r_{u,l}(m[u])>V[u-1,k]\) and updates the total utility as \(V[u-1,k\ -m[u]]+w[u]\times r_{u,l}(m[u])\). Otherwise, it does not assign the RBs to MS \(u\) and maintains the utility as \(V[u-1,k]\). If \(m[u]>k\); however, the RBs required by MS \(u\) are unavailable; therefore, our approach cannot meet the requirement of MS \(u\). As a result, the utility remains as \(V[u-1,k]\). With this, we design the dynamic programming algorithm for SRA based on these recursive properties, as shown in Algorithm 1.  
```
Input : Set of active users \(U:=\{u|Q_{u}\
eq\varnothing\}\) \(N_{MS}\): Number of MSs (=\(|U|\)) \(N_{free}\): Number of free RBs \(m[1..N_{MS}]\): Array of RBs required by MSs \(w[1..N_{MS}]\): Array of MS weights Output :SRA via Dynamic Programming knapsack(\(U,N_{free},m,w\)) { for\(j=0;j\leq N_{free}\);\(j\)++do \(V[0,j]=0\); /* no MS */  end for for(\(u=1;u\leq N_{MS};u++\))do \(V[u,0]=0\); /* no RB */ for(\(k=1;k<N_{free};k++\))do if(\(m[u]\leq k\))then \(V[u,k]=max\Big{(}V[u-1,k],V[u-1,k\ -m[u]]+w[u]\times r_{uJ}(m[u])\Big{)}\); else \(V[u,w]=v[u-1,w]\);  end if  end for  end for
```  
**Algorithm 1**SRA via dynamic programming.  
As discussed earlier, the base station has limited transmission capacity \(r_{uJ}(t,N_{B_{u}})\) at each TTI \(t\), where the spatial stream, \(l\), and number of RBs, \(N_{B_{u}}\), represent the resources in the frequency and time domain, respectively. At the 5G base station, the user requests in a queue may be of eMBB, URLLC and eMTC types. As a result, it may demand various \(m[u]\) RBs, such as 100, 25 and 6 for the eMBB, URLLC and eMTC use-cases, respectively. In this case, our utility function \(V\) allocates the required RBs only if \(m[u]\leq k\) and tries to maximize the transmission capacity \(r_{uJ}\). If \(m[u]>k\), it holds the request of user \(u\) till the next TTI and schedules it later. Hence, the user requests of diverse use-cases at the 5G base station can be scheduled together by our SRA algorithm based on dynamic programming. By leveraging dynamic programming, we fully optimize the allocation of the transmission capacity at the base station at every TTI.