IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v75y2019i4d10.1007_s10898-019-00827-5.html
   My bibliography  Save this article

Online hole healing for sensor coverage

Author

Listed:
  • Zhao Zhang

    (Zhejiang Normal University)

  • Zaixin Lu

    (Washington State University)

  • Xianyue Li

    (Lanzhou University)

  • Xiaohui Huang

    (Zhejiang Normal University)

  • Ding-Zhu Du

    (University of Texas at Dallas)

Abstract

Many applications of wireless sensor networks require a quality of service including coverage and connectivity. However, both coverage and connectivity may be lost due to failure of sensors, in which case some holes appear. To heal holes, a hybrid wireless sensor system with mobile sensors has been proposed in the literature. Redundant mobile sensors can move to heal holes. Limited by energy supply, the largest distance that a mobile sensor can move cannot be too large. Such a consideration calls for cascade hole healing. This paper studies online cascade hole healing problem in which holes appear online and should be healed immediately without knowing future locations of holes. Two targets are considered, aiming to minimize the total energy consumption and the largest individual energy consumption, respectively. We show that naive greedy strategy does not work well for both targets, having exponentially large competitive ratios in a worst case. Then, we present two online algorithms with theoretically guaranteed tight competitive ratios. Extensive experiments show that our algorithm approximates offline optimal solutions fairly well.

Suggested Citation

  • Zhao Zhang & Zaixin Lu & Xianyue Li & Xiaohui Huang & Ding-Zhu Du, 2019. "Online hole healing for sensor coverage," Journal of Global Optimization, Springer, vol. 75(4), pages 1111-1131, December.
    • Handle: RePEc:spr:jglopt:v:75:y:2019:i:4:d:10.1007_s10898-019-00827-5
    DOI: 10.1007/s10898-019-00827-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-019-00827-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-019-00827-5?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Andrew V. Goldberg & Robert E. Tarjan, 1990. "Finding Minimum-Cost Circulations by Successive Approximation," Mathematics of Operations Research, INFORMS, vol. 15(3), pages 430-466, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Havrda, Marek & Klocek, Adam, 2023. "Well-being impact assessment of artificial intelligence – A search for causality and proposal for an open platform for well-being impact assessment of AI systems," Evaluation and Program Planning, Elsevier, vol. 99(C).
    2. Sparacino, Daniele, 2019. "Funktionsweise und Möglichkeiten von Google Shopping mit einem Fokus auf Showcase Ads," Working Papers for Marketing & Management 42, Offenburg University, Department of Media and Information.
    3. Zweigle, Tanja & Hellinghausen, Paul, 2021. "Relevanz und Potential von TikTok für die Social-Media-Marketing-Strategie von Unternehmen," IU Discussion Papers - Marketing & Communication 01 (Dez. 2021), IU International University of Applied Sciences.
    4. Kühn, Frauke & Lichters, Marcel & Krey, Nina, 2020. "The touchy issue of produce: Need for touch in online grocery retailing," Journal of Business Research, Elsevier, vol. 117(C), pages 244-255.

    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. Durga Prasad Khanal & Urmila Pyakurel & Tanka Nath Dhamala & Stephan Dempe, 2022. "Efficient Algorithms for Abstract Flow with Partial Switching," SN Operations Research Forum, Springer, vol. 3(4), pages 1-17, December.
    2. Zheng, Hong & Peeta, Srinivas, 2014. "Cost scaling based successive approximation algorithm for the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 68(C), pages 17-30.
    3. Carlo Mannino & Alessandro Mascis, 2009. "Optimal Real-Time Traffic Control in Metro Stations," Operations Research, INFORMS, vol. 57(4), pages 1026-1039, August.
    4. Marins, Fernando A. S. & Senne, Edson L. F. & Darby-Dowman, Ken & Machado, Arlene F. & Perin, Clovis, 1997. "Algorithms for network piecewise-linear programs: A comparative study," European Journal of Operational Research, Elsevier, vol. 97(1), pages 183-199, February.
    5. Castro, Jordi & Nasini, Stefano, 2021. "A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks," European Journal of Operational Research, Elsevier, vol. 290(3), pages 857-869.
    6. Wang, Yan & Wang, Junwei, 2019. "Integrated reconfiguration of both supply and demand for evacuation planning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 82-94.
    7. Luce Brotcorne & Martine Labbé & Patrice Marcotte & Gilles Savard, 2000. "A Bilevel Model and Solution Algorithm for a Freight Tariff-Setting Problem," Transportation Science, INFORMS, vol. 34(3), pages 289-302, August.
    8. Karine Deschinkel & Sid-Ahmed-Ali Touati & Sébastien Briais, 2011. "SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling," Journal of Combinatorial Optimization, Springer, vol. 22(4), pages 819-844, November.
    9. Mehdi Ghiyasvand, 2019. "An $$O(n(m+n\log n)\log n)$$O(n(m+nlogn)logn) time algorithm to solve the minimum cost tension problem," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 957-969, April.
    10. Luce Brotcorne & Martine Labbé & Patrice Marcotte & Gilles Savard, 2001. "A Bilevel Model for Toll Optimization on a Multicommodity Transportation Network," Transportation Science, INFORMS, vol. 35(4), pages 345-358, November.
    11. Hongbo Li & Hanyu Zhu & Linwen Zheng & Fang Xie, 2024. "Software project scheduling under activity duration uncertainty," Annals of Operations Research, Springer, vol. 338(1), pages 477-512, July.
    12. Al-Takrouri, Saleh & Savkin, Andrey V., 2013. "A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(23), pages 6135-6145.
    13. Wei Zhang & Jianzhong Zhou & Yi Liu & Xiao Chen & Chao Wang, 2016. "Emergency evacuation planning against dike-break flood: a GIS-based DSS for flood detention basin of Jingjiang in central China," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 81(2), pages 1283-1301, March.
    14. Wei Zhang & Jianzhong Zhou & Yi Liu & Xiao Chen & Chao Wang, 2016. "Emergency evacuation planning against dike-break flood: a GIS-based DSS for flood detention basin of Jingjiang in central China," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 81(2), pages 1283-1301, March.
    15. Mehdi Ghiyasvand, 2017. "A faster strongly polynomial time algorithm to solve the minimum cost tension problem," Journal of Combinatorial Optimization, Springer, vol. 34(1), pages 203-217, July.
    16. Antonio Frangioni & Antonio Manca, 2006. "A Computational Study of Cost Reoptimization for Min-Cost Flow Problems," INFORMS Journal on Computing, INFORMS, vol. 18(1), pages 61-70, February.
    17. Gallegos, María Teresa & Ritter, Gunter, 2010. "Using combinatorial optimization in model-based trimmed clustering with cardinality constraints," Computational Statistics & Data Analysis, Elsevier, vol. 54(3), pages 637-654, March.

    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:spr:jglopt:v:75:y:2019:i:4:d:10.1007_s10898-019-00827-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.