Optimized Sparse Network Coverage via L1-norm Minimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912587753455616 |
|---|---|
| author | Paul, Souvik Sandoval, Iván Alexander Morales de Abreu, Giuseppe Thadeu Freitas |
| author_facet | Paul, Souvik Sandoval, Iván Alexander Morales de Abreu, Giuseppe Thadeu Freitas |
| contents | The selection of nodes that can serve as cluster heads, local sinks and gateways is a critical challenge in distributed sensor and communication networks. This paper presents a novel framework for identifying a minimal set of nexus nodes to ensure full network coverage while minimizing cost. By formulating the problem as a convex relaxation of the NP-hard set cover problem, we integrate the graph theoretic centrality measures of node degree and betweenness centrality into a cost function optimized via a relaxed L1-norm minimization. The proposed approach is applicable to static and dynamic network scenarios and does not require location or distance estimation. Through simulations across various graph models and dynamic conditions, it is shown that the method achieves faster execution times (lower complexity) and competitive sparsity compared to classical greedy and genetic algorithms (GA), offering a robust, distributed, and cost-efficient node selection solution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_11994 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimized Sparse Network Coverage via L1-norm Minimization Paul, Souvik Sandoval, Iván Alexander Morales de Abreu, Giuseppe Thadeu Freitas Signal Processing The selection of nodes that can serve as cluster heads, local sinks and gateways is a critical challenge in distributed sensor and communication networks. This paper presents a novel framework for identifying a minimal set of nexus nodes to ensure full network coverage while minimizing cost. By formulating the problem as a convex relaxation of the NP-hard set cover problem, we integrate the graph theoretic centrality measures of node degree and betweenness centrality into a cost function optimized via a relaxed L1-norm minimization. The proposed approach is applicable to static and dynamic network scenarios and does not require location or distance estimation. Through simulations across various graph models and dynamic conditions, it is shown that the method achieves faster execution times (lower complexity) and competitive sparsity compared to classical greedy and genetic algorithms (GA), offering a robust, distributed, and cost-efficient node selection solution. |
| title | Optimized Sparse Network Coverage via L1-norm Minimization |
| topic | Signal Processing |
| url | https://arxiv.org/abs/2509.11994 |