# Energy-Efficient Broadcast Scheduling Algorithm in Duty-Cycled Multihop Wireless Networks

Authors: Quan Chen; Tao Wang; Lianglun Cheng; Yongchao Tao; Hong Gao
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

Broadcasting is a fundamental function for disseminating messages in multihop wireless networks. Minimum-Transmission Broadcasting (MTB) problem aims to find a broadcast schedule with minimum number of transmissions. Previous works on MTB in duty-cycled networks exploit a rigid assumption that nodes have only active time slot per working cycle. In this paper, we investigated the MTB problem in duty-cycled networks where nodes are allowed arbitrary active time slots per working cycle (MTBDCA problem). Firstly, it is proved to be NP-hard ando(ln⁡Δ)-inapproximable, where Δ is the maximum degree in the network. Secondly, an auxiliary graph is proposed to integrate nodes’ active time slots into the network and a novel covering problem is proposed to exploit nodes’ multiple active time slots for scheduling. Then, a ln⁡(Δ+1)-approximation algorithm is proposed for MTBDCA and a (ln⁡(Δ+1)+Δ)-approximation algorithm is proposed for all-to-all MTBDCA. Finally, extensive experimental results demonstrate the efficiency of the proposed algorithm.


---

## Body

## 1. Introduction

Broadcasting is a fundamental function for many services in wireless sensor networks (WSNs) [1, 2], such as data collection, code updating, and topology discovering [3–6]. Many effective broadcasting algorithms have been investigated to improve the network performance, while the total number of transmissions is often taken as a measured metric. Obviously, the smaller the number of transmissions is, the more energy will be saved. Therefore, the Minimum-Transmission Broadcasting problem (MTB), which tries to minimize the number of transmissions, has got a lot of attentions from researchers. In traditional wireless sensor networks where each node always keeps awake, many broadcasting algorithms [7–15] have been proposed. Since the MTB problem has been proved to be NP-hard [7] and the aforementioned algorithms [7–15] are approximate ones, they achieve high energy efficiency during broadcasting.However, it is well known that the duty-cycled scheme is commonly adopted in wireless sensor networks to conserve energy [16, 17]. In such working mode, each node switches between the active state and sleep state cyclically. To save energy, all the functional modules (such as sensing the environment, sending, and receiving the messages) are turned off in sleep state. As this working mode is much different, the MTB problem in duty-cycled wireless sensor networks needs to be reinvestigated and the following two issues should be addressed: (1) A node may need several transmissions to inform all its neighbors since the neighbors may be active at different time slots. (2) How to construct the broadcast tree to exploit nodes’ multiple active time slots for scheduling is also a big challenge. In duty-cycled wireless networks, the MTB problem is mainly studied by [18–21] currently. To reduce the number of transmissions, these algorithms try to organize the nodes with the same active time slot together, and they provided a solution for the aforementioned Issue 1. However, these methods exploit a strong assumption that all nodes can be active only once in a working cycle. When each node can be active arbitrary times per working cycle [16, 17, 22], these methods cannot solve the aforementioned Issue 2 efficiently and may result in a large redundancy.Thus, to avoid the above shortcomings, the MTB problem in duty-cycled WSNs where nodes have arbitrary active time slots per working cycle (MTBDCA problem) is studied in this paper. To exploit nodes’ whole active time slots, an auxiliary graph is designed and a novel kind of node covering problem,i.e., minimum schedule node covering problem, is proposed. Finally, a ln⁡(Δ+1)-approximation algorithm is proposed for MTBDCA. The contributions of this paper are mainly listed as follows.(1) The MTBDCA problem is firstly formulated and proved to be NP-hard ando(ln⁡Δ)-inapproximable, where Δ is the maximum degree in the network. An auxiliary graph is designed to integrate nodes’ active time slots into the network.(2) In order to exploit nodes’ whole active time slots for scheduling, a novel kind of node covering problem,i.e., minimum schedule node covering problem, is proposed and proved to be NP-hard. An approximate algorithm is proposed to solve it.(3) An approximation algorithm with ratio ofln⁡(Δ+1) is proposed for MTBDCA, where Δ is the maximum degree in the network. An (ln⁡(Δ+1)+Δ)-approximation algorithm is also proposed for all-to-all MTBDCA problem.(4) The extensive simulations verify that the proposed algorithm can achieve high performance in terms of energy efficiency.Compared to the conference version [23], this paper not only investigates the all-to-all MTBDCA problem and provide a (ln⁡(Δ+1)+Δ)-approximation algorithm for it but also provides more details on the theoretical analysis, such as the proof of the NP-hardness of the Minimum Schedule Node Covering problem and the correctness of the broadcast tree construction algorithm, which are important for the completeness of the proposed methods. Additionally, the new experiments are also conducted to show some new findings of the proposed methods.The rest of this paper is organized as follows. The related works are introduced in Section2. Section 3 gives the network model and problem definition. The proposed approximate algorithm for MTBDCA is presented in Section 4. The simulation results and conclusion are given in Sections 5 and 6.


## 2. Related Works

The Minimum-Transmission Broadcasting (MTB) problem has drawn a lot of attentions from researchers. When each node always keeps awake, the MTB problem in WSNs are mainly studied by [7–15]. The NP-hardness of MTB problem was first proved in [7], where a tree-based structure is used to disseminate the messages. After that, the MCDS-based (Minimum Connected Dominate Set) scheme is used to further reduce the redundancy by minimizing the number of senders in the broadcast tree [8–10]. Louet al. [11, 12] proposed a Dominant Pruning scheme and a quasi-local forward-node-set-based scheme to reduce the redundancy. The multipoint relay scheme is introduced for MTB in [13–15], which can determine a small set of forwarding nodes in a localized way. Since CDS is the core of the algorithms for MTB, Wanet al. proposed an 8-approximation algorithm in [24]. With a two-phase constructing approach, they reduced the approximation ratio to 6.8 in [25]. Recently, the CDS construction problem in battery-free WSNs and the weakly CDS construction problem are studied in [26–28]. However, these methods are unsuitable for duty-cycled wireless networks.In duty-cycled wireless networks, the MTB problem are studied in [18–21]. The MTB problem in duty-cycled networks was first proved to be NP-hard in [18]. In [18], a centralized 3(ln⁡Δ+1)-approximation algorithm is proposed by exploiting a set covering technique. After that, the authors in [19, 20] proposed a level-based scheduling framework and constructed the backbone according to nodes’ level information to reduce the number of transmissions. Recently, the authors in [21] found that the number of transmissions can be further improved if a depth-first search is conducted on the forwarding nodes. Based on this, they proposed an efficient broadcasting algorithm outperforms the previous ones. However, these methods all assume that all nodes can active only once in a working cycle, which limits their application. When each node has multiple active time slot in a working cycle, the efficient algorithms have been proposed for multicasting [16, 29], flooding [22], data aggregation [17], and beaconing [30] in the duty-cycled networks, respectively. Thus, it is very necessary and meaningful to study the MTBDCA problem.


## 3. Problem Definition

LetG=(V,E) denote a duty-cycled WSN, where V=1,2,…,n denotes all nodes and E=(u,v)∣1≤u,v≤n&u≠v denotes the neighborhood relationship among nodes. As discussed before, each node owns two states in such network,i.e., the sleep state and the active state, and switches between these two states cyclically. Let W denote a working cycle which includes W time slots with same length,i.e., W=0,1,2,…,W-1. And assume W(u) denote theworking plan of node u, which is defined as the set of the active time slots of u,i.e., W(u)=t1,t2,…,tk⊆0,1,…,W-1. If node u wants to receive a packet, it can only receive it when it is active (i.e., the time slot t∈W(u)). When it wants to send a message, it can choose a time slot when the receiver is awake to switch to the active state. The duty cycle is calculated as Wu/W. Table 1 lists the major symbols used in this paper.Table 1
Symbols and notations.
Notation Description G=(V,E) a duty-cycled WSN n the number of nodes in the network W a working cycle W(u) nodeu’s working plan sch(u) nodeu’s transmitting schedule ch(u,t) the set of nodeu’s children which can be reached at time t ch(u) the set of all child nodes of nodeu S(u) all the transmitting schedules of nodeu T the broadcast tree ofG S=(T,S(T)) the broadcast schedules ofG G=(V′,E′) the auxiliary graph ofG au,i thei-th schedule node of v au,i.p the schedule nodeau,i’s primary node au,i.t the schedule nodeau,i’s transmitting time slot R(au,i) the set of primary nodes which can be reached byau,i AS the set of schedule nodes for the MSNC problem AP the set of all primary nodes of whose schedule node inAS L(u) the level of nodeu Tu the subtree rooted at nodeu NB(u) the set of nodeu’s neighbors ψ the average number of neighbors inG Δ the maximum node degree ofGAs for MTB problem in duty-cycled WSNs, one not only needs to construct a broadcast tree which is rooted at the source nodes, but also computes theTransmitting Schedule of each nonleaf node to informs its children while the number of transmissions is minimized. Before giving the formal definition ofTransmitting Schedule, some notations used in this paper should be clarified. Assume NB(u) denote the set of u’s one-hop neighbors in G. And let T denote the broadcast tree; nl(T) and ch(u) denote the set of nonleaf nodes and the set of u’s children in the broadcast tree, respectively. Then we can have,Definition 1 (transmitting schedule).
Given any nodeu∈V, let sch(u)=[u,t,ch(u,t)] denote node u’s one transmitting schedule, in which for any node v∈ch(u,t), we have (u,v)∈E and t%W∈W(v).Given a transmitting schedulesch(u), it means that node u can deliver the message to all the nodes in ch(u,t) through only one transmission at time slot t. To receive the message, each node v∈ch(u,t) is able to wake up at time slot t(t%W∈W(v)). Note that a node may have several transmitting schedules, then we can find that ch(u)=⋃sch(u)∈S(u)sch(u).ch(u,t), where S(u) is the set of all transmitting schedules of u.Thus, the MTB problem in duty-cycled WSNs where nodes have arbitrary active time slots per working cycle (MTBDCA) is to compute a broadcast tree T and calculate one or several transmitting schedules for nonleaf nodes in the broadcast tree,i.e., S(T), with minimum number of transmissions. The broadcast tree T and the transmitting schedules of each nonleaf node S(T) are called a broadcast schedule. It can be formalized as follows.Input:(1)
A duty-cycled networkG=(V,E) and a source node s.(2)
The working plans for all nodes,i.e., W(v)∣∀v∈V.Output: The broadcast schedule Smin=T,ST, where S(T)=S(u)∣∀u∈nl(T), where(1)
T is rooted at the source node s and spanning all of the nodes in V.(2)
For anysch(u)∈S(u) and S(u)∈S(T), sch(u) satisfies the conditions in Definition 1.(3)
The number of total transmissions,i.e., ∑S(u)∈S(T)Su, is minimized.Theorem 2.
The MTBDCA problem is NP-hard and there exists no polynomial-time approximation algorithm with ratio of1-o1ln⁡Δ for MTBDCA unless NP⊆DTIME(nO(log⁡log⁡n)), where Δ is the maximum degree in the network.Proof.
We prove the NP-hardness of MTBDCA by showing that the Minimum Set Cover (MSC) problem can be mapped to one of its special cases. It has been proved that the MSC problem [29] is NP-hard and there exists no polynomial-time algorithm with ratio of 1-o1ln⁡N unless NP⊆DTIME(nO(log⁡log⁡n)), where N is the size of the MSC problem. Consider a special case of MTBDCA, where there is only one source node s along with its neighbors in the network and all the neighbors are only connected to s. Thus, source node s can choose a set of active time slots to cover all its neighbors. In this case, the MTBDCA problem is equivalent to the MSC problem. The theorem is proved.


## 4. Approximation Algorithm for MTBDCA

In this section, we will introduce an algorithm with approximation ratio ofln⁡(Δ+1) for MTBDCA, which includes the following steps: (1) The auxiliary graph is designed and constructed to integrate nodes’ active time slots into the network. (2) AMinimum Scheduling Node Covering problem is designed for multiple active time slot scheduling and an approximate algorithm is proposed for it. (3) A pseudo broadcast tree which contains nodes’ schedule information is obtained on the constructed auxiliary graph. (4) A broadcast schedule for MTBDCA problem is computed according to the pseudo broadcast tree.


### 4.1. Constructing an Auxiliary Graph

In order to integrate nodes’ working plan into the network and construct the broadcast tree, anAuxiliary Graph is first designed based on the duty-cycled network G. Different from the duty-cycled network, a new kind of node is introduced in the auxiliary graph,i.e.,Schedule Node. It is used to calculate the transmitting schedules for the nonleaf nodes.In this paper, letau denote a schedule node of u(u∈V) (For simplicity, node u is called the primary node of au). Each schedule has two properties,i.e., (au.p, au.t), where au.p denotes the schedule node’s primary node and au.t denotes its transmitting time slot. The auxiliary graph is defined as follows.Definition 3 (auxiliary graph).
Given a duty-cycled networkG=(V,E), the auxiliary graph G=(V′,E′) is a directed graph which contains nodes’ active time slots. The set V′ includes two kinds of nodes (primary node and schedule node) and E′ is the set of all edges. They are constructed as follows: (i)
Initially,V′=V, E′=∅.(ii)
For any nodeu∈V and time t′∈⋃v∈NB(u)W(v), we create a schedule node au,i(1≤i≤⋃v∈NBuWv). Its two properties are set as (u,t′) (i.e., au,i.p=u and au,i.t=t′). Let Υ(u) denote the set of u’s schedule nodes, and then V′=V′⋃u∈VΥ(u).(iii)
For any nodeu∈V and schedule node au,i∈Υ(u), create an edge from u to au,i. Let Eu′=(u,au,i)∣au,i∈Υ(u), then E′ can be updated as E′=⋃u∈VEu′.(iv)
Letv be a one-hop neighbors of u in G. For each schedule node au,i∈Υ(u), add an directed edge (au,i,v) in G if au,i.t∈W(v). Let R(au,i) denote the set of such node v. Actually, it denotes the nodes can be reached by au,i.p at time slot au,i.t. And we can have E′=E′⋃u∈V⋃au,i∈ΥuEau,i′, where Eau,i′=(au,i,v)∣v∈R(au,i).Note that, the auxiliary graph is directed, where the edges are either started from the primary nodeu to its schedule nodes in Υ(u), or started from a schedule node au,i to the primary nodes it can reach at time au,i.t,i.e., R(au,i). For example, there is a simple duty-cycled network in Figure 1(a) and the number in the braces denotes nodes’ working plan. According to Definition 3, its auxiliary graph is constructed as in Figure 1(b). As for node v, there are two neighbors and the union of the active time slots of these neighbors are 1,3,5. Then, three schedule nodes av,1, av,2 and av,3 are created, and their properties are set as (v,1),(v,3) and (v,5). As we can see time slot 1 is only included in the working plan of node u, then there is an edge from node v to av,1 and an edge from av,1 to node u. The pseudo code for constructing the auxiliary graph is shown in Algorithm 1.Algorithm 1:Algorithm for constructing the auxiliary graph.
Input: The duty-cycled network G=(V,E), and the source node s; Output: The auxiliary graph G=(V′,E′); (1)V′←V,E′←∅; (2) for∀u∈Vdo (3) S←⋃v∈NB(u)Wv; (4) i←1; (5) for∀t′∈Sdo (6) V′=V′∪au,i; (7) E′=E′∪u,au,i; (8) au,i.p←u,au,i.t←t′; (9) Rau,i←v∣v∈NB(u)&au,i.t∈W(v); (10) for∀v∈Rau,ido (11) E′=E′∪au,i,v; (12) end for (13) i←i+1; (14) end for (15) end for (16) returnG;Figure 1
An example of the auxiliary graph. Figure1 is reproduced from Chen et al. (2018) (under the Creative Commons Attribution License/public domain).
(a) (b)The size of the auxiliary graph is analyzed in Theorem5.Lemma 4.
Any schedule node in the auxiliary graphG can connect to at most Δ primary nodes.Proof.
According to Definition3, a schedule node au,i is connected to u’s neighboring nodes which have the active time slot au,i.t in its working plan. Obviously, there are at most Δ such nodes. Since the auxiliary graph is directed, thus, the schedule node au,i can connect to at most Δ primary nodes.Theorem 5.
The number of nodes and edges in the auxiliary graphG are at most (1+W)×n and (1+Δ)×n×W, respectively, where W denotes the length of a working period and n=V is the number of nodes of the original graph.Proof.
Firstly, according to Definition3, a schedule node is created for each primary node u and each time slot t∈⋃v∈NB(u)W(v). Since there are at most W time slots in ⋃v∈NB(u)W(v), then there are at most W schedule nodes for each primary node. Thus, the number of nodes in G can be calculated as(1)V′=V+Vs=n+∑u∈VW≤n+n×W≤1+W×nwhere Vs is the number of schedule nodes.
Secondly, for any primary nodeu, there is an edge between u and au,i(au,i∈Υ(u)) according to Definition 3, which is included in Eu′. And for any schedule node au,i, there are at most Δ edges from au,i to the primary nodes in R(au,i). Then, we can have(2)E′=∑u∈VEu′+⋃u∈V⋃au,i∈ΥuEau,i′≤∑u∈VΥu+∑u∈VΥu×Δ≤1+Δ×n×W


### 4.2. Minimum Schedule Node Covering Problem

In this subsection, we will introduce a new kind of problem,i.e.,Minimum Scheduling Node Covering problem. It tries to cover all the nonsource primary nodes in the auxiliary graph with minimum schedule nodes. The new problem can be defined as follows.Definition 6 (minimum schedule node covering problem (MSNC)).
Given a source nodes and an auxiliary graph G, the MSNC problem is objected to compute a set of schedule nodes,i.e., AS, which satisfies the following conditions: (1)
For each nodeu∈V&u≠s, there must exist a schedule node in AS,i.e., av, which satisfies that u∈R(av) (R(av) is the set of primary nodes which can be reached by av).(2)
The size ofAS,i.e., AS, is minimized.Theorem 7.
The MSNC problem is NP-hard and there exists no polynomial-time approximation algorithm with ratio of1-o1ln⁡Δ for MSNC unless NP⊆DTIME(nOlog⁡log⁡n).Proof.
We prove the NP-hardness of the MSNC problem by showing that the MSC problem can be mapped to one of its special cases. For example, Figure2(a) gives an example of MSC, in which U=d1,d2,…,dn is the universe of all n elements and set S=S1,S2,…,Sm denotes m subsets of U. An edge is created between di and Sk if di(1≤i≤n)∈Sk(1≤k≤m). The MSC problem is then to calculate a set of minimum nodes from S to cover all the nodes in U.
To prove the NP-hardness of MSNC, a simple graph with a source nodes and its neighboring nodes di(1≤i≤n) is constructed. The working plan of each node is set as follows: (1) Initially, the working schedule of di(1≤i≤n) is set null; (2) If di(1≤i≤n)∈Sk(1≤k≤m), then W(di)=W(di)∪k. Then, the corresponding auxiliary graph is shown in Figure 2(b), where Sk(1≤k≤m) denote the schedule nodes. Then the MSNC problem is equivalent to the MSC problem, which is proved to NP-hard. The theorem is proved.Figure 2
The example of MSNC problem. Figure2 is reproduced from Chen et al. (2018) (under the Creative Commons Attribution License/public domain).
(a)
The MSC problem (b)
The MSNC problemTo solve the MSNC problem, we exploit the greedy set covering method [31] and choose the schedule node iteratively. Initially, AS is set ∅ and Vp is set V-s. In each loop, the schedule node which has maximum adjacent uncovered primary nodes,i.e., av=argmaxau∈Vs⁡Rau∩Vp, is found. Then, the schedule node av is added to AS, i.e., AS=AS∪{av}, and the covered primary nodes are removed from Vp. This process repeats until there are no uncovered primary nodes in Vp. The detailed procedure is shown in Algorithm 2. Since a schedule node can connect to at most Δ primary nodes, then Algorithm 2 can have an approximation ratio of ln⁡(Δ+1) [31].Algorithm 2:Approximate algorithm for MSNC problem.
Input: The auxiliary graph G, and the source node s; Output: The set of schedule nodes AS; (1) Vp←V-s,AS←∅; (2) Vs← all the schedule nodes in G; (3) whileVp≠∅do (4) av=argmaxau∈Vs⁡Rau∩Vp; (5) AS←AS∪{av}; (6) Vp←Vp-Rav∩Vp; (7) Vs←Vs-av; (8) end while (9) returnAS;


### 4.3. Generating the Pseudo Broadcast Tree

After obtaining the set of schedule nodesAS, aPseudo Broadcast Tree in the auxiliary graph is then constructed to connect all schedule nodes in AS and these schedule nodes’ primary nodes. The pseudo broadcast tree is mainly constructed by two steps: (1) The schedule nodes in AS and their primary nodes are first organized into several subtrees; (2) These subtrees are then merged into one primary tree.AssumeL(v) is the level of each node v (including the primary nodes and schedule nodes in the auxiliary graph). The above step (1) works as follows.Initially, the level of source nodes is set 0,i.e., L(s)=0. Then, a breadth-first search is conducted from s level by level.Second, letAP=av.p∣av∈AS denote the set of primary nodes whose schedule nodes is in AS. If s is not included in AP, add s into AP,i.e., AP=AP∪s.Third, letu be the primary node with the smallest level in AP and Tu denote the subtree rooted at u. Add u into Tu at the beginning,i.e., Tu=Tu∪u. Then we can construct Tu by the following:(1)
For any primary nodem in Tu∩AP, let AS(m)=av∣av∈AS&av.p=m be the set of schedule nodes which are contained in AS and their primary node is m.(2)
For any schedule nodeam∈AS(m), add it into the subtree Tu,i.e., Tu=Tu∪am and create an edge from m to schedule node am. Let n be a primary node in R(am) and not included in any subtrees, add it into subtree Tu,i.e., Tu=Tu∪n and create an edge from schedule node av to n.(3)
Delete the primary nodem from AP,i.e., AP=AP-{m}.The above three steps repeat until there are no nodes inTu∩AP. Then, we will choose another primary node with the smallest level in AP to begin the above process. Note that several subtrees may be generated in this step. Finally, when AP is empty, all the schedule nodes in AS and the primary nodes in AP are included in these subtrees.Next, we will introduce the method to merge these subtrees.LetTR denote the set of roots of these subtrees and the source node s is also included in TR. The objective of this process is to merge all the subtrees into the tree which is rooted at s,i.e., Ts. Note that Ts may include only one node at the beginning. Delete s from TR. The merging process mainly works as follows.Case 1.
If there is a nodem in Ts and one of its schedule nodes,i.e., am, that can cover most root nodes in TR, then create an edge from m to am, and connect these root nodes in TR to schedule node am, which is shown in Figure 3(a). Delete these root nodes from TR.Figure 3
The example of the merging process. Figure3 is reproduced from Chen et al. (2018) (under the Creative Commons Attribution License/public domain).
(a) (b)Case 2.
Assumeu is the root node with the smallest level in TR. There must exists a neighbor of u (i.e., x∈NB(u)) in the original graph and the primary node x is not in Ts. But it can be reached by a primary node in Ts,i.e., m, just as the example shown in Figure 3(b). Let the schedule node of m which can reach x be am,i.e., x∈R(am). Create an edge from m to am and an edge from am to x. After that, let the schedule node of x that can reach u be ax, then create an edge from x to ax and an edge from ax to u. Let the subtree contains x be Tw; remove node x from Tw. Delete u from TR.The above process repeats until all the subtrees are added toTs either by Case 1 or Case 2. And then the pseudo broadcast tree is constructed completely. The correctness of this merging process can be verified by Theorem 10.Lemma 8.
Letl denote the level of node x in the auxiliary graph. If x is a primary node, then l is even, and if x is a schedule node, then l is odd.Proof.
First, we prove that ifx is a primary node, then l is even. It can be easily verified that there exists a level of schedule nodes between two contiguous level of primary nodes when conducting the breadth-first search initiated from the source node s. Since the level of the source node s is 0,i.e., L(s)=0 at the beginning, then all the schedule nodes of s must be level 1, and then the primary nodes reached by these schedule nodes have the level 2. Actually, let the hop-distance from a primary node u to node s in the original network be k, then we can find the level of the primary node u in the auxiliary graph must be 2k, which is even.
Second, since the schedule nodes can only be reached by its corresponding primary nodes, whose level is even, then the level of the schedule nodes must be odd.
Therefore, in the generated breadth-first tree, the level of the primary nodes is even and the level of the schedule nodes is odd.Lemma 9.
For any nodev in the subtree rooted at node u,i.e., Tu, we have L(v)≥L(u)-2.Proof.
First, we prove that, for any primary nodev in the subtree rooted at node u, we have L(v)≥L(u)-2. According to the construction of subtree, we can find that the root node u must be a primary node in Ap. Since one of its schedule nodes can reach a node whose level is less than u,i.e., w, then we can have L(w)=L(u)-2. Assume there exist a primary node,i.e., w, that L(w)<L(u)-2. Then there must exist a schedule node ax in AS that covers primary node w. According to Lemma 4, then we can have L(w)-1≤L(ax)≤L(w)+1, that is, L(ax)<L(u)-3. The level of the primary node of the schedule node ax,i.e.,x, can be calculated as L(x)=L(ax)+1, which is less than L(u)-2. Since ax is in AS, then we can also have x is in AP. However, when subtree Tu is constructed, primary node u has the smallest level, then we have L(x)≥L(u), which is a contradiction. Therefore, the level of all the primary nodes is no less than L(u)-2.
Second, since the level of the schedule nodes are larger than level of its primary nodes, thus, the level of all schedule nodes is also no less thanL(u)-2.
Therefore, for any nodev in the subtree rooted at node u, we have L(v)≥L(u)-2. The lemma is proved.Theorem 10.
For any subtree rooted at nodeu, it can be merged into Ts.Proof.
First, according to the merging process, if there exists a schedule nodeax, whose primary node is included in Ts and can reach node u, then the subtree rooted at node u will be merged into Ts as in Case 1.
Second, we will prove that if there does not exist such a schedule node, then there must exists a primary nodem as in the Case 2. Let the set of the primary nodes whose level is less than the one of u and can reach node u by some of their schedule nodes be Pup(u). Then, there must exist a primary node in Ts,i.e., m, whose level is less than the one of Pup(u), and can reach some node in Pup(u),i.e., x, by some of its schedule nodes. According to Lemma 9, the level of the primary nodes in Pup(u) is L(u)-2. Obviously, we can have L(m)=L(u)-4. Let the subtree contain node m be Tw. According to Lemma 9, then we can have L(w)≤L(m)+2≤L(u)-2. Since the primary node with the smallest level is u, then the subtree Tw and node m must have been included in Ts, which means the primary node m is existed.
Therefore, the subtrees exceptTs can be added to the primary subtree Ts either by Case 1 or Case 2. The theorem is proved.


### 4.4. Calculating the Broadcast Schedule

Actually, the pseudo broadcast tree constructed in the above subsection not only includes the information of the broadcast tree but also the scheduling information of nonleaf nodes. It can be transformed to the broadcast schedule (including a broadcast treeT and the transmitting schedules of nonleaf nodes) easily.First, the broadcast treeT can be obtained by removing all the schedule nodes and create an edge from its father to all of its child nodes in the generated pseudo broadcast tree Ts.Second, the transmitting schedules of nonleaf nodes inT,i.e., S(T) can be obtained according to the schedule nodes in the pseudo broadcast tree. That is, for each schedule node au in Ts, a transmitting schedule for node au.p,i.e., [au.p,au.t+χ∗W,ch(au)] is added in S(T), where ch(au) denotes the set of children of schedule node au in Ts, and χ is used for collisions avoiding [32, 33] and data freshness guaranteed during broadcasting, which can be just set as the level of node u in the new broadcast tree T.Now, the complete Approximate Minimum-Transmission Broadcasting (i.e., AMTB) algorithm for MTBDCA problem is introduced and the detailed procedure is shown in Algorithm 3.Algorithm 3:Approximate Minimum-Transmission Broadcasting.
Input: The duty-cycled network G and the source node s; Output: The broadcast schedule S; (1) Constructing the auxiliary graph G as in Section 4.1 by integrating nodes’ active time slot into the network; (2) Exploiting Algorithm 2 for the MSNC problem to obtain a minimum number of schedule nodes, i.e., AS, to cover all the primary nodes in the auxiliary graph G; (3)  Calculating a set of subtrees as in Section 4.3 with the scheduled nodes in AS to connect all the primary nodes in G; (4)  Merging all the subtrees into a pseudo broadcast tree which contains the scheduling information of all nodes, i.e., Ts; (5)  Transforming the pseudo broadcast tree Ts to a broadcast schedule, i.e., S=T,ST; (6) return The broadcast schedule S;


### 4.5. Performance Analysis of AMTB Algorithm

The correctness of AMTB is proved in Theorem11, where the proof can be found in the conference version [23].Theorem 11.
The broadcast schedule generated by AMTB is complete and correct.Theorem12 gives the lower bound of MTBDCA problem. The approximation ratio of AMTB is proved in Theorem 13 and the proof of this theorem is available in the conference version [23].Theorem 12.
The lower bound on the number of transmissions of any optimal broadcast schedule for MTBDCA is at leastAS/ln⁡(Δ+1), where AS denote the size of the obtained set of schedule nodes by Algorithm 1.Proof.
AssumeOPT is the size for any optimal schedule for MTBDCA problem. To finish the broadcasting process, all nodes except the source need receive the messages from some intermediate nodes. It means all the primary nodes in the auxiliary graph except the primary node of the source need to be covered at least once, then we can get OPT≥ASopt, where ASopt denote the size of any optimal schedule for MSNC problem. According to the above analysis, AS≤ASopt·ln⁡(Δ+1). Thence, we can get OPT≥ASopt≥AS/ln⁡(Δ+1). The theorem is proved.Theorem 13.
The approximation ratio of AMTB is at mostln⁡(Δ+1).Lemma 14.
The time complexity of Algorithm2 is at most O(n2).Proof.
Since there are at most(1+W)∗n schedule nodes in the auxiliary graph according to Lemma 8, then step (4) in Algorithm 2 takes at most O((1+W)∗n)=O(n) time (W is often a constant). And there are at most n-1 primary nodes need to be covered, then the step (3) to (8) takes at most O(n2) time. Thus, the time complexity of Algorithm 2 is O(n2).Theorem 15.
The time complexity of AMTB isO(n2).Proof.
First, according to Lemma8, it takes at most O(1+Δ)×n×W time to construct the auxiliary graph. Since Δ and W are often constant, then Algorithm 1 takes at most O(n) time.
Second, according to Lemma14, it needs at most O(n2) time to return a set of minimum schedule nodes for MSNC problem.
Third, to construct the pseudo broadcast tree, several subtrees are first generated and then these subtrees are merged into a single tree. Since there are at mostO(n) root nodes, and each subtree takes at most O(n) time, then it takes at most O(n2) time to generate the subtrees. To merge these subtrees, one need to choose a subtree to merged into Ts at each step, which takes at most O(n) time, and there are at most O(n) subtrees. Thus, it takes at most O(n2) time to merge the subtrees.
Finally, the broadcast schedule can be obtained by searching the broadcast tree, which takes at mostO(n) time.
Therefore, the time complexity of AMTB isO(n+n2+n2+n)=O(n2).


### 4.6. Discussion of Algorithms for All-to-All Broadcasting Problem

In the above subsections, the Minimum-Transmission Broadcasting problem with only one source node is investigated. Despite the one-to-all broadcasting problem, the all-to-all broadcasting problem is also very important in wireless networks [34], which is aimed at distributing the messages from all the nodes to all the other nodes. Similar as in [34], we assume the size of messages is unbounded. Then the above AMTB algorithm can still give an upper bound for the all-to-all MTBDCA problem. It mainly works as follows. First, all the messages are aggregated to a center node with the data aggregation technique in [17]. Second, the aggregated messages can be delivered to all the other nodes with the AMTB algorithm. The proposed algorithm can achieve an approximation ratio of ln⁡(Δ+1)+Δ, which is shown in Theorem 16. As for the more efficient algorithms for all-to-all MTBDCA problem, it will be investigated in our future work.Theorem 16.
The approximation ratio of the proposed algorithm for all-to-all MTBDCA problem isln⁡(Δ+1)+Δ.Proof.
LetOPTa and OPT1 be the number of transmissions of the optimal solution for the all-to-all and one-to-all MTBDCA problem, respectively. In the above algorithm for all-to-all MTBDCA problem, the data aggregation process takes at most n-1 transmissions, and the broadcasting process takes at most ln⁡(Δ+1)×OPT1 transmissions according to Theorem 13. Then the total number of transmissions is n-1+ln⁡(Δ+1)×OPT1. In addition, each node covers at most δ neighbors in the AMTB algorithm, then we can have OPT1×Δ≤n. Since OPTa must be larger than OPT1, then we can have (n-1+(Δ+1)×OPT1)/OPTa≤OPT1×Δ+ln⁡Δ+1×OPT1/OPT1≤ln⁡(Δ+1)+Δ. The theorem is proved.


## 4.1. Constructing an Auxiliary Graph

In order to integrate nodes’ working plan into the network and construct the broadcast tree, anAuxiliary Graph is first designed based on the duty-cycled network G. Different from the duty-cycled network, a new kind of node is introduced in the auxiliary graph,i.e.,Schedule Node. It is used to calculate the transmitting schedules for the nonleaf nodes.In this paper, letau denote a schedule node of u(u∈V) (For simplicity, node u is called the primary node of au). Each schedule has two properties,i.e., (au.p, au.t), where au.p denotes the schedule node’s primary node and au.t denotes its transmitting time slot. The auxiliary graph is defined as follows.Definition 3 (auxiliary graph).
Given a duty-cycled networkG=(V,E), the auxiliary graph G=(V′,E′) is a directed graph which contains nodes’ active time slots. The set V′ includes two kinds of nodes (primary node and schedule node) and E′ is the set of all edges. They are constructed as follows: (i)
Initially,V′=V, E′=∅.(ii)
For any nodeu∈V and time t′∈⋃v∈NB(u)W(v), we create a schedule node au,i(1≤i≤⋃v∈NBuWv). Its two properties are set as (u,t′) (i.e., au,i.p=u and au,i.t=t′). Let Υ(u) denote the set of u’s schedule nodes, and then V′=V′⋃u∈VΥ(u).(iii)
For any nodeu∈V and schedule node au,i∈Υ(u), create an edge from u to au,i. Let Eu′=(u,au,i)∣au,i∈Υ(u), then E′ can be updated as E′=⋃u∈VEu′.(iv)
Letv be a one-hop neighbors of u in G. For each schedule node au,i∈Υ(u), add an directed edge (au,i,v) in G if au,i.t∈W(v). Let R(au,i) denote the set of such node v. Actually, it denotes the nodes can be reached by au,i.p at time slot au,i.t. And we can have E′=E′⋃u∈V⋃au,i∈ΥuEau,i′, where Eau,i′=(au,i,v)∣v∈R(au,i).Note that, the auxiliary graph is directed, where the edges are either started from the primary nodeu to its schedule nodes in Υ(u), or started from a schedule node au,i to the primary nodes it can reach at time au,i.t,i.e., R(au,i). For example, there is a simple duty-cycled network in Figure 1(a) and the number in the braces denotes nodes’ working plan. According to Definition 3, its auxiliary graph is constructed as in Figure 1(b). As for node v, there are two neighbors and the union of the active time slots of these neighbors are 1,3,5. Then, three schedule nodes av,1, av,2 and av,3 are created, and their properties are set as (v,1),(v,3) and (v,5). As we can see time slot 1 is only included in the working plan of node u, then there is an edge from node v to av,1 and an edge from av,1 to node u. The pseudo code for constructing the auxiliary graph is shown in Algorithm 1.Algorithm 1:Algorithm for constructing the auxiliary graph.
Input: The duty-cycled network G=(V,E), and the source node s; Output: The auxiliary graph G=(V′,E′); (1)V′←V,E′←∅; (2) for∀u∈Vdo (3) S←⋃v∈NB(u)Wv; (4) i←1; (5) for∀t′∈Sdo (6) V′=V′∪au,i; (7) E′=E′∪u,au,i; (8) au,i.p←u,au,i.t←t′; (9) Rau,i←v∣v∈NB(u)&au,i.t∈W(v); (10) for∀v∈Rau,ido (11) E′=E′∪au,i,v; (12) end for (13) i←i+1; (14) end for (15) end for (16) returnG;Figure 1
An example of the auxiliary graph. Figure1 is reproduced from Chen et al. (2018) (under the Creative Commons Attribution License/public domain).
(a) (b)The size of the auxiliary graph is analyzed in Theorem5.Lemma 4.
Any schedule node in the auxiliary graphG can connect to at most Δ primary nodes.Proof.
According to Definition3, a schedule node au,i is connected to u’s neighboring nodes which have the active time slot au,i.t in its working plan. Obviously, there are at most Δ such nodes. Since the auxiliary graph is directed, thus, the schedule node au,i can connect to at most Δ primary nodes.Theorem 5.
The number of nodes and edges in the auxiliary graphG are at most (1+W)×n and (1+Δ)×n×W, respectively, where W denotes the length of a working period and n=V is the number of nodes of the original graph.Proof.
Firstly, according to Definition3, a schedule node is created for each primary node u and each time slot t∈⋃v∈NB(u)W(v). Since there are at most W time slots in ⋃v∈NB(u)W(v), then there are at most W schedule nodes for each primary node. Thus, the number of nodes in G can be calculated as(1)V′=V+Vs=n+∑u∈VW≤n+n×W≤1+W×nwhere Vs is the number of schedule nodes.
Secondly, for any primary nodeu, there is an edge between u and au,i(au,i∈Υ(u)) according to Definition 3, which is included in Eu′. And for any schedule node au,i, there are at most Δ edges from au,i to the primary nodes in R(au,i). Then, we can have(2)E′=∑u∈VEu′+⋃u∈V⋃au,i∈ΥuEau,i′≤∑u∈VΥu+∑u∈VΥu×Δ≤1+Δ×n×W


## 4.2. Minimum Schedule Node Covering Problem

In this subsection, we will introduce a new kind of problem,i.e.,Minimum Scheduling Node Covering problem. It tries to cover all the nonsource primary nodes in the auxiliary graph with minimum schedule nodes. The new problem can be defined as follows.Definition 6 (minimum schedule node covering problem (MSNC)).
Given a source nodes and an auxiliary graph G, the MSNC problem is objected to compute a set of schedule nodes,i.e., AS, which satisfies the following conditions: (1)
For each nodeu∈V&u≠s, there must exist a schedule node in AS,i.e., av, which satisfies that u∈R(av) (R(av) is the set of primary nodes which can be reached by av).(2)
The size ofAS,i.e., AS, is minimized.Theorem 7.
The MSNC problem is NP-hard and there exists no polynomial-time approximation algorithm with ratio of1-o1ln⁡Δ for MSNC unless NP⊆DTIME(nOlog⁡log⁡n).Proof.
We prove the NP-hardness of the MSNC problem by showing that the MSC problem can be mapped to one of its special cases. For example, Figure2(a) gives an example of MSC, in which U=d1,d2,…,dn is the universe of all n elements and set S=S1,S2,…,Sm denotes m subsets of U. An edge is created between di and Sk if di(1≤i≤n)∈Sk(1≤k≤m). The MSC problem is then to calculate a set of minimum nodes from S to cover all the nodes in U.
To prove the NP-hardness of MSNC, a simple graph with a source nodes and its neighboring nodes di(1≤i≤n) is constructed. The working plan of each node is set as follows: (1) Initially, the working schedule of di(1≤i≤n) is set null; (2) If di(1≤i≤n)∈Sk(1≤k≤m), then W(di)=W(di)∪k. Then, the corresponding auxiliary graph is shown in Figure 2(b), where Sk(1≤k≤m) denote the schedule nodes. Then the MSNC problem is equivalent to the MSC problem, which is proved to NP-hard. The theorem is proved.Figure 2
The example of MSNC problem. Figure2 is reproduced from Chen et al. (2018) (under the Creative Commons Attribution License/public domain).
(a)
The MSC problem (b)
The MSNC problemTo solve the MSNC problem, we exploit the greedy set covering method [31] and choose the schedule node iteratively. Initially, AS is set ∅ and Vp is set V-s. In each loop, the schedule node which has maximum adjacent uncovered primary nodes,i.e., av=argmaxau∈Vs⁡Rau∩Vp, is found. Then, the schedule node av is added to AS, i.e., AS=AS∪{av}, and the covered primary nodes are removed from Vp. This process repeats until there are no uncovered primary nodes in Vp. The detailed procedure is shown in Algorithm 2. Since a schedule node can connect to at most Δ primary nodes, then Algorithm 2 can have an approximation ratio of ln⁡(Δ+1) [31].Algorithm 2:Approximate algorithm for MSNC problem.
Input: The auxiliary graph G, and the source node s; Output: The set of schedule nodes AS; (1) Vp←V-s,AS←∅; (2) Vs← all the schedule nodes in G; (3) whileVp≠∅do (4) av=argmaxau∈Vs⁡Rau∩Vp; (5) AS←AS∪{av}; (6) Vp←Vp-Rav∩Vp; (7) Vs←Vs-av; (8) end while (9) returnAS;


## 4.3. Generating the Pseudo Broadcast Tree

After obtaining the set of schedule nodesAS, aPseudo Broadcast Tree in the auxiliary graph is then constructed to connect all schedule nodes in AS and these schedule nodes’ primary nodes. The pseudo broadcast tree is mainly constructed by two steps: (1) The schedule nodes in AS and their primary nodes are first organized into several subtrees; (2) These subtrees are then merged into one primary tree.AssumeL(v) is the level of each node v (including the primary nodes and schedule nodes in the auxiliary graph). The above step (1) works as follows.Initially, the level of source nodes is set 0,i.e., L(s)=0. Then, a breadth-first search is conducted from s level by level.Second, letAP=av.p∣av∈AS denote the set of primary nodes whose schedule nodes is in AS. If s is not included in AP, add s into AP,i.e., AP=AP∪s.Third, letu be the primary node with the smallest level in AP and Tu denote the subtree rooted at u. Add u into Tu at the beginning,i.e., Tu=Tu∪u. Then we can construct Tu by the following:(1)
For any primary nodem in Tu∩AP, let AS(m)=av∣av∈AS&av.p=m be the set of schedule nodes which are contained in AS and their primary node is m.(2)
For any schedule nodeam∈AS(m), add it into the subtree Tu,i.e., Tu=Tu∪am and create an edge from m to schedule node am. Let n be a primary node in R(am) and not included in any subtrees, add it into subtree Tu,i.e., Tu=Tu∪n and create an edge from schedule node av to n.(3)
Delete the primary nodem from AP,i.e., AP=AP-{m}.The above three steps repeat until there are no nodes inTu∩AP. Then, we will choose another primary node with the smallest level in AP to begin the above process. Note that several subtrees may be generated in this step. Finally, when AP is empty, all the schedule nodes in AS and the primary nodes in AP are included in these subtrees.Next, we will introduce the method to merge these subtrees.LetTR denote the set of roots of these subtrees and the source node s is also included in TR. The objective of this process is to merge all the subtrees into the tree which is rooted at s,i.e., Ts. Note that Ts may include only one node at the beginning. Delete s from TR. The merging process mainly works as follows.Case 1.
If there is a nodem in Ts and one of its schedule nodes,i.e., am, that can cover most root nodes in TR, then create an edge from m to am, and connect these root nodes in TR to schedule node am, which is shown in Figure 3(a). Delete these root nodes from TR.Figure 3
The example of the merging process. Figure3 is reproduced from Chen et al. (2018) (under the Creative Commons Attribution License/public domain).
(a) (b)Case 2.
Assumeu is the root node with the smallest level in TR. There must exists a neighbor of u (i.e., x∈NB(u)) in the original graph and the primary node x is not in Ts. But it can be reached by a primary node in Ts,i.e., m, just as the example shown in Figure 3(b). Let the schedule node of m which can reach x be am,i.e., x∈R(am). Create an edge from m to am and an edge from am to x. After that, let the schedule node of x that can reach u be ax, then create an edge from x to ax and an edge from ax to u. Let the subtree contains x be Tw; remove node x from Tw. Delete u from TR.The above process repeats until all the subtrees are added toTs either by Case 1 or Case 2. And then the pseudo broadcast tree is constructed completely. The correctness of this merging process can be verified by Theorem 10.Lemma 8.
Letl denote the level of node x in the auxiliary graph. If x is a primary node, then l is even, and if x is a schedule node, then l is odd.Proof.
First, we prove that ifx is a primary node, then l is even. It can be easily verified that there exists a level of schedule nodes between two contiguous level of primary nodes when conducting the breadth-first search initiated from the source node s. Since the level of the source node s is 0,i.e., L(s)=0 at the beginning, then all the schedule nodes of s must be level 1, and then the primary nodes reached by these schedule nodes have the level 2. Actually, let the hop-distance from a primary node u to node s in the original network be k, then we can find the level of the primary node u in the auxiliary graph must be 2k, which is even.
Second, since the schedule nodes can only be reached by its corresponding primary nodes, whose level is even, then the level of the schedule nodes must be odd.
Therefore, in the generated breadth-first tree, the level of the primary nodes is even and the level of the schedule nodes is odd.Lemma 9.
For any nodev in the subtree rooted at node u,i.e., Tu, we have L(v)≥L(u)-2.Proof.
First, we prove that, for any primary nodev in the subtree rooted at node u, we have L(v)≥L(u)-2. According to the construction of subtree, we can find that the root node u must be a primary node in Ap. Since one of its schedule nodes can reach a node whose level is less than u,i.e., w, then we can have L(w)=L(u)-2. Assume there exist a primary node,i.e., w, that L(w)<L(u)-2. Then there must exist a schedule node ax in AS that covers primary node w. According to Lemma 4, then we can have L(w)-1≤L(ax)≤L(w)+1, that is, L(ax)<L(u)-3. The level of the primary node of the schedule node ax,i.e.,x, can be calculated as L(x)=L(ax)+1, which is less than L(u)-2. Since ax is in AS, then we can also have x is in AP. However, when subtree Tu is constructed, primary node u has the smallest level, then we have L(x)≥L(u), which is a contradiction. Therefore, the level of all the primary nodes is no less than L(u)-2.
Second, since the level of the schedule nodes are larger than level of its primary nodes, thus, the level of all schedule nodes is also no less thanL(u)-2.
Therefore, for any nodev in the subtree rooted at node u, we have L(v)≥L(u)-2. The lemma is proved.Theorem 10.
For any subtree rooted at nodeu, it can be merged into Ts.Proof.
First, according to the merging process, if there exists a schedule nodeax, whose primary node is included in Ts and can reach node u, then the subtree rooted at node u will be merged into Ts as in Case 1.
Second, we will prove that if there does not exist such a schedule node, then there must exists a primary nodem as in the Case 2. Let the set of the primary nodes whose level is less than the one of u and can reach node u by some of their schedule nodes be Pup(u). Then, there must exist a primary node in Ts,i.e., m, whose level is less than the one of Pup(u), and can reach some node in Pup(u),i.e., x, by some of its schedule nodes. According to Lemma 9, the level of the primary nodes in Pup(u) is L(u)-2. Obviously, we can have L(m)=L(u)-4. Let the subtree contain node m be Tw. According to Lemma 9, then we can have L(w)≤L(m)+2≤L(u)-2. Since the primary node with the smallest level is u, then the subtree Tw and node m must have been included in Ts, which means the primary node m is existed.
Therefore, the subtrees exceptTs can be added to the primary subtree Ts either by Case 1 or Case 2. The theorem is proved.


## 4.4. Calculating the Broadcast Schedule

Actually, the pseudo broadcast tree constructed in the above subsection not only includes the information of the broadcast tree but also the scheduling information of nonleaf nodes. It can be transformed to the broadcast schedule (including a broadcast treeT and the transmitting schedules of nonleaf nodes) easily.First, the broadcast treeT can be obtained by removing all the schedule nodes and create an edge from its father to all of its child nodes in the generated pseudo broadcast tree Ts.Second, the transmitting schedules of nonleaf nodes inT,i.e., S(T) can be obtained according to the schedule nodes in the pseudo broadcast tree. That is, for each schedule node au in Ts, a transmitting schedule for node au.p,i.e., [au.p,au.t+χ∗W,ch(au)] is added in S(T), where ch(au) denotes the set of children of schedule node au in Ts, and χ is used for collisions avoiding [32, 33] and data freshness guaranteed during broadcasting, which can be just set as the level of node u in the new broadcast tree T.Now, the complete Approximate Minimum-Transmission Broadcasting (i.e., AMTB) algorithm for MTBDCA problem is introduced and the detailed procedure is shown in Algorithm 3.Algorithm 3:Approximate Minimum-Transmission Broadcasting.
Input: The duty-cycled network G and the source node s; Output: The broadcast schedule S; (1) Constructing the auxiliary graph G as in Section 4.1 by integrating nodes’ active time slot into the network; (2) Exploiting Algorithm 2 for the MSNC problem to obtain a minimum number of schedule nodes, i.e., AS, to cover all the primary nodes in the auxiliary graph G; (3)  Calculating a set of subtrees as in Section 4.3 with the scheduled nodes in AS to connect all the primary nodes in G; (4)  Merging all the subtrees into a pseudo broadcast tree which contains the scheduling information of all nodes, i.e., Ts; (5)  Transforming the pseudo broadcast tree Ts to a broadcast schedule, i.e., S=T,ST; (6) return The broadcast schedule S;


## 4.5. Performance Analysis of AMTB Algorithm

The correctness of AMTB is proved in Theorem11, where the proof can be found in the conference version [23].Theorem 11.
The broadcast schedule generated by AMTB is complete and correct.Theorem12 gives the lower bound of MTBDCA problem. The approximation ratio of AMTB is proved in Theorem 13 and the proof of this theorem is available in the conference version [23].Theorem 12.
The lower bound on the number of transmissions of any optimal broadcast schedule for MTBDCA is at leastAS/ln⁡(Δ+1), where AS denote the size of the obtained set of schedule nodes by Algorithm 1.Proof.
AssumeOPT is the size for any optimal schedule for MTBDCA problem. To finish the broadcasting process, all nodes except the source need receive the messages from some intermediate nodes. It means all the primary nodes in the auxiliary graph except the primary node of the source need to be covered at least once, then we can get OPT≥ASopt, where ASopt denote the size of any optimal schedule for MSNC problem. According to the above analysis, AS≤ASopt·ln⁡(Δ+1). Thence, we can get OPT≥ASopt≥AS/ln⁡(Δ+1). The theorem is proved.Theorem 13.
The approximation ratio of AMTB is at mostln⁡(Δ+1).Lemma 14.
The time complexity of Algorithm2 is at most O(n2).Proof.
Since there are at most(1+W)∗n schedule nodes in the auxiliary graph according to Lemma 8, then step (4) in Algorithm 2 takes at most O((1+W)∗n)=O(n) time (W is often a constant). And there are at most n-1 primary nodes need to be covered, then the step (3) to (8) takes at most O(n2) time. Thus, the time complexity of Algorithm 2 is O(n2).Theorem 15.
The time complexity of AMTB isO(n2).Proof.
First, according to Lemma8, it takes at most O(1+Δ)×n×W time to construct the auxiliary graph. Since Δ and W are often constant, then Algorithm 1 takes at most O(n) time.
Second, according to Lemma14, it needs at most O(n2) time to return a set of minimum schedule nodes for MSNC problem.
Third, to construct the pseudo broadcast tree, several subtrees are first generated and then these subtrees are merged into a single tree. Since there are at mostO(n) root nodes, and each subtree takes at most O(n) time, then it takes at most O(n2) time to generate the subtrees. To merge these subtrees, one need to choose a subtree to merged into Ts at each step, which takes at most O(n) time, and there are at most O(n) subtrees. Thus, it takes at most O(n2) time to merge the subtrees.
Finally, the broadcast schedule can be obtained by searching the broadcast tree, which takes at mostO(n) time.
Therefore, the time complexity of AMTB isO(n+n2+n2+n)=O(n2).


## 4.6. Discussion of Algorithms for All-to-All Broadcasting Problem

In the above subsections, the Minimum-Transmission Broadcasting problem with only one source node is investigated. Despite the one-to-all broadcasting problem, the all-to-all broadcasting problem is also very important in wireless networks [34], which is aimed at distributing the messages from all the nodes to all the other nodes. Similar as in [34], we assume the size of messages is unbounded. Then the above AMTB algorithm can still give an upper bound for the all-to-all MTBDCA problem. It mainly works as follows. First, all the messages are aggregated to a center node with the data aggregation technique in [17]. Second, the aggregated messages can be delivered to all the other nodes with the AMTB algorithm. The proposed algorithm can achieve an approximation ratio of ln⁡(Δ+1)+Δ, which is shown in Theorem 16. As for the more efficient algorithms for all-to-all MTBDCA problem, it will be investigated in our future work.Theorem 16.
The approximation ratio of the proposed algorithm for all-to-all MTBDCA problem isln⁡(Δ+1)+Δ.Proof.
LetOPTa and OPT1 be the number of transmissions of the optimal solution for the all-to-all and one-to-all MTBDCA problem, respectively. In the above algorithm for all-to-all MTBDCA problem, the data aggregation process takes at most n-1 transmissions, and the broadcasting process takes at most ln⁡(Δ+1)×OPT1 transmissions according to Theorem 13. Then the total number of transmissions is n-1+ln⁡(Δ+1)×OPT1. In addition, each node covers at most δ neighbors in the AMTB algorithm, then we can have OPT1×Δ≤n. Since OPTa must be larger than OPT1, then we can have (n-1+(Δ+1)×OPT1)/OPTa≤OPT1×Δ+ln⁡Δ+1×OPT1/OPT1≤ln⁡(Δ+1)+Δ. The theorem is proved.


## 5. Simulation Results

In this section, we will evaluate the performance of AMTB through extensive simulations. In the experiments, AMTB is mainly compared with the following algorithms.First, the existing algorithms designed for MTB problem in duty-cycled networks, including the classical one,i.e., CSCA [18] and the recently proposed one,i.e., BRMS [21], are both evaluated to demonstrate that the AMTB algorithm can benefit from scheduling with nodes’ all active time slots.Second, two baseline algorithms,i.e., CDS-based (Connected Dominate Set) algorithm and SPT-based (Shortest Path Tree) algorithm, are also implemented. In such two algorithms, a CDS-based and SPT-based broadcast tree is constructed firstly. Then, to reduce the number of transmissions, we calculate the transmitting schedules of all forwarding nodes in the broadcast tree optimally by enumerating all the possible results.In the simulations, we mainly focus on the performance of the number of transmissions of each algorithm under various network topologies. Similar as in [30], the Networkx [35] tool was used to test more complex networks and generate different network topologies, where the number of sensor nodes is set from 100 to 400. The duty cycle of each node is set from 10% to 35% and the nodes’ working plan is generated randomly to satisfy a wide range of configurations. In all the simulation results, each plotted point represents the average of 100 executions.


### 5.1. Impact ofW

First, the performance of each algorithm under different length of working cycle (i.e., W) and number of nodes (i.e., N) is evaluated. In this group of experiments, the duty cycle is set 20% and the average number of neighbors of each node is set 5.Figure4 shows the number of transmissions of each algorithm when we vary the length of working cycle under different network size. The number of nodes in Figures 4(a), 4(b), 4(c), and 4(d) is set as 100, 200, 300, and 400, respectively. In all scenarios, the number of transmissions of AMTB is much less than the one of other algorithms. Compared to the recently proposed BRMS algorithm, the number of transmissions of AMTB is decreased by 50% on average. This is mainly due to AMTB can exploit the whole active time slots among all neighbors for scheduling to reduce the number of transmissions. Additionally, although the CDS-based and SPT-based methods consider multiple active time slots during scheduling, they perform even worse than BRMS. This demonstrates that the performance can be still be worse even exploiting the optimal scheduling method if the broadcasting tree is not constructed well. Thus one must choose the forwarding nodes carefully when constructing the broadcasting tree.Figure 4
The number of transmissions when duty cycle is set 20%. Figure4 is reproduced from Chen et al. (2018) (under the Creative Commons Attribution License/public domain).
(a)
n = 100 (b)
n = 200 (c)
n = 300 (d)
n = 400Another finding is that when the length of working cycle is increased and the duty cycle remains unchanged, the number of transmissions of BRMS and CSCA method is even more, while the one of the algorithms exploiting multiple active slots for scheduling,i.e., AMTB, SPT-based, and CDS-based method, is reduced. This is due to CSCA and BRMS methods only exploit nodes’ first active time slot for scheduling. However, the number of neighbors who shares the same active time slot may be reduced when W is increased. Actually, the number of active time slots in nodes’ working plan is increased, and AMTB, SPT-based and CDS-based method can benefit from the increased active time slots to reduce the number of transmissions.


### 5.2. Impact ofDuty Cycle

In this simulation, the performance of each algorithm under different duty cycle is compared. The length of nodes’ working cycle is equal to20.Figure5 shows the number of transmissions of each algorithm under different duty cycle. The number of nodes is set from 100 to 400, and the results are shown in Figures 5(a), 5(b), 5(c), and 5(d). As we can see, AMTB perform much better than all the other methods in all scenarios, which demonstrates its efficiency for MTBDCA problem. The SPT-based method still performs much worse than the others. This demonstrates that the SPT-based method may be not suitable for MTB problem in duty-cycled WSNs.Figure 5
The number of transmissions whenW is set 20.
(a)
n = 100 (b)
n = 200 (c)
n = 300 (d)
n = 400Another finding is that both the number of transmissions of the existing methods (BRMS and CSCA) and the one of AMTB is improved when we increase the duty cycle. This is because the probability of the first active time slot of neighbors being the same is increased when the duty cycle is increased (which means the size of node’s working plan is increased). Note that, if we further increase the duty cycle, the number of transmissions of each method will still be decreased until the duty cycle is increased to 1. In this case, the MTBDCA problem is equal to the MTB problem in the traditional WSNs, and the number of transmissions of each method will be steadily.


### 5.3. Impact of Neighbors

Finally, we exploit Networkx to investigate the relationship between the number of transmissions of each method and the average number of neighbors,i.e.,ψ. To compare, the number of nodes is set 200 and the average number of neighbors is set 5 and 10 in two group of experiments.Figure6 presents the number of transmissions of the above algorithms under different length of working cycle, where the duty cycle is set 20%. Firstly, as we can see in Figures 6(a) and 6(b), the number of transmissions of each method is decreased notably if we increase the average number of neighbors in the network from 5 to 10. Although the total number of nodes in the network is unchanged, the nodes sharing the same active time slot is increased when the number of neighbors is increased. As a result, the required number of transmissions is reduced. Compared to other methods, the proposed AMTB algorithm can reduce the number of transmissions by 40%, which demonstrates the efficiency of the proposed method. Similar to Figure 4, the number of transmissions of BRMS and CSCA are both increased when the length of working cycle is increased since they only exploit nodes’ first active time slot for scheduling.Figure 6
Performance analysis under differentW.
(a)
ψ = 5 (b)
ψ = 10Figure7 compares the number of transmissions of each method when we set n=200 and ψ=10 and change the duty cycle. In this case, the trend of each method is similar as in Figure 5,i.e., the number of transmissions of each method is decreased when the duty cycle is increased. And the number of transmissions of AMTB is much less than the one of other methods. Comparing Figure 7(a) with Figure 7(b), the number of transmissions of each method is decreased notably (almost 50%) when the average number of neighbors is increased. This demonstrates that the number of transmissions is also highly related to the average degree in the network.Figure 7
Performance analysis under differentDuty Cycle.
(a)
ψ = 5 (b)
ψ = 10


## 5.1. Impact ofW

First, the performance of each algorithm under different length of working cycle (i.e., W) and number of nodes (i.e., N) is evaluated. In this group of experiments, the duty cycle is set 20% and the average number of neighbors of each node is set 5.Figure4 shows the number of transmissions of each algorithm when we vary the length of working cycle under different network size. The number of nodes in Figures 4(a), 4(b), 4(c), and 4(d) is set as 100, 200, 300, and 400, respectively. In all scenarios, the number of transmissions of AMTB is much less than the one of other algorithms. Compared to the recently proposed BRMS algorithm, the number of transmissions of AMTB is decreased by 50% on average. This is mainly due to AMTB can exploit the whole active time slots among all neighbors for scheduling to reduce the number of transmissions. Additionally, although the CDS-based and SPT-based methods consider multiple active time slots during scheduling, they perform even worse than BRMS. This demonstrates that the performance can be still be worse even exploiting the optimal scheduling method if the broadcasting tree is not constructed well. Thus one must choose the forwarding nodes carefully when constructing the broadcasting tree.Figure 4
The number of transmissions when duty cycle is set 20%. Figure4 is reproduced from Chen et al. (2018) (under the Creative Commons Attribution License/public domain).
(a)
n = 100 (b)
n = 200 (c)
n = 300 (d)
n = 400Another finding is that when the length of working cycle is increased and the duty cycle remains unchanged, the number of transmissions of BRMS and CSCA method is even more, while the one of the algorithms exploiting multiple active slots for scheduling,i.e., AMTB, SPT-based, and CDS-based method, is reduced. This is due to CSCA and BRMS methods only exploit nodes’ first active time slot for scheduling. However, the number of neighbors who shares the same active time slot may be reduced when W is increased. Actually, the number of active time slots in nodes’ working plan is increased, and AMTB, SPT-based and CDS-based method can benefit from the increased active time slots to reduce the number of transmissions.


## 5.2. Impact ofDuty Cycle

In this simulation, the performance of each algorithm under different duty cycle is compared. The length of nodes’ working cycle is equal to20.Figure5 shows the number of transmissions of each algorithm under different duty cycle. The number of nodes is set from 100 to 400, and the results are shown in Figures 5(a), 5(b), 5(c), and 5(d). As we can see, AMTB perform much better than all the other methods in all scenarios, which demonstrates its efficiency for MTBDCA problem. The SPT-based method still performs much worse than the others. This demonstrates that the SPT-based method may be not suitable for MTB problem in duty-cycled WSNs.Figure 5
The number of transmissions whenW is set 20.
(a)
n = 100 (b)
n = 200 (c)
n = 300 (d)
n = 400Another finding is that both the number of transmissions of the existing methods (BRMS and CSCA) and the one of AMTB is improved when we increase the duty cycle. This is because the probability of the first active time slot of neighbors being the same is increased when the duty cycle is increased (which means the size of node’s working plan is increased). Note that, if we further increase the duty cycle, the number of transmissions of each method will still be decreased until the duty cycle is increased to 1. In this case, the MTBDCA problem is equal to the MTB problem in the traditional WSNs, and the number of transmissions of each method will be steadily.


## 5.3. Impact of Neighbors

Finally, we exploit Networkx to investigate the relationship between the number of transmissions of each method and the average number of neighbors,i.e.,ψ. To compare, the number of nodes is set 200 and the average number of neighbors is set 5 and 10 in two group of experiments.Figure6 presents the number of transmissions of the above algorithms under different length of working cycle, where the duty cycle is set 20%. Firstly, as we can see in Figures 6(a) and 6(b), the number of transmissions of each method is decreased notably if we increase the average number of neighbors in the network from 5 to 10. Although the total number of nodes in the network is unchanged, the nodes sharing the same active time slot is increased when the number of neighbors is increased. As a result, the required number of transmissions is reduced. Compared to other methods, the proposed AMTB algorithm can reduce the number of transmissions by 40%, which demonstrates the efficiency of the proposed method. Similar to Figure 4, the number of transmissions of BRMS and CSCA are both increased when the length of working cycle is increased since they only exploit nodes’ first active time slot for scheduling.Figure 6
Performance analysis under differentW.
(a)
ψ = 5 (b)
ψ = 10Figure7 compares the number of transmissions of each method when we set n=200 and ψ=10 and change the duty cycle. In this case, the trend of each method is similar as in Figure 5,i.e., the number of transmissions of each method is decreased when the duty cycle is increased. And the number of transmissions of AMTB is much less than the one of other methods. Comparing Figure 7(a) with Figure 7(b), the number of transmissions of each method is decreased notably (almost 50%) when the average number of neighbors is increased. This demonstrates that the number of transmissions is also highly related to the average degree in the network.Figure 7
Performance analysis under differentDuty Cycle.
(a)
ψ = 5 (b)
ψ = 10


## 6. Conclusion and Future Work

In this paper, the MTBDCA problem in duty-cycled wireless networks is investigated. It is proved to be NP-hard ando(ln⁡Δ)-inapproximable, where Δ denotes the maximum degree in the network. An auxiliary graph and the minimum schedule node covering problem is proposed to exploit nodes’ all active time slots for scheduling. Based on this, a ln⁡(Δ+1)-approximation algorithm is proposed for MTBDCA. The efficiency of the proposed algorithm is demonstrated by extensive simulations.As for the future work, we will further investigate the all-to-all MTBDCA problem, including providing a more efficient algorithm for the all-to-all MTBDCA problem and studying the tight approximation ratio of the proposed methods. The simulations will also be conducted to demonstrate the efficiency of the proposed algorithms.



---

*Source: 5064109-2019-02-06.xml*