چهارشنبه 28 شهریور 1397 | Wednesday 19 th of September 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
2-7-10-1-1تقسیم بندی دوم

در بیشتر مقالاتی که درمورد مساله پوشش کار شده از این دسته بندی برای معرفی روش خود استفاده کرده‌اند. این دسته بندی برمبنای چگونگی پوشش به سه گروه تقسیم شده، که عبارتند از 1- پوشش مرزی، 2- پوشش ناحیه‌ای[1] و 3- پوشش نقطه‌ای[2].[4]در ادامه برای هرکدام از این دسته بندیها چند مرجع ارائه می‌گردد.

1- پوشش مرزی

در مقالات به این نوع از پوششها نسبت به دیگر پوششها کمتر پرداخته شده است. یکی از این تحقیقات که در مرجع [34]به ان اشاره شده، مقاله‌ای است که فرض کرده ناحیه‌ای موجود است که در ان گره‌های حسگر پراکنده شده است. برای این ناحیه یک نقطه ورود و یک نقطه خروج درنظر گرفته شده است و هدف این مقاله پیدا کردن دو مسیر از مبدا به مقصد می‌باشد به گونه‌ای که در یکی از این مسیرها احتمال دیده شدن و شناسایی شدن کمترین میزان و در مسیر دیگر بیشترین میزان باشد. منظور از این مسیرها ، بهترین و بدترین راه نفوذ به محیط تحت پوشش می‌باشد. مسیری برای نفوذ مناسبتر است که هرنقطه از ان، از تمام حسگرها دور باشد و یا در محدوده غیرقابل پوششی قرار داشته باشد. نویسنده این مساله را با استفاده از دیاگرام وِرونوی[3]برای پیدا کردن مسیر با پوشش حداقل و از مثلث‌بندی دِلانی[4]برای پیداکردن مسیری با بیشترین پوشش استفاده کرده است.

یکی دیگر از انواع پوشش مرزی، مدلهایی برپایه اشکارسازی[5] می‌باشد که در مرجع [35]ارائه شده است. این مدلها بر این فرض استوار هستند که با افزایش فاصله، از دقت ناحیه حسی گره‌ها کاسته می‌شود و احتمال اینکه یک هدف را نتواند کشف کند افزایش پیدا می‌کند. هدف در اینگونه از مسائل پیدا‌ کردن یک مسیر بین مبدا و مقصد می‌باشد که دارای کمترین میزان دید توسط حسگرهاست. یعنی احتمال کشف یک هدف بر روی این مسیر کمترین است.

2- پوشش ناحیه‌ای

بیشتر تحقیقات انجام شده در مورد مساله پوشش، مربوط به پوشش ناحیه‌ای می‌باشد. هدف اصلی شبکه‌های حسگر در این نوع پوشش، پوشش دادن و نظارت کردن کامل یک محیط می‌باشد. البته در بعضی از مقالات مناطق بزرگ و جدا ازهم، نیز مشمول این تقسیم‌بندی شده است. به علت اینکه در اکثر موارد تعداد گره‌های موجود در محیط برای عمل پوشش بیش از تعداد مورد نیاز می‌باشد، می‌توان این گره‌ها را در درون مجموعه‌هایی جدا از هم دسته‌بندی کرد، به گونه‌ای که هردسته توانایی پوشش کامل ناحیه را داشته باشد. به این صورت گره‌هایی که عضو مجموعه انتخاب شده نیستند می‌توانند به خواب بروند. هدف اصلی بیشتر این تحقیقات بدست اوردن بیشترین زیرمجموعه از این گره‌ها می‌باشد.

در مقاله [27]یک روش مربوط به پوشش ناحیه‌ای ارائه شده است. در این مقاله ابتدا مجموعه‌های جدا از هم به صورت یکسری مجموعه غالب[6] در یک گراف غیرجهتدار مدل می‌شوند. در این گراف، حسگرها رئوس گراف را نشان داده و یال‌ها وجود قرارگیری دو حسگر در شعاع حسی یکدیگر را نشان می‌دهند. همچنین نشان داده شده است که محاسبه حداکثر تعداد مجموعه‌های غالب یک مساله، NP-completeمی‌باشد. در این مقاله همچنین برای پیدا کردن مجموعه‌های غالب از روش رنگبندی[7] گراف استفاده شده است.

در مرجع [7]روشی بیان شده است که تنها نشان می‌دهد که ایا هر نقطه در محیط تحت پوشش، حداقل توسط یک حسگر پوشش داده می‌شود یا خیر. در این روش مباحث مربوط به زمان‌بندی برای کاهش مصرف انرژی و برقراری اتصال در شبکه بررسی نشده است. همچنین ناحیه حسی به صورت یک دایره فرض شده است و روش کار ان به این صورت است که، هرگره بررسی می‌کند که ایا تمام نقاط پیرامونی[8] ناحیه حسی ان توسط Kحسگر پوشش داده می‌شود یا نه. سپس در مقاله اثبات می‌شود که در صورتی یک محیط دارای پوشش درجه Kمی‌شود که فقط و فقط تمام گره‌ها در ان دارای پوشش پیرامونی از درجه Kباشند. این مقاله این روش را در دوحالت شعاع حسی یکنواخت و متغیر توضیح داده است.

در مرجع [8]روشی ارائه شده است که بر مبنای روش قبلی است، با این تفاوت که در این روش اتصال نیز همراه با پوشش درنظر گرفته شده است. این روش این توانایی را دارا می‌باشد که دوحالت پوشش و اتصال Kتایی و همچنین پوشش Kتایی و اتصال درجه 1 را تضمین کند. در این مساله هیچ فرضی درمورد رابطه بین شعاع ارتباطی و حسی بیان نشده است. این روش بر اساس تعاریفی چون پوشش پیرامونی مستقیم این مساله را به صورت متمرکز حل می‌نماید.

همان طور که قبلا بیان شد، روشهایی مثل CCP[3]و OGDC[19]را به دلیل انجام عمل پوشش در کنار عمل زمان بندی می‌توان در این گروه دسته بندی کرد.

3- پوشش نقطه‌ای

در این گروه هدف تنها پوشش نقاط خاصی از محیط می‌باشد و این نقاط در سطح محیط پراکنده‌اند. در ظاهر می‌توان گفت که این روش زیرمجموعه‌ای از روش پوشش ناحیه‌ای می‌باشد و اگر ما کل ناحیه را پوشش دهیم به طور ضمنی ان نقاط را هم پوشش داده‌ایم. ولی این فرض اشتباه می‌باشد و دلیل انهم این است که، هدف اصلی در شبکه‌های حسگر کاهش مصرف انرژی و افزایش طول عمر شبکه می‌باشد.

بنابر این پوشش مناطقی که برای ما کاربردی ندارند اشتباه است. در تمام این روشها نقاط مورد نظر از قبل مشخص هستند و مکان انها معلوم است و به انها هدف گفته می‌شود. مانند روشهای پوشش ناحیه‌ای، در این روشها هم هدف پیداکردن حداکثر زیرمجموعه‌های حسگر جدا از هم می‌باشد که هرکدام به تنهایی قادر باشند اهداف مورد نظر را پوشش دهند.

در مقاله [25]توضیح داده شده است که یکسری از اهداف به طور پراکنده در محیط موجود می‌باشد و بیش از تعداد مورد نیاز حسگر برای این کار وجود دارد. در این مقاله مجموعه‌ حسگرهای مستقل از همِ ، به صورت مجموعه‌های پوششی مجزا مدل شده است و بعد از ان اثبات شده که مساله پیدا کردن حداکثر مقدار ممکن از این مجموعه‌ها یک مساله NP-completeمی‌باشد.

در مقاله [26]نشان داده شده است که وجود شرط مستقل بودن مجموعه‌های پوششی هیچ تاثیری در بهبود میزان طول عمر شبکه ندارد و سپس اثبات کرده است که با وجود اشتراک در مجموعه‌های پوششی باز مساله پیدا کردن حداکثر مقدار ممکن از این مجموعه‌ها، یک مساله  NP-completeمی‌باشد



[1] Area Coverage

[2] Point Coverage

[3] Voronoi Diagram(The basic Voronoi diagram describes the areas that are nearest to a set of given points)

[4] Delaunay Triangulation

[5] Exposure

[6] Dominating set

[7] Graph-Coloring

[8] Perimeter Covered

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26