# Critical-Path Aware Scheduling for Latency Efficient Broadcast in Duty-Cycled Wireless Sensor Networks

Authors: Duc-Tai Le; Giyeol Im; Thang Le Duc; Vyacheslav V. Zalyubovskiy; Dongsoo S. Kim; Hyunseung Choo
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Minimum latency scheduling has arisen as one of the most crucial problems for broadcasting in duty-cycled Wireless Sensor Networks (WSNs). Typical solutions for the broadcast scheduling iteratively search for nodes able to transmit a message simultaneously. Other nodes are prevented from transmissions to ensure that there is no collision in a network. Such collision-preventions result in extra delays for a broadcast and may increase overall latency if the delays occur along critical paths of the network. To facilitate the broadcast latency minimization, we propose a novel approach, critical-path aware scheduling (CAS), which schedules transmissions with a preference of nodes in critical paths of a duty-cycled WSN. This paper presents two schemes employing CAS which produce collision-free and collision-tolerant broadcast schedules, respectively. The collision-free CAS scheme guarantees an approximation ratio of(Δ-1)T in terms of latency, where Δ denotes the maximum node degree in a network. By allowing collision at noncritical nodes, the collision-tolerant CAS scheme reduces up to 10.2 percent broadcast latency compared with the collision-free ones while requiring additional transmissions for the noncritical nodes experiencing collisions. Simulation results show that broadcast latencies of the two proposed schemes are significantly shorter than those of the existing methods.


---

## Body

## 1. Introduction

Wireless Sensor Networks (WSNs) have become one of the most important technologies for the 21st century [1, 2] and have attracted a lot of attention from industrial and research perspectives [3–11]. A wide range of services in WSNs rely strongly on broadcasting, such as information dissemination, route discovery, and code update [12]. Implementing an effective network-wide broadcast scheduling is critical to improve the performance of WSNs. Like other wireless communications, broadcasting can suffer from collision when a node hears more than one message simultaneously from transmissions of its neighbors. If the collision occurs, the node is not able to receive any of these messages. The problem of Minimum Latency Broadcast Scheduling (MLBS) aims to schedule a broadcast such that a message will be disseminated from a source node to all other nodes in a network with a minimum period of time. The problem has been proven to be NP-hard and widely studied in conventional WSNs, where all nodes are active all the time [13–15].Recently, duty-cycle protocols let nodes in a network turns off their radios and go into a sleep state when they are idle to conserve energy and to extend network lifetime [16–18]. In a low-duty-cycled WSN, a sensor node sleeps most of the time periodically waking up within a short time slot for possible data communication by either transmitting or receiving a message. Such periodic sleeping leads to a notable increase of communication latency between sensor nodes while reducing their energy consumption. In particular, every sensor node has to wait until its receivers wake up before transmitting a message and may need to transmit the message more than once if its receivers wake up at different time slots. The MLBS problem in duty-cycled WSNs gets more complex and has been proved as a NP-hard problem [19].Throughout the literature, the MLBS in duty-cycle (MLBSDC) problem has been richly explored [19–30]. The existing solutions typically aim to find a subset of nodes that can simultaneously transmit a message at a time slot so that the number of collision-free receptions in the time slot is maximized. However, delaying a transmission to prevent collision at a node in a network may increase overall broadcast latency if the node is in a critical path of the network. On minimizing broadcast latency, we propose a novel approach, critical-path aware scheduling (CAS) that offers an opportunity to reduce the latency by providing a preference for transmitting a message to nodes along critical paths of a duty-cycled WSN.This paper presents two scheduling schemes employing CAS, Collision-Free-CAS (CF-CAS) and Collision-Tolerant-CAS (CT-CAS). Both schemes assign a numerical value for each node of a network to identify the critical paths during their scheduling phases. CF-CAS scheme does not allow any collision in a schedule to minimize the number of redundant transmissions in a broadcast. CT-CAS scheme further reduces broadcast latency by allowing collisions at noncritical nodes to speed up the broadcast process for critical nodes. To complete a broadcast schedule, it covers nodes experiencing collisions by additional transmissions. The increase of number of transmissions in CT-CAS reveals a trade-off between the redundancy and latency of a broadcast. Simulation results demonstrate the advantage of CAS in minimizing broadcast latency in duty-cycled WSNs. Broadcast latencies of both schemes are shorter than those of existing methods.The remainder of this paper is organized as follows. Section2 discusses related works. Section 3 includes a network model, problem formulation, and related terminology. In Section 4, we present the proposed schemes. Sections 5 and 6 show their performance analysis and evaluations, respectively. Finally, we conclude the paper and discuss our future work in Section 7.


## 2. Related Work

Research on the minimum-latency broadcast problem has increased over the past few decades. One of the earliest works, Gandhi et al. [13], proves the NP-hardness of the MLBS problem in the Unit Disk Graph (UDG) model, where all nodes have the same transmission range. Their proposed algorithm gives an approximation ratio in terms of latency of at least 400. Huang et al. [14] exploited the fact that 12 colors are sufficient to color all the nodes in any independent set of an UDG and thus the distance between nodes with same color is more than two hops. As a result, they improved the approximation ratio to 16. The algorithm in [15] recently reduced the ratio to 12 by allowing a node to transmit more than once to reduce broadcast latency.However, the above-mentioned algorithms fail to capture the intermittently connected characteristic of duty-cycled networks. Several issues for broadcasting in duty-cycled networks have been explored, such as minimum latency [19–26, 28–30], minimum number of transmissions [31–34], and energy-saving [35, 36]. The MLBSDC problem rises as one of the most crucial problem for broadcasting in duty-cycled networks. Many research efforts have been made in literature to tackle the problem under different network settings, such as single channel [19–22, 26, 29], multichannel [24, 28], and unreliable links [23, 25, 30]. Table 1 summarizes the characteristics of the broadcasting algorithms in duty-cycled WSNs.Table 1
Summary of broadcasting algorithms in duty-cycled WSNs.
Multichannel Unreliable link Clock drift Collision Enhanced LAyered Coloring [19] No No No Yes Vector-Iteration Algorithm [20] No No No Yes One-To-All Broadcast [21] No No No Yes Latency-Aware Broadcast Scheduling [22] No No No Yes Opportunistic flooding [23] No Yes No Yes NAB [24] Yes No No Yes Delay-Driven-Tree-based opportunistic flooding [25] No Yes No Yes Load-Balanced Parents Assignment Algorithm [26] No No No No MultiChannel Broadcast [28] Yes No No Yes Degree-based Collision Tolerant Scheduling [29] No No No Yes Minimum-Delay Energy-efficient flooding Tree [30] No Yes No YesThe paper revisits MLBSDC problem in a time-synchronized network, in which all nodes use the same channel and the communication links between them are reliable. The problem is proven as NP-hardness [19], and there is a handful of related work so far. Duan et al. [20] developed the Vector-Iteration Algorithm (VIA) which transforms a broadcast scheduling into a matrix multiplication. This work introduces several matrices and vectors to characterize the essentials of broadcast scheduling in duty-cycled WSNs. VIA has a high computational complexity for matrix multiplication. In order to reduce broadcast latency, the proposed scheme greedily searches for a set of forwarding nodes at each time slot such that as many nodes as possible can receive a broadcast message in the time slot. VIA produces a collision-free broadcast schedule with an approximation ratio of ΔT, where Δ is the maximum node degree in a network.The One-To-All Broadcast (OTAB) scheme [21] utilizes a correlation function between network topology information and the sleep schedule of each node to find the minimum latency from a source node to every node in a network. All nodes in the network are divided into layers, according to the minimum latency. The scheme applies a D2-coloring method on the MIS of each active slot and schedules transmissions layer-by-layer based on the assigned colors. Also, OTAB requires all forwarding nodes in a one-hop propagation to finish their transmissions before all neighbors in the next hop. As a result, it increases the delay to ensure collision-free transmissions from those one-hop neighbors and hence leads to a high broadcast latency. The scheme has an approximation ratio of 17T, where T denotes the number of time slots in a working period.Latency-Aware Broadcast Scheduling (LABS) [22] divides all nodes in a network into different layers according to their minimum latencies from the source node. It further reduces broadcast latency by employing an independent scheduling between consecutive layers of the network. The scheme schedules transmissions at several time slots in a single working period to maximize the number of receptions in the working period. It also explores geometric properties of the MIS to reduce the number of transmissions. A D2-coloring method is applied to prevent interference between transmissions for nodes within one layer. The broadcast schedule provided by LABS reduces up to 34 percent of latency while keeping the same approximation ratio as OTAB. The total number of transmissions of LABS is at most 10 times as large as the minimum number of transmissions.Recently, Le et al. [29] proposed the Degree-Based Collision Tolerant Scheduling (DCTS) scheme. The scheme first categorizes internal and leaf nodes in a degree-based broadcast tree as primary and secondary nodes of a network, respectively. In order to minimize broadcast latency, it then speeds up the broadcast process for the primary nodes by selectively allowing collisions at secondary nodes of the network. DCTS accommodates such collisions by additional transmissions, thus ensuring the completion of a broadcast schedule. The scheme guarantees an approximation ratio of (Δ-1)T. Simulation results show that the scheme reduces to at least 94 percent of the broadcast latency compared with LABS, while slightly increasing the number of transmissions due to the additional transmissions.On minimizing broadcast latency, we have discovered that scheduling a broadcast with a preference of nodes in critical paths of a duty-cycled WSN is beneficial to reduce latency. The intuition behind this is that broadcast latency may increase if a delay occurs along critical paths of the network. In [37], such critical paths are determined on an arbitraryShortest Path Tree (SPT) constructed by a one-to-all shortest path algorithm, such as Dijkstra’s algorithm [38]. Based on the critical-path awareness, we have sketched a collision-free schedule [37] and a collision-tolerant schedule [39] and presented preliminary simulation results to show the advantage of critical-path aware scheduling in reducing broadcast latency.In this paper, we determine the critical paths on an SPT constructed with a preference of high-degree nodes to reduce the number of transmissions in a broadcast. In addition to a collision-free schedule, we develop a collision-tolerant schedule, similar to the one in [29], by referring to nodes in such critical paths as primary nodes. Moreover, both collision-free and collision-tolerant approaches adaptively select forwarding nodes in a broadcast, instead of selecting parents to forward a message to their children in a preconstructed broadcast tree as in [22, 29]. Such flexible selections also contribute to the reduction of broadcast latency in a critical-path aware schedule. Theoretical analysis and simulation results in this paper demonstrate a significant improvement of the proposed scheduling on broadcast latency.


## 3. Preliminary

### 3.1. Network Model and Assumptions

We consider a WSN of uniformly deployed sensor nodes in a square field as in [19–22, 29]. Each sensor node in the network is assigned a unique identifier. Two sensor nodes form a bidirectional communication link and become neighbors whenever they are within their transmission ranges of each other. The network topology is modeled as a graph, in which each vertex and each edge correspond to a node and a communication link between two nodes in the network, respectively. Such a graph is called a communication graph and assumed to be connected.In duty-cycled environments, sensor nodes alternate betweenactive andsleep state to conserve their energy. Time is divided into unittime slots. These discrete time slots are grouped into multipleworking periods, with fixed length T. It is assumed that each time slot is long enough to accommodate the transmission of a message. All sensor nodes are time synchronized at the slot level using local time synchronization techniques, such as Reference-Broadcast Synchronization [40], Tiny-Sync [41], and Generalized ML-Like Estimator [42]. A sensor node u randomly selects one time slot in {0,1,…,T-1} as its active slot a(u). It periodically wakes up at a(u) for each working period and stays in the active state for the time slot. Figure 1 explicitly illustrates an example of the periodic sleeping schedule.Figure 1
Duty-cycle schedule of a node with an active slot3 and T=5.A sensor node can forward a broadcast message only after it receives the message. A sensor node can wake up at any time slot to transmit a message and can receive a message only at its active slot. Due to the properties of a wireless environment, whenever a node transmits a message, all its active neighbor nodes hear the message. If a node hears more than one message at a time slot, it cannot receive any of these messages due to a collision. We assume that every transmission occupies a unit time slot and no message suffers from bit error. Therefore, sensor nodeu successfully receives a message if only one neighbor of u transmits the message at time slot a(u) of a working period.


### 3.2. Problem Statement

In a one-to-all broadcast, a message is disseminated from a source node to all other nodes in a network. The broadcast completes when every node in the network receives the message. To be specific, letG=(V,E) denote the communication graph of a duty-cycled WSN, where V is the set of vertices, and E is the set of edges. Let s denote a predefined source node of the network. The source node starts a broadcast at time slot 0.Abroadcast scheduling assigns transmitting time slots for nodes in the network such that the broadcast can complete. As node u∈V∖{s} can receive a message only at its active time slot, one of its neighbors must be assigned a transmitting time slot in a form of iT+a(u) for a nonnegative integer i. Thebroadcast latency is determined by the maximum assigned transmitting time slot. The objective of the MLBSDC problem is to find broadcast schedule with a minimum broadcast latency. The MLBSDC problem is an NP-hard problem [19].Figure2 shows a simple duty-cycled WSN and a schedule for broadcasting a message from s to its two-hop neighbors in the network. In the schedule, nodes v0, v1, and v2 receive a message from one transmission of s. After the transmission, nodes s and v0 simultaneously transmit the message at time slot 1 to their corresponding neighbors v4 and v5, respectively. In contrast, s and v2 cannot transmit the message at the same time to prevent a collision at their common neighbor node v4. As a result, a transmission from v2 is delayed to the next working period. The two-hop broadcast completes after 4 time slots.Figure 2
Broadcasting in duty-cycled WSNs.
(a)
Communication graph along with active slots of nodes (b)
A two-hop broadcast schedule


### 3.3. Related Terminology

For each pair of neighboring nodes in a communication graphG=(V,E), we define two numerical values, calledcosts, corresponding to two asymmetrical directions of the edge between the nodes. Each cost value is the number of time slots for which a transmission on a direction of the edge is delayed due to the sleeping period of its receiver. For simplicity, the source node s is assumed to have a message in advance, and its active slot is defined as T-1. The cost of an edge (u,v)∈E with a direction from u to v can be determined as follows: (1)costu,v=av-au,ifav>auav-au+T,otherwiseThe minimum of accumulated costs on the paths from source nodes to node u∈V is referred to aslevel of u, denoted as lv(u). The level of u corresponds to the minimum possible latency for u to receive a broadcast message generated by s; i.e. the smaller the level of a node is, the sooner the node may receive a broadcast message. The maximum level of nodes in a network is the lower bound of broadcast latency [19]. As the source node s has generated the message in advance, its level is 0. Levels of other nodes in the network can be obtained by constructing an SPT rooted at s. The SPT construction utilizes cost values as the weight of the edges. An example of SPT construction and level distribution for the network in Figure 2 is shown in Figure 3. It is worth noting that every node with a level k(k>0) has the same active slot (k-1)modT.Figure 3
Level distribution in duty-cycled WSNs.
(a)
A shortest path tree. A solid link indicates an edge in the tree (b)
Communication graph along with levels of nodes


## 3.1. Network Model and Assumptions

We consider a WSN of uniformly deployed sensor nodes in a square field as in [19–22, 29]. Each sensor node in the network is assigned a unique identifier. Two sensor nodes form a bidirectional communication link and become neighbors whenever they are within their transmission ranges of each other. The network topology is modeled as a graph, in which each vertex and each edge correspond to a node and a communication link between two nodes in the network, respectively. Such a graph is called a communication graph and assumed to be connected.In duty-cycled environments, sensor nodes alternate betweenactive andsleep state to conserve their energy. Time is divided into unittime slots. These discrete time slots are grouped into multipleworking periods, with fixed length T. It is assumed that each time slot is long enough to accommodate the transmission of a message. All sensor nodes are time synchronized at the slot level using local time synchronization techniques, such as Reference-Broadcast Synchronization [40], Tiny-Sync [41], and Generalized ML-Like Estimator [42]. A sensor node u randomly selects one time slot in {0,1,…,T-1} as its active slot a(u). It periodically wakes up at a(u) for each working period and stays in the active state for the time slot. Figure 1 explicitly illustrates an example of the periodic sleeping schedule.Figure 1
Duty-cycle schedule of a node with an active slot3 and T=5.A sensor node can forward a broadcast message only after it receives the message. A sensor node can wake up at any time slot to transmit a message and can receive a message only at its active slot. Due to the properties of a wireless environment, whenever a node transmits a message, all its active neighbor nodes hear the message. If a node hears more than one message at a time slot, it cannot receive any of these messages due to a collision. We assume that every transmission occupies a unit time slot and no message suffers from bit error. Therefore, sensor nodeu successfully receives a message if only one neighbor of u transmits the message at time slot a(u) of a working period.


## 3.2. Problem Statement

In a one-to-all broadcast, a message is disseminated from a source node to all other nodes in a network. The broadcast completes when every node in the network receives the message. To be specific, letG=(V,E) denote the communication graph of a duty-cycled WSN, where V is the set of vertices, and E is the set of edges. Let s denote a predefined source node of the network. The source node starts a broadcast at time slot 0.Abroadcast scheduling assigns transmitting time slots for nodes in the network such that the broadcast can complete. As node u∈V∖{s} can receive a message only at its active time slot, one of its neighbors must be assigned a transmitting time slot in a form of iT+a(u) for a nonnegative integer i. Thebroadcast latency is determined by the maximum assigned transmitting time slot. The objective of the MLBSDC problem is to find broadcast schedule with a minimum broadcast latency. The MLBSDC problem is an NP-hard problem [19].Figure2 shows a simple duty-cycled WSN and a schedule for broadcasting a message from s to its two-hop neighbors in the network. In the schedule, nodes v0, v1, and v2 receive a message from one transmission of s. After the transmission, nodes s and v0 simultaneously transmit the message at time slot 1 to their corresponding neighbors v4 and v5, respectively. In contrast, s and v2 cannot transmit the message at the same time to prevent a collision at their common neighbor node v4. As a result, a transmission from v2 is delayed to the next working period. The two-hop broadcast completes after 4 time slots.Figure 2
Broadcasting in duty-cycled WSNs.
(a)
Communication graph along with active slots of nodes (b)
A two-hop broadcast schedule


## 3.3. Related Terminology

For each pair of neighboring nodes in a communication graphG=(V,E), we define two numerical values, calledcosts, corresponding to two asymmetrical directions of the edge between the nodes. Each cost value is the number of time slots for which a transmission on a direction of the edge is delayed due to the sleeping period of its receiver. For simplicity, the source node s is assumed to have a message in advance, and its active slot is defined as T-1. The cost of an edge (u,v)∈E with a direction from u to v can be determined as follows: (1)costu,v=av-au,ifav>auav-au+T,otherwiseThe minimum of accumulated costs on the paths from source nodes to node u∈V is referred to aslevel of u, denoted as lv(u). The level of u corresponds to the minimum possible latency for u to receive a broadcast message generated by s; i.e. the smaller the level of a node is, the sooner the node may receive a broadcast message. The maximum level of nodes in a network is the lower bound of broadcast latency [19]. As the source node s has generated the message in advance, its level is 0. Levels of other nodes in the network can be obtained by constructing an SPT rooted at s. The SPT construction utilizes cost values as the weight of the edges. An example of SPT construction and level distribution for the network in Figure 2 is shown in Figure 3. It is worth noting that every node with a level k(k>0) has the same active slot (k-1)modT.Figure 3
Level distribution in duty-cycled WSNs.
(a)
A shortest path tree. A solid link indicates an edge in the tree (b)
Communication graph along with levels of nodes


## 4. Proposed Schemes

### 4.1. Overall Idea

Existing broadcast scheduling schemes such as OTAB [21], CLBS [22], and VIA [20] are typically motivated to find a set of forwarders whose simultaneous transmissions will result in as many collision-free receptions as possible. The schemes schedule a broadcast with a preference of transmissions to high-degree nodes. The intuition behind this is that the higher the degree a node has, the more the neighbors it can cover after receiving a message. They use the neighbourhood information of nodes to determine whether a particular node needs to transmit a message. Different transmitting time slots are assigned to nodes having a common neighbor to prevent any collision.Figure4(a) illustrates a degree-based broadcast scheduling for the duty-cycled WSN with T=2, shown in Figure 2. In the schedule, the source node s broadcasts a message to its neighbors v0, v1, and v2 at time slot 0. A transmission to v4 is preferred to be scheduled as the node has the highest degree among the remaining ones. There are four neighboring nodes of v4 ready to forward the broadcast message. In order to prevent a collision at the common neighbor v4, only v1 is allowed to forward the message at the time slot 1. The other ones must delay their transmissions to the next working period. As transmission of v2 is delayed in the example, its neighbor node v3 receives the message at time slot 3. In the same manner, a transmission from v5 is delayed to prevent an interference with the transmission of v4 at time slot 2. As a result, the receiving time of v6 is postponed to time slot 4. Then, v6 can forward the message further to its neighbors, and the broadcast completes at time slot 8.Figure 4
A comparision between a degree-based schedule and a critical-path aware schedule.
(a)
Degree-based schedule. (latency: 8, number of transmissions: 11) (b)
Critical-path aware schedule. (latency: 6, number of transmissions: 11)On an SPT rooted at the source node of a duty-cycled WSN, we define acritical path as the longest path from the root to the leaves of the tree. For instance, the path (s-v2-v3-v9-v14-v15) is a critical path of the network in Figure 2. As node v3 belongs to the critical path, a delay of transmission from v2 to v3 increases the overall broadcast latency. Similarly, if the transmission from v5 to v6 is scheduled earlier, it can result in a reduction of the overall broadcast latency. The problem is more severe in highly dense networks because there may be more nodes which cannot be scheduled simultaneously due to collisions. By preferring transmissions to nodes along the critical path, the critical-path aware scheduling selects v2 to transmit a message to v3 and v4 at time slot 1, as shown in Figure 4(b). Consequently, the remaining nodes in the critical path of v3 can receive the message earlier than in the degree-based schedule. In the same manner, v5 is selected to forward the message to v6 and v7 at time slot 2. Even if a transmission from v4 to v8 is delayed to time slot 4, it does not affect the overall broadcast latency. The broadcast completes after time slot 6 with the critical-path aware scheduling.


### 4.2. Criticality Awareness

The critical-path aware scheduling (CAS) approach utilizes node criticality information in its scheduling process to minimize broadcast latency. To this end, all critical paths of a network need to be identified. Note that a critical path is the shortest path froms to a node with maximum level, identified by an SPT rooted at the source node of the network. The proposed SPT construction algorithm connects nodes to the tree in a nondecreasing order of their levels. The algorithm prefers to select high-degree nodes as internal nodes in the tree to reduce the number of transmissions. The notation utilized in this chapter is summarized in Table 2.Table 2
Notation for the critical-path aware broadcast scheduling.
G=(V,E) communication graph of a network V: set of nodes, E: set of edges s source node of the network T length of a working period N(u) 1-hop neighbors of nodeu in G R(u,k) set of intended receivers with levelk of a transmission from node u TS(u) transmitting schedule of nodeu a(u) active slot of nodeu (a(u)∈0,1,...,T-1) lv(u) level of nodeu, i.e. minimum latency to receive a message from s la(u) latency-ahead value of nodeu parent(u) parent node of nodeu in TB rcv(u) receiving time of nodeuGiven a networkG=(V,E) with level of every node and a predefined source node s∈V, Algorithm 1 constructs a degree-based SPT rooted at the source node by connecting nodes to the tree level by level. Let VB denote the set of nodes which have been connected to the tree, initially VB={s}. For adding nodes in each level k to VB, the algorithm considers nodes in VB with levels smaller than k as parent candidates. Among the candidates, node p adjacent to the largest number of nodes in V∖VB with the level k is selected as a parent node. Such a node must exist because of the network connectivity. All neighbors of p in V∖VB with the level k become children of p and are to VB. The process continues until VB contains all nodes in the network. Obviously, the tree is a shortest path tree rooted at the source node s. Figure 5(a) illustrates a degree-based SPT construction for the network in Figure 2.Algorithm 1:Degree-Based-SPT.
Input: G = ( V , E ), s∈V, lv(u)(∀u∈V) Output:Broadcast tree TB={V,EB} ( 1 ) V B ← { s } , E B ← ⌀ ( 2 ) while V B ≠ V do ( 3 )  k ← min ⁡ { l v ( u ) ∣ u ∈ V ∖ V B } ( 4 )  L ← { u ∈ V ∣ l v ( u ) = k } // nodes at levelk ( 5 )  while L ∖ V B ≠ ⌀ do ( 6 )  p ← arg  max u ∈ { v ∈ V B | lv ( v ) < k } ⁡ N u ∩ L ∖ V B ( 7 )  E B ← E B ∪ { ( p , u ) ∈ E ∣ u ∈ N ( p ) ∩ ( L ∖ V B ) } ( 8 )  V B ← V B ∪ ( N ( p ) ∩ L )Figure 5
Latency-ahead values calculation.
(a)
A degree-based shortest path tree (b)
Communication graph along with latency-ahead of nodesTo facilitate node criticality awareness, we define thelatency-ahead value of each node u, denoted by la(u), based on the constructed tree. The latency-ahead value of a node presents the minimum latency for transmitting a message from the node to the farthest leaf node in the subtree rooted at the node. The value is the accumulated costs from the node to a leaf node with the maximum level in its subtree. In other words, a node with a higher latency-ahead value requires a longer time to cover all nodes in its subtree. The higher latency-ahead value a node has, the more critical the node is. An example of latency-ahead calculation is shown in Figure 5(b).


### 4.3. Critical-Path Aware Scheduling

In this section, we present two broadcast scheduling schemes employing the critical-path aware scheduling (CAS) to reduce broadcast latency. The proposed schemes, named Collision-Free-CAS (CF-CAS) and Collision-Tolerant-CAS (CT-CAS), follow either collision-free or collision-tolerant strategy, respectively. A node is in acovered state if one of its neighbors has been scheduled to transmit a message to the node. Otherwise, it is in anuncovered state. The covered node is ready to be scheduled to cover its uncovered neighbors. The schemes schedule a broadcast with a preference of transmissions to uncovered nodes with high latency-ahead values. In each time slot, the schemes minimize the number of transmissions by selecting high-degree covered nodes as forwarders.


#### 4.3.1. CF-CAS

LetC denote the set of covered nodes in a network. Initially, C contains only the source node. The scheduling scheme starts at time slot 0 and iteratively works for each time slot as in Algorithm 2. At the current time slot i(i≥0), the algorithm searches for the most critical uncovered node u that has the highest latency-ahead value and a(u)=imodT. All covered neighbors of u are considered as its forwarder candidates. Among the candidates, the algorithm selects node f as aforwarder if it covers the largest number of uncovered nodes active at time slot i to reduce the number of transmissions. Let C¯ denote the set of uncovered nodes active at the current time slot.Algorithm 2:CF-CAS.
Input: G=(V,E) Output:Transmitting schedule TS(u) for every node u∈V ( 1 ) ∀ u ∈ V , T S ( u ) ← ⌀ , r c v ( u ) ← - ∞ ( 2 ) r c v ( s ) ← - 1 // source node has a message in advance ( 3 ) i ← 0 // current time slot ( 4 ) while ∃ u ∈ V , r c v ( u ) = - ∞ do ( 5 )  C ← { u ∣ u ∈ V , r c v ( u ) ≥ - 1 } // set of covered nodes ( 6 )  C ¯ ← { u ∣ u ∈ V ∖ C , N ( u ) ∩ C ≠ ⌀ , a ( u ) = i  m o d  T } // set of uncovered nodes ( 7 )  while C ≠ ⌀   &   C ¯ ≠ ⌀ do ( 8 )  u ← argmax u ∈ C ¯ ⁡ l a ( u ) ( 9 )  f ← argmax v ∈ C ∩ N ( u ) ⁡ N v ∩ C ¯ ( 10 )  T S ( f ) ← T S ( f ) ∪ { i } ( 11 )  foreach v ∈ N ( f ) ∩ C ¯ do ( 12 )  r c v ( v ) ← i , C ¯ ← C ¯ ∖ { v } ( 13 )  C ← C ∖ N ( v ) ( 14 )  i ← i + 1As a transmission from the selected forwarder covers all of its uncovered neighbors active at time sloti; such neighbors, calledlisteners, can receive a message from f at time slot i. The listeners become covered nodes and are excluded from C¯. All covered neighbors of the listeners are excluded from C to ensure that they will not be selected as forwarders in time slot i anymore. By doing so, the algorithm prevents any collision at the listeners. CF-CAS continues searching for a node with the highest latency-ahead value in C¯ until all nodes active at the current time slot are covered or it cannot find any forwarder for the node. The scheduling algorithm updates the node status, and moves to the next time slot, i.e., i+1, until it covers all nodes in the network, iteratively. Figure 6(a) shows an example of the proposed algorithm on the network shown in Figure 2.Figure 6
An illustration of the critical-path aware scheduling.
(a)
Collision-free schedule (latency: 6, number of transmissions: 11) (b)
Collision-tolerant schedule (latency: 5, number of transmissions: 13)


#### 4.3.2. CT-CAS

Observably, a delay of transmission caused by collision-prevention may increase the broadcast latency if the delay occurs along a critical path of the network. With the node criticality awareness, covering nodes in a nonincreasing order of their latency-ahead values can be beneficial for reducing broadcast latency. It motivates us to allow collision at low criticality nodes to speed up the broadcast process for high criticality ones. By doing so, the scheduling accelerates transmissions to nodes with high latency-ahead values. It also increases the number of simultaneous transmissions in each time slot to reduce broadcast latency. The CT-CAS algorithm accommodates the collisions possibly occurring at the low criticality nodes by retransmission to ensure the completion of a broadcast.Initially, the algorithm offers a preference to the most critical uncovered nodeu that has the highest latency-ahead value in time slot i. Forwarder f is selected among covered neighbors of u in a similar way as the CF-CAS algorithm. All uncovered neighbors of the selected forwarder are referred to aslisteners because they can hear a message at time slot i. The listeners are excluded from C¯ as they become covered nodes. The difference is that a listener may be changed back to an uncovered state later if it hears more than one message at the current time slot. Let num(x) denote the number of messages that node x can hear in a time slot. The number is increased by one for each listener as in Algorithm 3.Algorithm 3:CT-CAS.
Input:  G=(V,E) Output: Transmitting schedule TS(u) for every node u∈V ( 1 )   ∀ u ∈ V , T S ( u ) ← ⌀ , r c v ( u ) ← - ∞ , n u m ( u ) ← 0 ( 2 ) r c v ( s ) ← - 1 , n u m ( s ) ← 1 // source node has a message in advance ( 3 ) i ← 0 // current time slot ( 4 ) while ∃ u ∈ V , r c v ( u ) = - ∞ do ( 5 )  C ← { u ∣ u ∈ V , r c v ( u ) ≥ - 1 } // set of covered nodes ( 6 )  C ¯ ← { u ∣ u ∈ V ∖ C , N ( u ) ∩ C ≠ ⌀ , a ( u ) = i  m o d  T } // set of uncovered nodes ( 7 )  L ← ⌀ // set of listeners ( 8 )  while C ≠ ⌀   &   C ¯ ≠ ⌀ do ( 9 )  u ← argmax u ∈ C ¯ ⁡ l a ( u ) ( 10 )  ∀ v ∈ { x ∈ L ∣ l a ( x ) ≥ l a ( u ) , n u m ( x ) = 1 } , C ← C ∖ N ( v ) ( 11 )  f ← argmax v ∈ C ∩ N ( u ) ⁡ N v ∩ C ¯ ( 12 )  T S ( f ) ← T S ( f ) ∪ { i } ( 13 )  foreach v ∈ N ( f ) ∩ C ¯ do ( 14 )  n u m ( v ) ← n u m ( v ) + 1 , C ¯ ← C ¯ ∖ { v } ( 15 )  L ← L ∪ { v } ( 16 )  ∀ u ∈ { x ∈ L ∣ n u m ( x ) = 1 } , r c v ( u ) ← i ( 17 )  ∀ u ∈ { x ∈ L ∣ n u m ( x ) > 1 } , n u m ( u ) ← 0 ( 18 )  i ← i + 1CT-CAS algorithm continues searching for the next critical nodeu′ with the highest latency-ahead value among remaining nodes in C¯. To prevent collisions at listeners whose latency-ahead values are not smaller than la(u′) and numbers of heard messages are one, all covered neighbors of such listeners are excluded from C. Forwarder f′ for node u′ is selected in the same manner among the remaining candidates in C. All uncovered neighbors active at time slot i of f′ also become listeners. Collisions are allowed at listeners that are common neighbors of f and f′.The scheduling algorithm iterates the above procedure until all nodes active at the current time slot are covered, or it cannot find any proper forwarder. Only listeners hearing one message in the current tine slot become covered nodes. Other listeners are changed back to an uncovered state as they cannot receive any message. CT-CAS algorithm resets the number of heard messages for every uncovered node and iteratively moves to the next time slot,i+1, until all nodes in the network are in a covered state. Figure 6(b) shows an example of the proposed algorithm on the network shown in Figure 2.


## 4.1. Overall Idea

Existing broadcast scheduling schemes such as OTAB [21], CLBS [22], and VIA [20] are typically motivated to find a set of forwarders whose simultaneous transmissions will result in as many collision-free receptions as possible. The schemes schedule a broadcast with a preference of transmissions to high-degree nodes. The intuition behind this is that the higher the degree a node has, the more the neighbors it can cover after receiving a message. They use the neighbourhood information of nodes to determine whether a particular node needs to transmit a message. Different transmitting time slots are assigned to nodes having a common neighbor to prevent any collision.Figure4(a) illustrates a degree-based broadcast scheduling for the duty-cycled WSN with T=2, shown in Figure 2. In the schedule, the source node s broadcasts a message to its neighbors v0, v1, and v2 at time slot 0. A transmission to v4 is preferred to be scheduled as the node has the highest degree among the remaining ones. There are four neighboring nodes of v4 ready to forward the broadcast message. In order to prevent a collision at the common neighbor v4, only v1 is allowed to forward the message at the time slot 1. The other ones must delay their transmissions to the next working period. As transmission of v2 is delayed in the example, its neighbor node v3 receives the message at time slot 3. In the same manner, a transmission from v5 is delayed to prevent an interference with the transmission of v4 at time slot 2. As a result, the receiving time of v6 is postponed to time slot 4. Then, v6 can forward the message further to its neighbors, and the broadcast completes at time slot 8.Figure 4
A comparision between a degree-based schedule and a critical-path aware schedule.
(a)
Degree-based schedule. (latency: 8, number of transmissions: 11) (b)
Critical-path aware schedule. (latency: 6, number of transmissions: 11)On an SPT rooted at the source node of a duty-cycled WSN, we define acritical path as the longest path from the root to the leaves of the tree. For instance, the path (s-v2-v3-v9-v14-v15) is a critical path of the network in Figure 2. As node v3 belongs to the critical path, a delay of transmission from v2 to v3 increases the overall broadcast latency. Similarly, if the transmission from v5 to v6 is scheduled earlier, it can result in a reduction of the overall broadcast latency. The problem is more severe in highly dense networks because there may be more nodes which cannot be scheduled simultaneously due to collisions. By preferring transmissions to nodes along the critical path, the critical-path aware scheduling selects v2 to transmit a message to v3 and v4 at time slot 1, as shown in Figure 4(b). Consequently, the remaining nodes in the critical path of v3 can receive the message earlier than in the degree-based schedule. In the same manner, v5 is selected to forward the message to v6 and v7 at time slot 2. Even if a transmission from v4 to v8 is delayed to time slot 4, it does not affect the overall broadcast latency. The broadcast completes after time slot 6 with the critical-path aware scheduling.


## 4.2. Criticality Awareness

The critical-path aware scheduling (CAS) approach utilizes node criticality information in its scheduling process to minimize broadcast latency. To this end, all critical paths of a network need to be identified. Note that a critical path is the shortest path froms to a node with maximum level, identified by an SPT rooted at the source node of the network. The proposed SPT construction algorithm connects nodes to the tree in a nondecreasing order of their levels. The algorithm prefers to select high-degree nodes as internal nodes in the tree to reduce the number of transmissions. The notation utilized in this chapter is summarized in Table 2.Table 2
Notation for the critical-path aware broadcast scheduling.
G=(V,E) communication graph of a network V: set of nodes, E: set of edges s source node of the network T length of a working period N(u) 1-hop neighbors of nodeu in G R(u,k) set of intended receivers with levelk of a transmission from node u TS(u) transmitting schedule of nodeu a(u) active slot of nodeu (a(u)∈0,1,...,T-1) lv(u) level of nodeu, i.e. minimum latency to receive a message from s la(u) latency-ahead value of nodeu parent(u) parent node of nodeu in TB rcv(u) receiving time of nodeuGiven a networkG=(V,E) with level of every node and a predefined source node s∈V, Algorithm 1 constructs a degree-based SPT rooted at the source node by connecting nodes to the tree level by level. Let VB denote the set of nodes which have been connected to the tree, initially VB={s}. For adding nodes in each level k to VB, the algorithm considers nodes in VB with levels smaller than k as parent candidates. Among the candidates, node p adjacent to the largest number of nodes in V∖VB with the level k is selected as a parent node. Such a node must exist because of the network connectivity. All neighbors of p in V∖VB with the level k become children of p and are to VB. The process continues until VB contains all nodes in the network. Obviously, the tree is a shortest path tree rooted at the source node s. Figure 5(a) illustrates a degree-based SPT construction for the network in Figure 2.Algorithm 1:Degree-Based-SPT.
Input: G = ( V , E ), s∈V, lv(u)(∀u∈V) Output:Broadcast tree TB={V,EB} ( 1 ) V B ← { s } , E B ← ⌀ ( 2 ) while V B ≠ V do ( 3 )  k ← min ⁡ { l v ( u ) ∣ u ∈ V ∖ V B } ( 4 )  L ← { u ∈ V ∣ l v ( u ) = k } // nodes at levelk ( 5 )  while L ∖ V B ≠ ⌀ do ( 6 )  p ← arg  max u ∈ { v ∈ V B | lv ( v ) < k } ⁡ N u ∩ L ∖ V B ( 7 )  E B ← E B ∪ { ( p , u ) ∈ E ∣ u ∈ N ( p ) ∩ ( L ∖ V B ) } ( 8 )  V B ← V B ∪ ( N ( p ) ∩ L )Figure 5
Latency-ahead values calculation.
(a)
A degree-based shortest path tree (b)
Communication graph along with latency-ahead of nodesTo facilitate node criticality awareness, we define thelatency-ahead value of each node u, denoted by la(u), based on the constructed tree. The latency-ahead value of a node presents the minimum latency for transmitting a message from the node to the farthest leaf node in the subtree rooted at the node. The value is the accumulated costs from the node to a leaf node with the maximum level in its subtree. In other words, a node with a higher latency-ahead value requires a longer time to cover all nodes in its subtree. The higher latency-ahead value a node has, the more critical the node is. An example of latency-ahead calculation is shown in Figure 5(b).


## 4.3. Critical-Path Aware Scheduling

In this section, we present two broadcast scheduling schemes employing the critical-path aware scheduling (CAS) to reduce broadcast latency. The proposed schemes, named Collision-Free-CAS (CF-CAS) and Collision-Tolerant-CAS (CT-CAS), follow either collision-free or collision-tolerant strategy, respectively. A node is in acovered state if one of its neighbors has been scheduled to transmit a message to the node. Otherwise, it is in anuncovered state. The covered node is ready to be scheduled to cover its uncovered neighbors. The schemes schedule a broadcast with a preference of transmissions to uncovered nodes with high latency-ahead values. In each time slot, the schemes minimize the number of transmissions by selecting high-degree covered nodes as forwarders.


### 4.3.1. CF-CAS

LetC denote the set of covered nodes in a network. Initially, C contains only the source node. The scheduling scheme starts at time slot 0 and iteratively works for each time slot as in Algorithm 2. At the current time slot i(i≥0), the algorithm searches for the most critical uncovered node u that has the highest latency-ahead value and a(u)=imodT. All covered neighbors of u are considered as its forwarder candidates. Among the candidates, the algorithm selects node f as aforwarder if it covers the largest number of uncovered nodes active at time slot i to reduce the number of transmissions. Let C¯ denote the set of uncovered nodes active at the current time slot.Algorithm 2:CF-CAS.
Input: G=(V,E) Output:Transmitting schedule TS(u) for every node u∈V ( 1 ) ∀ u ∈ V , T S ( u ) ← ⌀ , r c v ( u ) ← - ∞ ( 2 ) r c v ( s ) ← - 1 // source node has a message in advance ( 3 ) i ← 0 // current time slot ( 4 ) while ∃ u ∈ V , r c v ( u ) = - ∞ do ( 5 )  C ← { u ∣ u ∈ V , r c v ( u ) ≥ - 1 } // set of covered nodes ( 6 )  C ¯ ← { u ∣ u ∈ V ∖ C , N ( u ) ∩ C ≠ ⌀ , a ( u ) = i  m o d  T } // set of uncovered nodes ( 7 )  while C ≠ ⌀   &   C ¯ ≠ ⌀ do ( 8 )  u ← argmax u ∈ C ¯ ⁡ l a ( u ) ( 9 )  f ← argmax v ∈ C ∩ N ( u ) ⁡ N v ∩ C ¯ ( 10 )  T S ( f ) ← T S ( f ) ∪ { i } ( 11 )  foreach v ∈ N ( f ) ∩ C ¯ do ( 12 )  r c v ( v ) ← i , C ¯ ← C ¯ ∖ { v } ( 13 )  C ← C ∖ N ( v ) ( 14 )  i ← i + 1As a transmission from the selected forwarder covers all of its uncovered neighbors active at time sloti; such neighbors, calledlisteners, can receive a message from f at time slot i. The listeners become covered nodes and are excluded from C¯. All covered neighbors of the listeners are excluded from C to ensure that they will not be selected as forwarders in time slot i anymore. By doing so, the algorithm prevents any collision at the listeners. CF-CAS continues searching for a node with the highest latency-ahead value in C¯ until all nodes active at the current time slot are covered or it cannot find any forwarder for the node. The scheduling algorithm updates the node status, and moves to the next time slot, i.e., i+1, until it covers all nodes in the network, iteratively. Figure 6(a) shows an example of the proposed algorithm on the network shown in Figure 2.Figure 6
An illustration of the critical-path aware scheduling.
(a)
Collision-free schedule (latency: 6, number of transmissions: 11) (b)
Collision-tolerant schedule (latency: 5, number of transmissions: 13)


### 4.3.2. CT-CAS

Observably, a delay of transmission caused by collision-prevention may increase the broadcast latency if the delay occurs along a critical path of the network. With the node criticality awareness, covering nodes in a nonincreasing order of their latency-ahead values can be beneficial for reducing broadcast latency. It motivates us to allow collision at low criticality nodes to speed up the broadcast process for high criticality ones. By doing so, the scheduling accelerates transmissions to nodes with high latency-ahead values. It also increases the number of simultaneous transmissions in each time slot to reduce broadcast latency. The CT-CAS algorithm accommodates the collisions possibly occurring at the low criticality nodes by retransmission to ensure the completion of a broadcast.Initially, the algorithm offers a preference to the most critical uncovered nodeu that has the highest latency-ahead value in time slot i. Forwarder f is selected among covered neighbors of u in a similar way as the CF-CAS algorithm. All uncovered neighbors of the selected forwarder are referred to aslisteners because they can hear a message at time slot i. The listeners are excluded from C¯ as they become covered nodes. The difference is that a listener may be changed back to an uncovered state later if it hears more than one message at the current time slot. Let num(x) denote the number of messages that node x can hear in a time slot. The number is increased by one for each listener as in Algorithm 3.Algorithm 3:CT-CAS.
Input:  G=(V,E) Output: Transmitting schedule TS(u) for every node u∈V ( 1 )   ∀ u ∈ V , T S ( u ) ← ⌀ , r c v ( u ) ← - ∞ , n u m ( u ) ← 0 ( 2 ) r c v ( s ) ← - 1 , n u m ( s ) ← 1 // source node has a message in advance ( 3 ) i ← 0 // current time slot ( 4 ) while ∃ u ∈ V , r c v ( u ) = - ∞ do ( 5 )  C ← { u ∣ u ∈ V , r c v ( u ) ≥ - 1 } // set of covered nodes ( 6 )  C ¯ ← { u ∣ u ∈ V ∖ C , N ( u ) ∩ C ≠ ⌀ , a ( u ) = i  m o d  T } // set of uncovered nodes ( 7 )  L ← ⌀ // set of listeners ( 8 )  while C ≠ ⌀   &   C ¯ ≠ ⌀ do ( 9 )  u ← argmax u ∈ C ¯ ⁡ l a ( u ) ( 10 )  ∀ v ∈ { x ∈ L ∣ l a ( x ) ≥ l a ( u ) , n u m ( x ) = 1 } , C ← C ∖ N ( v ) ( 11 )  f ← argmax v ∈ C ∩ N ( u ) ⁡ N v ∩ C ¯ ( 12 )  T S ( f ) ← T S ( f ) ∪ { i } ( 13 )  foreach v ∈ N ( f ) ∩ C ¯ do ( 14 )  n u m ( v ) ← n u m ( v ) + 1 , C ¯ ← C ¯ ∖ { v } ( 15 )  L ← L ∪ { v } ( 16 )  ∀ u ∈ { x ∈ L ∣ n u m ( x ) = 1 } , r c v ( u ) ← i ( 17 )  ∀ u ∈ { x ∈ L ∣ n u m ( x ) > 1 } , n u m ( u ) ← 0 ( 18 )  i ← i + 1CT-CAS algorithm continues searching for the next critical nodeu′ with the highest latency-ahead value among remaining nodes in C¯. To prevent collisions at listeners whose latency-ahead values are not smaller than la(u′) and numbers of heard messages are one, all covered neighbors of such listeners are excluded from C. Forwarder f′ for node u′ is selected in the same manner among the remaining candidates in C. All uncovered neighbors active at time slot i of f′ also become listeners. Collisions are allowed at listeners that are common neighbors of f and f′.The scheduling algorithm iterates the above procedure until all nodes active at the current time slot are covered, or it cannot find any proper forwarder. Only listeners hearing one message in the current tine slot become covered nodes. Other listeners are changed back to an uncovered state as they cannot receive any message. CT-CAS algorithm resets the number of heard messages for every uncovered node and iteratively moves to the next time slot,i+1, until all nodes in the network are in a covered state. Figure 6(b) shows an example of the proposed algorithm on the network shown in Figure 2.


## 4.3.1. CF-CAS

LetC denote the set of covered nodes in a network. Initially, C contains only the source node. The scheduling scheme starts at time slot 0 and iteratively works for each time slot as in Algorithm 2. At the current time slot i(i≥0), the algorithm searches for the most critical uncovered node u that has the highest latency-ahead value and a(u)=imodT. All covered neighbors of u are considered as its forwarder candidates. Among the candidates, the algorithm selects node f as aforwarder if it covers the largest number of uncovered nodes active at time slot i to reduce the number of transmissions. Let C¯ denote the set of uncovered nodes active at the current time slot.Algorithm 2:CF-CAS.
Input: G=(V,E) Output:Transmitting schedule TS(u) for every node u∈V ( 1 ) ∀ u ∈ V , T S ( u ) ← ⌀ , r c v ( u ) ← - ∞ ( 2 ) r c v ( s ) ← - 1 // source node has a message in advance ( 3 ) i ← 0 // current time slot ( 4 ) while ∃ u ∈ V , r c v ( u ) = - ∞ do ( 5 )  C ← { u ∣ u ∈ V , r c v ( u ) ≥ - 1 } // set of covered nodes ( 6 )  C ¯ ← { u ∣ u ∈ V ∖ C , N ( u ) ∩ C ≠ ⌀ , a ( u ) = i  m o d  T } // set of uncovered nodes ( 7 )  while C ≠ ⌀   &   C ¯ ≠ ⌀ do ( 8 )  u ← argmax u ∈ C ¯ ⁡ l a ( u ) ( 9 )  f ← argmax v ∈ C ∩ N ( u ) ⁡ N v ∩ C ¯ ( 10 )  T S ( f ) ← T S ( f ) ∪ { i } ( 11 )  foreach v ∈ N ( f ) ∩ C ¯ do ( 12 )  r c v ( v ) ← i , C ¯ ← C ¯ ∖ { v } ( 13 )  C ← C ∖ N ( v ) ( 14 )  i ← i + 1As a transmission from the selected forwarder covers all of its uncovered neighbors active at time sloti; such neighbors, calledlisteners, can receive a message from f at time slot i. The listeners become covered nodes and are excluded from C¯. All covered neighbors of the listeners are excluded from C to ensure that they will not be selected as forwarders in time slot i anymore. By doing so, the algorithm prevents any collision at the listeners. CF-CAS continues searching for a node with the highest latency-ahead value in C¯ until all nodes active at the current time slot are covered or it cannot find any forwarder for the node. The scheduling algorithm updates the node status, and moves to the next time slot, i.e., i+1, until it covers all nodes in the network, iteratively. Figure 6(a) shows an example of the proposed algorithm on the network shown in Figure 2.Figure 6
An illustration of the critical-path aware scheduling.
(a)
Collision-free schedule (latency: 6, number of transmissions: 11) (b)
Collision-tolerant schedule (latency: 5, number of transmissions: 13)


## 4.3.2. CT-CAS

Observably, a delay of transmission caused by collision-prevention may increase the broadcast latency if the delay occurs along a critical path of the network. With the node criticality awareness, covering nodes in a nonincreasing order of their latency-ahead values can be beneficial for reducing broadcast latency. It motivates us to allow collision at low criticality nodes to speed up the broadcast process for high criticality ones. By doing so, the scheduling accelerates transmissions to nodes with high latency-ahead values. It also increases the number of simultaneous transmissions in each time slot to reduce broadcast latency. The CT-CAS algorithm accommodates the collisions possibly occurring at the low criticality nodes by retransmission to ensure the completion of a broadcast.Initially, the algorithm offers a preference to the most critical uncovered nodeu that has the highest latency-ahead value in time slot i. Forwarder f is selected among covered neighbors of u in a similar way as the CF-CAS algorithm. All uncovered neighbors of the selected forwarder are referred to aslisteners because they can hear a message at time slot i. The listeners are excluded from C¯ as they become covered nodes. The difference is that a listener may be changed back to an uncovered state later if it hears more than one message at the current time slot. Let num(x) denote the number of messages that node x can hear in a time slot. The number is increased by one for each listener as in Algorithm 3.Algorithm 3:CT-CAS.
Input:  G=(V,E) Output: Transmitting schedule TS(u) for every node u∈V ( 1 )   ∀ u ∈ V , T S ( u ) ← ⌀ , r c v ( u ) ← - ∞ , n u m ( u ) ← 0 ( 2 ) r c v ( s ) ← - 1 , n u m ( s ) ← 1 // source node has a message in advance ( 3 ) i ← 0 // current time slot ( 4 ) while ∃ u ∈ V , r c v ( u ) = - ∞ do ( 5 )  C ← { u ∣ u ∈ V , r c v ( u ) ≥ - 1 } // set of covered nodes ( 6 )  C ¯ ← { u ∣ u ∈ V ∖ C , N ( u ) ∩ C ≠ ⌀ , a ( u ) = i  m o d  T } // set of uncovered nodes ( 7 )  L ← ⌀ // set of listeners ( 8 )  while C ≠ ⌀   &   C ¯ ≠ ⌀ do ( 9 )  u ← argmax u ∈ C ¯ ⁡ l a ( u ) ( 10 )  ∀ v ∈ { x ∈ L ∣ l a ( x ) ≥ l a ( u ) , n u m ( x ) = 1 } , C ← C ∖ N ( v ) ( 11 )  f ← argmax v ∈ C ∩ N ( u ) ⁡ N v ∩ C ¯ ( 12 )  T S ( f ) ← T S ( f ) ∪ { i } ( 13 )  foreach v ∈ N ( f ) ∩ C ¯ do ( 14 )  n u m ( v ) ← n u m ( v ) + 1 , C ¯ ← C ¯ ∖ { v } ( 15 )  L ← L ∪ { v } ( 16 )  ∀ u ∈ { x ∈ L ∣ n u m ( x ) = 1 } , r c v ( u ) ← i ( 17 )  ∀ u ∈ { x ∈ L ∣ n u m ( x ) > 1 } , n u m ( u ) ← 0 ( 18 )  i ← i + 1CT-CAS algorithm continues searching for the next critical nodeu′ with the highest latency-ahead value among remaining nodes in C¯. To prevent collisions at listeners whose latency-ahead values are not smaller than la(u′) and numbers of heard messages are one, all covered neighbors of such listeners are excluded from C. Forwarder f′ for node u′ is selected in the same manner among the remaining candidates in C. All uncovered neighbors active at time slot i of f′ also become listeners. Collisions are allowed at listeners that are common neighbors of f and f′.The scheduling algorithm iterates the above procedure until all nodes active at the current time slot are covered, or it cannot find any proper forwarder. Only listeners hearing one message in the current tine slot become covered nodes. Other listeners are changed back to an uncovered state as they cannot receive any message. CT-CAS algorithm resets the number of heard messages for every uncovered node and iteratively moves to the next time slot,i+1, until all nodes in the network are in a covered state. Figure 6(b) shows an example of the proposed algorithm on the network shown in Figure 2.


## 5. Performance Analysis

Recall that CAS along with collision-free and collision-tolerant strategies is referred to as the CF-CAS scheme and the CT-CAS scheme, respectively. In this section, we estimate approximation ratios between broadcast latencies given by the proposed schemes and the optimal latency for the MLBSDC problem. We first show that approximation ratio of the CF-CAS scheme does not exceed(Δ-1)T, where Δ is the maximum degree of a communication graph.The proposed scheme schedules all transmissions based on the latency-ahead value of each node with a preference of node degree. LetdCF denote the broadcast latency in a CF-CAS schedule. Let R(u,t) denote the receiver node set of the scheduled transmission from node u at time slot t, 0≤t≤dCF. Note that such receivers are active at the same time slot of tmodT.Lemma 1.
In CF-CAS scheme, if a transmission from nodeu is delayed to prevent a collision at node w then w∉R(u,t), ∀t∈[0,dCF].Proof.
We prove this lemma by contradiction. Assume that a transmission of nodeu is delayed until time slot t, 0≤t≤dCF, to prevent an interference with the prior scheduled transmission of node v at node w∈R(u,t). In the CF-CAS scheme, as v is scheduled prior to u and it has the common uncovered neighbor w, v must have a higher degree than u. According to Algorithm 2, w must be a receiver of v, which contradicts the assumption.Letd∗ denote the latency of an optimal broadcast schedule for the MLBSDC problem. In the optimal schedule, let Rt∗ be the set of all receivers at time slot t, 0≤t≤d∗. It is worth noting that every node in Rt∗ is uncovered and active at time slot t. The following is our key lemma.Lemma 2.
CF-CAS algorithm takes at mostt(Δ-1)T time slots to cover all nodes in ⋃k=0t‍Rk∗, ∀t∈[0,d∗].Proof.
We prove this lemma by induction ont. As all nodes in level 1 can receive a message from a transmission of s at time slot 0; the claim of this lemma is true for the receiver set R0∗. Suppose that the claim is true for any receiver set from ⋃k=01‍Rk∗ to ⋃k=0t-1‍Rk∗, where 1≤t≤d∗. We now prove it for the set ⋃k=0t‍Rk∗. Let u be a sender at time slot t′ that covers some nodes in R(u,t′)⊂⋃k=0t‍Rk∗. The transmission of node u is delayed till time slot t′ to prevent interference with other scheduled transmissions. We denote by IN(u,t′) the set of such interfering transmissions. According to the CF-CAS algorithm, we have(2)t′≤rcvu+INu,t′+1T
According to Lemma1, a transmission from node u to nodes in R(u,t′) can only be delayed to prevent collision at some uncovered nodes in N(u)∖R(u,t′). Since the transmission may be delayed until all of such uncovered nodes are covered, we have INu,t′≤|N(u)|-Ru,t′-1, where 1 accounts for the node parent(u). The reason is that parent(u) has been covered before u and has been excluded from the uncovered node set according to the CF-CAS algorithm. From (2), we have(3)t′≤rcvu+Nu-Ru,t′-1+1T=rcvu+Nu-Ru,t′T
Noting that in (3) Nu≤Δ and Ru,t′≥1, we have(4)t′≤rcvu+Δ-1T
Asu should receive a message before transmitting a message to ⋃k=0t‍Rk∗, u∈⋃k=0i‍Rk∗, where 0≤i≤t-1. By induction hypothesis, we have(5)rcvu≤iΔ-1T≤t-1Δ-1T
So the maximum transmitting time slot of nodeu for nodes in ⋃k=0t‍Rk∗ can be estimated from (4) and (5) as follows: (6)t′≤t-1Δ-1T+Δ-1T=tΔ-1T
Thus, the claim of the lemma holds for the receiver set⋃k=0t‍Rk∗, and the proof is complete.Theorem 3.
The approximation ratio of the CF-CAS scheme is at most(Δ-1)T.Proof.
From the definition of the receiver set in the optimal schedule, we have(7)⋃k=0d∗Rk∗=V∖s
According to Lemma2, the maximum time slot to cover all nodes in ⋃k=0d∗‍Rk∗ is t≤(Δ-1)Td∗. Thus, we have dCF≤(Δ-1)Td∗.In the following, we estimate the time complexities of the CAS-based schemes.Theorem 4.
The time complexity of the CF-CAS scheme isO(|V|2+Δ2|V|).Proof.
To facilitate the latency-ahead value calculation, Algorithm1 takes O(V2) time to construct the shortest path tree rooted at the source node. Then, it takes another O(V2) time to assign the latency-ahead value for every node in the network. In total, the time complexity of Algorithm 1 is bounded by O(V2).
The CF-CAS algorithm takes at mostO(V) time to collect covered set C and uncovered node set C¯ in each time slot i, i≥0. It takes at most C¯ time to pick the uncovered node with the highest latency-ahead value, and then C time to select a parent for the node from set C with a preference of node degree. Recall that uncovered neighbors active at time slot i of the selected parent become listeners at the time slot. The parent iterates at most Δ2 times to guarantee that all listeners can be covered by preventing their covered neighbors from transmitting a message at time slot i. Thus, the algorithm takes at most C¯+C+Δ2=V+Δ2 time for each uncovered node. To cover all nodes, the time complexity of the Algorithm 2 is bounded by O(V(V+Δ2))=O(V2+Δ2V). We combine all the running times and conclude that the time complexity of the scheme is O(V2+Δ2V).Theorem 5.
The time complexity of the CT-CAS scheme isO(Δ|V|2).Proof.
Similar to the proof of Theorem4, the CT-CAS scheme takes O(V2) time to assign latency-ahead value for every node in a network. The only difference between two CAS-based schemes is that the CT-CAS algorithm does not require Δ2 time to guarantee all listeners in a time slot will be covered. Instead, it takes Δ time to collect all listeners and then takes at most ΔV time to prevent collision at nodes with high latency-ahead values. Thus, the algorithm requires O(C¯+C+Δ+ΔV)=O(V+ΔV)=O(ΔV) time for each uncovered node, as V≥1 and Δ≥1. To cover all nodes, the time complexity of Algorithm 3 is bounded by O(VΔV)=O(ΔV2). Combining this with the time complexity of Algorithm 1, we conclude that the time complexity of the CT-CAS scheme is O(ΔV2).


## 6. Performance Evaluation

### 6.1. Simulation Environment

In this section, the performance of the proposed schemes is evaluated using a simulator written in C#. The simulation configurations are similar to the ones in [22]. Each network is generated by uniformly deploying all sensor nodes in a square area of 200 m×200m. All nodes are assumed to have the same transmission range. They obtain their active time slots randomly. To enable an energy consumption evaluation, we adopt the energy model of the Mica2 platform [43]. A node consumes 9.6mJ/s and 0.33mJ/s in an active state and a sleeping state, respectively. It costs 5.76×10-3mJ/byte for transmitting and 0.88×10-3mJ/byte for receiving a message. A message has a fixed size of 28 bytes as in TinyOS. The length of each time slot is 20 milliseconds. We neglect the energy consumed during the network initialization phase.Broadcast latency, the total number of transmissions, and the total energy consumption of the proposed schemes are compared with those of VIA [20], LABS[22], and DCTS [29]. We did not include ELAC [19] and OTAB [21] into the comparison because their performances in terms of both broadcast latency and number of transmissions are consistently dominated by LABS [22]. The effect of network parameters including network density, transmission range, and the duty-cycle on the performance of these schemes is studied. We vary one of the parameters while fixing the others in each simulation. Each value plotted on the curves is obtained from the results of 200 randomly generated networks with a randomly chosen source node. Table 3 summarizes the simulation parameters.Table 3
Simulation parameters for the critical-path aware broadcast scheduling.
Parameter Value Network area 200  m × 200  m Energy rate in active 9.6  m J / s Energy rate in sleep 0.33  m J / s Energy rate in transmitting 5.76 × 1 0 - 3  m J / b y t e Energy rate in receiving 0.88 × 1 0 - 3  m J / b y t e Message size 28  b y t e s Length of time slot 20 × 1 0 - 3  s Number of nodes 120 ~ 1000 Transmission range 20  m ~ 60  m Length of working period 2 ~ 10 time slots


### 6.2. Simulation Results

#### 6.2.1. The Impact of the Number of Nodes

Figure7 presents the performance of the schemes in low-density networks and high-density ones where the number of nodes is varied from 120 to 280 and from 400 to 1000 with increments of 40 and 200, respectively. The transmission range and the length of the working period are fixed to 30m and 4, respectively. In low-density scenarios, broadcast latencies of all schemes decrease when the network size increases because a node has more choices to forward a message, as shown in Figure 7(a). When the network density becomes high, there are more levels in a network. As level-based schemes, LABS and DCTS require more time to complete a broadcast process. The broadcast latencies of VIA and two proposed schemes decrease slightly since a node needs to wait longer to prevent interference with its neighbors. In all cases, the proposed schemes consistently outperform in terms of broadcast latency. By accelerating transmissions for nodes with high criticality, the broadcast latency of CF-CAS is 5.3-12 percent shorter than that of VIA. CT-CAS further reduces the latency up to 9.3 percent more than CF-CAS by allowing collision at less critical nodes.Figure 7
The impact of the number of nodes (transmission range is30m, length of working period is 4).
(a) (b) (c)Figure7(b) shows that the total number of transmissions of all schemes grows. The reason is that each forwarding node has more neighbors when the network density increases. It leads to the increment of number of transmissions to cover the neighbors. Consequently, the total energy consumption of all the schemes increases as shown in Figure 7(c). In order to reduce broadcast latency, CF-CAS and CT-CAS require up to 3.8 percent and 17.6 percent more transmissions than VIA, respectively. DCTS and CT-CAS produce more transmissions than LABS and CF-CAS because of additional transmissions for nodes experiencing collisions. Thanks to the shorter broadcast schedules, all nodes in a network can stop working earlier in the proposed schemes. It results in an improvement of up to 19.9 percent in total energy consumption compared to VIA.The experiment results depict a notable extra delay of LABS because it unnecessarily suspends the collision-free transmissions to nonindependent nodes in a layer until all independent nodes in the layer received a message. This extra latency persistently results in bigger broadcast latencies than those of other schemes throughout all our experiments. To reflect the influence of CAS in reducing broadcast latency, the rest of comparisons only include VIA and DCTS, which produce the shortest broadcast latency among existing schemes deploying a collision-free and a collision-tolerant approaches, respectively.


#### 6.2.2. The Impact of the Transmission Range

The effect of varying transmission ranges on the performance of the schemes is studied with400 nodes. The length of the working period is fixed to 4. As coverage area of a node gets bigger when its transmission range increases, a broadcast message can reach to a further node in a transmission. In other words, the message propagation may be faster with the bigger transmission range. This leads to a reduction of the broadcast latencies of all the schemes, as shown in Figure 8(a). CF-CAS achieves from 2.9 to 12 percent latency reduction over VIA while CT-CAS reduces up to 9.3 percent more.Figure 8
The impact of the transmission range (number of nodes is400, length of working period is 4).
(a) (b) (c)Subsequently, the number of neighbors of a node increases as its transmission range does. As the node can cover more neighbors with a transmission, it potentially requires a fewer number of transmissions to cover all nodes in a network. The total number of transmissions and the total energy consumption decrease, as shown in Figures8(b) and 8(c), respectively. Due to additional transmissions to nodes experiencing collision, CT-CAS requires 7.4-11.9 percent more transmissions than CF-CAS. The two schemes produce at most 16.3 and 3.8 percent more transmissions than VIA, respectively. However, the total energy consumptions of CF-CAS and CT-CAS consistently outperform VIA by 1.1-11.8 and 0.1-17.7 percent due to their shorter broadcast schedules, respectively.


#### 6.2.3. The Impact of the Duty-Cycle

Figure9 presents the impact of the duty-cycle on the performance of the schemes. While varying the length of the working period, we fix the number of nodes at 400 and the transmission range at 30 m. As nodes sleep longer when the length of working period increases, a forwarding node takes more time to wait for its receivers waking up. Figure 9(a) shows that the broadcast latencies of all schemes increase. Thanks to node criticality awareness, CF-CAS improves the broadcast latency by 1.8-15 percent compared to VIA. Instead of deferring a transmission to prevent a collision at every node, CT-CAS allows collisions at some nodes to reduce the broadcast latency by 0.5-10.2 percent compared to CF-CAS.Figure 9
The impact of the duty-cycle (number of nodes is400, transmission range is 30).
(a) (b) (c)In a longer working period, a forwarding node may require more transmissions to cover all of its neighbors with different active slots. Thus, the total number of transmissions grows with the decrease of working period length, as shown in Figure9(b). However, the total energy consumption of VIA, CF-CAS, and CT-CAS decreases because their broadcast schedules are short enough and there will be more nodes sleeping in each working period with a bigger T, as shown in Figure 9(c). Although the proposed schemes produce 2.4-28.8 percent more transmissions than VIA, CF-CAS and CT-CAS, respectively, require 0.8-14.8 and 9.9-20.8 percent less energy by completing a broadcast faster.


#### 6.2.4. The Trade-Off between Number of Transmissions and Broadcast Latency

While the network diameter, i.e., the shortest distance between the two most distant nodes, increases by adding more nodes or reducing the transmission range, the broadcast latency improvements of CF-CAS and CT-CAS schemes compared to VIA also increase, as shown in Figures7(a) and 8(a). This reveals that CAS approach reduces more broadcast latency in networks with longer diameters. By contrast, the proposed schemes become worse in terms of number of transmissions in such networks, as shown in Figures 7(b) and 8(b). The reason is that transmissions from high-degree forwarding nodes in VIA scheme can cover more nodes than transmissions from nodes in critical paths in the proposed schemes.To present the trade-off between the number of transmissions and the latency of a broadcast, we refer to nodes with latency-ahead values higher thanτ(0≤τ≤1) times the maximum latency-ahead value ascritical nodes in the network. The other nodes are referred to as noncritical ones. We slightly modify the CT-CAS algorithm, later on referred to as CT-CAS(τ), by allowing collisions at only nocritical nodes. After covering a critical node in a time slot, its covered neighbors will not be selected as forwarders in the time slot, i.e., excluded from the covered node set, to prevent collision at the critical node. It is worth noting that the CT-CAS algorithm is the case of CT-CAS(τ) when τ=1. The bigger the parameter τ is, the less the critical nodes a network has. And thus, it increases the number of collisions possible occurring at noncritical nodes.From simulation results shown in Figure10, we observe that the increase of τ results in performance improvement in terms of broadcast latency. With a high τ, transmissions to nodes with high latency-ahead values receive more preference in a broadcast schedule. Such nodes can receive a message sooner to forward the message further. Hence, the overall broadcast latency is reduced. Obviously, more transmissions are required to accommodate collision possibly occurring at the noncritical nodes. With τ=1, the latency of CT-CAS(1) is the closest to the lower bound of the broadcast latency, which is the the maximum latency-ahead value in a network. The results show that the broadcast latency of CT-CAS(1) is at least 4.1 percent lower than that of CF-CAS. CT-CAS(1) requires at most 14.3 percent more transmissions than CF-CAS due to retransmissions.Figure 10
The trade-off between the number of transmissions and the latency of a broadcast (transmission range is30m, the length of working period is 4).
(a) (b)


## 6.1. Simulation Environment

In this section, the performance of the proposed schemes is evaluated using a simulator written in C#. The simulation configurations are similar to the ones in [22]. Each network is generated by uniformly deploying all sensor nodes in a square area of 200 m×200m. All nodes are assumed to have the same transmission range. They obtain their active time slots randomly. To enable an energy consumption evaluation, we adopt the energy model of the Mica2 platform [43]. A node consumes 9.6mJ/s and 0.33mJ/s in an active state and a sleeping state, respectively. It costs 5.76×10-3mJ/byte for transmitting and 0.88×10-3mJ/byte for receiving a message. A message has a fixed size of 28 bytes as in TinyOS. The length of each time slot is 20 milliseconds. We neglect the energy consumed during the network initialization phase.Broadcast latency, the total number of transmissions, and the total energy consumption of the proposed schemes are compared with those of VIA [20], LABS[22], and DCTS [29]. We did not include ELAC [19] and OTAB [21] into the comparison because their performances in terms of both broadcast latency and number of transmissions are consistently dominated by LABS [22]. The effect of network parameters including network density, transmission range, and the duty-cycle on the performance of these schemes is studied. We vary one of the parameters while fixing the others in each simulation. Each value plotted on the curves is obtained from the results of 200 randomly generated networks with a randomly chosen source node. Table 3 summarizes the simulation parameters.Table 3
Simulation parameters for the critical-path aware broadcast scheduling.
Parameter Value Network area 200  m × 200  m Energy rate in active 9.6  m J / s Energy rate in sleep 0.33  m J / s Energy rate in transmitting 5.76 × 1 0 - 3  m J / b y t e Energy rate in receiving 0.88 × 1 0 - 3  m J / b y t e Message size 28  b y t e s Length of time slot 20 × 1 0 - 3  s Number of nodes 120 ~ 1000 Transmission range 20  m ~ 60  m Length of working period 2 ~ 10 time slots


## 6.2. Simulation Results

### 6.2.1. The Impact of the Number of Nodes

Figure7 presents the performance of the schemes in low-density networks and high-density ones where the number of nodes is varied from 120 to 280 and from 400 to 1000 with increments of 40 and 200, respectively. The transmission range and the length of the working period are fixed to 30m and 4, respectively. In low-density scenarios, broadcast latencies of all schemes decrease when the network size increases because a node has more choices to forward a message, as shown in Figure 7(a). When the network density becomes high, there are more levels in a network. As level-based schemes, LABS and DCTS require more time to complete a broadcast process. The broadcast latencies of VIA and two proposed schemes decrease slightly since a node needs to wait longer to prevent interference with its neighbors. In all cases, the proposed schemes consistently outperform in terms of broadcast latency. By accelerating transmissions for nodes with high criticality, the broadcast latency of CF-CAS is 5.3-12 percent shorter than that of VIA. CT-CAS further reduces the latency up to 9.3 percent more than CF-CAS by allowing collision at less critical nodes.Figure 7
The impact of the number of nodes (transmission range is30m, length of working period is 4).
(a) (b) (c)Figure7(b) shows that the total number of transmissions of all schemes grows. The reason is that each forwarding node has more neighbors when the network density increases. It leads to the increment of number of transmissions to cover the neighbors. Consequently, the total energy consumption of all the schemes increases as shown in Figure 7(c). In order to reduce broadcast latency, CF-CAS and CT-CAS require up to 3.8 percent and 17.6 percent more transmissions than VIA, respectively. DCTS and CT-CAS produce more transmissions than LABS and CF-CAS because of additional transmissions for nodes experiencing collisions. Thanks to the shorter broadcast schedules, all nodes in a network can stop working earlier in the proposed schemes. It results in an improvement of up to 19.9 percent in total energy consumption compared to VIA.The experiment results depict a notable extra delay of LABS because it unnecessarily suspends the collision-free transmissions to nonindependent nodes in a layer until all independent nodes in the layer received a message. This extra latency persistently results in bigger broadcast latencies than those of other schemes throughout all our experiments. To reflect the influence of CAS in reducing broadcast latency, the rest of comparisons only include VIA and DCTS, which produce the shortest broadcast latency among existing schemes deploying a collision-free and a collision-tolerant approaches, respectively.


### 6.2.2. The Impact of the Transmission Range

The effect of varying transmission ranges on the performance of the schemes is studied with400 nodes. The length of the working period is fixed to 4. As coverage area of a node gets bigger when its transmission range increases, a broadcast message can reach to a further node in a transmission. In other words, the message propagation may be faster with the bigger transmission range. This leads to a reduction of the broadcast latencies of all the schemes, as shown in Figure 8(a). CF-CAS achieves from 2.9 to 12 percent latency reduction over VIA while CT-CAS reduces up to 9.3 percent more.Figure 8
The impact of the transmission range (number of nodes is400, length of working period is 4).
(a) (b) (c)Subsequently, the number of neighbors of a node increases as its transmission range does. As the node can cover more neighbors with a transmission, it potentially requires a fewer number of transmissions to cover all nodes in a network. The total number of transmissions and the total energy consumption decrease, as shown in Figures8(b) and 8(c), respectively. Due to additional transmissions to nodes experiencing collision, CT-CAS requires 7.4-11.9 percent more transmissions than CF-CAS. The two schemes produce at most 16.3 and 3.8 percent more transmissions than VIA, respectively. However, the total energy consumptions of CF-CAS and CT-CAS consistently outperform VIA by 1.1-11.8 and 0.1-17.7 percent due to their shorter broadcast schedules, respectively.


### 6.2.3. The Impact of the Duty-Cycle

Figure9 presents the impact of the duty-cycle on the performance of the schemes. While varying the length of the working period, we fix the number of nodes at 400 and the transmission range at 30 m. As nodes sleep longer when the length of working period increases, a forwarding node takes more time to wait for its receivers waking up. Figure 9(a) shows that the broadcast latencies of all schemes increase. Thanks to node criticality awareness, CF-CAS improves the broadcast latency by 1.8-15 percent compared to VIA. Instead of deferring a transmission to prevent a collision at every node, CT-CAS allows collisions at some nodes to reduce the broadcast latency by 0.5-10.2 percent compared to CF-CAS.Figure 9
The impact of the duty-cycle (number of nodes is400, transmission range is 30).
(a) (b) (c)In a longer working period, a forwarding node may require more transmissions to cover all of its neighbors with different active slots. Thus, the total number of transmissions grows with the decrease of working period length, as shown in Figure9(b). However, the total energy consumption of VIA, CF-CAS, and CT-CAS decreases because their broadcast schedules are short enough and there will be more nodes sleeping in each working period with a bigger T, as shown in Figure 9(c). Although the proposed schemes produce 2.4-28.8 percent more transmissions than VIA, CF-CAS and CT-CAS, respectively, require 0.8-14.8 and 9.9-20.8 percent less energy by completing a broadcast faster.


### 6.2.4. The Trade-Off between Number of Transmissions and Broadcast Latency

While the network diameter, i.e., the shortest distance between the two most distant nodes, increases by adding more nodes or reducing the transmission range, the broadcast latency improvements of CF-CAS and CT-CAS schemes compared to VIA also increase, as shown in Figures7(a) and 8(a). This reveals that CAS approach reduces more broadcast latency in networks with longer diameters. By contrast, the proposed schemes become worse in terms of number of transmissions in such networks, as shown in Figures 7(b) and 8(b). The reason is that transmissions from high-degree forwarding nodes in VIA scheme can cover more nodes than transmissions from nodes in critical paths in the proposed schemes.To present the trade-off between the number of transmissions and the latency of a broadcast, we refer to nodes with latency-ahead values higher thanτ(0≤τ≤1) times the maximum latency-ahead value ascritical nodes in the network. The other nodes are referred to as noncritical ones. We slightly modify the CT-CAS algorithm, later on referred to as CT-CAS(τ), by allowing collisions at only nocritical nodes. After covering a critical node in a time slot, its covered neighbors will not be selected as forwarders in the time slot, i.e., excluded from the covered node set, to prevent collision at the critical node. It is worth noting that the CT-CAS algorithm is the case of CT-CAS(τ) when τ=1. The bigger the parameter τ is, the less the critical nodes a network has. And thus, it increases the number of collisions possible occurring at noncritical nodes.From simulation results shown in Figure10, we observe that the increase of τ results in performance improvement in terms of broadcast latency. With a high τ, transmissions to nodes with high latency-ahead values receive more preference in a broadcast schedule. Such nodes can receive a message sooner to forward the message further. Hence, the overall broadcast latency is reduced. Obviously, more transmissions are required to accommodate collision possibly occurring at the noncritical nodes. With τ=1, the latency of CT-CAS(1) is the closest to the lower bound of the broadcast latency, which is the the maximum latency-ahead value in a network. The results show that the broadcast latency of CT-CAS(1) is at least 4.1 percent lower than that of CF-CAS. CT-CAS(1) requires at most 14.3 percent more transmissions than CF-CAS due to retransmissions.Figure 10
The trade-off between the number of transmissions and the latency of a broadcast (transmission range is30m, the length of working period is 4).
(a) (b)


## 6.2.1. The Impact of the Number of Nodes

Figure7 presents the performance of the schemes in low-density networks and high-density ones where the number of nodes is varied from 120 to 280 and from 400 to 1000 with increments of 40 and 200, respectively. The transmission range and the length of the working period are fixed to 30m and 4, respectively. In low-density scenarios, broadcast latencies of all schemes decrease when the network size increases because a node has more choices to forward a message, as shown in Figure 7(a). When the network density becomes high, there are more levels in a network. As level-based schemes, LABS and DCTS require more time to complete a broadcast process. The broadcast latencies of VIA and two proposed schemes decrease slightly since a node needs to wait longer to prevent interference with its neighbors. In all cases, the proposed schemes consistently outperform in terms of broadcast latency. By accelerating transmissions for nodes with high criticality, the broadcast latency of CF-CAS is 5.3-12 percent shorter than that of VIA. CT-CAS further reduces the latency up to 9.3 percent more than CF-CAS by allowing collision at less critical nodes.Figure 7
The impact of the number of nodes (transmission range is30m, length of working period is 4).
(a) (b) (c)Figure7(b) shows that the total number of transmissions of all schemes grows. The reason is that each forwarding node has more neighbors when the network density increases. It leads to the increment of number of transmissions to cover the neighbors. Consequently, the total energy consumption of all the schemes increases as shown in Figure 7(c). In order to reduce broadcast latency, CF-CAS and CT-CAS require up to 3.8 percent and 17.6 percent more transmissions than VIA, respectively. DCTS and CT-CAS produce more transmissions than LABS and CF-CAS because of additional transmissions for nodes experiencing collisions. Thanks to the shorter broadcast schedules, all nodes in a network can stop working earlier in the proposed schemes. It results in an improvement of up to 19.9 percent in total energy consumption compared to VIA.The experiment results depict a notable extra delay of LABS because it unnecessarily suspends the collision-free transmissions to nonindependent nodes in a layer until all independent nodes in the layer received a message. This extra latency persistently results in bigger broadcast latencies than those of other schemes throughout all our experiments. To reflect the influence of CAS in reducing broadcast latency, the rest of comparisons only include VIA and DCTS, which produce the shortest broadcast latency among existing schemes deploying a collision-free and a collision-tolerant approaches, respectively.


## 6.2.2. The Impact of the Transmission Range

The effect of varying transmission ranges on the performance of the schemes is studied with400 nodes. The length of the working period is fixed to 4. As coverage area of a node gets bigger when its transmission range increases, a broadcast message can reach to a further node in a transmission. In other words, the message propagation may be faster with the bigger transmission range. This leads to a reduction of the broadcast latencies of all the schemes, as shown in Figure 8(a). CF-CAS achieves from 2.9 to 12 percent latency reduction over VIA while CT-CAS reduces up to 9.3 percent more.Figure 8
The impact of the transmission range (number of nodes is400, length of working period is 4).
(a) (b) (c)Subsequently, the number of neighbors of a node increases as its transmission range does. As the node can cover more neighbors with a transmission, it potentially requires a fewer number of transmissions to cover all nodes in a network. The total number of transmissions and the total energy consumption decrease, as shown in Figures8(b) and 8(c), respectively. Due to additional transmissions to nodes experiencing collision, CT-CAS requires 7.4-11.9 percent more transmissions than CF-CAS. The two schemes produce at most 16.3 and 3.8 percent more transmissions than VIA, respectively. However, the total energy consumptions of CF-CAS and CT-CAS consistently outperform VIA by 1.1-11.8 and 0.1-17.7 percent due to their shorter broadcast schedules, respectively.


## 6.2.3. The Impact of the Duty-Cycle

Figure9 presents the impact of the duty-cycle on the performance of the schemes. While varying the length of the working period, we fix the number of nodes at 400 and the transmission range at 30 m. As nodes sleep longer when the length of working period increases, a forwarding node takes more time to wait for its receivers waking up. Figure 9(a) shows that the broadcast latencies of all schemes increase. Thanks to node criticality awareness, CF-CAS improves the broadcast latency by 1.8-15 percent compared to VIA. Instead of deferring a transmission to prevent a collision at every node, CT-CAS allows collisions at some nodes to reduce the broadcast latency by 0.5-10.2 percent compared to CF-CAS.Figure 9
The impact of the duty-cycle (number of nodes is400, transmission range is 30).
(a) (b) (c)In a longer working period, a forwarding node may require more transmissions to cover all of its neighbors with different active slots. Thus, the total number of transmissions grows with the decrease of working period length, as shown in Figure9(b). However, the total energy consumption of VIA, CF-CAS, and CT-CAS decreases because their broadcast schedules are short enough and there will be more nodes sleeping in each working period with a bigger T, as shown in Figure 9(c). Although the proposed schemes produce 2.4-28.8 percent more transmissions than VIA, CF-CAS and CT-CAS, respectively, require 0.8-14.8 and 9.9-20.8 percent less energy by completing a broadcast faster.


## 6.2.4. The Trade-Off between Number of Transmissions and Broadcast Latency

While the network diameter, i.e., the shortest distance between the two most distant nodes, increases by adding more nodes or reducing the transmission range, the broadcast latency improvements of CF-CAS and CT-CAS schemes compared to VIA also increase, as shown in Figures7(a) and 8(a). This reveals that CAS approach reduces more broadcast latency in networks with longer diameters. By contrast, the proposed schemes become worse in terms of number of transmissions in such networks, as shown in Figures 7(b) and 8(b). The reason is that transmissions from high-degree forwarding nodes in VIA scheme can cover more nodes than transmissions from nodes in critical paths in the proposed schemes.To present the trade-off between the number of transmissions and the latency of a broadcast, we refer to nodes with latency-ahead values higher thanτ(0≤τ≤1) times the maximum latency-ahead value ascritical nodes in the network. The other nodes are referred to as noncritical ones. We slightly modify the CT-CAS algorithm, later on referred to as CT-CAS(τ), by allowing collisions at only nocritical nodes. After covering a critical node in a time slot, its covered neighbors will not be selected as forwarders in the time slot, i.e., excluded from the covered node set, to prevent collision at the critical node. It is worth noting that the CT-CAS algorithm is the case of CT-CAS(τ) when τ=1. The bigger the parameter τ is, the less the critical nodes a network has. And thus, it increases the number of collisions possible occurring at noncritical nodes.From simulation results shown in Figure10, we observe that the increase of τ results in performance improvement in terms of broadcast latency. With a high τ, transmissions to nodes with high latency-ahead values receive more preference in a broadcast schedule. Such nodes can receive a message sooner to forward the message further. Hence, the overall broadcast latency is reduced. Obviously, more transmissions are required to accommodate collision possibly occurring at the noncritical nodes. With τ=1, the latency of CT-CAS(1) is the closest to the lower bound of the broadcast latency, which is the the maximum latency-ahead value in a network. The results show that the broadcast latency of CT-CAS(1) is at least 4.1 percent lower than that of CF-CAS. CT-CAS(1) requires at most 14.3 percent more transmissions than CF-CAS due to retransmissions.Figure 10
The trade-off between the number of transmissions and the latency of a broadcast (transmission range is30m, the length of working period is 4).
(a) (b)


## 7. Conclusions

This paper presents a critical-path aware scheduling (CAS) for the Minimum Latency Broadcast Scheduling problem in duty-cycled wireless sensor networks. The scheduling reduces the broadcast latency by preferring transmissions to nodes along the critical paths of a network. We employ the scheduling in two latency-efficient broadcast schemes: Collision-Free-CAS (CF-CAS) and Collision-Tolerant-CAS (CT-CAS). By allowing collisions at low criticality nodes, CT-CAS accelerates the broadcast process for high criticality ones. It produces a shorter broadcast schedule with more transmissions than CF-CAS. Both proposed schemes improve up to19.6 percent in terms of broadcast latency while increasing the number of transmissions at most 28.8 percent compared with those of existing schemes. The shorter broadcast schedule reduces up to 20.8 percent the total energy consumption.For further study, finding a solution for latency-efficient multicasting in duty cycled WSNs is an appealing problem. Broadcast schemes that balance energy consumption of every node in order to maximize the network lifetime is another challenging problem. Last but not least, we intend to study more realistic uneven node deployments to prove the applicability of our proposed methods.



---

*Source: 5017319-2018-10-22.xml*