استفاده از روش ژنتیک موازی برای یافتن زیرگراف کمینه موجود درشبکههای عامل/ حسگر بیسیم

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

کلیدواژه ها:

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