Sage Journals: Discover world-class research

Abstract

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.

Keywords

Composite event wireless sensor networks heterogeneous node deployment costs coverage quality

Introduction

Public security events, natural disasters, and accidents occur frequently all over the world, which bring a great threat to people’s personal and property security. Wireless sensor networks (WSNs) have been widely used in the detection of these events.^1–5 For example, there has been a forest fire as shown in Figure 1. But if sensor networks are deployed in the forest in advance as shown in Figure 2, the fire may be found in time to avoid the occurrence of forest fire.

Figure 1.

Forest fire disaster.

Figure 2.

Monitor forest fires using wireless sensor networks.

In most detection cases of security events or natural disasters, monitoring scopes are usually large and events are complex. Large-scale monitoring requires a large number of sensor nodes which lead to a high deployment cost. For example, suppose that the sensing radius of every node is 20 m, and nodes are uniformly distributed in deployment area. There are totally 1250 nodes required for the deployment area of 1000 m × 1000 m, which require a big budget. Furthermore, complex events usually have multiple attributes so that a variety of heterogeneous sensor nodes are required for joint detection. This would further increase the deployment cost. For example, when the fire occurs, the temperature and brightness of the surrounding environment increase and accompanied by smoke. Temperature, brightness, smoke, and other types of heterogeneous sensor nodes are usually used to jointly detect the fire to improve the detection rate. Overall, for the composite event detection in large area, how to use as few sensor nodes as possible to detect the composite event effectively is a challenge.

Most of the traditional methods are mostly concerned with atomic event, which only has a specific property that only needs one type of homogeneous sensor node for detection. And they aim to guarantee that the monitoring area is covered by at least one sensor node or k nodes,^6–9 but ignore the temporal and spatial association among atomic events. For complex events with multiple properties, the deployment cost will be very high if every geometric point is required to be covered by all types of sensor nodes. Thus, traditional methods cannot be used in the wide range of composite event monitoring applications. However, if the temporal and spatial association among atomic events can be effectively used, deployment costs will be greatly reduced. As shown in Figure 3, area A₃ is covered by three types of sensor nodes, and its detection accuracy is the highest. Although areas A₁, A₂, and A₄ are only covered by two types of sensors, it is still possible to achieve higher detection accuracy. More importantly, we can reduce 1/3 sensor nodes. Based on the above idea, this article attempts to use as few sensor nodes as possible to effectively detect the complex events in large area. First, a novel atomic event model and a composite event model are proposed. Then, coverage quality, which is very important to the detection accuracy, can be evaluated based on these models. Second, in order to solve the high deployment cost problem of composite event detection in large area, a novel composite event deployment problem is put forward, with the purpose of minimizing deployment costs subject to the constraint of achieving a required coverage quality. And a mathematical model for this optimal problem is given. Finally, in order to solve this novel composite event deployment problem, an exact algorithm and an approximation algorithm are proposed. According to the approximation algorithm, a feasible deployment scheme can be rapidly found.

Figure 3.

Joint detection of composite event using heterogeneous sensor nodes.

The contributions of this article are as follows:

Based on the study of the temporal and spatial association among atomic events, a novel atomic event model and composite event model are proposed in this article.

The deployment cost minimization problem (DCMP) is formulated based on the event model, and its corresponding mathematical model is given. As we know, this is the first work to study the composite event DCMP problem.

An exact algorithm and a greedy strategy approximation algorithm are proposed to solve the DCMP, and the time complexity and approximability of the algorithms are analyzed in this article.

The rest of this article is organized as follows. The related works are analyzed in section “Related works.” The event models and definitions of the coverage quality are described in section “The event model and coverage quality evaluation method.” In section “DCMP and algorithm description,” the deployment cost optimization problem and its mathematical model are presented, and an exact algorithm and an approximate algorithm are proposed. The experimental results and analysis are provided in section “Experimental results.” Finally, a conclusion is drawn in section “Conclusion.”

Related works

The detection of composite event is mainly based on the temporal and spatial association among atomic events to improve detection accuracy. At present, there are some representative works about the detection of composite event.

S Lai et al.¹⁰ studied the energy cost of composite event detection in WSNs and proposed a distributed composite event detection algorithm TED (type-based composite event detection) to solve the minimum energy cost problem. Its essential idea is type-based event fusion, where some sensor nodes are selected as fusion points. X Liu et al.¹¹ took structural health monitoring as an example to illustrate how to support EECPS (Energy-Efficient Coverage-Preserving Scheduling) to extend the system lifetime in some special applications of WSNs. The authors re-defined the coverage model and proposed two methods, based on multi-dimensional knapsack problem and genetic algorithm, respectively, to partition the deployed sensor nodes into qualified cover sets so that the system lifetime could be maximized by letting these sets work by turns. In the energy-efficient k-watching composite event detection problem, M Marta et al.¹² proposed a localized connected dominating set–based approach and a sensor scheduling mechanism to increase network lifetime. The above articles mainly prolong the lifetime of the sensor network from the aspect of algorithm.

In addition, Y Li and colleagues^13,14 studied the timely energy-efficient k-watching event detection problem and proposed a real-time mechanism to improve the system response performance for some urgent composite event detection, at the same time prolong the network lifetime.

In the above literatures, the life cycle and real-time performance of sensor networks are studied, but coverage problem is less concerned. Y Yang and M Cardei¹⁵ divided the monitored area into grids, gave the initial deployment, and studied how to deploy the movement-assisted sensor nodes for minimum-breach composite event detection. But it is a deterministic deployment-based problem which is not suitable for the large area deployment. J Gao et al.¹⁶ first put forward a coverage quality maximum problem of composite event detection and studied how to deploy sensor nodes to maximize the coverage quality in a wide range of composite event monitoring and then proposed an approximate algorithm to solve this optimization problem.

In summary, most of the above papers are able to effectively use the temporal and spatial association among atomic events to detect composite event, but they mostly focus on the lifetime and real-time performance of the networks. And the literature¹⁶ is mainly concerned with the problem of maximizing the coverage quality. In the work by Dong,¹⁷ a DCMP and its optimization method are presented briefly, and in this article, this method is extended as follows:

An analysis of the complexity of the DCMP problem is added to prove that the problem is a nondeterministic polynomial complete (NP-complete) problem, which is the premise of the proposed approximate optimization method.

The approximate optimization method proposed by Dong¹⁷ is modified in this article, and the upper bound of the number of sensor nodes in the initial deployment scheme is given as equation (19).

The time complexity and approximability of the exact algorithm and approximation algorithm are analyzed in this article, and, finally, show that the theoretical analysis is consistent with the experimental results.

Conducted more experiments using different sample data, including experiments on the relationship between deployment cost and monitoring area, deployment cost and number of node types, coverage quality and running time, and coverage quality and deployment cost. And the experimental results are analyzed in detail.

To the best of our knowledge, in composite event detection, there is no relevant research result about how to minimize deployment costs, meanwhile achieving a required detection accuracy. And this is very important to large-area composite event detection and has a good research value.

The event model and coverage quality evaluation method

Event model

In WSNs, events are usually classified into atomic event and composite event and denoted as an occurrence of a phenomenon or an object. As shown in Figure 1, forest fire disaster happens occasionally in all regions in this world, and using sensor nodes to monitor forest fires is an important application of WSNs. When forest fire occurs, environmental parameters around will be changed, such as the temperature, smoke, and light. So, different types of heterogeneous nodes can be used to monitor these environmental parameters. Here, temperature, smoke, and light are properties of different aspects of fire, so they denote atomic events of the fire while fire is the composite event. When temperature, smoke, or light exceed the given thresholds, the fire will probably happen.

In this article, based on event models,^16,18,19 a novel atomic event model and a composite model are proposed, which are important to the WSN deployment problem.

Atomic event

Occurrence of atomic event denotes that one aspect of the state, which can be detected by one type of sensor node, of a target or a phenomenon exceeds a given threshold. In this article, an atomic event model is proposed, which can be denoted as follows

e = (l, t, r, w)

(1)

where l is the location of the event, t is the time when the event occurs, r is the threshold used to evaluate whether the event happens, and w is the weight which is used to indicate the occurrence probability of the composite event when this atomic event occurs. The weight w can be obtained by analyzing the historic data. When monitoring an event which has only one property, the value of w is 1. It means that the event will occur when r is true. And when w is less than 1, it denotes that e is an atomic event of a composite event, which needs to be united with other atomic events to determine whether the composite event occurs.

For example, atomic event $e (l, t, r, w) = ((x, y), 15 October 2016, Light > 250, 1)$ denotes that the light at location (x, y) on 15 October 2016 is greater than 250, and the weight is 1.

Composite event

Composite event is composed of several atomic events and it needs various types of heterogeneous nodes for joint monitoring. As shown in Figure 4, three types of heterogeneous nodes such as temperature sensor node, smoke density sensor node, and light intensity sensor node are used to detect the fire.

Figure 4.

Detection of composite event.

Suppose that the composite event consists of k atomic events which satisfy the following conditions

{\begin{matrix} d_{l_{i}} \leq r_{i}, 1 \leq i \leq k \\ t_{1} = t_{2} = \dots = t_{k}, 1 \leq i \leq k \end{matrix}

(2)

where $d_{l_{i}}$ denotes the distance between the locations of the composite event and the ith type of heterogeneous sensor node and $r_{i}$ is the sensing radius of ith type sensor node. And the above equation means that atomic events occur at the same time and on the location where can be monitored by the corresponding types of heterogeneous sensor nodes.

Then, a composite event can be denoted as

E (e_{1}, e_{2}, \dots, e_{k}) = (r_{1} \land r_{2} \land \dots \land r_{k}, W)

(3)

where e_i is an atomic event and $e_{i} = (l_{i}, t_{i}, r_{i}, w_{i}), 1 \leq i \leq k$ . W denotes the occurrence probability of the composite event E which is computed as $w_{1} \oplus w_{2} \oplus \dots \oplus w_{k}$ . $\oplus is$ the combination operator which can be any operator based on the specific application. And the combination operator $\oplus has$ the following properties¹⁸

{\begin{matrix} w_{i} \oplus w_{j} \geq w_{i} or w_{j}, i, j \in {1, 2, \dots, k} \\ w_{1} \oplus w_{2} \oplus \dots \oplus w_{k} = 1 \end{matrix}

(4)

For example, $E (e_{1}, e_{2}) = (Light > 250 \land Temperature > 80 \circ C, W = 0.3 \oplus 0.45)$ , where $e_{1} = (l_{1}, t_{1}, Light > 250, 0.3)$ and $e_{2} = (l_{2}, t_{2}, Temperature > 80 \circ C, 0.45)$ . The composite event E means that fire breaks out if light >250 and temperature >80°C, and the occurrence probability of the fire is $0.3 \oplus 0.45$ if these two atomic events occur at the same time and in the same intersecting region. Here, it should be known that only when all atomic events of the composite event occur, the occurrence probability of the composite event satisfies the equation $w_{1} \oplus \dots w_{i} \oplus \dots w_{k} = 1$ . When only some of the atomic events occur, the occurrence probability of the composite event is less than 1. And this example is the second case, in which only part of the atomic events occur, that is, $k > 2$ . So, the occurrence probability of the fire is $0.3 \oplus 0.45 < 1$ . When a certain weight value $w_{i}$ of one atomic event is equal to 1, it means that the composite event is a simple event, and it is a special case of the composite event.

Coverage quality evaluation method

Different deployment schemes have different coverage qualities. As the deployment schemes 1, 2, and 3 shown in Figure 5, locations l₁, l₂, and l₃ are covered by more than one node, and the final detecting results are fused from these heterogeneous nodes. Compared to locations l₂ and l₃, detection accuracy of l₁ where is covered by three sensor nodes is the highest according to equation (4). How to weigh the deployment cost and coverage quality is a question that needs to be considered.

Figure 5.

Covered by different deployment schemes.

In this article, the deployment of WSNs is stochastic deployment, and the coverage quality estimation model is based on Gao and Li.¹⁸ Suppose that k types of heterogeneous sensor nodes are deployed in monitoring area A, in which sensor nodes satisfy a uniform distribution. Here, monitoring area A refers to a very large area, where is much larger than the sensing area of one node. So, the shape of monitoring area A has little effect on the deployment scheme so that it can be ignored. And Figure 5 just denotes a local area in monitoring area A to illustrate the coverage of heterogeneous nodes. The number and the sensing radius of each type of heterogeneous sensor nodes are ${n_{1}, n_{2}, \dots, n_{k}}$ and ${r_{1}, r_{2}, \dots, r_{k}}$ , respectively. The deployment density of ith type sensor node is $d_{i} = n_{i} / A$ .

Let $D = {n_{1}, n_{2}, \dots, n_{k}}$ denote a deployment scheme, and n_i represents the number of nodes from type i, for $i \in {1, 2, \dots, k}$ . Let $S = {i | i \in {1, 2, \dots, k}}$ be a coverage scheme, and S denotes the geometric point covered by which types of sensor nodes. For example, as shown in Figure 5, there are three types of sensor nodes deployed in the monitoring area, and the number of each type is 1. The sequence numbers of sensor nodes of temperature, smoke density, and light intensity are 1, 2, and 3, respectively. So, the deployment schemes in Figure 5 can be denoted as $D_{1} = {1, 1, 1}$ , $D_{2} = {1, 0, 1}$ , and $D_{3} = {1, 1, 0}$ , respectively. And coverage schemes of l₁, l₂, and l₃ are $S_{l_{1}} = {1, 2, 3}$ , $S_{l_{2}} = {1, 3}$ , and $S_{l_{3}} = {1, 2}$ , respectively. The deployment of the sensor nodes follows a uniform distribution. Assume that the sensing radius and deployment density of sensor node of type i are $r_{i} (i = 1, 2, \dots, k)$ and $d_{i} = n_{i} / A$ , where n_i denotes the number of sensor node of type i. So, the number of sensor nodes of type i in its sensing region is $λ_{i} = π r_{i}^{2} d_{i}$ . In order to simplify the calculation, it is assumed that the average sensing radius and deployment density of all types of nodes are $r = (r_{1} + r_{2} + \dots + r_{k}) / k$ and $d = (d_{1} + d_{2} + \dots + d_{k}) / k$ , respectively. Then, the average number of all sensor nodes within sensing area is $λ = π r^{2} d$ . The probability of an arbitrary geometric point covered by n nodes, 0 nodes, sensor node from type i, and coverage scheme S_i¹⁸ are as follows

P_{c} (n) = (\frac{λ^{n}}{n!}) e^{- λ}

(5)

P_{c} (0) = e^{- λ}

(6)

p_{i} = 1 - e^{- λ_{i}}

(7)

P_{i} = \underset{j \in S_{i}}{Π} p_{j} \underset{j \notin S_{i}}{Π} (1 - p_{j})

(8)

where $\sum_{i = 1}^{2^{k}} P_{i} = 1$ . The probability of any geometric point covered by any coverage scheme can be calculated based on equations (5)–(8).

As shown in Figure 5, the coverage quality of l₁ with coverage scheme $S_{l_{1}}$ is $W_{l_{1}} = w_{1} \oplus w_{2} \oplus w_{3}$ , which is a fusion result from three types of heterogeneous nodes. So, the coverage quality of a coverage scheme S_i can be denoted as follows

W_{i} = w_{j_{1}} \oplus w_{j_{2}} \oplus \dots \oplus w_{j_{m}}, and S_{i} = {j_{1}, j_{2}, \dots, j_{m}}

(9)

Thus, from the probability P_i and coverage quality W_i of a coverage scheme S_i based on equations (8) and (9), the expectation of the coverage quality for any geometric point can be calculated as the following equation

Δ E = \sum_{i = 1}^{| S |} P_{i} W

(10)

where |S| denotes the number of all possible coverage schemes in deployment scheme D. In a deployment scheme, a geometric point may have many coverage schemes which have their corresponding coverage quality and probability so that the expectation of coverage quality for any geometric point can be calculated.

DCMP problem and algorithm description

Problem description

k types of heterogeneous sensor nodes are needed to detect the composite event which is composed of k atomic events. For a wide-range monitoring region, by traditional coverage methods, large number of sensor nodes need to be deployed in order to cover every geometric point by k types of sensor nodes. However, from the event model of section “The event model and coverage quality evaluation method,” it is known that it is no need to use all of the types of heterogeneous sensor nodes because of the temporal and spatial association among heterogeneous nodes. At the same time, it can still achieve good detecting result. So, a DCMP problem subject to a constraint of achieving a required coverage quality in composite event detection with WSNs is put forward in this article. To the best of our knowledge, this is the first work to study DCMP in composite event detection.

Definition 1

DCMP

Suppose that the number and cost of each type of heterogeneous nodes are n_i and c_i, respectively. Find a best deployment scheme $D = {n_{1}, n_{2}, \dots, n_{k}}$ such that the total cost C of the deployment scheme is minimum and the overall coverage quality is not less than constant $β$ . The DCMP optimal model can be denoted as

min C (D) = \sum_{i = 1}^{k} n_{i} c_{i}

(11)

s.t.

E = \sum_{i = 1}^{| S |} P_{i} W_{i} \geq β

(12)

When the arithmetic “+” is used to fuse the detection results of the related heterogeneous nodes, the DCMP optimal model has a simpler form as

min C (D) = \sum_{i = 1}^{k} n_{i} c_{i}

(13)

s.t.

E = \sum_{i = 1}^{k} p_{i} w_{i} \geq β

(14)

where w_i and p_i are the weight and probability of an arbitrary geometric point covered by sensor node of type i.

Complexity analysis for DCMP problem

Theorem 1

If the fusion operator $\oplus is$ “+,” the DCMP problem is NP-complete.

Proof

The purpose of DCMP problem is to find a best solution to decrease the deployment cost rapidly under the constraint of achieving a certain coverage quality. The following equation can be used to find the destination node which should be subtracted

V_{i} = \frac{c_{i}}{E (n_{1}, \dots, n_{i}, \dots, n_{k}) - E (n_{1}, \dots, n_{i} - 1, \dots, n_{k})}

(15)

where $E (n_{1}, \dots, n_{i}, \dots, n_{k})$ is the coverage quality of $D (n_{1}, \dots, n_{i}, \dots, n_{k})$ . $V_{i}$ is a greedy value, and the node whose $V_{i}$ is the largest means that its relative cost is the biggest compared to its contribution to coverage quality. Also, this problem can be solved from another angle to find the type of node which has the largest coverage quality compared to its cost, denoted as follows

V_{i} = \frac{E (n_{1}, \dots, n_{i} + 1, \dots, n_{k}) - E (n_{1}, \dots, n_{i}, \dots, n_{k})}{c_{i}}

(16)

So, DCMP problem can be transformed to coverage quality maximization problem (CQMP) under the cost constraint which can be denoted as follows

max E (D) = \sum_{i = 1}^{k} p_{i} w_{i}

(17)

s.t.

C (D) = \sum_{i = 1}^{k} n_{i} c_{i} \leq C'

(18)

where $C'$ is the constraint of the total budget. If n_i is limited to 0 and 1, and c_i is considered as the weight of the object, $C'$ is the size of the knapsack. Then, it is a standard 0–1 knapsack problem which is known as an NP-complete problem.¹⁸ So, the DCMP problem with “+” as the operator, which is a subset of DCMP with $“ \oplus ” as$ the operator, is also an NP-complete problem. Then, the DCMP problem is at least NP-complete.

Algorithm implementation

Approximate algorithm

Based on the same composite event model of equation (3) and coverage quality evaluation model of equation (10), deployment cost minimization subject to coverage quality constraint can be transformed into coverage quality maximization subject to deployment cost constraint. Just as described in section “Complexity analysis for DCMP problem,” the DCMP problem, shown as equations (13) and (14), can be transformed to the CQMP problem, shown as equations (17) and (18), and the objective function of equation (17) is proved to be nondecreasing and submodular.¹⁶ For the submodular function, greedy algorithm is considered as the best method.^20,21 Thus, greedy strategy is used to solve the DCMP problem in this article.

Table 1 shows the approximate algorithm with greedy strategy for solving the DCMP problem, including the inputs, outputs, and the key steps of the algorithm. As shown in Table 1, the main steps of the algorithm are as follows:

Step 1. Initial deployment scheme $D (n_{1 max}, \dots, n_{i max}, \dots, n_{k max})$ (line 1), where $n_{i max}$ denotes the upper bound of the number of sensor nodes of $i th$ type.

Table 1.

Details of the approximate algorithm for DCMP problem.

Approximate algorithm with greedy strategy
Input:k: the number of types of heterogeneous sensor nodesw_i: the weight of type i heterogeneous sensor node, i = 1, 2, …, kE: the expectation of the coverage quality for any geometric pointc_i: the cost of type i heterogeneous sensor node, i = 1, 2, …, kC: the total costsOutput:D = {n₁, n₂, …, n_k}: the minimum deployment costs with coverage quality no less than constant $β$ 1: initialize $D (n_{1 max}, \dots, n_{i max}, \dots, n_{k max})$ 2: while $E > β$ do3: for i = 1 to k do4: calculate greedy value $V_{i} = \frac{c_{i}}{E (n_{1}, \dots, n_{i}, \dots, n_{k}) - E (n_{1}, \dots, n_{i} - 1, \dots, n_{k})}$ $E (n_{1}, \dots, n_{i}, \dots, n_{k})$ is the coverage quality of the $D (n_{1}, \dots, n_{i}, \dots, n_{k})$ 5: j = argmax{V_i}6: subtract a jth node from the deployment scheme $D (n_{1}, \dots, n_{j} - 1, \dots, n_{k})$ 7: update the total budget C = C − c_j8: calculate the coverage quality E of the updated deployment scheme $D (n_{1}, \dots, n_{j} - 1, \dots, n_{k})$ 9: return C and D

Approximate algorithm with greedy strategy

Input:k: the number of types of heterogeneous sensor nodesw_i: the weight of type i heterogeneous sensor node, i = 1, 2, …, kE: the expectation of the coverage quality for any geometric pointc_i: the cost of type i heterogeneous sensor node, i = 1, 2, …, kC: the total costsOutput:D = {n₁, n₂, …, n_k}: the minimum deployment costs with coverage quality no less than constant

β

1: initialize

D (n_{1 max}, \dots, n_{i max}, \dots, n_{k max})

2: while

E > β

do3: for i = 1 to k do4: calculate greedy value

V_{i} = \frac{c_{i}}{E (n_{1}, \dots, n_{i}, \dots, n_{k}) - E (n_{1}, \dots, n_{i} - 1, \dots, n_{k})}

E (n_{1}, \dots, n_{i}, \dots, n_{k})

is the coverage quality of the

D (n_{1}, \dots, n_{i}, \dots, n_{k})

5: j = argmax{V_i}6: subtract a jth node from the deployment scheme

D (n_{1}, \dots, n_{j} - 1, \dots, n_{k})

7: update the total budget C = C − c_j8: calculate the coverage quality E of the updated deployment scheme

D (n_{1}, \dots, n_{j} - 1, \dots, n_{k})

9: return C and D

DCMP: deployment cost minimization problem.

It is known that if the weight value of the node is small, more nodes are needed to keep the coverage quality. Therefore, let the weight value of all types of sensor nodes be equal to the minimum weight value, that is, $w_{1} = \dots = w_{i} \dots = w_{k} = w_{\min}$ , so that the upper bound of the number of nodes can be obtained. From section “Coverage quality evaluation method,” it is known that the probability of an arbitrary geometric point covered by sensor nodes from type i is $p_{i} = 1 - e^{- λ_{i}}$ , the number of $i th$ type sensor nodes within sensing area is $λ_{i} = π r_{i}^{2} d_{i}$ , and deployment density of $i th$ type sensor node is $d_{i} = n_{i} / A$ . $k_{w_{min}}$ denotes the number of types when all types of the nodes are with the minimum weight value $w_{\min}$ . According to equation (14), the derivation of the upper bound of the number of nodes is as follows

E = \sum_{i = 1}^{k} p_{i} w_{i} \geq β

Let $w_{i} = w_{min} and k = k_{w_{min}}$ , then the above equation can be denoted as follows

\begin{matrix} k_{w_{min}} p_{i} w_{min} \geq β \\ \Rightarrow k_{w_{min}} (1 - e^{- λ_{i}}) w_{min} \geq β \\ \Rightarrow (1 - e^{- λ_{i}}) \geq \frac{β}{k_{w_{min}} w_{min}} \\ \Rightarrow 1 - \frac{β}{k_{w_{min}} w_{min}} \geq e^{- λ_{i}} \\ \Rightarrow \log (1 - \frac{β}{k_{w_{min}} w_{min}}) \geq - λ_{i} = - π r_{i}^{2} d_{i} = - π r_{i}^{2} \frac{n_{i}}{A} \\ \Rightarrow \frac{A \cdot \log (1 - \frac{β}{k_{w_{min}} w_{min}})}{- π r_{i}^{2}} \geq n_{i} \end{matrix}

From the above, it can be seen that the upper bound of the number of any type of nodes is $A \cdot \log (1 - (β / k_{w_{min}} w_{min})) / - π r_{i}^{2}$ , so the upper bound of the number of nodes in deployment scheme $D (n_{1 max}, \dots, n_{i max}, \dots, n_{k max})$ is as follow

n_{max} = \frac{\log (1 - \frac{β}{w_{min} k_{w_{min}}})}{- π r^{2}} \times A \times k_{w_{min}}

(19)

Step 2. Find the approximation deployment scheme using greedy strategy. Compute the greedy value V for each type of heterogeneous sensors which denotes the decreasing rate of deployment cost (lines 3 and 4), and subtract the sensor node which has the largest greedy value from the deployment scheme D (lines 5 and 6). Then, calculate the total cost (line 7) and coverage quality E (line 8) of the updated deployment D based on equation (10). If E satisfies the requirement of coverage quality, stop finding the other nodes (line 1). Otherwise, return to the line 2.

Step 3. Finally, return the cost C and the best deployment scheme D (line 9).

Exact algorithm

From section “Problem description,” it is known that the DCMP problem is at least NP-complete, and it is difficult to use an exact algorithm to solve the problem. However, in some applications, sensor nodes could be very expensive. So, it is preferable to obtain the best deployment scheme with minimum cost using the exact algorithm.

In this article, as shown in Table 2, the enumerate method is used to list all the possible deployment schemes which satisfy the required coverage quality (line 1). Then, calculate all the costs of the enumerated deployment schemes (line 2) and find the optimal deployment scheme which has minimum cost (lines 3 and 4). Finally, return the minimum cost C_min and its corresponding optimal deployment scheme D_o (line 5).

Table 2.

Key steps of the exact algorithm.

Exact algorithm with enumerate strategy
1: enumerate all the possible deployment schemes D = {n₁, n₂, …, n_k} with coverage quality E(D) ≥ β2: calculate all the costs C(D) of the enumerated deployment schemes D at step 1.3: find the minimum cost C_min = min(C(D))4: find the corresponding optimal deployment scheme D_o with minimum cost5: return C_min and D_o

Performance analysis

1. The time complexity of the DCMP-greedy strategy

Conclusion 1

The time complexity of the DCMP-greedy algorithm is O(n²)

Proof

In the DCMP-greedy algorithm, as shown in Table 1, the computational complexity of inner iterations, that is, lines 3–4, is O(n), and the computational complexity of the outer iterations, that is, lines 2–8, is O(n). For nested loops, the computation time is the multiplication result of these two loops. Thus, the time complexity of DCMP-greedy strategy is O(n²).

2. The approximability of the DCMP-greedy strategy

Conclusion 2

The approximate result of DCMP-greedy algorithm is (1 − e⁻¹) times of the optimal result.

Proof

From last section, it is known that the DCMP problem can be transformed to the optimal problem which is described as equations (17) and (18). In the work by Lai et al.,¹⁰ it has been proved that the objective function of equation (17) is nondecreasing and submodular, and Gao et al.¹⁶ and Sviridenko²¹ proved that the greedy strategy which is used for maximization of submodularity objective function subject to knapsack constraint has (1−e⁻¹) approximate ratio. Thus, the result of DCMP-greedy algorithm is (1 − e⁻¹) times of the optimal result.

3. The time complexity of the DCMP-enumerate strategy

Conclusion 3

The time complexity of the DCMP-enumerate algorithm is $O (n_{max}^{k})$ .

Proof

Suppose that E is the required lowest coverage quality, $w_{min}$ is the minimum weight of all the types of sensor nodes, A is the deployment area, and the fusion operator $\oplus is$ “+.” The upper bound of the number of nodes is $n_{max}$ , based on equation (19). As shown in Table 2, there are k types of sensor nodes, and the enumeration strategy lists all the possible deployment schemes, so the possible worst time complexity of enumerate strategy algorithm is $O (n_{max}^{k})$ .

Experimental results

In the experiments, the related performance of the two proposed methods is compared.

Stochastic deployment scheme is used for all types of sensor nodes, and the coverage quality estimation model is based on equation (10). Suppose that four types of heterogeneous sensor nodes are deployed in monitoring area A, in which the sensors nodes satisfy a uniform distribution. And the combination operator $\oplus is$ the arithmetic “+” which is used to fuse the detection results of the related heterogeneous nodes. Here, it should be known that the coverage quality of any point covered by multiple nodes of the same type is equal to the point covered by only one node. All of the experiments are performed on a PC with Intel^® Dual Core™ i5-4210U CPU, 4 GB memory, and windows 10 operating system.

In the first experiment, the relationship between the deployment cost and the coverage quality is evaluated for the two proposed algorithms under the condition that the monitoring area is fixed. The related parameters are as follows: costs and weights of each type are {0.15, 0.25, 0.28, 0.32} and {0.2, 0.26, 0.24, 0.3}, respectively. Sensing radius of each node and deployment area are 20 m and 200 × 200 m², respectively. Table 3 shows the corresponding deployment costs, deployment schemes, and node numbers of each requirement coverage quality. It can be observed from Table 3 that deployment costs of the two algorithms increase with the increase in requirement of coverage quality since the increasing coverage quality means that more sensor nodes should be deployed or replace the sensor nodes with the other with more weight which may have more costs in most cases. And the costs of the greedy strategy algorithm are just slightly more than costs of the enumerate strategy algorithm. This could also be seen from the number of sensor nodes. It can also be observed from the listed deployment schemes that the two algorithms tend to select the first type of sensor node since the first type of node has the largest greedy value which could be simply denoted as $w_{i} / c_{i}$ .

Table 3.

Deployment schemes of different coverage quality.

Required coverage quality (%)	Greedy strategy			Enumerate strategy
	Deployment costs	Deployment schemes	Number of nodes	Deployment costs	Deployment schemes	Number of nodes
20	6.81	[16, 9, 2, 5]	32	6.78	[17, 7, 2, 6]	32
25	8.96	[19, 11, 4, 7]	41	8.84	[18, 10, 5, 7]	40
30	11.24	[21, 13, 7, 9]	50	11.03	[21, 12, 6, 10]	49
35	13.56	[23, 15, 9, 12]	59	13.39	[24, 15, 9, 11]	59
40	15.96	[26, 18, 11, 14]	69	15.94	[24, 18, 12, 14]	68
45	18.81	[28, 21, 14, 17]	80	18.71	[29, 20, 14, 17]	80
50	21.81	[31, 24, 17, 20]	92	21.75	[32, 23, 16, 21]	92
55	25.24	[35, 27, 21, 23]	106	25.09	[34, 27, 21, 23]	105
60	28.96	[39, 31, 24, 27]	121	28.84	[38, 30, 25, 27]	120
65	33.24	[43, 35, 29, 31]	138	33.11	[44, 35, 28, 31]	138
70	38.24	[48, 40, 34, 36]	158	38.01	[46, 39, 34, 37]	156
75	43.81	[53, 46, 39, 42]	180	43.81	[53, 46, 39, 42]	180
80	50.96	[61, 53, 46, 49]	209	50.93	[62, 51, 46, 50]	209

In order to be more intuitive to see the growth trend of the deployment costs as the coverage quality increases, Figure 6 shows the coverage quality changing from 30% to 80%. It can be observed from the figure that the two trend lines almost overlap together, and the deployment costs increase faster and faster with an increase in the coverage quality, since the approximate result of greedy algorithm is (1–e⁻¹) times of the optimal result, and the increase in the coverage quality has a marginal effect.

Figure 6.

Deployment costs with varying coverage quality.

In the second experiment, the running time for the two proposed methods is evaluated while the coverage quality changes from 20% to 90%. The related parameters are the same as experiment 1. It can be observed from Figure 7 that the running time of the enumerate strategy algorithm increases rapidly as the coverage quality increases, and the running time of the greedy strategy algorithm grows very slowly, so that it is barely visible. From last section, it is known that the time complexity of enumerate strategy algorithm is O(n^k), and the upper bound of n is $n_{max} = (\log (1 - (β / w_{min} k_{w_{min}})) / - π r^{2}) \times A \times k_{w_{min}}$ . Thus, when the coverage quality increases, the running time increases fast. This indicates that the theoretical analysis results are in agreement with the experimental results.

Figure 7.

Running time with varying coverage quality.

Table 4 shows the results of the third experiment, in which the relationship between deployment cost and deployment area is evaluated, while the coverage quality remains unchanged. The related parameters are as follows: costs and weights of each type are {0.15, 0.25, 0.28, 0.32} and {0.2, 0.26, 0.24, 0.3}, respectively. Sensing radius of each node and coverage quality are 20 m and 60%, respectively. The deployment areas change from 50 × 50 to 400 × 400 m². It can be observed from Table 4 that with an increase in the area, the deployment costs also increase since more sensor nodes are needed to be deployed in the monitoring region in order to maintain sufficient coverage quality. On the whole, the deployment costs of the enumerate strategy algorithm are slightly less than that of the greedy strategy.

Table 4.

Deployment costs of different deployment areas.

Deployment area (m²)	Greedy strategy		Enumerate strategy
	Deployment costs	Deployment schemes	Deployment costs	Deployment schemes
50 × 50	2	[2, 2, 2, 2]	1.87	[3, 2, 1, 2]
100 × 100	7.27	[9, 8, 6, 7]	7.25	[11, 8, 6, 6]
150 × 150	16.27	[22, 17, 14, 15]	16.24	[22, 18, 13, 15]
200 × 200	28.96	[39, 31, 24, 27]	28.84	[38, 30, 25, 27]
250 × 250	45.08	[60, 48, 38, 42]	45.07	[58, 49, 37, 43]
300 × 300	65.07	[86, 69, 55, 61]	64.89	[86, 67, 55, 62]
350 × 350	88.51	[118, 93, 75, 83]	88.32	[120, 92, 73, 84]
400 × 400	115.49	[153, 122, 97, 109]	115.35	[154, 121, 98, 108]

Furthermore, in order to be more intuitive to see the growth trend of the deployment costs as the coverage area increases, Figure 8 is given. It can be observed from the figure that the two trend lines almost overlap together because the deployment costs of the two algorithms are almost the same.

Figure 8.

Deployment cost with different deployment areas.

In experiment 4, the relationship between the number of types of heterogeneous nodes and the deployment costs is evaluated. Suppose that the coverage quality and the deployment area remain unchanged. The number of types of heterogeneous node k varies from 4 to 10, and the weights of each node are the same, that is, $w_{k} = 1 / k$ . Cost c_i of each type of heterogeneous node is from 0.1 to 0.5, which is generated by uniformly distributed random function. In order to eliminate the influence of random selected samples, the experiment was repeated 50 times and the deployment costs in Figure 9 are the average costs. Since all the nodes have the same weight, the greedy strategy algorithm always could select the optimal nodes. In such a situation, the deployment scheme of the greedy strategy is the optimal scheme, whose deployment cost is the same with the enumerate strategy. It can be seen from Figure 9 that the deployment costs increase as the k increases. Because when k is increasing, the weights of each node become small, and the fusion coverage quality will be worse. In order to maintain the required coverage quality, more nodes should be deployed, so the deployment costs also go up.

Figure 9.

Deployment cost with varying k.

From the above four experiments, it can be seen that the performance of the exact algorithm in experiments 1 and 3 is slightly better than that of the approximate algorithm because it can find the optimal solution using the enumeration strategy. From experiment 2, it is known that the efficiency of enumeration strategy is poor because it needs to list all the possible deployment schemes, while the greedy strategy has a very high efficiency that its running time grows very slowly as the coverage quality increases. Generally speaking, the approximate algorithm with greedy strategy has better comprehensive performance and better adaptability. The exact algorithm of enumeration strategy is suitable for the applications in which the monitoring areas are relatively small or nodes are very expensive, and there is no need to consider the limitation of running time.

Conclusion

In this article, a novel composite event deployment problem was studied with the purpose of minimizing deployment costs subject to the constraint of achieving a required coverage quality, and the mathematical model for this optimal problem is given. Considering the temporal and spatial association of the heterogeneous nodes, a novel atomic event model and composite event model are proposed, and the coverage quality of the monitoring region based on these two event models is analyzed. Then, an exact algorithm using enumeration strategy and a greedy strategy approximation algorithm for finding the optimal solution are proposed. Furthermore, the time complexity and approximability of these two algorithms are analyzed.

Experimental results show that in the wide range of composite events monitoring, a feasible deployment scheme which has relatively less deployment cost and good coverage quality could be obtained rapidly using the greedy strategy approximation algorithm.

Footnotes

Acknowledgements

The authors thank the ICISCE conference for providing an opportunity to preliminarily present the DCMP problem and its preliminary solution. The authors also thank the anonymous reviewers for their constructive advice.

Academic Editor: Daniel Gutierrez-Reina

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the Science and technology project of Guangdong Province (2016A020209012 and 2015A010103015), the major projects in Guangdong Province (2015B010104005), Chinese National Natural Science Foundation (61502110), and the natural science foundation of Guangdong Province (2014A030307014).

References

Zhang

Nevat

Peters

. Event detection in wireless sensor networks in random spatial sensors deployments. IEEE T Signal Proces 2015; 63(22): 6122–6135.

Shirvanimoghaddam

Vucetic

. Binary compressive sensing via analog fountain coding. IEEE T Signal Proces 2015; 63(24): 6540–6552.

Keally

Zhou

Xing

. A learning-based approach to confident event detection in heterogeneous sensor networks. ACM T Sensor Network 2014; 11(1): 1–28.

Banerjee

Xie

Agrawal

. Fault tolerant multiple event detection in a wireless sensor network. J Parallel Distr Com 2014; 68(9): 1222–1234.

Zhu

. A probabilistic approach to statistical QoS provision of event detection in sensor networks. Wirel Netw 2015; 22(2): 439–451.

Jin

Wang

. EECCR: an energy-efficient m-coverage and n-connectivity routing algorithm under border effects in heterogeneous sensor networks. IEEE T Veh Technol 2009; 58(3): 1429–1442.

Esnaashari

Meybodi

. Deployment of a mobile wireless sensor network with k-coverage constraint: a cellular learning automata approach. Wirel Netw 2013; 19(5): 945–968.

Luo

Wang

. Autonomous deployment for load balancing k-surface coverage in sensor networks. IEEE T Wirel Commun 2014; 14(1): 279–293.

Wang

. Coverage control in sensor networks. London: Springer Publishing Company, 2010.

10.

Lai

Cao

Fan

. TED: efficient type-based composite event detection for wireless sensor network. In: Proceedings of the IEEE international conference on distributed computing in sensor systems and workshops (DCOSS), Barcelona, 27–29 June 2011. New York: IEEE.

11.

Liu

Cao

Tang

. A generalized coverage-preserving scheduling in WSNs: a case study in structural health monitoring. In: Proceedings of the 2014 IEEE INFOCOM, Toronto, ON, Canada, 27 April–2 May 2014. New York: IEEE.

12.

Marta

Yang

Cardei

. Energy-efficient composite event detection in wireless sensor networks. In: Proceedings of the international conference on wireless algorithms, systems, and applications, Boston, MA, 16–18 August 2009. Berlin, Heidelberg: Springer.

13.

. Delay-bounded and energy-efficient composite event monitoring in heterogeneous wireless sensor networks. IEEE T Parall Distr 2010; 21(9): 1373–1385.

14.

Beyah

. Composite event detection in wireless sensor networks. In: Proceedings of the IEEE international conference on performance, computing, and communications conference, New Orleans, LA, 11–13 April 2007, pp.264–271. New York: IEEE.

15.

Yang

Cardei

. Sensor deployment for composite event detection in mobile WSNs. In: Li

Huynh

Das

. (eds) Wireless algorithms, systems, and applications. Berlin, Heidelberg: Springer, 2008, pp.249–260.

16.

Gao

Cai

. Composite event coverage in wireless sensor networks with heterogeneous sensors. In: Proceedings of the 2015 IEEE international conference on computer communications (INFOCOM), Kowloon, Hong Kong, 26 April–1 May 2015. New York: IEEE.

17.

Dong

. Deployment cost optimal for composite event detection in heterogeneous wireless sensor networks. In: Proceedings of the 2016 3rd international conference on information science and control engineering, Beijing, China, 8–10 July 2016, pp.1288–1292. New York: IEEE.

18.

Gao

. Model-based approximate event detection in heterogeneous wireless sensor networks. In: Cai

Wang

Cheng

. (eds) Wireless algorithms, systems, and applications. Cham: Springer International Publishing, 2014, pp.225–235.

19.

Chakravarthy

Krishnaprasad

Anwar

. Composite events for active databases: semantics, contexts and detection. In: Proceedings of the 20th international conference on very large data bases (VLDB ’94), Santiago de Chile, 12–15 September 1994, pp.606–617. San Francisco, CA: Morgan Kaufmann Publishers.

20.

Tang

Wang

. The simulated greedy algorithm for several submodular matroid secretary problems. Theor Comput Syst 2016; 58(4): 681–706.

21.

Sviridenko

. A note on maximizing a submodular set function subject to a knapsack constraint. Oper Res Lett 2004; 32(1): 41–43.

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

Abstract

Keywords

Introduction

Related works

The event model and coverage quality evaluation method

Event model

Atomic event

Composite event

Coverage quality evaluation method

DCMP problem and algorithm description

Problem description

Definition 1

DCMP

Complexity analysis for DCMP problem

Theorem 1

Proof

Algorithm implementation

Approximate algorithm

Exact algorithm

Performance analysis

Conclusion 1

Proof

Conclusion 2

Proof

Conclusion 3

Proof

Experimental results

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

References