On Minimum-Latency Broadcast in Multichannel Duty-Cycled Wireless Sensor Networks

Abstract

Broadcast has critical significance for wide application of wireless sensor networks (WSNs). Minimum-latency broadcast (MLB) studies how to devise a broadcast schedule, which can achieve minimum broadcast latency with no signal interference. In multichannel duty-cycled WSNs, nodes can exploit multiple channels to communicate and periodically fall asleep after working for some time. Nevertheless, most solutions to the MLB problem either focus on nonsleeping scenarios or only exploit one single channel. Therefore, we investigate the MLB problem in multichannel duty-cycled WSNs in this paper and call this problem as MLBCD problem. We prove that MLBCD problem is NP-hard. We propose a new concept of active interference graph (AIG). Based on AIG, we present one novel approximation broadcast algorithm called NAB to solve the MLBCD problem. We prove that our proposed NAB algorithm achieves provable performance guarantee. The results of our extensive evaluations show that NAB algorithm can significantly improve the broadcast latency.

1. Introduction

Broadcast has critical significance for wide application of wireless sensor networks (WSNs). WSNs usually consist of many sensor nodes, which communicate through radio transmissions on multiple channels [1]. Sensor nodes often have limited energy, and to make effective use of the limited energy, these nodes periodically fall asleep after working for some time. In many scenarios, nodes independently determine their sleep/active cycles without coordination [2–5]. Moreover, since the data of WSNs may be outmoded very quickly, broadcast should be completed with low latency. However, in duty-cycled scenarios, a node can receive data only at its active state, which brings a great challenge for designing efficient broadcast schemes.

Minimum-latency broadcast (MLB) studies how to devise a broadcast schedule, which can achieve minimum broadcast latency with no signal interference. This problem has attracted plenty of researches during recent years. Gandhi et al. [6] have proved the NP-hardness of MLB problem in WSNs without sleep/active cycles in single-channel scenarios. Researchers have proposed many solutions to this problem [6–11]. Nevertheless, most solutions to the MLB problem either focus on nonsleeping scenarios or only exploit one single channel. Sensor nodes in duty-cycled scenarios can only receive data when they are active. Moreover, nodes can exploit multiple channels to communicate without signal interference. Most existing algorithms may incur high latency with simple extension. Thus we are motivated to study the MLB problem in multichannel duty-cycled WSNs (we call it as MLBCD problem) and to propose an efficient solution to this problem.

The transmissions are affected by signal interference. Protocol interference model is adopted as the interference model in this paper, which is a commonly used model in many researches [9–11]. Under this model, the interference range and the transmission range of one node are two disks, and the interference range of one node is usually larger than its transmission range. A node's data transmission may prevent other nodes in its interference range from correctly receiving data.

To solve the MLBCD problem, we should avoid the signal interference among the transmission links. The locations of sensor nodes are critical for judging whether these nodes are in the interference range of other nodes. Therefore, the MLBCD problem is an important location-related challenge in WSNs, and we focus on devising an efficient solution to this problem. In this paper, we assume that all the nodes know their locations in advance. The location information can be achieved by using fine-grained localization techniques [12–14]. These techniques exploit a few anchor nodes with known locations to derive the locations of other nodes and can achieve location information with high accuracy at the centimeter level.

To avoid the signal interference among the data transmissions, we need to choose some nodes as the forwarding nodes and carefully schedule the time when these nodes transmit the message. Multichannel duty-cycled scenarios have the following special features. First, the transmitter node can only send data to its receiver node when the receiver node is active. Second, it may require several times of data transmission for a node to inform all its receiver nodes. Third, multiple channels can be used to avoid interference. Therefore, it is critical to design efficient algorithms based on these special features.

This paper investigates the MLBCD problem, and to the best of our knowledge, our work is the first solution to this problem. To solve this problem, we present a new concept of active interference graph (AIG). This graph shows the interference relationship among the broadcast links and is associated with the nodes’ active time-slots. Based on AIG, we are motivated to devise an efficient approximation algorithm called NAB for the MLBCD problem under protocol interference model, which can provide an interference-free broadcast scheduling and can achieve provable performance guarantee.

In this paper, we have made the following contributions.

• (1)

We give the formulation of MLBCD problem and prove that this problem is NP-hard. Thus it is hard to devise an efficient polynomial-time algorithm which can minimize the broadcast latency without interference.

(2)

We propose a new concept of active interference graph (AIG), which facilitates the design of our interference-free scheduling algorithm.

(3)

We present an algorithm called NAB with an approximation ratio of $\left(⌈{\chi }_{\alpha +2}/m⌉+⌈{\chi }_{\alpha +1}/m⌉\right)\left|T\right|$ , where α denotes the ratio of a node's interference radius to its transmission radius, m denotes the number of channels, and $\left|T\right|$ denotes the amount of time-slots in one scheduling period. ${\chi }_{\lambda }$ is a function of λ, which is equal to $\left(\pi /\sqrt{3}\right){\lambda }^2+(\pi /2+1)\lambda +1$ .

(4)

We implement our algorithm and evaluate its performance. The results of our extensive evaluations show that NAB algorithm can significantly improve the broadcast latency.

The remainder of this paper is organized as follows. In Section 2, we detail the related work. Section 3 introduces the network model, the problem formulation, and some graph-theoretic definitions. We present our NAB algorithm in Section 4. In Section 5, we theoretically analyze the performance of our algorithm. The results of extensive simulations are shown and analyzed in Section 6. Finally, we conclude this paper in Section 7.

2. Related Work

Broadcast is a critical operation in WSNs and thus has attracted plenty of researches [9–11, 15–22] on this operation. In this paper, we only focus on the work which solves the MLB problem due to the space limit.

Many algorithms [9–11] have been proposed to address the MLB problem under protocol interference model. An efficient algorithm is proposed in [9], which achieves a ratio of $2\pi {\alpha }^2$ and turns out to be 26 if α equals 2. To solve the MLB problem, Mahjourian et al. [10] further take the carrier sensing range into consideration and prove that if the carrier sensing range is equal to the interference range, their algorithm achieves a ratio of $O({\alpha }^2)$ , and the constant before ${\alpha }^2$ is 4. A better approximation algorithm is proposed in [11] with a ratio of $6{⌈\left(2/3\right)(\alpha +2)⌉}^2$ . However, all these algorithms discussed above are based on the assumption that all the nodes do not fall asleep.

The broadcast problem in duty-cycled scenarios has been studied in [19–25]. The MLB problem in duty-cycled scenarios is investigated in [19, 20, 24, 25]. Hong et al. [19] propose ELAC-SC algorithm, which achieves a ratio of $O({\alpha }^2)$ , and the constant before ${\alpha }^2$ is $4\left|T\right|$ . Nevertheless, the ELAC-SC algorithm incurs high broadcast latency because of leaving a large number of idle scheduling periods unused.

Another piece of work [20] gives a better solution with a ratio of $\mathrm{17}\left|T\right|$ but is not suitable for protocol interference model. Xu et al. [25] develop a delay efficient broadcast scheduling algorithm for duty-cycled multihop wireless sensor networks with a small ratio, but they assume that a node's interference range equals its transmission range. An efficient solution for the MLB problem in duty-cycled scenarios under protocol interference model is proposed in [24], which achieves low broadcast latency.

However, all the solutions discussed above only consider the single-channel scenarios and are not suitable for multichannel scenarios. Wan et al. [1] propose an efficient broadcast algorithm in multichannel scenarios, but their work assumes that all nodes are active. Hence, this paper focuses on devising an efficient solution to the MLBCD problem, which can provide an interference-free broadcast scheduling and can achieve a small approximation ratio.

3. Preliminaries

3.1. Network Model and Assumptions

In this paper, we consider a multichannel duty-cycled wireless sensor network and model it as a UDG $G=(V,E)$ , where V denotes the set of all the n nodes in this network and E denotes the set of edges among these nodes, which are in the transmission range of other nodes. Protocol interference model is adopted as the interference model. We denote the transmission radius and the interference radius by r and $r_f$ , respectively. α denotes the ratio of $r_f$ to r, and we call it as the interference ratio. Each node can use m channels to communicate, and we use ${\text{Ch}}_{\mathrm{1}},{\text{Ch}}_{\mathrm{2}},\dots ,{\text{Ch}}_m$ to denote different channels. The transmissions on different channels can be carried out simultaneously without interference.

We suppose that nodes decide when to sleep without coordination in advance. We divide the whole scheduling time into several scheduling periods with the same number of time-slots. We denote one scheduling period by T, which contains several time-slots $\mathrm{0,1},\dots ,\left|T\right|-\mathrm{2}$ , and $\left|T\right|-\mathrm{1}$ . The active time-slot of each node v is a time-slot of T. A node can wake up to send data at any time-slot as required but can only receive data when it is active. We define the duty cycle as the ratio of a node's active time to the whole scheduling time. In this paper, the duty cycle equals to $\mathrm{1}/\left|T\right|$ .

We assume that a node cannot send and receive data at the same time. $R_s$ denotes the maximum depth of the breadth-first-search (BFS) tree, which is rooted at the source node s.

3.2. Problem Formulation

This paper investigates the broadcast problem in multichannel duty-cycled scenarios, where a source node s sends its message to all the other sensor nodes at time-slot 0. The broadcast task is completed when all the sensor nodes receive the message. The broadcast scheduling problem is modeled as assigning each node's transmitting time-slot. Interference-free broadcast scheduling aims to minimize the latency when each node is informed without signal interference. Therefore we can formulate the MLBCD problem as follows.

Definition 1.

MLBCD problem: given a multichannel duty-cycled wireless sensor network $G(V,E)$ and a single source node s, find a broadcast scheduling S such that the broadcast latency is minimized and all the nodes can be informed without interference.

Next we prove the NP-hardness of the MLBCD problem.

Lemma 2.

The MLBCD problem is NP-hard.

Proof.

If we set the interference ratio α as 1 and set the number of channels as 1, then the MLBCD problem will reduce to the MLB problem under the single-channel scenario without sleeping cycles, which has been proved to be NP-hard in [19]. Since the special case of the MLBCD problem is NP-hard, this lemma holds.

3.3. Graph-Theoretic Definitions

In this subsection, we give some graph-theoretic definitions. $G[U]$ denotes a subgraph of G, which is induced by V's subset U. An independent set (IS) U of G satisfies that the edge set of $G[U]$ is empty. A maximal independent set (MIS) U of G satisfies that U is not a subset of G's any other IS. According to [26], in a half-disk of radius $r_{\mathrm{1}}$ , the number of points with mutual distances at least $r_{\mathrm{2}}$ is at most ${\chi }_{r_1/r_2}$ .

Coloring of a graph G is to assign natural numbers to each node in this graph. If two nodes are adjacent in this graph, then their assigned numbers are different. First-fit coloring of a graph is to assign each node with the smallest number which is not used by its neighboring nodes. Particularly, the first-fit coloring in smallest-degree-last ordering requires at most $\varphi (G)+1$ colors, where $\varphi (G)$ is the maximum value of the minimum degrees of all subgraphs in G [26].

4. Approximation Algorithm

In previous section, we have proved that the MLBCD problem is NP-hard. In this section, we propose an approximation algorithm called NAB. Before detailing NAB algorithm, we present a new concept of active interference graph (AIG).

4.1. Active Interference Graph

Recall that a node can transmit its data to its receiver node only when its receiver node is active. If there are some broadcast links for scheduling, we construct several interference graphs as follows. For each active time-slot t of all the receiver nodes, we construct an interference graph $G_t=(V_t,E_t)$ . $V_t$ includes the transmitter nodes if at least one of their receiver nodes is active at time-slot t. The interference relationship only involves the links between these transmitter nodes and their receiver nodes with the active time-slot t.

We take an example to explain AIG. As shown in Figure 1(a), nodes $v_1$ , $v_2$ , and $v_3$ are transmitter nodes and nodes $v_4$ , $v_5$ , $v_6$ , $v_7$ , $v_{\mathrm{8}}$ , and $v_9$ are their respective receiver nodes. The solid lines denote the transmission relationship, and the dotted lines denote the interference relationship. The numbers beside the receiver nodes are active time-slots of these nodes. According to the construction method of AIG, we achieve three interference graphs $G_{\mathrm{1}}$ , $G_{\mathrm{2}}$ , and $G_{\mathrm{3}}$ as shown in Figure 1(b).

Figure 1

Active interference graph.

4.2. NAB Algorithm

Based on AIG, we propose the NAB algorithm. The main steps of the NAB algorithm are shown in Algorithm 3. We then detail this algorithm. The first and second steps are to divide all the nodes according to the depths of these nodes in the BFS tree $T_{\text{BFS}}$ rooted at source node s. $R_s$ denotes the maximum depth of $T_{\text{BFS}}$ .

Since MIS has special geometric features, we then make the best of these features. The third step is to construct the MIS from the top layer to the bottom layer in $T_{\text{BFS}}$ . The nodes in MIS are not connected, and thus we choose some connector nodes in $T_{\text{BFS}}$ to connect these nodes layer by layer based on the minimal cover rule.

The fourth step is to construct the broadcast tree $T_B$ based on MIS. The connector nodes are assigned as the father nodes of nodes in MIS. For the other nodes, which neither are connector nodes nor are in MIS, we choose some nodes in MIS at the same layer or at the topper layer as their father nodes.

The fifth step is to schedule the broadcast based on $T_B$ layer by layer. At each layer, we first schedule father nodes of nodes in MIS to broadcast the message to nodes in MIS and then schedule the broadcast from nodes in MIS to their children nodes. Note that each broadcast link is related to a node in MIS.

We then construct AIG based on these broadcast links. To avoid signal interference, we require a coloring method to color the nodes in AIG. Nodes with different colors cannot broadcast the data at the same time-slot on the same channel. To use the features of MIS, we adopt the first-fit coloring method to color the nodes in the smallest-degree-last ordering of AIG.

Algorithm 3 (NAB).

 

Input. Use $G=(V,E)$ , s.

Output. Broadcast scheduling:

• (1)

construct the BFS tree $T_{\text{BFS}}$ rooted at source node s;

(2)

assign $MaxDepth(T_{\text{BFS}})$ to $R_s$ , and divide V into different layers $L_0,L_1,\dots ,L_{R_s}$ ;

(3)

construct the maximal independent set (MIS) layer by layer, and choose some connector nodes in $T_{\text{BFS}}$ to connect the nodes in MIS based on the minimal cover rule;

(4)

construct the broadcast tree $T_B$ based on MIS;

(5)

schedule the broadcast based on $T_B$ layer by layer; at each layer, first schedule father nodes of nodes in MIS to broadcast the message to nodes in MIS, and then schedule the broadcast from nodes in MIS to their children nodes;

(6)

construct AIG based on these broadcast links, and adopt the first-fit coloring method to color the nodes in the smallest-degree-last ordering of AIG;

(7)

schedule the transmitting time-slots of father nodes based on their colors on different channels;

(8)

return broadcast scheduling.

Finally, we schedule the transmissions from the father nodes to their children nodes as follows. The scheduling works from the top layer to the bottom layer. The scheduling time $t_s$ starts at time-slot 0. At each layer $L_i$ , the message is first delivered to nodes in MIS, and $t_s$ proceeds to the smallest times of $\left|T\right|$ when the previous scheduling finishes. Then nodes in MIS broadcast the message to their children nodes. Similarly, $t_s$ proceeds to the smallest times of $\left|T\right|$ when the scheduling finishes.

To avoid the interference among the transmissions, we schedule the transmissions based on the colors of father nodes in AIG. For father nodes with different colors in $G_i$ ( $0\le i\le \left|T\right|-1$ ), we schedule the transmissions on different channels. If the number of colors $n_c$ is smaller than the number of channels m, the transmissions are scheduled on channels ${\text{Ch}}_1,{\text{Ch}}_2,\dots ,{\text{Ch}}_{n_c}$ at time-slot $t_s+i$ . Otherwise, father nodes with the first m colors are scheduled on channels ${\text{Ch}}_1,{\text{Ch}}_2,\dots ,{\text{Ch}}_m$ at time-slot $t_s+i$ . Father nodes with the next m colors (if available) are scheduled on channels ${\text{Ch}}_1,{\text{Ch}}_2,\dots ,{\text{Ch}}_m$ at time-slot $t_s+\left|T\right|+i$ . We repeat this process until all the father nodes are considered. The transmission time-slot increases $\left|T\right|$ time-slots in each loop.

5. Performance Analysis

In the previous section, we detail our NAB algorithm. In this section, we analyze the correctness and the approximation ratio of NAB algorithm. To analyze the approximation ratio, we first give the lower bound of the broadcast latency for the MLBCD problem and the worst-case latency of NAB algorithm.

Theorem 4.

The NAB algorithm is correct and provides an interference-free broadcast scheduling.

Proof.

The NAB algorithm first layers all the nodes and constructs the broadcast tree based on MIS. The NAB algorithm then schedules the broadcast layer by layer. At each layer, the message will be first delivered to nodes in MIS, and then these nodes broadcast the message to their children nodes at the same layer or at the lower layer. Therefore all the nodes can receive the broadcast message. The transmitting time-slots are scheduled based on the colors of nodes in AIG. According to the scheduling method, interfering broadcast links are scheduled at different channels or at different scheduling periods. Thus, the scheduled transmissions are interference-free.

Lemma 5.

The lower bound of the broadcast latency for the MLBCD problem is at least $R_s$ time-slots.

Proof.

Since the maximum depth of the BFS tree rooted at source node s is $R_s$ , it is easy to prove that node s requires at least $R_s$ time-slots to finish the broadcast task. Hence, this lemma holds.

Lemma 6.

If all the transmitter nodes are nodes in MIS, then, for these broadcast links, the number of colors of nodes in AIG is at most ${\chi }_{\alpha +1}$ .

Proof.

Consider the leftmost transmitter node v in MIS. If other nodes in MIS interfere with node v, then these nodes must lie in a half-disk of radius $r+r_f$ centered at node v. The number of these nodes is at most ${\chi }_{(r+r_f)/r+1}-1={\chi }_{\alpha +1}-1$ . Thus the minimum degree of the subgraph of AIG is bounded by ${\chi }_{\alpha +1}-1$ . The number of colors of nodes in AIG is at most the minimum degree plus one. Hence, this lemma holds.

Lemma 7.

If all the receiver nodes are nodes in MIS, then, for these broadcast links, the number of colors of nodes in AIG is at most ${\chi }_{\alpha +2}$ .

Proof.

Consider the leftmost transmitter node v. If another transmitter node u interferes with node v, then this node must have one child node w in MIS. This child node must lie in the half-disk of radius $r_f+2r$ centered at node v. The number of all the children nodes like node w is at most ${\chi }_{(r_f+2r)/r+1}-1={\chi }_{\alpha +2}-1$ . Thus the minimum degree of the subgraph of AIG is bounded by ${\chi }_{\alpha +2}-1$ . The number of colors of nodes in AIG is at most the minimum degree plus one. Hence, this lemma holds.

Theorem 8.

The worst-case latency of NAB algorithm is $(⌈{\chi }_{\alpha +2}/m⌉+⌈{\chi }_{\alpha +1}/m⌉)\left|T\right|R_s-\left(⌈{\chi }_{\alpha +2}/m⌉+⌈{\chi }_{\alpha +1}/m⌉-1\right)\left|T\right|$ .

Proof.

At the top layer, there is only one node s. Thus the time for node s to inform all the nodes at layer 1 is at most $\left|T\right|$ time-slots. From layer 2 to layer $R_s$ , the process splits into two phases. In the first phase, nodes in MIS receive the broadcast message from their father nodes. According to Lemma 7 and the scheduling method, we have that the first phase takes at most $⌈{\chi }_{\alpha +2}/m⌉\left|T\right|$ time-slots. In the second phase, nodes in MIS broadcast the message to their children nodes. According to Lemma 6 and the scheduling method, this phase takes at most $⌈{\chi }_{\alpha +1}/m⌉\left|T\right|$ time-slots. We combine the time of these two phases, and the worst-cast latency of NAB algorithm follows that

$$\begin{array}{l}\text{Latency}\left(\text{NAB}\right)\le \left|T\right|+{\displaystyle \sum }_{i=2}^{R_s}‍\left(⌈\frac{{\chi }_{\alpha +2}}{m}⌉\left|T\right|+⌈\frac{{\chi }_{\alpha +1}}{m}⌉\left|T\right|\right)\\ =\left(⌈\frac{{\chi }_{\alpha +2}}{m}⌉+⌈\frac{{\chi }_{\alpha +1}}{m}⌉\right)\left|T\right|R_s\\ \hspace{1em}-\left(⌈\frac{{\chi }_{\alpha +2}}{m}⌉+⌈\frac{{\chi }_{\alpha +1}}{m}⌉-1\right)\left|T\right|.\end{array}$$

(1)

Theorem 9.

The approximation ratio of NAB algorithm is at most $(⌈{\chi }_{\alpha +2}/m⌉+⌈{\chi }_{\alpha +1}/m⌉)\left|T\right|$ .

Proof.

First, according to Lemma 5, we have the lower bound $R_s$ for broadcast latency of the MLBCD problem. Theorem 8 gives the worst-case latency of the NAB algorithm. Note that $\left(⌈{\chi }_{\alpha +2}/m⌉+⌈{\chi }_{\alpha +1}/m⌉-1\right)\left|T\right|$ is larger than 0. Thus we have that the approximation ratio is at most $(⌈{\chi }_{\alpha +2}/m⌉+⌈{\chi }_{\alpha +1}/m⌉)\left|T\right|$ .

6. Performance Evaluation

In this section, we implement our NAB algorithm using MATLAB and evaluate its performance through extensive simulations. Our simulations focus on the effect of various network conditions on the performance of our NAB algorithm. The existing two broadcast algorithms ELAC-SC [19] and IFB [24] solve the MLB problem in single-channel duty-cycled scenarios under protocol interference model. Therefore we compare our NAB algorithm with these two algorithms and show how our NAB algorithm benefits from multichannel scheduling.

In the simulations, all the nodes are randomly deployed in a 1000 × 1000 m² area. The transmission radius is 300 m. We evaluate the broadcast latency of three algorithms and study the effect of different network conditions including the duty cycle, the interference ratio, and the number of channels on the performance of three algorithms.

In each simulation scenario, we adopt three network sizes of 100, 200, and 300 and adopt three numbers of channels of 1, 3, and 5. First, we evaluate the effect of different duty cycles. We adopt 10, 20, 30, 40, and 50 as the numbers of time-slots in T, and thus the duty cycle changes between 0.1 and 0.02. Then we evaluate the effect of different interference ratios. The interference ratio ranges from 2 to 6. In each experiment, we change one parameter and fix the other three parameters.

We use 20 different graph topologies to conduct these experiments. Moreover, 10 times of experiments are run on each graph topology, and the source node is randomly chosen in each experiment. Each data point reported in the figures results from an average of these simulation results. Since the gap among the simulation results of three algorithms is large, we show the denary logarithm of the results.

6.1. Impact of Different Duty Cycles

First, we study the impact of different duty cycles on the performance of three algorithms. In this simulation scenario, we set the interference ratio α as 3. Figure 2 illustrates the broadcast latency of three algorithms under different duty cycles. This figure also gives the results of our NAB algorithm under different numbers of channels.

Figure 2

Broadcast latency under different network sizes and duty cycles.

From Figure 2, we can see that, with the decrease of the duty cycle, the broadcast latency of three algorithms increases. The reason is that one node may wait more time-slots until its receiver node wakes up when the duty cycle decreases. Our NAB algorithm outperforms the other two algorithms notably even when only one channel can be used. This is because we well separate the transmissions of broadcast links based on AIG. When more channels can be used, more transmissions can be carried on at the same time-slot, and thus the broadcast latency is decreased.

From Figures 2(a), 2(b), and 2(c), we can also find that when the network size increases, the broadcast latency of all three algorithms increases. The reason is that more nodes require to be covered. In all these three figures, our NAB algorithm performs the best.

6.2. Impact of Different Interference Ratios

In this subsection, we study the impact of different interference ratios on the performance of three algorithms. The number of time-slots in T is set as 20. The results are shown in Figure 3. When the interference ratio increases, a node's interference range becomes larger, and hence fewer transmissions can be simultaneous. Therefore the broadcast latency of all the three algorithms increases when the interference ratio increases.

Figure 3

Broadcast latency under different network sizes and interference ratios.

Note that the increase of the broadcast latency is not as notable as that in the previous subsection. The reason is that when the network size and the duty cycle are fixed, the number of transmitter nodes and the waiting time-slots of these nodes do not change notably. The results in Figure 3 also verify that when the network size increases, all the algorithms’ broadcast latency increases, and our NAB algorithm outperforms the other two algorithms notably.

7. Conclusion

This paper investigates the MLBCD problem when protocol interference model is adopted as the interference model. We prove the NP-hardness of this problem and present one efficient algorithm NAB. We also prove that NAB algorithm is correct and provides an interference-free broadcast scheduling. The broadcast latency of NAB algorithm is bounded by $(⌈{\chi }_{\alpha +2}/m⌉+⌈{\chi }_{\alpha +1}/m⌉)\left|T\right|R_s-\left(⌈{\chi }_{\alpha +2}/m⌉+⌈{\chi }_{\alpha +1}/m⌉-1\right)\left|T\right|$ . NAB algorithm achieves a ratio of $\left(⌈{\chi }_{\alpha +2}/m⌉+⌈{\chi }_{\alpha +1}/m⌉\right)\left|T\right|$ . The results of extensive simulations show that our NAB algorithm achieves lower broadcast latency than existing algorithms even when only one channel can be used.