19785

17090

كارشناسي ارشد

نرم‌افزار

اصفهان : دانشگاه صنعتي اصفهان

1403

ده، 85ص: مصور، جدول، نمودار

1403/07/19

كتابنامه

مهندسي كامپيوتر

مهندسي برق و كامپيوتر

1403/07/23

23073220

در سالهاي اخير، اينترنت اشياء (IoT) يكي از محبوب‌ترين فناوري‌هايي بوده‌است كه تعاملات بين اشياء و انسان‌ها را براي افزايش كيفيت زندگي تسهيل مي‌كند. افزايش مداوم برنامه‌هاي اينترنت اشياء كه نياز به محاسبات در مقياس بزرگ و ذخيره‌سازي طولاني مدت دارند، منجر به اتكاي بيش از حد به محاسبات ابري شده‌است و ازدحام در فضاي ابري، همراه با فاصله مراكز داده ابري از اشياء، منجر به تأخير پاسخ انتها به انتها و غير قابل اعتمادي گشته‌است. محاسبات مبتني بر مه ساختاري توزيع شده را ارائه مي‌دهد كه در آن سرويس‌هاي محاسبات ابري ازجمله پردازش و ذخيره‌سازي داده‌ها تا لبه‌ي شبكه توسعه داده شده‌اند و تا حد امكان به دستگاه‌هاي پاياني نزديك هستند؛ بنابراين به ‌عنوان مكملي براي محاسبات ابري معرفي مي‌گردد كه با آوردن منابع پردازش و ذخيره‌سازي به لبه‌ي شبكه، خدماتي با تأخير كم ارائه مي‌دهد. از سوي ديگر، محدوديت منابع، ناهمگوني منابع، ماهيت پويا و غيرقابل پيش‌بيني بودن محيط مه، ايجاب مي‌كند كه مسئله مديريت منابع به ‌عنوان يكي از مشكلات چالش برانگيز در محاسبات مه مورد توجه قرار گيرد كه نيازمند تصميم‌گيري برخط و هوشمند مي‌باشد. در اين تحقيق، هدف، دستيابي به روشي متمركز براي اولويت‌بندي، زمان‌بندي و جايابي كارهاي پردازشي بر روي سرور‌هاي مه با قابليت‌هاي ناهمگون كه ساختار چندصفي دارند مي‌باشد. ابتدا مسئله با در نظرگرفتن معيارهاي حداقل تأخير و تعداد منقضي شدن زمان اتمام كارها فرمول‌بندي مي‌شود سپس با توجه به اينكه اندازه فضاي جستجو در اين مسئله نمايي است در اين تحقيق دو روش با پيچيدگي زماني كمتر پيشنهاد مي‌شوند؛ الگوريتم ژنتيك (GA) كه در دسته‌ي الگوريتم‌هاي تكاملي قرار دارد و الگوريتم يادگيري تقويتي (RL) كه يكي از رويكردهاي يادگيري ماشين است. همچنين جهت مقايسه نتايج از الگوريتم تصادفي و دو الگوريتم ابتدا كوتاه‌ترين كار (SJF) و ابتدا زودترين ضرب‌العجل (EDF) استفاده شده‌است. نتايج نشان مي‌دهد الگوريتم ژنتيك عملكرد بهتري را در هر دو معيار ميانگين تأخير و ميزان از دست رفتن مهلت‌هاي زماني از خود نشان مي‌دهد. اين روش در معيار ميانگين تأخير، نسبت به روش SJF و EDF، به ترتيب به ميزان %10 و %13 و نسبت به روش RA، %82 بهتر عمل مي‌كند. همچنين در اين معيار نسبت به روش RL، %23 عملكرد بهتري داشته‌است. از نظر معيار ميانگين تعداد وظايفي كه در مهلت مقرر خود به اتمام نرسيده‌اند، الگوريتم ژنتيك نسبت به روش SJF، EDF و RA ، به ترتيب به ميزان %10، %9 و %56 بهبود ايجاد مي‌نمايد و نسبت به الگوريتم RL، %15 درصد بهتر عمل مي‌كند. همچنين نتايج شبيه‌سازي نشان مي‌دهد ساختار چند صفي سرورهاي مه، در شرايطي كه تعداد سرورهاي مه كم است در بهبود عملكرد سيستم نقش دارد اما با افزايش سرورهاي مه عملكرد ساختار تك صفي بهتر از ساختار چند صفي خواهد بود. كلمات كليدي: اينترنت اشياء، محاسبات مبتني بر مه، تخصيص منابع، يادگيري تقويتي، الگوريتم ژنتيك

Abstract In recent years, the Internet of Things (IoT) has been one of the most popular technologies facilitating interactions between objects and humans to enhance the quality of life. The continuous increase in IoT applications, which require large-scale computing and long-term storage, has led to an over-reliance on cloud computing. The resulting congestion in the cloud, along with the distance of cloud data centers from objects, has caused end-to-end response delays and unreliability. Fog computing offers a distributed structure where cloud computing services, including data processing and storage, are extended to the network edge, as close as possible to end devices. Therefore, it is introduced as a complement to cloud computing, providing low-latency services by bringing processing and storage resources to the network edge. On the other hand, resource limitations, resource heterogeneity, and the dynamic and unpredictable nature of the fog environment necessitate that resource management be considered as one of the challenging problems in fog computing, requiring online and intelligent decision-making. In this research, the goal is to achieve a centralized method for prioritizing, scheduling, and placing processing tasks on heterogeneous fog servers that have a multi-queue structure. First, the problem is formulated considering the criteria of minimizing delay and the number of missed task deadlines. Then, given that the search space size for this problem is exponential, two methods with lower time complexity are proposed: a Genetic Algorithm (GA), which falls under the category of evolutionary algorithms, and a Reinforcement Learning (RL) algorithm, which is one of the machine learning approaches. Additionally, for comparison, a random algorithm and two algorithms, Shortest Job First (SJF) and Earliest Deadline First (EDF), are used. The results show that the Genetic Algorithm performs better in both the average delay and the deadline miss rate criteria. Specifically, in the average delay criterion, it performs %10 and %13 better than the SJF and EDF methods, respectively, and %82 better than the RA method. Moreover, in this criterion, it performs %23 better than the RL method. In terms of the average number of tasks that miss their deadlines, the Genetic Algorithm shows improvements of %38, %36, and %77 over the SJF, EDF, and RA methods, respectively, and %48 better performance compared to the RL algorithm. The simulation results also indicate that the multi-queue structure of fog servers plays a role in improving system performance when the number of fog servers is low. However, as the number of fog servers increases, the performance of the single-queue structure surpasses that of the multi-queue structure. KeyWords: Internet of Things, Fog computing, Resource allocation, Reinforcement learning, Genetic algorithm

محمدرضا حيدرپور

مسعودرضا هاشمي , علي فانيان