مقاله الگوریتم مسیر یابی

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

  مقاله الگوریتم مسیر یابی دارای ۱۶ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله الگوریتم مسیر یابی  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله الگوریتم مسیر یابی،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از متن مقاله الگوریتم مسیر یابی :

الگوریتم مسیر یابی

(خلاصه)
این مقاله به توصیف الگوریتم مسیر یابی Q برای مسیر یابی packet در ماجول تقویت کننده آموزش دهنده که در هر گروه از یک شبکه جابجا کننده قرار داده شده است می پردازیم. تنها ارتباطهای محلی برای هر گیرنده بکار می رود تا آمار آنها را در مرحله تصمیم های جهتیابی دقیق نگاه دارد که منجر به کاهش زمان ارسال می گردد. در آزمایشهای ساده که حاوی ۳۶ گره است و شبکه بصورت بی قاعده ای متصل گردیده است. جهتیابی Q برتری حضور را نسبت به الگوریتم غیر قابل تطابق مبتنی بر محاسبات کوتاهترین مسیر ها به اثبات می رساند و قادر خواهد بود تا به میزان کافی جهتیابی انجام دهد حتی زمانی که ویژگیهای بسیار مهم شبیه سازی همانند load کردن شبکه اجازه می یابند تا بطور پویا تغییر پیدا کنند. این مقاله در برگیرنده بحثی در مورد حالت حد ووسط بین کشف میان برها و سیاستهای با ثبات نگه داشتن می باشد.

معرفی INTROSUCTION
حیطه تقویت دانش بنحو چشمگیری در طی چند سال اخیر رشد کردهاست البته به استثناء ماتریس [۸,۲] که کاربردهای موفقیت آمیزی کمتری در مقایسه با کارهای عملی و بزرگ دشته است. این مقابله نشان می دهد که کار عملی جهتیابی Pachat ها درون یک ارتباط شیبکه ای یک کاربرد طبیعی برای الگوریتم تقویت کننده دانش می باشد.
الگوریتم جهتیابی Q تا، متناسب با برخی الگوریتمهای جهتیابی packet توزیع شده [۶,۷] یاد می دهد که سیاست جهتیابی که در آن توزان ها تعداد پرشهای یک pachet را به حداقل می رسانند با احتمال انسداد مسیرهای شلوغ بدست خواهد آمد. این امر به کمک آزمایش روشهای جهتیابی گوناگونم و جمع آوری آمار درباره تصمیمهایی که زمان ارسال را به حداقل می رساند میسر خواهد شد. یادگیری مستمر و پیوسته خواهد بود، تنها از اطلاعات محلی استفاده می کند و بصورت بی قاعده بسیار قوی و یکپارچه عمل می کند و الگوهای ارتباط شبکه دائما در حال تغییر load شدن است.

آزمایشات در این مقاله به کمک شبیه ساز گسسته رویداد صورت گرفته است تا حول انتقال packet ها را در درون یک شبکه محلی بدست دهد و در بخش [۵] توضیح کامل در این مورد داده شده است.
جهتیابی برای تقویت عملکرد یادگیری Routiny As A Reinforcement l earniy task
سیاست جهتیابی یک packet پاسخگویی این پرسش می باشد که : به کدام گروه مجاور می بایستی گره فعلی packet های خود را ارسال کند در مقایسه با مقصد نهایی اش آزاد دریافت دارد؟ از آنجائیکه عملکرد این روش به کمک کل زمان بدست آمده جهت ارسال یک packet اندازه گیری می شود، هیچ سیگنال آموزش دهنده ای برای برآورد کردن مستیم یا بهبود دادن سیاست تا زمانیکه یک packet نهایتا به مقصد خود می رسد وجود ندارد. با اینهمه، با استفاده از تقویت یادگیری،روش می بایستی سریعتر بروز شود و تنها از اطلاعات محلی استفاده کرد. فرض کنید Q(x)(d,y) زمانی باشد که یک گروه x تخمین زده می شود که یک packet را به گره d به کمک گروه همسایه x یعنی y تحویل دهد، که در برگیرنده هر زمانی است که p می بایستی در صفx صرف کند. در زمان ارسال p به y، x فورا برآورده y را برای زمان باقیمانده جهت ارسال بر می گرداند در نتیجه:

اگر packet مقدار q واحد زمان در صف x صرف کند و s واحد زمانی در انتقال بین گروه های y,x در نتجه x می تواند برآورده خود را طبق رابطه زیر بازبینی کند:

جایئکه پارامتر نرخ یادگیری است (معمولا در آزمایشس ما Q.5 در نظر گرفته می شود.)
اگلوریتم منبع می تواند در حکم نسخه ای از الگوریتم کوتاهترین مسیر Bellman – Ford در نر گرفته شود که (۱) نمایش دهنده گامهای مسیر آن بصورت غیر همزمان و online می باشد و (۲) طول مسیر را صرفا به کمک تعداد پرسشها بلکه به کمک زمان ارسال کل اندازه گیری می کند.
ما الگوریتم خود را مسیر یابی Q نامگذاری می کنیم تابع Q را((Qx(d,y) به کمک یک جدول بزرگ ارائه می کنیم. ما همچنین بصورت تقریبی Qx را با یک شبکه خنثی مشخص کنیم که به دانش آموز اجاز می دهد تا انواع مختلفی از پارامتر های سیستم شامل اندازه صف محلی و زمان روز به تخمین مسافت آن تبدیل و یکی کند. با اینهمه نتیجه های این آزمایشات نا تمام ماند.

نتایج (Results)
ما الگوریتم مسیر یابی Q را بر روی انواع توپولوژیهای شبکه شامل مکعب ۷ وجهی، شبکه تلفن ۱۱۶ گره ای LATA و جدول ۶*۶ بی قاعده آزمایش کرده ایم. از آنجائیکه بار شبکه متفاوت است، میزان متوسط زمان ارسال packet ها را در یک سیستم پس از فراگیری که بر مبنای مسیر یابی و روش آن بوده است اندازه گیری نمودم. و این زمان ها را با آنهائیکه طرح مسیر یابی ثابت بر مبنای کوتاهترین مسیر مقایسه کردیم. نتایج بدین صورت بود که در تمامی موارد، مسیر یابی Q قادر خواهد بود تا سطح بالاتری از بار شبکه را نسبت به حاتی که می توانست مسیر کوتاهتر را بپیماید بحالت تعلیق درآمده این بخش نتایج کامل بر شبکه چهار گوش تصویر شده در شکل ۱ را ارائه کند. تحت شرایط بار کم شبکه، نسبتا سریع تشخیص می دهد که packet ها را در طول کوتاهتری مسیرها به سوی مقصد شان مسیر یابی کند. منحنی عملکرد در برابر زمان که در سمت چپ شکل ۲ نمایش داده شده است این موضوع را عنوان می کند که الگوریتم مسیر یابی Q،

پس از دوره ابتدایی بی کفایتی زمانی که در حال شناخت توپولوژی شبکه است. همانند مسیریاب کوتاهترین مسیر عمل می کند که تحت بار کم بهترین انتخاب خواهد بود. زمانیکه بار شبکه افزایش می یابد، طرح کلی مسیر یابی کوتاهترین مسیر بای بهترین انتخاب بودن متوقف می شود: این روش سطوح در حال افزایش ترافیک را در نظر نمی گیرد و بزودی شبکه را با packet ها لبریز می کند. در سمت راست شکل ۲ نمایش دهنده جدول عملکرد بر زمان برای دو سطح مسیر یابی در شرایط بار سنگین شبکه می باشد. زمانیکه کوتاهترین مسیر قادر به تحمل کردن بار packet نیست مسیر یابی Q یک روش کار آمد مسیر یابی را فرا می گیرد. دلیل آموختن موفقیت الگوریتم در دیاگرام های خلاصه روش شکل ۳ آشکار می گردد این دیاگرامهای برای هر یک از روشهای ارائه شده نشان می دهد چه مقدار از مسیر نقطه به نقطه ۳۵*۳۶ از هر گره عبور می کند . در سمت چپ شکل ۳، که سیاست کوتاهترین مسیر را خلاصه می کند، در گره در مرکز شبکه (که ۵۷۰ و ۵۷۳ نامگذاری شده اند) در بسیاری از کوتاهترین مسیر ها قرار دارند و از اینرو زمانیکه بار شبکه زیاد است مسدود شده اند. بر خلاف اینحالت دیاگرام سمت راست مسیر یابی Q را نشان می دهد که در شرایط بار زیاد شبکه روشی را بزگریده است که طی آن در مسیری طولانی تر از مسیر مورد نیاز و با وجود ترافیک (در قسمت بالای شبکه) مسیر یابی

را انجام می دهد بگونه ای که از انسداد در مرکز شبکه پرهیز شود. نتیجه اولیه در شکل ۴ بدست می آید، که عملکرد های روش کوتاهترین مسیر را با روش آموخته شده مسیر یابی Q در مقیاسهای مختلف بار شبکه را با یکدیگر مقایسه می کند. هر نقطه نشاندهنده میانه حد وسط زمان ارسال هر packet پس از اینکه مسیر شناخته شده باشد، زمانیکه بار شبکه کم باشد الگوریتم مسیر یابی Q تقریبا هماند الگوریتم کوتاهترین مسیر عمل می کند. ولی در زمان بار زیاد روش کوتاهترین مسیر منجر به تعداد زیادی از انسداد های شبکه ای می گردد در حالیکه الگوریتم یادگیری به مسیر یابی خود با موفقیت ادامه می دهد
(شبکه های دائما در حال تغییر)Dynamically changing Netwosks
ایکی از مزایای الگوریتم یادگیری نسبت به مسیریابی استاتیک، پتانسیل بکارگیری جهت تغییرات در پارامترهای بسیار حیاتی سیستم در زمان کار شبکه است ما الگوریتم مسیر یابی را آزمایش کردیم، همچنین در شبکه هایی که توپولوژی، الگوهای ترافیک و میزان بار بصورت دینامیک تغییر می کردند:
توپولوژی
بصورت دستی ارتباطات را از شبکه در زمان شبیه سازی قطع کردیم. به لحاظ کیفی، مسیر یابی Q بسرعت به چنین تغییراتی واکنش نشان داد و قادر به مسیر یابی ترافیک بخوبی بود.
الگوهای ترافیک:
ما شبیه سازی را جهت به حالت نوسان در آوردن و بین دو حالت مختلف الگوهای درخواست در شبکه بی قاعده بطور دوره ای ایجاد کردیم: اولی در تمامی ترافی بین نیمه بالایی و پائینی شبکه هدایت شده بود و دومی در تمام زمان ترافیک بین نیمه راست و چپ حرکت کرده بود. دوباره، پس از تنها یک دوره کوتاه نه چندان کار آمد مسیر یابی هر زمان که الگوی تقاضا جابجا می شد، الگوریتم مسیر یابی Q با موفقیت بکار بسته می شد
سطح بار
زمان که تمام سطح ترافیک در زمان شبیه سازی زیاد می شد، مسیر یابی Q بسرعت سیاست را پذیرفته تا مسیر یابی packet در تنگنای جدید انجام دهد. با اینهمه زمانیکه ترافیک شبکه دوباره پائین آورده شد، بکارگیری کندتر صورت گرفت وهرگز در کوتاهترین مسیر بهینه متمرکز نمی شود. این اثر در بخش بعد مورد بحث قرار می گیرد
اکتشاف) Exploration
با تشابه به بدست آمده بین بروز کردن معادله مسیبر یابی Q و بازگشت کوتاهترین مسیر Bellman- Ford، شگفت آور این است که هیج تفاوتی بین عملکرد و مسیریابی Q و کوتاهترین مسیر که در بار کم مسیر یابی می کند وجود ندارد که اینحالت در شکل شماره ۴ قابل مشاهده است.

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

۱- شبکه دائما در حال تغییرات، از اینرو دوره اولیه اکتشاف هرگز به پایان نمی رسد و بطور قابل توجهی
۲- ترافیک تصادفی اثر فوق العاده منفی برانسداد شبکه دارد. Packet ارسال شده در مسیر و نمی بهینه تمایل دارند تا از تاخیرها صفی ایجاد نمایند که packet هایی که از این صفها می گذرند سرعتشان کاسته شده که موجب افزوده شدن تاخیر در صفها می گردد بدلیل اینکه که گره ها تصمیمات خود را بر اساس اطلاعات صرفا محلی می گیرد، این انسداد افزایش یافته عینا مسائلی را که فراگیران سعی در حل آنها دارند تغییر می دهند.

به جای ارسال نمونه packet ها در یک مسیر تصادفی، گره ای که از تغییر الگوی کامل مسیر یابی Q بهره می برد درخواست اطلاعات خود را به گره های مجاور در هر زمانی که نیاز به تصمیم گیری داشته باشد می فرستند. هر گره مجاور یک عدد ارسال می کند که از کانالی مجزا طوری استفاده می کند که انسداد را در مدل ما گسترش ندهد بدین گونه که گره جاری برآوری از کل زمان رسیدن به مقصد انجام می دهد. این برآوردها جهت تنظیم مقادیر (Qx (d,y) برای هر y مجاور صورت می گیرد. زمانیکه میان برها ظاهر می گردند. و یا اگر عدم کفایت در سایستها موجود باشد این اطلاعات سرعت در شبکه پخش می شود و روش مورد نظر بصور مناسب آنرا تنظیم می کند.