Mobility-Aware and Energy-Efficient Computation Offloading in Edge Computing for Multi-UAV based Networks
Subject Areas : electrical and computer engineering
Kimia Ghasemi
1
,
Zeinab Movahedi
2
*
1 - Comp. Eng. Faculty, Iran Science and Technology University, Tehran, Iran
2 - Comp. Eng. Faculty, Iran Science and Technology University, Tehran, Iran
Keywords: Computation Offloading, Edge Computing, Multi-UAV based Networks,
Abstract :
Communication networks and the Internet of Things respond to various needs with continuous development. The limitations of size, computing power and energy consumption in Internet of Things devices are the main challenges of this space. This paper emphasizes combining UAVs with edge computing so that this integration provides advanced coverage and efficient computing support, especially in uncertain situations such as incident response. The proposed solution, in terms of the mobility of IoT nodes and with the aim of improving the energy efficiency of the whole system, the problem of UAV path planning and computation offloading is jointly modeled. Then, a mobility- and energy-aware computation offloading and path planning algorithm based on the efficient coverage set of UAVs is presented, which helps to maximize the energy efficiency of the system by using communication and consensus agreements between IoT nodes. The evaluation results show that the proposed method improves energy efficiency by 137% and energy consumption by 28% compared to previous works.
[1] Statista Research Department, Internet of Things - Number of Connected Devices Worldwide 2015-2025, https://www.statista.com/statistics/471264/iot-number-of-connected-devices-worldwide/, Date Published: Nov 27, 2016, Last Access on Feb. 2024.
[2] C. Mateos, K. R. Choo, and A. Zunino, "Sharpening the edge: towards improved edge computing environment for mobile and IoT applications," Future Gener. Comput. Syst., vol. 107, pp. 1130-1133, Jun. 2020.
[3] W. Zhuang, Q. Ye, F. Lyu, N. Cheng, and J. Ren, "SDN/NFV-empowered future IoV with enhanced communication, computing, and caching," Proceedings of the IEEE, vol. 108, no. 2, pp. 274-291, Feb. 2020.
[4] T. Zhang, Y. Xu, J. Loo, D. Yang, and L. Xiao, "Joint computation and communication design for UAV-assisted mobile edge computing in IoT," IEEE Trans. Ind. Inform., vol. 16, no. 8, pp. 5505-5516, Oct. 2020.
[5] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, "A survey on mobile edge computing: the communication perspective," IEEE Commun. Surv. Tut., vol. 19, no. 4, pp. 2322-2358, Jan. 2017.
[6] X. Xiong, K. Zheng, L. Lei, and L. Hou, "Resource allocation based on deep reinforcement learning in IoT edge computing," IEEE J. Sel. Areas Commun., vol. 38, no. 6, pp. 1133-1146, Apr. 2020.
[7] Z. Chang, L. Liu, X. Guo, and Q. Sheng, "Dynamic resource allocation and computation offloading for IoT fog computing system," IEEE Trans. Ind. Inform., vol. 17, no. 5, pp. 3348-3357, Jun. 2021.
[8] X. Hu, K. Wong, K. Yang, and Z. Zheng, "UAV-assisted relaying and edge computing: scheduling and trajectory optimization," IEEE Trans. Wirel. Commun., vol. 18, no. 10, pp. 4738-4752, Dec. 2019.
[9] M. Li, N. Cheng, J. Gao, Y. Wang, L. Zhao, and X. Shen, "Energy efficient UAV-assisted mobile edge computing: resource allocation and trajectory optimization," IEEE Trans. Veh. Technol., vol. 69, no. 3, pp. 3424-3438, Jan. 2020.
[10] L. D. Nguyen, A. E. Kalør, I. L. Mayorga, and P. Popovski, "Trusted wireless monitoring based on distributed ledgers over NB-IoT connectivity," IEEE Commun. Mag., vol. 58, no. 6, pp. 77-83, Apr. 2020.
[11] M. Pradhan and J. Noll, "Security, privacy, and dependability evaluation in verification and validation life cycles for military IoT systems," IEEE Commun. Mag., vol. 58, no. 8, pp. 14-20, Aug. 2020.
[12] Z. Tan, H. Qu, J. Zhao, S. Zhou, and W. Wang, "UAV-aided edge/fog computing in smart IoT community for social augmented reality," IEEE Internet Things J., vol. 7, no. 6, pp. 4872-4884, Feb. 2020.
[13] F. Zhou, Y. Wu, R. Q. Hu, and Y. Qian, "Computation rate maximization in UAV-enabled wireless-powered mobile-edge computing systems," IEEE J. Sel. Areas Commun., vol. 36, no. 9, pp. 1927-1941, Jun. 2018.
[14] L. Li, T. Q. S. Quek, J. Ren, H. H. Yang, Z. Chen, and Y. Zhang, "An incentive-aware job offloading control framework for multi-access edge computing," IEEE Trans. Mobile Comput., vol. 20, no. 1, pp. 63-75, Jan. 2021.
[15] K. Poularakis, J. Llorca, A. M. Tulino, I. J. Taylor, and L. Tassiulas, "Service placement and request routing in MEC networks with storage, computation, and communication constraints," IEEE/ACM Trans. Netw., vol. 28, no. 3, pp. 1047-1060, Apr. 2020.
[16] K. Poularakis, J. Llorca, A. M. Tulino, I. J. Taylor, and L. Tassiulas, "Service placement and request routing in MEC networks with storage, computation, and communication constraints," IEEE/ACM Trans. Netw., vol. 28, no. 3, pp. 1047-1060, Apr. 2020.
[17] T. Ouyang, Z. Zhou, and X. Chen, "Follow me at the edge: mobilityaware dynamic service placement for mobile edge computing," IEEE J. Sel. Areas Commun., vol. 36, no. 10, pp. 2333-2345, Sep. 2018.
[18] S. Wang, Y. Guo, N. Zhang, P. Yang, A. Zhou, and X. Shen, "Delayaware microservice coordination in mobile edge computing: a reinforcement learning approach," IEEE Trans. Mobile Comput., vol. 20, no. 3, pp. 939-951, Dec. 2021.
[19] Y. Liu, Y. Li, Y. Niu, and D. Jin, "Joint optimization of path planning and resource allocation in mobile edge computing," IEEE Trans. Mobile Comput., vol. 19, no. 9, pp. 2129-2144, Sept. 2020.
[20] F. Guo, H. Zhang, H. Ji, X. Li, and V. C. Leung, "Joint trajectory and computation offloading optimization for UAV-assisted MEC with NOMA," in Proc. IEEE Conf. Comput. Commun. Workshops, 6 pp., Paris, France, 29 Apr.-2 May 2019.
[21] S. Jeong, O. Simeone, and J. Kang, "Mobile edge computing via a UAV-mounted cloudlet: optimization of bit allocation and path planning," IEEE Trans. Veh. Technol., vol. 67, no. 3, pp. 2049-2063, Sept. 2018.
[22] Y. Qian, et al., "User association and path planning for UAV-aided mobile edge computing with energy restriction," IEEE Wirel. Commun. Lett., vol. 8, no. 5, pp. 1312-1315, Apr. 2019.
[23] X. Chen, et al., "Distributed computation offloading and trajectory optimization in multi-uav-enabled edge computing," IEEE Internet of Things, vol. 9, no. 20, pp. 20096-20110, May 2022.
[24] Q. Ye, et al., "Learningbased computing task offloading for autonomous driving: a load balancing perspective," in Proc. IEEE Int. Conf. Commun., 6 pp., Montreal, Canada, 14-23 Jun. 2021.
[25] I. A. Elgendy, S. Meshoul, and M. Hammad, "Joint task offloading, resource allocation, and load-balancing optimization in multi-UAV-aided MEC systems," Applied Sciences, vol. 13, no. 4, Article ID: 2625, Feb. 2023.
[26] B. Li, et al., "Robust computation offloading and trajectory optimization for multi-UAV-assisted MEC: a multi-agent DRL approach," IEEE Internet of Things J., vol. 11, no. 3, pp. 4775-4786, Aug. 2023.
[27] Z. Yu, Y. Gong, S. Gong, and Y. Guo, "Joint task offloading and resource allocation in UAV-enabled mobile edge computing," IEEE Internet Things J., vol. 7, no. 4, pp. 3147-3159, Jan. 2020.
[28] Y. Wang, Z. Ru, K. Wang, and P. Huang, "Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing," IEEE Trans. Cybern., vol. 50, no. 9, pp. 3984-3997, Sept. 2020.
[29] A. Ranjha, G. Kaddoum, M. Rahim, and K. Dev, "URLLC in UAV-enabled multicasting systems: a dual time and energy minimization problem using UAV speed, altitude and beamwidth," Computer Communications, vol. 187, pp. 125-133, Apr. 2022.
[30] N. Lin, H. Tang, L. Zhao, S. Wan, A. Hawbani, and M. Guizani, "A PDDQNLP algorithm for energy efficient computation offloading in UAV-assisted MEC," IEEE Trans. on Wireless Communications, vol. 22, no. 12, pp. 8876-8890, Dec. 2023.
[31] M. Ma and Z. Wang, "Distributed offloading for multi-uav swarms in mec-assisted 5G heterogeneous networks," Drones, vol. 7, no. 4, Article ID: 226, Mar. 2023.
نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 22، شماره 4، زمستان 1403 259
مقاله پژوهشی
تخلیه بار محاسباتی آگاه از تحرک و انرژی در رایانش لبه
برای شبکههای مبتنی بر چند پهپاد
کیمیا قاسمی و زینب موحدی
چکیده: امروزه با توسعه روزافزون شبکههای ارتباطی، استفاده از اینترنت اشیا در همه ابعاد زندگی جوامع در حال گسترش میباشد. در این بستر، از تخلیه بار محاسباتی به رایانش لبه به عنوان راهحلی کارآمد برای مرتفعکردن محدودیتهای دستگاههای اینترنت اشیا از نظر توان محاسباتی و انرژی استفاده میگردد. همچنین با ظهور شبکههای G5 به طور گستردهای از پهپادها جهت توسعه پوشش شبکه در شرایط مختلف استفاده میگردد. در این مقاله به مسئله توأمان تخلیه بار محاسباتی و برنامهریزی مسیر پهپادها با لحاظ تحرک دستگاههای اینترنت اشیا در رایانش لبه مبتنی بر چند پهپاد پرداخته شده است. به این منظور، این مسئله را با هدف بیشینهکردن کارایی انرژی کل سیستم در هر دو لایه پهپاد و دستگاههای اینترنت اشیا و با احتساب هزینه وظایف اجرا شده به صورت محلی علاوه بر وظایف تخلیهشده مدلسازی مینماییم. همچنین با توجه به پیچیدگی محاسباتی مسئله، یک الگوریتم حل مبتنی بر مجموعه پوشش کاربردی با لحاظ تحرک گرههای اینترنت اشیا و با هدف بهبود کارایی انرژی کل سیستم پیشنهاد شده است. مطابق نتایج ارزیابیها الگوریتم پیشنهادی توانسته که کارایی انرژی و مصرف انرژی کل سیستم را به ترتیب تا ۱۳۷ و 28 درصد نسبت به کارهای پیشین بهبود بخشد.
کلیدواژه: تخلیه بار محاسباتی، رایانش لبه، شبکههای مبتنی بر چند پهپاد.
1- مقدمه
در دنیای امروز، اینترنت اشیا2 به صورت فراگیر و با رشد زیادی در حال توسعه و استفاده است؛ به طوری که پیشبینی شده تا سال ۲۰۲۵ تعداد دستگاههای متصل به این بستر به مرز ۷۵ میلیارد برسد [1]. این توسعه اینترنت اشیا منجر به ایجاد برنامههای کاربردی جدید با بار محاسباتی سنگین3، حجم عظیم دادهها و حساس به زمان4 گردیده است [2] و [3]. از طرفی، یکی از چالشهای اساسی در اینترنت اشیا محدودیت توان محاسباتی و انرژی دستگاههای متصل به آن میباشد. در واقع، این دستگاهها قادر نیستند برنامههای دارای بار محاسباتی سنگین و نیازمند تأخیر کم را انجام دهند و یا در صورت توانایی، به علت محدودیت انرژی دچار بحران میشوند. به دلیل وجود این محدودیتها برنامهها باید به فضای دیگری خارج از دستگاه اینترنت اشیا منتقل شوند که به آن تخلیه بار محاسباتی میگویند. با وجود اینکه تخلیه بار این برنامهها به یک مرکز ابری5 راه دور موجب بهبود سرعت پردازش محاسبات میگردد، اما با توجه به تأخیر دسترسی زیاد و مصرف منابع ارتباطی قابل توجه موجب کاهش کیفیت خدمات 6(QoS) و افزایش سربار شبکه میگردد [4] و [5]. برای کاهش تأخیر دسترسی به منابع ابری و توزیع گسترده آن، رایانش لبه موبایل 7(MEC) معرفی شد که در آن با قرارگیری ظرفیتهای محاسباتی و ذخیرهسازی در لبه شبکه، تأخیرهای ناشی از انتقال داده بهبود یافته است [۶] و [۷].
علاوه بر این با ظهور نسل پنجم شبکههای موبایل 8(G5)، هواپیماهای بدون سرنشین 9(UAV) یا همان پهپادها به عنوان راه حلی امیدوارکننده جهت توسعه پوشش شبکهای مطرح شدهاند. از کاربردهای این فناوری میتوان به ایجاد پوشش شبکه در مناطق دورافتاده، ارائه خدمات اضطراری در شرایط فقدان زیرساختها ناشی از بلایای طبیعی [۸] و [۹] و کاربردهای نظارت و سنجش در محیطهای بدون مراقبت10 [1۰] و [1۱] اشاره کرد. با توجه به فقدان زیرساخت زمینی یا کمبود منابع آن در برخی شرایط و غیر عملی بودن پشتیبانی محاسباتی توسط ایستگاههای پایه11 ثابت، سرورهای لبه12 سوار بر پهپاد به منظور پشتیبانی محاسباتی کارآمد از گرههای اینترنت اشیا، افزایش انعطافپذیری سیستم و افزایش طول عمر عملیاتی پدیدار شده است [1۲] و [۱۳].
با این حال، تخلیه بار محاسباتی به پهپاد مجهز به رایانش لبه با چالشهای متعددی از جمله انرژی مصرفی فرایند تخلیه بار محاسباتی با توجه به محدودیت باتری پهپادها و گرههای اینترنت اشیا، انتخاب پهپاد بهینه برای تخلیه بار محاسباتی و لحاظ توأمان برنامهریزی مسیر پهپادها و تصمیم تخلیه بار محاسباتی روبهرو میباشد.
با وجود لحاظ توأمان تخلیه بار محاسباتی و برنامهریزی مسیر در برخی از کارهای موجود، غالب این کارها کارایی انرژي را از منظر میزان سودمندی بهدستآمده به ازای انرژی مصرفشده مد نظر قرار ندادهاند. این در حالی است که کارایی انرژی بهتر میتواند منعکسکننده کیفیت تصمیم تخلیه بار و برنامهریزی مسیر در مقابل مصرف انرژی به صورت مطلق باشد. همچنین کارهای موجود تنها انرژی مصرفشده در پهپادها را لحاظ نموده و انرژی مصرفشده در دستگاههای اینترنت اشیا جهت تخلیه بار محاسباتی یا اجرای محلی وظایف باقیمانده را در نظر نمیگیرند. به علاوه، کارهای موجود در این زمینه، تحرک دستگاههای اینترنت اشیا
و موقعیتیابی دقیق آنها را با توجه به محدودیت منابع و عدم تجهیز
این دستگاهها به سیستمهای ماهوارهای ناوبری جهانی13 مد نظر قرار نمیدهند. این در حالی است که موقعیت دقیق دستگاههای اینترنت اشیا با توجه به ماهیت پویا و تحرک مداوم آنها، تأثیر بسزایی در تصمیم تخلیه بار محاسباتی و برنامهریزی مسیر بهینه دارد.
برای پرداختن به این چالشها در این مقاله به حل مسئله توأمان تخلیه بار محاسباتی و برنامهریزی مسیر پهپادها با لحاظ تحرک گرههای اینترنت اشیا و نیازهای محاسباتی متغیر در طول زمان در شبکههای مبتنی بر چند پهپاد پرداخته شده است. به این منظور در این مقاله مسئله توأمان تخلیه بار محاسباتی و برنامهریزی مسیر پهپادها را با هدف بیشینهکردن کارایی انرژی کل سیستم شامل پهپادها و دستگاههای اینترنت اشیا مدلسازی نمودهایم. در این راستا، کارآمدی انرژی مصرفی جهت اجرای محلی وظایف تخلیه نشده به دلیل تصمیم عدم تخلیه بار یا باقیمانده به دلیل محدودیت لینکهای ارتباطی علاوه بر کارآمدی انرژی مصرفی پهپادها در نظر گرفته شده است. همچنین به منظور حل مسئله مدلسازیشده، یک الگوریتم تخلیه بار محاسباتی و برنامهریزی مسیر آگاه از تحرک و کارآمدی انرژی 14(MECOP) مبتنی بر مجموعه پوشش کاربردی15 پهپادها پیشنهاد میکنیم. این مجموعه که از طریق ارتباطات و توافقات اجماعی بین گرههای اینترنت اشیا ایجاد میگردد، کارایی سیستم را حداکثر و مصرف انرژی آن را کاهش میدهد. در این الگوریتم با توجه به تحرک دستگاههای اینترنت اشیا، موقعیت آنها بر اساس روش موقعیتیابی هوشمند فضایی سهبعدی16 محاسبه شده است. به طور خلاصه، نوآوریهای این مقاله به شرح زیر است:
- با توجه به اینکه کارهای قبلی مصرف انرژی را صرفاً در لایه پهپادها و نه در کل سیستم مد نظر قرار دادهاند، ما در این مقاله مدل انرژی مصرفشده در هر دو لایه پهپادها و دستگاههای اینترنت اشیا را مبتنی بر انواع انرژی مصرفی در هر یک از آنها طراحی میکنیم. سپس کارآمدی انرژی هر یک از لایهها را بر اساس برآیند میزان سودمندی بهدستآمده از هر یک از تصمیمات تخلیه بار محاسباتی یا اجرای محلی وظایف به نسبت میزان انرژی مصرفشده مدلسازی مینماییم. نهایتاً مسئله توأمان تخلیه بار محاسباتی و برنامهریزی مسیر پهپادها را با هدف بیشینهکردن کارآمدی انرژی کل سیستم ضمن رعایت قیود مربوط به محدودیت لینکهای ارتباطی و منابع رایانشی مدلسازی میکنیم.
- با توجه به انپیسخت17بودن مسئله مدلسازیشده و عدم امکان حل آن در مدت زمان قابل قبول، در ادامه یک الگوریتم آگاه از تحرک و کارآمدی انرژی به نام MECOP برای حل مسئله فوق پیشنهاد میدهیم. الگوریتم پیشنهادی با ایجاد مجموعه پوشش کاربردی برای هر پهپاد، ضمن لحاظ تحرک گرههای اینترنت اشیا، تصمیم تخلیه بار محاسباتی و تعیین موقعیت مناسب برای پهپادها را با هدف بیشینهکردن کارایی انرژی اخذ مینماید.
- نهایتاً برای ارزیابی عملکرد روش پیشنهادی، الگوریتم MECOP و تعدادی از کارهای مرتبط را در نرمافزار متلب پیادهسازی نمودهایم. نتایج حاصل از شبیهسازیهای گسترده تحت سناریوهای مختلف نشان میدهد روش پیشنهادی میزان کارایی انرژی، انرژی مصرفی کل و سودمندی سیستم از لحاظ میزان داده پردازششده را به طور قابل توجهی به نسبت کارهای موجود بهبود میبخشد.
ساختار ادامه این مقاله به شرح زیر است: در بخش دوم به بررسی کارهای انجامشده در زمینه تخلیه بار محاسباتی در شبکههای مبتنی
بر چند پهپاد میپردازیم. در بخش سوم، ضمن ارائه مدل ارتباطی و محاسباتی، کارآمدی انرژی پهپاد و دستگاههای اینترنت اشیا را مدلسازی مینماییم. در بخش چهارم، مسئله توأمان تخلیه بار محاسباتی و برنامهریزی مسیر پهپادها را با هدف کارآمدی انرژی کل سیستم و با لحاظ تحرک دستگاههای اینترنت اشیا فرمولهسازی مینماییم. همچنین الگوریتم پیشنهادی برای حل مسئله مدلسازیشده در این بخش ارائه شده است. در بخش پنجم، نتایج ارزیابی و مقایسه روش پیشنهادی با سایر روشها مورد بررسی قرار گرفته است. نهایتاً در بخش آخر نتیجهگیری و پیشنهادهایی برای کارهای آتی مطرح مینماییم.
2- کارهای پیشین
در این بخش به منظور آشنایی با روشهای تخلیه بار محاسباتی در رایانش لبه برای شبکههای مبتنی بر چند پهپاد، به بررسی کارهای مرتبط اخیر موجود در این حوزه پرداختهایم.
امروزه تحقیقات بسیاری بر موضوع بهینهسازی تخلیه بار محاسباتی در رایانش لبه تحت شرایط ایستا تمرکز کرده است که عمدتاً شامل تخلیه بار محاسباتی و بهینهسازی همزمان تخلیه بار محاسباتی و استقرار سرویس میباشد [1۴] و [1۵]. به عنوان مثال در [1۵] یک چارچوب بارگذاری آگاهانه انگیزشی18 برای کاهش هزینه تخلیه بار محاسباتی به سرورهای رایانش لبه پیشنهاد شده است. در [۱۶]، بهینهسازی همزمان مسیریابی درخواستهای کاربر و استقرار خدمات در شبکههای رایانش لبه با هدف کاهش سربار انتقال داده به ابر مورد بررسی قرار گرفته است. علاوه بر این، برخی از کارهای مرتبط به بررسی تخلیه بار محاسباتی در شبکههای رایانش لبه با لحاظ تحرک کاربر پرداختهاند. به طور خاص در [۱۷] یک چارچوب آگاه از تحرک مبتنی بر بهینهسازی لیاپانوف پیشنهاد شده که به تعادلی بین عملکرد سیستم و هزینه عملیاتی برای شبکههای رایانش لبه دست یافته است. همچنین با توجه به تحرک کاربران در [۱۸] یک روش محاسباتی پویا برای به حداقل رساندن تأخیر کلی سرویس ارائه شده است. هدف این کار، تخلیه بار محاسباتی به سرورهای لبه ایستا با استقرار دائم در شبکه میباشد و سناریوهایی با زیرساخت زمینی پراکنده یا غیر قابل اعتماد را در نظر نمیگیرند.
با توجه به محدودیت استفاده از گرههای لبه ایستا در محیطهایی که زیرساختهای ارتباطی زمینی به ندرت مستقر هستند و ارتباطات غیر قابل اعتماد هستند، استفاده از گرههای لبههای متحرک به یک نیاز تبدیل شده و توجه محققان را به خود جلب کرده است. به منظور ارائه پشتیبانی محاسباتی به کاربران نهایی در [۱۹] مسئله بهینهسازی همزمان مسیر پهپاد و تخصیص منابع در رایانش لبه مبتنی بر وسایل نقلیه به عنوان گرههای لبه مورد بررسی قرار گرفته و به شکل یک برنامهریزی غیرخطی عدد صحیح مختلط مدلسازی شده است. همچنین در [۲۰] به بهینهسازی همزمان تخلیه بار محاسباتی و مسیر پهپاد در رایانش لبه برای به حداقل رساندن تأخیر کلی همه کاربران پرداخته شده است. به منظور کاهش انرژی مصرفی پهپاد در [2۱] مسئله توأمان تخصیص منابع رایانشی پهپاد، تخصیص منابع رادیویی برای ارتباطات فراسو و فروسو و برنامهریزی مسیر پهپاد با لحاظ قیود تأخیر و بودجه انرژی پهپاد مدلسازی شده است.
در [22]، مسئله بهینهسازی همزمان انتخاب پهپاد جهت تخلیه بار محاسباتی کاربر، برنامهریزی مسیر پهپاد و تخصیص توان ارسال کابران با هدف بیشینه نمودن مجموع گذردهی تخلیه بار محاسباتی ضمن رعایت محدودیتهای انرژی پهپاد و کیفیت سرویس کاربران مورد توجه قرار گرفته است. در [۹] مسئله بهینهسازی همزمان برنامهریزی مسیر پهپاد، تخصیص توان ارسال کاربران و تخصیص منابع رایانشی پهپاد با هدف بیشینهنمودن انرژی پهپاد مدلسازی شده است. در این مقاله مکانهای کاربران ثابت یا از قبل شناختهشده فرض شده و پیچیدگی سیستم چند پهپاد موجود و مسیر پهپاد در نظر نگرفته است. در [23] به بهینهسازی توأمان تخلیه بار محاسباتی و برنامهریزی مسیر پهپادها در رایانش لبه برای به حداکثر رساندن کارایی انرژی پهپادها پرداخته شده است. با وجود اینکه کارایی انرژی پهپادها در این مقاله لحاظ شده است، انرژی مصرفی در لایه کاربران جهت انجام وظایف تخلیه نشده و در نتیجه کارایی انرژی کل سیستم در نظر گرفته نشده که هدف این مقاله بهبود موارد لحاظنشده این تحقیق است.
اگرچه برخی از راهحلهای رایانش لبه با کمک پهپاد در کارهای پیشین پیشنهاد شدهاند، هنوز برخی مسائل باز وجود دارد که باید به آنها پرداخت. به طور خاص، بیشتر کارهای مرتبط فرض میکنند که مکانهای کاربران ثابت یا از قبل شناختهشده هستند و به طور کامل و واقعگرایانه نحوه به دست آوردن مکانهای کاربران را در بازههای زمانی مختلف در نظر نگرفتهاند. همچنین در برخی از کارها فرض شده که موقعیت مکانی کاربران مبتنی بر اطلاعات جهانی به دست میآید که این امر ممکن است بعضاً ممکن نبوده یا به سختی به دست آید. علاوه بر این، غالب کارها عمدتاً بر روی یک پهپاد تمرکز میکنند که برای سناریوهای اینترنت اشیا در مقیاس بزرگ مناسب نیست. به عنوان نتیجهگیری، با توجه به چالشها و مسائل باز در کارهای مرتبط مسئله بهینهسازی همزمان تخلیه بار محساباتی و برنامهریزی مسیر در یک سیستم پهپادی پیچیده با پهپادهای متعدد با در نظر گرفتن تقاضای محاسباتی متغیر با زمان و تحرک کاربر نیاز به مطالعات بیشتر دارد. این مقاله از یک الگوریتم موقعیتیابی بلادرنگ TSIP نیز در فضای سهبعدی برای به دست آوردن اطلاعات مکان گرههای اینترنت اشیا استفاده میکند و یک الگوریتم تخلیه بار محاسباتی MECOP بر اساس اطلاعات محلی برای بهینهسازی کارایی انرژی سیستم طراحی میکند.
3- مدل سیستم پیشنهادی
سیستم پیشنهادی شامل لایه زمین و لایه لبه است. لایه لبه شامل پهپادهای متعددی است که دائماً در حال حرکت هستند و پشتیبانی محاسباتی را برای گرههای اینترنت اشیا در نزدیکی خود ارائه میکنند. در لایه زمین، چندین گره لنگر19 ثابت برای موقعیتیابی گره اینترنت اشیا در فضای سهبعدی مستقر شدهاند. با توجه به نیازهای مختلف، گرههای اینترنت اشیا دائماً حرکت میکنند و درخواستهایی را ایجاد میکنند. با توجه به ظرفیت محاسباتی و محدودیتهای توان گرههای اینترنت اشیا، درخواستها باید تا حد امکان به پهپادها بارگذاری شوند تا اجرا شوند. در غیر این صورت، آنها به صورت محلی اجرا میشوند. بنابراین ما باید به طور مشترک تصمیم تخلیه بار محاسباتی هر گره اینترنت اشیا و مسیر هر پهپاد را تعیین کنیم تا کارایی انرژی سیستم را به حداکثر برسانیم.
پهپاد با و
، گره لنگر با
و و گره اینترنت اشیا با
و
نشان داده میشود. به منظور تجزیه و تحلیل تغییرات دینامیکی، سیستم را بر اساس یک سناریوی شبکه شبهاستاتیک [19] و [24] مدلسازی میکنیم و زمان سیستم را با شکافهای زمانی متعدد،
و
نمایش میدهیم که طول هر شکاف زمانی
است.
3-1 مدلسازی محاسباتی
مدل کار محاسباتی به صورت و
مشخص شده است که به ترتیب نشاندهنده نوع کار، اندازه کار دادههای ورودی (به بیت) و شدت محاسباتی کار است.
میباشد که در آن
مجموعهای از کارها در شکاف زمانی
است. متغیر تصمیمگیری تخلیه بار محاسباتی گره
را در شکاف زمانی
به عنوان یک متغیر باینری
نشان داده میشود و
به این معناست که گره
کار را برای اجرا به پهپاد
تخلیه میکند، در غیر این صورت
میشود.
هر سرور لبه مجهز به چندین هسته CPU است که میتواند محاسبات موازی را برای چندین کار اینترنت اشیا به طور همزمان با به اشتراکگذاری پردازنده فراهم کند [2۵]. بنابراین اگر پهپاد به محل گره اینترنت اشیا
حرکت کند، میتواند پشتیبانی محاسباتی را برای یک مجموعه کاربری
که در مرکز
با شعاع
قرار دارد، ارائه دهد. توجه داشته باشید که حداکثر فرکانس سیکل پردازنده برای پهپاد
و انجام کارها
است.
3-2 مدلسازی ارتباطی
چون کارایی، ارتباط نزدیکی با مکان گرههای اینترنت اشیا و پهپادها دارد، ما هم تحرک گرههای اینترنت اشیا و هم پهپادها را در معماری تحقیق لحاظ میکنیم. برای نمایش مکان گرههای اینترنت اشیا و پهپادها یک سیستم مختصات دکارتی سهبعدی میسازیم. مکان گره اینترنت اشیا در شکاف زمانی به صورت
، مکان گره لنگر به صورت
و مکان پهپاد به صورت
بهدست میآید؛ پس بردار سرعت متوسط
در شکاف زمانی
به صورت زیر بیان میشود
(1)
به طور مشابه، بردار شتاب متوسط در شکاف زمانی به صورت زیر محاسبه میشود
(2)
و مسیر از
را میتوان به صورت زیر مشخص کرد
(3)
شکل 1: فلوچارت روش پیشنهادی.
کانال بین پهپاد و گره اینترنت اشیا به عنوان خط دید 20(LoS) در نظر گرفته میشود [2۲] و [۲۶]. بر اساس مدل از دست دادن مسیر فضای آزاد21 [۹] و [۲۷]، توان کانال بین و
طبق (4) محاسبه میشود
(4)
نماد هنجار اقلیدسی را نشان میدهد و
توان کانال دریافتی در فاصله مرجع
متر بین
و
است. در مدل دسترسی کانال غیرمتعامد22 [۹]، نرخ انتقال داده از گره اینترنت اشیا
در ارتباط با پهپاد
در شکاف زمانی
توسط [۲۸] و [۲۹] محاسبه میشود
(5)
که در آن پهنای باند،
توان انتقال
،
تداخل سیگنال و قدرت نویز است. بنابراین در شکاف زمانی
، اندازه دادههای بارگذاریشده از
به
به صورت زیر محاسبه میشود
(6)
اندازه دادههای تخلیهشده است اگر دادهها را بتوان بهطور کامل در شکاف زمانی
بارگذاری کرد. در غیر این صورت (6) مقدار دادهای است که میتوان بارگذاری کرد و باید محاسبه گردد.
3-3 مدلسازی انرژی مصرفی
1) مدل مصرف انرژی پهپاد: برای مصرف انرژی نیروی محرکه پهپاد، ما یک مدل مصرف انرژی پرواز پهپاد اتخاذ کردیم [۳۰]. مصرف انرژی پرواز پهپاد در شکاف زمانی
مربوط به شتاب و سرعت آنی آن است که میتوان آن را به صورت زیر محاسبه کرد
(7)
که در آن و
پارامترهای ثابتی هستند که عمدتاً مربوط به وزن و بال پهپاد هستند و
نشاندهنده شتاب گرانشی است [۹] و [۳۰].
مصرف انرژی محاسباتی یک پهپاد عمدتاً به مقدار کارهای بارگذاریشده و فرکانس اجرایی مربوط میشود. در شکاف زمانی ، مصرف انرژی محاسباتی
در اجرای کار
برای
را میتوان به صورت زیر محاسبه کرد
(8)
که در آن ظرفیت سوئیچ مؤثر پردازنده پهپاد [2۱] و [2۲] و
فرکانس اجرای واقعی CPU برای کار
است. از آنجا که مصرف انرژی پهپاد ناشی از انتقال دادهها کمتر از مصرف انرژی در پرواز و محاسبات است، مصرف انرژی پهپاد به دلیل ارتباطات را نادیده میگیریم [۲۸].
2) مدل مصرف انرژی گره لنگر: انرژی اولیه گره لنگر را به عنوان
تعریف میکنیم و انرژی باتری در ابتدای شکاف زمانی
به صورت
بیان میشود که در آن
بیان میشود. بنابراین انرژی گره لنگر
در شکاف زمانی
به صورت زیر بیان میشود
(9)
که در آن تعداد دفعاتی را نشان میدهد که گره لنگر
به عنوان واحد موقعیتیابی در شکاف زمانی
انتخاب میشود و
کل انرژی مصرفشده آن در موقعیتیابی گرههای
اینترنت اشیا است.
3) مدل مصرف انرژی گره اینترنت اشیا: در این قسمت به محاسبه سربار حاصل از اجرای محلی یک کاربر از نظر تأخیر و همچنین مصرف انرژی میپردازیم. برای محاسبه تأخیر محاسبات در گره اینترنت اشیا مطابق زیر عمل میکنیم [۳1]
(10)
در فرمول بالا فرکانس پردازنده کاربر
میباشد. همچنین برای محاسبه انرژی مصرفی محلی داریم
(11)
که مقدار و
توسط پردازنده کاربر تعیین میشوند.
4- روش پیشنهادی تخلیه بار محاسباتی و برنامهریزی مسیر آگاه از تحرک و انرژی
در این بخش، در ابتدا برای به حداکثر رساندن کارایی انرژی به فرمولهسازی مسئله بهینهسازی توأمان تخلیه بار محاسباتی و برنامهریزی مسیر پهپاد میپردازیم. سپس برای در نظر گرفتن تحرک گرههای اینترنت اشیا از الگوریتم موقعیتیابی TSIP استفاده میکنیم که مکان گرههای اینترنت اشیا را مطابق با قضیه انتخاب گره لنگر پیدا میکند و برای مقابله با پیچیدگی سیستم ناشی از چندین گره اینترنت اشیا و پهپادها، الگوریتم MECOP را برای ساخت مجموعه پوشش کاربردی برای پهپادها و ارائه پشتیبانی محاسباتی از چندین گره اینترنت اشیا برای بهبود کارایی انرژی سیستم پیشنهاد میکنیم. در شکل 1 مراحل اجرای روش پیشنهادی به صورت فلوچارت نمایش داده شده است.
4-1 فرمولهسازی مسئله
انجام پردازشهای محلی، حرکت و اجرای پهپادهایی که از گرههای اینترنت اشیا پشتیبانی محاسباتی میکنند، هزینه انرژی را به همراه خواهد داشت. هدف ما به حداکثر رساندن کارایی انرژی کل است که به صورت زیر بیان شده است
(12)
این فرایند شامل دو متغیر ضروری است، از جمله تصمیم تخلیه بار محاسباتی گره اینترنت اشیا و برنامهریزی مسیر پهپاد
. ما کارایی انرژی را به عنوان نسبت مقدار دادههای کار پردازششده به انرژی مصرفشده به صورت محلی بر روی گره اینترنت اشیا و یا اجرا بر روی پهپاد تعریف میکنیم که میتواند به صورت زیر نشان داده شود
(13)
در این سیستم، مقادیر متغیرها به هنگام رخداد تخلیه بار محاسباتی بر روی پهپادها به این صورت است که مقدار به معنای دادههای بارگذاری شده از
به
میباشد که این دادهها توسط پهپاد
پردازش میشوند. این دادههای بارگذاریشده نمایانگر عملکرد اجرای پهپادها هستند که پشتیبانی محاسباتی برای گرههای اینترنت اشیا ارائه میدهند. مقدار
نشاندهنده مصرف انرژی نیروی محرکه پهپاد
و
نشاندهنده مصرف انرژی محاسباتی پهپاد برای داده
است. همچنین مقادیر متغیرها به هنگام اجرای محلی به این صورت است که مقدار
که مقدار کل داده است به صورت محلی اجرا میشود و
نشاندهنده سرعت انجام کار دستگاه اینترنت اشیاست. همچنین
مصرف انرژی محاسباتی محلی گره اینترنت اشیا را نشان میدهد.
در (۱5) چون قسمت تخلیه بار محاسباتی بر روی پهپاد نسبت داده به انرژی مصرفی است ولی قسمت اجرای محلی نسبت سرعت انجام کار به انرژی مصرفی است، امکان جمع این دو کسر را نداریم. برای اینکه بتوان هر دو قسمت را با هم جمع کرد، باید نرمالسازی انجام دهیم که بر حداکثر مقدار هر دو کسر تقسیم میکنیم. همچنین محدویتهای (14) تا (19) باید در (12) اعمال گردند.
متغیر تصمیم تخلیه بار محاسباتی باید محدودیت زیر را برآورده کند
(14)
دادههای یک گره اینترنت اشیا را فقط میتوان در یک پهپاد برای اجرا بارگذاری کرد و ما داریم
(15)
برای پهپاد ، حداکثر محدودیت منبع محاسباتی باید برآورده شود، یعنی
(16)
برای گره اینترنت اشیا ، حداکثر محدودیت منبع محاسباتی باید برآورده شود، یعنی
(17)
مجموعه کاربر در دامنه پوشش پهپاد
است که در موقعیت
در شکاف زمانی
واقع شده است. اگر
به
تعلق نداشته باشد، کار آن را نمیتوان در
بارگذاری کرد، به عبارت دیگر، تصمیم تخلیه بار محاسباتی مطابق با این شرط است
(18)
در فرایند موقعیتیابی، واحد موقعیتیابی باید با انتخاب چندین گره لنگر ساخته شود. گرههای لنگر در واحد موقعیتیابی باید برآورده شوند
(19)
(20)
جایی که فاصله
تا
است،
و
به ترتیب محدوده ارتباطی و محدودیت آستانه انرژی هستند.
در مدل بهینهسازی ارائهشده، دو مسئله کلیدی وجود دارد که باید حل شود. از یک طرف به دلیل عدم قطعیت تحرک گرههای اینترنت اشیا، طراحی یک الگوریتم موقعیتیابی بلادرنگ23 برای به دست آوردن اطلاعات موقعیت گرههای اینترنت اشیا به موقع برای ارائه پشتیبانی محاسباتی دقیق و کارآمد ضروری است. از سوی دیگر، تصمیمات مشترک تخلیه بار محاسباتی و پردازش محلی برای گرههای اینترنت اشیا در مقیاس بزرگ و برنامهریزی مسیر برای پهپادهای متعدد، پیچیدگی محاسباتی بالایی دارد. سیستم فاقد مدیریت متمرکز است و راهحلهای بهینهسازی سنتی مبتنی بر اطلاعات جهانی قابل اجرا نیستند. به منظور حل مسائل فوق، ابتدا از یک الگوریتم موقعیتیابی TSIP استفاده شده و سپس یک الگوریتم تخلیه بار محاسباتی در رایانش لبه مجهز به چند پهپاد MECOP را پیشنهاد شده است.
4-2 الگوریتم موقعیتیابی فضایی سهبعدی هوشمند
در ادامه الگوریتم فضایی هوشمند سهبعدی را جهت موقعیتیابی دقیق گرههای اینترنت اشیا مبتنی بر [2۳] ارائه میکنیم. در فضای سهبعدی، مختصات مکان گره اینترنت اشیا را میتوان با معرفی 4 گره لنگر غیرهمسطح و اندازهگیری فاصله
از گره لنگر
به گره اینترنت اشیا
محاسبه کرد. با این حال دررشرایط واقعی، ممکن است خطاهایی در اندازهگیری فاصله وجود داشته باشد که بر دقت موقعیتیابی تأثیر گذارد. به منظور افزایش دقت موقعیتیابی گرههای اینترنت اشیا باید گرههای لنگر قابل اعتمادتری را در ساخت واحدهای موقعیتیابی انتخاب کنیم. قضیه 1 (قضیه انتخاب گره لنگر) و نتیجه 1 پیشنهادی، راهنمای نظری برای ساخت واحدهای موقعیتیابی ارائه میدهد.
قضیه 1: زاویه بین هر دو گره لنگر و یک گره اینترنت اشیا برابر با 4736/109 درجه باشد، راهحل موقعیتیابی خطا حداقل مقدار را دارد.
اثبات در فرایند موقعیتیابی، خطای اندازهگیری را به صورت نشان میدهد، سپس فاصله تخمینی فاصله 4 گره لنگر
را میتوان در فضایی محصورشده توسط هشت سطح کروی محصور کرد. حجم دامنه فضایی میتواند به عنوان فاصله خطای موقعیتیابی گره اینترنت اشیا باشد. سطوح کروی حوزه فضایی به صورت یک هشتضلعی را تشکیل میدهند. با توجه به رابطه هندسی و تقارن هشتوجهی میتوان حجم را با
شکل 2: موقعیتیابی فضایی سهبعدی هوشمند.
(21)
که در آن مساحت چهارضلعی ABCD است و
برابر است با
حداقل مقدار
و
حداکثر مقدار را وقتی
به دست میآورد. از سوی دیگر برای
، مقدار
قرار میدهد. نقطه انتهایی آن را با
اشتقاق به دست میآوریم و با توجه به دامنه تعریف و ویژگیهای مشتق
دوم، وقتی و
درجه شود، حجم هشتوجهی به حداقل مقدار یعنی میرسد؛ یعنی خطای موقعیتیابی مربوطه به حداقل مقدار میرسد.
بنابراین قضیه 1 اثبات میشود.
نتیجه 1: در فرایند موقعیتیابی فضای سهبعدی، اگر تعداد گرههای لنگر موقعیتیابی موجود بیش از 4 عدد باشد، میتوانیم هر دو گره لنگر با زاویه بین آها و گره اینترنت اشیا نزدیک به 4736/109 درجه را برای ساخت واحد موقعیتیابی انتخاب کنیم که این نتیجه میتواند خطای موقعیتیابی را کاهش دهد.
سپس ما TSIP را برای بهدست آوردن اطلاعات مکان گرههای اینترنت اشیا پیشنهاد میکنیم. مجموعه گرههای لنگر را به صورت مشخص میکنیم که در آن هر گره لنگر حاوی مکان است. اطلاعات انرژی و فاصله با
نشان داده میشود. ابتدا گرههای لنگر موجود را که محدودیتهای (1۹) و (۲۰) را برآورده میکنند، انتخاب میکنیم و آنها را به مجموعه گرههای لنگر موجود
اضافه میکنیم. هدف ما استفاده از گرههای لنگر با انرژی باقیمانده بیشتر برای افزایش طول عمر سیستم است. TSIP به طور تصادفی گرههای لنگر موجود را از
انتخاب میکند و واحد موقعیتیابی
را از طریق قضیه انتخاب گره لنگر میسازد، سپس آنها را به مجموعه واحد موقعیتیابی
اضافه میکند و
آستانه اختلاف بین زاویه واقعی و زاویه بهینه است. سپس TSIP مختصات موقعیت گره اینترنت اشیا
را توسط واحد موقعیتیابی محاسبه میکند. همان طور که در شکل 2 مشاهده میکنید، الگوریتم TSIP شبیهسازی شده است.
4-3 الگوریتم MECOP
این الگوریتم پیشنهادی دو مسئله کلیدی را حل میکند: تصمیم تخلیه بار محاسباتی و اجرای محلی و برنامهریزی مسیر پهپاد
. یعنی نحوه تصمیمگیری
و
برای ارائه پشتیبانی محاسباتی گرههای اینترنت اشیا برای به حداقل رساندن مصرف انرژی پهپاد چگونه باشد
را به عنوان کاربر در پوشش پهپاد
با محوریت گره اینترنت اشیا
در شکاف زمانی
مشخص میشود که موقعیت دقیق گره اینترنت اشیا
از طریق الگوریتم TSIP بهدست میآید. به دلیل به اشتراکگذاری پردازنده، یک پهپاد میتواند درخواستهای کار از چندین گره اینترنت اشیا را به طور همزمان پردازش کند [25]. بنابراین تعاریف زیر را بیان میکنیم.
تعریف 1: مجموعهای که در آن درخواستهای کاربر را میتوان از به پهپاد
تخلیه کرد، مجموعه پوشش
با مرکز
است که به صورت
بیان میشود [23].
ایده اصلی MECOP این است که هر گره اینترنت اشیا با ایجاد یک مجموعه پوشش متمرکز روی خودش بر اساس اطلاعات محلی، تصمیم تخلیه بار محاسباتی را میگیرد. هر گره اینترنت اشیا بهطور متوالی کاربران را به مجموعه پوشش با توجه به کارایی انرژی اضافه میکند تا کارایی انرژی کلی سیستم را به حداکثر برساند. سپس مسیر هر پهپاد با توجه به تصمیمگیری در مورد کارایی انرژی بهینه سیستم برنامهریزی میشود. اگر هر داده نیز نتواند به طور کامل بر روی پهپاد اجرا شود، باقیمانده آن به صورت محلی اجرا میشود. همان طور که اشاره کردیم، مجموعه پوشش بدین معناست که اگر
به مکان
پرواز کند، درخواستهای کاربران در این مجموعه میتواند تحت محدودیت منابع پهپاد به
بارگذاری شود. از آنجا که در سیستم رایانش لبه مجهز به پهپاد، درخواستهای تخلیه بار متغیر با زمان از گرههای اینترنت اشیا وجود دارد، تابع
راندمان انرژی سیستم را تعریف میکنیم. به طور خاص، تابع افزودن
به مجموعه پوشش
به صورت زیر تعریف شده است
(22)
به طور کلی، مصرف انرژی یک پهپاد در حال حرکت به سمت مکان هدف ناوبری هر گره اینترنت اشیا در مجموعه پوشش تقریباً برابر است. بنابراین کارایی انرژی گره اینترنت اشیا در هنگام ساخت مجموعه پوشش بدون تغییر است. بر اساس تابع بهره فوق، تابع کل
را برای پهپاد
به صورت زیر محاسبه میکنیم
(23)
تعریف 2: سود کل حداکثر مقدار در (2۳) برای است، به عنوان حداکثر مجموعه پوشش
تعریف میشود که به صورت
بیان میشود.
اگر کاربر مرکزی
باشد، به این معناست که پرواز
به محل آن (مختصات افقی) میتواند حداکثر کارایی انرژی را به همراه داشته باشد. توجه کنید که هر کاربر میتواند برای ساخت مجموعهای از پوشش برای یک پهپاد خودمحور باشد اما فرایندهای انتخاب و نگهداری حداکثر مجموعه پوشش نیاز به ارتباطات و توافقهای اجماع24 بین گرههای اینترنت اشیا دارد.
شکل 3: الگوریتم توأمان تخلیه بار محاسباتی و برنامهریزی مسی آگاه از تحرک و انرژی.
الگوریتم MECOP با توجه به مجموعه پوشش ایجادشده، قادر به اتخاذ تصمیمات توأمان تخلیه بار محاسباتی و برنامهریزی مسیر پهپادها به منظور بهبود کارایی انرژی کل سیستم است. MECOP (شکل 3) از سه مرحله اصلی تشکیل شده است: ١) ساخت مجموعه پوشش کاربردی، ٢) اخذ تصمیمات تخلیه بار محاسباتی یا اجرای محلی و ٣) بهروزرسانی و حفظ حداکثر مجموعه پوشش مطلوبش 32 سیستم از طریق ارتباطات و توافقات اجماع. در این روند، هر کاربر تصمیمات تخلیه بار محاسباتی را انجام میدهد و سپس مجموعهای از پوشش کاربردی بر اساس ایده حریصانه ساخته میشود. در هر مرحله، اطلاعات تصمیمگیری از طریق ارتباطات به دست میآید و یک مجموعه پوشش ایجاد میشود. سپس هر کاربر حداکثر پوشش مطلوب خود را با توافق با همسایگان بهروز میکند و حفظ میکند. MECOP هنگامی که کاربران و همسایگانشان حداکثر پوشش مطلوب را برای هر پهپاد تعیین میکنند، تکرار را متوقف کرده و تصمیمات مربوط به تخلیه بار محاسباتی یا اجرای محلی و برنامهریزی مسیر پهپاد را اجرا میکند و کارایی انرژی سیستم را محاسبه میکند.
5- ارزیابی روش پیشنهادی
در این بخش، عملکرد روش MECOP پیشنهادی را از طریق پیادهسازی در ابزار Matlab و مقایسه با سایر روشهای مشابه تحت شرایط و سناریوهای مختلف مورد ارزیابی قرار میدهیم. به این منظور
با الهام از [۲3]، محیط شبیهسازی لحاظشده یک فضای سهبعدی متر مکعب میباشد که در آن 110 گره لنگر و 1000 گره اینترنت اشیا مستقر شدهاند و 3 پهپاد پشتیبانی محاسباتی را برای گرههای اینترنت اشیا ارائه میکنند. برای ارزیابی فرایند بهینهسازی پویا
جدول 1: پارامترهای ارزیابی.
پارامتر ارزیابی | مقدار |
تعداد گره اینترنت اشیا | 300- 1000 |
تعداد گره لنگر | 110 |
تعداد پهپاد | 3 |
حداکثر فرکانس سیکل پردازنده پهپاد | 4- 17 گیگاهرتز |
آستانه انرژی | 5 |
آستانه تفاوت بین زاویه واقعی و زاویه بهینه | 15 درجه |
سرعت پردازش مورد نیاز مؤلفه | 4 مگاهرتز |
توان کانال دریافتی | 50- دسیبل |
توان انتقال | 1 وات |
قدرت نویز | 110- |
ارتفاع پهپاد | ثابت |
10-4 × 26/9 | |
بال پهپاد | 2250 |
MECOP، ما از سناریوهای شبکه شبه استاتیک برای شبیهسازی استفاده میکنیم [۱۹] و [۲۱]. به طور خاص در یک شکاف زمانی، مکانهای گرههای پهپاد و اینترنت اشیا ثابت هستند، اما گرههای اینترنت اشیا بین شکافهای زمانی مختلف تحرک دارند. به منظور ارزیابی جامع عملکرد الگوریتمها، گرههای اینترنت اشیا از دو مدل حرکتی در شبیهسازیها پیروی میکنند: مدل حرکت مبتنی بر نقشه برای 40 درصد گرههای اینترنت اشیا و مدل حرکت تصادفی برای 60 درصد باقیمانده گرههای اینترنت اشیا اجرا میشود [۲3]. در هر شکاف زمانی، گرههای اینترنت اشیا به طور تصادفی درخواستهایی با احتمال تولید میکنند. اندازه کار اینترنت اشیا
به طور یکنواخت در [5/2، 5/0] مگابیت توزیع شده و اندازه محاسبات مورد نیاز
به طور یکنواخت در بازه [1000، 500] چرخه در بیت25 توزیع شده است [۲3]. برخی از پارامترهای مهم ارزیابی مورد استفاده در شبیهسازیها در جدول 1 نشان داده شده است. مطابق این جدول، مقدار پارامترهای مربوط به پهپاد بر اساس [9] مبتنی بر ویژگیهای پهپاد در دنیای واقعی و سایر پارامترها بر اساس [23] تنظیم شده است.
ما بین الگوریتم خود و الگوریتمهای زیر نیز مقایسههای عملکردی انجام میدهیم: ۱) الگوریتم تخلیه بار محاسباتی توزیعشده 26(DCOP) [۲3]: با ساخت مجموعه پوشش تخلیه بار محاسباتی انجام میشود و فقط کارایی انرژی لایه پهپاد محاسبه میشود. 2) الگوریتم نزدیکترین کاربر اول 27(NUFA) [۲0]: پهپادها مجموعه پوشش ابزاری را روی نزدیکترین کاربر ایجاد میکنند و پشتیبانی محاسباتی را ارائه میکنند. 3) الگوریتم بهینهسازی تصادفی 28(ROA) [۲2]: پهپادها بهطور تصادفی کاربرانی را انتخاب میکنند که وظایفی برای ساخت مجموعه پوشش ابزار و انجام بارگذاری محاسباتی دارند. ما عملکرد الگوریتمها را بر اساس معیارهای زیر ارزیابی میکنیم: کارایی انرژی، سودمندی سیستم و مصرف انرژی.
5-1 بررسی کارایی انرژی
کارایی انرژی، معیار عملکرد مهمی است که نشاندهنده کارایی اجرای
شکل 4: بررسی تأثیر تعداد کاربران بر کارایی انرژی.
شکل 5: بررسی تأثیر تعداد کاربران بر سودمندی سیستم.
سیستم رایانش لبه دارای چند پهپاد است. ما کارایی انرژی الگوریتم پیشنهادی خود را ارزیابی میکنیم و الگوریتمها را تحت تعداد متفاوت گرههای اینترنت اشیا و قابلیتهای پردازش پهپاد مقایسه میکنیم، همان طور که در (13) نشان داده شده است. MECOP پیشنهادی ما حداکثر مجموعه پوشش کاربردی را بر اساس کارایی انرژی و هزینه منابع ایجاد میکند. نتایج شبیهسازی کارایی انرژی در شکل 4 نشان داده شده است، جایی که میتوانیم مشاهده کنیم که MECOP به بالاترین کارایی انرژی دست مییابد. به طور خاص، زمانی که تعداد گرههای اینترنت اشیا ۵۰۰ باشد، کارایی انرژی MECOP 2/1 است که نسبت به NUFA 97/0 واحد انرژی، نسبت به ROA 84/0 واحد انرژی و نسبت به DCOP 4/0 واحد انرژی ارتقا یافته است. MECOP هم کاربرد و هم مصرف انرژی پهپادها را در ساخت مجموعه پوشش شهری در نظر میگیرد و حداکثر مجموعه پوشش کاربردی را برای برنامهریزی مسیر پهپاد و انجام تخلیه بار محاسباتی انتخاب میکند. الگوریتم پیشنهادی با توجه به ویژگیهای سیستم و محدودیتهای مصرف انرژی، بهترین راهکار برای بهینهسازی مصرف انرژی و افزایش کارایی عمومی سیستم را ارائه میدهد.
5-2 بررسی سودمندی سیستم
سودمندی سیستم، مقدار دادههای پردازششده است که نشاندهنده توانایی پهپادها برای ارائه پشتیبانی محاسباتی از گرههای اینترنت اشیا و
شکل 6: بررسی تأثیر تعداد کاربران بر مصرف انرژی.
توانایی پردازش در خود گرههای اینترنت اشیا است. شکل 3 ابزار سیستم را تحت تعداد مختلف گرههای اینترنت اشیا نشان میدهد. به طور خاص، همان طور که در شکل 3 نشان داده شده است، زمانی که تعداد گرههای اینترنت اشیا 700 باشد، سودمندی سیستم MECOP 5/94 مگابایت است که نسبت به ROA که 63 مگابایت است 5/31 مگابایت ارتقا یافته است. دلیل اصلی این است که MECOP مقدار دادههای بارگیریشده از گرههای اینترنت اشیا و منابع محاسباتی اشغالشده توسط وظایف را در نظر میگیرد، کاربران را با توجه به نسبت سودمندی به هزینه اضافه میکند و حداکثر مجموعه پوشش را برای اجرا انتخاب میکند. MECOP سودمندی سیستم را بهبود میبخشد و پشتیبانی محاسباتی قدرتمندی را برای گرههای اینترنت اشیا ارائه میدهد.
5-3 بررسی مصرف انرژی
مصرف انرژی پهپادها و انرژی محاسباتی گرههای اینترنت اشیا یک معیار اساسی برای ارزیابی عملکرد سیستم است و متأثر از تصادفیبودن حرکت کاربر است. شکل 4 مقدار متوسط مصرف انرژی را نشان میدهد. میانگین مصرف انرژی الگوریتم MECOP به نسبت الگوریتم DCOP ارتقا کمتر و به نسبت الگوریتم NUFA و الگوریتم ROA ارتقا بیشتری یافته است. بهطور مقایسهای، متوسط مصرف انرژی برای الگوریتم MECOP با 600 گره اینترنت اشیا حدود 71/4 کیلوژول است که به ترتیب 34/8، 29/3 و 5/0 کیلوژول کمتر از الگوریتمهای ROA، NUFA و DCOP است. این نتایج نشان میدهند که الگوریتم MECOP با استفاده از دادههای پردازششده از گرههای اینترنت اشیا و همچنین بهینهسازی مسیر پهپادها میتواند به طور قابل توجهی مصرف انرژی را کاهش دهد و از این رو کارایی و عملکرد کلی سیستم را ارتقا دهد.
6- نتیجهگیری
در این مقاله، مسئله بهینهسازی توأمان تخلیه بار محاسباتی و برنامهریزی مسیر پهپادها با لحاظ تحرک دستگاههای اینترنت اشیا و با هدف بیشینهکردن کارامدی انرژی کل سیستم مدلسازی شده است.
در مدل پیشنهادی، تصمیم تخلیه بار محاسباتی و تعیین موقعیت جدید پهپادها بر اساس کارایی انرژی کل سیستم در هر دو لایه پهپاد و دستگاههای اینترنت اشیا و با احتساب هزینه وظایف اجرا شده به صورت محلی علاوه بر وظایف تخلیهشده اخذ میگردد. همچنین به منظور حل مدل پیشنهادی در مدت زمان قابل قبول، یک الگوریتم حل توأمان مسئله تخلیه بار محاسباتی و برنامهریزی مسیر پهپادها مبتنی بر مجموعه پوشش کاربردی پیشنهاد شده است. در این الگوریتم با توجه به تحرک دستگاههای اینترنت اشیا، موقعیت آنها را طبق روش موقعیتیابی هوشمند فضایی سهبعدی محاسبه مینماییم. نتایج شبیهسازی نشان دادهاند که MECOP سودمندی سیستم، مصرف انرژی پهپادها وگرههای اینترنت اشیا و کارآمدی انرژی کل سیستم را به طور قابل توجهی بهبود میبخشد.
به عنوان یکی از کارهای آتی در نظر داریم مدل پیشنهادی را با رعایت قید تأخیر کاربردهای دارای محدودیت زمانی مورد حل قرار داده و در شبیهسازهای مخصوص شبکههای چندپهپاد پیادهسازی و ارزیابی نماییم. در ادامه، در نظر داریم ضمن ارائه یک روش مبتنی بر یادگیری جهت پیشبینی تحرک دستگاههای اینترنت اشیا، تصمیم بهینه مسئله توأمان تخلیه بار محاسباتی و برنامهریزی مسیر را بر اساس پیشبینی تحرک مورد حل قرار دهیم. همچنین به عنوان یکی دیگر از کارهای آتی، مسئله تخصیص منابع محاسباتی پهپادها را در کنار تصمیم تخلیه بار محاسباتی و برنامهریزی مسیر در محیطهای دارای تداخل و موانع برای بهبود قابلیت اطمینان و پایداری سیستم مد نظر قرار خواهیم داد.
مراجع
[1] Statista Research Department, Internet of Things - Number of Connected Devices Worldwide 2015-2025, https://www.statista.com/statistics/471264/iot-number-of-connected-devices-worldwide/, Date Published: Nov 27, 2016, Last Access on Feb. 2024.
[2] C. Mateos, K. R. Choo, and A. Zunino, "Sharpening the edge: towards improved edge computing environment for mobile and IoT applications," Future Gener. Comput. Syst., vol. 107, pp. 1130-1133, Jun. 2020.
[3] W. Zhuang, Q. Ye, F. Lyu, N. Cheng, and J. Ren, "SDN/NFV-empowered future IoV with enhanced communication, computing, and caching," Proceedings of the IEEE, vol. 108, no. 2, pp. 274-291, Feb. 2020.
[4] T. Zhang, Y. Xu, J. Loo, D. Yang, and L. Xiao, "Joint computation and communication design for UAV-assisted mobile edge computing in IoT," IEEE Trans. Ind. Inform., vol. 16, no. 8, pp. 5505-5516, Oct. 2020.
[5] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, "A survey on mobile edge computing: the communication perspective," IEEE Commun. Surv. Tut., vol. 19, no. 4, pp. 2322-2358, Jan. 2017.
[6] X. Xiong, K. Zheng, L. Lei, and L. Hou, "Resource allocation based on deep reinforcement learning in IoT edge computing," IEEE J. Sel. Areas Commun., vol. 38, no. 6, pp. 1133-1146, Apr. 2020.
[7] Z. Chang, L. Liu, X. Guo, and Q. Sheng, "Dynamic resource allocation and computation offloading for IoT fog computing system," IEEE Trans. Ind. Inform., vol. 17, no. 5, pp. 3348-3357, Jun. 2021.
[8] X. Hu, K. Wong, K. Yang, and Z. Zheng, "UAV-assisted relaying and edge computing: scheduling and trajectory optimization," IEEE Trans. Wirel. Commun., vol. 18, no. 10, pp. 4738-4752, Dec. 2019.
[9] M. Li, N. Cheng, J. Gao, Y. Wang, L. Zhao, and X. Shen, "Energy efficient UAV-assisted mobile edge computing: resource allocation and trajectory optimization," IEEE Trans. Veh. Technol., vol. 69,
no. 3, pp. 3424-3438, Jan. 2020.
[10] L. D. Nguyen, A. E. Kalør, I. L. Mayorga, and P. Popovski, "Trusted wireless monitoring based on distributed ledgers over NB-IoT connectivity," IEEE Commun. Mag., vol. 58, no. 6, pp. 77-83, Apr. 2020.
[11] M. Pradhan and J. Noll, "Security, privacy, and dependability evaluation in verification and validation life cycles for military IoT systems," IEEE Commun. Mag., vol. 58, no. 8, pp. 14-20, Aug. 2020.
[12] Z. Tan, H. Qu, J. Zhao, S. Zhou, and W. Wang, "UAV-aided edge/fog computing in smart IoT community for social augmented reality," IEEE Internet Things J., vol. 7, no. 6, pp. 4872-4884, Feb. 2020.
[13] F. Zhou, Y. Wu, R. Q. Hu, and Y. Qian, "Computation rate maximization in UAV-enabled wireless-powered mobile-edge computing systems," IEEE J. Sel. Areas Commun., vol. 36, no. 9,
pp. 1927-1941, Jun. 2018.
[14] L. Li, T. Q. S. Quek, J. Ren, H. H. Yang, Z. Chen, and Y. Zhang, "An incentive-aware job offloading control framework for multi-access edge computing," IEEE Trans. Mobile Comput., vol. 20,
no. 1, pp. 63-75, Jan. 2021.
[15] K. Poularakis, J. Llorca, A. M. Tulino, I. J. Taylor, and L. Tassiulas, "Service placement and request routing in MEC networks with storage, computation, and communication constraints," IEEE/ACM Trans. Netw., vol. 28, no. 3, pp. 1047-1060, Apr. 2020.
[16] J. Chen, Z. Chang, X. Guo, R. Li, Z. Han, and T. Hamalainen, “Resource allocation and computation offloading for multi-access edge computing with fronthaul and backhaul constraints,” IEEE Trans. Veh. Technol., vol. 70, no. 8, pp. 8037–8049, Aug. 2021.
[17] T. Ouyang, Z. Zhou, and X. Chen, "Follow me at the edge: mobilityaware dynamic service placement for mobile edge computing," IEEE J. Sel. Areas Commun., vol. 36, no. 10, pp. 2333-2345, Sept. 2018.
[18] S. Wang, Y. Guo, N. Zhang, P. Yang, A. Zhou, and X. Shen, "Delayaware microservice coordination in mobile edge computing:
a reinforcement learning approach," IEEE Trans. Mobile Comput., vol. 20, no. 3, pp. 939-951, Dec. 2021.
[19] Y. Liu, Y. Li, Y. Niu, and D. Jin, "Joint optimization of path planning and resource allocation in mobile edge computing," IEEE Trans. Mobile Comput., vol. 19, no. 9, pp. 2129-2144, Sept. 2020.
[20] F. Guo, H. Zhang, H. Ji, X. Li, and V. C. Leung, "Joint trajectory and computation offloading optimization for UAV-assisted MEC with NOMA," in Proc. IEEE Conf. Comput. Commun. Workshops, 6 pp., Paris, France, 29 Apr.-2 May 2019.
[21] S. Jeong, O. Simeone, and J. Kang, "Mobile edge computing via a UAV-mounted cloudlet: optimization of bit allocation and path planning," IEEE Trans. Veh. Technol., vol. 67, no. 3, pp. 2049-2063, Sept. 2018.
[22] Y. Qian, et al., "User association and path planning for UAV-aided mobile edge computing with energy restriction," IEEE Wirel. Commun. Lett., vol. 8, no. 5, pp. 1312-1315, Apr. 2019.
[23] X. Chen, et al., "Distributed computation offloading and trajectory optimization in multi-uav-enabled edge computing," IEEE Internet of Things, vol. 9, no. 20, pp. 20096-20110, May 2022.
[24] Q. Ye, et al., "Learningbased computing task offloading for autonomous driving: a load balancing perspective," in Proc. IEEE Int. Conf. Commun., 6 pp., Montreal, Canada, 14-23 Jun. 2021.
[25] I. A. Elgendy, S. Meshoul, and M. Hammad, "Joint task offloading, resource allocation, and load-balancing optimization in multi-UAV-aided MEC systems," Applied Sciences, vol. 13, no. 4, Article ID: 2625, Feb. 2023.
[26] B. Li, et al., "Robust computation offloading and trajectory optimization for multi-UAV-assisted MEC: a multi-agent DRL approach," IEEE Internet of Things J., vol. 11, no. 3, pp. 4775-4786, Aug. 2023.
[27] Z. Yu, Y. Gong, S. Gong, and Y. Guo, "Joint task offloading and resource allocation in UAV-enabled mobile edge computing," IEEE Internet Things J., vol. 7, no. 4, pp. 3147-3159, Jan. 2020.
[28] Y. Wang, Z. Ru, K. Wang, and P. Huang, "Joint deployment and task scheduling optimization for large-scale mobile users in multi-UAV-enabled mobile edge computing," IEEE Trans. Cybern., vol. 50, no. 9, pp. 3984-3997, Sept. 2020.
[29] A. Ranjha, G. Kaddoum, M. Rahim, and K. Dev, "URLLC in UAV-enabled multicasting systems: a dual time and energy minimization problem using UAV speed, altitude and beamwidth," Computer Communications, vol. 187, pp. 125-133, Apr. 2022.
[30] N. Lin, H. Tang, L. Zhao, S. Wan, A. Hawbani, and M. Guizani,
"A PDDQNLP algorithm for energy efficient computation offloading in UAV-assisted MEC," IEEE Trans. on Wireless Communications, vol. 22, no. 12, pp. 8876-8890, Dec. 2023.
[31] M. Ma and Z. Wang, "Distributed offloading for multi-uav swarms in mec-assisted 5G heterogeneous networks," Drones, vol. 7, no. 4, Article ID: 226, Mar. 2023.
کیمیا قاسمی دوره کارشناسی خود را در رشته مهندسی کامپیوتر طی سالهای ۱۳۹۵ تا ۱۳۹۹ در دانشگاه شریعتی تهران به پایان رسانده است. وی در ادامه، تحصیلات خود را در مقطع کارشناسی ارشد مهندسی کامپیوتر با گرایش شبکههای کامپیوتری در دانشگاه علم و صنعت ایران ادامه داده و در سال ۱۴۰۲ فارغالتحصیل شده است. حوزههای علاقهمندی پژوهشی ایشان شامل شبکههای کامپیوتری و مهندسی نرمافزار میباشد.
زینب موحدی مدرک کارشناسی خود را در سال 1384 از دانشگاه سندنی فرانسه و مدارک کارشناسی ارشد و دکتری خود را به ترتیب در سالهای 1386 و 1390 از دانشگاه پیر و ماری کوری فرانسه با امتیاز بسیار افتخار آمیز در رشته مهندسی کامپیوتر دریافت نمود. دکتر موحدی پس از آن در دانشکده مهندسی کامپیوتر دانشگاه علم و صنعت ایران به عنوان هیأت علمی فعالیت مینماید. همچنین، ایشان در سال 1397 موفق به کسب درجه عالی علمی HDR از دانشگاه سوربن فرانسه گردید. زمینههای علمی مورد علاقه نامبرده شامل شبکههای کامپیوتری، شبکههای بیسیم، اینترنت اشیاء، شهر هوشمند، دوقلوی دیجیتال، تخلیهبار محاسباتی، رایانش ابری، رایانش لبه، رایانش ابری موبایل، ارتباطات دستگاه-به-دستگاه، شبکههای مبتنی بر پهپاد، شبکههای مبتنی بر نرمافزار، ارتباطات و محاسبات سبز، شبکههای اتونومیک، و امنیت شبکه میباشد.
[1] این مقاله در تاریخ 22 بهمن ماه 1402 دریافت و در تاریخ 8 مهر ماه 1403 بازنگری شد.
کیمیا قاسمی، دانشكده مهندسي كامپيوتر، دانشگاه علم و صنعت ايران، تهران، ايران، (email: ghasemi_kimia@cmps2.iust.ac.ir).
زینب موحدی (نویسنده مسئول)، دانشكده مهندسي كامپيوتر، دانشگاه علم و صنعت ايران، تهران، ، ايران، (email: zmovahedi@iust.ac.ir).
[2] . Internet of Things
[3] . Computation-Intensive
[4] . Time-Senstive
[5] . Cloud Center
[6] . Quality of Service
[7] . Mobile Edge Computing
[8] . Fifth Generation Mobile Networks
[9] . Unnamed Aerial Vehicle
[10] . Hostile Enviroments
[11] . Base Stations
[12] . Edge Server
[13] . Global Navigation Satelite Systems
[14] . Mobility-Aware and Energy-Efficient Computation Offloading and Path Planning
[15] . Utility Coverage Set
[16] . Three-Dimensional Space Intelligent Positioning
[17] . NP-Hard
[18] . Incentive-Aware Offloading Framework
[19] . Anchor Node
[20] . Line of Sight
[21] . Free-Sapce Path Loss
[22] . Non-Orthogonal Channel Access Model
[23] . Realtime
[24] . Consensus Agreements
[25] . Cycle per Bit
[26] . Distributed Computation Offloading
[27] . Nearest User First Algorithm
[28] . Random Optimization Algorithm