بخشی از مقاله
چکیده
شبکههای حسگر بیسیم رشد شگرفی طی سالهای اخیر داشتهاند.. حفظ پوشش دریافت همراه با ذخیره انرژی شبکه حسگر بیسیم، یکی از چالشهای اصلی در پژوهش پیرامون این سیستمهاست. علاوه براین در بعضی از کاربردهای شبکه حسگر بیسیم نیاز به پوشش از درجه k میباشد تا از کیفیت نظارت اطمینان حاصل شود. در این پایان نامه، ما یک برنامه زمانبندی حسگری را دنبال میکنیم که مسئله پوشش از نوع k را بررسی میکند تا ضمن این برنامه، حسگرها به گونه ای موثر برنامه ریزی شوند که با هدف طولانی کردن طول عمر شبکه، کل ناحیه بررسی نیز دارای پوشش از نوع k باشد. ضمنا، ما یک الگوریتم زمانبندی توزیع شده پیشنهاد میکنیم که در آن هر گره خود در مورد روشن یا خاموش بودنش تصمیم می گیرد و این تصمیم گیری بر اساس اطلاعات موقعیتی اش و چگالی گره ای در ناحیه هدف میباشد.
برای این منظور ما ابتدا حداقل تعداد گره هایی را که برای پوشش درجه k کل ناحیه هدف کافی هستند را محاسبه می کنیم. سپس بهترین موقعیتها را برای این گرهها بدست میآوریم. براساس این موقعیتهای محاسبه شده، ناحیه به چندین زیر ناحیه تقسیم میشود که هر کدام توسط حداقل k حسگر قابل پوشش است. سپس در هر زیر ناحیه یک روند زمانبندی محلی، برنامه کاری حسگرها را تعیین میکند. نتایج شبیهسازی نشان میدهد که الگوریتم پیشنهادی که kCAOP نامیده میشود میتواند ضمن حفظ پوشش کامل ناحیه هدف، طول عمر شبکه را بیشینه کند.
مقدمه
شبکههای حسگر بی سیم شامل مجموعهای از گرههای حسگری با سایز کوچک هستند که کاربردهای گستردهای از جمله پیگیری وسایل نقلیه، اعلام خطر و مراقبت از میدان جنگ دارند. گرههای حسگر بی سیم که عموما به وسیله باتریهایی با توان محدود تجهیز میشوند، بهآسانی و با هزینه پایین میتوانند برای نظارت بر حوادث محیطی جایگذاری شوند. از آنجا که در چنین شبکههایی تعویض باتری گره به منظور افزایش طول عمر شبکه و حفظ سطح اطمینان بالا از پوشش محیط غیرممکن است، نوعی از افزونگی را با جایگذاری تراکم بالایی از حسگرها فراهم میکنند.
اما، چنانچه تمامی گرههای حسگری همزمان با هم فعال باشند، بخش عمدهای از انرژی گرهها به سبب تبادل حجم بالایی از پیامها مصرف خواهد شد. که این موضوع میتواند به طور قابل ملاحظهای موجب افت سریع انرژی گرهها و خاتمه عمر شبکه شود. برای جلوگیری از فعالیتهای غیر ضروری گرهها، ما میتوانیم از بعضی الگوریتمهای زمانبندی استفاده کنیم. الگوریتمهای زمانبندی برای برنامهریزی گرهها استفاده می-شوند تا با نوبتی کردن فعالیت گرهها، سرعت افت انرژی کل سیستم کاهش یابد.
این الگوریتمهای زمانبندی اغلب از بعضی اهداف طراحی همانند اتصال، پوشش، ذخیره انرژی و... آگاه هستند. به عبارت دیگر، از آنجا که سیاست برنامه زمانبندی، بعضی حسگرها را روشن میکند و سایر حسگرها را خاموش نگه میدارد، طبیعتا ممکن است این سیاست موجب کاهش اتصال و پوشش در شبکه شود. از این رو، یک زیر مجموعهای از گرهها میبایست برای حسکردن و ارتباط برقرار کردن با سایر حسگرها فعال نگه داشته شوند تا از پوشش، اتصال و سایر اهداف طراحی اطمینان حاصل شود.
مفهوم پوشش همانگونه که در فصل قبل نیز تشریح شد، یکی از اساسیترین مفاهیم در WSNها میباشد که به طور مستقیم کیفیت خدمات را تحت تاثیر قرار میدهد. در حقیقت پوشش نمایانگر چگونگی پیگیری مجموعهای از اهداف توسط گرههای حسگری جایگذاری شده میباشد. در برخی موارد ممکن است که بنابر اهمیت و حساسیت محیط تحت نظارت، بالابردن سطح اطمینان از پوشش تکتک نقاط محیط ضروری باشد. در چنین مواردی میبایست هر نقطه از محیط با حداقل k حسگر تحت پوشش قرار گیرد تا در صورت رخدادن حوادثی که منجر به از سرویس خارجشدن یک یا چند حسگر میشود، سطح پوشش نقاط محیط در حد مطلوب حفظ شود.
به این نوع از پوشش در ادبیات، پوشش از درجه k گفته میشود. سطح پوشش مورد نیاز k ممکن است برای کاربردهای مختلف، متفاوت باشد. در محیطهای مساعد همانند نظارت بر منازل، k میتواند روی یک مقدار کوچک تنظیم شود، در حالیکه در محیطهای متخاصم و امنیتی همانند میادین جنگ، k باید بر روی مقادیر بزرگ تنظیم شود. حتی برای یک شبکه حسگری خاص نیز ممکن است k در شرایط مختلف متفاوت باشد. به عنوان مثال، برای هشداردهنده آتش در جنگل، k ممکن است در فصول بارانی کوچک باشد، اما در فصول خشک بزرگ در نظر گرفته شود.
ممکن است اینگونه بیان شود که با وجود حسگرهای مازاد در شبکه، دستیابی به سطح پوشش k آسان است. با این وجود بنابر توضیحاتی که در بالا ذکر شد، محدودیت انرژی این شبکهها مسئله پوشش و کیفیت آن را به چالشی در این زمینه تبدیل کرده است. در همین رابطه، در مرجع [2] نشان داده شدهاست که هر حسگر در حالتهای گذار، دریافت و بیکاری توانی معادل با 0/34 تا 0/7 وات انرژی مصرف میکند و این در حالیست که مصرف انرژی آن در شرایط خواب - عدم فعالیت - برابر با 0/03 وات است.
علاوه براین بیان شده است که طول عمر باتری مورد استفاده در WSNها در شرایط عملیات با برنامه زمانبندی، تقریبا دو برابر حالتی است که عملیات به طور پیوسته انجام شود.[3] این حقایق لزوم استفاده از یک الگوریتم زمانبندی مناسب برای شبکه حسگر بی سیم را به خوبی روشن میکند. از اینرو در این پژوهش به دنبال آن هستیم تا با استفاده از یک الگوریتم زمانبندی جدید، برنامهای ارائه شود تا همزمان با محقق شدن پوشش درجه k برای محیط تحت نظارت، طول عمر شبکه نیز افزایش یابد.
بر اساس آنچه در بالا ذکر شد، الگوریتمهای زمانبندی پوشش بسیاری پیشنهاد شدهاند. بعضی از این الگوریتمها فرض میکنند که گرهها با استفاده از دستگاهها یا تکنیکهایی از موقعیت خود باخبر هستند. دیگران بر این عقیده هستند که فاصلههای بین گرهها با استفاده از طول موج سیگنالهای دریافتی قابل دستیابی هستند. برخی دیگر، بعضی گرههای متحرک با تحرک قابل کنترل را بررسی میکنند. و عدهای دیگر از محققان، الگوریتمهای کنترل کننده پوشش بدون استفاده از هیچ نوع اطلاعاتی از موقعیت، فاصله یا زاویه از گرههای حسگری پیشنهاد کردهاند.
از نقطه نظر دیگر، یک الگوریتم زمانبندی فعالیت حسگر میتواند به صورت توزیع شده یا متمرکز باشد. یک پروتکل زمانبندی توزیع شده به آسانی به شبکههای حسگری با اندازه بزرگ قابل بسط دادن است، بنابراین این پروتکل مطلوبتر است. در این پروتکلها اغلب اینگونه فرض میشود که زمان به دورههای کاری تقسیم شود. در شروع هر دور کاری، تمامی گرههای حسگری بیدار میشوند و میبایست در مورد فعالیتشان در دور کاری جاری تصمیمگیری کنند. این مرحله تصمیمگیری بر اساس تبادل پیام است. علاوه بر این، در پایان هر دور کاری، تمامی حسگرها میبایست فعال شوند و نیاز است تا مرحله تصمیمگیری در دور کاری بعد تکرار شود. از سوی دیگر، در صورت بزرگ بودن سایز شبکه، ممکن است نرخ مصرف انرژی ناشی از تبادل پیامها بسیار بالا باشد.
دراین مقاله براساس الگوریتم CAOP درمرجع شماره [38] نوشته شده است با این تفاوت که درالگوریتم پیشنهادی ما از پوشش درجه K یعنی برای هر نقطه از محیط Kسنسور درنظر گرفتیم مثلا اگر K=2باشد برای هرنقطه فقط 2 سنسور درهر دور کاری فعال خواهد شد درصورتی که در الگوربتم CAOP فقط برای هرنقطه یک سنسور قرارداده شده وهمچنین تفاوت دیگر این است که ما محیط را به چند زیر ناحیه تقسیم کردیم وبرای هرناحیه تعدادی گره به طور درنظر گرفتیم و بیان کردیم درهرناحیه چه سنسورهایی آن ناحیه را تحت پوشش قرارداده است ودر این الگوریتم دو شرط قراردادیم .
شرط اول ابتدا درهر ناحیه تعداد سنسورها را محاسبه می کنیم اگر تعداد سنسورها دردوناحیه مختلف متفاوت بود ویک سنسور دیگر درمرز دوناحیه قرارداشت آن سنسور را به ناحیه ای میدیم که تعداد سنسور کمتری دارد. شرط دوم اگر تعداد سنسورها در دو ناحیه مختلف برابر بود آن سنسور را به ناحیه ای میدهیم که یک قسمت ازناحیه سنسور ندارد. درشروع فعالیت فرض می شود هرسنسور موقعیتش را میداند وسپس برای طراحی یک الگوریتم زمانبندی پوشش درجه k در محیط و به صورت آگاهانه از مصرف انرژی، تلاش میکند.
الگوریتم پیشنهادی یک روش توزیع شده را دنبال میکند و برنامه زمانبندی آگاه از پوشش k برای جایدادن بهینه حسگرها - - KCAOP نامیده میشود. هدف از این طراحی حفظ سطح پوشش k و در عین حال طولانیتر کردن طول عمر شبکه با مصرف انرژی بهینه میباشد. در بخشهای بعدی این فصل برخی مقدمات برای ارائه مدل فوق - الذکر بیان میشود و سپس الگوریتم پیشنهادی - KCAOP - 1 تشریح میگردد.
روش کار
همانند دیگر پژوهشهای انجام شده در این زمینه، فرض میشود تمامی رخدادها در طول عمر شبکه، در دورههای کاری متوالی اتفاق میافتند. در اولین دور کاری، تمامی حسگرها فعال هستند و در مورد دور فعالیتشان آگاه میشوند. فرضیات زیر در این پژوهش در نظر گرفته شدهاست.
❖ جایگذاری گره حسگری در ناحیه تحت پوشش به صورت تصادفی است، یعنی موقعیت گرهها با روندهای تصادفی مستقل تعیین میشوند.
❖ هر گره از موقعیتش آگاه است و تمامی گرهها قادر به ارتباط برقرار کردن با یکدیگر هستند.
❖ می حسگرها دامنهی دریافت یکسان دارند که با Rs نمایش داده میشود.
❖ تمامی حسگرها از تعداد گرههای جای داده شده در محیط که با تعداد نود2 نمایش داده میشود، آگاه هستند.
