# Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast
## 4 Proposed Heuristic Coding-Based On-Demand Broadcast  
Recalling the objective of this work is to convert a traditional scheduling algorithm into the coding version with its original scheduling criteria along with maximizing the coding benefit by keeping the overhead minimal. Hence the key idea of the proposed heuristic coding-based approach is to broadcast the encoded packet, which (1) must contain the vertex corresponds to the scheduled client by the scheduling algorithm, and (2) satisfy as many clients as possible per broadcast by keeping the encoding complexity as minimal as possible. The proposed approach contains the following two important considerations. * Find the vertex, which holds the maximum priority value of the scheduling algorithm. If a data item \(d_{s}\in D\) of a client \(c_{p}\) is selected to broadcast, the corresponding vertex is \(v_{ps}\), we call as _selected vertex_. * To maximizing the exploitation of network coding and reducing encoding complexity, need to find the maximal clique \(\delta_{max}^{v_{ps}}\) (approximate maximum clique) which covers the selected vertex \(v_{ps}\). Please note that \(\delta_{max}^{v_{ps}}\) is the maximum among all the possible maximal cliques covering \(v_{ps}\) in \(G\). \(\delta_{max}^{v_{ps}}\) will be used to form the encoded packet \(\beta(\delta_{max}^{v_{ps}})\) for broadcasting. **Lemma 1**. : _For an arbitrary vertex \(v_{ij}\in\delta_{max}^{v_{ps}}\), the corresponding client \(c_{i}\in C_{\delta}\) can retrieve \(d_{j}\) from the encode packet \(\beta(\delta_{max}^{v_{ps}})\)._  
Proof. : As the proposed system is a closed system, which infers that one client can have only one pending request in the service queue. Hence, we can infer that all the vertices in a clique represents the unique clients. According to the clique definition, all the vertices in a clique are inter-connected. Again according to the edge definition of a CR-graph (Definition 1), a client only has edges with other clients if they request the same data item, or one client's cached data item is being requested by another client and vice versa. This implies that for a client \(c_{i}\in C_{\delta}\), if \(v_{ij}\in\delta_{max}^{v_{ps}}\), for \(K\geq 1\), \(c_{i}\) already has (in the cache) all the data items of \(\beta(\delta_{max}^{v_{ps}})\), except \(d_{j}\); otherwise all the vertices in \(\delta_{max}^{v_{ps}}\) requested for the same data item \(d_{j}\) and \(d_{j}=d_{s}\). Hence \(c_{i}\) can easily decode \(d_{j}\) from \(\beta(\delta_{max}^{v_{ps}})\) with its cached data items. **Lemma 2**. : _Broadcasting the encoded packet \(\beta(\delta_{max}^{v_{ps}})\) for the selected vertex \(v_{ps}\), ensures the migration of a scheduling algorithm into the coding version with preserving its original scheduling criteria._  
Proof. : The proposed coding-based system first selects the selected vertex \(v_{ps}\), then finds the maximal clique \(\delta_{max}^{v_{ps}}\), which covers \(v_{ps}\). Please note that \(v_{ps}\) is the highest priority vertex based on the scheduling criteria of a scheduling algorithm. For instance, in the real-time model, for EDF scheduling, \(v_{ps}\) is vertex with the vertex with the highest urgency; in the non-real-time model, for FCFS scheduling, \(v_{ps}\) is vertex with the longest waiting time; in the stretch optimal model, for LTSF scheduling, \(v_{ps}\) is vertex with the longest stretch. After selecting \(v_{ps}\), the maximal clique \(\delta_{max}^{v_{ps}}\) is found from the CR-graph \(G\), which cover \(v_{ps}\)