Performance analysis and optimization for chunked network coding based wireless cooperative downloading systems

Abstract

Dense network coding (NC) is widely used in wireless cooperative downloading systems. Wireless devices have limited computing resources. Researchers have recently found that dense NC is not suitable because of its high coding complexity, and it is necessary to use chunked NC in wireless environments. However, chunked NC can cause more communications, and the amount of communications is affected by the chunk size. Therefore, setting a suitable chunk size to improve the overall perfor-mance of chunked NC is a prerequisite for applying it in wireless cooperative downloading systems. Most of the existing studies on chunked NC focus on centralized wireless broadcasting systems, which are different from wireless cooperative downloading systems with distributed features. Accordingly, we study the performance of chunked NC based wireless cooperative downloading systems. First, an analysis model is established using a Markov process taking the distributed features into consideration, and then the block collection completion time of encoded blocks for cooperative downloading is optimized based on the analysis model. Furthermore, queuing theory is used to model the decoding process of the chunked NC. Combining queuing theory with the analysis model, the decoding completion time for cooperative downloading is optimized, and the optimal chunk size is derived. Numerical simulation shows that the block collection completion time and the decode completion time can be largely reduced after optimization.

Keywords

Wireless environments / Cooperative downloading / Chunked network coding / Markov process

References

[1] Abdelrahman, O.H., Gelenbe, E., 2009. Approximate analysis of a round robin scheduling scheme for network coding. European Performance Engineering Workshop, p.212–217. https://doi.org/10.1007/978-3-642-02924-0_17

[2] Ahmed, S., Kanhere, S.S., 2006. VANETCODE: network coding to enhance cooperative downloading in vehicular ad-hoc networks. Int. Conf. on Wireless Communications and Mobile Computing, p.527–532. https://doi.org/10.1145/1143549.1143654

[3] Choi, J.M., So, J., Ko, Y.B., 2005. Numerical analysis of IEEE 802.11 broadcast scheme in multi-hop wireless ad hoc networks. ICOIN 2005: Information Networking, Con-vergence in Broadband and Mobile Networking, p.1–10. https://doi.org/10.1007/978-3-540-30582-8_1

[4] Chou, P.A., Wu, Y., Jain, K., 2003. Practical network coding. Allerton Conf. on Communication, Control and Compu-ting, p.40–49.

[5] Eryilmaz, A., Ozdaglar, A., Medard, M., , 2008. On the delay and throughput gains of coding in unreliable net-works. IEEE Trans. Inform. Theory, 54(12):5511–5524. https://doi.org/10.1109/TIT.2008.2006454

[6] Heidarzadeh, A., Banihashemi, A.H., 2010. Overlapped chunked network coding. IEEE Information Theory Workshop on Information Theory, p.1–5. https://doi.org/10.1109/ITWKSPS.2010.5503153

[7] Heidarzadeh, A., Banihashemi, A.H., 2012. Coding delay analysis of chunked codes over line networks. Int. Symp. on Network Coding, p.55–60. https://doi.org/10.1109/NETCOD.2012.6261884

[8] Heide, J., Pedersen, M.V., Fitzek, F.H.P., , 2009. Network coding for mobile devices—systematic binary random rateless codes. IEEE Int. Conf. on Communications Workshops, p.1–6. https://doi.org/10.1109/ICCW.2009.5208076

[9] Joshi, G., Soljanin, E., 2013. Round-robin overlapping gener-ations coding for fast content download. IEEE Int. Symp. on Information Theory Proc., p.2740–2744. https://doi.org/10.1109/ISIT.2013.6620725

[10] Lee, U., Park, J.S., Yeh, J., , 2006. CodeTorrent: content distribution using network coding in VANET. Int. Workshop on Decentralized Resource Sharing in Mobile Computing and Networking, p.1–5. https://doi.org/10.1145/1161252.1161254

[11] Li, M., Yang, Z., Lou, W., 2011. CodeOn: cooperative popular content distribution for vehicular networks using symbol level network coding. IEEE J. Sel. Area Commun., 29(1): 223–235. https://doi.org/10.1109/JSAC.2011.110121

[12] Li, Y., Soljanin, E., Spasojevic, P., 2011. Effects of the gen-eration size and overlap on throughput and complexity in randomized linear network coding. IEEE Trans. Inform. Theory, 57(2):1111–1123. https://doi.org/10.1109/TIT.2010.2095111

[13] Li, Y., Vingelmann, P., Pedersen, M.V., , 2012. Round-robin streaming with generations. Int. Symp. on Network Coding, p.143–148. https://doi.org/10.1109/NETCOD.2012.6261899

[14] Lucani, D.E., Medard, M., Stojanovic, M., 2009a. Broadcast-ing in time-division duplexing: a random linear network coding approach. Workshop on Network Coding, Theory, and Applications, p.62–67. https://doi.org/10.1109/NETCOD.2009.5191395

[15] Lucani, D.E., Medard, M., Stojanovic, M., 2009b. Random linear network coding for time-division duplexing: field size considerations. Global Telecommunications Conf., p.1–6. https://doi.org/10.1109/GLOCOM.2009.5425257

[16] Ma, X., Chen, X., 2007. Delay and broadcast reception rates of highway safety applications in vehicular ad hoc networks. Mobile Networking for Vehicular Environments, p.85–90. https://doi.org/10.1109/MOVE.2007.4300809

[17] Ma, X., Zhang, J., Wu, T., 2011. Reliability analysis of one- hop safety-critical broadcast services in VANETs. IEEE Trans. Veh. Technol., 60(8):3933–3946. https://doi.org/10.1109/TVT.2011.2165975

[18] Magli, E., Wang, M., Frossard, P., , 2013. Network cod-ing meets multimedia: a review. IEEE Trans. Multim., 15(5):1195–1212. https://doi.org/10.1109/TMM.2013.2241415

[19] Maymounkov, P., Harvey, N.J.A., Lun, D.S., 2006. Methods for efficient network coding. Annual Allerton Conf. on Communication, Control, and Computing, p.482–491.

[20] Militano, L., Iera, A., Scarcello, F., 2013. A fair cooperative content-sharing service. Comput. Netw., 57(9):1955–1973. https://doi.org/10.1016/j.comnet.2013.03.014

[21] Newman, D.J., 1960. The double dixie cup problem. Am. Math. Mon., 67(1):58–61. https://doi.org/10.2307/2308930

[22] Pyattaev, A., Galinina, O., Andreev, S., , 2015. Under-standing practical limitations of network coding for as-sisted proximate communication. IEEE J. Sel. Area Commun., 33(2):156–170. https://doi.org/10.1109/JSAC.2014.2384232

[23] Tang, Y.H., Tang, X.W., 2006. Queue Theory, Basis and Analysis Methods. Science Publishing House, Beijing, China, p.92–95 (in Chinese).

[24] Wang, G., Lin, Z., 2014. On the performance of multi-message algebraic gossip algorithms in dynamic random geomet-ric graphs. IEEE Commun. Lett., PP(99):1–1. https://doi.org/10.1109/LCOMM.2014.2344047

[25] Wang, M., Li, B., 2006. How practical is network coding? IEEE Int. Workshop on Quality of Service, p.274–278. https://doi.org/10.1109/IWQOS.2006.250480

[26] Yu, M., Aboutorab, N., Sadeghi, P., 2014. From instantly decodable to random linear network coded broadcast. IEEE Trans. Commun., 62(11):3943–3955. https://doi.org/10.1109/TCOMM.2014.2364198

[27] Zhang, J., Zhang, Q., Jia, W., 2007. A novel MAC protocol for cooperative downloading in vehicular networks. IEEE Global Telecommunications Conf., p.4974–4978. https://doi.org/10.1109/GLOCOM.2007.943

[28] Zhou, H., Liu, B., Luan, T.H., , 2014. ChainCluster: engineering a cooperative content distribution framework for highway vehicular communications. IEEE Trans. In-tell. Transp. Syst., 15(6):2644–2657. https://doi.org/10.1109/TITS.2014.2321293

RIGHTS & PERMISSIONS

2017 Zhejiang University and Springer-Verlag GmbH Germany