# Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast
###### Abstract  
On-demand broadcast is a scalable approach to disseminating information to a large population of clients while satisfying dynamic needs of clients, such as in vehicular networks. However, in conventional broadcast approaches, only one data item can be retrieved by clients in one broadcast tick. To further improve the efficiency of wireless bandwidth, in this work, we conduct a comprehensive study on incorporating network coding with representative on-demand scheduling algorithms while preserving their original scheduling criteria. In particular, a graph model is derived to maximize the coding benefit based on the clients' requested and cached data items. Furthermore, we propose a heuristic coding-based approach, which is applicable for all the on-demand scheduling algorithms with low computational complexity. In addition, based on various application requirements, we classify the existing on-demand scheduling algorithms into three groups--real-time, non-real-time and stretch optimal. In view of different application-specific objectives, we implement the coding versions of representative algorithms in each group. Extensive simulation results conclusively demonstrate the superiority of coding versions of algorithms against their non-coding versions on achieving their respective scheduling objectives. network coding; on-demand broadcasting; data scheduling algorithm; performance evaluation +
Footnote †: journal:  
0000-0001-9991-558X/0000-0000-0000-0000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-000000-00000-000000-00000-0000  
dissemination services [9]. In this work, we focus on further improving the bandwidth efficiency of on-demand broadcast by exploiting network coding. Several previous studies have focused on on-demand broadcasting [9; 10; 11], which have different application-specific performance objectives. In a broadcast tick (transmission time of a unit-sized data item), these strategies only able to broadcast a single data item. This restriction hinders the further improvement of broadcast bandwidth efficiency. In contrast, network coding [12] can transmit multiple data items through an encoded packet in a broadcast tick. We observe that an inherited advantage of on-demand broadcast is having the feedback information from clients to the server, and hence applying network coding in on-demand broadcast does not require additional overhead for explicit feedback. A variety of network coding techniques have been studied. Random linear network coding (RLNC) [13] is suitable for push-based broadcast, especially for broadcasting popular contents which may serve a large population of clients [6; 14], such as periodic safety message, traffic information, etc. However, RLNC is not adaptive to customized services, such as mobile infotainment, gas station query, parking space query, etc. To support such services, the server needs to receive explicit on-demand requests from clients, so that it can provide services by encoding corresponding data items accordingly. XOR (\(\oplus\))-based network coding is a suitable candidate for such cases, as it has very low encoding and decoding overhead and it is simple to be implemented [15]. Many studies have applied XOR-based coding for improving network throughput [15; 16; 17] and enhancing packet delivery ratio [18]. [PERSON] and [PERSON] [19] introduced the index coding problem in wireless multicast network leveraging the network coding and opportunistic listening techniques. [PERSON] et al. [20] studied the network coding-based approach for minimizing deadline misses of real-time multi-item requests. [PERSON] et al. [21] proposed a decoding-oriented cache management scheme in coding-assisted broadcast for reducing the overall response time. [PERSON] et al. [22] proposed a coded multicast delivery strategy for reducing the bandwidth usages in content placement problem.