بخشی از مقاله
چکیده :
در سالهای اخیر، شبکههای حسگر بی سیم - Wireless Sensor Networks - در کاربردهای متعددی مانند کنترل و نظارت بر پدیدههای دینامیک مورد مطالعه قرارگرفته اند. یکی از مسائل مهم مورد مطالعه در این شبکهها، جایابی - Deployment - بهینه حسگرها بهمنظور دستیابی به بیشینهی مقدار پوشش - Coverage - است. ازاینرو، در اکثر تحقیقات برای رسیدن به پوشش حداکثر از الگوریتمهای بهینهسازی متعددی استفادهشده است. در یک ردهبندی کلی، الگوریتمهای بهینه سازی برای جایابی بهینه حسگر باهدف افزایش پوشش، به دو گروه الگوریتمهای بهینه سازی محلی و سراسری تقسیم میشوند.الگوریتمهای سراسری عموماً از یک روش تصادفی بر اساس یک روند تکاملی استفاده میکنند. در تمامی این الگوریتمها، محاسبهی تابع هدف جهت ارائه مدل پوشش حسگر در شبکه ضروری است.
در واقع بهبود پوشش از طریق بهینه سازی تابع هدف در فضای مساله صورت میگیرد. × در این تحقیق، با مدلسازی رستری محیط در فضاهای دو و سه بعدی، عملکرد الگوریتمهای بهینهسازی سراسری بهمنظور جانمایی بهینهحسگرها و در نتیجه ایجاد پوشش حداکثر شبکههای حس گر بیسیم با رویکرد افزایش پوشش، ارزیابی و مقایسه شده اند. از آنجاییکه هدف مقایسه عملکرد و نتایج الگوریتم های سراسری بوده است، منطقه مورد مطالعه و شرایط پیاده سازی یکسان فرض شده اند. در این مقاله، چند روش بهینهسازی برای جایابی سنسور، از جمله الگوریتمهای ژنتیک - Genetic Algorithm - GA - - ،L-BFGS - Limited-memory Broyden-Fletcher-Goldfarb-Shanno - ، VFCPSO - Virtual Force Co-evolutionary Particle Swarm Optimization - و CMA-ES - Covariance Matrix Adaption -Evolution Strategy - پیادهسازی شد و معیار ارزیابی الگوریتمها برای مسئله جایابی شبکههای حسگر بیسیم، مقدار پوشش بهینه و سرعت همگرایی الگوریتمها در نظر گرفته شده است.
واژههای کلیدی : شبکههای حسگر بی سیم، جایابی حسگر، پوشش شبکه، الگوریتمهای بهینهسازی سراسری، مدل رستری
-1 مقدمه
امروزه شبکههای حسگر بیسیم در علوم مهندسی و تحقیقات علمی کاربردهای متعددی یافته اند. آمایش زندگی حیوانات، بررسی فعالیتهای آتشفشانها و پایشهای زیست محیطی نمونههایی از این کاربردها هستند .[1]بدیهی است هر حس گر بخش خاصی از منطقه را پوشش می دهد و میزان پوشش منطقه، از مجموع سطح پوشش حسگرها بهدست میآید. بنابراین جایابی بهینه حسگرها بهمنظور دستیابی به بیشینه مقدار پوشش یکی از مسائل مهم در زمینه شبکههای حسگر بیسیم میباشد.موانع محیطی، نوع دادهای که برای مدلسازی محیط در نظر گرفته می شود و همچنین مدل تشخیص حسگر بر روی محاسبه پوشش شبکه تأثیر می گذارند . از انواع مدل های تشخیص حسگر به کار گرفته شده میتوان به مدل تشخیص دایرهای ساده و مدل جهتدار اشاره کرد 1] ، 2 ، .[3 همچنین مدلهای محیط از نظر نوع دادهای که برای آن در نظر میگیرند به صورت برداری و رستری تقسیمبندی میشوند 4]، 5 و .[6
چیدمان سنسورها به صورت بهینه یک مساله بسیار چالش برانگیز است و ثابت شده است برای بیشتر فرمولهای جایابی، پیچیدگی بالایی دارد. برای مقابله با این پیچیدگی، چندین الگوریتم بهینه سازی جهت یافتن بهترین مکان قرار دادن سنسورها پیشنهاد شده است4] ، 7 ، 8 ،.[9 الگوریتمهای سراسری همه فضای حل مساله در منطقه مورد مطالعه در جایابی شبکه حسگر بیسیم را در نظر میگیرند، یعنی به صورت یک جا در فضای مجهولات به جستجو راه حل برای بهینهکردن تابع هدف می پردازند. از ویژگیهای بارز این الگوریتم ها، تصادفی بودن آنها بر اساس یک روند تکاملی است. در تمامی این الگوریتمها، محاسبهی پوشش حسگر در شبکه به عنوان تابع هدف ضروری است. در واقع بهبود پوشش با توجه به نحوه محاسبه پوشش صورت میگیرد.در تحقیق حاضر، عملکرد الگوریتم های بهینهسازی سراسری تکاملی در مدل رستری دو و سهبعدی باقدرت تفکیکهای مختلف با وجود موانع و توپوگرافی محیط در آنها [10] اجرا، ارزیابی و مقایسه گردیده است.
مدل همه جهتی باینری برای مدل پوشش سنسور در حالتدو بُعدی محیط و مدل جهتدار باینری برای مدل پوشش سنسور در حالتسه بُعدی محیط در نظر گرفته می شوند .[4] از آنجاییکه هدف، مقایسه عملکرد و توانایی الگوریتمهای سراسری در مساله پوشش شبکه های سنسور بی سیم می باشد، منطقه مورد مطالعه و شرایط پیاده سازی کاملاً یکسان فرض شده اند. در این مقاله، چندین روش بهینهسازی برای جایابی سنسورها، از جمله الگوریتمهای ژنتیک [11]، [12] L-BFGS، 13] VFCPSO ، [9 و [8] CMA -ES پیاده سازی شده اند. علت انتخاب این الگوریتم ها، ماهیت تکاملی آنها در مقایسه با سایر روش های سراسری در بهینه سازی جایابی شبکه های سنسور بی سیم بوده است. معیار ارزیابی الگوریتمها برای مسئله جایابی شبکههای حسگر بیسیم، مقدار پوشش بهینه و سرعت همگرایی الگوریتمها در نظر گرفته میشود.در بخش دوم و سوم، نتایج حاصل از ارزیابی روش های منتخب بهینه سازی ارائه و با یکدیگر مقایسه میشوند و در ادامه پیشنهادهایی برای تحقیقات آتی مطرح خواهند شد.
-2 پیادهسازی و ارزیابی نتایج
در این بخش الگوریتمهای بهینهسازی سراسری تکاملی برای مسئله جایابی شبکههای حسگر پیادهسازی و پوشش شبکه بهعنوان تابع هدف مسئلهمدلو دو بُعدی و سه بُعدی رستری با قدرت تفکیک های مختلف به عنوان مدل محیط در نظر گرفته می شوند. همچنین مدل همهجهتی باینری برای مدل سنسور در مدل دو بُعدی محیط و مدل جهتدار باینری برای مدل سنسور در مدل سه بُعدی محیط در نظر گرفته شده اند .[ 4] هدف رسیدن به بیشینه پوشش سنسورها است که با توجه به مقدار درصد پوشش تمامی سنسورهای منطقه بدست می آید. در این تحقیق، الگوریتمها با توجه به درصد پوشش - تابع هدف - ، یعنی نسبت مساحت پوشش یافته به حداکثر توان پوشش سنسورها در منطقه،راه حلهای خود را به روز می کنند. معیار ارزیابی الگوریتمها برای مسئله جایابی شبکههای حسگر بیسیم،مقدار پوشش بهینه و سرعت همگرایی الگوریتمها در نظر گرفته می شود.
برای ارزیابی الگوریتمها
در مدل دوبعدی محیط، یک منطقه بهصورت دوبعدی با ابعاد 180 در 200 متردر نظر گرفته شد و مدل رستری آن بهعنوان ارزیاب مدل محیطی در فضای دوبعدی به کار گرفته شد
- شکل -1 - الف - - . در این منطقه ساختمانها بهعنوان موانع در مدل محیط در نظر گرفته شدند که ابعاد آنها در قدرت تفکیکهای مختلف، بهدلیل دقتهای مختلفی که دارند، متفاوت است.در حالتی که مدل سه بعدی برای محیط جایابی حسگرها استفاده می شود، از یک منطقه با ابعاد 200 در 200 متر، مجموعه دادههای رستری - مدل - DSM در قدرت تفکیکهای مختلف استفاده می گردد - شکل -1 - ب - - . این منطقه علاوه بر توپوگرافی زمین، شامل ساختمانها و درختان است که به عنوان موانع در نظر گرفته میشوند.
تعداد حسگرهای شبکه که بهعنوان یکی از پارامترهای مسئله جایابی شبکههای حس گر بیسیم است، برابر با 20 در نظر گرفته شده اند. فاصله عملکرد حسگرها ثابت و برابر با 15 متر است. در صورت استفاده از حسگر جهتدار زاویهعملکرد آن برابر با 120 درجه خواهد بود. بازه ارتفاع حسگر در مدل سهبعدی برای مسئله جایابی نیز از - روی سطح زمین - تا 10 متر ارتفاعی در نظر گرفته میشود. قدرت تفکیک مدلهای دو و سهبعدی رستری،بهعنوان مدل محیط جایابی شبکههای حسگر بیسیم، 100، 200، 300 و 500 سانتی متر در نظر گرفته شده اند.نمودار همگرایی برای مدلهای رستری با قدرت تفکیکهای مختلف بر مبنای الگوریتم های سراسری در شکلهای 2 - ، 3، 4 و - 5 نمایش داده شده است. در جدولهای -1 - الف تا د - ، مقدار پوشش نهایی، پوشش برداری، دقت پوشش و زمان محاسبه پوشش با استفاده از الگوریتمهای سراسری نشان داده شده است.
راهحلهای الگوریتم ژنتیک به صورت اعشاری در نظر گرفته شدند. مدل دو بُعدی، با در نظر گرفتن مدل سنسور همه جهتی پیادهسازی شد. ابتدا مدل سنسور همهجهتی در محیط دو بُعدی برای الگوریتم ژنتیک پیاده سازی شد که در این حالت، راه حلها به صورت کروموزومی در نظر گرفته شدند. در این راه حلها موقعیت سنسورها بهعنوان پارامترهای متغیر در نظر گرفته میشود. سپس روند بهینهسازی الگوریتم ژنتیک برای مدل سه بُعدی با مدل جهت دار سنسور پیاده سازی گردید . تعداد اعضای جمعیت در الگوریتم ژنتیک، برابر با 50 در نظر گرفته شد. عملگر انتخاب مسابقهای برای انتخاب راهحل نخبه در این الگوریتم در نظر گرفته شد. در این الگوریتم پارامتر نرخ تلفیق کهبهمنظور تعیین درصدی از جمعیت فعلی بهعنوان والدین برای تولید نسل جدید بهکاربرده میشود برابر با 70در نظر گرفته شد، بدین معنی که 70% جمعیت در هرتکرار برای تولید نسل بعدی با هم تلفیق میشوند.در واقع این پارامتر میزان تأثیر نسل قبل در نسل جدید را مشخص می کند. در این تحقیق پارامتر نرخ جهش برابر با 30% در نظر گرفته شد. شرط توقف نیز در 100 تکرار در نظر گرفته
