چهارشنبه 28 شهریور 1397 | Wednesday 19 th of September 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-3شبکه‌های سلسله مراتبی با مجموعه‌های غالب :

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

معمولاً، و نه لزوماً این انتخاب لینکها/همسایگان، دلالت بر نوعی سلسله مراتب میان گره‌ها دارد. در این بخش برخی از گره‌ها برای تشکیل یک ستون فقرات مجازی و یا یک مجموعه غالب انتخاب می‌شوند. مجموعه گره‌هایی D ÌVدر صورتی مجموعه غالب است که تمام گره‌های موجود در  Vیا در خود Dباشند و یا در همسایگی یک گامی‌برخی گره‌ها.

d ÎD ("v ÎV : v ÎD Ú$d ÎD : (v , d) ÎE)

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

چنین مجموعه غالبی باید کوچک و یا حتی در حداقل اندازه ممکن باشد. تعریف فوق V = Uرا می‌پذیرد که در واقع هیچ مزیتی ندارد. یک معیار معمولی که با ان اندازه یا کوچک بودن مجموعه غالب Uرا اندازه می‌گیرد، تعداد گره‌های این مجموعه می‌باشد. سایر موارد نیز قابل تصور می‌باشند این مسئله به نام حداقل مجموعه غالب (MDS)معروف است علاوه بر این یک ستون فقرات باید از طریق گره‌های عضو خود تشکیل شود و نباید برای هدایت بسته‌های ورودی مجبور به استفاده از گره‌های غیر عضو مجموعه خود شود. به‌همین دلیل یکی از صورت مسئله‌ها این است: " الگوریتمی ارائه دهید که مجموعه حداقل غالب را مشخص کند (MCDS). علاوه بر این هر گره باید بداند که در این مجموعه حضور دارد یا خیر و کدامیک از همسایگانش در مجموعه غالب حضور دارند

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