Deterministic protocols in the SINR model without knowledge of coordinates

摘要

This work studies multi-broadcasting for the SINR (Signal-to-Interference-plus-Noise-Ratio) model, assuming a subset of nodes are initially awake, when each device only has access to knowledge about the total number of nodes in the network n, the range from which each node's label is taken {1,…,N}, and the label of the device itself. We assume no knowledge of the physical coordinates of devices and no knowledge of the neighborhood of each node. We present a deterministic protocol for this problem that runs in O(nlg⁡Nlg⁡n) rounds. There is no known polytime deterministic algorithm for this setting. A lower bound of Ω(nlg⁡N) rounds is known for deterministic broadcasting without local knowledge [30]. We also present algorithms to achieve multi-broadcast in O(nlg⁡N) rounds and create a backbone in O(nlg⁡N) rounds, assuming that all nodes are initially awake.