دانلود رایگان مقاله رویکرد مبتنی بر ژنتیک برای ترکیب سرویس وب در محیط ابرهای توزیع شده

چکیده

     خدمات چندبخشی شده‌ی وب محور مستقل می‌تواند به خدمات کلی با ارزش‌افزوده از طریق فناوری‌های ترکیب‌کننده‌ی خدمات مرتبط گردند که این زمینه در معماری خدمات محور روی می‌دهد. با ظهور رایانش ابری، خدمات ابری بیشتری در بستر ابری می‌توانند عملکرد یکسانی را ارائه دهند ولی در عملکرد آن‌ها شاهد تغییراتی خواهیم بود. به‌علاوه، توسعه‌ی رایانش ابری می‌تواند یک‌روند توزیع یافته‌ی جغرافیایی را ارائه دهد که می‌تواند تاثیر شبکه را بر QoS مرتبط با خدمات ترکیبی وب مطرح سازد. درنتیجه یک مسئله‌ی مهم درزمینه‌ی تحقیق در رابطه با ترکیب خدمات است که چگونه می‌تواند بهترین خدمات کاندیدی را از مجموعه‌ای از خدمات متناظر در رابطه با توافق‌نامه‌ی سطح خدمات (SLA) انتخاب نمود. در این تحقیق، ما می‌توانیم مدلی ترکیبی ارائه دهید که هم QoS مرتبط با خدمات و محیط مرتبط با رایانش ابری را مدنظر قرار می‌دهد. ما همچنین یک‌روند ترکیبی خدمات وب محور را بر اساس الگوریتم ژنتیکی برای ابر توزیع یافته ازلحاظ جغرافیایی و فراهم‌کننده‌ی خدمات ارائه می‌دهیم که قصد دارند تا تخطی‌های مرتبط با SLA را به کمینه برسانند.

1. مقدمه

     رایانش ابری به‌عنوان یک فناوری انقلابی در حال تغییر زیست‌بوم فناوری اطلاعات (IT) است و همچنین این توانایی را دارد که بر تمامی جنبه‌های زندگی ما تاثیر گذارد. این زمینه نه‌تنها می‌تواند تغییرات فناوری محور را ارائه دهد بلکه می‌تواند تاثیر بسیار عمیق و جامعی را بر روی کاربردهای نهادهای کاری و مدل‌های کسب‌وکار داشته باشد. کاربردها می‌توانند به‌عنوان خدمات در یک محیط ابری در طول اینترنت ارائه شوند. امروزه کاربران به‌طور گسترده و عمده به استفاده از اینترنت عادت دارند تا بتوانند منابع نرم‌افزاری را در قالب خدمات وب محور به دست آورند. خدمات وب برنامه‌های خود توضیح‌دهنده‌ی نرم‌افزاری هستند که می‌توانند عملکردهای مشخص را به‌طور مستقل از فناوری‌های اجرایی پایه ارائه دهد. به‌واسطه‌ی ترکیب خدمات، خدمات دارای ارتباطات ضعیف که از یکدیگر مستقل هستند می‌توانند در بطن خدمات گسترده‌تری قرار گیرند، زیرا بستر اجزای خدماتی هرکدام باید در راستای یک دستورالعمل مشخص اجرایی گردد.

     معماری و ساختار شبکه برای ترکیب خدمات در محیط ابری در شکل 1 نشان داده‌شده است. معماری ابر دربرگیرنده‌ی سه لایه است: لایه‌ی نرم‌افزاری، لایه‌ی بستری و لایه‌ی زیر ساختاری. یک کاربر می‌تواند درخواست‌های ترکیبی را برای عامل میانجی بفرستد تا در بستر خدمات وب مورداستفاده قرار گیرند. لایه‌ی نرم‌افزاری دربرگیرنده‌ی کارگذاران و خدمات وب محور هستند. کارگذاران که می‌توانند مرکزگرا و یا توزیع یافته باشند، می‌توانند تمامی خدماتی را مدیریت کنند که توسط فراهم‌کننده‌های SaaS برای کاربران ارائه می‌شوند. خدمات وب محور می‌توانند برای کارگذاران ثبت شوند تا بتوانند خدمات کاندید را در رابطه با درخواست کاربر تائید کند. بر اساس خدمات ارائه‌شده‌ی کشف‌شده، موتورهای ترکیبی می‌تواند یک برنامه‌ی اجرایی را ارائه دهد که می‌تواند درخواست‌های QoS را عملیاتی کند. لایه‌ی زیر ساختاری می‌تواند تخصیص منابع واقعی را در رابطه با برنامه‌ی اجرایی تولیدشده در لایه‌ی بستری در برگیرد.

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

     رایانش ابری رفته‌رفته به‌عنوان یک الگوی رایانشی مهم قلمداد می‌شود. این بستر می‌تواند پایه و اساس قابل‌اطمینانی برای طیف گسترده از یک‌نهاد و کاربردهای مرتبط با کاربران باشد. تائو و همکارانش مسائل ترکیبی چندین منبع ابری را موردبررسی قراردادند که دراین‌بین می‌توان به خدمات نرم‌افزاری و سخت‌افزاری با چندین هدف و محدودیت اشاره داشت. با افزایش تعداد کاربران خدمات ابری در سراسر جهان، ارائه‌دهندگان اصلی خدمات ابری می‌توانند از پایگاه‌های داده‌ای توزیع یافته ازلحاظ جغرافیایی استفاده کنند تا بتوانند به آن دسته از کاربرانی که از آن‌ها فاصله‌ی زیادی دارند خدمات‌رسانی کنند. در عین زمان، خدمات ابری می‌توانند به رشد و توسعه‌ی سریع خود ادامه دهند. ظرفیت منابع مرتبط با یک پایگاه‌ها اطلاعاتی محدود است، درنتیجه‌ی توزیع بارکاری برای پایگاه‌های اطلاعاتی جهانی می‌تواند در فراهم آوردن خدمات پایدار مناسب باشد. خدمات وب محور بیشتری می‌توانند در پایگاه‌های داده‌ای توزیع‌شده ازلحاظ جغرافیایی قرار گیرند و همچنین می‌توان در سراسر جهان از آن‌ها بهره‌مند شد. پایگاه‌های داده‌ای ابری به شبکه‌های وابسته هستند تا بتوانند با یکدیگر و کاربران خدمات ابری ارتباط برقرار کنند. محیط شبکه می‌تواند بر عملکرد خدمات ترکیبی در طول پایگاه‌های داده‌ای تاثیر داشته باشد. QoS مربوط به شبکه می‌تواند پارامتر مهمی از ترکیب خدمات باشد. به‌منظور جلوگیری از تخطی‌های صورت گرفته درزمینه‌ی SLA، عملکرد شبکه می‌تواند توجه بسیار زیادی را در طول ترکیب خدمات به خود جلب کند. در تحقیقی که در این زمینه صورت گرفت، مؤلفان به بررسی ترکیب مسیر ارتباطی شبکه‌ی آگاه از QoS در شبکه‌های بزرگ‌مقیاس پرداختند. آن‌ها مسئله را تا حد مسئله‌ی k-MCOP (مسیر بهینه‌ی چندگانه‌ی محدودشده k) تقلیل دادند که در این روش از فرایند و فناوری توسعه‌ای و بسط جغرافیایی استفاده کردند و یک فرایند جستجو سریع را ارائه کردند. کلین و همکارانش یک مدل کلی را در رابطه با ترکیب خدمات وب محور در ابر ارائه دادند. مؤلفان که پایایی شبکه بین موقعیت‌های اختیاری خدمات و یا کاربران تخمین زدند و یک الگوریتم گزینشی وب محور ارائه دادند تا بتوانند آن دسته از خدماتی را پیدا کنند که منجر به این مانایی می‌گردد. هرچند در تحقیقی که انجام دادند آن‌ها تنها بر زمان واکنش تأکید داشتند. دیگر معیارهای QoS در این مقاله مدنظر قرار نگرفتند.

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

1. مشتریان

2. خدمات

3. خدمات

4. کارگذاران

5. سطح نرم افرازی

6. موتور ترکیب‌کننده

7. لایه‌ی بستری

8. پایگاه‌های داده‌ای

9. پایگاه‌های داده‌ای

10. پایگاه‌های داده‌ای

11. لایه‌ی زیر ساختار

     1.ما یک مدل ترکیبی واقع‌گرا بر اساس QoS ارائه دادیم که به ما اجازه می‌دهد تا بتوانیم محیط شبکه‌ی توزیع یافته را تشخیص دهیم. در مقایسه با تحقیق‌هایی که در این زمینه وجود دارند، مدل ما نه‌تنها خدمات QoS را مدنظر قرار می‌دهد بلکه QoS شبکه را نیز تحت نظر دارد. به‌علاوه مدلی که ما ارائه دادیم می‌تواند در بستر سناریوهایی از معیارهای چندگانه‌ی QoS قرار گیرد. این مدل نسبت به مدل‌های دیگر در تحقیق دیگری که در این زمینه ارائه‌شده‌اند قابل مقیاس بندی بیشتری است، مدل‌های قبلی بر معیارهای مشخصی از QoS تمرکز داشتد. ما همچنین روشی را برای محاسبه‌ی QoS مرتبط با خدمات ترکیبی در محیط ابری مطرح ساختیم.

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

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

     مابقی تحقیق کنونی به‌صورت زیر ساختار پیداکرده است: در بخش 2 ما مسئله را شرح می‌دهیم و مدل خود را برای بستر ترکیبی مطرح می‌سازیم. الگوریتم ژنتیکی که ما برای ترکیب خدمات ارائه داده‌ایم در بخش سوم مدنظر قرار می‌گیرد. در بخش 4 نتایج شبیه‌سازی و تحلیل عملکرد را نشان می‌دهیم. درنهایت، بخش 5 جمع‌بندی‌ها و دید کلی از زمینه‌های تحقیقات آتی را مطرح می‌سازد.

abstract

     Independent fine-grain web services can be integrated to a value-added coarse-grain service through service composition technologies in Service Oriented Architecture. With the advent of cloud computing, more and more web services in cloud may provide the same function but differ in performance. In addition, the development of cloud computing presents a geographically distributed manner, which elevates the impact of the network on the QoS of composited web services. Therefore, a significant research problem in service composition is how to select the best candidate service from a set of functionally equivalent services in terms of a service level agreement (SLA). In this paper, we propose a composition model that takes both QoS of services and cloud network environment into consideration. We also propose a web service composition approach based on genetic algorithm for geo-distributed cloud and service providers who want to minimize the SLA violations.

1. Introduction

     Cloud computing as a revolutionary technology is changing the entire IT ecosystem, and all aspects of our lives. It brings not only the technical change, but also profound influence on enterprise business applications and business models. Applications are delivered as services over the Internet in cloud environment [1]. Today, users are increasingly accustomed to using the Internet to gain software resources in the form of web services. Web services are self-describing software applications that provide certain functions independently from underlying implementation technologies [2,3]. Through service composition technologies, loosely-coupled services that are independent from each other can be integrated into complex and value-added composited services as long as each component service’s interface specification is subject to standard protocols.

     The system architecture for service composition in cloud environment is shown in Fig. 1. The cloud architecture includes three layers: software layer, platform layer and infrastructure layer. A user sends composition requests to brokers for utilizing composited web services. The software layer includes brokers and web services. The brokers, which can be centralized or distributed, manage all services that are offered to users by SaaS providers. Web services are registered to brokers by service providers in order to be discovered. The composition engine in platform layer communicates with the brokers to discover candidate services according to the user’s request. Based on the candidate services discovered, composition engine generates an execution plan which satisfies user’s QoS requirements. The infrastructure layer controls the actual resource allocation in terms of the execution plan generated in platform layer.

     QoS of web services refers to various nonfunctional characteristics such as response time, throughput, availability, and reliability [4]. Given an abstract representation of a composition request, a number of candidate services that provide the same function but differ in QoS can be obtained. Composition engine need to select the best candidate service from a set of functionally equivalent services according to the QoS. The work in [5,6] uses combinational model to find the optimal selection of component services. The authors use linear programming technique which is best suited for small scale problems. But with the increasing scale of problems, the complexity of this method increases exponentially. The work of Mahammad Alrifai et al. addresses the problem by combining global optimization with local selection methods [7,8]. By decomposing the optimization problem into small sub-problems, their approach is able to solve the problem in a distributed manner. The work in [9] extends the methods above. The authors present a strategy to further reduce the search space by examining only the subsets of candidate services since the number of candidate services for a composition may be too large. The above papers do not solve the composition problem in the cloud context. Thus, the distributed network environment is not considered in these papers.

    Cloud computing is an increasingly popular computing paradigm. It has become a reliable foundation for a wide array of enterprise and end-user applications [10]. Tao et al. investigate the composition problem of various cloud resource including software and hardware service with multiple objectives and constraints [11]. With the increasing number of cloud service users worldwide, major cloud service providers have been deploying and operating geographically dispersed datacenters to serve the globally distributed cloud users. At the same time, cloud services continue to grow rapidly. The resource capacity of a datacenter is limited, so distributing the load to global datacenters will be effective in providing stable services [12,13]. More and more web services are deployed on geo-distributed cloud datacenters and are offered all over the world. Cloud datacenters depend on networks to connect with each other and cloud users. Network environment has influence on the performance of composited services cross datacenters. QoS of network is a noticeable parameter of service composition. To avoid SLA violations, the network performance has been attracting more and more attention during service composition. In [14], the authors investigate the composition of QoS-aware network communication path across large scale multi-domain networks. They reduce the problem to k-MCOP (k multi-constrained optimal path) problem via domain graph expansion technique and developed a fast search heuristic. Klein et al. [15] propose a generic model towards network-aware service composition in the cloud. The authors estimate the network latency between arbitrary network locations of services or users and propose a network-aware selection algorithm to find services that will result in low latency. However, their work only focuses on response time. Other QoS criteria are not considered in this paper.

     In cloud environment, it is a challenge to search for an optimal and feasible composition path efficiently because the problem of service composition is an NP-complete problem. Cloud applications usually involve a large number of components and there are many candidate services for each component. With the increase of the number of components, the number of composition paths increases exponentially. So it is impractical to traverse all the composition paths in search space when the flow of composition is large. Furthermore, an important issue in cloud computing is the need for providers to guarantee the service level agreements (SLAs) established with users [13]. Cloud providers derive their profits from the margin between the operational cost of infrastructure and the revenue generated from users. Therefore, cloud providers are interested in maximizing profit and ensuring QoS for users to enhance their reputation in the marketplace. They are looking into solutions that can minimize the SLA violation. In this paper, we propose a new approach towards web service composition in geo-distributed cloud environment. Our main contributions can be summarized as follows:

     1. We first specify a realistic QoS-based composition model that allows us to consider the distributed network environment. Compared with most existing work, our model considers not only the QoS of services but also the QoS of network. In addition, our model can adapt to scenarios of multiple QoS criteria. It is more scalable than some related works [8,16] which only focus on certain QoS criterion. We also present an approach to calculate the QoS of composited service in cloud computing.

2. Some related methods use graph theory to solve the network-aware composition problem [17], which leads to the exponential growth of computation time. In order to reduce the complexity, a heuristic composition algorithm based on genetic algorithm to maximize user experience and minimize SLA violation is proposed to solve the problem in this work.

3. Unlike existing genetic algorithms, we use the notion of skyline to generate the initial population, which improve the solution quality and convergence speed. Simulation results show that our algorithm performs well in terms of solution feasibility, optimality and scalability with respect to different parameters.

     The rest of this paper is organized as follows: In Section 2, we introduce the problem and describe our model for composition. Our genetic-based algorithm for service composition is presented in Section 3. Section 4 shows the simulation results and performance analysis. Finally, Section 5 gives conclusions and an outlook on possible continuations of our work.

چکیده

1. مقدمه

2. مدل ترکیب

2.1. توافق‌نامه در سطح خدمات

2.2. خدمات وب بر اساس QoS

2.3. خدمات وب آگاه از موقعیت

1.4. خدمات ترکیب‌شده

1.5. بیان مسئله

3. الگوریتم ترکیب خدمات

3.1. طراحی الگوریتم

3.2. تابع برازش

3.3. کدگذاری

3.4. جمعیت اولیه

3.5. اپراتور گزینشی

3.6. اپراتور مقطعی

3.7. اپراتور جهش

4. شبیه‌سازی و ارزیابی

4.1. اجرای یک‌روند شبیه‌سازی

4.2. روش ارزیابی

4.3. ارزیابی مدل

4.4. میزان قابل‌اجرا

4.5. بهینه بودن و مقیاس‌پذیری

5. نتیجه‌گیری و تحقیقات آتی

abstract

1. Introduction

2. Composition model

2.1. Service level agreement

2.2. QoS-based web services

2.3. Location-aware web services

2.4. Composited service

2.5. Problem statement

3. Service composition algorithm

3.1. The design of algorithm

3.2. Fitness function

3.3. Encoding

3.4. Initial population

3.5. Selection operator

3.6. Crossover operator

3.7. Mutation operator

4. Simulation and evaluation

4.1. Simulation setup

4.2. Evaluation methodology

4.3. Model evaluation

4.4. Feasible rate

4.5. Optimality and scalability

5. Conclusion and future work

Acknowledgment

References