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

DOI10.1287/IJOC.2020.1045MaRDI QIDQ5084628zbMATH OpenOpenAlexFDO

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)

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A completeness theory for polynomial (Turing) kernelization
• A new view on rural postman based on Eulerian extension and matching
• 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
• Color-coding
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Exact algorithms for the minimum power symmetric connectivity problem in wireless networks
• Experiments on data reduction for optimal domination in networks
• From few components to an Eulerian graph by adding ARCS
• Fundamentals of parameterized complexity
• Kernelization. Theory of parameterized preprocessing
• 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
• On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem
• On the complexity of \(k\)-SAT
• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
• Parameterized algorithms
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parametrized complexity theory.
• Power assignment in radio networks with two power levels
• Power consumption in packet radio networks
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• Rural postman parameterized by the number of components of required edges
• Strong computational lower bounds via parameterized complexity
• Survivable network design problems in wireless networks
• The design of approximation algorithms
• Variable neighborhood search variants for min-power symmetric connectivity problem
• Which problems have strongly exponential complexity?

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
• scientific article; zbMATH DE number 5120927 (Why is no real title available?)
• 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

Describes a project that uses

Uses Software

• QNet
• CPLEX

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)