بخشی از مقاله
چکیده:
خوشهبندی یک نوع معماری سلسلهمراتبی، از شبکههای حسگر بیسیم است. در خوشهبندی محدوده عملیاتی شبکه، به بخشهای مجزایی به نام خوشه تقسیم میشود. هر خوشه شامل چندین گره حسگر است، با انتخاب گرهای به نام سرخوشه، وظایف مدیریت درون خوشه و انتقال دادهها به ایستگاه پایه به سرخوشه محول میشود. عملیات انتقال دادهها از خوشهها به ایستگاه پایه، با ایجاد یک مسیر فرضی توسط سرخوشهها انجام میشود. همین موضوع باعث افزایش بار کاری انتقال دادهها، برای سرخوشههای نزدیک به ایستگاه پایه میشود و اتلاف انرژی سرخوشهها را بدنبال دارد.
در خوشهبندی با اندازههای غیریکسان، اندازه خوشههای نزدیک به ایستگاه پایه کوچکتر در نظر گرفته میشود تا وظایف درون خوشهای و مصرف انرژی سرخوشه کاهش یابد. انتخاب صحیح گره سرخوشه، تعیین اندازه یک خوشه و تعیین تعداد اعضای هر خوشه، به منظور بهینهسازی مصرف انرژی گرهها، یک مساله بهینهسازی میباشد. در این مقاله یک روش خوشهبندی در اندازههای غیریکسان مبتنی بر الگوریتم بهینهسازی رفتار گروه میگوی آشوبی ارائه گردیده است. نتایج آزمایشها نشاندهنده عملکرد بهتر الگوریتم پیشنهادی در افزایش طول عمر شبکه حسگر بیسیم نسبت به الگوریتمهای موجود میباشد.
-1 مقدمه:
مهمترین عنصر یک شبکه حسگر بیسیم - WSN2 - گره حسگر است. گرههای حسگر در یک محیط عملیاتی مشخص با توجه به قابلیتهای خود پراکنده میشوند. هدف شبکه حسگر، جمعآوری دادهها توسط گرهها از محیط و انتقال اطلاعات به ایستگاه پایه جهت بررسی و نظارت میباشد. در بیشتر کاربردها، گرههای یک شبکه حسگر بیسیم در محیطهای نظامی و یا غیرقابل دسترس توزیع میشوند که امکان تعویض یا شارژ مجدد باتری گرهها وجود ندارد. با توجه به محدودیت انرژی در گرهها، روشهای بهینهسازی مصرف انرژی در شبکههای حسگر بیسیم بسیار مورد توجه قرار گرفته است 1]، 2، .[3 مصرف انرژی در گرهها به نحوه ارتباطات بین گرهها وابسته است، نحوه ارتباط بین گرهها در معماری شبکه تعریف میشود.
خوشهبندی، یک معماری از شبکههای حسگر بیسیم است. در این معماری گرهها در بخشهایی به نام خوشه سازماندهی میشوند. در هر خوشه یک گره به عنوان سرخوشه3، وظیفه جمعآوری دادههای گرههای دیگر موجود در خوشه و ارسال آنها به ایستگاه پایه را برعهده دارد 4]، .[5 الگوریتمهای خوشهبندی به طور معمول سه گام اصلی دارند: -1 انتخاب سرخوشه -2 شکلگیری خوشه - پیوستن گرههای دیگر به خوشه - -3 انتقال دادهها. در گام انتخاب سرخوشه، برخی از گرهها توسط یک روش مشخص شده به عنوان سرخوشه انتخاب میشوند.
در گام شکلگیری خوشهها، گرههای که سرخوشه نشدهاند براساس معیاری - مانند معیار فاصله - ، یک سرخوشه را انتخاب کرده و عضو آن خوشه میشوند. در گام انتقال داده، شبکه با استفاده از یک روند تکراری انتقال دادهها، مورد آزمایش و بررسی قرار میگیرد 1]، .[6 برای هر گره حسگر یک محدوده دایرهای شکل به عنوان ناحیه همسایگی گره تعریف میشود. این محدوده، ناحیهای است که یک گره امکان تبادل داده را با دیگر گرهها در آن داراست. شکل 1 محدوده همسایگی یک گره را با شعاع r نشان میدهد. گرههای داخل محدوده دایره - نقاط آبی رنگ - به عنوان همسایه گره محسوب میشوند. 7]، .[8
الگوریتمهای خوشهبندی از نظر اندازه یک خوشه به دو دسته یکسان و غیریکسان 4 تقسیم میشوند. اندازه یک خوشه همان شعاع همسایگی گره سرخوشه میباشد. در روشهای یکسان این اندازه برای تمام سرخوشهها یکسان میباشد. اما در روشهای غیریکسان شعاع همسایگی برای هر سرخوشه میتواند متفاوت باشد .[9] ایده الگوریتمهای خوشهبندی غیریکسان، کاهش وظایف درون خوشهای، سرخوشههای نزدیک به ایستگاه پایه است. در خوشهبندی غیریکسان، اندازه خوشه برای سرخوشههای نزدیک به ایستگاه پایه، به تناسب فاصله تا ایستگاه پایه، کوچکتر انتخاب میشود که موجب کاهش تعداد گرههای عضو خوشه و در نتیجه باعث کاهش وظایف درون خوشهای و صرفهجویی در انرژی سرخوشه میشود .[10] شکل 2 یک نمونه از خوشهبندی غیریکسان و نحوه ارسال دادهها به ایستگاه پایه را نشان میدهد.
در این مقاله یک روش خوشهبندی با اندازههای غیریکسان بر مبنای الگوریتم فرامکاشفهای گروه میگوی آشوبی ارائه شده است. به طور معمول موقعیت گرهها در محیط عملیاتی با تولیدکنندههای اعداد تصادفی مقداردهی میشوند. یکی از مشکلات تولیدکنندههای اعداد تصادفی این است که قادر به باز تولید رشته اعداد تصادفی تولید شده، نمیباشند. اما توابع آشوب این امکان را فراهم میسازند تا با در اختیار داشتن تابع نگاشت آشوب و مقدار اولیه تابع، اعداد تصادفی دوباره تولید شوند .[11] ساختار ادامه مقاله به شرح زیر است: در بخش دوم کارهای مرتبط بررسی شده است. روش پیشنهادی در بخش سوم مطرح شده است. در بخش چهارم نتایج آزمایشها نشان داده شده است و نتیجهگیری و کارهای آینده در بخش پنجم مطرح گردیده است.
-2 مروری بر کارهای مرتبط
روشهای بسیار زیادی برای خوشهبندی در شبکههای حسگر بیسیم معرفی شدهاند، از معروفترین و اولین الگوریتمهای خوشهبندی، الگوریتم خوشهبندی LEACH5 است. این روش از چندین مرحله تکراری تشکیل شده است. گام انتخاب سرخوشه در این الگوریتم از یک روش کاملا تصادفی استفاده میکند. در این روش برای هر گره حسگر یک عدد تصادفی بین صفر و یک تولید میشود سپس این عدد با خروجی یک تابع مقایسه میشود، اگر عدد تصادفی گره، از مقدار تابع کمتر باشد گره به عنوان سرخوشه انتخاب میگردد. برای گرهای که قبلا سرخوشه بوده است مقدار خروجی تابع صفر است. مزیت این روش سربار محاسباتی پایین در انتخاب سرخوشه میباشد اما انتخاب سرخوشه در این روش بدون درنظر گرفتن انرژی باقیمانده گره انجام میپذیرد. همچنین توزیع سرخوشهها کاملا تصادفی میباشد و میزان تراکم گرهها نقشی در انتخاب سرخوشه شدن گرهها ندارد .[12]
الگوریتم EAUCF6 یک روش خوشهبندی توزیعشده با اندازه خوشههای غیریکسان براساس رویکرد فازی میباشد. ایده این روش پیداکردن یک شعاع همسایگی مناسب برای هر گره با در نظرگرفتن میزان انرژی باقیمانده گره و فاصله گره تا ایستگاه پایه، میباشد. در ابتدا با یک روال تصادفی برخی از گرهها برای سرخوشه شدن کاندید میشوند. هر گره کاندید در محدوده همسایگی خود با گرههای کاندید دیگر با توجه به انرژی باقیمانده رقابت میکند و گره با انرژی باقیمانده بیشتر پیروز این رقابت خواهد شد که به عنوان سرخوشه انتخاب میشود. در گام شکلگیری خوشه، گرههای دیگر به سرخوشه نزدیکتر ملحق میشوند .[10]
الگوریتم TPSO-CR7، یک روش خوشهبندی و مسیریابی براساس الگوریتم بهینهسازی ازدحام ذرات - PSO - میباشد. در این الگوریتم به خوشهبندی و مسیریابی به عنوان دو مساله بهینهسازی جدا از هم نگاه میشود. در خوشهبندی هدف یافتن یک مجموعه بهینه از سرخوشههایی است که باعث کاهش اتلاف انرژی شود. همچنین در مسیریابی از یک تابع ارزشگذاری برای بدست آوردن یک درخت مسیریابی بهینه در بین سرخوشهها استفاده میشود. در هر دو بخش از روش ازدحام ذرات برای بهینهسازی استفاده میشود.[13]
-3 روش پیشنهادی
در این مقاله از رفتار غذایابی گروه میگوها آشوبی8 برای خوشهبندی یک شبکه حسگر بیسیم استفاده شده است. در رفتار غذایابی میگوها، موقعیت یک میگو تا غذا و تراکم بقیه میگوها به عنوان دو پارامتر در بهینهسازی مساله استفاده میشود 11]، .[14 رفتار غذایابی یک میگو مانند رفتار یک گره حسگر در انتخاب سرخوشه میباشد. برای یک گره حسگر مطلوب است که سرخوشه در کمترین فاصله از آن قرار داشته باشد، این پارامتر برای موقعیت غذا و میگو نیز برقرار است.
