پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شماره‌ها | 1,652 |
| تعداد مقالات | 13,408 |
| تعداد مشاهده مقاله | 30,253,945 |
| تعداد دریافت فایل اصل مقاله | 12,090,150 |
پوشش‌دهی اهداف و نواحی در شبکۀ حسگر بی‌سیم با استفاده از الگوریتم‌های تحلیلی و تکاملی در حل مسائل بهینه‌سازی | |||||||||||||||||||||||||||||||||||||||||||||||||||
| هوش محاسباتی در مهندسی برق | |||||||||||||||||||||||||||||||||||||||||||||||||||
| مقاله 5، دوره 13، شماره 1، فروردین 1401، صفحه 39-54 اصل مقاله (1.61 M) | |||||||||||||||||||||||||||||||||||||||||||||||||||
| نوع مقاله: مقاله پژوهشی فارسی | |||||||||||||||||||||||||||||||||||||||||||||||||||
| شناسه دیجیتال (DOI): 10.22108/isee.2020.122866.1372 | |||||||||||||||||||||||||||||||||||||||||||||||||||
| نویسندگان | |||||||||||||||||||||||||||||||||||||||||||||||||||
| محسن شیخ حسینی* 1؛ سیدروح الله ثمره هاشمی2 | |||||||||||||||||||||||||||||||||||||||||||||||||||
| 1استادیار گروه پژوهشی کامپیوتر و فناوری اطلاعات، پژوهشگاه علوم و تکنولوژی پیشرفته و علوم محیطی، دانشگاه تحصیلات تکمیلی صنعتی و فناوری پیشرفته، کرمان، ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||
| 2استادیار گروه پژوهشی فیبر نوری، پژوهشگاه علوم و تکنولوژی پیشرفته و علوم محیطی، دانشگاه تحصیلات تکمیلی صنعتی و فناوری پیشرفته، کرمان، ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||
| چکیده | |||||||||||||||||||||||||||||||||||||||||||||||||||
| شبکۀ حسگر بی‌سیم، متشکل از مجموعه‌ای از حسگرهای توزیع مکانی‌شده با ساختار ازپیش‌معین یا تصادفی است. مسئلۀ پوشش‌دهی، یکی از شاخص‌های عملکردی این شبکه، شامل سه دسته پوشش‌دهی اهداف، نواحی و مرز است. مسئلۀ مدنظر این مقاله به تحلیل مسائل پوشش‌دهی اهداف و نواحی در یک شبکه با پخش تصادفی معطوف است. در این راستا، الگوریتم تحلیلی شدیدترین نزول مبتنی بر قاعده‌های آرمیجو و وولف برای نخستین‌بار برای حل مسئلۀ پوشش‌دهی اهداف پیشنهاد می‌شود و در مسئلۀ پوشش‌دهی نواحی از یک روش ترکیبی مبتنی بر روش شدیدترین نزول و الگوریتم‌های تکاملی وراثتی و جهش قورباغه‌ای به‌هم‌آمیخته استفاده می‌شود. بر مبنای ارزیابی عملکرد روش‌های پیشنهادی در سناریوهای مختلف، مشخص می‌شود استفاده از روش شدیدترین نزول در مقایسه با الگوریتم وراثتی به پیچیدگی محاسباتی کمتر و دقت بالاتر در پوشش‌دهی اهداف منجر می‌شود و مهم‌تر اینکه این روش، قابلیت مدیریت نحوۀ حرکت حسگرها به مقصد را نیز دارا است. نتایج در مسئلۀ پوشش‌دهی نواحی نیز نشان می‌دهند الگوریتم جهش قورباغه‌ای به‌هم‌آمیخته در مقایسه با الگوریتم وراثتی، دقت بیشتری در پوشش‌دهی دارد؛ البته این افزایش در ازای پیچیدگی بالاتر حاصل می‌شود. | |||||||||||||||||||||||||||||||||||||||||||||||||||
| کلیدواژه‌ها | |||||||||||||||||||||||||||||||||||||||||||||||||||
| الگوریتم شدیدترین نزول؛ الگوریتم جهش قورباغه‌ای به‌هم‌آمیخته؛ الگوریتم وراثتی؛ پوشش‌دهی اهداف و نواحی؛ شبکۀ حسگر بی‌سیم؛ قاعده‌های جستجوی آرمیجو و وولف | |||||||||||||||||||||||||||||||||||||||||||||||||||
| اصل مقاله | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
1- مقدمه[1] شبکۀ حسگر بی‌سیم[1] متشکل از تعدادی گره است که هر گره مبتنی بر یک یا چند حسگر کوچک با انرژی محدود است. این حسگرها در تعامل با محیط نسبت به جمع‌آوری اطلاعات، پردازش جزئی، ذخیره و ارسال بی‌سیم آن اقدام می‌کنند. تکنیک‌های مخابرۀ تک و چندپرشی در سطح شبکه، این اطلاعات را بر مبنای خاصیت پخش محیط‌های بی‌سیم و توانایی همکاری گرهها با یکدیگر منتشر می‌کنند و درنهایت، در مرکز پردازش اطلاعات، دریافت و برای کاربرد در حوزه‌های مختلفی نظیر کشاورزی، صنعتی، نظامی و ... استفاده می‌شود [1-3]. طراحی و پیاده‌سازی شبکه‌های حسگر بی‌سیم در عمل با چالش‌های فراوانی روبه‌رو است که یکی از نخستین و در عین حال، مهم‌ترین این مسائل به نحوۀ استقرار گرهها در ناحیۀ مدنظر بر می‌گردد. به‌طورکلی، دو رویکرد برای استقرار گرهها در شبکۀ حسگر وجود دارد که عبارت‌اند از رویکرد قطعی و تصادفی [4-6]. حسگرها در رویکرد قطعی به‌صورت از پیش برنامه‌ریزی شده‌ای در مختصات مدنظر جایگذاری میشوند. این رویکرد به عملکرد بهینۀ شبکه از منظر پارامترهایی همچون پوشش‌دهی[2]، ارتباط و طول عمر منجر می‌شود؛ اما فقط برای پیاده‌سازی شبکه‌های کوچک کاربردی است و در محیط‌های نظامی و دسترس‌ناپذیر کارایی ندارد. حسگرها در رویکرد تصادفی به‌صورت تصادفی و با بالگرد یا ربات در ناحیۀ مدنظر پخش میشوند که امکان پیاده‌سازی شبکه‌های بزرگ در محیط دسترس‌ناپذیر را فراهم می‌آورند؛ اما عملکرد شبکه در این رویکرد نیازمند بهینه‌سازی است. صرف‌نظر از نوع رویکرد پیاده‌سازی ساختار شبکه‌های حسگر بی‌سیم در ارائۀ رهیافت برای چالش‌های این شبکه‌ها توجه به نکاتی همچون همگن یا ناهمگن بودن شبکه و ثابت یا متحرک بودن گرهها نیز حائز اهمیت است. منظور از شبکۀ همگن، شبکه‌ای است که گرههای شبکه از قابلیت‌های مشابهی همچون شعاع حسگری و مخابرۀ یکسان برخوردارند؛ اما در شبکۀ غیرهمگن گرههای مختلف قابلیت‌های متفاوتی دارند. همچنین از منظر مکان پردازش، شبکه‌های حسگر به دو دستۀ متمرکز و توزیع‌شده تقسیم‌بندی میشوند؛ در شبکه‌های متمرکز، بار پردازشی شبکه در یک پردازندۀ مرکزی انجام می‌شود؛ اما در شبکه‌های توزیع‌شده این بار در سطح گرهها توزیع می‌شود [7-8]. پوشش‌دهی ازجمله مهم‌ترین پارامترهای عملکردی شبکه است که بیان‌کنندۀ نحوۀ پوشش ناحیه با حسگرها است و مشخص می‌کند چه میزان از ناحیه در شعاع حسگری حسگرها واقع شده است [9-10]. چالش پوشش‌دهی معمولاً به سه دستۀ پوشش‌دهی ناحیه[3]، اهداف[4] و مرز[5] تقسیم‌بندی می‌شود. در پوشش‌دهی ناحیه، هدف، ایجاد پوشش حداکثری در ناحیۀ مدنظر است که به تعداد زیادی حسگر نیاز دارد؛ اما رویکرد پوشش‌دهی اهداف به پوشش تعدادی هدف خاص در ناحیۀ مدنظر مربوط است و در پوشش‌دهی مرز، مسیرهای خاصی نظیر مرزهای ناحیه به دلیل ممانعت از نفوذ خرابکاران و نیروهای دشمن تحت پوشش قرار می‌گیرند. ویژگی اصلی دو رویکرد آخر در نیازمندی به تعداد کمتری حسگر است. همچنین برای پوشش‌دهی اهداف نیز سه حالت مختلف متصور است که هر هدف، در ساده‌ترین حالت، فقط با یک حسگر پوشش داده می‌شود. عیب این حالت از دست دادن پوشش‌دهی با هرگونه خرابی حسگر است؛ بنابراین، برای پوشش‌دهی اهداف و نقاط استراتژیک بیش از یک حسگر منظور می‌شود. در این شرایط، اگر تعداد حسگرها برای پوشش اهداف استراتژیک با یکدیگر یکسان باشند، مسئله با عنوان پوشش‌دهی - تایی شناخته می‌شود و اگر این تعداد برای اهداف، مختلف متفاوت باشد، مسئلۀ مدنظر با عنوان پوشش‌دهی - تایی شناخته می‌شود [9-10]. حجم مطالعات در مواجهه با چالش‌های شبکۀ حسگر بی‌سیم همچون پوشش‌دهی بسیار زیاد است. این امر در وهلۀ نخست، ناشی از تنوع در انتخاب جزئیات مدل شبکه همچون همگن یا غیرهمگن بودن، متمرکز یا غیرمتمرکز بودن، متحرک یا ثابت بودن گرهها و ... است. در وهلۀ دوم، ناشی از دسته‌بندی‌های مختلف مسئلۀ پوشش‌دهی است که به مطالعات مجزا منجر می‌شود. در وهلۀ آخر، نتیجۀ تغییر رویکرد در مواجه با چالش‌های شبکۀ حسگر بی‌سیم است؛ زیرا رهیافت اولیۀ بررسی این چالش‌ها مستقل از یکدیگر بوده است؛ اما با توجه به وابستگی برخی چالش‌های شبکه به یکدیگر، به‌تازگی تحلیل هم‌زمان چندین چالش با یکدیگر به‌عنوان رهیافتی جدید مدنظر قرار گرفته است. این تغییر رویکرد نیز به مطالعات متنوعی همچون [11-12] منجر می‌شود که برخی از آنها صرفاً معطوف پوشش‌دهی است و در برخی دیگر، پوشش‌دهی هم‌زمان با سایر چالش‌ها تحلیل می‌شود. در اینجا برای پیشینۀ پژوهش چالش پوشش‌دهی به رویکرد ارائه‌شده در [13] اکتفا می‌شود که در آن، رهیافت‌های مواجهه با این چالش به سه دسته روش‌های کلاسیک، تکاملی و خودبرنامه‌ریزی‌شده تقسیم شدهاند. روش‌های کلاسیک به سه گروه نیرومحور [14، 15]، شبکه‌محور [16، 17] و هندسۀ محاسباتی‌محور [18، 19] تقسیم‌بندی میشوند. روش‌های تکاملی نیز مربوط به استفاده از الگوریتم‌های هوش مصنوعی‌اند که ازجمله آنها الگوریتم وراثتی[6] [20-22]، الگوریتم تبرید شبیه‌سازی‌شده [23] و الگوریتم بهینه‌سازی ازدحام ذرات [24] هستند. درنهایت، روش‌های خودبرنامه‌ریزی‌شده معطوف به حداقل‌سازی توان مصرفی با ارائۀ الگوریتم‌های زمان‌بندی روشن و خاموشی حسگرها هستند [25، 26]. بر مبنای پیشینۀ تحقیق یادشده، ذکر چند نکته در ارتباط با مطالعات موجود در حوزۀ چالش پوشش‌دهی و انگیزه و اهمیت انجام پژوهش حاضر حائز اهمیت است. اول اینکه ماهیت پوشش‌دهی اهداف، متفاوت از پوشش نواحی است و این تفاوت در مطالعات قبلی مدنظر قرار نگرفته است؛ زیرا در پوشش‌دهی اهداف، مطلوب پوشش تعدادی هدف با موقعیت مشخص توسط حسگرها است. بر این مبنا مختصات نهایی که حسگرها باید نسبت به پوشش آن اقدام کنند، مشخص و دردسترس است؛ اما این مختصات در چالش پوشش‌دهی نواحی از پیش تعیین شده نیست و الگوریتم ارائه‌شده باید توانایی دستیابی به آن را داشته باشد. نکتۀ دوم این است روش‌های تکاملی، اغلب از بار محاسباتی نسبتاً زیادی برخوردارند و پوشش نهایی آنها نیز کاملاً بهینه نیست؛ این درحالی است که در صورت تفکیک پوشش‌دهی اهداف از نواحی، امکان استفاده از روش‌های تحلیلی با دقت بالاتر و پیچیدگی کمتر برای چالش پوشش‌دهی اهداف وجود دارد. سوم اینکه خروجی الگوریتم‌های تکاملی صرفاً چیدمان نهایی حسگرها است و هیچ اطلاعاتی از نحوۀ حرکت حسگرها از مختصات تصادفی اولیه برای رسیدن به این چیدمان ارائه نمی‌دهند. بر مبنای این نکات نتیجه می‌شود استفاده از روش‌های تکاملی در حل پوشش‌دهی اهداف غیرضروری است؛ زیرا در پوشش‌دهی اهداف مختصات اولیه و نهایی حسگرها از قبل مشخص است و این چالش صرفاً نیازمندی الگوریتمی است برای مدیریت حرکت حسگرها از مبدا تا مقصد است؛ اما به دلیل نامشخص‌بودن چیدمان و مختصات بهینۀ حسگرها در پوشش‌دهی نواحی، استفاده از روش‌های تکاملی برای دستیابی به این چیدمان در پوشش‌دهی نواحی منطقی است؛ ولی چون خروجی این روش‌ها صرفاً همین چیدمان نهایی است، نیازمندی به الگوریتم مدیریت حرکت حسگرها همچنان در این حالت وجود دارد. در این مقاله، به‌منظور مرتفع‌کردن این نقایص، چالش پوشش‌دهی اهداف از نواحی متمایز فرض می‌شود و هر کدام به‌صورت جداگانه در یک شبکۀ حسگر بی‌سیم با پخش تصادفی بررسی و تحلیل شدند. با توجه به ماهیت چالش پوشش‌دهی اهداف، برای نخستین‌بار استفاده از الگوریتم تحلیلی شدیدترین نزول[7] مبتنی بر قاعدۀ آرمیجو[8] و قاعدۀ وولف[9] به‌عنوان روش کلاسیک تحلیلی (و جایگزین روش‌های تکاملی) برای این چالش پیشنهاد می‌شود. این روش به هر دو صورت متمرکز و توزیع‌شده ارائه می‌شود و نتایج پیاده‌سازی عددی، نخست مؤید جامعیت روش پیشنهادی و عملکرد مناسب آن در شبکه‌های همگن و ناهمگن، انواع مختلف پوشش‌دهی شامل پوشش اهداف با یک، و حسگر، محیط‌های مشتمل بر نویز و موانع است، دوم اینکه این نتایج بیان‌کنندۀ برتری این روش بر الگوریتم وراثتی در برخورداری از دقت بالاتر، پیچیدگی محاسباتی کمتر و فراهم‌آوردن قابلیت مدیریت مسیر حرکت حسگرها است؛ اما با توجه به نیازمندی به تعیین چیدمان بهینه در چالش پوشش‌دهی نواحی، پیشنهاد می‌شود در ابتدا از الگوریتم‌های تکاملی برای دستیابی به این چیدمان استفاده شود و پس از آن، چیدمان حاصل با الگوریتم شدیدترین نزول برای مدیریت حرکت حسگرها به کار گرفته شود. در این راستا، الگوریتم وراثتی به‌عنوان یک روش سنتی به همراه الگوریتم جدید و پیشرفته‌تر جهش قورباغه‌ای به‌هم‌آمیخته[10] به کار گرفته میشوند و عملکرد آنها در تعیین چیدمان بهینه ارزیابی و مقایسه میشوند. ساختار مقاله بدین صورت است که بخش بعد به معرفی الگوریتم شدیدترین نزول مبتنی بر قاعده‌های آرمیجو و وولف اختصاص دارد و بخش سوم، به مدل‌سازی، فرمول‌بندی مسئله و جزئیات الگوریتم پیشنهادی اختصاص دارد. بخش چهارم دربرگیرندۀ نتایج عددی و تحلیل عملکرد الگوریتم پیشنهادی است و درنهایت، در بخش پنجم جمع‌بندی و نتیجۀ پژوهش ارائه می‌شود. 2- الگوریتم شدیدترین نزول مبتنی بر قاعده‌های آرمیجو و وولف 2-1-الگوریتم‌های تکراری در حل مسائل بهینه‌سازی اصول کلی کار الگوریتم‌های تحلیلی در حل مسائل بهینه‌سازی مبتنی بر شروع از یک نقطۀ آغازین و بروزرسانی موقعیت آن در تکرارهای متوالی تا همگرایی به جواب است. فرایند بروزرسانی دنبالۀ جواب این الگوریتم‌ها در تکرارهای متوالی به‌صورت زیر فرمول‌بندی می‌شود:
که در آن و به‌ترتیب معرف جواب در تکرارهای و هستند. نیز میزان نمو تکرار ام است که بردار معرف برای نمو و مقدار ثابت اندازه یا طول گام نمو هستند. همگرایی این فرایند کاملاً به نحوۀ تعیین جهت و طول گام نمو وابسته است؛ بنابراین، اغلب در ابتدا جهت نمو بر مبنای روش‌های جستجوی جهت مشخص می‌شود و سپس طول گام بهینه متناظر با آن به کمک روش‌های جستجوی خط محاسبه می‌شود که جزئیات آنها به شرح ذیل است [27، 28].
2-2-الگوریتم جستجوی جهت مبتنی بر شدیدترین نزول هدف روش‌های جستجوی جهت، پیداکردن جهت جستجو به نحوی است که معرف جهت نزولی تابع در نقطه باشد. به‌صورت ریاضی اثبات می‌شود اگر باشد، آنگاه معرف جهت نزولی تابع در نقطه است که معرف بردار گرادیان تابع در نقطه است و بالانویس نیز معرف ترانهادۀ آن است. به‌منظور برآوردن این شرایط، جهت جستجو به‌صورت انتخاب می‌شود که در آن یک ماتریس معین مثبت است و دو دسته عمده الگوریتم‌های منتجه از آن عبارت‌اند از:
روش نیوتن در مقایسه با روش شدیدترین نزول، پیچیدگی محاسباتی بیشتری دارد و به محاسبۀ ماتریس هسین و معکوس آن نیازمند است. مضاف بر این، همگرایی آن منوط به معین مثبت‌بودن این ماتریس است؛ بنابراین، این مقاله به الگوریتم شدیدترین نزول معطوف است و در ادامه، فرایند جستجوی خط مبتنی بر این روش جستجوی جهت ارائه می‌شود [27، 28].
2-3-الگوریتم‌های جستجوی خط مبتنی بر قاعده‌های آرمیجو و وولف پس از تعیین ، قدم بعدی مشخص‌کردن طول گام برای تعیین میزان جلورفتن در راستای این جهت است. این دیدگاه شهودی در قالب مسئلۀ بهینه‌سازی یک‌بعدی زیر با روش‌های جستجوی خط مدل‌سازی می‌شود:
حل صریح این مسئله به معنای حل یک مسئلۀ بهینه‌سازی در هر تکرار الگوریتم‌های تحلیلی و پذیرفتن بار محاسباتی زیاد است؛ بنابراین، حل آن بیشتر با روش‌های جستجوی خط با پیچیدگی کمتر است که متضمن همگرایی الگوریتم نیز باشند. اصول این روش‌ها بر ارائۀ معیارهایی جهت ممانعت از انتخاب طول گام غیربهینه و بررسی آنها برای دنباله‌ای از طول گام‌ها استوار است [27-30]. قاعدۀ آرمیجو، پرکاربردترین الگوریتم جستجوی خط است که مبتنی بر دو پارامتر ثابت و است و در آن با شروع از طول گام اولیه ، مقدار گام بهینه برابر با انتخاب می‌شود که در آن کوچک‌ترین عدد حسابی است که به‌ازای آن حاصل در رابطۀ زیر صدق کند [29، 30].:
علاوه بر قاعدۀ آرمیجو، روش‌های جستجوی خط دیگری با پیچیدگی محاسباتی بیشتر وجود دارد؛ ازجمله قاعدۀ وولف که در آن به دلیل ممانعت از انتخاب طول گام‌های خیلی بزرگ و خیلی کوچک، بر مبنای ارضای دو معیار ذیل انتخاب می‌شود [29، 30]:
که همانند قاعدۀ آرمیجو، در اینجا است؛ اما است.
3- نتایج اصلی: مدل‌سازی مسئله و روش پیشنهادی 3-1-مدل‌سازی مسئلۀ پوشش‌دهی اهداف ناحیۀ دوبعدی پیوسته متشکل از هدف استراتژیک دردسترس است که مجموعه اهداف و مختصات آن به‌ترتیب با و نمایش داده میشوند. فرض می‌شود تعداد حسگر متحرک نیز به‌صورت تصادفی در این ناحیه پخش شدهاند که مجموعه حسگرها و مختصات آن به‌ترتیب با و نمایش داده میشوند. همچنین این شبکه به‌صورت کلی ناهمگن فرض می‌شود و شعاع حسگری حسگر منظور می‌شود. درخور ذکر است در این مدل، همواره باید باشد؛ زیرا در حالتی که باشد، مسئله فقط مربوط به پوشش‌دهی اهداف و پوشش هر هدف با یک حسگر است؛ اما در حالتی که باشد، هم می‌توان نسبت به پوشش‌دهی اهداف با بیش از یک حسگر اقدام کرد و هم در جهت پوشش‌دهی نواحی گام برداشت. مدل‌سازی پوشش‌دهی بدین صورت است که اگر فاصلۀ اقلیدسی هدف به مختصات از حسگر به مختصات کمتر یا مساوی با شعاع حسگری این حسگر باشد، آنگاه با پوشش داده می‌شود و بیشتربودن این فاصله از شعاع حسگری به معنای عدم پوشش است. به عبارت دیگر:
که احتمال پوشش‌دهی مختصات با حسگر ، شعاع حسگری ، برابر با فاصلۀ اقلیدسی مختصات از است.
3-2-پوشش‌دهی اهداف با الگوریتم شدیدترین نزول مبتنی بر قاعده‌های آرمیجو و وولف مطلوب پوشش‌دهی اهداف، ارائۀ الگوریتمی برای تحت پوشش قرار دادن هدف مفروض در ناحیه با زیرمجموعه‌ای از حسگر موجود است که از قابلیت مدیریت حرکت حسگرها نیز برخوردار باشد. در ادامه برای نخستین‌بار روش تحلیلی مبتنی بر الگوریتم شدیدترین نزول با قاعده‌های آرمیجو و وولف (به هر دو صورت متمرکز و توزیع‌شده) برای این منظور پیشنهاد می‌شود. الگوریتم متمرکز: در این حالت، تمام بار پردازشی الگوریتم به‌صورت متمرکز در پردازندۀ اصلی شبکه انجام می‌پذیرد. فرض بر این است که امکان ارتباط بین این مرکز و حسگرهای شبکه وجود دارد. همچنین در ابتدا فرض می‌شود مطلوب، پوشش‌دادن هر هدف فقط با یک حسگر است و در ادامه، این امر به بیش از یک حسگر تعمیم داده می‌شود. نخستین مرحلۀ الگوریتم پیشنهادی، انتخاب زیرمجموعه تایی از مجموعه حسگرهای دردسترس و تخصیص یک هدف از مجموعه به هر کدام از این حسگرها برای پوشش‌دهی آن هدف است. این کار در الگوریتم متمرکز می‌تواند قبل از پخش تصادفی حسگرها یا بعد از آن انجام شود. در حالت اول، اعضای مجموعه قبل از پخش حسگرها انتخاب و مختصات اهداف متناظر با هر عضو آن در حافظۀ آنها بارگذاری می‌شود. در حالت دوم، پس از پخش حسگرها و با توجه به امکان ارتباط بین مرکز پردازش و حسگرهای شبکه، این مرکز نسبت به انتخاب اعضای مجموعه و تخصیص اهداف به آنها اقدام می‌کند. پس از تعیین مجموعه و تخصیص اعضای به اعضای آن، مرحلۀ نهایی الگوریتم پوشش‌دهی انجام می‌شود که در آن، مرکز پردازش با استفاده از الگوریتم شدیدترین نزول با قاعده‌های آرمیجو و وولف نسبت به حداقل‌سازی فاصلۀ اقلیدسی بین اعضای متناظر دو مجموعه و اقدام می‌کند. اگر فرض شود اعضای به نحوی مرتب شدهاند که هر عضو این مجموعه مسئولیت پوشش عضو متناظر در مجموعه را دارد، آنگاه این فاصله یا به عبارت دیگر، تابع برازش[12] مسئلۀ پوشش‌دهی اهداف برای امین عضو مجموعه با تابع غیرخطی زیر فرمول‌بندی می‌شود:
که معرف فاصلۀ اقلیدسی حسگر ام مجموعه یا همان از امین هدف مجموعه است. در مرحلۀ نهایی الگوریتم با توجه به امکان ارتباط مرکز پردازش با حسگرها، مختصات اولیۀ حسگرهای مجموعه به این مرکز مخابره میشوند و در مرکز با شروع از این نقاط و استفاده از الگوریتم شدیدترین نزول مبتنی بر قاعده‌های آرمیجو وولف نسبت به محاسبۀ میزان نمو و مخابرۀ آن به حسگرها اقدام می‌شود. هر گره بر مبنای نمو دریافتی نسبت به بروزرسانی مختصات خود اقدام می‌کند و این فرایند تا زمان حصول نتیجه و قرارگرفتن اهداف در شعاع حسگری حسگرهای متناظر ادامه می‌یابد. الگوریتم فوق به‌راحتی تعمیم‌پذیر به مسائل پوشش K-تایی و Q- تایی است. تنها تفاوت این حالت در تعداد اعضای زیرمجموعۀ انتخابی است که در حالت کلی برابر است و در آن برابر با تعداد حسگرهای لازم برای پوشش‌دهی هدف است. همچنین در این حالت برای برقراری تناظر بین و و برابری اعضای این دو مجموعه با یکدیگر، باید هر عضو مجموعه به اندازۀ تعداد حسگرهای لازم برای پوشش‌دهی آن تکرار شود که این به معنای تخصیص حسگر به هدف است. الگوریتم توزیع‌شده: کلیات الگوریتم توزیع‌شده با الگوریتم متمرکز مشابه است و تفاوت اصلی در نبود پردازندۀ مرکزی و توزیع محاسبات در سطح گرههای شبکه است. در این حالت، اعضای مجموعه صرفاً باید قبل از پخش تصادفی حسگرها انتخاب و مختصات اهداف متناظر از مجموعه در حافظۀ آنها بارگذاری شود. سپس این حسگرها به‌صورت تصادفی در محیط پخش میشوند و هر کدام از اعضای بر مبنای قابلیت‌های محاسباتی خود با در نظر گرفتن مختصات اولیۀ خود به‌عنوان نقطۀ شروع و با استفاده از الگوریتم شدیدترین نزول مبتنی بر قاعده‌های آرمیجو و وولف نسبت به بروزرسانی مختصات خود تا قرارگرفتن در شعاع حسگری هدف مربوطه اقدام می‌کنند. تعمیم الگوریتم توزیع‌شده به پوشش‌دهی K- تایی و Q- تایی نیز همانند روش متمرکز است. درخور ذکر است مدل سیگنال حاکم بر الگوریتم متمرکز برداری است؛ چون در این حالت، مرکز پردازش مسئول محاسبات است و محاسبات بروزرسانی مختصات حسگرها در آن انجام می‌شود که برداری بعدی است؛ اما در الگوریتم توزیع‌شده این بردار به کمیت اسکالر شکسته می‌شود که هر کدام مربوط به یک حسگر است.
3-1- پوشش‌دهی نواحی با الگوریتم‌های تکاملیاین بخش دربارۀ مسئلۀ پوشش‌دهی نواحی است؛ بنابراین، فرض می‌شود؛ این بدان معنا است که تعداد حسگرهای دردسترس، بیشتر از تعداد مورد نیاز برای مسئلۀ پوشش‌دهی اهداف است. روند کار بدین صورت برنامه‌ریزی می‌شود که ابتدا از حسگر دردسترس، حسگر به مجموعه برای پوشش‌دهی اهداف تخصیص داده می‌شود و حسگر باقیمانده برای پوشش‌دهی نواحی منظور می‌شود. پس از این، الگوریتم مربوط به هر کدام از این چالش‌ها در راستای بیشینه‌سازی پوشش‌دهی مربوطه اقدام می‌کند. همان‌طور که پیش از این اشاره شد حل مسئلۀ پوشش‌دهی نواحی در وهلۀ نخست، در گرو دستیابی به چیدمان بهینۀ حسگرها است؛ بنابراین، در این بخش، الگوریتم‌های تکاملی وراثتی و جهش قورباغه‌ای به‌هم‌آمیخته برای بیشینه‌سازی پوشش‌دهی نواحی پیشنهاد میشوند. با توجه به اینکه پوشش‌دهی نواحی، معرف درصدی از ناحیۀ دوبعدی است که در شعاع حسگری گرههای شبکه قرار دارد، پوشش‌دهی نقطه در این ناحیه دو بعدی به‌صورت زیر مدل‌سازی می‌شود:
که در آن معرف پوشش‌دهی نقطه است و فاصلۀ اقلیدسی این نقطه از حسگر با شعاع حسگری است. درنهایت، نرخ پوشش‌دهی کل ناحیه ، ، که تابع برازش الگوریتم پوشش‌دهی نواحی محسوب می‌شود، برابر با ضریبی از مساحت این ناحیه است که با حسگرها پوشش داده شده است:
که و طول و عرض ناحیه دو بعدی هستند. شایان ذکر است الگوریتم بهینه‌سازی وراثتی از اصل انتخاب طبیعی الهام گرفته شده است که با شروع از یک جمعیت اولیه از جواب‌های مسئله، اصلاح آن بر مبنای عملگرهای انتخاب، نخبه‌پروری، ترکیب و جهش، و تکرار این روند تا رسیدن به پاسخ بهینه ادامه می‌یابد [31، 32]. به‌منظور ممانعت از همگرایی به بهینۀ محلی در برخی مسائل، الگوریتم‌های جدیدی نظیر الگوریتم جهش قورباغه‌ای به‌هم‌آمیخته ارائه شدهاند که از تکامل گروهی قورباغه‌ها در تعیین محل ذخیرۀ غذایی الهام گرفته شدهاند و از دو شیوۀ جستجوی محلی و به‌هم آمیختن اطلاعات در سیر تکاملی خود به‌منظور یافتن بهینۀ مطلق و ممانعت از همگرایی به بهینه‌های محلی بهره می‌گیرد [33، 34].
4- نتایج عددی و تحلیل عملکرد الگوریتم پیشنهادی این بخش به نتایج عددی و تحلیل عملکرد روش پیشنهادی برای پوشش‌دهی شبکۀ حسگر بی‌سیم در قالب دو زیربخش مجزا اختصاص دارد. زیربخش اول، به پوشش‌دهی اهداف معطوف است که در آن است؛ اما در زیربخش دوم فرض شده است و اثر چالش‌های پوشش‌دهی اهداف و نواحی با هم تحلیل می‌شود. شبکۀ آزمون مفروض یک شبکۀ پیوستۀ دوبعدی به ابعاد 400*400 متر متشکل از چهار هدف است و شبیه‌سازی‌های مربوطه با نرم‌افزار MATLAB پیاده‌سازی شدهاند. به‌منظور فراهم‌آوردن شرایط عادلانه، تمامی اجراهای نرم‌افزاری در یک دستگاه رایانه انجام شده است و شرایط اولیۀ یکسانی برای حالات مختلف منظور شده است. همچنین با توجه به پیوستگی فضای مسئلۀ پوشش‌دهی، از نسخۀ حقیقی الگوریتم‌های تکاملی وراثتی و جهش قورباغه‌ای به‌هم‌آمیخته در شبیه‌سازی‌ها استفاده شده است. پارامترهای تنظیمی الگوریتم‌های آرمیجو و وولف در شبیه‌سازی‌ها و هستند؛ این پارمترها به‌صورت تجربی و از [29، 30] استخراج شدهاند. تعداد اعضای جمعیت الگوریتم وراثتی برابر 40 فرض شده است و نرخ ترکیب و جهش آن نیز به‌ترتیب 0.9 و 0.1 است. ، تعداد اعضای جمعیت الگوریتم جهش قورباغه‌ای به‌هم‌آمیخته، به‌صورت معادل، برابر با 40 است که به 10 دسته (ممپلکس[13]) چهارتایی شکسته می‌شود و جستجوی محلی در هر ممپلکس پنج بار تکرار می‌شود.
4-1-نتایج عددی برای پوشش‌دهی اهداف این زیربخش به ارائۀ نتایج روش پیشنهادی شدیدترین نزول در پوشش‌دهی اهداف و مقایسۀ عملکرد آن با روش تکاملی مبتنی بر الگوریتم وراثتی در [22-20] اختصاص دارد. همچنین درخور ذکر است چون تفاوت رویکردهای متمرکز و توزیع‌شده به پیاده‌سازی عملی آنها معطوف است و در شبیه‌سازی آنها تفاوتی وجود ندارد، نتایج روش پیشنهادی صرف‌نظر از نوع رویکرد ارائه میشوند. نتایج حاصل از الگوریتم وراثتی نیز در هر دو حالت مختلف ارائه میشوند که در یک حالت، الگوریتم از عملگر نخبه‌پروری در تولید نسل‌های مختلف استفاده می‌کند و در حالت دوم، از استفاده از این عملگر صرف‌نظر می‌شود. در اینجا عملکرد الگوریتم‌های پیشنهادی و وراثتی از منظر دقت پوشش‌دهی و زمان اجرا یا همان پیچیدگی محاسباتی در دو سناریو ارزیابی و مقایسه می‌شود. در سناریوی اول فرض می‌شود چهار هدف در مختصات (1 و 1)، (1 و 400)، (400 و 1) و (400 و 400) واقع شدهاند و مطلوب پوشش‌دهی هر هدف فقط با یک حسگر به شعاع حسگری 50 متر در یک شبکه همگن است؛ بنابراین، درمجموع به حسگر نیاز است؛ اما در سناریوی دوم، این چهار هدف در مختصات (100 و 100)، (100 و 300)، (300 و 100) و (300 و 300) واقع شدهاند و مطلوب پوشش‌دهی آنها به‌ترتیب با 1، 2، 1 و 2 حسگر (پوشش‌دهی Q- تایی: کلی‌ترین حالت پوشش‌دهی اهداف) در یک شبکۀ ناهمگن است؛ بنابراین، در این سناریو به حسگر نیاز است که شعاع حسگری سه حسگر اول برابر با 80 متر و سه تای آخر 50 متر فرض می‌شود. برای اجرای الگوریتم در سناریوی اول و دوم به‌ترتیب چهار و شش حسگر به‌صورت تصادفی در ناحیۀ مفروض پخش میشوند و دو الگوریتم نسبت به پوشش‌دهی اهداف اقدام می‌کنند. همچنین از تابع برازش الگوریتم پوشش‌دهی اهداف یا همان متوسط فاصلۀ حسگرها از اهداف در رابطۀ (6) به‌عنوان معیار توقف الگوریتم‌ها استفاده شده است و اجرای هر الگوریتم در صورت دستیابی به متوسط فاصله پنج متر یا کمتر از آن متوقف می‌شود؛ اما اگر این معیار برآورده نشود، حداکثر تعداد تکرار، ملاک عمل قرار می‌گیرد و الگوریتم با رسیدن به 500 تکرار متوقف خواهد شد. نتایج حاصل برای سناریوهای اول و دوم به‌ترتیب در شکل‌های (1) و (2) ارائه شدهاند. در جدول (1) نیز به‌صورت کمی مقایسه شده است. نواحی تحت پوشش حسگرها در این شکل‌ها با رنگ سفید، مشخص و نقاط بدون پوشش با رنگ تیره نمایش داده شدهاند. قسمت‌های (الف) و (ب) این دو شکل به‌ترتیب نشان‌دهندۀ موقعیت اولیۀ اهداف و حسگرها و پوشش‌دهی اولیه قبل از اجرای الگوریتم‌اند. در قسمت‌های (د)، (ه) و (و) به‌ترتیب پوشش‌دهی نهایی حاصل از اجرای الگوریتم پیشنهادی شدیدترین نزول، الگوریتم وراثتی با عملگر نخبه‌پروری و الگوریتم وراثتی بدون نخبه‌پروری نمایش داده شده است. درنهایت، در قسمت (ج)، این دو شکل منحنی تابع برازش پوشش‌دهی اهداف (متوسط فاصلۀ اقلیدسی حسگرها از اهداف) در سه حالت فوق با یکدیگر مقایسه شدهاند. همچنین چون پوشش‌دهی نهایی الگوریتم شدیدترین با هر یک از قاعده‌های جستجوی خط آرمیجو و وولف کاملاً مشابه با دیگری است، نتایج در قسمت (د) این شکل‌ها صرف‌نظر از نوع قاعده خط ارائه شدهاند.
جدول (1): مقایسۀ نتایج الگوریتم پیشنهادی و الگوریتم وراثتی
با توجه به قسمت‌های (الف) و (ب) این شکل‌ها، پوشش‌دهی اولیه در هیچ‌یک از این دو سناریو مطلوب نیست و اهداف خارج از شعاع حسگری حسگرهای مربوطه قرار دارند؛ اما با اجرای برنامه، هر الگوریتم با جابه‌جایی حسگرها از موقعیت اولیه به مکان مطلوب‌تر نسبت به بهبود این شرایط اقدام می‌کند؛ جزئیات آن در موارد ذیل خلاصه میشوند:
درنهایت، به‌منظور تأیید کارایی الگوریتم شدیدترین نزول با قاعدۀ آرمیجو در محیط‌های واقعی‌تر و موفقیت آن در مدیریت حرکت حسگرها، عملکرد این الگوریتم برای سه حالت مختلف شبکه آزمون مفروض در شکل (3) ارزیابی شده است. ناحیۀ مفروض در حالت اول مشابه با سناریوی‌های قبل عاری از نویز و موانع فیزیکی فرض شده است. در حالت دوم، حسگرها غیردقیق و در معرض نویز هستند؛ بنابراین، محاسبات نمو آنها آغشته به نویز و حرکت آنها همراه با یک خطای تصادفی است. درنهایت، حالت سوم، یک ناحیۀ ممنوعه برای حرکت حسگرها در نظر گرفته شده که این ناحیه، در واقعیت شامل موانع فیزیکی مانند درختان، صخره‌ها و ... است. در اینجا این ناحیه با تابع جریمه رابطه (9) به‌صورت یک تابع باترورث تعریف شده است. هنگامی که حسگر بخواهد وارد این ناحیه شود، این تابع جریمه به تابع برازش رابطه (6) اضافه می‌شود و مقدار نهایی تابع برازش به‌شدت افزایش می‌یابد؛ بنابراین، انتظار می‌رود حسگر با تغییر مسیر حرکت در جهت شدیدترین نزول تابع برازش حاصل به سمت نقطۀ کمینه حرکت کند و مانع را دور بزند.
که دامنۀ تابع جریمه، شعاع ناحیۀ ممنوعه، فاصلۀ اقلیدسی حسگر ام از مرکز ناحیۀ ممنوعه (به مختصات ) و درجه تابع است. هرچه بزرگ‌تر باشد، تابع جریمه در مرز ناحیۀ ممنوعه شیب بیشتری خواهد داشت. در قسمت (و) شکل (3) شعاع ناحیۀ ممنوعه برابر با 50 متر فرض شده و مرکز آن با علامت ضربدر در مختصات (200و250) مشخص است. همچنین و فرض شدهاند. درخور ذکر است در شکل (3) حسگرها با و اهداف با مشخص شدهاند و مطلوب پوشش هدف ام توسط امین حسگر است. قسمت‌های (الف) و (ب) این شکل به‌ترتیب نشان‌دهندۀ موقعیت اولیۀ اهداف و حسگرها در سناریوی مفروض و پوشش‌دهی اولیه متناظر با آن قبل از اجرای الگوریتم هستند. در قسمت (ج) این شکل نیز پوشش‌دهی نهایی حاصل از اجرای الگوریتم پیشنهادی شدیدترین نزول در سه حالت یادشده ارائه شده است. همان‌طور که ملاحظه می‌شود این پوشش در هر سه حالت یکسان و کاملاً موفقیت‌آمیز است و تنها تفاوت آنها در رسیدن به این پوشش در زمان‌ها و تکرارهای متفاوت است؛ اما نکتۀ مهم دربارۀ مسیر حرکت حسگرها از مختصات تصادفی اولیه تا رسیدن به مختصات نهایی است. با توجه به قسمت‌های (د)، (ه) و (و) این شکل، با توجه به عاری‌بودن ناحیه از موانع و نویز در حالت اول، حسگرها و اهداف در مسیر دید مستقیم یکدیگرند؛ بنابراین، جهت حرکت تعیین‌شده با الگوریتم شدیدترین نیز در تمامی تکرارها یکسان و در راستای حداقل‌سازی فاصله (خط واصل بین اهداف و حسگرها) است و مسیر حرکت حسگرها خط مستقیم است؛ اما در حالت دوم، حسگرها به دلیل نویزی‌بودن محاسبات نمو در هر مرحله، از مسیر مستقیم منحرف میشوند؛ ولی با توجه به عملکرد الگوریتم شدیدترین نزول در جهت نزولی تابع فاصله، این انحراف به‌صورت متوالی اصلاح می‌شود و درنهایت، حسگرها در طی یک مسیر منحنی شکل به موقعیت مطلوب نهایی خود می‌رسند. جالب‌ترین اتفاق برای حالت سوم رخ می‌دهد که در آن حسگرهای شماره 3 و 4 در مسیر حرکت مستقیم خود به سمت اهداف مربوطه، هنگامی که به مانع می‌رسند، از این مسیر مستقیم منحرف میشوند و عملاً مانع را دور می‌زنند. این امر بدان دلیل است که ادامۀ مسیر مستقیم برای این حسگرها برابر با بالارفتن از مانع و به معنای افزایش تابع برازش یا همان فاصله از اهداف است؛ بنابراین، الگوریتم شدیدترین نزول بر مبنای ماهیت ذاتی خود با تغییر جهت حرکت حسگرها به‌منظور حداقل‌کردن تابع برازش، نسبت به دورزدن مانع اقدام می‌کند.
4-1- نتایج عددی برای پوشش‌دهی اهداف و نواحی این زیربخش به ارائۀ نتایج برای پوشش هم‌زمان اهداف و نواحی اختصاص دارد و با توجه به تأیید کارایی روش شدیدترین نزول در پوشش‌دهی اهداف، از این روش برای پوشش‌دهی اهداف استفاده می‌شود. همچنین، همان‌طور که پیش از این اشاره شد نخستین قدم در پوشش‌دهی نواحی، تعیین چیدمان بهینه برای حسگرهای توزیع تصادفی‌شده در ناحیۀ مدنظر با الگوریتم‌های تکاملی است؛ بنابراین، در اینجا یک سناریوی متشکل از چهار هدف به مختصات (1 و 1)، (1 و 400)، (400 و 1) و (400 و 400) و 14 عدد حسگر تصادفی با شعاع حسگری 50 متر فرض می‌شود. مطلوب این سناریو، پوشش این اهداف با روش شدیدترین نزول توسط چهار حسگر اول و استفاده از مابقی حسگرها برای دستیابی به چیدمان بهینه برای پوشش نواحی است. نتایج عملکردی این الگوریتم‌ها برای این سناریو در شکل (4) آورده شدهاند. قسمت‌های (الف) و (ب) این شکل به‌ترتیب نشان‌دهندۀ موقعیت اولیۀ اهداف و حسگرها، و پوشش‌دهی اولیه‌اند. قسمت‌های (ج) و (د) معرف توابع برازش پوشش‌دهی اهداف و نواحی‌اند و درنهایت، در قسمت‌های (و) و (ه) به‌ترتیب پوشش‌دهی نهایی حاصل از الگوریتم‌های وراثتی و جهش قورباغه‌ای به‌هم‌آمیخته نمایش داده شدهاند. همان‌طور که مشاهده می‌شود همانند شکل‌های قبلی، پوشش‌دهی اولیه، مطلوب نیست و نرخ پوشش نواحی (تابع برازش در قسمت (د) این شکل) نیز کمترین مقدار را دارد؛ اما با اجرای الگوریتم‌ها، پوشش لازم در اهداف با الگوریتم شدیدترین نزول تضمین می‌شود و ملاحظه می‌شود دو الگوریتم تکاملی به‌کاررفته برای دستیابی به چیدمان بهینه در مسئلۀ پوشش‌دهی نواحی نیز از قابلیت لازم برای دستیابی به این چیدمان برخوردارند و افزایش نرخ پوشش‌دهی نواحی در نتایج هر دو الگوریتم مشهود است؛ اما در مقایسۀ این دو الگوریتم با یکدیگر ملاحظه می‌شود پوشش‌دهی نهایی الگوریتم جهش قورباغه‌ای به‌هم‌آمیخته در قسمت (و) از پوشش الگوریتم وراثتی در قسمت (ه) مطلوب‌تر است و این امر از مقایسۀ مقادیر نهایی تابع برازش این دو در قسمت (د) شکل (4) نیز مشهود است. این بهبود به دلیل انجام جستجوی محلی در این الگوریتم است که البته افزایش زمان اجرای آن را در مقایسه با الگوریتم وراثتی به همراه دارد. درخور ذکر است در صورت نیازمندی به مدیریت حرکت حسگرها در این سناریو، الگوریتم شدیدترین نزول می‌تواند نسبت به هدایت حسگرها به این چیدمان اقدام کند که عملکرد آن در شکل‌های قبل به‌تفصیل بررسی شده است. در انتها گفتنی است با توجه به اینکه پیشنهاد استفاده از الگوریتم تحلیلی شدیدترین نزول برای نخستین‌بار در این پژوهش مطرح شده، این پیشنهاد و تمامی نتایج آن بخشی از نوآوری‌های این مقاله نسبت به مطالعات پیشین است؛ اما نتایج مقاله در حوزۀ الگوریتم وراثتی به نحوی بازتولید نتایج [20-22] هستند که در ادامه، تفاوت‌ها و شباهت‌های آنها نسبت به همدیگر تبیین میشوند. در [20، 21]، هدف استفاده از الگوریتم وراثتی برای دستیابی به چیدمان مطلوب ازطریق بیشینه‌سازی معیارهای پوشش‌دهی اهداف، پوشش‌دهی نواحی و ارتباط بوده است؛ اما در بخش نتایج عددی این مقالات به‌صراحت تاکید شده است قبل از اجرای الگوریتم وراثتی، حسگرهای مدنظر برای پوشش‌دهی اهداف در مختصات مدنظر جایگذاری شدهاند و این الگوریتم هیچ نقشی در آن ندارد. این درحالی است که در مقالۀ حاضر، علاوه بر الگوریتم شدیدترین نزول، پوشش‌دهی اهداف با الگوریتم وراثتی نیز به‌صورت عددی پیاده‌سازی شده است؛ اما در بخش پوشش‌دهی نواحی، با توجه به یکسان‌بودن تابع ارزیابی استفاده‌شده در مقالۀ حاضر و [20، 21]، نتایج مقالۀ حاضر بر مبنای الگوریتم وراثتی بازتولید نتایج [20، 21] هستند؛ البته در مقالۀ حاضر، پیاده‌سازی عددی با استفاده از الگوریتم پیشرفته‌تر جهش قورباغه‌ای به‌هم‌آمیخته به‌منظور بهبود نتایج نسبت به [20، 21] نیز مدنظر قرار گرفته است. درنهایت، در [22]، هدف دستیابی به چیدمانی از حسگرها به‌وسیلۀ الگوریتم وراثتی است که در آن، هر هدف، تحت پوشش حسگر (پوشش تایی) باشد و ارتباط هر حسگر نیز با حسگر دیگر برقرار باشد؛ بنابراین، بخشی از نتایج عددی مقالۀ حاضر که معطوف پوشش‌دهی اهداف با حسگر است، بازتولید نتایج [22] در پوشش تایی است. ضمن این نتایج، مقالۀ حاضر صرفاً به پوشش Kتایی معطوف نیست؛ بلکه سناریوی جامع‌تر پوشش‌دهی تایی در شبکه‌های همگن و ناهمگن را نیز شامل می‌شود
5- نتیجه‌گیری این مقاله به تحلیل هم‌زمان دو چالش پوشش‌دهی اهداف و نواحی در شبکه‌های حسگر بی‌سیم با پخش تصادفی اختصاص دارد که در آن، الگوریتم تحلیلی شدیدترین نزول مبتنی بر قاعده‌های آرمیجو و وولف برای حل مسئلۀ پوشش‌دهی اهداف پیشنهاد شد و برای دستیابی به مطلوب مسئلۀ پوشش‌دهی نواحی، از الگوریتم شدیدترین نزول در کنار الگوریتم‌های تکاملی وراثتی و جهش قورباغه‌ای به‌هم‌آمیخته استفاده شد. عملکرد این الگوریتم‌ها در سناریوهای مختلف یک شبکۀ آزمون به‌صورت عددی پیاده‌سازی و ارزیابی شد و نتایج بر قابلیت‌های منحصربه‌فرد الگوریتم شدیدترین نزول در کاهش پیچیدگی محاسباتی، افزایش دقت پوشش‌دهی و قابلیت مدیریت حرکت حسگرها در پوشش‌دهی اهداف صحه گذاشت. همچنین تأیید شد این الگوریتم در ترکیب با روش‌های تکاملی، عملکرد مطلوبی در مسئلۀ پوشش‌دهی دارد.
سپاسگزاری این پژوهش در قالب طرح پژوهشی شماره 2961/97 با استفاده از اعتبارات پژوهشی– پژوهشگاه علوم و تکنولوژی پیشرفته و علوم محیطی، دانشگاه تحصیلات تکمیلی صنعتی و فناوری پیشرفته، کرمان، ایران انجام شده است.
شکل (1): سناریوی اول، (الف): موقعیت اولیه اهداف (دایره) و حسگرها (ستاره)، (ب): پوشش‌دهی اولیه، (ج): مقایسۀ منحنی تابع برازش برای الگوریتم‌های مختلف، (د)، (ه) و (و): به‌ترتیب پوشش‌دهی نهایی الگوریتم‌های شدیدترین نزول با قاعده‌های آرمیجو و وولف، وراثتی با عملگر نخبه‌پروری و وراثتی بدون نخبه‌پروری.
شکل (2): سناریوی دوم، (الف): موقعیت اولیۀ اهداف (دایره) و حسگرها (ستاره)، (ب): پوشش‌دهی اولیه، (ج): مقایسۀ منحنی تابع برازش برای الگوریتم‌های مختلف، (د)، (ه) و (و): به‌ترتیب پوشش‌دهی نهایی الگوریتم‌های شدیدترین نزول با قاعده‌های آرمیجو و وولف، وراثتی با عملگر نخبه‌پروری و وراثتی بدون نخبه‌پروری.
شکل (3): (الف): موقعیت اولیۀ اهداف (دایره) و حسگرها (ستاره)، (ب): پوشش‌دهی اولیه، (ج): پوشش‌دهی نهایی حالت‌های مفروض، (د)، (ه) و (و): به‌ترتیب ترسیم مسیر حرکت حسگرها برای حالت ایدئال عاری از موانع و نویز، حالت دوم مبتنی بر نویز و حالت سوم در حضور مانع فیزیکی.
شکل (4): (الف): موقعیت اولیۀ اهداف (دایره) و حسگرها (ستاره)، (ب): پوشش‌دهی اولیه، (ج) و (د) منحنی برازش پوشش‌دهی اهداف و نواحی، (ه) و (و): به‌ترتیب پوشش‌دهی نهایی الگوریتم‌های وراثتی و جهش قورباغه‌ای به‌هم‌آمیخته [1] تاریخ ارسال مقاله: 15/02/1399 تاریخ پذیرش مقاله: 28/08/1399 نام نویسندۀ مسئول: محسن شیخ حسینی نشانی نویسندۀ مسئول: ایران – کرمان – دانشگاه تحصیلات تکمیلی صنعتی و فناوری پیشرفته – گروه پژوهشی کامپیوتر و فناوری اطلاعات | |||||||||||||||||||||||||||||||||||||||||||||||||||
| مراجع | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
[1] M. Tubaishat and S. Madria, “Sensor networks: an overview,” IEEE Potentials, vol. 22, no. 2, pp. 20-23, 2003. [2] M. Honarmand, A. Ghiasian and H. Saidi, “Design of an energy aware clustering scheme based on genetic algorithm in heterogeneous wireless sensor networks”, Computational Intelligence in Electrical Engineering, vol. 6, no. 3, pp. 0-16, 2015. [3] A. Ali, et. al., “A comprehensive survey on real-time applications of WSN” Future Internet, vol. 9, no.4, 2017. [4] J. Yick, B. Mukherjee, and D. Ghosal, “Wireless sensor network survey,” Computer networks, vol. 52, no. 12, pp. 2292–2330, 2008. [5] D. Culler, D. Estrin, and M. Srivastava, “Overview of wireless sensor networks,” IEEE Computer, vol. 38, no. 8, pp. 41-49, 2004. [6] M. Salkhordeh Haghighi, P. Aminsharie Najafi, “Improving the performance of three dimensional wireless sensor networks with nodes displacement capability”, Computational Intelligence in Electrical Engineering, vol. 11, no. 3, pp. 65-82, 2020. [7] S. Abdollahzadeh, and N. J. Navimipour, “Deployment strategies in the wireless sensor network: A comprehensive review,” Comput. Communications, vol. 91–92, pp. 1–16, 2016. [8] F. Aznoli, and N. J. Navimipour, “Deployment strategies in the wireless sensor networks: systematic literature review, classification, and current trends,” Wirel. Pers. Commun, vol. 95, no. 2, pp. 819–846, 2017. [9] B. Wang, “Coverage problems in sensor networks: A survey,” ACM Computing Surveys (CSUR), vol. 43, no. 4, 2011. [10] M. Esnaashari, and M. R. Meybodi, “Dynamic point coverage problem in wireless sensor networks: a cellular learning automata Approach,” Ad Hoc & Sensor Wireless Networks, vol. 10, no. 2, pp. 193-234, 2010. [11] M. Karatas, “Optimal deployment of heterogeneous sensor networks for a hybrid point and barrier coverage application,” Computer Networks, vol. 132, pp. 129-144, 2018. [12] P. M. Pradhan and G. Panda, “Connectivity constrained wireless sensor deployment using multiobjective evolutionary algorithms and fuzzy decision making,” Ad Hoc Networks, vol.10, pp.1134–1145, 2012. [13] M. Farsi, et. al., “Deployment Techniques in Wireless Sensor Networks, Coverage and Connectivity: A Survey,” IEEE Access 7, pp. 28940–28954, 2019. [14] K. Mougou, et. al., “Redeployment of randomly deployed wireless mobile sensor nodes,” VTC Fall, IEEE, 2012, pp. 1-5. [15] J. Li, et. al., “An extended virtual force-based approach to distributed self-deployment in mobile sensor networks,” Int. J. Distrib. Sensor Netw., vol. 8, no. 3, Art. no. 417307, 2012. [16] M. Maksimovic, “Evaluating the optimal sensor placement for smoke detection,” Yugoslav J. Oper. Res., vol. 26, no. 1, pp. 33-50, 2016. [17] Y. Liu, et. al., “A virtual square grid-based coverage algorithm of redundant node for wireless sensor network,” J. Netw. Comput. Appl., vol. 36, no. 2, pp. 811-817, 2013. [18] S. Fortune, “Voronoi diagrams and delaunay triangulations,” in Computing in Euclidean Geometry, 1995, pp. 225-265. [19] T.-W. Sung and C.-S. Yang, “Voronoi-based coverage improvement approach for wireless directional sensor networks,” J. Netw. Comput. Appl., vol. 39, pp. 202-213, 2014. [20] T. E. Kalayci, K. S. Yildirim, and A. Ugur, “Maximizing Coverage in a Connected and K-Covered Wireless Sensor Network Using Genetic Algorithms,” International Journal of Applied Mathematics and Informatics, vol. 1, no. 3, pp. 123-130, 2007. [21] K. S. Yildirim, T. E. Kalayci, and A. Ugur, “Optimizing Coverage in a K-Covered and Connected Sensor Network Using Genetic Algorithms,” In Proc. 9th WSEAS international conference on evolutionary computing, 2008. [22] S.-K. Gupta, P. Kuila, and P. K. Jana, “Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks,” Comput. Elect. Eng., vol. 56, pp. 544-556, 2016. [23] Y. El Khamlichi, et. al., “A hybrid algorithm for optimal wireless sensor network deployment with the minimum number of sensor nodes,” Algorithms, vol. 10, no. 3, 2017. [24] B. Cao, et. al., “Deployment optimization for 3D industrial wireless sensor networks based on particle swarm optimizers with distributed parallelism,” J. Netw. Comput. Appl., vol. 103, pp. 225-238, 2018. [25] H. Mostafaei, et. al., “A sleep scheduling approach based on learning automata for WSN partialcoverage,” J. Netw. Comput. Appl., vol. 80, pp. 67-78, 2017. [26] W. Osamy, et. al., “Sensor network node scheduling for preserving coverage of wireless multimedia networks,” IET Wireless Sensor Systems, vol. 9, no. 5, pp. 295-305, 2019. [27] J. Nocedal, S. J. Wright, Numerical Optimization; Springer Verlag: New York, NY, USA, 2006. [28] W.Y. Sun, Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer-Verlag, New York, 2006. [29] M. Ahookhosh, S. Ghaderi, “On efficiency of nonmonotone Armijo-type line searches”, Appl. Math. Model. Vol. 43, pp. 170–190, 2017. [30] M. Kim, S. Kwon, S. Oh, “The Performance of A Modified Armijo Line Search Rule in BFGS Optimization Method”, J. Chungcheong Math. Soc. Vol. 21, pp. 117-127, 200. [31] R. L. Haupt, S. E. Haupt, “Practical Genetic Algorithms”, Wiley, 2004. [32] M. Sharifiasn, H. Karshenas, S. Sharifiasn . “Improving Network Intrusion Detection by Identifying Effective Features using Evolutionary Algorithms based on Support Vector Machine”, Computational Intelligence in Electrical Engineering. vol. 11, no. 1, pp. 29-42, 2020. [33] T. H. Huynh, “A Modified Shuffled Frog Leaping Algorithm for. Optimal Tuning of Multivariable PID Controllers”, Proc. IEEE Int. Conf. on Industrial Technol. 2008, pp. 1-6. [34] M. Jadidoleslam, A. Bijami, A. Ebrahimi , “Generation Expansion Planning by a Modified SFL Algorithm”, Computational Intelligence in Electrical Engineering. vol. 2, no. 1, pp. 27-44, 2013. | |||||||||||||||||||||||||||||||||||||||||||||||||||
|
آمار تعداد مشاهده مقاله: 807 تعداد دریافت فایل اصل مقاله: 375 |
|||||||||||||||||||||||||||||||||||||||||||||||||||