مقالات و پایان نامه ها درباره :توزیع قابل اعتماد کد محور در شبکه های بی ... |
- End while
۳-۲-۳-۱- اندازه میدان
لم ۲٫ فرض کنید فضای بردارهای بعدی روی باشد. اگر و جفت در برای هر صدق کنند، آنگاه یک ترکیب خطی از موجود است، به قسمی که برای هر .
اثبات: فرض کنید که نشانگر فضای برداری باشد که توسط توسیع داده شده است و نشانگر بعد آن باشد. آنگاه یک زیرفضای بعدی ازبرای هراست. به وضوح اگر داریم. چون ها حداقل در بردار پوچ با یکدیگر اشتراک دارند، تعداد ترکیبات خطی مورد نیاز عبارت است از:
اگر آنگاه . اگر آنگاه زیرا یک میدان حداقل دو عضو دارد . □
نتیجه ۱٫ اگر و، آنگاه برای بردارهای یک ترکیب خطی از موجود است به قسمی که برای هر [۲].
لم۳٫ ترکیب خطی که وجود آن در لم ۲ اثبات شده است، در بدترین حالت در زمان ) بدست می آید.
اثبات: اثبات با استقرا روی انجام می شود. برای به آسانی قرار میدهیم برای گام استقرا از به از فرض استقرا برای بدست آوردن بردار با برای استفاده میکنیم. اگر غیر صفر باشد، نتیجه حاصل شده است در غیر این صورت لم ۲ را برای بکار میبریم. چون ، ترکیب خطی موجود است به قسمی که برای هر داریم . در حالت خاص چون ، از این رو و به فرم است و برای هر داریم . ضریب را میتوان با آزمودن تمام مولفههای میدان بدست آورد. تمام آزمون می تواند در زمان با از پیش محاسبه کردن ضربهای اسکالر برای انجام می شود. برای تکرار زمان مورد نیاز است [۲۴]. □
مشابه طرح ، طرح نیز عمل کدگذاری را عموما روی میدان متناهی انجام میدهد. قضیه زیر نشانگر شرط لازم برای اندازه برای این طرح است.
قضیه ۳٫ مقدار داده شده است، اگر ، آنگاه در طرح همواره یک بسته تغییر یافته برای تمام گیرندههای غیر اشباع شده برای انتقال مجدد موجود است.
اثبات: بر اساس نتیجه ۱ میتوانیم به آسانی نتیجه دلخواه را بدست آوریم. □
۳-۲-۳-۲- پیچیدگی محاسباتی
در اینجا به بررسی پیچیدگی محاسباتی بدست آوردن یک بسته انتقال هنگامی که از طرح استفاده میکنیم میپردازیم. در طول فاز انتقال، مبدا تنها به انتقال بستههای اصلی می پردازد که تنها به زمان ثابتی نیاز دارد. در طول گام ۲ از فاز انتقال مجدد، به روز رسانی به میزان زمان نیاز دارد. حذف بستهها از و به روز رسانی پارامترهای مرتبط با و افزودن بستهها به و به روز رسانی پارامترهای مرتبط به زمان نیاز دارد. در گام ۳ روش حذفی گاوس و گام متعامد سازی و محاسبه ´ به ترتیب و و زمان احتیاج دارند. بنابراین پیچیدگی محاسباتی کلی است [۲].
۳-۳- تحلیل اجرا
در این بخش به بررسی تحلیل تئوری این دو طرح جدید بر حسب تاثیر انتقال و تاخیر اجرا میپردازیم.
با تاثیر انتقال، متریکی مشابه آنچه نگوین در سال ۲۰۰۷ معرفی کرد به نام پهنای باند انتقال به عنوان میانگین انتقالهای مورد نیاز برای انتقال موفق یک بسته به تمام گیرندهها، تعریف می شود. در اینجا تاخیر اجرا را میانگین تعداد انتقالهایی که نیاز است از زمانیکه یک بسته برای اولین بار انتقال یابد تا هنگامی که تمام گیرندهها آن را به درستی دریافت کنند، تعریف میکنیم. (که در اینجا به آن تاخیر انتقال مجدد گوییم)
پیش از اینکه با جزئیات به تحلیل اجرای طرحهای بررسی شده بپردازیم، به بررسی کران پایین پهنای باند انتقال میپردازیم که با بهره گرفتن از آن میتوانیم ایدههایی در خصوص تاثیر مسایل مطرح شده بدست آوریم. ( این مبحث در بخش ۴ مورد بررسی قرار میگیرد. )
قضیه ۴٫ برای توزیع قابل اعتماد با گیرنده، نسبت انتقال بسته در گیرنده را با نشان میدهیم. در این صورت پهنای باند انتقال ، کران پایینی به صورت زیر دارد.
اثبات: بیایید گیرندهای را با مینیمم نسبت انتقال بسته در میان تمام گیرندهها در نظر بگیریم. برای این گیرنده میانگین تعداد انتقال های مورد نیاز برای دریافت موفقیت آمیز یک بسته عبارت است از چون گیرندههای دیگری نیز موجودند که نیاز به دریافت بستهها از مبدا دارند، میانگین تعداد انتقالهای مورد نیاز برای دریافت یک بسته توسط تمام گیرندهها به وضوح حداقل برابر است.
۳-۳-۱- تحلیل طرح
در ابتدا به تحلیل طرح میپردازیم.
۳-۳-۱-۱- پهنای باند انتقال
پهنای باند انتقال را هنگامی که از طرح استفاده میکنیم با و تعداد انتقالهای مجدد بستهها برای تولید بستههای از دسترفته را با نشان میدهیم. توسط رابطه زیر بدست می آید [۲].
جاییکه تعداد کل بستههای از دسترفته برای یک دوره از بستهها است.
در معادله بالا، با فرض اینکه احتمالات از دسترفتن بستهها از خطوط ارتباطی متفاوت مستقل از یکدیگر هستند، می تواند به آسانی توسط رابطه زیر بدست آید
جاییکه نسبت انتقال بسته از خطوط بیسیم است و احتمال دریافت یک بسته به صورت موفقیت آمیز توسط تمام گیرندهها است.
هم اکنون به تحلیل عدد امید شرطی از انتقالهای مجدد در معادله (۲) میپردازیم. در طرح استاتیک، بسته ازدست رفته به مجموعه از بستههای از دسترفته گروهبندی میشوند، مجموعه با اندازه و یک مجموعه با اندازه است. از آنجایی که مجموعهها با اندازه دارای عدد امید مشابه برای انتقال مجدد هستند، بنابراین داریم:
(۴)
جاییکه نشانگر مجموعه بستههای از دسترفته است که با هم برای انتقال مجدد کدگذاری شده اند و تعداد بستههای انتقال مجدد برای است.
تا کنون کارهایی که برای برآورد صورت گرفته محاسبه است که توسط فرمول زیر بدست می آید
تعداد بستههایی که توسط در مجموعه از بستههای از دسترفته دریافت نشدهاند را با نشان میدهیم.
برای یک مجموعه از بستههای از دسترفته، تعداد بستههای انتقال مجدد عبارت است از:
جاییکه متغیر تصادفی است که نشانگر تعداد انتقالهای مجدد مورد نیاز برای به منظور دریافت بسته است. در این صورت داریم :
در دومین تساوی فوق، در هر گیرنده ، تعداد از بستههای ازدست رفته از باید کوچکتر یا مساوی تعداد کل از انتقالهای مجدد و تعداد از بستههای از دسترفته در کل مجموعه باشد. بعلاوه واضح است که باید بزرگتر یا مساوی باشد. قسمت دوم در تساوی اخیر می تواند به صورت زیر تخمین زده شود:
در بالا تساوی اول با فرض اینکه از دسترفتن بست از گیرندهها مستقل است حاصل می شود.
در مورد تخمین در معادله (۶) لم زیر را داریم.
فرم در حال بارگذاری ...
[شنبه 1400-08-22] [ 12:27:00 ب.ظ ]
|