دانلود رایگان ترجمه مقاله الگوریتم ژنتیک برای خوشه بندی و مسیریابی در شبکه های سنسور بی سیم (نشریه الزویر 2018)

الگوریتم ژنتیک برای خوشه بندی و مسیریابی مقرون به صرفه از لحاظ انرژی در شبکه های سنسور بی سیم

Genetic Algorithm for Energy-Efficient Clustering and Routing in Wireless Sensor Networks

چکیده
1- مقدمه
2- کار مرتبط
2-1 WSNها با CHهای موقت
2-2 WSNها با CHهای دائمی
3- مدل شبکه و اصطلاحات
3-1 توپولوژی شبکه
3-2 مدل انرژی
3-3 اصطلاح شناسی
4- مقدمات
4-1 مرور اجمالی بر GA
4-2 فرمولاسیون مسئله
5- الگوریتم پیشنهاد شده
5-1 نمایندگی کروموزوم
5-2 راه اندازی (مقداردهی) جمعیت
5-4 تقاطع و جهش
6- نتایج تجربی
6-1 تنظیمات پارامتری
6-2 مقایسه وزن λ
6-3 ساختار خوشه بندی و مسیریابی
6-4 تعادل بار
6-5 چرخه عمر شبکه
6-6 مصرف انرژی
6-7 نتایج تجربی در OMNeT ++
7- نتایج

چکیده
شبکه های حسگر بی سیم به طور گسترده ای در زمینه های مختلف از جمله نظامی، مراقبت های بهداشتی و کاربردهای ساخت و تولید به کار گرفته شده اند. با این حال، گره های حسگر از نظر تامین انرژی، توانمندی ذخیره سازی و توان محاسباتی خود محدود هستند. بنابراین، به منظور بهبود بهره وری (مقرون به صرفگی) انرژی و طویل شدن چرخه عمر شبکه، یک رویکرد خوشه بندی و مسیریابی مقرون به صرفه از لحاظ انرژی مبتنی بر الگوریتم ژنتیک به نام GECR ارائه می دهیم. ما راه حل بهینه به دست آمده در دور شبکه قبلی را به جمعیت اولیه برای دور کنونی اضافه می کنیم و به این ترتیب کارایی جستجو را بهبود می بخشیم. علاوه بر این، طرح خوشه بندی و مسیریابی در یک کروموزوم تک به منظور محاسبه کل مصرف انرژی ترکیب می شود. ما تابع تناسب را مستقيماً بر اساس مصرف انرژي کلی می سازیم و بدین ترتیب بهره وري انرژي را بهبود مي بخشیم. علاوه بر این، تعادل بار در هنگام ساخت تابع تناسب در نظر گرفته می شود. بنابراین، مصرف انرژی در میان گره ها می تواند متعادل شود. نتایج تجربی نشان داد که GECR بهتر از سایر پنج روش عمل نمود. GECR بهترین تعادل بار را با کمترین واریانس ها در بارها در سرهای خوشه تحت سناریوهای مختلف حاصل نمود. علاوه بر این، GECR, بیشترین بهره وری (مقرون به صرفگی) انرژی را با کمترین انرژی متوسط مصرف شده توسط سرهای خوشه و کمترین انرژی مصرف شده توسط تمام گره ها در برداشت.
1- مقدمه
شبکه های حسگر بی سیم (WSNs), فناوری سنسور، فناوری محاسبات جاسازی شده، فناوری پردازش اطلاعات توزیع شده و فناوری ارتباطات را ادغام می کنند. WSN ها در زمینه های مختلف، از جمله نظامی، دفاع ملی، نظارت بر محیط زیست، مدیریت ترافیک، مراقبت های بهداشتی، تولید و برنامه های پیشگیری از بلایا، به طور گسترده ای مورد استفاده قرار گرفته اند [1]. در یک WSN، گره های حسگر به طور همکارانه, اطلاعات فیزیکی و زیست محیطی را از منطقه تحت پوشش شبکه جمع آوری و پردازش می کنند و اطلاعات را به ناظران ارسال می کنند [2]. یک ناحیه نظارت اغلب نیاز به استقرار تعداد زیادی از گره های حسگر دارد، اما گره های حسگر از لحاظ ظرفیت های محاسباتی، ذخیره سازی و توانایی های ارتباطی خود در کاهش هزینه ها محدود هستند. به عنوان مثال،Micaz [3] که توسط CrossBow توسعه داده شده است، یک نوع نماینده از گره حسگر است که با میکروپروسسور (ریزپردازنده) Atmegal28L، تراشه CC2420، 128 کیلوبایت فلش و 4 کیلوبایت RAM مجهز شده است. گره حسگر با قدرت باتری محدودی تامین می شود و فراهم نمودن ثانویه انرژی برای گره ها دشوار است. بنابراین، پس از مردن بیشتر از یک درصد معینی از گره ها، خرابی شبکه رخ می دهد. بنابراین، کاهش مصرف انرژی گره های حسگر و افزایش چرخه عمر شبکه، چالشی کلیدی برای WSN ها است.
مطالعات قبلی نشان داده اند که مصرف انرژی مورد نیاز برای انتقال 1 بیت, بسیار بیشتر از مصرف انرژی مورد نیاز برای پردازش داده 1 بیتی است [4]. بنابراین، کاهش اندازه داده های ارسال شده یا دریافت شده برای گره های حسگر و بهینه سازی مسیریابی انتقال داده ها بین گره ها می تواند به طور موثر انرژی مصرف شده توسط شبکه را کاهش دهد. الگوریتم خوشه بندی [5], شبکه را به چند خوشه مستقل تقسیم می کند، جایی که هر خوشه شامل یک گره سر خوشه ای (CH) و گره های عضو چند خوشه ای(CM) می باشد. گره CH, مسئول دریافت داده ها از گره های CM است. با استفاده از الگوریتم های جمع آوری داده موثر، CH می تواند داده های بیش از حد یا نادرست را حذف کند، بنابراین مقدار زیادی از داده های جمع آوری شده به مقدار کمی از اطلاعات معنی دار ادغام می شوند. بنابراین، الگوریتم های خوشه بندی کارآمد می توانند ترافیک داده را کاهش داده و توپولوژی را بهینه سازی کنند، و در نتیجه بهره وری انرژی WSN ها را بهبود بخشند.

Abstract

Wireless sensor networks have been employed widely in various fields, including military, health care, and manufacturing applications. However, the sensor nodes are limited in terms of their energy supply, storage capability, and computational power. Thus, in order to improve the energy efficiency and prolong the network life cycle, we present a genetic algorithm-based energy-efficient clustering and routing approach GECR. We add the optimal solution obtained in the previous network round to the initial population for the current round, thereby improving the search efficiency. In addition, the clustering and routing scheme are combined into a single chromosome to calculate the total energy consumption. We construct the fitness function directly based on the total energy consumption thereby improving the energy efficiency. Moreover, load balancing is considered when constructing the fitness function. Thus, the energy consumption among the nodes can be balanced. The experimental results demonstrated that the GECR performed better than other five methods. The GECR achieved the best load balancing with the lowest variances in the loads on the cluster heads under different scenarios. In addition, the GECR was the most energy-efficient with the lowest average energy consumed by the cluster heads and the lowest energy consumed by all the nodes.

1- Introduction

Wireless sensor networks (WSNs) integrate sensor technology, embedded computing technology, distributed information processing technology, and communication technology. WSNs have been employed widely in various fields, including military, national defence, environmental monitoring, traffic management, health care, manufacturing, and disaster prevention applications [1]. In a WSN, the sensor nodes collaboratively collect and process environmental and physical information from the area covered by the network and send the information to observers [2]. A monitoring area often requires the deployment of a large number of sensor nodes, but the sensor nodes are limited in terms of their computational, storage, and communication capacities in order to reduce costs. For instance, Micaz [3] developed by CrossBow is a representative type of sensor node, which is equipped with an Atmegal28L microprocessor, CC2420 chip, 128 KB Flash, and 4 KB RAM. The sensor node is supplied with limited battery power and it is difficult to provide secondary energy to the nodes. Thus, network failure occurs after more than a certain percentage of the nodes die. Therefore, reducing the energy consumption of sensor nodes and prolonging the network life-cycle is the key challenge for WSNs.

Previous studies have shown that the energy consumption required for transferring 1-bit is much more than that for processing 1-bit data [4]. Thus, reducing the transmitted or received data sizes for sensor nodes and optimizing data transmission routing between the nodes can effectively reduce the energy consumed by the network. Clustering algorithms [5] divide the network into multiple independent clusters, where each cluster comprises a cluster head (CH) node and multiple cluster member (CM) nodes. The CH node is responsible for receiving data from the CM nodes. By using effective data aggregation algorithms, the CH can remove redundant or incorrect data so the large amounts of collected data are merged into a small amount of meaningful information. Therefore, efficient clustering algorithms can reduce the data traffic and optimize the topology, thereby improving the energy efficiency of WSNs.