بخشی از مقاله
چکیده امروزه با توجه به کاربردهای مختلف شبکههای حسگر بیسیم در زمینههای مختلف، افزایش طول عمر این شبکهها از اهمیت زیادی برخوردار است. پژوهشهای انجام شده نشان داده است که پروتکلهای مسیریابی مبتنی بر خوشهبندی بهترین کارایی را از لحاظ افزایش طول عمر شبکه و پوشش شبکهای دارا میباشند. اما با توجه به اینکه خوشهبندی جزو مسایل NP-complete میباشد، الگوریتم جامع و سریعی که بتواند این مساله را در زمان چندجملهای حل کند وجود ندارد.
از این رو در این مقاله الگوریتمی برای خوشهبندی ارایه میشود - CME2 - که بر اساس الگوریتم تخمین توزیع و بهینهسازی مارکوف گرههای همسایه را مییابد و سعی دارد در هر مرحله مناسبترین سرخوشهها را از لحاظ سطح انرژی و نزدیکی به ایستگاه پایه و نزدیکی به مرکز ثقل خوشه انتخاب کند. در نهایت کارایی الگوریتم پیشنهادی مورد ارزیابی قرار گرفته و از لحاظ طول عمر شبکه و مقدار انرژی مصرفی با چند الگوریتم دیگر مقایسه شده که در همهی موارد نتایج ارزیابیها نشاندهندهی کارایی بالای الگوریتم ارایه شده نسبت به سایر روشهای شبیهسازی شده است.
.1 مقدمه
پیشرفت تکنولوژی مخابرات و صنعت قطعات الکترونیکی در سالهای اخیر منجر به ساخت حسگرهای کوچک و ارزان شده که از طریق شبکه حسگر بیسیم با یکدیگر در ارتباطند [1] این ریزحسگرها جمعآوری اطلاعات در مناطق دورافتاده و مکانهایی که برای اکتشافات انسانی مناسب نیستند را فراهم کرده است .در این شبکهها هر گره بطور مستقل و بدون دخالت انسان کار میکند .گرهها از لحاظ فیزیکی بسیار کوچک و دارای محدودیتهایی در قدرت پردازش، انرژی و غیره هستند که از این میان انرژی حیاتیترین عامل در تداوم حیات شبکههای حسگر است زیرا برای پوشش منطقهای وسیع با استفاده از این حسگرها همواره با محدودیت طول عمر این شبکهها مواجه هستیم و امکان آسیب دیدن شبکه با از بین رفتن گرهها خطر بزرگی به شمار میرود.
به محض اینکه انرژی گرهی به پایان میرسد، از کار افتاده و از چرخهی فعالیت شبکه خارج میشود. در بسیاری از موارد خاموش شدن یک گره موجب از کار افتادن کل شبکه میشود. به همین دلیل محدودیت انرژی منشأ بسیاری از مباحث پژوهشی در این زمینه شده است . [3] یکی از راههای مناسب برای بهینهسازی انرژی گرههای حسگر، خوشهبندی است .[4] خوشهبندی روشی برای سازماندهی وگروهبندی عناصر و داهها بهصورت خوشههایی است که عناصر درون هر خوشه بر اساس شباهت آنها در مقادیر برخی از خصوصیاتشان، بیشترین شباهت را نسبت به یکدیگر و کمترین شباهت را نسبت به عناصر موجود در خوشههای دیگر داشته باشند .
[5] ایجاد کنترل روی تعداد و مکان سرخوشه ها و همچنین اندازه خوشه ها از نظر تعداد اعضا همواره به عنوان یک چالش مطرح بوده است و حل این مسئله نیازمند الگورریتم های خوشه بندی کارا در مصرف انرژی و متعادل کننده بار شبکه می باشد .[6] با توجه به ماهیت NP-Complete بودن مسالهی خوشهبندی [3]، الگوریتم قطعیِ جامعی که بتواند این مساله را در زمان چندجملهای حل کند وجود ندارد.
محققین الگوریتمهای مختلفی برای این مساله ارائه کردهاند که هریک به طریقی، با استفاده از الگوریتمهای هوشمند یا در نظر گرفتن معیارهای کمتر یا بررسی راهحلهای امیدبخشتر سعی کردهاند بر این مشکل فائق آیند که در بخش بعدی چند مورد از آنها را بررسی خواهیم کرد. الگوریتم تخمین توزیع - EDA - نیز رویکرد جدیدی است که با ترکیب الگوریتمهای تکاملی و یادگیری ماشین راهحلهای بالقوهی مسئله را استخراج کرده [8,7] و با استفاده از توزیع احتمال افراد برگزیدهی هر نسل، جوابهای جزئی خوب را با احتمال بالا حفظ میکند و با دادن احتمال زیاد به راهحلهای امیدبخش برای پدیدار شدن در نسل بعد، سعی میکند که از نابودی راهحلهای امیدبخش جلوگیری کند .[9,8]
این الگوریتم جزو الگوریتمهای تکاملی بوده و شبیه الگوریتم ژنتیک است اما برخلاف الگوریتمهای تکاملی دیگر از عملگرهای برش و جهش استفاده نمیکند. به عبارت دیگر والدینمستقیماً فرزند تولید نمیکنند بلکه توزیع کلی والدین منتخب، منجر به تولید فرزندان میشود و فرزندان بهجای عملیات برش و جهش معمولی از روی مدل احتمالاتی تخمین شده از جمعیت والدین ساخته میشوند. پردازشهای این الگوریتمها وابسته به مدل احتمالی مورد استفاده است و خوبی این مدل احتمالی فاکتور تعیینکنندهای در کارآیی EDA به حساب میآید .
[9] این ایده نخستین بار بهوسیلهی موهلنبین و پاب در سال 1996 برای انجام محاسبات تکاملی بهکار برده شده است و اکنون برای حل حوزهی وسیعی از مسائل، از جمله مسائل رامنشدنی مورد استفاده قرار میگیرند .[9,8] در این مقاله روشی بر مبنای الگوریتمهای تخمین توزیع ارائه میشود - CME2 - که با استفاده از بهینهسازی مارکوف، با قرار دادن نزدیکترین گرهها در خوشههای یکسان، انرژی مصرفی برای ارسال یا دریافت پیام را کاهش میدهد و با انتخاب گرههایی که سطح انرژی باقیماندهی آنها نسبت به سایر گرهها بیشتر بوده و کمترین فاصله را با سایر گرههای خوشه و ایستگاه پایه - 1 BS - داشته باشند، به عنوان سرخوشه، سعی میکند از نابودی سریع گرهها جلوگیری نماید. مقایسهی نتایج حاصل از شبیهسازی CME2 و چند الگوریتم دیگر نشان میدهد که خوشههای ایجاد شده با CME2 نسبت به دو الگوریتم دیگر متعادلتر بوده و زمان مرگ آخرین گره، سطح انرژی باقیمانده گرهها و طول عمر شبکه با این روش بیشتر میباشد.
ادامهی مباحث این مقاله به این صورت سازماندهی شده است که در بخش 2 راهکارهایی هک قبلاً برای این مساله ارائه شده مورد بررسی قرار گرفته است. در بخش 3 راهکار پیشنهادی ما برای این مساله ارائه شده و ساختار و پیادهسازی آن توضیح داده خواهد شد. کارآیی الگوریتم در بخش 4 مورد ارزیابی قرار گرفته و در بخش 5 نتایج بهدست آمده از این تحقیق بیان میشود. در نهایت کارهایی که در آینده میتوان در این زمینه انجام داد در بخش 6 بیان خواهد شد.
.2 راهکارهای گذشته
پروتکل LEACH اولین پروتکل مسیریابی سلسلهمراتبی ارائه شده در شبکههای حسگر و پایهی بسیاری از پروتکلهای سلسلهمراتبی دیگر است که ایجاد خوشهها در آن بصورت توزیع شده انجام میگیرد .[10] مهمترین هدف LEACH، داشتن ایستگاههای پایهی محلی - سرخوشهها - برای کاهش مصرف انرژی ناشی از انتقال دادهها به یک BS دوردست است. پروتکل LEACH، گرههای حسگر اندکی را به طور تصادفی به عنوان سرخوشه انتخاب کرده و گرههای محلی را به عنوان خوشههای محلی سازماندهی میکند.
انتساب گرهها به سرخوشهی مربوطه براساس نزدیکی - فاصله - صورت میگیرد. برای انتقال داده در این پروتکل، گرههای عادی دادههای خود را به سرخوشهها ارسال نموده و سرخوشهها پس از انجام تجمیع داده، بستهی تجمیع شده را به BS انتقال میدهند تا میزان اطلاعاتی که باید به BS ارسال شود را کاهش دهند. در LEACH زمانبندی ارسال دادههای حسگر توسط پروتکل دستیابی چندگانه با تقسیم کد - CDMA - یا دستیابی چندگانه با تقسیم زمانی - - TDMA انجام میگیرد .[1]
پروتکل خوشهبندی LEACH متمرکز 2[11]، الگوریتم خوشهبندی است که در آن تشکیل خوشهها به صورت متمرکز و توسط BS انجام میگیرد. در این الگوریتم مرحله انتقال داده - حالت دائمی - مشابه با الگوریتم LEACH است و در طی آن هر گره اطلاعاتی در مورد موقعیت و سطح انرژی کنونی خود را به BS ارسال میکند. معمولاً این طور فرض میشود که هر گره از GPS برخوردار است. جین و همکارانش در [12] از الگوریتم ژنتیک برای خوشهبندی استفاده کردهاند.
در این روش آنها با استفاده از این الگوریتم خوشههای از قبل تعریف شدهای به وجود آوردهاند که به کاهش فاصلهی ارتباطی بین خوشهها کمک میکند. در این روش سرخوشهها 10 درصد کل گرههای شبکه تعریف میشوند. نتایج نشان میدهد که روش جین نسبت به الگوریتمهای مسیریابی مستقیم 80 درصد فاصلهی ارتباطی را کاهش میدهد. در [13] نیز کار جین توسعه داده شده و تابع شایستگی را بهبود بخشیدهاند. پارامترهایی که در این روش برای تابع شایستگی تعریف شده شامل وضعیت گرههای حسگر نیز است و خوشهبندی شبکه با انتخاب سرخوشههای مناسب انجام میشود.
