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

سال انتشار: 1397
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 448

فایل این مقاله در 26 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ITCT05_042

تاریخ نمایه سازی: 18 اردیبهشت 1398

چکیده مقاله:

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

کلیدواژه ها:

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

نویسندگان

سپیده پناهی

گروه مهندسی کامپیوتر ،واحد گرمی ،دانشگاه آزاد اسلامی ،گرمی ،ایران

سجاد جهان بخش گده کهریز

گروه مهندسی کامپیوتر ،واحد گرمی ،دانشگاه آزاد اسلامی ،گرمی ،ایران