Distributed and morphological operation-based data collection algorithm

Abstract

When monitoring the environment with wireless sensor networks, the data sensed by the nodes within event backbone regions can adequately represent the events. As a result, identifying event backbone regions is a key issue for wireless sensor networks. With this aim, we propose a distributed and morphological operation-based data collection algorithm. Inspired by the use of morphological erosion and dilation on binary images, the proposed distributed and morphological operation-based data collection algorithm calculates the structuring neighbors of each node based on the structuring element, and it produces an event-monitoring map of structuring neighbors with less cost and then determines whether to erode or not. The remaining nodes that are not eroded become the event backbone nodes and send their sensing data. Moreover, according to the event backbone regions, the sink can approximately recover the complete event regions by the dilation operation. The algorithm analysis and experimental results show that the proposed algorithm can lead to lower overhead, decrease the amount of transmitted data, prolong the network lifetime, and rapidly recover event regions.

Keywords

Wireless sensor networks morphological operations erosion dilation data collection

Introduction

With the development of low-power wireless communication, microsensors, microprocessors, embedded computing, and distributed information collecting and processing, wireless sensor networks (WSNs) have been widely used in many fields. WSNs sense the environment via a large number of inexpensive and tiny wireless sensor nodes. They are characterized by limited communicating and computing resources, un- or hard-rechargeable power, and other features. Limited node energy is one of the key constraints for applications in WSNs.¹

The energy consumption in wireless sensor nodes consists of three parts: sensing, computing, and communicating. The energy spent on communication accounts for the largest expenditure and depends on the transmission of data and control messages. Thus, decreasing in-network data volumes is an effective method of conserving energy. Currently, many researchers design data compression or fusion mechanisms, mine in-network data correlation, and investigate the methods for building aggregation routing trees that facilitate data aggregation to decrease the in-network data.^2–35

For in-network data transmissions, sensing data from nodes within event border regions is not sufficiently precise and fluctuate, and the sensing data from nodes within event backbone regions can determine the event information. In addition, data sensed by nodes in event backbone regions are highly correlated, whereas the sensing data from event border regions are poorly correlated. As a result, event backbone regions are more effective for aggregating data than whole event regions, and they present higher data aggregation efficiency and better data reconstruction accuracy. Although important information can be obtained from event border regions, the probability is small. Statistically, information in event backbone regions is important and well correlated. Under limited power conditions, energy should be saved as much as possible. Based on the discussion above, a method of determining the event backbone regions must be developed to facilitate decrease in data size. Although current methods associated with decreases of in-network data can save energy, they may not consider the advantages obtained from event backbone regions or provide a method of determining event backbone regions.

To address this issue, we incorporate the erosion and dilation of binary images to WSNs and propose a distributed and morphological operation-based data collection algorithm (DMOA). The major contributions of this article are threefold: (1) the DMOA can extract event backbone regions effectively to decrease in-network data transmission, and it can recover event regions quickly by simple morphological operations; (2) the DMOA provides a low overhead strategy for event information exchange; and (3) experimental analyses indicated that our proposed method can be combined with other energy saving strategies to improve energy conservation.

The remainder of this article is organized as follows: section “Related works” introduces the current energy-saving algorithms on in-network data in WSNs, section “Background and motivation” presents the background knowledge and our research motivation, section “Proposed algorithm” details the DMOA, section “Theoretical analysis and experiments” analyzes the algorithm and verifies it by simulation, and section “Conclusion” concludes the article.

Related works

The techniques for energy conservation represent essential research with regard to WSNs, and developing methods of decreasing in-network data transmission is always a hotspot problem. The volume and manner of decreasing data will directly affect the performance of the WSNs. In recent years, many experts have conducted studies on various strategies associated with decreasing data.

Routing for data aggregation, compression, and fusion is very effective to decrease in-network data transmission.^2–15 In the shortest path tree (SPT),² each source sends its information to the sink along the shortest path between the two and overlapping paths are combined to form an aggregation tree. Energy efficient cluster-based data aggregation (ECBDA)³ divides the monitoring region into multiple layers, forms K clusters for each layer according to the node residual energy and communication cost, fuses data in clusters, and routes data by efficient route discovery. Dynamic and scalable tree (DST)⁴ and dynamic and scalable tree aware of spatial correlation (YEAST)⁵ are algorithms for event-driven WSNs, and they can build routing trees with high fusion efficiency based on events. The load balanced data aggregation tree (LBDAT) can construct a load-balanced data aggregation tree based on a probability network model by solving maximum independent sets.⁶ Sutagundar and Manvi⁷ used multi-agent technology to construct the fishbone structure of the whole network, which can aggregate the data in parallel. Wan et al.⁸ work on constructing data aggregation trees to minimize the total energy cost of data transmission for large-scale WSNs. They divide query area and build trees within each sub-query area to reduce network hot spots, which can help prolong network lifetime. Liu et al.⁹ design a polynomial time algorithm to determine the optimal transmission policy and the corresponding time slot for each node to transmit the aggregation data on an arbitrary tree. Nguyen et al.¹⁰ studied the maximum lifetime data aggregation tree scheduling (MLDATS) problem and propose a local-tree-reconstruction-based scheduling algorithm (LTRBSA), which uses the local-tree reconstruction algorithm to find more virtual data aggregation trees. A lightweight, latency-aware routing for data compression (L2DC) scheme¹¹ facilitates data compression by determining each node to keep packets for compression locally or to send them out to be compressed in a distributed manner, and it can eliminate auxiliary redundant packet and select relay nodes to reduce packet latency. Aly et al.^12–14 proposed a series of distributed data collection algorithms for large-scale WSNs, and these algorithms do not depend on the sensor network topology, routing tables, or geographic locations of sensor nodes. Subtree merging–based data collection (SMDC) is designed for area query applications, and it can prevent unnecessary energy consumption in ancestor nodes for routing through the union of disjoint sets for different subtrees.¹⁵

In-network data compression, fusion, and scheduling are related to data decreasing directly.^16–24 Multi-level aggregation (MLA)¹⁶ utilizes Brownian motion to remove redundancies and processes data according to the entropy and wavelet based on clusters. Liu and Jhang¹⁷ analyze the problem of data scheduling with minimum transmission cost and proposed a distributed data scheduling algorithm based on the theory of a dominating set. The adaptive data aggregation strategy using network coding (ADANC)¹⁸ combines network coding and traditional data aggregation to improve the efficiency in the cluster-based, random, duty-cycled WSN regions. Li and Liang¹⁹ present a generalized predictive coding framework for unified lossless and lossy data compression and design a corresponding lossless compression algorithm to improve data compression performance for various applications in WSNs. Sheltami et al.²⁰ study discrete cosine transform (DCT) and discrete wavelet transform (DWT) image-compression techniques as they can be implemented on sensor nodes and find DWT outperforms DCT in terms of peak-signal-to-noise, throughput, end-to-end delay, and battery lifetime, while DCT provides better compression ratio than DWT. Chen et al.²¹ discover the DCT coefficients of sorted data become more concentrated and propose a data sorting–based adaptive spatial compression scheme (DS-ASCS) which includes a zigzag scan method and an adaptive spatial compression algorithm, gaining good performance on data compression. Alsheikh et al.²² utilize compressing neural networks to compress data with bound guarantee and propose a rate-distortion balanced data compression algorithm. Wu et al.²³ propose a novel framework with dedicated combination of data prediction, compression, and recovery to simultaneously achieve accuracy and efficiency of the data processing in clustered WSNs. Kim et al.²⁴ propose an m-hop averaging compression algorithm which makes each node compress a certain amount of packets according to the average energy levels of the next m nodes within m hops.

Node selection and sleeping schemes can also help decrease the volume of in-network data transmission, saving energy significantly.^25–35 Chen and Wassell²⁵ propose an active node selection framework for compressive sleeping WSNs, where the node selection problem is framed as the design of a specialized sensing matrix and solved as an optimization problem by a constrained convex relaxation plus a rounding scheme approximately. Cheng et al.²⁶ use the partially ordered tuple (data coverage range, residual energy) to find an initial active node set, calculate the correlated node set with minimum set size and maximum geometric mean of residual energy of each node, and finally, remove nodes based on correlated node sets to reduce the number of active nodes. For heterogeneous WSNs, Sandhya et al.²⁷ select the aggregator nodes periodically based on location, taking advantage of the energy heterogeneity of the sensor nodes. For sleep/wake-up scheduling, Ye and Zhang²⁸ make each node decide its own operation mode (sleep, listen, or transmission) autonomously in each time slot in a decentralized manner based on the reinforcement learning technique. Sleep-awake energy efficient distributed (SEED) clustering algorithm²⁹ divides the network sensing field into three energy regions and let same application base sensor nodes form sub-clusters to decrease the number of transmissions toward the base station. Wang and Wang³⁰ propose a dynamic node selection scheme based on genetic algorithms whose objective function for collaborative target tracking is constructed by the information utility and the remaining energy of sensor nodes. The scheme can optimize the tradeoff between the accuracy of tracking and the energy cost of nodes. Jiang et al.³¹ propose an energy efficient node selection algorithm for bearings-only target tracking WSNs, in which the residual energy of a node is incorporated into the objective function of node selection. Feng et al.³² design a novel spatial-correlated node selection strategy, which selects the node according to the residual energy and the spatial correlation of the nodes located at the different positions. Shi et al.³³ propose a centralized algorithm to determine the approximate minimum set of nodes based on the calculation of node redundancy degree and the partition of the target area. Group-based energy-conserving protocol (GECP)³⁴ divides the network into groups and selects only one active node in each group to maintain a connected backbone and minimizes the number of transitions between sleep and active states to minimize the transition energy and the leader election frequency. Nasridinov et al.³⁵ seem the aggregator node selection process as a top-k query problem and solve it using a modified sort-filter-skyline algorithm.

Background and motivation

Morphological operations

For a digital image, its pixel values can be regarded as a function of the pixel coordinates, $z = f (x, y)$ , where $(x, y)$ represents the coordinates of the pixels, and $(x, y) \in Z^{2}$ . If $f : Z^{2} \mapsto {0, 1}$ , the digital image is a binary image. In morphology theory, a binary image, denoted as A, is a set of foreground pixels: $A = {(x, y) | f (x, y) = 1 \land (x, y) \in Z^{2})}$ . As shown in Figure 1(a), $A = {(x, y) | (5 \leq x \leq 11) \land (4 \leq y \leq 6) \in Z^{2})}$ is a binary image with a rectangular object. Based on the set representation of binary images, one can execute set operations, such as union, intersection, complement, and difference.

Figure 1.

Morphological operations: (a) binary image with rectangle object (b) structuring element.

The basic concept of a mathematical morphology³⁶ is to measure and extract the corresponding shapes from an image using a structuring element for image analysis and recognition. The erosion and dilation operations are the basis of morphological image processing. The style of erosion and dilation on binary images and the changes in the images are controlled by structuring elements. A structuring element is a binary matrix image. For convenience, the structuring element can be displayed only by 1, and its origin must be marked as shown in Figure 1(b).

To erode and dilate binary images, the morphology defines two basic operators on binary images. Suppose that A is a binary image and S is a structuring element. The complement of A is $A^{c}$ : $A^{c} = {p | p \notin A}$ . The reflection of A is $\hat{A}$ : $\hat{A} = {p | p = - q, q \in A}$ , and the translation of A by a point $o = (x, y)$ is ${(A)}_{o}$ : ${(A)}_{o} = {p | p = q + o, q \in A}$ .

With the complement, reflection, and translation operators above, the erosion and dilation operators are defined as set operations based on the structuring element. The erosion of A by S, denoted as $E (A, S)$ , is defined in equation (1), where $ϕ$ is the empty set

E (A, S) = {o | {(S)}_{o} \cap A^{c} = ϕ}

(1)

The dilation of A by S, which is denoted as $D (A, S)$ , is defined in equation (2)

D (A, S) = {o | (\hat{S})_{o} \cap A \neq ϕ}

(2)

The rectangular object in Figure 1(a) is eroded and dilated using the structuring element in Figure 1(b), and the results are shown in Figure 2(a) and (b), respectively. For the object in Figure 1(a), Figure 2(a) depicts its backbone and Figure 2(b) shows the corresponding dilation. With different structuring elements, the style and level of erosion and dilation on binary images are different.

Figure 2.

Illustrations of erosion and dilation: (a) erosion and (b) dilation.

Research motivation

Based on the above information, the erosion operation on a binary image can thin or shrink the objects within the images to obtain the backbone, and the dilation operation can thicken or expand the objects. The eroded binary image can be dilated to obtain an approximate original image.

Suppose that $G = (V, a)$ is a WSN with nodes deployed uniformly, where $V = {Nod e_{1}, \dots, Nod e_{n}}$ is the node set and a is the interval between adjacent nodes. An example is shown in Figure 3(a). If the nodes that detected the event are marked with 1 (white nodes) and the other nodes are marked with 0 (black nodes), then the event monitoring status of the network could be regarded as a binary image as shown in Figure 3(b).

Figure 3.

Demonstration of a uniform WSN: (a) WSN with nodes deployed uniformly and (b) event-monitoring status.

Therefore, we can introduce erosion and dilation operations to WSNs with nodes deployed uniformly. Event backbone regions can be extracted by the erosion operation on the nodes, and collecting data only from the nodes within the backbone regions can help reduce inaccurate data transmission and improve data aggregation. In addition, through the dilation operation on nodes, the whole event region can be approximately recovered according to its backbone. Because WSNs are limited by energy and require a quick response and scientific decision-making, a method of applying simple morphological operations to WSNs is valuable.

For WSNs with nodes deployed irregularly, a uniform network can be transformed by gridding technologies.³⁷ For example, we can utilize the existing technologies to partition the network into meshes, choose one active node for each grid and take the center of the grid as the node’s position, thereby producing an approximate uniform WSN. Therefore, in this article, we only discuss the strategies for uniform WSNs.

Proposed algorithm

This section details the algorithm DMOA. For uniform WSNs, the location of each node is identified by the coordinates $(x, y)$ , where $(x, y) \in Z^{2}$ . In addition, the coordinates of the node located at the left bottom of the network are set to (1, 1) as shown in Figure 4. For each node, $Nod e_{u}$ , its coordinates are denoted as $(x_{u}, y_{u})$ . For example, in Figure 4, the coordinates of $Nod e_{u}$ are $(2, 3)$ .

Figure 4.

Coordinates of node.

Determination about border and backbone nodes

Suppose that the structuring element used for node erosion and dilation is S. For $Nod e_{u}$ , its coordinates are $(x_{u}, y_{u})$ . We move S to the $(x_{u}, y_{u})$ and obtain $S' (Nod e_{u}) = {p | p = q + (x_{u}, y_{u}), q \in S}$ . A node whose coordinates belong to $S' (Nod e_{u})$ is called a structuring neighbor of $Nod e_{u}$ . The coordinate set of all structuring neighbors of $Nod e_{u}$ is denoted as $SNeighbor (Nod e_{u})$ , as shown in equation (3). Correspondingly, the area covered by the nodes with coordinates in $SNeighbor (Nod e_{u})$ is called the structuring neighborhood of $Nod e_{u}$

\begin{array}{l} S N e i g h b o r (N o d e_{u}) \\ = {(x_{v}, y_{v}) | N o d e_{v} \in V, (x_{v}, y_{v}) \in S^{'} (N o d e_{u})} \end{array}

(3)

If $Nod e_{w}$ is located on the border of the monitoring area, its $S' (Nod e_{w})$ could be beyond the border; in other words, $S' (Nod e_{w}) - SNeighbor (Nod e_{w}) \neq ϕ$ could occur. When $S' (Nod e_{w}) - SNeighbor (Nod e_{w}) \neq ϕ$ , nodes are not observed at locations with coordinates in $S' (Nod e_{w}) - SNeighbor (Nod e_{w})$ . We assume that certain nodes are located at such coordinates, which are called virtual structuring neighbors, and they detect the same event as $Nod e_{w}$ so that all nodes in the border of the monitoring area are not eroded arbitrarily. Thus, for $Nod e_{u}$ , we define $VSNeighbor (Nod e_{u})$ in equation (4)

VSNeighbor (Nod e_{u}) = S' (Nod e_{u}) - SNeighbor (Nod e_{u})

(4)

where $VSNeighbor (Nod e_{u})$ is the coordinate set of all of the virtual structuring neighbors of $Nod e_{u}$ .

Each node has a field $E_ID$ , which is used to record the identifier of the event. If $Nod e_{u}$ monitors an event whose identifier is $Even t_{i}$ , then $E_ID (Nod e_{u}) = Even t_{i}$ . Otherwise, $E_ID (Nod e_{u}) = NULL$ . Once an event is monitored, $Nod e_{u}$ should know the event-monitoring status of its structuring neighbors and construct the corresponding event-monitoring map $M (Nod e_{u})$ based on the structuring neighbors according to equation (5)

\begin{matrix} M (Nod e_{u}) \\ = {(x_{v} - x_{u}, y_{v} - y_{u}) | (x_{v}, y_{v}) \in SNeighbor (Nod e_{u}), \\ E_ID (Nod e_{v}) = = E_ID (Nod e_{u})} \cup \\ {(x_{v} - x_{u}, y_{v} - y_{u}) | (x_{v}, y_{v}) \in VSNeighbor (Nod e_{u})} \end{matrix}

(5)

If $M (Nod e_{u}) = = S$ , $Nod e_{u}$ is marked as a backbone node (the nodes within the event backbone regions are called event backbone nodes, and the nodes within event border regions are called event border nodes) of the event and sends its sensing data to the sink. If $M (Nod e_{u}) \neq S$ , $Nod e_{u}$ does nothing.

Figure 5 shows the case of structuring neighbors of four nodes, where the numbers beside the nodes are node identifiers and the white nodes are monitoring an event. We take $Nod e_{29}$ , $Nod e_{32}$ , $Nod e_{35}$ and $Nod e_{40}$ as examples, where $Nod e_{32}$ and $Nod e_{40}$ are located at the border of the monitoring region. Using structuring element S, according to equation (3), we can calculate $SNeighbor (Nod e_{29}) = {(4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5), (6, 3), (6, 4), (6, 5)}$ , $SNeighbor (Nod e_{32}) = {(7, 3), (7, 4), (7, 5), (8, 3), (8, 4), (8, 5)}$ , $S N e i g h b o r (N o d e_{35}) = {(2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6)}$ , and $SNeighbor (Nod e_{40}) = {(7, 4), (7, 5), (7, 6), (8, 4), (8, 5), (8, 6)}$ . According to equation (5), $VSNeighbor (Nod e_{29}) = ϕ$ , $VSNeighbor (Nod e_{32}) = {(9, 3), (9, 4), (9, 5)}$ , $VSNeighbor (Nod e_{35}) = ϕ$ , and $VSNeighbor (Nod e_{40}) = {(9, 4), (9, 5), (9, 6)}$ . Finally, based on equation (5), the corresponding event-monitoring maps, $M (Nod e_{29})$ , $M (Nod e_{32})$ , $M (Nod e_{35})$ , and $M (Nod e_{40})$ , are calculated, as shown in Figure 5. Because $M (Nod e_{35}) \neq S$ and $M (Nod e_{40}) \neq S$ , $Nod e_{35}$ and $Nod e_{40}$ are regarded as event border nodes, and they must be eroded. Additionally, $M (Nod e_{29}) = S$ and $M (Nod e_{32}) = S$ ; thus, $Nod e_{29}$ and $Nod e_{40}$ are judged to be event backbone nodes.

Figure 5.

Structuring neighbors and event-monitoring maps of nodes.

Structuring neighbors

Considering the characteristics of WSNs, we select a square structuring element, such as $S_{s \times s}$ (s is odd). For example, Figure 6 shows three square structuring elements, $S_{3 \times 3}$ , $S_{5 \times 5}$ , and $S_{7 \times 7}$ . Correspondingly, each node locates its structuring neighbors within the 8-/24-/48- neighborhood (i.e. 8/24/48 nodes within the neighborhood). Moreover, the square structuring elements are central and bilaterally symmetric; thus, the relation of structuring neighbor R is symmetric, that is, $< Nod e_{u}, Nod e_{v} > \in R \Leftrightarrow < Nod e_{v}, Nod e_{u} > \in R$ . The method of obtaining structuring neighbors is shown in Algorithm 1.

Figure 6.

Square structuring elements.

Algorithm 1. Obtaining structuring neighbors
//The minimum and maximum X(Y) coordinates of the nodes are $x_{\min}$ and $x_{\max}$ ( $y_{\min}$ and $y_{\max}$ ).
// $S_{s \times s}$ is a square structuring element, and s is odd.
1. $SNetwork = {(x, y) \| x_{\min} \leq x \leq x_{\max}, y_{\min} \leq y \leq y_{\max}, x \in Z, y \in Z}$
2. for each node, such as $Nod e_{u}$ , in network do
3. $SNeighbor (Nod e_{u}) = {(x, y) \| x_{u} - \frac{s - 1}{2} \leq x \leq x_{u} + \frac{s - 1}{2}, y_{u} - \frac{s - 1}{2} \leq y \leq y_{u} + \frac{s - 1}{2}, x \in Z, y \in Z}$
4. $SNeighbor (Nod e_{u}) = SNeighbor (Nod e_{u}) \cap SNetwork$
5. end

Event information transmission

From section “Determination about border and backbone nodes,” a node requires event-monitoring information about its structuring neighbors and produces an event-monitoring map to determine whether it should be eroded. Because of the limited energy of sensor nodes, the cost for a node to acquire the event information from its structuring neighbors should be as small as possible. Thus, we design a strategy for event information transmission with a low cost.

Each node does not require its structuring neighbors to send their event-monitoring information actively. The node sends out the event-monitoring information within its structuring neighborhood when an event occurs, and then the structuring neighbors can passively obtain the event-monitoring information. Because a node only requires event information from its structuring neighbors, the transmission of event information is restricted within the structuring neighborhood determined by the structuring element.

For a WSN, $G = (V, a)$ , with uniformly distributed nodes, structuring neighbors are deployed in a square manner. To facilitate the transmission of event monitoring messages, the node communication radius should be the multiplication of an integer (denoted as k) and $\sqrt{2} a$ . Suppose that the structuring element is $S_{s \times s}$ (s is odd) and the communication radius is $k \sqrt{2} a$ . When k is equal to $(s - 1) / 2$ , one event message transmission of a node can transmit the event information to all of the structuring neighbors. When k is greater than $(s - 1) / 2$ , the coverage area of the event message transmission is larger than its structuring neighborhood, which means that unrelated nodes can also receive the event message, thereby leading to extra energy consumption during event message transmission and greater communication competition among the nodes. Therefore, we consider only $k = 1, \dots, (s - 1) / 2$ , and the event message can inform all of its structuring neighbors with $⌈ ((s - 1) / 2 k) ⌉$ hops.

The event information is enveloped in the event discovery message (EDM), $EDM \overset{Δ}{=} < E_ID, S_P, TTL >$ , where $E_ID$ is the identifier of an event, $S_P$ (source position) represents the coordinates of the source node that sends out the message, and TTL is the lifetime of the message. To decrease the energy consumption for the transmission of $EDM s$ , only a few nodes that meet a particular requirement forward the $EDM s$ , and the rules are as follows.

Suppose that a node $Nod e_{u}$ detects an event $Even t_{i}$ , and it sends its message $EDM = < Even t_{i}, (x_{u}, y_{u}), TT L_{initial} >$ with a communication radius of $k \sqrt{2} a$ . After $t (1, 2, \dots)$ hops, the coordinate set of nodes which can forward the EDM is $Forwarder (x_{u}, y_{u}, t)$ in equation (6)

Forwarder (x_{u}, y_{u}, t) = F - F'

(6)

where

\begin{matrix} F = {(x, y) | x = x_{u} - t \times k + j_{1} \times 2 k \\ y = y_{u} - t \times k + j_{2} \times 2 k, 0 \leq j_{1}, j_{2} \leq t, j_{1}, j_{2} \in Z} \end{matrix}

(7)

\begin{matrix} F' = {(x, y) | x = x_{u} - t \times k + j_{1} \times 2 k \\ y = y_{u} - t \times k + j_{2} \times 2 k, 0 < j_{1}, j_{2} < t, j_{1}, j_{2} \in Z} \end{matrix}

(8)

Figure 7 shows an example of EDM forwarding, and k is set to 2. In Figure 7(a), when the node $Nod e_{105}$ (marked in yellow) sends its EDM, t is set to 1 at the moment, and all of the nodes within the green region receive the message, although only the red nodes forward the EDM further. Thus, we can have $Forwarder (9, 7, 1) = {(7, 5), (11, 5), (7, 9), (11, 9)}$ . After the EDM is forwarded by the red nodes in Figure 7(a), t is set to 2. In Figure 7(b), all of the nodes within the blue region receive the message, and the updated red nodes are responsible for forwarding the message: $Forwarder (9, 7, 2) = {(5, 3), (9, 3), (13, 3), (5, 7), (13, 7), (5, 11), (9, 11), (13, 11)}$ . After the red nodes in Figure 7(b) forward the EDM, t is set to 3. In Figure 7(c), the nodes within the purple region receive the message, and the red nodes forward the EDM, that is, $Forwarder (9, 7, 3) = {(3, 1), (7, 1), (11, 1), (15, 1), (3, 5), (15, 5), (3, 9), (15, 9), (3, 13), (7, 13), (11, 13), (15, 13)}$ .

Figure 7.

Examples of EDM forwarding: (a) t = 1, (b) t = 2, and (c) t = 3.

To restrict the EDM forwarding to the structuring neighborhood, each node holds a variable $Num_H$ . $Num_H$ records the maximum number of EDM forwardings within the structuring neighborhood, and it is determined by the size of the structuring element and the node communication radius. If the size of the structuring element is $s \times s$ and the communication radius is r, then an EDM will be forwarded $⌈ (s - 1) a / (\sqrt{2} r) ⌉$ times to ensure that all of the structuring neighbors receive it. Thus, $Num_H$ is set to $⌈ (s - 1) a / (\sqrt{2} r) ⌉$ . The TTL field in EDM indicates the remaining times that the message can be forwarded, and it is initialized as $TT L_{initial} = Num_H$ . With $Num_H$ and TTL, a node can obtain the hop count of the EDM message. Then, the set of forwarders is calculated and whether to forward the EDM is decided. Finally, the forwarding strategy of $EDM s$ is executed as previously described.

Additionally, each node contains a processing table for EDM, and we denote the table as PT. This table can accelerate the nodes to discard the processed $EDM s$ . The table PT consists of three fields: $S_P$ , $E_ID$ , and TIME, where TIME records the moment of EDM forwarding. After processing an EDM successfully (forwarding or discarding), the node will add a new record to the PT. Then, the nodes calculate the occurrence time of each record according to TIME. If a record occurs longer than $Δ T_{1}$ ( $Δ T_{1}$ is set to the time interval of transmitting an EDM throughout the whole structuring neighborhood), then it is invalid. Nodes delete invalid records occasionally.

Algorithm 2 introduces the transmission strategy of the event information. Suppose that a node $Nod e_{u}$ has received an EDM message. It obtains the TTL from the EDM and subtracts the TTL by 1 to obtain the remaining number for forwarding. If the number is greater than 0, the node might forward the message; otherwise, there is no need to forward the EDM. If the EDM might need to be forwarded, $Nod e_{u}$ will decide whether it is one of the structuring neighbors of the source node or not. If not, $Nod e_{u}$ will not forward the EDM; otherwise, $Nod e_{u}$ must determine whether or not such an EDM has been processed recently. If $Nod e_{u}$ is a structuring neighbor of the source node of the EDM and it has not processed such an EDM recently (shown in Algorithm 2, lines 6–8), it updates its PT (which means that the node has completed the judgment about forwarding the EDM), calculates the times of the EDM forwarding according to TTL and $Num_H$ , and gains the forwarder set Forwarder based on the coordinates of the EDM’s source node (Algorithm 2, lines 9–11). It checks whether it is a member of the Forwarder or not, and if $(x_{u}, y_{u}) \in Forwarder$ , then $Nod e_{u}$ should forward the EDM, as shown in Algorithm 2, lines 12–14. Under other statuses, $Nod e_{u}$ does not forward the EDM.

Algorithm 2. Event information transmission
//The operations of $Nod e_{u}$ for EDM forwarding. $Num_H = ⌈ (s - 1) a / (\sqrt{2} r) ⌉$
1. while true do
2. if anEDMis received then
3. $TT L_{temp} = TTL (EDM) - 1$ ;
4. if $TT L_{temp} > 0$ then
5. $(x_{temp}, y_{temp}) = S_P (EDM)$ ;
6. if $(x_{temp}, y_{temp}) \in SNeighbor (Nod e_{u})$ then
7. Find an item I in $PT (Nod e_{u})$ with $E_ID (I) = = E_ID (EDM)$ and $S_P (I) = = S_P (EDM)$ ;
8. if (I does not exist) or (I exists and $T_{current} > TIME (I) + Δ T_{1}$ ) then
// $T_{current}$ represents the current time
9. $PT (Nod e_{u}) = (PT (Nod e_{u}) - {I}) \cup {< E_ID (EDM), S_P (EDM), T_{current} >}$ ;
10. $t = Nu m_H - TT L_{temp}$ ;
11. Calculate $Forwarder (x_{temp}, y_{temp}, t)$ according to equation (6);
12. if $(x_{u}, y_{u}) \in Forwarder (x_{temp}, y_{temp}, t)$ then
13. $TTL (EDM) = TT L_{temp}$ ;
14. Forward the EDM;
15. else
16. Discard the EDM;
17. end
18. end
19. end
20. end
21. end
22. end

Event backbone node acquisition

In addition, $E_ID$ , SNeighbor, $Num_H$ and PT, BB (BackBone), and $E_M$ (Event_Map) are maintained for each node to execute distributed node erosion. BB indicates whether the node is in the event backbone region or not (1 is yes and 0 is not). If the node detects no event, then $E_M$ is empty; otherwise, $E_M$ represents the coordinates set of the structuring neighbors that detect the same event. For $Nod e_{u}$ , the definition $E_M$ is in equation (9)

E_M (Nod e_{u}) = {\begin{matrix} ϕ, & E_ID (Nod e_{u}) = = NULL \\ Ω, & E_ID (Nod e_{u}) \neq NULL \end{matrix}

(9)

where $Ω \overset{Δ}{=} {(x_{v}, y_{v}) | (x_{v}, y_{v}) \in SNeighbor (Nod e_{u})$ and $E_ID (Nod e_{v}) = = E_ID (Nod e_{u})}$ .

If $Nod e_{u}$ detects an event $Even t_{i}$ , $E_ID$ and $E_M$ are updated to generate the EDM. A timer CollectEDM is set after the transmission of the EDM, and it indicates the beginning of the event information collecting phase. For $Nod e_{u}$ , $EDM s$ from the nodes that are not its structuring neighbors are all discarded. When $Nod e_{u}$ receives an EDM from a structuring neighbor and the structuring neighbor detects the same event from $Nod e_{u}$ , the coordinates of the structuring neighbor are recorded in $E_M$ of $Nod e_{u}$ . The forwarding of the EDM follows Algorithm 2. The process above is shown in lines 2–15 of Algorithm 3.

Algorithm 3. Event backbone node acquisition
//Distributed erosion operation on $Nod e_{u}$
1. while true do
2. if an event, say $Even t_{i}$ is detected then
3. $E_ID (u) = Even t_{i}$ ;
4. $E_M (Nod e_{u}) = E_M (Nod e_{u}) \cup {(x_{u}, y_{u})}$ ;
5. construct an $EDM = < Even t_{i}, (x_{u}, y_{u}), Num_H >$ and transmit it;
6. Start a timer CollectEDM with $Δ T_{1}$ ;
7. end
8. if anEDMis received and $S_P (EDM) \in SNeighbor (Nod e_{u})$ then
9. if $E_ID (EDM) = = E_ID (Nod e_{u})$ do
10. $E_M (Nod e_{u}) = E_M (Nod e_{u}) \cup {S_P (EDM)}$ ;
11. end
12. Act as Alg. 2;
13. else
14. The EDM is discarded;
15. end
16. if the timer CollectEDM* expires* then//node begins erosion when the timer expires
17. if $SNeighbor (Nod e_{u}) - E_M (Nod e_{u}) = = ϕ$ then
18. $BB (Nod e_{u}) = 1$ ;//backbone node, and its data should be transmitted to sink
19. else
20. $BB (Nod e_{u}) = 0$ ;
21. end
22. end
23. if the event detected by $Nod e_{u}$ ends then
24. $B B (N o d e_{u}) = 0; E_M (N o d e_{u}) = ϕ; E_I D (N o d e_{u}) = NULL$ ;
25. end
26. end

If CollectEDM expires, the event information collecting phase ends and the erosion phase begins as shown in lines 16–22 of Algorithm 3. When the $E_M$ of $Nod e_{u}$ is the same as $SNeighbor (Nod e_{u})$ , there must be $M (Nod e_{u}) = = S$ , which means that $Nod e_{u}$ is located in the event backbone region and should be reserved and transmit data to the sink; otherwise, $Nod e_{u}$ should be eroded and remain silent.

In addition, $Nod e_{u}$ should reset $BB, E_ID$ and $E_M$ to their initial values when the event ends, which is shown in lines 23–25 of Algorithm 3.

The structuring element to be used is not fixed, and its size can be changed according to the network conditions. When the average residual energy is low, a large size is recommended to produce a small event backbone region to extend the network’s lifetime. In this case, although the data cannot represent the whole event region exactly, the data are obtained from the nodes that are more related to the event; thus, the key information remains. Naturally, extending the lifetime at this time is more important than the exact data acquisition. A small size is recommended when the average residual energy is high because it can extend the event backbone region to represent the event more exactly. In other words, because the primary task of WSNs is collecting data, our proposed DMOA can transmit data with appropriate accuracy via an adaptive structuring element size while also saving energy.

Event region recovery

Based on the structuring element and the positions of the data-transmission nodes (i.e. the positions of the event backbone nodes), the sink can recover event regions through a dilation operation. Consequently, the sink can deduce the scope of the event and direct the response or decision. Suppose that there is a WSN used to monitor the environment temperature. If the temperature of a region rises sharply at a certain moment, to facilitate rapid and precise decision making, the backbone of the abnormal region should be dilated to obtain the rough scope of the event.

If a square structuring element is $S_{s \times s}$ , then the details of the recovered event region are provided in Algorithm 4. For $Nod e_{u}$ , suppose that $T_{u}$ is the latest time for the data to reach the sink and $Δ T_{3}$ is the time threshold for determining whether the node is a sending node (i.e. an event backbone node). The sink calculates the difference between the current time and $T_{u}$ and identifies $Nod e_{u}$ as a sending node if the difference is less than $Δ T_{3}$ . Based on all of the sending nodes, the approximate event region can be easily recovered.

Algorithm 4. Recovery of the event region
1. $REA = ϕ$ ;// REA is the set of node coordinates in the recovery event area
2. for each node $Nod e_{u}$ in network do
3. if $T_{current} - T_{u} \leq Δ T_{3}$ then
4. $REA = REA \cup SNeighbor (Nod e_{u})$
5. end
6. end

DMOA

DMOA includes two parts: event region erosion and event region recovery, and the corresponding pseudo-codes of DMOA are listed in Algorithm 5. In lines 2–3, a node $Nod e_{u}$ calculates its structuring neighbors based on its coordinates and structuring element $S_{s \times s}$ , and it initializes $E_M, E_ID, BB, Num_H$ , and the EDM processing table PT. CleanPT in lines 4, 11 and 15 represents a timer that is used to clean outdated records in the PT table periodically and Δ $T_{2}$ is the time interval. In lines 6–11, $Nod e_{u}$ executes Algorithm 3 to determine whether the node itself is an event backbone node or not. $BB (Nod e_{u}) = = 1$ if $Nod e_{u}$ is an event backbone node that transmits the data to sink. Otherwise, $Nod e_{u}$ should be eroded to keep silent. In lines 23–25, when the sink collects the data from all backbone nodes, it can recover the event area through a dilation operation to perform a response or decision. Obviously, the recovery of event area is simple because of the efficient dilation operation and centralized execution of the sink.

Algorithm 5. DMOA
//Node Operations
1. for each node, such as $Nod e_{u}$ do
2. $Nod e_{u}$ gains its structuring neighbor $SNeighbor (Nod e_{u})$ according to Alg. 1.;
3. $E_M (Nod e_{u}) = ϕ; E_ID (Nod e_{u}) = NULL; BB (Nod e_{u}) = 0; Num_H = ⌈ \frac{(s - 1) a}{\sqrt{2} r} ⌉; PT (Nod e_{u}) = ϕ$ ;
4. Start a timer CleanPT with $Δ T_{2}$ ;
5. while true do
6. Act as Alg. 3;
7. if $BB (Nod e_{u}) = = 1$ then
8. Start data transmission;
9. else
10. Keep silent;//Node is eroded in spite that the node detects event
11. end
12. if the timerCleanPTexpires then //Operation on PT table
13. for each item in $PT (Nod e_{u})$ , denoted asI do
14. if $T_{current} - TIME (I) > Δ T_{1}$ then
15. Delete the item I from $PT (Nod e_{u})$ ;
16. Start the timer CleanPT with $Δ T_{2}$ ;
17. end
18. end
19. end
20. end
21. end
22. //Sink Operations
23. Receive data;
24. Act as Alg. 4;
25. Make decision;

Theoretical analysis and experiments

Theoretical analysis

The feasibility and effectiveness of the DMOA are analyzed as below.

A. Based on reliable communication links, Algorithm 2 of the DMOA can transmit the $EDM s$ of any node to its structuring neighbors

Suppose that $Nod e_{v}$ is a structuring neighbor of $Nod e_{u}$ . We will show that $Nod e_{v}$ can receive the EDM of $Nod e_{u}$ .

Let $t_{1} = [(x_{v} - x_{u}) / k], t_{2} = [(y_{v} - y_{u}) / k]$ and $t = max {| t_{1} |, | t_{2} |}$ . Without loss of generality, we can assume that $| t_{1} | \leq | t_{2} |$ .

According to equation (6), calculate the forwarding set $Forwarder (x_{u}, y_{u}, t)$ for $Nod e_{u}$ . If $(x_{v}, y_{v}) \in Forwarder (x_{u}, y_{u}, t)$ , $Nod e_{v}$ must be able to receive the EDM from $Nod e_{u}$ . If $(x_{v}, y_{v}) \notin Forwarder (x_{u}, y_{u}, t)$ , we will show that $Nod e_{v}$ can also receive the EDM from $Nod e_{u}$ in the following.

Let $y_{temp} = y_{u} + t_{2} \times k$ and $| y_{v} - y_{temp} | \leq k$ .

Because $x_{u} - (t + 1) \times k < x_{v} < x_{u} + (t + 1) \times k$ , then $x_{temp} = \arg min_{x' \in {x | (x, y) \in Forwarder (x_{u}, y_{u}, t)}} {| x' - x_{v} |}$ , so $| x_{v} - x_{temp} | \leq k$ . Because $\sqrt{{(x_{v} - x_{temp})}^{2} + {(y_{v} - y_{temp})}^{2}} \leq k \sqrt{2}$ and $(x_{temp}, y_{temp}) \in Forwarder (x_{u}, y_{u}, t)$ , if the node at $(x_{temp}, y_{temp})$ forwards the EDM from $Nod e_{u}$ , then $Nod e_{v}$ can still receive the EDM.

From the above, $EDM s$ of any node can cover all its structuring neighbors.

B. Based on reliable communication links, DMOA can ensure that the correct and complete monitoring status of the structuring neighbors is transmitted to any node that detects an event

$Nod e_{u}$ should know its event-monitoring map after it detects an event $Even t_{i}$ . Suppose that $Nod e_{v}$ is a structuring neighbor of $Nod e_{u}$ . $Nod e_{v}$ will send out an EDM message when it detects $Even t_{i}$ . Because the structuring element is a square with the origin in its center and it is axisymmetric and centrosymmetric, $Nod e_{u}$ is also a structuring neighbor of $Nod e_{v}$ . Based on the conclusion in A, if the communication links are reliable, then $Nod e_{u}$ can receive the EDM of $Nod e_{v}$ and determine that $Nod e_{v}$ has detected $Even t_{i}$ . If $Nod e_{v}$ does not detect $Even t_{i}$ , it cannot generate and send an EDM. Then, $Nod e_{u}$ will not receive the EDM for $Even t_{i}$ from $Nod e_{v}$ , and it will believe that $Nod e_{v}$ does not detect $Even t_{i}$ . Thus, $Nod e_{u}$ can collect correct and complete monitoring statuses for structuring neighbors.

C. DMOA has low control overhead

The control overhead of the DMOA is mainly generated via EDM forwarding. Suppose that there are $N_{e}$ events and the average number of nodes in each event region is $N_{ea}$ . Based on section “Event information transmission”, a node sends its EDM message (counted as the first forwarding), and the size of the Forwarder set of the t-th forwarding is $4 (t - 1)$ . Therefore, the total number of the forwarding nodes is $1 + \sum_{i = 1}^{t} (i - 1) \times 4$ after the t -th forwarding. Because the size of the structuring element is $s \times s$ (s is odd) and the communication radius is $r = k \sqrt{2} a, k \leq (s - 1) / 2, k \in Z$ , the EDM message of a node should be forwarded by $⌈ (s - 1) / 2 k ⌉$ times to cover the whole structuring neighbor, and the number of forwardings of the EDM of a node is $1 + \sum_{i = 1}^{⌈ (s - 1) / 2 k ⌉} 4 (i - 1)$ . Thus, the total number of the EDM forwarding is $N_{e} N_{ea} (1 + \sum_{i = 1}^{⌈ (s - 1) / 2 k ⌉} 4 (i - 1))$ . Because the density a network is $1 / a^{2}$ , one forwarding of an EDM will lead the EDM to be sent to $π r^{2} / a^{2} = 2 π k^{2}$ nodes, and the total number of received $EDM s$ is $2 π k^{2} N_{e} N_{ea} (1 + \sum_{i = 1}^{⌈ (s - 1) / 2 k ⌉} 4 (i - 1))$ . Suppose that the energy consumption associated with forwarding and receiving one EDM is $e_{1}$ and $e_{2}$ , respectively. Then, the total control overhead on the event information transmission is $N_{e} N_{ea} (1 + \sum_{i = 1}^{⌈ (s - 1) / 2 k ⌉} 4 (i - 1)) (e_{1} + 2 π k^{2} e_{2})$ . Because the number of bytes of an EDM is low, the energy consumed for forwarding and receiving $EDM s$ is small. Thus, the control overhead of the DMOA is low.

D. DMOA is effective at energy conservation

To show the effectiveness of energy conservation, we estimate the number of backbone nodes for DMOA. To simplify the analysis, the shape of an event is assumed to be a convex polygon. Suppose that there is a minimum rectangle $R_{event}$ with length $l_{1}$ and width $l_{2}$ to cover all of the nodes in the event region. $Nod e_{u}$ is a node in the event region, and the corresponding minimum distances to the long side and wide side are $d_{1}$ and $d_{2}$ , respectively. Let $d = min {d_{1}, d_{2}}$ . $M (Nod e_{u})$ is the event-monitoring map of $Nod e_{u}$ , and the size of the structuring element S is $s \times s$ . If $d < (s - 1) a / 2$ , we can have $M (Nod e_{u}) \neq S$ , and $Nod e_{u}$ determines that it should be eroded. Thus, the number of remaining backbone nodes is less than or equal to $(l_{1} / a - s + 2) \times (l_{2} / a - s + 2)$ . From the above, with increment in s, the number of backbone nodes will decrease. Although the accuracy will decline, the energy spent on data transmission will also be reduced. With decrease in s, the number of backbone nodes will increase, which leads to a decrease in the energy consumption required for the data transmission and an increase in accuracy. Thus, the DMOA with a moderate structuring element can save energy effectively.

Experiments

To validate the effectiveness of the DMOA, we first perform experiments with different structuring element sizes and communication radiuses to show their influence on the control overhead of the DMOA. Then, we integrate our DMOA with three data collection algorithms, SPT,² MLA,¹⁶ and YEAST,⁵ and they are denoted as DMOA-SPT, DMOA-MLA, and DMOA-YEAST, respectively. We evaluate those algorithms according to the energy consumption and network lifetime with different node densities, transmission failures, time, and initial node energies. Finally, we verify the DMOA’s performance on backbone node mining and event region recovery under different structuring element sizes. We simulated the WSNs using MATLAB R2010b, and all of the experiments were executed on a PC with an Intel Xeon E3-1231 3.40 GHz CPU with 16 GB RAM.

The energy consumption model used in our experiments is the same as that in Heinzelman et al.³⁸ A node sends an l-bit message at a distance of d, and the energy cost is determined by equation (10)

\begin{matrix} E_{Tx} (l, d) & = E_{Tx - elec} (l) + E_{Tx - amp} (l, d) \\ = {\begin{matrix} l E_{elec} + l ε_{fs} d^{2} & d < d_{0} \\ l E_{elec} + l ε_{amp} d^{4} & d \geq d_{0} \end{matrix} \end{matrix}

(10)

When a node receives an l-bit message, the energy cost is calculated by equation (11)

E_{Rx} (l) = E_{Rx - elec} (l) = l E_{elec}

(11)

where $E_{elec}$ is the energy of the electronics, which depends on factors such as the modulation, digital coding, filtering, and spreading of the signal; $ε_{fs} d^{2}$ or $ε_{amp} d^{4}$ is the amplifier energy, which depends on the distance to the receiver. For the energy required for data aggregation, a node spends 5nJ/bit/signal.

We assume that the shape of the event regions is arbitrary and that the positions and start times are random. The main simulation parameters are listed in Table 1.

Table 1.

Simulation parameters.

Parameters	Value
Node interval a	2.5, 5, 7.5, 10, 12.5 (m)
Node number	$160 \times 160, 266 \times 266, 200 \times 200, 400 \times 400, 800 \times 800$
Sink position	(100.5, 100.5)
Coefficient of node communication radius r	1/2/3( $\times \sqrt{2} a m$ )
Size of structure element s	3/5/7
Packet size of EDM	400 bits
Packet size of data	2000 bits
Network monitoring time	10,000 min
Node number of event area	$\geq 7 \times 7$
Duration of event	50 min-400 min, Uniform Distribution
Number of concurrent	1–6
Transmission failure ratio	0, 5, 10, 15, 20 (%)
Energy model parameter $E_{elec}$	50 nJ/bit
Energy model parameter $ε_{fs}$	10 pJ/bit/m²
Energy model parameter $ε_{amp}$	0.0013 pJ/bit/m⁴
Energy for data aggregation $E_{DA}$	5 nJ/bit/signal

The performance assessments to be compared are listed as follows:

TEC: total energy consumption

EC-EDM: energy consumption of EDM

TN-S: total number of senders

TFDN: time of first died node

RP: recovery precision (ratio between the node number of the estimated event regions and that of the origin event regions)

Control overhead

To discuss the influence of the node communication radius r and the structuring element size s on the control overhead of the DMOA, the transmission energy consumed for the EDMs using different $r (1 / 2 / 3)$ and $s (3 / 5 / 7)$ is compared in Figure 8. Over time, the control overhead of the DMOA increases. At the same moment, the energy spent exchanging EDMs by the DMOA with $r = 2, s = 7$ is the largest, and the DMOA with $r = 1, s = 3$ obtains the smallest control overhead. Overall, the control overhead of the DMOA increases with increasing s, because increase in the number of structuring neighbors enlarges the transmission range of the EDM. Figure 8 shows that for the same s, the control overhead of the DMOA decreases as r increases except at $s = 7, r = 2$ . When $s = 7$ and $r = 2$ , the EDM message should be forwarded twice to cover the structuring neighbors, and the real range is wider than that of $r = 1$ and $r = 3$ ; thus, the energy consumption is the highest.

Figure 8.

Control overhead.

Network energy consumption

For DMOA-SPT, the DMOA is used first to erode nodes in event regions, and then the data sensed by the backbone nodes are transmitted and aggregated along the SPT created by the SPT algorithm. For DMOA-MLA, the backbone nodes in the event areas are mined by DMOA first, and their sensing data are processed by the method from the MLA algorithm. For DMOA-YEAST, the most correlated data are obtained by the DMOA, and they are aggregated and transmitted to the sink along the aggregation tree built by the YEAST algorithm.

Figure 9 shows a comparison of the TECs at different moments. The TEC of each algorithm increases approximately linearly over time, and the DMOA improves the performance of the other algorithms as the total energy consumption increases.

Figure 9.

Total energy consumption at different time.

Smaller values of a correspond to a greater density of the nodes in the network. Thus, to show the influence of the node density on the energy consumption, we perform experiments with different values of a. Figure 10 shows the results of the total energy consumption with different values of a at the 2000-th minute. With a larger value of a, the number of nodes in the event regions is reduced and the energy spent on data transmission would decrease. The DMOA can erode the nodes in the event border regions, which can help decrease the energy consumption with data transmission. Thus, as shown in Figure 10, the DMOA performs well regardless of the node density.

Figure 10.

Total energy consumption with varying a.

To verify the performance of the DMOA in WSNs with unreliable communication channels, we consider transmission failures in our experiments, and the results are shown in Figure 11. In these experiments, a reliable data transmission scheme is adopted when the nodes transmit the sensed data, and the event information exchange for the node erosion does not use a reliable data transmission method. With an increasing transmission failure ratio (TFR), the energy consumption of the SPT, MLA, and YEAST algorithms increases because of data retransmission, whereas the energy consumption of the other three algorithms decreases because a transmission failure can cause more nodes to be eroded by the DMOA. As the TFR value increases, the number of event backbone nodes determined by the DMOA decreases, which leads to less data transmission in the network. Compared to data retransmission, the decrease in the number of event backbone nodes plays a leading role, which decreases the energy consumption of the DMOA-SPT, DMOA-MLA and DMOA-YEAST (as shown in Figure 11).

Figure 11.

Total energy consumption with varying TFRs.

Time when the first node dies

Many parameters are used to measure the lifetime of WSNs. Because the network structure can destabilize after a node dies, we selected the time when the first node dies to measure the network lifetime.

Figure 12 shows the results about TFDN with different node initial energy. As the initial energy increases, the TFDN of those algorithms are lengthened, and especially DMOA is more significant in this point.

Figure 12.

Time at which the first node dies, with varying initial energies.

As a changes, we investigate the time at which the first node dies, and the results are shown in Figure 13. When a increases, the number of nodes in the event regions decreases, which leads to less data transmission in the network and prolongs the TFDN. Because the DMOA can further reduce the number of nodes that send data, it can lead to a longer TFDN, and this advantage is much more obvious with a smaller node density.

Figure 13.

Time at which the first node dies, with varying a a.

Although the communication links are unreliable, the DMOA can help the algorithms to lengthen the time at which the first node dies. In addition, with an increasing TFR, the TFDNs of the SPT, MLA, and YEAST shorten because of data retransmission, whereas the TFDNs of the DMOA-SPT, DMOA-MLA, and DMOA-YEAST lengthen because of the anabatic decrease in the event backbone nodes introduced by the DMOA as shown in Figure 14.

Figure 14.

Time at which the first node dies, with varying TFRs.

Number of transmission nodes

To clearly demonstrate the energy conservation of the DMOA, we conduct experiments to compare the total number of senders (TN-Ss) between the SPT and DMOA-SPT with different values of s at different moments, and the results are shown in Figure 15. As the network runs, the TN-Ss all increase, although the TN-Ss of DMOA_SPTs are always smaller than that of the SPT. Greater values of s correspond to a larger difference between SPT and DMOA_SPT and greater energy conservation of the DMOAs.

Figure 15.

Total number of senders.

Recovery accuracy

Based on the distribution of backbone nodes, the sink utilizes the dilation operation to recover the event regions. To respond more effectively for offline guiding, the approximate regions should be as close to the original regions as possible. In this subsection, the recovery accuracies at different moments of DMOAs with different values of s are presented in Figure 16. This figure shows that the recovery accuracy decreases with increase in s, although the accuracy changes are small over time. The average recovery accuracies for $s = 3$ , $s = 5$ , and $s = 7$ are 96.7%, 91.5%, and 85.2%, respectively, which show the effectiveness of the DMOA on region recovery.

Figure 16.

Recovery accuracy.

Node erosion and event region recovery

To further show the effectiveness of the DMOA, we extract the event distributions at the 4644-th and 6132-th minutes in the experiments, and the results are shown in Figure 17(a)–(c). The three subfigures correspond to the results with the structuring elements of size $3 \times 3$ , $5 \times 5$ , and $7 \times 7$ . Here, (a1) and (b1) of each subfigure show the node erosion situations of the event regions at the 4644-th and 6132-th minutes (the blue color denotes the eroded nodes, and the red color denotes the remaining event backbone nodes), and (a2) and (b2) of each subfigure show the recovery situations of the corresponding event regions. Based on Figure 17, as the size of the structuring element decreases, the recovery event regions become more similar to the original event regions because additional backbone nodes remain although the energy consumption of the data transmission increases. If the size of the structuring element increases, the difference between the recovery regions and original regions will increase, while the energy consumption of the data transmission will decrease because of fewer backbone nodes. (It should be noted that the core backbone nodes always remain.)

Figure 17.

Examples of erosion and recovery for event regions: (a) s = 3, (b) s = 5, and (c) s = 7.

Conclusion

The key mission of WSNs is sensory data collection. After an event occurs, the sensor nodes within the event border region sense more fluctuating data than the nodes within the event backbone region, and this discrepancy affects the conclusions on the whole event. To decrease the amount of data transmitted from the event border regions, a novel DMOA is proposed, and it is motivated by morphological erosion and dilation in digital image processing. This algorithm can extract event backbone nodes in a distributed manner and recover event regions rapidly. The DMOA takes the event monitoring of a uniform network as a binary image, which provides the possibility of applying distributed morphological operations. Each node determines its own structuring neighbors according to the structuring element and collects event monitoring information from its neighborhood using the constrained transmission of $EDM s$ at low cost. Then, the independent erosion operation is applied on each node, and the event backbone nodes are then obtained. In the DMOA, only the event backbone nodes can send their sensory data; thus, the amount of transmitted data is directly decreased and more accurate and correlated data are obtained for data aggregation. In addition, the sink can easily recover the event regions through the dilation operation, which benefits the offline work. The algorithm analysis and experiments show that the DMOA can lead to efficient energy conservation and effective recovery of the event regions.

However, the DMOA is designed for isomorphic WSNs. Researching on how to gain event backbone regions in a distributed manner with low cost for heterogeneous WSNs is one of our future goals.

Footnotes

Acknowledgements

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions.

Academic Editor: Fei Yu

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 was supported in part by the National Natural Science Foundation of China under grant no. 61602230, in part by the Key Scientific Research Project in Colleges and Universities of Henan Province under grant no. 16A520063 and 18A120002, in part by the Henan Province Education Department Cultivation Young Key Teachers under grant no. 2016GGJS-158, in part by the Henan Province Education Department Natural Science Foundation under grant no. 17A520044, and in part by High-level Talent Startup Foundation of Luoyang Institute of Science and Technology under grant no. 2015BZ01.

References

Rault

Bouabdallah

Challal

Energy efficiency in wireless sensor networks: a top-down survey. Comput Netw 2014; 67(4): 104–122.

Krishnamachari

Estrin

Wicker

. The impact of data aggregation in wireless sensor networks. In: Proceedings of the international conference on distributed computing systems, pp.575–578, http://www.cs.cornell.edu/~destrin/resources/conferences/2002july-Krishnamachari-Estrin-Impact.pdf

Ranjani

Krishnan

Thangaraj

. Achieving energy conservation by cluster based data aggregation in wireless sensor networks. Wireless Pers Commun 2013; 73(3): 731–751.

Villas

Guidoni

Boukerche

. A scalable and dynamic data aggregation aware routing protocol for wireless sensor networks. In: Proceedings of the international conference on modeling, analysis, and simulation of wireless and mobile systems, Bodrum, Turkey, 17–21 October 2010, pp.110–117. New York: ACM.

Villas

Boukerche

Oliveira

HABFD

. A spatial correlation aware algorithm to perform efficient data collection in wireless sensor networks. Ad Hoc Netw 2014; 12(1): 69–85.

Pan

. Constructing load-balanced data aggregation trees in probabilistic wireless sensor networks. IEEE T Parall Distr 2014; 25(7): 1681–1690.

Sutagundar

Manvi

SS.

Fish bone structure based data aggregation and routing in wireless sensor network: multi-agent based approach. Telecommun Syst 2014; 56(4): 493–508.

Wan

Zhang

Chen

On the construction of data aggregation tree with maximizing lifetime in large-scale wireless sensor networks. IEEE Sens J 2016; 16(20): 7433–7440.

Liu

Huang

. Energy-efficient tree-based cooperative data aggregation for wireless sensor networks. Int J Sens Netw 2013; 12(2): 65–75.

10.

Nguyen

Liu

Pham

. On maximizing the lifetime for data aggregation in wireless sensor networks using virtual data aggregation trees. Comput Netw 2016; 105: 99–110.

11.

Wang

Wei

Lightweight, latency-aware routing for data compression in wireless sensor networks with heterogeneous traffics. Wireless Commun Mobile Comput 2016; 16(9): 1035–1049.

12.

Aly

Kong

Soljanin

. Fountain codes based distributed storage algorithms for large scale wireless sensor networks. In: Proceedings of the information processing in sensor networks, St. Louis, MO, 22–24 April 2008, pp.171–182. New York: IEEE.

13.

Aly

Ali-Eldin

Poor

. A distributed data collection algorithm for wireless sensor networks with persistent storage nodes. In: Proceedings of the 4th IFIP international conference on new technologies, mobility and security, Paris, 7–10 February 2011, pp.1–5. New York: IEEE.

14.

Aly

Alghamdi

Salim

. Information gathering schemes for collaborative sensor devices. Proced Comput Sci 2014; 32: 1141–1146.

15.

Liu

An effective data collection algorithm for wireless sensor network. Computing 2013; 95(9): 723–738.

16.

Sinha

Lobiyal

DK.

A multi-level strategy for energy efficient data aggregation in wireless sensor networks. Wireless Pers Commun 2013; 72(2): 1513–1531.

17.

Liu

Jhang

Efficient distributed data scheduling algorithm for data aggregation in wireless sensor networks. Comput Netw 2014; 65: 73–83.

18.

Rout

Ghosh

SK.

Adaptive data aggregation and energy efficiency using network coding in a clustered wireless sensor network: an analytical approach. Comput Commun 2014; 40: 65–75.

19.

Liang

Temporal lossless and lossy compression in wireless sensor networks. ACM Tran Sens Netw 2016; 12(4): 1–35.

20.

Sheltami

Musaddiq

Shakshuki

Data compression techniques in wireless sensor networks. Future Gen Comput Syst 2016; 64: 151–162.

21.

Chen

Liu

Wang

. Data sorting-based adaptive spatial compression in wireless sensor networks. KSII Trans Internet Inform Syst 2016; 10(8): 3641–3655.

22.

Alsheikh

Lin

Niyato

. Rate-distortion balanced data compression for wireless sensor networks. IEEE Sens J 2016; 16(12): 5072–5083.

23.

Tan

Xiong

Data prediction, compression, and recovery in clustered wireless sensor networks for environmental monitoring applications. Inform Sciences 2016; 329: 800–818.

24.

Kim

Cho

Park

. Increasing network lifetime using data compression in wireless sensor networks with energy harvesting. Int J Distrib Sens Netw 2017; 13(1): 1–10.

25.

Chen

Wassell

IJ.

Optimized node selection for compressive sleeping wireless sensor networks. IEEE T Veh Tech 2015; 65(2): 827–836.

26.

Cheng

Zhang

. Energy-efficient node selection algorithms with correlation optimization in wireless sensor networks. Int J Distrib Sens Netw 2014; 2014(1): 1–14.

27.

Sandhya

Murugan

Devaraj

Selection of aggregator nodes and elimination of false data in wireless sensor networks. Wirel Netw 2015; 21(4): 1327–1341.

28.

Zhang

A self-adaptive sleep/wake-up scheduling approach for wireless sensor networks. IEEE T Cybern. Epub ahead of print 3 March 2017. DOI: 10.1109/TCYB.2017.2669996.

29.

Ahmed

Zou

Fareed

MMS

. Sleep-awake energy efficient distributed clustering algorithm for wireless sensor networks. Comput Electr Eng 2015; 56: 385–398.

30.

Wang

Energy-efficient node selection for target tracking in wireless sensor networks. Int J Distrib Sens Netw 2013; 2013(1): 127–137.

31.

Jiang

Yang

. An energy-efficient node selection algorithm in bearings-only target tracking sensor networks. Int J Distrib Sens Netw 2014; 2014(2): 1–12.

32.

Feng

Zhao

Lian

Efficient and adaptive node selection for target tracking in wireless sensor network. J Sens 2015; 2016: 1–9.

33.

Shi

Wei

Wang

. A novel energy efficient topology control scheme based on a coverage-preserving and sleep scheduling model for sensor networks. Sensors 2016; 16(10): 1–26.

34.

Zebbane

Chenait

Badache

A group-based energy-saving algorithm for sleep/wake scheduling and topology control in wireless sensor networks. Wireless Pers Commun 2015; 84(2): 959–983.

35.

Nasridinov

Ihm

Park

YH.

Skyline-based aggregator node selection in wireless sensor networks. Int J Distrib Sens Netw 2013; 2013(5): 1172–1175.

36.

Gonzalez

Woods

Eddins

SL.

Digital image processing using MATLAB. Beijing, China: Publishing House of Electronics Industry, 2005.

37.

Yue

Zhang

Xiao

. Structure-free and dynamic-adaptive data fusion algorithm for wireless sensor networks. J Commun 2012; 33(9): 53–65.

38.

Heinzelman

Chandrakasan

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks. IEEE T Wirel Commun 2002; 1(4): 660–670.

Distributed and morphological operation-based data collection algorithm

Abstract

Keywords

Introduction

Related works

Background and motivation

Morphological operations

Research motivation

Proposed algorithm

Determination about border and backbone nodes

Structuring neighbors

Event information transmission

Event backbone node acquisition

Event region recovery

DMOA

Theoretical analysis and experiments

Theoretical analysis

A. Based on reliable communication links, Algorithm 2 of the DMOA can transmit the EDM s of any node to its structuring neighbors

B. Based on reliable communication links, DMOA can ensure that the correct and complete monitoring status of the structuring neighbors is transmitted to any node that detects an event

C. DMOA has low control overhead

D. DMOA is effective at energy conservation

Experiments

Control overhead

Network energy consumption

Time when the first node dies

Number of transmission nodes

Recovery accuracy

Node erosion and event region recovery

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

References

A. Based on reliable communication links, Algorithm 2 of the DMOA can transmit the $EDM s$ of any node to its structuring neighbors