بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
مسيريابي در شبکه هاي کامپيوتري بر مبناي الگوريتم هاي کلوني(Antnet)
چکيده
تنوع زيادي در پروتکل ها و الگوريتم هاي مسيريابي براي ارتباطات شبکه اي وجود دارد. در مسيريابي سنتي جـداول مسـيريابي بـه واسـطه تبادل اطلاعات مسيريابي بين مسيريابها به روز مي شوند. امروزه با تقليد از رفتار اکتشافي کلوني مورچه ها الگوريتم هايي ارائه مي شوند کـه از عامل هاي موبايل در مسيريابي شبکه ها استفاده مي کنند. هوش جمعي به عنوان اساس اين سري جديد از الگـوريتم هاسـت کـه از رفتـار اجتماعي حشراتي که بصورت جمعي زندگي مي کنند الهام گرفته اند. اين الگوريتم هاي مسيريابي بر اساس مفاهيم سيسـتم هـاي چندعاملـه پيشنهاد شده اند و بصورت قدم به قدم و بر اساس خاصيت Stigmergic در کلوني مورچه ها انجام مي شوند. يکـي از ايـن الگـوريتم هـا، الگوريتم Antnet است که در مقايسه با روشهاي قبلي داراي کارايي بهتري در واکنش نسبت به تغييرات شبکه مي باشد.
کليد واژه
الگوريتم مسيريابي شبکه ، الگوريتم کلوني مورچه ها، الگوريتم AntNet ، فرمون
١. مقدمه
منظور از مسيريابي در شبکه انتقال داده ها و اطلاعات از مبدا به مقصد مي باشد. اين امر تاثير بسيار زيادي در کارايي شبکه از جمله ايجاد تاخير کمتر و گذردهي بالا دارد. اکثر الگوريتم هاي مسيريابي فعلي بر اساس يافتن کوتاهترين مسير بنا شده اند که براي رسيدن به همگرايي نياز به جابه جايي جداول مسيريابي دارند. از جمله الگوريتم هاي بردار فاصله مانند RIP و هم چنين الگوريتم هاي حالت پيوند مانند OSPF اخيرا با الهام از مسيريابي مورچه ها ، الگوريتم هايي ارائه شده که از عامل هاي موبايل براي مسيريابي شبکه هاي ارتباطي استفاده مي شود. از بين اين الگوريتم ها، الگوريتم Antnet داراي عملکرد بهتري است و تحقيقات جديد زيادي روي آن در حال انجام است . اين الگوريتم نسبت به الگوريتم هاي قديمي نيز کارايي بهتري دارد و نسبت به تغييرات شبکه سريعتر و کاراتر پاسخ ميدهد. مورچه ها در طبيعت اين توانايي را دارند که به کمک مواد شيميايي که از خود در محيط به جا مي گذارند کوتاه ترين مسير بين منبع غذايي و لانه خود را بيابند.
در الگوريتم Antnet دو نوع عامل به نام مورچه پيشرو و مرچه پسرو وجود دارد. در بازه هاي زماني مشخص هر گره مورچه ي پيشرويي به سمت مقصدي مشخص روانه مي کند. ولي بر خلاف الگوريتم هاي ديگر در اين ضمينه اين مورچه فقط وظيفه دارد به سمت مقصد موردنظر پيش رفته و اطلاعاتي در مورد مسير به دست آورد. مورچه پيشرو به مقصد که مي رسد مورچه پسرو را ايجاد مي کند و پس از انتقال اطلاعات خود
به او از بين مي رود. مورچه ي پسرو از همان مسيري که مورچه پيشرو طي کرده است به عقب بر مي گردد و به هر گره که ميرسد جدول مسيريابي آنرا تغيير مي دهد. به عبارت ديگر مورچه ي پسرو با اطلاع در مورد کل مسير جدولنودها را به روز رساني مي کند، بنابراين تغييرات مناسب تري روي جداول اعمال مي کند. چندسويه بودن مجموعه الگوريتم هاي مورچگان سبب استفاده ي بسيار گسترده از اين مجموعه الگوريتم ها براي حل مسائل بهينه يابي ترکيبي متنوع شده است . در حالت کلي الگوريتم هاي مورچگان توانايي بسيار زيادي براي حل مسائل بر مبناي گراف دارند.
مسيريابي يکي از اجزاي حياتي سيستم کنترل شبکه هاي ارتباطي است که شامل فرآيند يافتن مناسب ترين مسير بين هر دو نقطه مفروض شبکه مي باشد. مسيريابي در شبکه ها از طريق جداول مسيريابي انجام مي شود. جداول مسيريابي براي هر گره اطلاعاتي در شبکه تهيه مي شود و براي هدايت ورودي هاي به گره جهت رسيدن به مقصد با استفاده از مسيرهاي مناسب استفاده قرار مي گيرد. به طور کلي هدف از طرح مسائل مسيريابي در شبکه هاي ارتباطي، يافتن جداول مسيريابي و استفاده از آن ها براي انتقال داده ها بين گره ها از طريق ارتباطات موجود مي باشد؛ به طوري که برخي از معيارهاي عمل کرد شبکه حالت بهينه به خود بگيرد. انتخاب معيارهاي ارزيابي عمل کرد شبکه به نوع شبکه و کاربري آن بستگي دارد. عمدتاً در شبکه هاي ارتباطي نظير اينترنت ، شبکه هاي محلي و شبکه هاي گسترده از دومعيار ظرفيت و ميانگين تأخيرات براي ارزيابي عملکرد شبکه استفاده مي شود که اولي براي ارزيابي کمي سرويس دهي شبکه و دومي براي ارزيابي کيفي سرويس دهي شبکه مورداستفاده قرار مي گيرند. براي حل مسئله ي مسيريابي در شبکه هاي ارتباطي الگوريتم هاي بهينه ي زيادي نظير OSPF ،SPF و BF ارائه شده است ؛ ولي اکثر اين الگوريتم ها در شبکه هاي خيلي بزرگ نظير اينترنت کارايي خود را از دست مي دهند.
لذا تنها راه حل ممکن براي حل مسائل مسيريابي با ابعاد بزرگ ، الگوريتم هاي فراابتکاري مي باشند. ماهيت غيرمتمرکز و ناپايدار ساختار و الگوي ترافيک مسئله مسيريابي در شبکه هاي ارتباطي هم خواني زيادي با ايده ي اصلي الگوريتم هاي مورچگان - مسيريابي مورچه ها- دارد، به همين خاطر الگوريتم هاي مورچگان از کارآيي زيادي براي حل مسئله ي مسيريابي در شبکه هاي ارتباطي برخوردار بوده و در واقع جزو کارآمدترين الگوريتم هاي موجود براي حل مسئله مي باشند.[٢٢]
٢.الگوريتم Antnet
کليات الگوريتم گراف مورچگان يا الگوريتم AntNet مشابه ساير الگوريتم هاي مورچه مي باشد. در اين الگوريتم با حرکت مورچه ها بر روي گراف مسئله جواب هاي موجه ايجاد شده و مورچه ها با استفاده از فرمون ، اطلاعات و تجربه ي جستجوي خود را به يکديگر منتقل مي نمايند. دو تفاوت اصلي اين الگوريتم با ساير الگوريتم هاي مورچه به صورت زير است :[٦,٢٢]
• در اکثر الگوريتم هاي قبلي، ارزيابي جواب هاي بدست آمده با مقايسه ي جواب هاي مشابه مورچه هاي مختلف انجام مي شود؛ در حالي که در اين الگوريتم ارزيابي جواب ها به تنهايي و بدون مقايسه با جواب هاي مشابه آن مرحله انجام مي شود. به علاوه در اين الگوريتم شرايط متغير ترافيکي شبکه نيز در ارزيابي جواب ها بايستي لحاظ شود. چه بسا مسيري در يک شرايط ترافيکي براي رفتن از يک نقطه به نقطه ي ديگر مسير خوبي ارزيابي شود؛ در حالي که در يک شرايط ترافيکي ديگر مسير مناسبي ارزيابي نشود.
• وظايف و ويژگي هاي مورچه ها در الگوريتم AntNet بصورت زير مي باشد:
• از هر گره شبکه در بازه هاي زماني مشخصي مورچه اي به سمت مقصدي که بصورت تصادفي انتخاب شده است ، ارسال مي شود. علت انتخاب مقاصد مورچه ها شبيه سازي رفتار تصادفي بار شبکه مي باشد.
• مورچه ها کاملاً مستقل از هم بوده و بصورت همزمان بر روي گراف مسئله حرکت نموده ، از اطلاعات درج شده بر روي يال ها توسط مورچه هاي قبلي استفاده نموده و در نهايت تجربيات جستجوهاي خود را بر روي يال هاي گراف مي نويسند.
• هر مورچه داراي عمر محدودي مي باشد که بايستي در اين مدت زمان به مقصد برسد. چنان چه در اين مدت زمان نتواند به مقصد برسد از بين مي رود.
• مورچه ها همواره به دنبال بهترين مسير (با حداقل هزينه ) از مبدأ به مقصد هستند.
• هر مورچه حرکت خود را از مبدأ شروع نموده و مرحله به مرحله به طرف مقصد نهايي خود حرکت مي نمايند و در هريک از گره هاي مياني از يک رويه احتمالي کوته بين براي انتقال به گره بعدي استفاده مي نمايند. اين رويه احتمالي تابعي از اطلاعات مورچه هاي قبلي، اطلاعات خاص مسئله واطلاعات ذخيره شده در حافظه ي مورچه در آن تکرار مي باشد.
• مورچه ها در حين حرکت بر روي گراف مسئله اطلاعاتي راجع به گره هايي که از آن ها رد شده اند و زمان هاي حرکت بين گره ها را ثبت مي نمايند.
• به محض رسيدن مورچه به مقصد، هر مورچه مسير طي شده از مبدأ تا مقصد را در جهت عکس طي مي کند.
• مورچه ها در حين حرکت برگشت ، مدل بيان کننده ي وضعيت شبکه و جداول مسيريابي گره هايي که در حين حرکت رفت از آن ها عبور کرده اند را به روز مي نمايند.
• مورچه ها به محض رسيدن به مبدأ اصلي بلافاصله از بين مي روند.
براي راحتي کار در الگوريتم AntNet دو نوع مورچه ي رفت ومورچه ي برگشت تعريف شده است . هر دو نوع مورچه ساختار يکساني دارند؛ ولي وظايف متفاوتي انجام مي دهند. اين دو نوع مورچه ورودي هاي اطلاعاتي متفاوتي داشته و بالطبع خروجي هاي متفاوت و مستقلي نيز خواهند داشت .
١.٢. ساختار داده ها در هر گره از شبکه
مورچه ها در هر گره از گره هاي شبکه دو نوع ساختار اطلاعاتي متفاوت ذخيره نموده و از آن ها استفاده مـي نماينـد. ايـن دو نـوع سـاختار اطلاعاتي در شکل ١ آمده است . در اين شکل تعداد کل گره هاي شبکه N و تعداد گره هاي همسايه ي گره فعلي L فرض شده است . اين دو ساختار عبارتند از:[٦,١٩]
١- جدول مسيريابي Rk: ساختار اين جدول مشابه جداول مسيريابي مورد استفاده توسط ساير الگوريتم هاي مسيريابي است ؛ با ايـن تفـاوت که داده هاي اين جدول احتمالي مي باشند. جدول مسيريابي گره ، مورچه هاي (بسته هاي) ورودي به آن گـره را بـراي انتخـاب گـره بعـدي راهنمايي مي نمايند تا مورچه ها بتوانند با توجه به شرايط ترافيکي شبکه مسيري مناسب را براي رسيدن به مقصد انتخاب نمايند. عناصر ايـن جدول مطلوبيت هريک از گره هاي همسايه را در رسيدن به مقصدي خاص نشان مي دهند که مطلوبيت هريک از گره هـا در قالـب احتمـال انتخاب آن ها نمايان مي شود. در واقع درايه ي Pnd از جدول مسيريابي گره k ام احتمال انتخـاب شـدن گـره n در همسـايگي k را توسـط مورچه اي که مبدأ آن k و مقصد آن d است را نشان مي دهد. بديهي است که :
٢- آرايـــه ايـــن آرايـــه ، يـــک مـــدل تصـــادفي پـــارامتري از وضـــعيت ترافيکـــي شـــبکه از ديـــدگاه گره ي k ام مي باشد. اين مدل يک مدل آماري احتمال بوده که مي توان داده هاي آن را با تغيير شرايط ترافيکي شبکه به روز نمود.
در ايـــن مـــدل بـــه ترتيـــب ميـــانگين و واريـــانس زمـــان هـــاي حرکـــت از مبـــدأ گـــره k ام بـــه گـــره d ام مي باشند. در واقع براي هر گره مفروض d از شبکه ، طول مدت زمان مورد انتظار حرکت بين گره k ام و گره d ام بـوده و ميـزان تغييرپذيري اين زمان را نشان مي دهد. متغير wd نيز بهترين زمان هاي حرکـت مورچـه هـا از گـره k ام بـه گـره d ام ، wbestd را در w مشاهده ي آخر ذخيره کرده و در واقع کران پاييني براي زمان حرکت تا گره d در w مشاهده ي آخر مي باشد. نحوه ي به روز نمودن مقادير به صورت زير است :
که در رابطه بالا زمان حرکت مورچه ي فعلي از گره ي k به مقصد d بوده و پارامتر تعداد آخرين زمان هاي سفر مؤثر در محاسبه ي جديد را مشخص مي کند. مقدار وزن i امين زمان سفر مشاهده شده بعد از مشـاهده ي j زمـان سـفر براسـاس مـدل نمـايي مساوي با است . به عنوان مثال اگر تقريباً ٥٠ زمان سفر آخر مشاهده شده تأثير معني داري در محاسبه ي مقـادير جديد خواهند داشت . اين رقم براي مساوي با ١٠٠ خواهد بود. به طور کلي تعداد مشـاهدات مـوثر در محاسـبه ي مقادير جديد بر اساس مقدار n تقريباً مساوي با است .
شکل ١- ساختار نودهاي شبکه در الگوريتم [٦]Antnet
مقادير Rk و Mk نوعي حافظه براي نگهداري اطلاعات مربوط به شرايط شبکه مي باشند. مقدار Rk مطلوبيت نسبي گره هاي همسايه ي k را براي رسيدن به هريک از گره هاي ديگر شبکه در قالب اعداد تصادفي نشان مي دهد؛ در حالي که Mk بيان گر اطلاعاتي راجع به فاصله (زمان ) حرکت بين گره k تا ساير گره هاي شبکه مي باشد.
٢.٢.مراحل مختلف الگوريتم [٦٨]Antnet
با تعريف ساختار اطلاعاتي گره هاي شبکه ، مي توان مراحل مختلف الگوريتم AntNet را بصورت زير بيان نمود:
١. در بازه هاي زماني Δt از هر گره s شبکه ، يک مورچه ي Forward (که با نماد نشان داده مي شود) به سوي مقصدي که بصورت احتمالي انتخاب شده است ، ارسال مي شود. هدف تک تک مورچه ها يافتن مسيرهاي موجه با کم ترين هزينه و نيز جمع آوري اطلاعاتي راجع به وضعيت ترافيکي شبکه مي باشد. در شبکه با مورچه هاي Forward نظير بسته هاي داده در شبکه هاي ارتباطي برخورد مي شود. بدين صورت که اين مورچه ها در صورت نياز در صف عبور از گره ها قرار گرفته و مانند داده
