On the Optimality of Network Topology Discovery in Single-Hop Bounded-Interference Networks
This addresses the challenge of topology discovery for wireless networks with interference constraints, presenting a novel deterministic method with improved efficiency.
The paper tackles the problem of efficiently discovering network topology in single-hop wireless networks with bounded interference, achieving full discovery in O(L(1+δ)log K) rounds in expectation with failure probability K^{-δ} and O(L^2 log K) rounds deterministically, with simulations showing scaling around 0.9L log K.
We propose \emph{PRISM} (\textbf{Pseudorandom Residue-based Indexed Scheduling Method}), a deterministic topology-discovery framework for single-hop wireless networks with bounded interference. Each receiver has at most \(L\) interfering transmitters among \(K\) transmitters and identifies them through singleton transmissions. PRISM assigns finite-field labels to transmitters and schedules transmissions via modular multiplication and a second prime modulus. It achieves full discovery in \(O(L(1+δ)\log K)\) rounds in expectation with failure probability \(K^{-δ}\), and in \(O(L^2\log K)\) rounds deterministically. Simulations show \(\approx 0.9L\log K\) scaling, with \(q/L\approx1.2\) minimizing mean completion time and \(q/L\approx1.4\text{--}1.6\) improving tail performance.