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

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.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slideHighlights► We examine the problem of deploying and configuring a distributed network IDS in a wireless sensor network. ► We provide formal models for the network, detection units, configurations, and resource consumption. ► We show that the problem is NP-complete and investigate heuristic solutions through simulation.