Deployment cost minimization for composite event detection in large-scale heterogeneous wireless sensor networks

How to use as few sensor nodes as possible to detect composite event in large area is a difficult problem because multiple heterogeneous sensor nodes are required for detecting the composite event which consists of several atomic events, and the detection accuracy would be worse if there are no enough sensor nodes. Most of the traditional methods are focusing on atomic event detection which only needs one type of homogeneous node. Considering costs, weights, and sensing capability of different types of heterogeneous sensor nodes, a deployment cost minimization problem for composite event is put forward, and its corresponding mathematical model is given in this article, with the purpose of minimizing deployment costs subject to the constraint of achieving a required coverage quality. Different from traditional methods, according to the temporal and spatial association of heterogeneous nodes, two novel models for atomic event and composite event are proposed, respectively, and the coverage quality which is very important to the detection accuracy is analyzed based on these two models. Then, based on the composite event model and the coverage quality model, an exact algorithm and a greedy strategy approximation algorithm are proposed to solve the optimization problem. Also, the time complexity and approximability of these two algorithms are analyzed. The experimental results show that the proposed approximation algorithm has low deployment cost and low time complexity under the same coverage quality.