• کنترل فضایی

حسگر­های فعلی معمولا چندین سطح مصرف انرژی را دارا هستند. در هر سطح محدوده­ انتقال متفاوت است. در کنترل فضایی، نیاز به بررسی سیاست­های پیکربندی سطح انرژی از هر حسگر برای بهینه­سازی ارتباطات متقابل است.

پس می­توان مسائل کنترل توپولوژی را به صورت زیر طبقه ­بندی نمود.
شکل ۲-۸- طبقه بندی مسائل کنترل توپولوژی
۲-۸- دستیابی همزمان به پوشش و اتصال شبکه
تا اینجا تحقیقات مرتبط با پوشش و اتصال شبکه به صورت اجمالی مورد بررسی قرار گرفت. در ادامه به بررسی تحقیقاتی پرداخته شده که سعی به دستیابی همزمان پوشش و اتصال در شبکه را دارند [۳۶] [۳۷]. در [۳۷] ارتباط بین پوشش و اتصال شبکه توضیح داده شده است. در این مقاله نویسنده یک الگوی استقرار برای رسیدن به پوشش و اتصال ۲تایی کامل پیشنهاد داده است. بهینگی راه حل پیشنهادی برای همه نسبت­هایی که شعاع ارتباطی و شعاع حس کردن با هم دارند، اثبات کرده است. الگوی پیشنهادی در شکل ۲-۹ مشاهده می­ شود. در این شکل دایره های توپر روشن­تر نشانگر سنسورهایی هستند که در نوار افقی قرار می گیرند . نقاط توپر تیره­تر نشان­دهنده دو نوار عمودی هستند. در اینجا و است.
شکل ۲-۹- الگوی استقرار مبنی بر نوار برای رسیدن به پوشش و اتصال ۲ تایی.
در آخر نویسندگان میزان سودمندی بعضی از الگوهای معروف استقرار حسگرها در محیط را با توجه به تعداد حسگرهای مورد نیاز برای پوشش و اتصال مقایسه می­نمایند. چهار الگوری معروف استقرار حسگرها در محیط در شکل ۲-۱۰ مشاهده می­ شود.
شکل ۲-۱۰- چهار الگوی استقرار معروف حسگرها در محیط. (a) شش گوشه، (b) مربع، © متوازی الاضلاع و (d) شبکه مثلثی (با مثلث متساوی الاضلاع).
با توجه به نسبت شعاع حس کردن و شعاع ارتباطی سودمندترین الگو را از بین الگوهای معرفی شده در شکل ۲-۱۰ را از نظر تعداد حسگرهای مورد نیاز به صورت زیر معرفی می­نماید:

• هنگامی که الگوی مبتنی بر متوازی الاضلاع (مورد ج) از سه الگوی دیگر مناسب تر است.

• هنگامی که الگوی مربعی (مورد ب) از سه الگوی دیگر مناسب تر است.

• هنگامی که الگوی شش گوشه (مورد الف) از سه الگوی دیگر مناسب تر است.

۲-۹- الگوریتم ژنتیک و کاربرد آن در کنترل توپولوژی
در ابتدا با مفاهیم اولیه الگوریتم ژنتیک آشنا خواهیم شد و پس از آن به مرور کاربردهای الگوریتم ژنتیک در مسئله الگوریتم ژنتیک خواهیم پرداخت.
۲-۹-۱- مفاهیم اولیه در الگوریتم ژنتیک
الگوریتم ژنتیک، الهامی از علم ژنتیک و نظریه تکامل داروین است و بر اساس بقای برترین‏ها یا انتخاب طبیعی استوار است. این الگوریتم اولین بار توسط اچ هوللند در سال ۱۹۶۰ توسعه داده شده است [۳۸]. یک کاربرد متداول الگوریتم ژنتیک، استفاده از آن بعنوان تابع بهینه‏کننده است. الگوریتم ژنتیک ابزار سودمندی دربازشناسی الگو ،انتخاب ویژگی،درک تصویرو یادگیری ماشینی است. این الگوریتم با یک مجموعه از کروموزوم^[۵۴] ها شروع می­ شود. این مجموعه، جمعیت نام دارد. هرکروموزوم یک راه‏حل ممکن برای مسئله مورد نظر است. در این الگوریتم از جمعیت فعلی برای تولید جمعیت جدید استفاده می­ شود. در این فرایند امید است که جمعیت بعدی از جمعیت فعلی، بهتر باشد. یک تابع برازندگی^[۵۵] به هر راه‏ حل کدگذاری شده ارزشی را نسبت می­دهد. ژنتیک برروی کروموزوم­های موجود در جمعیت فعلی یا همان نسل فعلی به امید بدست آوردن جواب­های بهتر، قانون بقای بهترین را اعمال می­ کند و نسل جدیدی را ایجاد می­ کند. این فرایند باعث می­ شود که نسل­های جدید با شرایط مساله سازگارتر باشد. در هر نسل تابع برازندگی هر فرد در جمعیت موجود را ارزیابی می­ کند. افراد برازنده تر در جامعه، به صورت تصادفی انتخاب می­گردند. عمگر­های تلفیق^[۵۶] و جهش^[۵۷] به امید ایجاد نسلی برازنده­تر بر روی کروموزم­های انتخاب شده اعمال می­شوند و نسل جدید را شکل می­ دهند. الگوریتم با رسیدن به یک برازندگی مطلوب و یا تعداد حداکثر تکرار در نسل­ها خاتمه می­یابد. روند کلی الگوریتم ژنتیک به صورت زیر می­باشد:

• تولید جمعیت تصادفی شامل n کروموزوم.

• بررسی میزان برازندگی هر کروموزوم در جمعیت.

• ایجاد یک جمعیت جدید بر اساس تکرار گام­های زیر.

• انتخاب کروموزم­های پدر و مادر در جمعیت فعلی، بر اساس میزان برازندگی آن­ها (کروموزم­های مطلوب­تر شانس بیشتری برای انتخاب داشته باشند).

• در نظر گرفتن مقدار مشخصی برای احتمال عملگر تلفیق و سپس انجام این عملگر بر روی والدین به منظور ایجاد فرزندان جدید. اگر هیچ ترکیب جدیدی صورت نگیرد فرزندان همان والدین خواهند بود.

• اعمال جهش بر روی فرزندان با در نظر گرفتن احتمال جهش.

• جایگزینی فرزندان جدید در جمعیت.

• توقف اجرای الگوریتم در صورت مشاهده­ شرایط توقف.

• رفتن به گام ۲٫

فلوچارت این الگوریتم در شکل ۲-۱۱ مشاهده می­ شود.
شکل ۲-۱۱- فلوچارت الگوریتم ژنتیک
۲-۹-۲- کاربرد الگوریتم ژنتیک در شبکه حسگر و کنترل توپولوژی
الگوریتم ژنتیک ثابت کرده است که در کاربردهای مختلف رباتیک، شبکه حسگر و MANET^[58] (گروهی از گره­های متحرک که به صورت پویا یک شبکه را بدون هر گونه نیاز به زیرساخت­های موجود از قبل شکل می­ دهند) ابزار سودمندی است و در مسائل مختلف به کار گرفته شده است. درواقع الگوریتم ژنتیک در پیدا کردن جواب تقریبی در کاربردهای تجاری، نظامی که نیازمند تکنیک­های سریع، قابل تطبیق، خودکار و خودیادگیری است ابزار مفیدی است. در مقاله [۳۹] از الگوریتم ژنتیک برای مسئله برنامه­ ریزی مسیر برای چندین ربات متحرک که هریک هدف و سرعتی مشخص دارند، استفاده شده است. هدف الگوریتم بهینه­سازی کل مسیر پیموده شده توسط ربات­ها می­باشد. در این مقاله در دو سطح از الگوریتم ژنتیک استفاده می­ شود. در یک سطح الگوریتم سعی میکند، مسیرهای بهینه برای ربات ایجاد نماید. یعنی هر ربات الگوریتم ژنتیکی مختص به خود را دارد. درسطح دوم الگوریتم ژنتیک تلاش می­ شود تا بهترین ترکیب از مسیرهای رباتهای مختلف را به دست آورد تا کل مسیر پیموده شده توسط ربات ها بهینه شود. در [۴۰] از یک الگوریتم ژنتیک مبتنی بر دانش برای پیدا کردن مسیر ربات­های متحرک که در یک محیط پیچیده و دارای تغییرات پویا هستند استفاده شده است. در [۴۱] با بهره گرفتن از الگوریتم ژنتیک یک مدل داینامیک برای کنترل توپولوژی جهت رسیدن به توزیع یکنواخت گره­های متحرک خودمختار در فضای دو بعدی ارائه می­دهد. در [۴۲]، [۴۳] و [۴۴] نیز الگوریتم توزیع شده کنترل توپولوژی مبنی بر ژنتیک ارائه می­ دهند که در سیستم­های هوشمند تصمیم­­گیری نماید و به صورت یکنواخت در محیط توزیع شوند. در تحقیقات بسیاری مسئله کنترل توپولوژی در محیط دو بعدی مورد بررسی قرار گرفته است. کنترل توپولوژی سه بعدی یکی از چالش­های مطرح در مسائل مرتبط با این زمینه است. در مقایسه با روش های دو بعدی، دارای یک طیف وسیع تری از برنامه های کاربردی به ویژه برای بسیاری از ماموریت های نظامی و تجاری در محیط های زیر آب است. بنابراین نیاز به تحقیقات بیشتر در این زمینه وجود دارد. در [۴۵] یک توپولوژی کنترل سه بعدی بر مبنای الگوریتم ژنتیک در شبکه ­های حسگر زیر آب که متشکل از AUVهاست، ارانه شده است. در این مقاله هر AUV با بهره گرفتن از اطلاعات محدودی که از همسایگان خود جمع آوری می­ کنند، به صورت خودمختار سرعت و جهت حرکتش، با هدف رسیدن به یک توزیع مکانی یکنواخت و حفظ ارتباط، تعیین می_­نماید. در این تحقیق الگوریتم در شبیه­ساز چند عاملی رویداد-گسسته Mason [46] استفاده شده است که قابلیتی برای محیط زیر آب ارانه نمی­دهد. الگوریتم ارائه شده را می­توان از جهات مختلف مانند، به کار گیری شبیه­ساز مرتبط با محیط زیر آب، در نظر گرفتن محدودیت درجه­ همسایگی در گره­ها و اعمال تغییرات در الگوریتم، بهبود بخشید. این الگوریتم ۳D-GA نام دارد و در فصول آینده با روش پیشنهادی ما مقایسه خواهد شد.
فصل سوم: روش پیشنهادی
۳-۱- مقدمه
همانطورکه در فصل (۲) بیان شد، کنترل توپولوژی در شبکه­ حسگر بی­سیم به دو دسته پوشش در شبکه، اتصال شبکه تقسیم می­گردد. پوشش نیز خود به سه دسته­ی پوشش سراسری، حصاری و جاروبی دسته­بندی می­ شود. نوع پوشش مورد نظر در این پایان نامه به سه دسته تقسیم شده است. در دسته­ی اول هدف، پوشش سراسری در محیط است. در دسته­ی دوم ارائه­ پوششی حصاری برای حفاظت از یک شئ در محیط زیر آب، مورد نظر است. در دسته­ی سوم پوششی حصای برای حفاظت از یک درگاه در زیر آب مطرح است. در ادامه روش پیشنهادی در سه زیر عنوان کنترل توپولوژی با هدف پوشش سراسری و کنترل توپولوژی با هدف پوشش حفاظتی از یک شئ و پوشش حفاظتی از یک درگاه برای شبکه­ ای از AUVها مورد بررسی قرار خواهد گرفت.
۳-۲- کنترل توپولوژی با هدف پوشش سراسری
یک ناحیه­ می ­تواند توسط تعدادی AUV که آن را پوشش داده­اند، محافظت گردد. شکل ۳-۱ محافظت چند AUV از یک ناحیه را نشان می­دهد. در این پایان نامه، الگوریتم ژنتیک برای حداکثرسازی پوشش تمامی نقاط در محیط سه بعدی زیر آب توسط AUVها ارائه شده است. این الگوریتم هر AUV را توانمند می­سازد که به صورت مستقل سرعت و جهت حرکت خود را بر اساس اطلاعاتی که از همسایگانش به دست می ­آورد، تعیین نماید. این اطلاعات شامل مکان و درجه­ آن­ها است. هر AUV بهترین حرکت بعدی را در هر گام با اجرای الگوریتم ژنتیک به صورت مستقل به دست می ­آورد. در تابع برازندگی این الگوریتم، از یک تحلیل آماری برای میانگین درجه­ همسایگی با هدف تعیین حد بالای تعداد همسایگان یک AUV استفاده شده است. همانطور که در فصول گذشته بیان شد با مدیریت اتصالات می­توان میزان تداخلات ترافیکی را کاهش­ [۹] و میزان پوشش در محیط را افزایش داد [۱۱].
در ادامه به معرفی ساختار الگوریتم ژنتیک ارائه شده خواهیم پرداخت.
شکل ۳-۱- محافظت چند AUV از یک ناحیه
۳-۲-۱- ساختار کروموزوم­ ها
هر کروموزوم­ شامل جهت و سرعت حرکت بعدی AUV است. شکل ۳-۲ مدل حرکتی در نظر گرفته شده برای AUVها در فضای دکارتی سه بعدی را نمایش می­دهد. در این مدل AUVها می­توانند آزادانه در فضای دکارتی حرکت نمایند.
شکل ۳-۲- مدل حرکتی AUVها در فضای ۳ بعدی