دانلود مقاله ISI انگلیسی شماره 70683
عنوان فارسی مقاله

تقریب بهتری برای ساخت ستون فقرات مجازی در شبکه های ad-hoc بی سیم 3D

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
70683 2015 18 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Theoretical Computer Science, Volume 607, Part 3, 23 November 2015, Pages 363–380

کلمات کلیدی
شبکه Ad-hoc بی سیم؛ ستون فقرات مجازی؛ مجموعه غالب متصل(CDS)؛ نمودار توپ واحد
پیش نمایش مقاله
پیش نمایش مقاله تقریب بهتری برای ساخت ستون فقرات مجازی در شبکه های ad-hoc بی سیم 3D

چکیده انگلیسی

Wireless ad hoc networks have been widely used in many areas. In order to improve network performance, we often select a connected dominating set (CDS) as its virtual backbone to deal with routing-related tasks. The problem of finding a minimum CDS (MCDS) for 2-dimensional networks has been widely studied, whereas finding an MCDS in 3-dimensional networks draws more attention recently, because it can formulate the network environment more precisely. Since MCDS problem is proved to be NP-complete, lots of approximations were proposed in literature. Among those, the best approximation for MCDS in 3D network is 14.937 in [1]. However, their projection method during the approximation deduction process is incorrect, which overthrows its final bound completely. As a consequence, in this paper we will first propose a new projection method to overcome their problem, illustrate the cardinality upper bound of independent points in a graph (which will be used to analyze the approximation ratio), and then optimize the algorithms to select MCDS with prune techniques. The major technique we use is an adaptive jitter scheme, which solves the open question in this area.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.