کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6873897 1440711 2018 27 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Information gathering in ad-hoc radio networks with tree topology
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Information gathering in ad-hoc radio networks with tree topology
چکیده انگلیسی
We study the problem of information gathering in ad-hoc radio networks, focusing on the case when the network forms a tree, with edges directed towards the root. Initially, each node has a rumor, and we aim to deliver all rumors to the root as quickly as possible without knowing the tree's topology in advance. In the deterministic case, where nodes are labeled with small integers, we give an O(n)-time protocol for the model with unbounded message size, and an O(nlog⁡n)-time protocol for bounded message size. We also consider fire-and-forward protocols, in which nodes can transmit only their own rumor or the rumor received in the previous step. We give a deterministic fire-and-forward protocol with running time O(n1.5), and show that it is asymptotically optimal. We also present a randomized O(nlog⁡n)-time protocol in the model without node labels or aggregation, and show that it is asymptotically optimal.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 258, February 2018, Pages 1-27
نویسندگان
, , , ,