Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.19978 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911613903175680 |
|---|---|
| author | Seyfi, Tolunay Khadem, Erfan Afghah, Fatemeh |
| author_facet | Seyfi, Tolunay Khadem, Erfan Afghah, Fatemeh |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_19978 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Optimality of Network Topology Discovery in Single-Hop Bounded-Interference Networks Seyfi, Tolunay Khadem, Erfan Afghah, Fatemeh Networking and Internet Architecture 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. |
| title | On the Optimality of Network Topology Discovery in Single-Hop Bounded-Interference Networks |
| topic | Networking and Internet Architecture |
| url | https://arxiv.org/abs/2604.19978 |