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

Optimal sensor deployment to increase the security of the maximal breach path in border surveillance

Author

Listed:
  • Karabulut, Ezgi
  • Aras, Necati
  • Kuban Altınel, İ.

Abstract

Wireless Sensor Networks (WSN) are based on the collaborative effort of a large number of sensors which are low-cost, low-power, multi-functional small electronic devices. They provide a distributed sensing and monitoring environment for the area of interest and hence are used for applications such as environmental monitoring, border surveillance, and target tracking. In this work we study optimal deployment of WSNs for border surveillance using a static Stackelberg game frame and propose a bilevel optimization model for the optimal deployment of a heterogenous WSN so that the security of the area under consideration is increased as much as possible. There are two players in this game: defender and intruder. The defender is the leader and tries to determine the best sensor locations so as to maximize the security measured in terms of coverage intensity at discretized points in the area. The well-informed intruder assuming the role of the follower is capable of destroying some of the sensors so as to identify the maximal breach path, which represents the safest path from his perspective and thus increases the chance of being undetected by the sensors. This new approach results in a mixed-integer linear bilevel programming formulation that is difficult to solve exactly. Therefore, we propose three Tabu search heuristics and realize computational experiments on a large set of test instances in order to assess their performances.

Suggested Citation

  • Karabulut, Ezgi & Aras, Necati & Kuban Altınel, İ., 2017. "Optimal sensor deployment to increase the security of the maximal breach path in border surveillance," European Journal of Operational Research, Elsevier, vol. 259(1), pages 19-36.
  • Handle: RePEc:eee:ejores:v:259:y:2017:i:1:p:19-36
    DOI: 10.1016/j.ejor.2016.09.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716307524
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2016.09.016?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. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    2. Losada, Chaya & Scaparra, M. Paola & O’Hanley, Jesse R., 2012. "Optimizing system resilience: A facility protection model with recovery time," European Journal of Operational Research, Elsevier, vol. 217(3), pages 519-530.
    3. Berman, Oded & Gavious, Arieh, 2007. "Location of terror response facilities: A game between state and terrorist," European Journal of Operational Research, Elsevier, vol. 177(2), pages 1113-1133, March.
    4. O'Hanley, Jesse R. & Church, Richard L., 2011. "Designing robust coverage networks to hedge against worst-case facility losses," European Journal of Operational Research, Elsevier, vol. 209(1), pages 23-36, February.
    5. Oded Berman & Arieh Gavious & Rongbing Huang, 2011. "Location of response facilities: a simultaneous game between state and terrorist," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 10(1), pages 102-120.
    6. Jerome Bracken & James T. McGill, 1973. "Mathematical Programs with Optimization Problems in the Constraints," Operations Research, INFORMS, vol. 21(1), pages 37-44, February.
    7. James T. Moore & Jonathan F. Bard, 1990. "The Mixed Integer Linear Bilevel Programming Problem," Operations Research, INFORMS, vol. 38(5), pages 911-921, October.
    8. Mehmet Başdere & Necati Aras & İ. Kuban Altınel & Sezin Afşar, 2013. "A leader-follower game for the point coverage problem in wireless sensor networks," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 7(5), pages 635-656.
    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. Xiang, Yin, 2023. "Minimizing the maximal reliable path with a nodal interdiction model considering resource sharing," Reliability Engineering and System Safety, Elsevier, vol. 239(C).
    2. Haywood, Adam B. & Lunday, Brian J. & Robbins, Matthew J. & Pachter, Meir N., 2022. "The weighted intruder path covering problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 347-358.
    3. Wen Jiang & Zeyu Ma & Xinyang Deng, 2019. "An attack-defense game based reliability analysis approach for wireless sensor networks," International Journal of Distributed Sensor Networks, , vol. 15(4), pages 15501477198, April.
    4. Mehdi Firoozbakht & Hamidreza Vosoughifar & Alireza Ghari Ghoran, 2019. "Coverage intensity of optimal sensors for common, isolated, and integrated steel structures using novel approach of FEM-MAC-TTFD," International Journal of Distributed Sensor Networks, , vol. 15(8), pages 15501477198, August.
    5. Blanco, Víctor & Gázquez, Ricardo & Saldanha-da-Gama, Francisco, 2023. "Multi-type maximal covering location problems: Hybridizing discrete and continuous problems," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1040-1054.

    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. Chaya Losada & M. Scaparra & Richard Church & Mark Daskin, 2012. "The stochastic interdiction median problem with disruption intensity levels," Annals of Operations Research, Springer, vol. 201(1), pages 345-365, December.
    2. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2017. "A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs," Operations Research, INFORMS, vol. 65(6), pages 1615-1637, December.
    3. Zhang, Ying & Snyder, Lawrence V. & Ralphs, Ted K. & Xue, Zhaojie, 2016. "The competitive facility location problem under disruption risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 453-473.
    4. Parajuli, Anubhuti & Kuzgunkaya, Onur & Vidyarthi, Navneet, 2017. "Responsive contingency planning of capacitated supply networks under disruption risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 102(C), pages 13-37.
    5. Dajun Yue & Jiyao Gao & Bo Zeng & Fengqi You, 2019. "A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs," Journal of Global Optimization, Springer, vol. 73(1), pages 27-57, January.
    6. Gentile, José & Alves Pessoa, Artur & Poss, Michael & Costa Roboredo, Marcos, 2018. "Integer programming formulations for three sequential discrete competitive location problems with foresight," European Journal of Operational Research, Elsevier, vol. 265(3), pages 872-881.
    7. Fränk Plein & Johannes Thürauf & Martine Labbé & Martin Schmidt, 2022. "A bilevel optimization approach to decide the feasibility of bookings in the European gas market," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 95(3), pages 409-449, June.
    8. Losada, Chaya & Scaparra, M. Paola & O’Hanley, Jesse R., 2012. "Optimizing system resilience: A facility protection model with recovery time," European Journal of Operational Research, Elsevier, vol. 217(3), pages 519-530.
    9. George Kozanidis & Eftychia Kostarelou, 2023. "An Exact Solution Algorithm for Integer Bilevel Programming with Application in Energy Market Optimization," Journal of Optimization Theory and Applications, Springer, vol. 197(2), pages 573-607, May.
    10. Bo Zeng, 2020. "A Practical Scheme to Compute the Pessimistic Bilevel Optimization Problem," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1128-1142, October.
    11. Medal, Hugh R. & Pohl, Edward A. & Rossetti, Manuel D., 2014. "A multi-objective integrated facility location-hardening model: Analyzing the pre- and post-disruption tradeoff," European Journal of Operational Research, Elsevier, vol. 237(1), pages 257-270.
    12. Starita, Stefano & Scaparra, Maria Paola, 2016. "Optimizing dynamic investment decisions for railway systems protection," European Journal of Operational Research, Elsevier, vol. 248(2), pages 543-557.
    13. O’Hanley, Jesse R. & Scaparra, M. Paola & García, Sergio, 2013. "Probability chains: A general linearization technique for modeling reliability in facility location and related problems," European Journal of Operational Research, Elsevier, vol. 230(1), pages 63-75.
    14. Richard Oberdieck & Nikolaos A. Diangelakis & Styliani Avraamidou & Efstratios N. Pistikopoulos, 2017. "On unbounded and binary parameters in multi-parametric programming: applications to mixed-integer bilevel optimization and duality theory," Journal of Global Optimization, Springer, vol. 69(3), pages 587-606, November.
    15. Alexander Mitsos, 2010. "Global solution of nonlinear mixed-integer bilevel programs," Journal of Global Optimization, Springer, vol. 47(4), pages 557-582, August.
    16. Jalali, Sajjad & Seifbarghy, Mehdi & Niaki, Seyed Taghi Akhavan, 2018. "A risk-averse location-protection problem under intentional facility disruptions: A modified hybrid decomposition algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 196-219.
    17. Opher Baron & Oded Berman & Arieh Gavious, 2018. "A Game Between a Terrorist and a Passive Defender," Production and Operations Management, Production and Operations Management Society, vol. 27(3), pages 433-457, March.
    18. Maria Paola Scaparra & Richard Church, 2012. "Protecting Supply Systems to Mitigate Potential Disaster," International Regional Science Review, , vol. 35(2), pages 188-210, April.
    19. Parajuli, Anubhuti & Kuzgunkaya, Onur & Vidyarthi, Navneet, 2021. "The impact of congestion on protection decisions in supply networks under disruptions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    20. R. Paulavičius & C. S. Adjiman, 2020. "New bounding schemes and algorithmic options for the Branch-and-Sandwich algorithm," Journal of Global Optimization, Springer, vol. 77(2), pages 197-225, June.

    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:259:y:2017:i:1:p:19-36. 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.