broadcast در شبکه بیسیم وایرلس

می‌خواهیم پیامی را از یک پردازنده به بقیه برسانیم و حداقل تعداد ارسالها را داشته باشیم.

اطلاعات کامل را داشته باشیم: مجموعه‌ی رأسهایی که ارسال می‌کنند باید همبند باشد و باید یک پوشش رأسی برای گراف باشند.

این مسأله np-hard است.

تقریب مسأله با فرض داشتن اطلاعات محلی: اگر هر گره همسایه‌های خودش را بداند (شعاع ارسال ثابت باشد) می‌توان الگوریتمی با تقریب ثابت برای مسأله ارائه داد.

الگوریتم: هر گره مختصات خودش و همسایه‌هایش را دارد. پس چون رأسی که از آن پیام را دریافت کرده است حتما در همسایگی‌اش است مختصات آن را هم دارد و می‌تواند حساب کند که آیا نقاطی که در همسایگی‌اش هستند قبلاً پیام را دریافت کرده‌اند یا خیر و فقط در صورتی بفرستد که بداند آن نقطه از جای دیگری پیام را دریافت نکرده است یا در حال دریافت آن نیست.

ایراد: ممکن است یک نفر دو بار پیام دریافت کند و این کار ممکن است باعث تداخل و نامفهوم شدن پیام شود.