بخشی از مقاله
چکیده
روشهای متفاوتی برای تخصیص منابع در محاسبات ابری وجود دارد. از جمله روشهای تخصیص منابع میتوان روشهای اقتصادی را نام برد. روشهای مبتنی بر حراج مزایایی نسبت به روشهای قیمت ثابت دارند. یکی از روشهای مناسب برای تخصیص منابع در محاسبات ابری، حراج ترکیبی دوطرفه میباشد. تخصیص منابع در حراج ترکیبی دوطرفه شامل دو فاز تعیین برنده و تخصیص منابع میشود. روش پیشنهادی الگوریتم رقابت استعماری را برای تعیین برندهی حراج در تخصیص منابع مبتنی بر حراج ترکیبی دوطرفه پیادهسازی میکند. نتایج تجربی نشان میدهد الگوریتم پیشنهادی ما نسبت به الگوریتم ژنتیک همگراتر است و تعداد کاربران برنده در الگوریتم پیشنهادی ما بیشتر است ولی تعداد ارائهدهندگان برنده در الگوریتم ژنتیک بیشتر از الگوریتم پیشنهادی ما میباشد.
کلمات کلیدی:محاسبات ابری، حراج ترکیبی دوطرفه، تخصیص منابع، تعیین برنده، رقابت استعماری، ژنتیک
-1 مقدمه
در واقع محاسبات ابری ویژگیهایی دارد که کسبوکار را برای شرکتها و سازمانها جذاب میکند: بدون پیش پرداخت بودن، کاهش هزینههای عملیاتی، مقیاسپذیری بالا، دسترسی آسان، کاهش ریسکهای کسبوکار و هزینههای تعمیر و نگهداری.[1] تخصیص منابع، از مسائل مداوم و جداییناپذیر محاسبات ابری و مدیریت مراکز داده میباشد .[2] ارائه دهندگان کنونی ابر، از مکانیزم های قیمت ثابت برای تخصیص منابع به کاربران استفاده میکنند اما مکانیزم های مبتنی بر قیمت ثابت، تخصیصهای کارآمد را فراهم نمیکنند و درآمد ارائهدهندگان را به حداکثر نمیرسانند .[3] مدلهای اقتصادی برای تخصیص منابع مبتنی بر ابر، بخصوص برای تنظیم عرضه و تقاضای منبع، مناسبتر هستند.[4]
یک جایگزین بهتر، استفاده از مکانیزم های مبتنی بر حراج برای تخصیص منابع است. مناسبترین مکانیزم ها برای تخصیص منابع و قیمتگذاری در محاسبات ابری، حراج ترکیبی میباشد .[3] برای تبادل عادلانه بین ارائهدهندگان منابع - فروشندگان - و کاربران - خریداران - ، قیمت فقط باید به شرایط عرضه و تقاضا بستگی داشته باشد. حراج دوطرفه باعث میشود، مزایای خاصی شامل طرف ارائهدهندگان و یا طرف کاربران نشود. پس استفاده از حراج ترکیبی دوطرفه برای تخصیص منابع در محاسبات ابری، مدل مناسبی است.
حراج ترکیبی دوطرفه شامل دو مرحله میباشد: ابتدا، تعیین مجموعه برنده در میان پیشنهادات حراج با حل یک مدل بهینهسازی که هدفش به حداکثر رساندن رفاه اجتماعی - با تفاوت قائل شدن بین پرداخت خریداران و درآمد کل فروشندگان - است؛ دوم، تخصیص کامل منابع و قیمتگذاری میان مجموعه برندهی تعیین شده است. اما این روند حراج دارای مشکلاتی میباشد. مسئلهی تعیین برنده ، زمانی که تعداد داوطلبان و منابع در یک مقیاس خاص باشد، یک مسئلهی NP-hard است و نمیتوان برنده را در یک زمان چندجملهای یافت.[5] پس الگوریتمهای اکتشافی، مسئله را از چشماندازی علمی به خوبی حل میکنند. بخشهای مقاله شامل: محاسبات ابری، تخصیص منابع، حراج ترکیبی دوطرفه، کارهای مربوطه و روش پیشنهادی میباشد.
-2 محاسبات ابری
ایدهی اصلی محاسبات ابری جدید نیست. جان مک کارتی در سال 1960 پیشبینی کرد که محاسبات، امکاناتی را به عنوان ابزارهای کمکی برای عموم مردم فراهم میآورد . بدیهی است که، فقدان تعریف استاندارد از محاسبات ابری، شک و تردید و سردرگمی را ایجاد کرد. به همین دلیل اخراًی در استانداردسازی تعریف محاسبات ابری کار شده است.[1] بسیاری از محققان تلاش کردند که محاسبات ابری را از جنبههای کاربردی آن تعریف کنند ولی موفق نشدند و تعریف جامعی برای آن وجود ندارد. از میان تعاریف متفاوت، تعریف موسسهی ملی و استاندارد فناوری NIST در زیر آمده است: "محاسبات ابری مدلی است برای دسترسی راحت و برحسب تقاضای شبکه به مخزنی از منابع محاسباتی قابل پیکربندی مثل شبکهها،سرورها و سرویسها و ... که با کمترین تلاش مدیریتی و تعامل با ارائهدهندگان، به سرعت تأمین و آزاد میشوند ." [4]
-3 تخصیص منابع
تخصیص منبع، از مسائل مداوم و جداییناپذیر محاسبات ابری و مدیریت مراکز داده میباشد. سناریوی فرضی زیر را در نظر میگیریم. یک ارائهدهندهی سرویس ابر، سرورها را بر اساس نیاز به پردازنده، حافظه و دیسک به ماشینهای مجازی مستاجر ،تخصیص میدهد. در تاریخی دیگر، ارائهدهنده مدل را بهبود میبخشد و منابع پهنای باند شبکه را به ماشینهای مجازی مستاجر تخصیص میدهد. در این مرحله، استراتژی تخصیص منبع به محدودیتهایی مثل ظرفیت سرورها و ظرفیت پهنای باند شبکهی مراکز داده، بستگی دارد. در واقع تخصیص منبع شامل تقسیم و تخصیص منابع مشمول محدودیتهای خاص مثل تضمین عملکرد سرور،کارایی شبکه و تحمل خرابی میباشد .
اغلب این مسائل تخصیص منابع، مسائل NP-hard هستند. اغلب ابزارهای مدیریتی مراکز دادهی جدید از روشهای اکتشافی مناسب برای مسائل مستقل استفاده میکنند. برای مثال، تحقیقات اخیر مجازیسازی شبکه، از روشهای اکتشافی حریصانه برای تخصیص ماشینهای مجازی به مراکز داده استفاده میکنند. [2]مسئلهی تخصیص منبع میتواند به دو دسته تقسیم گردد: اول، پذیرش درخواستهای جدید و گرفتن ماشینهای مجازی برای آنها و قرار دادن این ماشینهای مجازی روی میزبانها. دوم،فرآیند تخصیص منابع به بهینهسازی تخصیصهای قبلی میپردازد. مسئلهی اول را میتوان یک مسئلهی کولهپشتی با اندازههای مختلف bin در نظر گرفت که الگوریتمهای متداول برای مسئلهی کولهپشتی عبارتند از Best [6] .fit,Worst fit ,First fit Next fit
-4 حراج ترکیبی دوطرفه
حراج ترکیبی دوطرفه یکی از عمومیترین روشهای حراج ترکیبی است که میتواند به عنوان مسئلهی بهینهسازی برای به حداکثر رساندن رفاه اجتماعی - پرداخت کلی خریداران و درآمد کلی فروشندگان - ، مدل شود. ممکن است چندین خریدار و چندین فروشنده برای بستهی کالاها وجود داشته باشد. شرکتکنندگان حراج، پیشنهاد خرید یا فروش بستهای از کالاها را ارسال میکنند. هدف از این حراج، به حداکثر رساندن کل مازاد تجاری است.هر بسته یا یک سفارش خرید است که تمام اقلام آن خریداری میشوند و یا یک سفارش فروش است که تمام اقلام آن به فروش میرسند. در این حراج پیشنهاد مهروموم شده است یعنی شرکتکنندگان در بازار یکدیگر را نمیشناسند. فقط حراج کننده به اطلاعات بستهها دسترسی دارد. [7]
-5 کارهای مربوطه
فوجی وارا و همکارانش در [5]، از حراج ترکیبی دوطرفه برای تخصیص منابع در محاسبات ابری استفاده کردهاند و در طرح پیشنهادیشان رزرو منابع جاری/آینده را در بازارهای نقطهای و جلویی، فراهم کردهاند. آنها برای تعیین برندهی حراج از برنامهنویسی خطی ترکیبی استفاده کردهاند که منجر شده است برنده در حراجهایی با مقیاس بزرگ در زمان طولانیتری تعیین شود. اشنایزلر و همکارانش در [8]، از حراج ترکیبی برای تخصیص منابع در محاسبات گرید استفاده کردهاند. آنها در این مقاله یک پروتکل تخصیص منابع مبتنی بر حراج ترکیبی را ارائه دادهاند که یک کاربر میتواند یک قیمت را برای هر ترکیبی از منابع موردنیاز برای اجرای وظایفش پیشنهاد دهد.
این پروتکل شامل یک الگوریتم تقریبی برای حل مسئلهی حراج ترکیبی است. روش ارائه شده شامل چهار مرحله میباشد: درخواست اطلاعات از بازار محلی حراج، تولید پیشنهادات، تعیین تخصیص و تخصیص وظایف به منابع برنده. آنها برای حل مسئلهی حراج ترکیبی از الگوریتم تقریبی استفاده کردهاند که یک تخصیص نزدیک به بهینه را مییابد و شامل دو مرحله میباشد. در مرحلهی اول یک تقریب با استفاده از برنامهنویسی خطی حراج ترکیبی تعیین میشود و در آخرین مرحله که مرحلهی تپه نوردی نام دارد، الگوریتم کیفیت راه حل را با اجرای دنبالهای از رویههای حریصانه در تخصیص بدست آمده از مرحلهی اول، بهبود میبخشد. نتایج نشان میدهد که مدل پیشنهادی آنها تاثیر اقتصادی بر عملکرد سیستم دارد.
قربانزاده و همکارانش در[9]، از الگوریتم ترکیبی ژنتیک برای حل مسئلهی تعیین برنده در حراج ترکیبی دوطرفه در گرید، استفاده کردهاند. آنها در این مقاله از دو نوع الگوریتم ترکیبی ژنتیک برای بهبود بهرهوری الگوریتم ژنتیک برای تعیین برنده استفاده کردهاند. آنها در این مقاله الگوریتم ژنتیک را با الگوریتم تبرید شبیهسازی شده و الگوریتم تپه نوردی برای حل مسئلهی تعیین برنده در حراج ترکیبی دوطرفه، ترکیب کردهاند. نتایج تجربی نشان میدهد که الگوریتمهای ترکیبی ژنتیک و تپه نوردی و ژنتیک و تبرید شبیهسازی نتایج بهتری نسبت به الگوریتم ژنتیک دارند.
-6 روش پیشنهادی
الگوریتم پیشنهادی ما برای حل مسئلهی تعیین برنده در حراج ترکیبی دوطرفه در محاسبات ابری، الگوریتم رقابت استعماری میباشد. الگوریتم رقابت استعماری برندههای حراج را مشخص میکند در واقع خروجی این الگوریتم مشخص میکند که کدام یک از بستههای پیشنهادی کاربران و ارائهدهندگان در حراج برنده شدهاند. جواب حاصل از این الگوریتم مشخص میکند که کدام یک از کاربران و ارائهدهندگان برنده شدهاند.
-1-6 بستههای پیشنهادی
مجموعه بستههای پیشنهادیB={B1'….'%j'…..%n} ، که n بسته n - مجموع تعداد متقاضیان و ارائهدهندگان است - وجود دارد. یک پیشنهاد Bj میتواند شامل چهار تاپل باشد - - Ej ,Rj ,Sj ,Pj که: که Eij واحد ECU درخواستی است اگر Eij >0 و یا واحد جزء عرضه شده است اگر Eij < 0 باشد. Rij واحد حافظهی درخواستی است اگر Rij> 0 و یا واحد جزء عرضه شده است اگر Rij <0 باشد Sij. واحد ذخیرهسازی درخواستی است اگر Sij>0 و یا واحد جزء عرضه شده است اگر Sij <0 باشد. Pij∈R، مقداری است که پیشنهاد کننده مشتاق به پرداخت آن است. اگر pij>0 باشد به عنوان پیشنهاد خرید در نظر گرفته میشود و اگر pij<0 باشد به عنوان پیشنهاد فروش در نظر گرفته میشود. لازم به ذکر است که یک بسته یا برنده میشود و تمام منابع آن تخصیص داده میشوند و یاصلاً برنده نمیشود.
-2-6اجزای الگوریتم رقابت استعماری
الگوریتم رقابت استعماری یا ICA روشی در حوزه محاسبات تکاملی است که به یافتن پاسخ بهینه مسائل مختلف بهینهسازی میپردازد. این الگوریتم با مدلسازی ریاضی فرایند تکامل اجتماعی - سیاسی، الگوریتمی برای حل مسائل ریاضی بهینهسازی ارائه میدهد. [10]
-1-2-6 کشور
در این الگوریتم تعداد بعد یک کشور برابر با تعداد بستههای پیشنهادی کاربران و ارائه دهندگان است .
