چکیده

در این مقاله یک الگوریتم خوشه بندی هوشمند به نام PMW برای شبکه های موردی سیار )MANET( بااستفاده از الگوریتم های خوشه بندی وزنی جدید ارائه می شود که انرژی باقیمانده، تحرک و حجم کار برای گره های موجود در خوشه ها را به کار می برد و سرخوشه×ها را با استفاده از ترکیب الگوریتم های هوشمند رقابت استعماری و K-means در بهینه ترین شکل خود انتخاب می×کند.

نتایج شبیه سازی تایید می کنند که PMW افزایش طول عمر MANET ها را در پی دارد و دارای نرخ پایین تری از تعویض سر خوشه ها را نسبت به الگوریتم موجودMOBIC دارد.

واژه های کلیدی: شبکه های موردی سیار، الگوریتم های خوشه بندی، الگوریتم رقابت استعماری

-۱ مقدمه
شبکه موردی سیار (MANET ) مجموعه ای از میزبان ۱ ها یا گره های۲ سیاری می باشد که انرژی خود را از باتری تامین می کننـد و بوسـیله پهنای باند پایین بی سیم به هم متصل شده اند . هر گـره ناحیـه ای از نفوذ خود را دارد که سلول۳ خوانده می شود و بدون آنکـه زیـر سـاخت های ثابتی داشته باشند فقط گره های داخل آن سلول می توانند بـا آن گره تبادل اطلاعات داشـته باشـند .]۰۱[ وقتـی کـه طوفـان، زلزلـه یـا سونامی اتفاق می افتد واکنش به حادثه بد و عمل بازیابی معمولاً بعلـت

خرابی ارتباطات مختل می شود زیرا احتمالا متصدی زیربنای ارتباطات در طول این حوادث خسارت دیده یا از بین رفته است. همچنین مناطق دور افتاده فاقـد زیرسـاخت هـای ارتبـاطی از راه دور هسـتند و فـراهم ساختن خدمات پزشکی به موقع و با کیفیـت مشـکل اسـت. در میـدان جنگ سربازان در یگان های نظامی سازماندهی می شوند نزدیک تانکها یا خودروهای نظامی شان می ایستند و اطلاعات بین تمـام آنهـا پخـش می شود به عبارت دیگر رهبر یا گروهی از رهبران هسـتند کـه بـه هـر شخص می گویند کجا و چگونه حرکت کند یا در کدام منطقـه هماننـد آنچه در شکل ۱ نشان داده شده است، قرار گیرند.]۲[

۱)Host

۲)Node

۳)Cell

شکل :۱ عملکردهای نظامی در میدان جنگ ]۲[

بنابر این واکنش در مقابل حوادث غیر مترقبـه مثـل زلزلـه، سـونامی و طوفان ]۰[ و]۰۱[و]۷[، سیستم های سیار خـدمات پزشـکی از راه دور ]۰۱[ ، و بهره برداری های نظامی مثل میادین جنگ ]۰[ می×تواننـد از چنین شبکه هایی استفاده نمایند.

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

-۲ پیشینه تحقیق

ما در جهانی پر از داده زندگی می کنیم و هر روز با حجم وسیعی از اطلاعات که باید آنها را ذخیره یا نمایش دهیم، روبه رو هستیم. یکی از روشهای حیاتی کنترل و مدیریت این داده ها، طبقه بندی یا خوشه بندی می باشد. اولین بار ایده خوشه بندی در دهه ۱۹۳۵ ارائه شد و امروزه، با پیشرفت ها و جهش های عظیمی که در آن پدید آمده، خوشه بندی مورد توجه بسیاری از محققان قرار گرفته است.

الگوریتم k-means یکی از روشهای معروف خوشه بندی افرازی محسوب می گردد که به سادگی قابل پیاده سازی می×باشد.در الگوریتم ژنتیک محدودیت های روش k-mean از بین رفته است .در عین حال با ترکیب این دو الگوریتم نتایج قابل توجهی حاصل شده است که سرعت همگرایی نیز به مراتب از نمونه های قبل، بیشتر گردیده است. همچنین از ترکیب الگوریتم k-means با الگوریتم جستجوی ممنوع به نتایج قابل توجهی دست خواهیم یافت و نیز با بهره گرفتن از محاسن هر الگوریتم، معایب آنها به طور قابل ملاحظه ای پوشش داده شده است.]۰۰[ با استفاده از ترکیب الگوریتم ژنتیک و روش فازی، روشی توسط عسگریان در سال ۲۰۰۷ مطرح شد .در این روش مشکل وابستگی به تعداد اولیه خوشه و مکان اولیه مراکز خوشه مرتفع گردید . همچنین با عدم توانایی خوشه بندی داده هایی، که فاصله آنها از مراکز چند خوشه به یک اندازه می باشد مقابله گردید.[۱۶] یکی دیگر از روشهای ترکیبی که در مسائل داده کاوی کاربرد دارد، استفاده از روش جستجوی ممنوع و PSO می باشد. این طرح در سال ۲۰۰۸ توسط شن و همکارانش مطرح شد و توانست همگرایی به بهینه محلی را پوشش دهد.به عبارتی یکی از روش های مناسب جهت انتخاب ژن ها در تومور می باشد.[۴] یکی دیگر از روشهای جدید برای مسائل داده کاوی، ترکیب الگوریتم PSO تطبیقی فازی با دو الگوریتم کلونی مورچه و k-means می باشد .این روش توسط نیکنام و همکارش در سال ۲۰۱۰ مطرح گردید[۱۵] .نتایج حاصله از این تکنیک در راستای بهبود عملکرد خوشه بندی اطلاعات بسیار جالب توجه می باشد از مزیت×های کلونی مورچگان، توانایی پیش بینی تعداد خوشه ها را می توان ذکر نمود و اینکه نتایج حاصله برتری کیفیت عملکرد ارزیابی را تضمین می نماید. در سال ۲۰۰۷ فتحیان و همکارانش روشی مبتنی بر ترکیب دو الگوریتم معروف k-means و جفت گیری زنبور عسل ارائه نمود. [۹] این الگوریتم بر پایه زندگی اجتماعی حشرات بنا شده است که در حوزه هوش مصنوعی می باشد .عملکرد این الگوریتم در مقایسه با نسخه های اصلی الگوریتم جستجوی ممنوع، آبکاری فولاد، ژنتیک و کلونی مورچه قابل ملاحظه می باشد. یکی از روشهای تکاملی که الهام گرفته از رفتار سیاسی -اجتماعی بشر می باشد، الگوریتم رقابت کشورهای استعماری می باشد که توسط اسماعیل آتش پز گرگری در

سال ۲۰۰۷ ابداع گردیده است . [۳] روش دیگری که توسط نیکنام و همکارانش در سال ۲۰۱۱ ارائه گردید خوشه بندی اطلاعات به روش MICA-k می باشد که به دلیل انتخاب مناسب مقدار اولیه برای الگوریتم k-means، جواب بهتری حاصل می گردد[۱۶]، ما نیز از این ایده جدید برای الگوریتم خوشه ای هوشمند پیشنهادی خود استفاده می کنیم.

الگوریتم های خوشه بندی وزنی متعددی، برای گروهی از گره های سیار در خوشه ها و انتخاب گره ای که سرخوشه نامیده می شود در [۱۹] پیشنهاد و بررسی شده اند.

با توجه به پارامترهای سیستم که برای محاسبه وزن هر گره استفاده می شوند، این روشها مبتنی بر سیار بودن محض[۶] ۱و[۱۲]، مبتنی بر انرژی محض[۱۷] ۲ و یا مبتنی بر ترکیبی[۵] ۳ و [۸] و [۱۳]، طبقه بندی می شوند.