در این کار، الگوریتم کوچ پرندگان را به صورت نیمه متمرکز با توجه به اطلاعات مکانی و انرژی باقیمانده گرههای حسگر خوشهها اجرا میشود. فرمول بهینگی در این الگوریتم به شکل زیر است.
(۲-۵) |
که در فرمول x1 ، x2 ، x3 و حدود مسئله به شرح زیر است:
(۲-۶) | |
(۲-۷) | |
(۲-۸) | |
(۲-۹) | |
(۲-۱۰) |
در این فرمولها تعداد عضای خوشه، و مختصات اقلیدسی اعضای خوشه انرژی اعضای خوشه و انرژی ذرات انتخاب شده به عنوان Particle در فرمول هستند.
در فرمول (۲-۸) مقدار ، تعداد دفعاتی است که یک حسگر به عنوان سرخوشه انتخاب شده است.
این الگوریتم یک گره دستیار و یک گره سرخوشه برای هر خوشه مشخص میکند که گره دستیار وظیفه جمعکردن اطلاعات اولیه و اجرای الگوریتم کوچ پرندگان و مشخص کردن سرخوشه را در هر دورهی زمانی به عهده دارد. انتخاب گره دستیار برای هر خوشه به صورت تصادفی است. گرهی دستیار خوشه اطلاعاتی مانند مکان، انرژی، تعداد سر اتصال هر گره در خوشه را برای اجرای الگوریتم کوچ پرندگان جمع آوری میکند [۵۰].
در فصل بعد به توضیح الگوریتم و تابع بهینگی پیشنهادشده اختصاص دارد که دلایل انتخاب تابع بهینگی توضیح داده می شود. بعد از آن ذکر ویژگیهای شبکهی حسگر بیسیم که در نرمافزار OMNET++ شبیهسازی شده است گفته می شود.
فصل سوم : الگوریتم پیشنهادی
همانطور که گفته شد، خوشهبندی گرههای حسگر بیسیم شبکه یکی از روشهای پرکاربرد برای مسیریابی در شبکه های حسگر بیسیم است. خوشهبندی در الگوریتمهای توزیعشده بر اساس اطلاعات محلی انجام می شود. و انتخاب سرخوشه مناسب همیشه از مسائل مهم مطرح شده است. یکی از راههای انتخاب سرخوشه، استفاده از الگوریتمهای هوشمند ابتکاری و فراابتکاری است.
در این الگوریتم سرخوشه مناسب از بین گرههای حسگر موجود در خوشه با بهره گرفتن از اطلاعات محلی جمعآوری شده به وسیله الگوریتم هوشمند فراابتکاری کوچ پرندگان برای هر خوشه مشخص می شود.
توضیح الگوریتم به دو بخش تقسیم میشود؛ ۱- توضیح تابع شایستگی الگوریتم کوچ پرندگان که مورد استفاده قرار گرفته است. ۲- توضیح مراحل اجرایی الگوریتم پیشنهاد شده در شبکههای حسگر بیسیم که مورد استفاده قرار گرفته است.
شرح تابع شایستگی به کار رفته در الگوریتم کوچ پرندگان
همانطور که در فصل قبل به آن اشاره شد، الگوریتم کوچ پرندگان برای انتخاب ذرهی بهینه نسبت به شرایط مسئله از تابع شایستگی استفاده میکند. تابع شایستگی به بررسی صفاتی از ذرات میپردازد که در انتخاب مناسب ذرهی بهینه مهم است.
الگوریتم کوچ پرندگان برای انتخاب سرخوشهی مناسب از تابع بهینگی به شکل زیر استفاده میکند.
( ۳ – ۱ ) |
در این تابع متغیرهای x1 ، x2 ، x3 و x4 هر کدام فرمولی هستند که برای وارد کردن صفتی منحصر به فرد از گرهها در محاسبات بهینگی از آن استفاده شده است.
پارامترهای α۱ ، α۲ و α۳ اعداد ثابتی بین صفر و یک هستند که درصد اهمیت دادن به هر فرمول را در فرمول تابع بهینگی نهایی مشخص میکنند.
همانطور که مشخص است تابع بهینگی واحد متریک خاصی ندارد و بدون عدد است و فقط تفاوت مقداری را برای هر ذره با توجه به متغیرهای داخلی خود نشان میدهد.
در نتیجه هر کدام از فرمولهایی که مربوط به متغیرها میشود باید طوری محاسبه شود که جواب به دست آمده از آنان فاقد واحد متریک خاصی باشد.