Improving Energy Adaptivity of Constructive Interference-Based Flooding for WSN-AF

Abstract

Constructive interference (CI) is a synchronous transmission technique for multiple senders transmitting the same packet simultaneously in wireless sensor networks (WSNs). CI enables fast and reliable network flooding in order to reduce the scheduling overhead of MAC protocols, to achieve accurate time synchronization, to improve link quality of lossy links, and to realize efficient data collection. By achieving microsecond level time synchronization, Glossy realizes millisecond level CI-based flooding and 99% reliability. However, Glossy produces substantial unnecessary data forwarding, which significantly reduces the network lifetime. This is a very critical problem, especially in energy-limited large-scale wireless sensor networks for agriculture and forestry (WSN-AF) system. In this paper, we present an energy adaptive CI-based flooding protocol (EACIF) by exploiting CI in WSN-AF. EACIF proposes a distributed active nodes selection algorithm (ANSA) to reduce redundant transmissions, thereby significantly reducing energy consumption and flooding latency. We estimate the performance of EACIF both with real data traces and with uniformly distributed topology. Simulation results show that EACIF achieves almost the same packet reception ratio (PRR) as Glossy (e.g., 99%), while reducing 63.96% energy consumption. EACIF also reduces 25% flooding latency. When the packet interval is 30 seconds, EACIF achieves 0.11% duty cycle.

1. Introduction

With the emergence of the Internet of Things (IoT) [1, 2], wireless sensor networks for agriculture and forestry (WSN-AF) are becoming a research hotspot. WSN-AF systems can provide real-time field data, including environment temperature, relative humidity (RH), O₂ concentration, CO₂ concentration [3], and ethylene (C₂H₄) concentration. The implementation of WSN-AF system demands forwarding data [4], synchronizing sensor nodes [5], creating data collection tree [6], locating the monitored objects [7], reprogramming the revised code [8], and so forth. All these common applications in WSNs depend on the service of network flooding which propagates a packet through the whole network.

Power consumption, latency, and reliability are three critical factors of flooding in wireless sensor networks (WSNs). Recently, constructive interference- (CI-) based flooding is emerging as a latency optimal and high reliability flooding technique. As a representative CI-based flooding protocol, Glossy [9] realizes 99th percentile packet reception ratio (PRR). Real testbed (MoteLab, Twist, and Local) experiments show that Glossy achieves millisecond level flooding latency which is almost 100 times faster than traditional flooding solutions [10, 11]. Then a question arises: is Glossy energy-efficient? Unfortunately, Glossy makes all nodes involved in the data forwarding, which directly triggers enormous number of superfluous data transmissions, eventually leading to unnecessary energy consumption and network life reduction. This is a very critical problem, especially in energy-limited large-scale WSNs. One effective solution is to reduce redundant transmissions while maintaining the advantages of CI-based flooding.

A concurrent transmission scenario of CI-based flooding can be illustrated in Figure 1. In this example, $S\mathrm{1}$ , $S\mathrm{2}$ , $S\mathrm{3}$ , $S\mathrm{4}$ , $S\mathrm{5}$ and $R\mathrm{1}$ are randomly deployed in a square area. Suppose all nodes having the same transmission range. According to the overlapping relations shown in Figure 1, the adjacency sets of $S\mathrm{1}$ , $S\mathrm{2}$ , $S\mathrm{3}$ , $S\mathrm{4}$ , $S\mathrm{5}$ can be expressed as $N_{s\mathrm{1}}=\{S\mathrm{5},S\mathrm{4},R\mathrm{1}\}$ , $N_{s\mathrm{2}}=\{S\mathrm{3},S\mathrm{4},R\mathrm{1}\}$ , $N_{s\mathrm{3}}=\{S\mathrm{2},S\mathrm{5},R\mathrm{1}\}$ , $N_{s\mathrm{4}}=\{S\mathrm{2},S\mathrm{1},R\mathrm{1}\}$ , and $N_{s\mathrm{5}}=\{S\mathrm{1},S\mathrm{3},R\mathrm{1}\}$ . As the most common behavior of CI-based flooding, $S\mathrm{1}$ , $S\mathrm{2}$ , $S\mathrm{3}$ , $S\mathrm{4}$ , $S\mathrm{5}$ are forwarding an identical packet to $R\mathrm{1}$ simultaneously. In order to transfer as soon as possible, Glossy makes all the five senders in the radio on mode (dashed arrows in Figure 1) which is obviously unnecessary. In fact, an optimized forwarding set can be selected via lightweight communication between neighbors. Suppose that the residual energy of each node can be expressed as $\text{E}{\text{r}}_{\mathrm{1}}$ , $\text{E}{\text{r}}_{\mathrm{2}}$ , $\text{E}{\text{r}}_{\mathrm{3}}$ , $\text{E}{\text{r}}_{\mathrm{4}}$ , and $\text{E}{\text{r}}_{\mathrm{5}}$ . The residual energy of each candidate sender and its neighbors is as follows: $E_{s\mathrm{1}}=\{\text{E}{\text{r}}_{\mathrm{1}},\text{E}{\text{r}}_{\mathrm{5}},\text{E}{\text{r}}_{\mathrm{4}}\}$ , $E_{s\mathrm{2}}=\{\text{E}{\text{r}}_{\mathrm{2}},\text{E}{\text{r}}_{\mathrm{3}},\text{E}{\text{r}}_{\mathrm{4}}\}$ , $E_{s\mathrm{3}}=\{\text{E}{\text{r}}_{\mathrm{2}},\text{E}{\text{r}}_{\mathrm{3}},\text{E}{\text{r}}_{\mathrm{5}}\}$ , $E_{s\mathrm{4}}=\{\text{E}{\text{r}}_{\mathrm{1}},\text{E}{\text{r}}_{\mathrm{2}},\text{E}{\text{r}}_{\mathrm{4}}\}$ , and $E_{s\mathrm{5}}=\{\text{E}{\text{r}}_{\mathrm{1}},\text{E}{\text{r}}_{\mathrm{3}},\text{E}{\text{r}}_{\mathrm{5}}\}$ . Then we have $\text{E}{\text{r}}_{\mathrm{1}}>\text{E}{\text{r}}_{\mathrm{2}}>\text{E}{\text{r}}_{\mathrm{3}}>\text{E}{\text{r}}_{\mathrm{4}}>\text{E}{\text{r}}_{\mathrm{5}}$ . Each node independently selects the node which has the largest residual energy from $E_{si}\hspace{0.17em}\hspace{0.17em}(i=\mathrm{1},\dots ,\mathrm{5})$ . For the example in Figure 1, $S\mathrm{1}$ and $S\mathrm{2}$ are selected as the final senders. $S\mathrm{3}$ , $S\mathrm{4}$ , and $S\mathrm{5}$ can keep silent to save energy. As shown by the red arrows in Figure 1, we can achieve the same flooding performance but save 60% energy consumption compared with Glossy. In particular, all nodes have the same residual energy in the initial state. There are two disjoint forwarding sets $\{S\mathrm{1},S\mathrm{2}\}$ and $\{S\mathrm{4},S\mathrm{5}\}$ . Network lifetime can be greatly extended by energy adaptive scheduling $\{S\mathrm{1},S\mathrm{2}\}$ (red arrows in Figure 1) or $\{S\mathrm{4},S\mathrm{5}\}$ (green arrows in Figure 1) as the practical forwarding set.

Figure 1

Compared with Glossy, EACIF can reduce redundant transmissions.

Inspired by this insight, we propose an energy adaptive CI-based flooding protocol (EACIF) for WSN-AF. EACIF improves energy adaptive CI-based flooding through energy scheduling and topology control. Compared with the state-of-art CI-based flooding protocols, EACIF achieves lower energy consumption, lower latency, and the same coverage and reliability. The major contributions of this work are summarized as follows.

• (i)

We are the first to propose a lightweight distributed energy adaptive CI-based flooding protocol (EACIF) for WSNs. EACIF adapts to the network changes in residual energy and selects the optimized forwarding set via the communication between neighbors.

(ii)

EACIF constructs a sparse topology for CI-based flooding via an approximate minimum connected dominating set (MCDS) algorithm, which can be completed approximately in $O(n)$ .

(iii)

EACIF proposes a k-covered mode switching algorithm (KMSA) for k-covered UDG and theoretically derives the energy saving formula for CI-based flooding.

(iv)

We simulate EACIF based on uniformly distributed topology and real topology. Simulation results show that EACIF can achieve the same reliability as Glossy, while reducing 63.96% energy consumption on the real trace.

The rest of the paper is organized as follows. We review the related work in Section 2. In Section 3, we analyze the process of CI-based flooding and present active nodes selection algorithm (ANSA) and k-covered mode switching algorithm (KMSA). We evaluate the performance of EACIF in Section 4 and conclude the paper in Section 5.

2. Related Work

Constructive interference (CI) is a physical layer phenomenon and was first experimentally discovered by Dutta et al. [12]. Subsequently, CI is used in backcast [13] to avoid broadcast storm problem. CI can be achieved by submicrosecond time synchronization of all coordinated senders. A typical scenario of CI is shown in Figure 2; $S\mathrm{1}$ , $S\mathrm{2}$ , and R all employ IEEE 802.15.4 radios. The packets ( $P_{s\mathrm{1}}$ and $P_{s\mathrm{2}}$ ) with the same data are, respectively, transmitted from $S\mathrm{1}$ and $S\mathrm{2}$ to R. R can decode the $P_{s\mathrm{1}}$ and $P_{s\mathrm{2}}$ as one packet if the maximum temporal displacement Δ of $P_{s\mathrm{1}}$ and $P_{s\mathrm{2}}$ is no more than one chip period $T_c=\mathrm{0.5}$  μs. By implementing chip-level time synchronization on IEEE 802.15.4 radio, CI can greatly improve the efficiency of concurrent transmission in WSNs. Compared with the typical concurrent transmission technologies, capture effect (CE) [14] and message-in-message (MIM) [15], CI neither needs to set packet with strong signal arrival first nor needs to add additional hardware detecting the signal strength. Recently, TriggerCast [16] improves CI technology by compensating synchronization errors caused by propagation delay and realizing link selections in the lossy-link condition.

Figure 2

The basic principle to generate CI.

CI requires that multiple senders simultaneously transmit the same packet. This behavior is consistent with the characteristics of network flooding. Besides CI-based flooding, opportunistic flooding [17] also achieves fast network flooding by constructing a tree-based topology. Previous technologies such as CF [11] and RBP [10] schedule the data forwarding through link quality assessment. Moreover, when multiple sensor nodes simultaneously send an identical packet to the same destination, existing flooding solutions (RBP [10], FLASH [18], and CF [11]) need to dispatch the transmission order. Otherwise, it will cause mutual interference. The dispatch overhead should never be neglected in the large size of WSN-AF system. Fortunately, CI-based flooding can eliminate redundant dispatch overhead while increasing the flooding speed.

Glossy [9] achieves the synchronization condition ( $\Delta \le \mathrm{0.5}$  μs) of CI by capturing interrupts of IEEE 802.15.4 radio. Accurate synchronization guarantees high reliability of CI-based flooding. However, Glossy produces considerable redundant packets during the flooding process. This leads to massive unnecessary energy consumption. LWB [19], Chaos [20], and Choco [21] build up level scheduling mechanism for data collection or dissemination based on Glossy. The above works [19–21] achieve low duty cycle and efficient network flooding. However, they do not fundamentally change the transmission mechanism of Glossy which brings unnecessary energy consumption. Splash [22] forms a parallel pipeline by scheduling channel switch between nodes on adjacent layers. Splash can achieve higher throughput than Glossy. However, frequent channel switching increases the cumulative synchronization error which decreases synchronization accuracy and reliability. Meanwhile, channel scheduling brings more energy consumption.

Recently, Wang et al. [23] prove that Glossy has a scalability problem. The PRR of Glossy is inversely proportional to the hops of independent paths. The reason is that independent paths increase cumulative synchronization errors. For example, the GreenOrbs project [3] is designed to deploy 1000 nodes in Tianmu Mountain, Jiaxing, China, for forest carbon sink. In order to achieve accurate data acquisition, GreenOrbs deploys 8~20 neighbors (according to the diversity of node's communication range) for every sensor node. The drawback of scalability problem is more serious in such a high dense WSN-AF system. Wang et al. also propose SCIF protocol which leverages grid topology to reduce the number of independent paths. However, the grid topology increases the path length of CI-based flooding and therefore increases the network delay. CX [24] uses the changes of relay count to conduct link selection, to some extent, reducing the number of nodes involved in transmission. Due to the randomness of relay count, CX costs considerable computational overhead and energy consumption. Compared with the above CI-based flooding protocols, EACIF is an energy adaptive CI-based flooding mechanism. EACIF achieves high reliability, high speed, and low-power network flooding via distributed management of node residual energy.

3. EACIF Implementation

Enlightened by SCIF [23], we find that a sparse topology can help to achieve energy adaptive CI-based flooding. However, there are still some challenges. The first challenge is to guarantee full network coverage while achieving fast network flooding and high packet reception ratio (PRR). The second challenge is to achieve a lightweight distributed energy scheduling algorithm for redundancy cover sets. In this section, we introduce the implementation of EACIF. We analyse the state migration of CI-based flooding in Section 3.1. Then, we introduce the topology control algorithm in Section 3.2, followed by the design of k-covered mode switching algorithm in Section 3.3. Moreover, we theoretically analyze the energy consumption of EACIF in Section 3.4.

3.1. The Analysis of CI-Based Flooding

CI-based flooding is a network flooding technique based on the hierarchical model. In the first round, the initiator broadcasts a packet to its one-hop neighbors. Then, the one-hop neighbors will forward the received packets to the initiator and the two-hop neighbors in the second round. Every other round, nodes on each layer forward the flooding packet once. Each node stops forwarding packet if its transmission count reaches the transmission threshold.

Key factors of CI-based flooding are listed in Table 1. $Tx$ represents the node that starts to send a packet and $Rx$ is the specific event of receiving packet. When the flooding begins, only the initiator can send packet. Let $\text{SF}\_i$ denote the node that becomes an initiator and $\text{SF}\_r$ let denote the node that becomes a receiver. $\text{SF}\_i$ and $\text{SF}\_r$ events are only triggered at the beginning of the network flooding process. Stop represents the external event stopping the network flooding. $C\_tx$ is the transmission counter which records the number of transmissions of the current node. $N\_tx$ is the transmission threshold. $Rx\_f$ indicates that the node fails to receive the packet. We use c to denote the relay count which will be increased by one after each successful reception.

Table 1

The key factors of CI-based flooding.

Factor	Definition
$$Tx$$	Transmitting event
$$Rx$$	Receiving event
$${\text{SF}}_r$$	Start flooding event for receiver
$${\text{SF}}_i$$	Start flooding event for initiator
$$Stop$$	Stop flooding event
$$C\_tx$$	Transmission counter
$$N\_tx$$	Transmission threshold
$$Rx\_f$$	Rx failed event
c	Relay counter

As Figure 3 shows, CI-based flooding has four correlative states including Radio off state, Standby state, Send state, and Receive state. When $\text{SF}\_i$ event happens, the initiator transforms from Radio off state into Send state. Then the initiator triggers the $Tx$ event to send a flooding packet to its one-hop neighbors. When $\text{SF}\_r$ event happens, the nodes except the initiator enter the Standby state to wait for the incoming packets. When $Rx$ event happens, the node switches to Receive state and starts to decode the received packet. If the reception is successful, ++c is performed. Meanwhile, the node shifts to Send state for new transmitting round. In contrast, if $Rx\_f$ happens ( $\Delta \ge \mathrm{0.5}$  μs), the node converts into Standby state for the next receiving round. After $Tx$ event is completed, the node has two candidate states: the Standby state and the Radio off state. If $C\_tx$ is less than $N\_tx$ , the node will turn to Standby state to wait for the new $Rx$ event. If $C\_tx$ reaches $N\_tx$ , the node will turn to Radio off state.

Figure 3

Node's state transition graph for CI-based flooding. Black solid lines represent the node working in active mode and red dashed lines represent the node working in passive mode.

Table 2 shows the energy consumption of a typical IEEE 802.15.4 compliant radio CC2420 [25]. The power consumption of Send state and Receive state is at milliampere level, while Radio off state and Standby state only consume microampere-level power. Obviously, CI-based flooding should convert the nodes to Send state and Receive state as seldom as possible. As a topology independent CI-based flooding protocol, Glossy employs all nodes in WSNs looping in Standby → Receive → Send until flooding ended. Each cycle has two “milliampere-level” states and one “microampere-level” state. As Figure 3 shows, each node in EACIF has two interconvertible modes: the active mode and the passive mode. In active mode, the node has the same state conversion schedule with Glossy, while the node in passive mode need not forward the received packet. If it has received the packet successfully, the node will turn to Radio off state to save energy. If the reception has failed, the node will turn to Standby state for the next $Rx$ event. Obviously, the more nodes in passive mode are, the more energy can be saved.

Table 2

Energy consumption of CC2420 radio.

Working state	Value	Unit
Send state
Power = −25 dBm	8.5	mA
Power = −15 dBm	9.9	mA
Power = −10 dBm	11	mA
Power = −5 dBm	14	mA
Power = 0 dBm	17.4	mA
Receive state	18.8	mA
Standby state	426	μA
Radiooff state	20	μA

The scenario shown in Figure 4 illustrates the flooding process of EACIF when $N\_tx=\mathrm{1}$ . Suppose an even-distributed WSN which has 25 nodes. Here, node I is the initiator; $A_{\mathrm{1}}$ , $A_{\mathrm{2}}$ , $A_{\mathrm{3}}$ , and $A_{\mathrm{4}}$ are working in active mode, while $P_{\mathrm{1}},\dots ,P_{\mathrm{20}}$ are working in passive mode. When the 1st transmission round begins, I broadcasts a packet to its one-hop neighbors $A_{\mathrm{1}}$ , $A_{\mathrm{2}}$ , $A_{\mathrm{3}}$ , $A_{\mathrm{4}}$ , $P_{\mathrm{1}}$ , $P_{\mathrm{2}}$ , $P_{\mathrm{3}}$ , and $P_{\mathrm{4}}$ . Upon receiving the packet, $P_{\mathrm{1}}$ , $P_{\mathrm{2}}$ , $P_{\mathrm{3}}$ , and $P_{\mathrm{4}}$ enter the Radio off state to save energy. Only $A_{\mathrm{1}}$ , $A_{\mathrm{2}}$ , $A_{\mathrm{3}}$ , and $A_{\mathrm{4}}$ participate in the 2nd transmission round. All the peripheral nodes ( $P_{\mathrm{5}},\dots ,P_{\mathrm{20}}$ ) are working in passive mode. It is not difficult to calculate that there are 80% nodes that can work in passive mode to save energy. However, Glossy makes all the 25 nodes work in active mode.

Figure 4

Flooding process with EACIF ( $N\_tx=\mathrm{1}$ ).

3.2. Topology Control Algorithm

To save energy, one of the main challenges is to find the fewest nodes in active mode to cover the whole WSN. Then, we need to design an energy-driven policy for mode scheduling. In order to complete these challenges, EACIF proposes a distributed algorithm to select the active nodes in a given topology and develops a mode scheduling policy based on residual energy.

3.2.1. Geometric Definitions

We assume a WSN consisting of n sensor nodes deployed in a two-dimensional plane. The node set is defined as V. A set of edges E can be defined by the Euclidean distance of any two nodes. In this way, we can define a simple undirected graph $G(V,E)$ . Suppose that the communication radius of all nodes is equal to one unit, we have the following definitions.

Definition 1.

In a simple undirected graph $G=(V,E)$ , for $\forall u$ , $v\in V$ , if $(u,v)\in E$ and $\exists (|uv|⩽\mathrm{1})$ , then G is a unit disk graph $\text{UDG}(V,E)$ .

Definition 2.

In $\text{UDG}(V,E)$ , a subset D of V is a dominating set (DS) if any node v in V either is in D or is a neighbor of some node d in D.

Definition 3.

In $\text{UDG}(V,E)$ , a set $C\in V$ is a connected dominating set (CDS) if the subgraph derived by C is a connected graph. For $\forall c\in C$ , if $C-\{c\}$ is not a CDS, then C is a minimal connected dominating set (MCDS).

Definition 4.

A $\text{UDG}(V,E)$ is a k-covered UDG if it contains k groups of mutually disjoint MCDS.

We call the nodes in D “active dominators” ( $\text{AD}$ ). The gateway nodes converting DS to CDS are called “active gateways” ( $\text{AG}$ ). The nodes outside $\text{CDS}$ are called “passive dominatees” ( $\text{PD}$ ).

3.2.2. Active Nodes Selection Algorithm

Enlightened by Section 3.1, we consider to construct an approximate MCDS as a sparse backbone. In a previous work, Wan et al. [26] have proposed an effective MCDS generation algorithm for wireless ad hoc networks. However, Wan's approach does not optimize the residual energy. In this paper, we propose a distributed active nodes selection algorithm (ANSA) which generates an approximate MCDS according to node's residual energy.

Definitions 2 and 3 indicate that “active nodes” include the $\text{AD}$ nodes and the $\text{AG}$ nodes. Therefore, ANSA can be divided into two subalgorithms: $\text{AD}$ election subalgorithm and $\text{AG}$ election subalgorithm.

AD Election Subalgorithm. $\text{AD}$ election subalgorithm constructs a CDS of a given topology. As Algorithm 1 shows, ${\psi }_v$ denotes the type of node v. The type of v is $\text{AD}$ if ${\psi }_v$ equals 1, while ${\psi }_v=\mathrm{0}$ indicates that the node is a $\text{PD}$ . If v is a $\text{AG}$ , ${\psi }_v$ equals 2. In the initial state, the type values of all nodes are zero. Any node v must broadcast its request to its one-hop neighbors ( $\text{QA}(v)==\text{True}$ ) if it wants to be a $\text{AG}$ . The request packets contain the residual energy of node v. Then, its neighbor nodes ( $N_v$ ) send response packets to v. When receiving the responses ( $\text{RA}(v)==\text{True}$ ), v compares its residual energy ( $\text{R}{\text{E}}_v$ ) with the residual energy set $\text{N}{\text{E}}_v$ . Node v is elected as $\text{AG}$ if and only if v has the maximum residual energy. Finally, v sets its node type and triggers $\text{TA}(v)$ event to send the declaring packets. After $\text{AD}$ election subalgorithm, each node in $G(V,E)$ is either a $\text{AG}$ or a $\text{PG}$ .

Algorithm 1: AD election algorithm.

Input: Given a node v of a unit disk graph $$G(V,E)$$ , $$v\in V$$ .

Output: The node type $${\psi }_v$$ , where Ψ denotes the set of node type and $${\psi }_v\in \mathrm{\Psi }$$ .

( $$\mathit{1}$$ )    Suppose $$QA(v)$$ , $$TA(v)$$ , $$RA(v)$$ , $${\text{RE}}_v$$ respectively represent $$\text{AD}$$ request, $$\text{AD}$$ announcement, the $$\text{AD}$$ response and the

  residual energy of v;

( $$\mathit{2}$$ )    Let $$N_v=\{N_{\mathrm{1}},N_{\mathrm{2}},\dots ,N_m\}$$ be neighbors set of node v, where p is v's neighbors number;

( $$\mathit{3}$$ )    Let $$N{E}_v=\{N{E}_{\mathrm{1}},N{E}_{\mathrm{2}},\dots ,N{E}_m\}$$ be the residual energy set of $$N_v$$ ;

( $$\mathit{4}$$ )    Let σ be the threshold of residual energy;

( $$\mathit{5}$$ )    //Set all the node type into $$\text{PD}$$ .

( $$\mathit{6}$$ )     $${\psi }_v=\mathrm{0}$$ ;

( $$\mathit{7}$$ )     $$c=\mathit{1}$$ ;

( $$\mathit{8}$$ )    //Node v initiatively apply to become a $$\text{AD}$$ .

( $$\mathit{9}$$ )    if   $$QA(v)==True$$ && $${\text{RE}}_v⩾\sigma$$   then

( $$\mathit{10}$$ )   //Node v sends the residual energy to its one-hop neighbors.

( $$\mathit{11}$$ )     $${\text{RE}}_v\to N_v$$ ;

( $$\mathit{12}$$ )  end

( $$\mathit{13}$$ )  //Node v receives residual energy from its one-hop neighbors.

( $$\mathit{14}$$ )  else if   $$RA(v)==True$$   then

( $$\mathit{15}$$ )    for   $$i=\mathrm{1}:m$$   do

( $$\mathit{16}$$ )      if   $${\text{RE}}_v<N{E}_i$$   then

( $$\mathit{17}$$ )        break;

( $$\mathit{18}$$ )      end

( $$\mathit{19}$$ )      c++;

( $$\mathit{20}$$ )   end

( $$\mathit{21}$$ )   if   $$c==m$$   then

( $$\mathit{22}$$ )      $${\psi }_v$$ = 1;

( $$\mathit{23}$$ )     //Declaring v as an $$\text{AD}$$ node.

( $$\mathit{24}$$ )      $$TA(v)=True$$ ;

( $$\mathit{25}$$ )   end

( $$\mathit{26}$$ ) end

( $$\mathit{27}$$ ) return   $${\psi }_v$$ ;

AG Election Subalgorithm. As Algorithm 2 shows, all $\text{PD}$ nodes first broadcast their ( $\text{AD},\text{PD}$ ) pairs. Alzoubi et al. [27] have proved that a $\text{PD}$ of $\text{UDG}(V,E)$ has at most five $\text{AD}$ nodes. After gathering two-hop $\text{AD}$ nodes information, a $\text{PD}$ node v can broadcast $\text{AG}$ request ( $\text{QG}(u,v,w)$ ) applying to be $\text{AG}$ between u and w (u and w are $\text{AD}$ nodes). Any two $\text{AD}$ nodes may have an interval of one hop or two hops. If the interval is one hop $(u\to v\to w)$ and v has the most residual energy, any of the two $\text{AD}$ nodes (u or w) can trigger $\text{TG}(u,v,w)$ event. If the interval is two hops, $\text{QG}(u,v,w)$ and $\text{QG}(u,z,w)$ are, respectively, sent to u and w. If v and z have the maximum residual energy, they are both elected as $\text{AG}$ nodes. Otherwise, u and w cooperatively select the $\text{AG}$ nodes for three-hop path $(u\to v\to z\to w)$ by Algorithm 2.

Algorithm 2: AG election subalgorithm.

Input: Given node v of a unit disk graph $$G(V,E)$$ .

Output: The node type $${\psi }_v$$ , where Ψ denotes the set of node type and $${\psi }_v\in \mathrm{\Psi }$$ .

( $$\mathit{1}$$ )    Suppose α and ρ respectively represent the sets of $$\text{AD}$$ node and $$\text{PD}$$ node;

( $$\mathit{2}$$ )    Suppose $$QG(u,v,w)$$ , $$RG(u,v,w)$$ , $$TG(u,v,w)$$ , $$TA(v)$$ respectively represent v's $$\text{AG}$$ request, $$\text{AG}$$ response, $$\text{AG}$$

  announcement and $$\text{AD}$$ announcement;

( $$\mathit{3}$$ )    Let $$\gamma (v)=\{(u\mathrm{1},v),(u\mathrm{2},v),\dots ,(uk,v)\}$$ be the ( $$\text{AD}$$ , $$\text{PD}$$ ) pairs set of v, $$k\le \mathrm{5}$$ ;

( $$\mathit{4}$$ )    Let $$\alpha (u,w)$$ be the connected relation set of $$\text{AD}$$ nodes u and w, where l is the number of elements of $$\alpha (u,w)$$ ;

( $$\mathit{5}$$ )    Let $$N_v=\{N_{\mathrm{1}},N_{\mathrm{2}},\dots ,N_m\}$$ be neighbors set of node v, where p is v's neighbors number;

( $$\mathit{6}$$ )    Let $${\text{RE}}_v$$ be the residual energy of v, and σ be the threshold value of residual energy;

( $$\mathit{7}$$ )    // $$\text{PD}$$ processing.

( $$\mathit{8}$$ )    if   $$v\in \rho$$   then

( $$\mathit{9}$$ )      //Node v broadcast the ( $$\text{AD}$$ , $$\text{PD}$$ ) pairs.

( $$\mathit{10}$$ )   if   $$TA(v)==True$$   then

(11)       $$\gamma (v)\to N_v$$ ;

(12)    end

(13)    //u, w are $$\text{AD}$$ nodes connected by v.

(14)     $$QG(u,v,w)=True$$ ; if   $$RG(u,v,w)==True$$   then

(15)       $$TG(u,v,w)=True$$ ;

(16)       $${\psi }_v$$ = 2;

( $$\mathit{17}$$ )    end

(18)    return   $${\psi }_v$$ ;

(19)  end

( $$\mathit{20}$$ ) // $$\text{AD}$$ processing.

( $$\mathit{21}$$ ) if   $$v\in \alpha$$   then

( $$\mathit{22}$$ )   if  v received $$QG(v,x,w)$$ of x  then

( $$\mathit{23}$$ )     //x is the candidate $$\text{AG}$$ of v and w.

( $$\mathit{24}$$ )     Traverse $$\alpha (v,w)$$ ;

( $$\mathit{25}$$ )     if   $${\text{RE}}_x$$ has the residual energy && $${\text{RE}}_x⩾\sigma$$   then

( $$\mathit{26}$$ )        $$RG(v,x,w)$$ = True;

( $$\mathit{27}$$ )     end

( $$\mathit{28}$$ )   end

( $$\mathit{29}$$ ) end

Time Complexity. As a distributed algorithm, the time complexity of a $\text{AD}$ election algorithm is $O(m)$ . For a $\text{PD}$ node, the time complexity of a $\text{AG}$ election algorithm is $O(m)$ . For a $\text{AD}$ node, the time complexity of a $\text{AG}$ election algorithm is $O(m)+O(l)$ . Therefore, time complexity of ANSA can be approximated as $O(n)$ .

3.3. k-Covered Mode Switching Algorithm

According to Definition 4, a k-covered $\text{UDG}$ can generate k groups of MCDS. k-covered mode switching algorithm (KMSA) motivates us to design an energy adaption strategy for node's residual energy. As Algorithm 3 shows, every node v of a k-covered UDG $G(V,E)$ holds a predefined residual energy threshold σ. If the residual energy of any node (generally $\text{AD}$ node or $\text{AG}$ node) is lower than σ, KMSA is triggered for a new MCDS building round. KMSA first empties the $\text{AD}$ and $\text{AG}$ sets and resets all the nodes’ type to $\text{PD}$ . Then, KMSA triggers Algorithms 1 and 2 to find new $\text{AD}$ and $\text{AG}$ sets. If the new α and β are not NULL, KMSA generates new MCDS which prolongs the lifetime of WSNs. However, if KMSA cannot find the new $\text{AD}$ set or $\text{AG}$ set, it will switch the type of all nodes to $\text{AD}$ .

Algorithm 3: k-covered mode switching algorithm.

Input: Given a k-covered UDG $$G(V,E)$$ .

Output: The set of node type Ψ, $${\psi }_v\in \mathrm{\Psi }$$ .

( $$\mathit{1}$$ )    Let Ψ be the set of node type and $${\psi }_v\in \mathrm{\Psi }$$ ;

( $$\mathit{2}$$ )    Let α and β be the sets of $$\text{AD}$$ node and $$\text{AG}$$ node;

( $$\mathit{3}$$ )    Let $$T_{\text{AD}}$$ and $$T_{\text{AG}}$$ be the triggers of Algorithms 1 and 2;

( $$\mathit{4}$$ )    Let $${\text{RE}}_v$$ be the residual energy of v, and σ be the threshold value of residual energy;

( $$\mathit{5}$$ )    if   $$\exists ({\text{RE}}_v<\sigma )$$   then

( $$\mathit{6}$$ )       $$\alpha =NULL$$ ;

( $$\mathit{7}$$ )       $$\beta =NULL$$ ;

( $$\mathit{8}$$ )       $$\forall {\psi }_v=\mathrm{0}$$ ;

( $$\mathit{9}$$ )       $$T_{\text{AD}}=True$$ ;

( $$\mathit{10}$$ )   if   $$\alpha \ne NULL$$   then

(11)       $$T_{\text{AG}}=True$$ ;

(12)    end

(13)    else

(14)       $$\forall {\psi }_v=\mathrm{1}$$ ;

(15)    end

(16)    if   $$\beta ==NULL$$   then

(17)       $$\forall {\psi }_v=\mathrm{1}$$ ;

(18)    end

(19)  end

( $$\mathit{20}$$ ) return  Ψ;

3.4. Power Consumption Model

In this section, we first establish the model of power consumption for CI-based flooding and then analyse the energy saving by EACIF in k-covered UDG.

Referring to Section 3.1, we define the main specifications of CI-based flooding. The unit time power consumption of Standby state, Send state, and Receive state can be, respectively, described as $E_{sd}$ , $E_{tx}$ , and $E_{rx}$ . The durations of Standby state, Send state, and Receive are $T_{sd}$ , $T_{tx}$ , and $T_{rx}$ . Other parameters include the packet length $P_l$ , the data transmission rate b, and node number n.

Glossy completes flooding after all nodes run $N\_tx$ cycles of $\text{Standby}\to \text{Receive}\to \text{Send}$ . The power consumption of Glossy ( $E_{\text{glossy}}$ ) can be expressed as

$$\begin{array}{l}{E}_{\text{glossy}}=nN\_tx\left(E_{sd}\times T_{sd}+E_{tx}\times T_{tx}+E_{rx}\times T_{rx}\right)\\ =nN\_tx\left(E_{sd}\times T_{sd}+E_{tx}\times \frac{P_l}{b}+E_{rx}\times \frac{P_l}{b}\right)\\ =nN\_tx\left(E_{sd}\times T_{sd}+\frac{P_l}{b}\left(E_{tx}+E_{rx}\right)\right).\end{array}$$

(1)

The energy consumption of active nodes is the same as Glossy, while the passive nodes only need to run $\text{Standby}\to \text{Receive}$ once. The power consumption of EACIF ( $E_{\text{eacif}}$ ) can be calculated as

$$\begin{array}{cc}& E_{\text{eacif}}=E_{\text{active}}+E_{\text{passive}},\hspace{1em}\text{where}\\ E_{\text{active}}=cN\_tx\left(E_{sd}\times T_{sd}+\frac{P_l}{b}\left(E_{tx}+E_{rx}\right)\right),\\ E_{\text{passive}}=\left(n-c\right)\left(E_{sd}\times T_{sd}+\frac{P_l}{b}{E}_{rx}\right).\end{array}$$

(2)

Here, c is the number of active nodes. $E_{\text{active}}$ and $E_{\text{passive}}$ are the energy consumption of active nodes and passive nodes, respectively. The energy saving of EACIF ( $E_{\text{saving}}$ ) can be calculated as

$$\begin{array}{l}{E}_{\text{saving}}\left(c\right)=E_{\text{glossy}}-E_{\text{eacif}}\\ =E_{\text{glossy}}-E_{\text{active}}-E_{\text{passive}}\\ =(n-c)\left(\left(N\_tx-\mathrm{1}\right)\left(E_{sd}\times T_{sd}\right)+N\_tx\frac{P_l}{b}{E}_{tx}\right.\\ \phantom{\text{hhihhhhhh}}\left.+\left(N\_tx-\mathrm{1}\right)\frac{P_l}{b}{E}_{rx}\right).\end{array}$$

(3)

Equation (3) shows that every passive node reduces ( $N\_tx-\mathrm{1}$ ) $Standby$ states, ( $N\_tx-\mathrm{1}$ ) $Receive$ states, and $N\_tx\hspace{0.17em}\hspace{0.17em}Send$ states. However, active nodes cannot save energy. EACIF can reduce energy consumption because it reduces the number of active nodes via ANSA algorithm. Moreover, suppose $\Omega =\{c_{\mathrm{1}},c_{\mathrm{2}},\dots ,c_k\}$ is the active nodes set for a k-covered UDG. Here, $c_i$ denotes the node number of active nodes in every cover set. EACIF's energy saving for k-covered UDG $\text{K}{\text{E}}_{\text{saving}}$ can be calculated as

$$\begin{array}{cc}& \text{K}{\text{E}}_{\text{saving}}={\displaystyle \sum }_{i=\mathrm{1}}^k‍E_{\text{saving}}\left(c_i\right).\end{array}$$

(4)

Equation (4) indicates that the energy saving is proportional to the redundant MCDS number k. Therefore, ECIF enables low-power network flooding in WSNs.

4. Performance

In this section, we evaluate EACIF in both real trace and uniformly distributed topology. Section 4.1 evaluates ANSA algorithm of Section 3.2. Section 4.2 measures the packet reception rate (PRR) of EACIF. Sections 4.3 and 4.4, respectively, evaluate the latency and energy consumption.

4.1. Topology Control Evaluation

We first evaluate the topology control algorithm of Section 3.2 by MATLAB 7.11 platform. We use a real trace of previous work [28] which has 1052 nodes deployed in a ten-kilometer area. As Figure 5(a) shows, all nodes labeled as $\text{PD}$ are represented by yellow. Figure 5(b) illustrates the node type after ANSA. The $\text{AD}$ nodes are represented by red, while green denotes the $\text{AG}$ nodes. Evaluation shows that ANSA selects 83 $\text{AD}$ nodes, 275 $\text{AG}$ nodes, and 694 $\text{PD}$ nodes. The nodes in the active mode are only 34.03%. It is indicated that there are 65.97% nodes working in the passive mode to save energy.

Figure 5

Active nodes selection in real traces. In (b), $\text{AD}$ nodes are marked in blue, while the red and green nodes represent $\text{AG}$ nodes and $\text{PD}$ nodes. Black lines outline the MCDS topology.

4.2. The PRR Evaluation

Figure 6 shows the evaluation of PRR. We define CI-based flooding parameters as follows: the length of packet payload is 32 bytes, the variance of clock frequency drift ${\sigma }_{\rho }=5$  ppm, the threshold of time displacement $\Delta =\mathrm{0.5}$  μs (for the IEEE 802.15.4 radio), and the period during one-hop packet reception and retransmission $T_{\text{slot}}=1.124$  ms. In the real trace of Figure 5, we change the transmission distance from 40 m to 100 m. In the uniformly distributed topology, we increase the node number varying from 500 to 2000 (referring to the scale of existing WSN-AF system). All the simulation results are averaged by 100 times.

Figure 6

The PRR evaluation.

As Figure 6(a) shows, the PRR of EACIF and Glossy are more than 97.1% ( $N\_tx=\mathrm{1}$ ). When $N\_tx=\mathrm{3}$ , both EACIF and Glossy achieve a 99.9% stability. Simulation results of uniformly distributed topology also prove that EACIF can achieve high PRR (see Figure 6(b)). However, we also note that there are lower PRR values in individual samples, especially when $N\_tx=\mathrm{1}$ . When the transmission distance is 65 m ( $N\_tx=\mathrm{1}$ ), one sample of 100 samples has 76.4th percentage of PPR (see Figure 6(a)). The reason is that EACIF reduces the amount of retransmission and also reduces opportunities to obtain the packets. The nodes in passive mode can only receive the packets from their parent nodes, while Glossy gives each node at least two chances of receiving packets, if the network degree is more than 2. Fortunately, the average PRR of EACIF is close to Glossy.

4.3. Flooding Latency Evaluation

For each node, the flooding latency is defined as the duration from $\text{SF}\_i$ event to the first successful $Rx$ event (see Table 1). Figure 7(a) shows the flooding latency of 1052 nodes in real trace ( $N\_tx=\mathrm{3}$ ). In EACIF, the latency of 263 nodes is less than 1 ms and 11.2 ms is needed for all nodes to receive packets, while Glossy spends $\mathrm{25}\%$ time more on flooding the whole network.

Figure 7

Flooding latency evaluation.

Figure 7(b) plots the flooding latency of a uniformly distributed network with 2000 nodes. Using EACIF, 125-node latency is less than 1 ms. In uniformly distributed topology, Glossy spends 27% time more than EACIF. Although Glossy is a fast CI-based flooding protocol, our evaluation results show that EACIF can flood much more quickly. This is because EACIF reduces retransmissions by constructing a sparse network topology. The simulation results indicate that EACIF can effectively resolve the scalability problem in large-scaled WSNs.

4.4. Energy Consumption Evaluation

We use the average radio on time to evaluate the energy consumption of EACIF. Figure 8(a) shows the average radio on time of real trace. When the transmission distance is increased from 40 m to 100 m, the average radio on time of Glossy changes from 22.4 ms to 19.7 ms, while the average radio on time in EACIF changes from 15.1 ms to 7.1 ms. When the transmission distance is 100 m, EACIF can save 63.96% more energy consumption than Glossy. Figure 8(a) indicates that EACIF's effect of energy saving is proportional to network density. Simulation results verify the indication of (4).

Figure 8

Average radio on time evaluation.

In Figure 8(b), the node number increases from 500 to 2000. The average radio on time of Glossy has 31.2% increasement. It means that Glossy suffers scalability problem. However, the average radio on time of EACIF has a slight decrease. When the node number is 2000, the average radio on time of EACIF is 11.2 ms. We assume that a WSN-AF system sends a packet every 30 seconds. The duty cycle of EACIF is 0.11%.

5. Conclusions and Future Work

In this paper, we introduce EACIF, the first work to improve energy adaptivity of CI-based flooding. We first implement ASNA to construct a sparse backbone on a given topology. Then, we propose KMSA algorithm to control the flooding process. We experimentally validate the performance of EACIF on real trace and the uniformly distributed topology. Simulation results indicate that EACIF can efficiently reduce redundancy retransmissions and significantly reduce energy consumption. Our future work includes the performance measurements of EACIF in real-world large-scale WSN-AF and the exploitation of EACIF in wireless time synchronization and remote reprogramming.