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

Authors: Dapeng Cheng; Yanyan Mao; Yin Wang; Xiangrong Wang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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), O2 concentration, CO2 concentration [3], and ethylene (C2H4) 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 Figure1. In this example, S1, S2, S3, S4, S5 and R1 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 S1, S2, S3, S4, S5 can be expressed as Ns1={S5,S4,R1}, Ns2={S3,S4,R1}, Ns3={S2,S5,R1}, Ns4={S2,S1,R1}, and Ns5={S1,S3,R1}. As the most common behavior of CI-based flooding, S1, S2, S3, S4, S5 are forwarding an identical packet to R1 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 Er1, Er2, Er3, Er4, and Er5. The residual energy of each candidate sender and its neighbors is as follows: Es1={Er1,Er5,Er4}, Es2={Er2,Er3,Er4}, Es3={Er2,Er3,Er5}, Es4={Er1,Er2,Er4}, and Es5={Er1,Er3,Er5}. Then we have Er1>Er2>Er3>Er4>Er5. Each node independently selects the node which has the largest residual energy from Esi(i=1,…,5). For the example in Figure 1, S1 and S2 are selected as the final senders. S3, S4, and S5 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 {S1,S2} and {S4,S5}. Network lifetime can be greatly extended by energy adaptive scheduling {S1,S2} (red arrows in Figure 1) or {S4,S5} (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 thefirst to propose a lightweight distributedenergy 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 approximateminimum connected dominating set (MCDS) algorithm, which can be completed approximately in O(n).(iii)
EACIF proposes ak-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 Section2. 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; S1, S2, and R all employ IEEE 802.15.4 radios. The packets (Ps1 and Ps2) with the same data are, respectively, transmitted from S1 and S2 to R. R can decode the Ps1 and Ps2 as one packet if the maximum temporal displacement Δ of Ps1 and Ps2 is no more than one chip period Tc=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 (Δ≤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 Table1. 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 SF_i denote the node that becomes an initiator and SF_r let denote the node that becomes a receiver. SF_i and 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
T
x
Transmitting event
R
x
Receiving event
SF
r
Start flooding event for receiver
SF
i
Start flooding event for initiator
S
t
o
p
Stop flooding event
C
_
t
x
Transmission counter
N
_
t
x
Transmission threshold
R
x
_
f
Rx failed event
c
Relay counterAs Figure3 shows, CI-based flooding has four correlative states includingRadio off state,Standby state,Send state, andReceive state. When SF_i event happens, the initiator transforms fromRadio off state intoSend state. Then the initiator triggers the Tx event to send a flooding packet to its one-hop neighbors. When SF_r event happens, the nodes except the initiator enter theStandby state to wait for the incoming packets. When Rx event happens, the node switches toReceive state and starts to decode the received packet. If the reception is successful, ++c is performed. Meanwhile, the node shifts toSend state for new transmitting round. In contrast, if Rx_f happens (Δ≥0.5 μs), the node converts intoStandby state for the next receiving round. After Tx event is completed, the node has two candidate states: theStandby state and theRadio off state. If C_tx is less than N_tx, the node will turn toStandby state to wait for the new Rx event. If C_tx reaches N_tx, the node will turn toRadio 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.Table2 shows the energy consumption of a typical IEEE 802.15.4 compliant radio CC2420 [25]. The power consumption ofSend state andReceive state is at milliampere level, whileRadio off state andStandby state only consume microampere-level power. Obviously, CI-based flooding should convert the nodes toSend state andReceive state as seldom as possible. As a topology independent CI-based flooding protocol, Glossy employs all nodes in WSNs looping inStandby→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 toRadio off state to save energy. If the reception has failed, the node will turn toStandby 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
μAThe scenario shown in Figure4 illustrates the flooding process of EACIF when N_tx=1. Suppose an even-distributed WSN which has 25 nodes. Here, node I is the initiator; A1, A2, A3, and A4 are working in active mode, while P1,…,P20 are working in passive mode. When the 1st transmission round begins, I broadcasts a packet to its one-hop neighbors A1, A2, A3, A4, P1, P2, P3, and P4. Upon receiving the packet, P1, P2, P3, and P4 enter theRadio off state to save energy. Only A1, A2, A3, and A4 participate in the 2nd transmission round. All the peripheral nodes (P5,…,P20) 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=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 ofn 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 graphG=(V,E), for ∀u, v∈V, if (u,v)∈E and ∃(|uv|⩽1), then G is a unit disk graph UDG(V,E).Definition 2.
InUDG(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.
InUDG(V,E), a set C∈V is a connected dominating set (CDS) if the subgraph derived by C is a connected graph. For ∀c∈C, if C-{c} is not a CDS, then C is a minimal connected dominating set (MCDS).Definition 4.
AUDG(V,E) is a k-covered UDG if it contains k groups of mutually disjoint MCDS.We call the nodes inD “active dominators” (AD). The gateway nodes converting DS to CDS are called “active gateways” (AG). The nodes outside CDS are called “passive dominatees” (PD).


#### 3.2.2. Active Nodes Selection Algorithm

Enlightened by Section3.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.Definitions2 and 3 indicate that “active nodes” include the AD nodes and the AG nodes. Therefore, ANSA can be divided into two subalgorithms: AD election subalgorithm and AG election subalgorithm.AD Election Subalgorithm.
AD election subalgorithm constructs a CDS of a given topology. As Algorithm 1 shows, ψv denotes the type of node v. The type of v is AD if ψv equals 1, while ψv=0 indicates that the node is a PD. If v is a AG, ψ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 (QA(v)==True) if it wants to be a AG. The request packets contain the residual energy of node v. Then, its neighbor nodes (Nv) send response packets to v. When receiving the responses (RA(v)==True), v compares its residual energy (REv) with the residual energy set NEv. Node v is elected as AG if and only if v has the maximum residual energy. Finally, v sets its node type and triggers TA(v) event to send the declaring packets. After AD election subalgorithm, each node in G(V,E) is either a AG or a PG.Algorithm 1:AD election algorithm.
Input: Given a node v of a unit disk graph G(V,E), v∈V.
Output: The node type ψv, where Ψ denotes the set of node type and ψv∈Ψ.
(1)    Suppose QA(v), TA(v), RA(v), REv respectively represent AD request, AD announcement, the AD response and the
residual energy ofv;
(2)    Let Nv={N1,N2,…,Nm} be neighbors set of node v, where p is v’s neighbors number;
(3)    Let NEv={NE1,NE2,…,NEm} be the residual energy set of Nv;
(4)    Let σ be the threshold of residual energy;
(5)    //Set all the node type into PD.
(6)    ψv=0;
(7)    c=1;
(8)    //Node v initiatively apply to become a AD.
(9)    if  QA(v)==True && REv⩾σ  then
(10)  //Node v sends the residual energy to its one-hop neighbors.
(11)   REv→Nv;
(12)  end
(13)  //Node v receives residual energy from its one-hop neighbors.
(14)  else if  RA(v)==True  then
(15)   for  i=1:m  do
(16)    if  REv<NEi  then
(17)     break;
(18)    end
(19)    c++;
(20)  end
(21)  if  c==m  then
(22)   ψv = 1;
(23)   //Declaring v as an AD node.
(24)   TA(v)=True;
(25)  end
(26) end
(27) return  ψv;AG Election Subalgorithm. As Algorithm 2 shows, all PD nodes first broadcast their (AD,PD) pairs. Alzoubi et al. [27] have proved that a PD of UDG(V,E) has at most five AD nodes. After gathering two-hop AD nodes information, a PD node v can broadcast AG request (QG(u,v,w)) applying to be AG between u and w (u and w are AD nodes). Any two AD nodes may have an interval of one hop or two hops. If the interval is one hop (u→v→w) and v has the most residual energy, any of the two AD nodes (u or w) can trigger TG(u,v,w) event. If the interval is two hops, QG(u,v,w) and 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 AG nodes. Otherwise, u and w cooperatively select the AG nodes for three-hop path (u→v→z→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 ψv, where Ψ denotes the set of node type and ψv∈Ψ.
(1)    Suppose α and ρ respectively represent the sets of AD node and PD node;
(2)    Suppose QG(u,v,w), RG(u,v,w), TG(u,v,w), TA(v) respectively represent v’s AG request, AG response, AG
announcement andAD announcement;
(3)    Let γ(v)={(u1,v),(u2,v),…,(uk,v)} be the (AD, PD) pairs set of v, k≤5;
(4)    Let α(u,w) be the connected relation set of AD nodes u and w, where l is the number of elements of α(u,w);
(5)    Let Nv={N1,N2,…,Nm} be neighbors set of node v, where p is v’s neighbors number;
(6)    Let REv be the residual energy of v, and σ be the threshold value of residual energy;
(7)    //PD processing.
(8)    if  v∈ρ  then
(9)     //Node v broadcast the (AD, PD) pairs.
(10)  if  TA(v)==True  then
(11)    γ(v)→Nv;
(12)   end
(13)   //u, w are 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)    ψv = 2;
(17)   end
(18)   return  ψv;
(19)  end
(20) //AD processing.
(21) if  v∈α  then
(22)  if  v received QG(v,x,w) of x  then
(23)   //x is the candidate AG of v and w.
(24)   Traverse α(v,w);
(25)   if  REx has the residual energy && REx⩾σ  then
(26)    RG(v,x,w) = True;
(27)   end
(28)  end
(29) endTime Complexity. As a distributed algorithm, the time complexity of a AD election algorithm is O(m). For a PD node, the time complexity of a AG election algorithm is O(m). For a AD node, the time complexity of a 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 Definition4, a k-covered 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 AD node or AG node) is lower than σ, KMSA is triggered for a new MCDS building round. KMSA first empties the AD and AG sets and resets all the nodes’ type to PD. Then, KMSA triggers Algorithms 1 and 2 to find new AD and 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 AD set or AG set, it will switch the type of all nodes to AD.Algorithm 3:
k-covered mode switching algorithm.
Input: Given a k-covered UDG G(V,E).
Output: The set of node type Ψ, ψv∈Ψ.
(1)    Let Ψ be the set of node type and ψv∈Ψ;
(2)    Let α and β be the sets of AD node and AG node;
(3)    Let TAD and TAG be the triggers of Algorithms 1 and 2;
(4)    Let REv be the residual energy of v, and σ be the threshold value of residual energy;
(5)    if  ∃(REv<σ)  then
(6)     α=NULL;
(7)     β=NULL;
(8)     ∀ψv=0;
(9)     TAD=True;
(10)  if  α≠NULL  then
(11)    TAG=True;
(12)   end
(13)   else
(14)    ∀ψv=1;
(15)   end
(16)   if  β==NULL  then
(17)    ∀ψv=1;
(18)   end
(19)  end
(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 ink-covered UDG.Referring to Section3.1, we define the main specifications of CI-based flooding. The unit time power consumption ofStandby state,Send state, andReceive state can be, respectively, described as Esd, Etx, and Erx. The durations ofStandby state,Send state, andReceive are Tsd, Ttx, and Trx. Other parameters include the packet length Pl, the data transmission rate b, and node number n.Glossy completes flooding after all nodes runN_tx cycles of Standby→Receive→Send. The power consumption of Glossy (Eglossy) can be expressed as(1)Eglossy=nN_txEsd×Tsd+Etx×Ttx+Erx×Trx=nN_txEsd×Tsd+Etx×Plb+Erx×Plb=nN_txEsd×Tsd+PlbEtx+Erx.The energy consumption of active nodes is the same as Glossy, while the passive nodes only need to runStandby→Receive once. The power consumption of EACIF (Eeacif) can be calculated as(2)Eeacif=Eactive+Epassive,whereEactive=cN_txEsd×Tsd+PlbEtx+Erx,Epassive=n-cEsd×Tsd+PlbErx.Here, c is the number of active nodes. Eactive and Epassive are the energy consumption of active nodes and passive nodes, respectively. The energy saving of EACIF (Esaving) can be calculated as(3)Esavingc=Eglossy-Eeacif=Eglossy-Eactive-Epassive=(n-c)N_tx-1Esd×Tsd+N_txPlbEtxhhihhhhhh+N_tx-1PlbErx.Equation (3) shows that every passive node reduces (N_tx-1) Standby states, (N_tx-1) Receive states, and N_txSend 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 Ω={c1,c2,…,ck} is the active nodes set for a k-covered UDG. Here, ci denotes the node number of active nodes in every cover set. EACIF’s energy saving for k-covered UDG KEsaving can be calculated as (4)KEsaving=∑i=1k‍Esavingci.Equation (4) indicates that the energy saving is proportional to the redundant MCDS number k. Therefore, ECIF enables low-power network flooding in WSNs.


## 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 Table1. 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 SF_i denote the node that becomes an initiator and SF_r let denote the node that becomes a receiver. SF_i and 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
T
x
Transmitting event
R
x
Receiving event
SF
r
Start flooding event for receiver
SF
i
Start flooding event for initiator
S
t
o
p
Stop flooding event
C
_
t
x
Transmission counter
N
_
t
x
Transmission threshold
R
x
_
f
Rx failed event
c
Relay counterAs Figure3 shows, CI-based flooding has four correlative states includingRadio off state,Standby state,Send state, andReceive state. When SF_i event happens, the initiator transforms fromRadio off state intoSend state. Then the initiator triggers the Tx event to send a flooding packet to its one-hop neighbors. When SF_r event happens, the nodes except the initiator enter theStandby state to wait for the incoming packets. When Rx event happens, the node switches toReceive state and starts to decode the received packet. If the reception is successful, ++c is performed. Meanwhile, the node shifts toSend state for new transmitting round. In contrast, if Rx_f happens (Δ≥0.5 μs), the node converts intoStandby state for the next receiving round. After Tx event is completed, the node has two candidate states: theStandby state and theRadio off state. If C_tx is less than N_tx, the node will turn toStandby state to wait for the new Rx event. If C_tx reaches N_tx, the node will turn toRadio 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.Table2 shows the energy consumption of a typical IEEE 802.15.4 compliant radio CC2420 [25]. The power consumption ofSend state andReceive state is at milliampere level, whileRadio off state andStandby state only consume microampere-level power. Obviously, CI-based flooding should convert the nodes toSend state andReceive state as seldom as possible. As a topology independent CI-based flooding protocol, Glossy employs all nodes in WSNs looping inStandby→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 toRadio off state to save energy. If the reception has failed, the node will turn toStandby 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
μAThe scenario shown in Figure4 illustrates the flooding process of EACIF when N_tx=1. Suppose an even-distributed WSN which has 25 nodes. Here, node I is the initiator; A1, A2, A3, and A4 are working in active mode, while P1,…,P20 are working in passive mode. When the 1st transmission round begins, I broadcasts a packet to its one-hop neighbors A1, A2, A3, A4, P1, P2, P3, and P4. Upon receiving the packet, P1, P2, P3, and P4 enter theRadio off state to save energy. Only A1, A2, A3, and A4 participate in the 2nd transmission round. All the peripheral nodes (P5,…,P20) 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=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 ofn 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 graphG=(V,E), for ∀u, v∈V, if (u,v)∈E and ∃(|uv|⩽1), then G is a unit disk graph UDG(V,E).Definition 2.
InUDG(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.
InUDG(V,E), a set C∈V is a connected dominating set (CDS) if the subgraph derived by C is a connected graph. For ∀c∈C, if C-{c} is not a CDS, then C is a minimal connected dominating set (MCDS).Definition 4.
AUDG(V,E) is a k-covered UDG if it contains k groups of mutually disjoint MCDS.We call the nodes inD “active dominators” (AD). The gateway nodes converting DS to CDS are called “active gateways” (AG). The nodes outside CDS are called “passive dominatees” (PD).


### 3.2.2. Active Nodes Selection Algorithm

Enlightened by Section3.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.Definitions2 and 3 indicate that “active nodes” include the AD nodes and the AG nodes. Therefore, ANSA can be divided into two subalgorithms: AD election subalgorithm and AG election subalgorithm.AD Election Subalgorithm.
AD election subalgorithm constructs a CDS of a given topology. As Algorithm 1 shows, ψv denotes the type of node v. The type of v is AD if ψv equals 1, while ψv=0 indicates that the node is a PD. If v is a AG, ψ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 (QA(v)==True) if it wants to be a AG. The request packets contain the residual energy of node v. Then, its neighbor nodes (Nv) send response packets to v. When receiving the responses (RA(v)==True), v compares its residual energy (REv) with the residual energy set NEv. Node v is elected as AG if and only if v has the maximum residual energy. Finally, v sets its node type and triggers TA(v) event to send the declaring packets. After AD election subalgorithm, each node in G(V,E) is either a AG or a PG.Algorithm 1:AD election algorithm.
Input: Given a node v of a unit disk graph G(V,E), v∈V.
Output: The node type ψv, where Ψ denotes the set of node type and ψv∈Ψ.
(1)    Suppose QA(v), TA(v), RA(v), REv respectively represent AD request, AD announcement, the AD response and the
residual energy ofv;
(2)    Let Nv={N1,N2,…,Nm} be neighbors set of node v, where p is v’s neighbors number;
(3)    Let NEv={NE1,NE2,…,NEm} be the residual energy set of Nv;
(4)    Let σ be the threshold of residual energy;
(5)    //Set all the node type into PD.
(6)    ψv=0;
(7)    c=1;
(8)    //Node v initiatively apply to become a AD.
(9)    if  QA(v)==True && REv⩾σ  then
(10)  //Node v sends the residual energy to its one-hop neighbors.
(11)   REv→Nv;
(12)  end
(13)  //Node v receives residual energy from its one-hop neighbors.
(14)  else if  RA(v)==True  then
(15)   for  i=1:m  do
(16)    if  REv<NEi  then
(17)     break;
(18)    end
(19)    c++;
(20)  end
(21)  if  c==m  then
(22)   ψv = 1;
(23)   //Declaring v as an AD node.
(24)   TA(v)=True;
(25)  end
(26) end
(27) return  ψv;AG Election Subalgorithm. As Algorithm 2 shows, all PD nodes first broadcast their (AD,PD) pairs. Alzoubi et al. [27] have proved that a PD of UDG(V,E) has at most five AD nodes. After gathering two-hop AD nodes information, a PD node v can broadcast AG request (QG(u,v,w)) applying to be AG between u and w (u and w are AD nodes). Any two AD nodes may have an interval of one hop or two hops. If the interval is one hop (u→v→w) and v has the most residual energy, any of the two AD nodes (u or w) can trigger TG(u,v,w) event. If the interval is two hops, QG(u,v,w) and 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 AG nodes. Otherwise, u and w cooperatively select the AG nodes for three-hop path (u→v→z→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 ψv, where Ψ denotes the set of node type and ψv∈Ψ.
(1)    Suppose α and ρ respectively represent the sets of AD node and PD node;
(2)    Suppose QG(u,v,w), RG(u,v,w), TG(u,v,w), TA(v) respectively represent v’s AG request, AG response, AG
announcement andAD announcement;
(3)    Let γ(v)={(u1,v),(u2,v),…,(uk,v)} be the (AD, PD) pairs set of v, k≤5;
(4)    Let α(u,w) be the connected relation set of AD nodes u and w, where l is the number of elements of α(u,w);
(5)    Let Nv={N1,N2,…,Nm} be neighbors set of node v, where p is v’s neighbors number;
(6)    Let REv be the residual energy of v, and σ be the threshold value of residual energy;
(7)    //PD processing.
(8)    if  v∈ρ  then
(9)     //Node v broadcast the (AD, PD) pairs.
(10)  if  TA(v)==True  then
(11)    γ(v)→Nv;
(12)   end
(13)   //u, w are 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)    ψv = 2;
(17)   end
(18)   return  ψv;
(19)  end
(20) //AD processing.
(21) if  v∈α  then
(22)  if  v received QG(v,x,w) of x  then
(23)   //x is the candidate AG of v and w.
(24)   Traverse α(v,w);
(25)   if  REx has the residual energy && REx⩾σ  then
(26)    RG(v,x,w) = True;
(27)   end
(28)  end
(29) endTime Complexity. As a distributed algorithm, the time complexity of a AD election algorithm is O(m). For a PD node, the time complexity of a AG election algorithm is O(m). For a AD node, the time complexity of a AG election algorithm is O(m)+O(l). Therefore, time complexity of ANSA can be approximated as O(n).


## 3.2.1. Geometric Definitions

We assume a WSN consisting ofn 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 graphG=(V,E), for ∀u, v∈V, if (u,v)∈E and ∃(|uv|⩽1), then G is a unit disk graph UDG(V,E).Definition 2.
InUDG(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.
InUDG(V,E), a set C∈V is a connected dominating set (CDS) if the subgraph derived by C is a connected graph. For ∀c∈C, if C-{c} is not a CDS, then C is a minimal connected dominating set (MCDS).Definition 4.
AUDG(V,E) is a k-covered UDG if it contains k groups of mutually disjoint MCDS.We call the nodes inD “active dominators” (AD). The gateway nodes converting DS to CDS are called “active gateways” (AG). The nodes outside CDS are called “passive dominatees” (PD).


## 3.2.2. Active Nodes Selection Algorithm

Enlightened by Section3.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.Definitions2 and 3 indicate that “active nodes” include the AD nodes and the AG nodes. Therefore, ANSA can be divided into two subalgorithms: AD election subalgorithm and AG election subalgorithm.AD Election Subalgorithm.
AD election subalgorithm constructs a CDS of a given topology. As Algorithm 1 shows, ψv denotes the type of node v. The type of v is AD if ψv equals 1, while ψv=0 indicates that the node is a PD. If v is a AG, ψ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 (QA(v)==True) if it wants to be a AG. The request packets contain the residual energy of node v. Then, its neighbor nodes (Nv) send response packets to v. When receiving the responses (RA(v)==True), v compares its residual energy (REv) with the residual energy set NEv. Node v is elected as AG if and only if v has the maximum residual energy. Finally, v sets its node type and triggers TA(v) event to send the declaring packets. After AD election subalgorithm, each node in G(V,E) is either a AG or a PG.Algorithm 1:AD election algorithm.
Input: Given a node v of a unit disk graph G(V,E), v∈V.
Output: The node type ψv, where Ψ denotes the set of node type and ψv∈Ψ.
(1)    Suppose QA(v), TA(v), RA(v), REv respectively represent AD request, AD announcement, the AD response and the
residual energy ofv;
(2)    Let Nv={N1,N2,…,Nm} be neighbors set of node v, where p is v’s neighbors number;
(3)    Let NEv={NE1,NE2,…,NEm} be the residual energy set of Nv;
(4)    Let σ be the threshold of residual energy;
(5)    //Set all the node type into PD.
(6)    ψv=0;
(7)    c=1;
(8)    //Node v initiatively apply to become a AD.
(9)    if  QA(v)==True && REv⩾σ  then
(10)  //Node v sends the residual energy to its one-hop neighbors.
(11)   REv→Nv;
(12)  end
(13)  //Node v receives residual energy from its one-hop neighbors.
(14)  else if  RA(v)==True  then
(15)   for  i=1:m  do
(16)    if  REv<NEi  then
(17)     break;
(18)    end
(19)    c++;
(20)  end
(21)  if  c==m  then
(22)   ψv = 1;
(23)   //Declaring v as an AD node.
(24)   TA(v)=True;
(25)  end
(26) end
(27) return  ψv;AG Election Subalgorithm. As Algorithm 2 shows, all PD nodes first broadcast their (AD,PD) pairs. Alzoubi et al. [27] have proved that a PD of UDG(V,E) has at most five AD nodes. After gathering two-hop AD nodes information, a PD node v can broadcast AG request (QG(u,v,w)) applying to be AG between u and w (u and w are AD nodes). Any two AD nodes may have an interval of one hop or two hops. If the interval is one hop (u→v→w) and v has the most residual energy, any of the two AD nodes (u or w) can trigger TG(u,v,w) event. If the interval is two hops, QG(u,v,w) and 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 AG nodes. Otherwise, u and w cooperatively select the AG nodes for three-hop path (u→v→z→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 ψv, where Ψ denotes the set of node type and ψv∈Ψ.
(1)    Suppose α and ρ respectively represent the sets of AD node and PD node;
(2)    Suppose QG(u,v,w), RG(u,v,w), TG(u,v,w), TA(v) respectively represent v’s AG request, AG response, AG
announcement andAD announcement;
(3)    Let γ(v)={(u1,v),(u2,v),…,(uk,v)} be the (AD, PD) pairs set of v, k≤5;
(4)    Let α(u,w) be the connected relation set of AD nodes u and w, where l is the number of elements of α(u,w);
(5)    Let Nv={N1,N2,…,Nm} be neighbors set of node v, where p is v’s neighbors number;
(6)    Let REv be the residual energy of v, and σ be the threshold value of residual energy;
(7)    //PD processing.
(8)    if  v∈ρ  then
(9)     //Node v broadcast the (AD, PD) pairs.
(10)  if  TA(v)==True  then
(11)    γ(v)→Nv;
(12)   end
(13)   //u, w are 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)    ψv = 2;
(17)   end
(18)   return  ψv;
(19)  end
(20) //AD processing.
(21) if  v∈α  then
(22)  if  v received QG(v,x,w) of x  then
(23)   //x is the candidate AG of v and w.
(24)   Traverse α(v,w);
(25)   if  REx has the residual energy && REx⩾σ  then
(26)    RG(v,x,w) = True;
(27)   end
(28)  end
(29) endTime Complexity. As a distributed algorithm, the time complexity of a AD election algorithm is O(m). For a PD node, the time complexity of a AG election algorithm is O(m). For a AD node, the time complexity of a 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 Definition4, a k-covered 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 AD node or AG node) is lower than σ, KMSA is triggered for a new MCDS building round. KMSA first empties the AD and AG sets and resets all the nodes’ type to PD. Then, KMSA triggers Algorithms 1 and 2 to find new AD and 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 AD set or AG set, it will switch the type of all nodes to AD.Algorithm 3:
k-covered mode switching algorithm.
Input: Given a k-covered UDG G(V,E).
Output: The set of node type Ψ, ψv∈Ψ.
(1)    Let Ψ be the set of node type and ψv∈Ψ;
(2)    Let α and β be the sets of AD node and AG node;
(3)    Let TAD and TAG be the triggers of Algorithms 1 and 2;
(4)    Let REv be the residual energy of v, and σ be the threshold value of residual energy;
(5)    if  ∃(REv<σ)  then
(6)     α=NULL;
(7)     β=NULL;
(8)     ∀ψv=0;
(9)     TAD=True;
(10)  if  α≠NULL  then
(11)    TAG=True;
(12)   end
(13)   else
(14)    ∀ψv=1;
(15)   end
(16)   if  β==NULL  then
(17)    ∀ψv=1;
(18)   end
(19)  end
(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 ink-covered UDG.Referring to Section3.1, we define the main specifications of CI-based flooding. The unit time power consumption ofStandby state,Send state, andReceive state can be, respectively, described as Esd, Etx, and Erx. The durations ofStandby state,Send state, andReceive are Tsd, Ttx, and Trx. Other parameters include the packet length Pl, the data transmission rate b, and node number n.Glossy completes flooding after all nodes runN_tx cycles of Standby→Receive→Send. The power consumption of Glossy (Eglossy) can be expressed as(1)Eglossy=nN_txEsd×Tsd+Etx×Ttx+Erx×Trx=nN_txEsd×Tsd+Etx×Plb+Erx×Plb=nN_txEsd×Tsd+PlbEtx+Erx.The energy consumption of active nodes is the same as Glossy, while the passive nodes only need to runStandby→Receive once. The power consumption of EACIF (Eeacif) can be calculated as(2)Eeacif=Eactive+Epassive,whereEactive=cN_txEsd×Tsd+PlbEtx+Erx,Epassive=n-cEsd×Tsd+PlbErx.Here, c is the number of active nodes. Eactive and Epassive are the energy consumption of active nodes and passive nodes, respectively. The energy saving of EACIF (Esaving) can be calculated as(3)Esavingc=Eglossy-Eeacif=Eglossy-Eactive-Epassive=(n-c)N_tx-1Esd×Tsd+N_txPlbEtxhhihhhhhh+N_tx-1PlbErx.Equation (3) shows that every passive node reduces (N_tx-1) Standby states, (N_tx-1) Receive states, and N_txSend 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 Ω={c1,c2,…,ck} is the active nodes set for a k-covered UDG. Here, ci denotes the node number of active nodes in every cover set. EACIF’s energy saving for k-covered UDG KEsaving can be calculated as (4)KEsaving=∑i=1k‍Esavingci.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. Section4.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 Section3.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 PD are represented by yellow. Figure 5(b) illustrates the node type after ANSA. The AD nodes are represented by red, while green denotes the AG nodes. Evaluation shows that ANSA selects 83 AD nodes, 275 AG nodes, and 694 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),AD nodes are marked in blue, while the red and green nodes represent AG nodes and PD nodes. Black lines outline the MCDS topology.
(a)
Original topology
(b)
The generated MCDS


### 4.2. The PRR Evaluation

Figure6 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 σρ=5 ppm, the threshold of time displacement Δ=0.5 μs (for the IEEE 802.15.4 radio), and the period during one-hop packet reception and retransmission Tslot=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.
(a)
PRR of real trace
(b)
PRR of uniformly distributed topologyAs Figure6(a) shows, the PRR of EACIF and Glossy are more than 97.1% (N_tx=1). When N_tx=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=1. When the transmission distance is 65 m (N_tx=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 fromSF_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=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 25% time more on flooding the whole network.Figure 7
Flooding latency evaluation.
(a)
Node latency of real trace
(b)
Node latency of uniformly distributed topology (node number = 2000)Figure7(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. Figure8(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.
(a)
Average radio on time of real trace
(b)
Average radio on time of uniformly distributed topologyIn Figure8(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%.


## 4.1. Topology Control Evaluation

We first evaluate the topology control algorithm of Section3.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 PD are represented by yellow. Figure 5(b) illustrates the node type after ANSA. The AD nodes are represented by red, while green denotes the AG nodes. Evaluation shows that ANSA selects 83 AD nodes, 275 AG nodes, and 694 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),AD nodes are marked in blue, while the red and green nodes represent AG nodes and PD nodes. Black lines outline the MCDS topology.
(a)
Original topology
(b)
The generated MCDS


## 4.2. The PRR Evaluation

Figure6 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 σρ=5 ppm, the threshold of time displacement Δ=0.5 μs (for the IEEE 802.15.4 radio), and the period during one-hop packet reception and retransmission Tslot=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.
(a)
PRR of real trace
(b)
PRR of uniformly distributed topologyAs Figure6(a) shows, the PRR of EACIF and Glossy are more than 97.1% (N_tx=1). When N_tx=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=1. When the transmission distance is 65 m (N_tx=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 fromSF_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=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 25% time more on flooding the whole network.Figure 7
Flooding latency evaluation.
(a)
Node latency of real trace
(b)
Node latency of uniformly distributed topology (node number = 2000)Figure7(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. Figure8(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.
(a)
Average radio on time of real trace
(b)
Average radio on time of uniformly distributed topologyIn Figure8(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.



---

*Source: 538145-2015-06-16.xml*