بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
روشی کارا برای خوشه بندی در شبکه های حسگر بیسیم با استفاده از منطق فازی
خلاصه:
شبکه ی حسگر بیسیم (WSN) از تعداد زیادی گره ی حسگر تشکیل شده که به یکدیگر متصل هستند تا عمل خاصی را انجام دهند. این گرهها انرژی، قدرت پردازش و حافظهی محدودی دارند. به دلیل اینکه طول عمر شبکه بستگی به این گرهها دارد به دلیل محدودیت منابع در شبکههای حسگر بیسیم، افزایش طول عمر شبکه همیشه مورد توجه بوده است. یک روش مسیریابی کارا، مسیریابی سلسلهمراتبی بر اساس خوشه بندی است که یافتن سر خوشههای بهینه و تعداد آنها یک چالش محسوب میشود. در این مقاله، ما یک روش کارا برای خوشهبندی با استفاده از منطق فازی با ورودیهای مناسب پیشنهاد میدهیم و آن را با ویژگیهای خوب LEACH ترکیب میکنیم. این روشکاملاً توزیع شده است. بنابراین سرعت آن بیشتر و مصرف انرژی آن کمتر از روشهای متمرکز است.
کلمات کلیدی: شبکه های حسگر بی سیم، خوشه بندی، سرخوشه، منطق فازی، طول عمر
-1 مقدمه:
یک شبکهی حسگر بیسیم (WSN) شامل تعداد زیادی گرهی حسگر و یک ایستگاه اصلی (BS) است. این حسگرها دادهها را جمعآوری و آنها را از طریق فرستندهی رادیویی به BS ارسال میکنند. این حسگرها نیرو و ظرفیت محاسباتی محدودی دارند. از WSNها میتوان در بسیاری از برنامهها مثل برنامههای نظامی، دارویی و محیطی استفاده کرد به دلیل ویژگیهای خاص شبکههای حسگر بیسیم، چالشهای متعددی در این شبکهها وجود دارد. یکی از این چالشها منبع انرژی محدود گرههاست. در اکثر موارد، منبع انرژی غیر قابل تعویض و غیر قابل شارژ است. بنابراین باید از روشهایی در WSNها استفاده شود که مصرف انرژی گرهها را کاهش میدهد. [1][2][3]
دادههایی که توسط گرهها حس میشود برای پردازش و تصمیمگیری باید به یک ایستگاه منتقل شوند. این ایستگاه، ایستگاه اصلی یا سینک نامیده میشود. اگر هر گره دادههایش را به طور مستقیم به سینک ارسال کند، انرژی زیادی مصرف میشود. به دلیل اینکه مقادیر حس شده توسط گرههای نزدیک کمی متفاوت است، احتمال افزونگی در دادههای انتقالی وجود دارد.
همانطور که اشاره شد، انرژی زیادی برای ارسال دادهها به سینک مصرف میشود. در نتیجه، گرههای سر خوشه با چالش کاهش سریع انرژی مواجه میشوند. به محض اینکه سر خوشه کند شود، قسمتی یا کل شبکه از کار میافتد. یک روش جلوگیری از این مسئله این است که گرههای سر خوشه، به منبع انرژی قابل تعویض یا قابل شارژ مجهز شوند. روش دیگر تغییر مداوم سر خوشهها بین گرههای شبکه است تا مصرف انرژی در شبکه توزیع شود.[5]
ما از روش دوم استفاده کردیم زیرا گرهها همگن هستند. در روش پیشنهادی، ابتدا سر خوشه انتخاب میشود. سپس هر گره نزدیکترین سر خوشه به خودش را انتخاب می کند. بنابراین خوشهها تولید میشوند.
در واقع، روش ما مشابه LEACH[4] است. دو دورهی زمانی تا انتهای شبکه تکرار میشود: مرحلهی شکل گیری خوشهها و مرحله ی استقرار. در این ساختار، مشابه با LEACH، هر گره خودش تصمیم میگیرد که سر خوشه باشد و دیگر گرهها را از این موضوع باخبر میکند. انتخاب سر خوشهها در LEACH تصادفی است. در حالی که در روش ما، سر خوشه بر اساس پارامترهای متعدد و یک سیستم فازی انتخاب میشود.
به دلیل اینکه LEACH سر خوشه را فقط به صورت تصادفی انتخاب میکند و کاری با دیگر پارامترهای دیگر مثل انرژی باقیمانده و موقعیت گرهها ندارد، همیشه بهترین خوشه را انتخاب نمیکند. برای مثال، یک گره ممکن است سر خوشه باشد و انرژی کمی داشته باشد. ممکن است به این گرهها هیچ توجهی نشود یا اگر یک گرهی دور افتاده سر خوشه شود، دیگر گرهها باید انرژی زیادی را برای ارسال داده به این سر خوشه صرف کنند. با این حال، LEACH توزیع متعادلی از سر خوشه ها فراهم می آورد و کارایی بالایی دارد.
ما از یک سیستم فازی با ورودیهای مناسب برای غلبه بر مشکل LEACH استفاده میکنیم. ورودیهایی که در سیستم فازی در نظر میگیریم عبارتند از: تعداد همسایهها، مرکزیت، انرژی باقیمانده، فرکانس سیگنال دریافتی از همسایهها و تعداد دورهایی که گره سرخوشه نبوده است. این پارامترها چندان به هم وابسته نیستند و به راحتی میتوانند با این پارامترهای ناهمگن و با استفاده از منطق فازی کار کنند. همچنین یک سیستم فازی نیاز به پیچیدگی محاسباتی زیادی ندارد، بنابراین برای WSN مناسب است.
باقیماندهی مقاله به این صورت سازماندهی شده است: در بخش بعدی مروری روی کارهای مرتبط و برخی مشکلات انتخاب تصادفی سر خوشهها خواهیم داشت. در بخش 3 مروری روی منطق فازی داریم. در بخش 4 روش پیشنهادی خود را توصیف میکنیم. نتایج شبیهسازی در بخش 5 ارائه شده است. در نهایت در بخش 6 نتیجهگیری مقاله را خواهیم داشت.
-2 کارهای مرتبط
یک معماری معمولی WSN در شکل 1 نشان داده شده است. گرهها، دادهها را به سر خوشههای مرتبط ارسال می کنند، در آنجا دادهها فشردهسازی و به ایستگاه اصلی منتقل میشوند. برای یک WSN فرضیات زیر را در نظر میگیریم:
· ایستگاه اصلی دور از گرههای حسگر قرار دارند و بیحرکت هستند.
· همه ی گرهها در شبکه همگن و دارای انرژی محدود هستند.
· کانال پخش متقارن
· ایستگاه اصلی، انتخاب سر خوشه را انجام می دهد.
· گره ها بدون حرکتند یا حرکت کمی دارند.
شکل .1 معماری WSN
یکی از معروفترین پروتکلهای مسیریابی خوشهای پروتکل سلسلهمراتبی خوشهبندی انطباقی با انرژی پایین (LEACH) است که در [4] بحث شده است. عملیات LEACH متشکل از چندین دور و هر دور متشکل از مرحله ی نصب و مرحلهی حالت پایدار است. در مرحله ی نصب، خوشهها سازماندهی و سر خوشهها (CH) انتخاب میشوند. هر حسگر n یک عدد تصادفی بین 0 و 1 تولید میکند. اگر این عدد کمتر از T(n) تعریف شده توسط معادله ی 1 بود، آنگاه حسگر n به عنوان سر خوشه انتخاب میشود.
در این معادله p درصد دلخواه از CH است، r دور فعلی و G مجموعه گرههایی که به عنوان سر خوشه در 1/p دور قبل انتخاب نشدهاند را تعیین میکنند. تعداد بهینهی سر خوشهها حدود 5 درصد کل تعداد گرهها تخمین زده میشود. پس از انتخاب سرخوشه، CH یک پیام تبلیغاتی میفرستد و دیگر گرهها، نزدیک ترین CH را بر اساس قدرت سیگنال دریافتی انتخاب میکنند. با وجود اینکه LEACH قادر به افزایش طول عمر شبکه است اما دو مشکل اصلی دارد:
· ممکن است هیچ یک یا تعداد زیادی از CHها انتخاب شوند.
· ممکن است ِCHهای زیادی در یک ناحیه ی خاص واقع باشند، یعنی CHها به صورت توزیع شده انتخاب
نمیشوند.
در [6]، گوپتا از منطق فازی برای یافتن سرخوشهها استفاده کرده است. در این الگوریتم، از سه متغیر فازی برای انتخاب سر خوشهها استفاده میشود. انرژی گره، تمرکز گره و مرکزیت گره این سه پارامتر هستند. در این روش، ایستگاه اصلی در ابتدا اطلاعات ضروری از همه ی گرهها را جمعآوری کرده و سپس یک گره را به عنوان سر خوشه بر اساس قوانین فازی انتخاب می کند. در این روش، تنها یک انتخاب برای هر دور وجود دارد، در حالیکه به CHهای بیشتری برای متعادل کردن مصرف انرژی و بهبود طول عمر شبکه نیاز است.
در [7]، کیم CHEF را پیشنهاد می کند که مشابه [6] است و CHها بر اساس منطق فازی انتخاب میشوند. تفاوت اینجاست که
در این روش بیش از یک سر خوشه در هر دور به صورت محلی انتخاب میشود. مجموعه ی فازی شامل انرژی گرهها و فاصلهی محلی آنهاست. CHEF یک عدد تصادفی نیز برای هر حسگر انتخاب میکند و اگر این عدد کمتر از آستانه ی از پیش تعریف شدهی Popt بود، آنگاه شانس آن گره قطعی است. بنابراین ممکن است گرههای واجد شرایطی وجود داشته باشد که شانس خود را به گونهای تصادفی از دست بدهند.
روشی که در [8] ارائه شده یک روش فازی برای انتخاب سرخوشهها است. این روش متمرکز است و شبکه از هماهنگی گرهها آگاه است. تصمیم انتخاب یک گره به عنوان سر خوشه توسط سینک انجام میشود. این روش روی سه متغیر تکیه دارد: باقیمانده ی انرژی گره، تمرکز و مرکزیت گره تصمیم گیرندهی سر خوشه بودن یک گره است.
در [9] روشی به نام LEACH-FL مطرح شده است. این روش از یک سیستم فازی با سه ورودی سطح باتری، چگالی گره وفاصله از سینک برای انتخاب سر خوشهها استفاده میکند. این روش با فرض اینکه مختصات شبکه موجود است معرفی شده است.
این دو روش متمرکز هستند. بنابراین برای محیطهایی که نیاز به پردازش بلادرنگ است مناسب نیستند. همچنین، انرژی زیادی برای ارسال موقعیت گرهها مثل انرژی باقیمانده برای سینک لازم است. در این روشها فرض میشود که مختصات شبکه در دسترس است. برای این مسئله، گرهها باید به سختافزار اضافی مثل سیستم موقعیتیابی جهانی (GPS) مجهز شوند. این راه در همهی محیطها ممکن نیست. مسئله ی دیگر این است که میتوانیم از ورودیها برای سیستم فازی به طور کاراتری از ورودیهای این روشهای سیستمهای فازی استفاده کنیم.[10]
بر طبق آنچه گفته شد، ما یک روش توزیع شده پیشنهاد دادیم و هر گره خودش دربارهی سر خوشه شدن یا نشدن تصمیم میگیرد. این روش باید در همه ی محیطها کار کند و بنابراین نیاز به مختصات گرهها ندارد. در این روش با انتخاب ورودیهای مناسب برای سیستم فازی، سیستمی کاراتر از روشهای موجود داریم و خوشهبندی بهتر انجام میشود.
-3 منطق فازی
منطق فازی (FL) منطق افکار انسانی است که انعطافپذیری بیشتری نسبت به محاسباتی دارد که کامپیوترها انجام میدهند.منطق فازی، ویژگیهای منحصر به فرد مختلفی را برای مسائل کنترلی ارائه میدهد. این موضوع ذاتاً انعطافپذیر نیست زیرا نیاز به ورودیهای دقیق ندارد و ممکن است به راحتی با برنامهنویسی با شکست مواجه شود.[12][11]
مجموعههای فازی با محدودهای از مقادیر واقعی به نام دامنه و تابع عضویت توصیف میشوند که مجموعه به آنها نگاشت میشود. یک تابع عضویت یک مقدار صحیح (دقیق) بین 0 و 1 را به یک نقطه در دامنهی مجموعه ی فازی اختصاص میدهد. بسته به شکل تابع عضویت، از انواع مختلفی از مجموعههای فازی مثل مثلثی، بتا، PI، گاوسی، حلقوی و ... میتوان استفاده کرد. توابع عضویت ذوزنقهای و مثلثی برای عملیات بلادرنگ مناسب هستند زیرا پیچیدگیهای محاسباتی ندارند و از دقت کافی برخوردارند.
یک سیستم فازی اصولاً از سه بخش تشکیل شده است: فازی کردن، موتور استنتاج و دیفازی کردن. شکل 1 اجزای سیستم فازی که در این مقاله استفاده کردیم را نشان میدهد. فازی کننده، هر مقدار ورودی دقیق را به مجموعهی فازی متناظر نگاشت میکند و بنابراین به آن یک مقدار صحیح یا درجهای از عضویت برای هر مجموعه ی فازی اختصاص میدهد. مقادیر فازی شده توسط موتور استنتاج که شامل یک پایگاه قوانین و روشهای مختلف برای استنتاج قوانین است پردازش میشوند. پایگاه قوانین یک سری از قوانین IF-THEN است که متغیرهای فازی ورودی را توسط متغیرهای زبانی به متغیرهای فازی خروجی مرتبط میکند و هر کدام از آنها با یک مجموعه ی فازی و عملگرهای ضمنی فازی AND و OR و ... توصیف میشوند.
سیستم فازی که در موتور استنتاج یک سیستم خبره استفاده میشود یک سیستم فازی Mamdani است. سیستم فازی ممدانی یک روش سادهی قانون گرا است که نیاز به محاسبات پیچیده ندارد و میتواند از قوانین IF…THEN برای کنترل سیستمها استفاده کند دیفازی کننده عمل دیفازی را روی فضای راهحل فازی انجام میدهد. یعنی یک مقدار خروجی دقیق از فضای فازی راه حل پیدا میکند. برخی از روشهای معمول دیفازی عبارتند از: مرکز ناحیه (COA)، مرکز گرانش (COG)، مرکز توسعه یافتهی ناحیه (ECOA)، میانگین ماکسیما (MeOM) و ... در این مقاله، از روش COA برای دیفازی کردن استفاده میکنیم.[14]
-4 روش پیشنهادی
ما از سیستم فازی زیر (شکل (2 در روش پیشنهادی استفاده می کنیم:
شکل .2 اجزای سیستم فازی
ورودیهای سیستم فازی اعداد دقیقی هستند که توسط تابع عضویت به مقادیر فازی تبدیل شدهاند. گرهها به سادگی این مقادیر ورودی را تعیین میکنند. به محض اینکه یک ارسال یا دریافت داده انجام شود، گرهها از گرههای همسایه و فاصلههای آنها آگاه میشوند.
این عملیات به سادگی توسط روش علامت قدرت سیگنال دریافتی (RSSI) انجام میشود. اگر یک گره فاصلهی کمتری نسبت به همسایگانش داشته باشد (مرکزیت)، دیگر گرهها انرژی کمتری برای ارسال داده به آن گره صرف می کنند. ما مرکزیت را با یک معادلهی ساده محاسبه میکنیم: جمع متقابل تفریق فاصله ی همسایگان یک گره. هر چه این عدد کمتر باشد، گره مرکزیت بیشتری دارد.
اگر یک گره در مرکز توجه باشد یعنی سیگنالهای زیادی از آن عبور میکنند تا به یک سر خوشه برسند و بهتر است این گره سر خوشه شود. همچنین به منظور مصرف انرژی توزیع شده، شانس یک گره برای سر خوشه شدن با افزایش دورهایی که آن گره سر خوشه نبوده بیشتر میشود. توابع عضویت که مقادیر ورودی دقیق را به مقادیر فازی تبدیل می کنند در شکل 3 نشان داده شده است.
