|IEEE TRANSACTIONS ON MOBILE COMPUTING,||VOL. 5,||NO. 11,||
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 , , 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.
For information on obtaining reprints of this article, please send e-mail to: email@example.com, and reference IEEECS Log Number TMC-0319-1104.
1536-1233/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 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 , the authors improved the above algorithms by adaptively choosing the threshold as a function of the number of neighbors. Both simulation comparison  and theoretical analysis  have been conducted. These approaches are simple to implement, but they cannot guarantee coverage of the whole network .
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 . But, its solution can be approximated by a greedy algorithm  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
|DING ET AL.: TREE-BASED DATA BROADCAST IN IEEE 802.15.4 AND ZIGBEE NETWORKS||TABLE 1||1563|
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 . But, finding a minimum energy broadcast tree is NP-hard . Many heuristic protocols have been introduced , 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 , 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|