A leader-follower game for the point coverage problem in wireless sensor networks

Sensors form an effective wireless network for the surveillance of a region. Ensuring coverage is an important issue in wireless sensor network design. This paper focuses on an application where sensors are used to detect intruders. The defender wants to determine the best locations of the sensors to maximise the point coverage in the area with the anticipation that an intruder will attack and destroy some of the sensors to reduce the coverage. This sequential game between the defender and the intruder is modelled using bilevel programming. Two models are formulated: a bilevel pure integer linear programme (BPILP) where an attacked sensor is destroyed completely and a bilevel mixed integer linear programme (BMILP) where a damaged sensor continues to operate at a reduced capacity. Since BPILP and BMILP models are difficult to solve exactly, solution methods based on local search and tabu search are proposed, which are hybridised with an exact method. [Received 9 September 2011; Revised 7 January 2012; Revised 20 March 2012; Accepted 20 March 2012]