The zigbee network characterized low data rate and low cost

Tree-Based Data Broadcast in

Index Terms—Broadcast, IEEE 802.15.4, ZigBee, ad hoc network.

Ç

working together to enable reliable, cost-effective, 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.

E-mail: dingg@ecn.purdue.edu.

For information on obtaining reprints of this article, please send e-mail to: tmc@computer.org, and reference IEEECS Log Number TMC-0319-1104.

1536-1233/06/$20.00 � 2006 IEEE

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 1-hop neighbors have already received the packet. In the latter algorithm, a node selects a subset of its 1-hop neighbors, called forward nodes, for forwarding, so as to cover all its 2-hop 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 NP-hard 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 algo-rithm rebroadcasts a packet only if the number of duplicated broadcast packets received during a waiting period is less than a threshold. The location-based 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 net-work information is available, the problem of selecting the minimum number of forward nodes is essentially the well-studied set cover problem, which is NP-hard [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 1-hop and 2-hop

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 NP-hard [22]. Many heuristic protocols have been introduced [23], which can approx-imate 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

information exchange. neighbors in TNðNðvÞÞ.

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 ON-TREE SELECTION ALGORITHM

Fig. 4. The optimal on-tree 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 On-Tree 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 capa-city. 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.

Fig. 6. The ZigBee on-tree 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.

The self-pruning 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 1-hop neighbors, instead of 1-hop tree neighbors, have been covered before it stops rebroadcasting. We omit

each broadcast; therefore, the resultant coverage time is only used for comparison.

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

1. the SBA algorithm [15], in which a node is self- pruned only if all its physical 1-hop neighbors are covered,
2. the AHBP algorithm [17], in which a greedy algorithm is employed to select a forward node

3. 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 redun-dancy, 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 transmis-sion range is fixed and the nodes are uniformly distributed, the number of duplicated packets is approximately propor-tional 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 self-pruning 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.

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.

In the above scenarios, we tested ZigBee networks of up to 300 nodes. A ZigBee network can actually support more

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.

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 rebroadcast-ing 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 transmis-sion range increases. For different network sizes, the communication overhead linearly increases when the net-work 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.

Fig. 14. The coverage time when the transmission radius is (a) 10m and (b) 55m.

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 1-hop neighbor information is not up-to-date or the nodes are moving. The trade-off between broadcast efficiency and reliability is studied in [25]. Future works include investi-gating 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.

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

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 on-tree 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

with FðvÞ to its 1-hop neighbors in NðvÞ. This transmis-sion certainly covers all 1-hop 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 Set-Covering Problem,”

networks and impulse radio ultra wide band precision ranging and positioning. He has coauthored a book-chapter on UWB geo-location and has been the author or coauthor of more than 30 conference and

2000. journal articles. He has provided significant contributions to emerging

Flooding Broadcast Message in Mobile Wireless Networks,” Proc.		Philip Orlik received the BE, MS, and PhD
		University of New York at Stony Brook. He
Computing, CRC Press, 2005.
		interests include wireless and optical commu-
S. Giordano, and I. Stojmenovic, eds., pp. 205-229, IEEE Press,
		lytical modeling. He is a member of the IEEE.

Wireless Networking and Computing, A. Boukerche and I. Chlamtac,

eds., CRC Press, 2005.

Gang Ding received the BE degree in control engineering from Tsinghua University, China. He is now a PhD student in electrical and computer engineering at Purdue University. His research interests include mobile wireless com-munications and networking, distributed sys-tems, and control theory. During his PhD study, Gang spent about one year working at Motorola Labs, Mitsubishi Electric Research Labs (MERL), and Intel Research. He has two

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.