پایگاه علمی سعید سان دانلود رایگان مقالات علمی کنفرانس و ژورنال
دانلود مقاله الگوریتم های داده پراکنی محلی در شبکه های بی سیم Ad hoc: کاهش تعداد انتقال
چکیده: دو روش اصلی، ایستا و پویا، برای الگوریتم داده پراکنی در شبکه های ad hoc بی سیم وجود دارد. در روش استاتیک، الگوریتم های محلی به طور فعالانه وضعیت (حمل و نقل / حمل و نقل) هر گره را با توجه به اطلاعات توپولوژی محلی و تابع اولویت شناخته شده جهانی تعیین می کند. در این مقاله، ما در ابتدا نشان دادیم که الگوریتم های داده پراکنی محلی بر اساس روش استاتیک نمی تواند یک عامل تقریب خوبی برای راه حل بهینه (مشکل NP-سخت) دست یابد. با این حال، نشان دادیم که یک فاکتور تقریبی ثابت دست یافتنی است اگر اطلاعات موقعیتی(نسبی) در دسترس باشد. در روش پویا، الگوریتم های محلی وضعیت هر گره “در حال پرواز” را بر اساس اطلاعات توپولوژی محلی و اطلاعات مربوط به حالت انتقال تعیین می کند. با استفاده از روش پویا، اخیرا نشان داده شده است که الگوریتم های داده پراکنی محلی می تواند هنگامی که (تقریبی) اطلاعات موقعیتی در دسترس است یک فاکتور تقریبی ثابت به دست یابد. با این حال، استفاده از اطلاعات موقعیت می تواند مشکل را ساده کند. همچنین، در برخی از برنامه های کاربردی داشتن اطلاعات موقعیت نمی تواند عملی باشد. بنابراین، ما تمایل داریم بدانیم که آیا الگوریتم های داده پراکنی محلی بر اساس روش پویا می تواند بدون استفاده از اطلاعات موقعیتی یک عامل تقریب ثابت دست یابد. به طور مثبت در پاسخ به این سوال می گوییم یک الگوریتم داده پراکنی محلی که در آن وضعیت هر گره تصمیم گرفته می شود”در حال پرواز” باشد طراحی و ثابت کردیم که این الگوریتم هم می تواند تحویل کامل داشته باشد و هم تقریب ثابت به راه حل مطلوب برشد.
1 مقدمه
شبکه های ad hoc بی سیم برای پشتیبانی از یک برنامه پدید آمده است، که در آن ارتباطات بی سیم در میان انواع دستگاه ها بدون تکیه بر هیچ زیرساخت ها یا مدیریت مرکزی مورد نیاز است. در شبکه های ad hoc، دستگاه های بی سیم، به سادگی گره نامیده می شود،که دارای محدوده انتقال محدودی هستند. بنابراین، هر گره به طور مستقیم می تواند با داخل محدوده خود ارتباط برقرار مند(به عنوان مثال، همسایگان آن) و به گره های دیگر به عنوان روتر به منظور برقراری ارتباط با خارج از محدوده نیاز دارد. یکی از عملکرد های اساسی در شبکه های بی سیم ad hoc ، پخش است، که در آن یک گره پیامی به تمام گره های دیگر در شبکه منتشر می کند. این می تواند از طریق غرقه انجام شود، که در آن هر گره پیام را پس از دریافت برای اولین بار انتقال می کند. با این حال، غرقه می تواند تعداد زیادی از انتقال برکنار شده را تحمیل کند، که می تواند در نتیجه از دست دادن قابل توجهی از منابع محدود مانند پهنای باند و قدرت باشد. به طور کلی، هر گرهی برای انتقال پیام به منظور تحویل آن به تمام گره ها در شبکه مورد نیاز نیست. اگر هر گره در شبکه باشد یا در مجموعه همسایه ای دارد مجموعه ای گره ها به صورت یک مجموعه غالب (DS) است. اگر گراف ناشی از گره های آن متصل باشد DS یک مجموعه غالب متصل (CDS) نامیده می شود. واضح است، گره های بعدی، همراه با گره منبع، یک CDS تشکیل می دهند. از سوی دیگر، هر CDS را می توان برای پخش پیام (تنها گره ها در مجموعه برای انتقال مورد نیاز هستند) استفاده کرد. بنابراین، مشکلات پیدا کردن حداقل تعداد انتقال های مورد نیاز (یا گره حمل و نقل) و پیدا کردن حداقل مجموعه غالب متصل (MCDS) می تواند یکدیگر را کاهش می یابد. متاسفانه، پیدا کردن یک MCDS (و از این رو حداقل تعداد گره های حمل و نقل) ثابت شد که NP سخت است حتی زمانی که تمام توپولوژی شبکه شناخته شده است [1]، [2]. هدف مورد نظر بسیاری از الگوریتم داده پراکنی کارآمد کاهش تعداد کل انتقال ترجیحا در یک ضریب ثابت مطلوب است. برای الگوریتم های محلی و در غیاب اطلاعات توپولوژی شبکه جهانی، معمولا تصور می شود که این بسیار دشوار یا غیر ممکن است [3]، [4].
الگوریتم های داده پراکنی محلی موجود می تواند بر اساس اینکه آیا گره های انتقال به طور استاتیک (بر اساس تنها اطلاعات توپولوژی محلی) تعیین می شود و یا به صورت پویا (هم بر اساس توپولوژی محلی و هم اطلاعات حالت پخش ) طبقه بندی شود[5]. در روش ثابت، ویژگی های متمایز الگوریتم های محلی بیش از سایر الگوریتم های داده پراکنی این است که با استفاده از الگوریتم های محلی هر گونه تغییرات توپولوژی محلی می تواند تنها بر وضعیت این گره در اطراف تاثیر می گذارد. بنابراین، الگوریتم های محلی می تواند مقیاس پذیری را به عنوان CDS ساخته شده فراهم کند که می تواند به طور موثر به روز شود. الگوریتم های محلی موجود در این گروه به طور معمول از یک تابع اولویت شناخته شده توسط تمام گره ها به منظور تعیین وضعیت هر گره استفاده می کند[5]. در این مقاله نشان می دهیم که تنها با استفاده از اطلاعات توپولوژی محلی و تابع اولویت جهانی شناخته شده ، الگوریتم های داده پراکنی محلی بر اساس رویکرد ایستاتیک قادر به تضمین یک عامل تقریب خوب به راه حل بهینه (یعنی، MCDS) نیستند. از سوی دیگر، نشان می دهیم که الگوریتم های محلی بر اساس روش استاتیک می تواند به نتایج جالبی مانند فاکتور تقریبی ثابت و کوتاه ترین مسیر حفظ دست یابد در صورتی که گره ها با اطلاعات موقعیتی فراهم گردند.
Local Broadcast Algorithms in
Wireless Ad Hoc Networks: Reducing
the Number of Transmissions
Majid Khabbazian, Member, IEEE, Ian F. Blake, Fellow, IEEE, and Vijay K. Bhargava, Fellow, IEEE
Abstract—There are two main approaches, static and dynamic, to broadcast algorithms in wireless ad hoc networks. In the static
approach, local algorithms determine the status (forwarding/nonforwarding) of each node proactively based on local topology
information and a globally known priority function. In this paper, we first show that local broadcast algorithms based on the static
approach cannot achieve a good approximation factor to the optimum solution (an NP-hard problem). However, we show that a
constant approximation factor is achievable if (relative) position information is available. In the dynamic approach, local algorithms
determine the status of each node “on-the-fly” based on local topology information and broadcast state information. Using the dynamic
approach, it was recently shown that local broadcast algorithms can achieve a constant approximation factor to the optimum solution
when (approximate) position information is available. However, using position information can simplify the problem. Also, in some
applications it may not be practical to have position information. Therefore, we wish to know whether local broadcast algorithms based
on the dynamic approach can achieve a constant approximation factor without using position information. We answer this question in
the positive—we design a local broadcast algorithm in which the status of each node is decided “on-the-fly” and prove that the
algorithm can achieve both full delivery and a constant approximation to the optimum solution.
Index Terms—Mobile ad hoc networks, distributed algorithms, broadcasting, connected dominating set, constant approximation.
این فایل ورد (word) ترجمه در 30 صفحه و فایل اصلی لاتین pdf مقاله در 12 صفحه به خدمتتون ارائه میشود.