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

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.