# Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast
## 2 Related Works
### Network Coding  
Random linear network coding (RLNC) is initially proposed for the transmission and compression of information in multi-source multicast networks ([PERSON] and [PERSON], 1998). [PERSON] et al. (2016) applied RLNC for pushing popular contents from a single sever to multiple clients. [PERSON] and [PERSON] (2014) proposed to apply RLNC for repetitive reliable safety message rebroadcasting in the congested wireless channel. [PERSON] et al. (2017) analyzed the throughput and delay in wireless mesh networks incorporating RLNC. [PERSON] et al. (2017) also studied the tradeoff between the throughput and decoding delay in applying RLNC in wireless mesh networks, and proposed a protocol named DCNC (Delay Controlled Network Coding). However, as in RLNC, the random coefficients need to be attached with the coded message, the coding overhead can be significant in a congested network. To reduce the overhead, a number of studies have considered XOR-based network coding in on-demand broadcast. [PERSON] et al. (2018) proposed On-demand Encoding (OE) algorithm for reducing clients' access time in on-demand broadcast. However, OE can only encode two data items in an encoded packet, and hence it is not flexible, and it cannot maximize the coding benefit. [PERSON] and [PERSON] (2018) transformed the on-demand broadcast coding problem to the Boolean satisfiability (SAT) problem. They proposed several heuristic solutions based on graph coloring and color saving algorithms. [PERSON] et al. (2018) studied XOR coding for packet retransmission in erroneous wireless medium. [PERSON] et al. (2018) proposed an on-demand broadcast algorithm called ADC (Adaptive Demand-oriented Coding) for serving multi-item requests. In ([PERSON] et al., 2018), [PERSON] et al. proposed ADC-1 and ADC-2, where ADC-1 considers scheduling and network coding operations separately, and in ADC-2, these two operations are considered integrally. [PERSON] et al. (2018) proposed a model for constructing encoding packet with several data items. The proposed approach greedily finds maximal cliques based on constructed graph model to find an approximate solution to the formulated coding problem. [PERSON] et al. (2018) proposed network coded opportunistic relaying for improving data dissemination performance.  
In summary, to improve the scheduling performance by further exploring the strength of on-demand broadcast, it is desirable to adopt network coding into data broadcast. With network coding,different data items can be encoded into one packet. Since different coding strategies have different impacts on scheduling performance, in this paper, we propose a general heuristic coding-based on-demand broadcast scheme, by which the data scheduling problem can be transformed to the maximal clique problem. With the proposed approach, existing on-demand scheduling algorithms can be migrated into their corresponding coding versions while preserving their original criteria in scheduling data items. In addition, this work validates the advantage of applying network coding in on-demand scheduling through a comprehensive simulation study.