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

Authors: Mehmet Başdere; Necati Aras; İ. Kuban Altınel; Sezin Afşar

Addresses: Department of Industrial Engineering, Engineering Faculty, Boğaziçi University, 34342 İstanbul, Turkey ' Department of Industrial Engineering, Engineering Faculty, Boğaziçi University, 34342 İstanbul, Turkey ' Department of Industrial Engineering, Engineering Faculty, Boğaziçi University, 34342 İstanbul, Turkey ' Inria Lille – Nord Europe, Parc scientifique de la Haute-Borne. 40, avenue Halley – Bât A – Park Plaza, 59650 Villeneuve d'Ascq, France

Abstract: 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]

Keywords: wireless sensor networks; WSNs; coverage problem; bilevel programming; matheuristics; tabu search; local search; leader-follower games; point coverage; intruder detection; modelling; destroyed sensors; damaged sensors; wireless networks; surveillance.

DOI: 10.1504/EJIE.2013.057385

European Journal of Industrial Engineering, 2013 Vol.7 No.5, pp.635 - 656

Received: 08 May 2021
Accepted: 12 May 2021

Published online: 29 Oct 2013 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article