امتیاز : 3

فهرست

چکیده 3

مقدمه 5

کارهاي گذشته 6

الگوریتم خوشه بندي 9

نگهداري خوشه 13

مسیریابی 15

1- محاسبه تاخیر 17

2- محاسبه پهناي باند 18

3- پهناي باند حقیقی موجود در مسیر 19

4- کشف مسیر 20

5- نگهداري مسیر 22

شبیه سازي 23

الگوريتم مسيريابي چندپخشي مبتني بركيفيت سرويس با استفاده ازكولوني مورچه ها 29

تئوري الگوريتم مورچه ها 29

روش پيشنهادي اول 31

روش پيشنهادي دوم 31

الگوریتم های مسیر یابی در شبکه های کامپیوتری 33

الگوريتم کوتاه‌ترين مسير 33

الگوريتم سيل‌آسا 33

الگوريتم بردار فاصله 34

الگوريتم حالت لينک 34

الگوریتمهای LS 36

الگوریتم Dijkstra 37

الگوريتمهاي DV 40

مسیریابی سلسله مراتبی 42

نتیجه گیري 43

مراجع 44

 

 

 

چکيده: 

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

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

همچنین دو الگور يتم توزيع شده همه منظوره بر اساس كولوني مورچه ها را پيشنهادخواهيم داد. اين دو الگوريتم به منظور حل هر چه موثرتر و كارآمدتر مسئله مسيريابي چندپخشي بر اساس تحقق چندين محدوديت كيفيت سرويس پيشنهاد مي شود. اساس الگو يتم هاي پيشنهادي برگرفته از قابليت و توانايي مورچه ها در پيدا كردن كوتاهترين مسير بين لانه و منبع غذا مي باشد. نتايج شبيه سازي انجام شد ه نشان مي دهد كه شيوه هاي پيشنهادي مي تواند بطور موثر و كارآمد مسيريابي چندپخشي مبتني بر كيفيت سرويس را به انجام رساند.

در الگوریتم های مسیر یابی غیر متمركز، هر روتر اطلاعاتی در مورد روترهایی كه مستقیما به آنها متصل میباشند در اختیار دارد. در این روش هر روتر در مورد همه روتر های موجود در شبكه،اطلاعات در اختیار ندارد.این الگوریتمها تحت نام الگوریتمهای (DV (distance vector معروف هستند.در الگوریتمهای مسیریابی عمومی،هر روتر اطلاعات كاملی در مورد همه روترهای دیگر شبكه و نیز وضعیت ترافیك شبكه در اختیار دارد.این الگوریتمها تحت نام الگوریتمهای(LS(Link state معروف هستند.ما در ادامه مقاله به بررسی الگوریتمهای LS میپردازیم

 

واژه هاي کليدي: 

شبکه ها موردي، مسيريابي کيفيت سرويس، مسيريابي چندپخشي، درخت اشتاينر، كيفيت سرويس، الگوريتم مورچه اي.

 

 

مقدمه

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

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

اين خصوصيات ذاتي شبکه هاي موردي باعث مي شود که بدست آوردن اطلاعات حالت پيوند از قبيل تاخير، پهناي باند و غيره دقيقا امکان پذير نباشد.

الگوريتم هاي مسيريابي متعددي براي شبکه هاي موردي معرفي شده است که آنها را مي توان در سه دسته فعال، غير فعال و ترکيبي تقسيم کرد.

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

در الگوريتمهاي فعال گره ها متناوبا اطلاعات مسيريابي خود را با يکديگر مبادله مي کنند و در نتيجه قبل از اينکه به مسيري نياز باشد، ايجاد مي شود. در الگوريتمهاي فعال سربار بروز رساني اطلاعات پيوندها بسيار بالا است ولي تاخير اوليه وجود ندارد . از ديگر مشکلات اين روشها عدم مقياس پذيري آنها مي باشد. 

در الگوريتمهاي ترکيبي از ترکيبي از دو روش فعال و غير فعال استفاده مي شود و از مزاياي هر دور روش فعال و غير فعال استفاده مي شود. يک زير دسته از الگوريتمهاي ترکيبي، الگوريتمهايي مي باشند که از خوشه بندي استفاده مي کنند. در روش خوشه بندي گرهها گروه بندي مي شوند و در هر گروه گرهي به عنوان سرگروه انتخاب مي شود. گره سرگروه مسئول انجام عمليات گروه خود مي باشد. اين الگوريتمها بسيار مقياس پذير و مناسب براي تضمين کيفيت سرويس مي باشند.

در اين مقاله الگوريتم مسيريابي مبتني بر کيفيت سرويس با استفاده از خوشه بندي ارائه شده است. ايجاد خوشه در روش پيشنهادي بسيار سريع است و خوشه هاي ايجاد شده بسيار پايدار مي باشند. الگوريتم پيشنهادي توسط شبيه سازي در شبيه ساز [NS2] با الگوريتم QOLSR مقايسه شده است. از نتايج شبيه سازي مي توان نتيجه گرفت که الگوريتم پيشنهادي نسبت به QOLSR تاخير انتها به انتهاي کمتر و نرخ تحويل بسته بالاتري دارد.

 

کارهاي گذشته

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

در گره ها بر اساس منابع موجودشان به سه دسته، گره ه اي کيفيت سرويس، گره هاي مسيرياب و گره هاي دريافت کننده تقسيم مي شوند. گره ها با ارسال متناوب پيام HELLO، مشخصات خود را براي همسايگانشان ارسال مي کنند. هر گره با دريافت پيام HELLO از گره هاي همسايه اش مي توانند دسته آنها را مشخص کند. در عمليات مسيريابي کيفيت سرويس فقط گره هاي کيفيت سرويس مي توانند شرکت کنند. براي مسير يابي از روش مسيريابي AODV استفاده شده است و در درخواست مسير پهناي باند درخواستي و تاخير بيان مي شود. در اين الگوريتم به دليل اينکه تنها نودهاي کيفيت سرويس مي توانند در مسيريابي شرکت کنند، سربار مسيريابي کم است.

در اين روش تداخل گره هاي همسايه و تاثير آن بر پهناي باند در نظر گرفته نشده است. علاوه بر آن پهناي باند ثابت در نظر گرفته شده است که اين امر بر خلاف خصوصيات ذاتي شبکه هاي موردي است.

الگوريتم  QOLSRيک الگوريتم مطرح مسيريابي مبتني بر یک الگوریتم مطرح مسیریابی مبتنی بر کیفیت سرویس است. این روش بر مبناي الگوریتم مسیریابی OSLR می باشد. در این روش هر گره مجموعه اي از همسایگانش را به عنوان مجموعه MPR انتخاب می کند. در هنگام پخش بسته هاي کنترلی یک گره، تنها گره هاي موجود در مجموعه MPR آن گره، بسته ها را بازپخش می کنند و در نتیجه از پخش تکراري پیام ها جلوگیري می شود. براي انتخاب مجموعه MPR هر گره، همسایگانی را انتخاب می کند که از طریق آنها بتواند با تمام همسایگانی که از گره دو پرش فاصله دارند، ارتباط برقرار کند. علاوه بر این خاصیت سعی می شود تا همسایگانی انتخاب شود که پارامترهاي کیفیت سرویس بهتري

داشته باشند (مانند پهناي باند بیشتر و تاخیر کمتر). روشهاي مختلفی براي انتخاب پارامترهاي کیفیت سرویس و انتخاب همسایگان بیان شده است.

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

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

 

 

الگوریتم خوشه بندي

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

هر گره می تواند چهار حالت NORMAL ، ISOLATED ، CLUSTEREAD و GATEWAY را داشته باشد.

قبل از عملیات خوشه بندي تمام گرهها در حالت ISOLATED هستند. هر گره متناوبا پیام LIVE را با همسایگانش ارسال می کند . 

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

LIVE (ID, IDch, W, STATE)

 

پارامتر ID آدرس هر گره می باشد . پارامترIDch  مشخص کننده ID سرگروهی است که گره عضو آن هست یا عضو آن بوده است. در ابتدا مقدار آن 1- است . مقدار W گروه وزنی گره را مشخص می کند. پارامتر STATE حالت گره را مشخص می کند.

گره ها براي مشخص کردن گروه وزنی خود ، ابتدا وزن خود را مشخص می کنند و سپس بر اساس وزن خود در یکی از سه گروه وزنی قرار می گیرد.

وزن هر گره از فرمول زیر محاسبه می شود :

Weight = aN + bR + cT + dP                                                                  (1)

 

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

 

  گزارش تخلف  |  افزودن به فایل های من | jikjik | تاریخ ارسال : 22 /04 /1394

شما هم می توانید در مورد این فایل نظر دهید.