Energy Efficient Scheduling for Cluster-Tree Wireless Sensor Networks With Time-Bounded Data Flows: Application to IEEE 802.15.4/ZigBee

Cluster scheduling and collision avoidance are crucial issues in large-scale cluster-tree Wireless Sensor Networks (WSNs). This paper presents a methodology that provides a Time-Division Cluster Scheduling (TDCS) mechanism based on the cyclic extension of Resource Constrained Project Scheduling with Temporal Constraints (RCPS/TC) problem for a cluster-tree WSN, assuming bounded communication errors. The objective is to meet all end-to-end deadlines of a predefined set of time-bounded data flows while minimizing the energy consumption of the nodes by setting the TDCS period as long as possible. Since each cluster is active only once during the period, the end-to-end delay of a given flow may span over several periods when there are the flows with opposite direction. The scheduling tool enables system designers to efficiently configure all required parameters of the IEEE 802.15.4/ZigBee beacon-enabled cluster-tree WSNs in the network design time. The performance evaluation of the scheduling tool shows that the problems with dozens of nodes can be solved while using optimal solvers.