کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873897 | 1440711 | 2018 | 27 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Information gathering in ad-hoc radio networks with tree topology
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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
Journal: Information and Computation - Volume 258, February 2018, Pages 1-27
نویسندگان
Marek Chrobak, Kevin P. Costello, Leszek Gasieniec, Dariusz R. Kowalski,