Abstract
In the Convergecast Scheduling Problem, it is required to find in the communication graph an oriented spanning aggregation tree with a root in a base station and the arcs oriented to the root and to build a conflict-free min-length schedule for aggregating data along the arcs of the aggregation tree. This problem is NP-hard in general, however, if the communication graph is a unit square grid in each node of which there is a sensor and in which a data packet is transmitted along any edge during a one-time slot, the problem is polynomially solvable. In this paper, we consider a communication graph in the form of a square grid with rectangular obstacles impenetrable by the messages. In our previous paper, we proposed a polynomial algorithm for constructing a feasible schedule and intensive numerical experiment allowed us to make a hypothesis that the algorithm constructs an optimal solution. In this paper, we present a counterexample and prove that the proposed algorithm constructs a schedule of length at most one time round longer than the optimal schedule.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsReferences
Calinescu, G., Mandoiu, I.I., Zelikovsky, A.: Symmetric connectivity with minimum power consumption in radio networks. In: Baeza-Yates, R.A., Montanari, U., Santoro, N. (eds.) Proc. 2nd IFIP International Conference on Theoretical Computer Science. IFIP Conference Proceedings, vol. 223, pp. 119–130. Kluwer, Dordrecht (2002)
Cardei, M., Wu, J.: Energy-efficient coverage problems in wireless ad-hoc sensor networks. Comput. Commun. 29, 413–420 (2006)
Carle, J., Simplot, D.: Energy-efficient area monitoring by sensor networks. IEEE Comput. 37, 40–46 (2004)
Chen, X., Hu, X., Zhu, J.: Minimum data aggregation time problem in wireless sensor networks. In: Jia, X., Wu, J., He, Y. (eds.) MSN 2005. LNCS, vol. 3794, pp. 133–142. Springer, Heidelberg (2005). https://doi.org/10.1007/11599463_14
Erzin, A., Plotnikov, R.: Efficient algorithm for convergecast scheduling problem on a square grid with obstacles. In: Proceedings of the OPTIMA-2017, Petrovac, Montenegro. CEUR-WS, vol. 1987, pp. 187–193 (2017)
Erzin, A., Pyatkin, A.: Convergecast scheduling problem in case of given aggregation tree: the complexity status and some special cases. In: 10th International Symposium on Communication Systems, Networks and Digital Signal Processing, article 16. IEEE-Xplore, Prague (2016)
Erzin, A.: Solution of the convergecast scheduling problem on a square unit grid when the transmission range is 2. In: Battiti, R., Kvasov, D.E., Sergeyev, Y.D. (eds.) LION 2017. LNCS, vol. 10556, pp. 50–63. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69404-7_4
Erzin, A.I., Mladenovich, N., Plotnikov, R.V.: Variable neighborhood search variants for min-power symmetric connectivity problem. Comput. Oper. Res. 78, 557–563 (2017)
Gagnon, J., Narayanan, L.: Minimum latency aggregation scheduling in wireless sensor networks. In: Gao, J., Efrat, A., Fekete, S.P., Zhang, Y. (eds.) ALGOSENSORS 2014. LNCS, vol. 8847, pp. 152–168. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46018-4_10
Incel, O.D., Ghosh, A., Krishnamachari, B., Chintalapudi, K.: Fast data collection in tree-based wireless sensor networks. IEEE Trans. Mob. Comput. 11(1), 86–99 (2012)
Malhotra, B., Nikolaidis, I., Nascimento, M.A.: Aggregation convergecast scheduling in wireless sensor networks. Wirel. Netw. 17, 319–335 (2011)
Ghods, F., Yousefi, H., Mohammad, A., Hemmatyar, A., Movaghar, A.: MC-MLAS: multi-channel minimum latency aggregation scheduling in wireless sensor networks. Comput. Netw. 57, 3812–3825 (2013)
Tian, C.: Neither shortest path nor dominating set: aggregation scheduling by greedy growing tree in multihop wireless sensor networks. IEEE Trans. Veh. Ttchnolohy. 60(7), 3462–3472 (2011)
Wang, P., He, Y., Huang, L.: Near optimal scheduling of data aggregation in wireless sensor networks. Ad Hoc Netw. 11, 1287–1296 (2013)
Xu, X., Li, X.-Y., Mao, X., Tang, S., Wang, S.: A delay-efficient algorithm for data aggregation in multihop wireless sensor networks. IEEE Trans. Parallel Distrib. Syst. 22, 163–175 (2011)
Zalyubovskiy, V., Erzin, A., Astrakov, S., Choo, H.: Energy-efficient area coverage by sensors with adjustable ranges. Sensors 9, 2446–2460 (2009)
Acknowledgments
The research of A.I. Erzin is partly supported by the Russian Foundation for Basic Research, Projects 16-07-00552 and by the program of fundamental scientific researches of the SB RAS No. I.5.1. (project 0314-2016-0014). The research of R.V. Plotnikov is partly supported by the Russian Foundation for Basic Research, Project 16-37-60006.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Erzin, A., Plotnikov, R. (2019). The Accuracy of One Polynomial Algorithm for the Convergecast Scheduling Problem on a Square Grid with Rectangular Obstacles. In: Battiti, R., Brunato, M., Kotsireas, I., Pardalos, P. (eds) Learning and Intelligent Optimization. LION 12 2018. Lecture Notes in Computer Science(), vol 11353. Springer, Cham. https://doi.org/10.1007/978-3-030-05348-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-05348-2_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-05347-5
Online ISBN: 978-3-030-05348-2
eBook Packages: Computer ScienceComputer Science (R0)