2012/10/05 by Tomasz Jurdziński, Jurdzinski, Tomasz, Dariusz R. Kowalski +3 · 1 citation
Computer Science · #Cooperative Communication and Network Coding #Distributed #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Parallel #Wireless Networks and Protocols #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1210.1804
openalex publication_date 2012/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we initiate a study of distributed deterministic broadcasting in ad-hoc wireless networks with uniform transmission powers under the SINR model. We design algorithms in two settings: with and without local knowledge about immediate neighborhood. In the former setting, our solution has almost optimal O(Dlog2 n) time cost, where n is the size of a network, D is the eccentricity of the network and 1,...,N is the set of possible node IDs. In the latter case, we prove an Omega(n log N) lower bound and develop an algorithm matching this formula, where n is the number of network nodes. As one of the conclusions, we derive that the inherited cost of broadcasting techniques in wireless networks is much smaller, by factor around minn/D,Delta, than the cost of learning the immediate neighborhood. Finally, we develop a O(D Delta log2 N) algorithm for the setting without local knowledge, where Delta is the upper bound on the degree of the communication graph of a network. This algorithm is close to a lower bound Omega(D Delta).