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

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

a method to simplify patterns in web services compositions and select optimal probabilistic composition

one of the most challenging issues in web services is their composition, which is presented as a graph to show the interaction between services. each node in such a graph is called an abstract web service with a specific function and undetermined quality attributes. for each abstract service, there is a set of candidate services with the same function but different quality attributes. selecting a candidate web service for each abstract service leading to an optimal combination is an np-hard problem; hence, heuristic algorithms should be used to resolve it. several methods have been proposed to select optimal web service composition, but most of them don’t support the probability structure. among others, one method supports a probability structure that is not scalable for large graphs, is constraint based, and analyzes each path of the graph separately. this paper presents an integrated scalable multi-objective approach for analyzing graph where not only two new patterns of nested loops and parallel loops are dealt with but also performance is improved by representing a method for simplifying web-service compositions. in this method, to select optimal web services and to respect scalability, evolutionary algorithms nsgaii and speaii are used. in the proposed method, first in conditional graphs, each path is traversed according to its probability and then nsgaii is used to determine the best path in the graph and find better solutions. the proposed method was compared with the best known method; results showed the proposed method enjoys 30% improvement in reliability and 121 milliseconds in response time.