## 4 Random Linear Network Coding for Mobile Video Delivery
### RLNC and Resource Allocation  
Integration of RLNC sublayer within LTE protocol stack opens novel and interesting problems of interaction between RLNC and resource allocation that we describe next. We consider a general system model where a base station broadcasts an \(\ell\)-layer video stream encoded according to the SVC paradigm. We also say that layer 1 is the basic and layers \(2,\ldots,L\) are the enhancement layers. Assuming our system model adopts a NOW-RLNC implementation, any resource allocation strategy has to answer the following questions [19; 69; 70; 71]:  
* How many coded packet transmissions per-video layer are to be scheduled for transmission? * What MCSs are to be used for broadcasting each coded packet? Figure 5: MAC-RLNC sublayer as part of LTE RAN protocol stack. Obviously, choosing the correct number of coded packet transmission affects the user decoding probability. Likewise, the MCS selection has a direct impact on the total number of users capable of successfully decoding a given number of video layers. Let \(\mathcal{F}\) be our utility function, a General Resource Allocation Problem (GRAP) for network coded video application has the following structure:  
\[\text{(GRAP)} \min_{\mathbf{m},\mathbf{N}}\ \mathcal{F}\] (4) subject to \[m_{\ell-1}<m_{\ell}, \ell=2,\ldots,L \tag{5}\] \[\mathcal{U}_{\ell}\geq\hat{\mathcal{U}}_{\ell}, \ell=1,\ldots,L\] (6) \[\mathcal{S}(\mathbf{N})\leq\hat{S}\] (7) \[\mathcal{T}(\mathbf{N})\leq\hat{T} \tag{8}\]  
where \(m_{\ell}\) signifies the MCS to be used for transmitting coded packets associated with layer \(\ell\). In addition, we define our optimization variables to be the vectors \(\mathbf{m}=\{m_{1},\ldots,m_{L}\}\) and \(\mathbf{N}=\{N_{1},\ldots,N_{L}\}\). Constraint (5) ensures that coded packets associated with layer \(\ell-1\) are being transmitted with a smaller MCS compared to that used for layer \(\ell\) - thus ensuring coded packets associated with layer \(\ell-1\) are received with a PER \(\epsilon\) that is smaller than or equal to that experienced in receiving coded packets associated with layer \(\ell\). From (2), it follows that the probability of a user successfully recovering the first \(\ell\) video layers can be expressed as \(\prod_{i=1}^{\ell}\ P_{d}^{i}(N_{i})\), where \(N_{i}\) is the number of coded packet transmission associated with layer \(i\). Let us signify with \(U_{\ell}\), the number of users that can successfully decode the first \(\ell\) video layers with a probability equal to or greater than \(\hat{p}_{d}\). Constraint (6) ensures that \(U_{\ell}\) is greater than or equal to a target number of users \(\hat{\mathcal{U}}_{\ell}\). We observe that relation \(\hat{\mathcal{U}}_{\ell-1}\geq\hat{\mathcal{U}}_{\ell}\) holds true for \(\ell=2,\ldots,L\) as it would be pointless to impose video layer \(\ell\) to be decoded by a number of users larger than \(\ell-1\). Constraint (7) ensures that the total number of coded packets scheduled on each radio frame does not exceed a given threshold \(\hat{S}\). Finally, constraint (8) ensure that each portion of video stream is transmitted by a time \(\hat{T}\). Unfortunately, to the best of our knowledge, GRAP is an integer (potentially) non-linear optimization problem with no obvious analytical solutions. However, when \(\mathcal{F}\) is equal to the total number of coded packet transmissions, authors' [69; 70] argued that it is possible to find a good-quality feasible solution to GRAP using a two-step heuristic operating as follows:  
1. _MCS Allocation_--The heuristic iterates over all the MCSs (starting from the highest), and for each video layer, it identifies the largest MCS such that constraints (5) and (6) are met. The output of this heuristic step is an instance of vector \(\mathbf{m}\). 2. _Code Packet Transmissions Optimisation_--On the basis of the instance of vector \(\mathbf{m}\) determined in the previous step, the minimum value of \(N_{\ell}\) is determined, for any \(\ell=1,\ldots,L\)--thus an instance of vector \(\mathbf{N}\) is found.