Photo Photo Photo Photo Photo Photo

Print
E-mail
Computer science: A Genetic Algorithm for Minimum Set Covering Problem in Reliable and Efficient Wireless Sensor Networks

 

A Genetic Algorithm for Minimum Set Covering Problem in Reliable and Efficient Wireless Sensor Networks

Bara'a A. Attea*, Sarab M. Hameed

Department of Computer Science, College of Science, Baghdad University, Baghdad, Iraq.

Abstract

   Densely deployment of sensors is generally employed in wireless sensor networks (WSNs) to ensure energy-efficient covering of a target area. Many sensors scheduling techniques have been recently proposed for designing such energy-efficient WSNs. Sensors scheduling has been modeled, in the literature, as a generalization of minimum set covering problem (MSCP) problem. MSCP is a well-known NP-hard optimization problem used to model a large range of problems arising from scheduling, manufacturing, service planning, information retrieval, etc. In this paper, the MSCP is modeled to design an energy-efficient wireless sensor networks (WSNs) that can reliably cover a target area. Unlike other attempts in the literature, which consider only a simple disk sensing model, this paper addresses the problem of scheduling the minimum number of sensors (i.e., finding the minimum set cover) while considering a more realistic sensing model to handle uncertainty into the sensors' target-coverage reliability. The paper investigates the development of a genetic algorithm (GA) whose main ingredient is to maintain scheduling of a minimum number of sensors and thus to support energy-efficient WSNs. With the aid of the remaining unassigned sensors, the reliability of the generated set cover provided by the GA, can further be enhanced by a post-heuristic step. Performance evaluations on solution quality in terms of both sensor cost and coverage reliability are measured through extensive simulations, showing the impact of number of targets, sensor density and sensing radius.

الخوارزمية الجينية لمشكلة المجموعةالادنىللتغطيةفي شبكات الاستشعار اللاسلكية الموثوقة والفعالة

براء علي عطيه، سراب مجيد حميد

قسم الحاسبات، كلية العلوم، جامعة بغداد، بغداد، العراق.

الخلاصة

يستخدم عادة نشر أجهزة الاستشعاربكثافة في شبكات الاستشعار اللاسلكية (WSNs) لضمان تغطية كفوءهوأقتصادية في المنطقة المستهدفة. حديثأتم اقتراح العديد من تقنيات جدولة أجهزة الاستشعار لتصميمWSNs كفوء من ناحية استخدام الطاقة وأصبحت هذه المشكل تعميم لمشكلهالمجموعة الادنىللتغطيهMSCP .(MSCP) هي مشكلة NP-Hardوالمطبقة في حلالعديد من المشاكل الناجمة مثل التصنيع، وتخطيط الخدمة، واسترجاع المعلومات، وما إلى ذلك من المشاكل. في هذ البحث ، تم نمذجةMSCP لتصميم شبكات الاستشعار اللاسلكية (WSNs) والتي يمكن أن تغطي المنطقة المستهدفة بثقة وبطريقة أقتصادية. على عكس محاولات أخرى في هذا المجال، يتناول هذاالبحث مشكلة جدولة الحد الأدنى لعدد من أجهزة الاستشعار ( إيجاد الحد الأدنى لغطاء مجموعة)، في نموذج الاستشعار أكثر واقعية للتعامل مع حالة عدم اليقين فيموثوقية أجهزة الاستشعار في تغطية الهدف. تدارس هذا البحث تطوير الخوارزمية الجينية (GA) للحفاظ على جدوله لعدد أدنى من أجهزة الاستشعار، لدعم WSNs كفوء في استخدام الطاقة . وبمساعدة من أجهزة الاستشعار غير المعينة المتبقية، يمكن زيادة موثوقية تغطية المجموعة التي تقدمها GA بعد خطوة الكشف عن مجريات الأمور. تم قياس تقييم الأداء على نوعية الحل من حيث تكلفة الاستشعار وموثوقية التغطية من خلال محاكاة واسعة النطاق، والتي تبين أثر عدد الأهداف، وكثافة اجهزة الاستشعار ونصف قطر الاستشعار عن بعد.



alt

 

S5 Box

Login



Register

*
*
*
*
*

Fields marked with an asterisk (*) are required.