۳-۲-۲-۱- اندازه میدان ۴۶
۳-۲-۲-۲- پیچیدگیهای محاسباتی ۴۶
۳-۲-۳- طرح جامع کدمحور پویا ۴۷
۳-۲-۳-۱- اندازه میدان ۴۹
۳-۲-۳-۲- پیچیدگی محاسباتی ۵۰
عنوان صفحه
۳-۳- تحلیل اجرا ۵۱
۳-۳-۱- تحلیل طرح ۵۱
۳-۳-۱-۱- پهنای باند انتقال ۵۱
۳-۳-۱-۲- تاخیر انتقال مجدد ۵۶
۳-۳-۲- تحلیل طرح ۵۸
۳-۳-۲-۱- پهنای باند انتقال ۵۸
۳-۳-۲-۲- تاخیر انتقال مجدد ۵۹
۳-۴- نتایج عددی ۶۰
۳-۴-۱- محیط شبیه سازی ۶۰
۳-۴-۲- پهنای باند انتقال ۶۰
۳-۴-۳- تاخیر انتقال مجدد ۶۳
۳-۵- نتیجه گیری ۶۴
فهرست منابع و مأخذ ۶۵
پیوست
- واژه نامه فارسی به انگلیسی ۶۸
– واژه نامه انگلیسی به فارسی ۷۲
فصل اول
مقدمه
امروزه با پیشرفت تکنولوژی اطلاعات نیاز به استفاده از امکانات روز جهت تبادل داده ها با سرعت و دقت بالا و رهایی از محدودیتهای محیطی بیشتر احساس می شود بنابراین لازم است از امکانات و تجهیزاتی که بتواند به سادگی و آسانی راه اندازی شود استفاده نمود.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
یکی از راحتترین، سادهترین و کم هزینهترین روشها استفاده از شبکه های کامپیوتری بخصوص شبکه های کامپیوتری بیسیم است.
با توجه به نیاز به اشتراک گذاشتن به موقع داده ها ایده ایجاد شبکه شکل گرفت. کامپیوترهای شخصی ابزارهایی جالب برای تولید انواعی از اطلاعات هستند، اما به شما این اجازه را نمیدهند که به سرعت داده های تولیدی خود را به اشتراک بگذارید. بدون شبکه، اسناد باید چاپ شوند تا دیگران بتوانند آنها را ویرایش کنند یا مورد استفاده قرار دهند. در بهترین حالت میتوانید فایل مربوطه را در اختیار آنها قرار دهید تا در کامپیوتر خود ذخیره کنند. اگر دیگران در آنها تغییراتی ایجاد کنند هیچ راهی برای ترکیب تغییرات وجود ندارد. اگر چند کامپیوتر و یا حتی وسایل دیگری مانند چاپگر و … به یکدیگر متصل شوند، یک شبکه ایجاد می شود که میتوانند اطلاعات را بین یکدیگر به اشتراک گذارند.
در بخش ۱ این فصل به بررسی مفهوم شبکه پرداخته و اجزای شبکه را مورد بررسی قرار خواهیم داد. در بخش دوم به بررسی شبکه های کامپیوتری میپردازیم. در بخش سوم
شبکه های بیسیم مورد مطالعه قرار خواهند گرفت و بخش ۴ به معرفی شبکه های سیار می پردازد.
یک شبکه از اتصال تعداد بسیاری گره[۲] که جریانی مطلوب در آن وجود دارد به وجود می آید. گرهها نقاطی هستند که در آنها بیش از دو شاخه یا خط ارتباطی[۳] که جریان از طریق آنها عبور می کند، یکدیگر را ملاقات می کنند. شکلی که در ادامه می آید یک شبکه با پنج گره A ، B ،C، D وE را نشان میدهد. این گرهها با خطوط ارتباطی یا شاخه های گوناگونی مانند ، ، ، و… با هم مرتبط شده اند.
شکل ۱-۱- ساختار شبکه
در مهندسی برق یک مثال ساده از شبکه، یک شبکه الکتریکی است که خطوط ارتباطی آن اجزای الکتریکی مانند مقاومت[۴]، خازنها[۵]، القاکنندهها[۶] و اجزای فعال هستند که جریان از طریق این شاخهها عبور و گرههای بسیاری را ملاقات می کند. جریان عبوری از طریق تعدادی از شاخهها به یک گره میرسد و از طریق تعدادی شاخه دیگر از گره خارج میشوند.
در شبکه های حمل و نقل جادهای جادههای مختلف در تقاطعها و یا چهارراه ها، که میتوان از آنها به عنوان یک گره یاد کرد، با یکدیگر برخورد می کنند. جادهها مانند خطوط ارتباطی عمل می کنند و وسایل نقلیه در آنها جریان دارند. دریک تقاطع یک وسیله نقلیه از یک جاده
می آید و به جاده دیگری که در نظر دارد میرود. به صورت مشابه شبکه های ریلی و خطوط هوایی را داریم. شبکه های پستی شبکه هایی هستند که در آنها پیام از مبدأ به مقصد فرستاده می شود. امروزه با ابداع ارتباطات الکترونیکی به شبکه های تلفنی، اطلاعاتی و رادیویی تلویزیونی دسترسی داریم.
سازماندهی شبکه های ارتباطی به صورت گام به گام مورد بحث قرار میگیرند. یک شبکه از گرهها و شاخهها به منظور تسهیل جا به جاییهای فیزیکی تشکیل شده است. جریان از طریق یک گره وارد شبکه می شود و از یک گره به نام گره مقصد از شبکه خارج می شود که این گره به گره مصرف کننده معروف است. هر گرهای می تواند به عنوان یک گره مبدأ و یا مصرف کننده باشد.
-
-
- مولفههای شبکه های ارتباطی
گره
در یک شبکه ارتباطی یک گره نقطهای است که در آن بیش از دو شاخه یکدیگر را ملاقات می کنند ممکن است یک شبکه ارتباطی دارای تعداد بسیار زیادی گره باشد که یک گره لزوما به تمام گرهها مرتبط نیست. کار یک گره از شبکه، اتصال مسیر وارد شونده به مسیر خارج شونده است، از این رو سیگنالها میتوانند مسیر خود را به مسیر مطلوبشان برای انتقال پیش رو تغییر دهند. به صورت متعارف در یک شبکه تلفنی، مراکز تلفنی و یا تلفن خانهها نقش گره را بازی می کنند. در یک شبکه اطلاعاتی یک گره یک بسته سوییچ[۷] است که به آن مسیریاب[۸] گفته می شود. برخی از گرهها به خصوص گرههای تغییر پیام یا بسته، دارای بافر و حافظه برای پیامها هستند. چنین گرههایی همانند سوییچهای ذخیره و ارسال کار می کنند. گرهها اعمال دیگری چون یکسان سازی پیامهای دریافتی، آزمایش کردن خروجیها و … را نیز انجام می دهند.
شاخه
شاخه شبکه های ارتباطی اساسا یک رسانگر انتقال[۹] است که یک سیم یا یک کانال رادیویی است. رسانگر انتقالات سیمی می تواند به هر یک از شکلهای جفت سیمهای مسی، کابلهای چند جفتی، کابلهای هممحور[۱۰] و یا فیبر نوری[۱۱] باشند. این سیمها سیگنالها را از یک گره به گره دیگر میبرند. یک کانال بیسیم یک طیف الکترومغناطیسی از فرکانسهای بسیار پایین تا فرکانسهای بسیار بالا شامل موجهای میلیمتری و نوری گسترده شده اند. پهنای باند[۱۲]
کانالهای سیمی یا بیسیم دارای برد عرضی بالایی است می تواند نسبت داده های عبوری را از چند بیت در ثانیه تا چند گیگا – پنتا بیت در ثانیه پوشش دهد. طول این خطوط انتقال با توجه به دلایل متنوعی مانند پراکنش محدود است. در یک شبکه ارتباطی چند منظوره لزومی ندارد که تمام خطوط ارتباطی از یک نوع باشد، بعضی میتوانند خطوط سیمی و بعضی خطوط بیسیم باشند.
هم اکنون یک شبکه ارتباطی را میتوان به صورت گردایهای از گرهها که توسط خطوط ارتباطی با یکدیگر مرتبط هستند تعریف کرد که اطلاعات را از طریق سیگنالها به شکل الکتریکی یا نوری منتقل می کنند. بنابراین گرهها، خطوط ارتباطی و انتقال اطلاعات ویژگی اساسی هر شبکه ای هستند. برخی از معمولترین و شناخته شدهترین و عریضترین شبکه های پیامی[۱۳]، شبکه های پستی[۱۴]، شبکه های تلگرافی[۱۵]، شبکه های تلفنی[۱۶] (ثابت، معمولی و سیار)، شبکه های کامپیوتری[۱۷] و
شبکه های سرگرمی[۱۸] (پخش کننده های تلویزیون یا صوتی) میباشند.
یک شبکه با توجه به کاربردی که دارد طراحی و به کار گرفته می شود. گونه های بسیاری از شبکه موجود است. شبکه تلگرافی برای ارسال تلگرافها از یک مکان به مکان دیگر مورد استفاده قرار میگیرند. در آنها از سوییچهای پیام به عنوان گره استفاده می شود و اساسا سرویسی با سرعت بسیار پایین ارائه میدهد. از سویی دیگر شبکه های تلکس مانند شبکه های تلفنی کار می کنند و کاربران میتوانند مستقیما پیامهای متنی خود را بدون کمک اپراتور به مقصد مورد نظر ارسال نمایند. شبکه تلفنی برای ارتباطات صوتی بین دو کاربر مورد استفاده قرار میگیرد. یک شبکه کامپیوتری به کاربران این اجازه را میدهد که با بهره گرفتن از شبکه کامپیوتری با هم ارتباط برقرار کنند. داده های صوتی و تصویری میتوانند از طریق شبکه پخش[۱۹] به طور همزمان از یک مبدأ به تعداد زیادی از استفادهکنندهها ارسال شود.
به منظور بیشتر مشخص شدن مفهوم شبکه، شبکه کامپیوتری را مورد بحث قرار میدهیم.
۱-۲- شبکه کامپیوتری
با توجه به استفاده گسترده از کامپیوترها، دیگر استفاده از آنها به یک مکان خاص محدود نمی شود و نیاز به اینکه کامپیوترها در مکانهای مختلف با یکدیگر مرتبط شوند احساس می شود. یک شبکه کامپیوتر که اغلب از آن به عنوان شبکه یاد می شود، از گروهی از کامپیوترها و وسیله ها تشکیل شده است که توسط کانالهای ارتباطی با یکدیگر مرتبط هستند و ارتباط بین کاربران را آسان میسازد. یک شبکه به کاربران این اجازه را میدهد که از منابع و اطلاعات به صورت مشترک استفاده کنند. بر اساس پراکندگی جغرافیایی کامپیوترها اساسا سه نوع شبکه موجود است که در ادامه به آنها اشاره میکنیم [۷].
شبکه های محلی (LAN)[20]
در این نوع شبکه، کامپیوترها و دیگر وسایل ارتباطی در یک محیط کوچک به یکدیگر مرتبط هستند. محیط می تواند یک ساختمان یا مجموعه ای از ساختمانها در یک محوطه باشد. نمونه ای از شبکه محلی، شبکه کتابخانهای است که مورد استفاده قرار میگیرد[۷].
شبکه های شهری (MAN)[21]
اساسا یک شبکه شهری بزرگتر از شبکه های محلی است و عموما از ساختاری مشابه استفاده می کنند که می تواند گروهی از دفاتر مجاور و یا در یک شهر را پوشش دهد و می تواند خصوصی و یا عمومی باشد [۷].
شبکه های گسترده (WAN)[22]
در این شبکه کامپیوترها میتوانند از یکدیگر دورتر باشند و شهرها، کشورها و یا حتی قارهها را پوشش دهند. کامپیوترها میتوانند از طریق خطوط تلفن[۲۳]، امواج رادیویی[۲۴] و فیبر نوری به یکدیگر متصل شوند [۷].
شبکه ها به دوگروه کلی تقسیم میشوند که عبارتند از شبکه های نظیر به نظیر[۲۵] و شبکه های سرویس دهنده محور[۲۶].
تفاوت بین شبکه های نظیر به نظیر و سرویسدهنده محور بسیار مهم است، زیرا هر یک دارای قابلیت های متفاوت هستند. نوع شبکه ای که شما آن را اجرا میکنید به عوامل بسیاری از جمله اندازه سازمان، سطح امنیت، نوع کار، سطح مدیریت شبکه، حجم ترافیک شبکه و بودجه شبکه وابسته است.
شبکه های نظیر به نظیر
تعریفهای مختلفی از سیستم نظیر به نظیر ارائه شده است که به طور کلی آن را سیستمی میدانند برای اشتراک منابع و سرویسهای کامپیوتر با انجام تبادل مستقیم بین آنها و در محیطی که اتصالات پایدار و آدرس های قابل پیش بینی وجود ندارد و سیستم نمیتواند متکی به یک سرویس دهنده متمرکز باشد استفاده می شود.
در یک شبکه نظیر به نظیر هیچ سرویس دهندهای وجود ندارد و یا بین کامپیوترها درجهبندی صورت نمیگیرد. تمام کامپیوترها یکسان هستند و از این رو نظیر یکدیگر میباشند. عموما هر کامپیوتر به عنوان یک سرویس گیرنده[۲۷] و یک سرویس دهنده[۲۸] عمل می کند و هیچ یک مسئول اداره کردن کل شبکه نمیباشند. در این نوع شبکه ها کاربر هر کامپیوتر مشخص می کند که چه دادههایی در کامپیوترش در شبکه به اشتراک گذاشته شود و کاربران مسئول کامپیوتر خود و امنیت آن میباشند.
شبکه نظیر به نظیر یک نوع شبکه ساده است و از آنجایی که هر کامپیوتر خودش به عنوان یک سرویس گیرنده و یک سرویس دهنده کار می کند، دیگر نیازی به یک سرویس دهنده مرکزی و قدرتمند نیست و در نتیجه شبکه های نظیر به نظیر نسبت به شبکه های سرویس دهنده محور ارزانتر هستند.
شبکه نظیر به نظیر می تواند خالص یا ترکیبی[۲۹] باشد. در مدل خالص هیچ سرویس دهنده متمرکزی وجود ندارد. در مدل ترکیبی، هر گره از طریق یک سرویس دهنده به سیستم وارد می شود که این سرویس دهنده می تواند برای شناسایی گره و اطلاعات دارای مجوز ورود بکار رود. بعد از ورود به سیستم جفتها بطور مستقیم و بدون دخالت سرویس دهنده با هم ارتباط برقرار
می کنند.
شبکه های نظیر به نظیر هنگامی مورد استفاده قرار میگیرند که :
- تعداد کامپیوترها از ۱۰ کمتر باشد.
- تمام کاربران در یک مکان قرار گرفته باشند.
- امنیت شبکه مهم نباشد.
- در آینده نیازی به توسعه شبکه نباشد.
در ادامه نمونه ای از شبکه های نظیر به نظیر نشان داده شده است [۱۸، ۲۶].
شکل ۱-۲- نمونه ای از شبکه های نظیر به نظیر
انتخاب یک روش نظیر به نظیر معمولا به دلیل یک یا چند مورد از اهداف زیر صورت میگیرد.
تقسیم و کاهش هزینه
راه اندازی یک سیستم متمرکز که بتواند از سرویس گیرندههای زیادی پشتیبانی کند، هزینه زیادی را به سرویس دهنده تحمیل خواهد کرد. معماری نظیر به نظیر می تواند کمک کند تا این هزینه بین تمام گرهها تقسیم شود.
افزایش قابلیت اعتماد
بدلیل عدم وجود یک منبع قدرتمند مرکزی، قابلیت اعتماد در سیستم یکی از اهداف مهم به شمار می آید و بنابراین باعث نوآوریهای الگوریتمی در این زمینه می شود.
افزایش خودمختاری
در بسیاری از موارد کاربران در یک شبکه توزیع مایل نیستند که متکی به یک سرویس دهنده متمرکز باشند چون متکی بودن به یک سرویس دهنده متمرکز باعث محدود بودن آنها
می شود. مثلا در مورد کاربرد اشتراک فایل، کاربران میتوانند بطور مستقیم فایلهای یکدیگر را دریافت کنند بدون آنکه متکی به یک سرویس دهنده متمرکز باشند که ممکن است مجوز دریافت فایل را به آنها ندهد.
گمنامی
این واژه وابسته به همان خودمختاری می شود. کاربران ممکن است مایل نباشند که هیچ کاربر دیگری یا سرویس دهندهای اطلاعاتی در مورد سیستم آنها داشته باشد. با بهره گرفتن از یک سرویس دهنده مرکزی نمی توان از گمنامی مطمئن بود، چون حداقل سرویس دهنده باید بگونهای بتواند سرویسگیرنده را شناسایی کند، مثلا با بهره گرفتن از آدرس اینترنتی آن. با بهره گرفتن از معماری نظیر به نظیر چون پردازشها به صورت محلی انجام می شود، کاربران
میتوانند از دادن اطلاعاتی در مورد خودشان به دیگران اجتناب کنند.
پویایی
فرض اولیه سیستمهای نظیر به نظیر این است که در یک محیط کاملا پویا قرار داریم. منابع و گرهها میتوانند آزادانه به سیستم وارد و از آن خارج شود.
شبکه های سرویس دهنده محور
در محیطی که تعداد کامپیوترها زیاد باشد شبکه های نظیر به نظیر مناسب نمی باشد و از این رو شبکه ها باید دارای سرویس دهنده مشخصی باشند. سرویس دهنده تنها به عنوان سرویس دهنده عمل می کند و نیاز اجزای شبکه را سریعا برآورده می کند و امنیت فایلهای شبکه را بر عهده دارد.
هنگامی که اندازه و ترافیک شبکه افزایش مییابد بیش از یک سرویس دهنده در شبکه مورد نیاز است. تقسیم کارها بین سرویس دهندهها تضمین کننده اجرای هر کار به بهترین روش ممکن در شبکه است. نمونه ای از شبکه های سرویس دهنده محور در شکل ۱-۳ نشان داده شده است [۱۸].
شکل ۱-۳- نمونه ای از شبکه های سرورمحور
۱-۲-۱- ساختار شبکه
ساختار شبکه به شکل شبکه اشاره دارد. چگونگی اتصال گرههای مختلف در یک شبکه به یکدیگر و انتقالات بین آنها با ساختار شبکه معین میگردد. چهار نوع معمول از ساختار شبکه موجود است که در ادامه به آن اشاره میکنیم.
۱-۲-۱-۱- ساختار گذر[۳۰]
در این ساختار تمام وسیله ها به یک کابل مرکزی به نام گذر یا ستون فقرات[۳۱] متصل هستند. سادگی، کم هزینه بودن و توسعه آسان این شبکه از نقاط قوت آن است و نقطه ضعف عمده این شبکه آن است که اگر کابل اصلی که به عنوان پل ارتباطی بین کامپیوترهای شبکه است، قطع شود، کل شبکه از کار خواهد افتاد [۱۸].
شکل ۱-۴- ساختار گذر
۱-۲-۱-۲- ساختار ستارهای[۳۲]
در این ساختار تمام وسیله ها به یک هاب[۳۳] مرکزی متصل هستند. گرهها با عبور داده ها از هاب با یکدیگر ارتباط دارند. نقطه ضعف این شبکه این است که عملیات کل شبکه به هاب وابسته است و اگر هاب از کار بیافتد کل شبکه از کار خواهد افتاد.
نقاط قوت شبکه ستارهای عبارتند از:
- نصب شبکه با این ساختار ساده است.
- توسعه شبکه با این ساختار به راحتی انجام می شود.
- اگر یکی از خطوط متصل به هاب قطع شود فقط یک کامپیوتر از شبکه خارج
می شود [۱۸].
شکل ۱-۵- ساختار ستارهای
۱-۲-۱-۳- ساختار حلقوی[۳۴]
در این ساختار تمام وسیله ها به شکل یک حلقه بسته به یکدیگر متصل هستند بنابراین هر وسیله مستقیما به دو وسیله دیگر در ارتباط است که در دو طرف آن قرار دارند.
نقطه ضعف شبکه های حلقوی این است که به سخت افزار پیچیده نیاز دارد. (کارت شبکه آن گران قیمت است)
و نقاط قوت شبکه های حلقوی عبارتند از:
- نصب شبکه با این ساختار ساده است.
- توسعه شبکه با این ساختار به راحتی انجام می شود [۱۸].
شکل ۱-۶- ساختار حلقوی
۱-۲-۱-۴- ساختار مش[۳۵]
در این ساختار وسیله ها از طریق ارتباطات فراوان بین گرهها به یکدیگر متصل هستند. در یک شبکه مش هر گره با تمام گرهها ارتباط دارد. مزیت این نوع شبکه این است که هر کامپیوتر با سایر کامپیوترها ارتباطی مجزا دارد که دارای بالاترین درجه پایداری و اطمینان است. اگر یک کابل از شبکه ارتباطی در ساختار مش قطع شود شبکه همچنان فعال باقی خواهد ماند. ضعف اساسی شبکه های مش آن است که از تعداد زیادی خطوط ارتباطی استفاده می کند، به خصوص هنگامی که تعداد ایستگاهها افزایش مییابد، به همین دلیل این ساختار از نظر اقتصادی مقرون به صرفه نیست.
شکل ۱-۷- ساختار مش
۱-۲-۲- اجزای شبکه
اجزای اساسی شبکه عبارتند از سخت افزار شبکه [۳۶]، رسانههای انتقال و نرم افزار شبکه[۳۷].
۱-۲-۲-۱- سخت افزار شبکه
جزء اصلی یک شبکه کامپیوتری سخت افزار شبکه است. کامپیوترها در یک شبکه به دو گروه سرویس دهنده و سرویس گیرنده تقسیم می شود. کامپیوتر سرویس دهنده کامپیوتری است که دارای قدرت و سرعت بالاتری است، سرویس گیرندهها به سرویس دهنده متصل هستند و در شبکه های نظیر به نظیر هیچ سرویس دهندهای وجود ندارد.
۱-۲-۲-۲- رسانههای انتقال
انتقال داده ها و عبور سیگنالها از انتقال دهنده به گیرندهها از طریق یک مسیر صورت میگیرد که این مسیر رسانه نام دارد.
رسانههای هدایت شده[۳۸]
در این گونه رسانه ها داده ها از طریق مسیرهای فیزیکی انتقال مییابند، گونه های متفاوتی از کابلها در این رسانه ها مورد استفاده قرار میگیرند که با توجه به ساختار شبکه انتخاب میشوند، که گونه هایی از آنها عبارتند از کابلهای هممحور، زوج سیمهای به هم تابیده شده مسی[۳۹] و کابل فیبرنوری.
رسانههای هدایت نشده[۴۰]
در این رسانه ها هیچ سیمی وجود ندارد و اطلاعات از طریق امواج رادیویی یا مایکروویو انتقال مییابند.
۱-۲-۲-۳- نرم افزار شبکه
نرم افزار شبکه مجموعه ای از نرم افزارهاست که به کامپیوترهایی که با هم در ارتباط هستند اجازه میدهد که به صورتی راحت و کم هزینه از نرم افزارها استفاده کنند. نرم افزار شبکه عملکرد هر سیستم شبکه را کنترل مینماید، به عنوان مثال کنترل می کند که چه کسانی اجازه استفاده از شبکه را دارند، چه زمانی میتوان از شبکه استفاده کرد، کاربران اجازه انجام چه کارهایی را دارند و چه منابعی برای شبکه در دسترس میباشد.
کارت شبکه (NIC)[41]
هر کامپیوتر به یک کارت شبکه نیاز دارد، که به هر ایستگاه اجازه میدهد تا با سایر ایستگاهها تبادل اطلاعات کنند.
سوییچ[۴۲]
سوییچها اساسا پلهای ارتباطی[۴۳] هستند که چندین قسمت دارند و قسمت های مختلف شبکه را به یکدیگر متصل می کنند.
هاب
یک هاب برای متصل کردن چندین کامپیوتر و وسیله از طریق کابلهای خاص استفاده
می شود. هابها ارزان هستند و اتصالها آسان صورت میگیرد[۱۸].
مسیریاب
در محیطی که قسمت های مختلفی از شبکه وجود دارد، ممکن است یک پل ارتباطی به منظور اطمینان از ارتباطات سریع میان قسمت های مختلف، کافی نباشد. در چنین محیطی وسیلهای لازم است که نه تنها آدرس هر قسمت از شبکه را بداند بلکه بتواند بهترین مسیر را برای ارسال داده ها به قسمت های مختلف تعیین کند، به چنین وسیلهای مسیریاب گویند. مسیریابها نسبت به پلهای ارتباطی اجازه دسترسی به اطلاعات بیشتری را دارند و از این اطلاعات به منظور مدیریت بهتر ترافیک در شبکه استفاده می کنند. مسیریابها گاهی مدخل[۴۴] نیز نامیده میشوند [۱۸].
۱-۲-۳- چگونه شبکه ها داده ها را ارسال می کنند؟
معمولا داده ها به صورت فایلهایی با اندازه های بزرگ میباشند. اگر کامپیوترها همزمان تعداد زیادی داده را در شبکه قرار دهند، شبکه نمیتواند به درستی کار کند و سرعت شبکه کاهش مییابد. مقادیر زیاد داده به عنوان یک واحد بزرگ عملکرد شبکه را مختل مینماید و ارتباطات را امکانناپذیر میسازد، زیرا کامپیوترها کابلها را توسط داده ها پر کرده اند. از آنجایی که کاربران مایل هستند داده ها را به سرعت و به آسانی در شبکه عبور دهند، داده ها باید به قسمت های کوچک و قابل اداره شکسته شوند، که به این قسمت ها بسته[۴۵] گفته می شود.
بستهها واحدهای اساسی شبکه های ارتباطی هستند. با تقسیم داده ها به بستهها، انتقالات مجزا به سرعت صورت میپذیرد و از این رو هر کامپیوتر در شبکه شانس بیشتری برای انتقال و دریافت اطلاعات دارد. در کامپیوتر گیرنده، بستهها جمعآوری میشوند و به منظور بدست آوردن داده اصلی با ترتیبی مناسب سرهمبندی میشوند.
هنگامی که کامپیوتر فرستنده، داده ها را به بستهها میشکند، اطلاعات کنترلی خاصی را در هر یک از بستهها قرار میدهد که از طریق آن :
- داده اصلی از طریق قسمت های کوچک غیر جفت شده ارسال میگردد.
- داده ها به ترتیب صحیح در مقصد با هم جفت میشوند.
- داده ها برای بررسی خطا بعد از جفت شدن بررسی میشوند.
بستهها میتوانند شامل انواع بسیاری از اطلاعات شامل پیامها، فایلها و یا داده های کنترلی خاص کامپیوتری باشند. مولفههای بسته عبارتند از:
- یک آدرس مبدا[۴۶] که نشانگر کامپیوتر فرستنده است.
- دادهای که میخواهیم آن را انتقال دهیم.
- یک آدرس مقصد[۴۷] که نشانگر گیرنده است.
- دستوری که به اجزای شبکه میگوید که چگونه داده ها را انتقال دهند.
- اطلاعاتی که به کامپیوتر گیرنده میگوید که چگونه به منظور داشتن داده کامل، بستهها را به یکدیگر مرتبط کند.
- اطلاعات بررسی کردن خطا که تضمین می کند داده ها بدون نقص دریافت شده اند [۱۸].
شکل۱-۸- بسته داده ها
۱-۳- شبکه های بیسیم[۴۸]
منظور از شبکه های بیسیم اتصال دو یا چند کامپیوتر و ایجاد یک شبکه محلی با بهره گرفتن از امواج رادیویی جهت ارسال و دریافت اطلاعات و داده ها و یا اصطلاحا سرویس انتقال میباشد. کامپیوترها در شبکه بیسیم توسط امواج رادیویی داده ها را منتقل مینمایند که این امر باعث می شود بتوان فایلها، چاپگر و دسترسی به اینترنت را با هر کامپیوتر موجود در شبکه به اشتراک گذاشت.
شبکه های بیسیم ، که سریعا در حال رشد و توسعهاند. این نوع شبکه دارای تجهیزات ساده بوده و نصب تجهیزات آن آسان است و قابل حمل میباشد. در شبکه های بیسیم نیازی به سیمکشیهای طویل و دراز نیست.
اگر سازمانی از یک شبکه بیسیم استفاده کند، کاربران قادر خواهند بود هر جا به صورت آنلاین با سایر کامپیوترها و چاپگرها ارتباط پیدا کنند. با بهره گرفتن از شبکه های بیسیم میتوان عملیات زیادی انجام داد که در شبکه های سیمی امکان آنها وجود ندارد، یعنی سایر تکنولوژیهای شبکه دارای انعطاف و قابلیت شبکه بیسیم نیستند. به همین دلیل
استفادهکنندگان از شبکه های بیسیم روز به روز افزایش مییابند. اگر شخصی متصل به شبکه های بیسیم باشد، محدودیتی از نظر مکان ندارد، یعنی شخص می تواند در هتل، فرودگاه، مرکز همایش و حتی کافیشاپ و یا سایر محلها در صورت وجود پوشش، بدون هیچ محدودیتی با سرعت خیلی بالا به شبکه بیسیم متصل شده و قابلیت استفاده از آن را داشته باشد [۳۱].
۱-۳-۱- قابلیت شبکه های بیسیم
شبکه های بیسیم دارای قابلیت های زیرند:
- امکان ارتباطات موقت در شبکه.
- پشتیبانی از شبکه موجود.
- فراهم آوردن درجهای معین از قابلیت حمل[۴۹].
- گسترش دادن شبکه فراتر از محدودیتهای کابلهای مسی یا حتی فیبر نوری [۱۸].
۱-۳-۲- کاربردهای شبکه بیسیم
بکار بردن مشکل کابلها در شبکه باعث می شود که شبکه های بیسیم بسیار مورد قبول واقع شوند. شبکه های بیسیم در موارد زیر بسیار مورد استفاده قرار میگیرند:
- محیطهای شلوغ مانند راهروها و محیطهای پذیرش.
- ساختمانها و محیطهای منفرد.
- بخشهایی که گاهی محیط فیزیکی آنها تغییر می کند.
- ساختارهایی مانند ساختمانهای تاریخی که سیم کشی در آنها مشکل میباشد و … [۱۸].
۱-۳-۳- شبکه های بیسیم محلی [۵۰]
یک شبکه بیسیم معمولی به جز در رسانگر مانند شبکه های سیمی عمل می کنند. در این نوع شبکه ها به یک نقطه دسترسی[۵۱] و یک کارت شبکه نیاز خواهد بود [۱۸].
نقطه دسترسی
نقطه دسترسی دستگاهی برای برقراری ارتباط بین دستگاههای بیسیم و سیمی به یکدیگر است
که کار انتشار و دریافت سیگنالها را از کامپیوترهای اطراف برعهده دارد.
استفاده از نقاط دسترسی روش بسیار مفیدی جهت توسعه شبکه های بیسیم میباشد. در این حالت امکان اتصال به شبکه های سیمی یا اشتراک گذاری مودم پهن باند نیز وجود دارد.
در کل دو نوع نقطه دسترسی وجود دارد:
- نقاط دسترسیهایی که به عنوان یک پل بین شبکه بیسیم و شبکه های سیمی بکار میرود.
- نقاط دسترسیهایی که در آنها مسیریاب نیز تعبیه شده است و این مسیریاب باعث
می شود که تمام کامپیوترهای موجود در شبکه به صورت اشتراکی به اینترنت دسترسی داشته باشند [۱۸].
کارت شبکه
هر یک از دستگاههای موجود در یک شبکه بیسیم به یک کارت شبکه بیسیم نیاز خواهند داشت.
۱-۳-۴- تکنیکهای انتقال
شبکه های بیسیم محلی از چهار تکنیک به منظور انتقال داده ها استفاده می کنند:
- مادون قرمز[۵۲]
- لیزر[۵۳]
- امواج رادیویی پهن باند[۵۴]
- امواج ( تقسیم داده های مورد نظر به بخشهای کوچکتر جهت ارسال با بهره گرفتن از فرکانسهای گسسته و قابل دستیابی در هر زمان) [۱۸].
۱-۴- شبکه های سیار[۵۵]
یک شبکه سیار که گاهی اوقات شبکه مش سیار نامیده می شود، خود یک شبکه متشکل از لوازم سیار (متحرک) است که توسط خطوط بیسیم با هم مرتبط هستند. هر وسیله در یک آزاد است که به صورت مستقل و در هر جهتی حرکت کند و از این رو گاهی خطوط ارتباطی خود را با سایر وسیله ها تغییر دهد. بنابراین ساختار شبکه به صورت تصادفی و بسیار سریع در زمانهای غیرقابل پیش بینی تغییر می کند. از آنجایی که هر گره دارای برد انتقالی محدودی است تمام پیامها نمی توانند به تمام گرههای مورد نظر برسند. برای حفظ ارتباط در کل شبکه در یک مسیر از مبدا به مقصد مسیر از چندین گره همسایه میانی میگذرد. هر یک از وسیله ها باید جریان را بدون درنظر گرفتن استفاده خود بفرستد و از این رو یک مسیریاب هستند. اولین ادعا در ساخت یک مجهز کردن هر وسیله به نگهداری پیوسته اطلاعات مورد نیاز برای راه عبور مناسب است. چنین شبکه هایی میتوانند خودشان به تنهایی کار کنند یا ممکن است به شبکه بزرگتری منتقل شوند.
هدف ها این است که سیار بودن را در حیطه خود گسترش دهند. کاربرد وسیع از تکنولوژی در محیطهایی است که تغییر ساختار به صورت پویا مورد نیاز است و شبکه بیسیم در دسترس نیست. به عنوان مثال در میدانهای جنگ، جستجوهای اضطراری، موقعیتهای امداد و نجات و ….
افزایش لپ تاپها و شبکه های بیسیم باعث شده است که از سالهای ۱۹۹۰ تا ۱۹۹۵ به موضوع پژوهشی مورد پسندی تبدیل شود[۱۰].
فصل دوم
کدگذاری شبکه
مقدمه
هدف شبکه های ارتباطی انتقال اطلاعات بین گرههای مبدا و مقصد است. اولین سوالی که در طرحریزی شبکه پیش می آید این است که چگونه میتوان اطلاعات انتقال یافته در شبکه را افزایش داد. اخیرا نشان داده شده است که توانایی شبکه در انتقال اطلاعات می تواند به صورت چشمگیری بهبود یابد، این کار با بهره گرفتن از کدگذاری شبکه صورت میگیرد. کدگذاری شبکه حیطه پژوهشی جدیدی است که کاربردهای بسیار جالبی در سیستمهای شبکه کاربردی دارد. با بهره گرفتن از کدگذاری شبکه، گرههای میانی به جای ارسال ساده اطلاعات، جریانی از اطلاعات را ارسال مینماید که ممکن است پیچیدهتر از اطلاعات دریافتی پیشین باشد، به عنوان مثال گرههای میانی میتوانند ترکیبات خطی از اطلاعاتی را که پیش از این دریافت کرده اند، ارسال کنند. این شیوه ارسال اطلاعات کلید افزایش بازده بالقوه و قوای با درجه بالاتر میباشد که در اینجا قوا به معنای کاهش برگشت بستهها و آسانکردن پیادهسازی الگوریتمهای توزیع است [۱۱،۴].
در بخش ۱ این فصل به بررسی عمل ساده میپردازیم و در بخش ۲ کدگذاری شبکه را مورد مطالعه قرار میدهیم سپس در بخش ۳ پهنای باند و در بخشهای ۴ و۵ و۶ به ترتیب توزیعهای تکی[۵۶]، همگانی[۵۷] و چندگانه[۵۸] را بررسی میکنیم و در ادامه در بخش ۷ توزیع قابل اعتماد را مورد بحث قرار میدهیم.
۲-۱- عمل
عمل منطقی ترکیب مجزا[۵۹] (ناسازگار) که گاهی یای ناسازگار[۶۰] نیز نامیده می شود و با نمادهای یا ) نمایش داده می شود، یک ترکیب فصلی روی دو عملوند است که نتیجه آن تنها هنگامی درست است که دقیقا یکی از عملوندها درست باشند ( این یا دیگری ولی نه هر دو).
جدول زیر ترکیب دو عملوند و را تحت عمل نشان میدهد.
جدول ۲-۱- ترکیب دو عملوند A وB تحت عمل XOR
| INPUT |
OUTPUT |
| A |
B |
A XOR B |
| ۰ |
۰ |
۰ |
| ۰ |
۱ |
۱ |
| ۱ |
۰ |
۱ |
| ۱ |
۱ |
۰ |
یک سیستم با بهره گرفتن از یای مجزا یا ( و{F وT} ) یک گروه آبلی است. ترکیب
عملگرهای Λ و روی مولفههای {F وT} میدان را تولید می کند. اگر سه داده ورودی داشته باشیم، نتیجه هنگامی درست است که دقیقا یکی ازاین داده ها درست باشد. اگر تعداد زیادی داده ورودی داشته باشیم، نتیجه هنگامی درست است که تعداد فرد از داده ها درست باشد.
۲-۲- کدگذاری شبکه[۶۱]
امروزه شبکه های ارتباطی در اساس عمل مشترک هستند، خواه بستهها در اینترنت یا سیگنالها در شبکه های تلفنی باشند، اطلاعات مانند عبور اتومبیلها در بزرگراه یا انتقال جریان در لولهها انتقال مییابند. یعنی جریان داده های مستقل ممکن است در منابع اشتراک داشته باشند، اما اطلاعات خودشان مجزا باشد. مسیریابی، ذخیره سازی داده ها و به طور کلی تمام اعمال شبکه بر فرض ارسال ساده اطلاعات استوار است. کدگذاری شبکه حیطه جدیدی است که این فرض را میشکند و به جای ارسال ساده اطلاعات، گرهها میتوانند چند بسته ورودی را با هم ترکیب کنند و به صورت یک یا چند بسته خروجی درآورند. مثالی ساده در زمینه
شبکه های بیسیم ساختاری با سه گره است که در شکل ۲-۱ نشان داده شده است.کدگذاری خطی شبکه در حالت کلی مشابه این مثال است با این تفاوت که در آن عمل جای خود را به ترکیبات خطی میدهد.
شکل ۲-۱مثالی ساده از کدگذاری شبکه.
گره های و میخواهند بستهها را از طریق گره میانی رد و بدل کنند. گره بسته و گره بسته را میفرستد و در ادامه به جای و توزیع میگردد و و میتوانند بستههای مورد نظر خود را احیا کنند و در این حالت تعداد انتقالات کاهش مییابد.
کدگذاری شبکه در حیطههایی که تنها اطلاعات جزیی و یا غیر قطعی برای تصمیم گیری در دسترس است، بسیار مناسب میباشد. دریافت موفقیتآمیز اطلاعات، به دریافت حجم مشخصی از بستهها وابسته نیست بلکه به دریافت تعداد کافی از بستههای مستقل وابسته است[۴].
۲-۲-۱- کدگذاری خطی شبکه [۶۲]
سیستمی را در نظر بگیرید که مانند یک مسیریاب یا یک گره در یک شبکه توزیع نظیر به نظیر به ارسال اطلاعات می پردازد. در روشهای سنتی هنگامی که بستههای اطلاعاتی به تعدادی از گرهها میرسیدند، آن گرهها نیز به آسانی همین کار را تکرار میکردند. با بهره گرفتن از کدگذاری شبکه، به گره این اجازه را میدهیم که تعدادی از بستههایی که دریافت کرده است را با هم ترکیب کند و به یک یا چند بسته خروجی تبدیل نماید. فرض کنید که هر بسته شامل بیت باشد. هنگامی که بستههایی که میخواهند با هم ترکیب شوند دارای اندازه یکسان نباشند، بستههایی با اندازه کمتر با دنبالهای از صفرها افزوده میشوند. میتوانیم بیت متوالی از یک بسته را به صورت نمادی روی میدان معرفی کنیم و هر بسته شامل یک بردار با مولفه میباشد. با استفاده ازکدگذاری خطی شبکه، بستههای خارج شده ترکیب خطی از بستههای اصلی هستند، جاییکه جمع و ضرب روی میدان انجام می شود. دلیل انتخاب چارچوب خطی این است که الگوریتمها برای کدگذاری[۶۳] و از کد خارج کردن[۶۴] بسیار قابل فهم هستند.
ترکیبات خطی سلسلهوار نیستند، اگر ما بستههایی به طول را با هم ترکیب کنیم، بسته کدگذاری بدست آمده دارای طول است. یک بسته کدگذاری شده عموما شامل اطلاعاتی در مورد چندین بسته اصلی است[۴].
۲-۲-۲- کدگذاری
فرض کنید که تعدادی بسته اصلی ، توسط یک یا چند منبع تولید شده اند. در کدگذاری خطی شبکه هر بسته در شبکه به دنبالهای از ضرایب در مرتبط است و ، این مجموع برای هر مولفه استفاده می شود، یعنی جاییکه و به ترتیب امین مولفه هستند. به منظور ساده سازی فرض میکنیم که هر بسته شامل ضرایب که بردار کدگذاری نامیده می شود و داده کدگذاری شده که بردار اطلاعات نامیده می شود، است. بردارهای کدگذاری به منظور از کد خارج کردن داده ها توسط گیرندهها استفاده می شود. به عنوان مثال، بردار کدگذاری ، جاییکه ۱ مولفه ام است، به این معناست که بردار اطلاعات برابر است. کدگذاری می تواند به صورت بازگشتی انجام گیرد. گرهای را در نظر بگیرید که مجموعه از بستههای کدگذاری شده را دریافت و ذخیره کرده است. جاییکه بردار کدگذاری امین بسته و بردار اطلاعات امین بسته است. این گره می تواند بسته کدگذاری شده جدید را با انتخاب یک مجموعه از ضرایب را تولید و ترکیب خطی را محاسبه نماید[۴].
۲-۲-۳- از کد درآوردن
فرض کنید که یک گره مجموعه را دریافت کرده است. به منظور بازیابی بستههای اصلی لازم است که دستگاه را حل کنیم. (جاییکه ها مجهول هستند.) این دستگاه خطی دارای معادله و مجهول است. به منظور داشتن شانس احیای تمام داده ها باید داشته باشیم ، یعنی تعداد بستههای دریافت شده باید حداقل به بزرگی اندازه بستههای اصلی باشد. برعکس شرط شرط کافی نیست، چون برخی از ترکیبها باید مستقل خطی باشند[۴].
۲-۲-۴- چگونه ترکیبات خطی را انتخاب کنیم؟
مساله کدگذاری شبکه این است که هر گره شبکه چه ترکیب خطی را انجام دهد. یک الگوریتم ساده این است که هر گره در شبکه به طور یکنواخت و به صورت تصادفی ضرایب را روی میدان به روشی کاملا مستقل و غیر متمرکز، انتخاب کند. با کدگذاری تصادفی شبکه، احتمالات قطعی از انتخاب ترکیبات مستقل خطی موجود است. این احتمالات به اندازه میدان مربوط است. نتایج شبیه سازی شده حاکی از آن است که برای میدانهایی با اندازه کوچک (مثلا ) احتمالات ناچیز و اندک است. الگوریتمهایی نیز موجودند که میتوان با بهره گرفتن از آنها کدهای شبکه را طراحی کرد. این الگوریتمها مشخص می کنند که هر گره در شبکه چه ترکیبات خطی را روی بستهها پیاده کند و از آنجایی که هر گره از ضرایب خطی ثابتی استفاده می کند، لازم است که بستهها تنها بردار اطلاعات را با خود حمل کنند [۴].
۲-۲-۵- ملاحظات عملی
در این بخش ابتدا به مبحث از کد خارج کردن اشاره میکنیم. از کد درآوردن نیازمند حل یک مجموعه از معادلات خطی است که در عمل به صورت زیر انجام می شود.
یک گره بردارهای کدگذاری را که دریافت کرده است، همانند بستههای اصلی خودش، سطر به سطر در ماتریسی که به آن ماتریس از کد درآوردن گویند، ذخیره می کند، که در ابتدا تنها شامل بستههای غیر کدگذاری شده است که توسط این گره به همراه بردارهای کدگذاری مورد نظر منتشر می شود. هنگامی که یک بسته کدگذاری شده دریافت می شود به عنوان سطر آخر وارد ماتریس از کد خارج کردن می شود. ماتریس ضرایب با بهره گرفتن از روش حذفی گاوس به یک ماتریس مثلثی تبدیل میگردد. بسته دریافت شده را تغییریافته نامند اگر رتبه ماتریس را افزایش دهد. اگر یک بسته تغییریافته نباشد به سطری از صفرها توسط روش حذفی گاوس کاهش مییابد. به محض اینکه ماتریس شامل یک سطر به شکل باشد، گره میداند که بسته اصلی برابراست. این حالت هنگامی رخ میدهد که بردار کدگذاری مستقل خطی دریافت شود. توجه کنید که لازم نیست از کد خارج کردن برای تمام گرهها انجام شود، تنها گرههای گیرنده این عمل را انجام می دهند[۴].
دورهها[۶۵]
برای تمام اهداف عملی باید اندازه ماتریسها برای کدگذاری شبکه محدود باشد. این مساله برای کدگذاری جبری شبکه ها مستقیما بدست می آید. اما در صورت کدگذاری تصادفی
شبکه ها این امر بسیار مشکل میباشد. در مورد آخر معمولا بستهها به دورههایی گروهبندی میشوند و تنها بستههایی که در یک دوره یکسان قرار دارند میتوانند با هم ترکیب شوند. اندازه و ترکیب دورهها می تواند تاثیر مهمی روی اجرای کدگذاری شبکه داشته باشد. ملاحضاتی مشابه نیز برای اندازه میدان متناهی برقرار است. هر دو پارامتر باعث کاهش حافظه مورد نیاز و پیچیدگیهای مثلثاتی می شود [۴].
تاخیر
تاخیر یک مشخصه اجرایی مهم در شبکه های کامپیوتری است. تاخیر در یک شبکه عبارت است از مدت زمانی که به طول میانجامد تا یک بیت از داده ها در شبکه از یک گره به گره دیگر برود که معمولا به صورت مضربی از ثانیهها یا کسری از ثانیه اندازه گیری می شود. کاربران تنها به تاخیر کلی شبکه توجه می کنند، اما مهندسان میانگین تاخیر و ماکزیمم تاخیر را مورد توجه قرار می دهند و تاخیر را به قسمت های مختلفی تقسیم بندی می کنند که عبارتند از:
تاخیر پردازش: زمانی که به طول میانجامد تا مسیریاب بستهها را پردازش کند.
تاخیر به صف کردن: زمانی که به صف کردن داده ها اختصاص مییابد.
تاخیر انتقال: زمانی که به طول میانجامد تا بیتهای بستهها در خط ارتباطی قرار گیرند.
تاخیر انتشار: زمان مورد نیاز برای رسیدن یک سیگنال به مقصد.
بستههایی که نیاز به از کد درآوردن دارند تاثیرات اندکی در تاخیر دارند. معمولا لازم نیست که تمام بستههای کدگذاری شده قبل از اینکه تعدادی از بستهها بتوانند از کد خارج شوند، دریافت شوند. (یعنی هرگاه قاعده حذفی گاوس منجر به ایجاد یک سطر به شکل شود.) در مجموع با کاهش انتقالات مورد نیاز، تاخیرات کلی در شبکه های کدگذاری شده بزرگتر از تاخیرات در شبکه های عادی نیست [۴].
۲-۲-۶- مزایای کدگذاری شبکه چیست؟
بازده مورد نظر در محیط استاتیک
اولین نتایجی که در کدگذاری شبکه درخشید این است که کدگذاری شبکه قادر است ظرفیت شبکه را برای جریان در توزیع با چند گیرنده افزایش دهد. شبکه ای را در نظر بگیرید که به صورت یک گراف جهتدار نشان داده می شود ( عموما این شبکه سیمی است). رئوس گراف نظیر ترمینالها و یالهای گراف نظیر کانالها هستند. فرض کنید منبع داشته باشیم که هر یک اطلاعات را به نسبت مشخص ارسال می کنند و گیرنده داریم. تمام گیرندهها تمایل دارند که تمام منابع را دریافت کنند.
قضیه ۱. اگر نسبتهای منبع به گونه ای باشد که بدون کدگذاری شبکه، شبکه بتواند هر گیرنده را به تنهایی حمایت کند. (یعنی هر گیرنده می تواند تمام منابع را هنگامی که تنها یک گیرنده در شبکه موجود باشد، از کد خارج کند.) در این صورت با انتخاب مناسب از ضرایب کدگذاری خطی شبکه قادر است تمام گیرندهها را همزمان حمایت کند [۴].
به عبارت دیگر هنگامی که گیرنده در منابع شبکه مشترک هستند هر یک از آنها می تواند ماکزیمم نسبتی را که امید به دریافت آن داشته است دریافت کند. حتی اگر تمام منابع شبکه را خودش استفاده کند. از این رو کدگذاری شبکه می تواند به اشتراک بهتر منابع شبکه در دسترس کمک کند.
قدرتمندی و انطباقپذیری
مهمترین مزیت کدگذاری شبکه، قدرتمندی و انطباقپذیری آن است. به صورت شهودی فکر میکنیم که کدکذاری شبکه مشابه کدگذاری سنتی، بستههای اطلاعات را دریافت می کند و بستههای کدگذاری شده را تولید مینماید، جاییکه هر بسته کدگذاری شده به یک میزان اهمیت دارند، مشروط به اینکه تعداد کافی از بستههای کدگذاری شده را دریافت کرده باشیم (مهم نیست کدام بسته دریافت شده باشد) میتوانیم آنها را از کد درآوریم. شکل جدیدی که کدگذاری شبکه فراهم می آورد این است که ترکیبات خطی به صورتی مصلحت اندیشانه و نه تنها روی گره منبع انجام میشوند، بنابراین کدگذاری شبکه در مواردی که گرهها تنها اطلاعات ناکافی در مورد موقعیت کلی شبکه دارند بسیار مناسب میباشد.
مجددا مثال شکل ۲-۱ را در نظر بگیرید و فرض کنید که و به صورت تصادفی و بدون توجه به موقعیت فعال نباشند (یا ممکن است از محدوده خارج شده باشند)، اگر ، یا را توزیع کند، از آنجایی که گیرنده مورد نظر ممکن است قادر به دریافت بستهها نباشد، انتقالات کاملا بیفایده خواهد بود. در حالی که اگر ، یا به صورت کلیتر ترکیب خطی تصادفی از بستههای اطلاعات را توزیع کند، انتقال می تواند اطلاعاتی جدید را به گرههای فعال منتقل کند[۴].
۲-۲-۷- مثال
در این قسمت شبکه پروانهای[۶۶] را مورد بررسی قرار میدهیم. در شبکه پروانهای ( شکل ۲-۲ ) دو منبع داریم (در بالای تصویر) که یکی دارای داده و دیگری دارای داده است. دو گره مقصد نیز موجود است (در پایین تصویر) که هر یک مایلند و را دریافت کنند. هر یال تنها قادر به انتقال یک مقدار است. اگر از روشهای عادی برای انتقال داده ها استفاده کنیم یال مرکزی تنها قادر به انتقال یا است و نمیتواند هر دو را انتقال دهد. حال فرض کنید را از طریق یال مرکزی عبور دهیم. مقصد سمت چپ را دو بار دریافت می کند در حالی که را اصلا دریافت نمیکند. مسالهای مشابه در حالتی که تنها را از یال مرکزی عبور دهیم نیز رخ میدهد. حال با بهره گرفتن از یک کد ساده میتوانیم و را همزمان به هر دو مقصد ارسال کنیم. با فرستادن داده از یال مرکزی مقصد سمت چپ با دریافت و قادر است را نیز تولید کند و مقصد سمت راست با دریافت و ، را تولید می کند. این کدگذاری یک کدگذاری خطی است، زیرا اعمال کدگذاری و از کد خارج کردن هر دو خطی میباشند.
شکل ۲-۲- شبکه پروانهای
۲-۲-۸- موارد استفاده از کدگذاری شبکه.
در زیر تعدادی از کاربردهای کدگذاری شبکه را مورد بررسی قرار میدهیم.
توزیع فایل [۶۷]
احتمالا شناخته شدهترین استفاده از کدگذاری شبکه ها در است. به توزیعی در شبکه نظیر به نظیر گفته می شود که توسط پابلو رودریگز[۶۸] و کریستس گانتسیدیس[۶۹] در مایکروسافت[۷۰] طراحی شد که در آن پهنای باند نسبت به سیستم نظیر به نظیر معمولی بهبود یافته است. برای توزیعهای با حجم زیاد در شبکه های نظیر به نظیر استفاده می شود و در آن کدگذاری شبکه به کار گرفته می شود. در اینگونه شبکه توزیع سرویس دهنده، یک فایل بزرگ را به تعدادی بلوک میشکند. گرههای همتراز سعی می کنند که فایل اصلی را با دانلود بلوکها از سرویس دهنده بازیابی کنند و بلوکهای دانلود شده را بین خودشان توزیع کنند. بدین منظور گرههای همتراز ارتباط خود را با تعداد محدودی از گرههای همتراز همسایه خود حفظ می کنند که این گرههای همسایه به صورت تصادفی از بین مجموعه گرههای همتراز انتخاب میشوند. در بلوکهایی که توسط سرویس دهنده فرستاده میشوند به صورت ترکیب خطی تصادفی از بلوکهای اصلی هستند. به صورت مشابه گرههای همتراز، ترکیبات خطی تصادفی از تمام بلوکهایی که در دسترس دارند را ارسال می کنند. یک گره می تواند تعیین کند که چه تعداد بلوک تغییریافته را می تواند به یکی از همسایگانش ارسال کند. این کار با مقایسه ماتریس ضرایب از کد درآوردن خود و همسایهاش انجام میگردد، یا اینکه به آسانی بلوکهای کد شده را ارسال می کند تا هنگامی که همسایهاش اولین بلوک تغییرنیافته را دریافت کند، سپس گره انتقالاتش را به این همسایه قطع می کند تا هنگامی که بلوکهای تغییریافته بیشتری را از دیگر گرهها دریافت کند. ضرایب کدگذاری به همراه بلوکها انتقال مییابند. اما از آنجایی که معمولا بلوکها دارای اندازهای در حدود هزاران کیلو بایت هستند، این اضافات اندک و نا چیز است. در اطلاعات به سرعت به تمام کاربران در شبکه میرسد. یک گره جدید می تواند در طول مدت زمانی که عملیات توزیع در شبکه صورت میگیرد به شبکه افزوده شود. کاربر جدید ابتدا به سرویس دهنده مرکزی متصل میگردد و سپس با گرههایی که در همسایگیاش قرار دارند به تبادل جریان می پردازد.
کدگذاری شبکه از جهات بسیاری به مسالههای زیر کمک می کند:
- زمان دانلود را مینیمم می کند. در یک سیستم توزیع با اندازه بزرگ طرح ریزی بهینه بستهها بسیار پیچیده است، به خصوص اگر کاربران اطلاعات بسیار محدودی در مورد ساختار شبکه داشته باشند. با بهره گرفتن از کدگذاری شبکه، عملکرد سیستم بسیار کمتر به ساختار شبکه وابسته میگردد. در نتیجه مکانیزم بسیار سادهای که یک پوشش تصادفی را میسازد مورد استفاده قرار میگیرد.
- با توجه به عدم تشابه یا تفاوت بلوکهای کد شده، جواب بر پایه کدگذاری شبکه در حالتی که سرور کارش را قبل از اینکه تمام جفتها دانلودشان را تمام کرده باشند یا در رویارویی با نسبت به شدت بالا ( هنگامی که گرهها تنها برای مدت زمان کوتاهی با هم مرتبط باشند یا اینکه سریعا بعد از اتمام دانلودشان ارتباط آنها قطع شود .)، قطع کند، دارای قدرت بالاتری میباشد.
- کدگذاری شبکه به گرههای شبکه این اجازه را میدهد که به کدگذاری بپردازند و این امر باعث ماکزیمم شدن بازده شبکه میگردد.
- برخلاف ارسال پروتکلهای اصلی، پروتکل کدگذاری شبکه تنها خطای کوچکی را متحمل میشوند [۴، ۲۹].
شبکه های بیسیم
جریان دو طرفه در شبکه های بیسیم
همانگونه که در مثال شکل ۲-۱ دیدیم، متوجه شدیم که کدگذاری شبکه می تواند هنگامی که دو گره با ارتباط بیسیم تحت یک ایستگاه پایهای با هم ارتباط دارند، بازده را افزایش دهد. این حالت را میتوان به حالت در یک شبکه بیسیم گسترش داد، جاییکه جریان بین دو گره انتهایی دو طرفه است و هر دو گره تعداد یکسانی بسته برای تغییر دارند. اگر برنامهای داشته باشیم که مسیریابهای مجاور با هم مبادله داشته باشند بعد از چند گام اولیه، تمام مسیریابهای میانی بستههایی را برای انتقال دو طرفه در مسیر در حافظه خود ذخیره کرده اند. هرگاه فرصت انتقال افزایش یابد یک مسیریاب دو بسته را هر یک برای یک جهت با عمل ساده با هم ترکیب و به همسایگانش توزیع می کند. هر دو مسیریاب گیرنده یکی ازبستههایی که در توزیع کدگذاری شده است را میشناسند، در حالی که بسته دیگر برای آنها جدید است. بنابراین هر توزیع به دو گیرنده اجازه میدهد که یک بسته جدید را دریافت کند که این کار ظرفیت مسیر را به طور موثری افزایش میدهد.
شبکه های بیسیم مش محلی[۷۱]
حتی اگر کدگذاری شبکه تنها از عمل محدود XOR برای ترکیب بستهها استفاده کند، می تواند به طور موثری کارایی شبکه های بیسیم مش را افزایش دهد. تمام انتقالها توزیع و توسط همسایگان دریافت میشوند. بستهها با خلاصهای از اطلاعات در مورد تمام بستههای دیگری که یک گره تاکنون دریافت شده است حاشیهنگاری می شود. بدین طریق اطلاعات در مورد اینکه کدام گرهها کدام بستهها را در یک همسایگی توزیع می کنند نگهداری میشوند. یک گره می تواند چندین بسته را تحت عمل XOR برای همسایگان متفاوت کدگذاری کند و آنها را تحت یک انتقال ارسال نماید، مشروط بر اینکه هر همسایه هنوز اطلاعاتی برای از کد درآوردن اطلاعات داشته باشد [۴].
امنیت شبکه
در هر شبکه امنیت اطلاعات باید مد نظر قرار گیرد.
امنیت در برابر شنود که تلاش به احیاسازی بخش داده ها دارد. امنیت در برابر مهاجمان بدخواه که تلاش برای محروم کردن گیرندهها از اطلاعات با کاهش بستهها دارد و امنیت در برابر هجوم پارازیت.
کدگذاری شبکه، محافظت در برابر شنود را بسیار آسان می کند، زیرا اطلاعات بیشتر گسترش مییابند و شنیدن آنها مشکل است. مبدا، داده های اصلی را با اطلاعات تصادفی ترکیب می کند و یک کد شبکه را به طریقی که تنها گیرندهها قادر به از کد خارج کردن بستهها باشند، تولید می کند. علاوه بر این اطلاعات مشترک بین بستههایی که توسط شنود کننده دریافت می شود و بستههای اصلی صفر است. نوع ضعیفتری از امنیت بر این حقیقت استوار است که تنها گرههایی میتوانند بستهها را از کد درآورند که به تعداد کافی بردارهای مستقل خطی دریافت کرده باشند کاری که شنود کنندهها نمی توانند انجام دهند. کدگذاری شبکه حفاظت در برابر کاهش بستهها در شبکه را نیز آسان می کنند. در یک شبکه بدون هیچ حفاظت اضافی، مهاجمان میانی میتوانند به دلخواه در بستهای تقلیل ایجاد کنند. در حالتی که از کدگذاری شبکه استفاده شده باشد، مهاجم نمیتواند به عمل از کد درآوردن بستهها در مقصد بدون داشتن تمام بستههای کدگذاری شده که توسط مقصد دریافت شده اند، غلبه کند. بستهها از طریق مسیرهای متفاوت جریان پیدا می کنند و این کار مهاجم را مشکل میسازد. از سویی دیگر به نظر می آید که کدگذاری شبکه امنیت شبکه در برابر هجوم پارازیت را ارتقا
میبخشد. پارازیت می تواند عملکرد شبکه را مختل گرداند. در شبکه ای که پارازیت ایجاد
می شود، گرههایی وجود دارند که بستههای نامعتبر و خراب را منتشر می کنند. هنگامی که این بستههای خراب توسط گیرندهها دریافت میشوند، گیرندهها توانایی بازخوانی و از کد درآوردن آنها را ندارند، از این رو شبکه دچار اختلال میگردد. چون در یک شبکه سرویس دهنده بسته داده ها را ارسال می کند، این بستهها معتبر و درست هستند در حالی که در شبکه ای که پارازیت وجود دارد گرههای میانی نیز موجودند که به ارسال بستههای خراب و نامعتبر
میپردازند. اگر از کدگذاری در شبکه استفاده کنیم که در آن بردارهای کدگذاری به صورت تصادفی انتخاب شده اند، از آنجایی که گرههای میانی که عمل کدگذاری را انجام می دهند ممکن است پیش از این بستههای خراب را نیز دریافت کرده باشند، بستههای کد شده جدید نیز نامعتبر خواهند بود و از این رو تعداد بستههای نامعتبر در شبکه افزایش مییابد. در
اینگونه شبکه ها از کدگذاریی استفاده می شود که در آن با بهره گرفتن از یک تابع به نام تابع هش[۷۲] عمل کدگذاری صورت میگیرد و یک گره قبل از اینکه بستهای را دریافت کند، بررسی می کند که آیا این بسته معتبر است یا نه و در صورت معتبر بودن این بسته وارد ترکیب
کدگذاری میگردد. از آنجایی که بررسی معتبر بودن بستهها عملی وقتگیر است، هنگامی که یک گره یک بسته نامعتبر را میشناسد به سایر گرههای همسایه اطلاع میدهد که این بسته نامعتبر است تا آنها نیز آن را دریافت نکنند و در نهایت این امر باعث میگردد تا گرهها از پذیرش بستههای نامعتبر خودداری کنند[۳، ۴].
۲-۳- پهنای باند
در ارتباطات، تفاوت بین بالاترین و پایینترین فرکانسها را پهنای باند گویند.
در یک شبکه تلفنی پهنای باند۳۰۰۰ هرتز است که از تفاوت بین پایینترین فرکانس ارسالی ممکن که ۳۰۰ هرتز است و بالاترین فرکانس ممکن که ۳۳۰۰ هرتز میباشد به وجود می آید. در شبکه های کامپیوتری بزرگترین پهنای باند به سریعترین یا بزرگترین ظرفیت انتقال داده دلالت دارد [۱۸].
۲-۴- توزیع تکی
توزیع تکی اصطلاحی است که به ارتباطی گفته می شود که در آن اطلاعات از نقطهای به نقطه دیگر انتقال مییابد. در این حالت تنها یک فرستنده و یک گیرنده داریم و اطلاعات از یک فرستنده به یک گیرنده خاص فرستاده می شود. هنوز توزیع تکی به عنوان بیشترین نوع انتقالات در شبکه های و اینترنت کاربرد دارد. شکل ۲-۳ نمونه ای از توزیع تکی را نشان میدهد.
شکل ۲-۳- توزیع تکی
۲-۵- توزیع همگانی
توزیع همگانی به ارتباطی گفته می شود که در آن اطلاعات از یک نقطه به تمام نقاط فرستاده می شود. در این حالت تنها یک فرستنده وجود دارد، اما اطلاعات به تمام گیرندههای مرتبط فرستاده می شود. از توزیع همگانی میتوان برای ارسال یک پیام یکسان به تمام کامپیوترها در یک شبکه استفاده کرد. شکل ۲-۴ نمونه ای از توزیع همگانی را نشان میدهد.
شکل ۲-۴- توزیع همگانی
۲-۶- توزیع چندگانه
توزیع چندگانه به ارتباطی گفته می شود که در آن اطلاعات از یک نقطه به مجموعه ای از نقاط فرستاده می شود در این حالت یک و یا شاید چند فرستنده داشته باشیم که اطلاعات را به گروهی از گیرندهها میفرستند. (تعداد گیرندهها می تواند یک یا بیشتر باشد) نمونه ای از کاربرد توزیع چندگانه در کنفرانسهای تلفنی و ارسال ویدیو یا صدا به گروه خاصی از گیرندههاست.
شکل ۲-۵ نمونه ای از توزیع چندگانه را نشان میدهد [۲۳].
شکل ۲-۵- توزیع چندگانه
۲-۷- توزیع قابل اعتماد[۷۳]
ما نیاز به تعریف دقیقی از توزیع قابل اعتماد داریم. تعریفهای متعددی در این زمینه موجود است. تعریفی کلی در سال ۲۰۰۲ توسط لی[۷۴] ارائه شد که در آن سه سطح از توزیع قابل اعتماد بسته داده ها مشخص شده است که در ادامه آمدهاند:
- تمام بستههای داده ها رسانده شوند.
- تمام ترتیبها بین بستهها نگهداری شود.
- ترتیب کلی رساندن بستهها حفظ شود.
تمام تعریفها نیاز دارند که فرستنده یک بسته داده را ارسال کند و تمام گیرندههای موجود در توزیع چندگانه آن را دریافت کنند. در صورتی که چند بسته داده ارسال شود که گیرندههای آنها مشابه یا متمایز باشند، هیچ تضمینی وجود ندارد که ترتیب خاصی برای دریافت بستهها حفظ شود. به عنوان مثال اگر فرستنده دو بسته را ارسال کند، گیرنده مایل است که را قبل از دریافت کند در حالی که ممکن است تمایل داشته باشد با ترتیب عکس بستهها را دریافت کند (یعنی را قبل از دریافت کند). حال آنکه رساندن تمام بستهها می تواند به عنوان کمترین نیاز هر مکانیزم توزیع قابل اعتماد در نظر گرفته شود، در برخی موارد شرطهای دقیقتر و سختگیرانهتری مورد نظر میباشد، به عنوان مثال ممکن است ترتیبی که بستهها دریافت میشوند به عنوان شرط مورد نیاز در توزیع قابل اعتماد باشد برای نمونه میتوان به گونه ای از توزیع چندگانه اشاره کرد که در آن بستهها، اعمال روی داده ها را به روز رسانی می کنند. اگر دو گیرنده این بستههای به روز رسانی را با ترتیبهای متفاوت دریافت کنند، نتایج متفاوت خواهند بود. به عنوان مثال فرض کنید که یک متغیر صحیح با مقدار اولیه ۱۰ داریم. اگر بسته به گیرنده بگوید که مقدار را دو برابر کند و بسته از گیرنده بخواهد که ۵ واحد به اضافه کند، مقدار نهایی بعد از اینکه ابتداو سپس را دریافت کند، ۲۵ خواهد بود، به صورت مشابه مقدار نهایی گیرنده که ابتدا و سپسرا دریافت کرده است ۳۰ خواهد بود، زیرا ابتدا ۵ واحد بهاضافه کرد و بعد از آن مقدار آن را دو برابر نمود.
تفاوت بین تعریفهای دوم و سوم توزیع قابل اعتماد در قید پذیرش بستههای متفاوت است. جدیترین تعریف، تعریف سوم است که ترتیب بین تمام بستههای توزیع چندگانه تعریف می شود (که میتوانند از فرستندههای یکسان یا متفاوت فرستاده شده باشند) و اجبار می کند که تمام گیرندهها تمام بستهها را دقیقا به ترتیب دریافت کنند. ترتیبی که در آن بستههای توزیع چندگانه به تمام گیرندهها فرستاده میشوند، ترتیب کلی[۷۵] نامیده می شود.
تعریف دوم کمی ضعیفتر است و ترتیبی را اجرا می کند که به آن ترتیب جزئی[۷۶] روی بستههای توزیع چندگانه رسانده شده گفته می شود که درآن روی تمام بستهها قید ترتیب نداریم. به صورت بسیار مختصر، این تعریف میگوید که اگربتواند روی تاثیر بگذارد، تمام گیرندهها بایدرا پیش از دریافت کنند، در صورتی که هیچ تاثیری روی نداشته باشد گیرندهها میتوانند بدون ترتیب خاصی بستههایو را دریافت کنند. بسته می تواند روی بسته این چنین تاثیر بگذارد:
- بعد از توسط فرستندهای یکسان ارسال شود.
- هنگامی توسط فرستنده ارسال شود کهدریافت شده باشد.
در این موارد میگویند که بر مقدم است. از آنجایی که این رابطه ترتیبی را برای تمام بستهها اجبار نمیکند، به آن ترتیب جزئی گویند [۱۰].
فصل سوم
توزیع قابل اعتماد کد محور در شبکه های بیسیم
مقدمه
توزیع قابل اعتماد کد محور، انتشار بدون اتلاف داده ها از یک فرستنده به گروهی از گیرندهها، دارای کاربردهای وسیعی میباشد. اخیرا از کدگذاری شبکه ها در توزیع قابل اعتماد در شبکه های بیسیم استفاده شده است، جاییکه چند بسته از دست رفته با گیرندههای متمایز تحت عمل با هم ترکیب میشوند و مجددا تحت یک انتقال ارسال میگردند، که در کاهش پهنای باند بسیار موثر است. از آنجا که عمل ساده نمیتواند فرصتهای بالقوه کدگذاری را کاملا بکار گیرد و یافتن مجموعه بهینه از بستههای از دست رفته برای عمل یک مساله بهینه سازی است، در این فصل به بررسی عملهای کدگذاری کلیتری میپردازیم و به صورت اخص دو طرح جدید را نیز ارئه میکنیم. طرح استاتیک که یک بسته کدگذاری شده را مرتبا انتقال میدهد تا هنگامی که تمام گیرندههایی که تمایل به دریافت این بسته دارند، این بسته را دریافت کنند و طرح پویا که در آن بسته کدگذاری شده بعد از دریافت توسط یک یا چند گیرنده به روز رسانی می شود. سپس با بررسی تحلیلی و شبیه سازی شده این دو طرح، نشان میدهیم که طرحهای مورد بحث قرار گرفته، پهنای باند مورد نیاز را نسبت به طرحهای کد محور دردسترس بسیار کاهش می دهند، به خصوص در حالتی که بستههای از دست رفته و تعداد گیرندهها زیاد باشد.
۳-۱- تاریخچه
پهنای باند یکی از مسایل مهم در شبکه های بیسیم است. تکنیکهای کدگذاری شبکه که به گرههای شبکه این امکان را میدهد که عمل کدگذاری را روی داده ها انجام دهند، تاثیر بسیاری در کاهش پهنای باند و مصرف انرژی در شبکه های بیسیم دارند، این مساله در سال ۲۰۰۰ توسط آلسود[۷۷] بررسی شد[۱]. امروزه تلاش های قابل توجهی در خصوص استفاده از کدگذاری شبکه ها در نمونههای ارتباطی متفاوت صورت گرفته است. یو[۷۸] در سال ۲۰۰۵ نشان داد که تغییر اطلاعات مستقل بین دو گره در یک شبکه بیسیم می تواند توسط کدگذاری شبکه و توزیع فیزیک محور صورت گیرد[۲۷]. لی[۷۹] در سالهای ۲۰۰۴ و ۲۰۰۵ به بررسی حالاتی از چندین توزیع تک گیرنده پرداخت و دریافت که کدگذاری شبکه تنها می تواند فوایدی حاشیهای داشته باشد[۱۳، ۱۴]. کاتی[۸۰] در سال ۲۰۰۶ کدگذاری را ارائه داد که در آن کدگذاری بر اساس معماری شبکه صورت میگیرد () و به صورت موثری بازده شبکه را در شبکه های بیسیم بالا میبرد[۹]. در سالهای ۲۰۰۶ و ۲۰۰۷ ، سنگوپتا[۸۱] به بررسی
کدگذاری شبکه با عمل بر اساس معماری شبکه پرداخت[۲۰، ۲۷]. تلاشهایی نیز در خصوص تخمین بازده شبکه هایی بیسیم در حالت کدگذاری بر اساس ساختار شبکه صورت گرفته است[۱۲، ۱۶، ۲۷]. روای هب[۸۲] ترکیبات کلی و پیچیدهتری را نسبت به ترکیبات تحت نام کدبندی شاخص[۸۳] بررسی کرد[۲۴]. اخیرا تلاشهایی نیز در خصوص کدگذاری فیزیک محور شبکه های بیسیم صورت گرفته است[۸، ۳۰]. یو در سال ۲۰۰۵ نشان داد که در یک شبکه سیار استفاده از کدگذاری شبکه به منظور مینیمم کردن هزینه توزیع می تواند به صورت یک مساله بهینه سازی خطی مدل سازی شود [۲۱]. الگوریتمهای غیر متمرکزی توسط لون[۸۴] در سال ۲۰۰۶ به منظور ساخت درخت توزیع با هزینه مینیمم ارائه شدند[۱۷]. پارک[۸۵] در سال ۲۰۰۶ به بررسی تئوری توزیع چندگانه به وسیله کدگذاری در شبکه های غیر قابل اطمینان پرداخت [۲۲] با توجه به کاربرد کدگذاری شبکه برای توزیع در شبکه های بیسیم، الگوریتمهایی احتمالی و قطعی برای توزیع به ترتیب توسط فراگولی[۸۶][۵، ۶] و لی[۱۳] ارائه شدند که نتایجی مهم در ذخیره سازی انرژی داشتند.
توزیع قابل اعتماد، انتشار بدون اتلاف داده ها از یک فرستنده به گروهی از گیرندهها، کاربردهای وسیعی در انتشار داده های دادوستد از یک موسسه مالی به مشتریهایشان دارند. توزیع قابل اعتماد نه تنها از اتلاف داده ها جلوگیری می کند بلکه تاخیر حاصل از انتقال را نیز مورد اغماض قرار میدهد. پیش از این برای اطمینان از توزیع قابل اعتماد، منبع به آسانی داده های از دست رفته (یعنی بستههایی که توسط گیرندهها دریافت نشدهاند) را یکی یکی منتقل میکرد. در سال ۲۰۰۷ نگوین[۸۷] از کدگذاری شبکه ها برای توزیع در شبکه های بیسیم استفاده کرد و دو طرح استاتیک و پویا را بر اساس کدگذاری شبکه ها اراده داد. ایده این طرحها بدین صورت است که ابتدا بستههای از دست رفته را در حافظه ذخیره می کنند، سپس به جای ارسال یکی یکی بستههای از دست رفته، منبع یک مجموعه بهینه از بستههای از دست رفته با گیرندههای متمایز را تحت عمل با هم ترکیب می کند و تحت یک انتقال این بسته کد شده را ارسال مینماید. به عنوان مثال، فرض کنید که گره مبدا باید بستههای را به و بفرستد. گره مبدا در ابتدا بستههای ، و را یکی یکی ارسال می کند تا توسط و دریافت شوند. علاوه بر این فرض میکنیم که و توانسته اند به ترتیب بستههای ، و ، را با موفقیت دریافت کنند. از آنجایی که بستههای از دست رفته که مایل به دریافت آن بود و که تمایل به دریافت آن داشت، دارای گیرندههای متمایز هستند، گره مبدا به جای ارسال مجدد و جداگانه و ، را ارسال می کند. با دریافت توسط ، او می تواند با بهره گرفتن از بسته که قبلا آن را دریافت کرده است بسته را احیا کند. به صورت مشابه با دریافت ، نیز قادر به احیای بسته خواهد بود. تفاوت عمده طرح استاتیک و پویا این است که در طرح استاتیک بسته کدگذاری شده (با عمل) متناوبا ارسال میگردد تا هنگامی که تمام گیرندههایی که تمایل به دریافت این بسته دارند، بسته را دریافت کنند. در حالی که در طرح پویا بسته کدگذاری شده به منظور بهبود تاثیرات انتقال، در هر انتقال به صورت پویا به روز رسانی می شود. (در بخش ۳-۲-۳ به بررسی این مطلب میپردازیم) به منظور بیشتر مشخص شدن آنچه گفته شد به بررسی مثالی ساده میپردازیم. شکل ۳-۱ شبکه ای با دو گیرنده و و ۹ بسته را نشان میدهد. در این مثال بستهها با اعداد ۱ تا ۹ مشخص شده اند.
| |
۱ |
۲ |
۳ |
۴ |
۵ |
۶ |
۷ |
۸ |
۹ |
| |
|
O |
O |
|
O |
O |
|
O |
|
| |
O |
O |
|
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 15th 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 39th 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
