شنبه 30 تیر 1397 | Saturday 21 st of July 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-4-7تثبیت اندازه خوشه‌ها با بودجه رشد

نگاه متفاوتی به قضیه خوشه‌بندی این است که سعی کنیم اندازه یک خوشه که عبارت است از تعداد گره‌های داخل ان و نه میزان قطر و یا عمق ان را تعیین و تجویز نمائیم. یک راه دستیابی به این هدف "بودجه رشد" است که توسط کریشنان و استاروبینسکی[1] [22]ارائه شد. ایده اصلی (که در الگوریتم سریع انها ارائه شده) بسیار ساده است وقتی که به یک خوشه محدودیت اندازه ایی برابر با Bرا دهیم سرخوشه از همسایگانش می‌خواهد تا Bi ³0گـــره را بـرای ورود به خـوشـه بپذیرند، در حالی که B – 1 = åBi(سرخوشه خود را نیز به عنوان یک عضو محسوب می‌کند وبه‌همین دلیلB – 1  می‌باشد). هر گره ‌هنگام مشاهده درخواست پذیرش xعدد گره، به عضویت خوشه در می‌اید و خود نیز به‌همسایگانش اعلام پذیرش x - 1گره را می‌دهد. (به طور تلویحی درخت پوشای خوشه نیز تشکیل می‌گردد) چنین جستجویی هنگامی که بودجه اعلام شده به پایان برسد و یا گره ایی برای پذیرش در خوشه باقی نماند، خاتمه می‌یابد.

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

چه موقع از خوشه‌های چندگامی استفاده کنیم:

این سوال توسط مهاتر و روزنبرگ[2][28]مطرح گردید. انها سیستمی ناهمگن را در نظر گرفتند که سرخوشه (از راه دور) مستقیماً با گره‌های جمع اوری داده و حسگرهای معمولی ارتباط برقرار می‌کرد و بدون انکه اطلاعات متراکم گردد مستقیماً به سرخوشه ارسال می‌شد.

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



[1] Krishnan and Starobinski

[2] Mhatre and Rosenberg

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