دانلود رایگان مقاله پروتکل خوشه بندی نابرابر توزیع شده رای شبکه های حسگر بی سیم

چکیده

          در این مقاله، یک نسخه بهبود یافته از پروتکل خوشه‌بندی نابرابر توزیع‌شده‌ی انرژی آگاه (EADUC) ارائه شده است. پروتکل EADUC معمولا برای حل مشکل فقدان انرژی در شبکه‌های حسگر بی‌سیم چند هاپی استفاده می‌شود. در EADUC، به محل ایستگاه پایه و انرژی باقی‌مانده به‌عنوان پارامترهای خوشه‌بندی اهمیت داده می‌شود. براساس این پارامترها، شعاع رقابت مختلفی به گره اختصاص داده می‌شود. در اینجا، یک رویکرد جدید به‌منظور بهبود کار EADUC، با انتخاب سخوشه با توجه به تعداد گره همسایگی علاوه بر دو پارامتر بالا مطرح شده است. گنجایش اطلاعات همسایگی برای محاسبه شعاع رقابت، تعادل انرژی بهتری در مقایسه با روش‌های موجود فراهم می‌کند. علاوه بر این، برای انتخاب گره هاپ بعدی، متریک به‌طورمستقیم از نظر هزینه انرژی به‌جای اطلاعات از راه دور مورد استفاده در EADUC و فاز انتقال داده در هر دور با گسترش تعداد جمع‌آوری داده‌ها از طریق استفاده از اسلات‌های بزرگ و کوچک تعریف می‌شود. روش مورد استفاده، جهت حفظ خوشه یکسان برای چند دور و درنتیجه کاهش سربار خوشه موثر است. عملکرد پروتکل ارائه شده تحت سه سناریو مختلف مورد ارزیابی قرار گرفته و از طریق شبیه‌سازی با پروتکل‌های موجود مقایسه شده است. نتایج نشان می‌دهد که این طرح پیشنهادی از نظر طول عمر شبکه در تمام حالات بهتر از پروتکل‌های موجود است. 

1. معرفی 

           شبکه‌های حسگر بی‌سیم (WSN ها) براساس بسیاری از محدودیت‌های مشخص منابع مانند انرژی، قدرت پردازش، ذخیره‌سازی و محدوده انتقال مشخص می‌شوند. علاوه بر این عوامل، انرژی حسگرها، از محدودیت‌های اساسی منابع در شبکه‌های حسگر بی‌سیم است. بسیاری از کارهای تحقیقاتی در دهه گذشته برای رسیدگی به این چالش انجام شده است [1-3]. WSN ها برای جمع‌آوری داده‌های کاربردی که شامل مقدار زیادی از منطقه از جمله مناطق زراعی، جنگل‌ها، معادن زغال سنگ، نظارت تونل راه‌آهن، نظارت سلول‌های خورشیدی فتوولتائیک در یک شبکه و غیره هستند کاربرد دارد و WSN ها نیاز به داده‌هایی از تمام مکان‌ها دارند [2،4-6]. ایستگاه پایه (BS) در بسیاری از موارد دور از حسگرها قرار دارد. در چنین شبکه‌هایی، داده‌ها به‌صورت دوره‌ای توسط BS جمع می‌شوند. خوشه‌بندی با توپولوژی سلسله مراتبی برای تحقق نظارت مستمر شبکه‌ها پرکاربرد است [7-11]. که نشان داده است خوشه‌بندی شبکه، طول عمر بیشتری از شبکه با انتقال مستقیم داده‌ها را امکان‌پذیر می‌کند. نشان داده شده است که طول عمر شبکه توسط یک عامل حدودا 2 یا 3 بار با خوشه‌بندی بهبود می‌یابد [12].

           مزایای بسیاری برای استفاده از پروتکل‌های خوشه‌بندی در شبکه‌های جمع‌آوری داده‌ها وجود دارد. در شبکه‌ی متراکم، به طور معمول حجم زیادی از ترافیک بین سنسورها وجود دارد، که منجر به دخالت و پس از آن برخورد می‌شود. انتظار می‌رود که گروه‌بندی سنسورها تعداد مسافت‌های طولانی را به‌حداقل برساند و در نتیجه در مصرف انرژی صرفه‌جویی شود. در خوشه‌بندی، زمان بیکاری گره‌های سنسور طبیعی (اعضای خوشه) استخراج می‌شود، در حالی‌که سرخوشه‌ها موجب هماهنگی فعالیت‌های گره‌های عضو و در نتیجه صرفه‌جویی انرژی [13] می‌شوند. برنامه‌ریزی فعالیت تا حد زیادی از طریق TDMA براساس برنامه‌ریزی اجرا می‌شود [5،11،14،15]. همچنین خوشه‌بندی، جمع‌آوری داده‌ها در سرخوشه (CH) را با کاهش تعداد بسته داده‌های منتقل شده تسهیل می‌کند، که به کاهش مصرف انرژی در گره‌های حسگر کمک می‌کند [13]. 

          ارتباطات در پروتکل‌های خوشه‌بندی در دو مرحله انجام می‌گیرد، ابتدا درون خوشه، به‌عنوان مثال در داخل خوشه، و دوم بین خوشه، به‌عنوان مثال بین خوشه‌ها و BS. علاوه بر این، ارتباطات در پروتکل خوشه‌بندی شبکه‌های حسگر بی‌سیم را می‌توان یا با به کارگیری انتقال هاپ و یا مسیریابی چند هاپ انجام داد [16،17]. بسیاری از پروتکل‌های خوشه‌بندی از ارتباطات تک هاپ برای برقراری ارتباط در داخل خوشه استفاده می‌کنند، همانگونه که فاصله بین سنسورها در داخل خوشه نسبتا کوتاه است، به‌عنوان مثال، LEACH  ]11[، LEACH-DT  ]15[، HEED [18]، و غیره. تحقیقات مطرح شده در کارهای گذشته بیان می‌کند که ارتباطات چند هاپ بین گره‌های حسگر و سرخوشه بیش از ارتباطات تک هاپ برای مصرف موثر انرژی کارآمد است. این زمانی اتفاق می‌افتد که گره‌های حسگر در مناطق با پوشش گیاهی متراکم و یا ساختمان یا کارخانه مستقر شده باشد [1،16]. در چنین مواردی، ارتباطات چند هاپ در غلبه بر دشواری انتشار سیگنال موفق است [1،7]. با این حال، انتقال مستقیم نه تنها به دلیل پراکندگی انرژی رادیو بلکه به دلیل پذیرش نیز مفید است. ولی یک محدودیت در انتقال مستقیم وجود دارد. این مورد فقط برای استفاده از آن تا فاصله آستانه‌ی خاصی خوب است [19]. به این خاطر در صورت انتقال از راه دور فراتر از فاصله آستانه، هزینه انرژی با توجه به توان چهارم فاصله افزایش می‌یابد[15،20]. همانگونه که گره‌های حسگر انرژی محدود هستند، آنها معمولا محدوده‌ی انتقال محدود دارند. بنابراین، به منظور افزایش مقیاس‌پذیری شبکه، ارتباطات چند هاپ ترجیح داده می‌شود [21]. در صورت ارتباط از گره سرخوشه به BS، اگر BS دور از میدان سنسورباشد بهتر است از ارتباطات چند هاپ استفاده شود [19]. تعدادی پروتکل خوشه‌بندی توسعه یافته وجود دارد که از ارتباطات چند هاپ برای ارتباطات درون خوشه با انرژی کارآمد استفاده می‌کند. چند هاپ LEACH ]22[، EADC  ]23[، EDUC [24]، و غیره برخی از این پروتکل‌ها هستند. 

          یکی از نگرانی‌های اصلی در شبکه‌های حسگر بی‌سیم افزایش طول عمر شبکه است چرا که پس از ناکارآمدی شبکه، مقدار قابل توجهی از انرژی نباید در گره‌ها باقی بماند، در غیر این‌صورت اتلاف انرژی است. بسیاری از کارهای تحقیقاتی، طول عمر شبکه را به زمانی که اولین گره می‌میرد (FND) تعریف کرده‌اند. ایده پشت این فرض این است که تمام گره‌های شبکه تقریبا در زمان یکسانی به‌منظور جلوگیری از دست رفتن زودرس پوشش سنجش و پارتیشن‌بندی شبکه می‌میرند [8،11،15،18]. اما، همان‌گونه که طول عمر به برنامه‌ها بستگی دارد، اولین گره مرده به عنوان طول عمر تعریف می‌شود [25]. انواع مختلفور برنامه‌های کاربردی برای حسگر وجود دارد [26] و در نتیجه، جهت فراهم نمودن نیازمندی‌های مختلف نرم‌افزار، طول عمر شبکه طی مراحل مختلف مورد بررسی قرار می‌گیرد، به‌عنوان مثال زمانی که اولین گره می‌میرد، و یا درصد معینی از گره‌ها شکست می‌خورند[27]. در هر صورت، شبکه باید مستقل عمل کند و اعمال خود را در طول عمرش تضمین کند [28].

         در یک پروتکل خوشه‌بندی، CH برای انجام کارهای مختلف مانند تشکیل خوشه‌بندی، جمع‌آوری داده‌ها و انتقال داده‌ها به‌شدت سنگین است. بنابراین سر خوشه مصرف انرژی بیشتری نسبت به گره غیر CH دارد. در انتقال درون خوشه برای هر دو نوع ارتباطات، تک هاپ و چند هاپ، مشکل اجتناب‌ناپذیر عدم تعادل انرژی در میان گره‌های سنسور وجود دارد [24]. برای ارتباط هاپ تک، سر خوشه‌هایی که دور از BS هستند به دلیل انتقال از راه دور تخلیه انرژیمی‌شوند. اما هنگام استفاده از ارتباطات چند هاپ در پروتکل‌های خوشه‌بندی، سرخوشه‌های نزدیک پایگاه به‌دلیل بار اضافی ترافیک به‌سرعت تخلیه انرژی می‌کنند. بار نامتعادل ارتباطات در فقدان انرژی و یا منطقه داغ نتیجه می‌شود. با توجه به این، از دست دادن پوشش سنسورها و پارتیشن‌بندی شبکه رخ می‌دهد و در نهایت بر کارایی شبکه تاثیر می‌گذارد. تحقیقات قبلی [29] نشان داده است که اگر سنسورها به‌طور یکنواخت در منطقه مورد علاقه توزیع شوند، زمانی که طول عمر شبکه به پایان می‌رسد 90 درصد از کل انرژی سنسور بدون استفاده می‌ماند، یعنی زمانی که اولین گره مرده است. این مورد در مرجع 30 ثابت شده است که به دلیل پارادایم ارتباطات چند به یک در شبکه‌های حسگر بی‌سیم، تخلیه انرژی نامتعادل در میان تمام سنسورها غیر قابل اجتناب است. برای به‌حداکثر رساندن طول عمر شبکه، مصرف انرژی در میان تمام گره‌های شبکه باید تعدیل شود. به‌تازگی، تحقیقات زیادی برای نشان دادن عدم تعادل انرژی و مسئله کاهش انرژی برای شبکه گیرنده بی‌سیم انجام شده است. تعدادی از استراتژی‌ها مانند استفاده از تحرک گره [31،32]، همزمانی تلفن‌همراه [33-36]،  به‌کار گیری سلسله مراتبی[37]، خوشه‌بندی غیریکنواخت [8،24،38]، فشرده‌سازی داده و تجمع ترافیک [36،39]، توزیع گره [2،29،30،40] و غیره برای حل مشکل فقدان انرژی ارائه شده است. 

         در این مقاله، تلاشی برای بهبود عمر شبکه در پروتکل EADUC مورد استفاده در نظارت مستمر برنامه‌های کاربردی صورت گرفته است [38]. EADUC الگوریتم خوشه‌بندی غیریکنواخت را برای کاهش مشکل فقدان انرژی به‌کار برده است. ایده اصلی در طرح پیشنهادی ما این است که در طول انتخاب سرخوشه، انتساب شعاع رقابتی گره نه تنها براساس عامل فاصله و انرژی باقی‌مانده گره که درEADUC استفاده شده است، بلکه بنا به یک عامل سوم، تعداد گره همسایه، نیز صورت می‌گیرد. اطلاعات همسایگی به‌عنوان پارامتر خوشه‌بندی برای گسترش طول عمر شبکه در نظر گرفته می‌شود. یکی دیگر از ایده‌های کلیدی مورد استفاده در این مقاله، بهبود پروتکل EADUC در طول روند انتخاب از ترافیک است. هزینه‌های درگیر در تقویت، از نظر انرژی، به‌عنوان معیارهایی برای انتخاب یکی از گره‌های ممکن به‌عنوان گره تقویتی به‌جای اطلاعات مسافت مورد استفاده در EADUC مشخص می‌شوند. طرح پیشنهادی به مصرف انرژی گره‌ها در شبکه برای توزیع یکنواخت همانند توزیع غیریکنواخت اشاره دارد. به‌منظور افزایش طول عمر شبکه، ایده‌ی گسترش مرحله انتقال داده‌ها با تقسیم به اسلات‌های عمده و اسلات‌های کوچک به‌طور موثر با خوشه‌بندی پیشنهادی و روش تقویتی استفاده شده در مرجع 41 ترکیب می‌شود. جمع‌آوری داده‌ها در هر حافظه کوچک با استفاده از خوشه‌های یکسان تشکیل می‌شود. بعد از هر حافظه بزرگ، چرخش سرخوشه در محدوده‌ی خوشه فعلی و تحویل اعضای خوشه صورت می‌گیرد. رویکرد پیشنهادی سربار خوشه را کاهش می‌دهد و در نتیجه موجب افزایش طول عمر شبکه می‌شود. کارآیی پروتکل ارائه شده با پروتکل‌های موجود بااستفاده از طول عمر شبکه به‌عنوان متریک کارآیی مقایسه می‌شود. 

          ادامه این مقاله به شرح زیر است: بخش 2 بررسی کارهای مرتبط و بخش 3 ارائه مدل سیستم است. بخش 4 توصیف عملیات پروتکل ارائه شده با جزئیات و بخش 5 تجزیه‌وتحلیل ویژگی‌های پروتکل را بیان می‌کند. بخش 6 نتایج شبیه سازی طرح‌های سنسور ما را انجام می‌دهد و آن را با پروتکل‌های موجود مقایسه می‌کند. بخش 7 شامل نتیجه‌گیری مقاله است.

ABSTRACT

         In this paper, an improved version of the energy aware distributed unequal clustering protocol (EADUC) is projected. The EADUC protocol is commonly used for solving energy hole problem in multi-hop wireless sensor networks. In the EADUC, location of base station and residual energy are given importance as clustering parameters. Based on these parameters, different competition radii are assigned to nodes. Herein, a new approach has been proposed to improve the working of EADUC, by electing cluster heads considering number of nodes in the neighborhood in addition to the above two parameters. The inclusion of the neighborhood information for computation of the competition radii provides better balancing of energy in comparison with the existing approach. Furthermore, for the selection of next hop node, the relay metric is defined directly in terms of energy expense instead of only the distance information used in the EADUC and the data transmission phase has been extended in every round by performing the data collection number of times through use of major slots and mini-slots. The methodology used is of retaining the same clusters for a few rounds and is effective in reducing the clustering overhead. The performance of the proposed protocol has been evaluated under three different scenarios and compared with existing protocols through simulations. The results show that the proposed scheme outperforms the existing protocols in terms of network lifetime in all the scenarios.

1. Introduction

          Wireless sensor networks (WSNs) are characterized by many resource constraints such as energy, processing power, storage and transmission range. Out of these factors, energy of deployed sensors has been the major resource constraint of the wireless sensor networks. Lot of research work has been carried out in the last decade to address this challenge [1–3]. WSNs are deployed densely for data gathering applications involving a large amount of area such as agriculture, forests, coal mines, monitoring of rail tunnels, monitoring of solar photovoltaic cell in a grid, etc., and WSNs require data from all locations [2,4–6]. The base station (BS) is placed far away from the sensing field in most of the cases. In such networks, data are gathered periodically by the BS. Clustering with hierarchical topology is found to be successful for realizing continuous monitoring networks [7–11]. It is exhibited that clustering the network offers greater lifespan than the network with direct data transmission. It is shown that the network lifespan gets improved by a factor of about 2 or 3 times with clustering [12].

         There are many advantages of using clustering protocols in datagathering networks. In dense network, normally there is large volume of traffic among the sensors, which leads to creation of interference and subsequently results into collisions. It is expected that grouping the sensors would minimize the number of long distance transmissions and thereby result into saving of the energy. In clustering, the normal sensor nodes (cluster members) sleep times are drawn out, while cluster heads coordinate the activities of its member nodes, again resulting into energy saving [13]. This activity scheduling is executed largely through TDMA based schedule [5,11,14,15]. Also clustering facilitates data aggregation at cluster head (CH) by decreasing the number of transmitted data packets, which helps in reduction of energy consumption of sensor nodes [13].

         The communication in clustering protocols is executed in two steps, first is intra-cluster, i.e. within the clusters, and the second is inter-cluster, i.e. between the clusters and the BS. Furthermore, the communication in a wireless sensor network clustering protocol can be taken up either by employing single hop transmission, or multi-hop routing [16,17]. Most of the clustering protocols use single hop communication for communicating inside the cluster, as the distance between sensors within the cluster is relatively short, e.g. LEACH [11], LEACH-DT [15], HEED [18], etc. Researches proposed in literature report that multi-hop communication between the sensor nodes and the cluster head is more energy-efficient than single hop communication, when the propagation loss exponent is high. This is when sensor nodes are deployed in dense vegetation regions, or buildings, or factories [1,16]. In such cases, multi-hop communication is successful in overcoming signal propagation difficulties [1,7]. However, because the radio dissipates energy in not only transmission but also in reception, direct transmission is also useful. But there is a limitation in case of direct transmission also. It is good to use it up to a certain threshold distance only [19]. This is because in case of transmission distance beyond threshold distance, the energy expense increases according to the fourth power of the distance [15,20]. As the sensor nodes are energy constrained, they usually have a limited transmission range. Thus, in order to increase the network scalability also, multi-hop communication is preferable [21]. In case of communication from cluster head node to the BS, if BS being far away from sensor field, then, it is better to use multi-hop communication [19]. There are number of clustering protocols developed that use multi-hop communication for achieving more energy-efficient inter-cluster communication. Multi-hop LEACH [22], EADC [23], EDUC [24], etc. are some such protocols.

           One of the primary concerns in wireless sensor networks is maximization of network lifetime because after the network becomes dysfunctional, significant amount of energy should not remain in the nodes, otherwise it is wastage. Many research works has defined the network lifetime to be when the first node is dead (FND). The idea behind this assumption is that it is important that all the nodes of the network die out approximately at the same time in order to avoid early loss of sensing coverage, and likely partitioning of the network [8,11,15,18]. But, as the lifetime requirement is applicationspecific, considering the first node dead as the lifetime definition is not a generic one [25]. There are different types of sensor network’s applications [26] and therefore, to cater to different application requirements, lifetime of the network has also been evaluated at different stages, i.e. the time when first node dies, or certain percentage of nodes fail [27]. In any case, it is more important that network functions autonomously and guarantees its operation until its lifetime [28].

           In a clustering protocol, a CH is heavily burdened as it has to perform various tasks such as cluster formation, data aggregation, data transmission and relaying. Cluster heads therefore consume more energy as compared to non-CH nodes. In inter-cluster transmission for both the modes of communication, single hop and multihop, there is inevitable problem of energy imbalance among sensor nodes [24]. For single hop communication, cluster heads which are far away from BS drain out their energy primarily because of the long distance transmission. But when using multi-hop communication in clustering protocols, then, the cluster heads near the base station deplete their energy quickly because of the extra burden of traffic relaying. This unbalanced communication load results in energy hole or hot spot area. Due to this, loss of sensing coverage and partitioning of the network occur and ultimately affect the network performance. Previous research [29] has demonstrated that if sensors are distributed uniformly in the area of interest, 90 percent of the total energy of the sensors is left unused when network lifetime ends, i.e. the time when first node is dead. It is proved in reference 30 that unbalanced energy depletion among all the sensors is unavoidable because of many-to-one communication paradigm inWSNs. For maximizing the network lifetime, energy consumption among all the network nodes must be balanced. Recently, much research has been carried out to address energy imbalance and mitigate energy hole problem for clustered WSNs. A number of strategies such as using node mobility [31,32], mobile sink [33–36], hierarchical deployment [37], non-uniform clustering [8,24,38], data compression and traffic aggregation [36,39], node distribution [2,29,30,40], etc. have been proposed for solving energy hole problem.

           In this paper, an attempt has been made to improve network lifespan of an EADUC protocol used in continuous monitoring applications [38]. The EADUC employs non-uniform clustering algorithm to mitigate the energy hole problem. The core idea in our proposed scheme is that during the cluster head selection subphase, nodes competition radius assignment would be based on not only the distance factor and node’s residual energy as is used in EADUC, but also a tertiary factor, number of neighbor nodes. This neighborhood information is considered as the clustering parameter to extend network lifespan. Another key idea used in our improved EADUC protocol is during selection procedure of traffic relaying. The cost involved in relaying, in terms of energy, is incorporated as the metrics for selecting one of the feasible nodes as a relay node instead of only the distance information used in EADUC. The proposed scheme poises the energy consumption of the nodes in the network for uniform distribution as well as for non-uniform distribution. Further to enhance the network lifetime, the idea of extending the data transmission phase by dividing into major slots and mini-slots is effectively combined with the proposed clustering and relaying technique as used in reference 41. The data collection occurs in each mini-slot using the same clusters once formed and the number of mini-slots comprises a major slot. After each major slot, cluster head rotation within the current cluster boundary and handover of the cluster members takes place. The proposed approach reduces the clustering overhead and thereby prolongs the network lifetime. The performance of our proposed protocol is compared with the existing protocols using network lifetime as the performance metric.

             The remainder of this paper is organized as follows: Section 2 reviews the related work and Section 3 presents the system model. Section 4 describes the proposed protocol operation in detail and Section 5 analyzes the protocol characteristics. Section 6 gives the simulation results of our sensor deployment schemes and compares it with existing protocols. Section 7 concludes the paper.

چکیده

1. معرفی 

 2. کارهای مرتبط 

 3. مقدمات 

3.1. مدل انرژی 

3.2. مدل تجمع داده 

 4. بهبود مکانیزم پروتکل EADUC 

5. تجزیه‌وتحلیل پروتکل 

6. ارزیابی عملکرد 

6.1. محیط شبیه‌ سازی 

6.2. پارامترهای شبیه‌ سازی 

7. نتایج و بحث 

7.1. ارزیابی توزیع CH 

 7.2. ارزیابی مصرف انرژی 

7.3. ارزیابی انرژی باقی‌ مانده شبکه 

7.4. ارزیابی طول‌عمر شبکه 

7.5. ارزیابی تعداد گره‌های زنده 

8. نتیجه‌گیری 

منابع

ABSTRACT

1. Introduction

2. Related work

3. Preliminaries

3.1. Energy model

3.2. Data aggregation model

4. The improved EADUC protocol mechanism

5. Protocol analysis

6. Performance evaluation

6.1. Simulation environment

6.2. Simulation parameters

7. Results and discussions

7.1. CH distribution evaluation

7.2. Energy consumption evaluation

7.3. Network remaining energy evaluation

7.4. Network lifetime evaluation

7.5. Number of alive nodes evaluation

8. Conclusions

References