بخشی از مقاله
چکیده-
پیشرفت در تکنولوژیهای ارتباطی، در دهههای اخیر سبب رشد سریعی در تحقیقات شبکههای بیسیم و ایجاد الگوریتمها وپروتکلهای ارتباطی شده است. انتخاب صحیح پروتکل مسیریابی، باعث افزایش کارایی و طول عمر شبکه و کاهش مصرف انرژی میشود. خوشهبندی یکی از رایجترین تکنیکها در مسیریابی است. در این مقاله، از الگوریتم کلونی زنبور عسل مصنوعی برای انتخاب سرخوشهها استفاده میکنیم. الگوریتم زنبور عسل شبیهسازی رفتار هوشمندانه جستجوی غذای جمعیت زنبورهای عسل در طبیعت است. این الگوریتم با ثابت درنظر گرفتن تعداد سرخوشهها در هر دور به خوبی در تکنیک خوشهبندی کار میکند. الگوریتم پیشنهادی از نظر مصرف انرژی و طول عمر با الگوریتمهای پیشین مقایسه شد. نتایج آزمایشها نشان میدهد که الگوریتم زنبورعسل نسبت به الگوریتم LEACH-SWDN در مرگ اولین گره، نیمی از گرهها و مرگ %95 گرهها به ترتیب %57، %37 و %35 بهتر عمل میکند.
کلید واژه- الگوریتم زنبور عسل، خوشهبندی، شبکه حسگر بیسیم، مسیریابی
-1 مقدمه
شبکههای حسگر بیسیم شامل تعدادی گره حسگر است. این شبکهها در سالهای اخیر توجه زیادی به خود جلب کرده-اند.[3-1] این شبکهها برای محیطهای بسیار بزرگ بسیار خوب عمل میکنند. دادههای ایجادشده در محیطهای نظامی، تشخیص مواد شیمیایی و اندازه گیری زلزله توسط گرههای حسگر به سادگی جمعآوری میشود. گرههای حسگر دادههای موجود در ناحیه حسگری خود را به کمک سایر گرههای حسگر به ایستگاه پایه ارسال میکنند. ایستگاه پایه بر اساس دادههای دریافتی از گرههای حسگر میتواند کل محیط مورد نظر را رصد کند. به دلیل ذات توزیعشده این شبکهها، اجرای سازماندهی برای همکاری بین گرههای حسگر برای یک ارتباط مداوم نیاز است.
گرههای حسگر به راحتی قابل پیکربندی برای هر برنامه کاربردی است. به هرحال، این گرهها دارای باتریهای غیرقابل تعویض با انرژی محدود است. بنابراین قدرت پردازشی و ارتباطی محدودی برای هر گره وجود دارد. برای غلبه بر این محدودیت، تکنیکهای نوآورانهای برای ارتباطات مطمئن و افزایش طول عمر شبکه نیاز است .[4] برای جمعآوری دادههای حسگر که به صورت مداوم در حال تولید است، مکانیزم مسیریابی خوشه بندی مناسب است. یکی از پروتکلهای خوشه بندی رایج، [5] LEACH نام دارد که دو فاز اجرایی بر پایه ارتباطات تکگامه از سرخوشه به ایستگاه پایه است. این پروتکل به صورت تصادفی سرخوشهها را ایجاد میکند و فرایند تجمیع داده درون هر خوشه توسط سرخوشه انجام می-شود. [6] LEACH-C، توسعهای از پروتکل LEACH برای افزایش کارایی مصرف انرژی است. [7] PEGASIS،
پروتکل دیگری بر پایه خوشهبندی است که شبیه به LEACH است اما مصرف انرژی کمتری در هر دور دارد. اگرچه LEACH-C و PEGASIS عملکرد بهتری نسبت به الگوریتم LEACH ارائه میدهند ، اما برای اجرای این الگوریتمها موقعیت گرههای حسگر باید از قبل مشخص باشد. از آنجایی که گرههای حسگر معمولاً به صورت تصادفی پخش میشوند و سختافزار سیستمهای موقعیتیاب جهانی اندازه و هزینه گرههای حسگر را افزایش می-دهد، این پروتکلها برای بسیاری از کاربردهای WSN مناسب نیستند. بنابراین در این مقاله الگوریتمهای بر پایه LEACH، مانند [8] ALEACH، [9] LEACH-DCHS و LEACH- [10] SWDN را مورد بررسی قرار دادیم.
در این مقاله، ما یک نگرش خوشهبندی متمرکز برای انتخاب سرخوشهها استفاده کردیم. این فرایند خوشهبندی استفادهشده در روش ما روی ایستگاه پایه کار میکند. درحالی که بعضی از الگوریتمها مثل LEACH، فرایند خوشهبندی را به روش توزیع-شده انجام میدهند. سختافزار ایستگاه پایه معمولاً قویتر و خبرهتر از سایر عناصر شبکه مثل سرخوشهها یا گرههای حسگر است. بنابراین، به دلیل این که وظیفه اصلی گرههای حسگر، حسکردن محیط پیرامون و گزارشدهی است، بهتر است سربار فرایند مسیریابی از گرههای حسگر به ایستگاه پایه منتقل شود. روش خوشهبندی ما از الگوریتم مسیریابی فراابتکاری کلونی زنبور عسل مصنوعی - ABC-RA - استفاده میکند. در نگرش ABC-RA پیشنهادی هدف اصلی بهینهسازی مصرف انرژی با استفاده از انتخاب سرخوشهها به یک روش متوازن است. ادامه مقاله به این شکل سازماندهی میشود: بخش دو شامل چهار قسمت است. در این بخش مفاهیم الگوریتم زنبور عسل، جزئیات مسیریابی بر پایه خوشهبندی، نگرش پیشنهادی و ارزیابی عملکرد آمده است و در بخش نهایی نتیجهگیری آمده است.
-2 پروتکل مسیریابی پیشنهادی بر اساس کلونی زنبور عسل مصنوعی
-1-2 الگوریتم کلونی زنبور عسل مصنوعی
الگوریتم کلونی زنبورعسل، یک الگوریتم هوشمند بر پایه جمعیت است. این الگوریتم از رفتار هوشمندانه یافتن غذای زنبوران عسل الهام گرفته شده است .[11] در الگوریتم ABC-RA، سه گروه در کلونی زنبور عسل مصنوعی وجود دارد: ناظرها - onlookers - ، دیدهبانها - scouts - و زنبوران کارگر - workers - که هر یک از زنبورها نمایانگر یک موقعیت در فضای جستجو هستند. زمانی که شبکه شامل n حسگر سرخوشه است، زنبورها در فضای جستجو با n بعد پرواز میکنند. ABC-RA یک جمعیتی از زنبورها را برای یافتن سرخوشهها به کار میگیرد. یک زنبور در حال انتظار در ناحیه رقص برای انتخاب یک منبع غذایی یک ناظر است و زنبور عسلی که به سمت منبع غذایی که از قبل توسط زنبور ناظر بازدید شده است، میرود زنبور کارگر نامیده میشود.
زنبوری که جستجوی تصادفی انجام میدهد، زنبور دیدهبان نامیده میشود. یک راهحل شدنی موقعیت منبع یک غذا را در مسئله بهینهسازی نمایش میدهد و مقدار شهد یک منبع غذا متناظر با کیفیت - برازش - راهحل مربوطه آن است. در الگوریتم ABC-RA نیمه اول کلونی شامل زنبورهای کارگر و نیمه دوم شامل زنبورهای ناظر است. اولین موقعیتهای منبع غذا به صورت تصادفی تولید شده است. که هر زنبور کارگر برای یک منبع غذا برگزیده میشود. سپس هر زنبور کارگر یک منبع غذای همسایه با منبع غذای مربوطه جاری خودش با استفاده از رابطه - 1 - تعیین میکند و مقدار شهد منبع غذای جدید برای هر تکرار محاسبه میشود. اگر مقدار شهد منبع غذای جدید بیشتر از قبلی باشد سپس زنبور کارگر به سمت منبع غذای جدید حرکت می-کند، در غیر اینصورت با همان منبع غذای قدیمی ادامه میدهد.
در این بخش مختصری از الگوریتم ABC-RA، تعریف این الگوریتم در مسئله مسیریابی شبکههای حسگر بیسیم و الگوریتمهای مبتنی بر خوشهبندی مورد مقایسه در این مقاله را ارائه میدهیم. در ادامه نتایج آزمایشات آمده است. در آخر نتیجه-گیری از کار انجامشده بیان شده است. که یک عدد تصادفی بین [-1 ,1] است، vi یک راهحل کاندید است، xi راهحل جاری است و xk یک راهحل همسایه است و j {1, 2, ..., D} اندیسی است که به صورت تصادفی انتخاب میشود که D بعد بردار راهحل است. زنبورهای کارگر اطلاعات مربوط به منابع غذایی خودشان را پس از اینکه همه آنها فرایند جستجو را تکمیل کردند، با زنبورهای ناظر به اشتراک میگذارند. یک زنبور ناظر، اطلاعات شهد به دست آمده از همه زنبورهای کارگر را ارزیابی میکند و یک منبع غذایی را با یک احتمال مرتبط با مقدار شهد خودش توسط رابطه - 2 - انتخاب میکند. رابطه - 2 - به عنوان روش انتخاب چرخ رولت شناخته میشود که شانس بالاتری برای انتخاب شدن کاندیدهای بهتر فراهم میکند.
که fiti ، مقدار برازش راهحل i است که با مقدار شهد منبع غذایی در موقعیت i متناسب است و sn تعداد منابع غذایی مساوی با تعداد زنبورهای کارگر است. همین که همه زنبورهای ناظر منابع غذایی خودشان را انتخاب کردند، هر کدام از آنها، یک منبع غذایی همسایه با منبع غذایی انتخابشدهاش تعیین می-کند و مقدار شهد آن را محاسبه میکند. اگر مقدار شهد موقعیت جدید بزرگتر از موقعیت قبلی باشد، زنبور ناظر موقعیت جدید را نگهداری میکند و موقعیت قدیمی را فراموش میکند؛ در غیراینصورت راهحل قدیمی را حفظ میکند. زمانیکه یک منبع غذایی توسط زنبورهای عسل کارگر و ناظر سبب اتلاف انرژی در شبکه شود، زنبور کارگر تبدیل به زنبور دیدهبان میشود. همه موقعیتها نمیتوانند از طریق تعداد مشخصی چرخه که پارامتر ترک راهحل نام دارد، بیشتر بهبود یابند. منبع غذایی به دست آمده در این تعداد دور مشخص به عنوان منبع غذایی ترکشده و زنبور کارگر آن منبع، دیدهبان میشود. در این وضعیت، زنبور دیدهبان یک راهحل جدید به صورت تصادفی تولید میکند. مراحل الگوریتم ABC-RA در شکل 1 آمده است.
-2-2 پروتکل مسیریابی WSN با استفاده از الگوریتم کلونی زنبور عسل مصنوعی
در این مقاله، سناریوی پروتکل مسیریابی WSN با استفاده از الگوریتم برای شبکههای بدون سیستم موقعیتیاب جهانی ایجاد شده است. هدف اصلی عملیات این پروتکلها، افزایش طول عمر شبکه توسط ماکزیمم سازی تعداد بستههای انتقالی در ماکزیمم دور ممکن با خوشهبندی است. مکانیزم خوشهبندی پروتکل پیشنهادی بر پایه تکنیک خوشهبندی پروتکل LEACH است. در این پروتکل سرخوشهها فرایندهای تجمیع داده خوشههای خود را انجام میدهند. تفاوت عملیات اصلی بین پروتکلهای پیشنهادی و LEACH در فرایند انتخاب سرخوشه - CH - است. در پروتکل پیشنهادی انتخاب سرخوشه توسط الگوریتم ABC-RA انجام میشود، در حالیکه LEACH از متد انتخاب تصادفی استفاده میکند. پروتکل خوشهبندی شبکه پیشنهادی بر پایه الگوریتم کنترل متمرکز است که در ایستگاه پایه پیادهسازی شده است. ایستگاه پایه یک گره با منبع انرژی نامحدود است.
