# Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast
###### Abstract
With respect to the different performance objectives, the on-demand scheduling algorithms can be classified into three groups: _real-time, non-real-time_ and _stretch optimal_ scheduling algorithms. Specifically, in real-time scheduling, the primary objective is to minimize the deadline miss ratio, namely serving as many requests as possible before their deadlines expire. For instance, in vehicular networks, real-time traffic information must be broadcast to vehicles with certain time-constraint (e.g., must serve before a vehicle exits the service range of a road-side unit) [23; 24]. Representative real-time scheduling algorithms include EDF (Earliest Deadline First) [25] and SIN (Slack time Inverse Number of pending requests) [9]. In non-real-time scheduling, the primary objective is to minimize the average response time, namely serving the requests as soon as possible. For instance, mobile clients wish to receive non-real-time infotainment information as soon as possible [10]. Representative non-real-time scheduling algorithms include FCFS (Fist Come First Served) [26], MRF (Most Requested First) [27], LWF (Longest Wait First) [27] and R \(\times\) W (Number of Pending Request Multiply Waiting Time) [4]. In stretch optimal scheduling, the primary objective is to minimize the stretch, which is the ratio of the response time to the service time, where the service time refers to the transmission time of the data items. For instance, fairness treatment to different size requests in satellite networks, wireless LANs, cellular networks etc. [28]. Representative stretch optimal scheduling algorithms include LTSF (Longest Total Stretch First) [29] and STOBS (Summary Table On-demand Broadcast Scheduler) [28]. Although existing studies have considered to improve scheduling performance with respect to different application-specific objectives, they do not fully use the advantage of on-demand broadcast, where the server can be aware of the requested and cached data items of mobile clients. The impact of network coding on different scheduling objectives highly depends on the applied coding strategy at the server. In order to evaluate possible benefits brought by network coding, apparently, it is desirable to preserve the original scheduling criteria when applying network coding to existing on-demand scheduling algorithms. In this work, we will investigate the potential benefit of applying network coding into different groups of on-demand scheduling algorithms. The major contributions of this work are stated as follows. * We present a graph model, where a CR-graph (Cache-Request-graph) [11; 19] is formed based on the clients requested and cached data items for reducing redundant broadcasting. * We transform the scheduling problem to the problem of finding maximum clique in the derived CR-graph, which is a well-known NP-complete problem in graph theory [30; 31]. Accordingly, we propose a heuristic coding-based approach, which ensures that each scheduling algorithm will transform into its corresponding coding version while preserving its original scheduling criterion. * For the three groups of scheduling algorithms, namely real-time, non-real-time and stretch optimal, we select representative solutions in each group and present the detailed implementation of their coding versions with the proposed approach. * To evaluate the impact of network coding to different groups of algorithms, we build the simulation model for each group and define the used performance metrics. * We give a comprehensive performance evaluation, which demonstrates the efficiency of network coding on enhancing system performance with respect to different scheduling objectives under various circumstances. The rest of this paper is organized as follows. Section 2 reviews the related work. Section 3 presents the system model. Section 4 proposes a heuristic coding-based approach. We build the simulation model in Section 5. An extensive performance evaluation is conducted in Section 6. Finally, we conclude this work in Section 7.