Photo Photo Photo Photo Photo Photo

Print
E-mail
Computer Science: Multi-layer Multi-objective Evolutionary Algorithm for Adjustable Range Set Covers Problem in Wireless Sensor Networks

 

Multi-layer Multi-objective Evolutionary Algorithm for Adjustable Range Set Covers Problem in Wireless Sensor Networks

Bara'a Ali Attea*, Dlsoz Abdalkarim Rashid

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

Abstract

Establishing complete and reliable coverage for a long time-span is a crucial issue in densely surveillance wireless sensor networks (WSNs). Many scheduling algorithms have been proposed to model the problem as a maximum disjoint set covers (DSC) problem. The goal of DSC based algorithms is to schedule sensors into several disjoint subsets. One subset is assigned to be active, whereas, all remaining subsets are set to sleep. An extension to the maximum disjoint set covers problem has also been addressed in literature to allow for more advance sensors to adjust their sensing range. The problem, then, is extended to finding maximum number of overlapped set covers. Unlike all related works which concern with the disc sensing model, the contribution of this paper is to reformulate the maximum overlapped set covers problem to handle the probabilistic sensing model. The problem is addressed as a multi-objective optimization (MOO) problem and the well-known decomposition based multi-objective evolutionary algorithm (MOEA/D) is adopted to solve the stated problem. A Multi-layer MOEA/D is suggested, wherein each layer yields a distinct set cover. Performance evaluations in terms of total number of set covers, total residual energy, and coverage reliability are reported through extensive simulations. The main aspect of the results reveals that the network's lifetime (i.e. total number of set covers) can be extended by increasing number of sensors. On the other hand, the coverage reliability can be increased by increasing sensing ranges but at the expense of decreasing the network's lifetime.

Keywords: adjustable sensing range, multi-objective optimization, set covers, heterogeneous wireless sensor networks.

 

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

براء علي عطية*, دلسوز عبد الكريم رشيد

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

الخلاصة

في الأدبيات تم اقتراح العديد من خوارزميات جدولة أجهزة الأستشعار باعتبارها مشكلة أمتداد لما يسمى مشكلة (DSC)  والغاية منها هو ترتيب أكبر عدد ممكن من المجموعات الفرعية المنفصلة لأجهزة الاستشعار. بعد ذلك يتم تعيين مجموعة فرعية واحدة فقط من أجهزة الاستشعار لتكون نشطة لأداء عملية التغطية، في حين يتم تسكين بقية  المجموعات الفرعية. أحد أهم امتدادات هذه المشكلة هو تحديد العدد الأقصى من المجاميع الفرعية وبنفس الوقت تضبيط قابلية التغطية لكل مستشعر وعلى هذا الأساس ممكن أن تتحول المجاميع من مجاميع منفصلة الى مجاميع مركبة مؤدية في النهاية الى زيادة تعقيد المشكلة. هدف هذا البحث هو إعادة صياغة مشكلة العدد الأقصى من المجاميع المتراكبة آخذا بنظر الأعتبار القابلية الواقعية لتحسس المستشعرات. تم أعتماد الخوارزمية التطورية متعددة الأهداف المعروفة (MOEA / D)  في حل المشكلة المذكورة. تم اقتراح تخطيط متعدد الطبقات لتصميم الخوارزمية ، حيث تنتج كل طبقة مجموعة متميزة من أجهزة الاستشعار النشطة. تم تقييم أداء النموذج المقترح من ثلاثة جوانب: من حيث العدد الإجمالي للمجاميع المتراكبة، ومجموع الطاقة المتبقية، وموثوقية التغطية من خلال محاكاة واسعة النطاق. النتائج المتوفرة تبين تأثير العوامل المختلفة بما في ذلك عدد أجهزة الاستشعار ونطاق التغطية للمستشعر. الجانب الرئيسي من النتائج تكشف عن أن عمر الشبكة (أي العدد الإجمالي للمجماميع المتراكبة) يتزايد مع تزايد عدد المستشعرات المتوفرة

. من ناحية أخرى، يمكن زيادة موثوقية التغطية عن طريق زيادة نطاقات الاستشعار ولكن على حساب تناقص عمر الشبكة


 

 

 

 

alt

 

S5 Box

Login



Register

*
*
*
*
*

Fields marked with an asterisk (*) are required.