TY - JOUR ID - TI - A Genetic Algorithm for Minimum Set Covering Problem in Reliable and Efficient Wireless Sensor Networks الخوارزمية الجينية لمشكلة المجموعة الادنى للتغطية في شبكات الاستشعار اللاسلكية الموثوقة والفعالة AU - Bara'a A. Attea براء علي عطيه AU - Sarab M. Hameed سراب مجيد حميد PY - 2014 VL - 55 IS - 1 SP - 224 EP - 240 JO - Iraqi Journal of Science المجلة العراقية للعلوم SN - 00672904 23121637 AB - 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 بعد خطوة الكشف عن مجريات الأمور. تم قياس تقييم الأداء على نوعية الحل من حيث تكلفة الاستشعار وموثوقية التغطية من خلال محاكاة واسعة النطاق، والتي تبين أثر عدد الأهداف، وكثافة اجهزة الاستشعار ونصف قطر الاستشعار عن بعد. ER -