CS Paper Radar

Quantifying the Relay-Coverage Trade-off in Mobile Multihop Flooding

Johannes F. Loevenich, Thies Möhlenhof, Roberto Rigolin F. Lopes

cs.NI cs.LG ·submitted 2026-10-29 08:01 UTC · v1
unusual

Abstract

Network-wide flooding in mobile multihop networks selects relays from locally maintained topology information. Mobility makes this information outdated, leaving two basic responses: add redundant relays or refresh the topology and re-select relays more frequently. How these mechanisms trade reliability for overhead, however, is not well quantified. We quantify this trade-off on a public trace of 157 vehicles using Optimized Link State Routing version 2 (OLSRv2) and exact minimum-cost relay sets. Twofold coverage increases median relay-cover lifetime by only 2.3x, rather than about an order of magnitude as predicted by an independent-hazard model. The limitation is structural: 43.6 % of two-hop neighbours have only one possible relay, and newly appearing neighbours invalidate existing covers. Moreover, the delivery gain of a second relay falls from 0.061 to 0.016 when relay selection uses instantaneous link state, showing that redundancy mainly compensates for outdated topology information. Relay coverage and topology refresh therefore form a measurable redundancy-freshness trade-off rather than independent robustness mechanisms. In our trace, twofold coverage has lower overhead below about 100 bit/s of application flooding per node, whereas fresher topology information has lower overhead above it. This makes relay redundancy a load-dependent design choice rather than a fixed heuristic robustness setting.

Closest papers

Nearest neighbours by meaning across the whole index.

Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon

cs.AI stat.MLcs.LG ·2026-09-30 ·Johannes F. Loevenich, Thies Moehlenhof, Laurin Holz, Maxime Schwarzer, Tobias Huerten +1 more
theory similarity 0.52
Abstract

Neural combinatorial optimization typically assumes a centralized solver that reads the whole instance. We study the opposite: combinatorial optimization under a hard information horizon, where every node commits to its share of a global solution seeing only its $k$-hop neighborhood, and those commitments must compose into a globally feasible solution. We formalize this as local set cover and instantiate it on weighted multipoint relay (MPR) selection, the NP-hard 2-hop covering problem of the Optimized Link State Routing Protocol version 2 (OLSRv2) routing protocol (RFC~7181), whose horizon is imposed by the protocol, not chosen by the modeler. We prove two results. Any deterministic selector whose horizon is one hop short must either fail coverage or land a factor $Δ$ from optimal, and an $L$-layer graph neural network (GNN) read out at the deciding node is exactly an $L$-hop selector, so capacity cannot buy back radius. Conversely, at the horizon a \ac{GNN} of depth $O(Δ)$ reproduces the RFC~7181 covering greedy, and at width $O(c_{\max}Δ)$ its metric-aware weighted analogue, inheriting the $(1+\lnΔ_2)$-approximation in both cases. Empirically, a 3-layer \ac{GATv2} with a coverage-completing decoder, behavior-cloned from the CP-SAT optimum, reaches $\text{cost}/\text{opt}=1.030\pm0.001$ against greedy's $1.138$, closing $79.1\%$ of the gap at $100\%$ coverage. Restricting the same learner to one hop, on identical instances with the same decoder and demonstrations, collapses it to $1.344$, far worse than greedy. Two transfer checks target real-world networks. OLSRv2's unmodified selection code matches our cardinality greedy on $200/200$ unit-cost instances, and on $40{,}308$ instances of real battalion mobility the frozen model closes $48\%$ of the gap at full coverage. The information horizon, not the model capacity, is the most significant variable.

0.23

Topology Design for Distributed Consensus with Relay-Assisted Communication

eess.SY math.OC ·2026-10-06 ·Shuyi Ren, Zheng Chen, Erik G. Larsson
publishedunusual similarity 0.52
Abstract · 5 pages, 4 figures. Accepted by IEEE SPAWC 2026

This paper focuses on relay-assisted topology optimization to accelerate the convergence of distributed consensus algorithms over weakly connected networks. Instead of permanently adding a fixed set of relay links, we introduce a time-sharing framework where multiple relay configurations are activated in a probabilistic manner. An ActiveSet-based algorithm incrementally constructs candidate relay edge sets and jointly optimizes the mixing matrices and the associated relay set activation probabilities, allowing adaptive relay selection in the optimization process. Simulation results demonstrate a substantially improved performance-cost trade-off compared with fixed-cardinality relay selection strategies.

0.37

Criticality-Aware RAN Function Placement for Robust 6G Networks

cs.NI ·2026-11-10 ·Gabriel M. Almeida, Joao F. Santos, Walid Saad, Nicola Marchetti, Kleber V. Cardoso
similarity 0.50
Abstract · 6 pages, 6 figures

The disaggregation of base stations into radio access network (RAN) functions introduces new vulnerabilities to mobile networks, as disruptions in cloud locations can interrupt multiple RAN functions and trigger cascading failures, leading to widespread outages. In this paper, we propose a criticality-aware RAN function placement solution to improve the robustness of disaggregated mobile networks against random failures and targeted attacks. Our solution optimizes the placement of centralized units (CUs) and distributed units (DUs) across cloud locations to reduce functional dependencies and limit the criticality of cloud locations, while preserving the cost benefits of RAN function centralization. We formulate the placement as an optimization model that jointly minimizes functional dependency and placement cost, subject to criticality constraints, as well as computing and transport requirements. We numerically evaluated our approach on a real-world mobile network topology across multiple disruption scenarios and demonstrated that our solution improves robustness, yielding up to 75% more operational radio units (RUs) after disruptions than existing approaches.

0.27

Sociotechnical Aspects of Tor Relay Rejection

cs.CR ·2026-09-14 ·Jules Dejaeghere, Lionel Goffaux, Pierre Luycx, Hosam Elkoulak, Florentin Rochet
similarity 0.50
Abstract · arXiv version, extended from the WPES. 17 pages, 11 figures, 1 table

In 2019, the Tor Project enforced an end-of-life (EoL) policy for Tor versions, leading to the rejection of outdated relays, amounting to a notable fraction of consensus weight. While this policy aids network maintenance, reduces backporting efforts, and shortens vulnerability exposure, its sociotechnical implications remain unstudied. A user study ($N=26$) reveals that relay operators, though not universally aware of the EoL policy, generally view it favorably. Operational practices vary, occasionally excluding newly installed relays from the network. Network simulations, grounded in historical data, assess the policy's immediate impact on Tor clients against common adversaries. Results indicate a marginal adversarial advantage, with network churn (i.e., relays entering and exiting) exerting a more pronounced effect on user anonymity. Security metrics are introduced to evaluate relay contributions against two adversary models, enabling ranking by individual utility and security. Analysis of four exclusion rounds shows that a minority of rejected relays typically account for over 50% of the security provided by all excluded relays. Recommendations for EoL policy implementation are proposed to mitigate potential drawbacks.

0.39

Adaptive Coverage Algorithms for Mobile Ad Hoc Networks in Dynamic Worlds

cs.RO cs.MA ·2026-10-30 ·Hugo Gandhi, Edwin Meriaux, Antonio Loría
publishedbenchmark similarity 0.50
Abstract · 8 pages, 10 figures. Accepted to the 2026 IEEE MIT Undergraduate Research Technology Conference (URTC)

This paper extends an existing framework for the coordination of mobile agents in unknown worlds, by considering the possibility of dynamic instability. In the original problem, known as the Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP) (arXiv:2512.09495), the multi-agent system must establish a communication network which completely covers an initially unknown constrained space. However, the POCGAGP fails to account for the unpredictability often seen in real-world deployment. To address this, the dynamic case (DPOCGAGP) introduces two settings which can influence the mobile network during deployment: Agent Loss and World Change, which represent dynamic changes to the world. Within this study, we present advancements to two state-of-the-art algorithms, the Centralized Agent-Directed Exploration for Network Coverage (CADENCE), and its decentralized analogue, DADENCE, to provide solutions in these cases. We then compare their performance against another state-of-the-art benchmark algorithm, and show that the adapted algorithms outperform across our benchmark test set, which comprises over 4500 test cases of varied size and structure.

0.28

Topology Construction Algorithms for DECT NR+ in Normal and Ultra-Dense Deployments

cs.NI ·2026-10-08 ·Andrey Samuylov, Dmitri Moltchanov, Roman Glazkov, Juho Pirskanen, Jussi Numminen +1 more
similarity 0.50
Abstract · 14 pages, 17 figures. Submitted to IEEE Transactions on Mobile Computing

The 5G-grade DECT NR+ technology designed to support massive machine-type communications (mMTC) relies on the decentralized mesh connectivity concept. The currently utilized topology construction algorithms are very sensitive to the node density, which causes interference at the node association phase and may lead to instable topologies. In this study, we propose several algorithms that need to be utilized at relay and leaf nodes to allow stabilization of the topology: (i) load-dependent relay allocation, (ii) hysteresis-based association control, (iii) blacklist-based association control, and (iv) smart beacon placement. Due to the complex interference structure in DECT NR+ mesh systems, we utilize system-level simulations to assess the performance in both normal and ultra-dense conditions in terms of the efficiency of topology construction and the performance characteristics of the resulting topology. Our results show that dense DECT NR+ networks do suffer from topology instability, with reassociation rates exceeding 10 per second and recovery times lasting over 10 minutes. By implementing the proposed mechanisms, the network dynamically scales, reducing the number of required relays by more than half, from 34% to 15%. They also stabilize the topology by reducing the reassociation rates to just 2-3 per second allowing large-scale networks of several hundred nodes to operate efficiently.

0.30

Performance Evaluation of HAPS-enabled Coverage Enhancement in Hard-to-Reach Areas

cs.NI ·2026-09-04 ·Hao Lin, Mustafa A. Kishk, Mohamed-Slim Alouini
top venue similarity 0.50
Abstract · 15 pages, 12 figures, published in IEEE Transactions on Wireless Communications

High altitude platform stations (HAPSs) are becoming a key component of future non-terrestrial networks (NTNs). HAPSs can serve a larger area than uncrewed aerial vehicles (UAVs) and offer lower propagation latency, maintenance expense, and energy costs than satellites. A major application of HAPSs is to serve the areas where terrestrial network (TN) deployment is infeasible, especially in hard-to-reach areas and post-disaster areas. For instance, in the Amazon rainforest, the Mediterranean region, and deserts, TN deployment is severely constrained by geographical and environmental conditions. Only areas close to transportation networks or coastlines can be covered, while large areas remain uncovered. Such coverage holes in hard-to-reach areas are typically overlooked in existing literature. Motivated by these realistic cases, in this paper, we use tools from stochastic geometry to mathematically model hard-to-reach areas where cellular terrestrial infrastructure only exists at their perimeter. We propose to deploy a HAPS constellation over this hard-to-reach area to enhance connectivity. For that setup, we derive the downlink (DL) and uplink (UL) coverage performance of the considered user equipment (UE) as a function of the location of the UE inside the coverage hole. Our results show how the number of HAPSs, beamwidth, and HAPS altitude affect the DL and UL coverage probabilities. Finally, we provide multiple useful guidelines for future HAPS deployment.

0.46

HERO-D3QN: Inter-Cluster Routing with Energy-Aware Soft Constraints in Wireless Sensor Networks

cs.NI ·2026-11-10 ·Weihao Wang, Heng Yang, Guangbo Chen, Shanshan Li, Jiulin Guo +4 more
similarity 0.49
Abstract · 23 pages, 20 figures

Inter-cluster forwarding in wireless sensor networks can concentrate energy consumption on frequently selected relays, while hard energy thresholds restrict forwarding choices as residual energy declines. We propose Hierarchical Energy-balanced Routing Optimization based on a dueling double deep Q-network (D3QN), termed HERO-D3QN. Given the cluster structure, the method combines direction- and cost-based relay screening with energy-aware soft constraints. Relays below an adaptive energy threshold remain eligible if the other selection criteria are met. An enhanced state representation captures relay energy, progress toward the sink, potential forwarding load, and hotspot risk, and a multi-objective reward guides learning. In the comparison with D3QN using the same node locations, HERO-D3QN delayed first-node death (FND) from time step 629 to 1269 and reduced peak residual energy variance by 55.5%. In the ablation study, the full method achieved the latest FND and half-node death (HND) and the largest cumulative transmitted volume (170.52 Mbit) among the tested variants. Across five seed settings in which node locations and the random processes used in training and evaluation varied jointly, the coefficients of variation of FND, HND, and transmitted volume were 8.26%, 2.75%, and 3.88%, respectively. These results demonstrate the effectiveness of HERO-D3QN in delaying early node failure and reducing peak energy dispersion.

0.37