{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:26:38Z","timestamp":1760243198569,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2014,11,4]],"date-time":"2014-11-04T00:00:00Z","timestamp":1415059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JSAN"],"abstract":"<jats:p>Network coding techniques are usually applied upon network-layer protocols to improve throughput in wireless networks. In scenarios with multiple unicast sessions, fairness is also an important factor. Therefore, a network coding-aware packet-scheduling algorithm is required. A packet-scheduling algorithm determines which packet to send next from a node\u2019s packet backlog. Existing protocols mostly employ a basic round-robin scheduling algorithm to give \u201cequal\u201d opportunities to different packet flows. In fact, this \u201cequal\u201d-opportunity scheduling is neither fair, nor efficient. This paper intends to accentuate the importance of a coding-aware scheduling scheme. With a good scheduling scheme, we can gain more control over the per-flow throughput and fairness. Specifically, we first formulate a static scheduling problem and propose an algorithm to find the optimal scheduling scheme. We then extend the technique to a dynamic setting and, later, to practical routing protocols. Results show that the algorithm is comparatively scalable, and it can improve the throughput gain when the network is not severely saturated. The fairness among flows is drastically improved as a result of this scheduling scheme.<\/jats:p>","DOI":"10.3390\/jsan3040274","type":"journal-article","created":{"date-parts":[[2014,11,4]],"date-time":"2014-11-04T09:41:15Z","timestamp":1415094075000},"page":"274-296","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Towards a Fair and Efficient Packet Scheduling Scheme in Inter-Flow Network Coding"],"prefix":"10.3390","volume":"3","author":[{"given":"Jin","family":"Wang","sequence":"first","affiliation":[{"name":"National University of Singapore, #02-02-10, AMI Lab, IDMI, 21 Heng Mui Keng Terrace,119613, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Teck","family":"Chai","sequence":"additional","affiliation":[{"name":"Institute for Infocomm Research, 1 Fusionopolis Way, #20-10 Connexis North Tower, 138632, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wai-Choong","family":"Wong","sequence":"additional","affiliation":[{"name":"National University of Singapore, #02-02-10, AMI Lab, IDMI, 21 Heng Mui Keng Terrace,119613, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,11,4]]},"reference":[{"key":"ref_1","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_2","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1109\/TIT.2002.807285","article-title":"Linear network coding","volume":"49","author":"Li","year":"2003","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1109\/TNET.2008.923722","article-title":"XORs in the air: Practical wireless network coding","volume":"16","author":"Katti","year":"2008","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1109\/TMC.2009.160","article-title":"DCAR: Distributed Coding-Aware Routing in Wireless Networks","volume":"9","author":"Le","year":"2010","journal-title":"IEEE Trans. Mobile Comput."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Fragouli, C., Katabi, D., Markopoulou, A., Medard, M., and Rahul, H. (2007, January 29\u201331). Wireless network coding: Opportunities & challenges. Proceedings of the Military Communications Conference (MILCOM 2007), Orlando, FL, USA.","DOI":"10.1109\/MILCOM.2007.4454988"},{"key":"ref_6","unstructured":"Sagduyu, Y., and Ephremides, A. (2005, January 3\u20137). Joint scheduling and wireless network coding. Proceedings of the WINMEE, RAWNET and NETCOD 2005 Workshops, Trentino, Italy."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Fasolo, E., Rossi, M., Widmer, J., and Zorzi, M. (2007, January 24\u201328). On MAC scheduling and packet combination strategies for practical random network coding. Proceedings of the IEEE International Conference on Communications (ICC 2007), Glasgow, UK.","DOI":"10.1109\/ICC.2007.591"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Shabdanov, S., Rosenberg, C., and Mitran, P. (2011, January 9\u201313). Joint routing, scheduling, and network coding for wireless multihop networks. Proceedings of the 9th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt 2011), Princeton, NJ, USA.","DOI":"10.1109\/WIOPT.2011.5930037"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Jones, N., Shrader, B., and Modiano, E. (2012, January 25\u201330). Optimal routing and scheduling for a simple network coding scheme. Proceedings of the 31st IEEE International Conference on Computer Communications (INFOCOM 2012), Orlando, FL, USA.","DOI":"10.1109\/INFCOM.2012.6195772"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Yomo, H., and Popovski, P. (2007, January 24\u201328). Opportunistic scheduling for wireless network coding. Proceedings of the IEEE International Conference on Communications (ICC 2007), Glasgow, UK.","DOI":"10.1109\/ICC.2007.930"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ni, B., Santhapuri, N., Gray, C., and Nelakuditi, S. (2008, January 16\u201320). Selection of bit-rate for wireless network coding. Proceedings of the 5th IEEE Annual Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks Workshops, San Francisco, CA, USA.","DOI":"10.1109\/SAHCNW.2008.31"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Chaporkar, P., and Proutiere, A. (2007, January 9\u201314). Adaptive network coding and scheduling for maximizing throughput in wireless networks. Proceedings of the 13th Annual International Conference on Mobile Computing and Networking (MobiCom 2007), Montreal, QC, Canada.","DOI":"10.1145\/1287853.1287870"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Zhao, M., and Yang, Y. (2009, January 12\u201315). Packet scheduling with joint design of MIMO and network coding. Proceedings of the IEEE 6th International Conference on Mobile Adhoc and Sensor Systems (MASS \u201909), Macau.","DOI":"10.1109\/MOBHOC.2009.5336992"},{"key":"ref_14","unstructured":"Karp, R. (2010). 50 Years of Integer Programming 1958\u20132008, Springer."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0012-365X(82)90169-8","article-title":"A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs","volume":"38","author":"Hsu","year":"1982","journal-title":"Discret. Math."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/S0304-0208(08)72944-X","article-title":"Algorithms for maximum weight cliques, minimum weighted clique covers and minimum colorings of claw-free perfect graphs","volume":"88","author":"Hsu","year":"1984","journal-title":"Top. Perfect Graphs"},{"key":"ref_17","unstructured":"Berge, C., and Minieka, C. (1973). Graphs and Hypergraphs, North-Holland Publishing Company."},{"key":"ref_18","unstructured":"Bonomo, F., Oriolo, G., and Snels, C. (2012). Graph-Theoretic Concepts in Computer Science, Springer."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Le, J., Lui, J., and Chiu, D. (2008, January 13\u201318). How many packets can we encode?\u2014An analysis of practical wireless network coding. Proceedings of the 27th IEEE International Conference on Computer Communications (INFOCOM 2008), Phoenix, AZ, USA.","DOI":"10.1109\/INFOCOM.2008.83"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","article-title":"Random graphs","volume":"30","author":"Gilbert","year":"1959","journal-title":"Ann. Math. Stat."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1177\/0037549705058073","article-title":"Mason: A multi-agent simulation environment","volume":"81","author":"Luke","year":"2005","journal-title":"Simul.: Trans. Soc. Model. Simul. Int."},{"key":"ref_22","unstructured":"Wang, J., Zhu, C., Guo, Q., Chai, T., and Wong, W. (2012, January 12\u201314). SCAR: A dynamic coding-aware routing protocol. Proceedings of the Sixth International Conference on Signal Processing and Communication Systems (ICSPCS 2012), Gold Coast, QLD."},{"key":"ref_23","first-page":"139","article-title":"others. DSR: The dynamic source routing protocol for multi-hop wireless ad hoc networks","volume":"5","author":"Johnson","year":"2001","journal-title":"Ad Hoc Netw."}],"container-title":["Journal of Sensor and Actuator Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2224-2708\/3\/4\/274\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:08:55Z","timestamp":1760216935000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2224-2708\/3\/4\/274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,4]]},"references-count":23,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2014,12]]}},"alternative-id":["jsan3040274"],"URL":"https:\/\/doi.org\/10.3390\/jsan3040274","relation":{},"ISSN":["2224-2708"],"issn-type":[{"type":"electronic","value":"2224-2708"}],"subject":[],"published":{"date-parts":[[2014,11,4]]}}}