مکان‌یابی ماشین‌های مجازی با استفاده از الگوریتم رقابت استعماری

نویسندگان

1 دانشگاه محقق اردبیلی - دانشکده فنی مهندسی

2 دانشگاه علم و صنعت - دانشکده مهندسی کامپیوتر

چکیده

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

کلیدواژه‌ها


   [1]     Y. Gao, H. Guan, Z. Qi, Y. Hou, and L. Lio, “A multi-objective ant colony system algorithm for virtual machine placement in cloud computing,” Journal of Computer and System Sciences, vol. 79, no. 8, pp. 1230-1242, 2013.
   [2]     S. Chaisiri, B. Lee, and D. Niyato, “Optimal virtual machine placement across multiple cloud providers,” Proceedings of the IEEE Asia-Pacific Services Computing Conference, pp. 103-110, 2009.
   [3]     S. Agrawal, S. Bose, and S. Sundarrajan, “Grouping genetic algorithm for solving the server consolidation problem with conflicts,” Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, pp. 1-8, 2009.
   [4]     S. Srikantaiah, A. Kansal, and F. Zhao, “Energy aware consolidation for cloud computing,” Proceedings of Hot Power’08 Workshop on Power Aware Computing and Systems, 2008.
   [5]     E. Atashpaz-Gargari, and C. Lucas, “Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition,” IEEE Congress on Evolutionary Computation, pp. 4661-4667, 2007.
   [6]     M. Morshed, and A. Asgharpour, “Hybrid imperialist competitive-sequential quadratic programming (HIC-SQP) algorithm for solving economic load dispatch with incorporating stochastic wind power: a comparative study on heuristic optimization techniques,” Journal of Energy Conversion and Management, v ol. 84, pp. 30-40, 2014.
   [7]     S. Shamshirband, A. Amini, N. Anuar, M. Kiah, T. Wah, and S. Furnell, “D-FICCA: a density-based fuzzy imperialist competitive clustering algorithm for intrusion detection in wireless sensor networks,” Proceeding of Journal of measurement, vol. 10, 2014.
   [8]     A. Nourmohammadi, M. Zandieh, and R. Tavakkoli Moghaddam, “An imperialist competitive algorithm for multi-objective U-type assembly line design,” Journal of Computational Science, vol. 4, no. 5, pp. 393-400, 2013.
   [9]     Y. Zhang, Y. Wang, and Peng, “Improved imperialist competitive algorithm for constrained optimization,” Proceedings of International Forum on Computer Science-technology and Applications, Chongqing, vol. 1, pp. 204-207, 2009.
[10]     M. Goldansaz, F. Jolali, and A. Zahedi Anaraki, “A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop,” Applied Mathematical Modelling, vol. 37, no. 23, pp. 9603-9616, 2013.
[11]     E. Falkenauer, “A hybrid grouping genetic for bin packing algorithm,” Journal of Heuristics, vol. 2, pp. 5-30, 2004.
[12]     R. Gupta, S.K. Bose, and S. Sundarrajan., “A two stage heuristic algorithm for solving the server consolidation problem with item-item and bin-item incompatibility constraints,” Proceedings of IEEE International Conference on Service Computing, vol. 2, pp. 39-46, 2008.
[13]     M. Bichler, T. Setzer, and B. Speitkamp, “Capacity planning for virtualized servers,” Workshop on Information Technologies and Systems, pp. 1-6, 2006.
[14]     B. Speitkamp, and M. Bichler, “A mathematical programming approach for server consolidation problems in virtualized data centers,” IEEE Trans. Services Comput., vol. 3, no. 4, pp. 266-278, 2010.
[15]     H. Duan, and L. Huang, “Imperialist competitive algorithm optimized artificial neural networks for UCAV global path planning”, Neurocomputing, vol. 125, 11, pp. 166-171, 2014.
[16]     A. Verma, P. Ahuja, and A. Neogi, “pMapper: power and migration cost aware application placement in virtualized systems,” Proceedings of the 9th ACM/IFIP/USENIX International Conference on Middleware, pp. 243-264, 2008.
[17]     D.V. Veldhuizen, Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations, PhD thesis, Grad. School of Eng. of the Air Force Institute of Technology, Air University, 1999.
[18]     E. Feller, L. Rilling, and C. Morin, “Energy-aware ant colony based workload placement in clouds,” Proceedings of the IEEE/ACM International Conference on Grid Computing (GRID), pp. 26-33, 2011.
[19]     B. Li, J. Li, J. Huai, T. Wo, Q. Li, and L. Zhong, “Enacloud: an energy-saving application live placement approach for cloud computing environments,” Proceedings of the IEEE International Conference on Cloud Computing, pp. 17-24, 2009.
[20]     M. Dorigo, and L.M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, pp. 53-66, 1997.
[21]     J. Békési, G. Galambos, and H. Kellerer, “A 5/4 linear time bin packing algorithm,” J. Comput. System Sci., vol. 60, no. 1, pp. 145-160, 2000.
[22]     X. Fan, W. Weber, and L. Barroso, “Power provisioning for warehouse-sized computer,” Proceedings of the 34th Annual International Symposium on Computer Architecture, pp. 13-23, 2007.
[23]     M. Cardosa, M. Korupolu, and A. Singh, “Shares and utilities based power consolidation in virtualized server environments,” Proceedings of IFIP/IEEE Integrated Network Management (IM’09), pp. 327-334, 2009.
[24]     B. Li, J. Li, J. Huai, T. Wo, Q. Li, and L. Zhong, “Enacloud: an energy-saving application live placement approach for cloud computing environments,” Proceedings of the IEEE International Conference on Cloud Computing, pp. 17-24, 2009.
 
[25]     Y. Ajiro, and A. Tanaka, “Improving packing algorithms for server consolidation,” Proceedings of the International Conference for the Computer Measurement Group (CMG), Computer Measurement Group, 2007.
[26]     M.J. Sannella, Constraint Satisfaction and Debugging for Interactive User Interfaces, Ph.D. thesis, University of Washington, Seattle, WA, 1994.
[27]     B. Li, J. Li, J. Huai, T. Wo, Q. Li, and L. Zhong, “EnaCloud: an energy-saving application live placement approach for cloud computing environments,” Proceedings of the IEEE International Conference on Cloud Computing, pp. 17-24, 2009.
[28]      R.N. Calheiros, R. Ranjan, A. Beloglazov, C.A.F.D. Rose, and R. Buyya, “CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms,” Software: Practice and Experience (SPE), vol. 41, no. 1, pp. 23-50, 2011.