Data Collection with Bounded-Sized Messages in Wireless Sensor Networks

Authors: Min Kyung An

Abstract:

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.

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

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

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.