بر مبنای این تقسیم بندی کل روش های پوشش در سه گروه زیر دسته بندی میگردند و هر دسته بر مبنای یکی از کاربردهایش نامگذاری شده است. این گروهها عبارتند از:
۱- مسئله گالری هنر[۵] ]۳ [و ]۴[، ۲- پوشش اقیانوس[۶] ]۳ [و ]۵[، ۳- پوشش سیستم های روبوتیک[۷] ]۳[، ]۶[، ]۷[ و ]۸[.
مسئله گالری هنر:
در این مسئله فرض شده است که یک محیطی، مثل یک گالری وجود دارد و هدف این است که تمام محیط این گالری توسط حسگرهایی پوشش داده شود به گونهای که هر نقطه از این گالری حداقل توسط یکی از این حسگرها پوشش داده شده باشد به صورتی که اگر این حسگرها دوربین فرض شوند، این گالری باید در مقابل سرقت، ایمن باشد و همچنین برای این کار میبایست حداقل گره حسگر مصرف گردد. مسئله ی گالری هنر یکی از مسائل کار آمدی است که در شاخه ی هندسه محاسباتی قرار دارد. انگیزه ی اصلی برای حل این مشکل، حل مشکلی در موزهها بود به این ترتیب که لازم بود از حداقل تعداد دوربینهای امنیتی که قابلیت چرخش را دارند برای پوشش دادن کل فضای موزهها یا نگارخانههای هنری استفاده کرد. اثبات شده است که برای محیط های دوبعدی تعیین مکان و تعداد حسگرها از لحاظ زمانی خطی است ولی برای حالات سه بعدی یک مساله NP-hard میباشد ]۳[ و ]۴[.
( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
پوشش اقیانوس:
در این نوع از مسائل بیان شده که برای مثال در صورتی که بخواهیم موجودات دریایی را تحت بررسی قرار دهیم و بخواهیم این کار را از طریق ماهوارهها انجام دهیم، به دلیل اینکه یک ماهواره بر اثر عواملی نمیتواند بیش از ۱۵% سطح اقیانوسها را در روز پوشش دهد، چند ماهواره برای این کار لازم است تا میزان پوشش افزایش یافته و از پوشش نقاط مشترک خودداری گردد]۳[ و ]۵[.
پوشش سیستم های روبوتیک:
این نوع پوشش برای اولین بار توسط شخصی به نام Gage مطرح شد و انواع پوشش ها را از دید سیستم های روبوتیک مطرح کرد. او سه نوع پوشش را بیان کرد که عبارتند از پوشش پوشاننده[۸] ]۳[ و ]۷[، پوشش مرزی (مانع)[۹] ]۳[ و ]۸[ و پوشش جاروبی[۱۰] ]۳[ و ]۹[. در پوشش پوشاننده هدف تعیین دقیق مکان حسگرهاست، به گونهای که حداکثر پوشش را برای یک ناحیه ایجاد کنند. در پوشش مرزی (مانع)، هدف قرارگیری یکسری حسگر در محیط است به گونهای که نواحی پوشش داده نشده بر اثر وجود موانع در محیط به حداقل برسد و پوشش جاروبی کم و بیش شبیه به پوشش مرزی (مانع) میباشد، با این فرض که موانع در آن متحرک میباشند]۳[، ]۶[، ]۷[ و ]۸[.
۲-۳) تقسیم بندی دوم انواع پوشش:
در بیشتر مقالاتی که درمورد مساله پوشش کار شده از این دسته بندی برای معرفی روش خود استفاده کردهاند. این دسته بندی بر مبنای چگونگی پوشش به سه گروه تقسیم شده، که عبارتند از:
۱- پوشش مرزی[۱۱] ]۳[ و ]۱۰[ ، ۲- پوشش ناحیهای[۱۲] ]۳[ و ]۱۰[ و ۳- پوشش نقطهای[۱۳] ]۳[، ]۶[، ]۷[ و ]۱۱[.
پوشش مرزی:
اگر ناحیه ای داشته باشیم که گره های حسگر در آن پراکنده شده باشند و برای این ناحیه یک نقطه ورود و یک نقطه خروج درنظر گرفته باشیم، هدف پیدا کردن دو مسیر از مبدا به مقصد میباشد به گونهای که در یکی از این مسیرها احتمال دیده شدن و شناسایی شدن کمترین میزان و در مسیر دیگر بیشترین میزان باشد. منظور از این مسیرها، بهترین و بدترین راه نفوذ به محیط تحت پوشش میباشد. مسیری برای نفوذ مناسب تر است که هرنقطه از آن، از تمام حسگرها دور باشد و یا در محدوده ی غیرقابل پوششی قرار داشته باشد. این مسئله با بهره گرفتن از دیاگرام وارونی[۱۴] برای پیدا کردن مسیر با پوشش حداقل و از مثلثبندی دِلانی[۱۵] برای پیداکردن مسیری با بیشترین پوشش حل می شود ]۹[.
یکی دیگر از انواع پوشش مرزی، مدل هایی برپایه آشکارسازی میباشد. این مدل ها بر این فرض استوار هستند که ناحیه حسی گرهها با افزایش فاصله از دقتش کاسته میشود و احتمال اینکه یک هدف را نتواند کشف کند افزایش پیدا میکند. هدف در اینگونه از مسائل پیدا کردن یک مسیر بین مبدا و مقصد میباشد که دارای کمترین میزان دید توسط حسگرهاست، یعنی احتمال کشف یک هدف بر روی این مسیر کمترین است ]۱۰[.
شکل ۲-۱: پوشش مرزی ]۳[
پوشش مرزی به تعداد خیلی کمتری از پوشش کامل ناحیه به حسگر نیاز دارد. این مدل از پوشش یک مدل مناسب برای کاربردهای تشخیص تجاوز (نفوذ) میباشد. در این نوع مدل پوشش نیازمندیم که عملیات پوشش را طوری انجام دهیم که اگر نفوذی از عرض ناحیه تحت پوشش صورت گیرد آن را بتوانیم تشخیص دهیم ]۱۲[.
برخی از کاربردهای مهم شبکه های حسگر با تشخیص حرکت درگیر هستند، مانند زمانی که حسگرها در طول مرزهای کشوری پخش می شوند تا نفوذ های غیرقانونی را تشخیص دهند. در هر لحظه، هر یک از هدف ها توسط حداقل یک حسگر تحت کنترل قرار میگیرد و هر حسگر قادر است تمامی اهداف موجود در محدوده حسگریاش را کنترل کند ]۱۲[.
در شکل ۲-۲ چگونگی آرایش گره های حسگر برای شناسایی گره های متجاوز را مشاهده می کنیم.
شکل ۲-۲: پوشش مرزی (مانع) برای شناسایی گره های متجاوز ]۱۲[
همان طور که در شکل ۲-۲ دیده می شود، نحوه ی چینش حسگرها باید به نحوه ای باشد که هیچ حفره ی پوششی در شبکه نداشته باشیم تا هیچ متجاوزی بدون اینکه شناسایی شود، نتواند از زنجیره ی گره های حسی عبور کند ]۱۲[.
پوشش ناحیهای:
بیشتر تحقیقات انجام شده در مورد مساله پوشش، مربوط به پوشش ناحیهای میباشد. هدف اصلی شبکههای حسگر در این نوع پوشش، پوشش دادن و نظارت کردن کامل یک محیط میباشد. البته در بعضی از مقالات مناطق بزرگ و جدا ازهم، هم مشمول این تقسیمبندی شده است. به علت اینکه در اکثر موارد تعداد گرههای موجود در محیط برای عمل پوشش بیش از تعداد مورد نیاز میباشد، میتوان این گرهها را در درون مجموعههایی جدا از هم دستهبندی کرد، به گونهای که هردسته توانایی پوشش کامل ناحیه را داشته باشد. به این صورت گرههایی که عضو مجموعه انتخاب شده نیستند میتوانند به خواب بروند. هدف اصلی بیشتر این تحقیقات بدست آوردن بیشترین زیرمجموعه از این گرهها میباشد]۳[ و ]۱۰[.
شکل ۲-۳: پوشش ناحیه ای ]۳[
پوشش نقطهای:
در این گروه هدف تنها پوشش نقاط خاصی از محیط میباشد و این نقاط در سطح محیط پراکندهاند. در ظاهر میتوان گفت که این روش زیرمجموعهای از روش پوشش ناحیهای میباشد و اگر ما کل ناحیه را پوشش دهیم به طور ضمنی آن نقاط را هم پوشش دادهایم. ولی این فرض اشتباه میباشد و دلیل آن هم این است که هدف اصلی در شبکههای حسگر کاهش مصرف انرژی و افزایش طول عمر شبکه میباشد. بنابر این پوشش مناطقی که برای ما کاربردی ندارند یک کار اشتباه میباشد. در تمام این روش ها نقاط مورد نظر از قبل مشخص هستند و مکان آن ها معلوم است و به آن ها هدف گفته میشود. مانند روش های پوشش ناحیهای، در این روش ها هم هدف پیداکردن حداکثر زیرمجموعههای جدا از هم حسگر میباشد که هرکدام به تنهایی قادر باشند اهداف مورد نظر را پوشش دهند ]۳[، ]۶[، ]۷[ و ]۱۱[.
در این روش تعدادی از اهداف با جایگاه مشخص که باید مورد کنترل قرار گیرند، در نظر گرفته می شوند. تعداد متوسطی از حسگرها به صورت تصادفی در نزدیکی اهداف پخش می شوند تا بر طبق زمانبندیهای خاص نسبت به انجام وظایف و تشخیص اهداف از پیش تعیین شده فعال گردیده و اطلاعات به دست آمده را به گره پردازشگر مرکزی بفرستند ]۳[، ]۶[، ]۷[ و ]۱۱[.
شکل ۲-۴: پوشش نقطه ای ]۳[
۲-۴) شبکه ی متصل[۱۶]:
تا به اینجا با مفهوم کلی پوشش آشنا شدیم. حال به این نکته می رسیم که آیا فقط پوشش کامل، مفهوم مناسبی برای یک شبکه ی حسگر بی سیم است یا این که شبکه باید دارای فاکتور دیگری هم باشد تا وقتی از این پوشش برخوردار شد، بتواند داده های محیطی را انتقال دهد؟ جواب مثبت است. زیرا یک شبکه باید شبکه ای متصل از نظر شعاع مخابراتی باشد. مفهوم پوشش که تا اینجای کار بررسی شد، به مفهوم مشاهده ی محیط از نظر شعاع حسی بود. اما گره ها اطلاعاتی را که از محیط به دست می آورند باید به مقصد منتقل کنند که این امر منوط به این است که گره ها با هم تبادل اطلاعات داشته باشند و گره یا گروهی از گره ها خارج از شبکه نباشد. اکنون لازم است که مفهوم شبکه ی متصل را بیان کنیم.
۲-۴-۱) شعاع های حسی و مخابراتی گره های حسگر:
هر گره ی حسگر دارای دو شعاع حسی[۱۷] (RS) و شعاع مخابراتی[۱۸] (RC) می باشد . این دو شعاع الزاما با هم برابر نیستند و همچنین این دو شعاع به صورت همگن نیز نمی باشند اما در اکثر مقالات برای سادگی محاسبات این دو شعاع را همگن در نظر می گیرند.
شکل ۲-۵: انواع شعاع های حسی و مخابراتی گره های حسگر
هر گاه دو گره در وضعیتی باشند که شعاع های مخابراتیشان بزرگتر از فاصله ی بین این دو گره باشد، این دو گره را متصل به هم گوییم و به همین ترتیب این مقوله را می توان به گره های دیگر تعمیم داد.
شکل ۲-۶: نمونه ای از دو گره ی متصل به هم
لازم به ذکر است که دلیلی ندارد تمام گره ها در محدوده ی شعاع مخابراتی یکدیگر باشند تا یک شبکه ی متصل داشته باشیم بلکه کافیست گره ها از طریق گره های رله، مسیری به سمت گره های دیگر پیدا کنند. در این صورت است که شبکه را متصل می گوییم و می توانیم داده هایی که از محیط توسط حسگر ها دریافت می شود را به سمت مقصد هدایت کنیم. توجه باید کرد که موارد سنجش شده باید مسیریابی شوند تا به مقصد برسند. نوع مسیریابی انجام شده با توجه به موضوع این پایان نامه در این مبحث نمی گنجد اما با توجه به انواع شبکه های حسگر بی سیم از نوع استاتیکی و دینامیکی فرق می کند به صورتی که در شبکه های استاتیکی مسیریابی ثابت است اما در شبکه های دینامیکی مانند شبکه های اقتضایی موبایل و خودرویی، این مسیریابی به صورت دینامیکی انجام می شود ]۱۳[.
برای نشان دادن مفهوم اتصال فرض می کنیم ناحیه ای به مساحت m2 ۱۰۰۰*۱۰۰۰ داریم. ۵۰ گره با شعاع مخابراتی m 150 داریم که به صورت تصادفی در محیط پخش شده اند. شکل منتج شده به صورت زیر در می آید.
شکل ۲-۷: یک شبکه ی حسگر بی سیم غیر متصل با ۵۰ گره و شعاع مخابراتی m 150
حال اگر فرض کنیم همین تعداد گره داریم اما با شعاع مخابراتی m 400 .
شکل ۲-۸: یک شبکه ی حسگر بی سیم متصل با ۵۰ گره و شعاع مخابراتی m 400
راه دیگر برای داشتن یک شبکه ی متصل این است که بدون اینکه شعاع های مخابراتی را زیاد کنیم، تعداد گره های حسگر را زیاد کنیم.
شکل ۲-۹: یک شبکه ی حسگر بی سیم متصل با ۲۵۰ گره و شعاع مخابراتی m 150
گره هایی که مستقیما با هم ارتباط مخابراتی ندارند، از طریق گره های دیگر که نقش رله را دارند می توانند با هم ارتباط برقرار کنند. بهترین روش برای داشتن یک شبکه متصل، یافتن الگوریتمی بهینه برای تعداد گره ها و شعاع مخابراتی و همچنین نحوه ی استقرار گره ها با توجه به توان شبکه است. لازم به یادآوری است هر شبکه ای که میخواهد هر کدام از پوشش های توضیح داده شده در این فصل را داشته باشد باید فضای مورد نظر را توسط شعاع حسی (RS) خودش بپوشاند. با این توضیحات تفاوت کلی مفاهیم پوشش و اتصال در شبکه های حسگر بی سیم را متوجه شدیم.
نکته ی دیگری که در مبحث پوشش پیش می آید، حفره ی پوشش است. به این معنی که در آن مناطق ما پوشش نداریم (شعاع حسی حسگرها در آن مناطق برد لازم را ندارد و ما با عدم پوشش همراه هستیم.). این امر می تواند بنا به دلایل زیست محیطی، عدم استقرار مناسب حسگرهای استاتیکی، عدم حرکت مناسب حسگرهای دینامیکی و امثال آن ها باشد. الگوریتم های مورد نظر برای استقرار یا حرکت حسگرها باید به گونه ای انجام شوند که این حفره ها را به حداقل برسانیم و در صورت امکان تعدادشان را به صفر برسانیم ]۱۳[.
در شکل ۲-۱۰ حفره های پوششی با علامت ضربدر مشخص شده است.
شکل ۲-۱۰: حفره ی پوشش
