مقاله انگلیسی مجموعه های مسلط متصل در شبکه های ادهاک و بی سیم سه بعدی (2020 الزویر)

مشکل Minimum Connected Domination Set (MCDS) یک مشکل اساسی در شبکه های ad hoc بی سیم است. اکثر الگوریتم های تقریبی برای این مشکل NP-سخت از یک رویکرد دو مرحله ای پیروی می کنند: مرحله اول ساخت یک مجموعه مستقل حداکثر (MIS) است و مرحله دوم اتصال گره های موجود در آن است. مرزهای بالای MIS نقش اساسی در طراحی الگوریتم های تقریبی MCDS دارند. این مقاله این مشکل را برای شبکه های ad hoc 3D ناهمگن ، که در آن محدوده انتقال گره مجاز است متفاوت باشد ، در نظر می گیرد. ما مرزهای بالای MIS با دو مشکل ریاضی کلاسیک ، مسئله کد کروی و مشکل بسته بندی کره را اثبات می کنیم. هنگامی که نسبت دامنه انتقال (نسبت حداکثر برد انتقال بیش از حداقل محدوده انتقال) (1 ، 1.023] ، (1.023 ، 1.055] ، (1.055 ، 1.082] ، … باشد ، ما مرزهای بالای MIS را از بهترین نتایج شناخته شده … ، به … ، جایی که OPT CDS بهینه است و | OPT | اندازه OPT است. با محدودیت MIS ها ، می توان نسبت تقریبی الگوریتم های MCDS را از 25.02 به 16.02 در ناهمگن کاهش داد. شبکه های تعطیل بی سیم 3D بی سیم.

1. مقدمه

مجموعه های مسلط متصل (CDS) به عنوان ستون فقرات مجازی در شبکه های موقت تبلیغاتی بی سیم استفاده می شوند [1] – [4]. برای شبکه بی سیم ad hoc که به عنوان نمودار G = (V ، E) انتزاع شده است ، یک زیر مجموعه C⊂V متصل یک CDS از G است ، اگر (1) زیر نویس ناشی از C به هم متصل باشد ، و (2) برای هر گره v در V \ C ، یک گره u در C وجود دارد به گونه ای که uv∈E باشد. یک گره در CDS یک سلطه گر نامیده می شود و یک گره غیر CDS تحت سلطه نامیده می شود. سلطه گرها به عنوان گره های رله در شبکه عمل می کنند و ستون فقرات مجازی را تشکیل می دهند. به طور طبیعی ، ستون فقرات مجازی کوچک تداخل سیگنال و مصرف انرژی کمتری را به همراه دارد. بنابراین ، بسیاری از تحقیقات بر حداقل مشکل سلطه گر متصل (MCDS) متمرکز شده اند. از آنجا که مشکل MCDS NP-سخت ثابت شده است [5] ، برای حل این مشکل از الگوریتم های تقریبی استفاده می شود.

توجه؛ (این ترجمه توسط نرم افزار انجام شده و ویرایش نشده است و احتمال وجود اشتباه در آن وجود دارد. در صورت ثبت سفارش، ترجمه توسط مترجمین مجرب انجام خواهد شد. برای مشاهده نمونه ترجمه های تخصصی و اخیر مترجمین جهت اطمینان از کیفیت ترجمه، اینجا کلیک نمایید.)

The Minimum Connected Dominating Set (MCDS) problem is a fundamental problem in wireless ad hoc networks. The majority of approximation algorithms for this NP-hard problem follow a two-phased approach: The first phase is to construct a Maximal Independent Set (MIS), and the second phase is to connect the nodes in it. The upper bounds of the MISs play a key role in the design of constant approximation MCDS algorithms. This paper considers this problem for 3D heterogeneous ad hoc networks, where the transmission ranges of nodes are allowed to be different. We prove upper bounds of MISs with two classical mathematical problems, the Spherical Code Problem and the Sphere Packing Problem. When the transmission range ratio (the ratio of the maximum transmission range over the minimum transmission range) is (1, 1.023], (1.023, 1.055], (1.055, 1.082], …, we reduce the MIS upper bounds from the best-known results …, to …, where OPT is an optimal CDS and |OPT| is the size of OPT. With the bounds of MISs, the approximation ratio of MCDS algorithms can be reduced from 25.02 to 16.02 in heterogeneous 3D wireless ad hoc networks.

1.Introduction

Connected dominating sets (CDSs) are used to serve as virtual backbones in wireless ad hoc networks [1]–[4]. For a wireless ad hoc network abstracted as a graph G = (V, E), a connected subset C⊂V is a CDS of G, if (1) the subgraph induced by C is connected, and (2) for any node v in V \C, there exists a node u in C such that uv∈E. A node in the CDS is called a dominator and a non-CDS node is called dominated. The dominators serve as relay nodes in the network and form a virtual backbone. Naturally, a small virtual backbone brings up less signal interference and less energy consumption. Therefore, many researches have focused on the minimum connected dominating set (MCDS) problem. Since the MCDS problem has been proven NP-hard [5], approximation algorithms are used to solve this problem.