# Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast
## 4 Proposed Heuristic Coding-Based On-Demand Broadcast
### The Heuristic Algorithm  
To sum up, our heuristic coding-based on-demand broadcast consists of the following three key steps. The pseudo code is shown in Algorithm 1. ```
1 Step 1: CR-graph construction
2\(G(V,E)\) is the already constructed CR-graph, and \(v_{kr}\) is the vertex for a newly arrived client \(c_{k}\), where \(1\leq k\leq n,\ 1\leq r\leq m\) ;
3 foreach\(v_{ij}\in V(G)\)do
4 if\(j\)=s then
5\(E(G)\gets E(G)+e(v_{ij},v_{kr})\);
6 elseif\(d_{j}\in H(c_{k})\) &&\(d_{r}\in H(c_{i})\)then
7\(E(G)\gets E(G)+e(v_{ij},v_{kr})\);
8
9 else
10\(/\)* There is no link between \(v_{ij}\) and \(v_{kr}\) */
11\(V(G)\gets V(G)+v_{kr}\);
12
13
14 Step 2: Find the selected vertex \(v_{ps}\)
15 Each vertex \(v_{ij}\in V(G)\) is associated with \(T_{i}\), \(t_{i}\), \(l_{i}\);
16 Each data item \(d_{j}\in D\) is associated with \(N(d_{j})\);
17 Initialize \(MAX\gets 0\);
18 for each\(v_{ij}\in V(G)\)do
19\(P\leftarrow\) Invoke the underlying scheduling algorithm with \(T_{i}\), \(t_{i}\), \(l_{i}\), \(N(d_{j})\);
20 if\(P>MAX\)then
21\(MAX\gets P\);
22\(v_{ps}\leftarrow v_{ij}\);
23
24
25 Step 3: Encode and broadcast the encoded packet \(\beta(\delta_{max}^{v_{ps}})\)
26 Find the maximal clique \(\delta_{max}^{v_{ps}}\) for the selected vertex \(v_{ps}\);
27 Form the encoded packet \(\beta(\delta_{max}^{v_{ps}})\leftarrow\{d_{1}\oplus d_{2}\oplus\cdots\oplus d_{ k}\}\); \(k\leq|\delta_{max}^{v_{ps}}|\);
28 Broadcast \(\beta(\delta_{max}^{v_{ps}})\);
29/* Update \(G(V,E)\) */
30 for each\(v_{ij}\in\delta_{max}^{v_{ps}}\)do
41\(V(G)\gets V(G)-v_{ij}\);
```  
**Algorithm 1**Heuristic coding-based on-demand broadcast. **Step 1: CR-graph \(G(V,E)\) construction**  
Upon a request arrival from a client \(c_{k}\) for the data item \(d_{r}\), the corresponding vertex \(v_{kr}\) will be added in the vertex set \(V(G)\). According the edge definition as defined in Definition 1, all the possible edges are formed for \(v_{kr}\) with the vertices in \(V(G)\). **Step 2: Finding the selected vertex \(v_{ps}\)**  
Based on the associated weights of a vertex \(v_{i}\), namely \(t_{i}\), \(T_{i}\), \(l_{i}\), and the associated weight of the requested data item \(d_{j}\), namely \(N(d_{j})\), a particular scheduling algorithm selects a vertex \(v_{ps}\) with the highest scheduling priority value (\(P\)) among all the vertices in \(V(G)\). For instance, EDF selects the vertex \(v_{ps}\) with the lowest \(T_{p}\) value, MRF selects a vertex \(v_{ps}\) with the highest \(N(d_{s})\), LTSF selectsa vertex \(v_{ps}\) with the highest \(\frac{t_{p}}{\frac{1}{\hbar}}\) value. The details of \(v_{ps}\) selection criteria of each of the scheduling algorithms are shown in Section 4.2. **Step 3: Encoding and broadcasting the encoded packet \(\beta(\delta^{v_{ps}}_{max})\)**  
After finding the selected vertex \(v_{ps}\), in this step the heuristic approach finds the maximal clique \(\delta^{v_{ps}}_{max}\) which covers \(v_{ps}\). For finding the maximal clique, we use the approach presented in [11], in which only the adjacent vertices of \(v_{ps}\) (directly connected vertices with \(v_{ps}\)) are checked for finding the maximal clique. After finding the maximal clique \(\delta^{v_{ps}}_{max}\), the next job is to encode the packet \(\beta(\delta^{v_{ps}}_{max})\) which consists all the corresponding data items in \(\delta^{v_{ps}}_{max}\). After broadcasting \(\beta(\delta^{v_{ps}}_{max})\), the system updates the CR-graph \(G\). For \(n\) number of vertices the Step 1 has \(O(n)\) complexity, Step 2 must search the selected vertex \(v_{ps}\) which incurs \(O(n)\) complexity, and the Step 3 needs to find the maximal clique for a specific selected vertex \(v_{ps}\) from the constructed (in Step 1) CR-graph \(G\), which incurs \(O(n^{3})\) complexity. As both encoding and decoding operations are performed using bitwise XOR (exclusive-OR) technique, the decoding can be performed with one single operation at each client. Therefore, decoding only incurs constant complexity \(O(1)\). Hence, for each client, the decoding complexity is \(O(1)\).