Date

Computer Sciences ii The nature of many sensor applications as well as continuously changing sensor data often impose real-time requirements on wireless sensor network protocols. Due to numerous design constraints, such as limited bandwidth, memory and energy of sensor platforms, and packet collisions that can potentially lead to an unbounded number of retransmissions, timeliness techniques designed for real-time systems and real-time databases cannot be applied directly to wireless sensor networks. Our objective is to design a protocol for sensor applications that require periodic collection of raw data reports from the entire network in a timely manner. Existing real-time techniques designed for wireless sensor networks cannot be applied directly because of either fundamentally different timeliness objectives or unrealistic assumptions. We formulate the problem as a 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. Although the end-to-end delay incurred by sensor data collection largely depends on a specific topology, platform, and application, TIGRA provides a trans-mission schedule that guarantees a near-optimal delay on sensor data collection. To the best of our knowledge, this is the first effort to deterministically provide a bound for timely sensor data collection in a multihop wireless sensor network using a dis-tributed heuristic. TIGRA is instrumental to real-time applications in setting realistic time constraints. ii