Delay-constrained flooding in extremely low-duty-cycle sensor networks

Abstract

Flooding is a fundamental function for the network-wide dissemination of command, query, and code update in wireless sensor networks. However, it is challenging to enable fast and energy-efficient flooding in sensor networks with low-duty cycles because it is rare that multiple neighboring nodes wake up at the same time, making broadcast instinct of wireless radio unavailable. The unreliability of wireless links deteriorates the situation. In this work, we study the delay-constrained flooding problem in order to disseminate data packets to all nodes within given expected delivery delay. In particular, a transmission power control–based flooding algorithm is proposed to reduce the flooding delay in such low-duty-cycle sensor networks. According to the soft delay bound, each node can locally adjust its transmission power level. To alleviate transmission conflicts, the backoff method with transmission power adaptive mechanism has been proposed. Based on the large-scale simulations, we validate that our design can reduce flooding delay with small extra energy expenditure compared with conventional flooding schemes.

Keywords

Sensor networks low-duty-cycle flooding transmission power control

Introduction

Multihop flooding is a fundamental network functionality in large-scale wireless networks, in which data packets are sent out from one control center to spread throughout the whole field in a multihop way. For example, sink node disseminates messages including update code to all sensor nodes in order to upgrade their firmware in large-scale sensor networks. In conventional networks, flooding algorithms are usually performed in a broadcasting or multicasting way by taking advantage of the broadcasting nature of wireless radio, that is, a single transmission could be heard and received by multiple neighbors within the sender’s communication range.

However, there are several challenges to enable flooding in extremely low-duty-cycle sensor networks, where duty-cycling operation is introduced to save energy. Under low-duty-cycle model, nodes are set to switch between the active and the dormant states periodically. The ratio of active state over the whole period is referred to as duty cycle, which is usually extremely low (less than 1% work period) for energy conservation. Consequently, network connectivity is time-dependent and it is rare that multiple receivers wake up at the same time, which makes broadcast unavailable and leads to a very long flooding delay when the sender has to wait the wake-up of its receivers. For example, if node S in Figure 1 wants to send data packet to its neighbors B and C, it can broadcast the packet in an always-on network. However, it is unworkable in low-duty-cycle sensor networks since nodes B and C may stay in dormant state and wake up asynchronously. Moreover, the unreliability of wireless link may defer flooding process and incur more energy consumption because redundant transmissions happen in case of delivery failures.

Figure 1.

Flooding process in low-duty-cycle sensor networks.

Therefore, most work conduct single-hop flooding by a number of unicasts in low-duty-cycle sensor networks.¹ In the above example, the sink sends data packets sequentially in the order of their wake-ups. Assuming perfect wireless links, node S transmits the packet to node C at time 7 and then retransmits to node B at time 8. In multihop flooding, the situation can be complicated due to unreliable link and redundant transmissions. Based on the locality of spatiotemporal correlation, researchers have proposed opportunistic forwarding to enable efficient flooding. Specially, network-wide flooding is usually performed based on a constructed tree² or a directed acyclic graph (DAG) topology.^1,3 Based on the structure, the flooding delay of the whole network can be defined as the delivery delay along with the longest flooding path in a tree or DAG. For example, the flooding delay in Figure 1 is the delivery delay enduring from the sink S to node G. Tree-based flooding has been shown to be efficient in that (1) it is easy to align the active slots of the sender and receiver with different work schedule so that energy consumed by idle listening could be reduced and (2) it is time-efficient if each node receives the flooding packet with minimum delay.³ However, such flooding schemes could suffer from an extremely long delay because a few nodes with bad link may fail to forward data packets and then defer the flooding process for its subtree nodes. It is particularly evident in nonuniform distributed (partially sparse) sensor networks.

In this article, we study the optimization of flooding problem by introducing transmission power control mechanism into tree-based structure in extremely low-duty-cycle sensor network. We construct a minimum spanning tree based on the expected flooding delay (EFD) and then propose on-demand transmission power augmentation algorithm to meet the given delay constraint with less energy consumption. Compared with the present work, our design fully utilize the power control capability of sensor nodes to exploit more reliable forwarding opportunities. As a result, our design can greatly reduce flooding delay even in sparse deployment with low connectivity. It is worth mentioning that the main concern in traditional power control design is how to decide the approximate transmission power level so that wireless interferences among neighboring nodes could be minimized. Instead, our design is based on the observation that increasing transmission power may bring more forwarding opportunities in such time-dependent connected networks.

Our contributions in this work include several folds. (1) This is the first attempt to utilize transmission power control mechanism to reduce flooding delay in extremely low-duty-cycle sensor networks. (2) We present a delay-constrained flooding (DCF) scheme. The main idea is to first build an expected delay-minimized spanning tree under fixed transmission power level, and then adjust transmission power on demand to bound the flooding delay. (3) Large-scale simulations are performed to validate our design. Compared with the state-of-the-art flooding schemes, our design can greatly reduce flooding delay at little extra energy cost.

The rest of the article is organized as follows. Section “Related works” discusses the related work. We define the network model and problem in section “Preliminaries.” The concrete design of our scheme is discussed in section “DCF scheme,” and the simulation results are presented in section “Performance evaluation.” Section “Conclusion” concludes the article.

Related works

In large-scale sensor networks, power supply has become the main concern and brought many design considerations, such as reliability, latency, and scalability. Working with various sleep scheduling, probability-based broadcast forwarding (PBBF)⁴ is a medium access control (MAC) layer solution for flooding by adjusting corresponding parameters to trade-off energy, latency, and delivery reliability.

The introduction of duty-cycle operations has brought great improvement in energy efficiency, but incurred long delivery delay. Some underneath protocols have been developed to enable the broadcasting in such duty-cycle sensor networks. Xu et al.⁵ study the optimization of energy-efficient broadcast subjected to the delay constraint, which has the same objective as our design. However, they assume that the working schedule of receivers could be postponed so that the spatiotemporal locality of broadcast can be utilized. In their another work, Xu et al.⁶ investigate the minimum end-to-end delay broadcast scheduling problem for load balance in low-duty-cycle sensor networks. For such NP-hard problem, both approximate and distributed heuristics have been developed. Jiao et al.⁷ devise a schedule algorithm in order to achieve minimum latency broadcasting without signal interference in multi-channel, duty-cycle sensor networks. All these solutions are based on the working reschedule of sensors, which may not be practical in the real-time applications.

In consideration of asynchronous scheduling, network-level broadcast schemes have also been designed to reduce latency of multihop communication in duty-cycle sensor networks. Jiao et al.⁸ study the minimum latency broadcast scheduling problem in duty-cycle wireless networks. They prove that such one-to-all and all-to-all broadcast problems are NP-hard and then build latency-based, collision-free shortest path tree to minimize the broadcast latency. Aiming at minimum energy consumption, Han et al.² propose the tree construction algorithms for minimum energy multicasting in duty-cycle sensor networks. Xu et al.⁹ observe that some nodes are not beneficial to the optimization of broadcasting latency because they are not on the critical paths. Then, they propose approximation algorithms to postpone the wake-up of these nodes in order to save energy. Some other works have been designed to trade-off energy efficiency and flooding latency in duty-cycle sensor networks. Wang and Liu¹⁰ study the broadcast problem to reduce latency with given coverage guarantees, which is translated into graph equivalence problem. Lai and Ravindran¹¹ present a hybrid casting with delivery deferring and opportunistic forwarding in order to balance broadcast latency and transmission count. Unfortunately, all the above works are based on the assumption of perfect wireless link, which is not practical in the real low-power sensor networks.

The unreliability of wireless link has significant impact on both delivery delay and data reliability in low-duty-cycle sensor networks.¹² Li et al.¹³ study how the practical factors, such as link quality and duty cycle, affect the flooding delay. Both theoretical and mathematical results verify that duty-cycle length has major impact on flooding delay, while unreliable link can significantly exacerbate such negative factors. To enable reliability, GRAdient Broadcast (GRAB)¹⁴ is the first data delivery protocol presented for large-scale sensor networks on the basis of broadcast nature of wireless radio, in which data packets are assumed to be forwarded over multiple interleave paths to prevent single-path failure. Sun et al.¹⁵ propose Asynchronous Duty-cycle Broadcasting (ADB), a cross-layer protocol, to implement efficient flooding. ADB incorporates multihop transmission with the collision and recovery in MAC layer and then dynamically selects links with better quality to achieve broadcast reliability and reduced latency.

Recently, flooding over unreliable links in asynchronous sensor networks has achieved some initial success.^1,16 Cheng et al.¹⁷ propose a dynamical switching-based flooding (DSRF) scheme for low-duty-cycle sensor networks. Based on the built flooding tree, DSRF can adjust its flooding process according to the packet reception so that the energy consumption and delay can be reduced. Guo et al.¹ introduce opportunistic forwarding into energy-efficient flooding tree so that data packets can be opportunistically delivered along with non-tree paths. Consequently, both flooding delay and energy consumption could be reduced. Nguyen et al.¹⁸ propose a similar opportunistic flooding scheme by introducing an energy-optimal mechanism to balance the energy consumption among the set of senders, which can prolong the network lifetime. Our work complements these solutions in that we apply variable transmission power mechanism instead of fixed one so that our design can be applied to both dense and sparse network deployments. The design³ constructs a minimum-delay, energy-efficient spanning tree for the data flooding in low-duty-cycle sensor networks, which has a similar problem description. They focus on the optimization of energy efficiency. Moreover, they assume that delay constraint is estimated as a posteriori instead of application requirement.

Based on the observed link correlation, Guo et al.¹⁶ design a correlated flooding algorithm in which the set of correlated neighbors can be scheduled to wake up simultaneously, reducing transmission count and then saving energy consumption. Based on the link correlation, Zhu et al.¹⁹ propose collective flooding (CF) in order to reduce the overhead of acknowledgements (ACKs) for low-duty-cycle sensor networks. All these designs are orthogonal to our solution.

To the best of our knowledge, our design is unique in that the transmission power control mechanism is first introduced to reduce flooding delay in low-duty-cycle sensor networks.

Preliminaries

In this section, we define the system model that is related to our flooding design and problem statement.

System model

We consider a static sensor network with a single sink node and large amount of duty-cycle nodes. Each sensor node determines its working schedules individually to reduce sense redundancy. Obviously, such duty-cycle sensor network is time-dependent, in which multicast happens only when multiple receivers wake up at the same time. Taking Figure 1 for example, the network can be formulated as a connected graph $G (V, E, W)$ , where V, E, and W are the sets of nodes, links, and working schedules, respectively. In Figure 1, $V = {S, A, B, C, D, E, F, G}$ and $W = {0, 2, 8, 7, 3, 6, 4, 5}$ .

Suppose T be the common working period of the network, and it is further divided into a number of equal time slots with the same length, in which a round-trip transmission could be performed. Then, Sleep latency (s) is referred to as the time interval from the moment the sender has a packet ready to be sent at time t to the moment the receiver wakes up. Since s dominates the data delay in low-duty-cycle sensor networks, both data delay and sleep latency are used interchangeably in this article.

Under reliable link, the sleep latency is the difference of active slots if the receiver wakes up later than the sender. Otherwise, the sender has to wait for the waking up of its receiver in the next working schedule. For example, the sleep latency from node F to node G is $5 - 4 = 1$ in Figure 1, while the sleep latency from node C to node E is $(6 - 7) + T = 9$ if T equals to 10. Under unreliable link, sleep latency is also dependent on the link quality besides the working schedule. Given the packet reception ratio (PRR), q, of link e, the one-hop expected data delay, d(e), can be estimated as

d (e) = \sum_{i = 0}^{k - 1} \frac{{(1 - q)}^{i} q (s + i * T)}{1 - {(1 - q)}^{k}}

(1)

here, k is the expected transmission count for successful data delivery, which can be evaluated as the reciprocal of the link quality.

Assumptions

Based on the network model, we make the following assumptions:

The working schedule of each node is predefined and shared with all its neighbors when it joins the network. The process is referred to as low-duty-cycle rendezvous,²⁰ which is performed in the initialization stage.

We assume the wireless radio is unreliable in real applications. The wireless link quality is quantified by the PRR within a given period of time. In practice, it can be estimated through MAC layer data loss measurement²¹ or low-cost piggybacking on the normal data traffic. Though the link quality changes over time but non-notably, the reliability of single-hop forwarding can be assured through the use of automatic repeat request (ARQ) in the unicast.

Each node has a fixed number of discrete transmission power levels. For example, the Chipcon CC2420 used by Micaz nodes has 32 output power levels controlled by a programmable register.²² To be brief, we confine the transmission powers between $l_{l}$ and $l_{h}$ , where $l_{l}$ is the minimum power level to ensure network connectivity and $l_{h}$ is often bounded by the maximum power level of wireless transceiver.

We assume an integer is used to denote the minimum number of hops from a node to the sink. Usually, the sink node is marked as 0. All it’s immediate neighbors are marked 1, and so on. A node only forwards a flooding packet to nodes with larger or equal hop count to prevent loop routing.

Problem statement

In this work, we consider the optimization of flooding delay from sink to all nodes in low-duty-cycle sensor networks. Based on the network model, the flooding is spread from the sink to those with equal or larger hop counts. Suppose each packet is only forwarded by one node, the flooding structure is formulated as a spanning tree rooted at the sink.

According to equation (1), we can define the flooding delay over a multihop path $P (S, v_{i})$ as the sum of data delays of each link e along with the path

d (P) = \sum_{e \in P (S, v_{i})} d (e)

(2)

The flooding delay of whole network is defined as the time interval from the moment a packet is sent out to the time slot of being received by the last node within the network. Therefore, the flooding delay of G is the sleep latency along the longest path P in the flooding tree ( $Γ$ )

FloodingDelay (G) = max_{P \in Γ} {d (P)}

(3)

Given link quality q over link e, we have the expected one-hop flooding energy cost

c (e) = ETX (e) * p = \frac{p}{q}

(4)

here, $ETX (e)$ is the expected number of transmissions for success forwarding over link e, which can be evaluated as the reciprocal of link quality. Suppose the size of flooding packet is fixed, and p is the energy consumed by the delivery of one single packet.

Thus, the total flooding cost, $FloodingCost (G)$ is the energy consumption of data flooding along with the flooding tree

FloodingCost (G) = \sum_{e \in Γ} {c (e)}

(5)

All present schemes are based on the assumption that sensor node communicates at default (fixed) transmission power level. However, both link quality (q) and energy consumption per packet (p) are related to the given transmission power.²³ Consequently, transmission power influences both flooding delay and energy efficiency. Our objective is to find the optimal transmission power control policy ( $Ψ_{opt}$ ) to achieve minimized energy expenditure under delay constraint $| D |$ , which can be formally defined as

Ψ_{opt} = min_{Ψ (Γ)} (FloodingCost (G))

(6)

which subjects to

FloodingDelay (G) \leq | D |

(7)

The transmission control scheme $Ψ (Γ)$ is the set of transmission power level for each edge in the flooding tree $Γ$ , that is, $Ψ (Γ) = {l_{1}, l_{2}, \dots, l_{m}, 1_{l} \leq l_{i} \leq l_{h}}$ , where m is the number of edge in $Γ$ .

Finding a feasible transmission scheme satisfying multiple constraints even along a predefined forwarding path has been proved to be NP-complete.²³ Our problem to find the optimal transmission schedule in a flooding tree is also NP-hard.

DCF scheme

In this section, we present a DCF scheme to find the sub-optimal solution for the above NP-hard problem.

Observations on transmission power augmentation

Increasing the transmission power of the sender can improve link quality of communications, which has been widely verified.²⁴ According to equation (1), single-hop delay is highly related to the link quality of wireless communication. In particular, better link quality can reduce the number of transmissions, leading to a less delivery delay. In multihop data delivery, another important observation is that transmission power augmentation may increase communication range and cover more sensor nodes, bringing more forwarding opportunities for low-duty-cycle sensor network. According to equation (2), the path delay is dependent on not only the hop delay but also the path length. In Figure 1, the path delay from node S to node A via C is 12 if the working period is 10. However, if node A can transmit data packets to node A directly at a higher transmission power, the path delay reduces to $2 - 0 = 2$ .

Based on these observations, one may argue that we can always use the maximum transmission power level to minimize flooding delay. However, minimizing flood delay and minimizing energy consumption are two contradictory objectives in low-duty-cycle sensor network. On one hand, better link quality can reduce the energy consumed by data retransmissions in case of failures. On the other hand, the sender itself has to consume more energy for data transmission at a higher power level. Moreover, two key issues about transmission power augmentation need to be considered. (1) Increasing is not always beneficial to the optimization of data delay. Taking Figure 1 as an example, if node D can reach node G at a higher power level, it is not helpful to reduce delivery delay but consume more energy. (2) While transmission power augmentation brings more communication opportunities, it may also incur more transmission conflicts with the increasing communication range.

Therefore, dedicated flooding scheme is necessary to optimize delay on the condition that the energy efficiency is not sacrificed in extremely low-duty-cycle sensor networks.

Design overview

Since our design is based on tree-based topology, we first construct a minimum spanning tree based on the expected flooding delay (EFD-MST). In Figure 2(a), the corresponding spanning tree is described ( $Γ$ ) for the low-duty-cycle sensor network in Figure 1. We illustrate the main design based on the assumption that all link qualities are reliable, and then relax it later in algorithm implementation.

Figure 2.

Delay-constrained flooding (DCF) hierarchy: (a) spanning tree (|D|= 10); (b) DCF-based structure.

At the beginning, the default transmission power level is assumed to be $l_{1}$ for network connectivity. Given delay bound $| D | = 10$ , EFDs of some nodes (including A, D, E, F, and G) are beyond the given delay bound as shown in Figure 2(a). For example, the delays from the sink to nodes A and D are 12 and 13, respectively. Therefore, we can reduce flooding delay by transmission power augmentation. As shown in Figure 2(b), if node A selects the sink (S) instead of node C as its parent, the flooding delay from the sink to node A has been reduced from 12 to 2. In this case, the sink needs to increase its transmission power in order to reach node A. Note that, transmission power adjusting is not necessary for all out-of-bound nodes since the sibling or children in the flooding tree can benefit from the reduction of delay from their ancestors. For example, the delays of nodes F and G are reduced to 4 and 5, respectively, after node A updates its flooding delay. However, node E has to switch its parent from node C to node A with the original transmission power level. In fact, node E can also be reachable by the sink with enough transmission power. Nevertheless, flooding through A is more energy-efficient compared with other policies. For node D, node A needs to increase its transmission power to level $l_{3}$ so that the delivery delay can meet the delay constraint.

In order to build the above flooding hierarchy, we devise a top-down, on-demand transmission power augmenting algorithm (Algorithm 1) to meet the flooding delay constraint. Based on the constructed EFD-MST, the sink node notifies all nodes by broadcasting the message including the given delay constraint ( $| D |$ ). On receiving the message from its parents, each node compares its EFD with the bound $| D |$ . If its EFD is less than $| D |$ , the message will be ignored. Otherwise, Algorithm 1 will be performed. In the procedure of EFD-MST construction, it assumes that each node has obtained the EFD and energy cost (EFC). After that, the node will search its neighboring tables at each transmission power level for the approximate parent, over which the current node can reduce its flooding delay to meet the bound at minimum energy. Since only transmission at higher power level can contribute to the deduction of flooding delay, each node only needs to scan the neighbors of those power levels which is larger than the default one.

Algorithm 1. On-demand transmission power augmention.
Require: Neighboring table $N T_{p}$ at power level $l_{p}$ $(l \leq p \leq h)$ ; Require: Delay constraint, $\| D \|$ ; Require: Expected flooding delay from the sink to node $v_{i}$ , $EF D_{i}$ ; Require: Expected flooding cost from the sink to node $v_{i}$ , $EF C_{i}$ ; Ensure: Tuple ( $l_{opt}, ParentId, EF D_{opt}, EF C_{opt}$ ); 1: $EF D_{opt} \leftarrow EF D_{i}$ ; 2: $EF C_{opt} \leftarrow EF C_{i}$ ; 3: if ( $EFD \geq \| D \|)$ ) then 4: for all transmission power $l_{p} \in [l_{l + 1}, l_{h}]$ do 5: for all neighbor nodes $v_{j} \in N T_{p}$ do 6: $EF D_{i} \leftarrow EF D_{j} + d_{ij} (l_{p});$ 7: $EF C_{i} \leftarrow EF C_{j} + c_{ij} (l_{p});$ 8: if ( $EF D_{i} \leq \| D \|$ AND $EF C_{i} < EF C_{opt}$ ) then 9: $EF C_{opt} \leftarrow EF C_{i};$ 10: $EF C_{opt} \leftarrow EF C_{i};$ 11: $l_{opt} \leftarrow l_{p};$ 12: $ParentId \leftarrow v_{j};$ 13: end if 14: end for 15: end for 16: end if 17: Announce the updating of EFD to those neighboring nodes with larger or equal hop count by broadcasting control message including the tuple $(v_{i}, EF D_{opt}, EF C_{opt})$ .

Algorithm 1. On-demand transmission power augmention.

Require: Neighboring table

N T_{p}

at power level

l_{p}

(l \leq p \leq h)

;
Require: Delay constraint,

| D |

;
Require: Expected flooding delay from the sink to node

v_{i}

EF D_{i}

;
Require: Expected flooding cost from the sink to node

v_{i}

EF C_{i}

;
Ensure: Tuple (

l_{opt}, ParentId, EF D_{opt}, EF C_{opt}

);
1:

EF D_{opt} \leftarrow EF D_{i}

;
2:

EF C_{opt} \leftarrow EF C_{i}

;
3: if (

EFD \geq | D |)

) then
4: for all transmission power

l_{p} \in [l_{l + 1}, l_{h}]

do
5: for all neighbor nodes

v_{j} \in N T_{p}

do
6:

EF D_{i} \leftarrow EF D_{j} + d_{ij} (l_{p});

EF C_{i} \leftarrow EF C_{j} + c_{ij} (l_{p});

8: if (

EF D_{i} \leq | D |

AND

EF C_{i} < EF C_{opt}

) then
9:

EF C_{opt} \leftarrow EF C_{i};

10:

EF C_{opt} \leftarrow EF C_{i};

11:

l_{opt} \leftarrow l_{p};

12:

ParentId \leftarrow v_{j};

13: end if
14: end for
15: end for
16: end if
17: Announce the updating of EFD to those neighboring nodes with larger or equal hop count by broadcasting control message including the tuple

(v_{i}, EF D_{opt}, EF C_{opt})

Collision avoidance

Though data traffic in low-duty-cycle sensor networks is rare, it is possible that multiple data transmissions are collided with each other, especially when transmission power is increased.

Note that, the concurrent transmissions happen only when multiple receivers wake-up at the same time. To resolve the conflicts, we introduce a transmission power aware backoff approach. When a node intends to send, it first backs off for a period of time at the start of each slot. The duration of the backoff depends on the selected power level. The higher the transmission power, the shorter the backoff duration. Thus, the sender with the highest power level starts first when multiple nodes within communication range decide to flooding through the flooding hierarchy. On listening the ongoing transmission, other conflicting senders would postpone their own transmissions. Using such backoff method, energy can be saved since failed transmissions at a higher power level consume more energy in case of conflict.

Suppose the whole backoff time bound is $T_{b}$ and the maximum number of concurrent transmissions is C, we can divide $T_{b}$ into C slots for holding various backoff nodes. A sender can compute its backoff duration $t_{b}$ with the following equation

t_{b} = ⌊ C (1 - \frac{i}{h}) ⌋ \frac{T_{b}}{C} + X, l \leq i \leq h

(8)

where i is the number of transmission power levels and X is a random number generated from $[- \frac{T_{b}}{C}, + \frac{T_{b}}{C}]$ if $i < h$ and from $[0, + \frac{T_{b}}{C}]$ if $i = = h$ . The random period is used to avoid the collision of two or more nodes which transmit at the same power level.

The DCF protocol

This section presents the details of our DCF protocol with unreliable links in extremely low-duty-cycle sensor networks. Our implementation includes the following phases.

Initialization

After the start-up, each node performs initialization tasks, such as neighboring discovery and work schedule sharing. Starting from the sink node, each node starts the neighboring discovery process using the default transmission power. To prevent loop, each node is assigned as a layer number based on the hop counts away from the sink (which is in the layer 0). Based on the hierarchical architecture, each node tries to build its neighboring table under various transmission power levels. Along with the neighbor discovery, the link qualities among neighbors at various power levels can also be evaluated. Finally, each entry in neighboring table consists of the neighbor ID, power level, and the corresponding link quality. Note that, only the minimum power level will be recorded in order to compress the neighboring table if the pair of communication parties has the same link quality through various transmission powers. For example, one pair of nodes has the same PRR under power levels $l_{2}$ , $l_{3}$ , and $l_{4}$ . In this case, we would retain the entry with transmission power level $l_{2}$ because data forwarding at level $l_{2}$ is the most energy-efficient. The compression process happens frequently in dense network deployments.

EFD-MST construction

Based on the initialized connected network, we can build EFD-based spanning tree. To do that, each node can calculate its EFD and EFC according to equation (2). In the beginning, the sink broadcasts its own EFD along with its own layer number (both are 0s). On receiving EFDs of its neighbors, a node can update its minimum EFDs and select the corresponding flooding parent. To prevent loop, each node only selects the node with less or equal layer as its parent. It is worthy that the construction of EFD-MST is based on the default transmission power level.

Reconstruction of flooding hierarchy

In our design, delay constraint ( $| D |$ ), a system parameter is dependent on application setting. For example, messages including code upgrading needs to be delivered to all nodes within the given delay bound. Once decided, the sink will announce to all nodes by broadcasting in the startup stage. Those out-of-bound nodes can reduce EFD according to Algorithm 1 in section “Design overview.” At the end of the algorithm, the node would notify all one-hop neighbors with its updated EFD and EFC. Once receiving the values, the neighbor compares its own EFD and EFC with the newest one by adding one-hop delay and energy expenditure. In the same way, the neighbor chooses new parent with less delay bound (lines 8–13 in Algorithm 1). In case of equal delay, it would select the one with less EFC from multiple potential parents. Theoretically, all nodes can meet the delay bound by selecting approximate transmission power and corresponding flooding parent.

Taking Figure 2 as an example, node A chooses sender S to replace its original parent C at power level $l_{2}$ . After that, node E updates its parent to node A; node D changes its power level and parent to $l_{3}$ and node A, respectively, because the flooding delay after updating is smaller. It is worth mentioning that nodes F and G can meet delay constraint without changing anything due to the renewal of node A’s EFD. The time complexity of Algorithm 1 depends on both the number of available power levels and the neighboring nodes. Suppose the number of all nodes in the network be N, the time complexity could be expressed as $O ((h - l) N)$ .

Performance evaluation

This section validates the performance of our DCF protocol by large-scale network simulations. In specific, we evaluate the flooding delay and the power consumption and compare with those common flooding schemes in asynchronous low-duty-cycle sensor networks as follows:

Minimum expected energy–based flooding (MEEF): To achieve the minimum expected energy cost, the flooding packets are only forwarded via the energy-optimal tree, in which each node selects the neighboring node with minimum expected transmission count (ETX) as its flooding parent to reduce the number of retransmissions.

Opportunistic flooding¹(OPPF for short): Opportunistic flooding is a famous flooding scheme proposed for low-duty-cycle sensor networks, in which the flooding packets may be opportunistically forwarded by some links outside the energy-optimal flooding tree. According to the original design, the related parameters are set as default, that is, l = 0.7 for flooding sender selection and p = 0.9 for decision-making.

Minimum expected delay–based flooding (MEDF): The MEDF scheme is proposed based on the minimum expected flooding delay spanning tree in order to minimize the flooding delay. In other words, each node selects neighbors with minimum EFD as its parent under given transmission power level.

Simulation settings

In the simulation, we assume that all sensor nodes are randomly deployed in a square field, where the sink is located in the center of sensor area. The links among nodes are wireless path loss channels with shadowing effects.²⁵ Without otherwise specified, the transmission power levels are set according to CC2420 radio hardware specification.²² In detail, we select six typical transmission power levels, that is, −11, −9, −7, −5, −3, and 0 dBm indexed from level 0 to level 5. By default, the duty cycle is set to 1% and the delay constraint ( $| D |$ ) in DCF is set to four times of working schedule, that is, 4 ×T.

Performance metrics

Flooding delay is defined as the time units elapsed from a message being sent out by the sink until it reaches 99% of the nodes in the network. Here, the delivery ratio is set to 99% instead of 100% to eliminate the possible condition of extremely low-degree nodes in random-generated network. Due to unreliable links, the flooding delay can be considered a random variable. Therefore, we use average flooding delay in the simulations.

Since the energy consumed by data reception is not related to transmission power, we use only sender-side power consumption as the energy performance metric. In specific, energy consumption is measured as the average power consumed by flooding a single data packet. The power consumed by unit of data packet is identical to the practical measures which range from 36.3 to 50.69 mW under the given transmission power levels.

Performance comparison

In this section, we compare our DCF with MEDF, MEEF, and OPPF.

Varied duty cycles

We first evaluate the performance of these schemes under different duty cycles. In the simulation, 600 nodes are deployed on a $250 m \times 250 m$ field. The duty cycle varies from 1% to 5%.

Figure 3(a) and (b) show the flooding delay and power cost, respectively. As shown in Figure 3(a), the average flooding delays decline with the increasing duty cycles for all schemes. DCF can reduce flooding delay by around 60% compared with MEDF and MEEF, and cut half of the delay achieved by OPPF. In Figure 3(b), OPPF can achieve the highest power efficiency due to opportunistic forwarding. Compared with OPPF, our design provides much shorter flooding delay while spends only more than $5 % - 8 %$ power efficiency. The rational behind is that flooding efficiency is highly dependent on the number of transmissions. Our design selects refined transmission power to maintain stable and better link qualities, which greatly reduces the retransmissions. Moreover, we observe that the duty cycle has little impact on the power consumption since only the energy of data transmission is taken into consideration.

Figure 3.

Duty cycle: (a) flooding delay vs duty cycle; (b) power cost vs duty cycle.

Varied expected delivery ratios

We compare the performance when a different flooding delivery ratio is required. The flooding delivery ratio is defined as the percentage of nodes that has received flooding packet. In the simulation, the 600-node network with a 1% duty cycle is used. The flooding process is terminated when the given percentage of nodes has received the packet.

According to Figure 4(a), the flooding delays of both MEDF and MEEF gradually increase with the expected delivery ratio. On the contrary, both DCF and OPPF have a rather stable flooding delay, while the delivery ratio increases from 85% to 99%. In a tree-based topology, data packet is usually flooded from the sink to whole network layer by layer. Besides duty cycle and link quality, another influence factor for multihop flooding is the length of flooding path. Given a lower delivery ratio, the flooding process is tended to be ended early, leading to shorter forwarding paths and delays. In OPPF, opportunistic forwarding provides a delay compensation mechanism by abandoning some nodes with bad link qualities. Instead, DCF tries to repair those bad channels by switching to a higher transmission power level, which can reduce flooding path and increase link qualities. Consequently, our design can reduce 50% delay compared with all other schemes.

Figure 4.

Delivery ratio: (a) flooding delay vs delivery ratio; (b) power cost vs delivery ratio.

Figure 4(b) shows that more power consumption is needed for covering more flooding nodes in both MEDF and MEEF. The power consumed by OPPF and DCF is fixed around 41.6 and 43.6 mW, respectively, which verifies our analysis.

Varied network sizes

To evaluate the performance under different network sizes, we keep a similar density by setting the number of nodes between 200 and 1000 and changing the corresponding length of network from 150 to 335.

Figure 5(a) shows that the flooding delays for all schemes increase with the number of nodes. For example, the average flooding delay for OPPF increases from 1088 to 1988 when the nodes vary from 200 to 1000. Figure 5(b) shows that the power consumption of single node for four schemes is stable. It is rational that the number of nodes only affects the total energy consumption instead of average power cost for single node. Overall, our design outperforms and reduces more than 40% of flooding delay at no more than 10% extra power cost.

Figure 5.

Network size: (a) flooding delay vs network size; (b) power cost vs network size.

Varied network densities

In this section, we evaluate how network density influences the performance. The network size is fixed at 600 nodes and the length of network sides ranges from 100 to 300.

Figure 6(a) shows that the average flooding delays in all schemes decrease at first and then gradually increase as the network density decreases. The minimum flooding delays are achieved by MEDF, MEEF, and OPPF when the side length is 150. An interesting observation in Figure 6(a) is that opportunistic flooding closes to DCF when the network is dense but endures a longer flooding delay than DCF in sparse networks. This is because with high density, the increasing number of neighboring nodes leads to more concurrent transmissions and conflicts. Figure 7 shows that the average number of conflicts is more than 350 when the side length is 100 and sharply drops to around 50 times at length 150. While the collisions happen frequently, extra delay incurred by data retransmissions dominates the flooding delay for MEDF, MEEF, and DCF. Notably, more neighboring nodes are beneficial to OPPF by providing more forwarding chances. Our design surpasses other schemes in sparse network since higher transmission power can improve link qualities and provide more forwarding opportunities.

Figure 6.

Flooding performance with various side length in networks: (a) flooding delay vs side length; (b) power cost vs side length; and (c) delivery ratio vs side length.

Figure 7.

Number of conflicts vs side length.

Figure 6(b) shows that the power cost increases gradually for other schemes except DCF. The power efficiency of DCF is quite close or even better than MEEF, which is built based on energy-optimal flooding tree. Conversely, DCF consumes more energy since it has to increase its power level to keep network connectivity.

Figure 6(c) shows the flooding delivery ratio under different network densities. When the network density is high, the flooding ratio is approximately 99% as expected for all designs. However, the delivery ratio quickly drops to around 95% at length 250. If the side length continues to grow, many nodes are isolated and flooding ratio decreases greatly.

System insights

This section presents some insights into why our design significantly reduces flooding delay.

System parameter

In real applications, $| D |$ may represent the delay requirement of users. For example, the user might expect that all nodes can update their code within a certain period of time, which imposes upper bound. However, the selection of delay constraint $| D |$ is limited by the network deployment setting, such as network size, density, and duty cycles. If the bound is set too tight, the delay cannot be guaranteed even if that packet is flooded at maximum transmission power level. On the contrary, if $| D |$ exceeds the maximum achieved expected delay, there is no need of adjusting transmission power.

We evaluate the average flooding delay and power consumption under various $| D |$ settings. In particular, the $| D |$ ranges from T/2 to 8 ×T, given T = 100. Figure 8(a) shows that the average flooding delay decreases first and then increases with $| D |$ , reaching the minimum value while $| D |$ is 4 T. Figure 8(b) shows that the impact of $| D |$ on power efficiency is trivial.

Figure 8.

Insights of system parameter $| D |$ : (a) flooding delay vs $| D |$ ; (b) power cost vs $| D |$ .

According to equation (3), the flooding delay depends on both the length of longest flooding path (hops) and the sleep latency per hops. Statistically, the average sleep latency per hop can be approximately estimated as T/2. Given the count of maximum hops H, the best theoretical setting of $| D |$ should be less than $HT / 2$ . In the above simulation, we set the value of $| D |$ to $HT / 4$ because the maximal hop count is around 16 in our simulations. In practice, we can refer to the maximal EFD as the optimal value of $| D |$ .

Investigation on system performance

To investigate how a flooding packet propagates in a network, we record the time stamps that the packet has been received and plot the cumulative distribution function (CDF) delay in Figure 9(a). As shown in the figure, more than 80% nodes can receive the packet within the bound $| D |$ for DCF, while the time durations to cover the same number of nodes are 717, 890, and 1053 for OPPF, MEDF, and MEEF, respectively. Furthermore, to deliver the flooding packet to about 99% nodes, it takes 619 time slots for DCF, only half of that OPPF. For MEDF and MEEF, the time could be as long as 2400, four times longer than our delay. This indicates that the total flooding delay for them is severely affected by only a few nodes, which may have either a bad link or a long sleep latency.

Figure 9.

Insights of system performance: (a) delay CDF; (b) power CDF (no. of transmissions).

In addition to flooding delay, we also record the number of transmissions for each single node and compare the power distribution with other schemes. According to Figure 9(b), about 90% of nodes forward the flooding packet less than 10 times. In contrast, the number of transmissions in OPPF is 13 to reach the same percent of nodes. To reach the last few nodes, especially the last 10%, the number of transmissions for MEDF and MEEF increases to more than 30 times due to poor connectivity and link quality. This implies that the flooding delay is dominated by the last few nodes.

Finally, we record the number of used transmission power levels in DCF. Figure 10 shows that the ratio of two minimum transmission power levels accounts for 63%, while the highest two levels take about 12%. This explains why our design has smaller transmission number than OPPF but consumes a little more power.

Figure 10.

Ratio of various transmission (Tx) levels.

Performance summary

Our implementation and simulation results show that our delay-constrained design can greatly reduce flooding delay at little extra power cost. In fact, our design is more suitable for a large-scale and sparse network with extremely low-duty-cycle (<1%) model. In a small network with reasonable scale and duty cycle, opportunistic flooding can be used. However, our design and OPPF are not mutually exclusive, that is, integrating opportunistic forwarding mechanism into DCF is possible.

Conclusion

In this article, we propose a DCF scheme, aiming at reducing flooding delay in extremely low-duty-cycle wireless sensor networks. In our design, we first build a minimum spanning tree based on the EFD and then present a transmission power control augmentation algorithm so that each node can adjust its transmission power according to the given delay constraint. To solve transmission conflict, transmission power aware backoff mechanism is discussed to prioritize those flooding at higher transmission power level to save energy consumption. Extensive simulations verify that our design can achieve a shorter average flooding delay with only a little extra power consumption. The flooding scheme in this article is designed for the application with a sparse and extremely low-duty-cycle network setting. In the future, we shall consider the efficient integration of opportunistic flooding and transmission power control mechanism so that the design can fit various application scenarios.

Footnotes

Acknowledgements

The authors are grateful to the anonymous referees for their valuable comments and suggestions to improve the presentation of this paper.

Handling Editor: Daniel Gutierrez-Reina

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the Natural Science Foundation of Guangdong Province of China (grant no. 2016A030313104), the Science and Technology Program of Guangzhou, China (grant no. 201707010404), and the NSFC (grant no. 61572233).

ORCID iD

Zuzhi Fan

References

Guo

et al . Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links. IEEE T Comput 2014; 63(11): 2787–2802.

Han

Liu

Luo

Duty-cycle-aware minimum-energy multicasting in wireless sensor networks. IEEE/ACM T Netw 2013; 21(3): 910–923.

Cheng

Niu

Luo

et al . Towards minimum-delay and energy-efficient flooding in low-duty-cycle wireless sensor networks. Comput Netw 2018; 134: 66–77.

Sengul

Miller

Gupta

Adaptive probability-based broadcast forwarding in energy-saving sensor networks. ACM T Sens Netw 2008; 4(2): 6.

Chen

Cao

et al . Optimizing energy efficiency for minimum latency broadcast in low-duty-cycle sensor networks. ACM T Sens Netw 2015; 11(4): 57.

Zhu

Dai

et al . Towards energy-fairness for broadcast scheduling with minimum delay in low-duty-cycle sensor networks. Comput Commun 2016; 75: 81–96.

Jiao

Xiao

et al . On minimum-latency broadcast in multichannel duty-cycled wireless sensor networks. Int J Distrib Sens N 2015; 11: 1–8.

Jiao

Lou

et al . Duty-cycle-aware minimum latency broadcast scheduling in multi-hop wireless networks. In: International conference on distributed computing systems, Genova, 21–25 June 2010, pp.754–763. New York: IEEE.

Cao

Lin

et al . Energy-efficient broadcast scheduling with minimum latency for low-duty-cycle wireless sensor networks. In: IEEE 10th international conference on mobile ad-hoc and sensor systems (MASS), Hangzhou, China, 14–16 October 2013, pp.163–167. New York: IEEE.

10.

Wang

Liu

On reliable broadcast in low duty-cycle wireless sensor networks. IEEE T Mobile Comput 2012; 11(5): 767–779.

11.

Lai

Ravindran

. On multihop broadcast over adaptively duty-cycled wireless sensor networks. In: International conference on distributed computing in sensor systems, Santa Barbara, CA, 21–23 June 2010, pp.158–171. Berlin: Springer.

12.

Dynamic switching-based data forwarding for low-duty-cycle wireless sensor networks. IEEE T Mobile Comput 2010; 10(12): 1741–1754.

13.

Liu

et al . Understanding the flooding in low-duty-cycle wireless sensor networks. In: IEEE international conference on parallel processing (ICPP), Taipei City, Taiwan, 13–16 September 2011, pp.673–682. New York: IEEE.

14.

Zhong

et al . GRAdient broadcast: a robust data delivery protocol for large scale sensor networks. Wirel Netw 2005; 11: 285–298.

15.

Sun

Gurewitz

et al . ADB: an efficient multihop broadcast protocol based on asynchronous duty-cycling in wireless sensor networks. In: Proceedings of the 7th ACM conference on embedded networked sensor systems, Berkeley, CA, 4–6 November 2009, pp.43–56. New York: IEEE.

16.

Guo

Kim

Zhu

et al . Correlated flooding in low-duty-cycle wireless sensor networks. In: 19th IEEE international conference on network protocols (ICNP), Vancouver, BC, Canada, 17–20 October 2011, pp.383–392. New York: IEEE.

17.

Cheng

Niu

et al . Achieving efficient reliable flooding in low-duty-cycle wireless sensor networks. IEEE/ACM T Netw 2016; 24: 3676–3689.

18.

Nguyen

Choe

Duc

et al . Delay-sensitive flooding based on expected path quality in low duty-cycled wireless sensor networks. Int J Distrib Sens N 2016; 12: 1–16.

19.

Zhu

Zhong

et al . Achieving efficient flooding by utilizing link correlation in wireless sensor networks. IEEE/ACM T Netw 2013; 21(1): 121–134.

20.

Dutta

Culler

. Practical asynchronous neighbor discovery and rendezvous for mobile sensing applications. In: Proceedings of the 6th ACM conference on embedded networked sensor systems, Raleigh, NC, 5–7 November 2008, pp.71–84. New York: ACM.

21.

De Couto

DSJ

. A high-throughput path metric for multi-hop wireless routing. Wirel Netw 2005; 11(4): 419–434.

22.

http://www.ti.com/

23.

Fan

Bai

Wang

et al . Delay-bounded transmission power control for low-duty-cycle sensor networks. IEEE T Wirel Commun 2015; 14(6): 3157–3170.

24.

Lin

Miao

Zhang

et al . ATPC: adaptive transmission power control for wireless sensor networks. ACM T Sens Netw 2016; 12(1): 6.

25.

Marco

Bhaskar

. Analyzing the transitional region in low power wireless links. In: First annual IEEE Communications Society conference on sensor and ad hoc communications and networks, Santa Clara, CA, 4–7 October 2004, pp.517–526. New York: IEEE.