30240

يك روش تركيبي نوين مبتني بر الگوريتم هاي فراابتكاري و يادگيري ماشين براي ايجاد تعميم پذيري در كاربردهاي مسيريابي در شبكه هاي حسگر بي سيم

دكتري تخصصي (PhD)

مهندسي كامپيوتر- هوش مصنوعي و رباتيك

1391

1402/6/29

بهروز مينايي - وصال حكمي

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

يكي از مهمترين عوامل مصرف انرژي در شبكه‌هاي حسگر بي‌سيم، لزوم مشاركت گره‌ها در مسيريابي است و روش‌هاي مسيريابي مختلفي به منظور كاهش انرژي مصرفي گره‌هاي حسگر ارائه شده است. خوشه‌بندي يكي از كارآمدترين روش‌هاي مسيريابي براي سازماندهي سلسله مراتبي توپولوژي شبكه به منظور متعادل كردن بار كاري و افزايش طول عمر شبكه است. با اين حال، دستيابي به خوشه‌بندي بهينه در شبكه‌هاي حسگر بي‌سيم يك مسئله NP-hard است، و در نتيجه، راهكارهاي ابتكاري و فراابتكاري به طور گسترده براي يافتن راه‌حل‌هاي نزديك به بهينه در آن بكار گرفته شده‌اند. در اين روش‌ها، حسگرها به گروه‌ها يا به عبارتي به خوشه‌هايي تقسيم مي‌شوند كه هر خوشه داراي يك سرخوشه است. فرض بر اين است كه در هر دور، تك تك حسگرهاي هر خوشه يك بسته اطلاعات را به سرخوشه‌ مربوطه ارسال مي‌كنند و سرخوشه‌ نيز پس از تجميع اين اطلاعات (در صورت نياز)، آنها را به صورت مستقيم و يا به صورت چندگامه به ايستگاه مركزي ارسال مي‌كند. يك مشكل اساسي در اكثر روش‌هاي مسيريابي در شبكه¬هاي حسگر بي¬سيم، اين است كه از معيار‌هاي محدودي براي انتخاب سرخوشه‌ها استفاده مي‌كنند. به عنوان مثال در بسياري از پروتكل‌ها فقط از يك يا دو معيار‌ (مثلا انرژي يا فاصله تا ايستگاه مركزي) براي خوشه‌بندي و مسيريابي استفاده شده و به ساير ويژگي‌ها توجهي نشده است. مشكل ديگر اين است كه اگرچه راهكارهاي مسيريابي فراابتكاري از نظر كيفيت، راه‌حل بهتري نسبت به روش‌هاي مسيريابي ابتكاري توليد مي‌كنند، اما شامل حلقه‌هاي تكرارهاي وقت‌گير در ساختار خود هستند. بنابراين نمي‌توانند به سرعت به درخواست‌هاي مسيريابي پاسخ دهند و از ديدگاه زماني، باعث ايجاد تاخير در فاز ارسال داده مي‌شوند. البته، اصلي‌ترين مشكل كليه روش‌هاي مسيريابي موجود اين است كه اين پروتكل‌ها بدون در نظر گرفتن كاربردهاي مختلف در فضاهاي كاري گوناگون ارائه شده¬اند. به عبارت ديگر، از آن‌جايي‌كه تعريف طول عمر شبكه در پروتكل¬هاي ارائه شده ثابت است، با تغيير كاربرد شبكه، اين پروتكل¬ها قابليت تعميم¬پذيري براي كار در شرايط جديد را ندارند و نمي‌توانند با تغيير پيكره‌بندي شبكه شامل تغيير چيدمان شبكه (به عنوان مثال، تغيير اندازه شبكه، تعداد گره‌ها، ضرايب تجميع و ...) و يا با تغيير تعريف طول عمر شبكه براي يك كاربرد خاص سازگار شوند. لذا هرچند ممكن است كارآيي آن‌ها براي برخي كاربردها مطلوب باشد، ولي نمي‌توانند كارايي مطلوب براي طيف وسيعي از كاربردها را تضمين كنند. با توجه به موارد ذكر شده، مي¬توان نتيجه گرفت كه يك فضاي باز پژوهشي درخصوص ارائه الگوريتمي جهت مسيريابي در شبكه¬هاي حسگر بي¬سيم، با هدف بررسي پارامترهاي مهم و تاثيرگذار در راستاي انتخاب سرخوشه‌هاي مناسب با توجه به قابليت تعميم‌پذيري در كاربردهاي مختلف و زمان پاسخ‌دهي كوتاه، از طريق يك روش تركيبي مبتني بر الگوريتم‌هاي فراابتكاري و يادگيري ماشين وجود دارد. لذا در روش پيشنهادي در اين رساله، ابتدا معيارهاي گوناگون براي مسئله مسيريابي مبتني بر خوشه‌بندي در شبكه‌هاي حسگر بي‌سيم را در نظر گرفته تا يك رابطه¬ي جامع ابتكاري چندمعياره جهت محاسبه ميزان اولويت هر گره جهت سرخوشه شدن بدست آوريم. در ادامه به منظور تنظيم پارامترهاي الگوريتم ابتكاري پيشنهادي، از يك الگوريتم فراابتكاري استفاده مي‌شود و متعاقباً از الگوريتم ابتكاري تنظيم شده جهت بدست آوردن راه‌حل‌هاي نزديك به بهينه استفاده مي‌شود. سپس تعدادي شبكه¬ حسگر بي¬سيم با پيكربندي‌ها و كاربردهاي مختلف (به عنوان مثال، براي اندازه‌هاي مختلف شبكه، تعداد گره‌ها، ضرايب تجميع، تعاريف مختلف طول عمر و غيره) تعريف شده و فرآيند تنظيم الگوريتم ابتكاري مسيريابي توسط يك الگوريتم فراابتكاري براي هر شبكه تكرار مي‌شود. در ادامه، با استفاده از رابطه مسيريابي بهينه بدست آمده، يك مجموعه داده شامل مقدار هريك از ويژگي‌هاي در نظر گرفته شده براي هر گره در ورودي رابطه ابتكاري (ويژگي‌هاي گره-محور) و ميزان اولويت سرخوشه شدن (خروجي رابطه ابتكاري) در هر دور ارسال اطلاعات جمع¬آوري مي¬شود. سپس اطلاعات مربوط به كاربرد شبكه (ويژگي‌هاي كاربرد-محور) مانند ابعاد شبكه، تعداد گره¬ها، جايگاه ايستگاه مركزي و تعريف طول عمر مورد نظر نيز به داده¬هاي جمع¬آوري شده اضافه مي¬شود. درنهايت از اين مجموعه داده براي آموزش يك سامانه يادگيري ماشين استفاده مي¬كنيم تا بتواند رابطه بهينه بدست آمده براي محاسبه ميزان اولويت سرخوشه شدن گره¬ها در مسيريابي شبكه¬هاي حسگر بي¬سيم با كاربردهاي گوناگون را تقريب بزند. در نهايت مي‌توان از سامانه يادگيري ماشين آموزش‌ديده به عنوان يك الگوريتم خوشه‌بندي بر‌خط جهت تخمين ضريب اولويت سرخوشه شدن گره‌ها در شبكه‌هاي حسگر بي‌سيم جديد با كاربردهاي مختلف، استفاده كرد.

1402/10/02

A novel hybrid method based on meta_heuristic and machine learning algorithms to create generalizability in routing applications in wireless sensor networks

9/19/2024 12:00:00 AM

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

شبكه‌هاي حسگر بي‌سيم , مسيريابي , خوشه‌بندي , روش‌هاي ابتكاري , الگوريتم‌هاي فراابتكاري , سامانه يادگيري ماشين , تعميم‌پذيري در كاربرد

Wireless Sensor Networks , routing , clustering , Heuristics , meta-heuristic algorithms , Machine Learning Models , Generalizability in Application

Hojjatollah Esmaeili

Dr.Behrooz Minaei - Dr. Vesal Kakami