• End while

۳-۲-۳-۱- اندازه میدان
لم ۲٫ فرض کنید فضای بردارهای بعدی روی باشد. اگر و جفت در برای هر صدق کنند، آنگاه یک ترکیب خطی از موجود است، به قسمی که برای هر .

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

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

جایی­که تعداد کل بسته­های از دست­رفته برای یک دوره از بسته­ها است.
در معادله بالا، با فرض اینکه احتمالات از دست­رفتن بسته­ها از خطوط ارتباطی متفاوت مستقل از یکدیگر هستند، می ­تواند به آسانی توسط رابطه زیر بدست آید
جایی­که نسبت انتقال بسته از خطوط بی­سیم است و احتمال دریافت یک بسته به صورت موفقیت آمیز توسط تمام گیرنده­ها است.
هم اکنون به تحلیل عدد امید شرطی از انتقال­های مجدد در معادله (۲) می­پردازیم. در طرح استاتیک، بسته ازدست رفته به مجموعه از بسته­های از دست­رفته گروه­بندی می­شوند، مجموعه با اندازه و یک مجموعه با اندازه است. از آن­جایی که مجموعه­ها با اندازه دارای عدد امید مشابه برای انتقال مجدد هستند، بنابراین داریم:
(۴)
جایی­که نشانگر مجموعه بسته­های از دست­رفته است که با هم برای انتقال مجدد کد­گذاری شده اند و تعداد بسته­های انتقال مجدد برای است.
تا کنون کارهایی که برای برآورد صورت گرفته محاسبه است که توسط فرمول زیر بدست می ­آید
تعداد بسته­هایی که توسط در مجموعه از بسته­های از دست­رفته دریافت نشده­اند را با نشان می­دهیم.
برای یک مجموعه از بسته­های از دست­رفته، تعداد بسته­های انتقال مجدد عبارت است از:
جایی­که متغیر تصادفی است که نشانگر تعداد انتقال­های مجدد مورد نیاز برای به منظور دریافت بسته است. در این صورت داریم :

در دومین تساوی فوق، در هر گیرنده ، تعداد از بسته­های ازدست رفته از باید کوچکتر یا مساوی تعداد کل از انتقال­های مجدد و تعداد از بسته­های از دست­رفته در کل مجموعه باشد. بعلاوه واضح است که باید بزرگتر یا مساوی باشد. قسمت دوم در تساوی اخیر می ­تواند به صورت زیر تخمین زده شود:

در بالا تساوی اول با فرض اینکه از دست­­رفتن بست از گیرنده_­ها مستقل است حاصل می­ شود.
در مورد تخمین در معادله (۶) لم زیر را داریم.