تحلیل روش کدگذاری شبکه تنک برای نرم افزار‌های بلادرنگ

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشکده علوم رایانه و فناوری اطلاعات - دانشگاه تحصیلات تکمیلی علوم پایه

2 دانشکده علوم رایانه و فناوری اطلاعات/دانشگاه علوم پایه زنجان

چکیده

کد‌گذاری شبکه تنک به ‌عنوان یک روش جهت کاهش پیچیدگی محاسباتی روش کد‌گذاری شبکه خطی تصادفی معرفی شد. در این روش برخلاف روش کد‌گذاری شبکه خطی تصادفی بیشتر ضرایب ماتریس کدگشایی صفر است. این تغییر باعث کاهش قابل توجه پیچیدگی محاسباتی الگوریتم های کدگشایی می‌شود. کدگشایی جزیی به معنای امکان کدگشایی بخشی از بسته‌های خام (پیش از دریافت بسته­های مورد نیاز برای کدگشایی همه بسته­های خام( تعریف می­شود و یکی از قابلیت‌های روش کد‌گذاری شبکه تنک است. در این مطالعه با بهره بردن از قابلیت ذکر شده، با ارائه سه مدل مختلف روش کد‌گذاری تنک را به‌عنوان یک رویکرد برای کاهش تأخیر کدگشایی در نرم افزاری‌های بلادرنگ بررسی می‌کنیم. به‌طور دقیق‌تر ما ابتدا، با معرفی یک مدل مبتنی بر زنجیره­ی مارکف، کد‌گذاری شبکه تنک را برای پیکربندی بدون یازخورد از لحاظ عملکرد­های تعداد ارسال‌های مورد نیاز و میانگین تأخیر کدگشایی ‌بسته برای یک نسل از بسته­های خام ارزیابی می­کنیم. سپس صحت مدل ارائه شده را با استفاده از شبیه‌سازی گسترده ارزیابی کر‌‌ده ونشان می‌د‌هیم مدل ارائه شده قادر به ارزیابی دقیق تعداد ارسال‌های مورد نیاز و تأخیر کدگشایی‌ ‌بسته برای یک نسل از بسته‌های خام است.  نتایج همچنین صحت مدل در کانال خطا دار را هم ارزیابی می­کند. در ادامه مدل مبتنی بر بازخورد را معرفی می­کنیم و در بخش شبیه­سازی نشان می­دهیم این مدل قادر به ایجاد یک تعادل بهتر بین عملکرد تعداد ارسال و میانگین تأخیر کدگشایی بر بسته است. در آخر با تمرکز بر مسئله پیدا کردن درخت پوشای تصادفی یک مدل مبنی بر گراف برای تحلیل کدگذاری شبکه تنک ارائه می­کنیم ونشان می­دهیم اگرچه مدل معرفی شده فقط برای تنکی 2 معتبر است، اما ظرفیت توسعه برا تنکی­های کمتر را نیز دارا است.

کلیدواژه‌ها

عنوان مقاله [English]

Analysis of Sparse Network Coding Method for Real-Time Applications

نویسندگان [English]

  • Amir Zaree 1
  • Sanaz Mohammadi 2
  • Peyman Pahlevani 2
1 Department of Computer Science and Information Technology, Institute for Advanced Studies in Basic Sciences
2 Department of Computer Science and Information Technology
چکیده [English]

Sparse network coding was introduced to reduce the computational complexity of the random linear network coding. In this method, most of the decoding matrix coefficients are zero. Partial decoding means the possibility of decoding a part of the raw packets is one of the capabilities of the sparse network coding method. We introduce three different models of sparse coding method as an approach to reduce decoding latency in real-time communication. More precisely, we first evaluate a sparse network coding for a no feedback configuration in terms of the performance of the total number of transmissions required, and the average packet decoding delay for a generation of raw packets, by introducing a Markov chain-based model. Then we evaluate the accuracy of the proposed model using extensive simulation and show that the proposed model can accurately estimate the number of required transmissions and decoding delay for a generation of packets. The results also evaluate the accuracy of the model in the erasure channel. In the following, we introduce the feedback-based model and we show that this model can create a better balance between the functions of the number of transmissions and the average decoding delay per packet. Finally, by focusing on the problem of finding the random spanning tree, we present a graph-based model for analyzing sparse network coding and show that although the proposed model is valid only for grade 2 sparsity, it also has the capacity to develop for lower sparsity.

کلیدواژه‌ها [English]

  • Random linear network coding
  • Sparse network coding
  • Number of packet transmissions
  • Average decoding delay

مراجع

Panwar, Sh. Sharma and A. K. Singh, “A survey on 5g: the next generation of mobile communication,” Physical Communication, vol.18, pp.64-84, 2016.
Cvijetic, Optical Network Evolution For 5g Mobile Applications And SDN-based Control, 2014 16th International Telecommunications Network Strategy and Planning Symposium (Networks), pp.1-5, 2014.
Garrido, D. E. Lucani, and R. Agüero, “A markov chain model for the decoding probability of sparse network coding,” IEEE Transactions on Communications, vol.65, no.4, pp.1675-1685, 2017.
Garrido, D. E. Lucani, and R. Aguero, How to tune sparse network coding over wireless links, 2017 IEEE Wireless Communications and Networking Conference (WCNC), pp 1-6, 2017.
Heide, M. V. Pedersen, F. K. H. P. Fitzek, and M.  Médard, “On code parameters and coding vector representation for practical rlnc,” 2011 IEEE International Conference on Communications (ICC), pp1-5, 2011.
Ho, M. Médard, R.  Koetter, D.  R.  Karger, M.  Effros, J. Shi, and B. Leong, “A random linear network coding approach to multicast,” IEEE Transactions on Information Theory, vol.52, no.10, pp.4413-4430, 2006.
Ho, M.  Medard, J. Shi, M.  Effros, and D. R. Karger, On Randomized Network Coding, In Proceedings of the Annual Allerton Conference on Communication Control and Computing, vol.41, no.1,  pp.11-20, 2003.
Silva, W. Zeng, and F. R.  Kschischang, Sparse Network Coding with Overlapping Classes. 2009 Workshop on Network Coding, Theory, and Applications, pp.74-79, 2009.
W. Sorensen, A. S Badr, J. A. Cabrera, D. E. Lucani, J. Heide, and F. H. P. Fitzek, A Practical View on Tunable Sparse Network Coding, Proceedings of European Wireless 2015; 21th European Wireless Conference, pp.1-6, 2015.
Sanghavi, Intermediate Performance of Rateless Codes, 2007 IEEE Information Theory Workshop, pp.478-48, 2007.
Talari and N. Rahnavard, “On the intermediate symbol recovery rate of rateless codes”, IEEE Transactions on Communications, vol.60, no.5, pp.1237-1242, 2012.
Jun, P. Yang, J.  No, and H.  Park, “New fountain codes with improved intermediate recovery based on batched zigzag coding,” IEEE Transactions on Communications, vol.65, no.1, pp.23-36, 2017.
Kamra, V. Misra, J. Feldman, and D. Rubenstein, Growth codes: maximizing sensor network data persistence, Proceedings of The 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp.255-266, 2006.
Zarei, P. Pahlevani and M. Davoodi, “On the partial decoding delay of sparse network coding,” IEEE Communications Letters, vol. 22, pp.1668-1671, 2018.
Zarei, P. Pahlevani and D. E. Lucani, “An Analytical model for sparse network codes: Field Size considerations,” IEEE Communications Letters, vol.24, pp.729 -733, 2020.
Peterson and B. Davie, Computer networks: a systems approach, Elsevier, 2007.
B. Wilson, Generating Random Spanning Trees More Quickly Than The Cover Time, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp.296-303, 1996.
Pedersen, J.Heide and F.H.Fitzek, KODO: An Open And Research Oriented Network Coding Library, International Conference on Research in Networking, pp.145-152, 2011.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار