Energy-Efficient Reliable Broadcast Protocol for WSNs Based on IEEE 802.15.5

Abstract

We propose two link-layer reliable broadcast protocols for wireless sensor networks based on IEEE 802.15.5. We compare them in terms of energy consumption. By including both positive and negative acknowledgement, our second proposed scheme can effectively reduce the number of unnecessary error control messages and, thereby, significantly reducing the unnecessary power consumption relative to the first scheme. Also, we provide an analytical framework for the evaluation of different reliable broadcast techniques. Simulation results show that Scheme 2 achieves energy savings of up to about 85% compared to Scheme 1.

1. Introduction

Recently, there have been several proposals to provide reliable transmission in wireless sensor networks (WSNs) between the transport layer and the link layer [1–3]. To keep pace with the rapidly increasing use of WSNs, the IEEE 802 standards association has developed standards for WSNs based on the IEEE 802.15 working group.

IEEE 802.15 Task Group 5 has recently released the IEEE 802.15.5 standard [4]. This standard provides an architectural framework enabling wireless personal area network (WPAN) devices to promote interoperable and stable wireless mesh topologies [5].

The IEEE 802.15.5 standard consists of low-rate and high-rate parts. The low-rate part basically targets a variety of applications in WSNs. Although the applications enable systems based on the low-rate part of IEEE 802.15.5 to utilize a fully distributed MAC without any central coordinator, logical groups are formed around each device to facilitate contention-free exchanges while exploring medium reuse over different spatial regions. The membership of devices to these groups can vary over time due to changes in location or topology.

The distributed MAC mechanism ensures high performance and efficient relaying of a MAC frame from a source to a destination in the network, possibly over several multihop relay devices that form an IEEE 802.15.5-based WSN. Although the applications enabled by WSNs are very attractive, there are many technical challenges to overcome in order to build well-functioning robust systems based on IEEE 802.15.5 technology; the identified challenges include scalability, reliability, and energy efficiency. Reliable broadcast is necessary for the IEEE 802.15.5, since many applications in the network depend on broadcasting, including service discovery, device paging, routing information propagation, and even data transfer. Full (i.e., 100%) reliability for those applications is not possible in the case where any node is not reachable via the mesh and its battery is not operable.

By relaxing the full reliability requirement, we can achieve an energy efficiency gain in WSNs based on IEEE 802.15.5. In this paper, we propose two link-layer reliable broadcast protocols for IEEE 802.15.5: Scheme 1 and Scheme 2 and compare them in terms of energy consumption. Scheme 2 reduces unnecessary error control messages and, thereby, significantly reducing unnecessary power consumption relative to Scheme 1.

The rest of this paper is organized as follows. Section 2 describes prior related work as well as the contributions of this paper. Section 3 describes the proposed reliable broadcasting algorithms. Section 4 presents mathematical analysis of the proposed schemes. Performance comparisons with another legacy technique are given in Section 5. Finally, we draw conclusions in Section 6.

2. Related Work and Contributions

Most of the earlier work in the area of reliable broadcast has focused on TDMA slot assignment [6–8]. These schemes require global time synchronization and a certain level of topology information, which are not easy to implement, especially in dynamically changing environments such as WSNs.

Recent works [9, 10] depended on dense deployment of devices to reduce duplication in the relay of broadcast frames. However, the authors did not consider wireless channel errors or lost frames, and the techniques are unlikely to work well in sparse topologies.

The pump slowly, fetch quickly (PSFQ) transport layer mechanism [11] was proposed for reliable retasking/reprogramming of sensors based on negative acknowledgment (NAK) from receivers. The event-to-sink reliable transport (ESRT) protocol was developed in [1]. ESRT is based on the notion of event-to-sink reliability and provides reliable event detection in WSNs without imposing any intermediate caching requirements and with minimum energy expenditure. Another NAK-based scheme for providing sink-to-sensors reliability in WSNs, called GARUDA, is introduced in [3]. GARUDA incorporates an efficient pulsing-based solution in which sensor nodes are informed of an impending reliable short-message delivery by transmitting a specific series of pulses at a certain amplitude and period. The pulses act as NAKs, if any receiver does not receive a broadcast frame from the transmitter.

The aforementioned techniques are all transport-layer reliable broadcast protocols. The biggest problem with end-to-end recovery has to cope with the link-layer errors which accumulate exponentially over multihop sensor nodes. Recovery mechanisms based on end-to-end reliability might waste considerable amounts of the sensor nodes' energy resources. It would be preferable to cure the errors before they propagate along the path, a solution that necessitates link-layer reliability.

There also exist link-layer approaches [12, 13] for reliable broadcast in wireless sensor networks. Forward error correction (FEC) has been an appealing approach to reduce the feedback implosion that usually occurs when a large-scale reliable broadcast is performed [13]. However, the use of FEC in WSNs requires considerable hardware cost and complexity.

Traditionally, reliable broadcast techniques have been based upon positive acknowledgment (ACK), NAK, or both. In the ACK-based approach, a slot-reservation-based reliable broadcast protocol (SRB) [14] was proposed to add a reliability component to the existing broadcast protocol in the IEEE 802.11 MAC. In the SRB, a transmitter needs an ACK from all receivers to guarantee full reliability. However, since ACKs from the receivers are typically synchronized, it will cause significant contention in the wireless channel. This problem is exacerbated as the number of receivers increases and is referred to as the ACK implosion problem.

In another ACK-based approach, Xie et al. [15] proposed the round-robin acknowledge and retransmit (RRAR) protocol to improve the reliability of broadcasting. In this protocol, after the broadcasting is finished, the sender requires a broadcast acknowledgement (BrACK) from one of its neighbors, and this BrACK scheme is performed in a round-robin fashion for all the neighbors of the sender. Thus, this protocol can reduce ACK implosion problem, but it cannot guarantee the reliability of all nodes as the number of receivers increases.

On the contrary, NAKs are well established as an effective mechanism to advertise losses in multihop wireless networks in particular and group communication in general, as long as the loss probabilities are not high. Cooperative loss recovery for reliable multicast (CoreRM) in ad hoc networks [16] is a NAK-based scheme in which the NAK frames are scheduled by random timers to avoid NAK implosion. Since one NAK is sufficient for the sender to be aware that an error has occurred, retransmission of the original frame informs the receivers with later NAK timers, thus allowing them to cancel their scheduled NAKs.

However, NAKs cannot handle the unique cases in which all frames are lost at a particular node in the network. Because such a node will be unaware that a data frame is expected, it will not advertise a NAK to request retransmission. For short message types, like queries consisting of a few frames, the probability is not negligible that a node will fail to receive any of the packets in a message. Because of the above problems, ACK or NAK has not been utilized for broadcasting services in IEEE 802 families such as IEEE 802.11 or IEEE 802.15.

To tackle the above problems, a hybrid scheme that uses both ACK and NAK has been proposed [17]. In this scheme, a transmitter elects a broadcast group leader. To cope with the ACK implosion problem, nonleader receivers use the NAK-based scheme while the leader uses an ACK-based scheme. However, this scheme still does not work in all cases; it will fail, if the leader receives a frame successfully, while all of the other receivers do not.

In this paper, we propose two reliable broadcast protocols for WSNs based on IEEE 802.15.5: Scheme 1 and Scheme 2. Within the aforementioned taxonomy, Scheme 1 is an ACK-based reliable broadcasting scheme, while Scheme 2 is a hybrid scheme. Compared with Scheme 1, Scheme 2 effectively reduces unnecessary error control messages, avoids unwanted collisions, and thus significantly conserves energy in the network. Simulation results show that Scheme 2 achieves energy savings of up to about 85% compared to Scheme 1 and a legacy technique.

3. Reliable Broadcasting Algorithm

In this paper, we assume that the wireless sensor networks form tree network environments (as in Figure 1) based on the IEEE 802.15.5 mesh formation [4]. In such networks, broadcasting is performed over the meshed tree network. For instance, if node A in the example of Figure 1 has broadcast data to send (A is the transmitter or originator), it transmits that data to its children nodes (B, C, and D). After the children nodes receive the data, they transmit the broadcast data to their own children nodes. Thus, in Figure 1, node C transmits data to nodes E and F. Additionally, the nodes transmit the broadcast data to their associated nodes; that is, in Figure 1, node C transmits data to nodes B and D (see details on the formation of the meshed tree in [4]).

Figure 1

Example meshed tree network (Level = 4) following the IEEE 802.15.5 framework; solid and dotted lines represent the relationships of parents to children and of associated neighbors, respectively.

We first consider simple flooding schemes for IEEE 802.15.5 [18]. Simple flooding starts with a source node broadcasting a frame to all its neighbors. Each of those neighbors in turn forwards the frame to all its neighbors exactly once, and this continues until all reachable network nodes receive the frame. IETF (Internet engineering task force) has proposed the use of this flooding scheme for broadcasting and multicasting in ad hoc networks, which are often characterized by low node densities and/or high mobility. However, it does not guarantee that all nodes receive the broadcast frame and can even cause a broadcast storm problem [9].

Consider a scheme in which, in an attempt to guarantee the reliability of all nodes, all receivers acknowledge the receipt of a frame from the transmitter. We refer to this technique as Scheme 1. Scheme 1 will cause severe network degradation due to serious redundancy, contention, and collisions in the network. The likely cause of this degradation is that the acknowledgments from the receivers are typically synchronized, which will lead to considerable contention in the wireless channel (i.e., an ACK implosion problem). The multiple receiver nodes transmit multiple ACK frames after receiving the data frame from the sender. Typically, the sequence of the ACK transmission is scheduled in a manner that avoids collision among the ACK frames. However, if the sequence of the ACK transmission is not scheduled, ACK frames will collide, wasting additional retransmission time. This problem is exacerbated as the number of receivers increases; we will demonstrate this problem in Section 3.

For the IEEE 802.15.5 wireless sensor network, we propose a new reliable broadcast protocol, referred to as Scheme 2, which we have developed to meet two objectives: reliability and lower power consumption. Scheme 2 does not require all receivers to acknowledge a received frame, instead soliciting only a few of the receivers to acknowledge receipt. The basic idea is to delay each receiver's feedback (ACK or NAK) by a random time, thereby, desynchronizing the feedback to reduce contention. Also, if an earlier feedback transmission is overheard by the other receivers, they can suppress their later feedback when they determine that their feedback is redundant. This will significantly reduce collisions and unnecessary feedback, conserving energy overall.

Separate transmission of the ACK and data frames is considered to be redundant. Hence, in Scheme 2, the receiver that needs to send an ACK simply broadcasts its received data frame without explicitly sending its ACK. Then, when the transmitter receives that data frame, it treats it as an implicit ACK. This results in further energy savings in the network.

Scheme 2 also exploits a random timer set in the range of $[0,D]$ at each node, when it needs to send its feedback. Since feedback can be lost due to errors or collisions, the transmitter also employs a timer D. In the proposed scheme, there are 2 types of timers: a NAK timer and an ACK timer. The NAK timer is set at random in the range $[0,\alpha D]$ , while the ACK timer is set at random in the range $[\alpha D,D]$ (see Figure 2). The shorter timer for NAK allows early rebroadcast of the original data to fix errors. The longer timer for ACK is for the case in which all nodes successfully received the data.

Figure 2

The timer used in the proposed scheme.

3.1. Transmitter Behavior

In the proposed scheme, the transmitter performs the following procedure repeatedly and automatically. When it has received broadcast data, the node checks whether the broadcast data frame was received from its child or its parent. If the data is from its child (see line 5 in Algorithm 1), the node broadcasts the data (piggybacked onto the ACK/NAK) to its children and its parent (not to its siblings) and sets its timer D. On the other hand, if the data is from its parent (see line 9 in Algorithm 1), it broadcasts its data to its children (not to its siblings) and sets its timer D. If the node is the originator of the broadcast data, it also broadcasts the data to its children and its parent (not to its siblings) and sets its timer D. In all cases, a node that has received broadcast data from another node does not unicast back to that other node. If timer D expires before receiving any ACK or NAK feedback (see line 15 in Algorithm 1), it retransmits the original data.

Algorithm 1: Transmitter behavior of Scheme  2.

(1)       $\mathcal{C}$ ← the set of children nodes

(2)       $\mathcal{P}$ ← the parent node

(3)      loop

(4)          if Has a data frame then  {Transmission case}

(5)         if Data is from child then  {Upstream case}

(6)      Piggyback the broadcast data onto the ACK/NAK;

(7)      Broadcast the data to $\mathcal{C},\mathcal{P}$ ;

(8)      Set timer D;

(9)   else  if Data is from parent then  {Downstream Case}

(10)      Broadcast the data to $\mathcal{C}$ ;

(11)       Set timer D;

(12)       else

(13)      Do nothing;

(14)       end  if

(15)       else  if The timer has expired then  {Retransmission case}

(16)      Go to Step  5;

(17)       else  if A feedback frame has been received then  {Feedback case}

(18)      if An ACK frame has been received then  {ACK case}

(19)      Transmit the next broadcast data;

(20)      Set timer D;

(21)       else if A NAK frame has been received then  {NAK case}

(22)      Retransmit data;

(23)      Set timer D;

(24)      else

(25)     Do nothing;

(26)      end if

(27)       else

(28)      Do nothing;

(29)       end if

(30)   end loop

3.2. Receiver Behavior

After receiving broadcast data, the receiver checks whether the broadcast data is erroneous. Based on the result of error detection/correction (see line 5 in Algorithm 2), the receiver uses a NAK/ACK timer and sends the feedback frame to transmitter. When a node receives rebroadcast data (see line 10 in Algorithm 2), the receiver node cancels its timer (either NAK or ACK). This can reduce unnecessary feedback to the transmitter.

Algorithm 2: Receiver behavior of Scheme  2.

(1)     ${\mathcal{F}}_{𝒟}$   ←the  received  broadcast  data

(2)    loop

(3)   if Broadcast data has been received then

(4)    if ( ${\mathcal{F}}_{𝒟}$   == broadcast  data) then

(5)      if ( ${\mathcal{F}}_{𝒟}$   == erroneous data) then

(6)     Set the NAK timer in the range $[\mathit{0},\mathit{\alpha }\mathit{D}]$ ;

(7)      else

(8)     Set the ACK timer in the range $[\mathit{\alpha }\mathit{D},\mathit{D}]$ ;

(9)      end  if

(10)     else  if ( ${\mathcal{F}}_{𝒟}$   == rebroadcast data) then

(11)     Cancel timer;

(12)     if   ${\mathcal{F}}_{𝒟}$ already exists then

(13)        Do nothing;

(14)     else

(15)        Go to Step  5;

(16)     end  if

(17)     else

(18)     Do nothing;

(19)     end  if

(20)   else  if Timer has expired then

(21)     Respond with feedback (NAK or ACK) to the transmitter

(22)   else

(23)     Do nothing;

(24)   end  if

(25)  end  loop

The following sequence will continue up to a predefined number of times. First, the transmitter broadcasts its data. Upon receiving it, the first and following NAKs are transmitted back to the transmitter from the receivers. Due to the first NAK, the transmitter rebroadcasts the data. Then, each other node suppresses its timer (either NAK or ACK), if the timer is in a waiting state. Suppose that an error is detected at one receiver. Then, the receiver sends its NAK. Upon receipt of the NAK, the transmitter rebroadcasts its data. Finally, all receivers have the error-free data. While one of the receivers sends its ACK, the transmitter can initiate the next broadcast data transmission.

3.3. Example of Scheme 2

Figure 3 shows an example scenario for the proposed scheme (downstream case at node C). As shown in the figure, there are 12 nodes in the network; let node A be the originator. At $T=t_0$ , parent node A broadcasts a data frame (Figure 3(a)). Then, node B replies with ACK at $T=t_0$ (Figure 3(b)) and node C may forward the broadcast data to its children (Figure 3(c)). However, if node F receives the data with errors, it replies with NAK to transmitter node C at $T=t_0+0.8D$ (Figure 3(d)). At about the same time, node E forwards the data to its children (Figure 3(d)). At $T=t_0+0.9D$ , node C rebroadcasts the data to its children, and node E suppresses its ACK for the previous broadcast data and also silently ignores the rebroadcast data (Figure 3(e)). After $T=t_0+0.9D$ , node F receives the rebroadcast data from node C and then forwards the data to its children (Figure 3(f)). Then node F receives ACK replies from its children.

Figure 3

Example of the proposed scheme (downstream case at node C).

Another example scenario for the proposed scheme is shown in Figure 4; here, node E is the originator node and a child of node C. At $T=t_0$ , it broadcasts to its children nodes G, H, and I and its parent node C (Figure 4(a)). Then, node C broadcasts data piggybacked onto the ACK to transmit the data to node A and F at $T=t_0+0.6D$ (Figure 4(b)). However, if node A receives the data with errors, it immediately replies with NAK to node C (Figure 4(c)). After correctly receiving broadcast data from node C, node A broadcasts the data, piggybacked onto the ACK, to nodes B and D (Figure 4(e)); also, node F broadcasts the data to its children nodes (Figure 4(f)). Finally, node B replies with ACK and the broadcast transmission is complete.

Figure 4

The example of the proposed scheme (upstream case at node E).

4. Analysis of the Proposed Scheme

We now provide a mathematical model measuring the energy consumption in the cases of a scheme based on ACK only, one based on NAK only, and the proposed scheme, which uses both ACK and NAK. To measure energy consumption, we calculate the minimum number of transmissions that will guarantee full reliability. Let $E[N]$ be the expected number of nodes that successfully receive a broadcast frame, where N is the number of nodes. For an ACK-based scheme, $E[N]$ is calculated as

$$\begin{array}{cc}& E\left[N\right]={\sigma }_{\text{ACK}}{\left(1-{\sigma }_{\text{ACK}}\right)}^{\left(N-qN-1\right)}\left(\gamma \right),\end{array}$$

(1)

where σ denotes the probability that a node transmits in one time slot, q is the frame error rate, and γ denotes the number of time slots. For a NAK-based scheme, $E[N]$ is calculated as

$$\begin{array}{cc}& E\left[N\right]={\sigma }_{\text{NAK}}{\left(1-{\sigma }_{\text{NAK}}\right)}^{\left(qN-1\right)}\left(\gamma \right)\left(N-qN\right).\end{array}$$

(2)

Lastly, in the proposed scheme, $E[N]$ is calculated as

$$\begin{array}{l}E\left[N\right]={\sigma }_{\text{ACK}}{\left(1-{\sigma }_{\text{ACK}}\right)}^{\left(N-qN-1\right)}\left(\gamma \right)\left(N-qN\right)\hfill \\ +{\sigma }_{\text{NAK}}{\left(1-{\sigma }_{\text{NAK}}\right)}^{\left(qN-1\right)}\left(\gamma \right)\left(1-qN\right).\hfill \end{array}$$

(3)

The minimum number of the transmissions (ℜ) can be evaluated as follows:

$$\begin{array}{cc}& \Re =\arg \min \left(n,{{\displaystyle \sum }}_{n=1}^{\infty }{E}^n\left[N\right]>N\right).\end{array}$$

(4)

In an ACK-based scheme and when $q=0.01$ , ℜ increases as the number of receiver nodes increases (Figure 5); this is because the probability of collisions increases with the number of nodes. However, ℜ is nonincreasing with the number of nodes in the NAK-based and proposed schemes. In the low-error-rate regime, fairly few receivers will fail to receive the broadcast data frame. Therefore, the NAK frame is likely to be successfully delivered in the NAK-based scheme and the proposed scheme. However, if the NAK frame is lost, the sender does not rebroadcast. For this reason, the NAK-based and proposed schemes do not provide the full reliability but consume less energy.

Figure 5

ℜ versus number of nodes ( $q=0.01$ ).

In the proposed scheme, increasing the channel error rate with $N=10$ has no effect on ℜ, whereas ℜ increases with channel error rate in the schemes based on ACK only and on NAK only (Figure 6); that is to say, our proposed scheme is insensitive to error rate. Especially, ℜ is smallest in the proposed scheme among the three schemes tested when the error rate is 0.3 or greater.

Figure 6

ℜ versus channel error rate ( $N=10$ ).

5. Performance Evaluation

To evaluate the efficiency of Scheme 2, we developed a network simulator based on ns-2 [19]. The ns-2 simulator incorporates the IEEE 802.15.5 specification. The IEEE 802.15.5 simulator module includes a unicast routing algorithm, an association procedure, and a disassociation procedure. Additionally, the simulator provides an option of simple flooding, Scheme 1 or Scheme 2. The distance between each pair of neighbors is less than 11 m. The transmission range is 12 m (see Table 1), and the simulator generates a random topology (e.g., see Figure 7). In this section, we compare Scheme 2 with simple flooding and Scheme 1 through simulations, measuring the proportion of nodes that successfully receive data, as well as ℜ, in various conditions. Because it is proportional to energy consumption, ℜ can be used as an energy budget.

Table 1

Simulation Parameters.

Parameters	Value
Number of nodes	Variable
Neighbor distance	7–11 m
Tx range	12 m
PAN coordinator (PC)	Bottom node (or any designated node)
Network startup	PC start at 0.0 Any other nodes: random time from 1.0 to 3.0
Packet error rate	10%

Figure 7

NS-2 WSN simulator.

Figure 8 shows the proportion of nodes that successfully received the data to the total number of nodes in each of the transmission schemes: Scheme 1, Scheme 2 (α = 0.75, 0.50, 0.25), and simple flooding. As can be seen from the figure, simple flooding does not guarantee 100% reliability. Simple flooding performs especially poorly as the number of nodes increases to near 50, making this scheme unsuitable for applications that require a decent degree of reliability. Hence, simple flooding cannot be used for many applications in IEEE 802.15.5 WSNs; so we exclude it from further performance comparisons. Scheme 2 is more reliable than simple flooding, but also does not provide full reliability because of NAK implosion. As the alpha variable which is related to NAK transmission period is increased, probability of NAK collisions can be decreased significantly. For that reason, Scheme 2, which has a large alpha variable, is more reliable than any other Scheme 2. Among the schemes tested, only Scheme 1 provides full reliability.

Figure 8

The proportion of nodes that successfully receive the data versus the number of nodes (channel error rate = 10%).

Now, to measure the energy conservation that can be realized by using Scheme 2, we compare the number of broadcast data frames and control frames that are generated per broadcast data frame, including rebroadcasting and NAK frames (Figure 9). This number will be directly proportional to the energy consumption, so we use this measure as an energy budget. As observed in the figure, the energy consumption of Scheme 2 is much less than that of Scheme 1. Especially, Scheme 2, which has a small alpha variable, can conserve more energy. This means that the smaller the alpha variable, the lower probability of ACK collisions, and it can reduce the unnecessary retransmissions. Therefore, we can choose either of them (Scheme 1 or Scheme 2) depending on the desired level of reliability or energy efficiency, using Scheme 1 to ensure full reliability and Scheme 2 for low-energy operation.

Figure 9

Number of transmissions per node versus the number of nodes (channel error rate = 10%).

6. Conclusion

In this paper, we propose two reliable broadcast protocols for wireless sensor networks based on IEEE 802.15.5: Scheme 1 and Scheme 2. Scheme 1 is an ACK-based reliable broadcasting scheme, while Scheme 2 is a hybrid scheme. Compared to Scheme 1, Scheme 2 effectively reduces unnecessary error control messages and avoids unwanted collisions, thereby realizing considerable energy savings in the network overall. Simulation results show that Scheme 2 achieves energy savings of up to about 85% compared to Scheme 1 and the other legacy technique.