  The Signal-to-Interference-and-Noise-Ratio (SINR) physical model is one of
the legitimate models of wireless networks. Despite of the vast amount of study
done in design and analysis of centralized algorithms supporting wireless
communication under the SINR physical model, little is known about distributed
algorithms in this model, especially deterministic ones. In this work we
construct, in a deterministic distributed way, a backbone structure on the top
of a given wireless network, which can be used for transforming many algorithms
designed in a simpler model of ad hoc broadcast networks without interference
into the SINR physical model with uniform power of stations, without increasing
their asymptotic time complexity. The time cost of the backbone data structure
construction is only O(Delta polylog n) rounds, where Delta is roughly the
inverse of network density and n is the number of nodes in the whole network.
The core of the construction is a novel combinatorial structure called
SINR-selector, which is introduced and constructed in this paper. We
demonstrate the power of the backbone data structure by using it for obtaining
efficient O(D+Delta polylog n)-round and O(D+k+Delta polylog n)-round
deterministic distributed solutions for leader election and multi-broadcast,
respectively, where D is the network diameter and k is the number of messages
to be disseminated.
