The placement-configuration problem for intrusion detection nodes in wireless sensor networks Articles uri icon

publication date

  • October 2013

start page

  • 2306

end page

  • 2317


  • 7


  • 39

International Standard Serial Number (ISSN)

  • 0045-7906

Electronic International Standard Serial Number (EISSN)

  • 1879-0755


  • The deployment and configuration of a distributed network intrusion detection system (NIDS) in a large Wireless Sensor Network (WSN) is an enormous challenge. A reduced number of devices equipped with detection capabilities have to be placed on strategic network locations and then appropriately configured in order to maximise the detection rate and minimise the amount of computational and physical resources consumed - fundamentally energy, which in turn depends on CPU, memory, and network usage. In practice, a major difficulty lies in the fact that the relationship between each node's tuning parameters and the overall cost/benefit rate achieved by the deployment is poorly understood. We call this the Placement-Configuration Problem (PCP). In this paper we formalise and study this problem both theoretically and empirically. We introduce a formal model of distributed NIDS upon which the cost/benefit tradeoffs can be appropriately derived. Subsequently we show that, in general, the PCP is hard (NP-complete) and present a heuristic local search algorithm to find near-optimal solutions for practical scenarios. Our analysis framework is general in the sense that it is applicable to a number of existing detection technologies for WSNs, and we discuss how further aspects can be easily introduced if required. (C) 2013 Elsevier Ltd. All rights reserved.