ارائه روش حریصانه بهبود یافته برای افزایش تعداد کاربران سرویس داده شده در شبکه‌های ابر لبه

نوع مقاله : مقاله پژوهشی

نویسندگان

گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامی، واحد سنندج، سنندج، ایران.

10.22052/scj.2022.243195.1005

چکیده

یکی از مهمترین چالش‌ها در محاسبات لبه، افزایش تعداد کاربران سرویس داده شده است بدون اینکه در پیچیدگی مساله تغییری حاصل شده و تاخیر بیشتری برای سرویس‌دهی به شبکه ابر لبه تحمیل شود. در ابر لبه، ابتدا تلاش می‌شود تا هر کاربر از سرور لبه خود، سرویس مورد نظرش را درخواست  داده و این سرویس در اختیار وی قرار گیرد. در صورت عدم وجود سرویس در ابر لبه، از سرور لبه مجاور بر اساس فاصله، استعلام صورت می‌گیرد تا از  نزدیک‌ترین ابرهای لبه که به صورت بی‌سیم می‌توانند با این ابر ارتباط داشته باشند، سرویس مورد نظر دریافت شود. اگر کاربر همچنان موفق به دریافت سرویس نشود، درخواست وارد پیوند بک‌هال شده و سرویس درخواستی در سایر سرورهای لبه جستجو می شود. در نهایت در صورتی که باز هم درخواست پاسخ داده نشود، سرویس از ابر دریافت می‌شود. استراتژی معرفی شده در مقاله، با توجه پیچیدگی بررسی شده، شرایطی را فراهم می‌کند که تعداد کاربران سرویس داده شده افزایش یابد بدون اینکه پیچیدگی تغییر کند. متوسط بهبود برای کاربران سرویس گرفته به کل کاربران در الگوریتم پیشنهادی نسبت به روش حریصانه 4/0 درصد و نسبت به روش بیشینه جریان 1/1 درصد است. همچنین این الگوریتم نسبت به الگوریتم بیشینه جریان و حریصانه در زمانبندی کاربران به ترتیب 20% و 22% بهبود را نشان می‌دهد.

کلیدواژه‌ها


عنوان مقاله [English]

Providing an improved greedy approach to increasing the number of users served on cloud-edge networks

نویسندگان [English]

  • Mohammad Shirkhani
  • Keyhan Khamforoosh
  • Mahsa Izadbin
Department of Computer Engineering, Islamic Azad University, Sanandaj Branch, Sanandaj, Iran.
چکیده [English]

The most critical challenge in edge computing is to increase the number of users of the service provided without changing the complexity of the problem and imposing further delays for servicing the cloud-edge network. First, every user will request the service from their edge server, which edges provide it. If there is no service in the edge cloud, the inquiry is made from the adjacent edge server based on the distance. The nearest edge clouds that can connect to it wirelessly provide the desired service. If it fails to receive the service from them, the service request enters the backhaul link and searches for the requested service on other edge servers. Finally, if it still fails to receive the service, it will receive the service from the cloud. Due to the complexity examined, the strategy presented in the paper provides the conditions to increase the number of service users without changing the service delay. The average improvement for users served to all users in the proposed algorithm. However, 0.4% relative to the greedy and 1.1% relative to the maximum flow, the proposed method shows a 20% and 22% improvement over the maximum flow and greedy algorithm in users' scheduling, respectively.

کلیدواژه‌ها [English]

  • Service allocation
  • User Scheduling
  • Edge Computing
  • Cloud Computing
  • Greedy Algorithm
[1] Borcoci E., Vochin M., and Obreja S., "Mobile Edge Computing versus Fog Computing in Internet of Vehicles," in research gate, Bucharest, Romania, 2018.
[2] Chunlin L., Sun H., Yi C., and Luo Y., "Edge cloud resource expansion and shrinkage based on workload for minimizing the cost," Future Generation Computer Systems, 101:327-340, 2019. 
[3] Li X. and Xu L. D., "A Review of Internet of Things-Resource Allocation," IEEE Internet of Things Journal, 8(11), 2021. 
[4] Jia M., Cao J., and Liang W., "Optimal cloudlet placement and user to cloudlet allocation in wireless metropolitan area networks," IEEE Transactions on Cloud Computing, 5(4):725-737, 2017. 
[5] Xu Z., Liang W., Xu W., Jia M., and Guo S., "Efficient algorithms for capacitated cloudlet placements," IEEE Transactions on Parallel and Distributed Systems, 27: 2866–2880, 2016. 
[6] Ceselli A., Premoli M., and Secci S., "Mobile edge cloud network design optimization," IEEE/ACM Transactions on Networking, 25:1818–1831, 2017. 
[7] Wang L., Jiao L., Li J., and Muhlhauser M., "Online resource allocation for arbitrary user mobility in distributed edge clouds," in 37th International Conference on Distributed Computing Systems (ICDCS), 2017. 
[8] Tan H., Han Z., Li X.-Y., and Lau F. C. M., "Online job dispatching and scheduling in edge-clouds," in IEEE INFOCOM, 2017. 
[9] Sabaghian K., Khamforoosh K., and Ghaderzadeh A., "Presentation of a new method based on modern multivariate approaches for big data replication in distributed environments," Plos one 16, no. 7 (2021): e0254210.
[10] Llorca J., Tulino A. M., Sforza A., and Sterle C., "Optimal content distribution and multi-resource allocation in software defined virtual," in AIRO ODS, 2017. 
[11] Zhao T., Zhou S., Guo X., and Niu Z., "Tasks Scheduling and Resource Allocation in Heterogeneous Cloud for Delay-bounded Mobile Edge Computing," in IEEE ICC 2017 SAC Symposium Cloud Communications and Networking Track, 2017. 
[12] Chen X., Li W., Lu S., Zhou Z., and Fu X., "Efficient Resource Allocation for On-Demand Mobile-Edge Cloud Computing," IEEE Transactions on Vehicular Technology , 67(9): 8769 - 8780, 2018. 
[13] He T., Khamfroush H., Wang S., La Porta T., and Stein S., "Joint Service Placement and Request Scheduling in Edge Clouds with Sharable and Non-Sharable Resources," in 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), Vienna, Austria, 2018. 
[14] Farhadi V., Mehmeti F., He T., La Porta T., Khamfroush H., Wang S., and Chan K. S., "Service Placement and Request Scheduling for Data-Intensive Applications in Edge Clouds," in IEEE INFOCOM 2019 - IEEE Conference on Computer Communications, Paris, 2019. 
[15] Zhao J., Li Q., Gong Y., and Zhang K., "Computation Offloading and Resource Allocation For Cloud Assisted Mobile Edge Computing in Vehicular Networks," IEEE Transactions on Vehicular Technology, 68: 7944 - 7956, 2019. 
[16] Li Y., Dai W., Gan X., Jin H., Fu L., Ma H., and Wang X., "Cooperative Service Placement and Scheduling in Edge Clouds: A Deadline-Driven Approach," IEEE Transactions on Mobile Computing, p. 1, 2021. 
[17] Han T. and Ansari N., "Network Utility Aware Traffic Load Balancing in Backhaul-Constrained Cache-Enabled Small Cell Networks with Hybrid Power Supplies," IEEE Transactions on Mobile Computing, 16(10): 2819 - 2832, 2017. 
[18] Wei Y., Zhang  Z., Yu F. R., and Han Z., "Joint User Scheduling and Content Caching Strategy for Mobile Edge Networks Using Deep Reinforcement Learning," in IEEE International Conference on Communications Workshops, Kansas City, MO, USA, 2018. 
[19] Li C., Bai J., and Tang J. H., "Joint optimization of data placement and scheduling for improving user experience in edge computing," Journal of Parallel and Distributed Computing, 125:93-105, 2020. 
[20] Yin B., Chen Z., and Tao M., "Joint User Scheduling and Resource Allocation for Federated Learning over Wireless Networks," in IEEE Global Communications Conference, 2020.
[21] Wang S., Chen M., Liu X., and Yin C., "A Machine Learning Approach for Task and Resource Allocation in Mobile Edge Computing Based Networks," IEEE Internet of Things Journal, 8(3): 1358-1372, 2020. 
[22] Wang J. and Wang L., "A Computing Resource Allocation Optimization Strategy for Massive Internet of Health Things Devices Considering Privacy Protection in Cloud Edge Computing Environment," Journal of Grid Computing, vol. 19, 2021. 
[23] Molner N., de la Oliva A., Stavrakakis I., and Azcorra A., "Optimization of an integrated fronthaul/backhaul network under path and delay constraints," Ad Hoc Networks, 83: 41-54, 2019.
[24] Korte B. and Vygen J., "Network flows," Combinatorial Optimization, 8: 153-184, 2000.
[25] Wang J., Hu J., Min G., Zhan W., Zomaya A., and Georgalas N., "Dependent Task Offloading for Edge Computing based on Deep Reinforcement Learning," in IEEE Transactions on Computers, 2021, doi: 10.1109/TC.2021.3131040.