تعیین چرخه فعالیت مورد نیاز برای رسیدن به طول عمر مورد نیاز.

برای حل این مسئله روشی به نام خوابیدن تصادفی مستقل ارائه می گردد که در آن زمان به دوره هایی تقسیم می گردد. در ابتدای هر دوره هر گره به صورت مستقل تصمیم می گیرد که برای ادامه دوره فعال باقی بماند (با احتمال p)و یا به خواب برود (با احتمال۱-p). به این ترتیب عمر شبکه به اندازه ۱/p افزایش خواهد یافت. به این ترتیب با دانستن عمر مدت نظر برای شبکه و دانستن مدت فعالیت گره ها در حالت فعال به دست آوردن چرخه فعالیت لازم برای رسیدن به طول عمر مورد نظر ساده می باشد. به علاوه این روش یکنواخت خواب گره ها باعث مصرف متوازن انرژی در شبکه می گردد.[۱۸]
باید توجه داشت که تقسیم فعالیت گره ها به دوره های مختلف قبلاً نیز در گره های حسگر پیشنهاد شده و مورد استفاده قرار گرفته است. روش بر پایه نگهبان [۷۷] که در آن گره فعال به عنوان نگهبان خوانده می شود پیشنهاد شده است. ولی انتخاب گره های نگهبان در آن به صورت پویا در نظر گرفته نشده است. در [۴۵] روشی برای انتخاب نگهبانان ارائه شده است.
در این حالت گره برای مدتی به نسبت عکس انرژی باقی مانده اش عقب نشینی می کند و سپس با انتخاب شعاع ارسال به اندازه شعاع حسگرش قصد خود را برای نگهبان شدن به سایر گره ها اعلام می دارد .با اینکه استفاده از باقی مانده انرژی روش خوبی برای تعیین نگهبان ها می باشد و مصرف انرژی را توزیع می نماید ولی در این روش راهی برای تعیین احتمال انتخاب نگهبانان برای رسیدن به یک طول عمر مشخص ارائه نشده است، بنابراین در این قسمت می توان از روش خوابیدن تصادفی مستقل استفاده کرد. به علاوه در این روش گره نیازی ندارد با همسایگانش هماهنگی کند که آیا حق دارد به خواب برود یا خیر؟
در کاربرد های پوشش توزیع بار تنها یک ویژگی دلخواه به شمار می رود. در حالی که هدف اصلی فراهم آوردن پوشش مورد نظر با بهره گرفتن از گره های نگهبان بر روی ناحیه حسگر به شمار می رود. یکی از اهداف روش ارائه شده در [۳۳] برای انتخاب گره های نگهبان فراهم آوردن پوشش کامل با بهره گرفتن از این گره ها می باشد. ولی اگر تعداد کافی گره های حسگر به کار نرفته باشند دسترسی به پوشش کامل غیر ممکن می باشد. هم چنین در [۷۸] [۲۳] روش های ارائه شده به این نکته می پردازند که چگونه گره های نگهبان پوشش k- لایه ای را بر روی ناحیه مورد نظر فراهم آورند ( با ارتباط با سایر گره ها و تعیین این نکته که به بیداری آنان نیازی هست یا نه).
ولی باز هم اگر تعداد کافی گره در شبکه به کار نرفته باشد این امر غیر ممکن می گردد. بنابراین توسعه روشی که بتواند پوشش k- لایه ای تضمینی ارائه کند و در عین حال این امکان را فراهم آورد که گره ها تنها به اندازه p درصد از وقت خود را فعال باشند از مسائل اساسی که در حال حاضر در شبکه های حسگر وجود دارد می باشد.
مزیت دیگر این روش این است که می توان به خواب رفتن گره ها را نوعی از کار افتادن در نظر گرفت و به این ترتیب می توان احتمال خرابی و از کار افتادن گره ها را نیز در این کار داخل گرداند. در این بخش می خواهیم روابط لازم را با داشتن تعدادی گره، k مورد نظر، شعاع حسگر، و اندازه ناحیه به دست آوریم. سه نوع توزیع برای گره ها در نظر گرفته می شود. توزیع تصادفی یکنواخت، توزیع پواسون، و توری ()می باشد.
پیش از اینکه به روابط موجود بپردازیم بد نیست برخی از دلایل نیاز به پوشش k- لایه ای به جای ۱-لایه ای را بر شمریم.
در برنامه های کشف نفوذگر برای تامین هدف دسته بندی، لازم است که نفوذگر توسط بیش از یک گره کشف شده و در عوض حداقل توسطk گره حس شود. مقدارk بستگی به میزان دقت برنامه دسته بندی دارد. به عنوان مثال دامنه حسگرهای مغناطیس سنج بستگی به نوع نفوذگر دارد. این مقدار برای افراد مسلح۲-۳ متر، برای ماشین ها ۷-۵ متر می باشد. بنابراین یک ماشین توسط تعداد بیشتری گره کشف می شود. از این امر می توان برای جداسازی یک اتومبیل از افراد مسلح استفاده کرد.
در یک شبکه چندگامه حسگر ممکن است نرخ از دست دادن بسته ها بسیار بالا باشد. بنابراین لازم است که k یا تعداد بیشتری حسگر نفوذگر را کشف کرده و گزارش کنند تا بتوان از رسیدن پیام به ایستگاه مرکزی اطمینان حاصل کرد.
پوشش k- لایه ای هم چنین برای تشخیص تحریک بی دلیل گره ها مورد نیاز است. به این ترتیب قادر هستیم که تحریک بی دلیل گره ها به دلیل باد و یا سایر رویدادهای طبیعی را از یک نفوذ جدا کنیم.
دلیل دیگر نیاز به پوششk- لایه ای بهبود کیفیت ردگیری اهداف می باشد. پوشش نفوذگر توسط k گره باعث می شود که بتوانیم موقعیت جغرافیایی و یا سرعت گره را با دقت بیشتری به دست اوریم ( برابر) در صورتی که داده های کشف به حالت بهینه ای ترکیب گردند.
۵-۱ تحقیقات پیشین
در [۳۰] روشی قطعی برای فراهم آوردن پوشش بر روی یک ناحیه تحت پوشش ارائه داده است. این روش تضمین می کند که پس از خاموش شدن گره های اضافی پوشش شبکه به اندازه قبل باقی می ماند. در این روش فرض می شود که همه گره ها دارای اطلاعات جغرافیایی می باشند. در این روش هم چنین فرض می شود که می توان جهت سیگنال را به دست آورد که برای فراهم آوردن این پیش فرض ممکن است به بیش از یک آنتن نیاز پیدا کرد. در این روش هم چنین نیاز است روشی برای به دست آوردن اطلاعات جغرافیایی گره های اطراف وجود داشته باشد.
در [۷۹] نویسندگان روشی بر پایه کلونی مورچه برای خودسازمان دهی در شبکه های حسگر ارئه داده اند. هر گره به صورت یک مورچه غیر متحرک در نظر گرفته می شود. هر مورچه در هر چرخه به احتمال p بیدار می شود با کشف شدن یک نفوذگر مورچه فرومون ترشح می کند که به تدریج به گره های اطراف انتشار پیدا می کند. گره هایی که این فرومون را دریافت می کنند احتمال بیداری خود را در دوره بعدی بالا می برند. در واقع بر اساس مقدار تجمعی فرومون دریافت شده در هر چرخه احتمال به خواب رفتن در چرخه بعدی تعیین می گردد. این روش درصد گره های سودمند ( گره هایی که نفوذگری را دریافت کرده اند) در شبکه را افزایش می دهد.این روش تضمینی برای کشف شدن رویدادها ارائه نمی دهد.
در [۳۲] به این نکته پرداخته شده است که احتمال به دست آوردن پوششk- لایه ای به چه نسبتی با شعاع حس کردن و تعداد گره های به کار رفته در توزیع های گوناگون (پواسون و تصادفی یکنواخت) تغییر می کند. در این مقاله اثر مرزی نیز در نظر گرفته شده است. گره ها همیشه فعال بوده و هیچ دوره خوابی نیز وجود ندارد.
در [۲۹] و [۴۵] نتایج به کار اندازی واقعی گره های حسگر ارئه شده و نکاتی کلیدی در مورد کشف، دسته بندی، مدل خطا ( از کار افتادن گره ها، خطای ارتباطی، …)، قابلیت های رادیویی، اعلان خطرهای اشتباه، و مصرف انرژی در حالت های مختلف ارائه می دهد.
در [۲۶]به مسئله پوشش k تایی که در آن با داشتن یک مجموعه متناهی از نواحی، هدف تقسیم گره ها به پوشش هایی است که در آن تعداد پوشش هایی که یک ناحیه را شامل می شوند حداکثر باشد. در حقیقت تعداد دفعاتی که ناحیه پوشیده می شود حداکثر می گردد. به این معنی که با چرخش میان k پوشش درصد مشخصی (مثلا۸۰%) از نواحی در پنجره ای به طول k مرحله قبلی پوشانیده شده باشند. بنابراین پوشش در این روش حفظ نمی گردد.
[۳۴] مسئله حداکثر سازی مجموعه پوشش را برای دانستن اهدافی که قرار است پوشانده شود حل می کند. هم چنین ثابت می کند مسئله بیشینه سازی تعداد پوشش ها np-complete می باشد.
در [۲۳] نشان داده شده است که برای به دست آورده اتصال در شبکه در شرایطی که پوشش ۱- لایه ای بر روی ناحیه وجود دارد، لازم است که شعاع فرستادن گره دو برابر و یا بیشتر بزرگتر از شعاع حسی حسگر باشد. .
در این مقاله هم چنین روشی برای فراهم آوردن اتصال و پوشش تضمینی (با درجه های مختلف) ارائه می دهد.
[۳۱] روشی توزیع شده برای کنترل چگالی در شبکه های حسگر بی سیم ارائه می دهد که از طریق کاوش محلی گره های همسایه صورت می گیرد این روش نیاز به اطلاعات ساختاری و موقعیتی گره های همسایه ندارد.
در [۷۵] روشی برای حساب کردن پوشش فراهم شده برروی هر ناحیه ارائه شده است که با بهره گرفتن از آن می توان تعیین کرد چه نقاطی از شبکه به اندازه کافی پوشانیده نشده اند.
اکثر روش های قطعی مانند [۳۰][۲۳][۳۱] از یک معیار شایستگی برای خاموشی های اضافی در هر ناحیه استفاده می کنند. برای اینکه تعیین شود که چه گره هایی می توانند به خواب بروند گره ها به اطلاعات جغرافیایی همسایگان خود نیاز دارند. هم چنین نیاز دارند که ناحیه برای گره های فعال جستجو کنند. این سربار ارتباطی و محاسباتی بیشتری نسبت به روش های احتمالاتی به شبکه تحمیل می گرداند.
تا حد اطلاع نویسنده تنها موردی که در آن سعی شده است تا با تنظیم پویای شبکه حسگر سطوح مختلفی از پوشش ارائه شود در [۲۳] ارائه شده است.
در [۱۸] شرایط مرزی مورد نیاز برای فراهم آوردن پوشش k-لایه ای در شبکه خواب آلود در سه توزیع (توری،یکنواخت تصادفی،پواسن) ارائه شده است. ما از حدهای ارائه شده در این مقاله برای حساب کردن احتمال مورد نیاز در شبکه استفاده می کنیم.
۵-۲ پوشش k-لایه ای پویا
۵-۲-۱ تعریف مسئله
مجموعه ای متشکل از N حسگر {s1,s2,s3,….}=S ،در محیط دو بعدی A وجود دارند.گره ها در سه توزیع تصادفی یکنواخت ، توری ، و یا پواسن ریخته شده اند.همه گره ها دارای شعاع حسی مشابه r می باشند.
همانطور که در شکل نشان داده شده است گره ها دارای دوره های خواب و بیداری می باشند.
شکل ۵-۱:دوره های خواب بیداری گره
گره ها در حالت خواب می توانند دستگاه حسگر ودستگاه فرستنده خود را خاموش کنند تا صرفه جویی انرژی بیشینه گردد. روشن و خاموش کردن دستگاه فرستنده توسط MAC کنترل می گردد واحتمال خواب و یا بیداری دستگاه حسی از روشی که در ادامه ارائه می گردد تعیین می شود.
پیش فرض های ما بسیار به مقالات [۱۸][۲۵] شبیه می باشد. شبکه بسیار چگال(چنان که تعداد گره هایی که در شبکه به کار رفته اند ممکن است چند مرتبه بزرگی بزرگتر از تعداد گره های فعال در شبکه باشد. (تعداد کافی گره در شبکه به کار رفته اند تا بتوان پوششk- لایه ای فراهم کرد. گره ها با بهره گرفتن از یکی از روش های همزمان سازی که همزمانی در سطح میکرو ثانیه را فراهم می آورند،هم زمان شده اند [۳۶][۳۷].
ما فرض می کنیم که تعداد رویدادهایی که در شبکه رخ می دهند زیاد باشد. پویا بودن پوشش بیهوده است. گره ها در حالت های مختلف خواب، بیداری، دریافت و ارسال دارای مصرف انرژی متفاوتی هستند[۲۹][۲۷]. ما فرض می کنیم که گره ها دارای اطلاعات جغرافیایی نمی باشند. هم چنین گره ها اطلاعاتی در مورد موقعیت و وضعیت گره های همسایه ندارند. شعاع ارتباطی گره ها مساوی و یا بیشتر از شعاع حسی گره ها می باشد. به علاوه ما فرض می کنیم که در شرایطی که مزاحمی در محدوده حسی حسگر باشد حتما توسط حسگر کشف خواهد شد.
ما روشی را برای فراهم آوردن پوشش ۱- لایه ای بر روی همه ناحیه ارائه می دهیم.در صورتی که رویدادی در شبکه توسط تنها گره فعال در آن ناحیه پیدا شود تعداد گره های فعال در آن ناحیه به k تا افزایش پیدا می کند. از آنجا که ما نمی خواهیم از اطلاعات جغرافیایی استفاده کرده و یا پیام کنترلی به کار ببریم از روشی احتمالاتی برای تعیین وضعیت گره ها استفاده می کنیم.
برای احتمال بیداری گره ها از معادلات ارائه شده در [۱۸] استفاده می کنیم.
تابع یک تابع با رشد آرام می باشد در صورتی که صعودی یکنواخت بوده
O(log log (np)) بوده به ازای n→∞ به سمت بی نهایت میل کند.
تابع را در نظر بگیرید، در صورتی که برای توزیع های تصادفی یکنواخت برای یک تابع داشته باشیم:
آنگاه تمامی نقاط شبکه تقریبا دارای پوششk- لایه ای می باشند [۱۸] . که در آنn تعداد گره ها، p احتمال بیداری هر گره در هر چرخه، و r شعاع حسی هر حسگر، و k سطح پوشش مورد نظر باشد.
برای توزیع توری به ازای یک تابع داریم که اگر
آنگاه تقریبا همه نقاط با رفتن n به سمت بی نهایت دارای پوششk- لایه ای هستند.
مشابه [۱۸]ما فرض می کنیم که تعداد گره های شبکه به اندازه کافی بزرگ می باشد. بنابراین روابط حدی (۱) و (۲) برقرار می باشند ما از این روابط برای به دست آوردن احتمال بیداری مورد نیاز برای دست یابی به سطوح مختلف پوشش( برای تعداد ثابتی گره) استفاده می کنیم.
هدف ما پیدا کردن پایین ترین احتمالی است که شرایط بالا را فراهم می آورد. کمینه کردن این احتمال منجر به پایین تر بودن تعداد گره های فعال در هر چرخه شده و صرفه جویی انرژی را بهبود می بخشد. البته احتمالات بالاتر هم ممکن می باشد، و پوشش بالاتری را فراهم می آورند ولی در عوض مصرف انرژی نیز افزایش می یابد. به کار بردن احتمالات بالاتر گاهی اوقات در شبکه ضروری می باشد چرا که ممکن است برنامه کاربردی به احتمال بالاتر و تضمین های بیشتری نیاز داشته باشد.
ما از این حدود برای تعیین احتمال مورد نیاز برای فراهم آوردن پوشش ۱- لایه ای بر روی شبکه استفاده می کنیم. هم چنین این احتمال برای فراهم آوردن پوششk- لایه ای در موردی که نفوذگری کشف شده است استفاده می گردد.
۵-۳ روش پیشنهادی
چنانکه در شکل ۵-۲ نشان داده شده است هدف ما داشتن حداقل یک گره فعال در تمامی نواحی می باشد تا بتوان ناحیه مورد نظر را کاملأ پوشش داد.از شرایط (۱) و (۲) برای تعیین احتمال بیداری مورد نیاز برای دستیابی به سطح پوشش مورد نیاز استفاده می گردد. تمامی گره ها برای محاسبه احتمال مورد نیاز برای رسیدن به پوشش ۱-لایه ای نیاز به داشتن نوع توزیع و تعداد گره های به کار رفته دارند.این مقادیر باید در شبکه پس از به کاراندازی آن به صورت سیل آسا پخش گردند. در صورتی که یکی از این مقادیر تغییر کرد و یا مثلأ سطح پوشش مورد نیاز کاربر عوض شد،لازم است که این داده ها دوباره در شبکه پخش گردند.