IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v207y2010i2p1014-1026.html
   My bibliography  Save this article

A column generation based heuristic for sensor placement, activity scheduling and data routing in wireless sensor networks

Author

Listed:
  • TürkogullarI, Yavuz B.
  • Aras, Necati
  • AltInel, I. Kuban
  • Ersoy, Cem

Abstract

A wireless sensor network is a network consisting of distributed autonomous electronic devices called sensors. In this work, we develop a mixed-integer linear programming model to maximize the network lifetime by optimally determining locations of sensors and sinks, sensor-to-sink data flows, and activity schedules of the deployed sensors subject to coverage, flow conservation, energy consumption and budget constraints. Since solving this model is difficult except for very small instances, we propose a heuristic method which works on a reformulation of the problem. In the first phase of this heuristic, the linear programming relaxation of the reformulation is solved by column generation. The second phase consists of constructing a feasible solution for the original problem using the columns obtained in the first phase. Computational experiments conducted on a set of test instances indicate that both the accuracy and the efficiency of the proposed heuristic is quite promising.

Suggested Citation

  • TürkogullarI, Yavuz B. & Aras, Necati & AltInel, I. Kuban & Ersoy, Cem, 2010. "A column generation based heuristic for sensor placement, activity scheduling and data routing in wireless sensor networks," European Journal of Operational Research, Elsevier, vol. 207(2), pages 1014-1026, December.
    • Handle: RePEc:eee:ejores:v:207:y:2010:i:2:p:1014-1026
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00376-0
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Enrique Campos-Nañez & Alfredo Garcia & Chenyang Li, 2008. "A Game-Theoretic Approach to Efficient Power Management in Sensor Networks," Operations Research, INFORMS, vol. 56(3), pages 552-561, June.
    2. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    3. Alfieri, A. & Bianco, A. & Brandimarte, P. & Chiasserini, C.F., 2007. "Maximizing system lifetime in wireless sensor networks," European Journal of Operational Research, Elsevier, vol. 181(1), pages 390-402, August.
    4. Jie Wang & Ning Zhong, 2006. "Efficient point coverage in wireless sensor networks," Journal of Combinatorial Optimization, Springer, vol. 11(3), pages 291-304, May.
    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. Gahm, Christian & Denz, Florian & Dirr, Martin & Tuma, Axel, 2016. "Energy-efficient scheduling in manufacturing companies: A review and research framework," European Journal of Operational Research, Elsevier, vol. 248(3), pages 744-757.
    2. Cerulli, R. & De Donato, R. & Raiconi, A., 2012. "Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges," European Journal of Operational Research, Elsevier, vol. 220(1), pages 58-66.
    3. Aizemberg, Luiz & Kramer, Hugo Harry & Pessoa, Artur Alves & Uchoa, Eduardo, 2014. "Formulations for a problem of petroleum transportation," European Journal of Operational Research, Elsevier, vol. 237(1), pages 82-90.
    4. Keskin, Muhammed Emre, 2017. "A column generation heuristic for optimal wireless sensor network design with mobile sinks," European Journal of Operational Research, Elsevier, vol. 260(1), pages 291-304.

    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. A. Ruszczynski, 1993. "Regularized Decomposition of Stochastic Programs: Algorithmic Techniques and Numerical Results," Working Papers wp93021, International Institute for Applied Systems Analysis.
    2. Ethem Çanakoğlu & İbrahim Muter & Tevfik Aytekin, 2021. "Integrating Individual and Aggregate Diversity in Top- N Recommendation," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 300-318, January.
    3. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    4. Sankaran, Jayaram K., 1995. "Column generation applied to linear programs in course registration," European Journal of Operational Research, Elsevier, vol. 87(2), pages 328-342, December.
    5. Metrane, Abdelmoutalib & Soumis, François & Elhallaoui, Issmail, 2010. "Column generation decomposition with the degenerate constraints in the subproblem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 37-44, November.
    6. Belanger, Nicolas & Desaulniers, Guy & Soumis, Francois & Desrosiers, Jacques, 2006. "Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1754-1766, December.
    7. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    8. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    9. Thomas W. M. Vossen & Dan Zhang, 2015. "Reductions of Approximate Linear Programs for Network Revenue Management," Operations Research, INFORMS, vol. 63(6), pages 1352-1371, December.
    10. Ternoy, Jacques Emmanuel, 1969. "Cooperation and economic efficiency," ISU General Staff Papers 196901010800004786, Iowa State University, Department of Economics.
    11. Ibrahim Muter & Tevfik Aytekin, 2017. "Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 405-421, August.
    12. Canca, David & Barrena, Eva, 2018. "The integrated rolling stock circulation and depot location problem in railway rapid transit systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 115-138.
    13. Barry C. Smith & Ellis L. Johnson, 2006. "Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition," Transportation Science, INFORMS, vol. 40(4), pages 497-516, November.
    14. Mercedes Esteban-Bravo & Jose M. Vidal-Sanz & Gökhan Yildirim, 2014. "Valuing Customer Portfolios with Endogenous Mass and Direct Marketing Interventions Using a Stochastic Dynamic Programming Decomposition," Marketing Science, INFORMS, vol. 33(5), pages 621-640, September.
    15. Ketabchi, Saeed & Behboodi-Kahoo, Malihe, 2015. "Augmented Lagrangian method within L-shaped method for stochastic linear programs," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 12-20.
    16. El-Sharafy, M. Zaki & Farag, Hany E.Z., 2017. "Back-feed power restoration using distributed constraint optimization in smart distribution grids clustered into microgrids," Applied Energy, Elsevier, vol. 206(C), pages 1102-1117.
    17. Ashwin Arulselvan & Mohsen Rezapour, 2017. "Exact Approaches for Designing Multifacility Buy-at-Bulk Networks," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 597-611, November.
    18. Bani, Abderrahman & El Hallaoui, Issmail & Corréa, Ayoub Insa & Tahir, Adil, 2023. "Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints," European Journal of Operational Research, Elsevier, vol. 311(1), pages 154-172.
    19. Prawat Sahakij & Steven Gabriel & Mark Ramirez & Chris Peot, 2011. "Multi-objective Optimization Models for Distributing Biosolids to Reuse Fields: A Case Study for the Blue Plains Wastewater Treatment Plant," Networks and Spatial Economics, Springer, vol. 11(1), pages 1-22, March.
    20. Borgonjon, Tessa & Maenhout, Broos, 2022. "An exact approach for the personnel task rescheduling problem with task retiming," European Journal of Operational Research, Elsevier, vol. 296(2), pages 465-484.

    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:eee:ejores:v:207:y:2010:i:2:p:1014-1026. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.