An exploration of aggregation convergecast scheduling

Authors: Evandro de Souza, Ioanis Nikolaidis

Abstract:
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 branchand-bound strategy is subsequently developed from which we derive numerical results that allow a comparison against the current state-of-the-art heuristic.

Keywords:
Convergecat
Scheduling
Data aggregation
Wireless sensor networks
Mixed graphs
Minimum interference tree

Published in: Ad Hoc Networks (Volume 11, Issue 8, January 2013)

Publisher: Elsevier

ISSN Information: 1570-8705

An exploration of aggregation convergecast scheduling

Bình luận của bạn

*

*

*

*

 Captcha

Gửi bình luận nhập lại