Minimum-latency aggregation scheduling in multihop wireless networks

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.

REFERENCES

• 1: J. Chen, X.D. Hu, J.M. Zhu, Minimum data aggregation timeproblem in wireless sensor networks, Lecture Notes in Computer Science 3794, pp. 133--142, 2005.
• 2: Groemer, Über die Einlagerung von Kreisen in einenkonvexen Bereich. Math. Z., 73:285--294, 1960.
• 3: Gupta and P. Kumar, The capacity of wireless networks, IEEE Trans. Inform. Theory, vol. 46, pp. 388--404, Mar. 2000.
• 4: C.-H. Huang, P.-J. Wan, C.T. Vu, Y. Li, and F. Yao: Nearly Constant Approximation for Data Aggregation Scheduling in Wireless Sensor Networks, IEEE INFOCOM 2007.
• 5: David W. Matula , Leland L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM (JACM), v.30 n.3, p.417-427, July 1983 [doi>10.1145/2402.322385]
• 6: Peng-Jun Wan , Khaled M. Alzoubi , Ophir Frieder, Distributed construction of connected dominating set in wireless ad hoc networks, Mobile Networks and Applications, v.9 n.2, p.141-149, April 2004 [doi>10.1023/B:MONE.0000013625.87793.13]
• 7: Peng-Jun Wan , Chih-Wei Yi , Xiaohua Jia , Dongsoo Kim, Approximation algorithms for conflict-free channel assignment in wireless ad hoc networks: Research Articles, Wireless Communications & Mobile Computing, v.6 n.2, p.201-211, March 2006 [doi>10.1002/wcm.v6:2]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Theory

Keywords:
aggregation, approximation algorithms, communication latency