رقم المقالة : 202007118308 زيارة : 14683 الصفحة: 31 - 40

نوع المخطوط: المحکّمة

استفاده از خوشه¬بندی در پروتکل مسیریابی AODV برای شبکه-های بین خودرویی بر روی سناریوی بزرگراه

الموضوعات :

امین فیضی ¹ , وحید ستاری نائینی ² , مجید محمدی ³

1 - -
2 - هیات علمی
3 - عضو هیات علمی

تاريخ الإرسال : 05 الأحد , ربيع الثاني, 1436 تاريخ التأكيد : 05 الأحد , ربيع الثاني, 1436 تاريخ الإصدار : 17 الثلاثاء , شوال, 1438

الکلمات المفتاحية: شبکه¬های بین خودرویی, پروتکل مسیریابی AODV , خوشه¬بندی , الگوریتم ازدحام ذرات,

ملخص المقالة :

شبکه های بین خودرویی زیرمجموعه‌ای از شبکه های سیار موردی می باشد که در آن خودروها به عنوان گره های شبکه محسوب می شوند. تفاوت اصلی آن با شبکه های سیار موردی در تحرک سریع گره ها است که باعث تغییر سریع توپولوژی در این شبکه می شود. تغییرات سریع توپولوژی شبکه یک چالش بزرگ برای مسیریابی محسوب می شود که برای مسیریابی در این شبکه ها، پروتکل های مسیریابی باید قوی و قابل‌اعتماد باشد. یکی از پروتکل های مسیریابی شناخته ‌شده در شبکه‌های بین خودرویی، پروتکل مسیریابیAODV است. اعمال این پروتکل مسیریابی بر روی شبکه های بین خودرویی نیز دارای مشکلاتی می‌باشد که با افزایش مقیاس شبکه و تعداد گره ها، تعداد پیام های کنترلی در شبکه افزایش می یابد. یکی از روش‌های کاهش سربار در پروتکل AODV، خوشه بندی کردن گره های شبکه است. در این مقاله برای خوشه بندی کردن گره ها از الگوریتم تغییریافته K-Means و برای انتخاب سر خوشه از الگوریتم ازدحام ذرات استفاده شده است. نتایج بدست آمده از روش پیشنهادی باعث بهبود بار مسیریابی نرمال شده و افزایش نرخ تحویل بسته در مقایسه با پروتکل مسیریابی AODV شده است.

المصادر:

1. Y. Liu, J. Bi, and J. Yang, "Research on vehicular ad hoc networks," in Control and Decision Conference, 2009. CCDC'09. Chinese, 2009, pp. 4430-4435.
2.S. Yousefi, M. S. Mousavi, and M. Fathy, "Vehicular ad hoc networks (VANETs): challenges and perspectives," in ITS Telecommunications Proceedings, 2006 6th International Conference on, 2006, pp. 761-766.
3. B. T. Sharef, R. A. Alsaqour, and M. Ismail, "Vehicular communication ad hoc routing protocols: A survey," Journal of Network and Computer Applications, vol. 40, pp. 363-396, 2014.
4. A. Dua, N. Kumar, and S. Bawa, "A systematic review on routing protocols for Vehicular Ad Hoc Networks," Vehicular Communications, vol. 1, pp. 33-52, 2014.
5. M. Al-Doori, "Directional routing techniques in vanet," Phd Thesis, De Montfort University, 2011.
6. M. Z. A. Mohammed ,N. Abdullah and Rooa Adnan Sabri, "AODV Protocol Improvement using Intelligent Clustering," International Journal of Computer, vol. 88 ,2014.
7. Daxin Tian, Yunpeng Wang, Guangquan Lu and Guizhen Yu," A VANETs Routing Algorithm Based on Euclidean Distance Clustering, " in Future Computer and Communication (ICFCC) ,2010, pp. 183-187.
8. Tao Song, Wei wei Xia, Tiecheng Song and Lianfeng Shen, "A Cluster-Based Directional Routing Protocol in VANET," in Communication Technology (ICCT),2010, pp. 1172-1175
9. Aswathy M C and Tripti C, "A cluster based enhancement to AODV for inter-vehicular communication in VANET," International Journal of Grid Computing & Applications (IJGCA) Vol.3, No.3, September 2012.
11. (AODV) routing," RFC 3561 , 2003.
11. C. E. Perkins and E. M. Royer, "Ad-hoc on-demand distance vector routing," in Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA'99. Second IEEE Workshop on, 1999, pp. 90-100.
12.E. M. Royer and C .E. Perkins, "An implementation study of the AODV routing protocol," in Wireless Communications and Networking Confernce, 2000. WCNC. 2000 IEEE, 2000, pp. 1003-1008.
13.R. C. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory," in Proceedings of the sixth international symposium on micro machine and human science, 1995, pp. 39-43. 14 ] X.-b. Wang, Y.-l. Yang, and J.-w. An, "Multi-metric routing decisions in vanet," in Dependable, Autonomic and Secure Computing, 2009. DASC'09 .Eighth IEEE International Conference on, 2009, pp. 551-556.
14. X.-b. Wang, Y.-l. Yang, and J.-w. An, "Multi-metric routing decisions in vanet," in Dependable, Autonomic and Secure Computing, 2009. DASC'09 .Eighth IEEE International Conference on, 2009, pp. 551-556.
15 K. Z. Ghafoor, K. A. Bakar, M. van Eenennaam, R. H. Khokhar, and A. J. Gonzalez, "A fuzzy logic approach to beaconing for vehicular ad hoc networks," Telecommunication Systems, vol. 52, pp. 139-149, 2013.
16. http://www.openstreetmap.org [seen January Dec. 2015].
S. R. Das, E. M. Belding-Royer, and C. E. Perkins, "Ad hoc on-demand distance vector

نص كامل:

فصلنامه علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال هشتم، شماره‌هاي 29 و 30، پاییز و زمستان 1395

صص: 31- 40

$E:\E Drive\logo\iicta Logo0.JPG$

استفاده از خوشهبندی در پروتکل مسیریابی AODV برای شبکههای بین خودرویی بر روی سناریوی بزرگراه

*امین فیضی **وحید ستارینائینی ***مجید محمدی

*دانشجوی کارشناسی ارشد، بخش مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان

** استادیار، بخش مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان

*** استادیار، بخش مهندسی کامپیوتر، دانشگاه شهید باهنر کرمان

تاریخ دریافت: 05/11/93 تاریخ پذیرش: 18/03/95

چکيده

شبکههای بین خودرویی¹ زیرمجموعه‌ای از شبکههای سیار موردی² میباشد که در آن خودروها بهعنوان گرههای شبکه محسوب میشوند. تفاوت اصلی آن با شبکههای سیار موردی در تحرک سریع گرهها است که باعث تغییر سریع توپولوژی در این شبکه
میشود. تغییرات سریع توپولوژی شبکه یک چالش بزرگ برای مسیریابی محسوب میشود که برای مسیریابی در این شبکهها، پروتکلهای مسیریابی باید قوی و قابل‌اعتماد باشد. یکی از پروتکلهای مسیریابی شناخته ‌شده در شبکه‌های بین خودرویی، پروتکل مسیریابیAODV³ است. اعمال این پروتکل مسیریابی بر روی شبکههای بین خودرویی نیز دارای مشکلاتی می‌باشد که با افزایش مقیاس شبکه و تعداد گرهها، تعداد پیامهای کنترلی در شبکه افزایش مییابد. یکی از روش‌های کاهش سربار در پروتکل AODV، خوشهبندی⁴ کردن گرههای شبکه است. در این مقاله برای خوشهبندی کردن گرهها از الگوریتم تغییریافته K-Means و برای انتخاب سر خوشه از الگوریتم ازدحام ذرات⁵ استفاده شده است. نتایج بدست آمده از روش پیشنهادی باعث بهبود بار مسیریابی نرمال شده و افزایش نرخ تحویل بسته در مقایسه با پروتکل مسیریابی AODV شده است.

نویسندۀ عهدهدار مکاتبات: امین فیضی aminfeyzi.1367@yahoo.com

واژههای کلیدی: شبکههای بین خودرویی، پروتکل مسیریابی AODV ، خوشهبندی ، الگوریتم ازدحام ذرات

[1] Vehicular Ad Hoc Networks(VANET)

[2] Mobile Ad Hoc Networks(MANET)

[3] Ad hoc On-Demand Distance Vector

[4] Clustering

[5] Particle Swarm Algorithm

1.مقدمه

امروزه پیشرفت‌های زیادی در زمینهی فنّاوری سیستم‌های حمل‌ونقل شده است که باعث بوجودآمدن سیستمهای حمل و نقل هوشمند¹ شده است. سیستمهای حمل و نقل هوشمند یک فناوری جدیدی است که بهمنظور بالا بردن سطح ایمنی، کارایی و مدیریت حمل و نقل استفاده میشود. با توجه به آمار روزانهی تصادف در جادهها و همچنین وجود ترافیک درخیابانها که باعث صرف زمان زیادی میشود، متخصصین خودروسازی مجبور به ساخت خودروهایی
شدهاند که توانایی تعامل با سیستمهای هوشمند را داشته باشند. در واقع مدیریت و کنترل ترافیک یکی از
ضروریتهای امروزی در این سیستمها میباشد. در
سیستمهای ITS هرکدام از خودروها میتوانند با دیگر خودروهای در حال حرکت ارتباط برقرار کنند و سفری مطمئن و با ایمنی بیشتری داشته باشند. ارتباط بین خودروها مولفهی اصلی در سیستمهای ITS بهشمار میرود که شامل انواع ارتباطات خودرو به خودرو² و ارتباط خودرو با تجهیزات کنار جادهای³ میباشد؛ این ارتباطات باعث ورود شبکههای بین خودرویی به عرصهی شبکههای کامپیوتری شده است.

یکی از مهم‌ترین ویژگیهای شبکههای بین خودرویی این است که خودروها در آن با سرعت‌ بالا حرکت میکنند و این باعث تغییر مداوم توپولوژی شبکه میشود ]1،2[. بنابراین طراحی یک پروتکل مسیریابی مؤثر و قابل‌اعتماد برای انتقال پیام در شبکه امری بسیار ضروری میباشد. در این رابطه، امروزه بسیاری از محققان تمام تلاش خود را بر روی طراحی یک پروتکل مسیریابی مناسب برای محیط‌های که تراکم وسایل نقلیه در آن زیاد است، متمرکز کرده‌اند. طراحی یک پروتکل مسیریابی کارآمد، به بهبود بسیاری از عوامل ازجمله درصد تحویل بسته، انتقال بسته در کوتاه‌ترین زمان و کاهش تداخل ناشی از ساختمان‌ها و موانع و غیره کمک میکند.

در حالت کلی مسیریابی در شبکه‌های بین خودرویی به دودستهی مسیریابی بر اساس توپولوژی ⁴ و مسیریابی بر اساس موقعیت⁵ طبقهبندی می‌شوند. پروتکلهای مسیریابی بر اساس موقعیت، از اطلاعات موقعیت جغرافیایی گرهها برای مسیریابی استفاده میکنند و پروتکلهای مسیریابی بر اساس توپولوژی، از اطلاعاتی که در شبکه برای ارسال بسته از جمله سرعت، جهت و غیره وجود دارد، استفاده
میکنند ]3،4،5[.

پروتکل مسیریابی AODV یک پروتکل مسیریابی بر حسب تقاضا میباشد که از لحاظ نسبت تحویل بسته و سربار مسیریابی، اما با تاخیر انتها به انتها و از دست رفتن بسته بیشتر، درمقایسه با دیگر پروتکلهای مسیریابی بر اساس توپولوژی، ترجیح داده شده است. یکی از ضعف‌های پروتکل مسیریابی AODV این است که در فرایند کشف مسیر تعداد زیادی پیامهای کنترلی در شبکه همهپخشی میشود و این فرایند باعث میشود مسیرهای غیرقابل استفاده بسیاری بین گره منبع و مقصد پیدا شود؛ همچنین باعث افزایش سربار مسیریابی و پهنای باند مصرفی میشود.

در این مقاله، از الگوریتم خوشهبندی K-Means برای خوشهبندی کردن گرهها استفاده میکند، با این تفاوت که علاوه بر معیار فاصله، از معیار جهت نیز برای خوشهبندی کردن گرهها استفاده شده است. پس از فرایند خوشهبندی، از هر خوشه یک گره سرخوشه برای مدیریت انتقال پیامهای کنترلی انتخاب میشود که برای اینکار از الگوریتم ازدحام ذرات استفاده شده است.

در ادامه این مقاله ابتدا در بخش 2 پیشینه تحقیق آورده شده است و در بخش3 پیشزمینه ارائه شده سپس در بخش4 پروتکل پیشنهادی، بررسی خواهد شد و در بخش 5 جزئیاتی در مورد پارامترها و سناریوی شبیهسازی بیان شده است و همچنین ارزیابی و تحلیل نتایج در بخش 6 ارائه میشود و نهایتا در بخش 7 نتیجهگیری بیان میگردد.

2.پیشینه تحقیق

در سالهای اخیر کارهای زیادی برای بهبود پروتکل مسیریابی AODV انجام شده است که در ادامه به برخی از مهمترین کارهای انجامی در این راستا میپردازیم. در مرجع ]6[ پروتکل مسیریابی Clustered-AODV توسط محمد عبدالله و همکارانش درسال 2014 پیشنهادشده است. این پروتکل از معماری خوشه‌بندی و ویژگی‌های AODV برای مسیریابی استفاده میکند. این پروتکل با استفاده از الگوریتم خوشه‌بندی K-Means گرهها را با استفاده از فاصلهی آن‌ها به تعداد مشخصی از خوشه‌ها، خوشهبندی میکند و با بهکارگیری الگوریتم ژنتیک، مرکز خوشهها از هر خوشه انتخاب میشود. در سال 2010 تیان و همکاران یک پروتکل مسیریابی خوشهبندی برای شبکههای بین خودرویی ارائه کردند]7[. در این پروتکل مسیریابی، برای خوشهبندی کردن خودروها از فاصلهی اقلیدسی استفاده شده است. در این پروتکل تنها خودروهای با جهت یکسان میتوانند در یک خوشه باشند. نتایج پیادهسازی این پروتکل
نشاندهندهی کاهش سربار مسیریابی و همچنین انتخاب مسیرهای پایدارتر برای انتقال بسته میباشد. تاووسونگ و همکاران در سال 2010 یک پروتکل مسیریابی تحت عنوان CBDRP⁶ برای سناریوی بزرگراه در شبکههای بین خودرویی ارائه کردند ]8[ که در این پروتکل مسیریابی برای خوشهبندی کردن خودروها از معیار جهت یکسان خودروها استفاده میکند. نتایج حاصل از اجرای این پروتکل،
نشاندهنده انتقال سریعتر بستهها به مقصد و همچنین انتخاب مسیرهای پایدارتر میباشد. پروتکل مسیریابیAODVC⁷ توسط اسواتی و همکاران در سال 2012 برای شبکههای بین خودرویی پیشنهاد شده است. این پروتکل مسیریابی بهبود یافته پروتکل مسیریابی AODV میباشد و مبتنی بر خوشهبندی است. در این کار مدیریت انتقال بسته توسط گرههای سرخوشه و گرههای دروازه انجام میگیرد؛ بدین طریق که در فرایند کشف مسیر بهجای همهپخشی شدن پیام درخواست مسیر به تمام
گرهها، تنها پیام درخواست مسیر تحویل گره سرخوشه داده میشود]9[.

3.پیشزمینه

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

1-3- پروتکل مسیریابی AODV

پروتکل مسیریابی AODVیکی از پروتکلهای مورد استفاده در شبکههای بین خودرویی است. این پروتکل مسیریابی یک نمونه از پروتکلهای مسیریابی براساس توپولوژی میباشد. این پروتکل مسیریابی شامل سه فاز کشف مسیر، انتقال داده و نگهداری مسیر است و همچنین شامل سه نوع پیام کنترلی، RREQ⁸، RREP⁹ و RERR¹⁰ است که برای کشف و نگهداری مسیر استفاده میشود. فرایند کشف مسیر، زمانی که گره منبع بخواهد پیامی را برای گره مقصد ارسال کند و هیچ مسیر معتبری به مقصد وجود نداشته باشد، آغاز میشود. در این فاز گره منبع یک بسته RREQ را به همسایههایش همهپخشی¹¹ میکند و همسایه‌ها نیز همین فرایند را انجام میدهند و این عمل تا زمانی انجام میشود که گره دریافتکننده پیام، گره مقصد باشد یا مسیری به مقصد داشته باشند؛ در این صورت گره دریافتکننده، یک بستهی RREP به مسیری که RREQ از آن دریافت کرده است، تکپخشی¹² میکند. پس از فاز کشف مسیر فاز انتقال داده انجام میشود که بر اساس مسیر انتخاب‌شده، داده انتقال پیدا میکند. در این فاز ممکن است پیوند شکسته شود که در این صورت فاز نگهداری مسیر برای تعمیر لینک شکسته و یا پیدا کردن مسیر جدید به مقصد فراخوانی میشود. در زمان شکسته شدن لینک،
گرهای که لینک آن شکسته شده، یک بستهی RERR به گره منبع تکپخشی میکند و گره منبع پس از دریافت بسته RERR در جدول مسیریابی خود یک مسیر دیگر به مقصد جستجو میکند که برای انتقال داده از آن استفاده کند و درصورتی‌که مسیری نباشد بستهی RREQ برای پیدا کردن مسیر جدید دوباره همهپخشی میشود که در صورت پیدا نشدن مسیر به مقصد خطا رخ میدهد و انتقال داده متوقف میشود. لازم به ذکر است که اطلاعات اتصال لینکها از طریق پیام سلام¹³ به دست میآید، که این پیام به‌صورت دوره‌ای از طریق گرهها برای مشخص کردن اتصالات، به همسایه‌هایش همه پخشی میشود ]10،11،12[.

2-3- خوشهبندی

ایدهی خوشه‌بندی اولین بار در سال 1935 ارائه شد و امروزه پیشرفتها و جهش‌های عظیمی در آن پدید آمده است. خوشه‌بندي را مي‌توان به‌عنوان مهم‌ترین مسئله در يادگيري بدون نظارت در نظر گرفت. در خوشه‌بندي سعي مي‌شود تا دادهها به خوشه‌هايي تقسيم شوند که شباهت بين داده‌هاي درون هر خوشه حداکثر و شباهت بين داده‌هاي درون خوشه‌هاي متفاوت حداقل شود. نمونه‌ای از الگوریتم‌های رایج در خوشه‌بندی، K-Means است که در آن هرکدام از داده‌ها دقیقاً به یک خوشه تعلق میگیرد.

K- Means، يکي از ساده‌ترین الگوریتم‌های يادگيري بدون نظارت است. این الگوریتم اولین بار توسط استاردلوید در سال 1957، ارائه‌شده است در این الگوریتم ابتدا k نقطه به‌عنوان مرکز خوشه استفاده میشود؛ سپس فاصله تمام نمونه داده‌ها با مراکز خوشه محاسبه ‌شده و هر نمونهی داده به نزدیک‌ترین خوشه اختصاص داده میشود. در شکل 1، فلوچارت الگوریتم K-Means نشان داده‌شده است.

شکل 1. فلوچارت الگوریتم K-Means

3-3- الگوریتم ازدحام ذرات

الگوریتم ازدحام ذرات در سال 1995 توسط ابرهارت و کندی پیشنهاد شده است]13[. این الگوریتم از زندگی حیواناتی ازجمله پرندگان و ماهیها الهام گرفته ‌شده است. در این الگوریتم فرض شده است که پرندگان در جستجوی غذا، به‌صورت غریزی فاصلهی خود را تا غذا حس میکنند، درحالی‌که از مکان آن اطلاعی ندارند؛ علاوه بر آن، فرض شده است که تمام پرندگان با به اشتراک گذاشتن اطلاعات خود، موقعیت نزدیک‌ترین پرنده به غذا را می‌دانند. در الگوریتم ازدحام ذرات هر جواب مسئله، یک پرنده در فضای جستجو است که ذره نام دارد. هر ذره دارای یک مقدار شایستگی است که توسط تابع شایستگی مسئله بدست
میآید. پرندهای که به غذا نزدیکتر است، شایستگی بیشتری دارد. الگوریتم ازدحام ذرات با يك گروه از جواب‌های تصادفی شروع به كار ميكند؛ سپس براي يافتن جواب بهينه در فضاي مسئله، با به‌روز كردن مكان ذرهها به جستجو ميپردازد. هر ذره با دو مقدار Xid و Vid كه به ترتيب معرف موقعيت مكاني و سرعت بعد dام از i امين ذره هستند، مشخص ميشود. در هر مرحله از حركت جمعيت، مكان هر ذره با دو مقدار p_best و g_best به‌روزرسانی ميشود. p_best بهترين جواب ازلحاظ شايستگي است كه تاكنون براي هر ذره به‌طور مجزا بدست آمده، است وg_best بهترين مقداري است كه تاکنون توسط تمام
ذرهها در ميان كل جمعيت به‌دست‌آمده، است. در هر تكرار الگوريتم بعد از يافتن دو مقدار p_best وg_best، سرعت و مكان جديد هر ذره طبق روابط (1) و (2) بهروزرسانی می‌شوند.

(1)

(2) در رابطهی بالا، w در بازه ]0،1[ ،c1 و c2 ضرایب یادگیری یا شتاب هستند که در بازه]1،2 [ هستند. rand عددی تصادفی در بازه ]0،1[ است. مقدار نهایی سرعت هر ذره برای جلوگیری از واگرائی به یک بازه [-vmax,vmax] محدود میشود. شرط خاتمهی الگوریتم، همگرایی آن یا توقف بعد از تکرار معینی از تکرار است.

4. پروتکل پیشنهادی

در فرایند کشف مسیر در پروتکل مسیریابی AODV، تعداد زیادی پیامهای کنترلی در شبکه همهپخشی میشود و این فرایند باعث میشود مسیرهای غیرقابل استفادهی بسیاری بین گرهی منبع و مقصد پیدا شود که بهعنوان یکی از ضعف‌های پروتکل مسیریابی AODV شناخته میشود که باعث افزایش سربار مسیریابی و پهنای باند مصرفی
میشود. یکی از روش‌های کاهش سربار مسیریابی در پروتکل AODV، خوشهبندی گرههای شبکه است که در آن مراکز هر خوشه، انتقال بسته RREQ را مدیریت می‌کنند که باعث بهبود کارایی پروتکل مسیریابی و همچنین کاهش پیام‌های کنترلی و مسیرهای غیرقابل استفاده میشود. خوشه‌بندی در این شبکه‌ها بدین معنی است که گره‌های موجود در شبکه با توجه به برخی از قوانین، خوشه‌بندی می‌شوند که این قوانین در هر الگوریتم خوشه‌بندی متفاوت است. با خوشهبندی کردن گرهها در شبکه، تمرکز فرایند مسیریابی تنها به زیرمجموعهای از
گرهها در شبکه می‌باشد و مسیریابی به‌سادگی انجام می‌گیرد و همچنین انتشار پیامهای درخواست مسیرکاهش مییابد. هرکدام از پروتکل‌های مسیریابی خوشه‌بندی‌ اهداف متفاوتی ازجمله پایداری خوشه، شکلدهی سریع خوشه و کاهش سربار پیام‌های کنترلی را دنبال می‌کنند. هدف از این پروتکل پیشنهادی کاهش سربار پیام‌های کنترلی است و شامل 3 مرحلهی تشکیل خوشه، انتخاب سرخوشه و مسیریابی در خوشه‌ها است.

1-4- تشکیل خوشه

هرکدام از خوشه‌ها دارای حداقل یک مرکز خوشه است که به‌وسیلهی دیگر گرههای موجود در هر خوشه انتخاب
میشوند. پروتکل پیشنهادی شامل دو نوع گره میباشد، گره سرخوشه و گره عضو. ارسال بسته‌های کنترلی از طریق
گرههای سرخوشه مدیریت می‌شود و بقیه گرهها، گرههای عضو خوشه هستند. شکل 2 گره‌های سر خوشه و گرههای عضو خوشه را نشان میدهد.

شکل2. گره‌های عضو و گره‌های سرخوشه

برای خوشه‌بندی کردن گره‌ها از الگوریتم K-Means استفاده‌ شده است که این کار در دورههای زمانی مشخصی انجام می‌شود که در شبیهسازی در نظر گرفته شده است. در این پروتکل یک سری تغییرات بر روی الگوریتم خوشه‌بندی K-Means انجام‌ شده است. همان‌طور که ذکر شد الگوریتم خوشه‌بندی K-Means از معیار نزدیک‌ترین فاصله برای خوشهبندی استفاده می‌کند ولی در اینجا علاوه بر معیار نزدیک‌ترین فاصله، معیار هم‌جهت بودن گرهها با یکدیگر نیز استفاده ‌شده است. این دو معیار به‌صورت فازی در نظر گرفته ‌شده‌اند که خروجی فازی مشخص‌کننده اولویت تعلق هرکدام از گرهها به خوشهها است. شکل 3 نشان دهنده الگوریتم خوشهبندی کردن گرهها در شبکه است.

شکل3. الگوریتم خوشهبندی پیشنهادی

برای بدست آوردن فاصله هر گره با مرکز خوشه از رابطه (3) استفاده ‌شده است که d فاصله بین دو گره است و (x1,y1) مختصات مرکز خوشه را نشان میدهد و (x2,y2) بیانگر مختصات گره جاری میباشد.

(3)

برای بدست آوردن میزان درجهی جهت، با فرض اینکه جهت حرکت گره جاری (dx1,dy1) و جهت گره مرکز خوشه (dx2,dy2) باشد؛ که dx و dy نشان‌دهنده مؤلفه بردار جهت بر روی محور X و محور Y است و اگر α برابر با میزان درجه بین دوگره باشد، α با استفاده از رابطه (4) بدست میآید]14،15[.

(4)

تابع عضویت جهت و فاصله در شکل 4 و تابع عضویت خروجی در شکل 5 قابل مشاهده است و قوانین به‌کار رفته در این سیستم استنتاج فازی، در جدول 1 نشان داده شده است.

جدول1 . مجموعه قوانین فاصله و جهت برای تعلق گره‌ها به سر خوشه

خروجی	فاصله	جهت
Prefect	Low	Low	Rule1
Good	Medium	Low	Rule2
Normal	High	Low	Rule3
Normal	Low	Medium	Rule4
Normal	Medium	Medium	Rule5
Bad	High	Medium	Rule6
Bad	Low	High	Rule7
Bad	Medium	High	Rule8
Very Bad	High	High	Rule9

شکل 4. توابع عضویت فاصله و جهت

شکل5. تابع عضویت خروجی

2-4- انتخاب سرخوشهها

پس از خوشه‌بندی کردن گره‌ها توسط الگوریتم K-Means ،با استفاده از الگوریتم ازدحام ذرات، از هر خوشه یک گره بهعنوان سرخوشه برای مدیریت انتقال بسته‌های کنترلی انتخاب میشود. در این الگوریتم تعداد ابعاد هر ذره به‌اندازه تعداد خوشه‌ها در نظر گرفته ‌شده است که هرکدام از این ابعاد مشخص‌کنندهی گره منتخب هر خوشه است. تابع ارزیابی آن نیز بدین‌صورت است که برای هرکدام از گره‌های منتخب در ابعاد ذره تعداد همسایهها و سرعت گره محاسبه ‌شده و به‌عنوان ورودی یک سیستم فازی در نظر گرفته‌ شده است و خروجی حاصل از سیستم فازی به‌عنوان ورودی تابع ارزیابی در نظر گرفته میشود.

جدول 2 مجموعه قوانین به‌کاررفته در سیستم استنتاج فازی مربوط به تابع ارزیابی الگوریتم ازدحام ذرات را نشان میدهد و همچنین توابع عضویت تعداد همسایهها و سرعت نیز در شکل 6 نشان داده‌ شده است. تابع خروجی نیز همانند شکل 5 میباشد.

شکل6. تابع عضویت تعداد همسایه و سرعت

جدول 2. مجموعه قوانین تعداد همسایه و سرعت برای مشخص کردن سر خوشه‌ها

خروجی	تعداد همسایه	سرعت
Normal	Low	Low	Rule1
Good	Medium	Low	Rule2
Prefect	High	Low	Rule3
Bad	Low	Medium	Rule4
Normal	Medium	Medium	Rule5
Normal	High	Medium	Rule6
Very Bad	Low	High	Rule7
Bad	Medium	High	Rule8
Normal	High	High	Rule9

برای محاسبهی تابع ارزیابی الگوریتم ازدحام ذرات از
رابطهی (5) استفاده ‌شده است که Costi نشان‌دهندهی ارزش هرکدام از ابعاد ذرات است و m بیانگر تعداد ابعاد است.

(5)

3-4- مسیریابی در خوشهها

هرکدام از گره‌های عضو در هر خوشه، دارای شناسهی خوشه، شناسهی گره، شناسهی سرخوشه و همچنین دارای یک جدول است که اطلاعات گره‌های همسایه ازجمله شناسهی گرهی همسایه و شناسهی سرخوشه گرهی همسایه در آن ذخیره میشود. هر گرهی سر خوشه نیز دارای فیلدهای ذکرشده و همچنین حاوی یک جدول خوشه است که در آن شناسه و موقعیت هرکدام از گرههای عضو خوشه ذخیره می‌شود.

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

لازم به ذکر است که گرههای عضو خوشه می‌توانند در محدودهی رادیویی گره سرخوشه نباشند و ارسال بستهی RREQ از طریق گرههای میانی انجام میشود و با توجه به اینکه گرهی سرخوشه موقعیت گره‌های عضو را می‌داند نزدیک‌ترین گرهها را برای ارسال بسته RREQ انتخاب میکند.

5. پارامترها و سناریوی شبیهسازی

پروتکل پیشنهادی با استفاده از شبیهساز شبکه NS2.34 پیادهسازی شده است که به منظور شبیهسازی مدل های تحرک واقعی از شبیهساز ترافیک جادهای SUMO استفاده شده است. سناریوی استفاده‌ شده در پروتکل پیشنهادی یک سناریوی بزرگراه به‌اندازه 2900×7400 متر از یک منطقه از شهر کرمان است که در شکل 7 نشان داده ‌شده است.

شکل 7. نقشه یک بزرگراه به‌اندازه 2900×7400 متر

برای بدست آوردن سناریوی بزگراه از مرجع]16[ استفاده شده است. زمان شبیهسازی این کار 1400 ثانیه میباشد و سرعت خودروها بین 10 تا 80 کیلومتر در ساعت و تعداد خودروها 100 در نظر گرفته‌شده است و سایر پارامترهای استفاده‌ شده در جدول 3 نشان داده شده است.

جدول 3. سایرپارامترهای شبیهسازی

7400m×2900m	Scenario Area
50m	Transmission Range
802.11	MAC
1000 byte	Packet size
1500 seconds	Simulation Time
100	Number of vehicles
UDP	Transport
CBR	Application
Two Ray Ground	Propagation
Omni Antena	Antena
10-80 km/h	Mobility of Vehicles
5-10-15	Cluster numbers

6. ارزیابی و تحلیل نتایج

در این مقاله روش پیشنهادی با الگوریتم AODV مقایسه شده است. پارامترهایی که مورد ارزیابی قرار گرفتهاند، نرخ بستههای تحویل داده شده، سربار مسیریابی نرمال شده و متوسط تاخیر انتها به انتها میباشد. نتایج حاصل از روش پیشنهادی برای تعداد 5، 10 و 15 خوشه تست ‌شده است.

1-6- میانگین تأخیر انتها به انتها

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

شکل 8. میانگین تاخیر انتها به انتها

2-6- نرخ بستههای تحویل داده‌ شده

این معیار نسبت بستههای دریافت شده توسط گره مقصد به بستههای ارسال ‌شده توسط گره منبع، میباشد که بهعنوان بستههای تحویل داده‌ شده مشخص میشود. شکل 9
نشاندهنده مقایسه این معیار در روش پیشنهادی با پروتکل مسیریابی AODV است. که این نتایج بیانگر بهبود عملکرد روش پیشنهادی میباشد.

شکل9. نرخ بستههای تحویل داده‌ شده

3-6- بار مسیریابی نرمالشده

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

شکل 10. بار مسیریابی نرمالشده

7. نتیجهگیری

روش پیشنهاد شده در این مقاله، بهبودیافتهی پروتکل مسیریابی AODV میباشد. روش پیشنهادی از ایدهی خوشهبندی در شبکههای بین خودرویی استفاده میکند. در این کار از الگوریتم تغییریافتهی K-Means، برای

خوشهبندی گرهها در شبکه استفاده شده است و برای انتخاب گرههای سرخوشه از الگوریتم ازدحام ذرات کمک گرفته شده است. این پروتکل مسیریابی بر روی یک سناریوی بزرگراه تست شده است. نتایج شبیهسازی نشان میدهد که الگوریتم پیشنهادی نسبت به پروتکل مسیریابی AODV دارای نرخ تحویل بسته بهتر و همچنین بار مسیریابی کمتری است. ضعف بزرگی که در این پروتکل پیشنهادی دیده می‌شود این است که در الگوریتم
خوشهبندی K-means باید تعداد خوشهها مشخص باشد و این منجر به یک روش خوشهبندی ایستا میگردد. در جهت بهبود این الگوریتم در کارهای آتی استفاده از الگوریتم خوشهبندی مناسبی برای انتخاب خودکار تعداد خوشهها مد نظر قرار خواهد گرفت و همچنین با توجه به مشکلاتی که در سناریوی شهری است، انتظار میرود با توسعه این روش پیشنهادی بتوان آن را برای سناریوی شهری نیز استفاده کرد.

6. M. Z. A. Mohammed ,N. Abdullah and Rooa Adnan Sabri, "AODV Protocol Improvement using Intelligent Clustering," International Journal of Computer, vol. 88 ,2014.

7. Daxin Tian, Yunpeng Wang, Guangquan Lu and Guizhen Yu," A VANETs Routing Algorithm Based on Euclidean Distance Clustering, " in Future Computer and Communication (ICFCC) ,2010, pp. 183-187.

8. Tao Song, Wei wei Xia, Tiecheng Song and Lianfeng Shen, "A Cluster-Based Directional Routing Protocol in VANET," in Communication Technology (ICCT),2010, pp. 1172-1175

9. Aswathy M C and Tripti C, "A cluster based enhancement to AODV for inter-vehicular communication in VANET," International Journal of Grid Computing & Applications (IJGCA) Vol.3, No.3, September 2012.

11. S. R. Das, E. M. Belding-Royer, and C. E. Perkins, "Ad hoc on-demand distance vector

منابع

1. Y. Liu, J. Bi, and J. Yang, "Research on vehicular ad hoc networks," in Control and Decision Conference, 2009. CCDC'09. Chinese, 2009, pp. 4430-4435.

2.S. Yousefi, M. S. Mousavi, and M. Fathy, "Vehicular ad hoc networks (VANETs): challenges and perspectives," in ITS Telecommunications Proceedings, 2006 6th International Conference on, 2006, pp. 761-766.

3. B. T. Sharef, R. A. Alsaqour, and M. Ismail, "Vehicular communication ad hoc routing protocols: A survey," Journal of Network and Computer Applications, vol. 40, pp. 363-396, 2014.

4. A. Dua, N. Kumar, and S. Bawa, "A systematic review on routing protocols for Vehicular Ad Hoc Networks," Vehicular Communications, vol. 1, pp. 33-52, 2014.

5. M. Al-Doori, "Directional routing techniques in vanet," Phd Thesis, De Montfort University, 2011.

(AODV) routing," RFC 3561 , 2003.

11. C. E. Perkins and E. M. Royer, "Ad-hoc on-demand distance vector routing," in Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA'99. Second IEEE Workshop on, 1999, pp. 90-100.

12.E. M. Royer and C .E. Perkins, "An implementation study of the AODV routing protocol," in Wireless Communications and Networking Confernce, 2000. WCNC. 2000 IEEE, 2000, pp. 1003-1008.

13.R. C. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory," in Proceedings of the sixth international symposium on micro machine and human science, 1995, pp. 39-43. 14 ] X.-b. Wang, Y.-l. Yang, and J.-w. An, "Multi-metric routing

decisions in vanet," in Dependable, Autonomic and Secure Computing, 2009. DASC'09 .Eighth IEEE International Conference on, 2009, pp. 551-556.

14. X.-b. Wang, Y.-l. Yang, and J.-w. An, "Multi-metric routing decisions in vanet," in Dependable, Autonomic and Secure Computing, 2009. DASC'09 .Eighth IEEE International Conference on, 2009, pp. 551-556.

15 K. Z. Ghafoor, K. A. Bakar, M. van Eenennaam,

R. H. Khokhar, and A. J. Gonzalez, "A fuzzy logic approach to beaconing for vehicular ad hoc networks," Telecommunication Systems, vol. 52, pp. 139-149, 2013.

16. http://www.openstreetmap.org [seen January Dec. 2015].

[1] Intelligent Transport System(ITS)

[2] Vehicle-to-Vehicle (V2V)

[3] Vehicle-to-RoadSide Unite(V2R)

[4] Topology-based Routing

[5] Position-Based Routing

[6] Cluster-based directional routing protocol

[7] AODV Clustering

[8] Route Request

[9] Route Reply

[10] Route Error

[11] Broadcast

[12] Unicast

[13] Hello Message

شارک

عنوان URL للمقالة

استفاده از خوشه¬بندی در پروتکل مسیریابی AODV برای شبکه-های بین خودرویی بر روی سناریوی بزرگراه

رایمگ

الروابط

المراكز ذات الصلة

دعامة

الصفحات الرسمية