An exploration of aggregation convergecast scheduling

We consider the problem of aggregation convergecast scheduling as it applies to wireless networks. The solution to aggregation convergecast satisfies the aggregation process, expressed as precedence constraints, combined with the impact of the shared wireless medium, expressed as resource constraints. Both sets of constraints influence the routing and scheduling. We propose an aggregation tree construction suitable for aggregation convergecast that is a synthesis of a tree tailored to precedence constraints and another tree tailored to resource constraints. Additionally, we show that the scheduling component can be modeled as a mixed graph coloring problem. Specifically, the extended conflict graph is introduced, and through it, a mapping from aggregation convergecast to mixed graphs is described. In the mixed graph, arcs represent the precedence constraints and edges represent the resource constraints. The mixed graph chromatic number corresponds to the optimal schedule length. Bounds for the graph coloring are provided and a branch-and-bound strategy is subsequently developed from which we derive numerical results that allow a comparison against the current state-of-the-art heuristic.