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 performance 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.

基于分代网络编码的无线协作下载系统性能分析和优化方法

[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.

[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.

[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, Convergence in Broadband and Mobile Networking, p.1-10.

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

[5]Eryilmaz, A., Ozdaglar, A., Medard, M., et al., 2008. On the delay and throughput gains of coding in unreliable networks. IEEE Trans. Inform. Theory, 54(12):5511-5524.

[6]Heidarzadeh, A., Banihashemi, A.H., 2010. Overlapped chunked network coding. IEEE Information Theory Workshop on Information Theory, p.1-5.

[7]Heidarzadeh, A., Banihashemi, A.H., 2012. Coding delay analysis of chunked codes over line networks. Int. Symp. on Network Coding, p.55-60.

[8]Heide, J., Pedersen, M.V., Fitzek, F.H.P., et al., 2009. Network coding for mobile devices—systematic binary random rateless codes. IEEE Int. Conf. on Communications Workshops, p.1-6.

[9]Joshi, G., Soljanin, E., 2013. Round-robin overlapping generations coding for fast content download. IEEE Int. Symp. on Information Theory Proc., p.2740-2744.

[10]Lee, U., Park, J.S., Yeh, J., et al., 2006. CodeTorrent: content distribution using network coding in VANET. Int. Workshop on Decentralized Resource Sharing in Mobile Computing and Networking, p.1-5.

[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.

[12]Li, Y., Soljanin, E., Spasojevic, P., 2011. Effects of the generation size and overlap on throughput and complexity in randomized linear network coding. IEEE Trans. Inform. Theory, 57(2):1111-1123.

[13]Li, Y., Vingelmann, P., Pedersen, M.V., et al., 2012. Round-robin streaming with generations. Int. Symp. on Network Coding, p.143-148.

[14]Lucani, D.E., Medard, M., Stojanovic, M., 2009a. Broadcasting in time-division duplexing: a random linear network coding approach. Workshop on Network Coding, Theory, and Applications, p.62-67.

[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.

[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.

[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.

[18]Magli, E., Wang, M., Frossard, P., et al., 2013. Network coding meets multimedia: a review. IEEE Trans. Multim., 15(5):1195-1212.

[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.

[21]Newman, D.J., 1960. The double dixie cup problem. Am. Math. Mon., 67(1):58-61.

[22]Pyattaev, A., Galinina, O., Andreev, S., et al., 2015. Understanding practical limitations of network coding for assisted proximate communication. IEEE J. Sel. Area Commun., 33(2):156-170.

[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 geometric graphs. IEEE Commun. Lett., PP(99):1-1.

[25]Wang, M., Li, B., 2006. How practical is network coding IEEE Int. Workshop on Quality of Service, p.274-278.

[26]Yu, M., Aboutorab, N., Sadeghi, P., 2014. From instantly decodable to random linear network coded broadcast. IEEE Trans. Commun., 62(11):3943-3955.

[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.

[28]Zhou, H., Liu, B., Luan, T.H., et al., 2014. ChainCluster: engineering a cooperative content distribution framework for highway vehicular communications. IEEE Trans. Intell. Transp. Syst., 15(6):2644-2657.