Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments

DOI10.1287/IJOC.2020.1045zbMATH Open1492.90031arXiv1706.03177OpenAlexW2984733936MaRDI QIDQ5084628FDOQ5084628

Authors: Matthias Bentert, René van Bevern, André Nichterlein, Rolf Niedermeier, Pavel V. Smirnov 

Publication date: 28 June 2022

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Abstract: We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless communication network: Given an edge-weighted $n$-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. On the negative side, we show that $o(logn)$-approximating the difference $d$ between the optimal solution cost and a natural lower bound is NP-hard and that, under the Exponential Time Hypothesis, there are no exact algorithms running in $2^{o(n)}$ time or in $f(d)cdot{n}^{O(1)}$ time for any computable function $f$. Moreover, we show that the special case of connecting $c$ network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size $c^{O(1)}$ unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects $O(logn)$ connected components with minimum additional cost in polynomial time. These algorithms are motivated by application scenarios of monitoring areas or where an existing sensor network may fall apart into several connected components due to sensor faults. In experiments, the algorithm outperforms CPLEX with known ILP formulations when $n$ is sufficiently large compared to $c$.

Full work available at URL: https://arxiv.org/abs/1706.03177

Recommendations

• Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
• Exact algorithms for the minimum power symmetric connectivity problem in wireless networks
• Algorithms for Wireless Sensor Networks: Design, Analysis and Experimental Evaluation
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• Approximation algorithms for minimum power \(k\) backbone node \(r\)-connected subgraph problem in wireless sensor networks
• Parameterized complexity of Min-power multicast problems in wireless ad hoc networks

zbMATH Keywords

color-codingapproximation hardnessconnected spanning subgraphsexperimental comparisonparameterized complexity analysisparameterization above lower boundsmonitoring areasreconnecting sensor networks

Mathematics Subject Classification ID

Communication networks in operations research (90B18)

Cites Work

• Fundamentals of parameterized complexity
• The design of approximation algorithms
• Which problems have strongly exponential complexity?
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Parametrized complexity theory.
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Color-coding
• Title not available (Why is that?)
• Parameterized algorithms
• Title not available (Why is that?)
• On the complexity of \(k\)-SAT
• Strong computational lower bounds via parameterized complexity
• From few components to an Eulerian graph by adding ARCS
• Rural postman parameterized by the number of components of required edges
• Experiments on data reduction for optimal domination in networks
• Power consumption in packet radio networks
• Survivable network design problems in wireless networks
• A new view on rural postman based on Eulerian extension and matching
• Exact algorithms for the minimum power symmetric connectivity problem in wireless networks
• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• Power assignment in radio networks with two power levels
• A completeness theory for polynomial (Turing) kernelization
• Kernelization. Theory of parameterized preprocessing
• On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• Variable neighborhood search variants for min-power symmetric connectivity problem
• Minimizing the number of max-power users in ad-hoc wireless networks with minimum node degree requirements
• On approximate data reduction for the Rural Postman Problem: Theory and experiments
• Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
• A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments
• An average case analysis of the minimum spanning tree heuristic for the power assignment problem

Cited In (9)

• On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
• A Branch-and-Cut Algorithm for the Minimum Energy Symmetric Connectivity Problem in Wireless Networks
• Variable neighborhood search-based heuristics for MIN-power symmetric connectivity problem in wireless networks
• Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
• Exact algorithms for the minimum power symmetric connectivity problem in wireless networks
• Strong minimum energy hierarchical topology in wireless sensor networks
• Title not available (Why is that?)
• Polynomial-time data reduction for weighted problems beyond additive goal functions
• An iterative exact solution for the dual power management problem in wireless sensor network

Uses Software

• CPLEX
• QNet

This page was built for publication: Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084628)