Data Collection with Bounded-Sized Messages in Wireless Sensor Networks

In this paper, we study the data collection problem in
Wireless Sensor Networks (WSNs) adopting the two interference
models: The graph model and the more realistic physical interference
model known as Signal-to-Interference-Noise-Ratio (SINR). The
main issue of the problem is to compute schedules with the minimum
number of timeslots, that is, to compute the minimum latency
schedules, such that data from every node can be collected without
any collision or interference to a sink node. While existing works
studied the problem with unit-sized and unbounded-sized message
models, we investigate the problem with the bounded-sized message
model, and introduce a constant factor approximation algorithm.
To the best known of our knowledge, our result is the first result
of the data collection problem with bounded-sized model in both
interference models.

Authors:

• Min Kyung An

Keywords:

• Data collection
• collision-free
• interference-free
• physical interference model
• SINR
• approximation
• bounded-sized message model
• wireless sensor networks
• WSN.

References:

[1] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, “Minimum
Latency Gossiping in Wireless Sensor Networks,” in Proceedings of
the International Conference on Wireless Networks (ICWN), 2012, pp.
406–412.
[2] M. K. An and H. Cho, “Efficient Data Collection in Interference-Aware
Wireless Sensor Networks,” Journal of Networks (JNW), 2015, to appear.
[3] P. Gupta and P. R. Kumar, “The Capacity of Wireless Networks,” IEEE
Trans. on Information Theory, vol. 46, pp. 388–404, 2000.
[4] C. Florens and R. J. McEliece, “Packet Distribution Algorithms for
Sensor Networks,” in INFOCOM, 2003.
[5] V. Bonifaci, P. Korteweg, A. Marchetti-Spaccamela, and L. Stougie,
“An Approximation Algorithm for the Wireless Gathering Problem,”
in SWAT, 2006, pp. 328–338.
[6] J.-C. Bermond, B. Li, N. Nisse, H. Rivano, and M.-L. Yu,
“Data Gathering and Personalized Broadcasting in Radio Grids with
Interferences,” INRIA, Research Report RR-8218, 2013.
[7] P.-J. Wan, L. Wang, and O. Frieder, “Fast Group Communications in
Multihop Wireless Networks Subject to Physical Interference,” in IEEE
6th Intern. Conf. on Mobile Adhoc and Sensor Systems (MASS), 2009,
pp. 526–533. [8] D. R. Kowalski, E. Nussbaum, M. Segal, and V. Milyeykovski,
“Scheduling Problems in Transportation Networks of Line Topology,”
Optimization Letters, vol. 8, no. 2, pp. 777–799, 2014.
[9] J.-C. Bermond, J. Galtier, R. Klasing, N. Morales, and S. Perennes,
“Hardness and Approximation of Gathering in Static Radio Networks,”
Parallel Processing Letters, vol. 16, no. 2, pp. 165–184, 2006.
[10] J.-C. Bermond, L. Gargano, S. Prennes, A. A. Rescigno, and
U. Vaccaro, “Optimal Time Data Gathering in Wireless Networks with
Multidirectional Antennas,” Theoretical Computer Science, vol. 509, pp.
122–139, 2013.
[11] 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.
[12] B. Yu, J. Li, and Y. Li, “Distributed Data Aggregation Scheduling in
Wireless Sensor Networks,” in INFOCOM, 2009, pp. 2159–2167.
[13] 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.
[14] 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 Trans. Parallel Distrib. Syst., vol. 22, pp. 163–175,
2011.
[15] 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.
[16] 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–101.
[17] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, “Minimum
Latency Data Aggregationg in the Physical Interference Model,”
Computer Communications, vol. 35, no. 18, pp. 2175–2186, 2012.
[18] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, “Minimum
Latency Aggregation Scheduling in Interference-Aware 3-Dimensional
WSNs,” in International Conference on Wireless Networks (ICWN),
2013.
[19] 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.
[20] 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.
[21] P. Wan, S. C. Huang, L. Wang, Z. Wan, and X. Jia, “Minimum-Latency
Aggregation Scheduling in MultihopWireless Networks,” in MOBIHOC,
2009, pp. 185–194.
[22] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, “Minimum
Data Aggregation Schedule in Wireless Sensor Networks,” International
Journal of Computers and Their Applications (IJCA), vol. 18, no. 4, pp.
254–262, 2011.
[23] S. C. Ergen and P. Varaiya, “TDMA Scheduling Algorithms for Wireless
Sensor Networks,” Wireless Networks, vol. 16, no. 4, pp. 985–997, 2010.
[24] X. Chen, X. Hu, and J. Zhu, “Minimum Data Aggregation Time Problem
in Wireless Sensor Networks,” in MSN, 2005, pp. 133–142.
[25] R. Bar-Yehuda, A. Israeli, and A. Itai, “Multiple Communication in
Multi-Hop Radio Networks,” SIAM Journal on Computing, vol. 22, pp.
875–887, 1993.
[26] M. Christersson, L. Gasieniec, and A. Lingas, “Gossiping with Bounded
Size Messages in Ad Hoc Radio Networks,” in ICALP, 2002, pp.
377–389.
[27] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction
to Algorithms, 3rd ed. MIT Press and McGraw-Hill, 2009.
[28] M. K. An, N. X. Lam, D. T. Huynh, and T. N. Nguyen, “Connectivity
in Wireless Sensor Networks in the SINR Model,” in MASCOTS, 2012,
pp. 145–152.