WSEAS Transactions on Communications

Print ISSN: 1109-2742
E-ISSN: 2224-2864

Volume 16, 2017

Notice: As of 2014 and for the forthcoming years, the publication frequency/periodicity of WSEAS Journals is adapted to the 'continuously updated' model. What this means is that instead of being separated into issues, new papers will be added on a continuous basis, allowing a more regular flow and shorter publication times. The papers will appear in reverse order, therefore the most recent one will be on top.

Conflict-Free Data Aggregation in WSN with Unbounded Number of Channels

AUTHORS: Roman Plotnikov, Adil Erzin, Vyacheslav Zalyubovskiy

Download as PDF

ABSTRACT: We consider a problem of minimum length scheduling for conflict-free aggregation convergecast in wireless networks in a case when each element of a network uses its own frequency channel. This problem is equivalent to the well-known NP-hard problem of telephone broadcasting, since only the conflicts between the children of the same parent are taken into account. We propose a new integer programming formulation and compare it with the known one by running the CPLEX software package. Based on the results of a numerical experiment, we concluded that our formulation is more preferable in practice to solve the considered problem by CPLEX than the known one. We also propose a novel heuristic algorithm, based on a genetic algorithm and a local search metaheuristic. The simulation results demonstrate the high quality of the proposed algorithm compared to the best known approaches.

KEYWORDS: wireless sensor networks, convergecast, minimum latency, genetic local search, telephone broadcasting, simulation


[1] A.I. Erzin, N. Mladenovich, R.V. Plotnikov, Variable neighborhood search variants for Minpower symmetric connectivity problem, Computers & Operations Research 78, 2017, pp. 557-563.

[2] B. Malhotra, I. Nicolaidis, M.A. Nascimento, Aggregation convergecast scheduling in wireless sensor networks, Wireless Netw. 17, 2011, pp. 319-335.

[3] I. Demirkol, C. Ersoy, F. Alagoz, MAC protocols for wireless sensor networks: A survey, IEEE Comm. Mag. 44, 2006, pp. 115-121.

[4] P.-J. Wan, S.C.-H. Huang, L. Wang, et al., Minimum-latency aggregation scheduling in multihop wireless networks, Proc. ACM MOBIHOC, 2009, pp. 185-194.

[5] X. Chen, X. Hu, J. Zhu, Minimum data aggregation time problem in wireless sensor networks, Lecture Notes Comput. Sci. 3794, 2005, pp. 133-142.

[6] A. Erzin, A. Pyatkin, Convergecast scheduling problem in case of given aggregation tree: The complexity status and some special cases, IEEE Int. Symp. On Comm. Systems, Networks and DSP (CSNDSP), 7574007, 2016.

[7] S.C.-H. Huang, P.J. Wan, C.T. Vu, et al., Nearly constant approximation for data aggregation scheduling in wireless sensor networks, Proc. IEEE INFOCOM, 2007, pp. 366-372.

[8] P.J. Slater, E.J. Cockayne, S.T. Heditniemi, Information dissemination in trees, SIAM J. Comput. 10, 1981, pp. 692-701.

[9] C. Tian, H. Jiang, C. Wang, et al., Neither shortest path nor dominating set: Aggregation scheduling by greedy growing tree in multihop wireless sensor networks, IEEE Trans. Veh. Technol. 60, 2011, pp. 3462-3472.

[10]B. Krishnamachari, D. Estrin, S. Wicker, Impact of data aggregation in wireless sensor networks, IEEE ICDCS, 2002, pp. 575-578.

[11]R. Rajagopalan, P.K. Varshney, Dataaggregation techniques in sensor networks: a survey, IEEE Commun. Surveys & Tutorials 8, 2006, pp. 48-63.

[12]M. Bagaa, Y. Challa, A. Ksentini, et al., Data aggregation scheduling algorithms in wireless sensor networks: Solutions and challenges, IEEE Commun. Surveys & Tutorials, 16, 2014, pp. 1339-1368.

[13]X. Xu, X. Mao, A delay-efficient algorithm for data aggregation in multihop wireless sensor networks, IEEE Trans. Parallel Distr. Syst., 22, 2011, pp. 163-175.

[14]P.J. Wan, K.L. Alzoubi, O. Frieder, Distributed construction of connected dominating set in wireless ad hoc networks, IEEE INFOCOM, 2002, pp. 1597-1604.

[15]M. Bagaa, A. Derhab, N. Lasla, A. Ouadjaout, N. Badache, Semi-structured and unstructured data aggregation scheduling in wireless sensor networks, IEEE INFOCOM, 2012, pp. 2671- 2675.

[16]T.D. Nguyen, V. Zalyubovskiy, H. Choo, Efficient time latency of data aggregation based on neighboring dominators in WSNs, IEEE Globecom, 6133827, 2011

[17]P. Wang, Y. He, L. Huang, Near optimal scheduling of data aggregation in wireless sensor networks, Ad Hoc Networks, 11, 2013, pp. 1287- 1296.

[18]A. Ghosh, O.D. Incel, V.S.A. Kumar, et al., MCMLAS: Multi-channel minimum latency aggregation scheduling in wireless sensor networks, IEEE MASS, 2009, pp. 363-372.

[19]M.-S. Pan, Y.-H. Lee, Fast convergecast for lowduty-cycled multi-channel wireless sensor networks, Ad Hoc Netw, 40C, 2016, pp. 1-14.

[20]M. Middendorf, Minimum broadcast time is NPcomplete for 3-regular planar graphs and deadline 2, Information Processing Letters 46, 1993, pp. 281-287.

[21]C.-T. Cheng, K.T. Chi, F. Lau, A delay0aware data collection network structure for wireless sensor networks, IEEE Sensors J. 11, 2011, pp. 699-710.

[22]H.A. Harutyunyan, E. Maraachlian, On broadcasting in unicyclic graphs, J. of Combinatorial Optimization, 16, 2008, pp. 307- 322.

[23]M. Elkin, G. Kortsarz, Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem, STOC, 2002, pp. 438-447.

[24]R. Beier, J.F. Sibeyn, A powerful heuristic for telephone gossiping, SIROCCO, 2000, pp. 17-36.

[25]H.A. Harutyunyan, B. Shao, An efficient heuristic for broadcasting in networks, J. Parallel Distrib. Comput. 66, 2006, pp. 68-76.

[26]P. Gupta, P. Kumar, The capacity of wireless networks, IEEE Trans. On Information Theory IT-46, 2000, pp. 388-404.

[27]J. Hromkovic, R. Klasing, B. Monien, R. Peine, Dissemination of information in interconnection networks (broadcasting & gossiping), Combinatorial Network Theory, 1996, pp. 125- 212.

[28]E.W. Zegura, K. Calvert, S. Bhattacharjee, How to model an internetwork, IEEE INFOCOM, 1996, pp. 594-602

[29]S.N. Sivanandam, S.N. Deepa, Introduction to genetic algorithms (Springer, 2008)

[30]P. Hansen, N. Mladenovic, J.A.M. Perez, Variable neighbourhood search: methods and applications. Annals of Operations Research, 175, 2010, pp. 367–407.

[31]R. Plotnikov, A. Erzin, N. Mladenovic, Variable neighborhood search-based heuristics for minpower symmetric connectivity problem in wireless networks, LNCS 9869, 2016, pp. 220- 232.

[32]A. Medina, A. Lakhina, I. Matta, J. Byers, BRITE: An approach to universal topology generation, Proc. Ninth Int. Symp. on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), 2001 p. 346.

WSEAS Transactions on Communications, ISSN / E-ISSN: 1109-2742 / 2224-2864, Volume 16, 2017, Art. #23, pp. 192-202

Copyright © 2017 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0

Bulletin Board


The editorial board is accepting papers.

WSEAS Main Site