ZigBee cluster tree formation for time-bounded data flows in one collision domain

We study one-collision domain ZigBee cluster-tree design problems to satisfy periodic time-bounded data flows. The formation of the cluster-tree topology can be seen as a bounded-degree-and-depth tree which is an NP-complete problem. The objective is to minimize the number of clusters such that all flows can take place and there exists a cluster schedule that meets the deadlines of the flows. For the resulting tree, the cluster schedule is required to be energy efficient, which can be achieved by maximizing the length of the schedule period, and consequently, increasing the lifetime of the network. We present a Cluster-Tree Formation and Energy-Efficient clusters scheduling algorithm, CFEFS, based on the Hungarian algorithm, the Maximum Matching algorithm and the Branch and Bound algorithm to tackle this design problem that integrates the cluster formation and the cluster scheduling in one problem.