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

Analysis of Sparse Network Coding Method for Real-Time Applications

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

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.