بخشی از مقاله
چکیده
با توسعهی تکنولوژی پردازش و ذخیرهسازی و موفقیت اینترنت، منابع محاسباتی ارزانتر، قویتر و دسترسپذیرتر از هر زمانی شدهاند. این تکنولوژی مدل محاسباتی جدیدی را تحقق بخشیده است که محاسبات ابری نام دارد که در آن منابع به عنوان خدمات به کاربران ارائه میشوند و کاربران میتوانند آنها را بر حسب تقاضا اجاره کنند و یا از اجاره در آورند. یکی از مشکلات محاسبات ابری مربوط به بهینه سازی منابع اختصاص یافته است.
در این مقاله یک روش تخصیص منابع مبتنی بر حراج ترکیبی دوطرفه پیشنهاد میشود. هدف از این پژوهش رسیدن به تخصیص منابعی اقتصادی است، به طوری که باعث افزایش سود کاربران و ارائه دهندگان شود. تخصیص منابع در حراج ترکیبی دوطرفه شامل دو فاز تعیین برنده و تخصیص منابع میشود. روش پیشنهادی الگوریتم رقابت استعماری را برای تعیین برنده و الگوریتم ژنتیک را برای تخصیص منابع و طرح پرداختی پیادهسازی میکند. از این پس الگوریتم پیشنهادی ما IG نامیده میشود. نتایج تجربی نشان میدهد الگوریتم پیشنهادی ما باعث افزایش سود ارائه دهندگان و کاربران میشود و در مورد افزایش دریافتی و سود ارائه دهندگان بهتر از سایر الگوریتمهای مورد مقایسه عمل میکند.
کلمات کلیدی محاسبات ابری ، حراج ترکیبی دوطرفه، تعیین برنده، رقابت استعماری، ژنتیک
مقدمه
در واقع محاسبات ابری ویژگیهایی دارد که کسبوکار را برای شرکتها و سازمانها جذاب میکند: بدون پیش پرداخت بودن، کاهش هزینههای عملیاتی، مقیاسپذیری بالا، دسترسی آسان، کاهش ریسکهای کسبوکار و هزینههای تعمیر و نگهداری. تخصیص منابع، از مسائل مداوم و جداییناپذیر محاسبات ابری و مدیریت مراکز داده میباشد . ارائه دهندگان کنونی ابر، از مکانیزم های قیمت ثابت برای تخصیص منابع به کاربران استفاده میکنند اما مکانیزم های مبتنی بر قیمت ثابت، تخصیصهای کارآمد را فراهم نمیکنند و درآمد ارائه دهندگان را به حداکثر نمیرسانند .
مدلهای اقتصادی برای تخصیص منابع مبتنی بر ابر، بخصوص برای تنظیم عرضه و تقاضای منبع، مناسبتر هستند.. یک جایگزین بهتر، استفاده از مکانیزم های مبتنی بر حراج برای تخصیص منابع است. مناسبترین مکانیزم ها برای تخصیص منابع و قیمتگذاری در محاسبات ابری، حراج ترکیبی میباشد. برای تبادل عادلانه بین ارائه دهندگان منابع - فروشندگان - و کاربران - خریداران - ، قیمت فقط باید به شرایط عرضه و تقاضا بستگی داشته باشد. حراج دوطرفه باعث میشود، مزایای خاصی شامل طرف ارائه دهندگان و یا طرف کاربران نشود. پس استفاده از حراج ترکیبی دوطرفه برای تخصیص منابع در محاسبات ابری، مدل مناسبی است.
حراج ترکیبی دوطرفه شامل دو مرحله میباشد: ابتدا، تعیین مجموعه برنده در میان پیشنهادات حراج با حل یک مدل بهینهسازی که هدفش به حداکثر رساندن رفاه اجتماعی - با تفاوت قائل شدن بین پرداخت خریداران و درآمد کل فروشندگان - است؛ دوم، تخصیص کامل منابع و قیمتگذاری میان مجموعه برندهی تعیین شده است. اما این روند حراج دارای مشکلاتی میباشد. مسئلهی تعیین برنده، زمانی که تعداد داوطلبان و منابع در یک مقیاس خاص باشد، یک مسئلهی NP-hard است و نمیتوان برنده را در یک زمان چند جملهای یافت.[4] پس الگوریتمهای اکتشافی، مسئله را از چشماندازی علمی به خوبی حل میکنند.
تخصیص منابع
تخصیص منبع،از مسائل مداوم و جداییناپذیر محاسبات ابری و مدیریت مراکز داده میباشد. در واقع تخصیص منبع شامل تقسیم و تخصیص منابع مشمول محدودیتهای خاص مثل تضمین عملکرد سرور،کارایی شبکه و تحمل خرابی میباشد. اغلب این مسائل تخصیص منابع، مسائل NP-hard هستند. اغلب ابزارهای مدیریتی مراکز دادهی جدید از روشهای اکتشافی مناسب برای مسائل مستقل استفاده میکنند . برای مثال، تحقیقات اخیر مجازیسازی شبکه، از روشهای اکتشافی حریصانه برای تخصیص ماشینهای مجازی به مراکز داده استفاده میکنند.
مسئلهی تخصیص منبع میتواند به دو دسته تقسیم گردد: اول، پذیرش درخواستهای جدید و گرفتن ماشینهای مجازی برای آنها و قرار دادن این ماشینهای مجازی روی میزبانها. دوم، فرآیند تخصیص منابع به بهینهسازی تخصیصهای قبلی میپردازد . مسئلهی اول را میتوان یک مسئلهی کولهپشتی با اندازههای مختلف bin در نظر گرفت که الگوریتمهای متداول برای مسئلهی کولهپشتی عبارتند از
کارهای مربوطه
از حراج ترکیبی دوطرفه برای تخصیص منابع در محاسبات ابری استفاده کردهاند و در طرح پیشنهادیشان رزرو منابع جاری/آینده را در بازارهای نقطهای و جلویی، فراهم کردهاند. آنها برای تعیین برندهی حراج از برنامهنویسی خطی ترکیبی استفاده کردهاند که منجر شده است برنده در حراجهایی با مقیاس بزرگ در زمان طولانیتری تعیین شود. اشنایزلر و همکارانش در [6]، از حراج ترکیبی برای تخصیص منابع در محاسبات گرید استفاده کردهاند.
آنها در این مقاله یک پروتکل تخصیص منابع مبتنی بر حراج ترکیبی را ارائه دادهاند که یک کاربر میتواند یک قیمت را برای هر ترکیبی از منابع مورد نیاز برای اجرای وظایفش پیشنهاد دهد. این پروتکل شامل یک الگوریتم تقریبی برای حل مسئلهی حراج ترکیبی است. روش ارائه شده شامل چهار مرحله میباشد: درخواست اطلاعات از بازار محلی حراج، تولید پیشنهادات، تعیین تخصیص و تخصیص وظایف به منابع برنده. آنها برای حل مسئلهی حراج ترکیبی از الگوریتم تقریبی استفاده کردهاند که یک تخصیص نزدیک به بهینه را مییابد و شامل دو مرحله میباشد.
در مرحلهی اول یک تقریب با استفاده از برنامهنویسی خطی حراج ترکیبی تعیین میشود و در آخرین مرحله که مرحلهی تپه نوردی نام دارد، الگوریتم کیفیت راهحل را با اجرای دنبالهای از رویههای حریصانه در تخصیص بدست آمده از مرحلهی اول، بهبود میبخشد. نتایج نشان میدهد که مدل پیشنهادی آنها تأثیر اقتصادی بر عملکرد سیستم دارد.
از الگوریتم ترکیبی ژنتیک برای حل مسئلهی تعیین برنده در حراج ترکیبی دوطرفه در گرید، استفاده کردهاند. آنها در این مقاله از دو نوع الگوریتم ترکیبی ژنتیک برای بهبود بهرهوری الگوریتم ژنتیک برای تعیین برنده استفاده کردهاند. آنها در این مقاله الگوریتم ژنتیک را با الگوریتم تبرید شبیهسازی شده و الگوریتم تپه نوردی برای حل مسئلهی تعیین برنده در حراج ترکیبی دوطرفه، ترکیب کردهاند. نتایج تجربی نشان میدهد که الگوریتمهای ترکیبی ژنتیک و تپه نوردی و ژنتیک و تبرید شبیهسازی نتایج بهتری نسبت به الگوریتم ژنتیک دارند.
روش پیشنهادی
الگوریتم پیشنهادی ما برای تخصیص منابع مبتنی بر حراج ترکیبی دوطرفه در محاسبات ابری، الگوریتم ترکیبی رقابت استعماری و ژنتیک میباشد. الگوریتم رقابت استعماری برندههای حراج را مشخص میکند در واقع خروجی این الگوریتم مشخص میکند که کدام یک از بستههای پیشنهادی کاربران و ارائهدهندگان در حراج برنده شدهاند. جواب حاصل از این الگوریتم فقط مشخص میکند که کدام یک از کاربران و ارائه دهندگان برنده شدهاند.
ما در مرحلهی نگاشت با استفاده از جواب حاصل از الگوریتم تعیین برنده و ماتریس بستههای پیشنهادی ، ماتریسی از برندهها را درست میکنیم . با استفاده از این ماتریسهای حاصل از نگاشت و کشور بهینهی حاصل از الگوریتم رقابت استعماری، میتوانیم کروموزومهای الگوریتم ژنتیک را بسازیم. در مرحلهی بعد باید مشخص شود که کدام منابع به کدامیک از کاربران تخصیص داده می شوند و با چه قیمتی؟ الگوریتم ژنتیک برای این مرحله استفاده میشود که در آن از طرح قیمتگذاری-k استفاده شده است. شمای الگوریتم پیشنهادی در شکل 1 آمده است.
اجزای الگوریتم رقابت استعماری
الگوریتم رقابت استعماری یا ICA روشی در حوزه محاسبات تکاملی است که به یافتن پاسخ بهینه مسائل مختلف بهینهسازی میپردازد. این الگوریتم با مدلسازی ریاضی فرایند تکامل اجتماعی سیاسی، الگوریتمی برای حل مسائل ریاضی بهینهسازی ارائه میدهد. در این الگوریتم تعداد بعد یک کشور برابر با تعداد بستههای پیشنهادی کاربران و ارائه دهندگان است. pi ∈{0,1} که مقدار 1 نشاندهندهی برنده شدن بستهی پیشنهادی است و مقدار 0 نشاندهندهی برنده نشدن بستهی پیشنهادی میباشد. در واقع هر کشور آرایه ای از صفر و یکها است.
تابع هزینه
هدف از انجام این پژوهش رسیدن به تخصیص منابعی اقتصادی است به طوری که در این تخصیص منابع سود طرفین در نظر گرفته شود. در واقع در حراج ترکیبی دوطرفه ارائه دهندهای برنده میشود که قیمت پیشنهادی کمتری داشته باشد - با توجه به منفی بودن قیمت پیشنهادی ارائه دهندگان، ارائه دهنده ای برنده است که قیمت پایینتری را پیشنهاد داده باشد - و همچنین کاربری در این حراج برنده است که قیمت پیشنهادی بالاتری داشته باشد. بنابراین کشوری بهتر است که مجموع قیمت پیشنهادی بستههای برندهی آن بیشتر است.
