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ÞÞ.