{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:51:33Z","timestamp":1760241093184,"version":"build-2065373602"},"reference-count":51,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T00:00:00Z","timestamp":1574726400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>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\u2019 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\u2014real-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.<\/jats:p>","DOI":"10.3390\/fi11120248","type":"journal-article","created":{"date-parts":[[2019,11,26]],"date-time":"2019-11-26T10:57:27Z","timestamp":1574765847000},"page":"248","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Performance Analysis of On-Demand Scheduling with and without Network Coding in Wireless Broadcast"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5861-0475","authenticated-orcid":false,"given":"G. G. Md. Nawaz","family":"Ali","sequence":"first","affiliation":[{"name":"Department of Applied Computer Science, University of Charleston, Charleston, WV 25304, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor C. S.","family":"Lee","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuxuan","family":"Meng","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5375-8961","authenticated-orcid":false,"given":"Peter H. J.","family":"Chong","sequence":"additional","affiliation":[{"name":"Department of Electrical and Electronic Engineering, Auckland University of Technology, Auckland 1010, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Information Management, Wuhan University, Wuhan 430072, Hubei, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,11,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.ins.2017.01.012","article-title":"Coding-based Cooperative Caching in On-demand Data Broadcast Environments","volume":"385","author":"Ji","year":"2017","journal-title":"Inf. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1109\/TBC.2014.2364533","article-title":"Admission Control-Based Multichannel Data Broadcasting for Real-Time Multi-Item Queries","volume":"60","author":"Ali","year":"2014","journal-title":"IEEE Trans. Broadcast."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"38:1","DOI":"10.1145\/3329865","article-title":"Cooperative Cache Transfer-based On-demand Network Coded Broadcast in Vehicular Networks","volume":"18","author":"Ali","year":"2019","journal-title":"ACM Trans. Embed. Comput. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1109\/90.811450","article-title":"R \u00d7 W: A scheduling approach for large-scale on-demand data broadcast","volume":"7","author":"Aksoy","year":"1999","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1002\/dac.1098","article-title":"Performance Analysis of data scheduling algorithms for multi-item requests in multi-channel broadcast environments","volume":"23","author":"Liu","year":"2010","journal-title":"J. Commun. Syst."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/JSAC.2012.120511","article-title":"Efficient Data Dissemination in Vehicular Ad Hoc Networks","volume":"30","author":"Ye","year":"2012","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.comcom.2016.04.007","article-title":"An adaptive relay nodes selection scheme for multi-hop broadcast in {VANETs}","volume":"87","author":"Rehman","year":"2016","journal-title":"Comput. Commun."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2419","DOI":"10.1109\/TITS.2014.2316006","article-title":"Temporal data dissemination in vehicular cyber\u2013physical systems","volume":"15","author":"Liu","year":"2014","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/TPDS.2006.14","article-title":"Time-critical on-demand data broadcast: Algorithms, analysis, and performance evaluation","volume":"17","author":"Xu","year":"2006","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"4336","DOI":"10.1016\/j.ins.2010.07.030","article-title":"On-demand broadcast for multiple-item requests in a multiple-channel environment","volume":"180","author":"Liu","year":"2010","journal-title":"Inf. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.ins.2012.12.044","article-title":"Efficient processing of requests with network coding in on-demand data broadcast environments","volume":"232","author":"Chen","year":"2013","journal-title":"Inf. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1204","DOI":"10.1109\/18.850663","article-title":"Network information flow","volume":"46","author":"Ahlswede","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"4413","DOI":"10.1109\/TIT.2006.881746","article-title":"A Random Linear Network Coding Approach to Multicast","volume":"52","author":"Ho","year":"2006","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1284","DOI":"10.1109\/TWC.2014.010214.122008","article-title":"Reliable Periodic Safety Message Broadcasting in VANETs Using Network Coding","volume":"13","author":"Hassanabadi","year":"2014","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.comcom.2013.09.006","article-title":"Online {XOR} packet coding: Efficient single-hop wireless multicasting with low decoding delay","volume":"39","author":"Qureshi","year":"2014","journal-title":"Comput. Commun."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.comcom.2015.09.026","article-title":"Spacetime efficient network coding for wireless multi-hop networks","volume":"73","author":"Yan","year":"2016","journal-title":"Comput. Commun."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"3774","DOI":"10.1109\/TWC.2011.092011.101652","article-title":"Coding-based data broadcast scheduling in on-demand broadcast","volume":"10","author":"Zhan","year":"2011","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1109\/TVT.2011.2172010","article-title":"Blind xor: Low-Overhead Loss Recovery for Vehicular Safety Communications","volume":"61","author":"Wang","year":"2012","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Chaudhry, M.A.R., and Sprintson, A. (2008, January 13\u201318). Efficient algorithms for Index Coding. Proceedings of the IEEE INFOCOM Workshops 2008, Phoenix, AZ, USA.","DOI":"10.1109\/INFOCOM.2008.4544612"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Shujuan Wang, C.Y., and Yu, Z. (2016). Efficient Coding-Based Scheduling for Multi-Item Requests in Real-Time On-Demand Data Dissemination. Mob. Inf. Syst., 2016.","DOI":"10.1155\/2016\/4320781"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"3361","DOI":"10.1109\/TVT.2016.2589460","article-title":"Efficient Cache Management for Network-Coding-Assisted Data Broadcast","volume":"66","author":"Chen","year":"2017","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"4683","DOI":"10.1109\/TCOMM.2019.2906305","article-title":"An Approximation Algorithm for Optimal Clique Cover Delivery in Coded Caching","volume":"67","author":"Asghari","year":"2019","journal-title":"IEEE Trans. Commun."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2127","DOI":"10.1016\/j.jss.2013.03.073","article-title":"Supporting real-time multiple data items query in multi-RSU vehicular ad hoc networks (VANETs)","volume":"86","author":"Ali","year":"2013","journal-title":"J. Syst. Softw."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1759","DOI":"10.1109\/TNET.2015.2432804","article-title":"Cooperative Data Scheduling in Hybrid Vehicular Ad Hoc Networks: VANET as a Software Defined Network","volume":"24","author":"Liu","year":"2016","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_25","unstructured":"Xuan, P., Sen, S., Gonzalez, O., Fernandez, J., and Ramamritham, K. (1997, January 9\u201311). Broadcast on demand: Efficient and timely dissemination of data in mobile environments. Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS\u201997), Montreal, QC, Canada."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1109\/TC.1985.1676645","article-title":"Analysis of broadcast delivery in a videotex system","volume":"100","author":"Wong","year":"1985","journal-title":"IEEE Trans. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1566","DOI":"10.1109\/5.16350","article-title":"Broadcast delivery","volume":"76","author":"Wong","year":"1988","journal-title":"Proc. IEEE"},{"key":"ref_28","unstructured":"Sharaf, M.A., and Chrysanthis, P.K. (2002, January 23\u201324). On-demand broadcast: New challenges and scheduling algorithms. Proceedings of the 1st Hellenic Data Management Symposium (HDMS\u201902), Athens, Greece."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Acharya, S., and Muthukrishnan, S. (1998, January 25\u201330). Scheduling on-demand broadcasts: New metrics and algorithms. Proceedings of the 4th Annual ACM\/IEEE International Conference on Mobile Computing and Networking (MobiCom\u201998), Dallas, TX, USA.","DOI":"10.1145\/288235.288248"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Miller, R., Thatcher, J., and Bohlinger, J. (1972). Reducibility among Combinatorial Problems. Complexity of Computer Computations, Springer.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","article-title":"A fast algorithm for the maximum clique problem","volume":"120","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Hu, C.L. (2007, January 24\u201328). Fair scheduling for on-demand time-critical data broadcast. Proceedings of the IEEE International Conference on Communications (ICC\u201907), Glasgow, UK.","DOI":"10.1109\/ICC.2007.966"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.is.2008.05.004","article-title":"On optimal scheduling for time-constrained services in multi-channel data dissemination systems","volume":"34","author":"Chen","year":"2009","journal-title":"Inf. Syst."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1337","DOI":"10.1016\/j.jss.2010.01.034","article-title":"On the performance of real-time multi-item request scheduling in data broadcast environments","volume":"83","author":"Chen","year":"2010","journal-title":"J. Syst. Softw."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.jss.2015.01.022","article-title":"On-demand data broadcast with deadlines for avoiding conflicts in wireless networks","volume":"103","author":"He","year":"2015","journal-title":"J. Syst. Softw."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1002\/dac.2343","article-title":"On low-complexity adaptive wireless push-based data broadcasting","volume":"27","author":"Polatoglou","year":"2014","journal-title":"Int. J. Commun. Syst."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"2427","DOI":"10.1109\/TC.2012.139","article-title":"Optimal Data Retrieval Scheduling in the Multichannel Wireless Broadcast Environments","volume":"62","author":"Lu","year":"2013","journal-title":"IEEE Trans. Comput."},{"key":"ref_38","unstructured":"Wu, Y., and Cao, G. (2001, January 15\u201317). Stretch-optimal scheduling for on-demand data broadcasts. Proceedings of the 10th International Conference on Computer, Communications and Networks (ICCCN\u201901), Scottsdale, AZ, USA."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/s11241-006-7982-5","article-title":"Scheduling Real-time Requests in On-demand Data Broadcast Environments","volume":"34","author":"Lee","year":"2006","journal-title":"Real-Time Syst."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.comcom.2015.05.001","article-title":"On the performance of network coding and forwarding schemes with different degrees of redundancy for wireless mesh networks","volume":"72","author":"Ploumidis","year":"2015","journal-title":"Comput. Commun."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1002\/wcm.2505","article-title":"DCNC: Throughput maximization via delay controlled network coding for wireless mesh networks","volume":"16","author":"Qu","year":"2014","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Chu, C.H., Yang, D.N., and Chen, M.S. (2008, January 27\u201330). Multi-data delivery based on network coding in on-demand broadcast. Proceedings of the Ninth International Conference on Mobile Data Management, Beijing, China.","DOI":"10.1109\/MDM.2008.25"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"3657","DOI":"10.1002\/dac.2565","article-title":"An Enhanced XOR-based Scheme for Wireless Packet Retransmission Problem","volume":"27","author":"Gao","year":"2014","journal-title":"Int. J. Commun. Syst."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Chen, J., Lee, V.C.S., and Zhan, C. (2009;, January 24\u201326). Efficient Processing of Real-Time Multi-item Requests with Network Coding in On-demand Broadcast Environments. Proceedings of the 2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Beijing, China.","DOI":"10.1109\/RTCSA.2009.20"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"6774","DOI":"10.1109\/TVT.2018.2820458","article-title":"Analysis and Improvement of Reliability Through Coding for Safety Message Broadcasting in Urban Vehicular Networks","volume":"67","author":"Ali","year":"2018","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Sorour, S., and Valaee, S. (2010, January 23\u201327). On minimizing broadcast completion delay for instantly decodable network coding. Proceedings of the IEEE International Conference on Communications (ICC\u201910), Cape Town, South Africa.","DOI":"10.1109\/ICC.2010.5502758"},{"key":"ref_47","unstructured":"Schwetman, H. (2001, January 9\u201312). CSIM19: A powerful tool for building system models. Proceedings of the 33nd Conference on Winter Simulation (WSC\u201901), Arlington, VA, USA."},{"key":"ref_48","unstructured":"Zipf, G. (1949). Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology, Addison-Wesley Press."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1109\/TKDE.2004.1264827","article-title":"Performance evaluation of an optimal cache replacement policy for wireless data dissemination","volume":"16","author":"Xu","year":"2004","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1016\/j.jss.2016.04.005","article-title":"Efficient data dissemination in cooperative multi-RSU Vehicular Ad Hoc Networks (VANETs)","volume":"117","author":"Ali","year":"2016","journal-title":"J. Syst. Softw."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"3499","DOI":"10.1109\/JIOT.2018.2830315","article-title":"Efficient Real-Time Coding-Assisted Heterogeneous Data Access in Vehicular Networks","volume":"5","author":"Ali","year":"2018","journal-title":"IEEE Internet Things J."}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/11\/12\/248\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:37:42Z","timestamp":1760189862000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/11\/12\/248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,26]]},"references-count":51,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2019,12]]}},"alternative-id":["fi11120248"],"URL":"https:\/\/doi.org\/10.3390\/fi11120248","relation":{},"ISSN":["1999-5903"],"issn-type":[{"type":"electronic","value":"1999-5903"}],"subject":[],"published":{"date-parts":[[2019,11,26]]}}}