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

چکیده

        بسیاری از تکنیک های مسیریابی مبتنی بر کلاستربندی برای شبکه‌های حسگر بی‌سیم (WSN ها) در راه‌کارهای پیشین مطرح شده است. با این حال، بسیاری از پروتکل‌های پیشنهادی بر انتخاب سرخوشه (CH) تاکید کرده و چگونگی ارسال مجدد داده‌های جمع‌آوری شده توسط سرخوشه به ایستگاه پایه (BS) را نادیده می‌گیرند. علاوه بر این، آن‌ها تمایل به استفاده از اطلاعات غیر واقع‌بینانه و پارامترهای فرضی دارند. این نمونه‎ها شامل استفاده از محدوده انتقال متناهی و آگاه از مکان است. آن‌ها همچنین از یک مدل انرژی که اساساً برای مدل‌سازی قدرت رادیویی مصرفی در شبکه‌های بی‌سیم است استفاده می‌کنند. در این مقاله، دو فرموله بندی برنامه‌ریزی خطی (LP) برای مشکل کلاستربندی و مسیریابی ارائه‌شده است که شامل دو الگوریتم براساس الگوریتم ازدحام ذرات هستند (PSO). الگوریتم کلاستربندی، بهینه‌ترین مجموعه سرخوشه را می‌یابد به گونه‌ای که انرژی مصرفی، کیفیت خوشه‌بندی و پوشش شبکه بیشینه شود. الگوریتم مسیریابی با یک روش کدگذاری و تابع عملکرد توسعه‌یافته و بهینه‌ترین درخت مسیریابی را که این سر خوشه‌ها را به ایستگاه پایه (BS) متصل می‌کند را می‌یابد. این دو الگوریتم سپس با یک پروتکل دو لایه‎ برای ارائه کامل و عملی مدل خوشه‌بندی ترکیب می‌شوند. تأثیر استفاده از یک شبکه واقعی و الگوی واقعی انرژی مصرفی در ارتباطات مبتنی بر خوشه‌بندی برای WSN مورد بررسی قرار خواهد گرفت. شبیه‌سازی‌های گسترده‌ای در 50 مدل WSN همگن و ناهمگن ارزیابی و با پروتکل‌های مبتنی بر خوشه‌بندی مقایسه شده است. نتایج نشان می‌دهد که پروتکل پیشنهادی در شرایط مختلف معیارهای عملکرد مانند مقیاس‌پذیری، نرخ تحویل بسته (PDR) در سرخوشه و تحویل بسته داده‌ها به BS بهتر از سایر پروتکل‌ها عمل می‌کند.

1. مقدمه

1.1. پس زمینه

        شبکه‌های حسگر بی‌سیم (WSN) تکنولوژی قدرتمندی به همراه هزاران برنامه کاربردی می‌باشند. این نوع شبکه‌ها به تکنولوژی مهمی در تشخیص کاربردهایی شامل کاربردهای پایش (مانیتورینگ) پدیده‌ها و کاربردهای  پردازش داده‌های سنگین مثل عملیات ارتشی و مانیتورینگ محیط‌های حساس و سیستم‌های surveillance تبدیل‌شده‌اند.

       هر WSN شامل ده‌ها تا هزاران گره حسگر است که از طریق کانال‌های بی‌سیم برای share کردن اطلاعات و پردازش‌های همکار (Yu et al., 2006) ارتباط برقرار می‌کنند. همواره، گره‌ها در مناطق وسیع به شکل ایستا قرار داده می‌شوند. به هر حال، این گره‌ها می‌توانند موبایل بوده و یا در محیط حرکت داشته باشند.

       گره‌های WSN می‌توانند محیط را حس کنند و با گره‌های همسایه ارتباط داشته باشند و در اغلب موارد محاسبات اساسی را بر روی‌ داده‌های جمع‌آوری شده اجرا کنند (Zungeru et al., 2012; Akkaya and Younis, 2005). این ویژگی‌ها WSNرا به انتخابی خوب در کاربردهای مانیتورینگ محیط، محیط حساس ارتشی، جستجو و تفتیش و مانیتورینگ ساختمان برای ایمن بودن زیرساخت یا ایمنی بدن انسان با مانیتورینگ بیماری می‌کند (Yu et al., 2006).

       فاکتورهایی بر روی طراحی و عملیات انجام‌شده توسط WSN ها تأثیر دارد. این فاکتورها شامل بهره‎وری انرژی و آگاهی، نگه‌داری ارتباطات، محدودیت استفاده از منابع، تأخیر کم، پوشش شبکه و تعادل بار در انرژی استفاده‌شده به وسیله گره‌های حسگر است. به دلیل این ویژگی‌ها، وظیفه انتخاب یا ارایه الگوریتم مسیریابی جدید یا الگوریتم ارتباطی برای کاربردهای خاص WSNها چالش‌برانگیز است (Dwivedi and Vays, 2010).

       با استفاده زا روش‌های خوشه‌بندی در WSNها می‌تواند به حل برخی از نگرانی‌ها کمک کند. این کمک می‌تواند به وسیله سازمان‌دهی گره‌های شبکه در خوشه‌های کوچک و انتخاب یک سرخوشه (CH) مناسب باشد. گره‌های حسگر در هر خوشه، داده‌های خود را به ایستگاه پایه خاصی ارسال می‌کنند (BS) (Abbasi and Younis, 2007). در حقیقت فقط سرخوشه، ارتباط بین اطلاعات درونی و بیرونی خوشه را برقرار می‌سازد و سایر گره‌ها ارتباطی با گره‌های سایر خوشه‌ها ندارند (Arboleda and Nasser, 2006).

        هنگامی که WSN ها به خوشه‌هایی تقسیم می‌شوند، ارتباط بین گره‌ها می‌تواند به صورت Inter-cluster یا intra-cluster باشد. ارتباطات intra-cluster شامل تغییر داده‌ها بین اعضای گره‎ها و سر خوشه‌های مربوطه است. ارتباطات inter-cluster شامل انتقال داده بین سر خوشه‌ها یا بین سرخوشه و ایستگاه پایه است.

       فرآیندی که به وسیله آن داده‌ها به طور کارا بین سر خوشه‌ها و ایستگاه‌های پایه فرستاده می‌شوند (ارتباطات inter-cluster) یکی از مهم‌ترین جنبه‌ها و ویژگی‌های WSN است. یک روش ساده برای انجام این کار، این است که هر سرخوشه، داده‌ها را به طور مستقیم (رویکرد مبتنی بر تک گام) با ایستگاه‌های پایه ارسال کند، یا به گره‌های میانی اجازه دهد تا در ارسال بسته‌های داده بین سرخوشه و ایستگاه پایه (رویکرد مبتنی بر چند گام) شرکت کنند (Zungeru et al., 2012). به هر حال، در هر WSN، گره‌های منفرد ارتباطات محدودی در قالب یک شبکه ad-hoc بر روی یک رسانه بی‌سیم دارند. علاوه براین، ایستگاه‌های کاری، همواره دورتر از منطقه سنجش قرار دارند و غالباً به طور مستقیم به تمام نقاط دسترسی ندارند. گره‌ها با توجه به محدوده ارتباط محدود، دارای مشکلاتی در انتشار سیگنال هستند. یک رویکرد واقع‌بینانه استفاده از یک یا چند گام درون خوشه برای ایجاد ارتباط است. برای ارتباط قابل‌اطمینان بین داده‌ها، هر دو بسته داده نیاز به کنترل و استفاده از مدل ارتباطی چند گامی دارند (Saleem et al., 2011). 

        هدف خوشه‌بندی، جستجو بین یک گروه از سنسورها نودها برای یافتن مجموعه‌ای از گره‌ها است که می‌توانند به عنوان سرخوشه عمل کنند. برای یک توپولوژی شبکه داده‌شده، یافتن مجموعه بهینه از گره‌های سرخوشه مشکل است. برای N گره حسگر، 2N-1 ترکیب متفاوت وجود دارد، که هر گره حسگر می‌تواند به عنوان سرخوشه یا CH انتخاب گردد تا انتخاب نگردد. این به عنوان یک مسئله چندجمله‌ای (NP) شناخته شده است. به این معنی که پاسخی برای این نوع مسائل در زمان چندجمله‌ای وجود ندارد ((Agarwal and Procopiuc, 2002. 

        تابع اصلی الگوریتم مسیریابی انتخاب مسیر از مجموعه مسیرهای موجود است که غالباً براساس برخی معیارهای محدود می‏باشد. وقتی که یکی از بهینه‌ترین مجموعه‌های انتخاب سرخوشه در فاز خوشه‌بندی انتخاب می‌گردد، گام بعدی یافتن مسیر بهینه درختی از سرخوشه تا BS است، اگرچه کمینه کردن هزینه کلی درخت مدنظر است. این مورد نیز به عنوان یک مسئله NP شناخته شده است (Dorigo et al., 2006). بنابراین، الگوریتم‌های چندجمله‌ای به دلیل پیچیدگی محاسباتی بالا در سی ستم‌های ارتباط زمان واقعی در زمان چندجمله‌ای قابل حل نمی‌باشند.

Abstract

        Many cluster-based routing techniques for Wireless Sensor Networks (WSNs) have been proposed in the literature. However, most of the proposed protocols emphasized on the Cluster Head (CH) selection ignoring how the CHs will send the aggregated data back to the Base Station (BS). Furthermore, they tend to use nonrealistic parameters and assumptions. Such examples include the use of infinite transmission range and location awareness. They also used an energy model that is fundamentally flawed for modelling radio power consumption in sensor networks. In this paper, two Linear Programming (LP) formulations to the problems of clustering and routing are presented followed by two proposed algorithms for the same based on Particle Swarm Optimization (PSO). The clustering algorithm finds the optimal set of CHs that maximize the energy efficiency, cluster quality and network coverage. The routing algorithm is developed with a novel particle encoding scheme and fitness function to find the optimal routing tree that connects these CHs to the BS. These two algorithms are then combined into a two-tier protocol to provide a complete and practical clustering model. The effect of using a realistic network and energy consumption model in cluster-based communication for WSN will be investigated. Extensive simulations on 50 homogeneous and heterogeneous WSN models are evaluated and compared against well-known cluster-based sensor network protocols. The results demonstrate that the proposed protocol performs better than such protocols in terms of various performance metrics such as scalability, Packet Delivery Rate (PDR) at the CHs and delivery of total data packets to the BS.

1. Introduction

1.1. Background

        Wireless Sensor Network (WSN) has emerged as a powerful technological platform with tremendous and novel applications. It has become an important technology in realizing many applications including both simple phenomena monitoring applications and heavy-duty data streaming applications such as military operations, environment monitoring and surveillance systems.

        A WSN usually consists of tens to thousands of sensor nodes that communicate through wireless channels for information sharing and cooperative processing (Yu et al., 2006). Usually, the nodes are statically deployed over vast areas. However, they can also be mobile and capable of interacting with the environment.

        WSN nodes also can sense the environment, communicate with neighboring nodes, and in many cases perform basic computations on the data being collected (Zungeru et al., 2012; Akkaya and Younis, 2005).These features made WSN an excellent choice for many applications like environmental monitoring, military surveillance, search and rescue, in buildings for infrastructure health monitoring, or even in bodies for patient monitoring (Yu et al., 2006).

        There are some factors that affect designing and operating WSN. These factors include energy efficiency and awareness, connection maintenance, minimum resource usage limitation, low latency, network coverage and load balancing in terms of energy used by sensor nodes. Due to these unique inherent characteristics it is a challenging task to select or propose a new routing or communication algorithm for a specific WSN application (Dwivedi and Vyas, 2010).

       Using clustering techniques in WSN can help solving some of those concerns, by organizing the network nodes into smaller clusters and elect a cluster head (CH). Sensor nodes in each cluster transmit their data to their respective CH and CH aggregates data and forward them to a central base station (BS) (Abbasi and Younis, 2007). The fact that only the CH is transmitting information out of the cluster helps avoid collisions between the sensors inside the cluster because they do not have to share the communication channel with the nodes in other clusters (Arboleda and Nasser, 2006).

        Once the WSN has been divided into clusters, the communication between nodes can be either intra-cluster or inter-cluster. Intracluster communication comprises the data exchanges between the member nodes and their respective CH. Inter-cluster communication includes transmission of the data between the CHs or between the CH and the BS.

       The process by which data are forwarded efficiently between the CHs and the BS (inter-cluster communication) is an important aspect and essential feature of WSN. A simple method to accomplish this task is for each CH to exchange data directly with the BS (a single hop based approach), or allowing intermediate nodes to participate in forwarding data packets between the CH and the BS (a multihop based approach) (Zungeru et al., 2012). However, in a WSN, individual nodes have limited communication range and form an ad hoc network over a shared wireless medium. Furthermore, the BS is usually located far away from the sensing area and is often not directly reachable to all nodes due to limited communication range and signal propagation problems. A more realistic approach is to use a multihop inter-cluster communication model. For a more reliable data communication, Both data and control packets need to be routed using a multihop communication model (Saleem et al., 2011).

         The objective of clustering is to search among a group of sensor nodes to find a set of nodes that can act as cluster-heads. For a given network topology, it is difficult to find the optimal set of CH nodes. For N sensor nodes, there are 2N1 different combination of solutions, where in each solution, a sensor node is either elected as CH or nonCH. This has been proved to be a Non-deterministic Polynomial (NP)- hard optimization problem (Agarwal and Procopiuc, 2002).

        The basic function of a routing algorithm is to select a route, from the set of available routes, that is most efficient based on some specific criteria. Once the optimal set of CHs is elected in the clustering phase, the next step is to find the optimal routing tree from the CHs to the BS while minimizing the total cost of that tree. Routing is at its most basic level an optimization problem. It also has been known to be NP-hard problem (Dorigo et al., 2006). Therefore, polynomial-time algorithms are impossible to use due to their high computational complexity in real-time communications systems.

چکیده

1. مقدمه

1.1. پس زمینه

1.2. اظهارنظر نویسندگان

2. راه‏کارهای پیشین

2.1. روش‌های اکتشافی

2.2. روش‌های فرا اکتشافی

3. بررسی اجمالی بهینه‌سازی ازدحام ذرات

3.1. ورژن اصلی PSO

3.2. الگوریتم PSO 2011

4. مدل سیستم

4.1. مدل WSN

4.2. مدل مصرف انرژی

5. تشکیل LP برای مشکل خوشه‌بندی و مسیریابی

5.1. تذکرات مورد استفاده

5.2. تشکیل خوشه برای مشکل خوشه‌بندی

5.2.1. بهره وری انرژی

5.2.2. کیفیت خوشه‌ها

5.2.3. پوشش شبکه

5.3. تشکیل LP برای مشکل مسیریابی

5.3.1. کارایی انرژی

5.3.2. کیفیت لینک

6. پروتکل پیشنهادی

6.1. الگوریتم خوشه‌بندی

6.1.1. مقداردهی اولیه ذرات

6.1.2. ارزیابی ذرات

6.2. الگوریتم مسیریابی

6.2.1. مقداردهی اولیه ذرات

6.2.2. ارزیابی ذرات

6.3. تجزیه و تحلیل پیچیدگی

6.3.1. گره BS

6.3.2. سایر گره‌های شبکه

7. شبیه‌ سازی و نتایج

8. نتیجه گیری و کارهای آتی

منابع

Abstract

1. Introduction

1.1. Background

1.2. Authors' contributions

2. Related work

2.1. Heuristic approaches

2.2. Metaheuristic approaches

3. Overview of particle swarm optimization

3.1. Original PSO version

3.2. Standard PSO 2011

4. The system model

4.1. The WSN model

4.2. The energy consumption model

5. LP formulations for the clustering and routing problem

5.1. Notations used

5.2. LP formulation for the clustering problem

5.2.1. Energy efficiency

5.2.2. Cluster quality

5.2.3. Network coverage

5.3. LP formulation for the routing problem

5.3.1. Energy efficiency

5.3.2. Link quality

6. The proposed protocol

6.1. The clustering algorithm

6.1.1. Initialization of particles

6.1.2. Particles evaluation

6.2. The routing algorithm

6.2.1. Initialization of particles

6.2.2. Particles evaluation

6.3. Complexity analysis

6.3.1. The BS node

6.3.2. Other network nodes

7. Simulations and results

8. Conclusions and future work

References