چهارشنبه 28 شهریور 1397 | Wednesday 19 th of September 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-4-5-1الگوریتم پدیدار شونده در تشکیل خوشه

اکثر الگوریتم هایی که تاکنون توضیح داده شده به صورتی توزیع شده بودند که‌هیچ موجود مرکزی در انها وجود نداشت که وضعیت کامل شبکه را بداند و بتواند اخرین محاسبات را انجام دهد. در این مدلها گره‌ها به صورت محلی براساس اطلاعات خود و یا همسایگانشان و اهدافی که در داخل الگوریتم نهادینه شده بود عمل می‌کردند(مثلاً گره‌های با درجه بالا سرخوشه می‌شدند). روش دیگر این است که ما الگوریتم محلی داشته باشیم که فراتر از اهداف قبلی عمل نماید. این روش الگوریتم و یا پروتکل پدیدار شونده نامیده شده است. در مرجع [30]اینگونه امده است.

پروتکل پدیدار شونده در شبکه‌های حسگر یک پروتکل محلی است که در ان مشخصه عمومی مورد نظر، نه به صورت مشخص در پروتکل امده و نه توسط بخش متمرکزی سازماندهی شده است، بلکه در اثر تعامل و بازخور بین گره‌ها پدیدار می‌شود.

چان و پریگ[1] این اصول طراحی را به مسئله خوشه‌بندی اعمال نمودند.انها الگوریتمی برای خوشه‌بندی ارائه نمودند که در اطراف سرخوشه‌ها انقدر حرکت می‌کند تا خوشه‌های مساوی را بدون انکه مستقیماً به عنوان هدف در نظر گرفته باشد، ایجاد نماید. در این الگوریتم هر گره می‌تواند در سه وضعیت باشد، خوشه‌بندی نشده (از هیچ خوشه ای اگاهی ندارد)، سرخوشه و دنباله رو(دنباله رو بیش از یک سرخوشه که در نهایت تصمیم خواهد گرفت که کدام سرخوشه را انتخاب نماید). گره‌های خوشه‌بندی نشده (با اندکی تاخیر تصادفی) تبدیل به سرخوشه شده و همسایگان خود را به حالت یک گره دنباله رو دراورده و عضو خوشه خود می‌نماید. ایده جالب توجه این است که عضویت در خوشه در صورتی که یک گره دنباله رو بتواند سرخوشه بهتری پیدا کند حذف و در خوشه دیگر قرار می‌گیرد. به طور مثال در صورتی که خوشه ای اعضای بیشتر و هم پوشانی کمتری با خوشه‌های دیگر دارد در اولویت قرار می‌گیرد. گره غالب با واگذاری مسئولیت سرخوشه ای در گره قبلی می‌تواند به حالت سرخوشه ارتقا یابد.

درواقع مسئولیت سرخوشه ای در کل شبکه گردش می‌کند. گره‌ها پس از گذشت زمان خاص الگوریتم را پایان خواهند داد. مشخصه جالب این الگوریتم این است که به یک مدل بهینه خوشه‌بندی دست می‌یابد که نزدیکترین مدل خوشه‌بندی به حالت شش گوشه می‌باشد. زمان اجرای ان ثابت و مستقل از اندازه شبکه است (الگوریتم به اندازه کافی سرخوشه در حالت توزیع شده تولید می‌نماید).



[1] Chan and Perig

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26