• الصفحة الرئيسية
  • زمان‌بندی مبتنی بر اولویت وظایف با استفاده از سیستم فازی در محاسبات لبه سیار

شارک

عنوان URL للمقالة


رقم المقالة : 13980221179245 زيارة : 3296 الصفحة: 257 - 270

20.1001.1.16823745.1401.20.4.1.1

نوع المخطوط: المحکّمة

زمان‌بندی مبتنی بر اولویت وظایف با استفاده از سیستم فازی در محاسبات لبه سیار

الموضوعات :

انتصار حسینی 1 , محسن نیک رای 2 , شمس اله قنبری 3

1 - دانشگاه قم
2 - دانشگاه قم
3 - دانشگاه آزاد واحد آشتیان

تاريخ الإرسال : 06 السبت , رمضان, 1440 تاريخ التأكيد : 17 السبت , ذو الحجة, 1443 تاريخ الإصدار : 24 الأربعاء , رجب, 1444

الکلمات المفتاحية: محاسبات لبه سیار, زمان‌بندی, حریصانه, فازی, انرژی مصرفی, زمان انتظار,

ملخص المقالة :

محاسبات لبه سیار، تکنولوژی نوینی برای بهبود مشکل تأخیر، ظرفیت و منابع موجود در محیط محاسبات ابری سیار است. هدف اصلی در محاسبات لبه سیار، زمان‌بندی پویا و بارگذاری بهینه با کمترین هزینه در استفاده از منابع است. ما در این مقاله، از یک مدل سیستم سه‌سطحی دستگاه‌های سیار، لبه و ابر استاندارد، استفاده و دو الگوریتم بارگذاری و زمان‌بندی را پیشنهاد می‌کنیم. یک الگوریتم تصمیم‌گیری برای بارگذاری وظایف مبتنی بر الگوریتم کوله‌پشتی حریصانه در سمت دستگاه سیار است که وظایف با انرژی مصرفی بالا را برای بارگذاری انتخاب می‌کند و باعث صرفه‌جویی در انرژی مصرفی دستگاه می‌شود. همچنین در سمت MEC، یک الگوریتم زمان‌بندی پویا را با اولویت‌بندی وظایف مبتنی بر فازی جهت اولویت‌بندی و زمان‌بندی وظایف بر اساس دو معیار ارائه می‌کنیم. نتایج عددی نشان می‌دهند که کار ارائه‌شده در مقایسه با سایر روش‌ها باعث کاهش زمان انتظار وظایف برای اجرا، تأخیر و بار سیستم می‌شود و تعادل سیستم با کمترین تعداد منابع تأمین می‌گردد و سیستم ارائه‌شده، مصرف باتری را در دستگاه هوشمند تا حدود 90% کاهش می‌دهد. نتایج نشان می‌دهند که بیش از 92% وظایف با موفقیت در محیط لبه اجرا می‌شوند.

المصادر:

[1] J. Huang, C. C. Xing, and C. Wang, "Simultaneous wireless information and power transfer: technologies, applications, and research challenges," IEEE Communications Magazine, vol. 55, no. 11, pp. 26-32, Nov. 2017.
[2] K. Zhang, et al., "Energy-efficient offloading for mobile edge computing in 5g heterogeneous networks," IEEE Access, vol. 4, pp. 5896-5907, 2016.
[3] Y. Sun, J. Li, X. Fu, H. Wang, and H. Li, "Application research based on improved genetic algorithm in cloud task scheduling," Journal of Intelligent & Fuzzy Systems, vol. 38, no. 1, pp. 239-246, Jan. 2020.
[4] G. Li, J. Wang, J. Wu, and J. Song, "Data processing delay optimization in mobile edge computing," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 6897523, 9 pp., 2018.
[5] W. Zhimin, Z. Qinglin, X. Fangxin, D. Hongning, and Z. Yujun, "Detection performance of packet arrival under downclocking for mobile edge computing," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 9641712, 2018.
[6] W. Yu, et al., "A survey on the edge computing for the Internet of things," IEEE Access, vol. 6, pp. 6900-6919, 2018.
[7] Y. Guo, et al., "Distributed machine learning for multiuser mobile edge computing systems," IEEE J. of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 460-473, Apr. 2022.
[8] Z. Jiao, et al., "Energy-latency trade-off for energy-aware offloading in mobile edge computing networks," IEEE Internet of Things J., vol. 5, no. 4, pp. 2633-2645, Aug. 2018.
[9] A. Selvaraj and S. Sundararajan, "Evidence-based trust evaluation system for cloud services using fuzzy logic," International J. of Fuzzy Systems, vol. 19, no. 2, pp. 329-37, Apr. 2017.
[10] M. Fonseca, U. H. Bezerra, J. D. Brito, J. C. Leite, and M. H. Nascimento, "Pre-dispatch of load in thermoelectric power plants considering maintenance management using fuzzy logic," IEEE Access, vol. 6, pp. 41379-41390, 2018.
[11] K. Wang, K. Yang, and C. Magurawalage, "Joint energy minimization and resource allocation in C-RAN with mobile cloud," IEEE Trans. Cloud Comput, vol. 6, no. 3, pp. 331-346, Jul./ Sept. 2017.
[12] Y. Mao, J. Zhang, and K. B. Letaief, "Dynamic computation offloading for mobileedge computing with energy harvesting devices," IEEE J. Sel. Areas Commun, vol. 34, no. 12, pp. 3590-3605, Dec. 2016.
[13] H. Kchaou, Z. Kechaou, and A. M. Alimi, "Towards an offloading framework based on big data analytics in mobile cloud computing environments," Procedia Comput. Sci., vol. 53, pp. 292-297, 2015.
[14] S. Misra and S. Sarkar, "Theoretical modeling of fog computing: a green computing paradigm to support IoT applications," IET Networks, vol. 5, no. 2, pp. 23-29, Mar. 2016.
[15] L. Yang, J. Cao, H. Cheng, and Y. Ji, "Multi-user computation partitioning for latencysensitive mobile cloud applications," IEEE Trans.Computers, vol. 64, no. 8, pp. 2253-2266, Aug. 2015.
[16] G. Shuaishuai, W. Dalei, Z. Haixia, and Y. Dongfeng, "Resource modeling and scheduling for mobile edge computing: a service provider's perspective," IEEE Access, vol. 6, pp. 35611-35623, 2018.
[17] Z. Wenchen, et al., "Markov approximation for task offloading and computation scaling in mobile edge computing," Mobile Information Systems, vol. 2019, Article ID: 8172698, 2019.
[18] T. Chia Wei, T. Fan Hsun, Y. Yao Tsung, L. Chien Chang, and C. LiDer, "Task scheduling for edge computing with agile VNFs on-demand service model toward 5G and beyond," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 7802797, 2018.
[19] Y. Yibo, M. Yongkui, X. Wei, G. Xuemai, and Z. Honglin, "Joint optimization of energy consumption and packet scheduling for mobile edge computing in cyber-physical networks," IEEE Access, vol. 6, pp. 15576-15586, 2018.
[20] W. Yuan, et al., "NOMA-Assisted multi-access mobile edge computing: a joint optimization of computation offloading and time allocation," IEEE Trans. on Vehicular Technology, vol. 67, no. 12, pp. 12244-12258, Dec. 2018.
[21] A. Aghababaeipour and S. Ghanbari, " A new adaptive energy-aware job scheduling in cloud computing," in Proc. Int. Conf. on Soft Computing and Data Mining, pp. 308-317, Senai, Malaysia, 5-7 Feb. 2018.
[22] S. Ghanbari and M. Othman, "Time cheating in divisible load scheduling: sensitivity analysis, results and open problems," Procedia Computer Science, pp. 935-943, vol. 1, no. 125, Jan. 2018.
[23] Y. Changyan, C. Jun, and S. Zhou, "A multi-user mobile computation offloading and transmission scheduling mechanism for delay sensitive application," IEEE Trans. on Mobile Computing, vol. 19, no. 2, pp. 99-110, Jan. 2018.
[24] D. Yueyue, X. Du, M. Sabita, and Y. Zhang, "Joint computation offloading and user association in multi-task mobile edge computing," IEEE Trans. on Vehicular Technology, vol. 67, no. 12, pp. 12313-12325, Dec. 2018.
[25] X. Chen, J. Lei, L. Wenzhong, and F. Xiaoming, "Efficient multi-user computation offloading for mobile-edge cloud computing," IEEE/ACM Trans. on Networking, vol. 24, no. 5, pp. 2795-2808, Oct. 2016.
[26] C. Ying, Z. Ning, Z. Yongchao, and C. Xin, "Dynamic computation offloading in edge computing for the Internet of Things," IEEE Internet of Things J., vol. 6, no. 3, pp. 239-251, Jun. 2019.
[27] N. Zhaolong, D. Peiran, K. Xiangjie, and X. Feng, "A cooperative partial computation offloading scheme for mobile edge computing enabled Internet of Things," IEEE Internet of Things J., vol. 6, no. 3, pp. 4804-4814, Jun. 2019.
[28] Y. Zhang, D. Niyato, and P. Wang, "Offloading in mobile cloudlet systems with intermittent connectivity," IEEE Trans. Mobile Computing, vol. 14, no. 12, pp. 2516-2529, Dec. 2015.
[29] L. Tianze, W. Muqing, Z. Min, and L. Wenxing, "An overhead optimizing task scheduling strategy for ad hoc based mobile edge computing," IEEE Access, vol. 5, pp. 5609-5622, 2017.
[30] R. Morabito and N. Beijar, "Enabling data processing at the network edge through lightweight visualization technologies," in Proc. of the IEEE Int. Conf. on Sensing, Communication, and Networking, SECON Workshops, 6 pp., London, UK, Jun. 2016.
[31] H. Wang, J. Gong, Y. Zhuang, H. Shen, and J. Lach, "Health edge: task scheduling for edge computing with health emergency and human behavior consideration in smart homes," in Proc. of the IEEE Int. Conf. on Big Data, pp. 1213-1222, Shenzhen, China, 7-9 Aug. 2017.
[32] P. Samal and P. Mishra, "Analysis of variants in round robin algorithms for load balancing in cloud computing," International J. of Computer Science and Information Technologies, vol. 4, no. 3, pp. 416-419, 2013.
[33] C. You, Y. Mao, J. Zhang, and K. Huang, "Energy-efficient offloading for mobile edge computing," In Wiley 5G Ref: The Essential 5G Reference Online, 2016.
[34] J. Maozhu, W. Hua, S. Lijun, L. Yuxue, and Z. Yucheng, "Man-machine dialog system optimization based on cloud computing," Personal and Ubiquitous Computing, vol. 22, no. 5-6, pp. 937-942, Oct. 2018.
[35] J. Wang, J. Peng, Y. Wei, D. Liu, and F. Jielin, "Adaptive application offloading decision and transmission scheduling for mobile cloud computing," in Proc. IEEE Int. Conf. on Communications, ICC’26, 7 pp., Kuala Lumpur, Malaysia, 22-27 May 2016.
[36] F. Scott, K. Carlenri, Y. Di, B. George, and K. Mellow, "An analysis of vehicular wireless channel communication via queueing theory model," in Proc. IEEE Int. Conf. on Communications, pp. 1736-1741, Sydney, Australia, 10-14 Jun. 2014.
[37] L. Tong, Y. Li, and W. Gao, "A hierarchical edge cloud architecture for mobile computing," in Proc. 35th Annual IEEE Int. Conf. on Computer Communications, IEEE INFOCOM’16, 9 pp., San Francisco, CA, USA, 10-14 Apr. 2016.
[38] X. Chen, L. Pu, L. Gao, W. Wu, and D. Wu., "Exploiting massive D2D collaboration for energy-efficient mobile edge computing," IEEE Wireless Communications, vol. 24, no. 4, pp. 64-71, Aug. 2017.
[39] A. Salehan, H. Deldari, and S. Abrishami, "An online context-aware mechanism for computation offloading in ubiquitous and mobile cloud environments," The J. of Supercomputing, vol. 75, no. 7, pp. 1-41, Ju.. 2019.
[40] M. Al-Zinati, R. Alrashdan, B. Al-Duwairi, and M. Aloqaily, "A reorganizing biosurveillance framework based on fog and mobile edge computing," Multimedia Tools and Applications, vol. 80, no. 11, pp. 16805-16825, 2021.
[41] S. Deng, et al., "Burst load evacuation based on dispatching and scheduling in distributed edge networks," IEEE Trans. on Parallel and Distributed Systems, vol. 32, no. 8, pp. 1918-1932, Aug. 2021.
[42] F. Jazayeri, A. Shahidinejad, and M. Ghobaei-Arani, "Autonomous computation offloading and auto-scaling the in the mobile fog computing: a deep reinforcement learning-based approach," J. of Ambient Intelligence and Humanized Computing, vol. 12, pp. 8265-8284, 2021.
[43] J. C. Guevara and N. L. da Fonseca, "Task scheduling in cloud-fog computing systems," Peer-to-Peer Networking and Applications, vol. 14, no. 2, pp. 962-977, 2021.
[44] T. D. Lee, B. M. Lee, and W. Noh, "Hierarchical cloud computing architecture for contextaware IoT services," IEEE Trans. Consume Electron, vol. 64, no. 2, pp. 222-230, May2018.
[45] Y. Shi, S. Chen, and X. Xu, "MAGA: a mobility-aware computation offloading decision for distributed mobile cloud computing," IEEE Internet of Things, vol. 5, no. 1, pp. 164-174, Feb. 2018.
[46] M. Goudarzi, M. Zamani, and A. Toroghi Haghighat, "A genetic-based decision algorithm for multisite computation offloading in mobile cloud computing," Int J. Commun Syst, vol. 30, no. 10, Article ID: e3241, Jul. 2017.
[47] A. Raneetha, H. Moshe, O. Binyamin, and Z. Ilze, "Strategic bidding in a discrete accumulating priority queue," Operations Research Letters, vol. 47, no. 3, pp. 162-167, May 2019.
[48] J. Yuan and Y. Li, "Solving binary multi-objective knapsack problems with novel greedy strategy," Memetic Comp., vol. 13, pp. 447-458, 2021.
[49] V. Kumar and K. Dinesh, "Transitive blocks and their applications in fuzzy interconnection networks," Fuzzy Sets and Systems, vol. 352, pp. 142-160, Dec. 2018.
[50] Y. Mao, J. Zhang, S. H. Song, and K. B. Letaief, "Power-delay tradeoff in multi-user mobile-edge computing systems," in Proc. IEEE Global Communication. Conf., GLOBECOM’16, 6 pp., Washington, DC, USA, 4-8 Dec. 2016.
[51] R. Gopi, S. T. Suganthi, R. Rajadevi, et al., "An enhanced green cloud based queue management (GCQM) system to optimize energy consumption in mobile edge computing," Wireless Pers Commun, vol. 117, pp. 3397-3419, 2021.
[52] P. Zou, O. Ozel, and S. Subramaniam, "Optimizing information freshness through computation-transmission tradeoff and queue management in edge computing," IEEE/ACM Trans. on Networking, vol. 29, no. 2, pp. 949-963, Apr. 2021.
نص كامل:
معرفي يک روش جديد خوشه‌يابي خودکار

نشریه مهندسی برق و مهندسی كامپیوتر ایران، ب- مهندسی کامپیوتر، سال 20، شماره 4، زمستان 1401  257

مقاله پژوهشی

زمان‌بندی مبتنی بر اولویت وظایف با استفاده از 
سیستم فازی در محاسبات لبه سیار

انتصار حسینی، محسن نیک‌رأی و شمس‌اله قنبری

 

 

1 

چكیده: محاسبات لبه سیار، تکنولوژی نوینی برای بهبود مشکل تأخیر، ظرفیت و منابع موجود در محیط محاسبات ابری سیار است. هدف اصلی در محاسبات لبه سیار، زمان‌بندی پویا و بارگذاری بهینه با کمترین هزینه در استفاده از منابع است. ما در این مقاله، از یک مدل سیستم سه‌سطحی دستگاه‌های سیار، لبه و ابر استاندارد، استفاده و دو الگوریتم بارگذاری و زمان‌بندی را پیشنهاد می‌کنیم. یک الگوریتم تصمیم‌گیری برای بارگذاری وظایف مبتنی بر الگوریتم کوله‌پشتی حریصانه در سمت دستگاه سیار است که وظایف با انرژی مصرفی بالا را برای بارگذاری انتخاب می‌کند و باعث صرفه‌جویی در انرژی مصرفی دستگاه می‌شود. همچنین در سمت MEC، یک الگوریتم زمان‌بندی پویا را با اولویت‌بندی وظایف مبتنی بر فازی جهت اولویت‌بندی و زمان‌بندی وظایف بر اساس دو معیار ارائه می‌کنیم. نتایج عددی نشان می‌دهند که کار ارائه‌شده در مقایسه با سایر روش‌ها باعث کاهش زمان انتظار وظایف برای اجرا، تأخیر و بار سیستم می‌شود و تعادل سیستم با کمترین تعداد منابع تأمین می‌گردد و سیستم ارائه‌شده، مصرف باتری را در دستگاه هوشمند تا حدود 90% کاهش می‌دهد. نتایج نشان می‌دهند که بیش از 92% وظایف با موفقیت در محیط لبه اجرا می‌شوند.

 

کلیدواژه: محاسبات لبه سیار، زمان‌بندی، حریصانه، فازی، انرژی مصرفی، زمان انتظار.

1-       مقدمه

امروزه دستگاه‌های تلفن همراه، نقش بسزایی در زندگی مردم ایفا می‌کنند. با توسعه شبکه تلفن همراه و اینترنت اشیا 2(IoT)، محاسبات، ذخیره‌سازی و مدیریت شبکه با چالش‌های بسیاری مواجه شده‌اند. این چالش‌ها شامل تأخیرهای زیاد، محدودیت فضای ذخیره‌سازی، دستگاه‌ها با منابع محدود، لزوم سرویس‌دهی متناوب بدون وقفه و امنیت بیشتر می‌باشند که با معماری مبتنی بر ابر به طور کامل حل نمی‌شوند [1] و [2]. دستگاه‌های سیار مانند تلفن‌های هوشمند، تبلت و دستگاه‌های پوشیدنی، از جمله دستگاه‌های فعال در IoT هستند که در آن بسیاری از حسگرها به سایر دستگاه‌ها در خانه‌ها، اداره‌ها و جاده‌ها تحت شبکه‌های پیشرفته امروزی متصل می‌شوند. نسل جدید شبکه سیستم‌های تلفن همراه به نام نسل پنجم 3G)5( با هدف تسریع در توسعه برنامه‌های کاربردی دستگاه‌های سیار به وجود آمدند. شبکه‌های G5 بر استفاده از تکنولوژی‌های نوین از جمله محاسبات ابری سیار 4(MCC) و محاسبات لبه سیار 5(MEC) برای دستیابی به انعطاف‌پذیری بیشتر و قابلیت پردازش بی‌درنگ تأکید می‌کنند [3] و [4]. برخی از برنامه‌های کاربردی دستگاه‌های سیار مانند واقعیت افزوده، بازی و تشخیص چهره، نیاز به توان محاسباتی بالایی دارند و به این دلیل در هنگام پردازش، انرژی زیادی مصرف می‌کنند [5]. از طرفی، تقسیم منابع در محاسبات ابری به دلیل دسترسی دور کاربر باعث تأخیر در زمان پاسخ می‌شود و به این دلیل نیاز به وجود یک فناوری جدید برای سرعت‌بخشیدن و افزایش کارایی در برنامه‌های حساس به تأخیر و بی‌درنگ احساس می‌شود. از سال 2016، مؤسسه استانداردهای ارتباطات اروپا 6(ETSI) یک چارچوب و معماری مرجع MEC تولید کرد. این معماری از خدماتی مانند اجرای برنامه­های پویا و انتشار اطلاعات شبکه رادیویی به صورت بلادرنگ پشتیبانی می­کند. [6]. محاسبات لبه بالقوه برای رفع محدودیت‌های زمان پاسخ، محدودیت عمر باتری، صرفه‌جویی در هزینه پهنای باند و همچنین ایمنی داده‌ها و حفظ حریم خصوصی است که در نزدیکی کاربر، خدمات خود را ارائه می‌دهد [7]. با توجه به منابع محدود دستگاه‌های هوشمند، صرفه‌جویی در منابع و انرژی موضوع مهمی است. محاسبات لبه به کاربران تلفن همراه اجازه می‌دهد که وظایف خود را در لبه به صورت پویا انجام دهند و بنابراین از این طریق، هزینه استفاده از منابع دستگاه کاهش می‌یابد. هدف MEC، ارتباط میلیون‌ها برنامه بی‌درنگ و حساس به تأخیر در لبه شبکه است، به طوری که به دنبال این کار، هزینه مصرف انرژی در دستگاه سیار کمتر شود، وظایف بی‌درنگ با سرعت بیشتری اجرا شوند و فضای ذخیره‌سازی داده و پردازش برنامه‌ها افزایش یابد. استفاده از این بستر علاوه بر مزیت‌هایی که به همراه دارد با چالش‌هایی نیز روبه‌رو است. انتخاب وظایف مناسب برای ارسال به MEC نیاز به دقت بالایی دارد زیرا در بعضی از موارد، ارسال مجموعه‌ای از وظایف در شبکه، هزینه بیشتری را از لحاظ انرژی مصرفی در باتری یا پهنای باند شبکه به دستگاه سیار اعمال می‌کند. چالش مطرح دیگری در این زمینه در سمت MEC وجود دارد و آن این است که وظایف رسیده، بدون دانش قبلی وارد این لایه می‌شوند و یا حداقل، یافتن اطلاعات کافی درباره معیارهای اولویت‌بندی کار زمان‌بری است که در زمان‌بندی وظایف اهمیت زیادی دارد. اولویت‌بندی پویای وظایف با هزینه مناسب بر اساس دانش فعلی موجود در شبکه از مسائل مهم در زمینه زمان‌بندی وظایف است [8].

در این مقاله از لایه لبه میان ابر و برنامه‌های کاربردی دستگاه‌های سیار و در سمت MEC از تعدادی ماشین مجازی7 با تعدادی پردازنده استفاده می‌کنیم. وظایف می‌توانند به صورت محلی در تلفن همراه، اجرا یا برای اجرا به MEC ارسال شوند [6]. وظایف دارای معیارهایی هستند که در این کار بر دو معیار انرژی مصرفی و زمان اجرا تأکید می‌کنیم [3]. در این مقاله، داشتن دانش در رابطه با این دو معیار یکی از گزینه‌های مهم در انتخاب وظایف برای ارسال و همین طور زمان‌بندی آنها است. انتخاب بهترین مجموعه از وظایف در سمت تلفن همراه برای ارسال به سمت MEC با استفاده از الگوریتم کوله‌پشتی حریصانه 8(GKOA) انجام شده که هدف آن، کاهش انرژی مصرفی در سمت دستگاه است. زمان‌بندی پویای وظایف در سمت MEC بر اساس روش فازی انجام می‌شود. در این الگوریتم، انرژی مصرفی و زمان اجرا دو ورودی روش فازی هستند که اولویت وظایف برای اجرا، خروجی این روش است. زمان‌بندی با اولویت‌بندی وظایف مبتنی بر فازی 9(FPTS) از منطق فازی برای تبدیل داده‌های ورودی به متغیرهای استنتاجی استفاده می‌کند. منطق فازی، یک روش مناسب برای اولویت‌بندی وظایف نسبت به روش‌های کلاسیک مانند خروج به ترتیب ورود 10(FIFO)، نوبت گردشی 11(RR) و ابتدا کوتاه‌ترین کار 12(SJF) است [9] و [10]. ما روش پیشنهادی خود را با این 3 روش برای پارامترهای مختلف از جمله زمان انتظار، سطح سرویس‌دهی و درصد تأخیر مقایسه می‌کنیم. در سمت لبه از یک سیاست تخصیص منابع بر اساس منابع فعال موجود در شبکه استفاده می‌کنیم که در صورت نبود منبع کافی مورد نیاز یکی از وظایف در شبکه، آن وظیفه برای اجرا به ابر ارسال می‌شود. به طور کلی هدف ما در این مقاله، ارسال مجموعه مناسب از وظایف از سمت دستگاه به لبه در جهت کاهش مصرف انرژی در دستگاه می‌باشد. همچنین هدف ما در سمت MEC، زمان‌بندی پویای وظایف با تخصیص کمترین منابع در جهت تحقق کاهش هزینه‌هاست. چنانچه یکی از کارها در لایه MEC اجرا نشد، برای اجرا به لایه بالاتر یعنی ابر ارسال می‌شود. اهداف اصلی این مقاله را می‌توان به صورت زیر خلاصه کرد:

-        ارائه GKOA به عنوان يك الگوريتم بارگذاري مطلوب در مصرف انرژي هر وظيفه و افزایش سرعت آن در سمت دستگاه سیار به منظور تقسیم‌بندی وظایف در جهت بهبود مصرف منابع دستگاه، هدف اولیه این کار است.

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

-        "تجزیه و تحلیل عددی نتایج ارزیابی برای پارامترهای زمان انتظار، احتمال تأخیر، سطح خدمات و سربار سیستم با حداقل تعداد پردازنده­ها، در روش زمانبندی پیشنهادی و روشهای خروج به ترتیب ورود، نوبت گردشی و ابتدا كوتاهترین كار مقایسه می­شود و میزان برتری 

عملکرد روش پیشنهادی نسبت به سایر روش­ها مشخص می­شود.

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

2-       کارهای پیشین

در این بخش، کارهای مربوط در زمینه بارگذاری و زمان‌بندی در محیط محاسبات سیار بررسی می‌گردد. کارهای مورد نظر در 3 محیط محاسبات سیار تقسیم می‌شوند: MEC، ابر لبه سیار و MCC. اهداف کارهای ارائه‌شده در این 3 محیط در 3 زیربخش زیر آمده است.

2-1 محاسبات سیار ابری

تعدادی از محققان در [11]، تعدادی از کلون‌ها را برای چندین دستگاه هوشمند در محیط ابر ایجاد کردند و وظایف از دستگاه سیار به ابر منتقل شد. در این صورت تعدادی کلون از یک دستگاه وجود دارد که در صورت آسیب‌دیدن یا گم‌شدن دستگاه، جایگزین برنامه‌های آن خواهد شد. مزیت دیگر این کار، مقابله با محدودیت سخت‌افزاری دستگاه هوشمند است. تجزیه و تحلیل داده‌های بزرگ با ترکیب MCC و Hadoop برای رفع محدودیت‌های ترافیکی و تأخیر نیز در [12] ارائه شد. نویسندگان در [13]، مسأله پارتیشن‌بندی محاسبات چندکاربره 13(MCPP) را برای به حداقل رساندن میانگین زمان‌بندی و زمان تأخیر مطالعه کردند. آنها از یک الگوریتم اکتشافی آفلاین یعنی جستجو در مدل 14(PRL) برای حل مشکل در برنامه‌های حساس به تأخیر استفاده نمودند. نویسندگان در [14]، یک چهارچوب در زمینه برنامه‌های سلامت به نام Health Edge را برای زمان‌بندی وظایف پیشنهاد دادند. محققان، اولویت‌های مختلف پردازش را برای وظایف مختلف بر اساس داده‌های سلامت جمع‌آوری‌شده تنظیم کردند. Health Edge کل زمان پردازش را تا آنجا که ممکن است کاهش می‌دهد. نویسندگان در [15]، الگوریتم RR را در محیط محاسبات ابری برای زمان‌بندی وظایف پیشنهاد دادند. نتایج الگوریتم RR نشان داد که زمان پاسخ و توازن بار در مقایسه با الگوریتم‌های دیگر بهینه‌تر است. یک کار دیگر، زمان‌بندی در ابر را با متوسط تأخیر در جریان ترافیکی و میانگین زمان انتظار در LTE به حداقل رساند [16]. نویسندگان در [17]، پیشنهاد یک برنامه زمان‌بندی و تصمیم‌گیری بارگذاری را بر اساس بهینه‌سازی Lyapunov برای صرفه‌جویی در زمان متوسط اجرا و متوسط مصرف انرژی ارائه دادند. در [18]، نویسندگان یک مدل تصمیم‌گیری بارگذاری محاسباتی را به نام 15MCOD برای به حداقل رساندن مصرف انرژی و زمان اجرای آن پیشنهاد کردند. محققان در [19]، یک مدل سلسله‌مراتبی جدید را در محاسبات ابر ارائه دادند که از لایه کاربر و لایه کنترل ابر با یک الگوریتم یادگیری ماشین برای زمان‌بندی استفاده می‌کند. نویسندگان در [20]، یک الگوریتم ژنتیک سازگار مبتنی بر رمزگذاری صحیح را برای تصمیم‌گیری در مورد بهبود بارگذاری تک‌وظیفه‌ای، چندوظیفه‌ای و چندین بخش پیشنهاد کردند. در [21]، روش تصمیم‌گیری مبتنی بر الگوریتم ژنتیک برای حل مسئله بارگذاری وظایف در محیط‌های چندسایتی پیشنهاد شد که باعث بهبود زمان اجرا و مصرف انرژی در MCC گردید. در [22]، یک مدل بهینه‌سازی چندهدفه مبتنی بر الگوریتم مرتب‌سازی ژنتیک برای به حداقل رساندن مصرف انرژی در محیط ابری برای مسئله تخصیص وظایف چندهدفه ارائه شد که در مقایسه با سایر الگوریتم‌های سنتی، زمان تکمیل و مصرف انرژی را به طور قابل توجهی کاهش داده است.

2-2 محاسبات لبه سیار

در [23]، گره‌های لبه به عنوان واحدهای جاده‌ای در شبکه‌های حمل و نقل برای ارائه خدمات IoT به وسیله OpenM2M به منظور بهبود تأخیر و ترافیک در شبکه توسعه داده شد. نویسندگان در [24]، یک الگوریتم بارگذاری را با استفاده از تکنیک‌های بهینه‌سازی تصادفی و بهینه‌سازی Lyapunov در لبه برای یک دستگاه پیشنهاد کردند. نتایج آنها نشان می‌دهد هزاران دستگاه IoT برای بارگذاری، انتخاب و باعث صرفه‌جویی در مصرف انرژی در دستگاه شدند. کار [25]، یک مثال از زمان‌بندی در لبه است که حداقل، تأخیر متوسط ترافیک را در پایین صفحه LTE کاهش می‌دهد. نویسندگان در [26]، مدل زمان‌بندی در ایستگاه پایه را با استفاده از تئوری شبکه صف متشکل از چندین نوع سرور ارائه دادند. کاربران در این مدل بر اساس اولویت، زمان‌بندی می‌شوند که این کار سرعت را در بارگذاری فایل‌های چندرسانه‌ای بهبود می‌بخشد. در [27]، یک سیستم چندسروری بر اساس تکنیک مارکوف پیشنهاد شده و یک دستگاه، وظایف محاسباتی را به سرورهای متعدد برای به حداقل رساندن زمان اجرا و مصرف انرژی دستگاه ارسال می‌کند. در [28]، یک مدل سرویس محاسباتی لبه بر اساس دروازه16 پیشنهاد شد که از طریق مجازی‌سازی باعث كاهش تأخیر، پهنای باند شبکه و افزایش سرعت انتقال در ابر شد. این مدل، عملکرد عملیاتی گره‌های لبه را بهبود بخشید. در [29]، یک مشکل بهینه‌سازی بر اساس اتخاذ یک احتمال ارتقا 17(PBP) پیشنهاد شد تا هزینه انرژی و تراکم بسته‌ها را بهبود بخشد. آنها از یک الگوریتم بهینه­سازی اكتشافی انبوه كریل برای به حداقل رساندن تراكم وظایف در صف استفاده كردند. محققان در [30]، پیشنهاد دسترسی چندگانه غیر متعامد 18(NOMA) را برای بهینه‌سازی کارایی انتقال رادیویی با دسترسی چندگانه پیشنهاد کردند. در این کار، یک ساختار لایه‌ای با استفاده از یک الگوریتم لایه‌ای کارآمد استفاده شد تا زمان تأخیر را برای تک‌کاربر دستگاه کاهش دهد. نویسندگان در [31]، یک مبادله بر اساس الگوریتم جستجوی تکرار بین مصرف انرژی و زمان تأخیر در شبکه MEC تک و چندسلولی برای کاهش این دو پارامتر پیشنهاد دادند. در [32]، چارچوب محاسبات لبه سیار برای برنامه‌های حساس به تأخیر مورد استفاده قرار گرفت. آنها یک مدل صف‌بندی، یعنی تخلیه محاسباتی چندکاربره 19(MUMCO) را برای بهبود هزینه و کنترل زمان‌بندی انتقال اعمال کردند. در [33]، یک الگوریتم مبتنی بر بازی ائتلافی برای بهبود تأخیر، قابلیت محاسبه و ذخیره‌سازی خدمات ناهمگن پیشنهاد شد. این میزان، تأخیر کاربران را به طور متوسط با مقدار 8/27% و 1/82% کاهش می‌دهد. نویسندگان در [34]، یک الگوریتم بارگذاری محاسباتی توزیع‌شده را بر اساس نظریه بازی برای بهبود عملکرد بارگذاری محاسبات برای اندازه کاربری بالا طراحی کردند. نویسندگان در [35]، پیشنهاد یک الگوریتم تخلیه پویای محاسباتی 20(DCOA) را به عنوان یک مشکل بهینه‌سازی برای به حداقل رساندن هزینه بارگذاری پیشنهاد کردند. در [36]، برنامه‌ریزی خطی صحیح تلفیقی 21(MILP) برای حل مشکل تخلیه محاسباتی چندکاربره پیشنهاد گردید. برای حل پیچیدگی محاسباتی فرموله‌شده، یک الگوریتم اختصاص منابع اکتشافی مکرر 22(IHRA) پیشنهاد شد تا تصمیمات تخلیه به صورت پویا با کمترین زمان اجرا و راندمان بالا انجام شوند. نویسندگان در [37]، پیشنهاد یک الگوریتم بهبود سربار زمان‌بندی چندمنظوره 23(OOMSG) را برای به حداقل رساندن سربار دستگاه و تکمیل زمان‌بندی کار ارائه کردند. نویسندگان در [38]، معماری محاسباتی لبه مبتنی بر شبکه تعریف نرم‌افزاری 24(SDN) را که زیرساختار نرم‌افزار 25(SDI) نامیده می‌شود، پیشنهاد دادند. آنها از OpenFlow و OpenStack برای مجازی‌سازی خدمات برای ساخت برنامه‌های هوشمند استفاده کردند. نویسندگان در [39]، مکانیسم تخلیه انرژی محاسباتی 26(EECO) را برای به حداقل رساندن مصرف انرژی پیشنهاد دادند.

نویسندگان در [40]، یک چارچوب نظارت زیستی را برای شناسایی و بومی‌سازی تهدیدات بیولوژیکی با پشتیبانی از محاسبات مه و لبه موبایل ارائه می‌کنند. گره‌های مه، داده‌های نظارتی را در سرورهای خود جمع می‌کنند و در افزایش سرعت اجرا و ذخیره‌سازی داده‌ها تأثیرگذار هستند. نویسندگان در [41]، ساختاری را برای یک محیط لبه ارائه کردند که شامل 3 لایه بود: لایه همکاری مهاجرت، لایه اشتراک محاسباتی و لایه محاسبات از راه دور. آنها الگوریتم‌های مسیریابی بهینه را برای توزیع وظایف 27(ORTD) و زمان‌بندی اولیه پیشنهاد کردند که مسیریابی بهینه را برای هر وظیفه و تخصیص منابع افزایش می‌دهد. همچنین ORTD، ترافیک کار و واریانس زمانی را برای هر کار و طول کارها کاهش داد. در [42]، یک برنامه نظارت هوشمند برای تخلیه وظایف در لبه یا ابر یا اجرای محلی ارائه گردید. از روش‌های یادگیری تقویتی عمیق 28(DRL) و مقیاس‌گذاری خودکار حریصانه و بارگذاری مبتنی بر یادگیری تقویت عمیق 29(GASDEO)، برای انتخاب بهترین گره و تخلیه آنها استفاده شد. نتیجه این بود که مصرف انرژی، هزینه کل اجرا، استفاده از شبکه و تأخیر به ترتیب 2، 4، 1 و 07/0 درصد نسبت به اجرای محلی، بهینه‌سازی شد. نویسندگان در [43]، دو روش زمان‌بندی را بر اساس برنامه­ریزی خطی اعداد صحیح ارائه كردند كه وظایف را در ابر و لبه به صورت پویا زمان‌بندی می­كرد. نتایج آنها نشان داد که الگوریتم آنها بهتر از روش‌های سنتی مانند RR کار می‌کند.

2-3 ابر لبه سیار

در [44]، مدل تصمیم‌گیری مارکوف برای به دست آوردن یک سیاست مطلوب برای به حداقل رساندن هزینه‌های محاسبات و تخلیه پیشنهاد شد. 

img0 

شکل 1:  مدل سیستم پیشنهادی.

 

نویسندگان در [45] از تئوری صف‌بندی با مدل M/M/m برای حرکت گره‌های لبه در شبکه وسیله نقلیه استفاده کردند که میانگین پاسخ در زمان بارگذاری را به حداقل می‌رساند. نویسندگان در [46]، یک الگوریتم زمان‌بندی را برای وظایف تصادفی در جهت بهبود زمان‌بندی و عملکرد 
با داشتن کامل در شیوه سلسله‌مراتبی پیشنهاد کردند. در [47]، سیستم جمع‌آوری دستگاه به دستگاه 30(D2D) در محاسبات ابر لبه‌های سیار پیشنهاد شد که مصرف انرژی و تخلیه موازی را بهبود می‌بخشد.

3-       روش پیشنهادی

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

3-1 مدل سیستم

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

جدول 1: نمادها.

 

تعریف

نماد

اندازه داده‌های ورودی پردازشی برنامه (به عنوان مثال، برنامه و داده‌ها)

img0 

اندازه پردازش‌ها (به عنوان مثال، تعداد چرخه پردازنده)

img0 

ظرفیت پردازنده در اجرای محلی

img0 

ظرفیت پردازنده در اجرا در لبه

img0 

انرژی مصرف‌شده دستگاه تلفن همراه

img0 

انرژی مصرف‌شده برای انتقال

img0 

انرژی در دسترس دستگاه تلفن همراه

img0 

توانایی محاسبه پردازنده توسط img0امین ماشین مجازی

img0 

وضعیت تصمیم‌گیری برای بارگذاری

img0 

مجموعه وظایف برای بارگذاری

img0 

مجموعه وظایف اجراشده

img0 

توانایی اجرای محلی یک وظیفه

img0 

توانایی اجرای یک وظیفه در لبه

img0 

تعداد ماشین‌های مجازی

img0 

تعداد وظایف موجود در img0امین ماشین مجازی

img0 

ظرفیت یک ماشین مجازی

img0 

شکاف زمانی

img0 

نرخ سرویس‌دهی

img0 

نرخ ورود به صف

img0 

تابع هزینه

img0 

پارامتر وزن در تابع هزینه

img0 

ظرفیت کوله‌پشتی

img0 

مقدار ارزش هر وظیفه

img0 

زمان آغاز برای انتخاب یک پردازنده برای اجرا

img0 

زمان انتها برای اجرای یک وظیفه در یک پردازنده

img0 

 

سطح ارسال می‌شوند. تصویر مدل سیستم پیشنهادی در شکل 1 نشان داده شده است.

3-2 فرمول‌بندی مسئله

این بخش، نحوه ارسال و اجرای وظایف به لایه لبه را نشان می‌دهد. برای سهولت فهم، تعریف نمادهای مهم استفاده‌شده روابط در جدول 1 ذکر گردیده است.

3-3 بارگذاری بهینه

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

 

[1] این مقاله در تاریخ 21 اردیبهشت ماه 1398 دریافت و در تاریخ 18 خرداد ماه 1401 بازنگری شد.

انتصار حسینی، دانشکده فنی و مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه قم، قم، ایران، (email: e.hoeesini@stu.qom.ac.ir).

محسن نیک‌رأی (نویسنده مسئول)، دانشکده فنی و مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه قم، قم، ایران، (email: m.nickray@qom.ac.ir).

شمس‌اله قنبری، دانشکده فنی و مهندسی کامپیوتر، واحد آشتیان، دانشگاه آزاد اسلامی، آشتیان، ایران، (email: myrshg@gmail.com).

[2] . Internet of Things

[3] . Fifth Generation

[4] . Mobile Cloud Computing

[5] . Mobile Edge Computing

[6] . European Telecommunications Standards Institute

[7] . Virtual Machine

[8] . Greedy Knapsack Offloading Algorithm

[9] . Fuzzy-Based Priority Task Scheduling

[10] . First in-First out

[11] . Round Robin

[12] . Shortest Job First

[13] . Multi-User Computation Partitioning Problem

[14] . Performance-Resource-Load

[15] . Multi-Criteria Offloading Decision

[16] . Gateway

[17] . Promoted by Probability

[18] . Non-Orthogonal Multiple Access

[19] . Multi-User Mobile Computation Offloading

[20] . Dynamic Computation Offloading Algorithm

[21] . Mixed Integer Linear Programming

[22] . Iterative Heuristic MEC Resource Allocation

[23] . Overhead-Optimizing Multi-Device Scheduling Game

[24] . Software-Defined Network

[25] . Software-Defined Infrastructure

[26] . Energy-Efficient Computation Offloading

[27] . Optimal Routing for Task Dispatching

[28] . Deep Reinforcement Learning

[29] . Greedy Auto-Scaling Deep Reinforcement Learning-Based Offloading

[30] . Device-to-Device

جدول 2: قوانین فازی بر اساس زمان اجرا و مصرف انرژی.

 

انرژی مصرفی

زمان اجرا

بسیار بالا

بالا

متوسط

پایین

بسیار پایین

بسیار بالا

بسیار بالا

بالا

متوسط

متوسط

پایین

بالا

بالا

بالا

متوسط

متوسط

پایین

متوسط

بالا

متوسط

متوسط

پایین

بسیار پایین

پایین

بالا

متوسط

پایین

بسیار پایین

بسیار پایین

بسیار پایین

متوسط

پایین

پایین

بسیار پایین

بسیار پایین

 

 

مجموع وزن وظایف، کمتر یا مساوی ظرفیت کوله‌پشتی الگوریتم ما است که با img0 نشان داده می‌شود. مقدار img0 برای هر وظیفه تعریف می‌شود به طوری که img0، وزن اشغال‌شده از هر وظیفه در کوله‌پشتی و img0 نیز ارزش هر وظیفه را نشان می‌دهد [48]. هدف الگوریتم GKOA در (1) و (2) نشان داده شده است

img0        (1)

img0        (2)

img0        (3)

در (3)، img0 ارزش وظیفه img0ام، آرایه img0، مجموعه ارزش تمام وظایف انتخاب‌شده برای بارگذاری و img0، سودمندی وظیفه img0ام را نشان می‌دهد.

3-4 زمان‌بندی پویا

برای سودمندی بهتر، زمان‌بندی بر اساس صف اولویت انجام می‌گردد که اولویت این وظایف از خروجی الگوریتم FPTS گرفته می‌شود. ما قصد داریم که درباره پارامترهای انرژی مصرفی و زمان اجرا برای افزایش قابلیت اطمینان برای محیط لبه مؤثر بحث کنیم. سیستم فازی ما از 
سه سطح تشکیل گردیده است: سطح فازی‌سازی، سطح استنتاج و سطح تخریب‌پذیری فازی. هر وظیفه با دو پارامتر به صورت وظیفه (پارامتر انرژی مصرفی و زمان اجرا)، ورودی سطح اول است. خروجی سطح فازی، ورودی سطح استنتاج است و نهایتاً خروجی سطح استنتاج، ورودی سطح سوم است. مقادیر ورودی در سطح اول تبدیل به داده‌های فازی می‌شوند. قوانین فازی در سطح دوم تعریف می‌شوند و نهایتاً سطح تخریب‌پذیری فازی، مجموعه‌های فازی را در فرم زبانی برای ارائه خروجی خالص تبدیل می‌کند. ورودی سیستم به صورت img0 نشان داده می‌شود که در واقع مجموعه وظایف با دو پارامتر زمان اجرا و انرژی مصرفی هستند و به ترتیب به صورت img0 و img0 می‌آیند. خروجی سیستم به فرم آرایه img0 نشان داده می‌شود، به طوری که img0 نشان‌دهنده آن است که این وظیفه، اولویت img0 دارد. به منظور تبدیل پارامترها به پارامترهای قابل استنتاج در سیستم فازی، قوانینی را در سطح استنتاج تعیین کرده که مجموعه‌ای از قوانین if…else هستند [49]. فازی‌کردن ورودی‌ها با استفاده از تابع عضویت گاوسی تعیین می‌گردد که در (4) نشان داده شده است

img0        (4)

در (4)، مقادیر img0 و img0 مرکزیت تابع و img0 مجموعه‌ای از دو ورودی انرژی مصرفی و زمان اجرا است که عرض img0امین مجموعه فازی img0 می‌باشد. خروجی تابع عضویت img0 است. توابع عضویت فازی گاوسی در ادبیات منطق فازی رایج هستند، زیرا آنها برای ارتباط بین سیستم‌های فازی و شبکه‌های عصبی با استفاده از تابع پایه شعاعی 1(RBF) مورد استفاده قرار می‌گیرند. قوانین استفاده‌شده در سیستم ما در جدول 2 نشان داده شده است. خروجی سیستم تعیین اولویت بر اساس ورودی‌های زمان اجرا و مصرف انرژی به عنوان خروجی سیستم فازی است. عناصر مقیاس در مجموعه img0، img0بسیار زیاد، زیاد، متوسط، پایین، بسیار پایینimg0 هستند و خروجی توسط ضرب مجموعه‌های فازی ارائه شده است. فرض می‌کنیم که دو مجموعه img0 و img0 را به عنوان ورودی داریم. ضرب مجموعه‌های فازی با img0 نشان داده شده که به صورت img0 می‌باشد. ماشین مجازی، اطلاعات و برنامه‌های کاربردی یک دستگاه هوشمند را زمانی که یک درخواست از طرف کاربر وارد می‌شود، کلون و در هر img0 برنامه کنترل، بهترین ماشین را برای سرویس‌دهی انتخاب می‌کند. این برنامه با اندازه محاسبات و داده بالا بهترین گزینه برای بارگذاری است. img0 برای توصیف اندازه داده ورودی برنامه استفاده می‌شود و img0 اندازه محاسبات را توصیف می‌کند. هر دو بردار به صورت مستقل و یکسان در هر شکاف زمانی img0 توزیع شده‌اند. زمان اجرا در لبه از روابط زیر محاسبه می‌شود

img0        (5)

img0        (6)

که در آن، مقدار img0 مدت زمانی است که طول می‌کشد تا یک درخواست در ماشین مجازی img0ام بررسی شود و img0 زمان پاسخ به اضافه زمان بارگذاری درخواست از ماشین مجازی است. مقدار img0، زمان انتقال وظیفه برای بارگذاری در ماشین مجازی در شکاف زمانی img0 و مقدار img0 در (6)، زمان اجرای وظیفه به صورت محلی در دستگاه است [44]. ما فرض می‌کنیم که img0، احتمال اجرای یک وظیفه به صورت محلی یا بارگذاری در لبه را نشان دهد. اگر مقدار img0 باشد، وظیفه به صورت محلی در دستگاه تلفن همراه اجرا می‌شود و در غیر این صورت، وظیفه 
با بارگذاری به لبه اجرا می‌شود. برای محاسبه انرژی مصرفی، مقدار img0 را تعریف می‌کنیم که انرژی مصرفی هنگام انتقال وظیفه و اجرا در ماشین مجازی را نشان می‌دهد [50]. در این رابطه img0 و img0 کل انرژی مصرفی از رابطه زیر به دست می‌آید

img0        (7)

در (7)، img0 مقدار انرژی مصرفی در دستگاه هوشمند است. وظایف با بیشترین زمان اجرا و مصرف انرژی بالا به لبه، منتقل می‌شوند و بهترین ماشین مجازی برای اجرای آنها انتخاب می‌گردد. ما چند پارامتر برای ارزیابی FPTS و مقایسه آن با سه روش زمان‌بندی دیگر در نظر می‌گیریم. نتیجه این مقادیر به عنوان پارامترهای ارزیابی در بخش 5 ارائه می‌شوند. در سمت لبه، هدف این است که بهترین عملکرد را با حداقل تعداد پردازنده‌ها داشته باشیم. زمان انتظار، زمان متوسط انتظار یک وظیفه در صف و احتمال تأخیر برابر با نسبت وظایفی است که به صف انتظار می‌پیوندند. ما یک مقدار آستانه برای سطح سرویس را در نظر می‌گیریم. حداقل تعداد پردازنده‌های مورد نیاز، مقداری است که به سطح سرویس برابر یا بالاتر از هدف آستانه برسیم. هنگامی که وظایف به لبه می‌رسند تا زمانی که اجرا شوند، زمان انتظاری را طی می‌کنند که از رابطه زیر محاسبه می‌شود

img0        (8)

که در (8)، مقادیر img0 و img0 به ترتیب زمان رسیدن یک وظیفه و زمان تخصیص یک پردازنده برای اجرا است. تعداد درخواست‌های رسیده، نشان‌دهنده تعداد درخواست‌های فرستاده‌شده از هر وظیفه است که این اندازه‌گیری می‌تواند میزان ترافیک شبکه را نشان دهد. نرخ درخواست پایین به این معنی است که ترافیک کمتری در شبکه وجود دارد و نرخ درخواست بالاتر به معنای ترافیک بیشتر در شبکه است [51]. نرخ درخواست ورود با img0 نشان داده می‌شود. زمانی که ترافیک در شبکه متناسب باشد، سیستم در حالت تعادل قرار دارد که فاکتور تعادل سیستم از رابطه زیر به دست می‌آید

img0        (9)

در (9)، img0 تعداد وظایف موجود در img0امین ماشین مجازی و مقدار img0 ظرفیت آن ماشین مجازی است. هنگامی که سیستم از حالت تعادل خارج می‌شود، بار سیستم افزایش می‌یابد. مقدار بار سیستم از رابطه زیر به دست می‌آید [52]

img0        (10)

که img0 تعداد ماشین‌های مجازی و img0 میانگین بار روی ماشین مجازی را نشان می‌دهد.

برای محاسبه تابع هزینه، یک مقدار را به عنوان پارامتر وزن در نظر می‌گیریم. پارامتر img0 به عنوان پارامتر وزن که در محدوده img0 قرار دارد تعریف می‌شود. اگر img0 باشد، مصرف انرژی در تصمیم‌گیری برای بارگذاری به لبه تأثیر ندارد. تابع هزینه برای مصرف انرژی و زمان اجرا به شرح زیر است

img0        (11)

4-       روش پیشنهادی

الگوریتم بارگذاری و زمان‌بندی بهینه در دو سمت دستگاه و لبه در این بخش ارائه می‌شوند. در سمت لبه، تخصیص منابع نیز انجام می‌شود. در نتیجه مدل ارائه‌شده ما با سه الگوریتم در سه مرحله ارائه می‌گردد:

-        الگوریتم بهینه بارگذاری GKOA در سمت دستگاه

-        الگوریتم زمان‌بندی پویای FPTS در سمت لبه

-        الگوریتم تخصیص منابع در سمت لبه

جزئیات الگوریتم‌ها به تفصیل در زیربخش‌های زیر آمده است. شکل 2 روند اجرای کار و تقسیم‌بندی وظایف را در روندنمایی ساده نشان می‌دهد.

4-1 الگوریتم بارگذاری به لبه GKOA

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

4-2 الگوریتم زمان‌بندی FPTS

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

1)        همه ماشین‌های مجازی مشغول هستند و img0 که در این صورت وظیفه به ابر مهاجرت می‌کند.

2)        بیش از یک ماشین مجازی فعال وجود دارد و img0 که بر اساس این سه پارامتر تخصیص انجام می‌شود.

مجموعه img0، ورودی این الگوریتم است که از خروجی الگوریتم GKOA می‌آید. همه وظایف به رابط FPTS، وارد و وظایف به ورودی‌های فازی بر اساس زمان اجرا و انرژی مصرفی تبدیل می‌شوند. پس از اولویت‌بندی وظایف، تخصیص منابع انجام می‌گردد که برای هر وظیفه، حداقل 
مقدار منابع لازم برای اجرا، نسبت به منابع موجود باید 1 یا بیشتر از 1 باشد. یعنی این روابط باید برقرار باشند: img0، img0 و 

[1] . Radial Basis Function

img0 

شکل 2:  روندنمای تقسیم‌بندی وظایف.

 

 

Input: img0

Output: img0

img0 

img0 

Calculate img0 according to "(3)"

Sort the tasks by decreasing order according to img0

for img0 do

     for img0 do

          if img0 then

               Swap img0

               Swap img0

               Swap img0

          end if

     end for

end for

for img0 to img0 do

     if img0 then

          img0

          img0

          img0

     else

          img0

          img0

          img0

     end if

end for

return img0

 

شکل 3:  الگوریتم بارگذاری GKOA.

 

img0. هر ماشین مجازی که یکی از این شرایط را داشته باشد،  انتخاب  و  نهایتاً  مجموعه  اشتراک  این  ماشین‌ها  به  عنوان  منابع 

Require: Work flow consisting offloading task as img0 and set of VM as img0

Ensure: Priority set of tasks img0 and img0

Ready task

for img0 to img0 do

     Fuzzification img0 according to completion time and energy

     consumption with gaussian membership function.

     Determine prioritize img0 based on fuzzy inference Rules

     Defuzzification the output.

     for img0 to img0 do

          if img0 then

               img0

          if img0 then

               img0

          if img0 then

               img0

          if img0 then

               Select img0 and assign to img0

          if img0 then

               Task migrates to Cloud

          Analyzes all task in work flow has been executed

          if All work flow did not execute in MEC then

               Task migrates to Cloud

     end for

end for

 

شکل 4:  الگوریتم زمان‌بندی FPTS.

 

img0 

شکل 5:  سیستم و ساختار مراحل کار پیشنهادی.

 

مناسبی برای تخصیص انتخاب می‌شود. در صورتی که هیچ منبع فعالی وجود نداشته باشد، وظایف به ابر ارسال می‌گردند.

5-       ارزیابی

در این بخش، جزئیات مدل سیستم، ارائه و نتایج عددی الگوریتم‌های استفاده‌شده، بررسی و تجزیه و تحلیل گردیده و در 2 بخش محیط ارزیابی و تجزیه و تحلیل نتایج آمده‌اند.

5-1 محیط ارزیابی

در این بخش، ارزیابی روش‌های بارگذاری، زمان‌بندی و تخصیص منابع در سیستم پیشنهادشده انجام می‌شود. ما عملکرد مدل پیشنهادی را با استفاده از یک کامپیوتر 10 هسته اینتل R در فرکانس 6/3 گیگاهرتز و RAM 8 گیگابایت ارزیابی می‌کنیم. سیستم عامل ویندوز 10 از نوع 64 بیت است. ما از دو ماشین مجازی به عنوان گره‌های لبه در لبه و یک دستگاه تلفن هوشمند استفاده می‌کنیم. هر ماشین با حافظه 2 مگابایتی و پردازنده 5 هسته کار می‌کند. کل هارددیسک 1 ترابایت است که هر ماشین مجازی با فضای 200 گیگابایت کار می‌کند. مدل دستگاه هوشمند سامسونگ F720 همراه با پردازنده 8 هسته با قدرت 2 گیگاهرتز و RAM 2815 مگابایت و رابط شبکه G4 و Wi-Fi است. سیستم عامل تلفن هوشمند از نوع نسخه اندروید 8 و ظرفیت باطری 3600 مگاهرتز است که در ابتدا مقدار باتری 90% بود. قدرت باتری غیر فعال، فعال 
و برای انتقال به ترتیب 79، 5/1 و 2/2 درصد است. ما از طریق شبکه Wi-Fi ارتباط میان لبه و دستگاه را ایجاد می‌کنیم. دو نوع برنامه کاربردی در دستگاه هوشمند اجرا می‌شوند. یک برنامه کاربردی وجود دارد که GKOA را اجرا می‌کند. کارها از برنامه‌های واقعیت افزوده و تشخیص چهره که هر کدام دارای دو معیار میزان انرژی مصرفی و زمان اجرا هستند، گرفته می‌شود. این معیارها از جمله انرژی مصرفی از توابع اندرویدی در کد اندروید برنامه محاسبه شده‌اند. برنامه کاربردی داخل دستگاه سیار، الگوریتم بارگذاری GKOA را اجرا و کارها را جهت اجرای محلی یا بارگذاری، دسته‌بندی می‌کند. کارها سپس به ماشین‌های مجازی که به عنوان سطح لبه در معماری ما در نظر گرفته شده‌اند، ارسال شده و به محض رسیدن به لبه، توسط برنامه‌ای که الگوریتم زمان‌بندی FPTS را اجرا می‌کند، اولویت‌بندی و به ترتیب اولویت بالا به پایین اجرا می‌شوند. پارامترهای ارزیابی از جمله زمان انتظار، تأخیر و نرخ سرویس‌دهی توسط دستگاه و ماشین مجازی مانیتورینگ می‌شوند و پس از جمع‌آوری، آنها را در نرم‌افزار R Studio با زبان کدنویسی C تجزیه و تحلیل می‌کنیم. بخش فازی این سیستم نیز در نرم‌افزار MATLAB انجام می‌شود. ما مقایسه نتایج تحقیقات خود را در نرم‌افزار R انجام دادیم. همچنین پارامترهای ارزیابی یک کار زمان‌بندی و اولویت‌بندی را با استفاده از کارهای تحقیقاتی پیشین استخراج کردیم و برای مقایسه با نتایج کار خود از جدول و نمودار در این نرم‌افزار کمک گرفتیم. رشد صعودی و نزولی نتایج تحقیقات ما با مقایسه عددی نیز در نمودارها مشخص است. در اکثر قسمت‌ها برای نتایج به دست آمده از جدول عددی نیز برای نشان‌دادن جزئی کار استفاده کردیم. لازم به ذکر است که از بخش نهایی کار که میزان استفاده از منابع دستگاه سیار را نشان می‌دهد، با استفاده از فراخوانی توابع اندرویدی، در کد برنامه اندروید، هنگام بارگذاری وظایف استفاده کردیم. در محاسبه تابع هزینه، مقدار img0 را تنظیم می‌کنیم. مقدار ظرفیت در الگوریتم GKOA با ظرفیت 200 و 500 تنظیم شده است. مراحل ساختار کلی کار ارائه‌شده برای روشنی و وضوح کار به طور کامل در شکل 5 آمده‌اند.

5-2 تجزیه و تحلیل نتایج

در این بخش، ابتدا مسئله بارگذاری را با توجه به الگوریتم شکل 3 ارزیابی می‌کنیم. وضعیت الگوریتم پیشنهادی GKOA نسبت به چند وضعیت دیگر بررسی می‌شود. همچنین این الگوریتم را برای موردی که در آن وظایف به صورت تصادفی انتخاب می‌شوند و مرتب نمی‌شوند، پیاده‌سازی می‌کنیم. سپس الگوریتم زمان‌بندی را در سمت لبه با توجه به الگوریتم شکل 4 تجزیه و تحلیل می‌کنیم و مدل پیشنهادی را با چندین الگوریتم معیار مقایسه می‌نماییم. FPTS با سه الگوریتم FCFS، RR و SJF مقایسه می‌شود. در FIFO وظایف به ترتیب ورود در صف، اجرا می‌شوند. در RR هر وظیفه در یک برش زمانی اختصاص داده شده، اجرا می‌شود. SJF یک صف زمان‌بندی است که وظایف با کمترین زمان اجرا را برای اجرای بعدی انتخاب می‌کند [9] و [10]. توابع عضوریت الگوریتم FPTS با توجه به مقادیر ورودی زمان اجرا و انرژی مصرفی در شکل 6 آمده‌اند. نهایتاً قسمت تخصیص منابع را بررسی کرده و تعیین می‌نماییم که چند درصد از وظایف به سمت ابر منتقل می‌شوند. الگوریتم GKOA پیشنهادشده را در دو حالت ظرفیت 200 و 500 با حالت اجرای تمام وظایف به صورت محلی، بارگذاری تمام وظایف به لبه و روش PBP [29] جایی  که img0 است، مقایسه  می‌کنیم.  شکل 7- الف مصرف  انرژی  را 

D:\hosseini\phd\mcc\persain1\1.png 

(الف)

D:\hosseini\phd\mcc\persain1\2.png 

(ب)

شکل 6:  تابع عضویت فازی مجموعه‌های ورودی.

 

برای این چهار حالت و تعداد مختلف کاربران نشان می‌دهد. مصرف انرژی در GKOA کمتر از PBP برای تعداد زیادی از کاربران است. همچنین مصرف انرژی برای بارگذاری تمام وظایف به لبه نسبت به اجرای تمام وظایف به صورت محلی پایین‌تر است. روش پیشنهادی با ظرفیت 500 برای حالتی که تعداد کاربران بالاتر از 20 است، بهترین مقدار را دارد. استفاده از GKOA کارآمدتر از بارگیری همه وظایف به لبه است و برای کاربران با تعداد زیاد بهتر عمل می‌کند. همان طور که در شکل 7- ب نشان داده شده است، در طرح PBP که در کار [29] ارائه گردید، میزان بار سیستم در هنگام افزایش تعداد کاربران افزایش می‌یابد. GKOA عملکرد بهتری را در سربار سیستم نسبت به سایر حالت‌ها ارائه می‌کند که بالاترین سربار سیستم برای اجرای محلی است. همان طور که در شکل 7- ج نشان داده شده است، میزان تأخیر در اجرای محلی از همه حالت‌ها کمتر می‌باشد. نتیجه این ارزیابی و برتری روش پیشنهادی با ظرفیت 500 نسبت به بقیه حالت‌ها در جدول 3 آمده است.

شکل 8- الف مقایسه عملکرد روش پیشنهادی با ظرفیت 200 و 500، اجرای محلی و بارگذاری تمام وظایف به لبه را نشان می‌دهد. برای img0، تابع هزینه حداقل است که تا حدودی کمتر از عملکرد هزینه در اجرای تمام وظایف به صورت محلی و بارگذاری تمام وظایف به لبه است. هنگامی که img0 در GKOA به 500 افزایش می‌یابد، تابع هزینه کاهش می‌یابد، زیرا امکان بارگذاری وظایف بیشتر به لبه وجود دارد. زمان اجرا و اتمام یک وظیفه کامل شامل جزئیاتی از زمان‌ها از جمله زمان اجرا در دستگاه تلفن همراه، زمان انتظار برای اجرای محلی، زمان انتظار  برای  انتقال،  زمان  انتقال،  زمان  انتظار  برای  اجرا  در  لبه  و  زمان  اجرا 

img0 

(الف)

img0 

(ب)

img0 

(ج)

شکل 7:  مقایسه تعدادی از پارامترها برای تعداد مختلف کاربران در 5 حالت روش پیشنهادی با ظرفیت 500 و 200، روش PBP، اجرای محلی و بارگذاری تمام وظایف به لبه، (الف) تأثیر تعداد کاربران بر انرژی مصرفی، (ب) تأثیر تعداد کاربران بر بار سیستم و (ج) تأثیر تعداد کاربران بر تأخیر.

 

در ابر است. زمان انتظار برای انتقال در اجرای محلی برابر 0 است زیرا انتقالی صورت نمی­گیرد و در الگوریتم بارگذاری پیشنهادی با افزایش تقاضا برای انتقال مقدار مطلوب دارد. وقتی مقدار img0 برابر با 500 شود، استفاده از الگوریتم GKOA برای پارامتر زمان اجرا بهترین مقدار را دارد، زیرا مقدار زمان انتظار در سمت دستگاه نسبت به اجرای محلی برای تعداد زیادی از کاربران کاهش می‌یابد. مقایسه این وضعیت در شکل 8- ب نشان داده شده است. شکل 8- ج نشان می‌دهد که میزان مصرف شبکه در حالت ارسال همه وظایف بیشترین مقدار را دارد  و  پس  از  آن،  زمانی  که  در  الگوریتم  پیشنهادی  ما  مقدار img0 برابر  با 

img0 

(الف)

img0 

(ب)

img0 

(ج)

img0 

(د)

 

شکل 8:  مقایسه چند پارامتر برای تعداد مختلف کاربران تلفن در چهار طرح img0 و img0، اجرای محلی و بارگذاری تمام وظایف به لبه و همچنین جزئیات الگوریتم GKOA، (الف) تأثیر تعداد کاربران بر تابع هزینه، (ب) تأثیر تعداد کاربران بر زمان اتمام وظایف، (ج) تأثیر تعداد کاربران بر زمان انتظار برای ارسال در شبکه و (د) جزئیات الگوریتم GKOA.

 

جدول 3: مزیت img0 نسبت به سایر روش‌ها با توجه به شکل 5.

 

پارامتر

اجرای محلی

اجرای همه وظایف در لبه

img0 

PBP

انرژی مصرفی

2/28

35/21

1/10

54/12

بار سیستم

05/18

24/16

5/10

7/10

میانگین تأخیر (ثانیه)

1/1

63/19

6/11

95/0

 

جدول 4: جزئیات الگوریتم GKOA.

 

الگوریتم

مجموع ارزش

وزن کل

تعداد وظایف انتخاب‌شده برای بارگذاری

img0 

9/320

435

668

img0 

6/117

2/189

314

 

 

500 است، بیشترین استفاده از شبکه را داریم. جزئیات الگوریتم پیشنهادی در 2 حالت در شکل 8- د نشان داده شده است. در img0 مقدار وزن پرشده برابر با img0 به همراه 314 وظیفه انتخابی و مقدار ارزش برابر با img0 است. در img0، مقدار وزن پرشده برابر با img0 به همراه 668 وظیفه انتخابی و مقدار ارزش برابر با img0 است. این جزئیات در جدول 4 نشان داده شده‌اند. ما در این قسمت، وضعیت پردازنده، RAM و شبکه را در چند حالت روش پیشنهادی با ظرفیت 200 و 500، انتخاب تصادفی وظایف img0، انتخاب تصادفی وظایف img0 و اجرای محلی همه وظایف در زمان img0 می‌سنجیم. در شکل 9، وضعیت پردازنده در اجرای محلی تمام وظایف در بالاترین ظرفیت استفاده است. مصرف باتری در اجرای محلی بیشتر از حالت‌های دیگر است، زیرا تمام وظایف در دستگاه اجرا می‌شوند. مقدار بهینه مصرف باتری در حالت img0 است. بیشترین مقدار استفاده از باتری در این حالت به مقدار 7% در img0 می‌باشد که در حالت انتخاب تصادفی img0 برابر با 19% است. وضعیت مصرف باتری در شکل 10 نشان داده شده است. با توجه به شکل 11 و 12، میزان استفاده از RAM در اجرای محلی، بالا و وضعیت استفاده از شبکه در اجرای محلی کمترین مقدار را دارد، زیرا هیچ کدام از وظایف بارگذاری نمی‌شوند. در حالت انتخاب تصادفی img0 و img0، وضعیت استفاده از RAM بهترین مقدار را دارد. وضعیت انتقال در شبکه در بازه زمانی تعریف‌شده منهای زمان‌های img0 و img0 برای چهار حالت 

img0 

شکل 9:  وضعیت پردازنده.

 

 

img0 

شکل 10:  وضعیت باتری مصرفی.

 

img0 

شکل 11:  وضعیت RAM.

 

دیگر تفاوت زیادی ندارد. بیشترین میزان استفاده از شبکه برای هر دو حالتی است که مقدار img0 است، زیرا وظایف بیشتری برای ارسال انتخاب می‌شوند. یکی از اهداف ما کاهش استفاده از منابع است، یعنی با کمترین تعداد پردازنده، بهترین بازدهی را داشته باشیم. مقایسه پارامترهای زمان انتظار، تأخیر، سربار سیستم و سطح سرویس برای الگوریتم پیشنهادی و سه الگوریتم FIFO، RR و SJF در شکل 13 آمده است. در FPTS بیشترین مقدار زمان انتظار با یک پردازنده برابر با مقدار 5 ثانیه است و با افزایش مقدار پردازنده‌ها به 3، زمان انتظار برابر 5/0 می‌شود. در حالی که این مقدار برای الگوریتم‌های FIFO، RR و SJF به ترتیب برابر با 15/0، 2/0 و 2/0 با تعداد 5، 4 و 4 پردازنده است. از طرفی در الگوریتم FPTS، احتمال کمترین تأخیر و بالاترین سطح سرویس با تعداد 4 پردازنده حاصل می‌شود. احتمال تأخیر و سطح خدمات با پردازنده‌های 8، 7 و 7-8 برای الگوریتم‌های FIFO و RR بهبود می‌یابند. سربار سیستم نیز در FPTS مقدار بهینه دارد و پس از الگوریتم پیشنهادی SJF مقدار بهینه‌ای   دارد.  به طور  کلی  الگوریتم  ارائه‌شده  با  روش  SJF  تفاوت   کمی  

img0 

شکل 12:  وضعیت پهنای باند شبکه.

 

دارد  اما  برای  تعداد زیاد وظایف، پاسخی بهینه دارد. استفاده از این الگوریتم زمان انتظار، احتمال تأخیر و سربار سیستم را تا حد قابل قبولی كاهش می­دهد و از سوی دیگر، سطح سرویس به میزان قابل توجهی افزایش می‌یابد. این الگوریتم با تعداد کم پردازنده‌ها کارایی بهتری دارد. جدول 5 وضعیت چهار الگوریتم را مطابق شکل 13 نشان می‌دهد.

با توجه به مقادیر ارائه‌شده در اکثر حالت‌ها، الگوریتم پیشنهادی ما یک مقدار بهینه برای همه پارامترها ارائه می‌دهد. سیستم پیشنهادی با استفاده از FPTS، دارای حالت پایدار با کمترین تعداد پردازنده‌ها در مقایسه با سایر الگوریتم‌ها است.

مسئله بعدی که مورد ارزیابی قرار می‌گیرد درباره تخصیص منابع است. اکثر وظایف در سمت لبه اجرا می‌شوند، اما در صورت نبود منابع کافی و انتظار، به ابر منتقل می‌گردند. این فرایند برای روش پیشنهادی و 3 روش معیار مورد بررسی قرار گرفت و در شکل 14 نشان داده شده است. این جریان برای داده‌ها با نرخ ورود 250 و 500 آزمایش شد. در الگوریتم پیشنهادی و بعد از آن SJF درصد بیشتری از وظایف در سمت لبه اجرا می‌شوند که به ترتیب 11/92% در جایی که نرخ ورود داده برابر با 250 است و 88/90% برای جایی که نرخ ورود داده برابر با 500 است، می‌باشد. این مقادیر برای الگوریتم SJF با کارایی بهتر در سطح دوم برابر با 68/80% برای نرخ ورود 250 و 38/71% برای نرخ ورود 500 هستند.

6-       نتیجه‌گیری

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

img0 

(الف)

img0 

(ب)

img0 

(ج)

img0 

(د)

 

شکل 13:  مقایسه پارامترهای ارزیابی با کمترین تعداد پردازنده‌ها برای الگوریتم پیشنهادی و الگوریتم‌های معیار، (الف) میانگین زمان انتظار، (ب) سطح سرویس، (ج) تأخیر و (د) بار سیستم.

 

 

img0 

شکل 14:  درصد اجرای وظایف در لبه و مهاجرت به ابر.

 

لبه انتخاب می‌کند. با تقسیم‌بندی این الگوریتم، وظایف به دو دسته جهت اجرای محلی و بارگذاری در لبه تقسیم می‌شوند. این الگوریتم وظیفه دارد که بهترین انتخاب از وظایف را برای بارگذاری به لبه داشته باشد، به طوری که با بارگذاری آنها هزینه اجرای وظایف در لبه نسبت به اجرای آنها به صورت محلی بیشتر نشود و بتوان در مصرف منابع صرفه‌جویی کرد. GKOA بهترین نتایج بهینه را برای به حداقل رساندن مصرف انرژی نشان داد. نتایج عددی نشان دادند که الگوریتم GKOA در مصرف انرژی نسبت به اجرای تمام وظایف به صورت محلی 2/28%، نسبت به اجرای تمام وظایف در سمت لبه به مقدار 35/21% و نسبت به روش PBP [29] در حدود 54/12% بهبود یافت. این الگوریتم با افزایش تعداد کاربران، عملکرد بهتری را نسبت به بقیه حالت‌های ارزیابی‌شده دارد. الگوریتم FPTS، اولویت‌بندی مناسبی را از وظایف بر اساس دو معیار زمان اجرا و انرژی مصرفی ارائه می‌کند که در سرعت اجرای وظایف در محیط لبه نسبت به اجرای محلی در دستگاه مؤثر است. به طوری که اجرای مجموعه وظایف اولویت‌بندی شده در این زمان‌بند نسبت به روش‌های دیگر، باعث بهبود زمان انتظار، تأخیر و سطح سرویس با حداکثر 5 پردازنده است، در حالی که این مقدار برای الگوریتم‌های FIFO، RR و SJF به ترتیب 7، 8 و 7 است. در سیستم ارائه‌شده، میزان وظایف اجراشده در بستر لبه به ترتیب 11/92% در جایی که نرخ ورود داده برابر با 250 است و 88/90% برای جایی که نرخ ورود داده برابر با 500 است،  که تنها در حدود 10% از وظایف برای اجرا به ابر منتقل می‌شوند. این کار یکی از محدودیت‌های مهم محیط محاسبات ابری یعنی دوری از کاربران  و ترافیک بالا را با  انتقال  وظایف  به  لایه میانی لبه رفع می‌کند. همچنین

جدول 5: مقایسه پارامترهای ارزیابی با توجه به شکل 13.

 

تعداد پردازنده

زمان انتظار (ثانیه)

سرویس (%)

تأخیر (%)

بار سیستم

الگوریتم

1

5

8

93

16

FPTS

2

08/0

08/82

3/90

431/0

3

04/0

85/98

43/46

156/0

4

02/0

2/99

8/10

039/0

5

01/0

7/99

42/1

010/0

6

005/0

9/99

35/0

002/0

1

10

1

100

1

FIFO

2

5

40

99

400

3

9/3

21/75

98

36/860

4

1

85

80

250/72

5

15/0

26/85

3/84

636/1

6

03/0

56/96

42/75

084/0

7

01/0

26/99

02/53

010/0

8

01/0

85/99

83/14

010/0

9

005/0

97/99

36/2

002/0

10

001/0

9/99

1

0

1

3

2/9

9/99

618/7

SJF

2

1

79

93

410/6

3

19/0

27/81

87/83

384/2

4

02/0

02/91

25/60

033/0

5

02/0

82/96

52/28

037/0

6

005/0

98/98

69/3

002/0

7

003/0

99

4/1

001/0

1

3

5

99

25/2

RR

2

1

65

93

25/42

3

19/0

80

9/79

310/2

4

02/0

02/86

65

030/0

5

02/0

82/91

40

034/0

6

005/0

6/96

3/12

002/0

7

003/0

2/98

5

001/0

8

001/0

99

1/2

001/0

 

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

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

مراجع 

[1]       J. Huang, C. C. Xing, and C. Wang, "Simultaneous wireless information and power transfer: technologies, applications, and research challenges," IEEE Communications Magazine, vol. 55,
no. 11, pp. 26-32, Nov. 2017.

[2]       K. Zhang, et al., "Energy-efficient offloading for mobile edge computing in 5g heterogeneous networks," IEEE Access, vol. 4, pp. 5896-5907, 2016.

[3]       Y. Sun, J. Li, X. Fu, H. Wang, and H. Li, "Application research based on improved genetic algorithm in cloud task scheduling," Journal of Intelligent & Fuzzy Systems, vol. 38, no. 1, pp. 239-246, Jan. 2020.

[4]       G. Li, J. Wang, J. Wu, and J. Song, "Data processing delay optimization in mobile edge computing," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 6897523, 9 pp., 2018.

[5]       W. Zhimin, Z. Qinglin, X. Fangxin, D. Hongning, and Z. Yujun, "Detection performance of packet arrival under downclocking for mobile edge computing," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 9641712, 2018.

[6]       W. Yu, et al., "A survey on the edge computing for the Internet of things," IEEE Access, vol. 6, pp. 6900-6919, 2018.

[7]       Y. Guo, et al., "Distributed machine learning for multiuser mobile edge computing systems," IEEE J. of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 460-473, Apr. 2022.

[8]       Z. Jiao, et al., "Energy-latency trade-off for energy-aware offloading in mobile edge computing networks," IEEE Internet of Things J., vol. 5, no. 4, pp. 2633-2645, Aug. 2018.

[9]       A. Selvaraj and S. Sundararajan, "Evidence-based trust evaluation system for cloud services using fuzzy logic," International J. of Fuzzy Systems, vol. 19, no. 2, pp. 329-37, Apr. 2017.

[10]       M. Fonseca, U. H. Bezerra, J. D. Brito, J. C. Leite, and M. H. Nascimento, "Pre-dispatch of load in thermoelectric power plants considering maintenance management using fuzzy logic," IEEE Access, vol. 6, pp. 41379-41390, 2018.

[11]       K. Wang, K. Yang, and C. Magurawalage, "Joint energy minimization and resource allocation in C-RAN with mobile cloud," IEEE Trans. Cloud Comput, vol. 6, no. 3, pp. 331-346, Jul./
Sept. 2017.

[12]       Y. Mao, J. Zhang, and K. B. Letaief, "Dynamic computation offloading for mobileedge computing with energy harvesting devices," IEEE J. Sel. Areas Commun, vol. 34, no. 12, pp. 3590-3605, Dec. 2016.

[13]       H. Kchaou, Z. Kechaou, and A. M. Alimi, "Towards an offloading framework based on big data analytics in mobile cloud computing environments," Procedia Comput. Sci., vol. 53, pp. 292-297, 2015.

[14]       S. Misra and S. Sarkar, "Theoretical modeling of fog computing: a green computing paradigm to support IoT applications," IET Networks, vol. 5, no. 2, pp. 23-29, Mar. 2016.

[15]       L. Yang, J. Cao, H. Cheng, and Y. Ji, "Multi-user computation partitioning for latencysensitive mobile cloud applications," IEEE Trans.Computers, vol. 64, no. 8, pp. 2253-2266, Aug. 2015.

[16]       G. Shuaishuai, W. Dalei, Z. Haixia, and Y. Dongfeng, "Resource modeling and scheduling for mobile edge computing: a service provider's perspective," IEEE Access, vol. 6, pp. 35611-35623, 2018.

[17]       Z. Wenchen, et al., "Markov approximation for task offloading and computation scaling in mobile edge computing," Mobile Information Systems, vol. 2019, Article ID: 8172698, 2019.

[18]       T. Chia Wei, T. Fan Hsun, Y. Yao Tsung, L. Chien Chang, and C. LiDer, "Task scheduling for edge computing with agile VNFs on-demand service model toward 5G and beyond," Wireless Communications and Mobile Computing, vol. 2018, Article ID: 7802797, 2018.

[19]       Y. Yibo, M. Yongkui, X. Wei, G. Xuemai, and Z. Honglin, "Joint optimization of energy consumption and packet scheduling for mobile edge computing in cyber-physical networks," IEEE Access, vol. 6, pp. 15576-15586, 2018.

[20]       W. Yuan, et al., "NOMA-Assisted multi-access mobile edge computing: a joint optimization of computation offloading and time allocation," IEEE Trans. on Vehicular Technology, vol. 67, no. 12, pp. 12244-12258, Dec. 2018.

[21]       A. Aghababaeipour and S. Ghanbari, " A new adaptive energy-aware job scheduling in cloud computing," in Proc. Int. Conf. on Soft Computing and Data Mining, pp. 308-317, Senai, Malaysia, 5-7 Feb. 2018.

[22]       S. Ghanbari and M. Othman, "Time cheating in divisible load scheduling: sensitivity analysis, results and open problems," Procedia Computer Science, pp. 935-943, vol. 1, no. 125, Jan. 2018.

[23]       Y. Changyan, C. Jun, and S. Zhou, "A multi-user mobile computation offloading and transmission scheduling mechanism for delay sensitive application," IEEE Trans. on Mobile Computing, vol. 19, no. 2, pp. 99-110, Jan. 2018.

[24]       D. Yueyue, X. Du, M. Sabita, and Y. Zhang, "Joint computation offloading and user association in multi-task mobile edge computing," IEEE Trans. on Vehicular Technology, vol. 67, no. 12, pp. 12313-12325, Dec. 2018.

[25]       X. Chen, J. Lei, L. Wenzhong, and F. Xiaoming, "Efficient multi-user computation offloading for mobile-edge cloud computing," IEEE/ACM Trans. on Networking, vol. 24, no. 5, pp. 2795-2808, Oct. 2016.

[26]       C. Ying, Z. Ning, Z. Yongchao, and C. Xin, "Dynamic computation offloading in edge computing for the Internet of Things," IEEE Internet of Things J., vol. 6, no. 3, pp. 239-251, Jun. 2019.

[27]       N. Zhaolong, D. Peiran, K. Xiangjie, and X. Feng, "A cooperative partial computation offloading scheme for mobile edge computing enabled Internet of Things," IEEE Internet of Things J., vol. 6, no. 3, pp. 4804-4814, Jun. 2019.

[28]       Y. Zhang, D. Niyato, and P. Wang, "Offloading in mobile cloudlet systems with intermittent connectivity," IEEE Trans. Mobile Computing, vol. 14, no. 12, pp. 2516-2529, Dec. 2015.

[29]       L. Tianze, W. Muqing, Z. Min, and L. Wenxing, "An overhead optimizing task scheduling strategy for ad hoc based mobile edge computing," IEEE Access, vol. 5, pp. 5609-5622, 2017.

[30]       R. Morabito and N. Beijar, "Enabling data processing at the network edge through lightweight visualization technologies," in Proc. of the IEEE Int. Conf. on Sensing, Communication, and Networking, SECON Workshops, 6 pp., London, UK, Jun. 2016.

[31]       H. Wang, J. Gong, Y. Zhuang, H. Shen, and J. Lach, "Health edge: task scheduling for edge computing with health emergency and human behavior consideration in smart homes," in Proc. of the IEEE Int. Conf. on Big Data, pp. 1213-1222, Shenzhen, China, 7-9 Aug. 2017.

[32]       P. Samal and P. Mishra, "Analysis of variants in round robin algorithms for load balancing in cloud computing," International J. of Computer Science and Information Technologies, vol. 4, no. 3,
pp. 416-419, 2013.

[33]       C. You, Y. Mao, J. Zhang, and K. Huang, "Energy-efficient offloading for mobile edge computing," In Wiley 5G Ref: The Essential 5G Reference Online, 2016.

[34]       J. Maozhu, W. Hua, S. Lijun, L. Yuxue, and Z. Yucheng, "Man-machine dialog system optimization based on cloud computing," Personal and Ubiquitous Computing, vol. 22, no. 5-6, pp. 937-942, Oct. 2018.

[35]       J. Wang, J. Peng, Y. Wei, D. Liu, and F. Jielin, "Adaptive application offloading decision and transmission scheduling for mobile cloud computing," in Proc. IEEE Int. Conf. on Communications, ICC’26, 7 pp., Kuala Lumpur, Malaysia, 22-27 May 2016.

[36]       F. Scott, K. Carlenri, Y. Di, B. George, and K. Mellow, "An analysis of vehicular wireless channel communication via queueing theory model," in Proc. IEEE Int. Conf. on Communications, pp. 1736-1741, Sydney, Australia, 10-14 Jun. 2014.

[37]       L. Tong, Y. Li, and W. Gao, "A hierarchical edge cloud architecture for mobile computing," in Proc. 35th Annual IEEE Int. Conf. on Computer Communications, IEEE INFOCOM’16, 9 pp., San Francisco, CA, USA, 10-14 Apr. 2016.

[38]       X. Chen, L. Pu, L. Gao, W. Wu, and D. Wu., "Exploiting massive D2D collaboration for energy-efficient mobile edge computing," IEEE Wireless Communications, vol. 24, no. 4, pp. 64-71, Aug. 2017.

[39]       A. Salehan, H. Deldari, and S. Abrishami, "An online context-aware mechanism for computation offloading in ubiquitous and mobile cloud environments," The J. of Supercomputing, vol. 75, no. 7, pp. 1-41, Ju.. 2019.

[40]       M. Al-Zinati, R. Alrashdan, B. Al-Duwairi, and M. Aloqaily, "A reorganizing biosurveillance framework based on fog and mobile edge computing," Multimedia Tools and Applications, vol. 80, no. 11, pp. 16805-16825, 2021.

[41]       S. Deng, et al., "Burst load evacuation based on dispatching and scheduling in distributed edge networks," IEEE Trans. on Parallel and Distributed Systems, vol. 32, no. 8, pp. 1918-1932, Aug. 2021.

[42]       F. Jazayeri, A. Shahidinejad, and M. Ghobaei-Arani, "Autonomous computation offloading and auto-scaling the in the mobile fog computing: a deep reinforcement learning-based approach," J. of Ambient Intelligence and Humanized Computing, vol. 12, pp. 8265-8284, 2021.

[43]       J. C. Guevara and N. L. da Fonseca, "Task scheduling in cloud-fog computing systems," Peer-to-Peer Networking and Applications, vol. 14, no. 2, pp. 962-977, 2021.

[44]       T. D. Lee, B. M. Lee, and W. Noh, "Hierarchical cloud computing architecture for contextaware IoT services," IEEE Trans. Consume Electron, vol. 64, no. 2, pp. 222-230, May2018.

[45]       Y. Shi, S. Chen, and X. Xu, "MAGA: a mobility-aware computation offloading decision for distributed mobile cloud computing," IEEE Internet of Things, vol. 5, no. 1, pp. 164-174, Feb. 2018.

[46]       M. Goudarzi, M. Zamani, and A. Toroghi Haghighat, "A genetic-based decision algorithm for multisite computation offloading in mobile cloud computing," Int J. Commun Syst, vol. 30, no. 10, Article ID: e3241, Jul. 2017.

[47]       A. Raneetha, H. Moshe, O. Binyamin, and Z. Ilze, "Strategic bidding in a discrete accumulating priority queue," Operations Research Letters, vol. 47, no. 3, pp. 162-167, May 2019.

[48]       J. Yuan and Y. Li, "Solving binary multi-objective knapsack problems with novel greedy strategy," Memetic Comp., vol. 13, pp. 447-458, 2021.

[49]       V. Kumar and K. Dinesh, "Transitive blocks and their applications in fuzzy interconnection networks," Fuzzy Sets and Systems, vol. 352, pp. 142-160, Dec. 2018.

[50]       Y. Mao, J. Zhang, S. H. Song, and K. B. Letaief, "Power-delay tradeoff in multi-user mobile-edge computing systems," in Proc. IEEE Global Communication. Conf., GLOBECOM’16, 6 pp., Washington, DC, USA, 4-8 Dec. 2016.

[51]       R. Gopi, S. T. Suganthi, R. Rajadevi, et al., "An enhanced green cloud based queue management (GCQM) system to optimize energy consumption in mobile edge computing," Wireless Pers Commun, vol. 117, pp. 3397-3419, 2021.

[52]       P. Zou, O. Ozel, and S. Subramaniam, "Optimizing information freshness through computation-transmission tradeoff and queue management in edge computing," IEEE/ACM Trans. on Networking, vol. 29, no. 2, pp. 949-963, Apr. 2021.

 

انتصار حسینی مدرک دکتری را در رشته امنیت اطلاعات در سال 1400 از دانشگاه قم دریافت نمود. برخی از زمینه های تحقیقی ایشان عبارتند از: رایانش ابری، امنیت در محیط­های محاسباتی رایانش ابری و محاسبات سیار.

 

محسن نیک رای مدرک دکتری خود را در سال 1391 در رشته معماری کامپیوتر از دانشگاه تهران اخذ نمود. در حال حاضر ایشان استادیار گروه کامپیوتر دانشگاه قم 
می‌باشد. برخی از زمینه های تحقیقاتی ایشان عبارت است از: معماری کامپیوتر، زمان بندی ، رایانش ابری، محاسبات سیار.

 

شمس‌اله قنبری مدرک دکتری را در سال 1394 از دانشگاه UPM مالزی در زمینه سیستم­های توزیع شده دریافت نمود. ایشان در حال حاضر عضو هیأت علمی گروه کامپیوتر دانشگاه آزاد استان مرکزی واحدآشتیان می باشند. برخی از زمینه­های تحقیقاتی مورد علاقه  ایشان عبارت است از: زمان بندی در محیط­های سیستم­های موازی و توزیع شده،  رایانش ابری، پایگاه­های داده، پیچیدگی محاسباتی.

 

 


رایمگ

يقوم نظام رایمگ بتنفيذ جميع عمليات الاستلام والتقييم والحكم والتحرير وتخطيط الصفحة والنشر الإلكتروني للمجلات العلمية.

الروابط

المراكز ذات الصلة

دعامة

الصفحات الرسمية

حقوق هذا الموقع الإلكتروني مملوكة لنظام Rimag Press Management. © 1438-1446

الصفحة الرئيسية| دخول| عنا| اتصل بنا|
[English] [فارسی] [en] [fa]