Sparse Backbone and Optimal Distributed SINR Algorithms

作     者：Halldorsson, Magnus M. Tonoyan, Tigran 

作者机构：Reykjavik Univ Dept Comp Sci ICE TCS Menntavegur 1 IS-102 Reykjavik Iceland Technion Dept Comp Sci IL-320000 Haifa Israel 

出 版 物：《ACM TRANSACTIONS ON ALGORITHMS》 (ACM Trans. Algorithms)

年 卷 期：2021年第17卷第2期

页      面：1–34页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

主　　题：Wireless network distributed algorithm plain SINR 

摘      要：We develop randomized distributed algorithms for many of the most fundamental communication problems in wireless networks under the Signal to Interference and Noise Ratio (SINR) model of communication, including (multi-message) broadcast, local broadcast, coloring, Maximal Independent Set, and aggregation. The complexity of our algorithms is optimal up to polylogarithmic preprocessing time. It shows-contrary to expectation-that the plain vanilla SINR model is just as powerful and fast (modulo the preprocessing) as various extensions studied, including power control, carrier sense, collision detection, free acknowledgements, and geolocation knowledge. Central to these results is an efficient construction of a constant-density backbone structure over the network, which is of independent interest. This is achieved using an indirect sensing technique, where message non-reception is used to deduce information about relative node-distances.