# Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast
## 4 Proposed Heuristic Coding-Based On-Demand Broadcast
### Scheduling Algorithms with Heuristic Coding Implementation
#### 4.2.2 Non-Real-Time Algorithms  
* FCFS [26]: FCFS serves requests according to their arrival order. The network coding version of FCFS, needs to find the largest clique \(\delta\) which contains the vertex \(v_{i}\) with longest waiting time \(t_{max}\) among all \(t_{i}\) in \(G\). In the heuristic coding implementation (denoted by FCFS_N), the system first finds the selected vertex \(v_{ps}\) with \(t_{max}\). In Step 2 of Algorithm 1, \(v_{ps}\) is the vertex with the highest FCFS scheduling priority, i.e., \(v_{ps}=\{v_{ij}|t_{i}=max\{t_{1},t_{2},\cdots,t_{n}\},1\leq j\leq m\}\). ThenStep 3 searches for the maximal clique \(\delta_{max}^{v_{ps}}\) to ensure that the encoded packet \(\beta(\delta_{max}^{v_{ps}})\) consists the requested data item of the client with the longest waiting time.
* MRF [27]: MRF broadcasts the data item with the largest number of pending requests. The network coding version of MRF, needs to find the maximum clique \(\delta_{max}\) in \(G\), where \(\delta_{max}\) is the maximum clique among all the possible cliques in \(G\). In the heuristic coding implementation (denoted by MRF_N), the system first finds the selected vertex \(v_{ps}\) with the maximum \(N(d_{s})\) value. In Step 2 of Algorithm 1, \(v_{ps}\) is the vertex with the highest MRF scheduling priority, i.e., \(v_{ps}=\{v_{ij}|N(d_{j})=max\{N(d_{1}),N(d_{2}),\cdots,N(d_{m})\},1\leq i\leq n\}\). Then Step 3 searches for the maximal clique \(\delta_{max}^{v_{ps}}\) to ensure that the encoded packet \(\beta(\delta_{max}^{v_{ps}})\) consists the requested data item with the largest number of pending requests.
* LWF [27]: LWF broadcasts the data item with the largest total waiting time. The network coding version of LWF, needs to find the largest clique \(\delta\) in \(G\) with the maximum summed waiting time of the corresponding vertices. In the heuristic coding implementation (denoted by LWF_N), the system first finds the selected vertex \(v_{ps}\) with the maximum sum waiting time (\(\sum t_{i}\), \(1\leq i\leq n\)) value of data item \(d_{s}\), denoted as \(\sum t(d_{s})\). In Step 2 of Algorithm 1, \(v_{ps}\) is the vertex with the highest LWF scheduling priority, i.e., \(v_{ps}=\{v_{ij}|\sum t(d_{j})=max\{\sum t(d_{1}),\sum t(d_{2}),\cdots,\sum t(d_ {m})\},1\leq i\leq n\}\). Then Step 3 searches for the maximal clique \(\delta_{max}^{v_{ps}}\) to ensure that the encoded packet \(\beta(\delta_{max}^{v_{ps}})\) consists the requested data item with the largest total waiting time of the pending requests.
* R \(\times\) W [4]: R \(\times\) W schedules the data item with the maximum R \(\times\) W value, where \(R\) is the number of pending requests for that data item and \(W\) is the waiting time of the earliest request for that data item. The network coding version of R \(\times\) W, needs to find the largest clique \(\delta\) with the maximum \(|\delta|\times t_{max}\) value, where \(t_{max}\) is the maximum waiting time value among all \(t_{i}\) in \(\delta\). In the heuristic coding implementation (denoted by R \(\times\) W_N), the system first finds the selected vertex \(v_{ps}\) with the maximum \(N(d_{s})\times t_{p}\) value. In Step 2 of Algorithm 1, the \(v_{ps}\) selection is done by finding the vertex with the maximum \(N(d_{s})\times t_{p}\) value, i.e., \(v_{ps}=\{v_{ij}|N(d_{j})\times t_{i}=max\{N(d_{r(1)})\times t_{1},N(d_{r(2)}) \times t_{2},\cdots,N(d_{r(n)})\times t_{n},1\leq r,j\leq m\}\}\). Then Step 3 searches for the maximal clique \(\delta_{max}^{v_{ps}}\) to ensure that the encoded packet \(\beta(\delta_{max}^{v_{ps}})\) consists the requested data item with the maximum R \(\times\) W value.