A Distributed Collision-Free Data Aggregation Scheme for wireless sensor network

Abstract

Due to the advantages of large-scale, data-centric and wide application, wireless sensor networks have been widely used in nowadays society. From the physical layer to the application layer, the multiply increasing information makes the data aggregation technology particularly important for wireless sensor network. Data aggregation technology can extract useful information from the network and reduce the network load, but will increase the network delay. The non-exchangeable feature of the battery of sensor nodes makes the researches on the battery power saving and lifetime extension be carried out extensively. Aiming at the delay problem caused by sleeping mechanism used for energy saving, a Distributed Collision-Free Data Aggregation Scheme is proposed in this article to make the network aggregate data without conflicts during the working states periodically changing so as to save the limited energy and reduce the network delay at the same time. Simulation results verify the better aggregating performance of Distributed Collision-Free Data Aggregation Scheme than other traditional data aggregation mechanisms.

Keywords

Data aggregation collision-free time delay aggregation latency wireless sensor network

Introduction

Wireless sensor network (WSN) consists of a numerous sensor nodes to form a multi-hop ad hoc network system in a self-organized manner.¹ WSN has very widespread applications, which can achieve real-time monitoring of the battlefield, targeting the target, monitoring crop irrigation, and so on.² For the most practical large-scale applications, the sensors may be thrown by airplanes in special environments.³ Considering the requirements of large quantities, low cost, and wide distribution area, it is impossible to replace the battery of the node artificially,⁴ so the problem of energy efficiency of great importance in WSN. How to use energy efficiently to maximize the lifetime is a top challenge for WSNs.

In the working process, the nodes will sense and receive a variety of information. The amount of data to be analyzed will increase in stages and also face data fusion problems with various heterogeneous networks or systems.⁵ Therefore, collision-free and efficient data aggregation mechanism is an indispensable part for WSN. The duration it takes to aggregate information from the sensor node to the sink node is called the data aggregation latency.⁶ It is a critical step in minimizing the data aggregation latency throughout the network’s work. The collision-free data transmission between nodes is the basis for reducing the data aggregation delay. Collision-free can ensure an unblocked communication channel, increase the efficiency, and save energy so that the delay of the data aggregation will be decreased. Searching for the fastest collision-free scheduling (FCFS) has raised the concern of people. When a sensor node simultaneously listens to signals from different transmitters, the collision will occur due to interference between the signals.⁷ At this time, the sensor node cannot receive any signals, so the sender should send a signal packet to other nodes instead of sending a signal directly.⁸ The retransmission of data packets will not only increase conflict probability but also lead to a large amount of energy consumption and time delay.⁹ Therefore, a mechanism to minimize the delay without conflicts is the key to solve the FCFS problem.

In addition, the battery of the sensor node cannot be changed artificially, so how to reduce the consumption of energy has also become a key problem in WSNs.¹⁰ Many methods to save energy by periodically switching the working states have been proposed recently, most of which will use a short period of time in the positive state to receive or transmit information and the rest of the time to sleep so as to save energy in each working period (WP).¹¹ However, it can exert a sleep waiting time in this way, that is, when the transmitter sends the data to the receiver, it needs to wait until the receiver’s state is positive, which will inevitably lead to network delay.¹²

From the above, it is necessary to reduce the delay caused by work states converting conflicts so as to solve the problem of FCFS and save the energy of the network. The main contributions of this article include in following:

Some equations and models are given for the proposed scheme.

Proposing a two main parts Distributed Collision-Free Data Aggregation Scheme (DCF-DAS): DAT (Date Aggregation Tree) to minimize the data aggregation by controlling the number of the node’s child node and FCFS is designed to reduce the WP of the node required for data aggregation and save the power of the node.

We do a mass of simulations to verify the correctness of the mechanism. The results show that DCF-DAS is superior to the classical improved data aggregation scheduling (IAS) and scheduling algorithm (SA) in time delay.

The rest of the article is organized as follows. We present the related work in section “Related work.” Section “Preliminaries” introduces the model of network, delay, conflict, and formulation. Our scheme DCF-DAS is proposed in section “Proposed DCF-DAS.” In section “Simulation analysis,” simulation results are analyzed to evaluate the DCF-DAS. Finally, we conclude this article in section “Conclusion.”

Related work

Data aggregation plays a significant role in WSNs, and the problem of minimizing the delay in this technique is NP-hard and many researches contribute to solve this problem. Yu and Li¹³ analyze the time cost that complete the aggregation in SA, and the algorithm shows that the time required is not lager than $T (15 R (G, s) + Δ - 3)$ time units, where T is the constant time units in every WP and $R (G, s)$ is the transmission range of node s in the network graph G. In Sarkar et al.,¹⁴ ARS (Action and Relay Station) line scheduling algorithm is proposed to manage data by cluster nodes collecting the data from different neighbor nodes and then transmit the aggregated data to the sink node. The disadvantages of this scheme are suit for low-consuming nodes only and conflict may be occurred during the transmission. A Dynamic Conflict-free Query Scheduling (DCQS) is proposed in Chipara et al.¹⁵ for query services; the Conflict-free scheme can adapt the changes of the workload and it can provide predictable performance when the query rate is maximal. But this approach can only work in homogeneous network. A practical idea in Abdulsalam et al.¹⁶ uses the aggregation algorithm based on LEACH into air quality monitoring so that it extends the lifetime of the network. Ukil¹⁷ proposed a privacy-preserving data aggregation framework to resist the certain type attack to ensure the security of the network. A compressed sensing (CS) data aggregation scheme is proposed by Xiang et al.¹⁸ to increase energy efficiency and achieve recovery fidelity. In Shu et al.,¹⁹ some main topics about data fusion and distributed intelligence for sensor systems are revealed in the article.

Preliminaries

Network model

Assuming the node set $V = {v_{1}, v_{2}, \dots, v_{n}}$ and edge set $E = {e_{1}, e_{2}, \dots, e_{m}}$ , when there is some kind of relationship R make $V \times V \to E$ , which means that every two nodes in set V can be trained into a line in set E, the node sets V and edge sets E make up a graph $G = (V, E)$ .²⁰ The relationship R is for each edge $e_{k}$ , and there is a corresponding node-pair $(v_{i}, v_{j})$ . The node set V in graph G can be given arbitrarily, while the edge set E only represents the binary relationship in V. As Figure 1 shows, in graph G, there are four nodes v₁, v₂, v₃, and v₄ and six edges e₁, e₂, e₃, e₄, e₅, and e₆. So the node set of graph G is $G = (V, E)$ and the edge set is $E = (e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6})$ . Edge e₁ connect the nodes v₁ and v₂, and nodes v₃ and v₄ are connected to v₁ by edges e₂ and e₆, respectively. In the same way, the nodes v₂, v₃, and v₄ are also connected to three other nodes by one edge $e_{k}$ , so $V \times V \to E$ can be satisfied and sets V and E make up the graph $G = (V, E)$ , which is shown in Figure 1. In our network model, the transmission radius of all nodes is set to R, and any two nodes $v_{1}, v_{2} \in V$ can communicate on the premise of $| v_{1} - v_{2} | \leq R$ , where $| v_{1} - v_{2} |$ is the distance between nodes $v_{1}$ and $v_{2}$ .

Figure 1.

Node v and edge e in graph G.

In the data aggregation mechanism proposed in this article, the lifetimes of all sensor nodes are divided into several equal periods. Each time period is called a WP, and each WP is divided into a number of fixed time slots (TS). The sensor node can randomly select one of the TS as its working TS, and the remaining in the same WP as the sleeping TS. For the sake of explaining the conflict avoidance, the case of receiving one packet in one working TS is considered. Nodes can send data packets to their parent nodes in any working TS, but can only receive data packet from its child nodes in the randomly selected working TS. The same TS cannot be used to send and receive simultaneously. In the whole network, all the nodes can aggregate different data packets received from their child nodes into one packet and then send it to their parent nodes. After the sink node receives the necessary data in the network, the data aggregation is achieved. An example is shown as Figure 2.

Figure 2.

Time slot division of sensor nodes.

Figure 2 shows the WP and TS assignment of nodes u and v, where there is $TS = 6$ for both. Actually, the lifetime of these two nodes is divided into a number of equal WPs, and Figure 1 only shows the first two segments. Nodes u and v randomly select TS4 and TS2 as the working slot, respectively, as the orange color TS shown in Figure 2. Node u in TS4 can receive the signal packets from its child nodes, and then aggregate the data, u can also send data in every TS from TS1 to TS6. In each WP, all six TS can send the data packets, but cannot receive and send data packet at the same TS. The explanation above also applies to node v.

Delay model

The time delay required for data to be transmitted from sensor node v to sink node s is called the end-to-end delay of node v, noted as $E 2 E (v)$ . Before computing $E 2 E (v)$ , the sleep latency $W_{t} (v, u)$ between sender v and its parent node u should be calculated first. Since the working TS are selected randomly, the sender may need to wait until the receiver wakes up before sending the data packet. The waiting time during this period is called sleep latency. The sleep latency $W_{t} (v, u)$ between v and u can be obtained as in equation (1)

W_{t} (v, u) = {\begin{matrix} ts (u) - ts (v), & ts (u) > ts (v) \\ ts (u) + TS - ts (v), & ts (u) \leq ts (v) \end{matrix}

(1)

where $ts (u)$ and $ts (v)$ are the working TS selected by nodes u and v, respectively. In the case shown in Figure 1, $ts (u) = 4$ , $ts (v) = 2$ , and $TS = 6$ . Considering there are no attacks and interference in the network, the end-to-end delay of node v can be expressed as in equation (2)

{\begin{matrix} E 2 E (s) = 0 \\ E 2 E (v) = E 2 E (u) + W_{t} (v, u) \end{matrix}

(2)

where in the data aggregation tree (DAT), node v’s parent node is node u.

Conflict model and conflict set

Conflict model

Assuming that the transmitting radius is R and the interfering radius is R′ for sensor nodes. There is $R \leq R'$ for usual, but $R = R'$ in this article for simplicity. Since the nodes can neither send nor receive data at the selected TS in each WP, two kinds of conflict models are defined in the conflict-free data aggregation scheme as primary conflict model and secondary conflict model as shown in Figure 3.

Figure 3.

Two conflict models in the conflict-free data aggregation scheme: (a) primary collision model and (b) secondary collision model.

In the primary collision model as shown in Figure 3(a), the transmission range of all nodes denoted by R and node y lies both in the communication radius of node x and node z. If x and z send data to node y in the same WP, node y cannot receive any data from x or z because y has only one working TS in a WP. $x \to y$ and $z \to y$ are two conflicting aggregation links in primary collision. Figure 3(b) is the secondary conflict model, node y lies in the communication radius of nodes x and m, node n in the range of m. Supposing there are two communication links as $x \to y$ and $m \to n$ , there will be $ts (y) = ts (n)$ . When x and m send data in the same WP, two links clash. Because nodes y and n are both in the radius of m, y can receive the broadcast of m and x in the same WP. But actually, m wants to send data to n rather than y, node y wants to receive data from node x instead of m. So links $x \to y$ and $m \to n$ are conflicting in this situation.

From above, it can be seen that the condition that v and u can transmit data successfully should satisfy the following two points: (1) $| v - u | \leq R$ and (2) node x existing in the network does not perform any data transmission, where x satisfies $| x - u | \leq R$ , $ts (y) = ts (u)$ , and node y is the intended receiver of node x.

Conflict set

In order to avoid the conflicts mentioned above during the process of data aggregation, each sensor node can define its own conflict set. During aggregation, for each node, it should be ensured that the communication link does not conflict with the link of the node in its conflict set when sending data packet to their parent node. With the aggregation process carrying forward, the conflict set of a node will also be constantly updated. As long as there is a node to satisfy any one of the following three conditions of some other node a, the node will be included in the conflict set of node a, which can be called $SCon (a)$ . $p (a)$ represents the parent node of a. Figure 3 simply depicts the conflict set of a node and colors the nodes with the same working TS:

Condition 1. It is the child node of node $p (a)$ (except a). Reason: The working TS of $p (a)$ is unique, so it is impossible to use the same WP to receive multi-child nodes’ data packets in the same TS. Nodes $c_{1}$ , $c_{2}$ , and $c_{3}$ in Figure 4(a) are the conflict nodes of node a.

Condition 2. It is the child of a’s neighbor node b, where node b satisfies $ts (b) = ts (p (a))$ . Reason: When a sends data to $p (a)$ , the child of node b will also send data to b in the same WP. Due to $ts (b) = ts (p (a))$ , the content sent by a may be received by b so that b will not receive data from its child nodes. Nodes $c_{1}$ and $c_{2}$ in Figure 4(b) are the conflict nodes of node a.

Condition 3. It is $p (a)$ ’s neighbor node x, where node x satisfies $ts (p (x)) = ts (p (a))$ . Reason: In the same WP, when a sends data to $p (a)$ , x will also send data to $p (x)$ . As there is $ts (p (x)) = ts (p (a))$ , the data sent by node x may be received by $p (a)$ mistakenly, and the data of node a will not be transmitted to $p (a)$ . Node x in Figure 4(c) is the conflict node of a.

Figure 4.

The conflict set of one node.

Figure 5 illustrates the node’s conflict set. The conflict nodes of $v_{8}$ corresponding to the above three conditions are $v_{9}$ , $v_{7}$ , and $v_{5}$ , respectively. $v_{4}$ is the parent node of $v_{8}$ , and $v_{4}$ ’s another child node is $v_{9}$ except node $v_{8}$ , that is, $v_{9}$ is the conflict node which satisfies Condition 1. In Figure 5, the neighbor nodes of $v_{8}$ are $v_{6}$ and $v_{9}$ , while the child nodes are $v_{7}$ and v₁₁, respectively. Node $v_{7}$ meets Condition 2 because there is $ts (v_{9}) \neq ts (v_{4})$ and $v_{7}$ is the conflict node of $v_{8}$ . Since the neighbor nodes of $v_{4}$ are v₅ and v₆, two nodes may become conflict nodes of $v_{8}$ . Node $v_{1}$ is $v_{6}$ ’s parent node, and node $v_{6}$ is excluded since $ts (v_{1}) \neq ts (v_{4})$ . So $v_{5}$ is the conflict node of $v_{8}$ which meets Conditions 3. It is known from above that the conflict set ${Con (v_{8})}$ of node $v_{8}$ is ${v_{9}, v_{7}, v_{5}}$ .

Figure 5.

The conflict set of nodes.

Problem formulation model

Assuming $V = {v_{1}, v_{2}, v_{3}, \dots, v_{α}}$ is the child nodes set of $u_{q}$ in WSN, and all child nodes will transmit their perceived information to their parent nodes. The number of packets received by the node $u_{q}$ is represented as $D_{u_{q}}$ , which is shown as equation (3)

D u_{q} = \sum_{i = 1}^{b} d_{i} + \sum_{j = 1}^{c} d_{j} + \dots + \sum_{n = 1}^{m} d_{α}

(3)

where $b, c, \dots, m$ represent the number of packets of node $v_{1}, v_{2}, v_{3}, \dots, v_{α}$ , respectively. Then, the total number of packets received by all the parent nodes in the network $\sum_{q = 1}^{k} u_{q}$ is given by equation (4)

\sum_{q = 1}^{k} D u_{q} = \sum_{q = 1}^{k} (\sum_{i = 1}^{b} d_{i} + \sum_{j = 1}^{c} d_{j} + \dots + \sum_{n = 1}^{m} d_{n})

(4)

To avoid conflicts, the parent node only allows receiving the data packet from only one child node in one WP. Then equations (5) and (6) will be obtained from equations (3) and (4)

D u_{q} = d_{1} + d_{2} + \dots + d_{α}

(5)

\sum_{q = 1}^{k} D u_{q} = \sum_{q = 1}^{k} (d_{1} + d_{2} + \dots + d_{α})

(6)

where $d_{1}, d_{2}, \dots, d_{α}$ represent the number of packets of nodes $v_{1}, v_{2}, v_{3}, \dots, v_{α}$ , respectively.

Let $S_{i}$ denote the set of nodes sending the packets with no conflict during the ith duty cycle. In the network with graph $G = (V, E)$ , assuming s is the sink node and N is the data aggregation delay (all data packets are transmitted to the sink node within N WPs), there will be

{\begin{matrix} S = V \ {s} = ⋃_{i = 1}^{N} S_{i} \\ S_{i} ⋂ S_{j} = Ø, \forall i \neq j \end{matrix}

(7)

In this article, a collision-free data aggregation mechanism is designed, in which the data collected by the sensor nodes is delivered to the sink nodes as fast as possible without any conflict, that is, the value of N is minimized by the data aggregation scheme.

Proposed DCF-DAS

The realization of the proposed DCF-DAS is mainly divided into two parts. (1) Establishment of DAT. During the data tree establishment, each parent node must wait until all the packets from the child nodes are collected before performing data aggregation. The larger the number of child nodes is, the longer the aggregation delay will be. Limiting the number of child nodes can effectively reduce the parent node data aggregation time. Therefore, in the establishment of data tree, a threshold k is preset for the environment, and the maximum number of child nodes owned by each parent node is adopted to control the number of child nodes so as to reduce the aggregation delay. When some special cases occur, like fewer nodes in the network or low node density, little number of child nodes are allowed to the maximum number of child node exceed to the value of k, but the number of parent nodes of such child nodes is required to be minimized. (2) Establishment of FCFS. After the DAT being established, an FCFS is proposed, by which the node will select the WP to send the data packet to its parent node according to the data aggregation algorithm, making all the data packets can be sent to the sink node without any conflict.

Establishment of DAT

It is necessary to consider that multiple nodes transmit data without conflict in the same WP to reduce the data aggregation delay. The more nodes there are with child nodes in the network, the longer time the data aggregation will require. Energy plays a crucial factor affecting the network lifetime, since changing the batteries of the nodes in WSN is impossible. In order to save the energy consuming of the entire network, the nodes will periodically change the working states. The nodes randomly select a time slot within each WP as their own working slot and the rest of the time into sleeping state (as mentioned in section “Network model”), which can effectively avoid the energy consumption that is caused by the state in working for a long time. On the contrary, it may extend the WP of the node to collect the data from all its child nodes in high network density. Therefore, the establishment process of DAT should take full account of the delay generated by the nodes with multi-child nodes.

Accordingly, the following theorem exists: Given a DAT, in the collision-free data aggregation mechanism, the value of the data time delay N is not less than the maximum number of one node’s child nodes number in the network. That is $N \geq max {ζ_{i} | i = 1, 2, \dots, n}$ , where $ζ_{i}$ refers to the number of node i’s child node in the DAT. Main proof procedure is as follows: suppose that q is the node with the largest number of child nodes. At least two child nodes of q will send data packets in the same WP if there is $N \geq max {ζ_{i} | i = 1, 2, \dots, n}$ , which will violate the principle of collision-free mechanism. $N \geq max {ζ_{i} | i = 1, 2, \dots, n}$ cannot be true, so there is $N \geq max {ζ_{i} | i = 1, 2, \dots, n}$ . It can be concluded that the minimum value of N depends on the maximum number of child nodes. To minimize N, the number of child nodes owned by one parent node should be as small as possible. Therefore, a preset threshold k is used in DAT establishment to limit the number of child nodes so as to reduce the delay.

Main variables during the establishment of DAT are listed in Table 1:

Table 1.

Variables and explanations.

Notation	Definition	Notation	Definition
$n_{n} (u)$	Number of neighbor nodes of u	$SA (u)$	Set of catalytic nodes of u
$n_{ch} (u)$	Number of child nodes of u	$sta (u)$	State of u
$SCh (u)$	Set of child nodes of u	Special	One label of u
$n_{cp} (u)$	Number of parent candidates of u	Normal	Another label of u

In Table 1, $n_{cp} (u)$ is the number of parent candidates which can be selected by node u. Node v being a candidate parent node of u must satisfy two conditions: (1) v is not the child node of u and (2) number of child nodes of u is less than threshold k. $A (u)$ is the catalytic node of u, which is selected from the child node of u to continue the establishment process of the DAT. $sta (u)$ is the state of u, including WAIT, ACTIVATED, LISTEN and COMPLETE. Special and Normal are two labels of node u. The label of the node is set as Special at $n_{cp} (u) = 1$ , noted as $lab (u) = Special$ . In the same way, the label of node is set to Normal when there is $n_{cp} (u) > 1$ , and it can be expressed as $lab (u) = Normal$ .

The establishment of DAT is divided into the Start-up stage and the Main stage. In the Start-up stage, nodes can be divided into two categories: Special and Normal. A Special node looks for its only parent node. In the Start-up stage, the Normal node may also be transformed to be a Special node. The Start-up stage ends when there is no Special node in the current network, and then the Main stage is executed. In the Main stage, the sink node is set as the first catalytic node, which can find its own child nodes to continue the DAT establishment. When a node cannot find any more child nodes, it will send a TRA (TRAPPED) message to its parent node. The Main stage ends when all child nodes of sink node s send TRA messages to s, and then the DAT has been established.

The pseudocode of Start-up stage is shown as follows:

Algorithm 1.

Process of Start-up stage
Start-up stage
Initialization: $n_{ch} (u) = 0$ , $n_{pc} (u) = n_{n} (u)$ , $SA (u) = Ø$ , $SCh (u) = Ø$ , $sta (u) = WAIT$ , $\forall u \in V$ 1. for each node v in the network do 2. if $n_{pc} (v) = 1$ then{ 3. $lab (v) = Special$ 4. v sends a ASK-JOIN message to its unique neighbor 5. ifu receives ASK-JOIN from vthen 6. $n_{ch} (u) = n_{ch} (u) + 1$ ; $n_{pc} (u) = n_{pc} (u) - 1$ ; $SCh (u) = SCh (u) \cup v$ 7. u sends a ACC-JOIN message to its one-hop neighbors 8. end if 9. ifv receives ACC-JOIN from uthen 10. $p (v) = u$ , $sta (u) = WAIT$ 11. other neighbors i of u do $n_{pc} (i) - 1$ if $n_{ch} (u) > k$ 12. end if 13. }else $lab (v) = Normal$ 14. end for

Process of Start-up stage

Start-up stage

Initialization:

n_{ch} (u) = 0

n_{pc} (u) = n_{n} (u)

SA (u) = Ø

SCh (u) = Ø

sta (u) = WAIT

\forall u \in V

1. for each node v in the network do
2. if

n_{pc} (v) = 1

then{
3. $lab (v) = Special$
4. v sends a ASK-JOIN message to its unique neighbor
5. ifu receives ASK-JOIN from vthen
6.

n_{ch} (u) = n_{ch} (u) + 1

;

n_{pc} (u) = n_{pc} (u) - 1

;

SCh (u) = SCh (u) \cup v

7. u sends a ACC-JOIN message to its one-hop neighbors
8. end if
9. ifv receives ACC-JOIN from uthen
10.

p (v) = u

sta (u) = WAIT

11. other neighbors i of u do

n_{pc} (i) - 1

n_{ch} (u) > k

12. end if
13. }else

lab (v) = Normal

14. end for

The details of the Start-up stage are shown as follows. All nodes should be initialized at first. As the DAT has not been formed yet, the node may not find any parent node in DAT. So, u does not have any child node and the number of candidate parent and neighbor node of u are same, that is, $n_{ch} (u) = 0$ , $n_{pc} (u) = n_{n} (u)$ . The status of the node is WAIT. For all nodes existing in the network, if the node’s candidate parent node is unique, the node’s label is Special, otherwise is Normal. Special node v first sends a join request ASK-JOIN (ask to join) message to the only alternative neighbor node. If node u receives the request, the number of node u’s child nodes will increase by 1, and v is included in u’s child nodes set SCh(u). Since v cannot be the parent node of u, the number of $n_{pc} (u)$ will be reduced by 1. At this time, node u sends an accept join message ACC-JOIN (accept to join) to its neighbor nodes. If node v receives the ACC-JOIN from u, v sets u as its own parent node and v’s state is still WAIT. When there is the number of u’s child node more than k, the other neighbor node i of u except v will reduce the number of candidate parent of i by 1 because u can no longer be its parent node. As long as there is Special node in the network, the above steps are repeated.

Data aggregation enters the Main stage when there is not any Special node in the current network. The pseudocode of Main phase is shown as follows.

Algorithm 2.

Process of Main stage
Main stage
1. if sink s has $n_{ch} (s) = n_{n} (s)$ then 2. return 3. else 4. s becomes the first catalyst: $sta (s) = ACTIVATED$ 5. while $sta (s)! = COMPLTE$ do 6. for each activator u $(sta (u) = ACTIVATED)$ do 7. u sends a ACC-JOIN message to its one-hop neighbors (except the node who $lab (v) = Special$ in Start_up Stage) 8. for each neighbor node v of node u in WAIT state upon received CH_FIND do 9. v sends ASK_JOIN to u 10. end for 11. for each u received ASK_JOIN from vdo 12. if $lab (v) = Normal$ then 13. u set $t (u, v) = d (u) + sl (u, v) + rand (0, 1) + (n_{ch} (v) * T)$ 14. if $lab (v) = Special$ then 15. u set $t (u, v) = 0$ 16. u hang onto the backoff times for other neighbors 17. for each $lab (v) = Normal$ then 18. ifu receives CON_JOIN of v for another catalyst z when $t (u, v)$ has not expired then 19. u recalls $t (u, v)$ 20. elseu executes Procedure 1 21. end for 22. end for 23. for each v in WAIT received ACC_JOIN from udo 24. $p (v) = u$ , $d (v) = d (u) + sl (u, v)$ 25. v sends a CON_JOIN message to its one-hop neighbors 26. if $lab (v) = Special$ then 27. $sta (v) = COMPLETE$ 28 if $lab (v) = Normal$ then 29. $sta (v) = ACTIVATED$ 30. end for 31. for each neighbor i of u in WAIT (except v) according to the CON_JOIN do 32: if $n_{ch} (u) \geq k$ then 33. $n_{pc} (i) = n_{pc} (i) - 1 s$ 34. if $n_{pc} (i) = 1$ then 35. $lab (i) = Special$ 36. i return Start_up Stage line 4 37. end for 38. end for 39. for each u cannot find any new catalyst then 40. u sends a TRA message to p(u) 41. $sta (u) = COMPLETE$ 42. end for 43. for each node u in LISTIN or sink s, according to TRA from all SA(u) do 44. u executes Procedure 2 45. end for 46. end while

Process of Main stage

Main stage

1. if sink s has

n_{ch} (s) = n_{n} (s)

then
2. return
3. else
4. s becomes the first catalyst:

sta (s) = ACTIVATED

5. while

sta (s)! = COMPLTE

do
6. for each activator u

(sta (u) = ACTIVATED)

do
7. u sends a ACC-JOIN message to its one-hop neighbors (except the node who

lab (v) = Special

in Start_up Stage)
8. for each neighbor node v of node u in WAIT state upon received CH_FIND do
9. v sends ASK_JOIN to u
10. end for
11. for each u received ASK_JOIN from vdo
12. if

lab (v) = Normal

then
13. u set

t (u, v) = d (u) + sl (u, v) + rand (0, 1) + (n_{ch} (v) * T)

14. if

lab (v) = Special

then
15. u set

t (u, v) = 0

16. u hang onto the backoff times for other neighbors
17. for each

lab (v) = Normal

then
18. ifu receives CON_JOIN of v for another catalyst z when

t (u, v)

has not expired then
19. u recalls

t (u, v)

20. elseu executes Procedure 1
21. end for
22. end for
23. for each v in WAIT received ACC_JOIN from udo
24.

p (v) = u

d (v) = d (u) + sl (u, v)

25. v sends a CON_JOIN message to its one-hop neighbors
26. if

lab (v) = Special

then
27.

sta (v) = COMPLETE

28 if

lab (v) = Normal

then
29.

sta (v) = ACTIVATED

30. end for
31. for each neighbor i of u in WAIT (except v) according to the CON_JOIN do
32: if

n_{ch} (u) \geq k

then
33.

n_{pc} (i) = n_{pc} (i) - 1 s

34. if

n_{pc} (i) = 1

then
35.

lab (i) = Special

36. i return Start_up Stage line 4
37. end for
38. end for
39. for each u cannot find any new catalyst then
40. u sends a TRA message to p(u)
41.

sta (u) = COMPLETE

42. end for
43. for each node u in LISTIN or sink s, according to TRA from all SA(u) do
44. u executes Procedure 2
45. end for
46. end while

When the number of child nodes of the sink node is equal to the number of its neighbors, DAT has already been formed in the Start-up stage. Otherwise, the following steps will be taken: The sink node becomes the first catalytic node in the network and begins to search for its own child node, and the state of the sink node changes from WAIT to ACTIVATED. When the state of the sink node is not COMPLETE, the catalytic node u sends a CH-FIND message (find the child node) to its one-hop neighbor except for those nodes that have been selected u as their parent node in the Start-up stage. Each neighbor node v receiving the CH-FIND message will send an ASK-JOIN message to node u, in order to notify u that v wants to be u’s child node. After receiving the ASK-JOIN message from one or more neighbor nodes successfully, u will set a backoff time $t (u, v)$ back. The backoff time is 0 for Special node, since the Special node’s parent node candidate is unique. The value of $t (u, v)$ for Normal node consists of the end-to-end delay from v to u, the current number of child node of v, and a random number between 0 and 1. The value of $t (u, v)$ is increased with the increase of time delay of data transmitted from v to sink node s when u is the parent node of v. The randomness is the gist to estimate different backoffs when the sum of end-to-end delay and the number of child nodes are the same. Before the value of $t (u, v)$ falling down to 0, if node u receives the CON-JOIN message (confirming join) from node v, u will cancel the backoff time for v. The CON-JOIN message sent by node v refers to that v determines to select other nodes rather than u as its parent nodes in backoff time $t (u, v)$ . The reason for this condition may be there are other nodes also set a backoff time to v and it shorter than $t (u, v)$ . When $t (u, v)$ expired and u has not yet received the CON-JOIN message from v, node u will take v as its child node, then u will perform the following Procedure 1.

The pseudocode of Procedure 1 is shown as follows.

Algorithm 3.

Pseudocode of procedure 1
Procedure 1
1. $SCh (u) = SCh (u) \cup v$ ; $n_{ch} (u) = n_{ch} (u) + 1$ 2. u sends a ACC_ JOIN message to its one-hop neighbors (except the node who lab(v) = special) 3. $SA (u) = SA (u) \cup v$ 4. if $n_{ch} (u) < k$ then 5. u hang onto the backoff times for other neighbors 6. if $n_{ch} (u) \geq k$ then 7. u recalls the backoff times for other neighbors 8. $sta (u) = LISTEN$

Procedure 1 shows the procedure that node u takes node v into its own child nodes set $SCh (u)$ , then adds the number of its child node by one and sends an ACC-JOIN message to its one-hop neighbors, telling them that v has become its child node and includes v into its catalysis nodes set $SA (u)$ . In this case, if the number of child nodes of node u is less than k, u continues the settings of $t (u, v)$ for other neighbors; otherwise, u withdraws the remaining ones and the state of u is converted from ACTIVATED to LISTEN.

When v receives an ACC-JOIN from u, v will confirm u as its parent node and sends a confirm join message CON-JOIN to its one-hop neighbor. If the label of v is Special before being added to the DAT, the state of v is converted to COMPLETE; otherwise, it is converted to ACTIVATED to continue searching for its child node. Another neighbor node i of node u in the state WAIT will judge the value of the number of child nodes of node u $n_{ch} (u)$ according to the ACC-JOIN sent by u, the value of the number of candidate parent nodes of i minus 1 if $n_{ch} (u)$ is greater or equal to k. If $n_{pc} (i)$ is equal to 1 at this moment, the node i’s label will turn to Special and node i will execute from line 4 in Start-up Stage. For all nodes in the network, it will send a TRA message to its parent node and the status will be changed into COMPLETE if the node can no longer find any catalytic nodes. When node u in network with the status of LISTEN receives the TRA from all the catalytic nodes, node u will execute Procedure 2.

The pseudocode for Procedure 2 is shown as follows.

Algorithm 4.

Pseudocode of procedure 2
Procedure 2
1. u sends CH_FIND message again to its one-hop neighbors 2. ifu does not receive any ASK_JOIN from the normal node then 3. u sends TRA to $p (u)$ 4. $sta (u) = COMPLETE$ 5. end if 6. ifu receives ASK_JOIN from its one-hop neighbors then 7. u return Main Stage line 11 8. end if 9. if sink s does not receive any ASK_JOIN from normal node then 10. $sta (u) = COMPLETE$ 11. end if

In Procedure 2, node u will send a CH-FIND message to its one-hop neighbor again. If receiving no ASK-JOIN messages, node u will send a TRA message to its parent node, and the state will be converted to COMPLETE. If node u happens to receive an ASK-JOIN message, it will begin to carry out the line 11 in Main stage. When the sink node s no longer receives any ASK-JOIN message, the establishment of DAT is completed.

During the establishment of DAT, the status of node is changing. A node may have four states as WAIT, ACTIVATED, LISTEN, and COMPLETE. The conversion relation of four states is shown in Figure 6.

Figure 6.

States transition for different nodes: (a) other nodes and (b) aggregation nodes.

Figure 6(a) depicts the states of other nodes (expect aggregation nodes). Normal node is initially in WAIT, and keeping WAIT state if it satisfies the following two conditions: not receive any ACC-JOIN message and another is that the number of its candidate parent is more than one; otherwise, it will change the state into ACTIVATIED. When the candidate parent of the node is 1, it became a Special node and the state is still in WAIT until it receives ACC-JOIN message, and then its state is in COMPLETE. The node which is in state ACTIVATIED will keep the state if it does not select a new catalyst or the number of its child node is less than k; otherwise, the node is being LISTEN and hold the mode if it finds a new catalyst after sending CH-FIND messages. The node in state ACTIVATIED and LISTEN can change into COMPLETE when the node cannot find any catalyst and no new catalyst is found after sending CH_FIND messages, respectively. Figure 6(b) describes the states of the aggregation nodes. The aggregation node is in WAIT state in Start-up phase, and then in ACTIVATIED when the Start-up stage is finish and the number of the child node and neighbor of aggregation node are not equal. If the node does not select any new catalyst or the number of its child node is less than k, the state is constant. The node will in LISTEN when the new catalyst is found and it will keep in LISTEN if the catalyst node is found after the aggregation node sending CH-FIND message; otherwise, the state will be in COMPLETE.

Establishment of FCFS

The FCFS is proposed based on the establishment of DAT, which will be described in detail in this section. Relative variables are shown in Table 2.

Table 2.

Main stored variables and explanations.

Notation	Definition	Notation	Definition
$R (u)$	Rank of u	$n_{ch} (u)$	Number of not confirm working period child nodes of u
$WP (u)$	Working period of u	$SCon (u)$	Conflicting set of u
$W P_{\min} (u)$	Minimum valid working period of u	$SFor (u)$	Forbidden working period set of u

In Table 2, $R (u)$ refers to the level of node u. The node’s level is determined by the distance from the node to the sink node as well as the node ID. The $R (u)$ of a node is higher when the node lies farther away from the sink node. When the distance of two nodes to the sink node is the same, $R (u)$ depends on the ID of the node, and the larger the node ID is, the higher the node level will be. $WP (u)$ refers to the WP of node u sending the data packet to its parent node. $W P_{\min} (u)$ refers to the minimum WP of node u sending the data packet to its parent node, and also the maximum WP of u’s child node sending packet back. $n_{nch} (u)$ refers to the child node of u who has not determined in which WP to transmit the packet to u. The collision set of node u is described as $SCon (u)$ , and the details are presented in section Conflict Set. $SFor (u)$ refers to the determined WP of the node in $SCon (u)$ .

The pseudocode of FCFS is shown as follows.

Algorithm 5. Pseudocode of FCFS
Initialization: $WP (u) = 0$ $W P_{\min} (u) = 0$ , $SFor (u) = Ø$ , $n_{nch} (u) = n_{ch} (u)$ , $SCh (u) = Ø$ , $\forall u \in V \ {s}$ . 1. for each node u not confirm working period do 2. if $n_{nch} (u) = 0$ and $R (u) > max R (i) \| \forall i \in SCon (u)$ then{ 3. if $W P_{\min} (u) = 0$ then 4. $WP (u) = W P_{\min} (u) + 1$ 5. else 6. if $ts (u) < ts (p (u))$ then 7. $WP (u) = W P_{\min} (u)$ 8. else 9. $WP (u) = W P_{\min} (u) + 1$ 10. end if 11. end if 12. while $WP (u) \in SFor (u)$ do 13. $WP (u) = WP (u) + 1$ 14. end while 15. $n_{nch} (P (u)) = n_{nch} (P (u)) - 1$ 16. if $WP (u) > W P_{\min} (P (u))$ then 17. $W P_{\min} (P (u)) = WP (u)$ 18. end if 19. u sends a CON_WP message to its two-hop neighbors 20. for each not confirm working period node v receives CON_WPdo 21. if $u \in SCon (v)$ then 22. $SFor (v) = SFor (v) \cup WP (u)$ 23. $SCon (v) = SCon (v) \ (u)$ 24. end if 25. end for 26. end if 27. end for

Algorithm 5. Pseudocode of FCFS

FCFS

Initialization:

WP (u) = 0

W P_{\min} (u) = 0

SFor (u) = Ø

n_{nch} (u) = n_{ch} (u)

SCh (u) = Ø

\forall u \in V \ {s}

.
1. for each node u not confirm working period do
2. if

n_{nch} (u) = 0

and

R (u) > max R (i) | \forall i \in SCon (u)

then{
3. if

W P_{\min} (u) = 0

then
4. $WP (u) = W P_{\min} (u) + 1$
5. else
6. if

ts (u) < ts (p (u))

then
7. $WP (u) = W P_{\min} (u)$
8. else
9.

WP (u) = W P_{\min} (u) + 1

10. end if
11. end if
12. while

WP (u) \in SFor (u)

do
13.

WP (u) = WP (u) + 1

14. end while
15.

n_{nch} (P (u)) = n_{nch} (P (u)) - 1

16. if

WP (u) > W P_{\min} (P (u))

then
17.

W P_{\min} (P (u)) = WP (u)

18. end if
19. u sends a CON_WP message to its two-hop neighbors
20. for each not confirm working period node v receives CON_WPdo
21. if

u \in SCon (v)

then
22.

SFor (v) = SFor (v) \cup WP (u)

23.

SCon (v) = SCon (v) \ (u)

24. end if
25. end for
26. end if
27. end for

The specific process of FCFS will be discussed as follows: first, the stored variables of the nodes in WSN are initialized, and the WP is not selected yet to send the data packets to their parent nodes. For the convenience of subsequent description, the node which determines the WP to send the data packet to its parent node is called certain node; otherwise, it is called uncertain node. For any uncertain node u, it can select the WP first if all its child nodes are certain nodes and $R (u)$ is greater than the rank of nodes in the SA(u). In this case, the WP of node u is 1 if $W P_{\min} (u) = 0$ . When $W P_{\min} (u) \neq 0$ , node u may transmit data without any collision to $P (u)$ in the last WP of u’s child node send packet to node u if $ts (u) < ts (p (u))$ ; otherwise, u needs to wait until the next WP. At this moment, u will judge whether the selected WP is consistent with the certain node in $SCon (u)$ . If it is consistent, u will add its WP by 1 to avoid conflict and become a certain node. Then $P (u)$ decreases the number of uncertain child nodes by 1. The value of $W P_{\min} (P (u))$ is equal to $WP (u)$ , if there is $WP (u) > W P_{\min} (P (u))$ ; otherwise, the value of $W P_{\min} (P (u))$ remains the same.

Node u now sends a CON_WP (confirm the WP) message to its two-hop neighbors, informing them that it has become a certain node. In this case, if the collision set of the uncertain node v which receives CON_WP contains the node u, node v adds $WP (u)$ to its $SFor (v)$ , so as to avoid conflict with u in WP selecting since u has become the certain node. Besides, v will also wipe out u from its $SCon (v)$ , because u becomes the certain node earlier than v, and u is still within the conflict set of v. This means that u’s rank must be higher than v; otherwise, no nodes can meet the conditions in line 2 if node u does not remove from $SCon (v)$ . When the FCFS is implemented, all the nodes except the sink node in the network will complete the data packet transmission according to the above algorithm.

Simulation analysis

Network simulator 2 is adopted to evaluate the performance of DCF-DAS. First, different values of k are taken and compared in terms of different values of TS, node densities (represented by different network side lengths), and the numbers of nodes. The optimal value of k is obtained by analyzing the minimum number of WP required to complete data aggregation. Second, using the value of k obtained above as the maximum number of node’s child node in the DAT, DCF-DAS is compared with SA¹³ and IAS²¹ still from the above three aspects to verify the effectiveness of the proposed mechanism. Assuming that the communication radius of the sensor node is 30 m and the node randomly select a working TS in 0–TS-1 in the simulation, the sink node is deployed in the upper left corner of the entire area, and all results are taken from the average value of 10 times experimental results.

Determination of k

To obtain the optimal value of k to achieve the fast data aggregation, several special values of k are selected to observe the total number of WPs required to complete the aggregation at different values of TS. So the purpose of this section is to get the optimal value of k and the value obtained can be used in the simulation experiment. The total number of nodes in the simulation experiment is 400, and Figure 7 shows the relationship between TS and WP under different values of k when the network length (NL) is 50, 100, and 200 m, respectively. As it can be seen in Figure 7(a), when the network density is large, that is, when the node’s average number of neighbor nodes is large, the condition of k = 1 can complete the data aggregation quickly. Figure 7(b) and (c) shows that when the network density reduces, the condition with k = 2 makes the data aggregation be completed faster than those with other values of k. The total number of WP decreases with the increase in TS, because the increasing TS which can be selected could increase the possibility of free-collision transmission.

Figure 7.

The relationship between number of WP and TS with different values of k: (a) NL = 50, (b) NL = 100, and (c) NL = 200.

The above is the number of WP required for the nodes to complete data aggregation with different TS settings. It can be concluded that when the node deployment density is large, k can take 1 for faster data aggregation. On the contrary, the condition of k = 2 can achieve good results. The following analysis will focus on the total WP required to complete the aggregation with node deployment density changing and different values of k. The total number of nodes in Figure 8 is still 400, and the values of TS in Figure 8(a)–(c) are 2, 10, and 100, respectively. The simulation results are as follows.

Figure 8.

The relationship between number of WP and network side with different values of k: (a) TS = 2, (b) TS = 10, (c) TS = 100.

The simulating results show that no matter whether the value of TS is large or small, the condition of k = 2 will take the shortest time for data aggregation. Therefore, it can be simply concluded that when the node density is large, the setting of k = 1 is the optimal choice, while in other conditions the setting of k = 2 will get better performance. In the simulations above, the number of nodes is fixed. Now the number of nodes is variable, the optimal value of k will be discussed by setting different node densities and TS. Figure 9 shows the relationship between the WP required for data aggregation and the number of nodes with different values of k. In Figure 9(a)–(c), the length of the network is set to be 50, 200, and 200 m, respectively. The TS’ values are set to be 100, 100 and 10, respectively. The simulation results are as follows.

Figure 9.

The relation between number of WP and number of nodes with different values of k: (a) NL = 50 TS = 100, (b) NL = 200 TS = 100, and (c) NL = 200 TS = 10.

Compared with Figure 9(a) and (b), we can see that when the value of TS is the same and the network density is small, the setting of k = 1 can not only finish the data aggregation faster but also reduce the total WP compared to that of k = 2, which verifies the correctness of the conclusion above. It also shows that when the TS value is large, the aggregation performance with k = 1 is superior to that of other k values.

To sum up, when node deployment density is large or the value of TS is high in the network, k = 1 will be prone to obtain good aggregation performance, otherwise k = 2 is a better choice for other network conditions. Based on this, the proposed mechanism DCF-DAS will be compared with some classical data aggregation mechanisms to verify the effectiveness and correctness.

DCF-DAS validity verification

In order to verify the effectiveness of the proposed DCF-DAS, the classical IAS and SA are adopted as the comparisons in simulation experiments, where SA is a most used centralized data aggregation scheme. Two parts of DCF-DAS (DAT and FCFS) are separately evaluated to fully verify the proposed mechanism. $DCF - DA S_{k = 1}$ and $DCF - DA S_{k = 2}$ are taken to express the DCF-DAS with k = 1 and k = 2, respectively. The traditional IAS scheme does not take the node periodically changing the working state into account in DAT establishment. For the subsequent verification, the traditional IAS mechanism can be regarded as $DCF - IA S_{k = 0}$ . To fully validate the performance of DAT and FCFS, three new mechanisms $DCF - DA S_{k = 0}$ , $IA S_{k = 1}$ , and $IA S_{k = 2}$ are generated from the combination of IAS and DCF-DAS, where $DCF - DA S_{k = 0}$ is the composition of the aggregation tree scheme in IAS and data aggregation mechanism of FCFS proposed in this article. $IA S_{k = 1}$ and $IA S_{k = 2}$ composed of the DAT (when the value of k is 1 and 2, respectively) and data aggregation scheme with no periodically changing working status in IAS.

Taking the condition with k = 1 as an example (the following condition are the same when k = 2), the correctness and effectiveness of the DAT algorithm can be verified by comparing IAS with $IA S_{k = 1}$ and $DCF - DA S_{k = 0}$ with $DCF - DA S_{k = 1}$ , while the performance of FCFS can be verified by comparing IAS with $DCF - DA S_{k = 0}$ and $IA S_{k = 1}$ with $DCF - DA S_{k = 1}$ . The entire simulation experiments are also carried out with different numbers of TS, node densities, and numbers of nodes.

Figure 10 shows the relationship between the total WP required for completing the aggregation and the value of TS under different data aggregation schemes. Assuming that the network sides are 50, 100, and 200 m in Figure 10(a)–(c), respectively, and the total number of nodes is 400. It can be concluded from the calculated results that in these three cases, the total WP required to complete the data aggregation of $IA S_{k = 1}$ are 13.285, 26.48, and 28.945 times more than $DCF - DA S_{k = 1}$ , respectively. We ignore the curve $IA S_{k = 1}$ for the better appearance of the results. As can be seen from Figure 10(a), the number of WP required by $DCF - DA S_{k = 1}$ is less than that by $DCF - DA S_{k = 2}$ , because the deployment density of nodes in the network is large when L = 50, which also verifies the conclusions in section “Establishment of DAT.” The effect of $DCF - DA S_{k = 2}$ is superior to $DCF - DA S_{k = 1}$ when the node density increases. As the number of TS increases, the number of WP required by data aggregation substantially reduces, due to growing opportunity of the node transmitting the data packets to its parent node in the same WP with receiving the last packet from its child node. Figure 10 shows that the DCF-DAS data aggregation mechanism proposed in this article is more efficient than other widely used mechanisms.

Figure 10.

The relation between number of WP and TS: (a) NL = 50, (b) NL = 100, and (c) NL = 200.

Figure 11 shows the relationship between the total WP required to complete the aggregation and the node deployment density under different data aggregation mechanisms. In Figure 11(a)–(c), the TS number of nodes in the network is set to be 2, 10, and 100, respectively, and the total number of nodes is 400. Statistical results from the experimental data show that the total WP required by $IA S_{k = 1}$ for data aggregation exceed $DCF - DA S_{k = 1}$ more than 89.1% in Figure 11(a) and is nearly 5.172 and 11.148 times more than $DCF - DA S_{k = 1}$ in Figure 11(b) and (c), respectively, so this curve of $IA S_{k = 1}$ is ignored for the brief appearance. As it can be seen from Figure 11(b) and (c), when the network side is about 60 m, the total aggregation WP for $DCF - DA S_{k = 1}$ and $DCF - DA S_{k = 2}$ is basically the same. But as the network deployment density decreases, the effect of $DCF - DA S_{k = 2}$ will be more excellent than that of $DCF - DA S_{k = 1}$ . Figure 11 shows that the effect of $DCF - DA S_{k = 1}$ is poor in low network deployment density. Overall, the total WP taken by $DCF - DA S_{k = 1}$ and $DCF - DA S_{k = 2}$ proposed in this article will be 65% and 50.1% lower than IAS and SA, respectively.

Figure 11.

The relation between number of WP and network side: (a) TS = 2, (b) TS = 10, (c) TS = 100.

Figure 12 shows the relationship between the total number of WP required to complete the aggregation and the number of nodes in the network under different data aggregation mechanisms. In Figure 12(a)–(c), it is assumed that the network side is 200, 200, and 50 m, respectively. The TS is 10, 100, and 50, respectively. The statistical results from the experimental data show that the total WP required to complete the data aggregation by $IA S_{k = 1}$ are 6.74, 11.65, 1.86 times more than $DCF - DA S_{k = 1}$ in these three cases, and the curve of $IA S_{k = 1}$ is ignored for the same reason. Figure 12(b) and (c) shows that the required WP for $DCF - DA S_{k = 1}$ will decrease with the increasing network density. Specifically, it is 4.9% more than the required WP of the SA with the network side length as 200 m, and 44.5% less than that of SA with the length being reduced to 50 m.

Figure 12.

The relation between number of WP and number of nodes: (a) NL = 200 TS = 10, (b) NL = 200 TS = 100, and (c) NL = 50 TS = 50.

The simulation shows that DCF-DAS, especially k = 2, can achieve less delay among the three algorithms (DCF-DAS, IAS and SA) and IAS is inferior relatively in terms of different number of TS, length of network side, and number of nodes. The proposed DCF-DAS adopts the working mode of node periodically changing the working state, so it can save more energy than IAS, since the sensor nodes of IAS are working all the time, which can lose a lot of energy. Compared with the centralized scheme SA, the distributed data aggregation scheme DCF-DAS can extensively reduce the time delay. The scheme in this article may not be the optimal algorithm to deal with the time delay in data aggregation, but from the aspect of collision-free, it is superior to some traditional mechanism. To sum up, the proposed DCF-DAS data aggregation scheme can effectively shorten the aggregation time required than other widely used mechanisms.

Conclusion

Aiming at the problem of time delay brought in by data aggregation in WSNs, this article proposes a DCF-DAS consisting of the two major components as the DAT and the FCFS for data aggregation. DAT will provide data aggregation topology for FCFS by controlling the number of child nodes. The whole mechanism takes the way of node periodically changing the working states to alleviate the node energy consumption. FCFS can shorten the total WP needed to complete the data aggregation of the whole network. In simulating experiments, the WP required for data aggregation is taken as the metrics based on DCF-DAS, IAS, and SA in terms of different numbers of TS, network deployment densities, and numbers of nodes. Statistical results show that DCF-DAS proposed in this article can reduce the time delay more effectively than other widely used mechanisms. The main advantages of this article is to design a data aggregation algorithm which is conflict free, using the limited number of child nodes to avoid the conflict and retransmission when transmitting the message, and then reduce the time needed to complete the data aggregation. We give a priority to collision-free to avoid retransmitting; therefore, the energy can be saved. Our current work focused on minimizing the time delay and collision-free in data aggregation in fixed network forms, and we will focus on the construction of the data aggregation algorithm in the condition of moving nodes in the future and improve the algorithm to guarantee the effectiveness, since the topological structure of the dynamic network is changing irregularly.

Footnotes

Handling Editor: Jaime Lloret

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 by the National Natural Science Foundation of China (61771186), Postdoctoral Research Project of Heilongjiang Province (LBH-Q15121), and University Nursing Program for Young Scholars with Creative Talents in Heilongjiang Province (UNPYSCT-2017125).

ORCID iD

Danyang Qin

References

Pandey

Hegde

RM.

Node localization over small world WSNs using constrained average path length reduction. Ad Hoc Netw 2017; 67: 87–102.

Sherazi

Grieco

Boggia

A comprehensive review on energy harvesting MAC protocols in WSNs: challenges and tradeoffs. Ad Hoc Netw 2018; 71: 117–134.

Zhang

Wang

Guo

KH.

Multi-functional secure data aggregation schemes for WSNs. Ad Hoc Netw 2018; 69: 86–99.

Xie

Ning

Wang

An efficient privacy-preserving compressive data gathering scheme in WSNs. Inform Sciences 2017; 390: 82–94

Mohamed

Hamza

Saroit

IA.

Coverage in mobile wireless sensor networks (M-WSN): a survey. Comput Commun 2017; 110: 133–150.

Mostafaei

Montieri

Persico

A sleep scheduling approach based on learning automata for WSN partialcoverage. J Netw Comput Appl 2017; 80: 67–78.

Tawalbeh

Hashish

Tawalbeh

Quality of service requirements and challenges in generic WSN infrastructures. Procedia Comput Sci 2017; 109: 1116–1121.

Roy

Conti

Setia

et al . Secure data aggregation in wireless sensor networks: filtering out the attacker’s impact. IEEE T Inf Foren Sec 2014; 9(4): 681–694.

Liu

et al . An efficient data aggregation algorithm for WSNs based on dynamic message list. Procedia Comput Sci 2016; 83: 98–106.

10.

Bramas

Tixeuil

The complexity of data aggregation in static and dynamic wireless sensor networks. Inform Comput 2017; 255: 369–383.

11.

Rajalakshmi

Prakash

APG

. MeMLO: mobility-enabled multi-level optimization sensor network. Wireless Pers Commun 2017; 97: 5675–5689.

12.

Byun

Yang

Energy-balancing node scheduling inspired by gene regulatory networks for wireless sensor networks. IET Commun 2017; 11: 2650–2659.

13.

JZ.

Minimum-time aggregation scheduling in duty-cycled wireless sensor networks. J Comput Sci Technol 2011; 26: 962–970.

14.

Sarkar

Panigrahi

Pati

et al . A novel approach for real-time data management in wireless sensor networks. In: Nagar

Mohapatra

Chaki

(eds) Smart innovation, systems and technologies. vol. 44. New Delhi, India: Springer, 2016, pp.599–607.

15.

Chipara

Stankovic

et al . Dynamic conflict-free transmission scheduling for sensor network queries. IEEE T Mobile Comput 2011; 10(5): 734–748.

16.

Abdulsalam

Ali

Alyatama

Air quality monitoring using a LEACH-based data aggregation technique in wireless sensor network. Ad Hoc Sens Wirel Ne 2016; 32: 275–300.

17.

Ukil

Privacy preserving data aggregation in wireless sensor networks. J Jinling Inst Technol 2014; 44(6): 480–486.

18.

Xiang

Luo

Rosenberg

Compressed data aggregation: energy-efficient and high-fidelity data collection. IEEE Press 2016; 21(6): 1722–1735.

19.

Shu

Lloret

Rodrigues

JJPC

et al . Distributed intelligence and data fusion for sensor systems. IET Commun 2011; 5(12): 1633–1636.

20.

Namalwar

Meshram

Thakare

et al . WSN based smart sensor and actuator for power management in intelligent buildings. IEEE/ASME T Mechatron 2015; 20: 564–571.

21.

Mao

et al . A delay-efficient algorithm for data aggregation in multihop wireless sensor networks. IEEE T Parall Distr 2011; 22: 163–175.