پایان نامه تأمين کيفيت سرويس در شبکه های متحرك موردي با استفاده از پروتكل مسيريابي OLSR
فهرست محتوا
چكيده
يكي از مسائل مطرح در زمينه شبكههاي موردي متحرك، تامين كيفيت سرويس در اين شبكهها است. درجهت تامين كيفيت سرويس در اين شبكهها، فعاليتهاي زيادي انجام شده است. ازجمله اين فعاليتها، تامين كيفيت سرويس توسط پروتكلهاي مسيريابي است. يكي از اين پروتكلهاي مسيريابي، OLSR است.اين پروتكل، يك پروتكل مسيريابي كنش گرا است. علاوه بر آن اين پروتكل براساس مكانيزمهاي وضعيت پيوند عمل ميكند.
پروتكل OLSR، پروتكلهاي متداول وضعيت پيوند را از نظر حجم اطلاعات ردوبدل شده و همچنين سربار مسيريابي بهبود ميبخشد. در پروتكلهاي وضعيت پيوند، وضعيت كليه پيوندها در شبكه پخش مي شود. در OLSR، به جاي همه پيوندها تنها بخشي از آنها كه شامل پيوندهاي بين گرههاي MPR و انتخاب كنندههاي آنها ميشود، به شبكه معرفي شده و مسيريابي تنها از طريق همين گرههاي MPR انجام ميشود.
براي تامين كيفيت سرويس، توسعهاي بر اين پروتكل به نام QOLSR ارائه شده است. در اين توسعه، از معيارهاي كيفيت سرويس مانند تاخير و پهناي باند در انتخاب MPR و محاسبه جداول مسيريابي گرهها استفاده ميشود.
در اين پايان نامه، پس از پيادهسازي QOLSR دو الگوريتم جديد براي مكانيزم انتخاب MPR در QOLSR ارائه شده است. اين دو الگوريتم، براساس روشهاي تخمين تحرك گرهها عمل ميكنند و باعث ميشوند كه مسيريابي از طريق پيوندهاي پايدارتر انجام شود. نتايج شبيه سازی و ارزيابی نشان می دهد که اين الگوريتمها به علت پايداري بيشتر پيوندها، نرخ گم شدن بستههاي شبكه و همچنين تاخير بستههاي دريافتي را كاهش ميدهند.
كلمات كليدي
پروتكل مسيريابي OLSR، كيفيت سرويس، پهناي باند، تخمين تحرك، مكانيزم انتخاب MPR
فهرست مطالب
فصل اول: مقدمه 1
فصل دوم: مروري بر شبكههاي موردي 5
- توپولوژي شبكههاي موردي 5
- مسائل مطرح در شبكههاي موردي 6 2-2-1 مسيريابي 6
2-2-2 مديريت تحرك 7
2-2-3 لايه انتقال 8
2-2-4 واسط راديويي 8
2-2-5 امنيت 9
2-2-6 مديريت توان 9
- پروتكلهاي مسيريابي در شبكههاي موردي 9
2-3-1 مسيريابي در شبكههاي مسطح 11
2-3-1-1 پروتكلهاي كنش گرا 12
2-3-1-2 پروتكلهاي واكنشي 13
2-3-1-3 مقايسه پروتكلهاي مسيريابي مسطح 15
2-3-2 مسيريابي سلسله مراتبي 17
2-3-3 مسيريابي با استفاده از اطلاعات جغرافيايي 20
فصل سوم: تامين کيفيت سرويس در شبكههاي موردي متحرك 23
- مدل كيفيت سرويس در شبكههاي موردي متحرك 25
3-1-1 سرويس مجتمع ( int serv ) 25
3-1-2 سرويس متمايز ( diff serv ) 27
3-1-3 مدل FQMM 29
3-1-3-1 معماري فضاي كاري FQMM 31
3-1-4 مدل كيفيت سرويس cross layer 34
3-1-4-1 فاز ايجاد مسير 36
3-1-4-2 فاز انتخاب مسير 38
3-1-4-3 پريود پايداري مسير 40
3-1-4-4 تمايز سرويس در گرهها 40
3-2 مسيريابي كيفيت سرويس در شبكههاي موردي متحرك 42
3-2-1 مسيريابي كيفيت سرويس به صورت كنش گرا 45
3-2-2 مسيريابي كيفيت سرويس به صورت واكنشي 46
3-2-2-1 مسيريابي AQOR 46
3-2-2-2 مسيريابي كيفيت سرويس واكنشي به صورت انطباق پذير 50
3-2-2-3 مسيريابي كيفيت سرويس واكنشي به صورت چند مسيره 53
3-2-2-4 مسيريابي QoS براساس تخمين پهناي باند در شبكههاي موردي 54
3-3 يك فضاي كاري مناسب براي رزرو منابع و سيگنالينگ در شبكههاي موردي متحرك 57
3-3-1 بازيابي 60
3-4 تضمين كيفيت سرويس براي ترافيك بلادرنگ در شبكههاي موردي متحرك 61
فصل چهارم: پروتكل مسيريابي OLSR و تامين كيفيت سرويس 64
4-1 پروتكل مسيريابي OLSR 64
4-1-1 گرههاي MPR 65
4-1-2 پيغامهاي hello 66
4-1-3 پيغامهاي TC 66
4-2 تامين QoS 67
4-2-1 معيار تاخير 67
4-2-2 كنترل پذيرش 68
4-2-3 تامين كيفيت سرويس با ارائه روشهاي جديد براي انتخاب MPR 69
فصل پنجم: توسعه بر پروتكل مسيريابي OLSR درجهت تامين QOLSR: QoS 73
5-1 عملكرد QOLSR 73
5-2 مكانيزم انتخاب مجموعه MPR هاي يك گره 74
5-3 معيارهاي كيفيت سرويس 75
5-3-1 معيار تاخير 75
5-3-2 معيار پهناي باند 75
5-4 محاسبه جدول مسيريابي گرهها در QOLSR 76
5-5 پيادهسازي QOLSR 77
فصل ششم: روشهاي پيشنهادي براي بهبود الگوريتم انتخاب MPR در QOLSR با استفاده از تخمين تحرك گرهها 79
6-1 پايداري مسير و تخمين تحرك گرهها 79
6-2 الگوريتمهاي پيشنهادي و پيادهسازي آنها 82
6-2-1 الگوريتمهاي پيشنهادي 82
6-2-1-1 الگوريتم اول (QMPR1) 83
6-2-1-2 الگوريتم دوم (QMPR2) 85
6-2-2 پيادهسازي الگوريتمهاي پيشنهادي 88
فصل هفتم: ارزيابي راه حلهاي ارائه شده 98
7-1 زمان ارسال متوسط بستهها 99
7-2 نرخ گم شدن بستهها 100
7-3 سربار كنترلي 103
فصل هشتم : نتيجه گيري و پيشنهاد كارهاي آينده 105
فهرست منابع و مراجع 107
فصل اول: مقدمه
امروزه، شبکههاي موردي[1] نقش مهمي در ارتباطات بيسيم بازي ميکنند. در شبکههاي موردي، گرههاي بيسيم با وجود فقدان يک محيط کاري ثابت با هم ارتباط دارند. اين شبکهها معمولا شامل گرههاي برابري هستند که از طريق پيوندهاي بيسيم بدون کنترل مرکزي با هم ارتباط دارند. ارتباط بين ميزبانها[2] در شبکههاي موردي مستقيم نيست و به صورت چندگامه[3] ميباشد. بنابراين هر ميزبان، مسيرياب[4] نيز هست. چون مصرف توان[5] به صورت مستقيم با فاصله بين ميزبانها متناسب است، ارسال يكگامه[6] بين دو ميزبان نيازمند توان به قدر کافي است که در شبکههاي موردي ممکن نيست. پس ارسال به صورت چندگامه ميباشد.
اين شبکهها مشکلات شبکههاي سلولي و موبايل مانند بهينهسازي پهناي باند، کنترل توان و بهبود کيفيت انتقال را دارا هستند. علاوه بر آن خاصيت چندگامه بودن اين شبکهها و همچنين فقدان فضاي کاري ثابت در آنها، مشکلات جديدي مانند پيکربندي شبکه، نگهداري اطلاعات توپولوژي و … را براي آنها به وجود آورده است.
به عنوان نمونه، شبکههاي حسگر[7]، شبکههاي موردي هيبريد ناميده ميشوند و براي مانيتور کردن مراکز و جمع آوري اطلاعات مانند دما، حرکت و غيره استفاده ميشوند. در سالهاي اخير تحقيقات بسياري درزمينه اين شبكهها درحال انجام است.
راه حلها و پروتکلهاي مختلفي براي برطرف کردن مشکلات شبکههاي موردي ارائه شده است و چندين استاندارد توسط IETF براي اين شبکهها در راه است.
با افزايش نيازهاي کيفيت سرويس در کاربردها، لازم است که کيفيت سرويس در شبکههاي MANET[8] هم پشتيباني شود] 1[ . شبکههاي بيسيم ميتوانند کاربردهاي چندرسانهاي[9] مانند صوت و ويدئو را منتقل نمايند. در نتيجه، براي انتقال کاربردهاي فوق با کيفيت مناسب لازم است که QoS[10] در شبکههاي موردي حداقل از لحاظ پهناي باند و تاخير تامين گردد. اما تامين QoS در اين شبکهها کار بسيار دشواري است، زيرا علاوه بر برآورده کردن نيازهاي QoS در اين شبکهها با وجود کمبود منابع، بايد توپولوژي پويا و رسانه[11] مشترک بيسيم را هم در نظر گرفت.
پروتكلOLSR[12]، يك پروتكل مسيريابي كنشگرا[13] براي شبكههاي متحرك موردي است. اين پروتكل همچنين يك پروتكل وضعيت پيوند[14] بهبود يافته نيز ميباشد. در اين پروتكل، به جاي اينكه وضعيت همه پيوندها در كل شبكه پخش شود، تنها وضعيت پيوند بين گرههاي خاصي به نام گرههاي MPR[15] و گرههاي انتخاب كننده آنها در شبكه پخش ميشود. يكي از مهمترين مكانيزمهاي اين پروتكل، مكانيزم انتخاب گرههاي MPR است.
در استاندارد OLSR، مكانيزم انتخاب گرههاي MPR به گونهاي است كه براي هر گره شبكه از بين همسايگان با يك گام فاصله[16] آن ، مجموعه MPR ها به گونهاي انتخاب ميشوند كه همه همسايگان با دو گام فاصله آن گره پوشش داده شوند و درعين حال تعداد گرهها در اين مجموعه كمترين مقدار ممكن باشد. پس از اين انتخاب، گرههاي MPR به طور متناوب پيغامهاي كنترلي خاصي به نام پيغامهاي TC[17] را در شبكه پخش ميكنند. در اين پيغامها، اطلاعات وضعيت پيوندهاي بين گرههاي MPR و گرههاي انتخاب كننده آنها قرار دارد. گرههاي دريافت كننده اين پيغامها جداول توپولوژي و مسيريابي خود را به روز ميكنند. درواقع، همه مسيرها در شبكه تنها از طريق همين پيوندهاي معرفي شده شكل ميگيرند، پس كيفيت سرويس اين پيوندها، بسيار مهم است. اگر از مكانيزم اوليه پروتكل OLSR براي انتخاب MPR ها استفاده شود، به دليل عدم در نظر گرفتن معيارهاي كيفيت سرويس در انتخاب گرههاي MPR و به دنبال آن مسيرهاي انتخابي، اين مسيرها كيفيت سرويس را به طور مناسب پشتيباني نميكنند.
يكي از مهمترين راه حلهاي ارائه شده جهت بهبود تامين كيفيت سرويس در پروتكل OLSR توسعهاي بر اين پروتكل به نام QOLSR[18] است. در اين توسعه، از معيارهاي كيفيت سرويس در انتخاب گرههاي MPR و همچنين در محاسبه جداول مسيريابي گرهها، استفاده ميشود. در اين پروتكل، نرخ تحرك گرهها در انتخاب MPR ها هيچ تاثيري ندارد.
اگر بتوان علاوه بر معيارهاي پهناي باند آزاد و ميزان تاخير پيوندها، معيارهاي ديگري نظير پايداري گرهها و تخمين تحرك آنها را در انتخاب گرههاي MPR دخالت داد، شايد بتوان مسيرهايي با پايداري بيشتر انتخاب نمود كه اين موجب آن خواهد شد كه نرخ گم شدن بستهها و تاخير ارسال آنها را كاهش داد.
در اين پايان نامه، ما به دنبال ارائه يك روش مسيريابي مبتني بر كيفيت سرويس هستيم. به دليل ويژگيهاي مناسب پروتكل QOLSR، اين پروتكل به عنوان مبناي اصلي كار در نظر گرفته شده است. با توجه به مطالب فوق، ما به دنبال راه حلهايي جهت افزودن معيارهاي ذكر شده به روش انتخاب گرههاي MPR هستيم.
اين پايان نامه به اين شكل سازماندهي شده است: بررسي اجمالي شبكههاي موردي در فصل دوم آمده است. فصل سوم به تامين كيفيت سرويس در شبكههاي موردي متحرك اختصاص دارد. در فصل چهارم، پروتكل مسيريابي OLSR و تامين QoS در آن را بررسي ميكنيم. فصل پنجم به شرح پروتكل QOLSR ميپردازد. فصل ششم به راه حلهاي پيشنهادي براي بهبود تامين كيفيت سرويس در پروتكل QOLSR اختصاص داده شده است. در فصل هفتم ارزيابي راه حلهاي پيشنهادي آمده است و نهايتا نتيجهگيري و پيشنهاد كارهاي آينده در فصل هشتم قرار دارد.
فصل دوم: مروري بر شبكههاي موردي
ايده شبكههاي موردي به زمانهاي بسيار دور برميگردد. اين شبكهها محصول پروژههاي تحقيقاتي است كه در اوايل دهه 70 ميلادي در زمينه تخصيص منابع راديويي و شبكههايي با ساختارهاي متفاوت انجام گرفت] 1[. به اين شبكهها در آن زمان شبكههاي packet radio اطلاق ميشد. در اين شبكهها هر گره به صورت مستقل از ديگران عمل ميكرد و بيشترين كاربرد آنها مربوط به كاربردهاي نظامي و ايجاد ارتباط نفر به نفر در شرايط جنگي بود.
با پيشرفت تكنولوژي، انواع جديدي از اين نوع شبكهها طراحي شد كه در آنها گرهها، حسگرهايي با ابعاد ميليمتري بودند. همزمان با آن، زمينههاي كاربردي جديدي براي اين نوع شبكهها در نظر گرفته شد. از اين شبكهها ميتوان در بلاياي طبيعي وآتش سوزي، شبكههاي اتومبيلي مانند اورژانس و همچنين ارتباطات بيسيم در محيطهاي جدا از هم استفاده نمود.
- توپولوژي شبكههاي موردي
در شبكههاي موردي، ميزبانها ميتوانند با يكديگر بدون نياز به زيرساخت مركزي ارتباط برقرار كنند. اين شبكهها معمولا داراي گرههاي برابري هستند كه بدون نياز به كنترل مركزي از طريق ارتباطات بيسيم با هم ارتباط برقرار ميكنند.
براي نمونه، وسايط نقليه در بزرگراهها ميتوانند يك شبكه موردي جهت انتشار اطلاعات ترافيكي تشكيل دهند. هر وسيله نقليه كه ترافيك را تشخيص ميدهد با پيغام آن را به ديگران اطلاع ميدهد. به جاي داشتن اين شبكه موردي، ميتوان از نقاط دسترسي اينترنت يا سلولي نزديك جاده جهت ارسال اطلاعات استفاده كرد.
ارتباطات بين دو ميزبان شبكههاي موردي هميشه به صورت مستقيم و تك گامه انجام نميشود. نوع ارتباط معمولا چندگامه است كه در آن هر ميزبان مسيرياب نيز ميباشد. ميزبانهاي شبكههاي موردي ميتوانند از پروتكلهاي استاندارد MAC[19] مانند IEEE 802.11 براي ارتباط از طريق يك فركانس استفاده كنند يا ميتوانند از Bluetooth و ديگر تكنولوژيهاي گام فركانسي[20] بهره بگيرند.
ارتباط چندگامه در اين شبكهها، به دليل رابطه مستقيم مصرف انرژي با فاصله بين دو ميزبان است. ارتباط مستقيم بين دو ميزبان نيازمند توان به حد كافي است كه علاوه بر اين كه توان مصرفي گرهها محدود است، اين امر ميتواند باعث ايجاد تداخل[21] با ارسال كنندههاي ديگر شبكه شود. به همين علت ميزبانهاي شبكه از پروتكلهاي چندگامه براي ارتباط با ميزبانهاي ديگر استفاده ميكنند.
- مسائل مطرح در شبكههاي موردي
2-2-1 مسيريابي
مسيريابي يك تابع اصلي و كليدي در هر شبكه اي است. طراحي پروتكلهاي مسيريابي براي شبكههاي موردي با دو معضل اساسي روبروست: اول اين كه راه حلهاي مسيريابي متداول ( براي مثال در اينترنت يا شبكههاي سلولي ) تغييرات در توپولوژي و دسترسي را سريعا در شبكه منتشر ميكنند. آنها با فرض پايدار بودن شبكه كار ميكنند. برخلاف اين شبكهها، در شبكههاي موردي توپولوژي مدام تعيير ميكند] 1[.
مساله دوم اين است كه راه حلهاي متداول مسيريابي براساس يك سري پايگاه داده توزيعي عمل ميكنند. اين پايگاه دادهها در هر گره شبكه يا گرههاي مديريتي خاصي نگهداري ميشوند. در شبكههاي موردي، گرهها نميتوانند پايگاه داده پايدار با اطلاعات به روز شده داشته باشند. همچنين در اين شبكهها گرهها هميشه قابل اعتماد نيستند. گروه كاري MANET در IETF راه حلهايي كه مشكل اول را برطرف ميكنند، ارائه كرده است. اين راه حلها بهينهسازيهايي از پروتكلهاي مسيريابي بردار فاصله[22]، وضعيت پيوند[23] و مسيريابي مبدا[24] هستند. براي حل مشكل دوم ميتوان از روشهاي جغرافيايي[25] استفاده كرد. در اين روشها، گرهها از موقعيت جغرافيايي خود و گرههاي ديگر مطلع ميشوند و مسيريابي براساس اين اطلاعات جغرافيايي در هر گره انجام ميشود. به اين ترتيب نيازي به پايگاه داده توزيعي در هر گره نميباشد] 1[.
2-2-2 مديريت تحرك[26]
يك شبكه بايد بتواند گرههاي خود را مديريت و درنتيجه اين گرهها را مكانيابي كند. در شبكههاي سلولي، موقعيت ايستگاههاي متحرك در يك سري سرويس دهندههاي مركزي نگهداري ميشوند. خودسازماندهي[27] شبكههاي موردي، امكان داشتن چنين سرويس دهندههايي را منتفي مينمايد. بنابراين اطلاعات موقعيت بايد بين خود گرهها توزيع شود. راهحلهايي براي تخمين موقعيت آينده يك گره براساس الگوي تحرك آن گره، ارائه شدهاست.
[1] Ad Hoc
[2] Hosts
[3] Multi-hop
[4] router
[5] power
[6] Single-hop
[7] Sensor
[8] Mobile Ad Hoc Network
[9] Multi-media applications
[10]Quality Of service
[11] medium
[12] Optimum Link State Routing
[13] proactive
[14] Link-State
[15] Multi-Point Relay
[16] One-hop neighbor
[17] Traffic Control
[18] QoS Optimum Link State Routing
[19] Medium Access Control
[20] Frequency-hopping
[21] interference
[22] Distance vector
[23] Link state
[24] Source routing
[25] Geographic methods
[26] Mobility management
[27] Self-organization
نقد و بررسیها
هنوز بررسیای ثبت نشده است.