Aggregation Scheduling Algorithms in Wireless Sensor Networks

Authors: Min Kyung An

Abstract:

In Wireless Sensor Networks which consist of tiny wireless sensor nodes with limited battery power, one of the most fundamental applications is data aggregation which collects nearby environmental conditions and aggregates the data to a designated destination, called a sink node. Important issues concerning the data aggregation are time efficiency and energy consumption due to its limited energy, and therefore, the related problem, named Minimum Latency Aggregation Scheduling (MLAS), has been the focus of many researchers. Its objective is to compute the minimum latency schedule, that is, to compute a schedule with the minimum number of timeslots, such that the sink node can receive the aggregated data from all the other nodes without any collision or interference. For the problem, the two interference models, the graph model and the more realistic physical interference model known as Signal-to-Interference-Noise-Ratio (SINR), have been adopted with different power models, uniform-power and non-uniform power (with power control or without power control), and different antenna models, omni-directional antenna and directional antenna models. In this survey article, as the problem has proven to be NP-hard, we present and compare several state-of-the-art approximation algorithms in various models on the basis of latency as its performance measure.

Keywords: Data aggregation, convergecast, gathering, approximation, interference, omni-directional, 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.