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

REFERENCES:

[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.