# Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast
## 3 System Model
### Coding-Based On-Demand Broadcast  
Recalling \(v_{ij}\) denotes a client \(c_{i}\) for the requested data item \(d_{j}\). For simplicity, we assume that the vertices in the graph are denoted by \(v_{1},\ v_{2},\ \cdots,\ v_{n}\), where \(n\) is number of vertices. Please note that this simple assumption does not refrain a vertex to also denote the corresponding requested data item. \(v_{i}\) corresponds to the request \(c_{i}\), where \(v_{i}\in V(G)\) and \(1\leq i\leq n\). A vertex \(v_{i}\) is associated with three weights, namely \(t_{i},\ l_{i},\ and\ T_{i}\), which represent the waiting time, the item size and the slack time, respectively. A data item \(d_{j}\) is also associated with a weight \(N(d_{j})\), which represents the popularity, namely the number of pending requests for \(d_{j}\). The broadcast channel bandwidth is \(B\). The relationships between the scheduling objectives and the properties of the cliques are stated as follows.  
* Relationship 1: Real-time scheduling algorithms which aim to serve the request with the minimum slack time such as EDF, should select the largest clique \(\delta\) which includes the vertex \(v_{i}\) with the largest \(\frac{1}{T_{i}}\) value. The other real-time algorithm SIN, also considers popularity in addition of slack time.
* Relationship 2: Non-real-time scheduling algorithms which aim to serve the request with the longest waiting time such as FCFS, should select the largest clique \(\delta\) which includes the vertex \(v_{i}\) with the largest \(t_{i}\) value.
* Relationship 3: Non-real-time scheduling algorithms which aim to broadcast the data item with the highest popularity such as MRF, should select the largest clique \(\delta\) which includes the maximum number of vertices. The working properties of other non-real-time algorithms are the combination of the properties of FCFS (waiting time) and MRF (data item popularity), such as LWF and R\(\times\)W, both consider waiting time and data item popularity for scheduling.
* Relationship 4: Stretch optimal scheduling algorithms which aim to reduce the stretch such as LTSF, should select the clique \(\delta\) which has the maximum current stretch, namely with the maximum summation of \(\frac{t_{i}}{T_{i}}\) value. The other stretch optimal scheduling algorithm STOBS considers data item popularity in addition of request waiting time and data item size.  
The relationships of all the algorithms are summarized in Table 2. From the above relationships it is understandable that to migrate the traditional scheduling algorithms into the network coding versions by exploiting the full coding benefits, we need to find the maximum clique \(\delta_{max}\) in the graph \(G(V,E)\). This is because the number of satisfying clients is equivalent to the number of vertices in \(\delta_{max}\). However, finding the maximum clique is a well-known NP-complete problem in graph theory [30]. This is computationally expensive, because the new maximum clique needs to find out every time before making a broadcast decision. This turns out applying network coding in on-demand broadcast may be infeasible in practice. Hence in the following we propose a heuristic coding-based approach to convert the traditional scheduling algorithms into the coding version in polynomial time, while preserving the original scheduling criteria.