Abstract
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 p ≤ 1. All known aggregation schedules assumed ? = 1, and the best-known aggregation latency with p = 1 is 23R + Δ - 18 where R and Δ are the radius and maximum degree of the communication topology respectively. In this paper, we first construct three aggregations schedules with p = 1 of latency 15R + Δ - 4, 2R + O (logR) + Δ and (1 + O (logR/ <sup>3</sup> √ & r)) R + & Delta; respectively. Then, we obtain two aggregation schedules with p < 1 by expanding the first two aggregation schedules with p = 1. Both aggregation schedules with p > 1 have latency within constant factors of the minimum aggregation latency. Copyright 2009 ACM.