دانشکده علوم
پایان نامهی کارشناسی ارشد در رشتهی ریاضی کاربردی- تحقیق در عملیات
توزیع قابل اعتماد کد محور در شبکههای بیسیم
به وسیلهی
راضیه دلپسند
استاد راهنما
دکتر محمد باقر احمدی
دی ماه 1390
به نام خدا
اظهار نامه
اینجانب راضیه دلپسند (880618) دانشجوی رشته ریاضی کاربردی گرایش تحقیق در عملیات دانشکدهی علوم اظهار میکنم که این پایان نامه حاصل پژوهش خودم بوده و در جاهایی که از منابع دیگران استفاده کردهام، نشانی دقیق و مشخصات کامل آن را نوشتهام. همچنین اظهار میکنم که تحقیق و موضوع پایاننامهام تکراری نیست و تعهد مینمایم که بدون مجوز دانشگاه دستاوردهای آن را منتشر ننموده و یا در اختیار غیر قرار ندهم. کلیه حقوق این اثر مطابق با آیین نامه مالکیت فکری و معنوی متعلق به دانشگاه شیراز است.
نام و نامخانوادگی: راضیه دلپسند
تاریخ و امضا:15/11/1390
هر چيز را بهانه ‌ايست و بهانه‌ي اين مجموعه، حضور لطيف پدر و مادرم است كه نكهت نگاه ژرف و فهيم آنان همانند بارش باران بود بر كوير دلم و گل ‌واژه‌هاي اين دفتر حاصل رويش جوانه‌هاي بعد از باران آن نگاه است.
سپاسگزاری
ثنا و ستایش بیکران خدای متعال را که توفیق نصیب من کرد تا این پایاننامه را به پایان برسانم و با تقدیر و تشکر از استاد ارجمند جناب آقای دکتر محمد باقر احمدی که حکمتها، راهنماییها و حمایتهای بیدریغ ایشان همواره راهنما و راهگشای من بوده است.
چکیده
توزیع قابل اعتماد کدمحور در شبکههای بیسیم
به کوشش
راضیه دلپسند
در این پایاننامه به بررسی توزیع قابل اعتماد کدمحور در شبکههای بیسیم بر اساس مقالهای با عنوان “توزیع قابل اعتماد کد محور در شبکههای بیسیم” که توسط چی، جیانگ و هوریگوچی نگارش شده است [2] میپردازیم. اخیرا از کدگذاری شبکهها در توزیع قابل اعتماد در شبکههای بیسیم استفاده شده است. چون استفاده از عمل XOR به منظور کدگذاری شبکه دارای محدودیتهایی است، در این پایاننامه به بررسی این محدودیتها میپردازیم و در ادامه عملهای کدگذاری کلیتر را مطالعه و دو طرح جدید استاتیک و پویا را معرفی میکنیم که نه تنها محدودیتهای عمل XOR را ندارند، بلکه دارای پیچیدگی چندجملهای نیز هستند. با بررسی تحلیلی و شبیهسازی شده این دو طرح، ثابت شده است که طرحهای مورد بحث قرار گرفته، پهنای باند مورد نیاز را نسبت به طرحهای کدمحور در دسترس بسیار کاهش میدهند، به خصوص در حالتی که بستههای از دسترفته و تعداد گیرندهها زیاد باشد.
فهرست مطالب
عنوان صفحه
فصل اول: شبکه
مقدمه2
1-1- شبکه3
1-1-1- مولفههای شبکههای ارتباطی 4
1-1-2- مثالهایی از شبکه5
1-2- شبکههای کامپیوتری6
1-2-1- ساختارشبکه9
1-2-1-1- ساختار گذر10
1-2-1-2- ساختار ستارهای10
1-2-1-3- ساختار حلقوی11
1-2-1-4- ساختار مش11
1-2-2- اجزای شبکه12
1-2-2-1- سخت افزار شبکه12
1-2-2-2- رسانههای انتقال12
1-2-2-3- نرم افزار شبکه12
1-2-3- چگونه شبکهها دادهها را ارسال میکنند13
1-3- شبکههای بیسیم15
1-3-1- قابلیت شبکههای بیسیم15
1-3-2- کاربردهای شبکه بیسیم16
1-3-3- شبکههای بیسیم محلی16
1-3-4- تکنیکهای انتقال17
1-4- شبکههایad-hoc سیار17
عنوان صفحه
فصل دوم: کدگذاری شبکه
مقدمه19
2-1- عمل XOR20
2-2- کدگذاری شبکه21
2-2-1- کدگذاری خطی شبکه22
2-2-2- کدگذاری22
2-2-3- از کد درآوردن23
2-2-4- چگونه ترکیبات خطی را انتخاب کنیم23
2-2-5- ملاحظات عملی23
2-2-6- مزایای کدگذاری شبکه چیست؟25
2-2-7- مثال26
2-2-8- موارد استفاده کدگذاری شبکه27
2-3- پهنای باند30
2-4-توزیع تکی 30
2-5-توزیع همگانی31
2-6- توزیع چندگانه31
2-7- توزیع قابل اعتماد32
فصل سوم: توزیع قابل اعتماد کد محور در شبکههای بیسیم
مقدمه35
3-1- تاریخچه36
3-2- طرحهای توزیع کد محور39
3-2-1- محدودیتهای عمل کدگذاری XOR40
3-2-2- طرح جامع کدمحور استاتیک43
3-2-2-1- اندازه میدان46
3-2-2-2- پیچیدگیهای محاسباتی46
3-2-3- طرح جامع کدمحور پویا47
3-2-3-1- اندازه میدان49
3-2-3-2- پیچیدگی محاسباتی50
عنوان صفحه
3-3- تحلیل اجرا51
3-3-1- تحلیل طرح SGC51
3-3-1-1- پهنای باند انتقال51
3-3-1-2- تاخیر انتقال مجدد56
3-3-2- تحلیل طرح DGC58
3-3-2-1- پهنای باند انتقال58
3-3-2-2- تاخیر انتقال مجدد59
3-4- نتایج عددی60
3-4-1- محیط شبیه سازی60
3-4-2- پهنای باند انتقال60
3-4-3- تاخیر انتقال مجدد63
3-5- نتیجه گیری64
فهرست منابع و مأخذ65
پیوست
– واژه نامه فارسی به انگلیسی68
– واژه نامه انگلیسی به فارسی72
فصل اول
مقدمه
امروزه با پیشرفت تکنولوژی اطلاعات نیاز به استفاده از امکانات روز جهت تبادل دادهها با سرعت و دقت بالا و رهایی از محدودیتهای محیطی بیشتر احساس میشود بنابراین لازم است از امکانات و تجهیزاتی که بتواند به سادگی و آسانی راهاندازی شود استفاده نمود.
یکی از راحتترین، سادهترین و کم هزینهترین روشها استفاده از شبکههای کامپیوتری بخصوص شبکههای کامپیوتری بیسیم است.
با توجه به نیاز به اشتراک گذاشتن به موقع دادهها ایده ایجاد شبکه شکل گرفت. کامپیوترهای شخصی ابزارهایی جالب برای تولید انواعی از اطلاعات هستند، اما به شما این اجازه را نمیدهند که به سرعت دادههای تولیدی خود را به اشتراک بگذارید. بدون شبکه، اسناد باید چاپ شوند تا دیگران بتوانند آنها را ویرایش کنند یا مورد استفاده قرار دهند. در بهترین حالت میتوانید فایل مربوطه را در اختیار آنها قرار دهید تا در کامپیوتر خود ذخیره کنند. اگر دیگران در آنها تغییراتی ایجاد کنند هیچ راهی برای ترکیب تغییرات وجود ندارد. اگر چند کامپیوتر و یا حتی وسایل دیگری مانند چاپگر و … به یکدیگر متصل شوند، یک شبکه ایجاد میشود که میتوانند اطلاعات را بین یکدیگر به اشتراک گذارند.
در بخش 1 این فصل به بررسی مفهوم شبکه پرداخته و اجزای شبکه را مورد بررسی قرار خواهیم داد. در بخش دوم به بررسی شبکههای کامپیوتری میپردازیم. در بخش سوم
شبکههای بیسیم مورد مطالعه قرار خواهند گرفت و بخش 4 به معرفی شبکههای ad-hoc سیار میپردازد.
شبکه 1
یک شبکه از اتصال تعداد بسیاری گره2 که جریانی مطلوب در آن وجود دارد به وجود میآید. گرهها نقاطی هستند که در آنها بیش از دو شاخه یا خط ارتباطی3 که جریان از طریق آنها عبور میکند، یکدیگر را ملاقات میکنند. شکلی که در ادامه میآید یک شبکه با پنج گره A ، B ،C، D وE را نشان میدهد. این گرهها با خطوط ارتباطی یا شاخههای گوناگونی مانند L_AB ، L_BC،L_CD ،L_BD و… با هم مرتبط شدهاند.
شکل 1-1- ساختار شبکه
در مهندسی برق یک مثال ساده از شبکه، یک شبکه الکتریکی است که خطوط ارتباطی آن اجزای الکتریکی مانند مقاومت4، خازنها5، القاکنندهها6 و اجزای فعال هستند که جریان از طریق این شاخهها عبور و گرههای بسیاری را ملاقات میکند. جریان عبوری از طریق تعدادی از شاخهها به یک گره میرسد و از طریق تعدادی شاخه دیگر از گره خارج میشوند.
در شبکههای حمل و نقل جادهای جادههای مختلف در تقاطعها و یا چهارراهها، که میتوان از آنها به عنوان یک گره یاد کرد، با یکدیگر برخورد میکنند. جادهها مانند خطوط ارتباطی عمل میکنند و وسایل نقلیه در آنها جریان دارند. دریک تقاطع یک وسیله نقلیه از یک جاده
میآید و به جاده دیگری که در نظر دارد میرود. به صورت مشابه شبکههای ریلی و خطوط هوایی را داریم. شبکههای پستی شبکههایی هستند که در آنها پیام از مبدأ به مقصد فرستاده میشود. امروزه با ابداع ارتباطات الکترونیکی به شبکههای تلفنی، اطلاعاتی و رادیویی تلویزیونی دسترسی داریم.
سازماندهی شبکههای ارتباطی به صورت گام به گام مورد بحث قرار میگیرند. یک شبکه از گرهها و شاخهها به منظور تسهیل جابهجاییهای فیزیکی تشکیل شده است. جریان از طریق یک گره وارد شبکه میشود و از یک گره به نام گره مقصد از شبکه خارج میشود که این گره به گره مصرفکننده معروف است. هر گرهای میتواند به عنوان یک گره مبدأ و یا مصرفکننده باشد.
مولفههای شبکههای ارتباطی
گره
در یک شبکه ارتباطی یک گره نقطهای است که در آن بیش از دو شاخه یکدیگر را ملاقات میکنند ممکن است یک شبکه ارتباطی دارای تعداد بسیار زیادی گره باشد که یک گره لزوما به تمام گرهها مرتبط نیست. کار یک گره از شبکه، اتصال مسیر وارد شونده به مسیر خارج شونده است، از این رو سیگنالها میتوانند مسیر خود را به مسیر مطلوبشان برای انتقال پیش رو تغییر دهند. به صورت متعارف در یک شبکه تلفنی، مراکز تلفنی و یا تلفن خانهها نقش گره را بازی میکنند. در یک شبکه اطلاعاتی یک گره یک بسته سوییچ7 است که به آن مسیریاب8 گفته میشود. برخی از گرهها به خصوص گرههای تغییر پیام یا بسته، دارای بافر و حافظه برای پیامها هستند. چنین گرههایی همانند سوییچهای ذخیره و ارسال کار میکنند. گرهها اعمال دیگری چون یکسان سازی پیامهای دریافتی، آزمایش کردن خروجیها و … را نیز انجام میدهند.
شاخه
شاخه شبکههای ارتباطی اساسا یک رسانگر انتقال9 است که یک سیم یا یک کانال رادیویی است. رسانگر انتقالات سیمی میتواند به هر یک از شکلهای جفت سیمهای مسی، کابلهای چند جفتی، کابلهای هممحور10 و یا فیبر نوری11 باشند. این سیمها سیگنالها را از یک گره به گره دیگر میبرند. یک کانال بیسیم یک طیف الکترومغناطیسی از فرکانسهای بسیار پایین تا فرکانسهای بسیار بالا شامل موجهای میلیمتری و نوری گسترده شدهاند. پهنای باند12
کانالهای سیمی یا بیسیم دارای برد عرضی بالایی است میتواند نسبت دادههای عبوری را از چند بیت در ثانیه تا چند گیگا – پنتا بیت در ثانیه پوشش دهد. طول این خطوط انتقال با توجه به دلایل متنوعی مانند پراکنش محدود است. در یک شبکه ارتباطی چند منظوره لزومی ندارد که تمام خطوط ارتباطی از یک نوع باشد، بعضی میتوانند خطوط سیمی و بعضی خطوط بیسیم باشند.
هم اکنون یک شبکه ارتباطی را میتوان به صورت گردایهای از گرهها که توسط خطوط ارتباطی با یکدیگر مرتبط هستند تعریف کرد که اطلاعات را از طریق سیگنالها به شکل الکتریکی یا نوری منتقل میکنند. بنابراین گرهها، خطوط ارتباطی و انتقال اطلاعات ویژگی اساسی هر شبکهای هستند. برخی از معمولترین و شناخته شدهترین و عریضترین شبکههای پیامی13، شبکههای پستی14، شبکههای تلگرافی15، شبکههای تلفنی16 (ثابت، معمولی و سیار)، شبکههای کامپیوتری17 و
شبکههای سرگرمی18 (پخش کنندههای تلویزیون یا صوتی) میباشند.
مثالهایی از شبکه
یک شبکه با توجه به کاربردی که دارد طراحی و به کار گرفته میشود. گونههای بسیاری از شبکه موجود است. شبکه تلگرافی برای ارسال تلگرافها از یک مکان به مکان دیگر مورد استفاده قرار میگیرند. در آنها از سوییچهای پیام به عنوان گره استفاده میشود و اساسا سرویسی با سرعت بسیار پایین ارائه میدهد. از سویی دیگر شبکههای تلکس مانند شبکههای تلفنی کار میکنند و کاربران میتوانند مستقیما پیامهای متنی خود را بدون کمک اپراتور به مقصد مورد نظر ارسال نمایند. شبکه تلفنی برای ارتباطات صوتی بین دو کاربر مورد استفاده قرار میگیرد. یک شبکه کامپیوتری به کاربران این اجازه را میدهد که با استفاده از شبکه کامپیوتری با هم ارتباط برقرار کنند. دادههای صوتی و تصویری میتوانند از طریق شبکه پخش19 به طور همزمان از یک مبدأ به تعداد زیادی از استفادهکنندهها ارسال شود.
به منظور بیشتر مشخص شدن مفهوم شبکه، شبکه کامپیوتری را مورد بحث قرار میدهیم.
1-2- شبکه کامپیوتری
با توجه به استفاده گسترده از کامپیوترها، دیگر استفاده از آنها به یک مکان خاص محدود نمیشود و نیاز به اینکه کامپیوترها در مکانهای مختلف با یکدیگر مرتبط شوند احساس میشود. یک شبکه کامپیوتر که اغلب از آن به عنوان شبکه یاد میشود، از گروهی از کامپیوترها و وسیلهها تشکیل شده است که توسط کانالهای ارتباطی با یکدیگر مرتبط هستند و ارتباط بین کاربران را آسان میسازد. یک شبکه به کاربران این اجازه را میدهد که از منابع و اطلاعات به صورت مشترک استفاده کنند. بر اساس پراکندگی جغرافیایی کامپیوترها اساسا سه نوع شبکه موجود است که در ادامه به آنها اشاره میکنیم [7].
شبکههای محلی (LAN)20
در این نوع شبکه، کامپیوترها و دیگر وسایل ارتباطی در یک محیط کوچک به یکدیگر مرتبط هستند. محیط میتواند یک ساختمان یا مجموعهای از ساختمانها در یک محوطه باشد. نمونهای از شبکه محلی، شبکه کتابخانهای است که مورد استفاده قرار میگیرد[7].
شبکههای شهری (MAN)21
اساسا یک شبکه شهری بزرگتر از شبکههای محلی است و عموما از ساختاری مشابه استفاده میکنند که میتواند گروهی از دفاتر مجاور و یا در یک شهر را پوشش دهد و میتواند خصوصی و یا عمومی باشد [7].
شبکههای گسترده (WAN)22
در این شبکه کامپیوترها میتوانند از یکدیگر دورتر باشند و شهرها، کشورها و یا حتی قارهها را پوشش دهند. کامپیوترها میتوانند از طریق خطوط تلفن23، امواج رادیویی24 و فیبر نوری به یکدیگر متصل شوند [7].
شبکهها به دوگروه کلی تقسیم میشوند که عبارتند از شبکههای نظیر به نظیر25 و شبکههای سرویس دهنده محور26.
تفاوت بین شبکههای نظیر به نظیر و سرویسدهنده محور بسیار مهم است، زیرا هر یک دارای قابلیتهای متفاوت هستند. نوع شبکهای که شما آن را اجرا میکنید به عوامل بسیاری از جمله اندازه سازمان، سطح امنیت، نوع کار، سطح مدیریت شبکه، حجم ترافیک شبکه و بودجه شبکه وابسته است.

شبکههای نظیر به نظیر
تعریفهای مختلفی از سیستم نظیر به نظیر ارائه شده است که به طور کلی آن را سیستمی میدانند برای اشتراک منابع و سرویسهای کامپیوتر با انجام تبادل مستقیم بین آنها و در محیطی که اتصالات پایدار و آدرس هایIP قابل پیشبینی وجود ندارد و سیستم نمیتواند متکی به یک سرویس دهنده متمرکز باشد استفاده میشود.
در یک شبکه نظیر به نظیر هیچ سرویس دهندهای وجود ندارد و یا بین کامپیوترها درجهبندی صورت نمیگیرد. تمام کامپیوترها یکسان هستند و از این رو نظیر یکدیگر میباشند. عموما هر کامپیوتر به عنوان یک سرویس گیرنده27 و یک سرویس دهنده28 عمل میکند و هیچ یک مسئول اداره کردن کل شبکه نمیباشند. در این نوع شبکهها کاربر هر کامپیوتر مشخص میکند که چه دادههایی در کامپیوترش در شبکه به اشتراک گذاشته شود و کاربران مسئول کامپیوتر خود و امنیت آن میباشند.
شبکه نظیر به نظیر یک نوع شبکه ساده است و از آنجایی که هر کامپیوتر خودش به عنوان یک سرویس گیرنده و یک سرویس دهنده کار میکند، دیگر نیازی به یک سرویس دهنده مرکزی و قدرتمند نیست و در نتیجه شبکههای نظیر به نظیر نسبت به شبکههای سرویس دهنده محور ارزانتر هستند.
شبکه نظیر به نظیر میتواند خالص یا ترکیبی29 باشد. در مدل خالص هیچ سرویس دهنده متمرکزی وجود ندارد. در مدل ترکیبی، هر گره از طریق یک سرویس دهنده به سیستم وارد میشود که این سرویس دهنده میتواند برای شناسایی گره و اطلاعات دارای مجوز ورود بکار رود. بعد از ورود به سیستم جفتها بطور مستقیم و بدون دخالت سرویس دهنده با هم ارتباط برقرار
میکنند.
شبکههای نظیر به نظیر هنگامی مورد استفاده قرار میگیرند که :
تعداد کامپیوترها از 10 کمتر باشد.
تمام کاربران در یک مکان قرار گرفته باشند.
امنیت شبکه مهم نباشد.
در آینده نیازی به توسعه شبکه نباشد.
در ادامه نمونهای از شبکههای نظیر به نظیر نشان داده شده است [18، 26].
شکل 1-2- نمونهای از شبکههای نظیر به نظیر
انتخاب یک روش نظیر به نظیر معمولا به دلیل یک یا چند مورد از اهداف زیر صورت میگیرد.
تقسیم و کاهش هزینه
راهاندازی یک سیستم متمرکز که بتواند از سرویس گیرندههای زیادی پشتیبانی کند، هزینه زیادی را به سرویس دهنده تحمیل خواهد کرد. معماری نظیر به نظیر میتواند کمک کند تا این هزینه بین تمام گرهها تقسیم شود.
افزایش قابلیت اعتماد
بدلیل عدم وجود یک منبع قدرتمند مرکزی، قابلیت اعتماد در سیستم یکی از اهداف مهم به شمار میآید و بنابراین باعث نوآوریهای الگوریتمی در این زمینه میشود.
افزایش خودمختاری
در بسیاری از موارد کاربران در یک شبکه توزیع مایل نیستند که متکی به یک سرویس دهنده متمرکز باشند چون متکی بودن به یک سرویس دهنده متمرکز باعث محدود بودن آنها
میشود. مثلا در مورد کاربرد اشتراک فایل، کاربران میتوانند بطور مستقیم فایلهای یکدیگر را دریافت کنند بدون آنکه متکی به یک سرویس دهنده متمرکز باشند که ممکن است مجوز دریافت فایل را به آنها ندهد.
گمنامی
این واژه وابسته به همان خودمختاری میشود. کاربران ممکن است مایل نباشند که هیچ کاربر دیگری یا سرویس دهندهای اطلاعاتی در مورد سیستم آنها داشته باشد. با استفاده از یک سرویس دهنده مرکزی نمیتوان از گمنامی مطمئن بود، چون حداقل سرویس دهنده باید بگونهای بتواند سرویسگیرنده را شناسایی کند، مثلا با استفاده از آدرس اینترنتی آن. با استفاده از معماری نظیر به نظیر چون پردازشها به صورت محلی انجام میشود، کاربران
میتوانند از دادن اطلاعاتی در مورد خودشان به دیگران اجتناب کنند.
پویایی
فرض اولیه سیستمهای نظیر به نظیر این است که در یک محیط کاملا پویا قرار داریم. منابع و گرهها میتوانند آزادانه به سیستم وارد و از آن خارج شود.
شبکههای سرویس دهنده محور
در محیطی که تعداد کامپیوترها زیاد باشد شبکههای نظیر به نظیر مناسب نمیباشد و از این رو شبکهها باید دارای سرویس دهنده مشخصی باشند. سرویس دهنده تنها به عنوان سرویس دهنده عمل میکند و نیاز اجزای شبکه را سریعا برآورده میکند و امنیت فایلهای شبکه را بر عهده دارد.
هنگامی که اندازه و ترافیک شبکه افزایش مییابد بیش از یک سرویس دهنده در شبکه مورد نیاز است. تقسیم کارها بین سرویس دهندهها تضمین کننده اجرای هر کار به بهترین روش ممکن در شبکه است. نمونهای از شبکههای سرویس دهنده محور در شکل 1-3 نشان داده شده است [18].

شکل 1-3- نمونهای از شبکههای سرورمحور
1-2-1- ساختار شبکه
ساختار شبکه به شکل شبکه اشاره دارد. چگونگی اتصال گرههای مختلف در یک شبکه به یکدیگر و انتقالات بین آنها با ساختار شبکه معین میگردد. چهار نوع معمول از ساختار شبکه موجود است که در ادامه به آن اشاره میکنیم.
1-2-1-1- ساختار گذر30
در این ساختار تمام وسیلهها به یک کابل مرکزی به نام گذر یا ستون فقرات31 متصل هستند. سادگی، کم هزینه بودن و توسعه آسان این شبکه از نقاط قوت آن است و نقطه ضعف عمده این شبکه آن است که اگر کابل اصلی که به عنوان پل ارتباطی بین کامپیوترهای شبکه است، قطع شود، کل شبکه از کار خواهد افتاد [18].
شکل 1-4- ساختار گذر
1-2-1-2- ساختار ستارهای32
در این ساختار تمام وسیلهها به یک هاب33 مرکزی متصل هستند. گرهها با عبور دادهها از هاب با یکدیگر ارتباط دارند. نقطه ضعف این شبکه این است که عملیات کل شبکه به هاب وابسته است و اگر هاب از کار بیافتد کل شبکه از کار خواهد افتاد.
نقاط قوت شبکه ستارهای عبارتند از:
نصب شبکه با این ساختار ساده است.
توسعه شبکه با این ساختار به راحتی انجام میشود.
اگر یکی از خطوط متصل به هاب قطع شود فقط یک کامپیوتر از شبکه خارج
میشود [18].
شکل 1-5- ساختار ستارهای
1-2-1-3- ساختار حلقوی34
در این ساختار تمام وسیلهها به شکل یک حلقه بسته به یکدیگر متصل هستند بنابراین هر وسیله مستقیما به دو وسیله دیگر در ارتباط است که در دو طرف آن قرار دارند.
نقطه ضعف شبکههای حلقوی این است که به سخت افزار پیچیده نیاز دارد. (کارت شبکه آن گران قیمت است)
و نقاط قوت شبکههای حلقوی عبارتند از:
نصب شبکه با این ساختار ساده است.
توسعه شبکه با این ساختار به راحتی انجام میشود [18].
شکل 1-6- ساختار حلقوی
1-2-1-4- ساختار مش35
در این ساختار وسیلهها از طریق ارتباطات فراوان بین گرهها به یکدیگر متصل هستند. در یک شبکه مش هر گره با تمام گرهها ارتباط دارد. مزیت این نوع شبکه این است که هر کامپیوتر با سایر کامپیوترها ارتباطی مجزا دارد که دارای بالاترین درجه پایداری و اطمینان است. اگر یک کابل از شبکه ارتباطی در ساختار مش قطع شود شبکه همچنان فعال باقی خواهد ماند. ضعف اساسی شبکههای مش آن است که از تعداد زیادی خطوط ارتباطی استفاده میکند، به خصوص هنگامی که تعداد ایستگاهها افزایش مییابد، به همین دلیل این ساختار از نظر اقتصادی مقرون به صرفه نیست.
شکل 1-7- ساختار مش
1-2-2- اجزای شبکه
اجزای اساسی شبکه عبارتند از سخت افزار شبکه 36، رسانههای انتقال و نرم افزار شبکه37.
1-2-2-1- سخت افزار شبکه
جزء اصلی یک شبکه کامپیوتری سخت افزار شبکه است. کامپیوترها در یک شبکه به دو گروه سرویس دهنده و سرویس گیرنده تقسیم میشود. کامپیوتر سرویس دهنده کامپیوتری است که دارای قدرت و سرعت بالاتری است، سرویس گیرندهها به سرویس دهنده متصل هستند و در شبکههای نظیر به نظیر هیچ سرویس دهندهای وجود ندارد.
1-2-2-2- رسانههای انتقال
انتقال دادهها و عبور سیگنالها از انتقال دهنده به گیرندهها از طریق یک مسیر صورت میگیرد که این مسیر رسانه نام دارد.
رسانههای هدایت شده38
در این گونه رسانهها دادهها از طریق مسیرهای فیزیکی انتقال مییابند، گونههای متفاوتی از کابلها در این رسانهها مورد استفاده قرار میگیرند که با توجه به ساختار شبکه انتخاب میشوند، که گونههایی از آنها عبارتند از کابلهای هممحور، زوج سیمهای به هم تابیده شده مسی39 و کابل فیبرنوری.
رسانههای هدایت نشده40
در این رسانهها هیچ سیمی وجود ندارد و اطلاعات از طریق امواج رادیویی یا مایکروویو انتقال مییابند.
1-2-2-3- نرم افزار شبکه
نرم افزار شبکه مجموعهای از نرم افزارهاست که به کامپیوترهایی که با هم در ارتباط هستند اجازه میدهد که به صورتی راحت و کم هزینه از نرم افزارها استفاده کنند. نرم افزار شبکه عملکرد هر سیستم شبکه را کنترل مینماید، به عنوان مثال کنترل میکند که چه کسانی اجازه استفاده از شبکه را دارند، چه زمانی میتوان از شبکه استفاده کرد، کاربران اجازه انجام چه کارهایی را دارند و چه منابعی برای شبکه در دسترس میباشد.
کارت شبکه (NIC)41
هر کامپیوتر به یک کارت شبکه نیاز دارد، که به هر ایستگاه اجازه میدهد تا با سایر ایستگاهها تبادل اطلاعات کنند.
سوییچ42
سوییچها اساسا پلهای ارتباطی43 هستند که چندین قسمت دارند و قسمتهای مختلف شبکه را به یکدیگر متصل میکنند.
هاب
یک هاب برای متصل کردن چندین کامپیوتر و وسیله از طریق کابلهای خاص استفاده
میشود. هابها ارزان هستند و اتصالها آسان صورت میگیرد[18].
مسیریاب
در محیطی که قسمتهای مختلفی از شبکه وجود دارد، ممکن است یک پل ارتباطی به منظور اطمینان از ارتباطات سریع میان قسمتهای مختلف، کافی نباشد. در چنین محیطی وسیلهای لازم است که نه تنها آدرس هر قسمت از شبکه را بداند بلکه بتواند بهترین مسیر را برای ارسال دادهها به قسمتهای مختلف تعیین کند، به چنین وسیلهای مسیریاب گویند. مسیریابها نسبت به پلهای ارتباطی اجازه دسترسی به اطلاعات بیشتری را دارند و از این اطلاعات به منظور مدیریت بهتر ترافیک در شبکه استفاده میکنند. مسیریابها گاهی مدخل44 نیز نامیده میشوند [18].
1-2-3- چگونه شبکهها دادهها را ارسال میکنند؟
معمولا دادهها به صورت فایلهایی با اندازههای بزرگ میباشند. اگر کامپیوترها همزمان تعداد زیادی داده را در شبکه قرار دهند، شبکه نمیتواند به درستی کار کند و سرعت شبکه کاهش مییابد. مقادیر زیاد داده به عنوان یک واحد بزرگ عملکرد شبکه را مختل مینماید و ارتباطات را امکانناپذیر میسازد، زیرا کامپیوترها کابلها را توسط دادهها پر کردهاند. از آنجایی که کاربران مایل هستند دادهها را به سرعت و به آسانی در شبکه عبور دهند، دادهها باید به قسمتهای کوچک و قابل اداره شکسته شوند، که به این قسمتها بسته45 گفته میشود.
بستهها واحدهای اساسی شبکههای ارتباطی هستند. با تقسیم دادهها به بستهها، انتقالات مجزا به سرعت صورت میپذیرد و از این رو هر کامپیوتر در شبکه شانس بیشتری برای انتقال و دریافت اطلاعات دارد. در کامپیوتر گیرنده، بستهها جمعآوری میشوند و به منظور بدست آوردن داده اصلی با ترتیبی مناسب سرهمبندی میشوند.
هنگامی که کامپیوتر فرستنده، دادهها را به بستهها میشکند، اطلاعات کنترلی خاصی را در هر یک از بستهها قرار میدهد که از طریق آن :
داده اصلی از طریق قسمتهای کوچک غیر جفت شده ارسال میگردد.
دادهها به ترتیب صحیح در مقصد با هم جفت میشوند.
دادهها برای بررسی خطا بعد از جفت شدن بررسی میشوند.
بستهها میتوانند شامل انواع بسیاری از اطلاعات شامل پیامها، فایلها و یا دادههای کنترلی خاص کامپیوتری باشند. مولفههای بسته عبارتند از:
یک آدرس مبدا46 که نشانگر کامپیوتر فرستنده است.
دادهای که میخواهیم آن را انتقال دهیم.
یک آدرس مقصد47 که نشانگر گیرنده است.
دستوری که به اجزای شبکه میگوید که چگونه دادهها را انتقال دهند.
اطلاعاتی که به کامپیوتر گیرنده میگوید که چگونه به منظور داشتن داده کامل، بستهها را به یکدیگر مرتبط کند.
اطلاعات بررسی کردن خطا که تضمین میکند دادهها بدون نقص دریافت شدهاند [18].
شکل1-8- بسته دادهها
1-3- شبکههای بیسیم48
منظور از شبکههای بیسیم اتصال دو یا چند کامپیوتر و ایجاد یک شبکه محلی با استفاده از امواج رادیویی جهت ارسال و دریافت اطلاعات و دادهها و یا اصطلاحا سرویس انتقال میباشد. کامپیوترها در شبکه بیسیم توسط امواج رادیویی دادهها را منتقل مینمایند که این امر باعث میشود بتوان فایلها، چاپگر و دسترسی به اینترنت را با هر کامپیوتر موجود در شبکه به اشتراک گذاشت.
شبکههای بیسیم ، که سریعا در حال رشد و توسعهاند. این نوع شبکه دارای تجهیزات ساده بوده و نصب تجهیزات آن آسان است و قابل حمل میباشد. در شبکههای بیسیم نیازی به سیمکشیهای طویل و دراز نیست.
اگر سازمانی از یک شبکه بیسیم استفاده کند، کاربران قادر خواهند بود هر جا به صورت آنلاین با سایر کامپیوترها و چاپگرها ارتباط پیدا کنند. با استفاده از شبکههای بیسیم میتوان عملیات زیادی انجام داد که در شبکههای سیمی امکان آنها وجود ندارد، یعنی سایر تکنولوژیهای شبکه دارای انعطاف و قابلیت شبکه بیسیم نیستند. به همین دلیل
استفادهکنندگان از شبکههای بیسیم روز به روز افزایش مییابند. اگر شخصی متصل به شبکههای بیسیم باشد، محدودیتی از نظر مکان ندارد، یعنی شخص میتواند در هتل، فرودگاه، مرکز همایش و حتی کافیشاپ و یا سایر محلها در صورت وجود پوشش، بدون هیچ محدودیتی با سرعت خیلی بالا به شبکه بیسیم متصل شده و قابلیت استفاده از آن را داشته باشد [31].
1-3-1- قابلیت شبکههای بیسیم
شبکههای بیسیم دارای قابلیتهای زیرند:
امکان ارتباطات موقت در شبکه.
پشتیبانی از شبکه موجود.
فراهم آوردن درجهای معین از قابلیت حمل49.
گسترش دادن شبکه فراتر از محدودیتهای کابلهای مسی یا حتی فیبر نوری [18].
1-3-2- کاربردهای شبکه بیسیم
بکار بردن مشکل کابلها در شبکه باعث میشود که شبکههای بیسیم بسیار مورد قبول واقع شوند. شبکههای بیسیم در موارد زیر بسیار مورد استفاده قرار میگیرند:
محیطهای شلوغ مانند راهروها و محیطهای پذیرش.
ساختمانها و محیطهای منفرد.
بخشهایی که گاهی محیط فیزیکی آنها تغییر میکند.
ساختارهایی مانند ساختمانهای تاریخی که سیم کشی در آنها مشکل میباشد و … [18].
1-3-3- شبکههای بیسیم محلی 50( WLAN)
یک شبکه بیسیم معمولی به جز در رسانگر مانند شبکههای سیمی عمل میکنند. در این نوع شبکهها به یک نقطه دسترسی51 (AP) و یک کارت شبکه WLAN نیاز خواهد بود [18].
نقطه دسترسی
نقطه دسترسی دستگاهی برای برقراری ارتباط بین دستگاههای بیسیم و سیمی به یکدیگر است
که کار انتشار و دریافت سیگنالها را از کامپیوترهای اطراف برعهده دارد.
استفاده از نقاط دسترسی روش بسیار مفیدی جهت توسعه شبکههای بیسیم میباشد. در این حالت امکان اتصال به شبکههای سیمی یا اشتراک گذاری مودم پهن باند نیز وجود دارد.
در کل دو نوع نقطه دسترسی وجود دارد:
نقاط دسترسیهایی که به عنوان یک پل بین شبکه بیسیم و شبکههای سیمی بکار میرود.
نقاط دسترسیهایی که در آنها مسیریاب نیز تعبیه شده است و این مسیریاب باعث
میشود که تمام کامپیوترهای موجود در شبکه به صورت اشتراکی به اینترنت دسترسی داشته باشند [18].

کارت شبکه
هر یک از دستگاههای موجود در یک شبکه بیسیم به یک کارت شبکه بیسیم نیاز خواهند داشت.
1-3-4- تکنیکهای انتقال
شبکههای بیسیم محلی از چهار تکنیک به منظور انتقال دادهها استفاده میکنند:
مادون قرمز52
لیزر53
امواج رادیویی پهن باند54
امواج Spread-spectrum 55 ( تقسیم دادههای مورد نظر به بخشهای کوچکتر جهت ارسال با استفاده از فرکانسهای گسسته و قابل دستیابی در هر زمان) [18].
1-4- شبکههای ad-hoc سیار56(MANET)
یک شبکه ad-hoc سیار که گاهی اوقات شبکه مش سیار نامیده میشود، خود یک شبکه متشکل از لوازم سیار (متحرک) است که توسط خطوط بیسیم با هم مرتبط هستند. هر وسیله در یک MANET آزاد است که به صورت مستقل و در هر جهتی حرکت کند و از این رو گاهی خطوط ارتباطی خود را با سایر وسیلهها تغییر دهد. بنابراین ساختار شبکه به صورت تصادفی و بسیار سریع در زمانهای غیرقابل پیشبینی تغییر میکند. از آنجایی که هر گره دارای برد انتقالی محدودی است تمام پیامها نمیتوانند به تمام گرههای مورد نظر برسند. برای حفظ ارتباط در کل شبکه در یک مسیر از مبدا به مقصد مسیر از چندین گره همسایه میانی میگذرد. هر یک از وسیلهها باید جریان را بدون درنظر گرفتن استفاده خود بفرستد و از این رو یک مسیریاب هستند. اولین ادعا در ساخت یک MANET مجهز کردن هر وسیله به نگهداری پیوسته اطلاعات مورد نیاز برای راه عبور مناسب است. چنین شبکههایی میتوانند خودشان به تنهایی کار کنند یا ممکن است به شبکه بزرگتری منتقل شوند.
هدف MANET ها این است که سیار بودن را در حیطه خود گسترش دهند. کاربرد وسیع از تکنولوژی MANET در محیطهایی است که تغییر ساختار به صورت پویا مورد نیاز است و شبکه بیسیم در دسترس نیست. به عنوان مثال در میدانهای جنگ، جستجوهای اضطراری، موقعیتهای امداد و نجات و ….
افزایش لپ تاپها و شبکههای بیسیم Wi-Fi باعث شده است که MANET از سالهای 1990 تا 1995 به موضوع پژوهشی مورد پسندی تبدیل شود[10].
فصل دوم

کدگذاری شبکه
مقدمه
هدف شبکههای ارتباطی انتقال اطلاعات بین گرههای مبدا و مقصد است. اولین سوالی که در طرحریزی شبکه پیش میآید این است که چگونه میتوان اطلاعات انتقال یافته در شبکه را افزایش داد. اخیرا نشان داده شده است که توانایی شبکه در انتقال اطلاعات میتواند به صورت چشمگیری بهبود یابد، این کار با استفاده از کدگذاری شبکه صورت میگیرد. کدگذاری شبکه حیطه پژوهشی جدیدی است که کاربردهای بسیار جالبی در سیستمهای شبکه کاربردی دارد. با استفاده از کدگذاری شبکه، گرههای میانی به جای ارسال ساده اطلاعات، جریانی از اطلاعات را ارسال مینماید که ممکن است پیچیدهتر از اطلاعات دریافتی پیشین باشد، به عنوان مثال گرههای میانی میتوانند ترکیبات خطی از اطلاعاتی را که پیش از این دریافت کردهاند، ارسال کنند. این شیوه ارسال اطلاعات کلید افزایش بازده بالقوه و قوای با درجه بالاتر میباشد که در اینجا قوا به معنای کاهش برگشت بستهها و آسانکردن پیادهسازی الگوریتمهای توزیع است [11،4].
در بخش 1 این فصل به بررسی عمل ساده XOR میپردازیم و در بخش 2 کدگذاری شبکه را مورد مطالعه قرار میدهیم سپس در بخش 3 پهنای باند و در بخشهای 4 و5 و6 به ترتیب توزیعهای تکی57، همگانی58 و چندگانه59 را بررسی میکنیم و در ادامه در بخش 7 توزیع قابل اعتماد را مورد بحث قرار میدهیم.
2-1- عملXOR
عمل منطقی ترکیب مجزا60 (ناسازگار) که گاهی یای ناسازگار61 نیز نامیده میشود و با نمادهای ⨁,Eor,E Xor,XOR) یا ⋁) نمایش داده میشود، یک ترکیب فصلی روی دو عملوند است که نتیجه آن تنها هنگامی درست است که دقیقا یکی از عملوندها درست باشند ( این یا دیگری ولی نه هر دو).
جدول زیر ترکیب دو عملوند A وB را تحت عملXOR نشان میدهد.
جدول 2-1- ترکیب دو عملوند A وB تحت عمل XOR
INPUTOUTPUTABA XOR B 000011101110

A⨁B A⨁B⨁C
یک سیستم با استفاده از یای مجزا یا (⋁ و{F وT} ) یک گروه آبلی است. ترکیب
عملگرهای Λ و⋁ روی مولفههای {F وT} میدان F_2 را تولید میکند. اگر سه داده ورودی داشته باشیم، نتیجه هنگامی درست است که دقیقا یکی ازاین دادهها درست باشد. اگر تعداد زیادی داده ورودی داشته باشیم، نتیجه هنگامی درست است که تعداد فرد از دادهها درست باشد.
A⨁B=(A⋀!B)⋁(!A⋀B)=(A⋁B)⋀(!A∨!B)

2-2- کدگذاری شبکه62
امروزه شبکههای ارتباطی در اساس عمل مشترک هستند، خواه بستهها در اینترنت یا سیگنالها در شبکههای تلفنی باشند، اطلاعات مانند عبور اتومبیلها در بزرگراه یا انتقال جریان در لولهها انتقال مییابند. یعنی جریان دادههای مستقل ممکن است در منابع اشتراک داشته باشند، اما اطلاعات خودشان مجزا باشد. مسیریابی، ذخیره سازی دادهها و به طور کلی تمام اعمال شبکه بر فرض ارسال ساده اطلاعات استوار است. کدگذاری شبکه حیطه جدیدی است که این فرض را میشکند و به جای ارسال ساده اطلاعات، گرهها میتوانند چند بسته ورودی را با هم ترکیب کنند و به صورت یک یا چند بسته خروجی درآورند. مثالی ساده در زمینه
شبکههای بیسیم ساختاری با سه گره است که در شکل 2-1 نشان داده شده است.کدگذاری خطی شبکه در حالت کلی مشابه این مثال است با این تفاوت که در آن عمل XOR جای خود را به ترکیبات خطی میدهد.
Traditional Method
A □(→┴a ) S B
A S □(←┴b ) B
A □(←┴a ) S □(→┴a ) B
A □(←┴b ) S □(→┴b ) BNetwork coding
A □(→┴a ) S B
A S □(←┴b ) B
A □(←┴(a xor b) ) S □(→┴(a xor b) ) B

شکل 2-1مثالی ساده از کدگذاری شبکه.
گره های A و B میخواهند بستهها را از طریق گره میانی S رد و بدل کنند. گره A بسته a و گره B بسته b را میفرستد و در ادامه a xor b به جای a و b توزیع میگردد و A وB میتوانند بستههای مورد نظر خود را احیا کنند و در این حالت تعداد انتقالات کاهش مییابد.
کدگذاری شبکه در حیطههایی که تنها اطلاعات جزیی و یا غیر قطعی برای تصمیم گیری در دسترس است، بسیار مناسب میباشد. دریافت موفقیتآمیز اطلاعات، به دریافت حجم مشخصی از بستهها وابسته نیست بلکه به دریافت تعداد کافی از بستههای مستقل وابسته است[4].
2-2-1- کدگذاری خطی شبکه 63
سیستمی را در نظر بگیرید که مانند یک مسیریاب یا یک گره در یک شبکه توزیع نظیر به نظیر به ارسال اطلاعات میپردازد. در روشهای سنتی هنگامی که بستههای اطلاعاتی به تعدادی از گرهها میرسیدند، آن گرهها نیز به آسانی همین کار را تکرار میکردند. با استفاده از کدگذاری شبکه، به گره این اجازه را میدهیم که تعدادی از بستههایی که دریافت کرده است را با هم ترکیب کند و به یک یا چند بسته خروجی تبدیل نماید. فرض کنید که هر بسته شامل L بیت باشد. هنگامی که بستههایی که میخواهند با هم ترکیب شوند دارای اندازه یکسان نباشند، بستههایی با اندازه کمتر با دنبالهای از صفرها افزوده میشوند. میتوانیم S بیت متوالی از یک بسته را به صورت نمادی روی میدان F_(2^s ) معرفی کنیم و هر بسته شامل یک بردار با L/S مولفه میباشد. با استفاده ازکدگذاری خطی شبکه، بستههای خارج شده ترکیب خطی از بستههای اصلی هستند، جاییکه جمع و ضرب روی میدان F_(2^s ) انجام میشود. دلیل انتخاب چارچوب خطی این است که الگوریتمها برای کدگذاری64 و از کد خارج کردن65 بسیار قابل فهم هستند.
ترکیبات خطی سلسلهوار نیستند، اگر ما بستههایی به طول L را با هم ترکیب کنیم، بسته کدگذاری بدست آمده دارای طول L است. یک بسته کدگذاری شده عموما شامل اطلاعاتی در مورد چندین بسته اصلی است[4].
2-2-2- کدگذاری
فرض کنید که تعدادی بسته اصلیM^1,…,M^n ، توسط یک یا چند منبع تولید شدهاند. در کدگذاری خطی شبکه هر بسته در شبکه به دنبالهای از ضرایب g_1,…,g_n درF_(2^s ) مرتبط است و X=∑_(i=1)^n▒〖g_i M^i 〗 ، این مجموع برای هر مولفه استفاده میشود، یعنی X_k=∑_(i=1)^n▒〖g_i M_k^i 〗 جاییکه M_k^i وX_k به ترتیب k امین مولفه X,M^i هستند. به منظور ساده سازی فرض میکنیم که هر بسته شامل ضرایب g=(g_1,…,g_n) که بردار کدگذاری نامیده میشود و داده کدگذاری شده X=∑_(i=1)^n▒〖g_i M^i 〗 که بردار اطلاعات نامیده میشود، است. بردارهای کدگذاری به منظور از کد خارج کردن دادهها توسط گیرندهها استفاده میشود. به عنوان مثال، بردار کدگذاری e_i=(0,…,0,1,0,…,0)، جاییکه 1 مولفه i ام است، به این معناست که بردار اطلاعات برابر M^i است. کدگذاری میتواند به صورت بازگشتی انجام گیرد. گرهای را در نظر بگیرید که مجموعه (g^1,X^1 ),…,(g^m,X^m) از بستههای کدگذاری شده را دریافت و ذخیره کرده است. جاییکه g^j بردار کدگذاری jامین بسته و X^j بردار اطلاعاتj امین بسته است. این گره میتواند بسته کدگذاری شده جدید (g ́,X ́) را با انتخاب یک مجموعه از ضرایب h_1,…,h_m را تولید و ترکیب خطی X ́=∑_(j=1)^m▒〖h_j X^j 〗 را محاسبه نماید[4].
2-2-3- از کد درآوردن
فرض کنید که یک گره مجموعه (g^1,X^1 ),…,(g^m,X^m) را دریافت کرده است. به منظور بازیابی بستههای اصلی لازم است که دستگاه {X^j=∑_(i=1)^n▒〖g_i^j M^i}〗 را حل کنیم. (جاییکه M^i ها مجهول هستند.) این دستگاه خطی دارای m معادله و n مجهول است. به منظور داشتن شانس احیای تمام دادهها باید داشته باشیم m≥n ، یعنی تعداد بستههای دریافت شده باید حداقل به بزرگی اندازه بستههای اصلی باشد. برعکس شرط m≥n شرط کافی نیست، چون برخی از ترکیبها باید مستقل خطی باشند[4].
2-2-4- چگونه ترکیبات خطی را انتخاب کنیم؟
مساله کدگذاری شبکه این است که هر گره شبکه چه ترکیب خطی را انجام دهد. یک الگوریتم ساده این است که هر گره در شبکه به طور یکنواخت و به صورت تصادفی ضرایب را روی میدان F_(2^s ) به روشی کاملا مستقل و غیر متمرکز، انتخاب کند. با کدگذاری تصادفی شبکه، احتمالات قطعی از انتخاب ترکیبات مستقل خطی موجود است. این احتمالات به اندازه میدان F_(2^s ) مربوط است. نتایج شبیه سازی شده حاکی از آن است که برای میدانهایی با اندازه کوچک (مثلا S=8 ) احتمالات ناچیز و اندک است. الگوریتمهایی نیز موجودند که میتوان با استفاده از آنها کدهای شبکه را طراحی کرد. این الگوریتمها مشخص میکنند که هر گره در شبکه چه ترکیبات خطی را روی بستهها پیاده کند و از آنجایی که هر گره از ضرایب خطی ثابتی استفاده میکند، لازم است که بستهها تنها بردار اطلاعات را با خود حمل کنند [4].
2-2-5- ملاحظات عملی
در این بخش ابتدا به مبحث از کد خارج کردن اشاره میکنیم. از کد درآوردن نیازمند حل یک مجموعه از معادلات خطی است که در عمل به صورت زیر انجام میشود.
یک گره بردارهای کدگذاری را که دریافت کرده است، همانند بستههای اصلی خودش، سطر به سطر در ماتریسی که به آن ماتریس از کد درآوردن گویند، ذخیره میکند، که در ابتدا تنها شامل بستههای غیر کدگذاری شده است که توسط این گره به همراه بردارهای کدگذاری مورد نظر منتشر میشود. هنگامی که یک بسته کدگذاری شده دریافت میشود به عنوان سطر آخر وارد ماتریس از کد خارج کردن میشود. ماتریس ضرایب با استفاده از روش حذفی گاوس به یک ماتریس مثلثی تبدیل میگردد. بسته دریافت شده را تغییریافته نامند اگر رتبه ماتریس را افزایش دهد. اگر یک بسته تغییریافته نباشد به سطری از صفرها توسط روش حذفی گاوس کاهش مییابد. به محض اینکه ماتریس شامل یک سطر به شکل (e_i,X) باشد، گره میداند که بسته اصلی M^i برابر X است. این حالت هنگامی رخ میدهد که n بردار کدگذاری مستقل خطی دریافت شود. توجه کنید که لازم نیست از کد خارج کردن برای تمام گرهها انجام شود، تنها گرههای گیرنده این عمل را انجام میدهند[4].
دورهها66
برای تمام اهداف عملی باید اندازه ماتریسها برای کدگذاری شبکه محدود باشد. این مساله برای کدگذاری جبری شبکهها مستقیما بدست میآید. اما در صورت کدگذاری تصادفی
شبکهها این امر بسیار مشکل میباشد. در مورد آخر معمولا بستهها به دورههایی گروهبندی میشوند و تنها بستههایی که در یک دوره یکسان قرار دارند میتوانند با هم ترکیب شوند. اندازه و ترکیب دورهها میتواند تاثیر مهمی روی اجرای کدگذاری شبکه داشته باشد. ملاحضاتی مشابه نیز برای اندازه میدان متناهی برقرار است. هر دو پارامتر باعث کاهش حافظه مورد نیاز و پیچیدگیهای مثلثاتی میشود [4].
تاخیر
تاخیر یک مشخصه اجرایی مهم در شبکههای کامپیوتری است. تاخیر در یک شبکه عبارت است از مدت زمانی که به طول میانجامد تا یک بیت از دادهها در شبکه از یک گره به گره دیگر برود که معمولا به صورت مضربی از ثانیهها یا کسری از ثانیه اندازهگیری میشود. کاربران تنها به تاخیر کلی شبکه توجه میکنند، اما مهندسان میانگین تاخیر و ماکزیمم تاخیر را مورد توجه قرار میدهند و تاخیر را به قسمتهای مختلفی تقسیمبندی میکنند که عبارتند از:
تاخیر پردازش: زمانی که به طول میانجامد تا مسیریاب بستهها را پردازش کند.
تاخیر به صف کردن: زمانی که به صف کردن دادهها اختصاص مییابد.
تاخیر انتقال: زمانی که به طول میانجامد تا بیتهای بستهها در خط ارتباطی قرار گیرند.
تاخیر انتشار: زمان مورد نیاز برای رسیدن یک سیگنال به مقصد.
بستههایی که نیاز به از کد درآوردن دارند تاثیرات اندکی در تاخیر دارند. معمولا لازم نیست که تمام بستههای کدگذاری شده قبل از اینکه تعدادی از بستهها بتوانند از کد خارج شوند، دریافت شوند. (یعنی هرگاه قاعده حذفی گاوس منجر به ایجاد یک سطر به شکل (e_i,M_i) شود.) در مجموع با کاهش انتقالات مورد نیاز، تاخیرات کلی در شبکههای کدگذاری شده بزرگتر از تاخیرات در شبکههای عادی نیست [4].
2-2-6- مزایای کدگذاری شبکه چیست؟
بازده مورد نظر در محیط استاتیک
اولین نتایجی که در کدگذاری شبکه درخشید این است که کدگذاری شبکه قادر است ظرفیت شبکه را برای جریان در توزیع با چند گیرنده افزایش دهد. شبکهای را در نظر بگیرید که به صورت یک گراف جهتدار نشان داده میشود ( عموما این شبکه سیمی است). رئوس گراف نظیر ترمینالها و یالهای گراف نظیر کانالها هستند. فرض کنید Mمنبع داشته باشیم که هر یک اطلاعات را به نسبت مشخص ارسال میکنند و N گیرنده داریم. تمام گیرندهها تمایل دارند که تمام منابع را دریافت کنند.
قضیه 1. اگر نسبتهای منبع به گونهای باشد که بدون کدگذاری شبکه، شبکه بتواند هر گیرنده را به تنهایی حمایت کند. (یعنی هر گیرنده میتواند تمام منابع را هنگامی که تنها یک گیرنده در شبکه موجود باشد، از کد خارج کند.) در این صورت با انتخاب مناسب از ضرایب کدگذاری خطی شبکه قادر است تمام گیرندهها را همزمان حمایت کند [4].
به عبارت دیگر هنگامی که N گیرنده در منابع شبکه مشترک هستند هر یک از آنها میتواند ماکزیمم نسبتی را که امید به دریافت آن داشته است دریافت کند. حتی اگر تمام منابع شبکه را خودش استفاده کند. از این رو کدگذاری شبکه میتواند به اشتراک بهتر منابع شبکه در دسترس کمک کند.
قدرتمندی و انطباقپذیری
مهمترین مزیت کدگذاری شبکه، قدرتمندی و انطباقپذیری آن است. به صورت شهودی فکر میکنیم که کدکذاری شبکه مشابه کدگذاری سنتی، بستههای اطلاعات را دریافت میکند و بستههای کدگذاری شده را تولید مینماید، جاییکه هر بسته کدگذاری شده به یک میزان اهمیت دارند، مشروط به اینکه تعداد کافی از بستههای کدگذاری شده را دریافت کرده باشیم (مهم نیست کدام بسته دریافت شده باشد) میتوانیم آنها را از کد درآوریم. شکل جدیدی که کدگذاری شبکه فراهم میآورد این است که ترکیبات خطی به صورتی مصلحت اندیشانه و نه تنها روی گره منبع انجام میشوند، بنابراین کدگذاری شبکه در مواردی که گرهها تنها اطلاعات ناکافی در مورد موقعیت کلی شبکه دارند بسیار مناسب میباشد.
مجددا مثال شکل 2-1 را در نظر بگیرید و فرض کنید که A و B به صورت تصادفی و بدون توجه به موقعیت S فعال نباشند (یا ممکن است از محدوده خارج شده باشند)، اگرS ، a یا b را توزیع کند، از آنجایی که گیرنده مورد نظر ممکن است قادر به دریافت بستهها نباشد، انتقالات کاملا بیفایده خواهد بود. در حالی که اگرS ، a xor b یا به صورت کلیتر ترکیب خطی تصادفی از بستههای اطلاعات را توزیع کند، انتقال میتواند اطلاعاتی جدید را به گرههای فعال منتقل کند[4].
2-2-7- مثال
در این قسمت شبکه پروانهای67 را مورد بررسی قرار میدهیم. در شبکه پروانهای ( شکل 2-2 ) دو منبع داریم (در بالای تصویر) که یکی دارای داده A و دیگری دارای داده B است. دو گره مقصد نیز موجود است (در پایین تصویر) که هر یک مایلند A و B را دریافت کنند. هر یال تنها قادر به انتقال یک مقدار است. اگر از روشهای عادی برای انتقال دادهها استفاده کنیم یال مرکزی تنها قادر به انتقال A یا B است و نمیتواند هر دو را انتقال دهد. حال فرض کنید A را از طریق یال مرکزی عبور دهیم. مقصد سمت چپ A را دو بار دریافت میکند در حالی که B را اصلا دریافت نمیکند. مسالهای مشابه در حالتی که تنها B را از یال مرکزی عبور دهیم نیز رخ میدهد. حال با استفاده از یک کد ساده میتوانیم A وB را همزمان به هر دو مقصد ارسال کنیم. با فرستادن داده A+B از یال مرکزی مقصد سمت چپ با دریافت A و A+B قادر است B را نیز تولید کند و مقصد سمت راست با دریافت B و A+B ، A را تولید میکند. این کدگذاری یک کدگذاری خطی است، زیرا اعمال کدگذاری و از کد خارج کردن هر دو خطی میباشند.
شکل 2-2- شبکه پروانهای
2-2-8- موارد استفاده از کدگذاری شبکه.
در زیر تعدادی از کاربردهای کدگذاری شبکه را مورد بررسی قرار میدهیم.
توزیع فایل P2P68
احتمالا شناخته شدهترین استفاده از کدگذاری شبکهها درAvalanche است.Avalanche به توزیعی در شبکه نظیر به نظیر گفته میشود که توسط پابلو رودریگز69 و کریستس گانتسیدیس70 در مایکروسافت71 طراحی شد که در آن پهنای باند نسبت به سیستم نظیر به نظیر معمولی بهبود یافته است. Avalanche برای توزیعهای با حجم زیاد در شبکههای نظیر به نظیر استفاده میشود و در آن کدگذاری شبکه به کار گرفته میشود. در اینگونه شبکه توزیع P2P سرویس دهنده، یک فایل بزرگ را به تعدادی بلوک میشکند. گرههای همتراز سعی میکنند که فایل اصلی را با دانلود بلوکها از سرویس دهنده بازیابی کنند و بلوکهای دانلود شده را بین خودشان توزیع کنند. بدین منظور گرههای همتراز ارتباط خود را با تعداد محدودی از گرههای همتراز همسایه خود حفظ میکنند که این گرههای همسایه به صورت تصادفی از بین مجموعه گرههای همتراز انتخاب میشوند. در Avalanche بلوکهایی که توسط سرویس دهنده فرستاده میشوند به صورت ترکیب خطی تصادفی از بلوکهای اصلی هستند. به صورت مشابه گرههای همتراز، ترکیبات خطی تصادفی از تمام بلوکهایی که در دسترس دارند را ارسال میکنند. یک گره میتواند تعیین کند که چه تعداد بلوک تغییریافته را میتواند به یکی از همسایگانش ارسال کند. این کار با مقایسه ماتریس ضرایب از کد درآوردن خود و همسایهاش انجام میگردد، یا اینکه به آسانی بلوکهای کد شده را ارسال میکند تا هنگامی که همسایهاش اولین بلوک تغییرنیافته را دریافت کند، سپس گره انتقالاتش



قیمت: تومان

دسته بندی : مقاله و پایان نامه

دیدگاهتان را بنویسید