ساخت مجموعه غالب متصل حداقلی در شبکه های سنسوری بیسیم با استفاده از مجموعه شبه غالب

در یک شبکه بیسیم، نیاز است که پیام ها به روشی بهینه شده برای حفظ انرژی شبکه فرستاده شوند. یک مجموعه غالب متصل حداقلی (MCDS) یک رویکرد بهینه را برای ارسال پیام ها ارایه می کند. اما، ایجاد چنین مجموعه ای یک مساله -NP سخت می باشد. در این مقاله، ما یک الگوریتم تقریب حریصانه مبتنی بر درجه به نام مجموعه شبه غالب متصل با استفاده از اطلاعات دو مرحله ای (CPD2SHI) را ارایه می کنیم، که اندازه مجموعه غالب متصل را تا حد امکان کاهش می دهد. روش ما در ابتدا مجموعه غالب متصل را می سازد سپس اندازه آن را با حذف برخی از گره های مجموعه غالب متصل بدون هیچ اتلافی در شمول یا اتصال گرهها کاهش می دهد. نتایج شبیه سازی نشان می دهند که روش ما بهتر از الگوریتم های موجود ایجاد مجموعه غالب متصل برحسب اندازه مجموعه غالب متصل عمل می کند هزینه ساخت پایین تری دارد.

Keywords:

مجموعه غالب متصل (CDS) , مجموعه مستقل بیشینه (MIS) , شبکه های سنسوری بیسیم , گراف دیسک واحد , درحت استینر