IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v34y2022i1p55-75.html
   My bibliography  Save this article

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

Author

Listed:
  • Matthias Bentert

    (Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, 10587 Berlin, Germany)

  • René van Bevern

    (Department of Mechanics and Mathematics, Novosibirsk State University, 630090 Novosibirsk, Russian Federation)

  • André Nichterlein

    (Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, 10587 Berlin, Germany)

  • Rolf Niedermeier

    (Algorithmics and Computational Complexity, Faculty IV, Technische Universität Berlin, 10587 Berlin, Germany)

  • Pavel V. Smirnov

    (Department of Mechanics and Mathematics, Novosibirsk State University, 630090 Novosibirsk, Russian Federation)

Abstract

We study a problem of energy-efficiently connecting a symmetric wireless communication network: given an n -vertex graph with edge weights, find a connected spanning subgraph of minimum cost, where the cost is determined by each vertex paying the heaviest edge incident to it in the subgraph. The problem is known to be NP-hard. Strengthening this hardness result, we show that even o (log n )-approximating the difference d between the optimal solution cost and a natural lower bound is NP-hard. Moreover, we show that under the exponential time hypothesis, there are no exact algorithms running in 2 o ( n ) time or in f ( d ) ⋅ n O ( 1 ) time for any computable function f . We also 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 (log n )-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 because of sensor faults. In experiments, the algorithm outperforms CPLEX with known integer linear programming (ILP) formulations when n is sufficiently large compared with c . Summary of Contribution: Wireless sensor networks are used to monitor air pollution, water pollution, and machine health; in forest fire and landslide detection; and in natural disaster prevention. Sensors in wireless sensor networks are often battery-powered and disposable, so one may be interested in lowering the energy consumption of the sensors in order to achieve a long lifetime of the network. We study the min-power symmetric connectivity problem, which models the task of assigning transmission powers to sensors so as to achieve a connected communication network with minimum total power consumption. The problem is NP-hard. We provide perhaps the first parameterized complexity study of optimal and approximate solutions for the problem. Our algorithms work in polynomial time in the scenario where one has to reconnect a sensor network with n sensors and O (log n )-connected components by means of a minimum transmission power increase or if one can find transmission power lower bounds that already yield a network with O (log n )-connected components. In experiments, we show that, in this scenario, our algorithms outperform previously known exact algorithms based on ILP formulations.

Suggested Citation

  • Matthias Bentert & René van Bevern & André Nichterlein & Rolf Niedermeier & Pavel V. Smirnov, 2022. "Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 55-75, January.
  • Handle: RePEc:inm:orijoc:v:34:y:2022:i:1:p:55-75
    DOI: 10.1287/ijoc.2020.1045
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.1045
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2020.1045?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Renhua Li & Leonie U Hempel & Tingbo Jiang, 2015. "A Non-Parametric Peak Calling Algorithm for DamID-Seq," PLOS ONE, Public Library of Science, vol. 10(3), pages 1-12, March.
    2. Jochen Alber & Nadja Betzler & Rolf Niedermeier, 2006. "Experiments on data reduction for optimal domination in networks," Annals of Operations Research, Springer, vol. 146(1), pages 105-117, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Carlos V. G. C. Lima & Dieter Rautenbach & Uéverton S. Souza & Jayme L. Szwarcfiter, 2022. "On the computational complexity of the bipartizing matching problem," Annals of Operations Research, Springer, vol. 316(2), pages 1235-1256, September.
    2. Hans L. Bodlaender & Josse Dobben de Bruyn & Dion Gijswijt & Harry Smit, 2022. "Constructing tree decompositions of graphs with bounded gonality," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2681-2699, November.
    3. Marjan Marzban & Qian-Ping Gu & Xiaohua Jia, 2016. "New analysis and computational study for the planar connected dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 32(1), pages 198-225, July.
    4. Édouard Bonnet & Sergio Cabello, 2021. "The complexity of mixed-connectivity," Annals of Operations Research, Springer, vol. 307(1), pages 25-35, December.
    5. Fomin, Fedor V. & Fraigniaud, Pierre & Golovach, Petr A., 2022. "Present-biased optimization," Mathematical Social Sciences, Elsevier, vol. 119(C), pages 56-67.
    6. Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.
    7. Juho Lauri & Sourav Dutta & Marco Grassia & Deepak Ajwani, 2023. "Learning fine-grained search space pruning and heuristics for combinatorial optimization," Journal of Heuristics, Springer, vol. 29(2), pages 313-347, June.
    8. Niels Lindner & Julian Reisch, 2022. "An analysis of the parameterized complexity of periodic timetabling," Journal of Scheduling, Springer, vol. 25(2), pages 157-176, April.
    9. Van Bang Le & Sheng-Lung Peng, 2018. "On the complete width and edge clique cover problems," Journal of Combinatorial Optimization, Springer, vol. 36(2), pages 532-548, August.
    10. Gramm, Jens & Guo, Jiong & Huffner, Falk & Niedermeier, Rolf & Piepho, Hans-Peter & Schmid, Ramona, 2007. "Algorithms for compact letter displays: Comparison and evaluation," Computational Statistics & Data Analysis, Elsevier, vol. 52(2), pages 725-736, October.
    11. Lucci, Mauro & Nasini, Graciela & Severín, Daniel, 2024. "Solving the List Coloring Problem through a branch-and-price algorithm," European Journal of Operational Research, Elsevier, vol. 315(3), pages 899-912.
    12. Goharshady, Amir Kafshdar & Mohammadi, Fatemeh, 2020. "An efficient algorithm for computing network reliability in small treewidth," Reliability Engineering and System Safety, Elsevier, vol. 193(C).
    13. Rim Wersch & Steven Kelk & Simone Linz & Georgios Stamoulis, 2022. "Reflections on kernelizing and computing unrooted agreement forests," Annals of Operations Research, Springer, vol. 309(1), pages 425-451, February.
    14. Danny Hermelin & Shlomo Karhi & Michael Pinedo & Dvir Shabtay, 2021. "New algorithms for minimizing the weighted number of tardy jobs on a single machine," Annals of Operations Research, Springer, vol. 298(1), pages 271-287, March.
    15. Johannes Blum, 2022. "W[1]-hardness of the k-center problem parameterized by the skeleton dimension," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2762-2781, November.
    16. Duv{s}an Knop & v{S}imon Schierreich, 2023. "Host Community Respecting Refugee Housing," Papers 2302.13997, arXiv.org, revised Mar 2023.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:34:y:2022:i:1:p:55-75. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.