Aggregation Scheduling Algorithms in Wireless Sensor Networks

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.

Authors:

• Min Kyung An

Keywords:

• Data aggregation
• convergecast
• gathering
• approximation
• interference
• omni-directional
• directional.

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.