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 
