۳-۲-۲-۱- اندازه میدان ۴۶

۳-۲-۲-۲- پیچیدگی­های محاسباتی ۴۶

۳-۲-۳- طرح جامع کد­محور پویا ۴۷

۳-۲-۳-۱- اندازه میدان ۴۹

۳-۲-۳-۲- پیچیدگی محاسباتی ۵۰

عنوان صفحه

۳-۳- تحلیل اجرا ۵۱

۳-۳-۱- تحلیل طرح ۵۱

۳-۳-۱-۱- پهنای باند انتقال ۵۱

۳-۳-۱-۲- تاخیر انتقال مجدد ۵۶

۳-۳-۲- تحلیل طرح ۵۸

۳-۳-۲-۱- پهنای باند انتقال ۵۸

۳-۳-۲-۲- تاخیر انتقال مجدد ۵۹

۳-۴- نتایج عددی ۶۰

۳-۴-۱- محیط شبیه سازی ۶۰

۳-۴-۲- پهنای باند انتقال ۶۰

۳-۴-۳- تاخیر انتقال مجدد ۶۳

۳-۵- نتیجه گیری ۶۴

فهرست منابع و مأخذ ۶۵

پیوست

- واژه نامه فارسی به انگلیسی ۶۸

– واژه نامه انگلیسی به فارسی ۷۲

فصل اول

مقدمه

امروزه با پیشرفت تکنولوژی اطلاعات نیاز به استفاده از امکانات روز جهت تبادل داده ­ها با سرعت و دقت بالا و رهایی از محدودیت­های محیطی بیشتر احساس می­ شود بنابراین لازم است از امکانات و تجهیزاتی که بتواند به سادگی و آسانی راه ­اندازی شود استفاده نمود.

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

یکی از راحت­ترین، ساده­ترین و کم هزینه­ترین روش­ها استفاده از شبکه ­های کامپیوتری بخصوص شبکه ­های کامپیوتری بی­سیم است.

با توجه به نیاز به اشتراک گذاشتن به موقع داده ­ها ایده ایجاد شبکه شکل گرفت. کامپیوترهای شخصی ابزارهایی جالب برای تولید انواعی از اطلاعات هستند، اما به شما این اجازه را نمی­دهند که به سرعت داده ­های تولیدی خود را به اشتراک بگذارید. بدون شبکه، اسناد باید چاپ شوند تا دیگران بتوانند آن­ها را ویرایش کنند یا مورد استفاده قرار دهند. در بهترین حالت می­توانید فایل مربوطه را در اختیار آن­ها قرار دهید تا در کامپیوتر خود ذخیره کنند. اگر دیگران در آن­ها تغییراتی ایجاد کنند هیچ راهی برای ترکیب تغییرات وجود ندارد. اگر چند کامپیوتر و یا حتی وسایل دیگری مانند چاپگر و … به یکدیگر متصل شوند، یک شبکه ایجاد می­ شود که می­توانند اطلاعات را بین یکدیگر به اشتراک گذارند.

در بخش ۱ این فصل به بررسی مفهوم شبکه پرداخته و اجزای شبکه را مورد بررسی قرار خواهیم داد. در بخش دوم به بررسی شبکه ­های کامپیوتری می­پردازیم. در بخش سوم
شبکه ­های بی­سیم مورد مطالعه قرار خواهند گرفت و بخش ۴ به معرفی شبکه ­های سیار می ­پردازد.

• 1. شبکه ^[۱]

یک شبکه از اتصال تعداد بسیاری گره^[۲] که جریانی مطلوب در آن وجود دارد به وجود می ­آید. گره­ها نقاطی هستند که در آن­ها بیش از دو شاخه یا خط ارتباطی^[۳] که جریان از طریق آن­ها عبور می­ کند، یکدیگر را ملاقات می­ کنند. شکلی که در ادامه می ­آید یک شبکه با پنج گره A ، B ،C، D وE را نشان می­دهد. این گره­ها با خطوط ارتباطی یا شاخه­ های گوناگونی مانند ، ، ، و… با هم مرتبط شده ­اند.

شکل ۱-۱- ساختار شبکه

در مهندسی برق یک مثال ساده از شبکه، یک شبکه الکتریکی است که خطوط ارتباطی آن اجزای الکتریکی مانند مقاومت^[۴]، خازن­ها^[۵]، القاکننده­ها^[۶] و اجزای فعال هستند که جریان از طریق این شاخه­ها عبور و گره­های بسیاری را ملاقات می­ کند. جریان عبوری از طریق تعدادی از شاخه­ها به یک گره می­رسد و از طریق تعدادی شاخه دیگر از گره خارج می­شوند.

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

سازمان­دهی شبکه ­های ارتباطی به صورت گام به گام مورد بحث قرار می­گیرند. یک شبکه از گره­ها و شاخه­ها به منظور تسهیل جا به ­جایی­های فیزیکی تشکیل شده است. جریان از طریق یک گره وارد شبکه می­ شود و از یک گره به نام گره مقصد از شبکه خارج می­ شود که این گره به گره مصرف ­کننده معروف است. هر گره­ای می ­تواند به عنوان یک گره مبدأ و یا مصرف ­کننده باشد.

•  

• • 1. مولفه­های شبکه ­های ارتباطی

گره

در یک شبکه ارتباطی یک گره نقطه­ای است که در آن بیش از دو شاخه یکدیگر را ملاقات می­ کنند ممکن است یک شبکه ارتباطی دارای تعداد بسیار زیادی گره باشد که یک گره لزوما به تمام گره­ها مرتبط نیست. کار یک گره از شبکه، اتصال مسیر وارد شونده به مسیر خارج شونده است، از این رو سیگنال­ها می­توانند مسیر خود را به مسیر مطلوبشان برای انتقال پیش رو تغییر دهند. به صورت متعارف در یک شبکه تلفنی، مراکز تلفنی و یا تلفن­ خانه­ها نقش گره را بازی می­ کنند. در یک شبکه اطلاعاتی یک گره یک بسته سوییچ^[۷] است که به آن مسیریاب^[۸] گفته می­ شود. برخی از گره­ها به خصوص گره­های تغییر پیام یا بسته، دارای بافر و حافظه برای پیام­ها هستند. چنین گره­هایی همانند سوییچ­های ذخیره و ارسال کار می­ کنند. گره­ها اعمال دیگری چون یکسان­ سازی پیام­های دریافتی، آزمایش کردن خروجی­ها و … را نیز انجام می­ دهند.

شاخه

شاخه شبکه ­های ارتباطی اساسا یک رسانگر انتقال^[۹] است که یک سیم یا یک کانال رادیویی است. رسانگر انتقالات سیمی می ­تواند به هر یک از شکل­های جفت سیم­های مسی، کابل­های چند جفتی، کابل­های هم­محور^[۱۰] و یا فیبر نوری^[۱۱] باشند. این سیم­ها سیگنال­ها را از یک گره به گره دیگر می­برند. یک کانال بی­سیم یک طیف الکترو­مغناطیسی از فرکانس­های بسیار پایین تا فرکانس­های بسیار بالا شامل موج­های میلیمتری و نوری گسترده شده ­اند. پهنای باند^[۱۲]
کانال­های سیمی یا بی­سیم دارای برد عرضی بالایی است می ­تواند نسبت داده ­های عبوری را از چند بیت در ثانیه تا چند گیگا – پنتا بیت در ثانیه پوشش دهد. طول این خطوط انتقال با توجه به دلایل متنوعی مانند پراکنش محدود است. در یک شبکه ارتباطی چند منظوره لزومی ندارد که تمام خطوط ارتباطی از یک نوع باشد، بعضی می­توانند خطوط سیمی و بعضی خطوط بی­سیم باشند.

هم اکنون یک شبکه ارتباطی را می­توان به صورت گردایه­ای از گره­ها که توسط خطوط ارتباطی با یکدیگر مرتبط هستند تعریف کرد که اطلاعات را از طریق سیگنال­ها به شکل الکتریکی یا نوری منتقل می­ کنند. بنابراین گره­ها، خطوط ارتباطی و انتقال اطلاعات ویژگی اساسی هر شبکه­ ای هستند. برخی از معمول­ترین و شناخته ­شده­ترین و عریض­ترین شبکه ­های پیامی^[۱۳]، شبکه ­های پستی^[۱۴]، شبکه ­های تلگرافی^[۱۵]، شبکه ­های تلفنی^[۱۶] (ثابت، معمولی و سیار)، شبکه ­های کامپیوتری^[۱۷] و

شبکه ­های سرگرمی^[۱۸] (پخش کننده­ های تلویزیون یا صوتی) می­باشند.

•  

• • 1. مثال­هایی از شبکه

یک شبکه با توجه به کاربردی که دارد طراحی و به کار گرفته می­ شود. گونه­ های بسیاری از شبکه موجود است. شبکه تلگرافی برای ارسال تلگراف­ها از یک مکان به مکان دیگر مورد استفاده قرار می­گیرند. در آن­ها از سوییچ­های پیام به عنوان گره استفاده می­ شود و اساسا سرویسی با سرعت بسیار پایین ارائه می­دهد. از سویی دیگر شبکه ­های تلکس مانند شبکه ­های تلفنی کار می­ کنند و کاربران می­توانند مستقیما پیام­های متنی خود را بدون کمک اپراتور به مقصد مورد نظر ارسال نمایند. شبکه تلفنی برای ارتباطات صوتی بین دو کاربر مورد استفاده قرار می­گیرد. یک شبکه کامپیوتری به کاربران این اجازه را می­دهد که با بهره گرفتن از شبکه کامپیوتری با هم ارتباط برقرار کنند. داده ­های صوتی و تصویری می­توانند از طریق شبکه پخش^[۱۹] به طور همزمان از یک مبدأ به تعداد زیادی از استفاده­کننده­ها ارسال شود.

به منظور بیشتر مشخص شدن مفهوم شبکه، شبکه کامپیوتری را مورد بحث قرار می­دهیم.

۱-۲- شبکه کامپیوتری

با توجه به استفاده گسترده از کامپیوتر­ها، دیگر استفاده از آن­ها به یک مکان خاص محدود نمی­ شود و نیاز به اینکه کامپیوترها در مکان­های مختلف با یکدیگر مرتبط شوند احساس می­ شود. یک شبکه کامپیوتر که اغلب از آن به عنوان شبکه یاد می­ شود، از گروهی از کامپیوترها و وسیله­ ها تشکیل شده است که توسط کانال­های ارتباطی با یکدیگر مرتبط هستند و ارتباط بین کاربران را آسان می­سازد. یک شبکه به کاربران این اجازه را می­دهد که از منابع و اطلاعات به صورت مشترک استفاده کنند. بر اساس پراکندگی جغرافیایی کامپیوترها اساسا سه نوع شبکه موجود است که در ادامه به آن­ها اشاره می­کنیم [۷].

شبکه ­های محلی (LAN)^[20]

در این نوع شبکه، کامپیوترها و دیگر وسایل ارتباطی در یک محیط کوچک به یکدیگر مرتبط هستند. محیط می ­تواند یک ساختمان یا مجموعه ­ای از ساختمان­ها در یک محوطه باشد. نمونه ­ای از شبکه محلی، شبکه کتابخانه­ای است که مورد استفاده قرار می­گیرد[۷].

شبکه ­های شهری (MAN)^[21]

اساسا یک شبکه شهری بزرگتر از شبکه ­های محلی است و عموما از ساختاری مشابه استفاده می­ کنند که می ­تواند گروهی از دفاتر مجاور و یا در یک شهر را پوشش دهد و می ­تواند خصوصی و یا عمومی باشد [۷].

شبکه ­های گسترده (WAN)^[22]

در این شبکه کامپیوتر­ها می­توانند از یکدیگر دورتر باشند و شهرها، کشورها و یا حتی قاره­ها را پوشش دهند. کامپیوترها می­توانند از طریق خطوط تلفن^[۲۳]، امواج رادیویی^[۲۴] و فیبر نوری به یکدیگر متصل شوند [۷].

شبکه­ ها به دوگروه کلی تقسیم می­شوند که عبارتند از شبکه ­های نظیر به نظیر^[۲۵] و شبکه ­های سرویس ­دهنده محور^[۲۶].

تفاوت بین شبکه ­های نظیر به نظیر و سرویس­دهنده ­محور بسیار مهم است، زیرا هر یک دارای قابلیت ­های متفاوت هستند. نوع شبکه­ ای که شما آن را اجرا می­کنید به عوامل بسیاری از جمله اندازه سازمان، سطح امنیت، نوع کار، سطح مدیریت شبکه، حجم ترافیک شبکه و بودجه شبکه وابسته است.

شبکه ­های نظیر به نظیر

تعریف­های مختلفی از سیستم نظیر به نظیر ارائه شده است که به طور کلی آن را سیستمی می­دانند برای اشتراک منابع و سرویس­های کامپیوتر با انجام تبادل مستقیم بین آن­ها و در محیطی که اتصالات پایدار و آدرس های قابل پیش ­بینی وجود ندارد و سیستم نمی­تواند متکی به یک سرویس­ دهنده متمرکز باشد استفاده می­ شود.

در یک شبکه نظیر به نظیر هیچ سرویس ­دهنده­ای وجود ندارد و یا بین کامپیوترها درجه­بندی صورت نمی­گیرد. تمام کامپیوترها یکسان هستند و از این رو نظیر یکدیگر می­باشند. عموما هر کامپیوتر به عنوان یک سرویس گیرنده^[۲۷] و یک سرویس دهنده^[۲۸] عمل می­ کند و هیچ یک مسئول اداره کردن کل شبکه نمی­باشند. در این نوع شبکه­ ها کاربر هر کامپیوتر مشخص می­ کند که چه داده­هایی در کامپیوترش در شبکه به اشتراک گذاشته شود و کاربران مسئول کامپیوتر خود و امنیت آن می­باشند.

شبکه نظیر به نظیر یک نوع شبکه ساده است و از آن­جایی که هر کامپیوتر خودش به عنوان یک سرویس گیرنده و یک سرویس دهنده کار می­ کند، دیگر نیازی به یک سرویس دهنده مرکزی و قدرتمند نیست و در نتیجه شبکه ­های نظیر به نظیر نسبت به شبکه ­های سرویس دهنده محور ارزان­تر هستند.

شبکه نظیر به نظیر می ­تواند خالص یا ترکیبی^[۲۹] باشد. در مدل خالص هیچ سرویس دهنده متمرکزی وجود ندارد. در مدل ترکیبی، هر گره از طریق یک سرویس دهنده به سیستم وارد می­ شود که این سرویس دهنده می ­تواند برای شناسایی گره و اطلاعات دارای مجوز ورود بکار رود. بعد از ورود به سیستم جفت­ها بطور مستقیم و بدون دخالت سرویس دهنده با هم ارتباط برقرار

می­ کنند.

شبکه ­های نظیر به نظیر هنگامی مورد استفاده قرار می­گیرند که :

1. تعداد کامپیوترها از ۱۰ کمتر باشد.
2. تمام کاربران در یک مکان قرار گرفته باشند.
3. امنیت شبکه مهم نباشد.
4. در آینده نیازی به توسعه شبکه نباشد.

در ادامه نمونه ­ای از شبکه ­های نظیر به نظیر نشان داده شده است [۱۸، ۲۶].

شکل ۱-۲- نمونه ­ای از شبکه ­های نظیر به نظیر

انتخاب یک روش نظیر به نظیر معمولا به دلیل یک یا چند مورد از اهداف زیر صورت می­گیرد.

تقسیم و کاهش هزینه

راه ­اندازی یک سیستم متمرکز که بتواند از سرویس گیرنده­های زیادی پشتیبانی کند، هزینه زیادی را به سرویس دهنده تحمیل خواهد کرد. معماری نظیر به نظیر می ­تواند کمک کند تا این هزینه بین تمام گره­ها تقسیم شود.

افزایش قابلیت اعتماد

بدلیل عدم وجود یک منبع قدرتمند مرکزی، قابلیت اعتماد در سیستم یکی از اهداف مهم به شمار می ­آید و بنابراین باعث نوآوری­های الگوریتمی در این زمینه می­ شود.

افزایش خودمختاری

در بسیاری از موارد کاربران در یک شبکه توزیع مایل نیستند که متکی به یک سرویس دهنده متمرکز باشند چون متکی بودن به یک سرویس دهنده متمرکز باعث محدود بودن آن­ها
می­ شود. مثلا در مورد کاربرد اشتراک فایل، کاربران می­توانند بطور مستقیم فایل­های یکدیگر را دریافت کنند بدون آن­که متکی به یک سرویس دهنده متمرکز باشند که ممکن است مجوز دریافت فایل را به آن­ها ندهد.

گمنامی

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

پویایی

فرض اولیه سیستم­های نظیر به نظیر این است که در یک محیط کاملا پویا قرار داریم. منابع و گره­ها می­توانند آزادانه به سیستم وارد و از آن خارج شود.

شبکه ­های سرویس دهنده محور

در محیطی که تعداد کامپیوترها زیاد باشد شبکه ­های نظیر به نظیر مناسب نمی ­باشد و از این رو شبکه­ ها باید دارای سرویس دهنده مشخصی باشند. سرویس دهنده تنها به عنوان سرویس دهنده عمل می­ کند و نیاز اجزای شبکه را سریعا برآورده می­ کند و امنیت فایل­های شبکه را بر عهده دارد.

هنگامی که اندازه و ترافیک شبکه افزایش می­یابد بیش از یک سرویس دهنده در شبکه مورد نیاز است. تقسیم کارها بین سرویس دهنده­ها تضمین کننده اجرای هر کار به بهترین روش ممکن در شبکه است. نمونه ­ای از شبکه ­های سرویس دهنده محور در شکل ۱-۳ نشان داده شده است [۱۸].

شکل ۱-۳- نمونه ­ای از شبکه ­های سرورمحور

۱-۲-۱- ساختار شبکه

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

۱-۲-۱-۱- ساختار گذر^[۳۰]

در این ساختار تمام وسیله­ ها به یک کابل مرکزی به نام گذر یا ستون فقرات^[۳۱] متصل هستند. سادگی، کم هزینه بودن و توسعه آسان این شبکه از نقاط قوت آن است و نقطه ضعف عمده این شبکه آن است که اگر کابل اصلی که به عنوان پل ارتباطی بین کامپیوتر­های شبکه است، قطع شود، کل شبکه از کار خواهد افتاد [۱۸].

شکل ۱-۴- ساختار گذر

۱-۲-۱-۲- ساختار ستاره­ای^[۳۲]

در این ساختار تمام وسیله­ ها به یک هاب^[۳۳] مرکزی متصل هستند. گره­ها با عبور داده ­ها از هاب با یکدیگر ارتباط دارند. نقطه ضعف این شبکه این است که عملیات کل شبکه به هاب وابسته است و اگر هاب از کار بیافتد کل شبکه از کار خواهد افتاد.

نقاط قوت شبکه ستاره­ای عبارتند از:

1. نصب شبکه با این ساختار ساده است.
2. توسعه شبکه با این ساختار به راحتی انجام می­ شود.
3. اگر یکی از خطوط متصل به هاب قطع شود فقط یک کامپیوتر از شبکه خارج
   می­ شود [۱۸].

شکل ۱-۵- ساختار ستاره­ای

۱-۲-۱-۳- ساختار حلقوی^[۳۴]

در این ساختار تمام وسیله­ ها به شکل یک حلقه بسته به یکدیگر متصل هستند بنابراین هر وسیله مستقیما به دو وسیله دیگر در ارتباط است که در دو طرف آن قرار دارند.

نقطه ضعف شبکه ­های حلقوی این است که به سخت افزار پیچیده نیاز دارد. (کارت شبکه آن گران قیمت است)

و نقاط قوت شبکه ­های حلقوی عبارتند از:

1. نصب شبکه با این ساختار ساده است.
2. توسعه شبکه با این ساختار به راحتی انجام می­ شود [۱۸].

شکل ۱-۶- ساختار حلقوی

۱-۲-۱-۴- ساختار مش^[۳۵]

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

شکل ۱-۷- ساختار مش

۱-۲-۲- اجزای شبکه

اجزای اساسی شبکه عبارتند از سخت افزار شبکه ^[۳۶]، رسانه­های انتقال و نرم افزار شبکه^[۳۷].

۱-۲-۲-۱- سخت افزار شبکه

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

۱-۲-۲-۲- رسانه­های انتقال

انتقال داده ­ها و عبور سیگنال­ها از انتقال دهنده به گیرنده­ها از طریق یک مسیر صورت می­گیرد که این مسیر رسانه نام دارد.

رسانه­های هدایت شده^[۳۸]

در این گونه رسانه ­ها داده ­ها از طریق مسیرهای فیزیکی انتقال می­یابند، گونه­ های متفاوتی از کابل­ها در این رسانه ­ها مورد استفاده قرار می­گیرند که با توجه به ساختار شبکه انتخاب می­شوند، که گونه ­هایی از آن­ها عبارتند از کابل­های هم­محور، زوج سیم­های به هم تابیده شده مسی^[۳۹] و کابل فیبرنوری.

رسانه­های هدایت نشده^[۴۰]

در این رسانه ­ها هیچ سیمی وجود ندارد و اطلاعات از طریق امواج رادیویی یا مایکروویو انتقال می­یابند.

۱-۲-۲-۳- نرم افزار شبکه

نرم افزار شبکه مجموعه ­ای از نرم افزارهاست که به کامپیوترهایی که با هم در ارتباط هستند اجازه می­دهد که به صورتی راحت و کم هزینه از نرم افزارها استفاده کنند. نرم افزار شبکه عملکرد هر سیستم شبکه را کنترل می­نماید، به عنوان مثال کنترل می­ کند که چه کسانی اجازه استفاده از شبکه را دارند، چه زمانی می­توان از شبکه استفاده کرد، کاربران اجازه انجام چه کارهایی را دارند و چه منابعی برای شبکه در دسترس می­باشد.

کارت شبکه (NIC)^[41]

هر کامپیوتر به یک کارت شبکه نیاز دارد، که به هر ایستگاه اجازه می­دهد تا با سایر ایستگاه­ها تبادل اطلاعات کنند.

سوییچ^[۴۲]

سوییچ­ها اساسا پل­های ارتباطی^[۴۳] هستند که چندین قسمت دارند و قسمت­ های مختلف شبکه را به یکدیگر متصل می­ کنند.

هاب

یک هاب برای متصل کردن چندین کامپیوتر و وسیله از طریق کابل­های خاص استفاده
می­ شود. هاب­ها ارزان هستند و اتصال­ها آسان صورت می­گیرد[۱۸].

مسیریاب

در محیطی که قسمت­ های مختلفی از شبکه وجود دارد، ممکن است یک پل ارتباطی به منظور اطمینان از ارتباطات سریع میان قسمت­ های مختلف، کافی نباشد. در چنین محیطی وسیله­ای لازم است که نه تنها آدرس هر قسمت از شبکه را بداند بلکه بتواند بهترین مسیر را برای ارسال داده ­ها به قسمت­ های مختلف تعیین کند، به چنین وسیله­ای مسیریاب گویند. مسیریاب­ها نسبت به پل­های ارتباطی اجازه دسترسی به اطلاعات بیشتری را دارند و از این اطلاعات به منظور مدیریت بهتر ترافیک در شبکه استفاده می­ کنند. مسیریاب­ها گاهی مدخل^[۴۴] نیز نامیده می­شوند [۱۸].

۱-۲-۳- چگونه شبکه­ ها داده ­ها را ارسال می­ کنند؟

معمولا داده ­ها به صورت فایل­هایی با اندازه­ های بزرگ می­باشند. اگر کامپیوترها همزمان تعداد زیادی داده را در شبکه قرار دهند، شبکه نمی­تواند به درستی کار کند و سرعت شبکه کاهش می­یابد. مقادیر زیاد داده به عنوان یک واحد بزرگ عملکرد شبکه را مختل می­نماید و ارتباطات را امکان­ناپذیر می­سازد، زیرا کامپیوتر­ها کابل­ها را توسط داده ­ها پر کرده ­اند. از آن­­جایی که کاربران مایل هستند داده ­ها را به سرعت و به آسانی در شبکه عبور دهند، داده ­ها باید به قسمت­ های کوچک و قابل اداره شکسته شوند، که به این قسمت ­ها بسته^[۴۵] گفته می­ شود.

بسته­ها واحدهای اساسی شبکه ­های ارتباطی هستند. با تقسیم داده ­ها به بسته­ها، انتقالات مجزا به سرعت صورت می­پذیرد و از این رو هر کامپیوتر در شبکه شانس بیشتری برای انتقال و دریافت اطلاعات دارد. در کامپیوتر گیرنده، بسته­ها جمع­­آوری می­شوند و به منظور بدست آوردن داده اصلی با ترتیبی مناسب سرهم­بندی می­شوند.

هنگامی که کامپیوتر فرستنده، داده ­ها را به بسته­ها می­شکند، اطلاعات کنترلی خاصی را در هر یک از بسته­ها قرار می­دهد که از طریق آن :

1. داده اصلی از طریق قسمت­ های کوچک غیر جفت شده ارسال می­گردد.
2. داده ­ها به ترتیب صحیح در مقصد با هم جفت می­شوند.
3. داده ­ها برای بررسی خطا بعد از جفت شدن بررسی می­شوند.

بسته­ها می­توانند شامل انواع بسیاری از اطلاعات شامل پیام­ها، فایل­ها و یا داده ­های کنترلی خاص کامپیوتری باشند. مولفه­های بسته عبارتند از:

1. یک آدرس مبدا^[۴۶] که نشانگر کامپیوتر فرستنده است.
2. داده­ای که می­خواهیم آن را انتقال دهیم.
3. یک آدرس مقصد^[۴۷] که نشانگر گیرنده است.
4. دستوری که به اجزای شبکه می­گوید که چگونه داده ­ها را انتقال دهند.
5. اطلاعاتی که به کامپیوتر گیرنده می­گوید که چگونه به منظور داشتن داده کامل، بسته­ها را به یکدیگر مرتبط کند.
6. اطلاعات بررسی کردن خطا که تضمین می­ کند داده ­ها بدون نقص دریافت شده ­اند [۱۸].

شکل۱-۸- بسته داده ­ها

۱-۳- شبکه ­های بی­سیم^[۴۸]

منظور از شبکه ­های بی­سیم اتصال دو یا چند کامپیوتر و ایجاد یک شبکه محلی با بهره گرفتن از امواج رادیویی جهت ارسال و دریافت اطلاعات و داده ­ها و یا اصطلاحا سرویس انتقال می­باشد. کامپیوترها در شبکه بی­سیم توسط امواج رادیویی داده ­ها را منتقل می­نمایند که این امر باعث می­ شود بتوان فایل­ها، چاپگر و دسترسی به اینترنت را با هر کامپیوتر موجود در شبکه به اشتراک گذاشت.

شبکه ­های بی­سیم ، که سریعا در حال رشد و توسعه­اند. این نوع شبکه دارای تجهیزات ساده بوده و نصب تجهیزات آن آسان است و قابل حمل می­باشد. در شبکه ­های بی­سیم نیازی به سیم­کشی­های طویل و دراز نیست.

اگر سازمانی از یک شبکه بی­سیم استفاده کند، کاربران قادر خواهند بود هر جا به صورت آنلاین با سایر کامپیوترها و چاپگرها ارتباط پیدا کنند. با بهره گرفتن از شبکه ­های بی­سیم می­توان عملیات زیادی انجام داد که در شبکه ­های سیمی امکان آن­ها وجود ندارد، یعنی سایر تکنولوژی­های شبکه دارای انعطاف و قابلیت شبکه بی­سیم نیستند. به همین دلیل
استفاده­کنندگان از شبکه ­های بی­سیم روز به روز افزایش می­یابند. اگر شخصی متصل به شبکه ­های بی­سیم باشد، محدودیتی از نظر مکان ندارد، یعنی شخص می ­تواند در هتل، فرودگاه، مرکز همایش و حتی کافی­شاپ و یا سایر محل­ها در صورت وجود پوشش، بدون هیچ محدودیتی با سرعت خیلی بالا به شبکه بی­سیم متصل شده و قابلیت استفاده از آن را داشته باشد [۳۱].

۱-۳-۱- قابلیت شبکه ­های بی­سیم

شبکه ­های بی­سیم دارای قابلیت ­های زیرند:

1. امکان ارتباطات موقت در شبکه.
2. پشتیبانی از شبکه موجود.
3. فراهم آوردن درجه­ای معین از قابلیت حمل^[۴۹].
4. گسترش دادن شبکه فراتر از محدودیت­های کابل­های مسی یا حتی فیبر نوری [۱۸].

۱-۳-۲- کاربردهای شبکه بی­سیم

بکار بردن مشکل کابل­ها در شبکه باعث می­ شود که شبکه ­های بی­سیم بسیار مورد قبول واقع شوند. شبکه ­های بی­سیم در موارد زیر بسیار مورد استفاده قرار می­گیرند:

1. محیط­های شلوغ مانند راهروها و محیط­های پذیرش.
2. ساختمان­ها و محیط­های منفرد.
3. بخش­هایی که گاهی محیط فیزیکی آن­ها تغییر می­ کند.
4. ساختار­هایی مانند ساختمان­های تاریخی که سیم کشی در آن­ها مشکل می­باشد و … [۱۸].

۱-۳-۳- شبکه ­های بی­سیم محلی ^[۵۰]

یک شبکه بی­سیم معمولی به جز در رسانگر مانند شبکه ­های سیمی عمل می­ کنند. در این نوع شبکه­ ها به یک نقطه دسترسی^[۵۱] و یک کارت شبکه نیاز خواهد بود [۱۸].

نقطه دسترسی

نقطه دسترسی دستگاهی برای برقراری ارتباط بین دستگاه­های بی­سیم و سیمی به یکدیگر است

که کار انتشار و دریافت سیگنال­ها را از کامپیوترهای اطراف برعهده دارد.

استفاده از نقاط دسترسی روش بسیار مفیدی جهت توسعه شبکه ­های بی­سیم می­باشد. در این حالت امکان اتصال به شبکه ­های سیمی یا اشتراک گذاری مودم پهن باند نیز وجود دارد.

در کل دو نوع نقطه دسترسی وجود دارد:

1. نقاط دسترسی­هایی که به عنوان یک پل بین شبکه بی­سیم و شبکه ­های سیمی بکار می­رود.
2. نقاط دسترسی­هایی که در آن­ها مسیریاب نیز تعبیه شده است و این مسیریاب باعث
   می­ شود که تمام کامپیوترهای موجود در شبکه به صورت اشتراکی به اینترنت دسترسی داشته باشند [۱۸].

کارت شبکه

هر یک از دستگاه­های موجود در یک شبکه بی­سیم به یک کارت شبکه بی­سیم نیاز خواهند داشت.

۱-۳-۴- تکنیک­های انتقال

شبکه ­های بی­سیم محلی از چهار تکنیک به منظور انتقال داده ­ها استفاده می­ کنند:

1. مادون قرمز^[۵۲]
2. لیزر^[۵۳]
3. امواج رادیویی پهن باند^[۵۴]
4. امواج ( تقسیم داده ­های مورد نظر به بخش­های کوچکتر جهت ارسال با بهره گرفتن از فرکانس­های گسسته و قابل دستیابی در هر زمان) [۱۸].

۱-۴- شبکه ­های سیار^[۵۵]

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

هدف ها این است که سیار بودن را در حیطه خود گسترش دهند. کاربرد وسیع از تکنولوژی در محیط­هایی است که تغییر ساختار به صورت پویا مورد نیاز است و شبکه بی­سیم در دسترس نیست. به عنوان مثال در میدان­های جنگ، جستجو­های اضطراری، موقعیت­های امداد و نجات و ….

افزایش لپ تاپ­ها و شبکه ­های بی­سیم باعث شده است که از سال­های ۱۹۹۰ تا ۱۹۹۵ به موضوع پژوهشی مورد پسندی تبدیل شود[۱۰].

فصل دوم

کدگذاری شبکه

مقدمه

هدف شبکه ­های ارتباطی انتقال اطلاعات بین گره­های مبدا و مقصد است. اولین سوالی که در طرح­ریزی شبکه پیش می ­آید این است که چگونه می­توان اطلاعات انتقال یافته در شبکه را افزایش داد. اخیرا نشان داده شده است که توانایی شبکه در انتقال اطلاعات می ­تواند به صورت چشمگیری بهبود یابد، این کار با بهره گرفتن از کدگذاری شبکه صورت می­گیرد. کد­گذاری شبکه حیطه پژوهشی جدیدی است که کاربردهای بسیار جالبی در سیستم­های شبکه کاربردی دارد. با بهره گرفتن از کد­گذاری شبکه، گره­های میانی به جای ارسال ساده اطلاعات، جریانی از اطلاعات را ارسال می­نماید که ممکن است پیچیده­تر از اطلاعات دریافتی پیشین باشد، به عنوان مثال گره­های میانی می­توانند ترکیبات خطی از اطلاعاتی را که پیش از این دریافت کرده ­اند، ارسال کنند. این شیوه ارسال اطلاعات کلید افزایش بازده بالقوه و قوای با درجه بالاتر می­باشد که در اینجا قوا به معنای کاهش برگشت بسته­ها و آسان­کردن پیاده­سازی الگوریتم­های توزیع است [۱۱،۴].

در بخش ۱ این فصل به بررسی عمل ساده می­پردازیم و در بخش ۲ کد­گذاری شبکه را مورد مطالعه قرار می­دهیم سپس در بخش ۳ پهنای باند و در بخش­­های ۴ و۵ و۶ به ترتیب توزیع­های تکی^[۵۶]، همگانی^[۵۷] و چندگانه^[۵۸] را بررسی می­کنیم و در ادامه در بخش ۷ توزیع قابل اعتماد را مورد بحث قرار می­دهیم.

۲-۱- عمل

عمل منطقی ترکیب مجزا^[۵۹] (ناسازگار) که گاهی یای ناسازگار^[۶۰] نیز نامیده می­ شود و با نمادهای یا ) نمایش داده می­ شود، یک ترکیب فصلی روی دو عملوند است که نتیجه آن تنها هنگامی درست است که دقیقا یکی از عملوند­ها درست باشند ( این یا دیگری ولی نه هر دو).

جدول زیر ترکیب دو عملوند و را تحت عمل نشان می­دهد.

جدول ۲-۱- ترکیب دو عملوند A وB تحت عمل XOR

INPUT		OUTPUT
A	B	A XOR B
۰	۰	۰
۰	۱	۱
۱	۰	۱
۱	۱	۰

یک سیستم با بهره گرفتن از یای مجزا یا ( و{F وT} ) یک گروه آبلی است. ترکیب
عملگر­های Λ و روی مولفه­های {F وT} میدان را تولید می­ کند. اگر سه داده ورودی داشته باشیم، نتیجه هنگامی درست است که دقیقا یکی ازاین داده ­ها درست باشد. اگر تعداد زیادی داده ورودی داشته باشیم، نتیجه هنگامی درست است که تعداد فرد از داده ­ها درست باشد.

۲-۲- کد­گذاری شبکه^[۶۱]

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

شکل ۲-۱مثالی ساده از کد­گذاری شبکه.

گره های و می­خواهند بسته­ها را از طریق گره میانی رد و بدل کنند. گره بسته و گره بسته را می­فرستد و در ادامه به جای و توزیع می­گردد و و می­توانند بسته­های مورد نظر خود را احیا کنند و در این حالت تعداد انتقالات کاهش می­یابد.

کد­گذاری شبکه در حیطه­هایی که تنها اطلاعات جزیی و یا غیر قطعی برای تصمیم گیری در دسترس است، بسیار مناسب می­باشد. دریافت موفقیت­آمیز اطلاعات، به دریافت حجم مشخصی از بسته­ها وابسته نیست بلکه به دریافت تعداد کافی از بسته­های مستقل وابسته است[۴].

۲-۲-۱- کد­گذاری خطی شبکه ^[۶۲]

سیستمی را در نظر بگیرید که مانند یک مسیریاب یا یک گره در یک شبکه توزیع نظیر به نظیر به ارسال اطلاعات می ­پردازد. در روش­های سنتی هنگامی که بسته­های اطلاعاتی به تعدادی از گره­ها می­رسیدند، آن گره­ها نیز به آسانی همین کار را تکرار می­کردند. با بهره گرفتن از کد­گذاری شبکه، به گره این اجازه را می­دهیم که تعدادی از بسته­هایی که دریافت کرده است را با هم ترکیب کند و به یک یا چند بسته خروجی تبدیل نماید. فرض کنید که هر بسته شامل بیت باشد. هنگامی که بسته­هایی که می­خواهند با هم ترکیب شوند دارای اندازه یکسان نباشند، بسته­هایی با اندازه کمتر با دنباله­ای از صفرها افزوده می­شوند. می­توانیم بیت متوالی از یک بسته را به صورت نمادی روی میدان معرفی کنیم و هر بسته شامل یک بردار با مولفه می­باشد. با استفاده ازکد­گذاری خطی شبکه، بسته­های خارج شده ترکیب خطی از بسته­های اصلی هستند، جایی­که جمع و ضرب روی میدان انجام می­ شود. دلیل انتخاب چارچوب خطی این است که الگوریتم­ها برای کد­گذاری^[۶۳] و از کد خارج کردن^[۶۴] بسیار قابل فهم هستند.

ترکیبات خطی سلسله­وار نیستند، اگر ما بسته­هایی به طول را با هم ترکیب کنیم، بسته کد­گذاری بدست آمده دارای طول است. یک بسته کد­گذاری شده عموما شامل اطلاعاتی در مورد چندین بسته اصلی است[۴].

۲-۲-۲- کد­گذاری

فرض کنید که تعدادی بسته اصلی ، توسط یک یا چند منبع تولید شده ­اند. در کد­گذاری خطی شبکه هر بسته در شبکه به دنباله­ای از ضرایب در مرتبط است و ، این مجموع برای هر مولفه استفاده می­ شود، یعنی جاییکه و به ترتیب امین مولفه هستند. به منظور ساده سازی فرض می­کنیم که هر بسته شامل ضرایب که بردار کد­گذاری نامیده می­ شود و داده کد­گذاری شده که بردار اطلاعات نامیده می­ شود، است. بردارهای کد­گذاری به منظور از کد خارج کردن داده ­ها توسط گیرنده­ها استفاده می­ شود. به عنوان مثال، بردار کد­گذاری ، جایی­که ۱ مولفه ام است، به این معناست که بردار اطلاعات برابر است. کدگذاری می ­تواند به صورت بازگشتی انجام گیرد. گره­ای را در نظر بگیرید که مجموعه از بسته­های کد­گذاری شده را دریافت و ذخیره کرده است. جایی­که بردار کد­گذاری امین بسته و بردار اطلاعات امین بسته است. این گره می ­تواند بسته کد­گذاری شده جدید را با انتخاب یک مجموعه از ضرایب را تولید و ترکیب خطی را محاسبه نماید[۴].

۲-۲-۳- از کد درآوردن

فرض کنید که یک گره مجموعه را دریافت کرده است. به منظور بازیابی بسته­های اصلی لازم است که دستگاه را حل کنیم. (جایی­که ها مجهول هستند.) این دستگاه خطی دارای معادله و مجهول است. به منظور داشتن شانس احیای تمام داده ­ها باید داشته باشیم ، یعنی تعداد بسته­های دریافت شده باید حداقل به بزرگی اندازه بسته­های اصلی باشد. برعکس شرط شرط کافی نیست، چون برخی از ترکیب­ها باید مستقل خطی باشند[۴].

۲-۲-۴- چگونه ترکیبات خطی را انتخاب کنیم؟

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

۲-۲-۵- ملاحظات عملی

در این بخش ابتدا به مبحث از کد خارج کردن اشاره می­کنیم. از کد درآوردن نیازمند حل یک مجموعه از معادلات خطی است که در عمل به صورت زیر انجام می­ شود.

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

دوره­ها^[۶۵]

برای تمام اهداف عملی باید اندازه ماتریس­ها برای کد­گذاری شبکه محدود باشد. این مساله برای کد­گذاری جبری شبکه­ ها مستقیما بدست می ­آید. اما در صورت کد­گذاری تصادفی
شبکه­ ها این امر بسیار مشکل می­باشد. در مورد آخر معمولا بسته­ها به دوره­هایی گروه­بندی می­شوند و تنها بسته­هایی که در یک دوره یکسان قرار دارند می­توانند با هم ترکیب شوند. اندازه و ترکیب دوره­ها می ­تواند تاثیر مهمی روی اجرای کد­گذاری شبکه داشته باشد. ملاحضاتی مشابه نیز برای اندازه میدان متناهی برقرار است. هر دو پارامتر باعث کاهش حافظه مورد نیاز و پیچیدگی­های مثلثاتی می­ شود [۴].

تاخیر

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

تاخیر پردازش: زمانی که به طول می­انجامد تا مسیریاب بسته­ها را پردازش کند.

تاخیر به صف کردن: زمانی که به صف کردن داده ­ها اختصاص می­یابد.

تاخیر انتقال: زمانی که به طول می­انجامد تا بیت­های بسته­ها در خط ارتباطی قرار گیرند.

تاخیر انتشار: زمان مورد نیاز برای رسیدن یک سیگنال به مقصد.

بسته­هایی که نیاز به از کد­ درآوردن دارند تاثیرات اندکی در تاخیر دارند. معمولا لازم نیست که تمام بسته­های کد­گذاری شده قبل از اینکه تعدادی از بسته­ها بتوانند از کد خارج شوند، دریافت شوند. (یعنی هرگاه قاعده حذفی گاوس منجر به ایجاد یک سطر به شکل شود.) در مجموع با کاهش انتقالات مورد نیاز، تاخیرات کلی در شبکه ­های کد­گذاری شده بزرگتر از تاخیرات در شبکه ­های عادی نیست [۴].

۲-۲-۶- مزایای کد­گذاری شبکه چیست؟

بازده مورد نظر در محیط استاتیک

اولین نتایجی که در کد­گذاری شبکه درخشید این است که کد­گذاری شبکه قادر است ظرفیت شبکه را برای جریان در توزیع با چند گیرنده افزایش دهد. شبکه­ ای را در نظر بگیرید که به صورت یک گراف جهت­دار نشان داده می­ شود ( عموما این شبکه سیمی است). رئوس گراف نظیر ترمینال­ها و یال­های گراف نظیر کانال­ها هستند. فرض کنید منبع داشته باشیم که هر یک اطلاعات را به نسبت مشخص ارسال می­ کنند و گیرنده داریم. تمام گیرنده­ها تمایل دارند که تمام منابع را دریافت کنند.

قضیه ۱. اگر نسبت­های منبع به گونه ­ای باشد که بدون کد­گذاری شبکه، شبکه بتواند هر گیرنده را به تنهایی حمایت کند. (یعنی هر گیرنده می ­تواند تمام منابع را هنگامی که تنها یک گیرنده در شبکه موجود باشد، از کد خارج کند.) در این صورت با انتخاب مناسب از ضرایب کد­گذاری خطی شبکه قادر است تمام گیرنده­ها را همزمان حمایت کند [۴].

به عبارت دیگر هنگامی که گیرنده در منابع شبکه مشترک هستند هر یک از آن­ها می ­تواند ماکزیمم نسبتی را که امید به دریافت آن داشته است دریافت کند. حتی اگر تمام منابع شبکه را خودش استفاده کند. از این رو کد­گذاری شبکه می ­تواند به اشتراک بهتر منابع شبکه در دسترس کمک کند.

قدرت­مندی و انطباق­پذیری

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

مجددا مثال شکل ۲-۱ را در نظر بگیرید و فرض کنید که و به صورت تصادفی و بدون توجه به موقعیت فعال نباشند (یا ممکن است از محدوده خارج شده باشند)، اگر ، یا را توزیع کند، از آن­جایی که گیرنده مورد نظر ممکن است قادر به دریافت بسته­ها نباشد، انتقالات کاملا بی­فایده خواهد بود. در حالی که اگر ، یا به صورت کلی­تر ترکیب خطی تصادفی از بسته­های اطلاعات را توزیع کند، انتقال می ­تواند اطلاعاتی جدید را به گره­های فعال منتقل کند[۴].

۲-۲-۷- مثال

در این قسمت شبکه پروانه­ای^[۶۶] را مورد بررسی قرار می­دهیم. در شبکه پروانه­ای ( شکل ۲-۲ ) دو منبع داریم (در بالای تصویر) که یکی دارای داده و دیگری دارای داده است. دو گره مقصد نیز موجود است (در پایین تصویر) که هر یک مایلند و را دریافت کنند. هر یال تنها قادر به انتقال یک مقدار است. اگر از روش­های عادی برای انتقال داده ­ها استفاده کنیم یال مرکزی تنها قادر به انتقال یا است و نمی­تواند هر دو را انتقال دهد. حال فرض کنید را از طریق یال مرکزی عبور دهیم. مقصد سمت چپ را دو بار دریافت می­ کند در حالی که را اصلا دریافت نمی­کند. مساله­ای مشابه در حالتی که تنها را از یال مرکزی عبور دهیم نیز رخ می­دهد. حال با بهره گرفتن از یک کد ساده می­توانیم و را همزمان به هر دو مقصد ارسال کنیم. با فرستادن داده از یال مرکزی مقصد سمت چپ با دریافت و قادر است را نیز تولید کند و مقصد سمت راست با دریافت و ، را تولید می­ کند. این کد­گذاری یک کد­گذاری خطی است، زیرا اعمال کد­گذاری و از کد خارج کردن هر دو خطی می­باشند.

شکل ۲-۲- شبکه پروانه­ای

۲-۲-۸- موارد استفاده از کد­گذاری شبکه.

در زیر تعدادی از کاربردهای کد­گذاری شبکه را مورد بررسی قرار می­دهیم.

توزیع فایل ^[۶۷]

احتمالا شناخته­ شده­ترین استفاده از کد­گذاری شبکه­ ها در است. به توزیعی در شبکه نظیر به نظیر گفته می­ شود که توسط پابلو رودریگز^[۶۸] و کریستس گانتسیدیس^[۶۹] در مایکروسافت^[۷۰] طراحی شد که در آن پهنای باند نسبت به سیستم نظیر به نظیر معمولی بهبود یافته است. برای توزیع­های با حجم زیاد در شبکه ­های نظیر به نظیر استفاده می­ شود و در آن کد­گذاری شبکه به کار گرفته می­ شود. در این­گونه شبکه توزیع سرویس دهنده، یک فایل بزرگ را به تعدادی بلوک می­شکند. گره­های هم­تراز سعی می­ کنند که فایل اصلی را با دانلود بلوک­ها از سرویس دهنده بازیابی کنند و بلوک­های دانلود شده را بین خودشان توزیع کنند. بدین منظور گره­های هم­تراز ارتباط خود را با تعداد محدودی از گره­های هم­تراز همسایه خود حفظ می­ کنند که این گره­های همسایه به صورت تصادفی از بین مجموعه گره­های هم­تراز انتخاب می­شوند. در بلوک­هایی که توسط سرویس دهنده فرستاده می­شوند به صورت ترکیب خطی تصادفی از بلوک­های اصلی هستند. به صورت مشابه گره­های هم­تراز، ترکیبات خطی تصادفی از تمام بلوک­هایی که در دسترس دارند را ارسال می­ کنند. یک گره می ­تواند تعیین کند که چه تعداد بلوک تغییر­یافته را می ­تواند به یکی از همسایگانش ارسال کند. این کار با مقایسه ماتریس ضرایب از کد درآوردن خود و همسایه­اش انجام می­گردد، یا اینکه به آسانی بلوک­های کد شده را ارسال می­ کند تا هنگامی که همسایه­اش اولین بلوک تغییر­نیافته را دریافت کند، سپس گره انتقالاتش را به این همسایه قطع می­ کند تا هنگامی که بلوک­های تغییر­یافته بیشتری را از دیگر گره­ها دریافت کند. ضرایب کد­گذاری به همراه بلوک­ها انتقال می­یابند. اما از آن­جایی که معمولا بلوک­ها دارای اندازه­ای در حدود هزاران کیلو بایت هستند، این اضافات اندک و نا چیز است. در اطلاعات به سرعت به تمام کاربران در شبکه می­رسد. یک گره جدید می ­تواند در طول مدت زمانی که عملیات توزیع در شبکه صورت می­گیرد به شبکه افزوده شود. کاربر جدید ابتدا به سرویس دهنده مرکزی متصل می­گردد و سپس با گره­هایی که در همسایگی­اش قرار دارند به تبادل جریان می ­پردازد.

کد­گذاری شبکه از جهات بسیاری به مساله­های زیر کمک می­ کند:

1. زمان دانلود را می­نیمم می­ کند. در یک سیستم توزیع با اندازه بزرگ طرح ریزی بهینه بسته­ها بسیار پیچیده است، به خصوص اگر کاربران اطلاعات بسیار محدودی در مورد ساختار شبکه داشته باشند. با بهره گرفتن از کد­گذاری شبکه، عملکرد سیستم بسیار کمتر به ساختار شبکه وابسته می­گردد. در نتیجه مکانیزم بسیار ساده­ای که یک پوشش تصادفی را می­سازد مورد استفاده قرار می­گیرد.
2. با توجه به عدم تشابه یا تفاوت بلوک­های کد شده، جواب بر پایه کد­گذاری شبکه در حالتی که سرور کارش را قبل از اینکه تمام جفت­ها دانلودشان را تمام کرده باشند یا در رویارویی با نسبت به شدت بالا ( هنگامی که گره­ها تنها برای مدت زمان کوتاهی با هم مرتبط باشند یا اینکه سریعا بعد از اتمام دانلودشان ارتباط آن­ها قطع شود .)، قطع کند، دارای قدرت بالاتری می­باشد.
3. کد­گذاری شبکه به گره­های شبکه این اجازه را می­دهد که به کد­گذاری بپردازند و این امر باعث ماکزیمم شدن بازده شبکه می­گردد.
4. بر­خلاف ارسال پروتکل­های اصلی، پروتکل کد­گذاری شبکه تنها خطای کوچکی را متحمل می­شوند [۴، ۲۹].

شبکه ­های بی­سیم

جریان دو طرفه در شبکه ­های بی­سیم

همان­گونه که در مثال شکل ۲-۱ دیدیم، متوجه شدیم که کد­گذاری شبکه می ­تواند هنگامی که دو گره با ارتباط بی­سیم تحت یک ایستگاه پایه­ای با هم ارتباط دارند، بازده را افزایش دهد. این حالت را می­توان به حالت در یک شبکه بی­سیم گسترش داد، جایی­که جریان بین دو گره انتهایی دو طرفه است و هر دو گره تعداد یکسانی بسته برای تغییر دارند. اگر برنامه­ای داشته باشیم که مسیریاب­های مجاور با هم مبادله داشته باشند بعد از چند گام اولیه، تمام مسیریاب­های میانی بسته­هایی را برای انتقال دو طرفه در مسیر در حافظه خود ذخیره کرده ­اند. هرگاه فرصت انتقال افزایش یابد یک مسیریاب دو بسته را هر یک برای یک جهت با عمل ساده با هم ترکیب و به همسایگانش توزیع می­ کند. هر دو مسیریاب گیرنده یکی ازبسته­هایی که در توزیع کدگذاری شده است را می­شناسند، در حالی که بسته دیگر برای آن­ها جدید است. بنابراین هر توزیع به دو گیرنده اجازه می­دهد که یک بسته جدید را دریافت کند که این کار ظرفیت مسیر را به طور موثری افزایش می­دهد.

شبکه ­های بی­سیم مش محلی^[۷۱]

حتی اگر کد­گذاری شبکه تنها از عمل محدود XOR برای ترکیب بسته­ها استفاده کند، می ­تواند به طور موثری کارایی شبکه ­های بی­سیم مش را افزایش دهد. تمام انتقال­ها توزیع و توسط همسایگان دریافت می­شوند. بسته­ها با خلاصه­ای از اطلاعات در مورد تمام بسته­های دیگری که یک گره تاکنون دریافت شده است حاشیه­نگاری می­ شود. بدین طریق اطلاعات در مورد اینکه کدام گره­ها کدام بسته­ها را در یک همسایگی توزیع می­ کنند نگهداری می­شوند. یک گره می ­تواند چندین بسته را تحت عمل XOR برای همسایگان متفاوت کد­گذاری کند و آن­ها را تحت یک انتقال ارسال نماید، مشروط بر اینکه هر همسایه هنوز اطلاعاتی برای از کد درآوردن اطلاعات داشته باشد [۴].

امنیت شبکه

در هر شبکه امنیت اطلاعات باید مد نظر قرار گیرد.

امنیت در برابر شنود که تلاش به احیاسازی بخش داده ­ها دارد. امنیت در برابر مهاجمان بدخواه که تلاش برای محروم کردن گیرنده­ها از اطلاعات با کاهش بسته­ها دارد و امنیت در برابر هجوم پارازیت.

کد­گذاری شبکه، محافظت در برابر شنود را بسیار آسان می­ کند، زیرا اطلاعات بیشتر گسترش می­یابند و شنیدن آن­ها مشکل است. مبدا، داده ­های اصلی را با اطلاعات تصادفی ترکیب می­ کند و یک کد شبکه را به طریقی که تنها گیرنده­ها قادر به از کد خارج کردن بسته­ها باشند، تولید می­ کند. علاوه بر این اطلاعات مشترک بین بسته­هایی که توسط شنود کننده دریافت می­ شود و بسته­های اصلی صفر است. نوع ضعیف­تری از امنیت بر این حقیقت استوار است که تنها گره­هایی می­توانند بسته­ها را از کد درآورند که به تعداد کافی بردارهای مستقل خطی دریافت کرده باشند کاری که شنود کننده­ها نمی ­توانند انجام دهند. کد­گذاری شبکه حفاظت در برابر کاهش بسته­ها در شبکه را نیز آسان می­ کنند. در یک شبکه بدون هیچ حفاظت اضافی، مهاجمان میانی می­توانند به دلخواه در بسته­ای تقلیل ایجاد کنند. در حالتی که از کد­گذاری شبکه استفاده شده باشد، مهاجم نمی­تواند به عمل از کد درآوردن بسته­ها در مقصد بدون داشتن تمام بسته­های کد­گذاری شده که توسط مقصد دریافت شده ­اند، غلبه کند. بسته­ها از طریق مسیرهای متفاوت جریان پیدا می­ کنند و این کار مهاجم را مشکل می­سازد. از سویی دیگر به نظر می ­آید که کد­گذاری شبکه امنیت شبکه در برابر هجوم پارازیت را ارتقا
می­بخشد. پارازیت می ­تواند عملکرد شبکه را مختل گرداند. در شبکه­ ای که پارازیت ایجاد
می­ شود، گره­هایی وجود دارند که بسته­های نامعتبر و خراب را منتشر می­ کنند. هنگامی که این بسته­های خراب توسط گیرنده­ها دریافت می­شوند، گیرنده­ها توانایی بازخوانی و از کد درآوردن آن­ها را ندارند، از این رو شبکه دچار اختلال می­گردد. چون در یک شبکه سرویس دهنده بسته داده ­ها را ارسال می­ کند، این بسته­ها معتبر و درست هستند در حالی که در شبکه­ ای که پارازیت وجود دارد گره­های میانی نیز موجودند که به ارسال بسته­های خراب و نامعتبر
می­پردازند. اگر از کد­گذاری در شبکه استفاده کنیم که در آن بردارهای کد­گذاری به صورت تصادفی انتخاب شده ­اند، از آنجایی که گره­های میانی که عمل کد­گذاری را انجام می­ دهند ممکن است پیش از این بسته­های خراب را نیز دریافت کرده باشند، بسته­های کد شده جدید نیز نامعتبر خواهند بود و از این رو تعداد بسته­های نامعتبر در شبکه افزایش می­یابد. در
این­گونه شبکه­ ها از کد­گذاریی استفاده می­ شود که در آن با بهره گرفتن از یک تابع به نام تابع هش^[۷۲] عمل کد­گذاری صورت می­گیرد و یک گره قبل از اینکه بسته­ای را دریافت کند، بررسی می­ کند که آیا این بسته معتبر است یا نه و در صورت معتبر بودن این بسته وارد ترکیب
کد­گذاری می­گردد. از آن­جایی که بررسی معتبر بودن بسته­ها عملی وقت­گیر است، هنگامی که یک گره یک بسته نامعتبر را می­شناسد به سایر گره­های همسایه اطلاع می­دهد که این بسته نامعتبر است تا آن­ها نیز آن را دریافت نکنند و در نهایت این امر باعث می­گردد تا گره­ها از پذیرش بسته­های نامعتبر خودداری کنند[۳، ۴].

۲-۳- پهنای باند

در ارتباطات، تفاوت بین بالا­ترین و پایین­ترین فرکانس­ها را پهنای باند گویند.

در یک شبکه تلفنی پهنای باند۳۰۰۰ هرتز است که از تفاوت بین پایین­ترین فرکانس ارسالی ممکن که ۳۰۰ هرتز است و بالا­ترین فرکانس ممکن که ۳۳۰۰ هرتز می­باشد به وجود می ­آید. در شبکه ­های کامپیوتری بزرگترین پهنای باند به سریع­ترین یا بزرگترین ظرفیت انتقال داده دلالت دارد [۱۸].

۲-۴- توزیع تکی

توزیع تکی اصطلاحی است که به ارتباطی گفته می­ شود که در آن اطلاعات از نقطه­ای به نقطه دیگر انتقال می­یابد. در این حالت تنها یک فرستنده و یک گیرنده داریم و اطلاعات از یک فرستنده به یک گیرنده خاص فرستاده می­ شود. هنوز توزیع تکی به عنوان بیشترین نوع انتقالات در شبکه ­های و اینترنت کاربرد دارد. شکل ۲-۳ نمونه ­ای از توزیع تکی را نشان می­دهد.

شکل ۲-۳- توزیع تکی

۲-۵- توزیع همگانی

توزیع همگانی به ارتباطی گفته می­ شود که در آن اطلاعات از یک نقطه به تمام نقاط فرستاده می­ شود. در این حالت تنها یک فرستنده وجود دارد، اما اطلاعات به تمام گیرنده­های مرتبط فرستاده می­ شود. از توزیع همگانی می­توان برای ارسال یک پیام یکسان به تمام کامپیوترها در یک شبکه استفاده کرد. شکل ۲-۴ نمونه ­ای از توزیع همگانی را نشان می­دهد.

شکل ۲-۴- توزیع همگانی

۲-۶- توزیع چندگانه

توزیع چندگانه به ارتباطی گفته می­ شود که در آن اطلاعات از یک نقطه به مجموعه ­ای از نقاط فرستاده می­ شود در این حالت یک و یا شاید چند فرستنده داشته باشیم که اطلاعات را به گروهی از گیرنده­ها می­فرستند. (تعداد گیرنده­ها می ­تواند یک یا بیشتر باشد) نمونه ­ای از کاربرد توزیع چندگانه در کنفرانس­های تلفنی و ارسال ویدیو یا صدا به گروه خاصی از گیرنده­هاست.

شکل ۲-۵ نمونه ­ای از توزیع چندگانه را نشان می­دهد [۲۳].

شکل ۲-۵- توزیع چندگانه

۲-۷- توزیع قابل اعتماد^[۷۳]

ما نیاز به تعریف دقیقی از توزیع قابل اعتماد داریم. تعریف­های متعددی در این زمینه موجود است. تعریفی کلی در سال ۲۰۰۲ توسط لی^[۷۴] ارائه شد که در آن سه سطح از توزیع قابل اعتماد بسته داده ­ها مشخص شده است که در ادامه آمده­اند:

1. تمام بسته­های داده ­ها رسانده شوند.
2. تمام ترتیب­ها بین بسته­ها نگهداری شود.
3. ترتیب کلی رساندن بسته­ها حفظ شود.

تمام تعریف­ها نیاز دارند که فرستنده یک بسته داده را ارسال کند و تمام گیرنده­های موجود در توزیع چندگانه آن را دریافت کنند. در صورتی که چند بسته داده ارسال شود که گیرنده­های آن­ها مشابه یا متمایز باشند، هیچ تضمینی وجود ندارد که ترتیب خاصی برای دریافت بسته­ها حفظ شود. به عنوان مثال اگر فرستنده دو بسته را ارسال کند، گیرنده مایل است که را قبل از دریافت کند در حالی که ممکن است تمایل داشته باشد با ترتیب عکس بسته­ها را دریافت کند (یعنی را قبل از دریافت کند). حال آن­که رساندن تمام بسته­ها می ­تواند به عنوان کم­ترین نیاز هر مکانیزم توزیع قابل اعتماد در نظر گرفته شود، در برخی موارد شرط­های دقیق­تر و سخت­گیرانه­تری مورد نظر می­باشد، به عنوان مثال ممکن است ترتیبی که بسته­ها دریافت می­شوند به عنوان شرط مورد نیاز در توزیع قابل اعتماد باشد برای نمونه می­توان به گونه ­ای از توزیع چندگانه اشاره کرد که در آن بسته­ها، اعمال روی داده ­ها را به روز­ رسانی می­ کنند. اگر دو گیرنده این بسته­های به روز رسانی را با ترتیب­های متفاوت دریافت کنند، نتایج متفاوت خواهند بود. به عنوان مثال فرض کنید که یک متغیر صحیح با مقدار اولیه ۱۰ داریم. اگر بسته به گیرنده بگوید که مقدار را دو برابر کند و بسته از گیرنده بخواهد که ۵ واحد به اضافه کند، مقدار نهایی بعد از اینکه ابتداو سپس را دریافت کند، ۲۵ خواهد بود، به صورت مشابه مقدار نهایی گیرنده که ابتدا و سپسرا دریافت کرده است ۳۰ خواهد بود، زیرا ابتدا ۵ واحد بهاضافه کرد و بعد از آن مقدار آن را دو برابر نمود.

تفاوت بین تعریف­های دوم و سوم توزیع قابل اعتماد در قید پذیرش بسته­های متفاوت است. جدی­ترین تعریف، تعریف سوم است که ترتیب بین تمام بسته­های توزیع چندگانه تعریف می­ شود (که می­توانند از فرستنده­های یکسان یا متفاوت فرستاده شده باشند) و اجبار می­ کند که تمام گیرنده­ها تمام بسته­ها را دقیقا به ترتیب دریافت کنند. ترتیبی که در آن بسته­های توزیع چندگانه به تمام گیرنده­ها فرستاده می­شوند، ترتیب کلی^[۷۵] نامیده می­ شود.

تعریف دوم کمی ضعیف­تر است و ترتیبی را اجرا می­ کند که به آن ترتیب جزئی^[۷۶] روی بسته­های توزیع چندگانه رسانده شده گفته می­ شود که درآن روی تمام بسته­ها قید ترتیب نداریم. به صورت بسیار مختصر، این تعریف می­گوید که اگربتواند روی تاثیر بگذارد، تمام گیرنده­ها بایدرا پیش از دریافت کنند، در صورتی که هیچ تاثیری روی نداشته باشد گیرنده­ها می­توانند بدون ترتیب خاصی بسته­هایو را دریافت کنند. بسته می ­تواند روی بسته این چنین تاثیر بگذارد:

1. بعد از توسط فرستنده­ای یکسان ارسال شود.
2. هنگامی توسط فرستنده ارسال شود کهدریافت شده باشد.

در این موارد می­گویند که بر مقدم است. از آن­جایی که این رابطه ترتیبی را برای تمام بسته­ها اجبار نمی­کند، به آن ترتیب جزئی گویند [۱۰].

فصل سوم

توزیع قابل اعتماد کد محور در شبکه ­های بی­سیم

مقدمه

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

۳-۱- تاریخچه

پهنای باند یکی از مسایل مهم در شبکه ­های بی­سیم است. تکنیک­های کد­گذاری شبکه که به گره­های شبکه این امکان را می­دهد که عمل کد­گذاری را روی داده ­ها انجام دهند، تاثیر بسیاری در کاهش پهنای باند و مصرف انرژی در شبکه ­های بی­سیم دارند، این مساله در سال ۲۰۰۰ توسط آلسود^[۷۷] بررسی شد[۱]. امروزه تلاش­ های قابل توجهی در خصوص استفاده از کد­گذاری شبکه­ ها در نمونه­های ارتباطی متفاوت صورت گرفته است. یو^[۷۸] در سال ۲۰۰۵ نشان داد که تغییر اطلاعات مستقل بین دو گره در یک شبکه بی­سیم می ­تواند توسط کد­گذاری شبکه و توزیع فیزیک محور صورت گیرد[۲۷]. لی^[۷۹] در سال­های ۲۰۰۴ و ۲۰۰۵ به بررسی حالاتی از چندین توزیع تک گیرنده پرداخت و دریافت که کد­گذاری شبکه تنها می ­تواند فوایدی حاشیه­ای داشته باشد[۱۳، ۱۴]. کاتی^[۸۰] در سال ۲۰۰۶ کد­گذاری را ارائه داد که در آن کد­گذاری بر اساس معماری شبکه صورت می­گیرد () و به صورت موثری بازده شبکه را در شبکه ­های بی­سیم بالا می­برد[۹]. در سال­های ۲۰۰۶ و ۲۰۰۷ ، سنگوپتا^[۸۱] به بررسی
کد­گذاری شبکه با عمل بر اساس معماری شبکه پرداخت[۲۰، ۲۷]. تلاش­هایی نیز در خصوص تخمین بازده شبکه­ هایی بی­سیم در حالت کد­گذاری بر اساس ساختار شبکه صورت گرفته است[۱۲، ۱۶، ۲۷]. روای هب^[۸۲] ترکیبات کلی و پیچیده­تری را نسبت به ترکیبات تحت نام کد­بندی شاخص^[۸۳] بررسی کرد[۲۴]. اخیرا تلاش­هایی نیز در خصوص کد­گذاری فیزیک محور شبکه ­های بی­سیم صورت گرفته است[۸، ۳۰]. یو در سال ۲۰۰۵ نشان داد که در یک شبکه سیار استفاده از کد­گذاری شبکه به منظور می­نیمم کردن هزینه توزیع می ­تواند به صورت یک مساله بهینه سازی خطی مدل سازی شود [۲۱]. الگوریتم­های غیر متمرکزی توسط لون^[۸۴] در سال ۲۰۰۶ به منظور ساخت درخت توزیع با هزینه می­نیمم ارائه شدند[۱۷]. پارک^[۸۵] در سال ۲۰۰۶ به بررسی تئوری توزیع چندگانه به وسیله کد­گذاری در شبکه ­های غیر قابل اطمینان پرداخت [۲۲] با توجه به کاربرد کد­گذاری شبکه برای توزیع در شبکه ­های بی­سیم، الگوریتم­هایی احتمالی و قطعی برای توزیع به ترتیب توسط فراگولی^[۸۶][۵، ۶] و لی[۱۳] ارائه شدند که نتایجی مهم در ذخیره سازی انرژی داشتند.

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

	۱	۲	۳	۴	۵	۶	۷	۸	۹
		O	O		O	O		O
	O	O		O		O		O	O

شکل ۳-۱

فرض می­کنیم که بسته­های کد شده و۹ باشند. در طرح استاتیک اگر بسته به درستی توسط هیچ گیرنده­ای دریافت نشود، این بسته آن­قدر ارسال می­گردد تا تمام گیرنده­ها این بسته را دریافت کنند و گیرنده­ها با کمک بسته کد شده­ای که دریافت شده است و بسته­هایی که پیش از این دریافت کرده بودند به احیای بسته­های مورد نظرشان می­پردازند. هنگامی که هر دو گیرنده بسته­ی یکسانی را ازدست داده باشند نیازی به کد­گذاری آن بسته نیست و مبدا آن بسته را به تنهایی مجددا ارسال می­نماید. طرح پیشرفته­تری بدین صورت است که مبدا به صورت پویا بسته­ها را کد­گذاری می­نماید. حال فرض کنید که بسته ارسال شود و گیرنده نتواند این بسته را دریافت کند اما گیرنده این بسته را به درستی دریافت کرده باشد. در این حالت به جای ارسال مجدد بسته مبدا می ­تواند بسته را ارسال گرداند. در این روش تعداد انتقالات به صورت موثری کاهش می­یابد که بعدا به بررسی این مطلب خواهیم پرداخت [۱۹].

عمل ساده دارای مزیت کد­گذاری و از کد خارج کردن سریع است که ابزاری مناسب برای شبکه­ هایی است که توانایی عملیاتی گره­ها در آن­ها بسیار محدود می­باشد، مانند
شبکه ­های سنسور^[۸۸]. لازم به ذکر است که کد­گذاری بسته­ها با عمل (روی میدان ) دارای دو محدودیت عمده می­باشد، اول اینکه، تنها بسته­های از دست رفته که گیرنده­های مایل به دریافت آن­ها متمایز بودند می­توانند با هم ترکیب شوند و از این رو فرصت­های بالقوه
کد­گذاری نمی ­توانند به صورت کامل به کار گرفته شوند. در واقع بسته­های از دست رفته با گیرنده­های یکسان نیز با عمل­های کد­گذاری کلی­تر ظرفیت ترکیب با یکدیگر را دارند. این کار به منظور بهبود در تاثیرات انتقال صورت می­گیرد و دوم اینکه جستجو برای یافتن مجموعه بهینه از بسته­های از دست­رفته یک مساله پیچیده است. این موارد توانایی این دو طرح را به طرز چشمگیری محدود می­ کنند.

در این فصل گام فراتر از عمل ساده می­نهیم و به بررسی اعمال کد­گذاری کلی­تر می­پردازیم تا به هدف­های کد­گذاری بزرگتری در شبکه ­های بی­سیم معمولی (مانند شبکه ­های سلولی^[۸۹]( برسیم. به منظور توزیع قابل اعتماد در شبکه ­های بی­سیم دو طرح جدید را با کد­گذاری به روش­های کلی­تر مورد بررسی قرار می­دهیم.

قسمت­ های اصلی این فصل بدین شرح است :

1. ابتدا به بررسی محدودیت­های کد­گذاری ساده می­پردازیم و سپس آن را به اعمال کد­گذاری کلی­تری توسیع می­دهیم، سپس به بررسی دو طرح استاتیک و پویا خواهیم پرداخت که در آن­ها کد­گذاری بسته­ها با روش کد­­گذاری کلی­تری که در آن­ها ظرفیت­های بالقوه کد­گذاری کاملا به کار گرفته می­ شود و پیچیدگی زمانی را به صورت چشمگیری کاهش می­دهد، انجام می­ شود.
2. ما به بررسی تحلیلی دو طرح فوق به منظور ارزیابی بازده انتقال و تاخیر در دریافت بسته­ها در این طرح­ها خواهیم پرداخت.
3. نتایج حاصل از استفاده این دو طرح را در کاهش پهنای باند مورد بررسی قرار می­دهیم، کاهش در پهنای باند به صورت چشمگیری اتفاق می­افتد، به خصوص در حالتی که تعداد بسته­های از دست رفته و تعداد گیرنده­ها زیاد باشد.

ادامه این فصل به صورت زیر سازمان دهی شده است.

در بخش ۲، ابتدا به بررسی محدودیت­های کد­گذاری ساده می­پردازیم و سپس دو طرح جدید را ارائه می­­کنیم.

در بخش ۳، ما به صورت تحلیلی به ارزیابی پهنای باند انتقال و عمل تاخیر برای دو طرح بررسی شده می­پردازیم، نتایج عددی بدست آمده از مدل تحلیلی و شبیه سازی در بخش ۴ مورد بررسی قرار می­گیرد و نهایتا در بخش ۵ به بررسی نتیجه حاصل از استفاده از طرح­های مورد بحث قرار گرفته، خواهیم پرداخت.

۳-۲- طرح­های توزیع کد محور

در این بخش ابتدا به معرفی محدودیت­های عمل کد­گذاری می­پردازیم و سپس
طرح­­هایی جدید را برای توزیع قابل اعتماد در شبکه ­های بی­سیم ارائه می­دهیم. طرح­های جدید که بسته_­ها را با اعمال کد­گذاری کلی­تری نسبت به کد­گذاری می­ کنند، نه تنها قادرند بسته­های از دست رفته با گیرنده­های یکسان را کد­گذاری کنند بلکه دارای پیچیدگی چند جمله­ای می­باشند.

۳-۲-۱- محدودیت­های عمل کد­گذاری

علی رغم اینکه در روش­های کد محور با کد­گذاری ، پهنای باند مورد نیاز در مقایسه با روش­های سنتی غیر کد­گذاری، بسیار کمتر است اما روش­های کد محور با کد­گذاری دارای دو محدودیت زیر می­باشند. اول اینکه تنها بسته­های از دست رفته با گیرند­ه های متمایز می­توانند با هم کد­گذاری شوند و از این رو ظرفیت­های بالقوه کد­گذاری نمی ­توانند کاملا بکار گرفته شوند در حالی که بسته­های از دست­رفته با گیرنده­های یکسان نیز می­توانند به منظور بالا بردن تاثیرات انتقال با هم کد­گذاری شوند. به عنوان مثال برای بسته­های از دست­رفته در شکل ۳-۲، هنگامی که از عمل کد­گذاری استفاده کنیم، هیچ شانسی برای کد­گذاری موجود نیست، زیرا هر دو بسته از دست رفته دارای گیرنده­های مشترک هستند. در این مثال مبدا نیاز دارد که حداقل ۳ بار عمل انتقال مجدد را انجام دهد در حالی که اگر بسته­ها با اعمال کد­گذاری کلی­تری، کد­گذاری شوند به انتقال­های کمتری احتیاج داریم. ( این مساله در ۳-۲-۲ مورد بحث قرار می­گیرد.)

	×	o	×	×
	o	×	×	o
	×	×	o	×

شکل ۳-۲- مثالی از اینکه هیچ امکانی برای کد­گذاری هنگامی که از طرح­های کد محور در دسترس استفاده می­کنیم وجود ندارد.

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

فرض کنید که تعداد بسته­های از دست­رفته باشد. بدون کاسته شدن از کلیت مساله فرض می کنیم ، بسته­های از دست­رفته باشند. سپس مساله بهینه سازی می ­تواند به این صورت مدل سازی شود.

داده ­ها : مقادیر ، به این معنا است که به درستی را دریافت نکرده است و به این معنا می­باشد که به درستی را دریافت کرده است. بسته کد شده به صورت می­باشد. Maximize : Subject to : . . .

قضیه ۱٫ مساله کد­گذاری ماکزیمم بسته­های از دست­رفته^[۹۰] یک مساله است [۲].

نماد­های به کار رفته در طرح­های مورد بررسی قرار گرفته در بخش ۳ به صورت خلاصه در جدول ۳-۱ آمده است.

جدول ۳-۱- نماد­های به کار رفته در طرح­های بررسی شده

معنا

نماد

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

۳-۲-۲- طرح جامع کد محور استاتیک^[۹۱]()

مشابه طرح­های کد محور در دسترس، این طرح نیز شامل فاز انتقال و فاز انتقال مجدد است. فاز انتقال این طرح مانند حالت قدیمی است که مبدا به آسانی تعداد ثابتی از بسته­ها را یک به یک انتقال دهد. تمام این بسته­ها یک دوره نامیده می­شوند. در طول فاز انتقال مجدد، به جای استفاده از یک الگوریتم پیچیده به منظور یافتن مجموعه بهینه از بسته­های از دست­رفته برای انجام عمل روی آن­ها، ابتدا یک تقریب ساده (گام ۱) را بیان می­کنیم که در آن تمام بسته­های از دست­رفته به مجموعه­های متفاوت گروه­بندی می­شوند و سپس مبدا مجموعه به مجموعه به ارسال بسته­های از دست­رفته می ­پردازد.

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

گام ۱ . ( گروه­بندی بسته­های از دست رفته )

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

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

با توجه به اینکه اعمال کد­گذاری کلی ( روی میدان متناهی انتخابی ) نسبت به عمل ساده بر روی مجموعه ­ای از بسته­های از دست­رفته مبدا را قادر می­سازد که بسته­های کد شده متفاوتی را برای انتقال ایجاد کنند (که در صورت استفاده از عمل غیر قابل بدست آمدن بودند) از این رو ظرفیت­های بالقوه کد­گذاری می­توانند به صورت بسیار موثرتری به کار گرفته شوند.

بیایید مجددا مثال ۳-۲ را در نظر بگیریم. با بهره گرفتن از طرح ، مبدا بسته­های ، و را در یک مجموعه قرار می­دهد. آن­گاه مبدا می ­تواند ابتدا بسته کد شده و سپس را انتقال دهد. هنگامی که این دو بسته کد شده را دریافت کند، می ­تواند و را با روش حذفی گاوس از کد خارج کند. به صورت مشابه و
می­توانند تمام بسته­ها را بازیابی کنند. بدین طریق این امکان وجود دارد که انتقال مجدد ، و را تنها با دو بار نسبت به حداقل سه بار در روش قدیمی خاتمه دهیم.

برای یک مجموعه از بسته­های اصلی ( یعنی بسته­های کد­گذاری نشده ) و یکی از بسته­های کد­گذاری شده­اش، روی میدان متناهی با پایه (یعنی ) ، () را با بردار کد­گذاری روی می­نامیم و با نشان می­دهیم. اکنون مساله اصلی انتخاب بردار کد­گذاری () برای هر انتقال مجدد است. قبل از انتخاب مجدد هر مجموعه از بسته­های از دست رفته، مبدا در ابتدا نیاز به تعیین پارامتر­های اولیه دارد.

گام ۲٫ (تعیین پارامتر­های اولیه )

برای مجموعه داده شده از بسته­های از دست­رفته فرض کنید تعداد بسته­ها در باشند که هنوز دریافت نکرده است. مقدار با () تعیین گردد و مجموعه از بردار­های کد­گذاری شده به صورت زیر تعیین می­ شود:

جاییکه مجموعه ماکزیمم از بردارهای - بعدی روی میدان متناهی است که شامل بردار یکه (۰و…و۰و۱) و… (۱و…و۰) است و هر بردار از این مجموعه مستقل خطی هستند.

گام ۳٫(انتخاب بردار کد­گذاری)

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

بعد از انتقال مجدد بسته کد­گذاری شده، مبدا نیاز دارد که پارامترهای و را به صورت آنچه در ادامه می ­آید، به روز رسانی کند.

گام ۴٫ ( به روز رسانی پارامترها)

برای هر گیرنده غیر اشباع ( با ) ، اگر به درستی را دریافت کند، داریم . برای هر بسته کد­گذاری شده از {بسته­های کد­گذاری شده انتقال یافته از } U ، اگر آن­گاه بردار کد­گذاری می ­تواند مجددا مورد استفاده قرار گیرد و بنابراین .

با خلاصه گام­های فوق، طرح در جدول ۳-۲ آمده است.

جدول ۲-۳ - طرح توزیع استاتیک جدید

Procedure of the SGC scheme Steps: transmit native packets one by one and build the packet-loss table. Conduct procedure 1 to group lost packets into sets. For to k do Let be the jth set of lost packets. Conduct procedure 2 to initialize parameters and . While exist one or more unsaturated receivers ( i.e. , ) do Conduct procedure 3 to select a coding vector and obtain an encoded packet . Repeatedly transmit packet until at least one unsaturated receiver receive it. Conduct procedure 4 to update parameters and . end while end for

در ادامه به بررسی اندازه لازم میدان و پیچیدگی­های این طرح می­پردازیم.

۳-۲-۲-۱- اندازه میدان

هنگامی که تعداد گیرنده­ها افزایش یابند، اندازه لازم ( و از این رو اندازه لازم از ) افزایش می­یابند. قضیه بعد شرط لازم و کافی را برای اندازه میدان مورد نیاز نشان می­دهد.

قضیه ۲٫ برای تعداد گیرنده­های داده شده ، طرح استاتیک مطرح شده، همیشه می ­تواند یک بسته تغییر یافته را برای تمام گیرنده­های اشباع نشده تضمین کند اگر و تنها اگر در رابطه­ صدق کند.

اثبات: ماکزیمم هنگامی مورد نیاز است که بدترین حالت زیر رخ دهد:

هر بسته انتقال یافته، دقیقا توسط یک گیرنده دریافت شود و هر گیرنده بسته را دریافت کرده باشد، همانند آنچه در شکل ۳-۳ نشان داده شده است. در بدترین حالت، بسته تغییر یافته تاکنون انتقال یافته­اند. اگر یک بسته تغییر یافته بیشتر برای تمام گیرنده­ها به منظور انتقال داشته باشیم، آن­گاه هنگامی که یک گیرنده این بسته تغییر یافته را دریافت کند، می ­تواند بسته را احیا کند و نیازی به دریافت تعداد بیشتری بسته ندارد. بنابراین هر بسته­ای که پیش از این توسط دریافت شده باشد می ­تواند برای انتقال مجدد مورد استفاده قرار گیرد که برای تمام گیرنده­های غیر اشباع باقیمانده تغییر می­یابد. □

	o	o	×	×	×	×
	×	×	×	o	o	×
	×	×	o	×	×	o

شکل ۳-۳ - مثالی که نیاز به ماکزیمم بسته­های تغییر یافته دارد

۳-۲-۲-۲- پیچیدگی­های محاسباتی

اینجا به اختصار به تحلیل پیچیدگی­های محاسباتی بسته­های کد شده بدست آمده برای انتقال در طرح می­پردازیم.

در طول فاز انتقال، مبدا بسته­های اصلی را انتقال می­دهد که تنها نیاز به یک زمان ثابت دارد. در طول فاز انتقال مجدد، مبدا ابتدا نیاز به زمان برای گرفتن و محاسبه دارد. سپس برای هر انتقال مجدد مبدا نیاز به زمان برای ترکیب خطی بسته از دست­رفته و زمان برای به روز رسانی پارامتر و برای به روز رسانی پارامتر دارد. بنابراین پیچیدگی محاسباتی کل برای بدست آوردن بسته کد­گذاری شده برای انتقال مجدد است [۲].

۳-۲-۳- طرح جامع کد محور پویا^[۹۵] ()

طرح نیز شامل فاز انتقال و فاز انتقال مجدد است. مشابه طرح ، طرح نیز اصل کد­گذاری محدود را حذف می­ کند و از الگوریتمی ساده به منظور یافتن مجموعه ­ای از بسته­های از دست­رفته برای کد­گذاری استفاده می­ کند. تفاوت عمده این دو طرح این است که در طرح ، بسته­های از دست­رفته به صورت پویا برای هر انتقال مجدد به روز رسانی
می­شوند به قسمی که ظرفیت­های بالقوه کد­گذاری به صورت موثرتری به کار گرفته می­شوند.

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

گام ۱٫ ( تعیین پارامتر )

فرض کنید مجموعه ­ای از بسته­ها در دوره جاری باشد و مجموعه ­ای از بسته­ها برای کد­گذاری در دوره جاری باشد و مجموعه ­ای از بردارهای کد شده از بسته­های کد­گذاری شده است که تا کنون توسط دریافت شده ­اند. را تعیین می­کنیم و را به عنوان مجموعه تهی را در نظر می­گیریم. در هر انتقال مجدد نیاز به تعریف مجموعه و نیز بردار کد­گذاری روی مجموعه برای بدست آوردن بسته کد­گذاری شده داریم.

گام۲٫( مشخص کردن )

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

• به روز رسانی : برای هر گیرنده با مساوی و هر قرار می­دهیم زیرا تمام بسته­های از دست­رفته در را احیا کرده است.
• حذف بسته­ها : برای هر بسته که در صدق کند، ابتدا بردار
  کد­گذاری را به صورت زیر تنظیم می­کنیم : برای هر و هر بردار از مولفه نظیر بسته را حذف می­کنیم و اگر نتیجه باشد قرار می­دهیم و سپس بسته را از حذف می­کنیم.
• اضاف کردن بسته­ها : برای هر بسته در اعمال زیر را اعمال می­کنیم : بررسی
  می­کنیم که آیا حداقل یک گیرنده موجود است که در و صدق کند. اگر چنین است ابتدا بسته را به اضافه کنید سپس برای هر یک مولفه جدید صفر در انتهای می­افزاییم و اگر یک بردار یکه با بعد به صورت (۱و…و۰و۰) به اضافه می­کنیم.

با داشتن مجموعه ، تعیین بردار کد­گذاری روی به صورت زیر انجام می­گیرد.

گام ۳٫ ( تعیین بردار کد­گذاری )

ابتدا برای هر گیرنده با یک بردار که مستقل از است را با بهره گرفتن از روش حذفی گاوس بدست می­آوریم و یک مجموعه عمود با عمود سازی بردارهای تولید می­کنیم، سپس برای هر بردار بدست آمده قرار می­دهیم :

سرانجام با بدست آمده از تقریبی که در زیر معرفی شده است به منظور بدست آوردن بردار کد­گذاری که در رابطه برای هر صدق می­ کند، استفاده می­کنیم. با توجه به اثبات لم ۳ می­توان طریقه یافتن را دریافت.

لمی که در ادامه می ­آید نشان می­دهد که بدست آمده از هر مستقل است.

تعریف: بردار را بر مجموعه که شامل بردارهای - بعدی است، عمود گویند، هرگاه برای هر داشته باشیم .

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

گام ۳ تضمین می­ کند که بردار کد­گذاری انتخاب شده از بردارهای کد­گذاری بسته­های دریافت شده این گیرنده مستقل است. به وضوح روش کد­گذاری پویا می ­تواند میانگین تعداد انتقال­های مجدد را در هر دوره کاهش دهد. طرح به صورت اختصار در جدول ۳-۳ آمده است. بعد از آن به اختصار به بررسی اندازه میدان مورد نظر و پیچیدگی­های محاسباتی این طرح
می­پردازیم.

جدول ۳-۳- طرح جدید پویا

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 ,. End while

۳-۲-۳-۱- اندازه میدان

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

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

اگر آن­گاه . اگر آن­گاه زیرا یک میدان حداقل دو عضو دارد . □

نتیجه ۱٫ اگر و، آنگاه برای بردارهای یک ترکیب خطی از موجود است به قسمی که برای هر [۲].

لم۳٫ ترکیب خطی که وجود آن در لم ۲ اثبات شده است، در بدترین حالت در زمان ) بدست می ­آید.

اثبات: اثبات با استقرا روی انجام می­ شود. برای به آسانی قرار می­دهیم برای گام استقرا از به از فرض استقرا برای بدست آوردن بردار با برای استفاده می­کنیم. اگر غیر صفر باشد، نتیجه حاصل شده است در غیر این صورت لم ۲ را برای بکار می­بریم. چون ، ترکیب خطی موجود است به قسمی که برای هر داریم . در حالت خاص چون ، از این رو و به فرم است و برای هر داریم . ضریب را می­توان با آزمودن تمام مولفه­های میدان بدست آورد. تمام آزمون می ­تواند در زمان با از پیش محاسبه کردن ضرب­های اسکالر برای انجام می­ شود. برای تکرار زمان مورد نیاز است [۲۴]. □

مشابه طرح ، طرح نیز عمل کد­گذاری را عموما روی میدان متناهی انجام می­دهد. قضیه زیر نشانگر شرط لازم برای اندازه برای این طرح است.

قضیه ۳٫ مقدار داده شده است، اگر ، آنگاه در طرح همواره یک بسته تغییر یافته برای تمام گیرنده­های غیر اشباع شده برای انتقال مجدد موجود است.

اثبات: بر اساس نتیجه ۱ می­توانیم به آسانی نتیجه دلخواه را بدست آوریم. □

۳-۲-۳-۲- پیچیدگی محاسباتی

در اینجا به بررسی پیچیدگی محاسباتی بدست آوردن یک بسته انتقال هنگامی که از طرح استفاده می­کنیم می­پردازیم. در طول فاز انتقال، مبدا تنها به انتقال بسته­های اصلی می ­پردازد که تنها به زمان ثابتی نیاز دارد. در طول گام ۲ از فاز انتقال مجدد، به روز رسانی به میزان زمان نیاز دارد. حذف بسته­ها از و به روز رسانی پارامترهای مرتبط با و افزودن بسته­ها به و به روز رسانی پارامترهای مرتبط به زمان نیاز دارد. در گام ۳ روش حذفی گاوس و گام متعامد سازی و محاسبه ´ به ترتیب و و زمان احتیاج دارند. بنابراین پیچیدگی محاسباتی کلی است [۲].

۳-۳- تحلیل اجرا

در این بخش به بررسی تحلیل تئوری این دو طرح جدید بر حسب تاثیر انتقال و تاخیر اجرا می­پردازیم.

با تاثیر انتقال، متریکی مشابه آنچه نگوین در سال ۲۰۰۷ معرفی کرد به نام پهنای باند انتقال به عنوان میانگین انتقال­های مورد نیاز برای انتقال موفق یک بسته به تمام گیرنده­ها، تعریف می­ شود. در این­جا تاخیر اجرا را میانگین تعداد انتقال­هایی که نیاز است از زمانی­که یک بسته برای اولین بار انتقال یابد تا هنگامی که تمام گیرنده­ها آن را به درستی دریافت کنند، تعریف می­کنیم. (که در اینجا به آن تاخیر انتقال مجدد گوییم)

پیش از اینکه با جزئیات به تحلیل اجرای طرح­های بررسی شده بپردازیم، به بررسی کران پایین پهنای باند انتقال می­پردازیم که با بهره گرفتن از آن می­توانیم ایده­هایی در خصوص تاثیر مسایل مطرح شده بدست آوریم. ( این مبحث در بخش ۴ مورد بررسی قرار می­گیرد. )

قضیه ۴٫ برای توزیع قابل اعتماد با گیرنده، نسبت انتقال بسته در گیرنده را با نشان می­دهیم. در این صورت پهنای باند انتقال ، کران پایینی به صورت زیر دارد.

اثبات: بیایید گیرنده­ای را با مینیمم نسبت انتقال بسته در میان تمام گیرنده­ها در نظر بگیریم. برای این گیرنده میانگین تعداد انتقال های مورد نیاز برای دریافت موفقیت آمیز یک بسته عبارت است از چون گیرنده­های دیگری نیز موجودند که نیاز به دریافت بسته­ها از مبدا دارند، میانگین تعداد انتقال­های مورد نیاز برای دریافت یک بسته توسط تمام گیرنده­ها به وضوح حداقل برابر است.

۳-۳-۱- تحلیل طرح

در ابتدا به تحلیل طرح می­پردازیم.

۳-۳-۱-۱- پهنای باند انتقال

پهنای باند انتقال را هنگامی که از طرح استفاده می­کنیم با و تعداد انتقال­های مجدد بسته­ها برای تولید بسته­های از دست­رفته را با نشان می­دهیم. توسط رابطه زیر بدست می ­آید [۲].

جایی­که تعداد کل بسته­های از دست­رفته برای یک دوره از بسته­ها است.

در معادله بالا، با فرض اینکه احتمالات از دست­رفتن بسته­ها از خطوط ارتباطی متفاوت مستقل از یکدیگر هستند، می ­تواند به آسانی توسط رابطه زیر بدست آید

جایی­که نسبت انتقال بسته از خطوط بی­سیم است و احتمال دریافت یک بسته به صورت موفقیت آمیز توسط تمام گیرنده­ها است.

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

(۴)

جایی­که نشانگر مجموعه بسته­های از دست­رفته است که با هم برای انتقال مجدد کد­گذاری شده اند و تعداد بسته­های انتقال مجدد برای است.

تا کنون کارهایی که برای برآورد صورت گرفته محاسبه است که توسط فرمول زیر بدست می ­آید

تعداد بسته­هایی که توسط در مجموعه از بسته­های از دست­رفته دریافت نشده­اند را با نشان می­دهیم.

برای یک مجموعه از بسته­های از دست­رفته، تعداد بسته­های انتقال مجدد عبارت است از:

جایی­که متغیر تصادفی است که نشانگر تعداد انتقال­های مجدد مورد نیاز برای به منظور دریافت بسته است. در این صورت داریم :

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

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

در مورد تخمین در معادله (۶) لم زیر را داریم.

لم ۴٫ برای بسته، فرض می­ شود که هر یک از آن­ها حداقل توسط یک گیرنده به درستی دریافت نشده­اند و احتمال اینکه () به درستی بسته را از میان بسته دریافت نکرده باشد، توسط رابطه زیر بدست می ­آید:

اثبات: توسط رابطه زیر تخمین زده می­ شود:

از میان بسته احتمال اینکه به ترتیب بسته را دریافت نکنند، عبارت است از:

برای بسته، احتمال اینکه هر بسته حداقل توسط یک گیرنده به درستی دریافت نشود، توسط رابطه زیر بدست می ­آید

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

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

آن­گاه داریم

در نهایت با جایگذاری معادلات (۱۰) و (۱۱) و (۱۴) در (۹) نتیجه حاصل می­ شود. □

حال با جایگذاری معادلات (۸) و (۷) در (۶) و جایگذاری (۶) در (۵) ، داریم :

جاییکه

در قضیه زیر تخمینی برای ارائه می­گردد.

قضیه ۵٫ پهنای باند انتقال از طرح استاتیک ارائه شده با گیرنده و اندازه بافر بسته از دست رفته ، عبارت است از:

جایی­که توسط معادله (۱۶) داده شده است و

اثبات : با ترکیب معادلات (۲) و (۳) و (۴) و (۱۵) نتیجه به راحتی حاصل می­ شود.□

۳-۳-۱-۲- تاخیر انتقال مجدد

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

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

قضیه ۶٫ تاخیر انتقال مجدد از طرح استاتیک مورد بحث دارای کران بالای زیر است :

جایی­که در معادلات (۱۶) و (۱۸) نشان داده شده اند. و علامت نشانگر باقیمانده صحیح^[۹۶] است.

اثبات: تاخیر کلی انتقال­های مجدد از یک دوره از بسته­ها تنها از بسته­های از دست­رفته ناشی می­ شود که شامل زمان انتظار در فاز انتقال^[۹۷] و زمان انتظار در فاز انتقال مجدد^[۹۸] می­ شود. بسته انتقال یافته را به ترتیب با نشان می­دهیم. اگر از دست­ رود، زمان انتظار برایدر فاز انتقال است، بنابراین توسط رابطه زیر داده می­ شود.

جایی­که مجموعه ­ای از بسته­های از دست­رفته، از یک دوره از بسته­هاست و تعداد بسته­های انتقال یافته در فاز انتقال مجدد است تا هنگامی که توسط تمام گیرنده­ها دریافت شود. آن­گاه داریم:

در معادله (۲۱) توسط رابطه زیر بدست می ­آید

در اولین تساوی فوق، میانگین زمان انتظار در فاز انتقال را با توجه به میانگین شرطی زمان انتظار در فاز انتقال تحت تعداد متفاوت از بسته­های از دست­رفته محاسبه کردیم. به آسانی می­توان دریافت که هنگامی که تعداد بسته­های از دست­رفته باشد، میانگین زمان انتظار در فاز انتقال است. در (۲۱) توسط رابطه زیر بدست می ­آید

در طول انتقال مجدد مجموعه از بسته­های از دست­رفته در بدترین حالت، هر گیرنده ، بسته مجددا انتقال یافته را دقیقا بعد از امین انتقال مجدد دریافت کرده است و هر یک از بسته از دست­رفته را دقیقا هنگامی که بسته مجددا انتقال یافته را دریافت کرد، احیا می­ کند. بنابراین تاخیر کلی مورد انتظار از بسته­های از دست­رفته از امین مجموعه کمتر از است. بنابراین

در نهایت باترکیب معادلات (۲۱) تا (۲۴) نتیجه حاصل می­ شود. □

۳-۳-۲- تحلیل طرح

در این جا پهنای باند انتقال و تاخیر انتقال مجدد را در طرح تخمین می­زنیم.

۳-۳-۲-۱- پهنای باند انتقال

پهنای باند انتقال را هنگامی که از طرح استفاده می­کنیم با نشان می­دهیم. تاثیر انتقال از طرح پویای مورد بحث قرار گرفته، توسط قضیه زیر داده می­ شود.

قضیه ۷٫ پهنای باند انتقال از طرح پویا با گیرنده و اندازه بافر بسته از دست رفته به این صورت است:

جایی­که .

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

میانگین تعداد انتقال­­های مورد نیاز برای این که یک بسته را بتوان به صورت موفقیت آمیزی به تمام گیرنده­ها فرستاد توسط رابطه زیر داده می­ شود :

در معادله بالا توسط رابطه زیر داده می­ شود.

در نهایت با جایگذاری رابطه (۲۷) در (۲۶)، نتیجه حاصل می­ شود.□

۳-۳-۲- ۲- تاخیر انتقال مجدد

هنگامی که از طرح استفاده می­کنیم تاخیر انتقال مجدد را با نشان می­دهیم. قضیه زیر تاخیر طرح پویای مورد بحث را نشان می­دهد.

قضیه ۸٫ تاخیر انتقال مجدد از طرح پویای بحث شده دارای کران بالایی به این صورت است :

جایی­که به ترتیب توسط روابط (۱۶) و (۱۸) داده شده ­اند.

اثبات : مشابه طرح استاتیک بحث شده تاخیر انتقال مجدد طرح پویا این­گونه بدست می ­آید.

در معادله بالا توسط معادله (۲۲) داده می­ شود و داریم

با ترکیب معادلات (۱۵) و (۲۹) و (۳۰) نتیجه حاصل می­ شود.□

۳-۴- نتایج عددی

در این بخش به اجرای طرح­های بحث شده بر حسب تاثیر انتقال و تاخیر می­پردازیم. نتایج عددی با بهره گرفتن از تحلیل و شبیه سازی بدست آمده­اند. نتایج را با طرح استاتیک کد محور با بهره گرفتن از عمل و طرح پویای کد محور با بهره گرفتن از عمل نیز مقایسه خواهیم کرد.

۳-۴-۱- محیط شبیه سازی

در شبیه سازی ما بسته­های ارسال شده از یک مبدا به یک مجموعه از گیرنده­ها، بسته­های از دست­رفته در هر گیرنده از توزیع برنولی پیروی می­ کنند. به علاوه بسته­های از دست­رفته از گیرنده­های متفاوت ناهمبسته هستند.

برای حالت­هایی با محیط متفاوت از پارامتر­ها ( مانند تعداد گیرنده­ها ، اندازه بافر بسته­های از دست­رفته و احتمالات مرتبط با ازدست رفتن بسته­ها)، به عنوان نمونه ما توزیع انتقال از بسته را (یعنی یک مجموعه از بسته­ها ) با بهره گرفتن از طرح غیر کد محور،
طرح­های کد محور در دسترس و طرح­های جدید شبیه سازی می­کنیم. از آن­جایی که احتمال از دست رفتن بسته از هر گیرنده داده شده است، نتایج شبیه سازی به مکان گیرنده­ها وابسته نیست. برای هر حالت، میانگین تعداد انتقال­های هر بسته برابر است با نسبت تعداد کل
انتقال­ها (استفاده شده برای انتقال بسته به تمام گیرنده­ها ) به .

۳-۴-۲- پهنای باند انتقال

پهنای باند انتقال کلیه شبکه­ ها با طرح­های کد محور به اندازه بافر بسته­های از دست­رفته وابسته است. بنابراین در ابتدا به بررسی پهنای باند انتقال طرح­های متفاوت تحت اندازه بافر بسته­های از دست­رفته متفاوت می­پردازیم. شکل ۳-۴ نتایج عددی حاصل از طرح­های متفاوت را روی پهنای باند­انتقال نشان می­دهد، جایی­که

.

برای هر طرح با مشخص، ۲۰ آزمایش توزیع بسته شبیه سازی شدند. تمام مقادیر رسم شده در شکل ۳-۴ به جز ۲% آن­ها دارای بازده اطمینان ۹۵% هستند. با توجه به این شکل، می­توان دید که نتایج تحلیلی پهنای باند انتقال به زیبایی با نتایج شبیه سازی شده مطابقت دارند.

شکل ۳-۴- پهنای باند انتقال در مقابل اندازه بافر

بنابرآنچه گفته شد مدل­های مطرح شده می­توانند به صورت موثرتری به منظور بررسی پهنای باند طرح­های مطرح شده، استفاده شوند. علاوه براین، مشاهده می­کنیم که در کل پهنای باند انتقال هر شبکه با طرح­های کد محور، هنگامی که اندازه بافر بسته­های از دست­رفته افزایش می­یابد، کاهش پیدا می­ کند و هنگامی که اندازه بافر بسته از دست­رفته خیلی کوچک نباشد، طرح توزیع کد محور می ­تواند اساسا مفیدتر ازطرح توزیع غیر کد محور باشد. برای مثال برای اندازه بافر ، در مقایسه با طرح توزیع قدیمی، میانگین تعداد انتقالات هر بسته
می ­تواند با بهره گرفتن از طرح استاتیک مورد بحث تا بیشتر از ۱۶% کاهش یابد.

با توجه به شکل ۳-۴ می­توانیم مشاهده کنیم که در مقایسه با طرح استاتیک در دسترس، طرح استاتیک مورد بحث می ­تواند به صورت موثری پهنای باند انتقال را کاهش دهد، به خصوص هنگامی که اندازه بافر بسته از دست­رفته کوچک باشد. به عنوان مثال، هنگامی که اندازه بافر ۳ باشد، طرح استاتیک در دسترس تنها می ­تواند ۹/۷% پهنای باند را کاهش دهد در حالی که طرح استاتیک مورد بحث پهنای باند را تا ۳/۱۳% کاهش می­دهد. به صورت مشابه طرح پویای مورد بحث همیشه مفید تر از طرح پویای در دسترس می­باشد. به عنوان مثال در مقایسه با طرح پویای در دسترس، طرح پویای مورد بحث قرار گرفته می ­تواند تاثیر انتقال را برای تا ۲/۲% بهبود بخشد. علاوه بر این نتایج شکل ۳-۴ نشان می­دهد که طرح­های پویا موثرتر از طرح­های استاتیک است. درافزایش پیچیدگی­های محاسباتی نتیجه مهم دیگری که می­توانیم بگیریم این است که هنگامی که اندازه بافر مقدار بزرگی باشد، عملکرد طرح پویای کد محور بسیار به کران پایین نزدیک است (که در معادله (۱) داده شده است.) به عنوان مثال در شکل ۳-۴ هنگامی که ، ۱۵ باشد، کران پایین تنها ۹/۲% کوچکتر از طرح پویای مورد بحث است. از این رو طرح پویای کد محور مورد بحث قادر است که تاثیر انتقال بالایی را کسب کند.

پهنای باند انتقال را تحت احتمالات مرتبط با ازدست رفتن بسته­ها و تعداد متفاوت از گیرنده­ها بررسی کردیم که در شکل ۳٫۵ به صورت خلاصه آمده­اند.

شکل ۳-۵ - پهنای باند حالات متفاوت

نتایج در شکل ۳-۵ () نشان می­دهد که با افزایش احتمالات از دست رفتن بسته­ها، مزیت طرح­های بحث شده نسبت به طرح­های در دسترس بسیار چشمگیرتراند. به عنوان مثال هنگامی که احتمال از دست رفتن بسته از هر خط ارتباطی ۵/۰ باشد، در مقایسه با طرح غیرکد محور طرح استاتیک در دسترس پهنای باند را تا ۳/۱۰% کاهش می­دهد اما پهنای باند بدست آمده از طرح به بزرگی ۱/۲۱% است. نتایج در شکل ۳-۵ () حاکی از آن است که در مقایسه با طرح­های در دسترس، کاهش پهنای باند انتقال با بهره گرفتن از طرح­های مورد بحث قرار گرفته هنگامی که تعداد گیرنده­ها زیاد شوند، افزایش می­یابد. به عنوان مثال برای حالتی با ۳ گیرنده طرح استاتیک در دسترس و بحث شده پهنای باند انتقال را در حدود ۴/۱۰% کاهش می­ دهند و در حالت با ۶ گیرنده طرح استاتیک مورد بحث می ­تواند پهنای باند انتقال را ۸/۲۴% بیشتر از طرح استاتیک در دسترس که پهنای باند را تا ۳/۱۶% کاهش می­دهد، کاهش دهد.

۳-۴-۳- تاخیر انتقال مجدد

از آن­جایی که مدل تحلیلی برای تحلیل دقیق تاخیر در دسترس نمی ­باشد، لذا مدل کران بالای مورد بحث قرار گرفته در این جا به منظور بررسی رفتار تاخیر طرح­های مطرح شده، مورد استفاده قرار می­گیرد.

شکل ۳-۶ تاخیر انتقال مجدد را به صورت تابعی از اندازه بافر بسته از دست­رفته نشان
می­دهد، جاییکه می­توانیم ببینیم که تاخیر انتقال مجدد از طرح­های کد محور هنگامی که اندازه بافر بسته­های از دست­رفته افزایش می­یابد، تقریبا به صورت خطی افزایش پیدا می­ کند. دلیل این رفتار این است که در طول فاز انتقال، مبدا بسته­های از دست­رفته را برای بسته­های کد­گذاری آینده ذخیره می­ کند تا اینکه فورا آن­ها را مجددا انتقال دهد. این افزایش تاخیر، هزینه­ای است که برای بدست آوردن فرصت­های کد­گذاری حاصل می­ شود. همان­گونه که قبلا بحث شد، بهبود تاثیر انتقال هنگامی که اندازه بافر بسته از دست­رفته افزایش می­یابد به صورت یکنواخت افزایش می­یابد. بنابراین یک رابطه بین تاخیر انتقال و تاخیر بسته­ها هنگامی که اندازه بافر بسته از دست رفته معلوم است، موجود می­باشد.

شکل ۳-۶ -تاخیر انتقال مجدد در مقابل اندازه بافر بسته از دست­رفته

با توجه به شکل ۳-۶ می­توانیم ببینیم که اگر چه کران بالای طرح­های مطرح شده به منظور مقایسه با طرح­های کد محور در دسترس اختیار شده ­اند، فاصله بین طرح­های جدید و نمونه­های قدیمی نظیرشان بزرگ نیست. به عنوان مثال، هنگامی که اندازه بافر ۱۵ است کران بالای تاخیر انتقال مجدد از طرح­های تنها ۴/۲۰% بزرگتر از تاخیر انتقال مجدد از طرح استاتیک قدیمی است.

تاخیر انتقال مجدد تحت احتمالات متفاوت ازدست رفتن بسته­ها در شکل ۳-۷ () و تاخیر انتقال مجدد تحت تعداد متفاوت از گیرنده­ها در شکل ۳-۷ () نشان داده شده ­اند. نتیجه­ای مشابه که از این دو شکل می­توان دریافت این است که تاخیر انتقال طرح­های کد محور مطرح شده با طرح­های کد محور قدیمی بسیار به یکدیگر نزدیک هستند.

شکل ۳-۷ - تاخیر انتقال مجدد از حالات متفاوت

۳-۵- نتیجه گیری

در این فصل به بررسی دو طرح کد محور جدید پرداختیم که به منظور توزیع قابل اعتماد از اعمال کد­گذاری کلی­تری نسبت به عمل کد­گذاری استفاده می­ شود. طرح استاتیک با پیچیدگی کمتر و طرح پویا با پیچیدگی نسبتا بالاتر ولی اجرای بهتر، برخلاف طرح­های کد محور در دسترس برای شبکه که دارای پیچیدگی محاسباتی نمایی هستند، طرح­های بحث شده دارای پیچیدگی­ چند جمله­ای هستند. به علاوه، نتایج تحلیلی و شبیه سازی شده نشان دادند که در مقایسه با طرح­های کد محور در دسترس، طرح­های مطرح شده می­توانند به صورت موثرتری پهنای باند را کاهش دهند، به خصوص در حالتی که احتمال از دست رفتن بسته­ها و تعداد گیرنده­ها زیاد باشد. علاوه بر این نشان داده شد که بهبود تاثیر انتقال با بهره گرفتن از کد­گذاری شبکه با اندازه بافر بسته از دست­رفته و تعداد گیرنده­های توزیع افزایش می­یابد. این تاثیر هنگامی که اندازه بافر بسته از دست­رفته و تعداد گیرنده­ها به اندازه کافی بزرگ باشند، بسیار چشمگیر است. به عنوان مثال در حالتی که تعداد گیرنده­ها ۶ و اندازه بافر ۱۲ باشد تاثیر انتقال می ­تواند در صورتی که از طرح پویای مطرح شده استفاده شود به اندازه ۸/۲۴% بهبود یابد. بنابراین کد­گذاری شبکه بعدی جدید را برای انتقال موثر از توزیع قابل اعتماد، فراهم می ­آورد.

فهرست منابع و مأخذ

[۱] Ahlswede,R. , Cai,N. , Li,Y.R. , Yeung,R.W. .(2000). “Network information flow”, IEEE Transacations on Information Theory, Vol.46, N.1:1204-1216.

[۲] Chi,K. , Jiang,X. , Horiguchi,S. .(2010). “Network coding-based reliable multicast in wireless networks”, Computer Networks, Vol.54: 1823-1836.

[۳] Ckantsidis,C. , Rodriguez,P.R. .(2006). “Cooperative security for network coding file distribution”, INFOCOM.

[۴] Fragouli,C. , Bodec, J-Y.L. , Widmer,J. .(2006). “Network Coding: An Instant Primer”, Vol.36, No.1:63-68.

[۵] Fragouli,C. , Bodec, J-Y.L. , Widmer,J. .(2006). “A network coding approach to energy efficient broadcasting: from theory to practice”, IEEE INFOCOM, Barcelona, Spain.

[۶] Fragouli,C. , Bodec, J-Y.L. , Widmer,J. .(2008). “Efficient broadcasting using network coding” , IEEE IACM Transacation on Networking, Vol.16, No.2:450-463.

[۷] Hekmat, Sharam .(2005). “Communication Networks”, Pragsoft Corporation.

[۸] Katti,S. , Gollakota,S. , Katabi,D. .(2007). “Embaracing wireless interference: analog network coding”, ACM SIGCOMM, Koyoto, Japan.

[۹] Katti,S. , Rohul,H. , Hu,W. , Katabi,D. , Medard,M. , Crowcraft,I. .(2006). “Xor in the air: Practical wireless networks coding”, ACM SIGCOMM, Pisa.

[۱۰] Kunz,T. .(2003). “Rrliable Multicasting in MANETs”, Communication Research Centre, Canada, Ottawa.

[۱۱] Langberg,M. , Sprintson,A. , Bruch,J. .(2006). “The Encoding Complexity of Networking” IEEE Transactions on Information Theory, Vol.52, No.6: 2386-2397.

[۱۲] Le,J. , Lui,J.C.S. , Chui,D.M. .(2008).”How many packets can we encode? An analysis of practical wireless network coding”, IEEE INFOCOM, Hongkong: 1040-1048.

[۱۳] Li,L. , Romjee,R. , Bwdhiket,M. , Miller,S. .(2007). “Network coding-based broadcast in mobile ad hoc networks”, IEEE INFOCOM: 1739-1747.

[۱۴] Li,Z. , Li,B. .(2005). “On increasing end-to-end throuput in wireless ad hoc networks”, Proceedings of the Second International Conference on Quality of Service in Hetegenous Wired/Wireless Network, Orlando.

[۱۵] Li,Z. , Li,B. .(2004). “Network coding: the case for multiple unicast sessions”, Annual Allerton Conference on Communication, Control and Computing, Monticello.

[۱۶] Liu,J. , Goeckei,D. , Towsley,D. .(2007). “Bounds on the gain of network coding and broadcasting in wireless networks”, IEEE INFOCOM: 724-732.

[۱۷] Lun,D.S. , Ratnakar,N. ,Medard,M. , Koetter,R. , Karger, D.R. , Ho,T. , Ahmed,E. , Zhao,F. .(2006). “Minimum-cost multicast over coded packet networks”, IEEE Transactions on Information Theory, Vol.52, No.6: 2608-2623.

[۱۸] Microsoft Corporation .(1999). “Networking Essentials”, second edition, Microsoft Press.

[۱۹] Nguyen,D. , Nguyen,T. , Bose,B. .(2007). “Wireless broadcasting using network coding”, Third workshop on network coding, Theory and Applications.

[۲۰] Ni,B. , Santhapuri,N. , Zhang,Z. , Nelakuditi,S. .(2006). “Routing with opportunistically coded exchanges in wireless mesh networks”, Reston,VA: 157-159.

[۲۱] Nu,Y. , Chou,P.A. , Kung,S-Y. .( 2005). ”Minimum energy multicast in mobile ad hoc networks using networking”, IEEE Transacations on Communications, Vol.53, No.11:1906-1918.

[۲۲] Park,JS. , Lun,D. , Soldo,F. , Gerla,M. .(2006). “Performance of network coding in ad hoc networks,IEEE MILCOM.

[۲۳] Paul,S. , Sabnani,K. , Lin,JC-H. , Bhattacharya,S. .(1997). “Reliable multicast transport protocol”. IEEE Journal On Selected Areas In Communication ,Vol.15, No.3.

[۲۴] Rouayheb,S.Y.EL. , Sprintson,A. , Georghiades,C.N. .(2008). “On the Index Coding Problem and its Relation to Network Coding and Matroid Theory”.

[۲۵] Sanders,P. , Egner,S. , Tolhoizen,L. .(2003). “ Polynomial time algorithms for network information flow”, Proceedings of the 15^th ACM Symposiom on Parallel Algorithms and Architectures, San Diego.

[۲۶] Schollmeier,R. .(2002). “A Definition of peer-to-peer Networking for the Classification of peer-to-peer Architectures and applications”, Proceedings of the first International Conference on peer-to-peer Computing.IEEE.

[۲۷] Sengupta,S. , Rayanchu,S. , Banerjee,S. .(2007). “An annaysis of wireless network coding for unicast sessons: the case for coding-aware routing”, IEEE INFOCOM: 1028-1036.

[۲۸] Wu,Y. , Chou,P.A. , Kung, S.Y. .(2005). “Information exchange in wireless networks with network coding and physical-layer broadcast” , Proceedings of the 39^th Annual Conference on Information Sciences and Systems(CISS) , Baltimore.

[۲۹] Yeung,R.W. .(2007). “Network coding Analysis”, Vol.7, No.4: 353-358.

[۳۰] Zhang,S. , Liew,S.G. , Lam,P.P. .(2006). “Hot topic: Physical-layer network coding”, ACM MOBICOM.

[۳۱] حکیمی­کیا، مرتضی (۱۳۸۹)، شبکه ­های بی­سیم. کتاب الکترونیکی.

پیوست

واژه نامه فارسی به انگلیسی

الف

آدرس مبدا source address

آدرس مقصد destination address

از کد خارج کردن decoding

القا کننده inductor

امواج رادیویی پهن باند narrow-band radio

آنلاین online

ب

باقیمانده صحیح integer modulo

بسته packet

بسته از دست رفته lost packet