بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه روشي مبتني بر کيفيت سرويس براي ترکيب وب سرويس هاي معنايي در محاسبات ابري
چکيده
يکي از چالش هاي موجود در ابرهاي محاسباتي ترکيب وب سرويس است . در اين مقاله روشي براي ترکيب وب سرويس هاي معنايي بر اساس الگوريتم بازگشت به عقب طراحي شده است که مي تواند نيازهاي کيفيت خدمت (هزينه و زمان پاسخگويي ) کاربران را برآورده کند . اين روش از سه مرحله محدود کردن منبع وب سرويس ، ساختن درخت جستجو و بازگشت به عقب تشکيل مي شود . نتايج حاصل از اين روش با نتايج اعلام شده در مسابقات WSC٠٨ مقايسه شده است که روش پيشنهادي مي تواند ترکيب بهينه را همراه با ويژگي هاي کيفيت خدمت کاربر ارئه دهد . براي کم کردن هر چه بيشتر زمان اجراي روش پيشنهادي ، دو الگوريتم RET-QOS و RET_MQOS طراحي شده است . اين دو الگوريتم زمان اجرا را تا حد زيادي کاهش مي دهند.
واژه هاي کليدي ترکيب سرويس ، وب سرويس معنايي ، کيفيت خدمت ، ابرهاي محاسباتي .
١- مقدمه
يکي از جديدترين تکنولوژي هاي دنيا محاسبات ابري مي باشد .
با محاسبات ابري ، ديگر نيازي به کامپيوتر هاي با قدرت پردازش بالا و حافظه ي زياد نيست ، چون که همه چيز در ابر ذخيره ، اجرا ، و پردازش مي شود . يعني با محاسبات ابري ، هرچه تاکنون انجام مي شد ، بجاي برنامه هاي روميزي ، از طريق برنامه هاي تحت وب قابل انجام مي باشد .کاربران مي توانند به همه برنامه ها و اسناد خود از هر کامپيوتري که به اينترنت متصل مي باشد ، امکانات موجود بر روي ابرها بصورت سرويس ارائه مي شوند . از آنجائيکه يک سرويس به تنهايي نمي تواند پاسخگوي نياز مشتري باشد لازم است که عملکردهاي چندين سرويس وب با يکديگر ترکيب شود که حاصل سرويس مرکب ناميده مي شود . به فرايند ايجاد سرويس مرکب ، ترکيب سرويس مي گويند . ترکيب وب سرويس يکي از چالش هاي عمده در سال هاي اخير است . با افزايش تعداد تامين کنندگان وب سرويس ، تعداد زيادي وب سرويس با عملکرد يکسان و ويژگي هاي متفاوت مانند هزينه و زمان پاسخگويي در وب منتشر شده اند . براي پيدا کردن ترکيبي با بهترين کيفيت ، بررسي تمام حالاتي که مي توان اين سرويس ها را با هم ترکيب کرد بسيار زمان بر بوده و جزء مسائل حل نشدني محسوب مي شود . لذا در اين مقاله روشي کارا براي ترکيب وب سرويس هاي معنايي مبتني بر الگوريتم بازگشت به عقب ٣ پيشنهاد شده است که مي تواند پيچيدگي و عملکرد کار را بهبود دهد و نيازهاي کيفيت خدمت کاربران را بر آورده کند . روش پيشنهادي از سه مرحله محدود کردن زير مجموعه سرويس ها ، ساختن درخت جستجو ، هرس کردن شاخه هاي درخت و بازگشت به عقب تشکيل شده است . در ادامه مقاله ، در بخش دوم مروري بر کارهاي انجام شده ، بخش سوم به مسئله ترکيب وب سرويس و روش پيشنهادي پرداخته است ، بخش چهارم نتايج حاصل از اين تحقيق و در بخش آخر خلاصه و نتيجه گيري آورده شده است .
٢- مرور کارهاي گذشته
Yu و همکارانش در [١,٢] دو روش براي حل مسأله ترکيب وب سرويس ها پيشنهاد داده اند . روش هاي پيشنهادي اين پژوهشگران مبتني بر يک مدل ترتيبي بر اساس يک محدوديت مي باشد . روش اول در [١] مسأله به عنوان يک مسأله کوله پشتي در نظر گرفته مي شود که هر آيتم يک وزن و يک ارزش دارد و خود کوله پشتي هم يک گنجايش مشخص دارد. هر کدام از آيتم ها در واقع يک سرويس کانديد هستند که ارزش و وزن آنها به ترتيب همان ارزش و ويژگي هاي کيفي سرويس را نشان مي دهد .گنجايش کوله پشتي يک محدوديت سراسري مي باشد. الگوريتم براي انتخاب يک سرويس از مجموع سرويس هاي کانديد تلاش مي کند، بطوريکه ارزش مجموع سرويس ها با شرط در نظر گرفتن گنجايش کوله پشتي ماکزيمم شود . آنها براي حل مسأله از روش برنامه نويسي پويا استفاده کردند . استفاده از روش کوله پشتي در کارهاي ديگر نيز [٢,١٩] پيشنهاد شده است . که در [١٩] الگوريتم اکتشافي براي حل آن بکار برده شده است .روش دوم اين تحقيق يک تئوري گراف است . بطور کلي ايده اصلي در[٣] اين است که مسأله ترکيب سرويس هاي وب به صورت مسأله يافتن کوتاهترين مسير در گراف مدل شده است . که از الگوريتم هاي CBF4 و CSP5 استفاده شده است . در اين روش هر سرويس کانديد در هر کلاس يک گره را نشان مي دهد .CBF ، الگوريتمي براي پيمايش گراف است که مسئله کوتاهترين مسير از مبدأ واحد را براي گراف هاي وزن دار با روش جستجوي عمقي حل مي کند . و CSP ، که مشابه با الگوريتم CBF عمل مي کند با اين تفاوت که ابتدا همه ي گره هاي گراف بازديد مي شوند . در هر گره يک ليست سود بدست آمده براي مسيرهاي مختلف از گره مبدأ تا آخرين گره نگهداري مي شود . سپس در هر گره مسيري انتخاب مي شود که بالاترين سود را دارد . در [٢٤] نيز هر سرويس بصورت عامل در نظر گرفته مي شود سپس بصورت گراف مدل مي شوند و در گراف از الگوريتم DFS مسير اجرا پيدا مي شود و در ديتابيس سرويس ها ذخيره مي شود . به اين وسيله مسير بهنيه را پيدا مي کند . عيب اين روش در آ ن است که براي محيط هاي ساکن قابل اجرا است . و در[٢٥] ازالگوريتم *REV که توسط Chakrabarti معرفي شد را براي پيدا کردن کوچکترين مسير در گراف بکار مي گيرند
. در [٤] براي حل مسأله ترکيب سرويس ها از الگوريتم ژنتيک استفاده شده است . پژوهشگران در اين تحقيق اثر ويژگي هاي مختلف مثل نرخ جهش و تابع برازندگي را روي توانايي بهينه سازي الگوريتم ژنتيک بررسي کرده و نشان داده اند که ويژگي هاي مختلف در کارآيي اين روش تأثيرهاي متفاوتي را دارند. در [٤] نيز با اشاره به تأثير انتخاب تابع برازش و قوانين جهش ، خاطرنشان شده است که چگونگي انتخاب اين ويژگي ها مي تواند در بهبود سرعت همگرايي الگوريتم ژنتيک نقش بسزايي داشته باشد .در تحقيقي ديگر [٥] از يک بهينه ساز محلي براي اصلاح مقادير برازندگي افراد جمعيت استفاده شده که منجر به اصلاح مقادير بهينه نهايي مي شود. Confora و همکارانش نيز در [٦] از اين الگوريتم با يک تابع برازندگي پويا استفاده کرده اند . در اين روش ساختار ژنوم آرايه اي از اعداد صحيح مي باشد که هر مدخل آن به يک وب سرويس اشاره دارد. عملگر تقاطع در اينجا دو نقطه اي و عملگر جهش بصورت تصادفي عمل مي کند .اما در کاري ديگر [٧] ساختار ژنوم بصورت آرايه اي در نظر گرفته شده که هر مدخل آن به جاي اشاره به يک وب سرويس به يک ويژگي کيفي اشاره دارد .عملگر تقاطع در اينجا يک نقطه اي و عملگر جهش مانند روش قبل عمل مي کند. از ديگر تفاوتها ميان پياده سازي هاي مختلف الگوريتم ژنتيک بحث روش کدگذاري اين الگوريتم مي باشد .برخي ها مثل [٨,٩] روش رمزگذاري يک کروموزوم تک بعدي را اتخاذ کرده اند که البته در صورت افزايش تعداد وب سرويس هاي کانديد قابليت اطمينان کروموزوم ها در اين روش خيلي ضعيف مي باشد؛ از طرفي ديگر اين متد نمي تواند اطلاعات معنايي را نشان دهد .بنابراين برخي از روشها بر پايه الگوريتم رمزگذاري ماتريکس روابط بنا نهاده شده اند [١٠] ؛ گرچه اين روش نيز در موارد زيادي باعث توليد افراد غير مجاز بوده و راندمان را پايين مي آورد .در [١١] از رمزگذاري درختي که مي تواند روابط ترکيبهاي مختلف را مشخص کند صحبت شده است .اين مدل از طراحي دوباره در زمان اجرا حمايت مي کند. همانطور که بيان شد براي جلوگيري از افتادن الگوريتم دردام بهينه محلي کارهاي ترکيبي زيادي صورت گرفته است . از کارهاي انجام شده در اين زمينه مي توان به [١٢.١٣] اشاره کرد .در اينجا دو نوع متفاوت از الگوريتم سيستم ايمني در ترکيب با الگوريتم ژنتيک استفاده شده است که تفاوت آنها در روش رمزگذاري و فرايند جهش مي باشد در [٢٣] براي کم کردن زمان پاسخگويي اين الگوريتم از تابع بهينه کننده محلي استفاده مي کند بدين صورت که قبل از ورود سرويس به الگوريتم ويژگي هاي کيفيت خدمت آن بررسي مي شود اگر بهتر از انتخاب موجود نباشد اين سرويس رد مي شود . و زماني که قرار بود صرف اجراي اين سرويس باشد ذخيره مي شود .د[١٤] خاطر نشان کرده اند که انتخاب ويژگي هاي الگوريتم مورچگان تأثير زيادي در راندمان آن دارد بنابراين الگوريتم ژنتيک را براي قراردادن ويژگي هاي کليدي استفاده کرده واز يک الگوريتم ترکيبي بر پايه ژنتيک و کلوني مورچگان براي ترکيب وب سرويسها بهره برده اند .نتايج نشان داده که اين الگوريتم ترکيبي مي تواند سرعت انتخاب سرويسها را تسريع کندو باعث راندمان بهتر و همگرايي سريعتر شود.در [١٥] روشي بر مبناي ترکيب الگوريتم مورچگان و تئوري گراف پيشنهاد شده است .در [١٦] محققان عملگر آشفته را براي افزايش راندمان الگوريتم کلوني مورچگان به آن اضافه کرده اند .اين عملگر باعث شده تا الگوريتم از افتادن در دام بهينه محلي دور شود .در [١٧] مولفان پيشنهاد استفاده از چند نوع فرمون را با فرض اينکه بک نوع فرمون نمي تواند جوابگوي ويژگي هاي کيفي چندگانه باشد مطرح کرده اند. در [١٨] ترکيبي از الگوريتم مورچان با سيستم هاي چند عامله پيشنهاد شده است و هر سرويس را بصورت يک عامل در نظر گرفته است . در [٢٠] از الگوريتم پرندگان استفاده شده است که دورنمايي از مکانيزم هاي کوانتومي است و سعي دارد استراتژي جستجو را بر مبناي پتانسل دلتا و رفتار ذرات کوانتوم است تغيير مي دهد .
در[٢١] از مدل متحرک renold استفاده شده است . و با استفاده از چهار عمل متحرک مانند حرکت منسجم ، منظم ، تصادفي و دسته جمعي از گير افتادن در بهينه هاي محلي خودداري مي کنند . در نتيجه ايمني بيشتري براي بهينه هاي محلي دارد. در [٢٢] سه کار اساسي انجام شده است . سپس از طريق مدل شبکه اي petri براي ترکيب سرويس استفاده مي کند . اول اينکه يک روش يادگيري پسخورد سلسه مراتبي HRL براي توزيع و بهينه کردن ويژگي هاي کيفيت خدمت استفاده شده است . دوم مقدار ويژگي کيفيت خدمت در فرايند يادگيري از سرويس پر بازده يا سرويس که بيشترين استفاده را داشته است ، بدست مي آيد . و سوم ، عملکرد ترکيب يک وب سرويس پر بازده توسط قوانين کسب و کار براي بهينه سازي ويژگي هاي کيفيت خدمت بلادرنگ پيشنهاد مي شود . در [٢٦] از الگوريتم سيل آسا براي پيدا کردن ترکيب استفاده مي کند . و هنگاميکه يک سرويس از بين مي رود توانايي ترميم ترکيب را دارد .در [٢٧] ، از الگوي موازي ترکيب سرويس پيروي مي شود . پژوهشگران مدلي را براي پاسخ به اين سوال که چطور مي توان سرويس مرکب را بهينه کردن در حاليکه ويژگي هاي کيفيت خدمت آن از نوع منفي مانند هزينه که بايد کمينه شود و از نوع مثبت مانند ظرفيت که بايد بيشينه شود ؟ طراحي مي کنند. به اين صورت که مقدار ويژگي مثبت کيفيت خدمت بر مقدار ويژگي منفي آن تقسيم مي شود و آن را به عنوان درجه موازي بودن در نظر ميگيرد . در نهايت سرويس مرکبي انتخاب مي شود که درجه موازي بودن آن بشينه باشد . عيب اين روش اين است ، در صورتي که درجه موازي بودن خيلي کم باشد . در محيط هايي با مقياس بالا ، نرخ تأخير سرويس ها محدود است .
٣- مسئله ترکيب وب سرويس هاي معنايي
٣-١- معيارهاي کيفيت خدمت
در اين مقاله نيازهاي غير عملکردي کيفيت خدمت در نظر گرفته شده اند . اين نيازها عبارتند از : هزينه ٦، شهرت ٧، قابليت در دسترس بودن ٨ ، قابليت اعتماد٩وزمان پاسخگويي ١٠ که به دو دسته تقسيم مي شوند .ويژگي هاي منفي نظير هزينه و زمان پاسخگويي که بايد مينيمم شوند و ويژگي هاي مثبت نظير در دسترس بودن و قابليت اعتماد که بايد ماکزيمم شوند .
ما بردار را براي نشان دادن ويژگي هاي کيفيت خدمت سرويس s نشان مي دهيم که مقدار i – امين ويژگي کيفيت خدمت سرويس s را نشان مي دهد . از ميان ويژگي هاي کيفيت خدمت دو ويژگي هزينه و زمان پاسخگويي به عنوان ويژگي هاي کيفيت خدمت در نظر گرفته شده است . در اين مقاله براي هر ويژگي کيفيت خدمت ضرايبي بصورت زير در نظرگرفته شده است :
در اين صورت کاربر مي تواند بين نيازهاي کيفيت خدمت خود اولويت تعيين کند . ضريب هر کدام از ويژگي هاي کيفيت خدمت بيشتر باشد، آن ويژگي از اهميت بالاتري بر خوردار است . ويژگي هاي کيفيت خدمت ترکيب وب سرويس ها بر اساس الگوي ترتيبي ترکيب وب سرويس ها بصورت زير محاسبه مي شوند :
لذا مي توان بصورت زير نمايش داد :
هر سرويس مرکب از n سرويس تشکيل شده است . si.time به معني زمان پاسخگويي براي i- امين سرويس استفاده شده در سرويس مرکب است . و si.cost به معني هزينه i- امين سرويس استفاده شده در سرويس مرکب است .
٣-٢- وب سرويس معنايي
يک سرويس وب يک سرويس نرم افزاري است که با يک URL
شناخته شده و واسط هاي عمومي و انقيادهاي آن با استفاده از XML
توصيف و شناسايي مي شود . براي تعريف وب سرويس معنايي نياز به آنتولوژي ١١ داريم که بتوانيم تمام روابط و مفاهيم ١٢بين سرويس هارا تعريف کنيم . در سرويس معنايي بجاي استفاده از مقادير براي پارامتر هاي ورودي و خروجي از مفهوم هاي تعريف شده در آنتولوژي استفاده مي شود . هر سرويس از تعدادي مفهوم وروديS.in ،مفهوم خروجي s.out و پارامتر هاي کيفيت خدمت qr تشکيل شده است .
فرض کنيد O يک مجموعه از تمام مفاهيم تعريف شده آنتولوژي وب سرويس ها باشد . بر طبق [٢٨] اگر A,B ε O دو مفهوم باشند ، عملگر subsumes بين A و B به صورت زير تعريف مي شود :
اگر و فقط اگر A شامل B باشد (سپس B جزء A مي باشد ) . اگر هيچکدام (subsumes)A,B و (subsumes)B,A موجود نباشد ، A با B در ارتباط نيست .درصورتيکه هر دو موجود باشند آنگاه A=B .
در سيستم ترکيب وب سرويس هاي معنايي ، ما مجموعه اي از سرويس هاي S را داريم که در منبع سرويس تعريف شده اند و هر سرويس ε S s توسط مجموعه اي از پارامتر هاي ورودي و پارامتر هاي خروجي تعريف مي شوند که مفاهيم ورودي و مفاهيم خروجي به شکل نشان داده شده اند .
يک درخواست داده شده به ترکيب کننده معنايي شامل تعدادي مفهوم ورودي داده شده و تعدادي مفهوم خروجي خواسته شده مي باشد . ترکيب کننده معنايي بايد مجموعه اي از سرويس هايي را که ترکيب معتبري ارائه مي دهد بطوريکه تمام مفاهيم خروجي مورد تقاضا را پوشش دهد. بنابراين هر ترکيب معتبر بايد به شکل زير باشد:
يک ترکيب کننده سرويس بايد همه جايگشت هاي ممکن از سرويس ها را که در منبع سرويس تساوي بالا را برآورده مي کنند بررسي و امتحان کند .
٣-٣- روش پيشنهادي ترکيب وب سرويس هاي معنايي
روش پيشنهادي براي ترکيب وب سرويس هاي معنايي از سه مرحله محدود کردن زير مجموعه سرويس ها ، ساختن درخت جستجو و بازگشت به عقب تشکيل شده است . در مرحله اول الگوريتمي پيشنهاد شده است که کمک زيادي به بهبود زمان اجراي روش پيشنهادي مي کند بدين صورت که تعداد زيادي از ترکيبات نامعتبر از مجموعه ترکيبات ممکن حذف مي شود و ما را به ترکيب معتبر نزديکتر مي کند . در مرحله دوم الگوريتمي براي ساختن درخت جستجو پيشنهاد مي شود و با جستجوي عمقي در اين درخت به دنبال ترکيب معتبر مي گرديم و با برخورد به دوشرط افزايش طول ترکيب بيشتر مقدار طول بهينه و يا تهي بودن مجموعه سرويس کانديد جديد وارد مرحله سوم مي شويم . در اين مرحله ابتدا صحت ترکيب بدست آمده بررسي مي شود در صورتيکه ترکيب معتبر باشد همراه با مقدار ويژگي کيفيت خدمت آن ارائه مي شود . سپس يک گام به عقب برگشته و سرويس ديگري را براي گسترش درخت جستجو انتخاب مي کنيم . با دوشرط ذکر شده تا ابتداي درخت تمام سرويس ها را بررسي مي کنيم و ترکيب سرويس هاي معتبر همراه با مقدار ويژگي هاي کيفيت خدمت آن پيدا مي شوند.
٣-٣-١-محدود کردن مجموعه سرويس ها
در اين مرحله سعي مي کنيم از ميان تمام سرويس هاي موجود در منبع سرويس زير مجموعه اي که ما را به ترکيب نهايي نزديک تر خواهد کرد ، انتخاب نماييم .اين الگوريتم يک زير مجموعه از همه سرويس هاي موجود در منبع سرويس به عنوان مجموعه سرويس هاي کانديد براي شروع ترکيب سرويس معنايي انتخاب مي کند . براي هر سرويس s در مجموعه سرويس کانديد CS بايد شرط زير بر قرار باشد :
در واقع (٣) به اين معني است که بايد عملگر subsumes بين تمام مفاهيم پارامتر ورودي سرويس هاي انتخاب شده در مجموعه سرويس کانديد و R.in بر قرار باشد . در نتيجه همه ي سرويس هاي موجود در مجموعه ي سرويس کانديد s ε CS مي تواند شروع يک ترکيب سرويس معتبر باشد . بدين صورت منبع سرويس را محدود کرده ايم و نيازي نيست ترکيبات نامعتبر بررسي شوند .
٣-٣-٢- ساختن درخت جستجو
در ابتداي کار هر يک از سرويس هاي موجود در CS مي توانند براي شروع ترکيب بکار روند . از آنجايي که انتخاب سرويس ها بر اساس ترتيب قرار گرفتن آنهاست . در نتيجه براي شروع ابتدا اولين سرويس از CS به عنوان ريشه درخت انتخاب مي شود . سپس فرزندان ريشه درخت بر اساس (٤) توليد شده است و در سطح اول درخت قرار مي گيرند . فرزندان توليد شده براي هر سرويس به عنوان مجموعه سرويس کانديد جديد ’CS به شکل زير در نظر گرفته شده اند:
تساوي (٤) به اين معني اسـت کـه هـر سـرويس موجـود در مجموعـه سرويس کانديد فرصتي براي انتخاب شدن به عنوان سرويس بعـدي در يک ترکيب معتبر را دارد . انتخاب هر سرويس به ترتيب بر اساس مکان قرار گرفتن آن در مجموعه سرويس کانديد انجام مـي شـود . و شـانس انتخاب براي تمام سرويس ها يکسان است .
در مرحله بعد اولين سرويس در سطح اول از درخت انتخاب شده است و همه فرزندان قابل توليد آن ’CS در سطح دوم درخت تشکيل مي شوند. رابطه (٤) تا زماني که تمام مفاهيم موجود در R.out پيدا شده باشند ، به شرطي که طول ترکيب از مقدار طول بهينه گزارش شده در مسابقات WSC08 کمتر باشد ، تکرار مي شود و در هر تکرار يک سطح به درخت جستجو اضافه مي شود . سرويس هاي موجود در مجموعه جديد سرويس هاي کانديد بايد رابطه (٤) را حفظ کند . در صورتي که اين رابطه حفظ نشود ، مجموعه جديد سرويس هاي کانديد ’CS تهي است .
