On the Optimality of Network Topology Discovery in Single-Hop Bounded-Interference Networks Tolunay Seyfi1 , Erfan Khadem2 , Fatemeh Afghah1
arXiv:2604.19978v1 [cs.NI] 21 Apr 2026
1
Holcombe Department of Electrical and Computer Engineering, Clemson University, Clemson, SC, USA 2 Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran [email protected], [email protected], [email protected]
Abstract—We propose PRISM (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(L2 log K) rounds deterministically. Simulations show ≈ 0.9L log K scaling, with q/L ≈ 1.2 minimizing mean completion time and q/L ≈ 1.4–1.6 improving tail performance. Index Terms—Topology discovery, bipartite networks, deterministic algorithms, pseudorandom functions, number theory, network discovery.
I. I NTRODUCTION Large-scale wireless systems require scalable and reliable mechanisms for topology discovery, i.e., for identifying which transmitters interfere with which receivers, since such information underlies scheduling, routing, interference management, and resource allocation [1]. Classical neighbordiscovery methods based on random access or probabilistic contention [2] are often ill-suited to ultra-reliable and lowlatency settings such as industrial wireless control [3], dense vehicular systems, and UAV networks. This has motivated heuristic approaches [4], [5], learning-based methods [6], and structured code constructions such as on-off necklace codes for asynchronous discovery [7]. At the same time, lower bounds for radio communication highlight the intrinsic difficulty of fast deterministic discovery in adversarial settings [8]. Motivated by these limitations, we study deterministic, non-adaptive topology discovery in single-hop bounded-interference networks. Prior work [9] introduced a deterministic prime-indexed scheduling framework with round complexity scaling as log2 K due to repeated prime reuse across phases. In contrast, we develop a multiplicative residuebased construction that uses a cyclic permutation over a finite field together with a second prime modulus to induce analyzable transmission patterns, thereby reducing systematic collisions without requiring feedback. Our model is a bipartite interference graph G = (T ∪R, E), where T = {T1 , . . . , TK } is the set of transmitters, R = {R1 , . . . , RK } is the set of receivers, and (Ti , Rj ) ∈ E indicates that transmitter Ti is in the interference neighborhood of receiver Rj . For each receiver Rj , the neighborhood N (Rj ) = {i : (Ti , Rj ) ∈ E} satisfies |N (Rj )| ≤ L. Each edge (Ti , Rj ) ∈ E represents a potential interfering transmission from Ti at receiver Rj , and the discovery goal is for each receiver to identify all transmitters in its interference neighborhood. This abstraction captures both structured locally connected interference patterns arising in sectorized cellular layouts and more general non-local interference topologies
induced by beamforming, reuse, blockage, mobility, and programmable wireless environments [10]–[12]. A. Contributions This work makes the following contributions: • We propose PRISM, a deterministic scheduling framework based on modular residue classes that enables topology discovery in bounded-interference bipartite networks without adaptive feedback. • We establish provable complexity guarantees: O(L(1 + δ) log K) rounds in expectation over random topology realizations, and O(L2 log K) rounds in the worst case. • We show that PRISM is zero-error and fully deterministic, and we validate its practical performance through Monte Carlo simulations, including parameter tuning with respect to q/L, empirical scaling close to 0.9L log K, and a linear-time residue-alignment verification procedure for certifying deterministic convergence. II. A LGORITHM : P SEUDORANDOM R ESIDUE - BASED I NDEXED S CHEDULING M ETHOD (PRISM) A. Algorithm Description Choose a prime p > K, assign each transmitter i a unique initial label xi,0 ∈ Z∗p , select a generator g of Z∗p , and choose a second prime q = O(L) with q > L, where L is the maximum receiver degree. The modulus q determines the number of rounds per phase and controls the collision rate. The protocol proceeds in phases. In phase ϕ ≥ 1, transmitter i updates its label as xi,ϕ = (gxi,ϕ−1 ) mod p = (xi,0 g ϕ ) mod p, and maps its current label to round yi,ϕ = xi,ϕ mod q. Thus phase ϕ consists of q rounds indexed by j ∈ {0, . . . , q − 1}, and transmitter i sends its original label xi,0 only in round j = yi,ϕ . Each receiver starts with candidate set {1, . . . , K} and refines it phase by phase. In round j: (i) if the round is silent, all candidates mapping to j are eliminated; (ii) if exactly one transmitter xA is observed, then xA is declared a true neighbor and all candidates mapping to j are removed; and (iii) if multiple transmitters collide, then the receiver cannot distinguish them and all candidates mapping to j are retained. Hence a false candidate survives a phase only if it repeatedly falls into collision rounds. Set q = cL, c > 1. As shown later, L2 L2 1 Psurvive ≤ 2 = 2 2 = 2 . 2q 2c L 2c
For example, c = 2 gives Psurvive ≤ 1/8. Thus c controls the trade-off between shorter phases and lower collision persistence. In practice, values near c ≈ 1.2 minimize the mean completion time, values around 1.4–1.6 improve tail latency, and larger values such as c ∈ [2, 3] are useful when seeking stronger deterministic separation guarantees. Let M denote the number of phases. For a false candidate, Pr[survives M phases] = (Psurvive )M , M
K(Psurvive )
<K
−δ
M
(1) −(δ+1)
=⇒ (Psurvive ) < K , (2) (δ + 1) log K . (3) M> log(1/Psurvive ) Substituting Psurvive = 1/(2c2 ) gives M = O((1 + δ) log K). Since each phase contains q = O(L) rounds, the total probabilistic runtime is M q = O(L(1 + δ) log K). B. Deterministic Runtime Analysis We now show that even without probabilistic assumptions on the topology, a false candidate cannot remain indistinguishable from true neighbors indefinitely. 1) Stuck Candidates Argument: Call a false candidate xc stuck if it collides with the same true neighbor over multiple consecutive phases. Let xi,ϕ denote the index of a true neighbor i in phase ϕ, and let xc,ϕ denote the corresponding index of candidate c. Suppose that in two consecutive phases ϕ − 1 and ϕ, xc,ϕ−1 ≡ xi,ϕ−1 (mod q), xc,ϕ ≡ xi,ϕ (mod q). Using the update rule xi,ϕ = gxi,ϕ−1 − ℓi p, xc,ϕ = gxc,ϕ−1 − ℓc p, where gxc,ϕ−1 gxi,ϕ−1 , ℓc = , ℓi = p p we obtain gxi,ϕ−1 − ℓi p ≡ gxc,ϕ−1 − ℓc p (mod q), (4) g(xi,ϕ−1 − xc,ϕ−1 ) ≡ (ℓi − ℓc )p (mod q). (5) Since the nodes already collide in phase ϕ − 1, xi,ϕ−1 ≡ xc,ϕ−1 (mod q), so the left-hand side is 0 modulo q, implying (ℓi − ℓc )p ≡ 0 (mod q). Because p and q are coprime, ℓi − ℓc ≡ 0 (mod q). Now assume g ≤ q. Then 0 ≤ ℓi , ℓc < g ≤ q ⇒ |ℓi − ℓc | < q, so the congruence modulo q forces ℓi = ℓc . Substituting back yields xi,ϕ − xc,ϕ = g(xi,ϕ−1 − xc,ϕ−1 ) (mod p). Thus, as long as the candidate remains stuck to the same true neighbor, the difference is multiplied by g at each phase. Unrolling over N phases gives |xi,N − xc,N | = g N |xi,0 − xc,0 |,
ignoring modular wraparound to expose the raw growth. Although the actual dynamics are modulo p, the absolute difference cannot exceed p, so once g N |xi,0 − xc,0 | > p, continued sticking becomes impossible. Hence the number of stuck phases is bounded by p , ∆0 = |xi,0 − xc,0 |. N ≤ 1 + logg ∆0 Since stuck candidates must initially satisfy |xi,0 − xc,0 | = kq, k ∈ Z+ , we obtain the conservativebound log(p/q) p =1+ . N ≤ 1 + logg q log g Therefore, no false candidate can remain stuck to a single true neighbor for more than logarithmically many phases. In particular, this already implies O(L log K) discovery time for small values such as L ≤ 3. 2) Window-Based Separation Analysis (General Case): For larger L, a false candidate may survive by colliding with different true neighbors across phases. To handle this case, we use a window-based covering argument over the multiplicative sequence induced by g. Phase behavior and collision model: In phase ϕ, xi,ϕ = g ϕ xi,0 mod p. Two nodes i and j collide if xi,ϕ ≡ xj,ϕ (mod q), equivalently, g ϕ (xi,0 − xj,0 ) mod p ≡ 0
(mod q).
Let rij = xi,0 − xj,0 . Then a collision occurs when g ϕ rij mod p mod q ∈ {0, p mod q}, where the two cases correspond to the two possible orderings of g ϕ xi,0 mod p and g ϕ xj,0 mod p. Boolean collision window: Consider the sequence −1 {g ϕ rij mod p}W ϕ=0
and mark phase ϕ as True whenever g ϕ rij mod p mod q ∈ {0, p mod q}. Because multiplication by g permutes Z∗p , this sequence behaves like a cyclic traversal of residue values, and changing the pair (i, j) only cyclically shifts the same sequence. The number of residues in Zp satisfying x mod q ∈ {0, p mod q} is approximately (2/q)p, so 2 P [True] = . q This gives a certifiable sufficient condition for separation: for fixed (p, q, g), one can compute {g ϕ r mod p mod q} and verify in linear time whether every window satisfies the required separation property. Since different pairs correspond only to cyclic shifts, it suffices to check one representative sequence. In our implementation, we perform this verification
after parameter selection; if it fails, one may increase the window length W . Sliding window argument: Fix a window of W phases and let Nhits be the number of True entries in that window. Then 2W E[Nhits ] = . q Set 2W 4W µ= , t = 2µ = . q q Applying the Chernoff bound, eµ t Pr[Nhits ≥ t] ≤ exp(−µ) (6) t 4W e q 2W . (7) = exp − q 2 Hence the tail probability decays exponentially in W/q. Union bound over all shifts: There are at most p cyclic shifts of the sequence, so W Pr[∃ window with Nhits > 2E] ≤ p exp −0.76 . q To make this probability smaller than 1, it is sufficient that p e−0.76W/q < 1, ⇒ W > 1.33 q log p. Separation guarantee: Take W = 2q log p. Then, with high probability, every window of length W contains at most 4W W 2W = =O 2· q q q marked collision positions. A false candidate can survive only by aligning with at least two true neighbors per phase, so over W phases it would require at least 2W admissible collision slots across the L relevant sequences. But the total number of marked positions available across those L windows is at most 4W L· . q Therefore survival is impossible whenever 4W q L· < 2W ⇐⇒ L< , q 2 which holds by construction when q > 2L. Final deterministic bound: Thus no false candidate can survive beyond W = O(q log p) phases. Since each phase consists of q rounds, the total deterministic runtime is W q = O(q 2 log p) = O(L2 log K), using q = O(L) and log p = O(log K). This establishes deterministic convergence for arbitrary (K, L)-bounded interference topologies. C. Probabilistic Runtime Analysis We now derive the expected number of phases needed to eliminate all false candidates with high probability. Let a receiver have s ≤ L true neighbors, and let xC be a false candidate. In phase ϕ, every node computes yi,ϕ = xi,ϕ mod q. Candidate xC survives phase ϕ only if its mapped round yC,ϕ collides with at least two true neighbors; silence or a singleton
eliminates it. Hence survival requires a triple collision. There are s s(s − 1) = 2 2 pairs of true neighbors, and each pair maps to the same round with probability approximately 1/q. Therefore L(L − 1) . E[Ncollisions ] ≤ 2q Assuming pessimistically that all such pairwise collisions occur in distinct rounds, we obtain L2 Psurvive < 2 . 2q With q = cL, c > 1, this becomes 1 Psurvive < 2 . 2c If M phases are used, then Ptotal = (Psurvive )M , K(Psurvive )
M
<K
−δ
M
(8) −(δ+1)
=⇒ (Psurvive ) < K , (9) (δ + 1) log K . (10) M> log(1/Psurvive ) Each phase uses q = O(L) rounds, so the total runtime is (δ + 1) log K Mq = O L · = O(L log K) log(1/Psurvive ) for constant δ and fixed c > 1. The analysis relies on the fact that xi,ϕ mod q behaves approximately like a pseudorandom uniform mapping across phases, justified by the full-cycle permutation induced by multiplication by a primitive root g in Z∗p . III. P ERFORMANCE E VALUATION AND S IMULATION R ESULTS We evaluate PRISM to validate the predicted scaling laws and quantify the effect of the design parameter q on discovery efficiency. Unless otherwise stated, simulations are conducted in a single-hop collision-channel setting with K transmitters and K receivers, where each receiver has an interference neighborhood of L transmitters drawn uniformly at random under the (K, L)-bounded degree model. We sweep K ∈ [128, 7234], use 200 topology realizations per configuration, and consider L ∈ {3, . . . , 12}. All algorithms are evaluated under the same collision-channel abstraction, topology realizations, and completion criterion. Performance is measured in communication rounds, i.e., the total number of rounds until all receivers complete topology discovery. Each round is treated as one abstract unit of controlplane effort, independent of physical-layer details such as modulation, coding, and bandwidth. We report two metrics: (i) the mean network completion time, defined as the average number of rounds required for the last receiver to finish across 200 realizations, and (ii) the maximum completion time across those realizations, capturing rare high-collision tail events. A key PRISM parameter is the per-phase modulus q. The ratio q/L trades off phase length and collision density: increasing q improves transmitter separation but increases the number of rounds per phase, whereas decreasing q shortens each phase but increases persistent collisions. To identify effective operating points, we generate heatmaps versus K and q/L, showing that the mean completion time is minimized
Algorithm 1 Simulated Execution of PRISM 1: Input: K, L, p, q, g 2: Assign each transmitter i a unique label xi,0 ∈ Z∗ p 3: For each receiver j, initialize Cj ← {1, . . . , K}, Nj ← ∅ 4: for each phase ϕ = 1, 2, . . . do 5: for each transmitter i = 1, . . . , K do 6: xi,ϕ ← (gxi,ϕ−1 ) mod p 7: yi,ϕ ← xi,ϕ mod q 8: end for 9: for each receiver j = 1, . . . , K do 10: for each round r = 0, . . . , q − 1 do 11: Observe active transmitters in round r 12: if no transmission then 13: Cj ← Cj \ {i ∈ Cj : yi,ϕ = r} 14: else if exactly one transmitter xA then 15: Nj ← Nj ∪ {xA } 16: Cj ← Cj \ {i ∈ Cj : yi,ϕ = r} 17: else 18: continue 19: end if 20: end for 21: if Cj = ∅ or |Nj | = L then 22: Mark Rxj complete 23: end if 24: end for 25: if all receivers are complete then 26: break 27: end if 28: end for 29: Output: Total rounds until full network discovery
near q/L ≈ 1.2, while the maximum completion time is minimized near q/L ≈ 1.6, indicating improved robustness to rare collision-heavy realizations. We simulate PRISM according to Algorithm 1: each transmitter is assigned a unique identifier in Z∗p and transmits in exactly one round per phase according to the residue-cycling rule; each receiver monitors all q rounds and updates its candidate set based on silence, singleton, or collision outcomes. The protocol terminates when every receiver identifies its full neighborhood, and the same completion criterion is used for all baselines. Using these empirically selected operating points, we evaluate the scaling behavior of PRISM. Figure 2a shows the mean completion time versus K for q/L = 1.2, exhibiting a clear logarithmic dependence with fitted trend 0.9 L log K, consistent with the bound O(L log K). Figure 2b shows the corresponding maximum completion time for q/L = 1.6, which also follows an approximately logarithmic trend of the form 0.9 L log K + C. Across all configurations, the variance remains small relative to the mean, while the maximum metric captures rare but severe collision realizations. These results confirm that PRISM achieves predictable and scalable topology discovery under collision-channel constraints. A. Baseline Algorithms and Adaptations We compare PRISM with five baselines: ALOHA [13], CSMA [14], the deterministic scheduling method of [9], the block-design-based discovery scheme of [15], and the sparse OFDMA-based approach of [16]. All methods are evaluated under the same slotted collision-channel abstraction, in which each round yields silence, a singleton, or a collision; only singleton observations reveal neighbors; and discovery terminates once every receiver identifies its complete neighborhood. For ALOHA and CSMA, each transmitter follows
(a) Relative degradation of the mean network completion time versus K and q/L. The optimum occurs near q/L ≈ 1.2.
(b) Relative degradation of the maximum network completion time versus K and q/L. The optimum occurs near q/L ≈ 1.6.
Fig. 1: Heatmaps of PRISM performance as a function of network size K and the ratio q/L
the standard random-access rule in the slotted setting. For [9], we use the original deterministic cyclic schedule and map each scheduled transmission opportunity to one discovery round. For [15], we retain the deterministic on–off structure while adapting the original asynchronous design to synchronous round-based discovery. For [16], we preserve the sparse access graph and singleton-peeling dynamics while abstracting away the physical-layer processing. To ensure fairness, we disable auxiliary physical-layer features in the original methods, including asynchronous timing, energy-awareness mechanisms, power-domain separation, and successive interference cancellation. Thus, performance differences reflect discovery structure rather than PHY-layer enhancements. For each (K, L) configuration, all methods are evaluated on the same 200 topology realizations. As shown in Figure 3, PRISM consistently requires fewer discovery rounds than all baselines, with the performance gap widening as K grows.
(a) Mean and interquartile range of discovery rounds versus network size K at q/L = 1.2. The observed scaling is well approximated by 0.9 L log K, and the narrow interquartile range indicates low variance across topology realizations.
Fig. 3: Comparison of mean network completion time (discovery rounds) for topology discovery. PRISM outperforms ALOHA [13], CSMA [14], [9], [15], and [16] across all tested K and L. R EFERENCES
(b) Maximum discovery rounds versus network size K at q/L = 1.6. The maximum completion time follows an approximate 0.9 L log K + C trend while preserving logarithmic scaling.
Fig. 2: Scaling behavior of PRISM.
IV. C ONCLUSION We presented PRISM, a deterministic and non-interactive framework for topology discovery in single-hop wireless networks under collision-channel constraints. PRISM uses modular arithmetic over multiplicative residue classes to construct fixed discovery schedules without feedback or probabilistic access. We showed that PRISM achieves complete discovery in O(L(1 + δ) log K) rounds in expectation and in O(L2 log K) rounds in the worst case. Simulations support these results, showing empirical scaling close to 0.9 L log K, with q/L ≈ 1.2 minimizing mean completion time and q/L ≈ 1.4–1.6 improving tail performance. We also showed that deterministic convergence can be certified efficiently through lineartime residue-alignment checks, making PRISM practical for settings requiring verifiable worst-case guarantees.
[1] V. V. Veeravalli and A. E. Gamal, Interference Management in Wireless Networks: Fundamental Bounds and the Role of Cooperation. Cambridge, U.K.: Cambridge University Press, 2018. [2] S. Vasudevan, M. Adler, D. Goeckel, and D. Towsley, “Efficient algorithms for neighbor discovery in wireless networks,” IEEE/ACM Trans. Netw., vol. 21, no. 1, pp. 69–83, Feb 2013. [3] A. Ahmed and B. H. Far, “Topology discovery for network fault management using mobile agents in ad-hoc networks,” in Proc. Can. Conf. Electr. Comput. Eng., Saskatoon, SK, Canada, May 2005, pp. 2041–2044. [4] Y. Bejerano, K. Guo, and T. Nandagopal, “Fast detection of compact topology representation for wireless networks,” in Proc. Conf. Local Comput. Netw. (LCN), Oct 2015, pp. 535–543. [5] M. Li and H.-L. Tsai, “Design and evaluation of a hybrid d2d discovery mechanism in 5g cellular networks,” in Proc. Int. Conf. Ubiquitous Future Netw. (ICUFN), Jul 2018, pp. 641–643. [6] J. Yang, S. C. Draper, and R. Nowak, “Learning the interference graph of a wireless network,” IEEE Trans. Signal Inf. Process. Netw., vol. 3, no. 3, pp. 631–646, Sep 2017. [7] O. Tirkkonen, Z. Li, L. Wei, and A. V. Vinel, “On–off necklace codes for asynchronous mutual discovery,” in Proc. IEEE 28th Annu. Int. Symp. Pers. Indoor Mobile Radio Commun. (PIMRC), Oct 2017, pp. 1–6. [8] N. Alon, A. Bar-Noy, N. Linial, and D. Peleg, “On the complexity of radio communication,” in Proc. 21st Annu. Symp. Theory Comput. (STOC), 1989, pp. 274–285. [9] T. Seyfi, A. P. Mohamed, and A. E. Gamal, “A number theoretic approach for fast discovery of single-hop wireless networks,” IEEE Networking Letters, vol. 3, no. 2, pp. 89–93, 2021. [10] V. S. Annapureddy, A. El Gamal, and V. V. Veeravalli, “Degrees of freedom of interference channels with comp transmission and reception,” IEEE Transactions on Information Theory, vol. 58, no. 9, pp. 5740– 5760, 2012. [11] A. E. Gamal, V. S. Annapureddy, and V. V. Veeravalli, “Interference channels with coordinated multipoint transmission: Degrees of freedom, message assignment, and fractional reuse,” IEEE Transactions on Information Theory, vol. 60, no. 6, pp. 3483–3498, 2014. [12] Y. Karacora, T. Seyfi, and A. E. Gamal, “The role of transmitter cooperation in linear interference networks with block erasures,” in 2017 51st Asilomar Conference on Signals, Systems, and Computers, 2017, pp. 1427–1431. [13] N. Abramson, “The aloha system: another alternative for computer communications,” in Proceedings of the November 17-19, 1970, Fall Joint Computer Conference, ser. AFIPS ’70 (Fall). New York, NY, USA: Association for Computing Machinery, 1970, p. 281–285. [Online]. Available: https://doi.org/10.1145/1478462.1478502 [14] L. Kleinrock and F. Tobagi, “Packet switching in radio channels: Part i - carrier sense multiple-access modes and their throughput-delay characteristics,” IEEE Transactions on Communications, vol. 23, no. 12, pp. 1400–1416, 1975. [15] S. Choi and G. Yi, “Asymmetric block design-based neighbor discovery protocol in sensor networks,” Sustainability, vol. 8, no. 5, 2016. [Online]. Available: https://www.mdpi.com/2071-1050/8/5/431 [16] X. Chen, L. Liu, D. Guo, and G. W. Wornell, “Asynchronous massive access and neighbor discovery using ofdma,” IEEE Transactions on Information Theory, vol. 69, no. 4, pp. 2364–2384, 2023.