TY - JOUR ID - TI - Multi-Objective Set Cover Problem for Reliable and Efficient Wireless Sensor Networks مشكلة تغطية المجموعة متعددة الأهداف لموثوقية وكفاءة شبكات الأستشعار اللاسلكية AU - Bara'a Ali Attea براء علي عطية PY - 2015 VL - 56 IS - 2A SP - 1147 EP - 1160 JO - Iraqi Journal of Science المجلة العراقية للعلوم SN - 00672904 23121637 AB - Achieving energy-efficient Wireless Sensor Network (WSN) that monitors all targets at all times is an essential challenge facing many large-scale surveillance applications.Single-objective set cover problem (SCP) is a well-known NP-hard optimization problem used to set a minimum set of active sensors that efficiently cover all the targeted area. Realizing that designing energy-efficient WSN and providing reliable coverage are in conflict with each other, a multi-objective optimization tool is a strong choice for providing a set of approximate Pareto optimal solutions (i.e., Pareto Front) that come up with tradeoff between these two objectives. Thus, in the context of WSNs design problem, our main contribution is to turn the definition of single-objective (SCP) into a multi-objective problem by adopting an additional conflicting objective to be optimized. To the best of our knowledge, improving coverage reliability of WSNs has not been explored while simultaneously solving SCP problem. This paper addresses the problem of improving coverage reliability of WSNsusing a realistic sensing model to handle coverage uncertainty. To this end, this paper formulates the so-called multi-objective SCP with the goal of selecting the minimum number of sensors so that the selected set reliably covers all the targets.To cope with two optimization objectives rather than one objective, this paperinvestigates the use of a multi-objective evolutionary algorithm, the so-called non-dominated sorting genetic algorithm for tackling the formulated problem. Moreover, it adopts a heuristic crossover operator designed specifically to improve the performance of the algorithm.The effectiveness of the algorithm is verified in terms of sensors cost and coverage reliability under extensive simulations.

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