بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
مروری بر روشهای خوشهبندی در شبکه حسگر بیسیم با استفاده از الگوریتمهای تکاملی
چکیده
شبکهی حسگر بیسیم از صدها ویا هزاران دستگاه کوچک بنام گرهی حسگر تشکیل شده است. این گرهها بایکدیگر درتعاملند و ظیفه یا وظایف خاصی را انجام میدهند. منابع تغذیهی گرهها غالبا غیرقابل شارژ، غیرقابل تعویض و محدود است لذا اتمام انرژی یک گره مساوی با خاموشی و ازکار افتادن آن گره میشود. برای جلوگیری از خاموشی سریع گرهها وکاهش مصرف انرژی راهکارهای متوعی ارائه شده است که خوشهبندی کاراترین آنهاست. انتخاب چند گره از بین گرههای شبکه بعنوان سرخوشه که مسئولیت جمعآوری داده از سایر گرهها و ارسال آن بعد از فشرده سازی به ایستگاه پایه را برعده دارند خوشهبندی گفته میشود. انتخاب الگوریتمهای مناسب برای خوشهبندی میتواند درکارآیی شبکه تاثیر قابل ملاحظه-ای داشته باشد. آنچه ما دراین مقاله مورد بررسی قرار دادهایم کاربرد الگوریتمهای تکاملی بعنوان تکنیکهای خوشهبندی است. استفاده از الگوریتمهای تکاملی میتواند ساختار خوشه-بندی مناسبی را ایجاد کند.
کلمات کلیدی: شبکه حسگر بیسیم، خوشهبندی، الگوریتم تکاملی، کاهش مصرف انرژی
مقدمه
پیشرفتهای اخیر در زمینه الکترونیک و مخابرات بیسیم توانایی طراحی و ساخت حسگرهایی را با توان مصرفی پایین، اندازه کوچک، قیمت مناسب و کاربریهای گوناگون ایجاد کرده است. این حسگرهای کوچک که توانایی انجام اعمالی چون دریافت اطلاعات مختلف محیطی بر اساس نوع حسگر، پردازش و ارسال آن اطلاعات را دارند، موجب پیدایش ایدهای برای ایجاد و گسترش شبکههای موسوم به شبکه حسگر بیسیم (1WSN) شدهاند. یک شبکه حسگر متشکل از تعداد زیادی گرههای حسگر است که در یک محیط به طور گسترده پخش شده و به جمعآوری اطلاعات از محیط میپردازندلزوماً. مکان قرار گرفتن گرههای حسگر، از قبلتعیینشده و مشخص نیست. چنین خصوصیتی این امکان را فراهم میآورد که بتوانیم آنها را در مکانهای خطرناک و یا غیرقابل دسترس رها کنیم.
از طرف دیگر این بدان معنی است که پروتکلها و الگوریتمهای شبکههای حسگری باید دارای تواناییهای خودساماندهی باشند. دیگر خصوصیتهای منحصر به فرد شبکههای حسگر، توانایی همکاری و هماهنگی بین گرههای حسگر است. هر گره حسگر روی برد خود دارای یک پردازشگر است و به جای فرستادن تمامی اطلاعات خام به مرکز یا به گرهای که مسئول پردازش و نتیجهگیری اطلاعات است، ابتدا خود یک سری پردازشهای اولیه و ساده را روی اطلاعاتی که به دست آورده است، انجام میدهد و سپس دادههای نیمه پردازش شده را ارسال میکند. با اینکه هر حسگر به تنهایی توانایی ناچیزی دارد، ترکیب صدها حسگر کوچک امکانات جدیدی را عرضه میکند. در واقع قدرت شبکههای بی سیم حسگر در توانایی بهکارگیری تعداد زیادی گره کوچک است که خود قادرند سرهم و سازماندهی شوند و در موارد متعددی چون مسیریابی همزمان، نظارت بر شرایط محیطی، نظارت بر سلامت ساختارها یا تجهیزات یک سیستم به کار گرفته شوند.
علاوه بر یک یا چند حسگر،هر گره از شبکه معمولاً مجهز به یک فرستنده و گیرنده رادیویی (یا هر وسیله مخابراتی بی سیم دیگر)، یک میکروکنترلر کوچک، و یک منبع انرژی (معمولا یک باتری) است. اندازه یک گره حسگر بسته به اندازه بستهبندی آن تغییر کرده و تا یک دانه شن قابل کوچکسازی است. یکی از اصلیترین چالشها در این شبکهها منبع انرژی محدود، غیرقابل تعویض وغیرقابل شارژ است. ازاین رو الگوریتمهای مورد استفاده در آن، سعی میکنند مصرف انرژی را به حداقل برسانند.
یکی از تکنیکهای موثر در کاهش مصرف انرژی خوشهبندی است، به این صورت که بجای اینکه هر گره بطور جداگانه اطلاعات خودش را ارسال کند، چند گره بعنوان سرخوشه انتخاب شوند و گرههای نزدیک به هریک از این سرخوشهها با آن تشکیل یک خوشه دهند. اطلاعات اعضای خوشه بعد از فشردهسازی توسط سرخوشه به چاهک ارسال میشود. الگوریتمهای خوشهبندی که معروفترین و خوشنام ترین آن LEACH است باعث افزایش طول عمر شبکه میشوند. همچنین الگوریتمهای تکاملی در سالهای اخیر با موفقیت بعنوان فراابتکاری برای برطرف کردن چالشهای موجود با طراحی مدلهای هوشمندی که با یکدیگر همکاری میکنند تا یک تابع هدف انرژی آگاه مناسب را بهینه کنند، مورد استفاده قرار گرفتهاند. از سوی دیگر بعضی پروتکلها نظیر پروتکل انتخاب پایدار با هدف دیگری در ارتباط هستند: افزایش زمان پایداری تا مرگ اولین گره. هدف ما ارائهی یک روش خوشهبندی جدید برای شبکههای حسگر بیسیم بمنظور کاهش تاخیر، تداخل و مصرف انرژی و افزایش طول عمر شبکه با استفاده از یک الگوریتم فراابتکاری مناسب است.
الگوریتم تکاملی
همان طور که تاریخ الگوریتم های تکاملی نشان می دهد، گونه های زیادی از الگوریتمهای تکاملی وجود دارند. ولی ایده همه آنها یکی است: با داشتن جمعیتی از گونهها، فشار محیطی باعث انتخاب می شود (القاء بهترین) و این افزایش شایستگی جمعیت را نتیجه می دهد. با داشتن یک تابع کیفیتی که می خواهیم بیشینه شود، می توان مجموعه ای از جواب های کاندید را به طور تصادفی تولید کرد و تابع کیفیت را به عنوان معیاری برای محاسبه شایستگی به کار برد – (هر چه بیشتر، بهتر) بر اساس این شایستگی ، بعضی از کاندیدهای بهتر انتخاب می شوند، تا به عنوان هسته ای برای تولید نسل بعد به کار روند. بر روی این کاندیدها ترکیب و یا جهشِ اعمال می شود. ترکیب بر روی دو یا بیشتر کاندید اعمال می شود (والدین) و نتیجه آن تولید فرزند (فرزندانی) است.
اعمال ترکیب و جهش باعث تولید مجموعه جدیدی می شود که با مجموعه قبلی (والدین) رقابت می کنند تا در نهایت برنده ها در نسل بعدی ظاهر شوند. این کار می تواند ادامه پیدا کند تا یک کاندید با ویژگی های کافی (جواب) به دست بیاید و یا اینکه محدودیتهایی که از قبل برای مسئله تعریف کرده ایم، ارضا شوند. در این عمل دو نیروی اصلی وجود دارد که پایه سیستم تکاملی است:
عملگرهای تغییر (ترکیب و جهش) که باعث ایجاد گوناگونی لازم و در نتیجه نوآوری می شود. انتخاب که نیرویی است که کیفیت را به جلو می برد.
ترکیب تغییر و انتخاب باعث بهتر شدن مقادیر شایستگی در جمعیت ها می شود. با مشاهده روند حرکت جمعیت می توان تکامل به سوی بهینگی را مشاهده کرد. تکامل به عنوان فرایند تطبیق بیان می شود. از این دید، شایستگی به عنوان هدف اصلی که باید بهینه شود مطرح نیست، بلکه عبارتی است که نیازمندی کل محیط را بیان میکند، هرچه این نیازمندی ها بیشتر ارضا شوند، نتیجه در تعداد بیشتری از اعضای جمعیت خود را نشان می دهد. عمل تکامل باعث می شود که جمعیت با محیط خود بیشتر و بیشتر سازگار شود.
بسیاری از اجزای فرآیند تکامل اتفاقی6 هستند. این اجزا در زمان انتخاب موجوداتی که مناسب تر7 هستند، احتمال انتخاب بیشتری دارند، هر چند در بیشتر اوقات، موجودات ضعیف تر هم شانس انتخاب شدن و زنده ماندن را دارند. اکثر اوقات موجودات به طور تصادفی برای ترکیب از جمعیت خارج می شوند. این مطلب در مورد تغییرات نیز صادق است.
الگوریتم تکاملی مبتنی بر جمعیت است.
الگوریتم تکاملی از ترکیب استفاده می کند تا اطلاعات گونه های بیشتری را در یک گونه خلاصه کند. الگوریتم تکاملی اتفاقی است.
گونه های مختلف الگوریتم های تکاملی همگی از طرح کلی که ارائه شد، پیروی میکنند و فقط در جزئیات تکنیکی متفاوت هستند.
الگوریتم های تکاملی در مقایسه با سایر الگوریتم های بهینه سازی برتری هایی دارند که موجب شده است به طور گسترده مورد استفاده قرار بگیرند. به عنوان مثال، این الگوریتم ها، نیاز به معرفی کامل مسئله ندارند و تنها با داشتن اطلاعات چندی در مورد تعریف مسئله می توانند کار کنند. همچنین محدودیتی درمورد تابع شایستگی ندارند و لزومی ندارد که این تابع
مثلاً مشتق پذیر باشد.
علاوه بر این موارد، چون الگوریتم های تکاملی دارای جمعیتی از موجودات هستند و روی بخش های مختلفی از جمعیت به طور موازی کار می کنند، احتمال کمتری برای قرار گرفتن در بهینه های محلی دارند. این قابلیت الگوریتم های تکاملی اجازه می دهد که کار بهینه سازی را به طور موازی روی چندین بخش جمعیت انجام داد. به عنوان نتیجه این ویژگی گفته می شود که الگوریتم های تکاملی روی جمعیت های "فضول" خوب عمل میکنند. این گونه جمعیت ها دارای تعداد زیادی بهینه های محلی هستند. الگوریتم های تکاملی در این بهینه های محلی گیرنمی کنند و معمولاً می توانند در نهایت به بهینه ترین جواب برسند. [1]
بررسی روشهای تکاملی در خوشهبندی گرههای شبکه حسگر بیسیم
در پروتکل LEACH [2] یک گره به عنوان CH با یک احتمال P انتخاب می شود و هر گره بدون کلاسترها، سرخوشه خود را انتخاب می کند که به وسیله آن به کمترین میزان مصرف انرژی برسد. نقش سرخوشه در میان تمام گره های سنسور برطبق یک عدد تصادفی T که میان 0و1 است می چرخد. یک گره می تواند به عنوان سرخوشه انتخاب شود اگر در مرحله جاری عدد آن کمتر از حد آستانه باشد.
از آنجایی که طرح های نوع LEACH به عنوان شبکه های حسگر بی سیم همگن فرض شده اند، SEP[3] یک مسیریابی سلسله مراتبی را در شبکه های سنسور یکسان ایجاد می کند، که درصدی از جمعیت سنسورها به یک مقدار انرژی اضافه نسبت به گره های معمولی در یک شبکه یکسان مجهز شده اند.[3] دراین مقاله با تغییر حدآستانه به نتایج قابل توجهی دست یافته است، هرچند که استفاده از گرههایی با قابلیتهای بیشتر همواره ممکن نیست. در این دو طرح، LEACH و SEP، عنصر احتمال و تصادف نقش مهمی را ایفا میکند که بهتر است این نقش کمرنگتر شود.
مشکل خوشه بندی به عنوان یک مسئله NP-hard مطرح شده است، رشته های گوناگون از روش هایی نظیر محاسبات تکاملی به دنبال پیشنهاد و ارائه یک الگوریتم جدید هستند. یک بازبینی کلی از جزئیات الگوریتم های خوشه بندی تکاملی در مقاله [4] تهیه شده است. که علاوه برآن ها کاربردهای تکامل تفاضلی (DE) به عنوان تکنیک خوشه بندی قوی تر و سریع و کاملا اتوماتیک که می تواند این مشکل را با طرح های خوشه بندی قدیمی حل کند ارائه شده است. در شبکه های حسگر بی سیم CI و شاخه اصلی آن EAها برای چند چالش به کار رفته اند. یک برآورد کلی (Survey) را می توانید در مقاله [5] پیدا کنید. در مقاله حاضر، یک بازنگری از رشته ای از مسیریابی برمبنای خوشه بندی فراابتکاری مبتنی بر جمعیت در شبکه های حسگر بی سیم می باشد که با تمرکز بر روی الگوریتم تکاملی انجام شده است.
دیگر الگوریتم فرا ابتکاری مبتنی بر جمعیت که اخیرا برای مشکل مسیریابی بر مبنای خوشه بندی در شبکه های حسگر بی سیم توسعه یافته است، الگوریتم جستجوی تطبیقی ,(HAS)[13] است که برای بهبود بخشیدن به طول عمر و کاهش انرژی مصرفی در مسیریابی خوشه بندی در شبکه های حسگر بی سیم توسعه یافته است .[14] تابع تناسب جستجوی تطبیقی به صورت زیر تعریف می شود:
که در آن f1 بیشترین فاصله اقلیدوسی میان گره هاست و به صورت زیر تعریف می شود:
f2 که نرخ انرژی تمام گره های زنده در شبکه است با کل انرژی جاری هر CH در مرحله جاری است و به صورت زیر تعریف می شود:
