**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**30855

##### Aggregation Scheduling Algorithms in Wireless Sensor Networks

**Authors:**
Min Kyung An

**Abstract:**

**Keywords:**
Approximation,
data aggregation,
Interference,
omni-directional,
convergecast,
gathering,
directional

**Digital Object Identifier (DOI):**
doi.org/10.5281/zenodo.1130433

**References:**

[1] S. Roy, Y. C. Hu, D. Peroulis, and X.-Y. Li, “Minimum-Energy Broadcast Using Practical Directional Antennas in All-Wireless Networks,” in INFOCOM, 2006.

[2] P. Gupta and P. R. Kumar, “The Capacity of Wireless Networks,” IEEE Transctions on Information Theory, vol. 46, pp. 388 – 404, 2000.

[3] X.-Y. Li, X. Xu, S. Wang, S. Tang, G. Dai, J. Zhao, and Y. Qi, “Efficient Data Aggregation in Multi-hop Wireless Sensor Networks under Physical Interference Model,” in MASS, 2009, pp. 353–362.

[4] X. Chen, X. Hu, and J. Zhu, “Minimum Data Aggregation Time Problem in Wireless Sensor Networks,” in MSN, 2005, pp. 133–142.

[5] ——, “Data Gathering Schedule for Minimal Aggregation Time in Wireless Sensor Networks,” IJDSN, vol. 5, no. 4, pp. 321–337, 2009.

[6] D. Lichtenstein, “Planar Formulae and Their Uses,” SIAM J. Comput., vol. 11, no. 2, pp. 329–343, 1982.

[7] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, “Minimum Data Aggregation Schedule in Wireless Sensor Networks,” IJCA, vol. 18, no. 4, pp. 254–262, 2011.

[8] C. Lund and M. Yannakakis, “On the Hardness of Approximating Minimization Problems,” Journal of the ACM, vol. 41, no. 5, pp. 960 – 981, 1994.

[9] U. Feige, “A Threshold of ln(n) for Approximating Set Cover,” J. ACM, vol. 45, no. 4, pp. 634–652, 1998.

[10] N. X. Lam, M. K. An, D. T. Huynh, and T. N. Nguyen, “Minimum Latency Data Aggregation in the Physical Interference Model,” in MSWiM, 2011, pp. 93–102.

[11] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, “Minimum Latency Data Aggregation in the Physical Interference Model,” COMCOM, vol. 35, no. 18, pp. 2175–2186, 2012.

[12] R. Karp, “Reducibility among Combinatorial Problems,” in Complexity of Computer Computations. Plenum Press, 1972, pp. 85–103.

[13] N. X. Lam, T. Tran, M. K. An, and D. T. Huynh, “A Note on the Complexity of Minimum Latency Data Aggregation Scheduling with Uniform Power in Physical Interference Model,” Theoretical Computer Science, vol. 569, pp. 70–73, 2015.

[14] C. H. Papadimitriou and M. Yannakakis, “Optimization, Approximation, and Complexity Classes,” J. Comput. System Sci., vol. 43, no. 3, pp. 425–440, 1991.

[15] S. C. H. Huang, P.-J. Wan, C. T. Vu, Y. Li, and F. Yao, “Nearly Constant Approximation for Data Aggregation Scheduling,” in INFOCOM, 2007, pp. 6–12.

[16] B. Yu, J. Li, and Y. Li, “Distributed Data Aggregation Scheduling in Wireless Sensor Networks,” in INFOCOM, 2009, pp. 2159–2167.

[17] X. Xu, S. Wang, X. Mao, S. Tang, P. Xu, and X.-Y. Li, “Efficient Data Aggregation in Multi-hop WSNs,” in GLOBECOM, 2009, pp. 3916–3921.

[18] P.-J. Wan, S. C.-H. Huang, L. Wang, Z. Wan, and X. Jia, “Minimum-Latency Aggregation Scheduling in Multihop Wireless Networks,” in MOBIHOC, 2009, pp. 185–194.

[19] X. Xu, X. Y. Li, X. Mao, S. Tang, and S. Wang, “A Delay-Efficient Algorithm for Data Aggregation in Multihop Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 22, pp. 163–175, 2011.

[20] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, “Minimum Latency Aggregation Scheduling in Interference-Aware 3-Dimensional WSNs,” in ICWN, 2013.

[21] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson, Introduction to Algorithms, 3rd ed. McGraw-Hill Higher Education, 2009.

[22] P.-J. Wan, K. Alzoubi, and O. Frieder, “Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks,” in INFOCOM, 2002, pp. 159–1604.

[23] H. Li, Q. S. Hua, C. Wu, and F. C. M. Lau, “Minimum-Latency Aggregation Scheduling in Wireless Sensor Networks under Physical Interference Model,” in MSWiM, 2010, pp. 360–367.

[24] N. X. Lam, M. K. An, D. T. Huynh, and T. N. Nguyen, “Scheduling Problems in Interference-Aware Wireless Sensor Networks,” in ICNC, 2013, pp. 783–789.

[25] V. Annamalai, S. K. S. Gupta, and L. Schwiebert, “On Tree-based Convergecasting in Wireless Sensor Networks,” in WCNC, 2003, pp. 1942–1947.

[26] H. Du, X. Hu, and X. Jia, “Energy Efficient Routing and Scheduling for Real-time Data Aggregation In WSN,” COMCOM, vol. 29, no. 17, pp. 3527–3535, 2006.

[27] S. Khuller, B. Raghavachari, and N. E. Young, “Balancing Minimum Spanning Trees and Shortest-Path Trees,” Algorithmica, vol. 14, no. 4, pp. 305–321, 1995.

[28] H. Yousefi, M. Malekimajd, M. Ashouri, and A. Movaghar, “Fast Aggregation Scheduling in Wireless Sensor Networks,” IEEE Trans. Wireless Communications, vol. 14, no. 6, pp. 3402–3414, 2015.

[29] A. Kesselman and D. R. Kowalski, “Fast Distributed Algorithm for Convergecast in Ad Hoc Geometric Radio Networks,” Journal of Parallel and Distributed Computing, vol. 66, no. 4, pp. 578–585, 2006.

[30] N. Hobbs, Y. Wang, Q.-S. Hua, D. Yu, and F. C. M. Lau, “Deterministic Distributed Data Aggregation under the SINR Model,” in TAMC, 2012, pp. 385–399.

[31] H. Li, C. Wu, Q.-S. Hua, and F. C. Lau, “Latency-minimizing Data Aggregation in Wireless Sensor Networks under Physical Interference Model,” Ad Hoc Networks, vol. 12, pp. 52–68, 2014.

[32] M. M. Halld´orsson and P. Mitra, “Wireless Connectivity and Capacity,” in SODA, 2012, pp. 516–526.

[33] H. Liu, Z. Liu, D. Li, X. Lu, and H. Du, “Approximation Algorithms for Minimum Latency Data Aggregation in Wireless Sensor Networks with Directional Antenna,” Theor. Comput. Sci., vol. 497, pp. 139–153, 2013.