TIGRA: Timely Sensor Data Collection Using Distributed Graph Coloring

In this paper we present a protocol for sensor applications that require periodic collection of raw data reports from the entire network in a timely manner. We formulate the problem as an NP-hard graph coloring problem. We then present TIGRA - a distributed heuristic for graph coloring that takes into account application semantics and special characteristics of sensor networks. TIGRA ensures that no interference occurs and spatial channel reuse is maximized by assigning a specific time slot for each node to transmit. Although the end-to-end delay incurred by sensor data collection largely depends on specific topology, platform, and application, TIGRA provides a transmission schedule that guarantees near-optimal delay on sensor data collection.