بخشی از مقاله
چکیده
یکی از مسائل اساسی در طراحی شبکه های حسگر بیسیم1، محدود بودن منبع انرژی حسگر هاست. زمان حیات باتری ها، چرخه حیات یک شبکه را مشخص می کند و به همین دلیل بهرهوری از انرژی، فاکتوری مهم برای داشتن طول حیات بیشتر یک شبکه خواهد بود که به منظور رسیدن به این هدف، از خوشه بندی2 استفاده میشود. در پروتکلهای خوشهبندی سرخوشه3 انرژی بسیاری را برای ارسال مصرف میکند، چون علاوه بر ارسال دادههای خود وظیفه ارسال دادههای همسایه خود که جزئی از خوشه می باشند را نیز دارد، که این باعث تسریع در کاهش عمر سرخوشه و به طبع آن کاهش طول عمر و انرژی شبکه میشود.
لذا با سازماندهی گرههای شبکه در خوشهها و کنترل روی تعداد و مکان سرخوشهها و همچنین اندازه خوشهها از نظر تعداد اعضا، میتوان به کارایی بیشتری از انرژی رسید که به افزایش عمر شبکه منتهی میشود. با تغییر پیاپی سرخوشهها در هر دوره از عملکرد شبکهی حسگر، با یک مسئله پیچیده که با روشهای کلاسیک قابل حل نیست مواجه خواهیم شد. هدف این تحقیق کاهش محاسبات مورد نیاز از طریق بکارگیری الگوریتمهای اکتشافی و الگوریتمهای تکاملی است.
به نحوی که به جای استفاده از روشهای صرفا ریاضیاتی در یافتن پاسخ، به کمک الگوریتمهای تکاملی و با استفاده از مفاهیم این حوزه، مسئله را به یک مسئله بهینهسازی تبدیل کنیم. در این مقاله با استفاده از الگوریتم فرهنگی4، تعداد و محل سرخوشهها را بطور بهینه تعیین میکنیم که البته تابع برازش5 بر اساس حداقل انرژی مصرف شده گرههای شبکه در طی هر دوره عملیات ارسال داده است که منجر به ایجاد تعادل در مصرف انرژی سرخوشهها و در نتیجه طولانی تر شدن عمر شبکه میشود.
-1 مقدمه
پیشرفتهای اخیر در سیستمهای میکروالکترومکانیکال، الکترونیک دیجیتال و ارتباطات بیسیم منجر به ظهور شبکههای حسگر بیسیم شده است که شامل تعداد زیادی از حسگرهایی است که هر کدام قابلیت احساس کردن، پردازش و ارسال اطلاعات محیطی را دارند.[1] یک گره حسگر تنها توانایی برقراری ارتباط و انجام محاسبات محدودی را دارد. علاوه بر این، گرهها در شبکههای حسگر بیسیم، میتوانند بطور هماهنگ وظایف پردازش سیگنال را برای بهدست آوردن اطلاعات از یک ناحیه خطرناک و غیر قابل دسترس انجام دهند.[2] منبع انرژی یک گره حسگر توسط یک باطری تامین میشود، که تعویض و شارژ دوبارهی باطری بسیار سخت بوده و مقرون به صرفه نمیباشد. بر این اساس بهینه بودن مصرف انرژی به عنوان مهمترین چالش در شبکههای حسگر محسوب میگردد.[1][3]
این امر موجب گردید تا پروتکلهایی برای این شبکهها طراحی شوند که از نظر مصرف انرژی بهینه و طول عمر شبکه را افزایش دهند. در بین پروتکل های ارائه شده، پروتکل های سلسله مراتبی مبتنی بر خوشه بندی، به طور قابل توجهی باعث صرفهجوئی در مصرف انرژی میگردد. در پروتکل-های بهینهسازی مصرف انرژی، کل شبکه به چندین خوشه افراز میشود و در هر کدام از خوشهها یک گره به عنوان سرخوشه انتخاب میشود. وظیفهی سرخوشه جمعآوری دادههای ارسالی از گرههای آن خوشه، حذف دادههای تکراری، ترکیب دادهها و ارسال آن به گره سینک4 می باشد.
گرهها دادهها را جمع آوری و آنها را به سرخوشه منتقل میکنند و سرخوشه نیز دادههای جمعآوری شده در یک منطقه را از طریق دسترسی چندگانه تقسیم زمانی5 به گره سینک ارسال میکند . در این پروتکلها انتخاب یک گره در هر خوشه به عنوان سرخوشه و ترکیب دادهها به عنوان هدف مطرح است.[4][5] از آنجائی که انرژی مصرفی سرخوشهها بیشتر از گرههای معمولی است از خوشهبندیهای پویا استفاده میشود. در این نوع خوشهبندی پس از هر دوره عملیات ارسال و دریافت یا به عبارت دیگر پس از هر بار اجرای فاز راهاندازی، سرخوشهها عوض شده و گره دیگری بطور تصادفی به عنوان سرخوشه انتخاب میشود.
اما انتخاب تصادفی سرخوشهها ممکن است به توزیع نامناسب آنها در شبکه منتهی شود بدین معنی که در قسمتی از ناحیه تحت پوشش، دو یا چند سرخوشه تجمع کنند در حالی که در منطقههای دیگر هیچ سرخوشهای وجود نداشته باشد.[6] یکی از دغده های امروزی علوم مهندسی حل مسائل با تعداد زیادی از متغیرهای مختلف و بهینه کردن جواب میباشد. در دو دهه اخیر با الهام گرفتن از طبیعت، بازسازی الگویهای طبیعی موجود در آن و با در نظر گرفتن قدرت محاسباتی کامپیوترهای دیجیتال روشهایی ابداع شد تا بتوانند در کمترین زمان ممکن بهترین جوابهای قابل محاسبه را برای مسائل پیچیده چند متغیره پیدا کنند.[9][8][ 7]
از جمله این روش ها میتوان به انواع الگوریتمهای ژنتیک6، ازدحام ذرات7 و فرهنگی اشاره کرد که در اینجا موضوع بحث الگوریتم فرهنگی است. عموما در مسائل از الگوریتم ژنتیک استفاده میگردد که البته ضعف این الگوریتم در این است که در هر تکرار به دلیل استفاده از عملگر جهش برای تولید نسل، نسل جدید ممکن است از نظر برازش نسبت به نسل قبلی در جایگاه پایینتری قرار گیرد و یا خاطرهی بهترین نسل را به حافظه نمیسپارد که این امر موجب افزایش تعداد تکرار میگردد در صورتی که در الگوریتم فرهنگی در هر تکرار، در دو فضای جستجو، فرایند تکامل پی گرفته میشود؛ یکی فضای جمعیت و دیگری فضای اعتقادی برای تنظیم مولفههای فرهنگی. فضای اعتقادی اطلاعات فرهنگی اعضای جمعیت را مدل میکند، در حالی که فضای جمعیت، اعضا را در سطح ژنوم و ژن بررسی میکند. هر دو فضا به صورت موازی سیر تکاملی را طی میکنند در حالی که بر روی یکدیگر تاثیر میگذارند.[10][11]
-2 مدل سیستم و انرژی
شبکه حسگر بیسیم مورد نظر دارای ویژگیهای زیر است:
• گرهها همگی یکسان بوده و در تمام شبکه و در یک ناحیه مربعی شکل بطور یکنواخت توزیع شدهاند.
• ایستگاه پایه در موقعیتی خارج از ناحیه مربع شکل و در فاصله دور قرار دارد. انتخاب موقعیت ایستکاه پایه بستگی به کاربرد دارد.[12]
• کانال مخابراتی متقارن و مدل چند مسیری فرض میشود.
• گرهها قادرند توان ارسال خود را با توجه به فاصله خود تا گیرنده مدنظر تنظیم کنند. که برای حصول اطمینان از پیوستگی شبکه ضروری است.[13]
• گرهها همگی دارای انرژی و توانایی یکسان هستند.
• موقعیت و شناسه تمام گرهها برای ایستگاه پایه معلوم است.
-3 الگوریتم فرهنگی
الگوریتم فرهنگی اولین بار توسط Raynolds & chung درسال 1991 به عنوان یک مدلی از تکامل مولفه های فرهنگی برای استفاده در سیستمهای محاسبات کامپیوتری ارائه شد. بر اساس دیدگاه رینولد فرهنگ به عنوان منبعی از اطلاعات که بر روی رفتار اعضای جمعیت اثر میگذارد مدل شده است. در الگوریتم فرهنگی، فرهنگ ویژگیهای رفتاری عمومی جمعیت را ذخیره کرده سپس این اطلاعات را با یک سری تغییرات طی نسل های مختلف در اختیار همه اعضای جمعیت قرار میدهد.
الگوریتم فرهنگی یک سیستم وراثتی دوگانه است که در دو فضای جستجو فرایند تکامل را دنبال میکند. یکی فضای جمعیت که در اینجا بر اساس الگوریتم ژنتیک است و دیگری فضای اعتقادی برای تنظیم مولفههای فرهنگی. فضای اعتقادی اطلاعات فرهنگی اعضای جمعیت را مدل میکند، در حالی که فضای جمعیت، اعضا را در سطح ژنوم و ژن بررسی میکند. هر دو فضا به صورت موازی سیر تکاملی را طی میکنند در حالی که بر روی یکدیگر تاثیر میگذارند. بین این دو فضا یک پروتکل ارتباطی دو کاناله وجود دارد که یک کانال برای انتخاب گروهی از اعضای جمعیت برای تاثیر گذاری بر فرهنگ و کانال دیگر برای تاثیر فرهنگ بر روی همه اعضای جمعیت مدنظر گرفته شده است.[15]
-3-1 مدلسازی الگوریتم فرهنگی
شکل 1 نحوه ارتباط بین جمعیت و فرهنگ را نشان می دهد، نحوه عملکرد الگوریتم به این صورت است که در هر تکرار اعضای جمعیت توسط تابع هزینه ارزیابی می شوند، سپس با استفاده از یک تابع پذیرش مشخص می شود که کدامیک از اعضای جمعیت نسل فعلی امکان تاثیر گذاری بر فضای فرهنگی را دارند. در مرحله بعد از تجربیات نخبگان فرهنگی برای تنظیم کردن اعتقادات استفاده میشود و در مرحله چهارم از فرهنگ تکامل یافته برای سیر تکاملی جمعیت استفاده می شود.
