The zigbee network characterized low data rate and low cost
IEEE TRANSACTIONS ON MOBILE COMPUTING,  VOL. 5,  NO. 11, 

1561 

TreeBased Data Broadcast in
Index Terms—Broadcast, IEEE 802.15.4, ZigBee, ad hoc network.
Ç
working together to enable reliable, costeffective, low
power, wirelessly networked monitoring and control
still at its early stage [4], [5], partly because the ZigBee
specifications were not publicly available until June 2005
. G. Ding is with the School of Electrical and Computer Engineering, Purdue University, W. Lafayette, IN 47907.
Email: dingg@ecn.purdue.edu.
For information on obtaining reprints of this article, please send email to: tmc@computer.org, and reference IEEECS Log Number TMC03191104.
15361233/06/$20.00 � 2006 IEEE
1562  IEEE TRANSACTIONS ON MOBILE COMPUTING,  VOL. 5,  NO. 11,  NOVEMBER 2006 

Fig. 1. ZigBee protocol stack.
rebroadcast, while every node in the network is still able to receive the packet. In the first algorithm, a node decides by itself whether it should rebroadcast or not; it need not rebroadcast if a certain subset of its 1hop neighbors have already received the packet. In the latter algorithm, a node selects a subset of its 1hop neighbors, called forward nodes, for forwarding, so as to cover all its 2hop tree neighbors. It is proven that the proposed algorithm is of polynomial computation complexity and memory complexity, and it provides an optimal solution of selecting the minimum number of forward nodes. In contrast, for general ad hoc networks, this optimum problem is NPhard so that it cannot be solved by any known algorithms of polynomial complexity.



once. To reduce the broadcast redundancy and avoid collisions during rebroadcasting, they introduced some simple algorithms. For example, the counter based algorithm rebroadcasts a packet only if the number of duplicated broadcast packets received during a waiting period is less than a threshold. The locationbased approach only rebroadcasts when the additional coverage by the rebroadcast is larger than a threshold. In [9], the authors improved the above algorithms by adaptively choosing the threshold as a function of the number of neighbors. Both simulation comparison [10] and theoretical analysis [11] have been conducted. These approaches are simple to implement, but they cannot guarantee coverage of the whole network [10].
More complicated algorithms assume the knowledge of network topology in order to guarantee network coverage and reduce broadcast redundancy. When the global network information is available, the problem of selecting the minimum number of forward nodes is essentially the wellstudied set cover problem, which is NPhard [12]. But, its solution can be approximated by a greedy algorithm [13] with an approximation factor of logðnÞ, where n is the maximum number of neighbors. Since global network topology is not practically available, localized algorithms which only need the information of 1hop and 2hop
DING ET AL.: TREEBASED DATA BROADCAST IN IEEE 802.15.4 AND ZIGBEE NETWORKS  TABLE 1  1563 

Notations 
Research on energy efficient broadcast protocols is usually coupled with topology control, which tries to maintain a connected network topology with the minimum total transmission power [21]. But, finding a minimum energy broadcast tree is NPhard [22]. Many heuristic protocols have been introduced [23], which can approximate the optimal solution with a constant factor when the
global network information is available. Some localized rebroadcast.
protocols have recently been proposed [24], but they need location or distance information and introduce extra communication overhead to exchange such information
.  The distance between nodes and the position of 


. 


The transmission power of nodes is fixed and the  
.  
The network topology is not necessarily modeled as  
.  a unit disk graph. But, the symmetry of neighbor  


hood is assumed. That is, if A is a neighbor of B,  


Addresses are hierarchically assigned. Hence, given 
information exchange. neighbors in TNðNðvÞÞ.
1564  IEEE TRANSACTIONS ON MOBILE COMPUTING,  VOL. 5,  NO. 11,  NOVEMBER 2006 

Theorem 1. When every node in a ZigBee network runs the OSR algorithm, a broadcast packet from any source can reach all the other nodes, provided the network is physically connected.
4 ZIGBEE ONTREE SELECTION ALGORITHM

tu 


DING ET AL.: TREEBASED DATA BROADCAST IN IEEE 802.15.4 AND ZIGBEE NETWORKS  1565 

Fig. 4. The optimal ontree forward node selection algorithm. given in Theorem 2.
Theorem 2. For a node v, the OOS algorithm finds a minimum
Proof. See Appendix B. tu 4.2 ZigBee OnTree Selection Algorithm
The OOS algorithm assumes that the construction and traversing of a tree does not introduce any extra cost. When implementing the algorithm in the real system, however, this assumption is not practical because a ZigBee device usually has very limited memory and computation capacity. Since a large part of the memory has already been used by the routing table and neighbor table, it may not even have enough space to store the whole forest or even a tree of OðnnmÞ nodes. It needs considerable computation capacity to generate, merge, and delete nodes on the tree. Even if a tree is constructed, it requires extra effort to sort and traverse it level by level.
1566  IEEE TRANSACTIONS ON MOBILE COMPUTING,  VOL. 5,  NO. 11,  NOVEMBER 2006 

Fig. 6. The ZigBee ontree forward node selection algorithm.
way. Basically, the OOS works on both S and C with size OðnÞ and OðnnmÞ, respectively, while the ZOS only works on S, which is stored in the existing neighbor table. Since C just contains the tree neighbors of set S, it can be easily derived from S whenever needed. A small memory of size M is required to temporarily store nodes at a level in C. The ZOS algorithm is explained in Fig. 6.
Theorem 3. Given an arbitrary broadcast source, if the source and every forward node uses the ZOS algorithm to select its own forward nodes and rebroadcasts the packet once, every nonforward node drops the packet and never rebroadcasts even if it is selected as a forward node later, the whole network is guaranteed to be covered, and the broadcast process will automatically stop when all nodes are marked as either forward node or nonforward node. This process takes at most 2dm steps.
DING ET AL.: TREEBASED DATA BROADCAST IN IEEE 802.15.4 AND ZIGBEE NETWORKS  1567  

tu  
The selfpruning technique introduced in the previous section can be integrated into the above forward node selection algorithm, but a forward node needs to ensure that all its 1hop neighbors, instead of 1hop tree neighbors, have been covered before it stops rebroadcasting. We omit
each broadcast; therefore, the resultant coverage time is only used for comparison.
1.  


2. 


3. 


generator. We assume an ideal case when there is no packet loss in MAC and the physical layer. The reliability
4. 

1. the SBA algorithm [15], in which a node is self pruned only if all its physical 1hop neighbors are covered,
2. the AHBP algorithm [17], in which a greedy algorithm is employed to select a forward node3. from NðvÞ to cover TNðNðvÞÞ, the ZigBee broadcast algorithm currently used by the ZigBee specification, in which only tree neigh bors rebroadcast, and
4. the Global algorithm, in which a greedy algorithm is applied to the whole network, assuming the global network topology is known.For the number of duplicated packets received by each node shown in Fig. 10, similar conclusions to the number of rebroadcast nodes can be drawn. In contrast to less than two duplicated packets by the Global algorithm, all the other localized algorithms introduce significant broadcast redundancy, which increases with respect to the network size. Basically, the number of duplicated packets is determined by both the number of rebroadcast nodes and the number of neighbors covered by each broadcast. When the transmission range is fixed and the nodes are uniformly distributed, the number of duplicated packets is approximately proportional to the number of rebroadcast nodes.
For the coverage time displayed in Fig. 11, the ZigBee broadcast algorithm takes the longest time because only tree neighbors respond to each broadcast while all the other neighbors drop the packet even if they can successfully receive it. The Global algorithm offers the fastest coverage because all of the globally selected forward nodes start broadcasting after a random waiting period and there are no further rebroadcasts. The selfpruning algorithms SBA and OSR cover the whole network a little faster than the forward node selection algorithms AHBP and ZOS. It is also observed that their coverage time converges to that of the Global algorithm when the network size increases.
1568  IEEE TRANSACTIONS ON MOBILE COMPUTING,  VOL. 5,  NO. 11,  NOVEMBER 2006 

For the number of rebroadcast nodes shown in Figs. 9 and 12, it is observed that the performance of the ZOS algorithm is significantly increased when the transmission radius increases, while the performance of the OSR algorithm does not change much. This is because, when the transmission range increases, a node covers more neighbors and there is a better chance that all of the tree neighbors of a node already exist in the neighborhood. Hence, this node does not need to be selected as a forward node by the ZOS algorithm. The OSR algorithm always waits for the coverage of all its tree neighbors, which is not significantly affected by the transmission range.
coverage than the forward node selection algorithms AHBP and ZOS. This is due to the fact that, in the forward node selection algorithms, nodes far away from the source in the logical topology cannot receive the broadcast packet faster even if they become physically closer to the source when the transmission range increases. However, when the transmission range is increased to 55m, the forward node selection algorithms cover the whole network faster because the nodes are no longer far away from the source. It is also observed that the coverage time converges to that of the global algorithm when the transmission range increases.
5.2  

In the above scenarios, we tested ZigBee networks of up to 300 nodes. A ZigBee network can actually support more
DING ET AL.: TREEBASED DATA BROADCAST IN IEEE 802.15.4 AND ZIGBEE NETWORKS  1569 

times of algorithms SBA, OSR, AHBP, and ZOS all converge to that of the Global algorithm when the network size is increasing. This phenomenon is similar to the last scenario when the transmission range increases. It is because, in the same area, when the total number of nodes increases, the density of neighborhood increases correspondingly, so that a transmission will cover more nodes.

5.3 

According to the above results, the proposed ZOS algorithm outperforms the OSR algorithm in general. However, it should be noted that the forward node selection algorithm introduces a communication overhead when a rebroadcasting node sends a list of forward nodes, along with the original broadcast packet, to all its neighbors. Assuming the network address of each selected forward node needs 2 bytes, Fig. 18 shows the average communication overhead of each forward node when the transmission range and the ZigBee network parameters vary. When the transmission range increases, every rebroadcast node will have more neighbors and more selected forward nodes, hence, the communication overhead increases with respect to the transmission range. But, it should be noted that the total communication overhead may not increase because the number of total forward nodes drops when the transmission range increases. For different network sizes, the communication overhead linearly increases when the network size increases. But, it increases slower when the number of children nm is larger.
A final note about the communication overhead of forward node selection algorithms is that a node does not need to send the list of selected forward nodes every time it rebroadcasts. If a node v has sent the list once and its neighbor table has not been changed since then, v does not need to send the same list of forward nodes when it is rebroadcasting later, because every neighbor u can save the status of “Forward” or “nonForward” in its own neighbor table entry for node v. In case a new neighbor u does not know its status for node v, it just rebroadcasts the packet like a selected forward node for v.
1570  IEEE TRANSACTIONS ON MOBILE COMPUTING,  VOL. 5,  NO. 11,  NOVEMBER 2006 

Fig. 14. The coverage time when the transmission radius is (a) 10m and (b) 55m.
DING ET AL.: TREEBASED DATA BROADCAST IN IEEE 802.15.4 AND ZIGBEE NETWORKS  1571 

selection algorithm AHBP for general ad hoc networks. The proposed broadcast algorithms are feasible in terms of both computation complexity and memory space complexity.
In the real ZigBee networks, in addition to minimizing the number of rebroadcast nodes, we need to consider the robustness of the broadcast algorithm, which means that the broadcast algorithm should allow some kind of redundancy in order to cover the whole network even if the 1hop neighbor information is not uptodate or the nodes are moving. The tradeoff between broadcast efficiency and reliability is studied in [25]. Future works include investigating the relationship between system performance and the ZigBee network parameters and the impact of dynamic network topology and power constraints on the broadcast algorithm.
Fig. 15. The number of rebroadcast nodes of (a) small and (b) large ZigBee networks.
1572  IEEE TRANSACTIONS ON MOBILE COMPUTING,  VOL. 5,  NO. 11,  NOVEMBER 2006 

Fig. 18. The communication overhead of the ZOS algorithm. (a) Different transmission range. (b) Different network size.
packet or have not received the packet either. We first APPENDIX B
tu 


DING ET AL.: TREEBASED DATA BROADCAST IN IEEE 802.15.4 AND ZIGBEE NETWORKS  1573 

and rebroadcast the packet. As a result, any node in TN2ðvÞ (actually, TNðNðvÞÞ) will be covered by either FðvÞ or v itself.
The same process is repeated by the selected forward nodes (which are not previously nonforward nodes). To apply mathematical induction, we assume that, at the end of step k � 2, every node in TNkðvÞ is covered. We next prove that TNkþ1ðvÞ will be covered after step k þ 1. In step k þ 1, we only need to consider any node x 2 TNkðvÞ � TNk�1ðvÞ. Since x has already been covered, there are two possible ways that x is covered in step k and earlier: 1) if x is covered by a forward node u in step k � 1 or before, that is, x 2 NðuÞ, then TNðxÞ � x has already been covered in step k or before by either the forward nodes selected by u or u itself, or 2) if x is covered in step k by a forward node f selected in step k � 1, f has selected its own forward nodes FðfÞ in step k that will rebroadcast in order to ontree cover TNðxÞ � x in step k þ 1. These two cases are both illustrated in Fig. 20, so, at the end of step k þ 1, TNðTNkðvÞ � TNk � 1ðvÞÞ will be covered. Knowing that TNðTNkðvÞ � TNk�1ðvÞÞ � TNkþ1ðvÞ � TNkðvÞ;
we prove that all nodes in TNkþ1ðvÞ will be covered at the end of step k þ 1. Finally, we have proven that, after each step, one more hop of tree neighbors will be covered. Since there are at most 2dm hops between any two nodes on a tree of maximal depth dm, the total number of steps will be at most 2dm. Since the network is connected, every node will eventually be covered and marked as either a forward node or a nonforward node.tu
[1] 





[2]  
[3]  ZigBee Alliance, Network Specification, Version 1.0, Dec. 2004.  
[4] 


[5] 



[6] 

[7]  



[8]  
with FðvÞ to its 1hop neighbors in NðvÞ. This transmission certainly covers all 1hop tree neighbors of v. The
nonforward nodes in NðvÞ � FðvÞ receive the broadcast packet from v, but drop it. Every node in FðvÞ, however, will run the ZOS algorithm, using sets S and C defined
1574 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 5, NO. 11, NOVEMBER 2006
[13] V. Chvatal, “A Greedy Heuristic for the SetCovering Problem,”
networks and impulse radio ultra wide band precision ranging and positioning. He has coauthored a bookchapter on UWB geolocation and has been the author or coauthor of more than 30 conference and
2000. journal articles. He has provided significant contributions to emerging












lytical modeling. He is a member of the IEEE.  
Wireless Networking and Computing, A. Boukerche and I. Chlamtac,
eds., CRC Press, 2005.


US patents pending. He is a student member of the IEEE.
. For more information on this or any other computing topic, please visit our Digital Library at www.computer.org/publications/dlib.