Sage Journals: Discover world-class research

Abstract

Flooding in low duty-cycled wireless sensor networks suffers from a large transmission delay because a sender has to wait until a receiver becomes active to forward a packet. With the presence of unreliable radio links, the delay performance is even more severely degraded. In this article, we aim to reduce the flooding delay in low duty-cycled wireless sensor networks in relation to link unreliability. The key idea is to build a delay-sensitive flooding tree in which a node receives packet through the shortest path in terms of the total expected number of transmissions. In addition, the algorithm allows multiple senders to send through links outside of the tree if they can provide earlier expected delivery time. To give priorities to potential senders, we employ an energy-balancing mechanism which dynamically distributes the sending role among them. The mechanism not only makes sure senders start to acquire the channel at different times to prevent collisions but also lets them alternatively take turns based on residual energy, in order to lengthen network lifetime. Compared with the best known schemes, the proposed algorithm achieves up to 8% improvement in terms of flooding delay, energy consumption, and network lifetime.

Keywords

Duty-cycling wireless sensor networks unreliable links opportunistic flooding

Introduction

Wireless sensor networks (WSNs) are often deployed in a large scale, with hundreds to thousands of nodes. They use flooding as a primitive operation to update network parameters, code, or disseminate a route discovery message to each node.^1–3 A pure flooding is when a node receives a packet and sends the packet to all neighboring nodes, except the one from which it received. However, this method results in redundant transmissions, since multiple nodes may transmit to a common neighbor. To reduce that redundancy, a handful of studies have focused on building an efficient flooding tree, where the packet is sent according to a parent–child relationship.^4–7

Since a WSN is a collection of battery-powered motes, energy consumption is a critical issue. One possible way to prolong network life span is to run sensors in low duty-cycled mode.^8–10 As the name suggests, nodes in duty cycle mode periodically switch between active and sleeping states. Each sensor node is active for just a short period of time (time slot), and rest of the time, it stays in sleeping state (turning off the radio). Although a low duty-cycled configuration can greatly enhance network lifetime, it increases the flooding delay. In the case of tree-based flooding, a parent has to wait until a child becomes active to broadcast; and with multiple children being active at different time slots, the parent has to send a packet multiple times.¹¹ Such multiple transmissions cause not only longer flooding latency but also more energy consumption.¹²

In addition, research has shown that the wireless communication channel is unreliable,^13–15 especially in WSNs, where nodes with low power are spread over a wide area, and the presence of obstacles and other environmental effects worsen the quality of wireless links. Consequently, to successfully transmit a packet to a receiver, a sender might have to send it several times. Those retransmissions also make the delay and energy consumption performance more severe. Previous approaches for multi-hop ad hoc networks, such as hop-based shortest path tree⁶ and minimum connected dominating set,¹⁶ are mostly suitable for a reliable link model. So far, regarding the unreliable environment, only a few studies have addressed the flooding tree construction problem. Among them, Guo et al.⁵ proposed a dominant tree-based flooding structure in which the expected total number of transmissions is minimized. In their work, each node selects the one having the least number of expected transmissions to be its parent. Although flooding through this tree structure results in a remarkably smaller delay than pure flooding, the parent–child relationship is built by considering only one-hop neighbors, so that leaf nodes might receive a packet through a long delay path.

This article proposes a flooding scheme that provides efficient delay for low duty-cycled WSNs where the communication links are unreliable. A flooding tree is constructed to minimize the expected cumulative transmissions on each path connecting the source node to any other node. The scheme further enhances the delay performance by opportunistically utilizing links outside the tree that would help in faster packet delivery than tree-based flooding. Additionally, the proposed scheme contains a mechanism to alternatively distribute the sending role among potential senders based on their remaining energy. Such a sending distribution alleviates energy imbalance between potential senders, which plays key role in prolonging network lifetime. In brief, our contributions are as follows:

We design a flooding tree for an unreliable WSN, considering both the hop count and the quality of links to provide a delay-efficient path to any node in the network. Since hop-count information failed to capture the unreliable property of a path, combining it with the expected delay information is necessary to build efficient path between nodes.

We come up with a result that even when a tree is built to minimize the expected delay to each node, there are still chances to improve the delay performance of the network by allowing several sender candidates to participate in a broadcasting task to a single node.

To select a transmitting node among the sender candidates, we devise dynamic priorities to broadcast to a node based on the candidates’ residual energies. The priorities aim to resolve the energy imbalance issue and therefore to lengthen the network lifetime.

The organization of this article is as follows: in section “Related work”, we review important work focusing on the flooding problem in WSNs. Section “Preliminaries and motivation” restates basic terms and assumptions. Section “Delay-sensitive flooding scheme” presents the proposed scheme, which consists of the following: (1) building the delay-efficient flooding tree structure, (2) the determination of opportunistic transmissions based on the tree structure, and (3) the method for alleviating the collision at the receiver and balancing the energy consumption among senders. Section “Performance evaluation” shows simulation results and quantifies the gain over the best known scheme. Finally, we conclude our work in section “Conclusion.”

Related work

The flooding problem in duty-cycled WSNs has been studied intensively in the last decade. Depending on different applications, the scheme may require delay or energy efficiency to be the main metric. This part reviews some existing approaches toward the two concerns when a packet is flooded in an unreliable wireless environment.

So far, there are several methods to conserve energy: radio optimization, data reduction, sleep/wake-up schemes, and mobility.¹⁷ Regarding wireless sensor nodes, Anastasi et al.¹⁸ observed that energy for transmitting, receiving, and idle listening is in the same order of magnitude; only sleeping can drop the energy consumption rate remarkably. Therefore, the sleep/wake-up mechanisms, especially duty-cycling, became a prominent approach toward the energy conservation and have attracted a lot of research efforts.¹⁹ Accordingly, the common ways to assess energy efficiency are through the number of transmissions,⁵ the averaged power consumption per node,^4,7 or the network lifetime.²⁰ Among them, network lifetime is an important objective in WSNs, which requires a wise balancing strategy.

In a typical wireless ad hoc network, pure flooding is a fundamental method for disseminating data across the network, but it can cause a broadcasting storm problem.⁷ The broadcasting storm introduces a considerable degree of transmission redundancy and a high probability of contentions and collisions.²¹ Many researchers tried to resolve the problem, essentially by proposing to broadcast along an efficient spanning tree. Guo et al.⁵ introduced an energy-optimal tree (EOT) in which the total number of transmissions for a flooding packet is minimal. Couto et al.²² considered the expected transmission count (ETX) as an important metric when constructing a communication path in a multi-hop wireless network. Later, Niu et al.²³ used ETX as a criterion to build a minimum delay flooding tree in WSNs. Such an approach is desirable for achieving efficient delay but costly, since each node ignores the hop-count information during the tree construction process. One serious issue of tree-based flooding is that a bottleneck node (e.g. a node with long delay or out of energy) will affect all of the descendants in its subtree.

Several existing approaches improved the robustness and reliability of the flooding performance in WSNs. Guo et al.⁵ designed an opportunistic algorithm, utilizing the uncertain nature of the unreliable channel to reduce the flooding delay and alleviate the single path issue. Niu et al.’s²³ algorithm starts with a minimum delay spanning tree and then refines the tree structure to lessen energy consumption while maintaining delay efficiency. Cheng et al.’s²⁴ algorithm lets each node choose between a delay-optimal path and an energy-optimal path when forwarding a packet based on a real-time context.

Existing schemes can provide either a small flooding delay for a packet or a minimum amount of spent energy to complete a flooding round. However, they neglect a compromise between delay and network lifetime. In our work, we are concerned not only with the flooding delay of a single packet but also with the network lifetime of a low duty-cycled WSN containing unreliable communication links. The proposed scheme considers both hop-count information and quality of links to construct a delay-driven tree (DDT) and dynamically uses opportunistic transmissions.

Preliminaries and motivation

We consider a WSN which consists of N nodes. Every node has an equal transmission range and power supply. The entire time is split into working periods with equal length. In turn, a working period is divided into Ttime slots ${0, 1, \dots, T - 1}$ . We assume that a time slot duration is sufficient to transmit a whole packet, and time is synchronized over the entire network, so that a node knows when to send to a neighbor provided the neighbor’s active time slot. If two nodes send at the same time, their common neighbor cannot receive any of the transmitted packets due to a collision.

Nodes are deployed in a given area, and links between them are unreliable. Link quality can be characterized by a real number indicating the average success rate when the sender transmits to the receiver and can be measured using the wireless link estimation method in Niu et al.²³ Each node maintains a table of link qualities toward its neighbors. Given link qualities between nodes, a communication graph can be easily constructed by connecting every pair of nodes which have a communication link to each other. Figure 1(a) illustrates an example of a communication graph where dashed lines represent the communication links (edges), and the numbers next to the links are the corresponding qualities. Based on the communication graph, the level of a node is defined as the hop distance from the source node in the communication graph. A node only receives a packet from previous-level neighbors, and as a result, a directed acyclic graph (DAG) is formed as in Figure 1(b). The arrows point out the direction of a transmission.

Figure 1.

Example of network graphs: (a) communication graph (dashed lines are edges between nodes; a number next to an edge indicates its quality) and (b) directed acyclic graph (arrows indicates possible sending directions).

Recall that the flooding delay of a packet is the time when the last leaf node in the network receives the packet. The objective of this research is to efficiently reduce the flooding delay and balance the energy consumption to prolong network lifetime in low duty-cycled WSNs with the presence of unreliable links. As effective flooding tree construction plays a crucial role in reducing the delay, this work focuses on improving flooding delay in a delay-driven flooding tree. Furthermore, in order to lengthen the network life span, the proposed scheme should consider the residual energy of nodes as an important parameter while making a forwarding decision.

Guo et al.⁵ introduced an EOT. For each node, it selects the parent among its previous-level neighbors, so that the link between the two is of highest quality. For example, in Figure 3(a), nodes A, B, and C are one-hop neighbors of node S, so S is the parent of the three nodes. For node E, there are two parent candidates: node B and node C. Because the link quality $C - E$ is better than link quality of $B - E$ , node C becomes a parent of node E, and so on.

The EOT minimizes the number of transmissions for each flooding packet to be spread through the whole network, because each node receives the packet from the node providing the best incoming link quality. Let us say link delay is the time it takes one link’s end (sender) to successfully transmit a packet to the other end (receiver). It can be seen that the number of expected transmissions (ETX) toward a node to get one success is smallest, which can be translated to small link delay. However, since the time a node receives the packet is an accumulation of all link delays along the path from source to that node, and the EOT does not guarantee efficient delay to leaf nodes which lie at the boundary of the network and determine the overall delay.

Given a flooding tree structure, Guo et al.⁵ proved that the delay performance can be further improved by utilizing the random nature of a wireless channel. A link quality only represents the average success rate of a link, so that even with a better link, there is no guarantee that the link will deliver the packet earlier than the worse link. The same is true for paths. If there is an opportunity for another path to offer statistically earlier packet delivery than the tree-based one, it will use that one instead. A node therefore can receive the packet through different paths, reducing the chance that a single large-delay node will affect all of its subtree nodes. This approach, opportunistic mechanism, brings flexibility and reliability to the tree-based flooding which solely carries a packet along the tree paths.

Delay-sensitive flooding scheme

In this section, we first sketch the basic idea of the proposed scheme. After that the flooding algorithm is explained in detail, including the following: (1) constructing a DDT, (2) utilizing opportunistic transmissions for faster packet flooding, and (3) implementing a reliable transmission mechanism. Finally, a summary of the scheme is presented concerning the operation flow at the nodes. The idea of the scheme is outlined as follows:

We propose a tree-based flooding structure which aims to improve the flooding delay in WSNs consisting of unreliable links. The key idea is that the tree-build algorithm pays attention to the delay of the path connecting the source with each node rather than individual one-hop transmissions. Because the delay of a flooding packet is determined by the last leaf node receiving the packet, providing an efficient delay path to any node will contribute to a reduction in overall flooding delay. Based on the constructed tree, a statistically expected flooding delay at each node can be measured. Note that when calculating the expected flooding delay, the algorithm ignores the presence of collisions. The expected flooding delay later will be used as one input for the opportunistic forwarding decision.

We use the opportunistic mechanism as an overlaying layer to enhance the delay efficiency of flooding. Given a node, an opportunistic mechanism selects some nodes among the previous-level neighbors, whose links to the node do not belong to the tree, to transmit to the node if the transmission is beneficial in delay. Generally, the nodes selected by the opportunistic mechanism must be the one, which by any chance receives the packet early enough, which can provide a smaller delay to the next-level neighbors (excluding its children) than the tree-based transmissions. Furthermore, the receiver with improved packet delay, in turn, will start to send to its descendants earlier than with the tree-based flooding. Hence, finally, the overall delay of the network is improved. The presence of opportunistic senders, however, raises the problem of collisions at the receiver.

In order to alleviate the collisions at a node, the scheme forms a sender set for the node. Only nodes in the sender set are considered to be opportunistic senders. The algorithm lets each node in the sender set wake up in sequence, so that it can check the channel for potential collisions before deciding to send. Given a set of senders for each node, we propose a novel energy-balancing backoff scheme: a sender with more residual energy has a higher priority to transmit. Such an algorithm is expected to lengthen network lifetime.

Delay-driven tree construction

An ETX of a link is the number of expected transmissions for one success, which is the reciprocal of link quality. In this article, we define path quality to represent the sum of the links’ETX along the path. The goal of the path quality approach is to minimize the total number of transmissions of a single packet along the path from a source to any node. Taking that idea into account, the DDT is built in a manner that each receiver connects to the source node through the path with smallest path quality (smaller is better).

The starting point to build the DDT is the DAG. Basically in the DAG, each receiver might receive a packet from one of the previous-level neighbors. For each node m, we define node ETX, $λ_{m}$ , as the best path quality from the source to the node. Initially, node ETX of the source $λ_{s} = 0$ . Let $P_{m}$ be the set of previous-level neighbors of node m. Parent of node m is determined as in equation (1)

p (m) = \arg min_{s_{i}} ET X_{s_{i} \to m}; s_{i} \in P_{m}

(1)

in which $ET X_{s_{i} \to m} = λ_{s_{i}} + 1 / q_{s_{i} m}$ representing the minimal path cost from source node to node m through node $s_{i}$ , $q_{s_{i} m}$ is the link quality between nodes $s_{i}$ and m, and $p (m)$ is the selected parent of node m. Then, $λ_{m}$ is computed as in equation (2)

λ_{m} = \frac{1}{q_{p (m) m}} + λ_{p (m)}

(2)

Figure 2 shows the pseudocode of an algorithm to compute node ETX for all nodes. Starting from the source node of a DAG, each node computes its node ETX and shares that information with the next-level neighbors. A node, upon receiving the information from its previous-level neighbors (line 5), will extract the node $ETX s$ . After that it calculates its own node ETX (line 6) and then determines the parent. Finally, the computed node ETX is shared with the next-level neighbors (line 11). The iteration ends if all the network nodes get their node ETX. All the processes are done at the initialization phase of the network.

Figure 2.

Node ETX computation.

While building the DDT, for node m (not the source node), it takes the node ETX of each previous-level neighbor $s_{i} \in P_{m}$ and then plus $1 / q_{s_{i} m}$ (referring to equation (2)). Afterward, it compares those sums and takes the smallest one. Meanwhile, each node in the EOT chooses among link qualities $q_{s_{i} m} (s_{i} \in P_{m})$ from previous-level neighbors to itself. It means that the DDT approach needs exactly one additional calculation (i.e. calculating $λ_{p_{i}} + 1 / q_{s_{i} m}$ ) for each previous-level neighboring node $s_{i} \in P_{m}$ than the EOT. As the result, the DDT construction complexity is the same as the EOT.

To illustrate the difference between DDT and EOT, let us consider the example for the network in Figure 1(a). In Figure 3(a) and (b), the constructed EOT and DDT, respectively, are shown. The solid lines connecting nodes represent the tree’s links, while the dotted lines are edges in the communication graph. The arrows point out the packet flow direction of each link. For instance, link quality from node S to nodes A, B, and C are $0.9$ , $0.8$ , and $0.6$ , respectively; thus, node $ETX s$ of these nodes are $1.1, 1.25, and 1.67$ , respectively. For node E, there are two possible senders (i.e. node B and node C). The ETX of the path going through node B: $ET X_{B \to E} = λ_{B} + 1 / q_{BE} = 1.25 + 1 / 0.7 = 2.68$ and the ETX of path going through node C: $ET X_{C \to E} = λ_{C} + q_{CE} = 1.67 + 1 / 0.8 = 2.92$ . Referring to Algorithm 1, node B is selected as parent of node E, and $λ_{E} = 2.68$ . Similarly, the best path from S to D is $S - A - D$ , and the best path from S to G is $S - A - D - G$ , and so forth.

Figure 3.

(a) EOT and (b) DDT structures.

Compared with the EOT, the DDT needs less cumulative transmissions from the source node toward any node. Therefore, the expected flooding delay to each node in DDT is smaller than that in the EOT. For example, with the EOT in Figure 3(a), the path cost from S to G is $1 / 0.6 + 1 / 0.8 + 1 / 0.8 = 4.17$ , which is larger than the ETX introduced by the DDT.

Opportunistic mechanism

In an unreliable transmission environment, the number of retransmissions along a link is a random variable and usually follows the geometric distribution.⁵ On a link with quality q, the first successful transmission happens at a $k th$ trial with probability $q (1 - q)^{k - 1}$ , which means that there is no certainty of when a packet is successfully delivered. Consequently, although the DDT supplies the path with the least expected number of retransmissions toward a node, there are still chances that other links outside the DDT could provide faster packet delivery than the chosen tree path.

The randomness of an unreliable transmission plays a key role in the foundation of the opportunistic mechanism. Given the link qualities, the reception delay probability distribution could be estimated for each network node, assuming that packet is sent only using the DDT links. Such a probability spectrum is calculated in section “Calculating pmf distribution.” Based on the delay probability distribution of node m, in section “Opportunistic link selection,” we show how a previous-level neighbor can estimate the packet delay at node m with confidence level p. In runtime, a previous-level neighbor, after receiving the packet, computes the expected delay to node m, as if it sent to m, and will decide to opportunistically send to node m or not, for earlier delivery. For the rest of this section, we will use the example from Figure 3(b) to illustrate corresponding calculations. Suppose that the working period is 5, the active time slots for each node are presented in Table 1.

Table 1.

Active time slots of network nodes.

Node	S	A	B	C	D	E	F	G
Active time slot	0	1	3	2	4	2	3	0

Calculating pmf distribution

In the case of an unreliable communication link, a sender node might have to send multiple times until it is successful. For example, in Figure 4, node S generates the packet, so the probability that node S has the packet is $1.0$ . To send the packet to node A along the link having a quality of 0.9, node S transmits at node A’s active times: 1, 6, 11, and so on. The probability that node A gets the packet at time 1 (the first trial) is $0.9 \times (1 - 0.9)^{0} = 0.9$ , the probability that node A gets the packet at time 6 (the second trial) is $0.9 \times (1 - 0.9)^{1} = 0.09$ , and so forth. The full distribution is called probability mass function (pmf) of node A.²⁵

Figure 4.

Reception probability distribution of one-hop transmission.

For a node which is multi-hop away from the source, its pmf not only depends on the link quality from which it receives but also is affected by the pmf of its parent. Let $a (m)$ be the active time slot of node m, $t_{m} (j) = a (m) + (j - 1) T$ be the jth active time of node m, and $p_{m} (j)$ be the probability that node m receives the packet at time $t_{m} (j)$ . The $p_{m} (j)$ is computed by the following rule of total probability

\begin{matrix} p_{m} (j) = \sum_{i : t_{p (m)} (i) < t_{m} (j)} \\ \Pr [m receives at t_{m} (j) | p (m) receives at t_{p (m)} (i)] \times p_{p (m)} (i) \end{matrix}

(3)

Formula (3) states that $p_{m} (j)$ is broken up into all possibilities that $p (m)$ receives the packet at time $t_{p (m)} (i)$ earlier than $t_{m} (j)$ . If the $p (m)$ receives the packet at time $t_{p (m)} (i)$ , the conditional probability that node m gets the packet at time $t_{m} (j) > t_{p (m)} (i)$ will simply follow the geometric distribution like the one-hop transmission. For $j > i > 0$ , let $n_{i, j}^{m}$ be the number of times node m becomes active between $t_{p (m)} (i)$ and $t_{m} (j)$

n_{i, j}^{m} = {\begin{matrix} j - i - 1, if a (m) = a (p (m)) \\ j - i + ⌊ \frac{a (m) - a (p (m))}{T} ⌋, otherwise \end{matrix}

(4)

Then, the probability that the first success occurs at time $t_{m} (j)$ is $q_{p (m) m} \times (1 - q_{p (m) m})^{n_{i, j}^{m}}$ . Substituting this value for the conditional probability in formula (3), we get

p_{m} (j) = \sum_{i : t_{p (m)} (i) < t_{m} (j)} q_{p (m) m} \times {(1 - q_{p (m) m})}^{n_{i, j}^{m}} \times p_{p (m)} (i)

(5)

Figure 5 shows an example for the calculation of pmf for node D and node G. If node A receives a packet at time $t_{A} (1) = 1$ , then probability that node D receives the packet at time $t_{D} (1) = 4$ is $p_{D} (1) = q_{AD} \times p_{A} (1) = 0.9 \times 0.9 = 0.81$ because there is no active time of node D between time $t_{p (D)} (1) = t_{A} (1) = 1$ and $t_{D} (1) = 4$ ; therefore, $n_{1, 1}^{D} = 0$ . The $p_{D} (2)$ at time $t_{D} (2) = 9$ is summation of two possibilities: (1) node A receives a packet at time 1 and then transmits successfully to node D at the second trial and (2) node A receives the packet at time 6 and then transmits successfully to node D at the first trial. That summation is $0.9 \times 0.9 \times (1 - 0.9) + 0.09 \times 0.9 = 0.162$ . Similarly, pmf of all nodes can be computed.

Figure 5.

Example of computing pmf.

Opportunistic link selection

After computing the pmf distribution for the whole network, each node estimates its $p - quantile delay$ , $D_{p}$ , if it receives the packet through the DDT. Given a threshold p, $D_{p}$ of a node is the time that the node would have received a packet from its parent with the confidence level of at least p. Suppose that $T (m)$ is the set of active times of node m, the $t_{m}$ is the time when node m receives a flooding packet; then $D_{p} (m)$ is defined as follows

D_{p} (m) = min {x \in T (m) | P (t_{m} \leq x) \geq p}

(6)

Applying that to the example in Figure 5, if $p = 0.9$ , then $D_{0.9} (A) = 1$ , $D_{0.9} (D) = 9$ (as $0.81 + 0.162 > 0.9$ ), and $D_{0.9} (G) = 15$ (since $0.567 + 0.2835 + 0.10206 > 0.9$ ).

When node $s_{i} \in P_{m} \ {p (m)}$ receives a flooding packet at time $t_{s_{i}}$ , it will compute the expected packet delay (EPD) to flood the packet toward node m, noted as $EP D_{s_{i} \to m} (t_{s_{i}})$ . The $EP D_{s_{i} \to m} (t_{s_{i}})$ depends on link quality between node $s_{i}$ and node m and the time $t_{s_{i}}$ as in equation (7)

EP D_{s_{i} \to m} (t_{s_{i}}) = t_{s_{i}} + ⌈ \frac{1}{q_{s_{i} m}} ⌉ \times T

(7)

Note that $⌈ 1 / q_{s_{i} m} ⌉$ is a number of transmissions which node $s_{i}$ is expected to make toward node m. Node $s_{i}$ will compare $EP D_{s_{i} \to m} (t_{s_{i}})$ with $D_{p} (m)$ to make the forwarding decision. Figure 6 represents the cases whether the link $s_{i} \to m$ would be an opportunistic link or not.

Case 1. $EP D_{s_{i} \to m} (t_{s_{i}}) \leq D_{p} (m)$ . The link $s_{i} \to m$ can be considered as an opportunistic link, since the expected time required for sending the packet from node $s_{i}$ to node m would be equal or shorter than sending through DDT.

Case 2. $EP D_{s_{i} \to m} (t_{s_{i}}) > D_{p} (m)$ . The link $s_{i} \to m$ is excluded, since the delay it provides is bigger than that of DDT link.

Figure 6.

Opportunistic link decision.

For instance, assume that the threshold p is set to 0.9, and flooding packet arrives at node B and node C at times 3 and 7, respectively. We already know that $D_{0.9} (D) = 9$ . Node D has two candidates to become opportunistic sender: one is node B and the other one is node C. Both B and C expect two attempts for a successful transmission to node D, since $⌈ 1 / 0.8 ⌉ = ⌈ 1 / 0.5 ⌉ = 2$ . However, B receives a packet at time 3, so it counts two active times of node D after time 3 (i.e. times 4 and 9). Hence, $EP D_{B \to D} (3) = 9$ . For the case of link $C \to D$ , it counts two active times of node D after time 7 (i.e. times 9 and 14), so that $EP D_{C \to D} (7) = 14$ . Comparing with $D_{0.9} (D)$ , link $B \to D$ is considered as an opportunistic link because $EP D_{B \to D} (3) = D_{0.9} (D) = 9$ , while link $C \to D$ is marked as excluded because $EP D_{C \to D} (7) = 14 > D_{0.9} (D) = 9$ . Note that in this case, we call node B a sender. Each node only has one parent, but it can have multiple potential senders.

Reliable transmission

The utilization of opportunistic links leads to multiple senders deciding to send a packet to the same receiver at the same time. To resolve this problem, two steps are applied: building a sender set for each node and an energy-balancing sending prioritization for nodes in the sender set.

Building a sender set

In order to reduce the collisions (caused by the hidden terminal problem), each node maintains a sender set, consisting of nodes that can overhear each other’s transmission. The sender set of a node is the subset of previous-level neighbors in which link quality between any pair of nodes in the set is better than the preset threshold $l_{th}$ . The higher the $l_{th}$ , the higher the probability the nodes in the sender set could overhear each other’s transmissions. Figure 7 describes the selection process. The algorithm first includes the parent of the receiver and then others are considered in the descending order of their link qualities toward the receiver. If any link between the considering candidate and the already selected sender candidates is worse than $l_{th}$ , the considering candidate will not be included in the sender set.

Figure 7.

Building the sender set algorithm.

For instance, in Figure 8, with $l_{th} = 0.7$ , node D is the receiver, and nodes $A, B, and C$ are the previous-level neighbors. Since node A is the parent of node D, it will be included in the sender set of D first: $S_{D} = {A}$ . The next node to be examined is node B, as the link quality $q_{BD} > q_{CD}$ . Because $q_{BA} = 0.7 = l_{th}$ , node B is added to the sender set: $S_{D} = {A, B}$ . Finally, the mechanism checks node C. Although $q_{BC} = 0.8 > l_{th}$ , but because the link quality between node C and node A is $q_{CA} = 0.5 < l_{th}$ , C is not included in $S_{D}$ .

Figure 8.

Sender set construction for node D, with $l_{th} = 0.7$ : (a) A, B, C: previous-level neighbors of D; (b) A is included first; (c) considering node B; (d) B is included; (e) considering node C; node C is excluded; and (f) final sender set.

Energy-balanced sending prioritization

Nodes in the sender set of node m (m can be any node in the network) could overhear each other’s transmission to m with the probability not less than $l_{th}$ . In the next step, the collision problem can be resolved by giving a different backoff time to each member of the sender set. After the backoff timer ends, a node in the sender set listens to the channel before sending. If the channel is clear, the node transmits the packet to node m. Otherwise, it means that there is another node with higher priority sending to m. In this case, the node will mark its intended transmission of the current packet to node m as unnecessary.

In order to define the sending priorities for nodes in the sender set, the existing solution⁵ relies on the link quality toward node m. If there is more than one node wanting to transmit, the one with best link quality to node m will have highest priority to send. This approach helps in very short delay but remains an unbalanced energy problem. The node with highest link quality to node m always takes its turn first if a flooding packet has arrived at it. For instance, in Figure 8, among two nodes in the sender set ${A, B}$ of node D, if the two nodes both have packet, node A will always take turn because its link quality toward node D is higher than that of node B. This prioritization is called link quality–based backoff strategy.

To resolve this, the proposed algorithm takes both the link quality and the residual energy of the sender into account when determining the sending priorities in a sender set. When the packet has arrived, each node $s_{i}$ in the sender set $S_{m}$ of the receiver m will set its backoff timer to $b_{s_{i}}$ as follows

b_{s_{i}} = (1 - \frac{e_{s_{i}} \times q_{s_{i} m}}{E_{0}}) \times T_{0} where s_{i} \in S_{m}

(8)

in which $e_{s_{i}}$ is the residual energy of node $s_{i}$ , $E_{0}$ is the initial energy, $q_{s_{i} m}$ is link quality from node $s_{i}$ to node m, and $T_{0}$ is the maximum backoff timer. Basically, $q_{s_{i} m}$ is the success probability for the link $s_{i} - m$ . Let $δ_{0}$ be the energy amount a node spends on each transmission; we can rewrite the quantity $e_{s_{i}} \times q_{s_{i} m} / E_{0}$ in the following form

\frac{e_{s_{i}}}{δ_{0}} \times {(\frac{E_{0}}{δ_{0}})}^{- 1} \times q_{s_{i} m}

(9)

Then, it can be seen that $e_{s_{i}} / δ_{0}$ is the number of more transmissions node $s_{i}$ could make; $E_{0} / δ_{0}$ is a constant implying the total number of transmissions a node could make in its entire life (until the energy becomes zero). Finally, the quantity $e_{s_{i}} \times q_{s_{i} m} / E_{0}$ can be seen as proportional to how many successes node $s_{i}$ could make toward node m. A node having a large quantity will have small backoff timer. It is obvious that $e_{s_{i}} \times q_{s_{i} m} / E_{0} \in [0, 1]$ ; hence, $t_{s_{i}}$ is bounded in the range $(0, T_{0})$ . Such proposed prioritization is called energy-balanced sending prioritization.

Design summary

The proposed scheme consists of three main parts: the design of a flooding tree, the opportunistic mechanism, and the reliable transmission mechanism. The opportunistic mechanism works in tandem with the reliable transmission approach. While the first allows nodes to send a packet along the link with a smaller delay, the second resolves the collision by assigning different priorities to nodes in the sender set which are intended to transmit to the same node.

In the initialization phase of the network, all nodes cooperate to build the DDT. After the tree construction, in the case of opportunistic utilization, each node in the network will make further steps with DDT as a base structure. Two important parameters of the opportunistic mechanism, the statistical delay’s confidence level p and the sender set’s link quality threshold $l_{th}$ , are preset. Starting from the source node, each node calculates its delay distribution, pmf, and shares with the children. Based on the pmf of the parent, the child node calculates its own pmf distribution, and the process continues until all nodes have their pmf. Next, each node computes its statistical delay, $D_{p}$ . The value of $D_{p}$ of a node depends on p and the node itself, and later will affect the opportunistic decision. In the initializing phase, the algorithm also forms the sender set for each node. After the sender sets are all determined, each node shares its $D_{p}$ with nodes in its sender set. For a different flooding packet, depending on the time a node receives the packet, if the node is in the sender set of the next-level neighbor (excluding its children), it will examine the expected delay it could provide to the next-level neighbor and then make decision whether to forward to that neighboring node or not by comparing the calculated expected delay with the statistical delay $D_{p}$ of the neighboring node. The decision might be different for different flooding packets.

It is worth noting that the opportunistic mechanism is an optional building block to enhance the delay performance of tree-based flooding. We can also use either the energy-balanced sending prioritization or the link quality–based backoff strategy to resolve potential collisions in the sender set, depending on whether the network lifetime or the delay performance is preferred. The number of schemes that will be examined and their abbreviations are described in Table 2.

Table 2.

Scheme names.

Scheme name	Details
EOT	Flooding scheme based on the EOT structure
DDT	Flooding scheme based on the DDT structure
EOTo	Flooding scheme based on the EOT structure, with opportunistic mechanism and link quality–based backoff strategy
DDTo	Flooding scheme based on the DDT structure, with opportunistic mechanism and link quality–based backoff strategy
DDToe	Flooding scheme based on the DDT structure, with opportunistic mechanism and energy-balanced sending prioritization

Performance evaluation

This section evaluates the performance of different flooding schemes based on two tree structures: our design DDT and the best known EOT in Guo et al.⁵ Either flooding operation on the two structures with or without the integration of opportunistic mechanism will be quantified. We also measure the merit of the energy-balancing prioritization in lengthening network lifetime.

Simulation methodology

We use the same assumptions and methodology as in Guo et al.⁵ The network has one source node which has unlimited power, and all the nodes are stationary and homogeneous. Each node picks up its active time slot randomly. The nodes are randomly placed in a two-dimensional squared area, and the source node is positioned at a corner. We vary the duty cycle, network size, and network density and observe the change accordingly. Table 3 shows the simulation’s network configuration.

Table 3.

Network configuration.

Simulation tuner	Duty cycle	Network size	Number of nodes
Duty cycle	2%–20% (2%, 5%, 10%, 15%, and 20%)	300 m × 300 m	800 nodes
Network size	10%	250 m × 250 m–450 m × 450 m	Varying to keep constant density
Network density	10%	300 m × 300 m	200 nodes–1000 nodes

The three following metrics are considered:¹⁸

Average flooding delay. The time elapsed from when the flooding packet is sent out by the source node until it reaches all nodes in the network (called one flooding round). Note that we measure the delay by the number of time slots (one time unit equals one time slot).

Energy consumption. The average amount of energy that each node spends in one flooding round. The value is averaged among all the network nodes.

Network lifetime. The number of flooding rounds until the first node runs out of battery.

For evaluating the average flooding delay and energy consumption, the simulator generates 50 random networks. In each network, 50 flooding packets are generated. The performance metrics are averaged among 50 × 50 cases. For the network lifetime, flooding packets are broadcasted until the first node runs out of battery. The lifetime is averaged among the 50 random networks.

Simulation environment

As mentioned above, an important parameter that controls the delay performance of the opportunistic mechanism is the quality threshold p. The larger the p, the bigger the value of statistical delay $D_{p}$ , which means that more nodes are allowed to make opportunistic transmissions. As a result, delay of a flooding packet is reduced. Similarly, the sender set’s link quality threshold $l_{th}$ impacts the flooding delay. The smaller the $l_{th}$ is, the fewer the nodes included into the sender set. Hence, there is less chance for opportunistic transmission and eventually less delay gain. In this simulation, we set $p = 0.9$ and $l_{th} = 0.7$ to prefer the delay performance.

We ignore the computational energy cost in sensors, as it is relatively small compared to the communication one.²⁶ We adopt the energy consumption model of MICA2 as presented in Table 4.^27,28

Table 4.

Simulation parameters.

Parameter	Value
Energy rate in idle listening	9.6 mJ/s
Energy rate in sleeping	0.33 mJ/s
Energy rate in transmitting	5.76 × 10⁻³ mJ/byte
Energy rate in receiving	0.88 × 10⁻³ mJ/byte
Message size	28 bytes
Time slot	20 × 10⁻³ s
Transmission range	30 m
Initial energy per node	1000 mJ

In an active state, a node consumes 9.6 mJ/s and in a sleeping state, it spends 0.33 mJ/s. In the active state, if a node does a transmission or reception, it costs an additional 5.76 × 10⁻³ mJ/byte or 0.88 × 10⁻³ mJ/byte, respectively. After a node receives the packet, in its subsequent active time slots in the flooding round, the node will not wake up and listen anymore.

Let one flooding round to be the time from when the source node starts to send out the flooding packet, until the packet reaches every node. Energy consumption of node i in one flooding round is the summation of energy for transmitting, receiving, listening (being active without transmitting/receiving), and sleeping as in equation (10)

E_{i} = n_{i}^{t} E^{t} + n_{i}^{r} E^{r} + n_{i}^{l} E^{l} + n_{i}^{s} E^{s}

(10)

in which $E^{t}, E^{r}, E^{l}, and E^{s}$ are the energy spent of a node for transmitting, receiving, listening, or sleeping per time slot, respectively. The $n_{i}^{t}, n_{i}^{r}, n_{i}^{l}, and n_{i}^{s}$ stand for the number of time slots in one flooding round that the node is in the four states mentioned above. Based on Table 4’s parameters, the values of energy spent in each mode per time slot are shown in Table 5.

Table 5.

Node energy consumption in different modes.

Mode	Value
Transmitting $(E^{t})$	0.343 mJ
Receiving $(E^{r})$	0.207 mJ
Listening $(E^{l})$	0.182 mJ
Sleeping $(E^{s})$	6.6 µJ

In one flooding round, a node only receives one time, so we have $n_{i}^{r} = 1$ for all i except the source node that sends out the packet. The sum $n_{i}^{t} + n_{i}^{r} + n_{i}^{l} + n_{i}^{s}$ is the flooding delay (based on the unit time slot). The sum $n_{i}^{r} + n_{i}^{l}$ of node i indicates the flooding delay at that node. Assuming that the source node is excluded, the network consists of N nodes, and then the total energy consumption of the network in one flooding round is calculated as in equation (11)

E_{total} = \sum_{i = 1}^{N} E_{i}

(11)

Impact of duty cycle

Figure 9(a) compares the delays of the EOT and the DDT with different duty cycles (from 2% to 20%). For all the cases, our DDT is around 9% better, and the peak gain is more than 10% when the duty cycle is critically low (duty cycle 2%). The DDT cuts 8.5% off the energy amount that EOT has to spend, as shown in Figure 9(b). When the duty cycle increases, the flooding delay and consumed energy of one flooding round both decrease because each working period contains fewer time slots. Therefore, the time and energy each node spends sleeping decreases. The whiskers show the confidence interval at 95% confidence level. Throughout the collected results, the interval width is less than 4.8% of the corresponding value.

Figure 9.

Comparison between EOT and DDT: (a) delay performance and (b) energy consumption performance.

Figure 10 depicts the enhancement when an opportunistic mechanism is present: the DDTo and EOTo schemes have a similar reduction in delay over DDT and EOT, respectively. This improvement persists throughout all our experiments. However, our purpose is to reflect the best achievable delay performance, so that in the following comparisons, we only include schemes with opportunistic utilization (i.e. EOTo, DDTo, and DDToe).

Figure 10.

Delay improvement using opportunistic mechanism.

Figure 11(a) shows the changes of an average flooding delay by the number of time slots when we vary the duty cycle settings. In this case, DDTo provides the smallest delay, followed by the DDToe, and then the EOTo. Although based on the same flooding tree DDT, in DDTo, the sending priorities among nodes in the sender set are static over time. DDToe balances between the quality of the link and the remaining energy of the sender; thus, the sending role is distributed across different sender candidates over time. Correspondingly, the delay provided by DDToe is slightly bigger than DDTo’s. The reported gain of DDTo compared with the EOTo is around 7.5%, while DDToe’s flooding delay is 6% smaller than the EOTo.

Figure 11.

Flooding performance on different duty cycles: (a) average flooding delay, (b) energy consumption per node, and (c) network lifetime.

Considering the averaged energy consumption per node, for one flooding packet, the DDTo and DDToe show around 6%–8% less energy consumed than the EOTo (Figure 11(b)). This is reasonable, since with the smaller delay of DDTo or DDToe, at the time when the whole network of our two schemes completed flooding, the network with EOTo algorithm continued to operate and consume energy. The levels of energy spent at each node in the two DDT-based schemes are very close, but the number of flooding rounds DDToe can carry is around 3% more than that of DDTo. Compared with EOTo, the DDToe is approximately 6%–7% better. Figure 11(c) shows the increase in network lifetime when the duty cycle increases. With the lower duty cycle, in one flooding round, the higher fraction of energy spent is for sleeping, and the smaller fraction is for transmitting/receiving, so that the network lifetime is proportional to the duty cycle.

Performance comparison for various network sizes

In this test, we evaluate the impact of network sizes on the flooding delay, number of transmissions, and network lifetime. The size of the network varies from 200 to 1000 nodes. The network area is kept squared and its size changes accordingly to keep the network density constant. The duty cycle in this experiment is set to 10%. In Figure 12(a), DDTo and DDToe demonstrate up to 8.3% and 7.5% improvement in delay. Figure 12(b) presents the comparable performance between DDTo and DDToe: both reduce up to 7% energy consumption in one flooding round. In terms of the network lifetime, DDToe is up to 8% longer than the EOTo, while DDTo has up to 7% gain. From Figure 12(c), we can see that DDToe brings the largest number of flooding rounds with the energy-balancing mechanism. As the network size increases, the energy reduced at each node in one round increases, and thus, the number of rounds the network can afford is decreased.

Figure 12.

Flooding performance on different network sizes: (a) average flooding delay, (b) energy consumption per node, and (c) network lifetime.

Impact of network density

In order to observe the performance of DDTo and DDToe with the network density variation, we fix the number of nodes at 800, and let the side length vary between 250 and 500 m. When the side length increases, network density decreases, so that the number of neighboring nodes decreases. Consequently, the paths of the network get longer (i.e. the number of hops). In addition, the probability of finding opportunistic links is reduced because of a smaller number of the node’s neighbors. For those reasons, flooding delay increases, network nodes consume more energy, and network lifetime decreases in all the three schemes (Figure 13). As a result, we can see a 7% delay improvement and an 8.6% energy saving (by DDTo) and up to a 7.5% development of network lifetime (by DDToe) over the EOTo.

Figure 13.

Flooding performance on different network densities: (a) average flooding delay, (b) energy consumption per node, and (c) network lifetime.

Conclusion

In this article, we proposed a new flooding tree structure, a DDT, in which the path from the source to any sensor node is of the smallest cumulative expected number of transmissions. As a result, the delay along each path to a single node is the lowest possible one, and thus, the overall energy consumption of the network is reduced. In addition to that, we introduced an energy-balancing algorithm that spreads the forwarding role based on the residual energy factor, so that it can prolong the network lifetime, with its ability to carry more flooding packets. We use the opportunistic algorithm and the sender set concept to let previous-level neighboring nodes dynamically take over the sending task of a parent of a receiver. Intensive simulation shows that our algorithm stably outperforms the flooding scheme based on EOT around 8% in terms of flooding delay, energy consumption, and network lifetime.

Footnotes

Academic Editor: Yong Lee

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 research was supported in part by PRCP (NRF-2010-0020210), G-ITRC (IITP-2016-R6812-16-0001), and the Smart TV 2.0 Software Platform (no. 10041244).

References

Niu

Cheng

. Energy efficient flooding under minimum delay constraint in synchronous low-duty-cycle wireless sensor networks. In: Proceedings of the IEEE computing, communications and IT applications conference (ComComAp), Beijing, China, 20–22 October 2014, pp.121–126. New York: IEEE.

Guo

Kim

Zhu

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

Whitehouse

. Flash flooding: exploiting the capture effect for rapid flooding in wireless sensor networks. In: Proceedings of the IEEE Infocom, Rio de Janeiro, Brazil, 19–25 April 2009. New York: IEEE.

Cheng

. Dynamic switching-based reliable flooding in low-duty-cycle wireless sensor networks. In: Proceedings of the IEEE Infocom, Turin, 14–19 April 2013, pp.1393–1401. New York: IEEE.

Guo

Jiang

. Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links. In: Proceedings of the 15th annual international conference on mobile computing and networking (MobiCom), Beijing, China, 20–25 September 2009, pp.133–144. New York: ACM.

Lim

Kim

. Multicast tree construction and flooding in wireless ad-hoc networks. In: Proceedings of the 3rd ACM international workshop on modeling, analysis and simulation of wireless and mobile systems (MSWiM), Boston, MA, 20 August 2000, pp.61–68. New York: IEEE.

Choi

Kim

. A new directional flooding protocol for wireless sensor networks. In: Proceedings of the international conference (ICOIN), Busan, Korea, 18–20 February 2004, pp.93–102. Heidelberg: Springer.

Wang

Liu

. Duty-cycle-aware broadcast in wireless sensor networks. In: Proceedings of the IEEE Infocom, Rio de Janeiro, Brazil, 19–25 April 2009, pp.468–476. New York: IEEE.

Chang

Jiang

Sheu

. ADCA: an asynchronous duty cycle adjustment MAC protocol for wireless sensor networks. In: Proceedings of the 2008 IEEE global telecommunications conference (Globecom), New Orleans, LO, 30 November–4 December 2008, pp.1–5. New York: IEEE.

10.

Hong

. Sleeping schedule-aware local broadcast in wireless sensor networks. Int J Distrib Sens N 2013; 9: 12451970.

11.

Chen

Zhu

. A low latency, energy efficient MAC protocol for wireless sensor networks. Int J Distrib Sens N 2015; 11: 946587.

12.

Medidi

Zhou

. Extending lifetime with differential duty cycles in wireless sensor networks. In: Proceedings of the 2007 IEEE global telecommunications conference (Globecom), Washington, DC, 26–30 November 2007, pp.1033–1037. New York: IEEE.

13.

Yagan

Makowski

. Designing securely connected wireless sensor networks in the presence of unreliable links. In: Proceedings of the 2011 IEEE international conference on communications (ICC), Kyoto, Japan, 5–9 June 2011, pp.1–5. New York: IEEE.

14.

Zamalloa

Seada

Krishnamchari

. Efficient geographic routing over lossy links in wireless sensor networks. ACM Trans Sens Netw 2008; 4: 111–143.

15.

. Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links. In: Proceedings of the 5th international conference on embedded networked sensor systems (SenSys), Sydney, NSW, Australia, 6–9 November 2007, pp.321–334. New York: ACM.

16.

Chen

Kao

. Game-based broadcast over reliable and unreliable wireless links in wireless multi-hop networks. IEEE T Mobile Comput 2013; 12(8): 1613–1233.

17.

Rault

Bouabdallah

Challal

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

18.

Anastasi

Conti

Francesco

. Energy conservation in wireless sensor networks: a survey. Comput Netw 2009; 7: 537–568.

19.

Carrano

Passos

Magalhaes

LCS

. Survey and taxonomy of duty cycling mechanisms in wireless sensor networks. IEEE Commun Surv Tutor 2014; 16: 181–194.

20.

Zhao

. On maximizing the lifetime of wireless sensor networks using virtual backbone scheduling. IEEE T Parall Distr 2012; 23: 1528–1535.

21.

Jeong

Kim

Yoo

. Adaptive broadcasting method using neighbor type information in wireless sensor networks. Sensors 2011; 11: 5952–5967.

22.

Couto

Aguayo

Bicket

. A high-throughput path metric for multi-hop wireless routing. In: Proceedings of the 9th annual international conference on mobile computing and networking (MobiCom), San Diego, CA, 14–19 September 2003, pp.134–146. New York: ACM.

23.

Niu

Cheng

. Minimum-delay and energy-efficient flooding tree in asynchronous low-duty-cycle wireless sensor networks. In: Proceedings of the IEEE wireless communications and networking conference (WCNC), Shanghai, China, 7–10 April 2013, pp.1261–1266. New York: IEEE.

24.

Cheng

Niu

. Energy-efficient statistical delay guarantee for duty-cycled wireless sensor networks. In: Proceedings of the 12th annual IEEE international conference on sensing, communication, and networking (SECON), Seattle, WA, 23–25 June 2015, pp.46–54. New York: IEEE.

25.

Stewart

. Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. Princeton, NJ: Princeton University Press, 2011.

26.

Razzaque

Dobson

. Energy-efficient sensing in wireless sensor networks using compressed sensing. Sensors 2014; 14: 2822–2859.

27.

Zalyubovskiy

. LABS: latency aware broadcast scheduling in uncoordinated duty-cycled wireless sensor networks. J Parallel Distr Com 2014; 74: 3141–3152.

28.

Jiang

Ravindran

Choo

. Probability-based prediction and sleep scheduling for energy-efficient target tracking in sensor networks. IEEE T Mobile Comput 2013; 12: 735–747.

Delay-sensitive flooding based on expected path quality in low duty-cycled wireless sensor networks

Abstract

Keywords

Introduction

Related work

Preliminaries and motivation

Delay-sensitive flooding scheme

Delay-driven tree construction

Opportunistic mechanism

Calculating pmf distribution

Opportunistic link selection

Reliable transmission

Building a sender set

Energy-balanced sending prioritization

Design summary

Performance evaluation

Simulation methodology

Simulation environment

Impact of duty cycle

Performance comparison for various network sizes

Impact of network density

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References