کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433937 689658 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the complexity of neighbourhood learning in radio networks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the complexity of neighbourhood learning in radio networks
چکیده انگلیسی

Consider a synchronous radio network of n   stationary nodes represented by an undirected graph with maximum degree Δ. Suppose that each node has a unique ID from {1,…,U}{1,…,U}, where U≫nU≫n. In the neighbourhood learning task, each node must produce a list of the IDs of its neighbours in the network. We prove new lower bounds on the number of slots needed by certain classes of deterministic algorithms that solve this task. First, we show that O(U)O(U)-slot round-robin algorithms are optimal for the class of collision-free algorithms. Then, we consider algorithms where each node fixes its entire transmission schedule at the start. For such algorithms, we prove a Ω(Δ2log⁡Δlog⁡U)-slot lower bound on schedule length that holds in very general models, e.g., when nodes possess collision detectors, messages can be of arbitrary size, and nodes know the schedules being followed by all other nodes. We also prove a similar result for the SINR model of radio networks. To prove these results, we consider a generalization of cover-free families of sets. We also show a separation between the class of fixed-schedule algorithms and the class of algorithms where nodes can choose to leave out some transmissions from their schedule.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 608, Part 2, 10 December 2015, Pages 135–145
نویسندگان
,