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

Abstract

یکی از چالش¬برانگیزترین موضوعات مرتبط با وب¬سرویس¬ها مساله ترکیب آن¬هاست که به صورت یک گراف برای نمایش تعامل بین سرویس¬ها ارائه می¬شود. هر گره از این گراف، یک وب¬سرویس انتزاعی نام دارد که وظیفه آن مشخص اما ویژگی¬های کیفی آن نامشخص است. برای هر سرویس انتزاعی، مجموعه¬ای از سرویس¬های کاندید با وظیفه یکسان اما ویژگی¬های کیفی متفاوت وجود دارد. جایگزینی یک وب¬سرویس کاندید برای هر سرویس انتزاعی به نحوی که یک ترکیب بهینه حاصل شود، یک مساله NP-hard است که در زمان چند جمله¬ای قابل حل نیست، از این رو برای حل آن از الگوریتم¬های هیوریستیک استفاده می¬شود. تاکنون روش¬های متعددی برای ترکیب بهینه وب¬سرویس ها ارائه شده است اما بیشتر این روش¬ها ساختار احتمالی را پشتیبانی نمی¬کنند. تنها یک روش ساختار احتمالی را پشتیبانی می¬کند که برای گراف های بزرگ مقیاس¬پذیر نیست، مبتنی بر قیود است و به تحلیل هر مسیر گراف به صورت جداگانه پرداخته است. این مقاله، رویکردی مقیاس¬پذیر و چندهدفه برای تحلیل گراف به صورت یکپارچه ارائه می-دهد که علاوه بر پوشش دو الگوی جدید حلقه¬های تودرتو و حلقه¬های موازی، با ارائه روشی جهت ساده¬سازی ترکیب وب¬سرویس¬ها موجب بهبود در کارایی نیز می¬شود. در این روش برای انتخاب بهینه وب¬سرویس¬ها و حفظ مقیاس¬پذیری، از الگوریتم¬های¬ تکاملی استفاده می¬شود. دو الگوریتم تکاملی منتخب، NSGAII و SPEAII هستند. در روش پیشنهادی ابتدا در گراف¬هایی با الگوی شرطی، هر مسیر بر حسب احتمال آن، چند بار می¬شود و سپس از الگوریتم NSGAII به منظور تعیین بهترین مسیر در گراف و یافتن راه¬حل-های بهتر استفاده می¬شود. در انتهای مقاله نتایج 8 روش آمده است که روش پیشنهادی در مقایسه با بهترین آنها، 30 درصد در پارامتر قابلیت اطمینان و 121 میلی ثانیه در زمان پاسخ بهبود داشته است.