21337

21337

مديريت تخصيص و زمانبندي وظايف در شبكه هاي حسگر كنشگر بي¬سيم با معماري تركيبي با آگاهي از قابليت اطمينان

دكتري

كامپيوتر

1398

1398/04/26

دكتر محمدرضا كنگاوري

كامپيوتر

زمانبندي وظايف در شبكه¬هاي حسگر كنشگر بي¬سيم، بيشتر با هدف كاهش انرژي مصرفي و به نسبت كمتر كاهش زمان پاسخ شبكه انجام شده¬اند و از معيار مهمي چون قابليت اطمينان سرويس غافل شده-اند. همچنين نوع وظايف و ويژگي¬هاي گوناگون آنها كه مي¬توانند بر اجراي وظايف در اين شبكه¬ها اثرگذار باشند، چندان مورد توجه قرار نگرفته¬اند و لذا استفاده از اين زمانبندها در كاربردهايي نظير عمليات امداد و نجات كاربردي نشده است. در اين رساله، راهكاري براي تخصيص و زمانبندي وظايف در شبكه¬هاي حسگر كنشگر بي¬سيم با هدف رفع چالش¬هاي مذكور ارائه گرديده است. بدين منظور، ابتدا مدل زمانبندپذيري كه معيارهاي مهم توازن باركاري، قابليت اطمينان و قابليت پاسخگويي كنشگرها را در نظر مي¬گيرد، معرفي شده است. سپس جهت تحليل زمانبندپذيري وظايف، مدل صوري دسترس¬پذيري با استفاده از جبر فرآيندي ارائه شده و با بهره¬گيري از مدل زمانبندپذيري پيشنهادي، راهكاري جهت توزيع وظايف با توجه به نيازمندي¬هاي معماري تركيبي ارائه گرديده است. به منظور تخصيص وظايف محلي، پروتكل DSP ارائه شده است كه با استفاده از پروتكل پيشنهادي FitCa بهترين كنشگرها را جهت تخصيص وظايف محلي تعيين كرده و با بهره¬گيري از نظريه مزايده، وظايف را به بهترين كنشگرها تخصيص مي¬دهد. به منظور زمانبندي وظايف سراسري، با توجه به پيچيدگي بيشتر اين وظايف در مقايسه با وظايف محلي و در نظر گرفتن اين واقعيت كه اين وظايف داراي يك يا چند زيروظيفه هستند كه بين آنها مي¬تواند وابستگي وجود داشته باشد، با بهره¬گيري از بهينه¬سازي مبتني بر جغرافياي زيستي، تكنيكي جهت تخصيص وظايف سراسري به كنشگرها ارائه گرديده است. در نهايت پس از تخصيص وظايف به كنشگرها، زمانبندي وظايف با استفاده از پروتكل پيشنهادي TSP در سطح گره¬هاي كنشگر انجام مي¬گردد. در بحث درستي¬يابي راهكار پيشنهادي، ويژگي¬هاي ايمني، زنده بودن محدود و عدم وجود بن¬بست مدنظر بوده است كه به كمك روش بررسي مدل و آتوماتاي زماني، برقراري اين ويژگي¬ها اثبات شده است. نتايج بدست آمده از شبيه¬سازي¬ها نشان مي¬دهد راهكار پيشنهادي در مقايسه با بهترين نتايج بدست آمده از تحقيقات مورد مقايسه، بطور ميانگين، زمان پاسخ شبكه را به ميزان %14 كاهش، نرخ رعايت موعد زماني وظايف را به ميزان %15 افزايش، قابليت اطمينان سرويس و انرژي باقي¬مانده كنشگرها را به ترتيب به ميزان %11 و %12 افزايش داده است. همچنين همانگونه كه نشان داده شده، راهكار پيشنهادي مي¬تواند طول عمر گره¬هاي كنشگر را نيز افزايش دهد. از مهمترين كارهاي آتي، زمانبندي وظايفي است كه به صورت پيوسته و جرياني بوده و مكان رويدادهاي مرتبط با اين وظايف در شبكه¬هاي حسگر كنشگر بي¬سيم متحرك مي¬باشند.

1398/09/04

Service Reliability Aware Task Allocation Management and Scheduling in Hybrid Architecture Wireless Sensor Actor Networks

12/21/2019 12:00:00 AM

Majority of existing task schedulers in WSANs are only concerned with energy savings or meeting temporal constraints, overlooking service reliability. They do not consider the types and various features of tasks that WSANs may need to perform, making such schedulers inapplicable to critical applications such as search and rescue missions. In this study, an approach is presented to address the mentioned challenges. To this end, we have introduced a scheduling model that considers important criteria such as load balancing, reliability, and performability of actors. For schedulability analysis, a reachability model formally using process algebra is presented. Based on the proposed schedulability model, the schedulability of tasks scheduling approach, the formal availability model is presented using process algebra. Also, using the proposed scheduling model, we have proposed a task scheduling approach considering requirements of hybrid architecture. To allocate local tasks, a cost-effective and auction-based distributed scheduling protocol (DSP) is presented. Using the proposed protocol named FitCa, DSP determines a cost-effective set of actors and assigns local tasks to the best actors. In order to allocate global tasks considering the fact that they are more complex than local tasks and may have one or more dependent subtasks, using bibgeography optimization technique, allocation of global tasks is carried out. Finally, after allocation of all tasks to actors, tasks are scheduled at actor level using the proposed task scheduling protocol (TSP). To verify the correctness of the proposed approach and models, a framework based on timed automata is presented. Based on this model checking technique we analyze and prove bounded liveness, deadlock-freeness, and correctness. The results obtained from the required simulations of the proposed approach represent 14% improvement in reducing make-span, 11% improvement in increasing service reliability, 15% improvement in increasing deadline hit ratio, and 12% improvement in increasing residual energies of actors compared to the best results of the related works. It is also shown that the proposed approach can increase the life time of actor nodes.