برچسب مسیر - نیک فایل

پروژه یافت کوتاهترین مسیر در شبکه های کامپیوتری مبتنی برپردازش تکاملی. doc

اختصاصی از نیک فایل پروژه یافت کوتاهترین مسیر در شبکه های کامپیوتری مبتنی برپردازش تکاملی. doc دانلود با لینک مستقیم و پر سرعت .

پروژه یافت کوتاهترین مسیر در شبکه های کامپیوتری مبتنی برپردازش تکاملی. doc

نوع فایل: word

قابل ویرایش 67 صفحه

چکیده:

هدف از انجام این پروژه آن است که در لایه ی شبکه سیستم های کامپیوتری با استفادهازالگوریتم های ژنتیک بتوان یک مسیر را از یک نقطه به نقطه ی دیگر انتخاب کرد تا زمان و ترافیک شبکه حداقل شود .روی شبکه ای که از هزاران هزار کامپیوتر تشکیل یاقته است ارسال و دریافت اطلاعات بین دو کامپیوتر می تواند از مسیرهای مختلف و متفاوتی صورت گیرد.این مسیرها دارای طول و میزان ترافیک های متفاوتی خواهند بود.اما ما با بهره گیری از الگوریتم های ژنتیک به دنبال روش هستیم که مسیر بهینه را از لحاظ طول و ترافیک به دست آوریم.به طوریکه زمان ارسال ودریافت اطلاعات کاهش یابد.در انجام این پروژه با تحقیق روی الگوریتم های ژنتیک روشی را برای مسیریابی بر مبنای آن به دست می آوریم که نتیجتاً مسیری بهینه و موفق خواهد بود هر چند که در همسایگی پاسخ بهینه نیز باشد.

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

مقدمه:

در شبکه های کامپیوتری لایه ی شبکه بسته ها را از مبدا به مقصد می رساند برای رسیدن به مقصد باید در بین راه از چندین منبع بگذرد. کار لایه ی شبکه با لایه ی پیوند داده ها متفاوت است. لایه ی شبکه پایین ترین لایه ای است که با انتقال انتها به انتها سروکار دارد این لایه برای رسیدن به اهدافش باید توپولوژی زیر شبکه ی ارتباطات را بداند و مسیرهای مناسبی را انتخاب نماید.نباید مسیرهایی انتخاب کند که بعضی از خطوط ارتباطی و مسیریابها بار اضافی را تحمل کند و بعضی دیگر بی کار باشند. زمانی که منبع و مقصد در دو شبکه مختلف باشد لایه ی شبکه باید از عهده ی اختلافهای بین آنها برآید و مشکلات ناشی از آنها را حل کند.اکنون به چگونگی عملکرد لایه ی شبکه می پردازیم.دو مسئله ی مختلف برای سازماندهی زیر شبکه وجود دارد.یکی از آنها از اتصالها استفاده می کند و دیگری بی اتصال کار می کند.در زمینه ی عملکرد داخلی زیر شبکه اتصال را مدار مجازی می نامند.بسته های مستقل سازمان بی اتصال،داده گرام نامیده می شود.هدف مدارهای مجازی پرهیز از انتخاب مسیر جدید برای هر بسته یا سلول است.هربسته که از زیر شبکه عبور میکند به مسیریاب میرسد،مسیریاب میداند که از کدام خط رسیده و شماره ی مدار مجازی را نیز میداند و بر مبنای این اطلاعات بسته باید به خط خروجی صحیحی انتقال داده شود. وقتی اتصال شبکه برقرار شد شماره ی مدار مجازی که اکنون در آن ماشین در حال استفاده نیست،به عنوان شناسه ی اتصال انتخاب می شود و این شماره ها فقط دارای ارزش محلی هستند.اگر به طورعمومی در کل شبکه معنی داشته باشند امکان دارد دو مدار مجازی که دارای شماره ی مدار یکسانی هستند از مسیرهایی عبور کنند که منجر به ابهام میشوند.با توجه یه اینکه در این پروژه هدف ما پیدا کردن کوتاهترین مسیر بین دو مسیریاب برای انتقال بسته از مسیریاب مبدا به مسیریاب مقصد میباشد لذا اولین مورد برای شروع کار چگونگی نمایش صورت مسئله می باشد که شرح و بیان مسئله در فصل دوم توضیح داده میشود.به طوری که قابل پیاده سازی باشد.در واقع ما شبکه را به صورت گرافی متشکل از گرهها و یالها نمایش خواهیم داد.برایپیاده سازی این مسئله در فصل سوم به بررسی الگوریتمهای قطعی می پردازیم و به ایننتیجه خواهیم رسید که الگوریتمهای قطعی پیدا کردن جواب بهینه را تضمین می کند ولی هزینه ی زمانی برای n>=40 غیر قابل قبول است در واقع چنین الگوریتمهایی دارای هزینه ی زمانی نمایی خواهند بود که سودمند نخواهند بود.به همین خاطر ما به دنبال روشی خواهیم بود که این هزینه ی زمانی را کاهش دهد و لذا الگوریتمهای ژنتیک روش مناسبی پیشنهاد میشود.که در فصل چهارم به بررسی الگوریتمهای تکاملی و مفاهیم موجود در آن می پردازیم در ادامه فصل مثالی از رنگ آمیزی گراف برای آشنای با کارکرد این الگوریتم ارائه می شود و سپس در فصل پنجم به رائه ی روشی بر اساس الگوریتمهای ژنتیک برای مسئله ی مسیریابی می پردازیم. و براساس این طراحی در فصل 6 به پیاده سازی و شرح کد مربوطه خواهیم پرداخت.و در نهایت ارزیابی و ارائه ی نتایج بدست آمده را در فصل 7 ارائه می دهیم و نتیجه خواهیم گرفت که الگوریتمهایژنتیک جوابهای نزدیک به بهینه را ارائه میدهند.

فهرست مطالب:

چکیده

فصل اول

مقدمه

فصل دوم

بیان و شرح مسئله

فصل سوم

انواع الگوریتم های مسیر یابی

معرفی نمونه ای از الگوریتم قطعی

فصل چهارم

تاریخچه

مفاهیم ژنتیکی

الگوریتم GA

کاربردهای الگوریتم ژنتیک

کد رنگ آمیزی گراف با GA

فصل پنجم

طرح کلی مسئله

فصل ششم

ورودی و خروجی مسئله

پیدا کردن شایسگی هر ژن

عملگر انتخاب

عملگر ترکیب و جهش

نحوه ی اجرا و شرط خاتمه الگوریتم

کد مسیر یابی در شبکه

فصل هفتم

ارزیابی و نتایج

منابع و ماخذ

منابع و مأخذ:

[1] میبدی، محمد رضا وبیگی، حمید."حل مسئله تناظر گراف توسط آتوماتاهای یادگیر". دانشکده ی مهندسی کامپیوتر. دانشگاه صنعتی امیر کبیر. تهران. ایران. 1379.

[2] مبیدی، محمد رضا و رضا پور میر صالح، مهدی. "یک روش ترکیبی (GA+LA) برای حل مسئله تناظر گراف ". دانشکده مهندسی کامپیوتر . دانشگاه صنعتی امیر کبیر. تهران. ایران . 1382.

[3] پرژه پایانی آقای مهندس ناصر لطفی

[4] K.Bryant,’Genetic Algrithms and the travelling salesman problem’, Thesis, Harvey mudd college , Dept.of Mathematics,2000.

دانلود با لینک مستقیم

پروژه یافت کوتاهترین مسیر در شبکه های کامپیوتری مبتنی برپردازش تکاملی. doc

پروژه یافت کوتاهترین مسیر شبکه های کامپیوتری مبتنی برپردازش تکاملی.

yarafile سه‌شنبه 2 آذر 1395 ساعت 20:54

0 نظر

پروژه کلاس بندی مسیر ها روی الگوریتم ((AODV)). doc

اختصاصی از نیک فایل پروژه کلاس بندی مسیر ها روی الگوریتم ((AODV)). doc دانلود با لینک مستقیم و پر سرعت .

پروژه کلاس بندی مسیر ها روی الگوریتم ((AODV)). doc

نوع فایل: word

قابل ویرایش 81 صفحه

مقدمه:

در شبکه های سیار دونوع معماری وجود دارد:شبکه های دارای ساختار(Single-hop) و شبکه های سیار و بدون ساختار (multi-hop) .شبکه های داری ساختار خود نیر از دو نوع می باشند که یکی شبکه های سلولی می باشد ودیگری شبکه های محلی که کاربران برای ارتباط از یک ایستگاه یا یک کنترل کننده مرکزی استفاده می کنند.در شبکه های سیار نودها می توانند به طور دلخواه و وسیع حرکت کنندکه همین امر باعث شده است که آنهارا شبک های خود مختار نیز معرفی کنند.یکی از مسایل مهم در این شبکه ها اطمینان دریافت بسته (delivery) کارا بدون توپولوزی از قبل تعیین شده یا یک کنترل مرکزی می باشد.هرنود در این شبکه ها هم به عنوان میزبان وهم به عنوان مسیر یاب یا جلو برنده بسته عمل می کند.

الگوریتم های مسیر یابی ری هیبرید یا ترکیبی جزالگوریتم هایی هستند که مطالعات زیادی بر روی این الگوریتم ها شده است.الگوریتم هایی چون Zone Routing Protocol (ZRP) و Zone-Based Hierarchical Link State Protocol(ZHLS) ازاین قبیل می باشند.در این پروتکلها مسیر یابی هم به صورت پرو اکتیو وهم به صورت ری اکتیو انجام می گیرد در هر یک از این ناحیه ها همه نودها رویکرد یکسانی دارند وبه صورت پرو اکتیو عمل می کنند.که استفاده از یک موقعیت سنج در پروتکل (ZHLS) کارایی خاص از لحاظ پهنای باند ایجاد کند.

الگوریتم هابی مسیر یابی کلاستری مانند الگوریتمهای تقیسم منطقه ای تحقیقات وپیشرفت های چشم گیری داشته است که منجر به نتا یج خوبی شده است.که Cluster-Head Gateway Switch Routing Protocol (CGSR)و Cluster Based Routing Protocol (CBR) استفاده از کلاستر کردن نودها و انتخاب یک کلا ستر – هد و ایجاد جدول های کلاستر های همسایه برای هر نود و دردوازه های ارتباطی بین نودها منجر شده است که کاریی این الگوریتمها در شبکه های سیار موردی بالا باشد.در پرو تکل(CGSR) با استفاده از رویکرد توکنی و استفاده از CDMA برای Allocate Wireless Channels باعث ایجاد یک رویکرد حریصانه شده است که موجب کاهش تاخیر (Delay) شده است.

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

فهرست مطالب:

مقدمه

(1-1)شبکه های موردی

(2-1)انواع شبکه های بی سیم

(1-2-1)شبکه هایInfrastructure Based

(2-2-1)روشهای ارتباط بی سیم

)1-2-2-1)شبکه های بی سیم و درون سازمانی( ( in door

(2-2-2-1)شبکه های بی سیم و بیرون سازمانی ( out door)

)3-1)کلاس بندی الگوریتم های مسیر یابی

(4-1)الگوریتم های پرواکتیو در مقابل ری اکتیو

)5-1)مسیر یابی کلاسترشده وسلسله مراتبی

)6-1)بررسی پروتکل های مسیر یابی پرواکتیو

)1-6-1)الگوریتم مسیر یابی (DSDV)

(2-6-1)الگوریتم مسیر یابیThe wireless Routiy

(3-6-1)الگوریتم مسیریابیGSR))

)7-1)بررسی الگوریتم های مسیر یابی ری اکتیو

(1-7-1)الگوریتم مسیر یابی (AODV)

(2-7-1)الگوریتم مسیر یابی(DSR)

(8-1)الگوریتم مسیر یابیHybrid

(1-8-1)الگوریتم مسیریابی(CBRP)

)2-8-1)الگوریتم مسیر یابی(ZHLS)

فصل دوم

)2-1)درجه بندی نودها

(2-2)پیاده سازی رویکرد جدید بر روی الگوریتم های مسیریابی ری اکتیو(درجه بندی)

)3-2)پیاده سازی رویکرد جدید بر روی الگوریتم مسیر یابی پرواکتیو(درجه بندی)

(4-2)استفاده از شمارنده برای تعادل باردر شبکه

(5-2(پیاده سازی رویکرد جدید بر روی الگوریتم های ری اکتیو)شمارنده)

(6-2)پیاده سازی رویکرد جدید بر روی الگوریتم های مسیریابی پرواکتیو(شمارنده)

(1-3)اشنایی مقدماتی با ns-2

(1-2-3)طریقه downloadکردن54

(2-2-3)نصب ns

(3-3)شروع کار با ns

(1-3-3)اجرای ns

)2-3-3)معماری ns

(3-3-3)زبان کاربری OTCL

)4-3)نرم افزارnam

(1-4-3)پیکر بندی nam برای نمایش توپولو ی

(2-4-3)واسط کاربری

(3-4-3)مثالهای عملی

(4-4-3)فرمانهای اولیهns 2

(1-4-4-3)مشخص کردن جریانهای ترافیک ومونیتور کردن لینک

(2-4-4-3)تعریف منابع ترافیک و گیرنده های ترافیک

(3-4-4-3)مشخص کردن جریانهای ترافیک

(4-4-4-3)مونیتور کردن یک لینک

(1-5-3)پیاده سازی نود های سیار در ns

(6-3)شبیه سازی وارزیابی نتایج شبیه سازی

(1-6-3)- تغییرات انجام گرفته بر روی AODV

(2-6-3)شبیه سازی

(6-3-3)- ارزیابی نتایج شبیه سازی

(7-3) نتیجه گیری

(8-3)کار های بعدی

فهرست شکل ها:

شکل1-1 ارتباط بین ایستگاهابا نودها در شبکه های دارای ساختار

شکل2-1 شبکه بدون ساختار یازیربنا

شکل 3-1 نحوه مسیر یابی درDSDV

شکل 4-1 نمایش انتشار پیام درخواست مسیر

شکل 5-1 نحو ارسال RREP به مبداء

شکل6-1 ایجاد شکست لینک در شبکه

شکل7-1 مسیر یابی در ِDSR

شکل 8-1 نحوه مسیر یابی در CBR

شکل 9-1 منطقه ای با شعاع 2

شکل10-1 نحوه ارتباط بین پروتکل ها را نشان می دهد

شکل 11-1در سطح نود

شکل 12-1 در سطح ناحیه ای ارتباط بین ناحیه ها

شکل 13-1جدول مسیر در هر نود

شکل 14-1 جدول مسیر یابی بین ناحیه ای

شکل 15-1 مثالی ازمسیر یابی

شکل 1-2-شبکه نمونه

شکل 2-2 – محاسبه درجه مسیر روی نودها

شکل1-3 - شمای کلی ns از دید کاربر

شکل 2-3- ایجاد و فراخوانی روال در tcl

شکل 3-3 - ایجاد شی و استفاده از ارث بری در otcl

شکل 4-3 –ایجاد یک لینک بین دو نود

شکل 5-3 – ترافیک عبوری بر روی لینک

شکل 8-3 –جریانهای ترافیکی

شکل 9-3 – مونیتور کردن لینک

شکل 10-3 – استفاده از صف SFQ

شکل11-3- نحوه محاسبه درجه مسیر

شکل12- 3- کلاسبندی مسیرروی نودکم ترافیک

شکل 13-3 – حالت اولیه از نودهای سیار

شکل 14-3- ترافیک بر روی شبکه سیار

شکل 15-3 –میانگین تعادل باربر روی شبکه

شکل 16-3- میزان بسته های گم شده بر روی شبکه

شکل 17-3 –میزان قابلیت اطمینان

شکل 18-3- میانگین تاخیر بروی شبکه

منابع و مأخذ:

[1] Charalampos Konstantopoulos a, Damianos Gavalas b, Grammati Pantziou cClustering in mobile ad hoc networks through neighborhood stability-based mobility prediction 2008

[2] L. Hanzo (II.) and R. Tafazolli: A Survey of QoS Routing Solutions for Mobile Ad hoc Networks Centre for Communication Systems Research (CCSR) University of Surrey, UK 2006

[3] Apoorva Jindal, Member, IEEE, and Konstantinos Psounis, Member, IEEE:Discovering long lifetime routes in mobile ad hoc networks 2009

[4] Y. Ganjali and A. Keshavarzian , “Load Balancing in Ad Hoc Networks: Single path Routing vs. multipath Routing”, Proceedings of the IEEE INFOCOM'04

. Hong Kong

[5] T. Clausen, P. Jacquet, and L. Viennot. Analyzing control tra±c overhead versus mobility and data tra±c activity in mobile ad-hoc network protocols. ACM Wireless Networks journal (Winet), 10(4), july 2004.

[6]Navid Nikaein and Christian Bonnet: A Glance at Quality of Service Models for Mobile Ad Hoc Networks 2007

[7] Krishna Gorantala : Routing Protocols in Mobile Ad-hoc Networks 2007 Master’s Thesis in Computing Science, 10 credits Supervisor at CS-UmU: Thomas Nilsson Examiner: Per Lindstr¨om

[8] Jun Miao, U Teng Wong, and Ji Hui Zhang, “Survey of Multipath Routing Protocols for Wireless Mobile Ad Hoc Networks”, May 2002.

[9] http://wiki.uni.lu/secan-lab/Ad-Hoc+Protocols.htm

[10] R. Dube, C.D. Rais, K.Y Wang, and S.K. Tripathi, “Signal stability-based adaptive routing (SSA) for ad hoc mobile networks”, IEEE PersonalCommunications, Volum e: 4 Issue: 1 , Feb. 1997, pp 36 –45

[11] C.E. Perkins, E.M. Royer, Ad-hoc on demand distance vector (AODV) routing, in: 2nd IEEE Annual Workshop on Mobile Computing Systems and Applications, 1999, pp. 90– 100.

[12] S. Basagni, M. Mastrogiovanni, A. Panconesi, C. Petrioli, Localized protocols for ad hoc clustering and backbone formation: A performance comparison, IEEE Transactions on Parallel and Distributed Systems 17 (4) (2006) 292–306.

[13] Y. Wang, W. Wang, X.-Y. Li, Distributed low-cost backbone formation for wireless ad hoc networks, in: Proceedings of the Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2005), May 2005, pp. 2–13.

[14] A.K. Saha, D.B. Johnson, Modeling mobility for vehicular ad-hoc networks, in: Proc. 1st ACM Workshop on Vehicular Ad Hoc Networks (VANET 2004), 2004, pp. 91–92 (poster paper).

[15] B. Ishibashi, R. Boutaba, Topology and mobility considerations in mobile ad hoc networks, Ad Hoc Networks 3 (6) (2005) 762–776.

دانلود با لینک مستقیم

پروژه کلاس بندی مسیر ها روی الگوریتم ((AODV)). doc

پروژه کلاس بندی مسیر روی الگوریتم ((AODV)). doc پایان نامه

yarafile سه‌شنبه 2 آذر 1395 ساعت 19:58

0 نظر