| آقای حجت‌اله اسماعیلی دانشجوی دکترای آقایان دکتر بهروز مینایی و دکتر وصال حکمی مورخ ۱۴۰۲/۰۶/۲۹ ساعت ۱۶:۰۰ از رساله دکتری خود با عنوان "یک روش ترکیبی نوین مبتنی بر الگوریتم‌های فراابتکاری و یادگیری ماشین برای ایجاد تعمیمپذیری در کاربردهای مسیریابی در شبکههای حسگر بیسیم" دفاع خواهند نمود. |
ارائه دهنده:
حجت‌اله اسماعیلی
اساتید راهنما:
دکتر
بهروز مینایی و دکتر وصال حکمی
هیات داوران:
دکتر اکبری، دکتر دیانت، دکتر صنیعی آباده، دکتر منظوری
زمان : ۲۹ شهریور ماه ۱۴۰۲
ساعت ۱۶:۰۰
چکیده پایان نامه :
یکی از مهمترین عوامل مصرف انرژی در شبکههای حسگر بیسیم، لزوم مشارکت گرهها در مسیریابی است و روش‌های مسیریابی مختلفی به منظور کاهش انرژی مصرفی گره‌های حسگر ارائه شده است. خوشه‌بندی یکی از کارآمدترین روش‌های مسیریابی برای سازماندهی سلسله مراتبی توپولوژی شبکه به منظور متعادل کردن بار کاری و افزایش طول عمر شبکه است. با این حال، دستیابی به خوشه‌بندی بهینه در شبکههای حسگر بیسیم یک مسئله NP-hard است، و در نتیجه، راهکارهای ابتکاری و فراابتکاری به طور گسترده برای یافتن راه‌حل‌های نزدیک به بهینه در آن بکار گرفته شدهاند. در این روش‌ها، حسگرها به گروه‌ها یا به عبارتی به خوشه‌هایی تقسیم می‌شوند که هر خوشه دارای یک سرخوشه است. فرض بر این است که در هر دور، تک تک حسگرهای هر خوشه یک بسته اطلاعات را به سرخوشه مربوطه ارسال می‌کنند و سرخوشه نیز پس از تجمیع این اطلاعات (در صورت نیاز)، آنها را به صورت مستقیم و یا به صورت چندگامه به ایستگاه مرکزی ارسال می‌کند. یک مشکل اساسی در اکثر روش‌های مسیریابی در شبکههای حسگر بیسیم، این است که از معیارهای محدودی برای انتخاب سرخوشه‌ها استفاده می‌کنند. به عنوان مثال در بسیاری از پروتکلها فقط از یک یا دو معیار (مثلا انرژی یا فاصله تا ایستگاه مرکزی) برای خوشه‌بندی و مسیریابی استفاده شده و به سایر ویژگی‌ها توجهی نشده است. مشکل دیگر این است که اگرچه راهکارهای مسیریابی فراابتکاری از نظر کیفیت، راه‌حل بهتری نسبت به روش‌های مسیریابی ابتکاری تولید می‌کنند، اما شامل حلقه‌های تکرارهای وقت‌گیر در ساختار خود هستند. بنابراین نمی‌توانند به سرعت به درخواست‌های مسیریابی پاسخ دهند و از دیدگاه زمانی، باعث ایجاد تاخیر در فاز ارسال داده می‌شوند. البته، اصلی‌ترین مشکل کلیه روش‌های مسیریابی موجود این است که این پروتکلها بدون در نظر گرفتن کاربردهای مختلف در فضاهای کاری گوناگون ارائه شدهاند. به عبارت دیگر، از آن‌جایی‌که تعریف طول عمر شبکه در پروتکلهای ارائه شده ثابت است، با تغییر کاربرد شبکه، این پروتکلها قابلیت تعمیمپذیری برای کار در شرایط جدید را ندارند و نمی‌توانند با تغییر پیکره‌بندی شبکه شامل تغییر چیدمان شبکه (به عنوان مثال، تغییر اندازه شبکه، تعداد گرهها، ضرایب تجمیع و ...) و یا با تغییر تعریف طول عمر شبکه برای یک کاربرد خاص سازگار شوند. لذا هرچند ممکن است کارآیی آنها برای برخی کاربردها مطلوب باشد، ولی نمی‌توانند کارایی مطلوب برای طیف وسیعی از کاربردها را تضمین کنند. با توجه به موارد ذکر شده، میتوان نتیجه گرفت که یک فضای باز پژوهشی درخصوص ارائه الگوریتمی جهت مسیریابی در شبکههای حسگر بیسیم، با هدف بررسی پارامترهای مهم و تاثیرگذار در راستای انتخاب سرخوشه‌های مناسب با توجه به قابلیت تعمیمپذیری در کاربردهای مختلف و زمان پاسخ‌دهی کوتاه، از طریق یک روش ترکیبی مبتنی بر الگوریتم‌های فراابتکاری و یادگیری ماشین وجود دارد. لذا در روش پیشنهادی در این رساله، ابتدا معیارهای گوناگون برای مسئله مسیریابی مبتنی بر خوشه‌بندی در شبکههای حسگر بیسیم را در نظر گرفته تا یک رابطهی جامع ابتکاری چندمعیاره جهت محاسبه میزان اولویت هر گره جهت سرخوشه شدن بدست آوریم. در ادامه به منظور تنظیم پارامترهای الگوریتم ابتکاری پیشنهادی، از یک الگوریتم فراابتکاری استفاده میشود و متعاقباً از الگوریتم ابتکاری تنظیم شده جهت بدست آوردن راه‌حل‌های نزدیک به بهینه استفاده میشود. سپس تعدادی شبکه حسگر بیسیم با پیکربندی‌ها و کاربردهای مختلف (به عنوان مثال، برای اندازه‌های مختلف شبکه، تعداد گرهها، ضرایب تجمیع، تعاریف مختلف طول عمر و غیره) تعریف شده و فرآیند تنظیم الگوریتم ابتکاری مسیریابی توسط یک الگوریتم فراابتکاری برای هر شبکه تکرار میشود. در ادامه، با استفاده از رابطه مسیریابی بهینه بدست آمده، یک مجموعه داده شامل مقدار هریک از ویژگی‌های در نظر گرفته شده برای هر گره در ورودی رابطه ابتکاری (ویژگی‌های گره-محور) و میزان اولویت سرخوشه شدن (خروجی رابطه ابتکاری) در هر دور ارسال اطلاعات جمعآوری میشود. سپس اطلاعات مربوط به کاربرد شبکه (ویژگی‌های کاربرد-محور) مانند ابعاد شبکه، تعداد گرهها، جایگاه ایستگاه مرکزی و تعریف طول عمر مورد نظر نیز به دادههای جمعآوری شده اضافه میشود. درنهایت از این مجموعه داده برای آموزش یک سامانه یادگیری ماشین استفاده میکنیم تا بتواند رابطه بهینه بدست آمده برای محاسبه میزان اولویت سرخوشه شدن گرهها در مسیریابی شبکههای حسگر بیسیم با کاربردهای گوناگون را تقریب بزند. در نهایت میتوان از سامانه یادگیری ماشین آموزش‌دیده به عنوان یک الگوریتم خوشه‌بندی بر‌خط جهت تخمین ضریب اولویت سرخوشه شدن گرهها در شبکههای حسگر بیسیم جدید با کاربردهای مختلف، استفاده کرد.
Abstract:
One of the most important factors of energy consumption in wireless sensor networks is the routing problem. Various routing methods have been proposed to reduce the energy consumption of sensor nodes. Clustering is one of the most efficient routing approaches for hierarchical organization of network topology in order to balance workload and increase network lifetime. However, achieving optimal clustering in wireless sensor networks is an NP-hard problem, and as a result, heuristics and meta-heuristics have been widely applied to find near-optimal solutions. In these methods, sensors are divided into groups or, in other words, into clusters, where each cluster has a cluster head. It is assumed that in each round, each sensor of each cluster sends a packet of information to the corresponding cluster head, and the cluster head, after aggregating this information (if needed), sends them to the central station directly or in multiple hops. A major challenge in most routing methods in wireless sensor networks is that they use limited criteria to select cluster heads. For example, in many protocols, only one or two criteria (e.g., energy or distance to the base station) are used for clustering and routing, and other features are not considered. Another problem is that although meta-heuristic routing algorithms produce a better solution than heuristic routing methods in terms of quality, they include time-consuming iteration loops in their structure. Therefore, they cannot respond to routing requests quickly, and from a time point of view, they cause delays in the data transmission phase. However, the main problem of all existing routing methods is that these protocols are presented without considering different applications in various working fields. In other words, since the definition of the network lifetime in the provided protocols is fixed, with the change of the network application, these protocols do not have the ability to adapt to new conditions if there is a change in the network configuration (for example, a change in the size of the network, the number of nodes, aggregation coefficients, etc.) or in the definition of the network lifetime for a specific application. Therefore, even though their efficiency may be favorable for some applications, they cannot guarantee optimal efficiency for a wide range of applications. According to the mentioned issues, it can be concluded that there is an open research gap regarding the suggestion of wireless sensor network routing protocols, with the aim of analyzing important and influential parameters in order to select suitable cluster heads with regard to generalizability in different applications and short response time, through a hybrid method based on meta-heuristic and machine learning algorithms. Therefore, in this thesis, we propose a method that considers various criteria for the problem of routing based on clustering in wireless sensor networks in order to obtain a comprehensive multi-criteria heuristic relationship to calculate the priority factor of each node to become a cluster head. Next, in order to adjust the parameters of the proposed heuristic algorithm, a meta-heuristic algorithm is used, and subsequently, the adjusted heuristic algorithm is used to obtain near-optimal solutions. Then, a number of wireless sensor networks with different configurations and applications (for example, for different network sizes, number of nodes, aggregation factors, different definitions of lifetime, etc.) are defined and the process of adjusting the heuristic routing algorithm by a meta-heuristic algorithm for each of these networks will be repeated. Subsequently, by using the obtained optimal routing relation, a data set will be collected which includes the value of each of the features considered for each node in the input of the heuristic relationship (node-based features) and the priority of becoming a cluster head (the output of the heuristic relationship) in each round of sending information. Then, the information related to the application of the network (application-based features) such as the dimensions of the network, the number of nodes, the location of the base station, and the definition of the expected lifetime are also added to the collected data. Finally, we use this data set to train a machine learning model so that it can approximate the optimal relationship obtained to calculate the priority of nodes in the routing of wireless sensor networks for various applications. Finally, the trained machine learning model can be used as an online clustering algorithm to estimate the priority factor of nodes for becoming a cluster head in new wireless sensor networks with various applications.
Keywords: Wireless Sensor Networks, Routing, Clustering, Heuristics, Meta-Heuristic Algorithms, Machine Learning Models, Generalizability in Application
|