Minimum-Latency Aggregation Scheduling in Multihop Wireless Networks

Minimum-latency aggregation schedule (MLAS) in synchronous multihop wireless networks seeks a shortest schedule for data aggregation subject to the interference constraint. In this paper, we study MLAS under the protocol interference model in which each node has a unit communication radius and an interference radius ρ ≥ 1. All known aggregation schedules assumed ρ = 1, and the best-known aggregation latency with ρ = 1 is 23R + Δ - 18 where R and Δ are the radius and maximum degree of the communication topology respectfully. In this paper, we first construct three aggregations schedules with ρ = 1 of latency 15R + Δ - 4, 2R + O (log R) + Δ and (1 + O (log R/³√R)) R + Δ respectively. Then, we obtain two aggregation schedules with ρ > 1 by expanding the first two aggregation schedules with ρ = 1. Both aggregation schedules with ρ > 1 have latency within constant factors of the minimum aggregation latency.