Optimal sensor deoployment to increase the security of the minimal exposure path

Wireless Sensor Networks (WSN) are based on collaborative work of a collection of sensors which are low-cost, multi-functional devices. There is a wide range of application areas of WSN including border surveillance and forest fire controls. Maximizing the security of maximal breach path, also known as the minimal exposure path, is an important approach in the design of WSN. This thesis focuses on this aspect, and develops a mixed integer bilevel programming formulation to determine the sensor locations that maximize the exposure on the minimal exposure path. The leader in the upper level problem intends to maximize the exposure on the maximal breach path by finding the optimal sensor locations. The follower in the lower level problem, on the other hand, selects the sensors to be destroyed to minimize the exposure on the maximal breach path. There are two basic heuristics proposed to solve this bilevel optimization problem. The first one employs tabu search on the upper level variables, and solves the lower level problem to optimality. The other heuristic breaks down the problem into three levels, performs tabu search on the first two levels, and solves the lowest level as the shortest path problem. The computational results indicate the success of the bilevel programming formulation and the solution methods.