دانشکده علوم
پايان نامهي کارشناسي ارشد در رشتهي رياضي کاربردي- تحقيق در عمليات
توزيع قابل اعتماد کد محور در شبکههاي بيسيم
به وسيلهي
راضيه دلپسند
استاد راهنما
دکتر محمد باقر احمدي
دي ماه 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 ? که بردار اطلاعات ناميده ميشود، است. بردارهاي کدگذاري به منظور از کد خارج کردن دادهها توسط گيرندهها استفاده ميشود. به



قیمت: تومان


پاسخ دهید