Modeling Aggregation Convergecast Scheduling Using Constraints

摘要

We consider the transmission scheduling problem for aggregation convergecast in wireless sensor networks. All transmissions required for a completed data collection to the sink node are to be scheduled in a single TDMA frame. Concurrent transmissions are possible within each TDMA slot as long as no collisions occur at the intended recipients of each transmission. We observe that previously proposed heuristics to solving the aggregation convergecast scheduling problem rely on a decomposition into two phases. The first phase is the construction of an aggregation tree, typically a Shortest Path Tree (SPT), and the second phase is sheduling transmissions. We express the constraints of the aggregation convergecast problem in a manner compatible with a constraint programming solver, and extract solutions for small sized instances. The, admittedly sparse, evidence suggests that the resultant aggregation trees is almost never SPTs and point to alternative considerations that would be useful when constructing aggregation convergecast scheduling heuristics.