بخشی از مقاله
چکیده
شبکه حسگر بیسیم مجموعهای از تعداد بسیار زیادی گره حسگر با ابعاد کوچک و قابلیتهای مخابراتی و محاسباتی محدود است که به منظور جمعآوری و انتقال اطلاعات از یک محیط به سمت یک کاربر و یا ایستگاه پایه بهکاربرده میشوداساساً. پوشش، تعیینکنندهی کیفیت مشاهدهی پدیده - محیط یا هدف - میباشد . مسالهی پوشش در شبکههای حسگر بیسیم به انواع مختلفی تقسیم می شود که از آن جمله می توان به پوشش سطح ، پوشش مانع و نیز پوشش هدف، اشاره کرد. با توجه به نیاز موجود میتوان هر یک از آنها را در حل مساله بکار بست . با استفادهی درست از الگوریتمهای پوشش میتوان به افزایش طول عمر شبکههای حسگر بیسیم و در نتیجهی آن به کاهش هزینه ها دست یافت .
کلمات کلیدی: شبکه های حسگر بی سیم، انواع پوشش، پوشش سطح، پوشش هدف، پوشش مانع.
– 1 مقدمه
شبکه حسگر بیسیم، یک نامگذاری عمومی برای انواع شبکههای مختلفی است که به منظورهای خاص طراحی میشوند. برخلاف شبکههای سنتی که همهمنظورهاند، شبکههای حسگر، تک منظورهاند. منظور از "تک منظوره" بودن این شبکهها آن است که نیازمندیها و شرایط طراحی یک شبکه حسگر بیسیم بسته به کاربرد آن متفاوت خواهد بود. درصورتیکه گرهها توانایی حرکت داشته باشند، شبکه میتواند گروهی از رباتهای کوچک در نظر گرفته شود که باهم بهصورت تیمی کار میکنند و جهت مقاصد خاصی ثلاًم بازی فوتبال و یا مبارزه با دشمن طراحیشدهاند.
از دیدگاه دیگر اگر در شبکه تلفن همراه، ایستگاههای پایه حذف شوند و هر گوشی یک گره فرض شود و ارتباط بین گرهها بهطور مستقیم و یا از طریق یک یا چند گره میانی برقرار شود، این خود نوعی شبکه حسگر بیسیم است. اگرچه به نقلی تاریخچه شبکههای حسگر به دوران جنگ سرد و ایدهی اولیهی آن به طراحان نظامی صنایع دفاع آمریکا برمیگردد، ولی این ایده میتوانسته در ذهن طراحان رباتهای متحرک مستقل و یا حتی طراحان شبکههای بیسیم موبایل نیز شکلگرفته باشد.
بههرحال از آنجاکه این فن نقطه تلاقی دیدگاههای مختلف است تحقق آن میتواند بستر پیادهسازی بسیاری از کاربردهای آینده باشد. کاربرد فراوان این شبکهها و ارتباط آن با مباحث مطرح در کامپیوتر و الکترونیک از جمله امنیت شبکه، ارتباط بلادرنگ، پردازش صوت و تصویر، دادهکاوی، رباتیک، طراحی خودکار سیستمهای تعبیه شدهی دیجیتال، بهینهسازی توان و انرژی و... میدان وسیعی برای پژوهش محققان باعلاقهمندیهای متفاوت فراهم نموده است.به بیانی دیگر میتوان گفت شبکههای حسگر بیسیم از تعداد زیادی حسگر، که حس میکنند، داده پردازش میکنند و عملیات ارتباطی انجام میدهندتشکیلشدهاند .[1] موضوع پوشش، مسئلهی اساسی برای شبکههای حسگر بیسیم است. مطالعات بسیار وسیعی در مساله پوشش، در شبکههای حسگر جهتدار همه جهته وجود دارد .[2-3] بااینحال بهینهسازی پوشش در شبکههای حسگر جهتدار جذابیت بیشتری برای محققین و متخصصان داشته است. از وقتیکه مدل حسی شبکههای حسگر سنتی، جهتدار همه جهته فرض شده است، راهحلها برای شبکههای حسگر بیسیم نتوانست روی مشکلات گرههای حسگر جهتدار مثل زاویه دید، جهت پذیری و میدان دید غلبه کند .[4]در این مقاله سعی شده است مروری بر انواع پوشش در شبکه های حسگر بی سیم همه جهته و جهت دار صورت گیرد .
– 2 پیشینهی تحقیق
تاکنون راهکارها و روشهای متعددی در جهت بهبود مساله پوشش ارائه گردیده است که هر یک به نحوی موجب افزایش پوشش و درعینحال بالا بردن کیفیت پوشش در شبکه نیز گردیده است. در [5] نویسندگان بیان میکنندکه تمامی مدلهای پوشش حسگر بهعنوان تابعی از مسافت و زاویه هستند و بهصورت ریاضی فرموله میشوند و بین حسگر و نقطهای از محیط تعریف میشوند. ورودی تابع اندازهی - میزان - پوشش مسافت و زاویه بوده و خروجی آنکه مقدار پوشش نامیده میشود،یک عدد حقیقی غیر منفی است. همچنین به معرفی و تحلیل رفتاری پنج مدل پوشش به نامهای پوشش قطاع بولی، دیسک بولی، دیسک تضعیفی، تضعیفشده تقریبی و تشخیصی پرداختهشده است. هدف اصلی مقایسههای خود را اثبات تحلیلی بر پایه روابط ریاضی در میزان پوشش هر مدل و همچنین نزدیکی به هدف موردنظر قرار دادهاند. نتایج ارائهشده حاکی از آن است که مدلهای تضعیفشده تقریبی و تشخیصی نسبت به سایر مدلها از درصد خطای کمتر و موفقیت بیشتر در درصد تحقق اهداف مدنظر برخوردارند .[5]
ما و لیو1 در سال 2005 اولین محققینی بودند که مفهوم شبکه حسگر جهتدار را معرفی کردند و درباره مسائل پوشش شبکه حسگر جهتدار بحث کردند. آنها برای حل مساله اتصال برای حسگرهایی که بهصورت تصادفی استقرار یافتهاند تحت عنوان مدل ارتباطی تلاش کردند. موضوع پوشش هدف در شبکههای حسگر جهتدار در چندین مطالعهی انجامشده، بحث شده است 9] و8 ،7،[6، که هدف آن، افزایش طول عمر شبکه بهوسیلهی پیدا کردن مجموعه پوشش بوده است.در این میان ای آی و ابو زید2 در سال 2006 پیشگامانی بودند که روی مسئلهی پوشش هدف در شبکههای حسگر جهتدار مطالعه کردهاند. آنها مدلی دارند که مسئلهی بیشترین پوشش با کمترین حسگرها 3 - MCMS - را برای تعداد اهداف پوشش دادهشده با کمترین تعداد حسگرهای فعال، حداکثر میکند. حسگرهای درون مجموعههای پوشش ساختهشده نباید همپوشانی داشته باشند 10]و.[8
یانگ و همکاران4 در سال 2010 فرض کردند که هر هدف مطابق نقشش نیازمند پوشش مخصوصی است که در کاربرد آن مفید است و فاصلهی بین هدف و حسگر کیفیت پوشش را تحت تأثیر قرار میدهد. آنها از یک مدل حسی جهتدار استفاده کردند که فقط یکجهت از حسگر میتواند در یکزمان کار کند. بعلاوه، آنها برای پیدا کردن یک الگوریتم زمانبندی حریصانه که دربرگیرندهی ترتیبی از مجموعههای پوشش عملی که میتواند طول عمر شبکه را طولانیتر کند کوشش بسیار کردند. اگرچه الگوریتمهای حریصانه قادر به حل مساله هستند، کارایی این الگوریتمها بسیار به تراکم اولین نامزدها برای راهحل بهینه بستگی دارد. بنابراین الگوریتمهای حریصانه میتوانند در کمترین محل به دلیل جستجوی ابتکاری، نتیجه دهند .[10 کای و همکاران1 مساله مجموعههای پوشش جهتدار چندتایی 2 - MDCS - را معرفی کردهاند. آنها چندین الگوریتم پیشنهادی برای حل مساله از طریق پیدا کردن زیرمجموعههای گسستهی حسگرها، دارند. ازآنجاییکه آنها از برنامهریزی خطی استفاده میکنند، الگوریتمهایشان از پیچیدگی بالا و زمان اجرای طولانی رنج میبرند. بعلاوه، الگوریتمهایشان با برخوردهای زیادی در میان جهتها، مواجه میشوند.مضافاً آنها برای حل مسئله، الگوریتم حریصانهای پیشنهاد دادهاند 10]و.[8
جیل و هان3 در سال 2011 دو الگوریتم پیشنهادی برای حل مساله پوشش هدفدارند، یکی روش الگوریتم حریصانه و دیگری الگوریتم ژنتیک. اولی - الگوریتم حریصانه - میتواندراهحلی پیدا کند که در مقایسه با دیگر الگوریتمهای ابتکاری سریعتر است، اما ممکن است برای پیدا کردن راهحلی بهینه به دلیل جستجوی محلی به شکست منجر شود. دومی - الگوریتم ژنتیک - به یک کران بالاتر روی تعدادی از پوششهانیاز دارد درحالیکه نمیتواند به آسانی به دست آید .[11] مطالعات اشارهشدهی بالا به مساله پوشش صرفنظر از موضوعات اتصال رسیدگی میکند.
-3 پوشش در شبکههای حسگر بی سیم - همه جهته و جهت دار -
دادهی بهدستآمده از محیط پیرامون، عملکرد اصلی کاربردهای حسگر بیسیم است. هر کاربرد هدف متفاوتی دارد و انواع متفاوتی از داده را جمعآوری میکند. بههرحال اغلب، هدف کاربردهای حسگر، حداکثر کردن پوشش با حداقل تعداد حسگر است. مساله پوشش در شبکههای حسگر بیسیم در دههی گذشته مورد تحقیقات وسیعی بوده است. این مساله تعدادی زیرمجموعه از قبیل پوشش سطح، پوشش هدف، پوشش _Kگانه، دارد که هرکدام نیازمند استراتژی متفاوتی برای حل است.
اتصال نیز قسمتی از مساله پوشش است، مطمئن میسازد که حداقل یک ارتباط بین هر دو زوج حسگر فعال وجود دارد. چون در شبکههای حسگر بیسیم ارتباط مستقیم به دلیل تحویل بسته در محیط وسیع، انرژی زیادی مصرف میکند، اغلب ارتباط چند گامه ترجیح داده میشود. بنابراین اتصال، مسئلهای برای شبکههای حسگر بیسیم میشود. برای مدل ارتباطی در شبکههای حسگر جهتدار چهار حالت وجود دارد:
– 1 ارسال و دریافت همه جهته، – 2 حس جهتدار و دریافت همه جهته، – 3 ارسال همه جهته و دریافت جهتدار و – 4 ارسال و دریافت جهتدار. اولی مشابه شبکههای حسگر جهتدار همه جهته است. در سه تای بعدی نیز دو حالت وجود دار. –I جهتهای حس و ارسال یکسان و –II جهتهای حس و ارسال متفاوت. بنابراین مساله نگهداری اتصال تحت مدل حس جهتدار پیچیده و سخت است. بسیار از راهحلهای شبکههای حسگر جهتدار فرض میکنند گرههای حسگر، همه جهته ارتباط دارند و حوزهی ارتباط گرههای حسگر حداقل دو برابر حوزهی حس - سنجش - آنهاست .[7]
– 4 طبقه بندی پوشش
سه نوع طبقهبندی پوشش بر اساس اینکه چه سنجشی باید تحت پوشش قرار بگیرد وجود دارند که عبارتاند از: پوشش ناحیه – پوشش هدف - نقطه مستقیم - و پوشش مانع 13]و[12 در یک استقرار تصادفی، شبکه حسگر جاییکه چگالی گرههای حسگر کافی است نظارت قویی روی اغلب اهداف وجود دارد.
