شکل ۳-۳ - مثالی که نیاز به ماکزیمم بستههای تغییر یافته دارد
۳-۲-۲-۲- پیچیدگیهای محاسباتی
اینجا به اختصار به تحلیل پیچیدگیهای محاسباتی بستههای کد شده بدست آمده برای انتقال در طرح میپردازیم.
در طول فاز انتقال، مبدا بستههای اصلی را انتقال میدهد که تنها نیاز به یک زمان ثابت دارد. در طول فاز انتقال مجدد، مبدا ابتدا نیاز به زمان برای گرفتن و محاسبه دارد. سپس برای هر انتقال مجدد مبدا نیاز به زمان برای ترکیب خطی بسته از دسترفته و زمان برای به روز رسانی پارامتر و برای به روز رسانی پارامتر دارد. بنابراین پیچیدگی محاسباتی کل برای بدست آوردن بسته کدگذاری شده برای انتقال مجدد است [۲].
۳-۲-۳- طرح جامع کد محور پویا[۹۵] ()
طرح نیز شامل فاز انتقال و فاز انتقال مجدد است. مشابه طرح ، طرح نیز اصل کدگذاری محدود را حذف می کند و از الگوریتمی ساده به منظور یافتن مجموعه ای از بستههای از دسترفته برای کدگذاری استفاده می کند. تفاوت عمده این دو طرح این است که در طرح ، بستههای از دسترفته به صورت پویا برای هر انتقال مجدد به روز رسانی
میشوند به قسمی که ظرفیتهای بالقوه کدگذاری به صورت موثرتری به کار گرفته میشوند.
بیایید شکل ۳-۲ را در نظر بگیریم، همانند طرح ، مبدا ابتدا می تواند بسته کدگذاری شده و سپس را انتقال دهد. فرض کنید که از طریق بسته کدگذاری جاری تمام بستههای اصلی را احیا کرده باشد (یعنی و )، بر خلاف طرح ، طرح بسته کدگذاری شده جدید را پیدا می کند که هنوز برای تمام گیرندهها تغییر یافته است. این قابل توجه است، اگر چه که نیازمند به روز رسانی پویای بستههای کدگذاری شده است، گام اصلی گروهبندی و نیز گام انتخاب بردار کدگذاری شده در فاز انتقال مجدد بسیار متفاوت است. در اصل، قبل از شروع به کدگذاری بستههای از دسترفته برای انتقال در طرح ، ابتدا در گام ۱ پارامترها را معین میکنیم که در زیر بدان پرداختهایم. بعد از این گام، طرح مجموعه از بستههای از دسترفته را در گام ۲ مشخص می کند و سپس در گام ۳ بردار کدگذاری را بدست میآوریم. بعد از انتقال بسته کدگذاری شده، طرح به منظور به روز رسانی بر اساس دریافت واکنش اطلاعات از گیرندهها توسط گام ۲ ادامه مییابد و سپس از گام ۳ به منظور بدست آوردن یک بسته
کدگذاری شده جدید برای انتقال استفاده میکنیم. این مراحل مرتبا تکرار میگردند تا تمام گیرندهها، تمام بستههای از دسترفته را احیا کنند. در ادامه با جزئیات به بررسی طرح میپردازیم.
گام ۱٫ ( تعیین پارامتر )
فرض کنید مجموعه ای از بستهها در دوره جاری باشد و مجموعه ای از بستهها برای کدگذاری در دوره جاری باشد و مجموعه ای از بردارهای کد شده از بستههای کدگذاری شده است که تا کنون توسط دریافت شده اند. را تعیین میکنیم و را به عنوان مجموعه تهی را در نظر میگیریم. در هر انتقال مجدد نیاز به تعریف مجموعه و نیز بردار کدگذاری روی مجموعه برای بدست آوردن بسته کدگذاری شده داریم.
گام۲٫( مشخص کردن )
برای هر گیرنده بررسی کنید که آیا با برابرند یا نه. اگر نتوانستیم بیابیم که با برابر باشد، بدون تغییر برای انتقال جاری باقی میماند (همانند انتقال قبل) و در غیر این صورت مبدا را برای انتقال جاری با حذف و یا اضاف کردن برخی از بستهها به صورت زیر به روز رسانی می کند.
- به روز رسانی : برای هر گیرنده با مساوی و هر قرار میدهیم زیرا تمام بستههای از دسترفته در را احیا کرده است.
- حذف بستهها : برای هر بسته که در صدق کند، ابتدا بردار
کدگذاری را به صورت زیر تنظیم میکنیم : برای هر و هر بردار از مولفه نظیر بسته را حذف میکنیم و اگر نتیجه باشد قرار میدهیم و سپس بسته را از حذف میکنیم.
- اضاف کردن بستهها : برای هر بسته در اعمال زیر را اعمال میکنیم : بررسی
میکنیم که آیا حداقل یک گیرنده موجود است که در و صدق کند. اگر چنین است ابتدا بسته را به اضافه کنید سپس برای هر یک مولفه جدید صفر در انتهای میافزاییم و اگر یک بردار یکه با بعد به صورت (۱و…و۰و۰) به اضافه میکنیم.
با داشتن مجموعه ، تعیین بردار کدگذاری روی به صورت زیر انجام میگیرد.
گام ۳٫ ( تعیین بردار کدگذاری )
ابتدا برای هر گیرنده با یک بردار که مستقل از است را با بهره گرفتن از روش حذفی گاوس بدست میآوریم و یک مجموعه عمود با عمود سازی بردارهای تولید میکنیم، سپس برای هر بردار بدست آمده قرار میدهیم :
سرانجام با بدست آمده از تقریبی که در زیر معرفی شده است به منظور بدست آوردن بردار کدگذاری که در رابطه برای هر صدق می کند، استفاده میکنیم. با توجه به اثبات لم ۳ میتوان طریقه یافتن را دریافت.
لمی که در ادامه می آید نشان میدهد که بدست آمده از هر مستقل است.
تعریف: بردار را بر مجموعه که شامل بردارهای - بعدی است، عمود گویند، هرگاه برای هر داشته باشیم .
لم ۱٫ فرض کنید که یک مجموعه از بردارهای - بعدی باشد و بردار بر بردار عمود است. آنگاه اگر بردار در رابطه صدق کند ، از مستقل خطی است [۲].
گام ۳ تضمین می کند که بردار کدگذاری انتخاب شده از بردارهای کدگذاری بستههای دریافت شده این گیرنده مستقل است. به وضوح روش کدگذاری پویا می تواند میانگین تعداد انتقالهای مجدد را در هر دوره کاهش دهد. طرح به صورت اختصار در جدول ۳-۳ آمده است. بعد از آن به اختصار به بررسی اندازه میدان مورد نظر و پیچیدگیهای محاسباتی این طرح
میپردازیم.
جدول ۳-۳- طرح جدید پویا
Procedure of the DGC scheme
Steps:
-
- Transmit native packets one by one and build the packet-loss table.
-
- Conduct procedure 1 to initialize parameters , and ().
-
- While and do
-
- Conduct procedure 2 to update .
-
- Conduct procedure 3 to obtain , which is independent of each satisfying , and obtain the encoded packet .
-
- Repeatedly transmit packet until one or more receivers receive it.
- For any that correctly receives ,.