پوشش در شبکه های سنسوری بیسیم

مروری بر روشهای پوشش در شبکه‌های حسگر

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

تقسیم بندی اول

برمبنای این تقسیم بندی کل روشهای پوشش در سه گروه زیر دسته بندی می‌گردند و هر دسته بر مبنای یکی از کاربردهایش نامگذاری شده است. این گروه‌ها عبارتند از 1- مساله گالری هنر[1]، 2- پوشش اقیانوس[2]، 3- پوشش سیستمهای روبوتیک[3].[5][4]

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

2- پوشش اقیانوس : در این نوع از مسائل بیان شده که برای مثال درصورتی که بخواهیم موجودات دریایی را تحت بررسی قرار دهیم و بخواهیم این کار را از طریق ماهواره‌ها انجام دهیم، به دلیل اینکه یک ماهواره براثر عواملی نمی‌تواند بیش از 15% سطح اقیانوسها را در روز پوشش دهد، چند ماهواره برای این کار لازم می‌گردد تا میزان پوشش افزایش یافته و از پوشش نقاط مشترک خودداری گردد.

3- پوشش سیستمهای روبوتیک : این نوع پوشش برای اولین بار توسط شخصی به نام Gage مطرح شد و انواع پوششها را از دید سیستمهای روبوتیک مطرح کرد. او سه نوع پوشش را بیان کرد که عبارتند از پوشش پوشاننده[4]، پوشش مرزی[5] و پوشش جاروبی[6]. در اولی هدف تعیین دقیق مکان حسگرهاست، به گونه‌ای که حداکثر پوشش را برای یک ناحیه ایجاد کنند. در دومی‌ هدف قرارگیری یکسری حسگر در محیط است به گونه‌ای که نواحی پوشش داده نشده براثر وجود موانع در محیط به حداقل برسد و سومی ‌کم و بیش شبیه به پوشش دوم می‌باشد، با این فرض که موانع در آن متحرک می‌باشد.

تقسیم بندی دوم

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

پوشش مرزی

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

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

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

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

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

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

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

پوشش نقطه‌ای

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

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

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

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

ترکیب پوشش نقطه‌ای با همبندی

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

مراجع:

[1] C.F. Huang and Y.C. Tseng, "The coverage problem in wireless sensor networks," In International Workshop on Wireless Sensor Networks and Applications, pp. 115-121, 2003.

[2] C.F. Huang, Y.C. Tseng, and H.L. Wu, "Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network," In ACM Transaction on Sensor Networks, vol. 3, no. 5, March 2007.

[3] M. Cardei, and J. Wu, "Energy efficient coverage problem in wireless ad-hoc sensor network," In Computer Communication, vol. 29, pp. 413-420, February 2006.

[4] M. Ilyas, and I. Mahgoub, "Handbook of sensor networks : compact wireless and wired sensing systems," In CRC Press Publishers, ISBN: 0-8493-1968-4, 2005.

[5] A. Ghosh, and S.K. Das, "Coverage and Connectivity issues in wireless sensor networks: A survey," In Pervasive and Mobile Computing, vol. 4, pp. 303-334, June 2008.

[6] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, "Coverage problems in wireless ad hoc sensor networks," In 20th Annual Joint Conference of the IEEE Computer and Communication Societies, pp. 1380-1387, 2001.

[7] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, "Exposure in wireless ad-hoc sensor network," In International Conference of Mobile Computing and Networking, pp. 139-150, 2001.

[8] M. Cardei, and D.Z. Du, "Improving wireless sensor networks lifetime through power aware organization," In Wireless Networks, vol. 11, no. 3, pp. 333-340, May 2005.

[9] M. Cardei, D.M. Callum, and X. Cheng, "Wireless sensor network whit energy efficient organization," In Journal of Interconnection Network, vol. 3, pp. 213-229, 2002.

[10] G. Anastasi, M. Conti, M.D. Francesco, and A. Passarella, "Energy conservation in wireless sensor networks: A survey," In Ad Hoc Networks, vol. 7, no. 3, pp. 537-568, May 2009.

[11] I. Cardei, and M. Cardei, "Energy-efficient connected-coverage in wireless sensor networks," In International Journal of Sensor Networks, vol. 3, no. 3, pp. 201-210, May 2008.

[12] M. Cardei, M.T. Thai, Y. Li, and W. Wu, "Energy-efficient target coverage in wireless sensor networks," In IEEE Infocom, pp. 1976-1984, 2005.

کلمات کلیدی: شبکه ، شبکه سنسوری ، شبیه سازی، پوشش ، رایگان، آموزش رایگان، شبکه های کامپیوتری

پوشش در شبکه های سنسوری بیسیم

مطالب مشابه :

شبکه های بیسیم چیست؟

شبکه های بیسیم - فصل دوم

تکنیک های مکان یابی شبکه حسگر بی سیم (ادامه)

شبکه های بیسیم شهری

پوشش در شبکه های سنسوری بیسیم

شبیه سازی الگوریتم های فازی شبکه های حسگر بیسیم در متلب

چالش های مسیریابی در شبکه حسگر بی سیم 2