Minimum-latency aggregation scheduling in multihop wireless networks
Top Cited Papers
- 18 May 2009
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 185-194
- https://doi.org/10.1145/1530748.1530773
Abstract
[[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 ρ ≥ 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/3√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.[[fileno]]2030167030007[[department]]電機工程學Keywords
This publication has 6 references indexed in Scilit:
- Nearly Constant Approximation for Data Aggregation Scheduling in Wireless Sensor NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Minimum Data Aggregation Time Problem in Wireless Sensor NetworksLecture Notes in Computer Science, 2005
- Distributed Construction of Connected Dominating Set in Wireless Ad Hoc NetworksMobile Networks and Applications, 2004
- The capacity of wireless networksIEEE Transactions on Information Theory, 2000
- Smallest-last ordering and clustering and graph coloring algorithmsJournal of the ACM, 1983
- Über die Einlagerung von Kreisen in einen konvexen BereichMathematische Zeitschrift, 1960